Расстояние Фреше - Fréchet distance

В математике расстояние Фреше - это мера сходства между кривыми, которая учитывает расположение и порядок точек вдоль кривых. Он назван в честь Мориса Фреше .

Интуитивное определение

Представьте себе человека, идущего по конечной изогнутой дорожке, выгуливая свою собаку на поводке, при этом собака проходит отдельный конечный изогнутый путь. Каждый может изменять свою скорость, чтобы поводок оставался слабым, но ни один из них не может двигаться назад. Расстояние Фреше между двумя изгибами - это длина самого короткого поводка, достаточная для того, чтобы оба прошли свой путь от начала до конца. Обратите внимание, что определение симметрично относительно двух кривых - расстояние Фреше было бы таким же, если бы собака выгуливала своего хозяина.

Формальное определение

Позвольте быть метрическое пространство . Кривая в является непрерывной картой от единичного интервала в , то есть . Перепараметризация из является непрерывным, не убывает , сюръекция . ${\ displaystyle S}$ ${\ displaystyle A}$${\ displaystyle S}$ ${\ displaystyle S}$${\ displaystyle A: [0,1] \ rightarrow S}$ ${\ displaystyle \ alpha}$${\ displaystyle [0,1]}$ ${\ Displaystyle \ альфа: [0,1] \ rightarrow [0,1]}$

Позвольте и быть двумя заданными кривыми в . Затем Фреше расстояние между и определяются как нижняя грань по всем заменам и из максимума за все расстояния в между и . В математических обозначениях расстояние Фреше равно ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle S}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle [0,1]}$${\ Displaystyle т \ в [0,1]}$${\ displaystyle S}$${\ Displaystyle А (\ альфа (т))}$${\ Displaystyle В (\ бета (т))}$${\ Displaystyle F (А, В)}$

${\ Displaystyle F (A, B) = \ Inf _ {\ alpha, \ beta} \, \, \ max _ {t \ in [0,1]} \, \, {\ Bigg \ {} d {\ Большой (} A (\ alpha (t)), \, B (\ beta (t)) {\ Big)} {\ Bigg \}}}$

где - функция расстояния от . ${\ displaystyle d}$${\ displaystyle S}$

Неформально мы можем думать о параметре как о «времени». Тогда это позиция собаки и позиция владельца собаки в данный момент (или наоборот). Длина поводка между ними по времени - это расстояние между и . Взять нижнюю границу по всем возможным перепараметризациям соответствует выбору прогулки по заданным дорожкам, где максимальная длина поводка минимизирована. Ограничение, а не убывает , означает , что ни собака , ни его владелец может возвращаться назад. ${\ displaystyle t}$${\ Displaystyle А (\ альфа (т))}$${\ Displaystyle В (\ бета (т))}$${\ displaystyle t}$${\ displaystyle t}$${\ Displaystyle А (\ альфа (т))}$${\ Displaystyle В (\ бета (т))}$${\ displaystyle [0,1]}$${\ displaystyle \ alpha}$${\ displaystyle \ beta}$

Метрика Фреше учитывает поток двух кривых, потому что пары точек, расстояние которых влияет на расстояние Фреше, непрерывно перемещаются вдоль своих соответствующих кривых. Это делает расстояние Фреше лучшей мерой сходства для кривых, чем альтернативы, такие как расстояние Хаусдорфа , для произвольных наборов точек. Две кривые могут иметь небольшое расстояние Хаусдорфа, но большое расстояние Фреше.

Расстояние Фреше и его варианты находят применение в нескольких задачах, от морфинга и распознавания почерка до выравнивания структуры белка . Альт и Годау были первыми, кто описал алгоритм с полиномиальным временем для вычисления расстояния Фреше между двумя многоугольными кривыми в евклидовом пространстве , основанный на принципе параметрического поиска . Время работы их алгоритма - для двух ломаных кривых с m и n сегментами. ${\ Displaystyle О (мн \ cdot \ журнал (мн))}$

Диаграмма свободного пространства

Диаграмма свободного пространства красной и синей кривых. В отличие от определения в тексте, в котором для обеих кривых используется интервал параметра [0,1], в этом примере кривые параметризованы длиной дуги.

Важным инструментом для вычисления расстояния Фреше двух кривых является диаграмма свободного пространства, введенная Альт и Годо. Диаграмма свободного пространства между двумя кривыми для заданного порогового значения расстояния ε представляет собой двумерную область в пространстве параметров, которая состоит из всех пар точек на двух кривых на расстоянии не более ε:

${\ Displaystyle D _ {\ varepsilon} (A, B): = \ {\, (\ alpha, \ beta) \ in [0,1] ^ {2} \ mid d (A (\ alpha), B (\ бета)) \ leq \ varepsilon \, \}}$

