TWI385595B - Image segmentation method using image region merging algorithm - Google Patents

Description

利用影像區域合併演算法之影像分割方法

本發明是有關於一種影像分割方法，特別是指一種利用影像區域合併演算法影像分割方法。

電腦影像技術與工具的發展越來越成熟，讓逼真面貌的影像又再度獲得想像空間的發展。因此，各種影像處理之相關技術也就孕育而生，其中影像分割是不可欠缺的重要處理之一。

簡單來說，影像分割可定義為：將一數位影像分割成若干區域，而這些由像素組成的區域必須為各個相類似的像素所相連而成。此外，影像分割的目的，在於根據影像構成的物件來分割影像，以使電腦像人類一樣具有分析影像特徵的能力。要達到這樣的目的，必須使電腦具有足夠的知識去認知影像的內容。舉例來說，播報員在攝影棚裡播報新聞，播報員是屬於前景的部分，而播報員以外的影像就屬於攝影棚背景的部分，若以此原則執行影像分割，可以將播報員從影像中分割出來。

因此，運用上述之影像分割技術可再進一步地利用於影像特徵擷取領域，而影像特徵擷取是由影像中擷取可以代表這張影像的特徵，例如影像中顏色的分布、影像的紋路構成、與影像中物體分布的特性等。要取得影像中顏色的分布，最簡單的方法就是透過顏色的直方圖(histogram)。舉例來說，將一影像中紅色的分布位置與強弱，轉換成紅 色分布的直方圖，比較不同影像顏色的直方圖，就可以約略看出其相似度。影像紋路構成的特徵，可由其紋路的方向性或重複性來探討。舉例來說，有些木材紋路是水平方向的，而有些木材紋路則是垂直方向的。

現今影像分割主要可用於：(1)軍事用途，例如用來檢測所設定之特徵物體，如運動中的坦克車等；或是空照圖之地標的搜尋。

(2)工業用途，例如被動元件之定位與缺陷偵測技術；(3)環保用途，例如用來對環境變化的控制測量或是因天災所致之地區災害評估。

(4)目標搜索，有利於加強感興趣目標物而減弱無關的影像成分，例如警方欲從路上的各種物體中辯認出車輛來之車輛追蹤系統或其他如自動大樓監控系統、人臉辨識系統及道路車流計算等。

再者，目前影像分割主要技術手段大致可分為二階段：(1)影像量化，其目的是降低影像使用的顏色。影像量化的步驟大致可以分成兩個部份，首先是取得影像中主要的代表色，其次是將影像的原始顏色以代表色來替換。而代表色擷取的方式有很多，一般是以聚類(clustering)的方法來達成。最簡單的方式就是使用k－mean演算法，首先要決定類別的數量(也就是k值)，接著以亂數產生k個種子，並且針對每一個資料點計算資料點本身與每一個種子之間的距離，並將此資料點歸類至距離最小的類別中。然後計算 每一類的平均值，並以此平均值為新的種子，重覆上述分類作業，直到每一類的資料點不再產生變化為止。

至於顏色的替換，一般的做法就是針對影像中每一個像素(pixel)，計算該像素的顏色與每一個代表色之間的距離，然後以距離最小的代表色來替換該像素的顏色。

(2)影像區域合併，其目的是要將影像初始分割形成的多個較小的區域合併成較大且對後續應用較有意義的區域。一般採用的合併方式是由小區域開始，將其合併到與其相鄰並且顏色最接近的區域，直到所有存在的區域都大於一定的面積為止。

然而，上述之現有方法中，在進行影像區域合併時，一般傳統所使用的合併方式是由小區域開始，將其合併到與其相鄰並且顏色最接近的區域，直到所有存在的區域都大於一定的面積為止。由於影像量化後所形成之各個初始區域之間顏色本來就不是太相近，只考量顏色來進行合併所得到的結果往往和人類的感知不符。

因此，如何針對上述現有技術缺失之改良，研發出較佳的影像區域合併技術，便成為相關業者所欲努力研究的方向。

因此，本發明之目的，即在提供一種利用影像區域合併演算法之影像分割方法。

於是，本發明利用影像區域合併演算法之影像分割方法包含以下步驟： (a)輸入一原始影像，並對該原始影像進行一量化運算處理，而得到一量化影像及複數於該量化影像內之顏色區域。

(b)藉由一重要性索引作業，對該量化影像內之各顏色區域進行重要性評估，而得出與該等顏色區域相對應之複數重要性索引值。

