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

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

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

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

Определение

Позволять $(M,d)$ быть метрическим пространством . Для каждой пары непустых подмножеств $X\subset M$ и $Y\subset M$ , расстояние Хаусдорфа между $X$ и $Y$ определяется как

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

где $\operatorname {sup}$ представляет оператор супремума , $\operatorname {inf}$ оператор инфимума , и где $d(a,B):=\inf _{b\in B}d(a,b)$ определяет расстояние от точки $a\in X$ к подмножеству $B\subseteq X$ .

Эквивалентное определение выглядит следующим образом. ^[3] Для каждого набора $X\subset M,$ позволять $X_{\varepsilon }:=\bigcup _{x\in X}\{z\in M\mid d(z,x)\leq \varepsilon \},$ который представляет собой набор всех точек внутри $\varepsilon$ из набора $X$ (иногда называемый $\varepsilon$ -откорм $X$ или обобщенный шар радиуса $\varepsilon$ вокруг $X$ ).Тогда расстояние Хаусдорфа между $X$ и $Y$ определяется как $d_{H}(X,Y):=\inf\{\varepsilon \geq 0\mid X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq X_{\varepsilon }\}.$

Эквивалентно, ^[1] ${\begin{aligned}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|\\&=\sup _{w\in M}|d(w,X)-d(w,Y)|,\end{aligned}}$ где $d(w,X):=\inf _{x\in X}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$ закрыты.

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

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

Мотивация

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

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

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

Приложения

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

Если $X$ это поверхность Земли и $Y$ — это поверхность суши Земли, то, найдя точку Немо , мы увидим $d_{H}(X,Y)$ составляет около 2704,8 км.

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Рокафеллар, Р. Тиррелл ; Мокрый, Роджер Дж.Б. (2005). Вариационный анализ . Спрингер-Верлаг. п. 117. ИСБН 3-540-62772-3 .
^ Бирсан, Темистокл; Тиба, Дэн (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) . Математический журнал бакалавриата Массачусетского технологического института : 69–80. Архивировано из оригинала (PDF) 23 июня 2002 г.
^ Барнсли, Майкл (1993). Фракталы повсюду . Морган Кауфманн . пп. гл. II.6. ISBN 0-12-079069-6 .
^ Чиньони, П.; Роккини, К.; Скопиньо, Р. (1998). «Метро: ошибка измерения на упрощенных поверхностях». Форум компьютерной графики . 17 (2): 167–174. CiteSeerX 10.1.1.95.9740 . дои : 10.1111/1467-8659.00236 . S2CID 17783159 .

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

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

[rock-1] Jump up to: ^а ^б Рокафеллар, Р. Тиррелл ; Мокрый, Роджер Дж.Б. (2005). Вариационный анализ . Спрингер-Верлаг. п. 117. ИСБН 3-540-62772-3 .

[2] Бирсан, Темистокл; Тиба, Дэн (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) . Математический журнал бакалавриата Массачусетского технологического института : 69–80. Архивировано из оригинала (PDF) 23 июня 2002 г.

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]