Расстояние Фреше не превосходит ε тогда и только тогда, когда диаграмма свободного пространства содержит путь из нижнего левого угла в верхний правый угол, который монотонен как в горизонтальном, так и в вертикальном направлении. ${\ Displaystyle F (А, В)}$${\ Displaystyle D _ {\ varepsilon} (А, В)}$

Как расстояние между распределениями вероятностей (оценка FID)

Помимо измерения расстояний между кривыми, расстояние Фреше также можно использовать для измерения разницы между распределениями вероятностей . Для двух многомерных гауссовских распределений со средними и ковариационными матрицами и расстояние Фреше между этими распределениями равно ${\ displaystyle \ mu _ {X}}$${\ displaystyle \ mu _ {Y}}$${\ displaystyle \ Sigma _ {X}}$${\ displaystyle \ Sigma _ {Y}}$

${\ displaystyle d ^ {2} = | \ mu _ {X} - \ mu _ {Y} | ^ {2} + tr (\ Sigma _ {X} + \ Sigma _ {Y} -2 (\ Sigma _ {X} \ Sigma _ {Y}) ^ {1/2})}$.

Это расстояние является основой для начального расстояния Фреше (FID), которое используется для сравнения изображений, созданных генеративной враждебной сетью, с реальными изображениями, которые использовались для обучения.

Варианты

Слабый Фреш расстояние представляет собой вариант классического Фреше расстояния без требования о том , что конечные точки двигаются монотонно вдоль соответствующих кривых - собака и ее владелец разрешено возвратиться , чтобы держать поводок между ними коротким. Альт и Годо описывают более простой алгоритм вычисления слабого расстояния Фреше между многоугольными кривыми, основанный на вычислении минимаксных путей в связанном сеточном графе .

Дискретный Фреше расстояние , которая также называется расстоянием муфты , является приближением Fréchet метрики для ломаных, определяемого Eiter и Mannila. Дискретное расстояние Фреше учитывает только положения поводка, когда его концы расположены в вершинах двух многоугольных кривых, а не внутри края. Эта специальная структура позволяет вычислять дискретное расстояние Фреше за полиномиальное время с помощью простого алгоритма динамического программирования.

Когда две кривые вложены в метрическое пространство, отличное от евклидова, например, многогранный рельеф или некоторое евклидово пространство с препятствиями, расстояние между двумя точками на кривых наиболее естественно определяется как длина кратчайшего пути между ними. Поводок должен быть геодезическим, соединяющим его конечные точки. Результирующая метрика между кривыми называется геодезическим расстоянием Фреше . Кук и Венк описывают алгоритм с полиномиальным временем для вычисления геодезического расстояния Фреше между двумя многоугольными кривыми в простом многоугольнике .

Если мы дополнительно потребуем, чтобы поводок непрерывно перемещался в окружающем метрическом пространстве, то мы получим понятие гомотопического расстояния Фреше между двумя кривыми. Поводок не может прерывисто переключаться из одного положения в другое - в частности, поводок не может перепрыгивать через препятствия и может проноситься через гору на местности, только если он достаточно длинный. Движение поводка описывает гомотопию между двумя кривыми. Chambers et al. описать алгоритм с полиномиальным временем для вычисления гомотопического расстояния Фреше между многоугольными кривыми в евклидовой плоскости с препятствиями.

Примеры

Расстояние Фреше между двумя концентрическими кругами радиуса и, соответственно, составляет. Самый длинный поводок требуется, когда владелец стоит на месте, а собака движется на противоположную сторону круга ( ), и самый короткий поводок, когда и владелец, и собака идут с постоянным углом. скорость по окружности ( ). ${\ displaystyle r_ {1}}$${\ displaystyle r_ {2}}$${\ displaystyle | r_ {1} -r_ {2} |.}$${\ displaystyle r_ {1} + r_ {2}}$${\ displaystyle | r_ {1} -r_ {2} |}$

Приложения

Расстояние Фреше использовалось для изучения визуальной иерархии , принципа графического дизайна.

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

• Начальное расстояние Фреше

использованная литература

дальнейшее чтение

• де Берг, Марк, «Анализ траекторий движущихся объектов», « Вычислительная геометрия», Two Selected Topics (PDF) , стр. 11–75.
• Аронов, Борис ; Хар-Пелед, Сариэль; Кнауэр, Кристиан; Ван, Юсу ; Венк, Карола (2006), "Расстояние Фреше для кривых, повторение", Proc. 14-й Европейский симпозиум по алгоритмам (PDF) , Lecture Notes in Computer Science, 4168 , Springer-Verlag, pp. 52–63, arXiv : 1504.07685 , doi : 10.1007 / 11841036_8 , заархивировано из оригинала (PDF) 12.06.2010.
• Альт, Гельмут; Бучин, Майке (2010), «Можем ли мы вычислить сходство между поверхностями?», Дискретная и вычислительная геометрия , 43 : 78–99, arXiv : cs.CG/0703011 , doi : 10.1007 / s00454-009-9152-8.