二值圖像的歐拉數(shù)計(jì)算公式

歐拉數(shù)定義

二值圖像分析中歐拉數(shù)重要的拓?fù)涮卣髦?，在圖像分析與幾何對(duì)象識(shí)別中有著十分重要的作用，二值圖像的歐拉數(shù)計(jì)算公式表示如下：
E = N – H 其中
E表示計(jì)算得到歐拉數(shù)
N表示聯(lián)通組件的數(shù)目
H表示在聯(lián)通組件內(nèi)部的洞的數(shù)目
下圖是二值圖像，白色背景，兩個(gè)對(duì)象、分析計(jì)算得到歐拉數(shù)的例子：

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

歐拉數(shù)是圖像幾何識(shí)別中重要的屬性，舉例如下圖中三個(gè)英文字母

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

二：輪廓層次信息獲取

在OpenCV對(duì)二值圖像進(jìn)行輪廓分析輸出的層次結(jié)構(gòu)會(huì)保存在一個(gè)Vec4i的結(jié)構(gòu)體中，這里有必要首先看一下輪廓發(fā)現(xiàn)API及其相關(guān)參數(shù)的解釋：

voidcv::findContours(
InputOutputArrayimage,
OutputArrayOfArrayscontours,
OutputArrayhierarchy,
intmode,
intmethod,
Pointoffset=Point()
)
image參數(shù)表示輸入的二值圖像
contours表示所有的輪廓信息，每個(gè)輪廓是一系列的點(diǎn)集合
hierarchy表示對(duì)應(yīng)的每個(gè)輪廓的層次信息，我們就是要用它實(shí)現(xiàn)對(duì)最大輪廓?dú)W拉數(shù)的分析
mode表示尋找輪廓拓?fù)涞姆椒ǎ绻獙ふ彝暾膶哟涡畔?，要選擇參數(shù)RETR_TREE
method表示輪廓的編碼方式，一般選擇簡(jiǎn)單鏈?zhǔn)骄幋a，參數(shù)CHAIN_APPROX_SIMPLE
offset表示是否有位移，一般默認(rèn)是0

上面的參數(shù)中最重要的是hierarchy信息，它的輸出是vector每個(gè)輪廓對(duì)應(yīng)的Vec4i結(jié)構(gòu)體里面四個(gè)值解釋如下：

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

• 背景是黑色 ，0表示

• 對(duì)象或者前景是白色，1表示

三：歐拉數(shù)計(jì)算方法

有了輪廓的層次信息與每個(gè)輪廓的信息之后，嘗試遍歷每個(gè)輪廓，首先通過(guò)調(diào)用findContours就可以獲取二值圖像的輪廓層次信息，然后遍歷每個(gè)輪廓，進(jìn)行層次遍歷，獲得每層子輪廓的總數(shù)，最終根據(jù)輪廓層級(jí)不同分為孔洞與連接輪廓的計(jì)數(shù)，二者想減得到每個(gè)獨(dú)立外層輪廓的歐拉數(shù)。

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

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;
}

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

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

四：運(yùn)行與測(cè)試結(jié)果

測(cè)試圖一（ABC）與運(yùn)行結(jié)果：

測(cè)試圖二與運(yùn)行結(jié)果

五：完整源代碼

#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){
//計(jì)算當(dāng)前層
queue<int>nodes;
vector<int>indexes=current_layer_holes(hireachy,child);
for(inti=0;iwhile(!nodes.empty()){
//當(dāng)前層總數(shù)目
if(index%2==0){//聯(lián)通組件對(duì)象
n_total+=nodes.size();
}
else{//孔洞對(duì)象
h_total+=nodes.size();
}
index++;
//計(jì)算下一層所有孩子節(jié)點(diǎn)
intcurr_ndoes=nodes.size();
for(intn=0;nintvalue=nodes.front();
nodes.pop();
//獲取下一層節(jié)點(diǎn)第一個(gè)孩子
intchild=hireachy[value][2];
if(child>=0){
nodes.push(child);
}
}
}
printf("holenumber:%d
",h_total);
printf("connectionnumber:%d
",n_total);
//計(jì)算歐拉數(shù)
inteuler_num=n_total-h_total;
printf("numberofeuler:%d
",euler_num);
drawContours(result,contours,t,Scalar(0,0,255),2,8);
//顯示歐拉數(shù)
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:代碼未經(jīng)更多嚴(yán)格測(cè)試，僅供參考！

審核編輯 ：李倩