漫水填充:也就是用一定顏色填充聯通區域,通過設置可連通像素的上下限以及連通方式來達到不同的填充效果;漫水填充經常被用來標記或分離圖像的一部分以便對其進行進一步處理或分析,也可以用來從輸入圖像獲取掩碼區域,掩碼會加速處理過程,或只處理掩碼指定的像素點,操作的結果總是某個連續的區域。
種子填充算法是從多邊形區域內部的一點開始,由此出發找到區域內的所有像素。
種子填充算法采用的邊界定義是區域邊界上所有像素具有某個特定的顏色值,區域內部所有像素均不取這一特定顏色,而邊界外的像素則可具有與邊界相同的顏色值。
具體算法步驟:
當然在搜索的時候有兩種檢測相鄰像素:四向連通和八向連通。四向連通即從區域上一點出發,通過四個方向上、下、左、右來檢索。而八向連通加上了左上、左下、右上、右下四個方向。這種算法的有點是算法簡單,易於實現,也可以填充帶有內孔的平面區域。但是此算法需要更大的存儲空間以實現棧結構,同一個像素多次入棧和出棧,效率低,運算量大。
該算法屬於種子填充算法,它是以掃描線上的區段為單位操作。所謂區段,就是一條掃描線上相連著的若干內部象素的集合。掃描線種子填充算法思想:首先填充當前掃描線上的位於給定區域的一區段,然後確定於這一區段相鄰的上下兩條線上位於該區域內是否存在需要填充的新區段,如果存在,則依次把他們保存起來,反復這個過程,直到所保存的各區段都填充完畢。
借助於堆棧,上述算法實現步驟如下:
初始化堆棧。
種子壓入堆棧。
while(堆棧非空){
從堆棧彈出種子象素。
如果種子象素尚未填充,則:
求出種子區段:xleft、xright;
填充整個區段。
檢查相鄰的上掃描線的xleft <= x <= xright區間內,是否存在需要填充的新區段,如果存在的話,則把每個新區段在xleft <= x <= xright范圍內的最右邊的象素,作為新的種子象素依次壓入堆棧。
檢查相鄰的下掃描線的xleft <= x <= xright區間內,是否存在需要填充的新區段,如果存在的話,則把每個新區段在xleft <= x <= xright范圍內的最右邊的象素,作為新的種子象素依次壓入堆棧。
}
原算法中, 種子雖然代表一個區段, 但種子實質上仍是一個象素, 我們必須在種子出棧的時候計算種子區段, 而這裡有很大一部分計算是重復的. 而且, 原算法的掃描過程如果不用mask的話, 每次都會重復掃描父種子區段所在的掃描線, 而用mask的話又會額外增加開銷。所以, 對原算法的一個改進就是讓種子攜帶更多的信息, 讓種子不再是一個象素, 而是一個結構體. 該結構體包含以下信息: 種子區段的y坐標值, 區段的x開始與結束坐標, 父種子區段的方向(上或者下), 父種子區段的x開始與結束坐標.
struct seed{
int y,
int xleft,
int xright,
int parent_xleft,
int parent_xright,
bool is_parent_up
};
這樣算法的具體實現變動如下
初始化堆棧.
將種子象素擴充成為種子區段(y, xleft, xright, xright+1, xrihgt, true), 填充種子區段, 並壓入堆棧. (這裡有一個構造父種子區段的技巧)
while(堆棧非空){
從堆棧彈出種子區段。
檢查父種子區段所在的掃描線的xleft <= x <= parent_xleft和parent_xright <= x <= xright兩個區間, 如果存在需要填充的新區段, 則將其填充並壓入堆棧.
檢查非父種子區段所在的掃描線的xleft <= x <= xright區間, 如果存在需要填充的新區段, 則將其填充並壓入堆棧.
}
另外, opencv裡的種子填充算法跟以上方法大致相同, 不同的地方是opencv用了隊列不是堆棧, 而且是由固定長度的數組來實現的循環隊列, 其固定長度為 max(img_width, img_height)*2. 並且push與pop均使用宏來實現而沒有使用函數. 用固定長度的數組來實現隊列(或堆棧)意義是顯然的, 能大大減少構造結構, 復制結構等操作, 可以大大提高效率.
//漫水法填充標定實現
//像素值
unsigned char pixel;
Seed *Seeds; //種子堆棧及指針
int StackPoint;
int iCurrentPixelx,iCurrentPixely; //當前像素位置
Seeds = new Seed[iWidth*iLength]; //分配種子空間
//計算每個標定值的像素個數
int count[251];
for(i=1;i<252;i++){
count[i]=0; //初始化為0
}
//濾波的阈值
int yuzhi = 700;
for (i=0;i<iWidth;i++) {
for (j=0;j<iLength;j++) {
if (grey_liantong.GetPixel(i,j)==0){ //當前像素為黑,對它進行漫水法標定
//初始化種子
Seeds[1].x = i;
Seeds[1].y = j;
StackPoint = 1;
while( StackPoint != 0){
//取出種子
iCurrentPixelx = Seeds[StackPoint].x;
iCurrentPixely = Seeds[StackPoint].y;
StackPoint--;
//取得當前指針處的像素值,注意要轉換為unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely);
//將當前點標定
grey_liantong.SetPixel(iCurrentPixelx,iCurrentPixely,flag);
count[flag]++; //標定像素計數
//判斷左面的點,如果為黑,則壓入堆棧
//注意防止越界
if(iCurrentPixelx > 1){
//取得當前指針處的像素值,注意要轉換為unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx-1,iCurrentPixely);
if (pixel == 0){
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely;
Seeds[StackPoint].x = iCurrentPixelx - 1;
}
}
//判斷上面的點,如果為黑,則壓入堆棧
//注意防止越界
if(iCurrentPixely < iLength - 1)
{
//取得當前指針處的像素值,注意要轉換為unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely+1);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely + 1;
Seeds[StackPoint].x = iCurrentPixelx;
}
}
//判斷右面的點,如果為黑,則壓入堆棧
//注意防止越界
if(iCurrentPixelx < iWidth - 1)
{
//取得當前指針處的像素值,注意要轉換為unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx+1,iCurrentPixely);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely;
Seeds[StackPoint].x = iCurrentPixelx + 1;
}
}
//判斷下面的點,如果為黑,則壓入堆棧
//注意防止越界
if(iCurrentPixely > 1)
{
//取得當前指針處的像素值,注意要轉換為unsigned char型
pixel = (unsigned char)grey_liantong.GetPixel(iCurrentPixelx,iCurrentPixely-1);
if (pixel == 0)
{
StackPoint++;
Seeds[StackPoint].y = iCurrentPixely - 1;
Seeds[StackPoint].x = iCurrentPixelx;
}
}
}//end while( StackPoint != 0)
flag = (flag + 7)%251+1; //當前點連通區域標定後,改變標定值
}//end if
}//end for(i
}//end for(j
//釋放堆棧
delete Seeds;
grey_res.Clone(grey_liantong);