二值圖像的歐拉數計算公式

歐拉數定義

二值圖像分析中歐拉數重要的拓撲特征之一，在圖像分析與幾何對象識別中有著十分重要的作用，二值圖像的歐拉數計算公式表示如下：
E = N – H 其中
E表示計算得到歐拉數
N表示聯(lián)通組件的數目
H表示在聯(lián)通組件內部的洞的數目
下圖是二值圖像，白色背景，兩個對象、分析計算得到歐拉數的例子：

可以看到通過簡單的歐拉數屬性就可以對它們進行區(qū)分。左側對象中有兩個聯(lián)通區(qū)域，所以N=2，沒有洞孔區(qū)域，所以H=0， 計算得到歐拉數目為 2 – 0 = 。右側是大寫字母B，它只有一個聯(lián)通區(qū)域所以N = 1， 內部有兩個洞孔區(qū)域所以H = 2，最終計算得到歐拉數為 2 – 1 = -1。對于任意一個幾何形狀來說，如果我們要求得它的歐拉數，就首先要分析它的輪廓結構，然后根據輪廓層次結構計算得到N與H值。

歐拉數是圖像幾何識別中重要的屬性，舉例如下圖中三個英文字母

?對字母A來說它的內部有一個黑色孔洞，所以它的H=1，其本身是一個聯(lián)通組件所以N =1，最終計算得到歐拉數為 E = 1 -1 = 0，同樣可以計算B與C它們的歐拉數分布為-1與1，可見通過歐拉數屬性可以輕而易舉的區(qū)分ABC三個英文字母。

二：輪廓層次信息獲取

在OpenCV對二值圖像進行輪廓分析輸出的層次結構會保存在一個Vec4i的結構體中，這里有必要首先看一下輪廓發(fā)現API及其相關參數的解釋：

voidcv::findContours(
InputOutputArrayimage,
OutputArrayOfArrayscontours,
OutputArrayhierarchy,
intmode,
intmethod,
Pointoffset=Point()
)
image參數表示輸入的二值圖像
contours表示所有的輪廓信息，每個輪廓是一系列的點集合
hierarchy表示對應的每個輪廓的層次信息，我們就是要用它實現對最大輪廓歐拉數的分析
mode表示尋找輪廓拓撲的方法，如果要尋找完整的層次信息，要選擇參數RETR_TREE
method表示輪廓的編碼方式，一般選擇簡單鏈式編碼，參數CHAIN_APPROX_SIMPLE
offset表示是否有位移，一般默認是0

上面的參數中最重要的是hierarchy信息，它的輸出是vector每個輪廓對應的Vec4i結構體里面四個值解釋如下：

上面的索引如果是負數就表示沒有相關層次信息，如果是非負數就表示有相關的層次關系信息。此外輪廓發(fā)現函數對輸入image圖像的要求必須滿足

• 背景是黑色 ，0表示

• 對象或者前景是白色，1表示

三：歐拉數計算方法

有了輪廓的層次信息與每個輪廓的信息之后，嘗試遍歷每個輪廓，首先通過調用findContours就可以獲取二值圖像的輪廓層次信息，然后遍歷每個輪廓，進行層次遍歷，獲得每層子輪廓的總數，最終根據輪廓層級不同分為孔洞與連接輪廓的計數，二者想減得到每個獨立外層輪廓的歐拉數。

二值化與輪廓發(fā)現的代碼如下：

Matgray,binary;
cvtColor(src,gray,COLOR_BGR2GRAY);
threshold(gray,binary,0,255,THRESH_BINARY|THRESH_OTSU);
vectorhireachy;
vector<vector>contours;
findContours(binary,contours,hireachy,RETR_TREE,CHAIN_APPROX_SIMPLE,Point());

獲取同層輪廓的代碼如下：

vector<int>current_layer_holes(vector<Vec4i>layers,intindex){
intnext=layers[index][0];
vector<int>indexes;
indexes.push_back(index);
while(next>=0){
indexes.push_back(next);
next=layers[next][0];
}
returnindexes;
}

