一種圖像粒標記模型及其實現(xiàn)

李仲生,黃同成,蔡則蘇

(1.邵陽學院信息工程系,湖南邵陽422000;2.哈爾濱工業(yè)大學計算機科學與技術(shù)學院,哈爾濱150001)

一種圖像粒標記模型及其實現(xiàn)

李仲生1,黃同成1,蔡則蘇2

(1.邵陽學院信息工程系,湖南邵陽422000;2.哈爾濱工業(yè)大學計算機科學與技術(shù)學院,哈爾濱150001)

針對圖像分析領域缺乏可擴展的基礎模型,對灰度圖和彩圖的標記模型展開研究。通過分析粗糙集和商空間理論的適用性,綜合圖像標記處理的特定應用需求,引出概念粒和連通粒2個概念,構(gòu)建粒標記模型?；谕ǔＧ闆r下圖像尤其是彩圖標記中粒的數(shù)量巨大、結(jié)構(gòu)復雜等現(xiàn)狀,定義行連通段、潛在連通范圍,引入動態(tài)預設標記集,簡化連通判定,給出實現(xiàn)粒標記模型的線性算法,即圖像粒標記算法。用二值圖和彩圖分別作驗證和對比分析,結(jié)果表明,該標記算法有效、精確,且較傳統(tǒng)標記算法更高速。

行連通段;連通粒;概念粒;圖像處理;粒標記模型;圖像粒標記算法

1 概述

已全面普及的圖像攝制設備,迅猛發(fā)展的物聯(lián)網(wǎng),使得圖像的數(shù)量爆炸式增長,給基于內(nèi)容的圖像檢索帶來了巨大的挑戰(zhàn)。為加速圖像的檢索速度和精度,圖像處理領域涌現(xiàn)出了一系列研究熱點,例如顯著對象提取、圖像的語義標注等。分析這些熱點方向產(chǎn)出的研究文獻發(fā)現(xiàn):處理的初始區(qū)域(或稱基元)為全圖、規(guī)則區(qū)域或某種圖像分割結(jié)果。對于圖像中潛在的語義對象而言,全圖和規(guī)則區(qū)域與它除非碰巧相符(如一個圖像中僅一個對象或一個對象正好和規(guī)則區(qū)域一樣),否則沒對應性。使用某種圖像分割結(jié)果為基元與潛在對象間可能產(chǎn)生對應性,但處理速度會因為要分割圖像而慢下來。因此,為進一步加快圖像處理的精度和速度,尋找一種能與人類的思維方式有一致性、與潛在的語義對象有對

應性的基元是必要的,有益的。

粒計算(Granular Computing,GrC)是一個近些年來才凸現(xiàn)出的研究領域,是人工智能領域中的一種模擬人類思考和解決復雜問題的新理念和新方法［1］。這種模擬性使得粒計算理論對數(shù)據(jù)隱含語義的把握有著獨具一格的能力,催生出了各具特色的眾多成果。文獻［2］提出了一種基于粒計算和云模型的彩色圖像分割算法。文獻［3］在文獻［2］的基礎上作了進一步的探索。文獻［4］用粗糙集實現(xiàn)圖像分割,文獻［5］提出了一種粗糙集與mPCA相結(jié)合的人臉識別算法。文獻［6］提出了一種基于模糊集的圖像壓縮技術(shù)。文獻［7］利用粗糙集尋找區(qū)域語義分類。文獻［8］述及了大量基于粒計算的研究成果,并展示了粒計算在圖像處理領域的深入研究前景。這些成果涉及面廣,對底層數(shù)據(jù)的隱含語義把握到位,可惜一般只針對特定應用,未形成簡潔、高效和易于擴展的基礎模型,因而難以被持續(xù)深入拓展和泛化、推廣。針對這種情況,為表達出與語義對象有對應性的基元,給出基元生成的基礎平臺,本文參照粒計算理論,以粒作為基元,構(gòu)建并實現(xiàn)一種圖像粒標記模型。

2 圖像粒計算模型

圖像粒標記模型作為一種將二值圖標記技術(shù)推廣到一般圖像(包括彩圖)的基礎平臺,可用于顯著對象發(fā)現(xiàn)、圖像語義標注等幾乎所有圖像處理領域。

粒計算理論中的粗糙集理論模型［9］和商空間理論模型雖類似于孿生兄弟,但在具體應用中各有側(cè)重:粗糙集理論主要用于表達數(shù)據(jù)、發(fā)現(xiàn)規(guī)則,而商空間理論常用于分析具有偏序(半序)關(guān)系的對象集問題。本文綜合兩者的優(yōu)勢,根據(jù)圖像處理的特點,定義圖像粒標記模型如下:

