基於行程編碼的多個連通域快速合併算法及裝置的製作方法

2023-06-29 20:28:34 2

本發明涉及圖像處理，尤其涉及到對多個連通域合併的實現。

背景技術：

在機器視覺中，多個連通域合併算法是Blob分析中常用的算法，應用主要為：圖像閾值分割得到感興趣區域後，進行連通域標記，進而結合Blob特徵，例如：面積，選取符合特徵的連通域，此時利用多個連通域合併作為一個新連通域單獨進行Blob分析，或與其它Blob算法，例如：連通域差集、交集，結合求取符合需求的連通域進行Blob分析。

目前Blob分析算法中，主要針對標記後的連通域，選取符合特徵的連通域去操作；對於某些具體應用，需要產生新的連通域進行Blob分析，則通過組合多個已有連通域去實現。多個標記連通域的Blob分析可以分為兩種：1)連通域的標記採用二值圖的方式，即一副灰度圖裡，用像素值標記連通域，所有具有相同像素值的像素點組成一個連通域；2)連通域採用行程編碼的方式。這兩種連通域表示方法在需求特定新連通域時，都分別對多個標記連通域分析，然後組合操作以達到功能需求。多個標記連通域的Blob分析的優點是直觀容易理解；缺點則有：若連通域採用二值圖方式，速度慢，佔用內存大，對感興趣區域的操作受圖像的寬高限制，需訪問圖像內所有點，同時無法表示連通域重疊的部分，後續Blob分析操作複雜；若連通域採用行程編碼方式，後續Blob分析操作複雜，連通域重疊時重複計算，導致耗時增加。

技術實現要素：

本發明要解決的技術問題在於，針對現有技術的上述缺陷，提出一種基於行程編碼的多個連通域快速合併算法，能夠實現多個連通域的快速合併，並且降低程序內存佔用量。

本發明解決其技術問題所採用的技術方案是：提供一種基於行程編碼的多個連通域快速合併算法，包括：對輸入圖像進行圖像分割，得到採用行程編碼的感興趣區域；對採用行程編碼的感興趣區域進行處理，得到多個連通域；以及合併多個連通域，得到合併後的連通域。

在一些實施例中，所述的對輸入圖像進行圖像分割，得到採用行程編碼的感興趣區域，具體包括：選取適當的高、低閾值；然後，遍歷圖像中所有像素點，滿足閾值要求的則為感興趣區域像素點，將所有感興趣區域的像素點用行程編碼保存。

在一些實施例中，所述的對採用行程編碼的感興趣區域進行處理，得到多個連通域，具體包括：對採用行程編碼的感興趣區域進行連通域標記。

在一些實施例中，所述的行程編碼是基於行行程實現的；所述的合併多個連通域是逐行合併的。

在一些實施例中，所述的合併多個連通域，得到合併後的連通域，具體包括：求取多個連通域的最小行號和最大行號，然後行號由小到大去統計多個連通域具有相同行號的行程，進而一一合併兩個行程。

在一些實施例中，所述的合併兩個行程，具體包括三種情況：兩個行程沒有交集，結果存儲兩個行程；兩個行程有部分交集，結果為最小列號和最大列號組成的新行程；一個行程包含另外一個行程，結果存儲包含的行程。。

本發明解決其技術問題所採用的技術方案還是：提供一種基於行程編碼的多個連通域快速合併裝置，包括：第一模塊，用於對輸入圖像進行圖像分割，得到採用行程編碼的感興趣區域；第二模塊，用於對採用行程編碼的感興趣區域進行處理，得到多個連通域；以及第三模塊，用於合併多個連通域，得到合併後的連通域。

在一些實施例中，所述的第一模塊具體實現的功能包括：選取適當的高、低閾值；遍歷圖像中所有像素點，滿足閾值要求的則為感興趣區域像素點，將所有感興趣區域的像素點用行程編碼保存。

在一些實施例中，所述的第三模塊具體實現的功能包括：求取多個連通域的最小行號和最大行號，然後行號由小到大去統計多個連通域具有相同行號的行程，進而一一合併兩個行程。

在一些實施例中，所述的合併兩個行程，具體包括三種情況：兩個行程沒有交集，結果存儲兩個行程；兩個行程有部分交集，結果為最小列號和最大列號組成的新行程；一個行程包含另外一個行程，結果存儲包含的行程。

本發明的有益效果在於，通過對圖像進行行程編碼，所有操作都是針對編碼後的圖像，可以節省佔用內存，而且脫離了圖像的限制；另外，通過將多個連通域合併，再進行後續Blob分析更易獲取特徵信息，耗時更少。

附圖說明

