泛洪填充(Flood Fill)很多時(shí)候國內(nèi)的開發(fā)者稱它為漫水填充，該算法在圖形填充與著色應(yīng)用程序比較常見，屬于標(biāo)配。在圖像處理里對(duì)二值圖像的Hole可以通過泛洪填充來消除，這個(gè)是泛洪填充在圖像處理中很經(jīng)典的一個(gè)用途，此外還可以通過泛洪填充為ROI區(qū)域著色。這個(gè)在圖像處理也經(jīng)常用到。讓我們首先看一下泛洪填充算法本身，然后再說一下在圖像處理中的應(yīng)用場(chǎng)景。

泛洪填充算法

通常泛洪填充需要從一個(gè)點(diǎn)開始，這個(gè)點(diǎn)可以隨機(jī)選擇的一點(diǎn)，但是一定要在填充區(qū)域內(nèi)部，然后它就會(huì)進(jìn)行四鄰域或者把鄰域?qū)ふ覍?duì)周圍像素完成填充，直到遇到跟指定隨機(jī)點(diǎn)像素值不同的像素為止，也可以認(rèn)為是到達(dá)了區(qū)域邊界。通過鄰域像素尋找實(shí)現(xiàn)填充速度比較慢、不是泛洪填充好的實(shí)現(xiàn)方式，最常見與快速的泛紅實(shí)現(xiàn)是基于掃描線算法的，步驟如下：

1.首先從開始點(diǎn)出發(fā)進(jìn)行垂直方向列的掃描，填充

2.然后以填充點(diǎn)開始進(jìn)行每一行的掃描與填充

3.繼續(xù)以每一行新填充的像素為開始點(diǎn)，執(zhí)行1,2步驟

4.直到區(qū)域所有點(diǎn)都完成填充為止。

圖示如下：

第一步：假設(shè)有圖像如下，紅色表種子像素點(diǎn)。

首先進(jìn)行豎直方向的掃描，填充結(jié)果如下：

然后以填充的紅色像素為起始點(diǎn)，開始水平方向的掃描填充，結(jié)果如下：

用水平方向被填充像素點(diǎn)為種子像素點(diǎn)，繼續(xù)豎直方式掃描填充，結(jié)果如下：

以填充的像素點(diǎn)為種子像素點(diǎn)繼續(xù)水平方向掃描，結(jié)果如下：

這樣就完成了對(duì)整個(gè)區(qū)域的填充。從上面的例子可以看出，泛洪填充可以通過遞歸方式編碼實(shí)現(xiàn)，但是基于遞歸方式編碼實(shí)現(xiàn)有個(gè)致命的缺點(diǎn)，對(duì)大圖填充時(shí)候容易導(dǎo)致棧溢出，所以更常用的基于隊(duì)列或者棧的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)非遞歸的泛洪填充。OpenCV中的實(shí)現(xiàn)主要是基于棧的掃描線算法實(shí)現(xiàn)泛洪填充。

應(yīng)用場(chǎng)景一：

通過泛洪填充算法實(shí)現(xiàn)對(duì)二值圖像對(duì)象區(qū)域中Hole填充

運(yùn)行顯示原圖如下：

填充以后結(jié)果如下：

實(shí)現(xiàn)代碼如下：

應(yīng)用場(chǎng)景二：

通過泛洪填充實(shí)現(xiàn)對(duì)ROI區(qū)域的著色， 跟上個(gè)例子使用API唯一不同地方是帶了mask參數(shù)。運(yùn)行結(jié)果如下：

實(shí)現(xiàn)代碼如下：

編輯：jq