轉自https://www.cnblogs.com/ronny/p/img_aly_01.html。侵删。記錄下基于行程的标記算法。
一、前言
二值圖像,顧名思義就是圖像的亮度值隻有兩個狀态:黑(0)和白(255)。二值圖像在圖像分析與識别中有着舉足輕重的地位,因為其模式簡單,對像素在空間上的關系有着極強的表現力。在實際應用中,很多圖像的分析最終都轉換為二值圖像的分析,比如:醫學圖像分析、前景檢測、字元識别,形狀識别。二值化+數學形态學能解決很多計算機識别工程中目标提取的問題。
二值圖像分析最重要的方法就是連通區域标記,它是所有二值圖像分析的基礎,它通過對二值圖像中白色像素(目标)的标記,讓每個單獨的連通區域形成一個被辨別的塊,進一步的我們就可以擷取這些塊的輪廓、外接矩形、質心、不變矩等幾何參數。
下面是一個二值圖像被标記後,比較形象的顯示效果,這就是我們這篇文章的目标。
二、連通域
在我們讨論連通區域标記的算法之前,我們先要明确什麼是連通區域,怎樣的像素鄰接關系構成連通。在圖像中,最小的機關是像素,每個像素周圍有8個鄰接像素,常見的鄰接關系有2種:4鄰接與8鄰接。4鄰接一共4個點,即上下左右,如下左圖所示。8鄰接的點一共有8個,包括了對角線位置的點,如下右圖所示。
如果像素點A與B鄰接,我們稱A與B連通,于是我們不加證明的有如下的結論:
如果A與B連通,B與C連通,則A與C連通。
在視覺上看來,彼此連通的點形成了一個區域,而不連通的點形成了不同的區域。這樣的一個所有的點彼此連通點構成的集合,我們稱為一個連通區域。
下面這符圖中,如果考慮4鄰接,則有3個連通區域;如果考慮8鄰接,則有2個連通區域。(注:圖像是被放大的效果,圖像正方形實際隻有4個像素)。
三、連通區域的标記
連通區域标記算法有很多種,有的算法可以一次周遊圖像完成标記,有的則需要2次或更多次周遊圖像。這也就造成了不同的算法時間效率的差别,在這裡我們介紹2種算法。
第一種算法是現在matlab中連通區域标記函數bwlabel中使的算法,它一次周遊圖像,并記下每一行(或列)中連續的團(run)和标記的等價對,然後通過等價對對原來的圖像進行重新标記,這個算法是目前我嘗試的幾個中效率最高的一個,但是算法裡用到了稀疏矩陣與Dulmage-Mendelsohn分解算法用來消除等價對,這部分原理比較麻煩,是以本文裡将不介紹這個分解算法,取而代這的用圖的深度優先周遊來替換等價對。
第二種算法是現在開源庫cvBlob中使用的标記算法,它通過定位連通區域的内外輪廓來标記整個圖像,這個算法的核心是輪廓的搜尋算法,這個我們将在文章中詳細介紹。這個算法相比與第一種方法效率上要低一些,但是在連通區域個數在100以内時,兩者幾乎無差别,當連通區域個數到了103103數量級時,上面的算法會比該算法快10倍以上。
四、基于行程的标記
我們首先給出算法的描述,然後再結合實際圖像來說明算法的步驟。
1,逐行掃描圖像,我們把每一行中連續的白色像素組成一個序列稱為一個團(run),并記下它的起點start、它的終點end以及它所在的行号。
2,對于除了第一行外的所有行裡的團,如果它與前一行中的所有團都沒有重合區域,則給它一個新的标号;如果它僅與上一行中一個團有重合區域,則将上一行的那個團的标号賦給它;如果它與上一行的2個以上的團有重疊區域,則給目前團賦一個相連團的最小标号,并将上一行的這幾個團的标記寫入等價對,說明它們屬于一類。
3,将等價對轉換為等價序列,每一個序列需要給一相同的标号,因為它們都是等價的。從1開始,給每個等價序列一個标号。
4,周遊開始團的标記,查找等價序列,給予它們新的标記。
5,将每個團的标号填入标記圖像中。
6,結束。
我們來結合一個三行的圖像說明,上面的這些操作。
第一行,我們得到兩個團:[2,6]和[10,13],同時給它們标記1和2。
第二行,我們又得到兩個團:[6,7]和[9,10],但是它們都和上一行的團有重疊區域,是以用上一行的團标記,即1和2。
第三行,兩個:[2,4]和[7,8]。[2,4]這個團與上一行沒有重疊的團,是以給它一個新的記号為3;而[2,4]這個團與上一行的兩個團都有重疊,是以給它一個兩者中最小的标号,即1,然後将(1,2)寫入等價對。
全部圖像周遊結束,我們得到了很多個團的起始坐标,終止坐标,它們所在的行以及它們的标号。同時我們還得到了一個等價對的清單。
下面我們用C++實作上面的過程,即步驟2,分兩個進行:
1)fillRunVectors函數完成所有團的查找與記錄;
void fillRunVectors(const Mat& bwImage, int& NumberOfRuns, vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun)
{
for (int i = 0; i < bwImage.rows; i++)
{
const uchar* rowData = bwImage.ptr<uchar>(i);
if (rowData[0] == 255)
{
NumberOfRuns++;
stRun.push_back(0);
rowRun.push_back(i);
}
for (int j = 1; j < bwImage.cols; j++)
{
if (rowData[j - 1] == 0 && rowData[j] == 255)
{
NumberOfRuns++;
stRun.push_back(j);
rowRun.push_back(i);
}
else if (rowData[j - 1] == 255 && rowData[j] == 0)
{
enRun.push_back(j - 1);
}
}
if (rowData[bwImage.cols - 1])
{
enRun.push_back(bwImage.cols - 1);
}
}
}
2)firstPass函數完成團的标記與等價對清單的生成。相比之下第二個函數要稍微難了解一些。
void firstPass(vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun, int NumberOfRuns,
vector<int>& runLabels, vector<pair<int, int>>& equivalences, int offset)
{
runLabels.assign(NumberOfRuns, 0);
int idxLabel = 1;
int curRowIdx = 0;
int firstRunOnCur = 0;
int firstRunOnPre = 0;
int lastRunOnPre = -1;
for (int i = 0; i < NumberOfRuns; i++)
{
if (rowRun[i] != curRowIdx)
{
curRowIdx = rowRun[i];
firstRunOnPre = firstRunOnCur;
lastRunOnPre = i - 1;
firstRunOnCur = i;
}
for (int j = firstRunOnPre; j <= lastRunOnPre; j++)
{
if (stRun[i] <= enRun[j] + offset && enRun[i] >= stRun[j] - offset && rowRun[i] == rowRun[j] + 1)
{
if (runLabels[i] == 0) // 沒有被标号過
runLabels[i] = runLabels[j];
else if (runLabels[i] != runLabels[j])// 已經被标号
equivalences.push_back(make_pair(runLabels[i], runLabels[j])); // 儲存等價對
}
}
if (runLabels[i] == 0) // 沒有與前一列的任何run重合
{
runLabels[i] = idxLabel++;
}
}
}
接下來是我們的重點,即等價對的處理,我們需要将它轉化為若幹個等價序列。比如有如下等價對:
(1,2),(1,6),(3,7),(9-3),(8,1),(8,10),(11,5),(11,8),(11,12),(11,13),(11,14),(15,11)
我們需要得到最終序列是:
list1:list1:1-2-5-6-8-10-11-12-13-14-15
list2:list2:3-7-9
list3:list3:4
一個思路是将1-15個點都看成圖的結點,而等價對(1,2)說明結點1與結點2之間有通路,而且形成的圖是無向圖,即(1,2)其實包含了(2,1)。我們需要周遊圖,找出其中的所有連通圖。是以我們采用了圖像深入優先周遊的原理,進行等價序列的查找。
從結點1開始,它有3個路徑1-2,1-6,1-8。2和6後面都沒有路徑,8有2條路徑通往10和11,而10沒有後續路徑,11則有5條路徑通往5,12,13,14,15。等價表1查找完畢。
第2條等價表從3開始,則隻有2條路徑通向7和9,7和9後面無路徑,等價表2查找完畢。
最後隻剩下4,它沒有在等價對裡出現過,是以單兒形成一個序列(這裡假設步驟2中團的最大标号為15)。
下面是這個過程的C++實作,每個等價表用一個vector<int>來儲存,等價對清單儲存在map<pair<int,int>>裡。
void replaceSameLabel(vector<int>& runLabels, vector<pair<int, int>>&
equivalence)
{
if (equivalence.size() != NULL)
{
int maxLabel = *max_element(runLabels.begin(), runLabels.end());
vector<vector<bool>> eqTab(maxLabel, vector<bool>(maxLabel, false));
vector<pair<int, int>>::iterator vecPairIt = equivalence.begin();
while (vecPairIt != equivalence.end())
{
eqTab[vecPairIt->first - 1][vecPairIt->second - 1] = true;
eqTab[vecPairIt->second - 1][vecPairIt->first - 1] = true;
vecPairIt++;
}
vector<int> labelFlag(maxLabel, 0);
vector<vector<int>> equaList;
vector<int> tempList;
cout << maxLabel << endl;
for (int i = 1; i <= maxLabel; i++)
{
if (labelFlag[i - 1])
{
continue;
}
labelFlag[i - 1] = equaList.size() + 1;
tempList.push_back(i);
for (vector<int>::size_type j = 0; j < tempList.size(); j++)
{
for (vector<bool>::size_type k = 0; k != eqTab[tempList[j] - 1].size(); k++)
{
if (eqTab[tempList[j] - 1][k] && !labelFlag[k])
{
tempList.push_back(k + 1);
labelFlag[k] = equaList.size() + 1;
}
}
}
equaList.push_back(tempList);
tempList.clear();
}
cout << equaList.size() << endl;
for (vector<int>::size_type i = 0; i != runLabels.size(); i++)
{
runLabels[i] = labelFlag[runLabels[i] - 1];
}
}
}
寫了一個 函數進行輔助,這個函數同時完成了 畫出不同的連通域的功能
void Drawcontours(Mat & src,vector<int>& runLabels, vector<int>& stRun, vector<int>& enRun, vector<int>& rowRun)
{
int RunsNumber = *max_element(runLabels.begin(), runLabels.end());// 連通域個數
vector<int> Scolor;
int color = 255 / RunsNumber;
for (int i = 1; i <= RunsNumber; i++)
{
Scolor.push_back(color*i);
}
/*for (auto i : Scolor)
{
cout << i << endl;
}*/
Mat dst = Mat::zeros(src.size(), CV_8UC1);
for (size_t i = 0; i < rowRun.size(); i++)
{
uchar *dst_rowData = dst.ptr<uchar>(rowRun[i]);//指向第一個 白條所在的行
for (size_t j = 0; j < dst.cols; j++)
{
if (j >= stRun[i] && j <= enRun[i])
{
dst_rowData[j] = (Scolor[runLabels[i] - 1]);
}
}
}
imshow("dst", dst);
}
五、基于輪廓的标記
在這裡我還是先給出算法描述:
1,從上至下,從左至右依次周遊圖像。
2,如下圖A所示,A為遇到一個外輪廓點(其實上周遊過程中第一個遇到的白點即為外輪廓點),且沒有被标記過,則給A一個新的标記号。我們從A點出發,按照一定的規則(這個規則後面詳細介紹)将A所在的外輪廓點全部跟蹤到,然後回到A點,并将路徑上的點全部标記為A的标号。
3,如下圖B所示,如果遇到已經标記過的外輪廓點A′A′,則從A′A′向右,将它右邊的點都标記為A′A′的标号,直到遇到黑色像素為止。
4,如下圖C所示,如果遇到了一個已經被标記的點B,且是内輪廓的點(它的正下方像素為黑色像素且不在外輪廓上),則從B點開始,跟蹤内輪廓,路徑上的點都設定為B的标号,因為B已經被标記過與A相同,是以内輪廓與外輪廓将标記相同的标号。
5,如下圖D所示,如果周遊到内輪廓上的點,則也是用輪廓的标号去标記它右側的點,直到遇到黑色像素為止。
6,結束。
整個算法步驟,我們隻掃描了一次圖像,同時我們對圖像中的像素進行标記,要麼賦予一個新的标号,要麼用它同行的左邊的标号去标記它,下面是算法更詳細的描述:
對于一個需要标記的圖像II,我們定義一個與它對應的标記圖像LL,用來儲存标記資訊,開始我們把L上的所有值設定為0,同時我們有一個标簽變量CC,初始化為1。然後我們開始掃描圖像I,遇到白色像素時,設這個點為PP點,我們需要按下面不同情況進行不同的處理:
情況1:如果P(i,j)P(i,j)點是一個白色像素,在LL圖像上這個位置沒有被标記過,而且PP點的上方為黑色,則P是一個新的外輪廓的點,這時候我們将C的标簽值标記給L圖像上P點的位置(x,y)(x,y),即L(x,y)=CL(x,y)=C,接着我們沿着P點開始做輪廓跟蹤,并把把輪廓上的點對應的L上都标記為C,完成整個輪廓的搜尋與标記後,回到了P點。最後不要忘了把C的值加1。這個過程如下面圖像S1中所示。
情況2:如果P點的下方的點是unmarked點(什麼是unmark點,情況3介紹完就會給出定義),則P點一定是内輪廓上的點,這時候有兩種情況,一種是P點在L上已經被标記過了,說明這個點同時也是外輪廓上的點;另一種情況是P點在L上還沒有被标記過,那如果是按上面步驟來的,P點左邊的點一定被标記了(這一處剛開始了解可能不容易,不妨畫一個簡單的圖,自己試着一個點一個點标記試試,就容易了解了),是以這時候我們采用P點左邊點的标記值來标記P,接着從P點開始跟蹤内輪廓把内輪廓上的點都标記為P的标号。
下面圖像顯示了上面分析的兩種P的情況,左圖的P點既是外輪廓上的點也是内輪廓上的點。
情況3:如果一個點P,不是上面兩種情況之一,那麼P點的左邊一定被标記過(不了解,就手動去标記上面兩幅圖像),我們隻需要用它左邊的标号去标記L上的P點。
現在我們隻剩下一個問題了,就是什麼是unmarked點,我們知道内輪廓點開始點P的下方一定是一個黑色像素,是不是黑色像素就是unmarked點呢,顯然不是,如下圖像的Q點,它的下面也是黑色像素,然而它卻不是内輪廓上的點。
實際上在我們在輪廓跟蹤時,我們我輪廓點的周圍做了标記,在輪廓點周圍被查找過的點(查找方式見下面的輪廓跟蹤算法)在L上被标記了一個負值(如下面右圖所示),是以Q點的下方被标記為了負值,這樣Q的下方就不是一個unmarked點,unmarked點,即在L上的标号沒有被修改過,即為0。
顯然,這個算法的重點在于輪廓的查找與标記,而對于輪廓的查找,就是确定搜尋政策的問題,我們下面給内輪廓與外輪廓定義tracker規則。
我們對一點像素點周圍的8個點分析作一個标号0-7,因為我們在周遊圖像中第一個遇到的點肯定是外輪廓點,是以我們先來确定外輪廓的搜尋政策,對于外輪廓的點P,有兩種情況:
1)如果P是外輪廓的起點,也就是說我們是從P點開始跟蹤的,那麼我們從7号(右上角)位置P1P1開始,看7号是不是白色點,如果是,則把這個點加入外輪廓點中,并将它标記與P點相同,如果7号點是黑色點,則按順時針7-0-1-2-3-4-5-6這個順序搜尋直到遇到白點為止,把那個點确定為P1P1,加入外輪廓,并把這個點的标号設定與P點相同。這裡很重要一步就是,假設我們2号點才是白點,那麼7,0,1這三個位置我們都搜尋過,是以我們要把這些點在L上标記為一個負值。如下圖所示,其中右圖像标記的結果。
2)那麼如果P是不是外輪廓的起點,即P是外輪廓路徑上的一個點,那麼它肯定是由一個點進入的,我們設定為P−1P−1點,P−1P−1點的位置為x(0<=x<=7)x(0<=x<=7),那麼P點從(x+2)mod8(x+2)mod8這個位置開始尋找下一步的路徑,(x+2)mod8(x+2)mod8是加2取模的意思,它反映在圖像就是從P-1點按順時針數2個格子的位置。确定搜尋起點後,按照上面一種情況進行下面的步驟。
外輪廓點的跟蹤方式确定了後,内輪廓點的跟蹤方式大同小異,隻是如果P是内輪廓的第一個點,則它的開始搜尋位置不是7号點而是3号點。其他的與外輪廓完全一緻。
如要上面搜尋方式,你不是很直覺的了解,不妨嘗試着去搜尋下面這幅圖像,你應該有能有明确的了解了。一個路徑搜尋結束的條件是,回到原始點S,則S周圍不存在unmarked點。
如下邊中間圖像所示,從S點開始形成的路徑是STUTSVWV。
在OpenCV中查找輪廓的函數已經存在了,而且可以得到輪廓之間的層次關系。這個函數按上面的算法實作起來并不困難,是以這裡就不再實作這個函數,有興趣的可以看OpenCV的源碼(contours.cpp)。
void bwLabel(const Mat& imgBw, Mat & imgLabeled)
{
// 對圖像周圍擴充一格
Mat imgClone = Mat(imgBw.rows + 1, imgBw.cols + 1, imgBw.type(), Scalar(0));
imgBw.copyTo(imgClone(Rect(1, 1, imgBw.cols, imgBw.rows)));
imgLabeled.create(imgClone.size(), imgClone.type());
imgLabeled.setTo(Scalar::all(0));
vector<vector<Point>> contours;
vector<Vec4i> hierarchy;
findContours(imgClone, contours, hierarchy, CV_RETR_CCOMP, CV_CHAIN_APPROX_NONE);
vector<int> contoursLabel(contours.size(), 0);
int numlab = 1;
// 标記外圍輪廓
for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++)
{
if (hierarchy[i][3] >= 0) // 有父輪廓
{
continue;
}
for (vector<Point>::size_type k = 0; k != contours[i].size(); k++)
{
imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = numlab;
}
contoursLabel[i] = numlab++;
}
// 标記内輪廓
for (vector<vector<Point>>::size_type i = 0; i < contours.size(); i++)
{
if (hierarchy[i][3] < 0)
{
continue;
}
for (vector<Point>::size_type k = 0; k != contours[i].size(); k++)
{
imgLabeled.at<uchar>(contours[i][k].y, contours[i][k].x) = contoursLabel[hierarchy[i][3]];
}
}
// 非輪廓像素的标記
for (int i = 0; i < imgLabeled.rows; i++)
{
for (int j = 0; j < imgLabeled.cols; j++)
{
if (imgClone.at<uchar>(i, j) != 0 && imgLabeled.at<uchar>(i, j) == 0)
{
imgLabeled.at<uchar>(i, j) = imgLabeled.at<uchar>(i, j - 1);
}
}
}
imgLabeled = imgLabeled(Rect(1, 1, imgBw.cols, imgBw.rows)).clone(); // 将邊界裁剪掉1像素
}