一種適于硬件實(shí)現(xiàn)的快速連通域標(biāo)記算法

張國和, 徐快, 段國棟, 趙晨, 梁峰

(西安交通大學(xué)電子與信息工程學(xué)院, 710049, 西安)

在計(jì)算機(jī)視覺、遙感、醫(yī)學(xué)、生物特征學(xué)、文檔分析、機(jī)器人等領(lǐng)域,圖像中連通區(qū)域信息的提取和標(biāo)記具有重要的作用[1]。在基于硬件實(shí)現(xiàn)的圖像、視頻處理系統(tǒng)中,與可流水實(shí)現(xiàn)的圖像濾波、邊緣檢測(cè)和閾值分割等算法相比,連通區(qū)域標(biāo)記算法往往需要占用更多的硬件資源和處理時(shí)間[2],成為高速圖像處理的瓶頸。因此,如何提高連通區(qū)域標(biāo)記算法的執(zhí)行效率是整個(gè)圖像處理系統(tǒng)中的關(guān)鍵問題[3]。

通過對(duì)近些年提出的典型的二值圖像連通域標(biāo)記算法進(jìn)行詳細(xì)描述,總結(jié)其優(yōu)缺點(diǎn),對(duì)相應(yīng)算法復(fù)雜度和資源需求進(jìn)行了分析,以供設(shè)計(jì)出適合于硬件實(shí)現(xiàn)的二值圖像連通域標(biāo)記算法。當(dāng)前已有的區(qū)域連通標(biāo)記算法根據(jù)其實(shí)現(xiàn)方式可以分為2類:軟件可實(shí)現(xiàn)算法和硬件可實(shí)現(xiàn)算法。

Rosenfeld等提出的兩遍掃描算法被視為經(jīng)典的區(qū)域連通標(biāo)記算法[4],但是由于存儲(chǔ)等價(jià)標(biāo)記所需的內(nèi)存空間和合并等價(jià)標(biāo)記所需的時(shí)間都很大,此算法僅僅適用于軟件實(shí)現(xiàn)。Chang等提出的輪廓追蹤(CT)算法[5]只需掃描圖像一次,然而輪廓像素點(diǎn)可能被掃描多次。由于算法中對(duì)內(nèi)存的訪問非常沒有規(guī)律,此算法也僅僅適用于軟件實(shí)現(xiàn)。何立風(fēng)等人設(shè)計(jì)的基于游程的兩遍掃描連通域標(biāo)記算法[6-8],引入游程的概念,對(duì)像素批量進(jìn)行標(biāo)記和等價(jià)標(biāo)記合并。經(jīng)過測(cè)試,該算法在同類算法中的效率最高,且隨著圖像像素和復(fù)雜度的增大具有較穩(wěn)定的線性特性,本文的連通域標(biāo)記算法借鑒了此算法對(duì)于等價(jià)標(biāo)記表的實(shí)現(xiàn)方式。在目前已知的區(qū)域連通算法中,Grana等提出的塊決策表(BBDT)算法[9]具有最好的性能,該算法增大了相鄰像素的掃描窗口,缺點(diǎn)是只能支持8連通規(guī)則。

由于對(duì)大存儲(chǔ)空間的要求,上述區(qū)域連通算法往往無法通過硬件邏輯加速,由此又出現(xiàn)了一些適用于硬件實(shí)現(xiàn)的連通域標(biāo)記算法。Kofi等提出一種基于游程長(zhǎng)度的區(qū)域連通算法[10],可以通過片上RAM實(shí)現(xiàn),但對(duì)于大于1 024×1 024像素的圖像,過高的存儲(chǔ)空間要求依然成為瓶頸。Johnston等提出的一次掃描算法[11]在FPGA實(shí)現(xiàn)過程中,由于需要對(duì)堆棧進(jìn)行復(fù)雜的寫入讀出操作,使得電路的最高工作頻率很低,并不利于圖像的實(shí)時(shí)高速處理。