下面將結合附圖及實施例對本發明作進一步說明，附圖中：

圖1為本發明的行程編碼的示意圖。

圖2為本發明的圖像閾值分割得到感興趣區域的示意圖。

圖3為本發明的多個連通域的示意圖。

圖4a、4b為本發明的兩個行程沒有交集相合併的示意圖，其中圖4a示出合併前，圖4b示出合併後。

圖5a、5b為本發明的兩個行程有部分交集相合併的示意圖，其中圖5a示出合併前，圖5b示出合併後。

圖6a、6b為本發明的一個行程包含另一個行程相合併的示意圖，其中圖6a示出合併前，圖6b示出合併後。

圖7為本發明算法的流程示意圖。

圖8為採用本發明算法對圖3所示的連通域進行合併後的結果示意圖。

圖9為本發明裝置的示意性框圖。

具體實施方式

現結合附圖，對本發明的較佳實施例作詳細說明。

本發明提出一種基於行程編碼的多個連通域快速合併算法，主要包括三個步驟：對輸入圖像進行行程編碼；標記連通域；以及合併多個連通域。本發明算法適用的領域包括，但不限於：圖像處理blob分析；與圖形、輪廓匹配算法組合創建各種匹配的模板。

關於對輸入圖像進行行程編碼的步驟，圖像處理中常需要對圖像進行閾值分割以獲得感興趣區域。現有算法中感興趣區域通常直接用圖像像素點表示，像素點表示感興趣區域存在的弊端：一是內存佔用大，二是無法表示多個連通域重疊部分。在內存佔用方面，以一幅8位深度200萬像素的灰度圖為例，若一片感興趣區域含30萬個像素點，其內存佔用量為：2000000byte，約1.9MB。若採用行程編碼方式，內存佔用量可能低至3KB，二者相差近650倍，由此可見行程編碼感興趣區域對減少內存佔用是有效的。採用行程編碼的另一個優點是對感興趣區域分析時，藉助行程編碼可以直接對區域操作，而二值圖則需要先遍歷圖像再處理，耗時明顯增加。

行程編碼可分為行行程與列行程。其中，行行程包含行程所在行號Row、行程起始列Cb與行程終止列Ce。列行程包含行程所在列號Col、行程起始行Rb與行程終止行Re。

本發明的行程編碼是基於行行程實現的。感興趣區域每一行中連續符合閾值分割的像素點組成的區域稱為一個行程。表示一個行程僅需所在行號Row，起始列Cb與終止列Ce。若這三個分量都用兩個字節的Short(短)數據類型來表示，則一個行程佔用6個字節。每一片感興趣區域是由有限個行程組成的。每一行可能包含若干個行程，存儲可以按照行號由小到大，行號相同時按列號由小到大。

參見圖1，圖1為本發明的行程編碼的示意圖。作為一個例舉，圖1示意出了像素101，第一行程103，第二行程105，第三行程107以及感興趣區域109。

參見圖2，圖2為本發明的圖像閾值分割得到感興趣區域的示意圖。作為一個例舉，圖2示出了背景200下的三個感興趣區域201、203和205。其中，第一感興趣區域201呈橫躺的葫蘆狀；第二感興趣區域203呈豎立且尺寸較大的矩形狀；第三感興趣區域205呈橫躺且尺寸較小的矩形狀。

關於標記連通域的步驟，在行程編碼圖像後，需要進行連通域標記。具體實現可以參考已有的連通域標記方法，例如：Two-Pass遍歷和Seed種子填充，在此不再贅述。

關於合併多個連通域的步驟，參見圖3，圖3為本發明的多個連通域的示意圖。作為一個例舉，圖3示出了背景300下的多個連通域301、303、305、307和309。其中，第一連通域301呈橢圓狀，其與第二連通域303存在部分重疊；第三連通域305和第四連通域307均為豎立且尺寸較大的矩形狀，並且第三連通域305包含第四連通域307在內；第五連通域309為橫躺且尺寸較小的矩形狀。

合併多個連通域的方法採用逐行合併，首先求取多個連通域中行程最小行號MinRow和最大行號MaxRow，然後根據行號由小到大遍歷多個連通域的行程，每次將行程具有相同行號的作為行程合併的操作源。當循環從最小行號MinRow到最大行號MaxRow後，多個連通域也就合併成一個或多個新的連通域，並且行程的存儲順序也符合先前的規則：按照行號由小到大，行號相同時按列號由小到大。