定義2(不可分辨關(guān)系,概念粒) 不可分辨關(guān)系是由任意屬性子集B?A確定的一種二值關(guān)系,定義如下:

上述關(guān)系是容錯關(guān)系。用不可分辨關(guān)系劃分論域,將不可分辨的對象歸入一類,得概念粒。概念粒的合集記為{AG［i］|i=1,2,…,n}(n為總數(shù)),滿足以下約束:

定義3(連通關(guān)系,連通粒) 依據(jù)給定任意拓撲屬性子集T?P,用式(3)判定連通關(guān)系:

上文首先定義了拓撲信息系統(tǒng),接著給出了其上的一種粒的統(tǒng)一形式化描述及對應約束,完成了圖像粒標記模型的構(gòu)建。下面依據(jù)圖像粒標記模型,設計論證連通粒的獲取和標記算法。

3 圖像粒標記算法

3.1 圖像連通區(qū)的標記

圖像連通區(qū)標記是計算機視覺、圖像理解、模式識別等領域中的基礎工作之一。它賦給每個連通區(qū)一個唯一的標記,借此把圖像轉(zhuǎn)換成符號圖,完成標記。標記研究目前只針對二值圖或灰度圖,已有大量研究成果。標記形成的方式上,這些成果可分為2類:(1)基于標記等價的算法,如文獻［13］算法等,此類算法要做2輪或多輪光柵式掃描,由預設標記生成代表標記,完成后,再在最末一輪掃描中用代表標記替換相應的預設標記,完成標記;(2)基于搜索和擴展的算法,尋找一個未標記的前景點,賦予一個標記號,然后將此標記號擴展到所有與之連通的前景點,完成標記。

現(xiàn)有連通區(qū)標記算法存在局限性:只針對N×N或N×M的規(guī)則圖,不適合標記任意形狀、任意分布的連通區(qū)域;不能標記彩圖;標記的結(jié)果為符號圖,未提取記錄各連通區(qū),與圖像中潛在對象的關(guān)系弱,不便于后續(xù)分析處理;標記速度仍有提升空間。針對這些情況,本文依據(jù)前文定義的粒標記模型,提出一種新的標記算法,即圖像粒標記(Image Granule Labeling,IGL)算法。

3.2 IGL標記算法

定義4(行連通段) 一個概念粒在同一行上的連續(xù)象元構(gòu)成的塊,定義如下:

其中,r是行坐標;l為標記;s為列坐標的起點;t為相應終點;pn為指針,指向后繼行連通段。初始行連通段中標記l被置為-1。對應的潛在連通范圍和列坐標集如下。

定義5(潛在連通范圍) 列坐標集,令k≥0,k,x為整數(shù);sa=s-k;ta=t+k,則R的潛在連通范圍為:ASR(r,s,t)={x|x≥saandx≤ta};列坐標集為:SR(r,s,t)={x|x≥sandx≤t}。

基于上述二定義,給出連通判定定義如下。

定義6(連通判定)R(y,s,t)在第y行,R(y1,s1,t1)處于第(y+1)行,如果ASR(y,s,t)∩SR(y1,s1,t1)≠Φ,則它們互相連通。當k=1時,八連通;k=0時,四連通。

定義6源于式(3),更利于實現(xiàn),能極大地提升連通分析的速度。以下給出IGL算法標記和提取連通區(qū)的過程。

