不規則物體形狀比對綜述

不規則物體形狀比對綜述

　

　　物體識别是計算機視覺應用的一項基本任務。識别通常基于目标物體的灰階資訊、顔色資訊或形狀資訊。物體識别的目的就是要找到一個包含可以區分不同目标物體的有效資訊的描述。由于要識别的物體是事先知道的，是以目标物體的幾何特征可以被直接應用到識别任務中。

　　不規則物體的形狀比對是一種有效的利用物體幾何特征進行識别的方法。根據比對對象的不同，可以将不規則物體的形狀比對分為基于區域的比對方法和基于輪廓的比對方法。

一、基于輪廓特征的形狀比對

　　基于輪廓特征的形狀比對在實際中更為常用，這主要有兩方面的原因：一是基于輪廓特征的比對計算量小，可以較好的滿足實時性要求；二是要識别的目标物通常是預先知道的，那麼它的幾何資訊完全可以被用于識别過程中。為了識别不規則物體，主要任務就是設計一種基于（少量的）目标物幾何限制先驗知識的有效比對方法。

1.   鍊碼直方圖(chain code histogram)

　　鍊碼直方圖将人眼看上去相似的物體歸為一類。是以利用它不能進行精确的識别和分類。

　　方向鍊碼（Freeman鍊碼）是用來表示物體輪廓的典型鍊碼表示法。一條離散曲線可以定義為Z2域内一組數量有限的8聯通點。是以，一條數字化二值曲線可以用方向鍊碼表示方向鍊碼是相鄰兩像素連線的8種可能的方向值。一條曲線被網格離散化後形成n個鍊碼方向，最終此曲線鍊碼可表示為{ai}n，每條鍊指向8個方向重的一個方向，ai={0,1,2,3,4,5,6,7}，i為像素的索引值，ai是由像素(i)指向像素(i+1)的方向鍊碼。

　　鍊碼直方圖的計算簡單而且快速。計算公式如下：

　　　　

　　其中，nk是一個鍊碼中鍊碼值k的數目，n是一個鍊碼中的節點數。

　　

  　　　(a)編碼的方向示意，(b)簡單物體形狀，(c)形狀的鍊碼表示，(d)鍊碼直方圖

　　鍊碼法的特點：

　　(1) 計算量小，可滿足實時性要求；

　　(2) 具有平移、尺度不變性；

　　(3) 具有90度旋轉不變性；

　　(4) 規格化鍊碼直方圖可以達到更好的旋轉不變性。

2.   成對幾何直方圖(Pairwise Geometric Histogram)

　　成對幾何直方圖通過相對角和相對位置特征來描述目标輪廓，并采用關系直方圖統計這對幾何特征來進行形狀索引。采用這種編碼方式需要具備一定的前提，即對于一個不規則物體我們可以将其近似為一個幾何多邊形。這種編碼方法可以很好地描述一個多邊形物體。

 　　将不規則形狀近似為多邊形，并将其定義為邊緣點的集合。這樣它所包含的輪廓邊緣（線段）就可以由連續的邊緣點來表示。接下來我們計算多邊形的PGH：将每一個輪廓邊緣視為其方向上的基準線，那麼它與其他輪廓邊緣間的相對角 以及最大最小垂直距離(dmin和dmax)可以被計算出來。邊緣之間的角度定義了直方圖的行，然後在其中增加對應的計算出來的最大和最小距離的所有直方塊，就得到了目前多邊形的PGH。

　　它具有如下特點：

　　(1) 計算簡單，可滿足實時性要求；

　　(3) 具有360度旋轉不變性。

3.   簡單形狀描述符的結合(Combination of Simple Shape Descriptors)

　　如圖，它們是幾種簡單的形狀描述符，分别代表了凹凸性、主軸、緻密性、差異性和橢圓差異性。

　　凹凸性：輪廓凸包周長與原輪廓周長的比率。（所有凸起的覆寫輪廓稱為凸包）

　　主軸：過物體質心的正交軸，主軸之間的比例可以由物體輪廓的協方差矩陣計算出來

　　緻密性：物體區域面積與等面積的正方形周長的比例，也可以是圓。

　　差異性：表現為與模闆比較的比例均方誤差。

 　　

