搬以前寫的博客【2014-03-01 08:09】
圖像連通域標記算法研究?ConnectedComponent?Labeling? ? ? ? ? ? ? ??
最近在研究一篇復雜下背景文字檢測的論文。
“Detecting?Text?in?Natural?Scenes?with?Stroke?Width?Transform?”?CPVR?2010的文章，它主要探討利用文字內部筆畫寬度一致作為主要線索來檢測文字的一個新奇的算法，當然，我不是想討論文字檢測，論文算法實施的過程中有一步涉及到圖像連通域標記算法，在這里我遇到了一些問題，查閱了一些相關文章，所以想分享一下。
數字圖像處理中有介紹到過連通域的概念，簡單來說就是圖像中一片顏色近似一致的區域，準確說是某一片區域中的任何一個像素都與該區域的其他的一個或幾個像素8連通（或4連通），連通是指兩個像素相鄰并且某些屬性相同（狹義上是灰度值，廣義上可以像素所具備的各種屬性，我看的論文里屬性就是指像素所在筆畫的筆畫寬度），那么把這些相同的區域做上統一的標記是我們經常要做的事，研究這一類問題的算法我們就稱其連通域標記算法，連通域標記是最基本的圖像處理算法之一。
關于這一類問題，先說說我的想法。
想法一：
第一次了解這個問題的時候，看的是維基百科上關于這個的介紹，全英文嘛沒看太懂，但是看懂了一部分，于是出現了我的第一種時間效率極其差的辦法：
1.逐行掃描，對除了邊界像素的每一個像素（邊界像素特殊處理）作分析，分析它的左、左上、上、右上鄰居：
（1）如果本像素的屬性與其他四個鄰居中每一個鄰居的屬性都不同（例如都不是一個灰度級別，再如筆畫寬度不在同一個區間范圍），那么區域號加1，并把這個新的區域號標記本像素的區域號；
（2）如果只和其中某一個鄰居屬性相同，那么把鄰居的區域號標記本像素區域號
（3）如果和多個鄰居屬性相同，但是鄰居的區域號又各有不同，那么說明了不同鄰居雖然區域號不同，但是他們其實是在同一個連通域中，只不過沒有掃描到本像素之前，他們并未匯合，所以這里就要統一他們的區域號，這里需要掃描所有的已經標記過的像素，把其中標記的區域號和本像素的鄰居們區域號相同的那些像素群的區域號全部統一為其中最小的那個值，同時本像素標記也設為那個值。
2.重復1直到所有點全部掃描完成，最后可以得到一個大小和圖像一樣大的區域號map，區域號map的值是圖像中對應位置的像素所在的區域號。
這樣下來，經過一遍掃描之后，各個連通域的區域號已經設定出來，但是會出現不是區域號1,2,3,4,5。。。這樣，而可能是1,3,4,6,9。。。這樣。??時間復雜度上是O（n^2），n為圖像像素的個數。
當然這種算法跑下來時間很久，一張640*480的圖需要3分鐘（當然是matlab我內部還有許多其他的判定和執行過程）。
想法二：
當然不能就此就這樣了，我需要跑200多張圖片，一張3分鐘。。。所以得改進，重新看了維基百科和一部分介紹二值圖像連通域標記算法的論文，發現原來他們講的是掃描兩遍的思想，于是借鑒了他們的想法：
1.還是從上至下逐行掃描，如果遇到想法一里面的（1）（2）兩種情況，方法不變，如果遇到第三種情況，不像想法一中那樣傻傻的再掃描一次統一賦值，而是把這些鄰居的區域號碼作為一個對記錄到等價關系表equal中，equal（i）=【xi?yi】表明區域號為xi,yi的區域是在同一片連通域中，并且在等價表中第i行。那么這里時間復雜度是O（n），
2.把等價關系表先簡化，除去重復的部分，再從表做樹形檢索：
從表的equal（1）開始，在表中搜索滿足x1∈equal（i）或者y1∈equal（i）的i的集合，再對集合中每一個i繼續做檢索直到表中和x1,y1有等價關系的區域號全部被找到。記錄下這些區域號，把這些區域號對應的像素，全部統一，從表中刪去這些對。重復對表做這樣的樹形檢索，直到每一對都被掃描到，表最后為空，結束，這里的時間復雜度又是O(n)，但是用到遞歸調用，會占據大量的空間，matlab跑竟然報out?of?memory=?=。
想法三：
http://www.cnblogs.com/tiandsp/archive/2012/12/06/2804922.html
這個是網上看到的，同樣是兩步計算，大同小異，但是比傳統的兩步標記簡單一些，不是等價對，而是等價序列，遞歸的過程更簡單清楚，里面關于算法里面并查集?的介紹很好
想法四：
C：http://blog.stevenwang.name/connected-component-labeling-rg-545001.html
Matlab：http://www.cnblogs.com/tiandsp/archive/2012/12/06/2805276.html
同樣是這位老兄推薦的別人的方法，區域生長法，簡單高效,O(n)復雜度，實測很快
最后還是借鑒的想法四的思想，畢竟速度快，看來以后得多看一些算法方面的書了。
的時間復雜度)
)