國內(nèi)許多高校也對(duì)區(qū)域連通標(biāo)記算法進(jìn)行了一定的研究[12-14],如沈陽工業(yè)大學(xué)的馮海文等人提出的高效一遍掃描連通域標(biāo)記算法[12]、四川大學(xué)的王凱等人設(shè)計(jì)的基于圖像分塊的連通域標(biāo)記算法[13]、華東理工大學(xué)的劉關(guān)松提出的新型二值圖像連通域標(biāo)記算法[14]等都是在一些經(jīng)典算法的基礎(chǔ)之上做了一定的改進(jìn),對(duì)算法效率的改善不大,且大多基于軟件實(shí)現(xiàn),本文主要研究連通域標(biāo)記算法的硬件電路實(shí)現(xiàn),因此這類算法僅作參考。

從國內(nèi)外研究現(xiàn)狀來看,比較主流的連通域標(biāo)記算法仍然是基于對(duì)圖像的光柵掃描,這些算法受限于過高的資源需求,只適用于軟件實(shí)現(xiàn),因此速度成為其主要的衡量指標(biāo)。

為了減少存儲(chǔ)等價(jià)標(biāo)記所需的空間和處理等價(jià)標(biāo)記所需的時(shí)間,本文以游程為單位批量地對(duì)行內(nèi)連續(xù)像素進(jìn)行處理。在逐行對(duì)圖像進(jìn)行光柵掃描的過程中,將已經(jīng)結(jié)束的連通區(qū)域即時(shí)輸出,不僅減少了存儲(chǔ)這些連通域信息所需的空間,而且只需對(duì)圖像完整地掃描一遍,就可以完成對(duì)連通域信息的提取或者連通域像素的標(biāo)記,極大地提高了運(yùn)行速度,使其能高速、高效完成連通域的標(biāo)記,用于實(shí)現(xiàn)圖像的快速掃描與追蹤。

1 二值圖像連通域標(biāo)記算法的設(shè)計(jì)

常見的連通區(qū)域分8鄰域和4鄰域連通2種,由于8鄰域連通更為全面,通用性好[15],因此本文以8鄰域連通為例進(jìn)行描述。本文所提出的快速連通域標(biāo)記算法需要經(jīng)過行掃描、游程標(biāo)記和等價(jià)游程對(duì)合并、已結(jié)束游程檢測(cè)和已結(jié)束區(qū)域信息輸出幾個(gè)主要階段,完成整幅圖片的連通域標(biāo)記和特征提取。

本文所提出的連通域標(biāo)記算法采用光柵掃描順序[16],逐行逐列掃描圖像的每個(gè)像素,將每一行內(nèi)連續(xù)的前景像素歸為一個(gè)游程,以游程為基本單位進(jìn)行預(yù)標(biāo)記和等價(jià)標(biāo)記合并,降低了所需記錄標(biāo)記的數(shù)量和處理等價(jià)標(biāo)記所需的時(shí)間。為了減小存儲(chǔ)已掃描完游程所需的存儲(chǔ)空間,在當(dāng)前行掃描結(jié)束后對(duì)上一行游程進(jìn)行檢測(cè),輸出已結(jié)束區(qū)域包含的所有游程。該算法只需對(duì)圖像完整地掃描一遍,就可以完成所有連通域的標(biāo)記,避免了對(duì)整幅圖像的臨時(shí)標(biāo)記值進(jìn)行緩存。本文算法的流程圖如圖1所示,主要分為以下幾個(gè)步驟。

(1)行掃描。從左至右逐個(gè)對(duì)當(dāng)前行的像素進(jìn)行掃描,判定行內(nèi)的所有游程,并將游程的起始坐標(biāo)和結(jié)束坐標(biāo)存入Ao或Ae數(shù)組(奇數(shù)行存入Ao數(shù)組,偶數(shù)行存入Ae數(shù)組)。當(dāng)目標(biāo)像素和前一個(gè)像素為“01”時(shí),意味著一個(gè)游程的開始,當(dāng)目標(biāo)像素和前一個(gè)像素為“10”時(shí),意味著一個(gè)游程的結(jié)束,需要注意的是在行開始和行結(jié)束像素的邊界情況。

圖1 本文提出算法流程圖

