圖像分析：二值圖像連通域標記

1、g. 一、前言二值圖像，顧名思義就是圖像的亮度值只有兩個狀態(tài)：黑（o）和白（255）。二值圖像在圖像分析與識別中有著舉足輕重的地位，因為其模式簡單，對像素在空間上的關系有著極強的表現(xiàn)力。在實際應用中，很多圖像的分析最終都轉換為二值圖像的分析，比如：醫(yī)學圖像分析、前景檢測、字符識別，形狀識別。二值化+數(shù)學形態(tài)學能解決很多計算機識別工程中目標提取的問題。二值圖像分析最重要的方法就是連通區(qū)域標記，它是所有二值圖像分析的基礎，它通過對二值圖像中白色像素（目標）的標記，讓每個單獨的連通區(qū)域形成一個被標識的塊，進一步的我們就可以獲取這些塊的輪廓、外接矩形、質(zhì)心、不變矩等幾何參數(shù)。下面是一個二值圖像被標記后

2、，比較形象的顯示效果，這就是我們這篇文章的目標。二、連通域在我們討論連通區(qū)域標記的算法之前，我們先要明確什么是連通區(qū)域，怎樣的像素鄰接關系構成連通。在圖像中，最小的單位是像素，每個像素周圍有8個鄰接像素，常見的鄰接關系有2種：4鄰接與8鄰接。4鄰接一共4個點，即上下左右，如下左圖所示。8鄰接的點一共有8個，包括了對角線位置的點，如下右圖所示。XX如果像素點A與B鄰接，我們稱A與B連通，于是我們不加證明的有如下的結論：如果A與B連通，B與C連通，則A與C連通。在視覺上看來，彼此連通的點形成了一個區(qū)域，而不連通的點形成了不同的區(qū)域。這樣的一個所有的點彼此連通點構成的集合，我們稱為一個連通區(qū)域。下面

3、這符圖中，如果考慮4鄰接，則有3個連通區(qū)域；如果考慮8鄰接，則有2個連通區(qū)域。（注：圖像是被放大的效果，圖像正方形實際只有4個像素）。三、連通區(qū)域的標記連通區(qū)域標記算法有很多種，有的算法可以一次遍歷圖像完成標記，有的則需要2次或更多次遍歷圖像。這也就造成了不同的算法時間效率的差別，在這里我們介紹2種算法。第一種算法是現(xiàn)在matlab中連通區(qū)域標記函數(shù)bwlabel中使的算法，它一次遍歷圖像，并記下每一行（或列）中連續(xù)的團（run）和標記的等價對，然后通過等價對對原來的圖像進行重新標記，這個算法是目前我嘗試的幾個中效率最高的一個，但是算法里用到了稀疏矩陣與Dulmage-Mendelsohn分解

4、算法用來消除等價對，這部分原理比較麻煩，所以本文里將不介紹這個分解算法，取而代這的用圖的深度優(yōu)先遍歷來替換等價對。第二種算法是現(xiàn)在開源庫cvBlob中使用的標記算法，它通過定位連通區(qū)域的內(nèi)外輪廓來標記整個圖像，這個算法的核心是輪廓的搜索算法，這個我們將在文章中詳細介紹。這個算法相比與第一種方法效率上要低一些，但是在連通區(qū)域個數(shù)在100以內(nèi)時，兩者幾乎無差別，當連通區(qū)域個數(shù)到了103103數(shù)量級時，上面的算法會比該算法快10倍以上。四、基于行程的標記我們首先給出算法的描述，然后再結合實際圖像來說明算法的步驟。逐行掃描圖像，我們把每一行中連續(xù)的白色像素組成一個序列稱為一個團（run），并記下它的起

5、點start、它的終點end以及它所在的行號。對于除了第一行外的所有行里的團，如果它與前一行中的所有團都沒有重合區(qū)域，則給它一個新的標號；如果它僅與上一行中一個團有重合區(qū)域，則將上一行的那個團的標號賦給它；如果它與上一行的2個以上的團有重疊區(qū)域，則給當前團賦一個相連團的最小標號，并將上一行的這幾個團的標記寫入等價對，說明它們屬于一類。將等價對轉換為等價序列，每一個序列需要給一相同的標號，因為它們都是等價的。從1開始，給每個等價序列一個標號。遍歷開始團的標記，查找等價序列，給予它們新的標記。5，將每個團的標號填入標記圖像中。6，結束。我們來結合一個三行的圖像說明，上面的這些操作。第一行，我們得到

