基于改進(jìn)型像素標(biāo)記算法的目標(biāo)定位
2012-04-12 00:00:00宋南趙晶
現(xiàn)代電子技術(shù) 2012年5期
摘 要：提出新的像素標(biāo)記算法，與以前的像素標(biāo)記算法不同，該算法首先對目標(biāo)點(diǎn)進(jìn)行分類，然后根據(jù)不同的標(biāo)記規(guī)則對不同的目標(biāo)點(diǎn)進(jìn)行標(biāo)記。該算法不僅在算法復(fù)雜度上有所減少，只需一次掃描就能完成目標(biāo)的描述，而且能夠得到目標(biāo)的面積、重心和邊界坐標(biāo)等信息。該算法已經(jīng)應(yīng)用于帶鋼表面缺陷檢測，具有快速、準(zhǔn)確等特點(diǎn)。
關(guān)鍵詞：圖像處理; 二值圖像; 像素標(biāo)記; 目標(biāo)定位
中圖分類號：
TN911.7334; TP317.4
文獻(xiàn)標(biāo)識碼：A
文章編號：1004373X(2012)05
0052
03
Objective orientation based on improved pixel mark algorithm
SONG Nan1， ZHAO Jing2
(1.Beijing Information Science and Technology University， Beijing 100101，China； 2.Xi’an University of Technology， Xi’an 710048， China)
Abstract：
A novel pixel mark algorithm is proposed and the algorithm is different. The novel algorithm frist classified the objective，and then marked different target according to different mark rules. The novel algorithm not only decreased the algorithm complexity， accomplished description of objective only one time， and gained the target area， center of gravity and boundary coordinates and other information. The algorithm has been used in the strip surface defects detection，and has the characteristics of fast speed and accuracy.
Keywords： image processing; binary image; pixel mark;objective orientation
收稿日期：20111021
基金項(xiàng)目：國家自然科學(xué)基金(61072151)；陜西省自然科學(xué)基金(2009JQ8007)
0 引 言
對二值圖像中連通區(qū)域進(jìn)行標(biāo)記有兩種比較實(shí)用的方法:像素標(biāo)記算法\\[1\\]和游程連通性算法。游程連通性分析法是通過分析由連續(xù)掃描線得到的游程連通性來標(biāo)記目標(biāo)的方法。其條件是在掃描前已經(jīng)形成了灰度相同的像素塊即游程。像素標(biāo)記算法與游程連通算法不同的是，它不需要事先對圖像進(jìn)行處理，就可以對二值圖像進(jìn)行標(biāo)記，過程極為簡便。考慮到實(shí)時(shí)性要求，本文只對像素標(biāo)記法進(jìn)行了研究。
近年來出現(xiàn)了一些改進(jìn)的像素標(biāo)記算法如擴(kuò)展像素標(biāo)記算法\\[2\\]、帶標(biāo)記校正的像素標(biāo)記算法\\[3\\]、快速目標(biāo)描述方法\\[4\\]、一種改進(jìn)的二值圖像的象素標(biāo)記算法\\[5\\]、基于遞歸的二值圖像連通域像素標(biāo)記算法\\[6\\]、帶標(biāo)記矯正的二值圖象連通域像素標(biāo)記算法\\[3\\]、一種基于鏈表的二值圖像像素標(biāo)記改進(jìn)算法\\[7\\]、基于等價(jià)對的圖像連通域標(biāo)記算法\\[8\\]、一種圖像分割的快速目標(biāo)描述方法 \\[4\\]。擴(kuò)展像素標(biāo)記算法需要進(jìn)行兩次掃描才能完成。帶標(biāo)記校正的像素標(biāo)記算法對包含向上分叉的圖形不能在一次掃描中完成標(biāo)記。快速目標(biāo)描述方法借用像素標(biāo)記的思想確定目標(biāo)的邊界，但其算法較復(fù)雜，得到的目標(biāo)特征信息較少。本文提出的算法只需要對圖像進(jìn)行一次掃描就能完成目標(biāo)的描述，對于復(fù)雜形狀的目標(biāo)也能正確處理。通過存儲目標(biāo)中像素的坐標(biāo)，不僅達(dá)到了像素標(biāo)記的目的，而且得到目標(biāo)的面積、重心和邊界坐標(biāo)等信息。該算法已經(jīng)用VC實(shí)現(xiàn)，用于帶鋼表面缺陷檢測。
1 典型的像素標(biāo)記算法
下面介紹典型的像素標(biāo)記算法。在對圖像進(jìn)行分割以后，得到了一幅二值圖像，為了檢測不同的目標(biāo)區(qū)域，需要對灰度值為1的像素點(diǎn)進(jìn)行標(biāo)記，然后檢查鄰近像素間的連通性，將具有連通關(guān)系的像素點(diǎn)合并到同一個(gè)目標(biāo)區(qū)域。考慮8連通的情況，根據(jù)以上建立的概念可按如下方法對圖像進(jìn)行標(biāo)記：對圖像逐像素掃描，假如當(dāng)前像素的灰度值為0，就移到下一個(gè)掃描位置。假如當(dāng)前像素的灰度值是1，檢查它左方、上方、左上和右上和四個(gè)近鄰像素(根據(jù)所采用的掃描次序，當(dāng)掃描到達(dá)當(dāng)前像素時(shí)這四個(gè)近鄰像素已被處理過了)。這四個(gè)像素灰度值和標(biāo)記的組合中有四種情況要考慮:
(1) 它們的灰度值都是0，給當(dāng)前像素一個(gè)新的標(biāo)記(根據(jù)已有信息，直到目前這是該連通區(qū)域第一次被掃描到)；
(2) 它們中間只有一個(gè)灰度值為1，把該像素的標(biāo)記賦給當(dāng)前像素；
(3) 它們的灰度值都為1且具有相同的標(biāo)記，就將該標(biāo)記賦給當(dāng)前像素；
(4) 它們的灰度值都為1但具有不同的標(biāo)記，就將其中的一個(gè)標(biāo)記賦給當(dāng)前像素并做個(gè)記號表明這兩個(gè)標(biāo)記等價(jià)。
在掃描終結(jié)時(shí)所有灰度值為1的點(diǎn)都已有了標(biāo)記但有些標(biāo)記可能是等價(jià)的。此時(shí)所需做的就是將所有等價(jià)的標(biāo)記對結(jié)合，對各個(gè)對賦一個(gè)不同的標(biāo)記。然后第2次掃描圖像，將每個(gè)標(biāo)記用它所在等價(jià)對的標(biāo)記代替。
2 改進(jìn)的像素標(biāo)記算法
本文提出了一種改進(jìn)型像素標(biāo)記方法，該算法使像素標(biāo)記在單次掃描中完成，而且能夠得到目標(biāo)的面積、重心以及邊界坐標(biāo)。在掃描之前，首先對圖像進(jìn)行擴(kuò)展，使圖像中的每個(gè)點(diǎn)都具有完整的8鄰域。對于二值圖像中的目標(biāo)點(diǎn)，分成三種情況：第一種是開始點(diǎn)，它的左方、左上、上方、右上的點(diǎn)均為0；第二種是內(nèi)部點(diǎn)，它左方的點(diǎn)為1；第三種是邊界點(diǎn)，它左方的點(diǎn)為0，但其左上，上方，右上至少有一個(gè)點(diǎn)為1。
為了說明像素標(biāo)記的過程，首先定義如下數(shù)據(jù)類型：
m：當(dāng)前像素點(diǎn)的行坐標(biāo)，n：當(dāng)前像素點(diǎn)的列坐標(biāo)；
E(m，n)：當(dāng)前掃描像素點(diǎn)灰度值；
S(m，n)：當(dāng)前像素點(diǎn)的目標(biāo)標(biāo)記；
Br(S(m，n))：當(dāng)前像素所屬標(biāo)記的等效標(biāo)記；
MS(m，n) (m，n)：M用來存儲目標(biāo)標(biāo)記S(m， n)中像素點(diǎn)的坐標(biāo)；
為了說明改進(jìn)型像素標(biāo)記算法的標(biāo)記流程，首先介紹三種點(diǎn)的標(biāo)記規(guī)則和有效目標(biāo)標(biāo)記的定義。
(1) 開始點(diǎn)標(biāo)記規(guī)則
當(dāng)遇到一個(gè)開始點(diǎn)時(shí)，將其標(biāo)記記為1，同時(shí)等效標(biāo)記也為1，將該點(diǎn)的坐標(biāo)存入數(shù)組M1中。后面開始點(diǎn)的標(biāo)記依次加1。
(2) 內(nèi)部點(diǎn)標(biāo)記規(guī)則
若當(dāng)前點(diǎn)為內(nèi)部點(diǎn)，該點(diǎn)的標(biāo)記記S(m，n)等于S(m，n-1)，并將該點(diǎn)的坐標(biāo)記入數(shù)組MS(m，n )。進(jìn)一步判斷，若上方為0，右上方為1，且右上方標(biāo)記的等效標(biāo)記和當(dāng)前點(diǎn)的標(biāo)記不同，就令右上方點(diǎn)標(biāo)記的等效標(biāo)記Br(S(m-1，n+1))等于S(m，n)，并將數(shù)組MS(m-1，n+1)并入數(shù)組MS(m，n )。
(3) 邊界點(diǎn)標(biāo)記規(guī)則
首先判斷該點(diǎn)左上方是否為1，若為1，則當(dāng)前點(diǎn)的標(biāo)記S(m，n)等于S(m-1，n-1)。并將當(dāng)前點(diǎn)的坐標(biāo)寫入數(shù)組MS(m，n )。進(jìn)一步判斷，若正上方為0且右上方點(diǎn)均為1，則令右上方點(diǎn)標(biāo)記的等效標(biāo)記Br(S(m-1，n+1))等于S(m，n)，并將數(shù)組MS(m-1，n+1)并入數(shù)組MS(m，n )。
若左上方為0，正上方為1，則當(dāng)前點(diǎn)標(biāo)記S(m，n)等于S(m-1，n)，并將當(dāng)前點(diǎn)的坐標(biāo)寫入數(shù)組MS(m，n )。
若左上方為0，正上方為0，右上方為1，則當(dāng)前點(diǎn)標(biāo)記S(m，n)等于S(m-1，n+1)，并將當(dāng)前點(diǎn)的坐標(biāo)寫入數(shù)組MS(m，n )。
(4) 有效目標(biāo)標(biāo)記的定義
對圖像掃描完成后，找出那些沒有被合并的標(biāo)記，即自身的標(biāo)記號與它的等效標(biāo)記相同，這些標(biāo)記的存儲數(shù)組M中存儲了屬于該標(biāo)記的所有點(diǎn)的坐標(biāo)，根據(jù)這些坐標(biāo)就可以計(jì)算出目標(biāo)的邊界、重心和面積。
該算法只用一次掃描就能達(dá)到像素標(biāo)記的目的，而且三種目標(biāo)點(diǎn)有各自的標(biāo)記規(guī)則，這些規(guī)則定義了像素標(biāo)記和標(biāo)記合并的原則，在掃描完后，要判斷哪些標(biāo)記是有效標(biāo)記，哪些標(biāo)記被合并，同時(shí)計(jì)算出有效標(biāo)記的邊界、重心和面積。
3 改進(jìn)的像素標(biāo)記法驗(yàn)證
為了驗(yàn)證算法的有效性，本文對復(fù)雜圖形的目標(biāo)標(biāo)記過程進(jìn)行了分析，圖1給出了一個(gè)復(fù)雜圖形實(shí)例，該圖形包含了二值圖像中會遇到的大部分情況。
圖1 復(fù)雜圖形實(shí)例
下面就對圖1中圖形的像素標(biāo)記過程進(jìn)行說明：
(1) 從第一行進(jìn)行掃描，像素點(diǎn)(1，3)滿足開始點(diǎn)的要求，令其目標(biāo)標(biāo)記為1，同時(shí)目標(biāo)標(biāo)記1的等效標(biāo)記為1，將該點(diǎn)的坐標(biāo)存入M1中。像素點(diǎn)(1，14)滿足開始點(diǎn)的要求，令其目標(biāo)標(biāo)記為2，同時(shí)目標(biāo)標(biāo)記2的等效標(biāo)記為2，將該點(diǎn)的坐標(biāo)存入M2中。
(2) 對第二行進(jìn)行掃描，像素點(diǎn)(2，3)的標(biāo)記與(1，3)點(diǎn)相同，同時(shí)將該點(diǎn)坐標(biāo)存入M1中。像素點(diǎn)(2，5)是一個(gè)開始點(diǎn)，令其目標(biāo)標(biāo)記為3，同時(shí)目標(biāo)標(biāo)記3的等效標(biāo)記為3，將該點(diǎn)坐標(biāo)存入M3中，后面的像素做類似的處理。點(diǎn)(2，14)屬于標(biāo)記2。
(3) 對第三行進(jìn)行掃描，根據(jù)邊界點(diǎn)的標(biāo)記規(guī)則，點(diǎn)(3，3)、(3，6)、(3，9)、(3，14)分別屬于標(biāo)記1，3，2。
(4) 對第四行進(jìn)行掃描，像素點(diǎn)(4，1)滿足開始點(diǎn)的要求，因此開始一個(gè)新的標(biāo)記4，并令其等效標(biāo)記為4，在點(diǎn)(4，2)處，目標(biāo)標(biāo)記1合并入目標(biāo)標(biāo)記4，使目標(biāo)標(biāo)記1的等效標(biāo)記指向4。在帶點(diǎn)(4，5)處，目標(biāo)標(biāo)記3合并入目標(biāo)標(biāo)記4，目標(biāo)3的等效標(biāo)記指向4。從(4，9)開始的點(diǎn)屬于目標(biāo)4。點(diǎn)(3，14)屬于目標(biāo)2。
(5) 第五行的點(diǎn)(5，4)、(5，9)、(5，11)均屬于目標(biāo)4，點(diǎn)(5，14)屬于目標(biāo)2。
(6) 第六行的點(diǎn)(6，2)滿足開始點(diǎn)的要求，開始一個(gè)新的標(biāo)志5，并令其等效標(biāo)志為5，在點(diǎn)(6，3)處，目標(biāo)標(biāo)記4并入目標(biāo)標(biāo)記5，使目標(biāo)4的等效標(biāo)記為5，同時(shí)目標(biāo)1和3的等效標(biāo)記為4，故使目標(biāo)1和3的等效標(biāo)記指向5。在點(diǎn)(6，8)處由于目標(biāo)4的等效標(biāo)記指向5，不做合并，在點(diǎn)(6，13)處，目標(biāo)2并入目標(biāo)5，目標(biāo)2的等效標(biāo)記指向5，點(diǎn)(6，15)屬于目標(biāo)5。
(7) 根據(jù)標(biāo)記規(guī)則，點(diǎn)(7，5)和點(diǎn)(7，13)屬于目標(biāo)5。
(8) 在點(diǎn)(8，1)處開始了一個(gè)新標(biāo)記6，其等效標(biāo)記為6，在點(diǎn)(8，4)處，目標(biāo)5并入目標(biāo)6，同時(shí)目標(biāo)5的等效標(biāo)記為6，考慮到目標(biāo)1，2，3，4的等效標(biāo)記為5，這里使它們的等效標(biāo)記指向6，在點(diǎn)(8，12)處由于目標(biāo)5的等效標(biāo)記為6，故不做合并。
(9) 查看這六個(gè)標(biāo)記的等效標(biāo)記，只有第六個(gè)標(biāo)記的等效標(biāo)記與它自身序號相等，故圖中只包含一個(gè)目標(biāo)。
前面介紹了改進(jìn)型像素標(biāo)記算法，并分析了其有效性。下面采用本文提出的算法和輪廓跟蹤算法、像素標(biāo)記算法，分別對圖2所示帶鋼圖像中的三個(gè)缺陷進(jìn)行定位，圖像大小為768×280像素。
從表1，表2可以看出，三種方法找到的目標(biāo)邊界
坐標(biāo)完全一樣，而改進(jìn)型像素標(biāo)記算法的處理速度更快，在有實(shí)時(shí)性要求的條件下該算法更有優(yōu)勢。在缺陷區(qū)域定位之后，根據(jù)目標(biāo)邊界坐標(biāo)就可以從原圖中提取缺陷區(qū)域圖像。
4 結(jié) 論
本文算法不僅在實(shí)時(shí)性上有優(yōu)勢，復(fù)雜度有所減小，而且通過實(shí)驗(yàn)證明在圖像的缺陷區(qū)域定位之后，根據(jù)目標(biāo)邊界坐標(biāo)就可以從原圖中提取缺陷區(qū)域的圖像。
參 考 文 獻(xiàn)
［1］章毓晉.圖像分割［M］.北京：科學(xué)出版社，2001.
［2］張新宇，劉廣智，李建勛，等.一種圖像分割的目標(biāo)描述方法及實(shí)現(xiàn)［J］.系統(tǒng)工程與電子技術(shù)，2003，25(2):219222.
［3］張修軍，郭霞，金心宇.帶標(biāo)記矯正的二值圖像連通域像素標(biāo)記算法［J］.中國圖象圖形學(xué)報(bào)，2003，8(2):198202.
［4］張慶，向健勇，趙小明，等.一種圖像分割的快速目標(biāo)描述方法［J］.紅外技術(shù)，2004，26(6):8385.
［5］王亮，黃飛，馮少彤，等.一種改進(jìn)的二值圖像像素標(biāo)記算法［J］.南京師范大學(xué)學(xué)報(bào):工程技術(shù)版，2006，6(2):2325.
［6］徐正光，鮑東來，張利欣.基于遞歸的二值圖像連通域像素標(biāo)記算法［J］.人工智能及識別技術(shù)，2006，32(24):186188.
［7］李偉，何強(qiáng).一種基于鏈表的二值圖像像素標(biāo)記改進(jìn)算法［J］.科技風(fēng)，2008(14)：5556.
［8］左敏，曾廣平，涂序彥，等.基于等價(jià)對的圖像連通域標(biāo)記算法［J］.計(jì)算機(jī)仿真，2011(1)：1416.