(c)判斷該等顏色區域之重要性索引值是否低於一門檻值，若是，則利用一合併可能性作業對每一低於該門檻值之顏色區域進行評估再合併，再得出一第一合併結果。

(d)輸出一分割影像。

本發明之功效在於，透過該量化運算處理、該重要性索引作業，以及該合併可能性作業，對該原始影像進行處理，產生出該分割影像，而達到改良現有技術缺失之目的。

有關本發明之前述及其他技術內容、特點與功效，在以下配合參考圖式之一較佳實施例的詳細說明中，將可清楚的呈現。

參閱圖1至圖3及附件1至3，本發明利用影像區域合併演算法之影像分割方法的一較佳實施例，包含以下步驟：首先，如步驟11所示，輸入一原始影像20，並對該原始影像20進行一量化運算處理，而得到一量化影像21及複數於該量化影像21內之顏色區域22。

值得一提的是，在本較佳實施例中，該該量化運算處 理包括以下次步驟：首先，如次步驟111所示，先對該原始影像20進行一模式轉換作業，得出複數第一影像值30；而該模式轉換作業實際上就是把該原始影像20分成如圖2所示之複數顏色通道(即該等第一影像值30)；而該等顏色通道是區分為亮度通道31、U色差通道32及V色差通道33，也就是目前相關領域中所常用的YUV。

其次，如次步驟112所示，對該等第一影像值30進行一分析處理作業，使得該等第一影像值30變成如圖3所示之複數第二影像值40。

再來，如次步驟113所示，將該等第二影像值40結合成如附件2所示之複數顏色候選子。

接著，如次步驟114所示，對該等顏色候選子進行一排序編號作業，以將該原始影像之複數原始色彩替換成該等顏色候選子，而得到該量化影像。在此，我們為所有的顏色候選子建立一如附件3所示之顏色對應表，並將這些無序的顏色數字，結合成字串並排序及編號。並以該原始影像之複數原始顏色為索引，查表取得對應之顏色候選子，並利用二元搜尋法得到各顏色候選子的編號，對該原始影像進行量化，將該等原始色彩替換成該等顏色候選子，得到一量化影像21及複數顏色區域22。因此每一個像素顏色替換的時間複雜度便由Cn 變成了log₂ Cn ＋1。節省了大量的計算時間。

在此補充說明的是，如圖2及圖3所示，該分析處理 作業是對原始直方圖利用一非參數密度函數使其平滑化。 其詳細的運算細節為：對直方圖之每一等級，用密度估測核心函數計算出其他等級對該等級之貢獻並加總後求其平均值做為新的直方圖函數值，最後再進行局部最大值之選定，而得出該等第二影像值40。然而前述之核心函數、核心值及其他相關參數間之關係，可藉由下列公式而詳知： f(x) ：代表非參數密度函數h(r) ：代表三個顏色通道中任一個通道的直方圖r _k ：代表某一個顏色通道中第k 等級K _σ (x )：代表密度估測核心函數σ：代表密度估測核心函數之頻寬M ：代表某一個顏色通道的等級總數

圖2為該原始影像20經YUV通道轉換後之個別直方圖函數圖形，然經由前述之作業處理後，得出如圖3所示之直方圖函數圖形。本例中每一直方圖函數圖形恰好可以選出三個局部最大值，進而得出該等9個(如圖3中之圓圈標示處)第二影像值。

緊接著，如步驟12所示，藉由一重要性索引作業，對該量化影像21內之各顏色區域22進行重要性評估，而得出與該等顏色區域22相對應之複數重要性索引值。

值得一提的是，某一區域的重要性索引是藉由將該區域之像素數量平方後，除以所有顏色區域22之像素數量的總和，再除以所有與該區域相同顏色之區域22中面積最大者之像素數量，而得出每一顏色區域22之重要性索引值， 並將所得出之該等重要性索引值由小至大予以排序；而前述之重要性索引值可利用以下公式實現： R ⁱ _j ：顏色編號為i ，區域索引為j 的區域Imp(R ⁱ _j ) ：R' _j 的重要性索引：R ⁱ _j 的像素數量Mor (N _R' )：顏色編號為i 的區域中最大者的像素數量：影像大小m ：初始區域數量

然後，如步驟13所示，依序判斷該等顏色區域22之重要性索引值是否低於一門檻值，若否，則如步驟15所示，得出一第一合併結果；若是，則如步驟14所示，利用一合併可能性作業對每一低於該門檻值之顏色區域22進行評估再合併，循序地檢查是否有下一顏色區域存在而須進行該合併可能性作業，最後得出如步驟15所示之第一合併結果23(在本較佳實施例中，得出如附件1內由數字標示0到6之7個區域)，然後進行步驟18。