6、兩個團：2,6和10,13，同時給它們標記1和2。第二行，我們又得到兩個團：6,7和9,10，但是它們都和上一行的團有重疊區(qū)域，所以用上一行的團標記，即1和2。第三行，兩個：2,4和7,8。2,4這個團與上一行沒有重疊的團，所以給它一個新的記號為3；而2,4這個團與上一行的兩個團都有重疊，所以給它一個兩者中最小的標號，即1,然后將（1,2）寫入等價對。全部圖像遍歷結束，我們得到了很多個團的起始坐標，終止坐標，它們所在的行以及它們的標號。同時我們還得到了一個等價對的列表。下面我們用C+實現(xiàn)上面的過程，即步驟2,分兩個進行：1)fillRunVectors函數(shù)完成所有團的查找與記錄；voidfil

7、lRunVectors(constMat&bwImage,int&NumberOfRuns,vector&stRun,vector&enRun,vector&rowRun)for(inti=0;ibwImage.rows;i+)constuchar*rowData=bwImage.ptr(i);if(rowData0=255)NumberOfRuns+;stRur.push_back(0);rowRur.push_back(i);_for(intj=1;jbwImage.cols;j+)if(rowDataj-1=0&rowDataj=255)NumberOfRuns+;stRur.push_

8、back(j);rowRur.push_back(i);_elseif(rowDataj-1=255&rowDataj=0)enRur.push_back(j-1);_if(rowDatabwImage.cols-1)enRu.push_back(bwImage.cols-1);_2)firstPass函數(shù)完成團的標記與等價對列表的生成。相比之下第二個函數(shù)要稍微難理解一些。voidfirstPass(vector&stRun,vector&enRun,vector&rowRun,intNumberOfRuns,vector&runLabels,vectorpair&equivalences,i

9、ntoffset)runLabels.assign(NumberOfRuns,0);intidxLabel=1;intcurRowldx=0;intfirstRunOnCur=0;intfirstRunOnPre=0;intlastRunOnPre=-1;for(inti=0;iNumberOfRuns;i+)if(rowRuni!=curRowldx)curRowldx=rowRuni;firstRunOnPre=firstRunOnCur;lastRunOnPre=i-1;firstRunOnCur=i;for(intj=firstRunOnPre;j=lastRunOnPre;j+)if

