如何理解弗雷歇距離

1、如何理解弗雷歇距離(Fréchet distance) 如何理解弗雷歇距離（Fréchet distance） 作者：陳郁蔥 定義 設(shè)二元組 ?,? 是一個度量空間，其中 ? 是 ? 上的度量函數(shù)，在無需指明度量函數(shù)的情況下，我們把度量空間簡稱為 ?。 定義1 如果定義在單位區(qū)間 0,1 上的映射 ?: 0,1 ? 是連續(xù)映射，則稱 ? 為 ? 上的連續(xù)曲線。 定義2 如果從單位區(qū)間到其自身的映射 ?，即函數(shù) ?: 0,1 0,1 ，滿足如下三個條件：1 ? 是連續(xù)的，2 ? 是非降的，即對于任意 ?,? 0,1 ，且 ?，都有 ? ? ? ? 成3 ? 是滿射，則稱函數(shù)

2、? 為單位區(qū)間 0,1 的重參數(shù)化函數(shù)，且此時有 ? 0 =0，立， ? 1 =1。特別地，當 ? 為恒等函數(shù) ? ? =? 時，稱 ? 為平凡重參數(shù)化函數(shù)，否則，稱 ? 為非平凡重參數(shù)化函數(shù)。顯然，單位區(qū)間的重參數(shù)化函數(shù)有無窮多個。 有了以上設(shè)定，我們來正式定義度量空間中兩條曲線之間的弗雷歇距離。 定義3 設(shè) ? 和 ? 是 ? 上的兩條連續(xù)曲線，即 ?: 0,1 ?，?: 0,1 ?；又設(shè) ? 和 ? 是單位區(qū)間的兩個重參數(shù)化函數(shù)，即 ?: 0,1 0,1 ，?: 0,1 0,1 ；則曲線 ? 與曲線 ? 的弗雷歇距離 ? ?,? 定義為： ? ?,? =infmax ? ? ? ? ,?

3、 ? ? ?,? 0,1 其中 ? 是 ? 上的度量函數(shù)。 幾個引理 為了更好地理解弗雷歇距離，我們先引入如下幾個概念與命題。 定義4 對于度量空間 ? 上的任一連續(xù)曲線 ?: 0,1 ?，我們稱 ? 0 為該曲線的起點，稱 ? 1 為該曲線的終點；如果參數(shù) ?,? 0,1 ，且 ?，則稱 ? ? 在 ? ? 的前面，也稱 ? ? 在 ? ? 的后面。 命題1 連續(xù)曲線上某點是起點，當且僅當它在所有點的前面；連續(xù)曲線上某點是終點，當且僅當它在所有點的后面。 證明：命題顯然為真，證略。? 定義5 設(shè)度量空間 ? 上有一連續(xù)曲線 ?: 0,1 ?，單位區(qū)間上有一重參數(shù)化函數(shù) ?: 0,1 0,1

4、，我們把復合映射 ?°?: 0,1 ? 稱為曲線 ? 在重參數(shù)化函數(shù) ? 作用下的重參數(shù)化曲線 ?，即 ?=?°。 命題2 度量空間中連續(xù)曲線的重參數(shù)化曲線不改變原曲線上各點的前后關(guān)系。 證明：設(shè)連續(xù)曲線為 ?，任取參數(shù) ?,? 0,1 ，且 ?，則 ? ? 在 ? ? 的前面。又設(shè)重參數(shù)化函數(shù)為 ?，則重參數(shù)化曲線為 ?=?°?，故參數(shù) ? 與 ? 在 ? 上對應(yīng)的點分別為 ? ? = ?°? ? =? ? ? 與 ? ? = ?°? ? =? ? ? ，又由重參數(shù)化函數(shù)的性質(zhì)可知，? ? ,? ? 0,1 ，且 ? ? ? ? ，故 ? ?

5、 ? 在 ? ? ? 的前面，即 ? ? 在 ? ? 的前面，因此參數(shù) ? 與 ? 在 ? 與 ? 上對應(yīng)兩點之間的前后關(guān)系保持一致，又因為參數(shù) ?,? 是任取的，所以重參數(shù)化曲線不改變原曲線上各點的前后關(guān)系，證畢。? 推論 度量空間中連續(xù)曲線的重參數(shù)化曲線不改變原曲線的起點與終點。 證明：由命題1知，原曲線的起點在原曲線上所有點的前面，故由命題2可知，位于重參數(shù)化曲線上與原曲線起點參數(shù)對應(yīng)的點也在重參數(shù)化曲線上所有點的前面，再由命題1即可知該點就是重參數(shù)化曲線的起點，因此連續(xù)曲線的重參數(shù)化曲線不改變原曲線的起點；終點的證明同理；證畢。? 理解弗雷歇距離 下面我們回到定義3中對弗雷歇距離的定義