(2)游程標(biāo)記和等價(jià)游程對(duì)合并。對(duì)于步驟(1)中在當(dāng)前行產(chǎn)生的每個(gè)游程,需要對(duì)其賦予臨時(shí)標(biāo)記。對(duì)于當(dāng)前行的某個(gè)游程R1,需要掃描上一行的所有游程信息,若當(dāng)前行為奇數(shù)行,則掃描Ae數(shù)組中上一行的游程信息,若當(dāng)前行為偶數(shù)行,則掃描Ao數(shù)組中上一行的游程信息。2行間的2個(gè)游程由于位置不同存在的連通情況如圖2所示。

圖2 行間游程可能存在的連通關(guān)系示意圖

若上一行的游程與當(dāng)前行的游程的位置關(guān)系如圖2中的游程②、③、④的情況所示,則認(rèn)定兩者之間存在連通關(guān)系。算法中的實(shí)現(xiàn)方式為:設(shè)當(dāng)前行游程的起始坐標(biāo)為X0,結(jié)束坐標(biāo)為X1,上一行游程的起始坐標(biāo)為Y0,結(jié)束坐標(biāo)為Y1,若坐標(biāo)滿足下列2個(gè)公式,則認(rèn)定這2個(gè)游程存在連通關(guān)系,可描述為

X0≤Y1;X1≥Y0(四連通)

(1)

X0≤Y1+1;X1≥Y0-1(八連通)

(2)

若當(dāng)前行游程R1僅與上一行的一個(gè)游程R2連通,則將R2的臨時(shí)標(biāo)記L2賦予R1即可,同時(shí)需要將該標(biāo)記值存入Ao或Ae數(shù)組中相應(yīng)的游程信息中,以供后續(xù)的等價(jià)標(biāo)記合并時(shí)查看,還需將游程信息(起始坐標(biāo)、結(jié)束坐標(biāo)、所在行數(shù)、臨時(shí)標(biāo)記)記錄到An數(shù)組(記錄所有游程的信息)中,以供后續(xù)輸出已結(jié)束游程的信息時(shí)查看。如圖2所示,若當(dāng)前行游程R1同時(shí)與上一行的多個(gè)游程②、③、④連通,則將這些游程中最左側(cè)的(即最早被掃描到的)游程②的臨時(shí)標(biāo)記L2賦予R1即可,并將相應(yīng)信息記錄到Ao、Ae和An數(shù)組中。同時(shí),游程③、④的標(biāo)記值L3、L4與L2被認(rèn)定為等價(jià)標(biāo)記對(duì),需要在后續(xù)的等價(jià)標(biāo)記對(duì)合并操作中進(jìn)行合并。

若當(dāng)前行游程R1與上一行的游程的位置關(guān)系如游程①或⑤的情況所示,說明未與上一行的任何游程連通,則需要為R1新建一個(gè)臨時(shí)標(biāo)記L1,新的臨時(shí)標(biāo)記L1的代表標(biāo)記也為L(zhǎng)1,并將相應(yīng)信息記錄到Ao、Ae和An數(shù)組中。

對(duì)于上述記為等價(jià)標(biāo)記對(duì)的2個(gè)臨時(shí)標(biāo)記,需要進(jìn)行合并。合并的主要操作是將2個(gè)臨時(shí)標(biāo)記所在的代表標(biāo)記集合進(jìn)行合并。首先取出這2個(gè)臨時(shí)標(biāo)記值的代表標(biāo)記S1和S2,若S1=S2,則不需要合并;否則,將較大的代表標(biāo)記集合中的所有臨時(shí)標(biāo)記歸入較小的代表標(biāo)記集合中,實(shí)現(xiàn)了2個(gè)游程所代表的區(qū)域的合并。

(3)掃描上一行游程。在當(dāng)前行游程標(biāo)記和等價(jià)游程對(duì)合并結(jié)束后,需要對(duì)上一行的游程信息進(jìn)行掃描,主要檢測(cè)Fl(代表該游程是否與下一行的游程發(fā)生連通關(guān)系)標(biāo)志位。若Fl=1,意味著該游程與當(dāng)前行的游程發(fā)生連通關(guān)系,跳過;若Fl=0,意味著該游程未與當(dāng)前行的游程發(fā)生連通關(guān)系,但這只能說明該游程所在的區(qū)域在局部結(jié)束,是不是真正結(jié)束還要根據(jù)該游程的代表標(biāo)記與當(dāng)前行所有游程代表標(biāo)記的關(guān)系來判定。如圖3所示的圖像形狀,當(dāng)掃描到第5行時(shí),第4行的游程②未與當(dāng)前行的任何游程連通,但其所在區(qū)域在游程①、③的位置與當(dāng)前行游程④、⑤連通,因此并未結(jié)束。