IGL算法僅需對圖像做一次掃描。首先,提取一個概念粒的首行數(shù)據(jù),將之視為當前行,記錄行連通段,同時分別賦預設標記,記它們?yōu)榕R時連通區(qū)(即連通粒未提取完的中間結(jié)果,記為TCnw,下標n為概念粒號,w為相應的預設標記。所有在用的預設標記合成一個動態(tài)集W。接下來,提取下一行數(shù)據(jù),記錄行連通段,查找其中與當前行八連通的各行連通段。若當前行的當前行連通段在下行中沒找到相連通的行連通段,跳過,處理當前行的下一個行連通段。若有,根據(jù)所找到的行連通段的標記l是否-1分別處理。若是-1,將它的標記改為w,加入對應于當前行當前行連通段的臨時連通區(qū)TCnw。若非,則需進一步分2種情況:(1)l=w,意味著此前已加入過,不需再作處理;(2)l≠w,TCnw和TCnl將被合并為一個,設為TCnm,其中,m=min(l,w)。合并時,非m的標記將替換為m,同時,從預設標記集W中刪除max(l,w)。

完成當前行所有行連通段的處理后,所有未找到后繼行連通段的TCnw成為最終連通區(qū),記為Cij(i是概念粒號,j=1,2,…是連通粒號),從W中刪除w;同時,給下行中未被任何TC合并的行連通段賦預設標記,形成新的臨時連通區(qū)。

處理完畢后,向前迭進,將下行設為當前行,它的后續(xù)行成為新的下一行,重復前述過程,直到一個概念粒的最后一行完畢。接著進入下一個概念粒,直至最終全部完成。

在標記使用上,IGL算法與以往所有基于標記等價的算法不同的是:IGL算法的預設標記和代表標記完全無關(guān)。預設標記可無序;代表標記連續(xù)遞增。為約束預設標記的賦值范圍,減少計算量,給出以下定理。

推論標記任意一個N×M圖像的過程中,臨時連通區(qū)不超過sup(N/2)個。

同理可知,以上定理、推論可用于N×N或任意區(qū)域(此時N是區(qū)域的最大寬、高度)。以圖1所示概念粒為例演示IGL的提取和標記過程。

圖1 概念粒示例

令圖1所示的概念粒號為6。首行第6行成為當前行,R(6,2,25)被賦預設標號1,R(6,32,45)為2,分別記作TC61和TC62,更新W={1,2}。第7行,R(7,3,5),R(7,19,23)和R(6,2,25)連通,被依次并入TC61。TC62完畢,記作連通粒C61,W={1}。第8行,R(8,2,5),R(8,16,25)被順序并入TC61,R(8,7,12)得到預設標號2,記為新的TC62,W={1, 2}。第9行,R(9,2,5),R(9,17,26)被順序并入TC61,R(9,8,13)則并入TC62。R(9,33,42)得預設標號3,記作TC63,W={1,2,3}。第10行,R(10,2, 5),R(10,15,26)被順序并入TC61,R(10,34,43)并入TC63。TC62完畢,記作C62,W={1,3}。第11行,R(11,6,17),R(11,20,40)被順序并入TC61。在R(11,20,40)并入TC63時,被發(fā)現(xiàn)已得到正標號1,不等于3,即TC63應和TC61合并。合并過程:將R(9, 33,42)置于R(9,17,26)之后,R(10,34,43)置于R(10,15,26)之后,R(11,20,40)置于R(11,6,17)之后。至此,本概念粒最后一行畢,記TC61為C63。即圖1中有3個連通粒:C61～C63。

以上標記、提取及相關(guān)的統(tǒng)計操作在圖像的一次掃描中完成,優(yōu)于當前的基于等價標記的標記算法。

IGL算法旨在為后續(xù)處理提供基礎平臺,所得連通粒除了有標記之外,在標記過程中已將每個連

通區(qū)單獨以壓縮方式存放,并附有區(qū)域大小、邊緣特征等統(tǒng)計信息,平臺的應用者可以隨機獨立地訪問其中的任何一個,也可輕松地根據(jù)需要為連通粒建立索引。

3.3 算法實現(xiàn)

以式(5)做依據(jù),定義針對行連通段的結(jié)構(gòu)體類型run:

typedef struct run;

接下來的標記和提取的實現(xiàn)有2個關(guān)鍵步驟。

(1)臨時連通區(qū)的指針組的定義與使用。設N是圖像的寬度,或是不規(guī)則(例如是圖1所示的概念粒)區(qū)域的最大寬度,Tn=sup(N/2)+1,按照推論定義指針組:run?TC［n+1］［Tn］;n為概念粒號。

(2)連通和合并的判定。為簡化實現(xiàn)算法的說明,設y代表當前行,y1是它的下一行,R(y,s,t)為當前行的當前行連通段,R(y1,s1,t1)為下一行中待檢測的行連通段,根據(jù)6設計連通、合并的判定算法如下。

算法連通與合并判定算法

4 驗證與對比分析

為測試IGL算法對資源有限環(huán)境的適應性,本文用低配置設備做了驗證比較實驗,用的是一臺筆記本電腦(Intel(R)Pentium(R)T2330@1.60 GHz, 1 GB內(nèi)存,MPSoC),VC60和OpenCV 2編程。

測試圖像集共有220幅自然圖像(包括指紋圖、風景圖、肖像等,引自貝克利分割庫),另有20幅紋理圖(引自哥倫比亞反射紋理庫),10幅Canny邊緣圖,和25幅醫(yī)學圖像(引自芝加哥大學醫(yī)學圖像庫)。

4.1 彩色圖像的驗證與分析

彩圖標注是個熱點,有眾多成果,彩圖標記則尚未見諸公開文獻,沒有同類可比較的文獻,是種探索。為驗證IGL算法提供的基礎平臺的應用潛力,從連通粒與圖像中潛在對象的對應性及標記速度2個角度給出實驗結(jié)果,驗證基礎平臺的應用潛力。

在表1中,Ci列為每幅圖經(jīng)截分后得到的概念粒之一,作為示例,CCj列出該概念粒中的一個連通粒,Nc是全圖概念?？倲?shù),Ncc為全圖連通粒總數(shù)。

