bwlabel算法_bwlabel函数的c++实现
實驗中需要用到區域聯通的算法，就是類似于matlab中bwlabel的函數。網上找了找c++源碼未果，bwlabel-python版用python描述了matlab中的實現方法，但是最后對標簽的處理部分并未看明白，故自己用c++實現了一個。先直接看bwlabel函數代碼：
cv::Mat bwlabel(const cv::Mat in, int * num, const intmode)
{const int num_runs = number_of_runs(in);int * sc = new int[num_runs];int * ec = new int[num_runs];int * r = new int[num_runs];int * labels = new int[num_runs];
memset(labels,0, sizeof(int)*num_runs);
fill_run_vectors(in, sc, ec, r);
first_pass(sc, ec, r, labels, num_runs, mode);
cv::Mat result= cv::Mat::zeros(in.size(), CV_8UC1);int number = 0;for(int i = 0; i < num_runs; i++)
{
uchar* p_row = result.ptr(r[i]);for(int j = sc[i]; j <= ec[i]; j++)
p_row[j]=labels[i];if(number
number=labels[i];
}if(num !=NULL)*num =number;
delete [] sc;
delete [] ec;
delete [] r;
delete [] labels;returnresult;
}
bwlabel中要用到三個輔助函數：number_of_runs，fill_run_vectors，first_pass。函數number_of_runs計算每一行中非零像素團的個數并累加起來。
1 1 0 0 0 1 1 1 0 0
比如，上面這一行就有2個非零像素團，我們稱這樣的像素團為Run，函數number_of_runs實現如下：
int number_of_runs(const cv::Mat in)
{const int rows = in.rows;const int cols = in.cols;int result = 0;for(int row = 0; row < rows; row++)
{const uchar * p_row = in.ptr(row);if(p_row[0] != 0)
result++;for(int col = 1; col < cols; col++)
{if(p_row[col] != 0 && p_row[col-1] == 0)
result++;
}
}returnresult;
}
這個函數算法思想是，掃描每一行，對每一行，如果當前元素非零并且前一元素為零則Run的個數加一。
函數fill_run_vectors的作用是填充三個數據結構：sc[],ec[],r[]，它們分別表示開始列標、結束列標和行標，數組長度為由number_of_runs函數得到的Run的個數。函數fill_run_vectors實現如下：
void fill_run_vectors(const cv::Mat in, int sc[], int ec[], intr[])
{const int rows = in.rows;const int cols = in.cols;int idx = 0;for(int row = 0; row < rows; row++)
{const uchar * p_row = in.ptr(row);int prev = 0;for(int col = 0; col < cols; col++)
{if(p_row[col] !=prev)
{if(prev == 0)
{
sc[idx]=col;
r[idx]=row;
prev= 1;
}else{
ec[idx++] = col - 1;
prev= 0;
}
}if(col == cols-1 && prev == 1)
{
ec[idx++] =col;
}
}
}
}
算法思想還是遍歷每一行，用變量prev保存一行中上一個團是0還是1，如果出現01跳變那么就要記錄下新的Run的開始列標和行標，如果出現10跳變(或者這行結束并且prev=1)那么就記錄下這個Run的結束列標。
函數first_pass顧名思義，字面上說第一次掃描。因為函數掃描每一個Run塊，給它打標簽。當出現如下情況時：
1 1 0 0 1 1 1 0
0 1 1 1 1 0 0 0
函數給第一行第一個Run打上標簽1，第二個Run打上標簽2，當遍歷到第二行時，發現這一行的一個Run與第一行第一個Run相鄰，故打上標簽1，但當繼續遍歷時發現這個Run也與第一行第二個Run相鄰，但函數并沒有改變第一行第二個Run的標簽，而是記錄下這兩個標簽其實該一樣。遍歷完第二行結果為：
1 1 0 0 2 2 2 0
0 1 1 1 1 0 0 0
遍歷完每一個Run過后就是處理剛才未處理的標簽了。函數first_pass實現如下：
void first_pass(const int sc[], const int ec[], const int r[],int labels[], const int num_runs, const intmode)
{int cur_row = 0;int next_label = 1;int first_run_on_prev_row = -1;int last_run_on_prev_row = -1;int first_run_on_this_row = 0;int offset = 0;int * equal_i = new int[num_runs];int * equal_j = new int[num_runs];int equal_idx = 0;if(mode == 8)
offset= 1;for(int k = 0; k < num_runs; k++)
{if(r[k] == cur_row + 1)
{
cur_row+= 1;
first_run_on_prev_row=first_run_on_this_row;
first_run_on_this_row=k;
last_run_on_prev_row= k - 1;
}else if(r[k] > cur_row + 1)
{
first_run_on_prev_row= -1;
last_run_on_prev_row= -1;
first_run_on_this_row=k;
cur_row=r[k];
}if(first_run_on_prev_row >= 0)
{int p =first_run_on_prev_row;while(p <= last_run_on_prev_row && sc[p] <= (ec[k] +offset))
{if(sc[k] <= ec[p] +offset)
{if(labels[k] == 0)
labels[k]=labels[p];else if(labels[k] !=labels[p])
{//labels[p] = labels[k];
equal_i[equal_idx] =labels[k];
equal_j[equal_idx]=labels[p];
equal_idx+= 1;
}
}
p+= 1;
}
}if(labels[k] == 0)
{
labels[k]= next_label++;
}
}/// process labels
for(int i = 0; i < equal_idx; i++)
{int max_label = equal_i[i] > equal_j[i] ?equal_i[i] : equal_j[i];int min_label = equal_i[i] < equal_j[i] ?equal_i[i] : equal_j[i];for(int j = 0; j < num_runs; j++)
{if(labels[j] ==max_label)
labels[j]=min_label;
}
}
delete [] equal_i;
delete [] equal_j;/process ignore labels
int * hist = new int[next_label];int * non_labels = new int[next_label];
memset(hist,0, sizeof(int)*next_label);int non_num = 0;for(int i = 0; i < num_runs; i++)
{
hist[labels[i]]++;
}for(int i = 1; i < next_label; i++)
{if(hist[i] == 0)
non_labels[non_num++] =i;
}for(int j = 0; j < num_runs; j++)
{int k =labels[j];for(int i = non_num-1; i >= 0; i--)
{if(k >non_labels[i])
{
labels[j]-= (i+1);break;
}
}
}
delete [] hist;
delete [] non_labels;
}
前面遍歷每一個Run分兩種情況，上一行有Run和上一行無Run：當上一行無Run時就分配一個新的標簽，當上一行有Run時還要考慮是否與上一行Run相鄰，若相鄰則打上上一行的標簽，當出現上面講到的情況時就保存這兩個標簽到數組equal_i,equal_j中。
接下來就是處理equal_i和equal_j這兩個數組了，要將它們當中相同族的不同標簽合并到一起(注釋process labels下面代碼)。
這樣過后還不能完事，有可能出現標簽間斷的現象(如1，2，4，6)，就是還必須把標簽(如1，2，4，6)映射到一個連續的空間(1，2，3，4)。參見注釋process ignore labels以下代碼。
這樣過后就差不多了，最后一步是在bwlabel中給返回的Mat中元素打上對應的標簽。
總結
以上是生活随笔為你收集整理的bwlabel算法_bwlabel函数的c++实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： echarts迁徙图 vue_【可视化插
- 下一篇： 方差为什么用平方不用绝对值_为什么炖鸡汤