考慮到這種特殊情況,本文采取的策略是對(duì)于上一行未與當(dāng)前行的連通的游程,取出其代表標(biāo)記值S2與當(dāng)前行所有游程的代表標(biāo)記值進(jìn)行比較(代表標(biāo)記表征了游程所在的區(qū)域),若沒有與之相等的,則說明該游程未與當(dāng)前行的任何游程存在等價(jià)關(guān)系,換言之就是該游程未與當(dāng)前行的任何游程處在同一區(qū)域,說明此區(qū)域在上一行的這個(gè)游程位置已經(jīng)結(jié)束,將其代表標(biāo)記值S2作為結(jié)束標(biāo)記存入Af數(shù)組(記錄上一行已結(jié)束游程的代表標(biāo)記),不重復(fù)記錄;若有與之相等的,則該游程所在的區(qū)域在當(dāng)前行還在延伸,不作任何操作。

圖3 判定游程結(jié)束的特殊案例

(4)輸出已結(jié)束區(qū)域信息。若步驟(3)中檢測(cè)出上一行存在已經(jīng)結(jié)束的游程,則從Af數(shù)組中取出其代表標(biāo)記Lf,遍歷An數(shù)組中游程的臨時(shí)標(biāo)記,將代表標(biāo)記和Lf相等的所有游程的信息輸出,輸出后要對(duì)An數(shù)組中空出的空間做出填充以節(jié)省存儲(chǔ)空間。

2 存儲(chǔ)機(jī)制和資源需求優(yōu)化

2.1 游程信息表存儲(chǔ)機(jī)制

根據(jù)上文的描述,本文算法需要的資源需求主要是來自Ao、Ae、An、Af、Br(記錄臨時(shí)標(biāo)記集合中所有標(biāo)記的代表標(biāo)記)、Bn(記錄臨時(shí)標(biāo)記集合中所有標(biāo)記的排列順序)、Bt(記錄臨時(shí)標(biāo)記集合的結(jié)束點(diǎn))等數(shù)組,其中An數(shù)組用來記錄掃描過程中所有游程的信息,所需的位寬和深度最大。為了降低An存儲(chǔ)塊的大小,本文對(duì)第1章中算法步驟(2)中An數(shù)組的存儲(chǔ)機(jī)制進(jìn)行一定的優(yōu)化,主要的思想就是將已結(jié)束游程的信息輸出后,將新建立的游程信息存入空閑的存儲(chǔ)空間里,避免建立新的存儲(chǔ)空間。如圖4所示,位于An數(shù)組中地址4的游程被檢測(cè)為結(jié)束游程,將其游程信息輸出,這樣地址4指向的空間就閑置了出來,當(dāng)掃描下一行像素檢測(cè)到新的游程時(shí),把新的游程信息存入地址4,避免建立新的地址空間,這樣可以降低存儲(chǔ)所有游程信息需要的存儲(chǔ)塊深度。

通過對(duì)多幅分辨率為2 048×1 536像素的圖片進(jìn)行測(cè)試,經(jīng)過優(yōu)化后,An數(shù)組的深度需求大大減少,最大降低的幅度高達(dá)90.3%,最少的也有32.6%,其中資源節(jié)約率為后者相對(duì)于前者降低的幅度,計(jì)算公式為

式中:Pr為資源節(jié)約率;Hbefore為優(yōu)化前應(yīng)有深度;HAn為An數(shù)組實(shí)際占用深度。