表1彩圖的粒標記驗證示例

對比CCj列中的連通粒和Ci列對應對象,所有10個實例中,兩者都有嚴格的、精確的對應性,同時也基本反映出了原圖像中對應的潛在對象的原貌,為依據(jù)連通粒分析對應對象打下了扎實的基礎。

圖2顯示了10幅圖像(按序與表1對應)的運行時間及連通?？倲?shù)(Ncc)。為了直觀,后者顯示連通?？倲?shù)除以35 000的值。從結(jié)果看,運行時間均在1%秒級,比較快捷,能適應低資源環(huán)境。整體趨勢上,運行時間隨著連通粒的增加而提高,但也有局部震蕩(如road1)。分析具體數(shù)據(jù),發(fā)現(xiàn)這是受了圖像本身的連通結(jié)構(gòu)影響,road1的平均行連通長度偏短。

圖2 運行時間與連通粒數(shù)

為了進一步分析連通粒數(shù)對運行速度的影響,用最高值與最低值之比粗略地估計兩者的增速。根據(jù)表1、圖2,連通粒數(shù)最少的為tower2.jpg,256個,對應的運行時間為0.031 s。最多的是mushr.jpg, 159 3個,運行時間是0.078 s。即在連通?？倲?shù)增加6.22倍的情況下,時間的增幅是2.52倍。特別的,在極端情況下,在連通?？倲?shù)高達22 217個(tower2的87倍)時,運行時間也僅為0.352 s (tower2的11倍)。這從一個側(cè)面說明,限制預設標記數(shù)對因連通粒增加而帶來的圖像復雜性有抑制作用,提升了處理速度,因此,IGL算法能較好地適應復雜圖或大圖的快速標記。

實驗證實IGL算法找到的區(qū)域與圖像中的潛在對象有較好的對應性,作為有著嚴密的理論依托的基礎平臺,它可在圖像處理和分析領域中的眾多研究方向上得到應用,比如圖像檢索、顯著對象提取、圖像語義標注等。

4.2 對比分析

RTS算法是目前較突出的灰度圖基于行連通段標記算法之一,且已被文獻［13］證實快于其他標記算法,因此本文選擇與文獻［13］提出的RTS算法作比較分析。

表2列出了有代表性的8種類型共15幅二值圖像的實驗結(jié)果。表中CC列顯示實際的連通粒數(shù),RTS列記錄RTS算法的預設標記數(shù),IGL是相應的IGL算法的預設標記數(shù),結(jié)果數(shù)據(jù)顯示,兩者最少相差7倍,最大時,近于70倍,IGL算法所用的預設標記遠低于RTS算法。

表2 所用標識數(shù)比較

用表2中所有圖像做標記所用時間比較,見圖3,表中每個時間值為運行1 000次總時間的平均值,實驗結(jié)果顯示出IGL算法在所有被測圖像上都快于RTS算法。

圖3 不同類型圖的運行時間

這種速度差異有著客觀原因:(1)如表2所示,IGL算法的預設標記遠低于RTS算法,且其上限可預知。(2)在RTS算法中,由預設標記中產(chǎn)生代表標記,也就是說,預設標記將被代表標記劃分成一個個集合,表2顯示,一個圖中的連通區(qū)數(shù)量通常較大,數(shù)目也不定,這些集合的記錄存儲將很費時,相對的,在IGL算法中,預設標記與代表標記無關(guān),不必記錄。(3)RTS搜索需合并的臨時連通區(qū)時,用的仍是逐象元方式,IGL算法則完全基于行連通段。

5 結(jié)束語