兩個行程相合併主要有三種情況：1)兩個行程沒有交集，結果存儲兩個行程；參見圖4a、4b，圖4a、4b為本發明的兩個行程沒有交集相合併的示意圖，其中圖4a示出合併前在背景400下的兩個行程401、403，圖4b示出合併後在背景400下的兩個行程405、407。2)兩個行程有部分交集，結果為最小列號和最大列號組成的新行程；參見圖5a、5b，圖5a、5b為本發明的兩個行程有部分交集相合併的示意圖，其中圖5a示出合併前在背景500下的兩個行程501、503，二者具有交集505，圖5b示出合併後在背景500下的一個行程507。3)一個行程包含另外一個行程，結果存儲包含的行程；參見圖6a、6b，圖6a、6b為本發明的一個行程包含另一個行程相合併的示意圖，其中圖6a示出合併前在背景600下的兩個行程601、603，行程601包含行程603，圖6b示出合併後在背景600下的一個行程605。

參見圖7，圖7為本發明算法的流程示意圖。本發明算法大致包括以下步驟：S701、對輸入圖像進行圖像分割，得到採用行程編碼的感興趣區域。具體而言，首先，選取適當的高、低閾值；然後，遍歷圖像中所有像素點，滿足閾值要求的則為感興趣區域像素點，將所有感興趣區域的像素點用行程編碼保存，具體可參考圖1與圖2。

S702、對採用行程編碼的感興趣區域進行處理，得到多個連通域。具體而言，可以對感興趣區域進行連通域標記，得到多個連通域；或者，將其它的處理方式得到多個連通域。

S703、合併多個連通域，得到合併後的連通域。合併多個連通域的方法是逐行合併，求取多個連通域的最小行號MinRow和最大行號MaxRow，然後行號由小到大去統計多個連通域具有相同行號的行程，進而一一合併兩個行程，具體合併兩個行程可以參考圖4a、4b示出的兩個行程不需改變存儲的第一種情形；圖5a、5b示出的兩個行程中最小的列號和最大的列號組成新的行程存儲的第二種情形；以及圖6a、6b示出的存儲包含另一行程的行程本身的第三種情形。循環重複兩個行程合併的過程，直至將多個連通域的所有行程都遍歷完畢後，即可快速完成合併多個連通域。

參見圖8，圖8為採用本發明算法對圖3所示的連通域進行合併後的結果示意圖。作為一個例舉，圖8示出了背景800下的三個連通域801、803和805。可以理解的是，連通域801是前述圖3中的兩個連通域301、303的合併結果；連通域803是前述圖3中的兩個連通域305、307的合併結果；連通域805為前述圖3中的連通域309。

參見圖9，圖9為本發明裝置的示意性框圖。作為在一種例舉，該裝置900包括：第一模塊901，用於對輸入圖像進行圖像分割，得到採用行程編碼的感興趣區域；第二模塊902，用於對採用行程編碼的感興趣區域進行處理，得到多個連通域；以及第三模塊903，用於合併多個連通域，得到合併後的連通域。

該第一模塊901具體實現的功能包括：選取適當的高、低閾值；遍歷圖像中所有像素點，滿足閾值要求的則為感興趣區域像素點，將所有感興趣區域的像素點用行程編碼保存。

該第三模塊903具體實現的功能包括：求取多個連通域的最小行號和最大行號，然後行號由小到大去統計多個連通域具有相同行號的行程，進而一一合併兩個行程。所述的合併兩個行程，具體包括三種情況：兩個行程沒有交集，結果存儲兩個行程；兩個行程有部分交集，結果為最小列號和最大列號組成的新行程；一個行程包含另外一個行程，結果存儲包含的行程。

可以理解的是，上述的三個模塊901、902、903既可以對應於處理器上運行的程序的三個軟體模塊，也可以對應於專門構建的三個硬體模塊。

本發明的有益效果包括：感興趣區域經行程編碼後表示的最小單位為行程，每個行程可包含多個像素點，因此行程數必然比像素點數少，與遍歷像素點的算法相比遍歷行程則變得簡單，耗時也將減少；採用行程編碼後，感興趣區域脫離二值圖表示的圖像寬度與高度的限制，直接保存任意形狀、任意大小的感興趣區域，無數據冗餘，內存佔用少，可以解決資源有限制的應用；多個連通域合併可以解決Blob分析中由多個連通域組合求取特徵的繁瑣操作，可以由合併的新連通域直觀便捷分析Blob的特徵信息；另外，多個連通域合併可以為圖形、輪廓匹配創建各種形狀的模板。

應當理解的是，以上實施例僅用以說明本發明的技術方案，而非對其限制，對本領域技術人員來說，可以對上述實施例所記載的技術方案進行修改，或者對其中部分技術特徵進行等同替換；而這些修改和替換，都應屬於本發明所附權利要求的保護範圍。