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

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

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

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

Определение

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

Позволять Икс и Y два непустых подмножества метрического пространства ${\displaystyle (M,d)}$. Определим их хаусдорфово расстояние ${\displaystyle d_{\mathrm {H} }(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\in X}d(x,y)\,\right\},\!}$

куда Как дела представляет супремум и инф то инфимум.

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

${\displaystyle d_{H}(X,Y)=\inf\{\varepsilon \geq 0\,;\ X\subseteq Y_{\varepsilon }{\text{ and }}Y\subseteq 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}$).

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

${\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|,}$^[1]

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

Замечание

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

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

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

${\displaystyle d(x,y):=|y-x|,\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\subseteq {\overline {Y_{\varepsilon }}}}$ и ${\displaystyle Y\subseteq {\overline {X_{\varepsilon }}}}$ ; в частности это верно, если ${\displaystyle X,Y}$ закрыты.

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

• В целом, ${\displaystyle d_{\mathrm {H} }(X,Y)}$ может быть бесконечным. Если оба Икс и Y находятся ограниченный, тогда ${\displaystyle d_{\mathrm {H} }(X,Y)}$ гарантированно будет конечным.
• ${\displaystyle d_{\mathrm {H} }(X,Y)=0}$ если и только если Икс и Y имеют такое же закрытие.
• За каждую точку Икс из M и любые непустые множества Y, Z из M: d(Икс,Y) ≤ d(Икс,Z) + d_ЧАС(Y,Z), куда d(Икс,Y) - расстояние между точкой Икс и ближайшая точка в наборе Y.
• | диаметр (Y)-диаметр(Икс)| ≤ 2 d_ЧАС(Икс,Y).^[4]
• Если пересечение Икс ∩ Y имеет непустую внутренность, то существует постоянная р > 0, такое, что каждый набор ИКС' чье расстояние Хаусдорфа от Икс меньше чем р также пересекает Y.^[5]
• На множестве всех подмножеств M, d_ЧАС дает расширенный псевдометрический.
• На съемочной площадке F(M) всех непустых компактных подмножеств M, d_ЧАС это метрика.
  • Если M является полный, то так F(M).^[6]
  • Если M компактно, то и F(M).
  • В топология из F(M) зависит только от топологии M, а не по метрике d.

Мотивация

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

• Определите функцию расстояния между любой точкой Икс из 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.

• Определите функцию расстояния между любыми двумя непустыми наборами Икс и 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.}$

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

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

Приложения

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

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

Мера различия двух форм дается выражением Расстояние Хаусдорфа с точностью до изометрии, обозначенный D_ЧАС. А именно пусть Икс и Y - две компактные фигуры в метрическом пространстве M (обычно Евклидово пространство ); тогда D_ЧАС(Икс,Y) - нижняя грань d_ЧАС(я(Икс),Y) вдоль всего изометрии я метрического пространства M себе. Это расстояние определяет, насколько далеко формы Икс и Y изометричны.

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

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

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

Рекомендации

1. Рокафеллар, Р. Тиррелл; Мокрый, Роджер Джей-Би (2005). Вариационный анализ. Springer-Verlag. п. 117. ISBN  3-540-62772-3.
2. Бирсан, Темистокле; Тиба, Дэн (2006), «Сто лет с момента введения Димитри Помпейу установленного расстояния», в Чераджоли, Франческа; Дончев, Асен; Futura, Hitoshi; Марти, Курт; Пандольфи, Лучано (ред.), Системное моделирование и оптимизация, 199, Бостон: Kluwer Academic Publishers, стр. 35–39, Дои:10.1007/0-387-33006-2_4, ISBN  978-0-387-32774-7, МИСТЕР  2249320
3. Мункрес, Джеймс (1999). Топология (2-е изд.). Prentice Hall. С. 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. Дои:10.1111/1467-8659.00236.

внешняя ссылка

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