В математике расстояние Фреше - это мера сходства между кривыми, которая учитывает расположение и порядок точек вдоль кривых. Он назван в честь Мориса Фреше .
Интуитивное определение
Представьте себе человека, идущего по конечной изогнутой дорожке, выгуливая свою собаку на поводке, при этом собака проходит отдельный конечный изогнутый путь. Каждый может изменять свою скорость, чтобы поводок оставался слабым, но ни один из них не может двигаться назад. Расстояние Фреше между двумя изгибами - это длина самого короткого поводка, достаточная для того, чтобы оба могли пройти свой путь от старта до финиша. Обратите внимание, что определение симметрично относительно двух кривых - расстояние Фреше было бы таким же, если бы собака выгуливала своего хозяина.
Формальное определение
Позволять - метрическое пространство . кривая в является непрерывной карты от единичного интервала в, т.е. . перепараметризация из является непрерывным, не убывает , сюръекция .
Позволять а также быть двумя заданными кривыми в . Тогда расстояние Фреше между а также определяется как нижняя грань по всем параметризациям а также из максимума по всем расстояния в между а также . В математических обозначениях расстояние Фреше является
где является функцией расстояния от.
Неформально мы можем думать о параметре как «время». Потом, позиция собаки и положение хозяина собаки во время (или наоборот). Длина поводка между ними во времени это расстояние между а также . Взяв нижнюю грань по всем возможным перепараметризациямсоответствует выбору прогулки по заданным дорожкам, где максимальная длина поводка минимальна. Ограничение, что а также быть неубывающим означает, что ни собака, ни ее владелец не могут отступить.
Метрика Фреше учитывает поток двух кривых, потому что пары точек, расстояние которых влияет на расстояние Фреше, непрерывно перемещаются вдоль своих соответствующих кривых. Это делает расстояние Фреше лучшей мерой сходства для кривых, чем альтернативы, такие как расстояние Хаусдорфа , для произвольных наборов точек. Две кривые могут иметь небольшое расстояние Хаусдорфа, но большое расстояние Фреше.
Расстояние Фреше и его варианты находят применение в нескольких задачах, от морфинга [1] и распознавания почерка [2] до выравнивания структуры белка . [3] Альт и Годау [4] были первыми, кто описал алгоритм с полиномиальным временем для вычисления расстояния Фреше между двумя многоугольными кривыми в евклидовом пространстве , основанный на принципе параметрического поиска . Время работы их алгоритмадля двух ломаных с m и n отрезками.
Диаграмма свободного пространства
Важным инструментом для вычисления расстояния Фреше двух кривых является диаграмма свободного пространства, введенная Альт и Годо. [4] Диаграмма свободного пространства между двумя кривыми для заданного порогового значения расстояния ε представляет собой двумерную область в пространстве параметров, которая состоит из всех пар точек на двух кривых на расстоянии не более ε:
Расстояние Фреше не превосходит ε тогда и только тогда, когда диаграмма свободного пространства содержит путь из левого нижнего угла в правый верхний, который монотонен как в горизонтальном, так и в вертикальном направлении.
Как расстояние между распределениями вероятностей (оценка FID)
Помимо измерения расстояний между кривыми, расстояние Фреше также можно использовать для измерения разницы между распределениями вероятностей . Для двух многомерных гауссовских распределений со средними а также и ковариационные матрицы а также , расстояние Фреше между этими распределениями равно [5]
.
Это расстояние является основой для начального расстояния Фреше (FID), которое используется для сравнения изображений, созданных генеративной враждебной сетью, с реальными изображениями, которые использовались для обучения.
Варианты
Слабый Фреш расстояние представляет собой вариант классического Фреше расстояния без требования о том , что конечные точки двигаются монотонно вдоль соответствующих кривых - собака и ее владелец разрешено возвратиться , чтобы держать поводок между ними коротким. Альт и Годау [4] описывают более простой алгоритм вычисления слабого расстояния Фреше между многоугольными кривыми, основанный на вычислении минимаксных путей в связанном сеточном графе .
Дискретный Фреше расстояние , которая также называется расстоянием муфты , является приближением Fréchet метрики для ломаных, определяемого Eiter и Mannila. [6] Дискретное расстояние Фреше учитывает только положения поводка, когда его концы расположены в вершинах двух многоугольных кривых, и никогда не внутри края. Эта специальная структура позволяет вычислять дискретное расстояние Фреше за полиномиальное время с помощью простого алгоритма динамического программирования.
Когда две кривые вложены в метрическое пространство, отличное от евклидова, такое как многогранный ландшафт или некоторое евклидово пространство с препятствиями, расстояние между двумя точками на кривых наиболее естественно определяется как длина кратчайшего пути между ними. Поводок должен быть геодезическим, соединяющим его конечные точки. Результирующая метрика между кривыми называется геодезическим расстоянием Фреше . [1] [7] [8] Кук и Венк [7] описывают алгоритм с полиномиальным временем вычисления геодезического расстояния Фреше между двумя многоугольными кривыми в простом многоугольнике .
Если мы дополнительно потребуем, чтобы поводок непрерывно двигался в окружающем метрическом пространстве, то мы получим понятие гомотопического расстояния Фреше [9] между двумя кривыми. Поводок не может прерывисто переключаться из одного положения в другое - в частности, поводок не может перепрыгивать через препятствия и может проноситься через гору на местности, только если он достаточно длинный. Движение поводка описывает гомотопию между двумя кривыми. Chambers et al. [9] описывают алгоритм с полиномиальным временем для вычисления гомотопического расстояния Фреше между многоугольными кривыми на евклидовой плоскости с препятствиями.
Примеры
Расстояние Фреше между двумя концентрическими окружностями радиуса а также соответственно Самый длинный поводок требуется, когда хозяин стоит на месте, а собака едет на противоположную сторону круга (), и самый короткий поводок, когда и владелец, и собака ходят с постоянной угловой скоростью по окружности ().
Приложения
Расстояние Фреше использовалось для изучения визуальной иерархии , принципа графического дизайна. [10]
Рекомендации
- ^ а б Эфрат, Алон; Гибас, Леонидас Дж .; Хар-Пелед, Сариэль ; Митчелл, Джозеф SB ; Murali, ТМ (2002), "Новые меры сходства между полилинией с приложениями к морфингу и многоугольник подметания" (PDF) , дискретная и вычислительная геометрия , 28 (4): 535-569, DOI : 10.1007 / s00454-002-2886-1.
- ^ Sriraghavendra, R .; Karthik, K .; Bhattacharyya, Chiranjib (2007), "Подход, основанный на расстоянии Фреше для поиска рукописных документов в Интернете", Proc. 9-я Международная конференция по анализу и распознаванию документов (ICDAR '07) , стр. 461–465, DOI : 10.1109 / ICDAR.2007.121.
- ^ Минхуэй, Цзян; Инь, Сюй; Бинхай, Чжу (2008), "Протеин структура-структура выравнивания с дискретным Фреше расстояния" (PDF) , Журнал биоинформатики и вычислительной биологии , 6 (1): 51-64, DOI : 10,1142 / S0219720008003278 , PMID 18324745.
- ^ а б в Альт, Гельмут; Годау, Майкл (1995), «Вычисление расстояния Фреше между двумя полигональными кривыми» (PDF) , Международный журнал вычислительной геометрии и приложений , 5 (1-2): 75-91, DOI : 10,1142 / S0218195995000064.
- ^ Доусон, Д. С.; Ландау Б. В. (1 сентября 1982 г.). «Расстояние Фреше между многомерными нормальными распределениями». Журнал многомерного анализа . 12 (3): 450–455. DOI : 10.1016 / 0047-259X (82) 90077-X . ISSN 0047-259X .
- ^ Эйтер, Томас; Маннила, Хейкки (1994), Вычисление дискретного расстояния Фреше (PDF) , Tech. Отчет CD-TR 94/64, Лаборатория экспертных систем им. Христиана Доплера, Технический университет Вены, Австрия.
- ^ а б Кук, Атлас Ф., IV; Венк, Карола (2008), Геодезическое расстояние Фреше с многоугольными препятствиями (PDF) , Tech. Отчет CS-TR-2008-0010, Техасский университет в Сан-Антонио.
- ^ Махешвари, Анил; Yi, Jiehua (2005), "О вычислении расстояния Фреше двух путей на выпуклом многограннике", Proc. 21-й Европейский семинар по вычислительной геометрии (PDF) , стр. 41–44.
- ^ а б Чемберс, Эрин Вульф; Колен де Вердьер, Эрик; Эриксон, Джефф; Лазар, Сильвен; Лазарь, Франциск; Thite, Shripad (2009), «Гомотопическое расстояние Фреше между кривыми, или Прогулка с собакой в лесу за полиномиальное время» (PDF) , Computational Geometry: Theory and Applications , 43 (3): 295–311, doi : 10.1016 / j .comgeo.2009.02.008.
- ^ Урано, Йоко; Куросу, Аарон; Хензельман-Петрусек Григорий; Тодоров, Александр (2021). «Визуальная иерархия связана с впечатлениями от хорошего дизайна» . Семинар CHI'21 по движениям глаз как интерфейсу к когнитивному состоянию : 1–9. DOI : 10.31234 / osf.io / hksf9 .
дальнейшее чтение
- де Берг, Марк, «Анализ траекторий движущихся объектов», « Вычислительная геометрия», 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.