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

редактировать

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

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

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

Содержание

1 Определение
- 1.1 Примечание
2 Свойства
3 Мотивация
4 Приложения
5 Понятия, связанные с данным
6 См. Также
7 Ссылки
8 Внешние ссылки

Определение

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

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

d H (X, Y) = макс {sup x ∈ X inf y ∈ Y d (x, y), sup y ∈ Y inf x ∈ X d (x, y)}, {\ displaystyle d _ {\ mathrm {H}} (X, Y) = \ max \ left \ {\, \ sup _ {x \ in X} \ inf _ {y \ in Y} d (x, y), \, \ sup _ {y \ in Y} \ inf _ {x \ в X} d (x, y) \, \ right \}, \!}

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

где sup представляет верхнюю грань, а inf точную нижнюю границу.

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

d H (X, Y) = inf {ε ≥ 0; Икс ⊆ Y ε и Y ⊆ X ε}, {\ displaystyle d_ {H} (X, Y) = \ inf \ {\ varepsilon \ geq 0 \,; \ X \ substeq Y _ {\ varepsilon} {\ text {и }} Y \ substeq X _ {\ varepsilon} \}, \ quad}

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

где

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

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

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

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

d H (X, Y) = sup w ∈ M | inf x ∈ X d (w, x) - inf y ∈ Y d (w, y) | = sup w ∈ X ∪ Y | inf x ∈ X d (w, x) - inf y ∈ Y d (w, y) |, {\ 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 (w, y) \ right |,}

{\ displa ystyle 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 ( w, y) \ справа |,}

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

Замечание

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

X ⊆ Y ε и Y ⊆ X ε. {\ displaystyle X \ substeq Y _ {\ varepsilon} \ {\ t_dv {and}} \ Y \ substeq X _ {\ varepsilon}.}

{\ displaystyle X \ substeq Y _ {\ varepsilon} \ {\ t_dv {and}} \ Y \ subteq X _ {\ varepsilon}.}

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

d (x, y): = | у - х |, x, y ∈ R. {\ displaystyle d (x, y): = | yx |, \ quad x, y \ in \ mathbb {R}.}

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

Возьмите

X: = (0, 1] и Y: = [- 1, 0). {\ displaystyle X: = (0,1] \ quad {\ t_dv {and}} \ quad Y: = [- 1,0).}

{\ displa ystyle X: = (0,1] \ quad {\ t_dv {and}} \ quad Y: = [- 1,0).}

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

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

Свойства

В общем, $d H (X, Y) {\ displaystyle d _ {\ mathrm {H}} (X, Y)}$ ${\ displaystyle d _ {\ mathrm {H}} (X, Y)}$ может быть бесконечным. Если и X, и Y ограничены, то $d H (X, Y) {\ displaystyle d _ {\ mathrm {H}} (X, Y)}$ ${\ displaystyle d _ {\ mathrm {H}} (X, Y)}$ гарантировано быть конечным.
$d H (X, Y) = 0 {\ displaystyle d _ {\ mathrm {H}} (X, Y) = 0}$ ${\ 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) - расстояние между точкой x и ближайшей точкой в множестве Y.
| диаметр (Y) -диаметр (X) | ≤ 2 d H (X, Y).
Если пересечение X ∩ Y имеет непустую внутренность, то существует константа r>0, такая, что каждое множество X ′ расстояние Хаусдорфа от X меньше r также пересекает Y.
На множестве всех подмножеств M, d H дает расширенный псевдометрический.
На множестве F (M) всех непустых компактных подмножеств M, d H является метрикой.
- Если M полное, то F (M) тоже.
- Если M компактно, то и F (M) тоже.
- Топология F (M) зависит только от топологии M, а не от метрики d.

Мотивация

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

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

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

{\ 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 следующим образом:

d (X, Y) = sup {d (x, Y) ∣ x ∈ X}. {\ displaystyle d (X, Y) = \ sup \ {d (x, Y) \ mid x \ in X \}. \}

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

Например,

d ({1, 7}, {3, 6}) = sup {d (1, {3, 6}), d (7, {3, 6})} = sup {d (1, 3), d (7, 6)} = 2. { \ textstyle d (\ {1,7 \}, \ {3,6 \}) = \ sup \ {d (1, \ {3,6 \}), d (7, \ {3,6 \}) \} = \ sup \ {d (1,3), d (7,6) \} = 2.}

{\ 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 наследует свойство неравенства треугольника от функции расстояния в M. В его нынешнем виде d (X, Y) не является метрикой, потому что d (X, Y) не всегда симметричен, а d (X, Y) = 0 не означает, что X = Y (это означает, что $X ⊆ Y {\ displaystyle X \ substeq Y}$ $X \ substeq Y$ ). Например, d ({1,3,6,7}, {3,6}) = 2, но d ({3,6}, {1,3,6,7}) = 0. Однако мы можем создать метрику, задав для расстояния Хаусдорфа значение:

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

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

Приложения

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

Понятия, связанные с данным

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

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

См. Также

Ссылки

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

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