經(jīng)過優(yōu)化后的An數(shù)組的存儲(chǔ)機(jī)制雖然極大地降低了資源需求,但是考慮到每次有新的游程需要存儲(chǔ)時(shí),都需要對(duì)An數(shù)組中已占用過的所有的空間進(jìn)行遍歷,尋找閑置的空間,這個(gè)過程會(huì)隨著游程數(shù)量的增多耗費(fèi)更多的時(shí)間。因此也需要對(duì)1中算法步驟(4)An數(shù)組中游程信息的輸出機(jī)制進(jìn)行優(yōu)化,主要的思想就是當(dāng)某個(gè)地址的游程信息輸出后,將數(shù)組末尾的游程信息存至該位置,地址指針減1,這樣有新的游程需要存儲(chǔ)時(shí),就可以省去遍歷An數(shù)組的時(shí)間,直接將數(shù)組信息存入地址指針指向的空間,即原來末尾游程的存儲(chǔ)空間,如圖4所示。

(a)優(yōu)化前 (b)優(yōu)化后圖4 An數(shù)組輸出機(jī)制優(yōu)化前后示意圖

2.2 硬件實(shí)現(xiàn)資源需求分析及優(yōu)化

在硬件實(shí)現(xiàn)時(shí),首先要考慮算法需求的片上資源。由上述分析過程可知,該算法共需要7個(gè)數(shù)據(jù)陣列:Ao、Ae、An、Af、Bn、Bt和Br,對(duì)于分辨率M×N圖像,每組存儲(chǔ)塊所需的位寬和深度分析如下。

對(duì)于分辨率M×N圖像,區(qū)域個(gè)數(shù)的極限值為M×N/2,考慮到發(fā)生這種情況的時(shí)候,圖像檢測(cè)區(qū)域已經(jīng)沒有意義,所以即使求出區(qū)域信息也是沒有必要的。故可以約定一個(gè)可以接受的區(qū)域上限,來減少資源的占用。如果輸入圖像對(duì)單獨(dú)一個(gè)點(diǎn)的區(qū)域做了過濾,那么區(qū)域上限為M×N/4。

當(dāng)圖像像素分辨率為2 048×1 536像素時(shí),本文連通域標(biāo)記算法在硬件實(shí)現(xiàn)時(shí)理論上所需的存儲(chǔ)資源大約為88.87 Mbit,這大大超出了可以接受的范圍。但是,在實(shí)際測(cè)試中發(fā)現(xiàn)一些RAM的使用率遠(yuǎn)遠(yuǎn)小于其理論所需設(shè)計(jì)的深度,而且一些變量的最大值也遠(yuǎn)遠(yuǎn)小于其理論預(yù)估的極值,因此需要對(duì)上述RAM深度和寬度的分配進(jìn)行一定的優(yōu)化。

首先需要優(yōu)化的變量為臨時(shí)標(biāo)記和代表標(biāo)記的最大值。根據(jù)上文的分析,認(rèn)定臨時(shí)標(biāo)記和代表標(biāo)記的最大值為區(qū)域數(shù)量的上限,對(duì)于分辨率M×N的圖像,最大的連通域數(shù)量為M×N/4。考慮到本文算法最大支持的圖像分辨率為2 048×1 536像素,在MATLAB中對(duì)于大量分辨率為2 048×1 536像素、且構(gòu)成復(fù)雜的圖像進(jìn)行測(cè)試,發(fā)現(xiàn)其游程的最大臨時(shí)標(biāo)記和代表標(biāo)記值遠(yuǎn)遠(yuǎn)小于理論最大值M×N/4。出于節(jié)約硬件資源的考慮,這里取214=16 384即可以滿足實(shí)際需求,也就是臨時(shí)標(biāo)記和代表標(biāo)記的記錄需要占用位寬14 bit,深度為16 kbit。因此Bn、Bt和Br數(shù)組的RAM需求為16 000×14 bit。Ao和Ae數(shù)組的位寬需求為40(40=2×12+14+2)bit,Af數(shù)組的位寬需求為14 bit,An數(shù)組的位寬需求為50(50=2×12+12+14)bit。

表1 本文算法各數(shù)組對(duì)應(yīng)的RAM需求

圖5 本文算法的硬件系統(tǒng)結(jié)構(gòu)圖