本文構(gòu)建并實現(xiàn)了一個圖像粒標記模型,并給出了相應的實現(xiàn)算法——IGL算法,形成了一種可同時適應灰度圖和彩圖的基礎標記平臺。平臺有嚴格的粒計算理論基礎,可擴展性強,速度快,所得連通粒信息全,與圖像中的潛在對象有對應性,能用于諸如顯著對象局部提取、圖像檢索、圖像語義標注等眾多圖像分析方向。

［1]張 鈸,張 鈴.粒計算未來發(fā)展方向探討［J］.重慶郵電大學學報:自然科學版,2010,22(5):538-540.

［2]馬鴻耀,王國胤,張清華,等.基于云模型的多粒度彩色圖像分割［J］.計算機工程,2012,38(20): 184-187.

［3]姚 紅,王國胤,張清華.基于粗糙集和云模型的彩色圖像分割方法［J］.小型微型計算機系統(tǒng),2013, 34(11):2615-2620.

［4]Milind M M,Ray A K.Color Image Segmentation: Rough-set Theoretic Approach［J］.Pattern Recognition Letters,2008,29(4):483-493.

［5]任小康,李文靜,靳艷峰.基于粗糙集和mPCA的人臉識別算法［J］.計算機工程,2008,34(14):178-181.

［6]Petrosino A,Ferone A.Rough Fuzzy Set-based Image Compression［J］.FuzzySetsandSystems,2009, 160(10):1485-1506.

［7]謝 昭,高 雋.一種基于粗糙集區(qū)域分割和語義分類的方法［J］.模式識別與人工智能,2007,20(2): 287-294.

［8]Yao J T,Vasilakos,A V,Pedrycz W.Granular Computing:PerspectivesandChallenges［J］.IEEE Transactions on Cybernetics,2013,43(6):1977-1989.

［9]王國胤,張清華.不同知識粒度下粗糙集的不確定性研究［J］.計算機學報,2008,31(9):1588-1598.

［10]李仲生,李仁發(fā),蔡則蘇.顯著對象的非監(jiān)督粗糙認知算法［J］.計算機研究與發(fā)展,2012,49(1):202-209.

［11]李仲生,李仁發(fā),蔡則蘇,等.稀疏表示下的非監(jiān)督顯著對象提取［J］.電子學報,2012,40(6):1097-1102.

［12]李仲生,蔡則蘇,黃同成,等.粒邊緣模型及其實現(xiàn)［J］.計算機工程與應用,2014,50(5):1-5.

［13]He L,Chao Y,SuzukiK.A Run-basedTwo-scan Labeling Algorithm［J］.IEEE Transactions on Image Processing,2008,17(5):749-756.

編輯 顧逸斐

An Image Granule Labeling Model and Its Implementation

LI Zhongsheng1,HUANG Tongcheng1,CAI Zesu2
(1.Department of Information Engineering,Shaoyang University,Shaoyang 422000,China;
2.School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China)

With regard to the absence of base models which are extendible in the field of image analysis,an image granule labeling model is proposed.On the analysis of the applicability of rough sets and quotient space,two new concepts,semantic granule and conception granule,are defined and the image labeling model based on granules is constructed with them.A linear algorithm,Image Granule Labeling(IGL)algorithm,is presented for the realization of the granule labeling model with the definitions of connected segment in a line and potential connection range between two lines.It simplifies connectivity determination using a dynamic set of provisional labels and takes into account the fact that the quantity of granules may be huge and the structure of granules is very complex normally.Comparisons and experimental results on binary images and color images show that the proposed granule labeling algorithm is effective and accurate,and it is quicker than conventional labeling algorithms.

connected segment in a line;connected granule;conception granule;image processing;granule labeling model;Image Granule Labeling(IGL)algorithm

李仲生,黃同成,蔡則蘇.一種圖像粒標記模型及其實現(xiàn)［J］.計算機工程,2015,41(3):223-227,236.

英文引用格式:Li Zhongsheng,Huang Tongcheng,Cai Zesu.An Image Granule Labeling Model and Its Implementation［J］.Computer Engineering,2015,41(3):223-227,236.

1000-3428(2015)03-0223-05

:A

:TP391.41

10.3969/j.issn.1000-3428.2015.03.042

國家自然科學基金資助項目(61075076);湖南省自然科學基金資助項目(13JJ6078,14JJ7075);湖南省教育廳基金資助重點項目(13A091)。

李仲生(1967-),男,副教授、博士,主研方向:圖像處理,粒計算,物聯(lián)網(wǎng)技術(shù);黃同成,教授、博士;蔡則蘇,副教授、博士。

2014-01-28

:2014-05-12E-mail:zsli666@163.com