В математике , то расстояние Хаусдорфа , или метрика Хаусдорфа , которая также называется Помпейя-Хаусдорфово расстоянием , [1] [2] меры , как далеко два подмножества из в метрическом пространстве друг от друга. Он превращает множество непустых компактных подмножеств метрического пространства в собственное метрическое пространство. Он назван в честь Феликса Хаусдорфа и Димитри Помпейу .
Неформально, два набора близки по расстоянию Хаусдорфа, если каждая точка любого набора близка к некоторой точке другого набора. Расстояние Хаусдорфа - это самое длинное расстояние, которое вы можете заставить пройти противник, который выбирает точку в одном из двух наборов, откуда вы затем должны отправиться в другой набор. Другими словами, это наибольшее из всех расстояний от точки в одном наборе до ближайшей точки в другом наборе.
Это расстояние впервые было введено Хаусдорфом в его книге Grundzüge der Mengenlehre , впервые опубликованной в 1914 году, хотя очень близкий родственник появился в докторской диссертации Мориса Фреше в 1906 году, когда он изучал пространство всех непрерывных кривых из.
Определение
Пусть X и Y два непустых подмножества метрического пространства. Определим их хаусдорфово расстояние от
где sup представляет супремум , inf - нижнюю грань , а где определяет расстояние от точки к подмножеству .
Эквивалентно,
где
то есть набор всех точек внутри из набора (иногда называемый - откорма или обобщенный шар радиуса вокруг ).
Эквивалентно,
это, , где это расстояние от точки к набору .
Замечание
Это неверно для произвольных подмножеств что подразумевает
Например, рассмотрим метрическое пространство действительных чисел с обычной метрикой индуцированный абсолютной величиной,
Брать
потом . тем не мение так как , но .
Но это правда, что а также ; в частности это верно, если закрыты.
Характеристики
- В общем, может быть бесконечным. Если оба X и Y имеют ограниченные , то гарантированно будет конечным.
- тогда и только тогда, когда 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 следующим образом: [7]
- Определите функцию расстояния между любой точкой x из M и любым непустым множеством Y из M следующим образом:
- Например, d (1, {3,6}) = 2 и d (7, {3,6}) = 1.
- Определите функцию расстояния между любыми двумя непустыми наборами X и Y из M следующим образом:
- Например,
- Если 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 . Однако мы можем создать метрику, определив расстояние Хаусдорфа следующим образом:
Приложения
В компьютерном зрении расстояние Хаусдорфа можно использовать для поиска заданного шаблона в произвольном целевом изображении. Шаблон и изображение часто предварительно обрабатываются с помощью детектора края, что дает двоичное изображение . Затем каждая 1 (активированная) точка в двоичном изображении шаблона рассматривается как точка в наборе, «форме» шаблона. Точно так же область двоичного целевого изображения обрабатывается как набор точек. Затем алгоритм пытается минимизировать расстояние Хаусдорфа между шаблоном и некоторой областью целевого изображения. Область на целевом изображении с минимальным расстоянием Хаусдорфа до шаблона может считаться лучшим кандидатом для размещения шаблона в целевом объекте. [8] В компьютерной графике расстояние Хаусдорфа используется для измерения разницы между двумя разными представлениями одного и того же трехмерного объекта [9], особенно при генерации уровня детализации для эффективного отображения сложных трехмерных моделей.
Связанные понятия
Мера для несходства двух форм задаются хаусдорфовым расстоянием до изометрии , обозначенного D Н . А именно, пусть X и Y - две компактные фигуры в метрическом пространстве M (обычно евклидовом пространстве ); тогда D H ( X , Y ) - точная нижняя грань d H ( I ( X ), Y ) по всем изометриям I метрического пространства M самому себе. Это расстояние измеряет, насколько формы X и Y отличаются от изометричности.
Сходимость Громова-Хаусдорфа является связанной идеей: мы измеряем расстояние двух метрических пространств M и N , взяв инфимума вдоль всех изометрических вложений а также в некоторую общую метрике пространства L .
Смотрите также
Рекомендации
- ^ a b Рокафеллар, Р. Тиррелл ; Влажный, Роджер JB (2005). Вариационный анализ . Springer-Verlag. п. 117. ISBN 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) . Журнал математики для студентов 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]