接下來對(duì)各數(shù)組所需求RAM的深度進(jìn)行優(yōu)化。如之前2.1所述,通過對(duì)An數(shù)組存入讀出機(jī)制進(jìn)行一定的調(diào)整,實(shí)現(xiàn)了對(duì)其存儲(chǔ)深度的最大利用,根據(jù)表1統(tǒng)計(jì)的信息,將An數(shù)組對(duì)應(yīng)RAM的深度設(shè)為64 kbit即可滿足實(shí)際需求。為了節(jié)省硬件資源,將Ao和Ae數(shù)組的RAM深度設(shè)為M/4=512 bit,將Af數(shù)組的RAM深度設(shè)為M/8=256 bit,即可滿足實(shí)際需求。因此,對(duì)于分辨率為2 048×1 536的圖像,RAM總需求量為20.48+224+3.584+3 200=3 448 kbit≈3.45 Mbit。

表2 5種算法硬件實(shí)現(xiàn)需求的片上資源對(duì)比

如表2所示,對(duì)比可見本文算法硬件實(shí)現(xiàn)時(shí)需要的片上資源為BBDT算法的21.9%,為He算法[8]的7.6%。該配置所提供的硬件資源空間足以處理分辨率2 048×1 536像素及其以下的絕大多數(shù)二值圖像。

3 算法的硬件架構(gòu)

本文所提出標(biāo)記算法的硬件系統(tǒng)結(jié)構(gòu)框圖如圖5所示。其中對(duì)外連接的數(shù)據(jù)接口主要分為3組,第一組接口連接圖像源輸入模塊,接受來自圖像源的數(shù)據(jù)和數(shù)據(jù)有效信號(hào),并反饋行結(jié)束信號(hào)給圖像輸入模塊,以開啟下一行的圖像數(shù)據(jù)輸入;第二組接口連接參數(shù)配置模塊,主要完成對(duì)圖像分辨率以及二值圖像連通規(guī)則的配置,圖像分辨率的配置一定要與圖像的像素個(gè)數(shù)匹配,避免出現(xiàn)數(shù)據(jù)不足或溢出的情況;第3組接口通過輸出使能信號(hào)的控制,輸出已結(jié)束的區(qū)域游程息。

在二值圖像連通域標(biāo)記硬件結(jié)構(gòu)內(nèi)部,主要分為4個(gè)操作模塊、2個(gè)控制模塊以及4組片上RAM,這4個(gè)操作模塊都受狀態(tài)機(jī)控制模塊的控制,與片上RAM交互標(biāo)記過程中產(chǎn)生中間信息,其中An數(shù)組對(duì)應(yīng)RAM的存儲(chǔ)機(jī)制較為復(fù)雜,要受到An存儲(chǔ)控制模塊的控制。這4個(gè)操作模塊組成了一個(gè)完整的行操作流程,完成一幅分辨率M×N的二值圖像的連通域標(biāo)記需要N次行操作流程。

掃描模塊根據(jù)輸入的圖像數(shù)據(jù),判定當(dāng)前行的所有游程,將游程的起始坐標(biāo)和結(jié)束坐標(biāo)存入Ao、Ae數(shù)組中;標(biāo)記及合并模塊讀取當(dāng)前行和上一行的游程坐標(biāo),判定當(dāng)前行每一個(gè)游程與上一行游程的連通關(guān)系,將游程的臨時(shí)標(biāo)記和標(biāo)志位送回Ao、Ae數(shù)組中,將新建的代表標(biāo)記和合并等價(jià)標(biāo)記對(duì)的信息傳遞給Bn、Bt、Br存儲(chǔ)器,最終還要將游程的信息存入An存儲(chǔ)器中;結(jié)束區(qū)域檢測(cè)模塊根據(jù)Ao/Ae存儲(chǔ)器中存的上一行游程的標(biāo)記位,將上一行中未與當(dāng)前行連通的游程取出作為待檢測(cè)游程,將這些游程的代表標(biāo)記與當(dāng)前行所有游程的代表標(biāo)記進(jìn)行比較(需要與Br存儲(chǔ)器交互信息),鎖定已結(jié)束的游程,再將這些游程的代表標(biāo)記存入Af存儲(chǔ)器中;結(jié)束區(qū)域信息輸出模塊根據(jù)Af中存儲(chǔ)的代表標(biāo)記,將An存儲(chǔ)器中所有與之相等的游程全部輸出。在算法的硬件實(shí)現(xiàn)過程中,為了提高運(yùn)行速度,使用多個(gè)電路同時(shí)工作以充分利用硬件系統(tǒng)的并行處理能力。

