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

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

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

Это расстояние впервые было введено Хаусдорфом в его книге 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}

^[3]

где

{\ 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}$

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

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|,

^[1]

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

Замечание [ править ]

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

X\subseteq Y_{\varepsilon }\ {\mbox{and}}\ Y\subseteq X_{\varepsilon }.

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

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

Брать

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

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

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

Свойства [ править ]

В общем, может быть бесконечно. Если оба X и Y имеют ограниченные , то гарантированно будет конечным. $d_{\mathrm {H} }(X,Y)$ $d_{\mathrm {H} }(X,Y)$
$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 ). ^[4]
Если пересечение X ∩ Y имеет непустую внутренность, то существует константа г > 0, таким образом, что каждое множество X ' , чье Хаусдорфово расстояние от X меньше г , пересекает Y . ^[5]
На множестве всех подмножеств M , d _H дает расширенную псевдометрику .
На множестве Р ( М ) всех непустых компактных подмножеств М , д _Н является метрикой.
- Если M является полным , то и F ( M ). ^[6]
- Если M компактно, то и F ( M ) компактно .
- Топологии из F ( M ) зависит только от топологии М , а не на метрике д .

Мотивация [ править ]

Определение расстояния Хаусдорфа может быть получено серией естественных расширений функции расстояния в базовом метрическом пространстве M следующим образом: ^[7] $d(x,y)$

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

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

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

Приложения [ править ]

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

Понятия, связанные с данным [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

^ a b Рокафеллар, Р. Тиррелл ; Влажный, Роджер JB (2005). Вариационный анализ . Springer-Verlag. п. 117. ISBN 3-540-62772-3.
^ Bîrsan, Temistocle; Тиба, Дэн (2006), «Сто лет с момента введения Димитри Помпейу установленного расстояния», в Чераджоли, Франческа; Дончев, Асен; Футура, Хитоши; Марти, Курт; Пандольфи, Лучано (ред.), Системное моделирование и оптимизация , 199 , Бостон: Kluwer Academic Publishers , стр. 35–39, DOI : 10.1007 / 0-387-33006-2_4 , ISBN 978-0-387-32774-7, Руководство по ремонту 2249320
^ Манкрес, Джеймс (1999). Топология (2-е изд.). Прентис Холл . С. 280–281. ISBN 0-13-181629-2.
^ Диаметр и расстояние Хаусдорфа , Math.SE
^ Расстояние Хаусдорфа и пересечение , Math.SE
^ Хенриксон, Джефф (1999). «Полнота и полная ограниченность метрики Хаусдорфа» (PDF) . Журнал математики для студентов MIT : 69–80. Архивировано из оригинального (PDF) 23 июня 2002 года.
^ Барнсли, Майкл (1993). Фракталы везде . Морган Кауфманн . стр. гл. II.6. ISBN 0-12-079069-6.
^ Сопоставление на основе Хаусдорфа
^ Cignoni, P .; Rocchini, C .; Скопиньо Р. (1998). «Метро: погрешность измерения на упрощенных поверхностях». Форум компьютерной графики . 17 (2): 167–174. CiteSeerX 10.1.1.95.9740 . DOI : 10.1111 / 1467-8659.00236 . S2CID 17783159 .

Внешние ссылки [ править ]

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

[rock-1] Рокафеллар, Р. Тиррелл ; Влажный, Роджер JB (2005). Вариационный анализ . Springer-Verlag. п. 117. ISBN 3-540-62772-3.

[2] Bîrsan, Temistocle; Тиба, Дэн (2006), «Сто лет с момента введения Димитри Помпейу установленного расстояния», в Чераджоли, Франческа; Дончев, Асен; Футура, Хитоши; Марти, Курт; Пандольфи, Лучано (ред.), Системное моделирование и оптимизация , 199 , Бостон: Kluwer Academic Publishers , стр. 35–39, DOI : 10.1007 / 0-387-33006-2_4 , ISBN 978-0-387-32774-7, Руководство по ремонту 2249320

[3] Манкрес, Джеймс (1999). Топология (2-е изд.). Прентис Холл . С. 280–281. ISBN 0-13-181629-2.

[4] Диаметр и расстояние Хаусдорфа , Math.SE

[5] Расстояние Хаусдорфа и пересечение , Math.SE

[6] Хенриксон, Джефф (1999). «Полнота и полная ограниченность метрики Хаусдорфа» (PDF) . Журнал математики для студентов MIT : 69–80. Архивировано из оригинального (PDF) 23 июня 2002 года.

[7] Барнсли, Майкл (1993). Фракталы везде . Морган Кауфманн . стр. гл. II.6. ISBN 0-12-079069-6.

[8] Сопоставление на основе Хаусдорфа

[9] Cignoni, P .; Rocchini, C .; Скопиньо Р. (1998). «Метро: погрешность измерения на упрощенных поверхностях». Форум компьютерной графики . 17 (2): 167–174. CiteSeerX 10.1.1.95.9740 . DOI : 10.1111 / 1467-8659.00236 . S2CID 17783159 .

[1]