而在上述步驟13至步驟15中所提及之每二顏色區域22間之合併，是將被合併者顏色編號替換為另一顏色編號，而新的顏色則為二者依面積比例之加權平均。

此外，在本較佳實施例中，該合併可能性作業，首先是分別計算出每一低於該門檻值之顏色區域22與其相鄰之每一顏色區域22間的顏色距離值與邊界長度值，及其相鄰之每一顏色區域22之面積值。接著由以下合併可能性公式計算出一合併可能性： ML (a,k ) 區域a和k之間的合併可能性CD (a,k ) 區域a和k之間的顏色距離BL (a,k ) 區域a和k之間的邊界長度RS (k ) 區域k的區域大小w ₁ ,w ₂ ,w ₃ , 分別為顏色距離，邊界長度及區域大小等項目的權重max( ) 極大值函數 簡而言之，上述式子所要表示的是，任二顏色區域22間之顏色愈相近，邊界長度愈長，區域面積愈小，就代表此二顏色區域22間有愈強的合併可能性，也因此該二顏色區域22即應合併在一起。

而後，如步驟16所示，對該第一合併結果23利用一整體相似度評估進行二次合併，得出一第二合併結果24。 在本較佳實施例中，該整體相似度評估是藉由對該第一合併結果23再次進行該重要性索引作業及合併可能性作業所實現。

最後，如步驟17所示，輸出一標有複數分割線的分割影像25。

歸納上述，本發明利用影像區域合併演算法之影像分割方法，主要是將該原始影像20藉由上述之模式轉換作業、分析處理作業、編號排序作業而得出該量化影像21及該等顏色區域22，之後，再藉由該重要性索引作業以及該合併可能性作業(可總稱為影像區域合併演算法)，得出該第一合併結果23，甚至可依所需，利用整體相似度評估進行二次合併作業，而得出該第二合併結果24，最後產生出該分割影像25。

此外，鑒於現有之僅利用顏色距離之合併的缺失進行改良，故前述之重要性索引作業以及合併可能性作業的運用，不但考量了合併時，顏色的同質性，同時亦考量了區域間之幾何特性，因此，大大降低了使用傳統方法所造成之過度分割之情況，也因此，藉由本發明利用影像區域合併演算法之影像分割方法所得到的分割結果與人類的感知也就更為接近，所以確實能夠達到本發明之目的。

惟以上所述者，僅為本發明之一較佳實施例而已，當不能以此限定本發明實施之範圍，即大凡依本發明申請專利範圍及發明說明內容所作之簡單的等效變化與修飾，皆仍屬本發明專利涵蓋之範圍內。

11~17‧‧‧步驟

111~114‧‧‧次步驟

20‧‧‧原始影像

21‧‧‧量化影像

22‧‧‧顏色區域

23‧‧‧第一合併結果

24‧‧‧第二合併結果

25‧‧‧分割影像

30‧‧‧第一影像值

31‧‧‧亮度通道

32‧‧‧U色差通道

33‧‧‧V色差通道

40‧‧‧第二影像值

圖1是一流程圖，說明本發明影像分割方法之較佳實施例的處理流程；圖2是一組直方圖，說明該較佳實施例中，將該原始影像轉換為複數第一影像值；及圖3是一組直方圖，說明該較佳實施例中，將該第一影像值轉換為複數第二影像值。

【附件簡單說明】

附件1是一組影像圖，說明該較佳實施例中，一原始影像、一量化影像、複數顏色區域、一第一合併結果、一第二合併結果及一分割影像所呈現之個別差異；附件2是一示意圖，說明該較佳實施例中，由複數第二影像值所結合而成的顏色候選子態樣；及 附件3是一對應表，說明該較佳實施例中，由該等原始色彩所取得該等顏色候選子的最相近顏色候選子快對應表。

11~17‧‧‧步驟

111~114‧‧‧次步驟

Claims (14)

