Расстояние Хаусдорфа - Hausdorff distance

В математике , то расстояние Хаусдорфа , или метрика Хаусдорфа , называемое также Помпейя-расстоянием Хаусдорф мера , как далеко два подмножества из в метрическом пространстве друг от друга. Он превращает множество непустых компактных подмножеств метрического пространства в собственное метрическое пространство. Он назван в честь Феликса Хаусдорфа и Димитри Помпейу .

Неформально, два набора близки по расстоянию Хаусдорфа, если каждая точка любого набора близка к некоторой точке другого набора. Расстояние Хаусдорфа - это самое большое расстояние, на которое вы можете быть вынуждены пройти противник, который выбирает точку в одном из двух наборов, откуда вы затем должны отправиться в другой набор. Другими словами, это наибольшее из всех расстояний от точки в одном наборе до ближайшей точки в другом наборе.

Это расстояние впервые было введено Хаусдорфом в его книге Grundzüge der Mengenlehre , впервые опубликованной в 1914 году, хотя очень близкий родственник появился в докторской диссертации Мориса Фреше в 1906 году в его исследовании пространства всех непрерывных кривых из . ${\ Displaystyle [0,1] \ к \ mathbb {R} ^ {3}}$

Определение

Компоненты вычисления расстояния Хаусдорфа между зеленой линией X и синей линией Y .

Пусть X и Y два непустых подмножества метрического пространства . Определим их хаусдорфово расстояние как ${\ displaystyle (M, d)}$${\ displaystyle d _ {\ mathrm {H}} (X, Y)}$

${\ Displaystyle d _ {\ mathrm {H}} (X, Y) = \ max \ left \ {\, \ sup _ {x \ in X} d (x, Y), \, \ sup _ {y \ in Y} d (X, y) \, \ right \}, \!}$

где sup представляет собой верхнюю грань , inf - нижнюю грань , а где количественно определяет расстояние от точки до подмножества . ${\ displaystyle d (a, B) = \ inf _ {b \ in B} d (a, b)}$${\ displaystyle a \ in X}$${\ Displaystyle B \ substeq X}$

Эквивалентно,

${\ displaystyle d_ {H} (X, Y) = \ inf \ {\ varepsilon \ geq 0 \,; \ X \ substeq Y _ {\ varepsilon} {\ text {and}} Y \ substeq X _ {\ varepsilon} \ }, \ quad}$

куда

${\ displaystyle X _ {\ varepsilon}: = \ bigcup _ {x \ in X} \ {z \ in M ​​\,; \ d (z, x) \ leq \ varepsilon \},}$

то есть, набор всех точек в пределах набора (иногда называемый -уплотнением или обобщенным шаром радиуса вокруг ). ${\ displaystyle \ varepsilon}$${\ displaystyle X}$${\ displaystyle \ varepsilon}$${\ displaystyle X}$${\ displaystyle \ varepsilon}$${\ displaystyle X}$

Эквивалентно,

${\ displaystyle d_ {H} (X, Y) = \ sup _ {w \ in M} \ left | \ inf _ {x \ in X} d (w, x) - \ inf _ {y \ in Y} d (w, y) \ right | = \ sup _ {w \ in X \ cup Y} \ left | \ inf _ {x \ in X} d (w, x) - \ inf _ {y \ in Y} d (ш, у) \ право |,}$

то есть, где - расстояние от точки до множества . ${\ displaystyle d _ {\ mathrm {H}} (X, Y) = \ sup _ {w \ in M} | d (w, X) -d (w, Y) |}$${\ Displaystyle д (ш, Х)}$${\ displaystyle w}$${\ displaystyle X}$

Замечание

Это неверно для произвольных подмножеств , из которых следует ${\ Displaystyle X, Y \ подмножество M}$${\ Displaystyle d _ {\ mathrm {H}} (X, Y) = \ varepsilon}$

${\ displaystyle X \ substeq Y _ {\ varepsilon} \ {\ mbox {and}} \ Y \ substeq X _ {\ varepsilon}.}$

Например, рассмотрим метрическое пространство действительных чисел с обычной метрикой, индуцированной модулем: ${\ Displaystyle \ mathbb {R}}$${\ displaystyle d}$

${\ Displaystyle d (x, y): = | yx |, \ quad x, y \ in \ mathbb {R}.}$

Брать

${\ Displaystyle X: = (0,1] \ quad {\ mbox {and}} \ quad Y: = [- 1,0).}$

Тогда . Однако потому что , но . ${\ Displaystyle d _ {\ mathrm {H}} (X, Y) = 1 \}$${\ Displaystyle X \ nsubseteq Y_ {1}}$${\ Displaystyle Y_ {1} = [- 2,1) \}$${\ displaystyle 1 \ in X}$

Но это правда, что и  ; в частности это верно, если закрыты. ${\ Displaystyle X \ substeq {\ overline {Y _ {\ varepsilon}}}}$${\ Displaystyle Y \ substeq {\ overline {X _ {\ varepsilon}}}}$${\ displaystyle X, Y}$

Характеристики