　　單獨用這幾種簡單描述符的任何一種來表示形狀進行比對，都不能達到較好的比對結果。但是如果我們将這五種簡單形狀描述符進行結合，同時用它們來描述一個形狀，那麼這個形狀的描述資訊就非常豐富了，比對的結果也會很好。

這種形狀描述方式具有如下的特點：

　　(1) 單獨的任何一種簡單描述符都不能用于精确識别物體，但是多種簡單描述符的結合可以達到很高的識别效率；

　　(2) 計算簡單，可以達到實時性；

　　(3) 具有平移、尺度不變性；

　　(4) 理論上360度旋轉不變性。

4.   基于hausdorff距離的形狀比對

　　Hausdorff距離用來計算兩個點集之間的比對程度。給定兩個有限集A={a1,a2,…,ap}和B={b1,b2,…,bq},A，B之間的Hausdorff距離定義如下：

　　其中：

　　Hausdorff距離H(A,B)取h(A,B)和h(B,A)的最大值，這樣通過計算h(A,B)和h(B,A)就可以獲得兩個點集A，B之間的比對程度。

　　為了減少計算量，可以取角點進行比對。但這樣比對率将降低。基于hausdorff距離的形狀比對的特點;

　　(1) 對每個邊緣點進行hausdorff距離計算，計算量稍大，但對不是過于複雜的輪廓（如小尺寸輪廓），可以滿足實時性；

　　(3) 具有旋轉不變性；

二、基于區域特征的形狀比對

　　基于不變矩的形狀比對是典型的基于區域的比對方法。其中，基于Hu不變矩的形狀比對應用最為廣泛。

      圖像的矩函數在模式識别、目标分類中得到了廣泛的應用。在1961年首先基于代數不變量引入矩不變量。通過對幾何矩的非線性組合，導出了一組對于圖像平移、尺度、旋轉變化不變的矩，這種矩就成為Hu矩。

       一幅大小為M×N的二維圖像其中(p+q)階矩：

對于二值圖像，其零階矩就是該形狀區域的面積。是以，将面積歸一化，每一個圖像矩除以零階矩得到的商具有形狀的尺度變化無關性。

　　求圖像的p+q階中心矩，面積歸一化，使得具有平移、尺度不變性。

　　(1) 

　　(2) 

　　計算圖像的7個面積歸一化的中心矩，{m11,m02,m20,m21,m12,m03,m30}Hu不變矩是關于這7個矩的函數。具有平移、旋轉和尺度不變性。

　　彩色圖像Hu不變矩的計算流程如下：

　　基于Hu矩的形狀比對所具有的特點：

　　(1) Hu不變矩隻能用于對區域的檢測，不能用于邊界的檢測，但由于計算簡單，計算量不大，可以滿足實時性；

　　(3) 具有旋轉不變性。

三、比對方法間的比較

　　CCH（鍊碼直方圖）：是一種基于輪廓比對方法。具有較強的平移不變性，尺度不變性一般，具有90度的旋轉不變性。由于編碼簡單，執行速度快。計算量和所需記憶體都較小，适合差别明顯的物體，對平滑和非平滑物體的識别并不明顯；

　　PGH（成對幾何直方圖）：是一種基于輪廓比對方法。具有較強的平移不變性和尺度不變性，具有360度的旋轉不變性。執行速度快，可以較好地識别多邊形物體和部分自封閉的物體，由于它的計算過程，對非多邊形物體的識别可能會浪費計算量；

　　CFSS（五種簡單形狀描述符結合）：是一種基于輪廓比對方法。具有較強的平移不變性和尺度不變性，具有360度的旋轉不變性。執行速度處于CCH方法和PGH方法之間。識别率與PGH相當，但是比它需要更少的計算時間和記憶體。

　　HAUSDORFF距離：是一種基于輪廓比對方法。具有較強的平移不變性，但是尺度不變性和旋轉不變性都較差。由于處理的資料維數較多，執行效率是這五種方法中最慢的一個。可用于比對部分重和形狀物體。

　　Hu不變矩：是一種基于區域的形狀比對方法。具有較強的平移、尺度和旋轉不變性，其中旋轉不變性為360度。但由于比對的資料量大，執行速度較慢。适合于進行一些更精确的比對。