1. 一種利用影像區域合併演算法之影像分割方法包含以下步驟：(a)輸入一原始影像，並對該原始影像進行一量化運算處理，而得到一量化影像及複數於該量化影像內之顏色區域；(b)藉由一重要性索引作業，對該量化影像內之各顏色區域進行重要性評估，而得出與該等顏色區域相對應之複數重要性索引值；(c)判斷該等顏色區域之重要性索引值是否低於一門檻值，若是，則利用一合併可能性作業對每一低於該門檻值之顏色區域進行評估再合併，再得出至一第一合併結果，其中該合併可能性作業是藉由分別計算出每一低於該門檻值之顏色區域與其相鄰之每一顏色區域間的顏色距離值與邊界長度值，及其相鄰之每一顏色區域之面積值，接著，利用一合併可能性公式計算出該區域應被合併之相鄰區域；及(d)輸出一分割影像。
2. 依據申請專利範圍第1項所述之利用影像區域合併演算法之影像分割方法，其中，在該(b)步驟中，該重要性索引作業是藉由分別將每一顏色區域之像素數量平方後，除以所有顏色區域之像素數量的總和，再除以所有顏色區域中所佔區域最大者之像素數量，而得出每一顏色區域之重要性索引值。
3. 依據申請專利範圍第2項所述之利用影像區域合併演算法之影像分割方法，更包含一位於該(c)步驟與該(d)步驟間之(e)步驟，對該第一合併結果進行一整體相似性評估合併作業，得出一第二合併結果。
4. 依據申請專利範圍第3項所述之利用影像區域合併演算法之影像分割方法，其中，在該(e)步驟中，該整體相似性評估合併作業是對該第一合併結果再次進行該重要性索引作業及合併可能性作業。
5. 依據申請專利範圍第4項所述之利用影像區域合併演算法之影像分割方法，其中，在該(a)步驟中，該量化運算處理是先對該原始影像進行一模式轉換作業，而成複數第一影像值，再對該等第一影像值進行一分析處理作業，使得該等第一影像值變成複數第二影像值，接著再將該等第二影像值結合成複數顏色候選子，並對該等顏色候選子進行一排序編號作業，以將該原始影像之複數原始色彩替換成該等顏色候選子，而得到該量化影像。
6. 依據申請專利範圍第5項所述之利用影像區域合併演算法之影像分割方法，其中，在該(a)步驟之排序編號作業中，該等原始顏色之替換，是以該等原始顏色為索引，查詢一與該等原始顏色最相近顏色候選子快速對應表而取得對應之顏色候選子及其編號。
7. 依據申請專利範圍第6項所述之利用影像區域合併演算法之影像分割方法，其中，在該(c)步驟中，每二顏色區域間之合併，是將被合併者之顏色編號替換為另一者顏 色編號，而新的顏色則為二者依面積比例之加權平均。
8. 依據申請專利範圍第7項所述之利用影像區域合併演算法之影像分割方法，其中，在該(a)步驟中，該模式轉換作業是將該原始影像分成複數顏色通道，成為該等第一影像值，而該分析處理作業是對原始直方圖利用一非參數密度函數使其平滑化，最後再進行局部最大值之選定，而得出該等第二影像值。
9. 依據申請專利範圍第8項所述之利用影像區域合併演算法之影像分割方法，其中，在該(a)步驟中，該等顏色候選子的編號是利用二元搜尋法來取得。
10. 依據申請專利範圍第9項所述之利用影像區域合併演算法之影像分割方法，其中，在該(c)步驟中，該合併可能性公式是藉由一第一權值乘上1減去各該顏色距離值所佔其中最大顏色距離值之比例後，加上一第二權值乘上各該邊界長度值所佔其中最大邊界長度值之比例，再加上一第三權值乘上1減去各該面積值所佔其中最大面積值之比例，最後得出至少一可能性值。
11. 依據申請專利範圍第10項所述之利用影像區域合併演算法之影像分割方法，其中，在該(a)步驟中，該非參數密度函數是將其各顏色通道中每一等級值帶入其顏色通道之直方圖函數，並將該等等級值之其中一值減去其他等級值後帶入一密度估測核心函數，得出複數核心值，再對所得之核心值加總後再除以其顏色通道之等級總數。
12. 依據申請專利範圍第11項所述之利用影像區域合併演算 法之影像分割方法，其中，在該(b)步驟中，所得出之該等重要性索引值是由小至大予以排序，而在該(c)步驟中，是依序地判斷該等顏色區域之重要性索引值是否低於該門檻值。
13. 依據申請專利範圍第12項所述之利用影像區域合併演算法之影像分割方法，其中，在該(c)步驟中，當所判斷出該等顏色區域之重要性索引值是不低於該門檻值時，則直接得出該第一合併結果，並進行下一步驟。
14. 依據申請專利範圍第1或12項所述之利用影像區域合併演算法之影像分割方法，其中，在該(b)步驟中之重要性索引作業及在該(c)步驟中之合併可能性作業總稱為影像區域合併演算法。