連通域的原理與Python實現(xiàn)
向AI轉(zhuǎn)型的程序員都關(guān)注了這個號???
機器學習AI算法工程?? 公眾號：datayx
二值圖像連通域
二值圖像分析最基礎的也是最重要的方法之一就是連通域標記，它是所有二值圖像分析的基礎。它通過對二值圖像中目標像素的標記，讓每個單獨的連通區(qū)域形成一個被標識的塊，進一步的我們就可以獲取這些塊的輪廓、外接矩形、質(zhì)心、不變矩等幾何參數(shù)。
連通區(qū)域的定義一般有兩種，分為4鄰接和8鄰接。下面這幅圖中，如果考慮4鄰接，則有3個連通域，8鄰接則是2個連通域。
從連通區(qū)域的定義可以知道，一個連通域是由具有相同像素值的相鄰像素組成像素集合，因此，我們就可以通過這兩個條件在圖像中尋找連通區(qū)域，對于找到的每個連通域，我們賦予其一個唯一的標識（ Label ），以區(qū)別其他連通域。
連通域分析的基本算法有兩種：1) Two-Pass 兩遍掃描 2) Seed-Filling 種子填充法。
Two-Pass 算法
兩遍掃描法（ Two-Pass ），正如其名，指的就是通過掃描兩遍圖像，將圖像中存在的所有連通域找出并標記。
另外，我在代碼實現(xiàn)的過程中想到另外一種 Two-Pass 的方式
(即掃描兩遍圖像的方式)實現(xiàn)，就是第二次掃描與 (1) 同樣的過程,
只是方向換成從右下到左上。
我后面的 Two-Pass 代碼是使用我自己想到的方法實現(xiàn)的，
自己使用了幾個例子測試了下，目前沒出現(xiàn)啥問題。
Seed-Filling 算法
種子填充方法來源于計算機圖形學，常用于對某個圖形進行填充。它基于區(qū)域生長算法。我的理解就是遞歸遍歷。
附上兩種方法的 Python 的實現(xiàn)
python驗證碼識別教程之利用投影法、連通域法分割圖片
接下來文章主要記錄一下如何切分驗證碼，用到的主要庫就是Pillow和Linux下的圖像處理工具GIMP。首先假設一個固定位置和寬度、無粘連、無干擾的例子學習一下如何使用Pillow來切割圖片。
使用GIMP打開圖片后，按 加號 放大圖片，然后點擊View->Show Grid來顯示網(wǎng)格線：
其中，每個正方形邊長為10像素，所以數(shù)字1切割坐標為左20、上20、右40、下70。以此類推可以知道剩下3個數(shù)字的切割位置。
代碼如下：
那么，如果字符位置不固定怎么辦呢？現(xiàn)在假設一種隨機位置寬度、無粘連、無干擾線的情況。
第一種方法，也是最簡單的方法叫做”投影法”。原理就是將二值化后的圖片在豎直方向進行投影，根據(jù)投影后的極值來判斷分割邊界。這里我依然使用上面的驗證碼圖片來進行演示：
通過vertical函數(shù)我們就得到了一個包含所有黑色像素在X軸上投影后左右邊界的位置。由于驗證碼沒有任何干擾，所以我的閾值設定為0。
所以對于簡單粘連的情況，調(diào)整閾值也是可以解決的。
第二種方法，叫做CFS連通域分割法。原理就是假定每個字符都由一個單獨的連通域組成，換言之就是無粘連，找到一個黑色像素并開始判斷，直到所有相連的黑色像素都被遍歷標記過后即可判斷出這個字符的分割位置。算法如下：
將二值化后的圖片進行從左到右、從上到下的遍歷，如果遇到黑色像素并且這個像素沒有沒訪問過，就將這個像素入棧并標記為已經(jīng)訪問。
如果棧不為空，則繼續(xù)探測周圍8個像素，并執(zhí)行第2步；如果?？?，則代表探測完了一個字符塊。
探測結(jié)束，這樣就確定了若干字符。
代碼如下：
調(diào)用后輸出結(jié)果和使用投影法是一樣的。另外我看網(wǎng)上還有一種叫做“泛洪填充(Flood Fill)”的方法，似乎和連通域是一樣的。
參考文章
https://zhuanlan.zhihu.com/p/97689424
https://www.jb51.net/article/141434.htm
閱讀過本文的人還看了以下文章：
基于40萬表格數(shù)據(jù)集TableBank，用MaskRCNN做表格檢測
《深度學習入門：基于Python的理論與實現(xiàn)》高清中文PDF+源碼
python就業(yè)班學習視頻，從入門到實戰(zhàn)項目
2019最新《PyTorch自然語言處理》英、中文版PDF+源碼
《21個項目玩轉(zhuǎn)深度學習：基于TensorFlow的實踐詳解》完整版PDF+附書代碼
PyTorch深度學習快速實戰(zhàn)入門《pytorch-handbook》
【下載】豆瓣評分8.1,《機器學習實戰(zhàn):基于Scikit-Learn和TensorFlow》
《Python數(shù)據(jù)分析與挖掘?qū)崙?zhàn)》PDF+完整源碼
汽車行業(yè)完整知識圖譜項目實戰(zhàn)視頻(全23課)
李沐大神開源《動手學深度學習》，加州伯克利深度學習（2019春）教材
筆記、代碼清晰易懂！李航《統(tǒng)計學習方法》最新資源全套！
《神經(jīng)網(wǎng)絡與深度學習》最新2018版中英PDF+源碼
重要開源！CNN-RNN-CTC 實現(xiàn)手寫漢字識別
【Keras】完整實現(xiàn)‘交通標志’分類、‘票據(jù)’分類兩個項目，讓你掌握深度學習圖像分類
VGG16遷移學習，實現(xiàn)醫(yī)學圖像識別分類工程項目
特征工程(二) :文本數(shù)據(jù)的展開、過濾和分塊
如何利用全新的決策樹集成級聯(lián)結(jié)構(gòu)gcForest做特征工程并打分？
Machine Learning Yearning 中文翻譯稿
斯坦福CS230官方指南：CNN、RNN及使用技巧速查（打印收藏）
python+flask搭建CNN在線識別手寫中文網(wǎng)站
中科院Kaggle全球文本匹配競賽華人第1名團隊-深度學習與特征工程
不斷更新資源
深度學習、機器學習、數(shù)據(jù)分析、python
?搜索公眾號添加：?datayx??
機大數(shù)據(jù)技術(shù)與機器學習工程
?搜索公眾號添加：?datanlp
長按圖片，識別二維碼