形狀匹配

形狀也是描述圖像內容的一個重要特徵。利用形狀進行匹配有三個問題值得注意。首先，形狀常與目標聯繫在一起，所以形狀特徵可以看作是比顏色或紋理要高層一些的特徵。要獲得有關目標的形狀參數，常要先對圖像進行分割，所以形狀特徵會受圖像分割效果的影響。其次，目標形狀的描述是一個非常複雜的問題，事實上，至今還沒有找到形狀的確切數學定義，使之能與人的感覺相一致。最後，從不同視角獲取的圖像中目標形狀可能會有很大差別，為準確進行形狀匹配，需要解決平移、尺度、旋轉變換不變性的問題。

基本介紹

• 中文名：形狀匹配
• 外文名：shape match
• 簡述：依據判定準則計算兩個形狀相似度
• 依據：度量準則，動態規劃
• 要素：聯繫，本質和角度
• 套用：工程繪圖

形狀匹配簡介

形狀匹配就是在形狀描述的基礎上，依據一定的判定準則，計算兩個形狀的相似度或者非相似度。兩個形狀之間的匹配結果用一個數值表示，這一數值稱為形狀相似度。形狀相似度越大，表示兩個形狀越相似。非相似度也稱為形狀距離。與相似度相反，形狀距離越小，兩個形狀越相似。

1．度量準則

採用SC形狀描述子對獲得的區域形狀進行描述，依據z。統計一量作為形狀距離的度量準則。若兩個形狀上的任一特徵點P和q，對應的形狀上下文分別為H_p和H_q，則兩者之間的匹配代價為：

C（p，q）=X²（h_p，h_q）=1/2Σ^K[h_p（k）-h_q（k）]²/h_p（k）+h_q（k）

式中：K為形狀上下文描述子的總扇區數，K=S×T；h_p（k）與h_q（k）為點p和點q的歸一化形狀上下文，計算公式如下：

公式

對於由點集表示的圖像區域輪廓P和目標形狀模板Q，P{p_i，i =1，2，…，N_p}，Q={q_j，j=1，2，…，N_q}則形狀P和形狀Q之間的匹配代價矩陣C（P，Q）為：

矩陣方程

形狀之間的相似度可以轉化為求形狀P和形狀Q之間的最小匹配代價問題。同時考慮輪廓點的順序信息，使用動態規劃解決形狀匹配。

2．動態規劃
給定兩個形狀點集P ={p₁，p₂，…，p_n}和Q ={q₁，q₂，…，q_n}。按照上式計算P和Q之間的匹配代價矩陣。形狀匹配的目標就是尋找一個匹配，令匹配代價之和最小，即

M_g（P，Q）=∑C（p_i，g（p_i））
M* =argminM（P，Q）
式中：g（p_i）表示在形狀點集P和形狀點集Q的匹配g中與點p_i相對應的Q中的特徵點；C（p_i，g（p_i）），是它們之間的匹配代價。
計算形狀距離的具體方法就是，在考慮採樣點次序的前提下，尋找兩個點集合P和Q中元素之間的對應關係。下圖展示了一個簡單的匹配例子，其中，n =8，m =7。在定義了匹配點對p_i和q_i之間的匹配代價C（p_i，q_i），以及非匹配點對的匹配代價ε的基礎上，形狀距離可通過圖中最短路徑問題解決。

兩個形狀之間的匹配結果

假設G =（V，E）是一個有向圖，節點集合和邊集合分別為V和E。V中的節點對應（n+1）×（m+1）格線中的點。邊E有兩種類型：權重為E的邊，如連線點（i，j）和點（i+1，j）的水平邊，以及連線點（i，j）和點（i，j+1）的垂直邊；權重為C（p_i，q_i）的對角邊，連線點（i，j）和點（i+1，j+1）。採用動態規劃解決匹配問題如圖所示，行列中的各元素分別對應於兩個形狀輪廓線上的採樣點，有向圖G中從點（0，0）到點（n，m）的路徑就對應形狀P和Q之間的匹配：路徑中從節點（i，j）出去的對角邊，代表點p_i與點q_i相對應。匹配路徑從第一行的某一個矩陣項開始，沿對角線方向到最後一行的某一矩陣項結束。 經過多尺度分割獲得一系列圖像塊區域，採用形狀描述方法對區域形狀進行描述，得到各個區域的SC描述向量；同時，利用形狀匹配衡量分割區域與目標模型之間的相似度，選取相似度高的區域作為目標的種子區域。

採用動態規劃解決形圖匹配

形狀匹配要素

形狀是描述圖像內容的一個重要特徵，因此，可以利用形狀進行匹配。但採用形狀進行匹配應綜合考慮以下三個問題。

（1）形狀常與目標特徵相聯繫，與顏色特徵相比，形狀特徵被認為是更高層次的圖像特徵。要獲取目標的有關形狀參數，一般應先對圖像進行分割，所以形狀特徵會受圖像分割結果精度的影響。

