Введение
Расстояние между двумя подмножествами метрического пространства
В математике расстояние Хаусдорфа, или метрика Хаусдорфа, также называемое расстоянием Помпею — Хаусдорфа, измеряет, насколько далеки друг от друга два подмножества метрического пространства. Оно превращает множество непустых компактных подмножеств метрического пространства в метрическое пространство само по себе. Оно названо в честь Феликса Хаусдорфа и Димитрия Помпею. Неформально, два множества близки в смысле расстояния Хаусдорфа, если каждая точка одного из множеств находится близко к некоторой точке другого множества. Расстояние Хаусдорфа – это максимальное расстояние, на которое кому-либо может потребоваться переместиться, если противник выбирает точку в одном из двух множеств, откуда этот человек должен добраться до другого множества. Иными словами, это наибольшее из всех расстояний от точки одного множества до ближайшей точки другого множества. Это расстояние было впервые введено Хаусдорфом в его книге «Grundzüge der Mengenlehre», впервые опубликованной в 1914 году, хотя очень близкий аналог появился в докторской диссертации Мориса Фреше в 1906 году, в его исследовании пространства всех непрерывных кривых из .
In mathematics, the Hausdorff distance, or Hausdorff metric, also called Pompeiu–Hausdorff distance, measures how far two subsets of a metric space are from each other. It turns the set of non empty compact subsets of a metric space into a metric space in its own right. It is named after Felix Hausdorff and Dimitrie Pompeiu. Informally, two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set. The Hausdorff distance is the longest distance someone can be forced to travel by an adversary who chooses a point in one of the two sets, from where they then must travel to the other set. In other words, it is the greatest of all the distances from a point in one set to the closest point in the other set. This distance was first introduced by Hausdorff in his book Grundzüge der Mengenlehre, first published in 1914, although a very close relative appeared in the doctoral thesis of Maurice Fréchet in 1906, in his study of the space of all continuous curves from .
Приложения
В компьютерном зрении расстояние Хаусдорфа может использоваться для поиска заданного шаблона в произвольном целевом изображении. Шаблон и изображение часто предварительно обрабатываются с помощью детектора границ, что приводит к созданию бинарного изображения. Далее каждая единица (активированная точка) в бинарном изображении шаблона рассматривается как точка в множестве, представляющем "форму" шаблона. Аналогично, область бинарного целевого изображения рассматривается как множество точек. Затем алгоритм пытается минимизировать расстояние Хаусдорфа между шаблоном и некоторой областью целевого изображения. Область в целевом изображении с минимальным расстоянием Хаусдорфа до шаблона может считаться наилучшим кандидатом для определения местоположения шаблона в целевом изображении. В компьютерной графике расстояние Хаусдорфа используется для измерения разницы между двумя различными представлениями одного и того же 3D-объекта, особенно при генерации уровней детализации для эффективного отображения сложных 3D-моделей. Если – это поверхность Земли, а – поверхность суши Земли, то, найдя точку Немо, мы видим, что составляет примерно 2704,8 км.
Связанные понятия
Мера различия двух фигур задается расстоянием Хаусдорфа с точностью до изометрии, обозначаемым DH. А именно, пусть X и Y – две компактные фигуры в метрическом пространстве M (обычно евклидовом пространстве); тогда DH(X,Y) – это инфимум dH(I(X),Y) по всем изометриям I метрического пространства M на себя. Это расстояние измеряет, насколько формы X и Y далеки от изометричности. Сходимость Громова — Хаусдорфа – связанная идея: измерение расстояния между двумя метрическими пространствами M и N путем взятия инфимума по всем изометрическим вложениям M и N в некоторое общее метрическое пространство L.