10、(stRuni=stRunj-offset&rowRuni=rowRunj+1)if(runLabelsi=0)/沒有被標號過runLabelsi=runLabelsj;elseif(runLabelsi!=runLabelsj)/已經(jīng)被標號equivalences.push_back(make_pair(runLabelsi,runLabelsj);/保存等價對if(runLabelsi=0)/沒有與前一列的任何run重合runLabelsi=idxLabel+;接下來是我們的重點，即等價對的處理，我們需要將它轉化為若干個等價序列。比如有如下等價對：(i,2),(i,6),(3,7),(9-

11、3),(8,i),(8,io),(ii,5),(ii,8),(ii,12),(ii,13),(ii,14),(15,ii)我們需要得到最終序列是：listl：listi:i-2-5-6-8-io-ii-i2-i3-i4-i5list2：list2：3-7-9Iist3：list3：4一個思路是將1-15個點都看成圖的結點，而等價對(1,2)說明結點1與結點2之間有通路，而且形成的圖是無向圖,即(1,2)其實包含了(2,1)。我們需要遍歷圖，找出其中的所有連通圖。所以我們采用了圖像深入優(yōu)先遍歷的原理，進行等價序列的查找。從結點1開始，它有3個路徑1-2，1-6,1-8。2和6后面都沒有路徑，8有

12、2條路徑通往10和11,而10沒有后續(xù)路徑，11則有5條路徑通往5，12，13，14，15。等價表1查找完畢。第2條等價表從3開始，則只有2條路徑通向7和9,7和9后面無路徑，等價表2查找完畢。最后只剩下4,它沒有在等價對里出現(xiàn)過，所以單兒形成一個序列(這里假設步驟2中團的最大標號為15)。竽價表1等價表2等價表3下面是這個過程的C+實現(xiàn)，每個等價表用一個vectorvint來保存，等價對列表保存在mappairint,int里。pg.4pg. voidreplaceSameLabel(vector&runLabels,vectorpair&equivalence)intmaxLabel=*m

13、ax_element(runLabels.begin(),runLabels.end();vectorvectoreqTab(maxLabel,vector(maxLabel,false);vectorpair:iteratorvecPairIt=equivalence.begin();while(vecPairIt!=equivalence.end()eqTabvecPairIt-first-1vecPairIt-second-1=true;eqTabvecPairIt-second-1vecPairIt-first-1=true;vecPairIt+;vectorlabelFlag(max

14、Label,0);vectorvectorequaList;vectortempList;coutmaxLabelendl;for(inti=1;i=maxLabel;i+)if(labelFlagi-1)continue;labelFlagi-1=equaList.size()+1;tempList.push_back(i);for(vector:size_typej=0;jtempList.size();j+)for(vector:size_typek=0;k!=eqTabtempListj-1.size();k+)if(eqTabtempListj-1k&!labelFlagk)temp

15、List.push_back(k+1);labelFlagk=equaList.size()+1;equaList.push_back(tempList);tempList.clear();coutequaList.size()endl;for(vector:size_typei=0;i!=runLabels.size();i+)runLabelsi=labelFlagrunLabelsi-1;五、基于輪廓的標記在這里我還是先給出算法描述：從上至下，從左至右依次遍歷圖像。如下圖A所示，A為遇到一個外輪廓點（其實上遍歷過程中第一個遇到的白點即為外輪廓點），且沒有被標記過，則給A一個新的標記號。我

16、們從A點出發(fā)，按照一定的規(guī)則（這個規(guī)則后面詳細介紹）將A所在的外輪廓點全部跟蹤到，然后回到A點，并將路徑上的點全部標記為A的標號。如下圖B所示，如果遇到已經(jīng)標記過的外輪廓點AA,則從AA向右，將它右邊的點都標記為AA的標號，直到遇到黑色像素為止。如下圖C所示，如果遇到了一個已經(jīng)被標記的點B,且是內(nèi)輪廓的點(它的正下方像素為黑色像素且不在外輪廓上)，則從B點開始，跟蹤內(nèi)輪廓，路徑上的點都設置為B的標號，因為B已經(jīng)被標記過與A相同，所以內(nèi)輪廓與外輪廓將標記相同的標號。如下圖D所示，如果遍歷到內(nèi)輪廓上的點，則也是用輪廓的標號去標記它右側的點，直到遇到黑色像素為止。6，結束。整個算法步驟，我們只掃描了

17、一次圖像，同時我們對圖像中的像素進行標記，要么賦予一個新的標號，要么用它同行的左邊的標號去標記它，下面是算法更詳細的描述：對于一個需要標記的圖像II，我們定義一個與它對應的標記圖像LL,用來保存標記信息，開始我們把L上的所有值設置為0同時我們有一個標簽變量CC，初始化為1。然后我們開始掃描圖像I,遇到白色像素時，設這個點為PP點，我們需要按下面不同情況進行不同的處理：情況1：如果p(i,j)p(i,j)點是一個白色像素，在LL圖像上這個位置沒有被標記過，而且PP點的上方為黑色,則P是一個新的外輪廓的點，這時候我們將C的標簽值標記給L圖像上P點的位置(x,y)(x,y),即L(x,y)=CL(x

18、,y)=C，接著我們沿著P點開始做輪廓跟蹤，并把把輪廓上的點對應的L上都標記為C,完成整個輪廓的搜索與標記后，回到了P點。最后不要忘了把C的值加1。這個過程如下面圖像Si中所示。11L11111L1L1L11L1情況2:如果P點的下方的點是unmarked點（什么是unmark點，情況3介紹完就會給出定義），則P點一定是內(nèi)輪廓上的點，這時候有兩種情況，一種是P點在L上已經(jīng)被標記過了，說明這個點同時也是外輪廓上的點；另一種情況是P點在L上還沒有被標記過，那如果是按上面步驟來的，P點左邊的點一定被標記了（這一處剛開始理解可能不容易，不妨畫一個簡單的圖，自己試著一個點一個點標記試試，就容易理解了），

19、所以這時候我們采用P點左邊點的標記值來標記P,接著從P點開始跟蹤內(nèi)輪廓把內(nèi)輪廓上的點都標記為P的標號。:如果一個點P,不是上面兩種情況之一，那么P點的左邊一定被標記過（不理解，就手動去標記上面兩幅圖像），我們只需要用它左邊的標號去標記L上的P點。現(xiàn)在我們只剩下一個問題了，就是什么是unmarked點，我們知道內(nèi)輪廓點開始點P的下方一定是一個黑色像素，是不是黑色像素就是unmarked點呢，顯然不是，如下圖像的Q點，它的下面也是黑色像素，然而它卻不是內(nèi)輪廓上的點。實際上在我們在輪廓跟蹤時，我們我輪廓點的周圍做了標記，在輪廓點周圍被查找過的點（查找方式見下面的輪廓跟蹤算法）在L上被標記了一個負值（

20、如下面右圖所示），所以Q點的下方被標記為了負值，這樣Q的下方就不是一個unmarked點，unmarked點，即在L上的標號沒有被修改過，即為0。1111111111Q111111顯然，這個算法的重點在于輪廓的查找與標記，而對于輪廓的查找，就是確定搜索策略的問題，我們下面給內(nèi)輪廓與外輪廓定義tracker規(guī)則。我們對一點像素點周圍的8個點分析作一個標號0-7,因為我們在遍歷圖像中第一個遇到的點肯定是外輪廓點，所以我們先來確定外輪廓的搜索策略，對于外輪廓的點P,有兩種情況：5674P03211)如果P是外輪廓的起點，也就是說我們是從P點開始跟蹤的，那么我們從7號(右上角)位置P1P1開始，看7號

21、是不是白色點，如果是，則把這個點加入外輪廓點中，并將它標記與P點相同，如果7號點是黑色點，則按順時針7-O-1-2-3-4-5-6這個順序搜索直到遇到白點為止，把那個點確定為P1P1，加入外輪廓，并把這個點的標號設置與P點相同。這里很重要一步就是，假設我們2號點才是白點，那么7,0，1這三個位置我們都搜索過，所以我們要把這些點在L上標記為一個負值。如下圖所示，其中右圖像標記的結果。00-10n-10n-12)那么如果P是不是外輪廓的起點，即P是外輪廓路徑上的一個點，那么它肯定是由一個點進入的，我們設置為P-1P-1點，P1P-1點的位置為x(0v=xv=7)x(o=x=7)，那么P點從(x+2

22、)mod8(x+2)mod8這個位置開始尋找下一步的路徑，(x+2)mod8(x+2)mod8是加2取模的意思，它反映在圖像就是從P-1點按順時針數(shù)2個格子的位置。確定搜索起點后，按照上面一種情況進行下面的步驟。外輪廓點的跟蹤方式確定了后，內(nèi)輪廓點的跟蹤方式大同小異，只是如果P是內(nèi)輪廓的第一個點，則它的開始搜索位置不是7號點而是3號點。其他的與外輪廓完全一致。如要上面搜索方式，你不是很直觀的理解，不妨嘗試著去搜索下面這幅圖像，你應該有能有明確的了解了。一個路徑搜索結束的條件是，回到原始點S,則S周圍不存在unmarked點。如下邊中間圖像所示，從S點開始形成的路徑是STUTSVWV。在Open

23、CV中查找輪廓的函數(shù)已經(jīng)存在了，而且可以得到輪廓之間的層次關系。這個函數(shù)按上面的算法實現(xiàn)起來并不困難，所以這里就不再實現(xiàn)這個函數(shù)，有興趣的可以看OpenCV的源碼(contours.cpp)。voidbwLabel(constMat&imgBw,Mat&imgLabeled)/對圖像周圍擴充一格MatimgClone=Mat(imgBw.rows+1,imgBw.cols+1,imgBw.type(),Scalar(0);imgBw.copyTo(imgClone(Rect(1,1,imgBw.cols,imgBw.rows);imgLabeled.create(imgClone.size(),imgClone.type();imgLabeled.setTo(Sca