（2）目標形狀的描述是一個非常抽象和複雜的問題，目前還沒有與人的感覺一致且被大多數人所接受的關於圖像形狀描述的確切數學定義。

（3）從不同視角和方法獲取的圖像中目標形狀可能會有很大差別，為準確進行形狀匹配，應保證平移、尺度、旋轉變換的不變性等。

目標輪廓在一定程度上可以表示目標物體的形狀。輪廓是由物體的一系列邊界點所形成的。因此根據圖像分析的相關理論可知，在較大尺度下一般能較可靠地消除對物體邊界點的誤檢。但卻對邊界的定位易產生不準確；相反，在較小尺度下，雖然增加了邊界點誤檢的比例，但對物體或區域真正邊界點的定位卻比較準確。因此，可以結合兩者的優點，即可先在較大尺度下檢測出真正的邊界點，然後在較小尺度下對邊界點進行較精確的定位。

目前。常用的形狀匹配法主要有不變矩法、幾何參數法、特徵模表示法、邊界方向直方圖法、小波重要係數法以及我國學者楊翔英、章毓晉於1999年發表的小波輪廓表示法等許多方法。有著數學顯微鏡之稱的小波變換與分析作為一種多尺度、多解析度的分析工具，比較適合於對圖像進行多尺度的邊界檢測。

形狀匹配工具

形狀匹配工具（Register）通過使物體和目標物體儘量重合定義一個幾何變換。

可以用一個常見問題作為例子，對舊車型外觀故局部改動，有時在真實車體上用油泥進行。改動部分的數據如果和原始三維數據坐標有偏差，可以用形狀匹配工具（Register）把測量數據移動到合適的位置。使用工具時，選取三對起始點和目標點，並根據情況選取匹配區域，通過三對點使物體初步移動到目標位置，然後進行若干次疊代運算，使匹配區域與目標物體形狀儘可能貼合。

形狀匹配工具通過點擊幾何變換工具箱中的按鈕Register或下拉選單Modify→Move→Register激活，彈出形狀匹配工具視窗，有Register，lteration，Progress3個選項卡，如圖所示是Register選項卡，定義幾何變換參數。

1.Register選項卡

（1）Select：取消已有形狀匹配定義，重新選取物體定義形狀匹配。

（2）Obieet：選取要進行形狀匹配的物體。

Register選項卡

（3）Region：在要匹配的掃描點雲數據上選一塊或幾塊匹配參考區城，選取特徵明顯的局部而不用全部數據能提高匹配速度和精度。最終移動的是物體全部而不只是這幾塊參考區域,不用該按鈕則用掃描點雲數據全體進行定位計算，點擊按鈕增加匹配參考區域，原始數據。

（4）Reference：選取目標物體。

（5）Manua：激活位置選取視窗，選取至少3對起始點和目標點，對物體進行初步定位。為便於操作，起始點在要移動的物體上，參考點在目標物體上。選取能準確定位的位置可以減少計算時間提高匹配精度，如圖所示。

定義起始點和目標點以及操作結果

（6）Move：只有在形狀匹配定義完成後才可用。上一次定義的形狀匹配參數（匹配前後的位置關係）在定義新形狀匹配或退出ICEM Surf前保持不變，隨時選取要移動物體（可以使用工具後重新進人形狀匹配工具），點擊Move按鈕即按上次定義的匹配關係移動物體。定義形狀匹配移動數據後，用Move按鈕把邊界按同一幾何變換參數移動到合適位置。

（7）Save：保存兩個工作平面，分別代表物體形狀匹配前後的位置，退出工具後用坐標映射工具（2 Planes）根據這兩個工作平面定義幾何變換，重新使用形狀匹配結果。

2. Iteration選項卡

如圖所示，定義物體初步定位後的疊代參數。

Iteration選項卡

（1）Iterations：定義在進行初步定位後形狀匹配最大疊代次數。

（2）Angle、Translation：疊代過程中，通過一系列平移和旋轉使物體與目標物體逐步接近貼合。達到最大疊代次數前已經滿足匹配精度，疊代過程提前結束。Angle，Translation輸人框定義角度和平移距離作為匹配精度準則：下一次計算後物體的角度、位置調整量小於Angle，Translation輸人框中定義值，認為匹配精度滿足要求，停止疊代過程。

3. Progress選項卡

如圖所示，顯示疊代進展情況。

Progress選項卡

（1）Range：在目標物體上定義一一個偏移量。偏移量越小，疊代結束後物體與目標物體偏差量小於該偏移量的區域百分比越大，表示匹配精度越高。

（2）狀態條... %：顯示疊代完成後，要移動物體上所選區域與目標物體偏差小於在Range輸人框中定義偏差值區域的百分比。

（3）Dela... % ：每次疊代後，新增加與目標物體偏差小於在Range偏差值區域的百分比。