4 實(shí)驗(yàn)結(jié)果及分析

為了對(duì)比本文算法與其他算法的性能,選取了2幅分辨率為512×512像素的圖像,分為記為圖A和圖B在圖像源一定的情況下,對(duì)比不同算法處理的運(yùn)行時(shí)間。由于其他算法都是在高速PC工作站上基于軟件運(yùn)行,因此這里引入頻率換算因數(shù)來有效地對(duì)比工作速度。各算法的類型和仿真平臺(tái)如表3所示。并且將本文提出的算法在Altera公司的StrtixIV系列EP4SGX530H H35C2板子上進(jìn)行了驗(yàn)證,證實(shí)了其硬件可行性。

表3 不同算法的類型和仿真平臺(tái)

仿真結(jié)果如表4所示,其中用到3個(gè)不同的仿真平臺(tái),平臺(tái)1為C language on a PC-based workstation(Intel Pentium D 3.0 GHz+3.0 GHz CPUs,2GB-Memory,Mandriva Linux OS);平臺(tái)2為C++language on a PC-based workstation(Inter Core i5 2.4 GHz+2.4 GHz CPUs,2GB-Memory);平臺(tái)3為Verilog language on Modelsim 10.2c @100 MHz。從表4可以看出,在頻率換算以后,本文的算法要快于其他4種算法,其中比He算法要快至少3倍以上,比BBDT算法要快至少9倍以上。考慮到仿真頻率較低,在最大工作頻率限度內(nèi)提高運(yùn)行頻率能夠極大提高處理速度,而且SMIC 0.18 um仿真庫并不是當(dāng)前最先進(jìn)的工藝,因此若將工藝尺寸減小,本文算法的工作性能還有很大的提升潛力。

表4 對(duì)比測(cè)試仿真結(jié)果

為了進(jìn)一步驗(yàn)證本算法的正確性和與已有算法相比較的優(yōu)勢(shì),在SIMPLIcity數(shù)據(jù)庫[18]中選取了500張分辨率都為512×512像素的圖片,將其分為9個(gè)不同疏密等級(jí)(即前景像素占總像素的比例),圖6為各算法在圖像密度不同時(shí)的柱型統(tǒng)計(jì)圖。

由圖6分析可得,本文算法在圖像疏密等級(jí)較低,圖像構(gòu)成復(fù)雜度稍低時(shí)具有明顯優(yōu)勢(shì),游程數(shù)量巨大,圖像復(fù)雜度太高時(shí)標(biāo)記速度會(huì)有所減慢,分析其原因主要是本文算法在掃描過程中實(shí)時(shí)輸出已結(jié)束游程的信息,這樣可以大大減少需要存儲(chǔ)的游程信息條目,但是代價(jià)是,在游程信息表中遍歷查找已結(jié)束游程需要耗費(fèi)絕大部分運(yùn)行時(shí)間,特別是游程數(shù)量巨大的情況。這主要是資源需求和運(yùn)算速度之間的折中問題。

圖6 各算法在圖像疏密不同時(shí)標(biāo)記時(shí)間對(duì)比圖

5 結(jié) 論

本文提出了一種快速連通區(qū)域標(biāo)記算法的硬件實(shí)現(xiàn)方法。算法的主要特點(diǎn)是在掃描過程中實(shí)時(shí)輸出檢測(cè)到的已結(jié)束區(qū)域信息,只需完整地掃描一遍圖像,就可以完成對(duì)所有區(qū)域的標(biāo)記,不僅避免了對(duì)整幅圖像標(biāo)記值的緩存,還減少了需要記錄的游程信息。通過對(duì)游程信息表存取機(jī)制的優(yōu)化,大大降低了算法的存儲(chǔ)資源需求,但是由于算法在掃描過程中實(shí)時(shí)輸出檢測(cè)的已結(jié)束游程信息,這樣可以減少存儲(chǔ)資源,而在游程信息表中遍歷查找已結(jié)束游程需要耗費(fèi)絕大部分運(yùn)行時(shí)間,特別是游程數(shù)量巨大、圖像復(fù)雜的情況,這主要是資源需求和運(yùn)算速度之間的折衷問題。因此,本文所提出的算法是一種對(duì)于小圖像特別高效的算法。