• В общем, может быть бесконечно. Если оба X и Y имеют ограниченные , то гарантированно будет конечным.${\ displaystyle d _ {\ mathrm {H}} (X, Y)}$${\ displaystyle d _ {\ mathrm {H}} (X, Y)}$
• ${\ displaystyle d _ {\ mathrm {H}} (X, Y) = 0}$тогда и только тогда, когда X и Y имеют одинаковое замыкание.
• Для любой точки x из M и любых непустых множеств Y , Z из M : d ( x , Y ) ≤ d ( x , Z ) + d _H ( Y , Z ), где d ( x , Y ) - расстояние между точкой х и ближайшей точкой в множестве Y .
• | диаметр ( Y ) -диаметр ( X ) | ≤ 2 d _H ( X , Y ).
• Если пересечение X  ∩  Y имеет непустую внутренность, то существует константа г  > 0, таким образом, что каждое множество X ' , чье Хаусдорфово расстояние от X меньше г , пересекает Y .
• На множестве всех подмножеств M , d _H дает расширенную псевдометрику .
• На множестве Р ( М ) всех непустых компактных подмножеств М , д _Н является метрикой.
  • Если M является полным , то и F ( M ).
  • Если M компактно, то и F ( M ) компактно .
  • Топологии из F ( M ) зависит только от топологии М , а не на метрике д .

Мотивация

Определение расстояния Хаусдорфа может быть получено серией естественных расширений функции расстояния в базовом метрическом пространстве M следующим образом: ${\ Displaystyle д (х, у)}$

• Определите функцию расстояния между любой точкой x из M и любым непустым множеством Y из M следующим образом:

${\ displaystyle d (x, Y) = \ inf \ {d (x, y) \ mid y \ in Y \}. \}$

Например, d (1, {3,6}) = 2 и d (7, {3,6}) = 1.

• Определите (не обязательно симметричную) функцию «расстояния» между любыми двумя непустыми наборами X и Y из M следующим образом:

${\ Displaystyle d (X, Y) = \ sup \ {d (x, Y) \ mid x \ in X \}. \}$

Например, ${\ textstyle d (\ {1,7 \}, \ {3,6 \}) = \ sup \ {d (1, \ {3,6 \}), d (7, \ {3,6 \} ) \} = \ sup \ {d (1,3), d (7,6) \} = 2.}$

• Если X и Y компактны, то d ( X , Y ) будет конечным; d ( X , X ) = 0; и d наследует неравенство треугольника свойство из функции расстояния в М . В существующем виде d ( X , Y ) не является метрикой, потому что d ( X , Y ) не всегда симметрично, а d ( X , Y ) = 0 не означает, что X = Y (из этого следует, что ). Например, d ({1,3,6,7}, {3,6}) = 2 , но d ({3,6}, {1,3,6,7}) = 0 . Однако мы можем создать метрику, определив расстояние Хаусдорфа следующим образом:${\ Displaystyle X \ substeq Y}$

${\ Displaystyle d _ {\ mathrm {H}} (X, Y) = \ max \ {d (X, Y), d (Y, X) \} \ ,.}$

Приложения

В компьютерном зрении расстояние Хаусдорфа можно использовать для поиска заданного шаблона в произвольном целевом изображении. Шаблон и изображение часто предварительно обрабатываются с помощью детектора края, что дает двоичное изображение . Затем каждая 1 (активированная) точка в двоичном изображении шаблона рассматривается как точка в наборе, «форме» шаблона. Точно так же область двоичного целевого изображения обрабатывается как набор точек. Затем алгоритм пытается минимизировать расстояние Хаусдорфа между шаблоном и некоторой областью целевого изображения. Область на целевом изображении с минимальным расстоянием Хаусдорфа до шаблона может считаться лучшим кандидатом для размещения шаблона в целевом объекте. В компьютерной графике расстояние Хаусдорфа используется для измерения разницы между двумя разными представлениями одного и того же трехмерного объекта, особенно при генерации уровня детализации для эффективного отображения сложных трехмерных моделей.

Связанные понятия

Мера для несходства двух форм задаются хаусдорфовым расстоянием до изометрии , обозначенного D _Н . А именно, пусть X и Y - две компактные фигуры в метрическом пространстве M (обычно евклидовом пространстве ); тогда D _H ( X , Y ) - точная нижняя грань d _H ( I ( X ), Y ) по всем изометриям I метрического пространства M самому себе. Это расстояние измеряет, насколько формы X и Y отличаются от изометричности.

Сходимость Громова-Хаусдорфа является связанной идеей: мы измеряем расстояние двух метрических пространств M и N , взяв инфимума вдоль всех изометрических вложений и в некоторой общей метрики пространства L . ${\ displaystyle d _ {\ mathrm {H}} (I (M), J (N))}$${\ Displaystyle I \ двоеточие M \ to L}$${\ Displaystyle J \ двоеточие N \ to L}$

Смотрите также

• Конвергенция Вейсмана
• Конвергенция Куратовского
• Геминепрерывность
• Расстояние Фреше

использованная литература

внешние ссылки

• Хаусдорфово расстояние между выпуклыми многоугольниками .
• Использование MeshLab для измерения разницы между двумя поверхностями Краткое руководство о том, как вычислить и визуализировать расстояние Хаусдорфа между двумя триангулированными трехмерными поверхностями с помощью инструмента MeshLab с открытым исходным кодом .
• Код MATLAB для расстояния Хаусдорфа: [1]