6、中來，為了更加直觀的理解，我們用圖1中二維歐氏平面上的兩條曲線來解釋弗雷歇距離。 圖1 二維歐氏平面上兩條曲線之間的弗雷歇距離的計算示意圖 思想 按照定義3，曲線 ? 與曲線 ? 的弗雷歇距離 ? ?,? 定義為： ? ?,? =infmax ? ? ? ? ,? ? ? ?,? 0,1 其中 ? 是 ? 上的度量函數(shù)。 在 ? ?,? 的計算公式中，先固定最外層的 ? 與 ?，也就是對每一個選定的 ? 與 ? 的組合，計算下式： ?,? ?,? =max ? ? ? ? ,? ? ? ? 0,1 上式中 ?,?,?,?,? 均視為被固定住的已知函數(shù)，只將 ? 當作變量。此時，由于變量 ? 將

7、在單位區(qū)間 0,1 內(nèi)遍歷所有連續(xù)取值（無窮多個），為了便于直觀理解，我們將該區(qū)間作離散化處理，即在該區(qū)間采樣若干個點來作分析，然后通過逐漸增加采樣點的個數(shù)來提高精度，最后通過求極限的思想來理解兩條曲線的弗雷歇距離。 數(shù)列在原曲線上的點列 +1在單位區(qū)間 0,1 中任意抽取由 ?+2 個互不相同的數(shù)構(gòu)成單調(diào)遞增數(shù)列 ? ?使得 ?=0， ?0=0，?+1=1，且滿足 ?<?+1。 +1將 ? ? ?=0 與 ? ? ?=0 分別稱為數(shù)列 ? ?=0 分別在曲線 ? 與 ? 上的點列。其?+1?+1 中，? ?0 （即? 0 ）與 ? ?+1 （即? 1 ）分別是曲線 ? 的起點與

8、終點，? ?0 （即? 0 ）與 ? ?+1 （即? 1 ）分別是曲線 ? 的起點與終點。 ? ? ?=0 與 ? ? ?=0 在圖1中由黑點標出。 分別連接 ? ? ?=0 與 ? ? ?=0 相互對應(yīng)的點，即 ? ? 與 ? ? 連接，即圖1中兩曲線之間的黑色連接線，? ? 與 ? ? 之間的距離為 ? ? ? ,? ? 。 ?+1?+1?+1?+1 數(shù)列在重參數(shù)化曲線上的點列 現(xiàn)在引入曲線的重參數(shù)化函數(shù)，設(shè)作用于曲線 ?,? 的重參數(shù)化函數(shù)分別是 ?,?，它們對應(yīng)的重參數(shù)化曲線分別為 ?,?，則 ?=?°?，?=?°?。 類似地，將 ? ? ?=0（即 ? ? ? ?

9、+1?+1 ?=0） 與 ? ? ?=0（即 ? ? ? ?+1?+1 ?=0） 分別稱 +1?+1為數(shù)列 ? ?=0 分別在重參數(shù)化曲線 ? 與 ? 上的點列，或分別稱為數(shù)列 ? ?=0 分別 在重參數(shù)化函數(shù)分別是 ? 與 ? 的曲線 ? 與 ? 上的點列。兩曲線的重參數(shù)化點列 ? ? ?=0 與 ? ? ?=0 在圖1中由紅點標出。 類似地，分別連接 ? ? ?=0 與 ? ? ?=0 相互對應(yīng)的點，即 ? ? 與 ? ? 連接，即圖1中兩曲線之間的紅色連接線，? ? 與 ? ? 之間的距離為 ? ? ? ,? ? ，也即 ? ? ? ? ,? ? ? 。 ?+1?+1?+1?+1 重參數(shù)

10、化前后點列之間的關(guān)系 +1由命題2及其推論可知，數(shù)列 ? ?=0 在每條曲線重參數(shù)化前后的點列保持了各點之間的 前后關(guān)系，即圖1中每條曲線上的紅點的排列順序與黑點的排列順序保持一致。 用極限思想理解弗雷歇距離 ?,? ?,? 的離散化計算公式為 ? ? ? ? ? ? ,? ? ? ,? ?,? =max?+1? ? ?=0 因此，? ?,? 的離散化計算公式為 ? ? ?,? =inf ? ?,? ?,? ?,? =inf max ? ? ? ? ,? ? ? ?+1?,? ? ?,? 的極限就是 ? ?,? 再令 ?，max? 0,? ?+1 0，? ? ?,? ? ?,? =lim? ?

11、 0,? ? ? ?=0max ?+1 0 = ? 0,? ?,?max ?+1 0lim inf max ? ? ? ? ,? ? ? ?+1? ? ?=0 用兩串珠子理解弗雷歇距離 將圖1中的兩條曲線 ?,? 設(shè)想為兩條堅硬的、被固定住的、不會變形的鋼絲，每條鋼絲都串上同樣數(shù)目的 ? 個珠子（即圖1中的黑點），再用可任意無限自由伸縮的橡皮筋把兩串珠子上對應(yīng)的珠子連接起來（即圖1中兩曲線之間連接兩曲線上黑點的黑線），最后再用橡皮筋連接兩條鋼絲對應(yīng)的端點（如圖1所示）。此時即為初始狀態(tài)。 接下來準備好紙、筆和尺子，我們開始操作、測量和記錄： ? 首先，測量初始狀態(tài)下各條橡皮筋的長度，并記錄下它們中的最大值 ?0； ? 用手任意挪動兩條鋼絲上的若干珠子使其到達新位置（即圖1中的紅