使用隊列迭代尋找遍歷每層的代碼如下：

while(!nodes.empty()){
//當前層總數目
if(index%2==0){//聯(lián)通組件對象
n_total+=nodes.size();
}
else{//孔洞對象
h_total+=nodes.size();
}
index++;
//計算下一層所有孩子節(jié)點
intcurr_ndoes=nodes.size();
for(intn=0;nintvalue=nodes.front();
nodes.pop();
//獲取下一層節(jié)點第一個孩子
intchild=hireachy[value][2];
if(child>=0){
nodes.push(child);
}
}
}

四：運行與測試結果

測試圖一（ABC）與運行結果：

測試圖二與運行結果

五：完整源代碼

#include
#include

usingnamespacecv;
usingnamespacestd;

vector<int>current_layer_holes(vectorlayers,intindex);

intmain(intargc,char**argv){
Matsrc=imread("D:/holes.png");
if(src.empty()){
printf("couldnotloadimage...
");
return-1;
}
namedWindow("input",CV_WINDOW_AUTOSIZE);
imshow("input",src);

Matgray,binary;
cvtColor(src,gray,COLOR_BGR2GRAY);
threshold(gray,binary,0,255,THRESH_BINARY|THRESH_OTSU);

vectorhireachy;
vector<vector>contours;
findContours(binary,contours,hireachy,RETR_TREE,CHAIN_APPROX_SIMPLE,Point());
Matresult=Mat::zeros(src.size(),src.type());
for(size_tt=0;tintnext=hireachy[t][0];//nextatthesamehierarchicallevel
intprev=hireachy[t][1];//prevatthesamehierarchicallevel
intchild=hireachy[t][2];//firstchild
intparent=hireachy[t][3];//parent
printf("next%d,previous%d,children:%d,parent:%d
",next,prev,child,parent);
drawContours(result,contours,t,Scalar(0,255,0),2,8);
//startcalculateeulernumber
inth_total=0;
intn_total=1;
intindex=1;
vector<int>all_children;
if(child>=0&&parent0){
//計算當前層
queue<int>nodes;
vector<int>indexes=current_layer_holes(hireachy,child);
for(inti=0;iwhile(!nodes.empty()){
//當前層總數目
if(index%2==0){//聯(lián)通組件對象
n_total+=nodes.size();
}
else{//孔洞對象
h_total+=nodes.size();
}
index++;
//計算下一層所有孩子節(jié)點
intcurr_ndoes=nodes.size();
for(intn=0;nintvalue=nodes.front();
nodes.pop();
//獲取下一層節(jié)點第一個孩子
intchild=hireachy[value][2];
if(child>=0){
nodes.push(child);
}
}
}
printf("holenumber:%d
",h_total);
printf("connectionnumber:%d
",n_total);
//計算歐拉數
inteuler_num=n_total-h_total;
printf("numberofeuler:%d
",euler_num);
drawContours(result,contours,t,Scalar(0,0,255),2,8);
//顯示歐拉數
Rectrect=boundingRect(contours[t]);
putText(result,format("euler:%d",euler_num),rect.tl(),FONT_HERSHEY_SIMPLEX,1.0,Scalar(255,255,0),2,8);
}
if(child0&&parent0){
printf("holenumber:%d
",h_total);
printf("connectionnumber:%d
",n_total);
inteuler_num=n_total-h_total;
printf("numberofeuler:%d
",euler_num);
drawContours(result,contours,t,Scalar(255,0,0),2,8);
Rectrect=boundingRect(contours[t]);
putText(result,format("euler:%d",euler_num),rect.tl(),FONT_HERSHEY_SIMPLEX,1.0,Scalar(255,255,0),2,8);
}

}

imshow("result",result);
waitKey(0);
return0;
}

vector<int>current_layer_holes(vectorlayers,intindex){
intnext=layers[index][0];
vector<int>indexes;
indexes.push_back(index);
while(next>=0){
indexes.push_back(next);
next=layers[next][0];
}
returnindexes;
}

PS:代碼未經更多嚴格測試，僅供參考！

審核編輯 ：李倩