圖像連通元快速標記的方法
2023-04-23 15:00:11 2
專利名稱：圖像連通元快速標記的方法
技術領域：
本發明涉及圖像分析與識別技術領域，特別涉及一種二值圖像的連通元目標的快速標記方法。
背景技術：
在大多數的圖像分析和識別系統中，連通元標記是一個基本的操作，是後續處理的基礎。標記連通元的目的，是為了將二值圖像轉換成符號圖像，即給每個連通元分配一個標籤將它們區分開來。
在現有技術中，最常用的方法是將圖像按順序進行處理，並且建立等價類表來保存等價類的相關信息。在第一次掃描中基於相鄰象素的值給每個前景(目標)象素分配一個臨時標記。如果發生兩個相鄰的前景象素擁有不同的標記的情況，那麼這兩個標記視為等價類，並記錄到等價類表中。在第二次掃描中，將圖像中屬於同一等價類的象素用相同的標記表示。
由於連通元標記是圖像象素級的處理，相對比較費時，而且需要佔用大量內存。隨著計算機技術的快速發展，雖然存儲空間問題已不再突出，但是，如何以更快的速度對圖像進行處理，正是人們期待的。
為此，人們一直致力於連通元標記方法的研究，以提高處理速度和減少存儲空間。
發明內容
對大多數的圖像識別系統而言，連通元的標記是最耗時的過程之一，尤其是對較大尺寸的圖像更是如此。為了減少連通元的標記時間，提高連通元的標記速度，本發明提出了以下技術方案。
1.一種圖像連通元的標記方法，包括以下步驟；a.進行初始化工作，即把行標j指向起始行、總遊程數K置為0；b.掃描圖像第j行數據，得到Zj個遊程，並記錄為Rk(j)(k＝K+1，K+2，…，K+Zj)；c.檢查Zj是否為0，如果檢查結果為是，則跳過步驟d、e，進行步驟f；d.如果步驟c檢查結果為否，則記錄第j行的每個遊程、並將它們標記到對應的樹上；e.總遊程數量增加Zj個，即由原來的K個總遊程數量變為K+Zj個總遊程數量；f.行標號j增加1，即由原來的行標號j變為行標號j+1；g.檢查行標號是否超出圖像高度範圍，如果檢查結果為否，則返回步驟b；h.如果步驟g檢查結果為是，則輸出遊程和樹結構信息。
2.所述的記錄第j行的每個遊程、並將它們標記到對應的樹上，其方法包括以下步驟；a.置當前處理的遊程標號k為K+1；b.對遊程Rk(j)，尋找上一行與其相連接的遊程；c.檢查是否存在步驟b中所述的相連接的情況，如果檢查結果為是，則先進行步驟d後、再跳過步驟e直接進行步驟f；如果檢查結果為否，則跳過步驟d後，直接進行步驟e；d.確定並記錄與遊程Rk(j)相連的上一行的某一個遊程為Rk(j)的父遊程；e.生成一個新的樹，遊程Rk(j)作為其根節點；f.將k增加1；g.檢查k是否大於K+Zj，如果檢查結果為否，則返回步驟b；h.如果步驟g檢查結果為是，則轉入其它相連的後續步驟。
3.所述的確定並記錄與遊程Rk(j)相連的上一行的某一個遊程為Rk(j)的父遊程，其方法包括以下步驟；a.上一行與遊程Rk(j)相連的遊程，按從左到右順序記為Rl(j-1)、Rl+1(j-1)、….、Rr(j-1)；b.檢查上一行是否只有一個相連的遊程，即檢查Rl(j-1)是否等於Rr(j-1)；如果檢查結果為是，則跳過步驟c，直接進行步驟d；c.如果步驟b檢查結果為否，設置Rm(j-1)(m＝l+1，…，r)的根節點的父遊程Rl(j-1)對應的樹根；所述的Rm(j-1)(m＝l+1，…，r)，Rm(j-1)和Rl(j-1)屬於不同的樹；d.確定並記錄Rl(j-1)為Rk(j)的父遊程；e.轉入其它相連的後續步驟。
本發明的有益效果是只用一次掃描就能獲得數字圖像的外接矩形和象素麵積等特性，由於大大地提高了連通元的標記速度，所以對圖像處理速度、尤其是對大尺寸的圖像處理速度，能明顯的得到提高。
附圖1是輸入輸出示意圖。
附圖2是本發明方法的主流程圖，也是權利要求1的流程圖。
附圖3是第j行遊程標記到樹上的方法流程圖，也是權利要求2的流程圖。
附圖4是確定記錄遊程Rk(j)的父遊程的方法流程圖，也是權利要求3的流程圖。
附圖5是遊程之間的連接類型示意圖；其中x是各種一對一的連接類型；y是一對多的連接類型；z是多對一的連接類型。
附圖6是實施例的示意圖，以一個連通元為例，說明如何對遊程進行處理的；圖中的A、B、C、D、E、F、G都是遊程；j、j+1、j+2、j+3是依順序連續的行。
附圖7是樹結構示意圖，圖中的雙線圓圈代表根節點、單線圈代表內部節點或葉節點。
附圖7中a部分的樹結構，即j部分的樹結構，與附圖6中的j行掃描相對應；附圖7中b部分的樹結構，即j+1部分的樹結構，與附圖6中的j+1行掃描相對應；附圖7中c部分的樹結構，即j+2部分的樹結構，與附圖6中的j+2行掃描相對應；附圖7d中部分的樹結構，即j+3部分的樹結構，與附圖6中的j+3行掃描相對應。
附圖6和附圖7應該一一對應起來進行理解。
下面結合附圖和具體實施方式
對本發明作進一步的詳細說明。
具體實施例方式
標記連通元的目的是為了將二值圖像轉換成符號圖像，即給每個連通元分配一個標籤將它們區分開來。在現有技術中，最常用的方法是將圖像按順序進行處理，並且建立等價類表來保存等價類的相關信息。在第一次掃描中基於相鄰象素的值給每個前景(目標)象素分配一個臨時標記。如果發生兩個相鄰的前景象素擁有不同的標記的情況，那麼這兩個標記視為等價類，並記錄到等價類表中。在第二次掃描中，將圖像中屬於同一等價類的象素用相同的標記表示。
本發明的目的在於實現一種基於遊程並以樹結構表示的快速標記連通元的方法。首先，從圖像中逐行提取遊程，並把它們的位置間關係信息存儲下來。用樹來表示當前行的遊程與上一行遊程間的位置關係，每棵樹就對應一個連通元，圖1是本方法的輸入輸出示意圖。該方法只需一次掃描就可以獲得連通元的外接矩形框和象素總數等有用信息。
下面，結合圖進行描述。
首先對圖像，按從上到下和從左到右的順序進行掃描，在每一行中，尋找且記錄每個遊程。
遊程定義為同一行中左右連續相鄰的前景(也稱目標)象素點的集合。我們用一個五元組(k，yk，sk，tk，pk)來表示一個遊程Rk(y)k表示遊程在圖像中的序列號；yk 表示遊程的行坐標；sk 表示遊程起始點的列坐標；tk 表示遊程終止點的列坐標；pk 該遊程在上一行的父遊程。
每個連通元內的遊程之間的關係用樹結構來表示。每個遊程對應著樹中的一個節點，如果當前行的一個遊程與上一行的一個遊程相連通，那麼這兩個遊程在樹中對應的節點相連。遊程間的連通關係定義如下定義假設Rk(y)是第y行的一個遊程。Rm(y-1)是第y-1行的遊程，如果它們滿足下列條件中的任意一個，那麼我們稱Rk(y)與Rm(y-1)是連通的。
(1)sk-n≤sm≤tk(2)sk≤tm≤tk+n(3)sm-n≤sk≤tm(4)sm≤tk≤tm+n對於8連通的情況n＝1；而4連通的情況n＝0。
如果Rk(y)與Rm(y-1)是連通的，則稱Rm(y-1)是Rk(y)的父遊程，或稱Rk(y)是Rm(y-1)的子遊程。
當一個新的遊程產生時，將它的起始點和終止點坐標與上一行的遊程相比較，判斷是否與上一行的遊程相連通。兩個相鄰行(當前行與上一行)遊程之間的關係可以總結為三種類型，即一對一，一對多和多對一共三種類型，如圖5中的上圖、中圖、下圖所示。在一對一的類型中，當前行有一個遊程與上一行的一個遊程相連通；在一對多的類型中，當前行有多個遊程與上一行的一個遊程相連通；在多對一的類型中，當前行有一個遊程與上一行的多個遊程相連通。
如果一個遊程在上一行中沒有找到與之相連通的遊程，那麼這個遊程就作為樹的根節點。這棵樹對應一個新的連通元。如果一個遊程在上一行中找到與之相連通的遊程，這個遊程就作為上一行中與之相連通的遊程的子節點。在一對一類型中，當前遊程是上一行中相連遊程的唯一子節點，而在一對多的類型中，上一行的對應遊程在當前行有多個相連通的遊程，所以有多個子節點。
如果多對一的類型出現，也即上一行中有多個遊程與當前一個遊程相連，那麼必須做特別的處理。我們首先觀察上一行中與之相連通的所有遊程是否屬於不同的樹。如果是，應將這些不同的樹合併。本方法中，這種處理非常簡單，只需把包含最左邊節點的樹的根節點予以保留，而其他樹的根節點合併為保留的根節點的子節點。基於上述處理，每棵樹只對應於圖像中的一個連通元。
為了更好的理解這個方法，在以下實施例中進行更詳細的描述。
實施例一。
現結合圖6、圖7，進行進一步的說明。圖6和圖7的內容，應該一一對照起來看。
當掃描進行到第j行時，找到了遊程A，這個遊程是一棵新樹的根節點，如圖7中的(a)部分所示。
當掃描到第j+1行時，找到了遊程B和C，如圖7中的(b)部分所示，B與A連接，所以A是B的父節點，而C是另一棵新樹的根節點。繼續掃描至第j+2行時，如圖7中的(c)部分所示，找到遊程D、E和F，D和E與B連接。因此，它們是B的子節點，F與C相連接，所以F是C的子節點。當掃描至第j+3行時，找到遊程G，因為E和F都與G連接，G作為最左邊遊程E的子節點。此外，我們必須檢查E和F是否屬於同一棵樹。如果他們屬於不同的樹，那麼必須把他們合併起來。在這裡，A是E的根，C是F的根。因此，這兩棵樹需合併起來。其中一棵樹的根節點變為內部節點，成為另一棵樹的子節點。如圖7中的(d)部分所示，遊程C為A的子節點。
當整幅圖像掃描完畢後，所有的遊程都記錄下來了，每棵樹對應一個連通元。根據一棵樹，我們可以得到對應的那個連通元的所有信息，如連通元外接矩形的寬、高和連通元的象素總數等。
對於一個連通元Cn，所有屬於Cn的遊程的序號用集合Ψn表示。Cn的外接矩形的左上角坐標和右下角坐標分別用(xn(l)，yn(t))和(xn(r)，yn(b))表示，它們的坐標值可由下面的計算得到xn(l)=mininsi]]>yn(t)=mininyi]]>xn(r)=maxinti]]>yn(b)=maxinyi]]>其中min表示求最小值，max表示求最大值。該連通元外接矩形的寬和高分別為寬xn(r)-xn(l)高yn(b)-yn(t)該連通元中的象素總數可以由下式直接計算得到in(ti-si+1)]]>
權利要求
1.一種圖像連通元的標記方法，包括以下步驟；a.進行初始化工作，即把行標j指向起始行、總遊程數K置為0；b.掃描圖像第j行數據，得到Zj個遊程，並記錄為Rk(j)(k＝K+1，K+2，…，K+Zj)；c.檢查Zj是否為0，如果檢查結果為是，則跳過步驟d、e，進行步驟f；d.如果步驟c檢查結果為否，則記錄第j行的每個遊程、並將它們標記到對應的樹上；e.總遊程數量增加Zj個，即由原來的K個總遊程數量變為K+Zj個總遊程數量；f.行標號j增加1，即由原來的行標號j變為行標號j+1；g.檢查行標號是否超出圖像高度範圍，如果檢查結果為否，則返回步驟b；h.如果步驟g檢查結果為是，則輸出遊程和樹結構信息。
2.根據權利要求1所述的一種圖像連通元的標記方法，所述的記錄第j行的每個遊程、並將它們標記到對應的樹上，其方法包括以下步驟；a.置當前處理的遊程標號k為K+1；b.對遊程Rk(j)，尋找上一行與其相連接的遊程；c.檢查是否存在步驟b中所述的相連接的情況，如果檢查結果為是，則先進行步驟d後、再跳過步驟e直接進行步驟f；如果檢查結果為否，則跳過步驟d後，直接進行步驟e；d.確定並記錄與遊程Rk(j)相連的上一行的某一個遊程為Rk(j)的父遊程；e.生成一個新的樹，遊程Rk(j)作為其根節點；f.將k增加1；g.檢查k是否大於K+Zj，如果檢查結果為否，則返回步驟b；h.如果步驟g檢查結果為是，則轉入其它相連的後續步驟。
3.根據權利要求2所述的一種圖像連通元的標記方法，所述的確定並記錄與遊程Rk(j)相連的上一行的某一個遊程為Rk(j)的父遊程，其方法包括以下步驟；a.上一行與遊程Rk(j)相連的遊程，按從左到右順序記為Rl(j-1)、Rl+1(j-1)、….、Rr(j-1)；b.檢查上一行是否只有一個相連的遊程，即檢查Rl(j-1)是否等於Rr(j-1)；如果檢查結果為是，則跳過步驟c，直接進行步驟d；c.如果步驟b檢查結果為否，設置Rm(j-1)(m＝l+1，…，r)的根節點的父遊程為Rl(j-1)對應的樹根；所述的Rm(j-1)(m＝l+1，…，r)，Rm(j-1)和Rl(j-1)屬於不同的樹；d.確定並記錄Rl(j-1)為Rk(j)的父遊程；e.轉入其它相連的後續步驟。
全文摘要
本發明涉及圖像技術領域，公開了一種二值圖像的連通元目標的快速標記方法。步驟是a.進行初始化工作，即把行標j指向起始行、總遊程數K置為0；b.掃描圖像第j行數據，得到Zj個遊程，並記錄；c.檢查Zj是否為0，如果為是，則跳過步驟d、e，進行步驟f；d.如果步驟c檢查為否，則記錄第j行的每個遊程、並標記到對應的樹上；e.總遊程數量增加Zj個；f.行標號j增加1；g.檢查行標號是否超出圖像高度範圍，結果為否，則返回步驟b；h.如果步驟g檢查結果為是，則輸出遊程和樹結構信息。有益效果是由於只用一次掃描就能獲得數字圖像的外接矩形和象素麵積等特性，大大地提高了連通元的標記速度，所以對圖像處理速度能明顯的得到提高。
文檔編號G06K9/20GK101042734SQ200710039540
公開日2007年9月26日 申請日期2007年4月17日 優先權日2007年4月17日
發明者呂嶽 申請人:華東師範大學