單次掃描連通域分析算法研究綜述

曲立國，陳國豪，胡 俊，陳 鵬

（1. 安徽師范大學(xué)物理與電子信息學(xué)院,安徽蕪湖 241002；2. 安徽省智能機(jī)器人信息融合與控制實(shí)驗(yàn)室,安徽蕪湖 241002）

1 引言

連通域標(biāo)記（Connected Component Labeling，CCL）和基于CCL 改進(jìn)的連通域分析（Connected Component Analysis，CCA）是二值圖像分析和圖像處理的重要步驟，在醫(yī)學(xué)［1～3］、自動(dòng)監(jiān)控系統(tǒng)［4～6］、天氣監(jiān)測［7］、人臉識(shí)別［8］和天文觀測［9］等諸多領(lǐng)域有廣泛應(yīng)用. 它對(duì)二值圖像中前景像素（也稱對(duì)象像素）進(jìn)行標(biāo)記，讓每個(gè)單獨(dú)的連通域形成一個(gè)被標(biāo)識(shí)的塊，進(jìn)而獲取這些區(qū)域的面積、邊界框和質(zhì)心等相關(guān)圖像特征信息.

為了不失一般性，在W×H像素大小的二值圖像中，坐標(biāo)為（x，y）的像素表示為b（x，y），其中0≤x≤W-1，0≤y≤H-1. 圖像內(nèi)像素值只有0 和1，假設(shè)0 代表背景像素，1代表前景像素.

CCL 算法常見的連通關(guān)系有四連通和八連通兩種，如圖1 所示. 任意像素b（x，y）的上下左右四個(gè)像素，即b（x，y-1），b（x，y+1），b（x-1，y），b（x+1，y）被稱為它的四連通像素. 四連通像素加上四個(gè)對(duì)角相鄰像素，即b（x-1，y-1），b（x+1，y-1），b（x-1，y+1），b（x+1，y+1）被稱為它的八連通像素.

圖1 四連通和八連通

根據(jù)圖1的連通關(guān)系，相互連通的對(duì)象像素屬于同一個(gè)連通域. 連通域標(biāo)記就是給屬于一個(gè)連通域的所有對(duì)象像素分配相同標(biāo)簽，利用唯一的標(biāo)簽區(qū)分圖像中不同連通域. 連通域是一副圖像中相互連通的對(duì)象像素的最大集合，所以一個(gè)連通域也可以被稱為一個(gè)物體對(duì)象.

自20 世紀(jì)60 年代以來，大量學(xué)者致力于連通域標(biāo)記算法的研究. Rosenfeld 等人［10］和Lumia 等人［11］設(shè)計(jì)了基于像素的連通域標(biāo)記算法；Ronse等人［12］設(shè)計(jì)了基于游程的連通域標(biāo)記算法. 現(xiàn)代算法都是在它們的基礎(chǔ)上發(fā)展而來的，根據(jù)算法通過圖像的掃描次數(shù)的不同，其可以分為以下幾類：（1）多次掃描標(biāo)記算法［13，14］；（2）基于輪廓跟蹤的標(biāo)記算法［15～18］；（3）兩次掃描標(biāo)記算法［19～39］；（4）單次掃描標(biāo)記算法［40～68］.

已有一些文章對(duì)CCL 算法進(jìn)行了比較. 文獻(xiàn)［30］對(duì)文獻(xiàn)［10，11，15，25～28］中提出的算法進(jìn)行了綜述，并提出了用于測試不同算法性能的基準(zhǔn). 此外，文獻(xiàn)［35］對(duì)基于標(biāo)簽傳播［15］和基于標(biāo)簽等價(jià)解析［22～26，32］的標(biāo)記算法進(jìn)行了綜述，詳細(xì)介紹了一些典型算法的原理，并給出了一些算法的偽代碼. 但這些比較綜述主要針對(duì)兩次掃描CCL算法，很少提及單次掃描算法.

單次掃描連通域標(biāo)記算法又稱為單次掃描連通域分析（CCA），也有文獻(xiàn)對(duì)CCA 算法進(jìn)行了比較. 文獻(xiàn)［50］對(duì)一些現(xiàn)有CCL 和CCA 算法進(jìn)行了比較，然而這篇文章對(duì)除了文獻(xiàn)［48］算法以外的所有算法都只是進(jìn)行了簡單的描述，并沒有詳細(xì)說明算法的原理和算法之間的聯(lián)系. 為此本文對(duì)最近十年來發(fā)展的單次掃描CCA 算法進(jìn)行分析，描述適用于單次掃描CCA 算法的聯(lián)合查找算法，闡述典型CCA 算法的原理，給出它們的偽代碼，并對(duì)算法FPGA 性能的實(shí)現(xiàn)情況進(jìn)行了比較.

2 聯(lián)合查找算法

無論是在CCL 算法還是CCA 算法中，標(biāo)簽等價(jià)關(guān)系的記錄和處理都是算法實(shí)現(xiàn)的重要操作，并且影響著算法處理效率. 聯(lián)合查找（Union-find）算法是記錄和解析標(biāo)簽等價(jià)關(guān)系的一種有效方法［50］，它通過一個(gè)聯(lián)合查找森林結(jié)構(gòu)實(shí)現(xiàn)，森林由相互獨(dú)立的聯(lián)合查找樹組成. 聯(lián)合查找樹的特點(diǎn)：（1）給每個(gè)連通域分配的臨時(shí)標(biāo)簽都是樹中的一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都連接到它所在樹中的父結(jié)點(diǎn)；（2）樹中的所有結(jié)點(diǎn)都是等價(jià)的，一棵樹代表一個(gè)連通域；（3）如果樹中一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)就是它本身，那么該結(jié)點(diǎn)被稱為該樹的根結(jié)點(diǎn)，根結(jié)點(diǎn)是樹中最小的標(biāo)簽，對(duì)應(yīng)著該樹代表連通域的根標(biāo)簽.

可以采用圖像進(jìn)一步表示聯(lián)合查找樹算法的結(jié)構(gòu)，做以下定義：結(jié)點(diǎn)Ni通過有向邊指向另一個(gè)結(jié)點(diǎn)Nj，有向邊E可以表示為Ni→Nj，其中Ni是Nj的子結(jié)點(diǎn)，Nj是Ni的父結(jié)點(diǎn). 一個(gè)結(jié)點(diǎn)可以有很多子結(jié)點(diǎn)，沒有子結(jié)點(diǎn)的結(jié)點(diǎn)是葉結(jié)點(diǎn). 所有結(jié)點(diǎn)的集合N（F）和有向邊集合E（F）構(gòu)成森林F，如式（1）所示：

每一個(gè)結(jié)點(diǎn)都沿著一條路徑連接到樹的根結(jié)點(diǎn)，路徑中有向邊E的條數(shù)就是該結(jié)點(diǎn)的等級(jí). 根結(jié)點(diǎn)的等級(jí)為0，其它結(jié)點(diǎn)比它的父結(jié)點(diǎn)等級(jí)高1，葉結(jié)點(diǎn)的等級(jí)最高，樹中葉結(jié)點(diǎn)的等級(jí)就是這棵樹的高度. 兩個(gè)連通域和它們對(duì)應(yīng)的聯(lián)合查找樹結(jié)構(gòu)F如圖2所示.

圖2 連通域示例和聯(lián)合查找樹數(shù)據(jù)結(jié)構(gòu)F

聯(lián)合查找樹已經(jīng)衍生出多種改進(jìn)算法，如快速查找（QuickFind）算法［37］、快速聯(lián)合（QuickUnion）算法［37］和帶有路徑壓縮的快速聯(lián)合（QuickUnion with Path Compassion）算法［37］. 在單次掃描CCA 算法中，一種有效的聯(lián)合查找算法是文獻(xiàn)［50］中提出的基于上下文（Context-based）的聯(lián)合查找算法，它不僅結(jié)合了快速查找和快速聯(lián)合的最佳特性，還加入年齡平衡（Agebalancing）［39］策略. 年齡平衡策略不再依據(jù)標(biāo)簽數(shù)值大小定義標(biāo)簽大小，而是依據(jù)分配標(biāo)簽的時(shí)間先后順序（即標(biāo)簽“年齡”），越早分配的標(biāo)簽?zāi)挲g越大，標(biāo)簽越小. 年齡平衡策略可以確保給連通域分配的初始標(biāo)簽始終是根標(biāo)簽，避免許多復(fù)雜的合并，簡化了算法計(jì)算復(fù)雜度.

基于上下文的聯(lián)合查找算法偽代碼如算法1所示，它主要包含新樹（Newtree）、查找（Find）、聯(lián)合（Union）和展平（Flatten）四個(gè)操作. 當(dāng)給新連通域分配新標(biāo)簽時(shí)，將會(huì)在森林中創(chuàng)建一個(gè)新樹，樹的根結(jié)點(diǎn)n指向自己. 通常，查找操作會(huì)迭代找出結(jié)點(diǎn)的根結(jié)點(diǎn)［38］，但算法1中查找操作只找出結(jié)點(diǎn)n的父結(jié)點(diǎn). 在聯(lián)合操作中連接結(jié)點(diǎn)u和v，需要對(duì)兩個(gè)結(jié)點(diǎn)進(jìn)行一次查找，找出它們的父結(jié)點(diǎn)e和f. 當(dāng)e小于f時(shí)，把e作為f的父結(jié)點(diǎn)；而當(dāng)e大于f時(shí)，不僅要把f作為e的父結(jié)點(diǎn)，還需要把這兩個(gè)合并標(biāo)簽壓入鏈堆棧中保存. 展平操作在圖像每一行行尾執(zhí)行，將鏈堆棧中的標(biāo)簽反向彈出，把較小標(biāo)簽的父結(jié)點(diǎn)作為較大標(biāo)簽的父結(jié)點(diǎn)，從而解析兩個(gè)標(biāo)簽的等價(jià)關(guān)系.

3 連通域標(biāo)記

表1 從以下幾個(gè)方面對(duì)典型CCL 算法和CCA 算法的性能進(jìn)行了比較：（1）掃描次數(shù)和連通性；（2）掃描和標(biāo)記單元；（3）運(yùn)行時(shí)間復(fù)雜度和采用的等價(jià)解析策略；（4）是否重用標(biāo)簽. 圖3 列舉了CCL 算法和CCA 算法主要的掃描窗口，其中圖3（d）是文獻(xiàn)［54］中提出的TRSP（Tang’s Run-based Single Pass）算法的掃描窗口，該算法將會(huì)在4.2.1節(jié)分析.

表1 典型CCL和CCA算法的性能比較

Rosenfeld 等人［10］在1966 年提出的OCL（Original Connected-component Labeling）算法是經(jīng)典連通域標(biāo)記算法，它采用如圖3（a）所示的掃描窗口對(duì)輸入圖像進(jìn)行兩次掃描并生成一個(gè)包含標(biāo)記結(jié)果的輸出圖像. 第一次掃描圖像時(shí)給像素分配臨時(shí)標(biāo)簽：當(dāng)前像素如果是背景像素，則標(biāo)記為0；如果是對(duì)象像素，需要根據(jù)四個(gè)鄰域像素信息為當(dāng)前像素選擇臨時(shí)標(biāo)簽. 如果鄰域都是背景像素，則分配一個(gè)新標(biāo)簽；如果鄰域內(nèi)只存在一個(gè)標(biāo)簽，則把該標(biāo)簽分配給當(dāng)前像素；如果鄰域中存在兩個(gè)不同標(biāo)簽，則把較小標(biāo)簽分配給當(dāng)前像素，并在等價(jià)表中記錄兩個(gè)標(biāo)簽的等價(jià)關(guān)系. 第二次掃描圖像時(shí)用等價(jià)表中的代表標(biāo)簽（連通域中最小的標(biāo)簽）替換所有臨時(shí)標(biāo)簽.OCL 算法需要為最終圖像和等價(jià)表分配足夠的內(nèi)存，并且由于在檢測等價(jià)關(guān)系時(shí)重復(fù)采用排序算法，計(jì)算量較大.

算法1 基于上下文的聯(lián)合查找算法1234567891 0 11 12 13 14 15 16 17 18 19 20 21 22 Newtree(node n)T[n]=n END OF Newtree Find(node n)RETURN T[n]END OF Find Union(node u,node v)e=Find(node u)f=Find(node v)IF e

圖3 CCL和CCA算法的掃描窗口

為了減少內(nèi)存需求，Haralick 等人［13］提出一種多次掃描算法，該算法根據(jù)鄰域像素信息對(duì)二值圖像進(jìn)行交替地向前掃描（圖3（a））和向后掃描（圖3（b）），在交替掃描中處理標(biāo)簽等價(jià)關(guān)系，不需要等價(jià)表和額外內(nèi)存空間. 交替掃描圖像使得算法掃描次數(shù)不固定，連通域幾何形狀越復(fù)雜，掃描次數(shù)越多.Suzuki 等人［14］提出的SCL（Suzuki’s Connected-component Labeling）算法對(duì)Haralick 等人的算法做出了改進(jìn)，采用標(biāo)簽連接表記錄和處理標(biāo)簽等價(jià)關(guān)系.SCL 算法也需要多次掃描，作者證明最大掃描次數(shù)為4次，算法執(zhí)行時(shí)間與圖像連通域中的像素?cái)?shù)成正比.

Chang等人［15］提出的算法采用了完全不同的方法，通過輪廓跟蹤（Contour Tracing，CT）技術(shù)標(biāo)記連通域.CT算法從上到下、從左到右逐行掃描二值圖像，當(dāng)遇到一個(gè)連通域的外部輪廓或內(nèi)部輪廓時(shí)，采用輪廓跟蹤技術(shù)給輪廓上所有對(duì)象像素分配相同的標(biāo)簽，執(zhí)行輪廓跟蹤的同時(shí)也標(biāo)記與輪廓相連的背景像素以保證輪廓只會(huì)被跟蹤一次. 標(biāo)記完連通域外部輪廓之后，整個(gè)連通域的標(biāo)簽就確定了，給連通域內(nèi)部像素分配的標(biāo)簽都與外部輪廓標(biāo)簽相同. 作者已經(jīng)證明CT 算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系.

He 等人［22］提出的基于配置轉(zhuǎn)換的標(biāo)記算法（Con?figuration Transition-based Connected component Label?ing，CTCL）采用如圖4（a）所示的掃描窗口一次性處理兩個(gè)像素，通過考慮掃描窗口中像素的9 種配置的轉(zhuǎn)換，盡可能多地利用處理后兩個(gè)像素時(shí)檢測到的信息處理當(dāng)前兩個(gè)像素，使在第一次掃描中要檢查的像素平均數(shù)目減少，從而加快算法處理速度.Zhao等人［23］提出的ICTCL（Improved CTCL）算法對(duì)CTCL 算法做出改進(jìn)，進(jìn)一步減少處理像素要檢查的像素平均數(shù)目，采用如圖4（b）所示的掃描窗口一次處理三個(gè)像素，考慮的配置有16種.CTCL算法和ICTCL算法都采用等價(jià)標(biāo)簽集（Equivalent Label Set）策略記錄和解析標(biāo)簽等價(jià)關(guān)系. 文獻(xiàn)［35］已經(jīng)證明這兩種算法的時(shí)間復(fù)雜度都與圖像大小呈線性關(guān)系. 本文不介紹等價(jià)標(biāo)簽集策略，相關(guān)細(xì)節(jié)參考文獻(xiàn)［22，23］.

圖4 CTCL和ICTCL算法的掃描窗口

He 等人［24］提出的基于游程的一次半掃描算法（Run-based Connected-component Labeling，RCL）采用等價(jià)標(biāo)簽集策略記錄和解析標(biāo)簽等價(jià)關(guān)系.RCL 算法把一個(gè)游程視為一個(gè)超級(jí)像素，在第一次掃描中給每個(gè)游程而不是給游程中的像素分配臨時(shí)標(biāo)簽. 由于第一次掃描記錄了所有游程數(shù)據(jù)，第二次掃描只需重新掃描對(duì)象像素而不用掃描背景像素，故作者稱算法為一次半掃描算法. 一般圖片中游程數(shù)量比對(duì)象像素?cái)?shù)量少得多，采用基于游程的技術(shù)將大大減少分配標(biāo)簽的成本.RCL 算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系，雖然作者聲稱該算法是一次半掃描，但是實(shí)質(zhì)上還是兩次掃描算法.

Grana 等人［26］提出的基于像素塊的兩次掃描標(biāo)記算法（Block-based Connected-component Labeling，BCL）采用等價(jià)標(biāo)簽集策略記錄和解析等價(jià)標(biāo)簽. 由于一個(gè)2×2 的塊內(nèi)所有像素必定屬于同一連通域，BCL 算法把基于像素的標(biāo)簽處理擴(kuò)展到塊上，將如圖3（a）所示的掃描窗口中的像素替換成2×2的塊，擴(kuò)展后可以一次實(shí)現(xiàn)對(duì)20 個(gè)像素的連通關(guān)系分析.BCL 算法在第一次掃描中給像素塊分配臨時(shí)標(biāo)簽并記錄塊之間的等價(jià)關(guān)系，在第二次掃描中把塊的代表標(biāo)簽分配給塊中每個(gè)對(duì)象像素. BCL 算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系.

4 連通域分析

CCL 在處理圖像時(shí)需要兩次掃描，第一次掃描分配臨時(shí)標(biāo)簽，第二次掃描重新標(biāo)記，并生成一個(gè)和圖像同樣大的標(biāo)記圖像. 圖像分析中最重要的是連通域的特征數(shù)據(jù)提取，標(biāo)記圖像本質(zhì)上只是一個(gè)輔助圖像數(shù)據(jù)結(jié)構(gòu). 如果在第一次掃描中直接提取特征數(shù)據(jù)，那么第二次掃描就可以省去，兩次掃描就可以減少到單次掃描. 在單次掃描圖像的同時(shí)提取特征數(shù)據(jù)并動(dòng)態(tài)地解決數(shù)據(jù)關(guān)聯(lián)問題，這是近十年來研究發(fā)展的單次掃描CCA 算法的原理.CCA 算法可以處理位流圖像，且不需要儲(chǔ)存標(biāo)簽圖像，只需要少量內(nèi)存，這些特性使它們適合在FPGA 上實(shí)現(xiàn)，完成圖像實(shí)時(shí)高速處理，因此單次掃描CCA 算法都是基于FPGA 硬件架構(gòu)設(shè)計(jì)的.

4.1 基于像素的單次掃描CCA算法

基于像素的單次掃描CCA 算法處理圖像時(shí)考慮像素之間的連接關(guān)系，本節(jié)分析以下幾種CCA算法：

（1）原始的單次掃描（Original Single Pass，OSP）CCA算法［42］；

（2）改進(jìn)的OSP（Improved OSP，IOSP）CCA算法［45］；

（3）單次查找單次掃描（Single Lookup Single Pass，SLSP）CCA算法［48］；

（4）雙重查找單次掃描（Double Lookup Single Pass，DLSP）CCA算法［50］；

（5）“Z”字形單次掃描（Zig-Zag Single Pass，ZZSP）CCA算法［51］.

4.1.1 OSP算法

Bailey 等人［42］提出的OSP 算法采用基于上下文的聯(lián)合查找算法記錄和解析標(biāo)簽等價(jià)關(guān)系，它并不回收標(biāo)簽，分配標(biāo)簽的順序按照標(biāo)簽數(shù)值由小到大排序，因此不引入年齡平衡策略.OSP算法的硬件架構(gòu)如圖5所示，主要包含鄰域標(biāo)簽處理模塊、標(biāo)簽選擇模塊、合并控制和合并表模塊以及數(shù)據(jù)表模塊，行緩沖區(qū)只緩存一行圖像像素.

圖5 OSP算法的架構(gòu)

OSP 算法的掃描窗口和標(biāo)簽選擇策略與OCL 算法相同，由鄰域標(biāo)簽處理模塊給掃描窗口提供鄰域標(biāo)簽LA，LB，LC和LD，標(biāo)簽選擇模塊根據(jù)鄰域標(biāo)簽信息給當(dāng)前像素分配標(biāo)簽LX，同時(shí)數(shù)據(jù)表累加連通域的特征數(shù)據(jù).為了減少對(duì)內(nèi)存訪問次數(shù)，鄰域標(biāo)簽更新采用標(biāo)簽傳播方法，執(zhí)行步驟如算法2 所示，其中添加符號(hào)“'”的標(biāo)簽表示上一時(shí)鐘周期的標(biāo)簽.

算法2 標(biāo)簽傳播12345678 LA=LB'LD=LX'IF B&D THEN LB=LX'ELSE LB=LC'END IF LC=Find(C)

當(dāng)發(fā)生標(biāo)簽合并時(shí)，合并控制器控制合并表記錄合并操作中生成的標(biāo)簽等價(jià)關(guān)系. 如圖6（a）所示的傳播合并模式生成的標(biāo)簽等價(jià)關(guān)系可以直接記錄在合并表中，因?yàn)檩^大標(biāo)簽在合并之后不再出現(xiàn)（鏈的長度總是為1），不會(huì)影響后續(xù)標(biāo)記結(jié)果. 而如圖6（b）所示的非傳播合并模式會(huì)形成一條長標(biāo)簽鏈，被稱為鏈?zhǔn)叫?yīng)［54］. 對(duì)于非傳播合并模式，必須把兩個(gè)合并標(biāo)簽記錄在一個(gè)鏈堆棧中，在行尾展平操作中解析標(biāo)簽等價(jià)關(guān)系該操作被（稱為解鏈）.

圖6 兩種合并模式

OSP算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系，數(shù)據(jù)表和合并表大小與標(biāo)簽數(shù)量成正比，儲(chǔ)存合并標(biāo)簽的鏈堆棧大小與圖像寬度W成正比.

4.1.2 SLSP算法

OSP 算法的標(biāo)簽數(shù)量很多，與標(biāo)簽數(shù)量相關(guān)的結(jié)構(gòu)占用了大量內(nèi)存空間，為了減少內(nèi)存需求，回收標(biāo)簽方法被提出. Ma 等人［45］發(fā)現(xiàn)一行像素中標(biāo)簽數(shù)量最多為圖像寬度的一半，把標(biāo)簽數(shù)量壓縮到這樣大小可以節(jié)省可觀的內(nèi)存.Ma 在IOSP 算法中采用了激進(jìn)的重標(biāo)記方法實(shí)現(xiàn)了這一點(diǎn)，在圖像每一行開頭采用標(biāo)簽0 重新標(biāo)記圖像，使得標(biāo)簽數(shù)目最大為W/2，這種重標(biāo)記技術(shù)需要一個(gè)轉(zhuǎn)換表轉(zhuǎn)換兩行標(biāo)簽的連接關(guān)系.

Klaiber 等人［48］提出的SLSP 算法采用一種新的標(biāo)簽回收方法改進(jìn)了OSP 算法，基于硬件實(shí)現(xiàn)的算法如算法3 所示，對(duì)每個(gè)像素執(zhí)行標(biāo)簽傳播（Label Propa?gate）、更新數(shù)據(jù)結(jié)構(gòu)（Update Data Structure）和解析過期標(biāo)簽（Resolve Stale Labels）三個(gè)操作，在一行像素行尾執(zhí)行展平操作. 采用標(biāo)簽回收策略后，更新數(shù)據(jù)結(jié)構(gòu)具體操作如算法4所示.

算法3 SLSP算法12345678 FOR y=0 TO H-1 DO FOR x=0 TO W-1 DO Label Propagate Update Data Structure Resolve Stale Labels END FOR Flatten END FOR算法4 更新數(shù)據(jù)結(jié)構(gòu)1234567891 0 11 12 13 14 15 16 17 18 19 20 21 22 IF X THEN IF!A&!B&!C&!D THEN△New label LX=Newtree V[LX]=TRUE ELSE△label merge IF(A|D)&C&(LA or D ≠LC)THEN LX=Union(LA or D,LC)IF V[Max(LA or D,LC)]THEN Max(LA or D,LC)to reuse END IF V[Max(LA or D,LC)]=FALSE ELSE△label copy LX=LabelCopy(LA or D,LB,LC)END IF IF!V[LX]THEN Push(LX)to SLS END IF END IF AT[LX]=Y ELSE LX=0 END IF

當(dāng)連通域的所有像素都被標(biāo)簽標(biāo)記，我們稱連通域標(biāo)記完成，標(biāo)記標(biāo)簽在后續(xù)掃描中不會(huì)再出現(xiàn)，這種標(biāo)簽可以回收重利用.SLSP 算法的標(biāo)簽回收策略采用活動(dòng)標(biāo)簽AT（Active Tag）關(guān)聯(lián)每個(gè)標(biāo)簽，在每一行動(dòng)態(tài)地檢查連通域是否標(biāo)記完成，通過回收標(biāo)簽減少標(biāo)簽數(shù)量. 重用標(biāo)簽打亂了標(biāo)簽排列順序，因此算法中引入增強(qiáng)標(biāo)簽（Augmented label）實(shí)現(xiàn)年齡平衡策略，增強(qiáng)標(biāo)簽由行號(hào)L·rw 與索引L·index 組成，如圖6 所示的兩種合并模式可以通過式（2）評(píng)估，其中LAorD表示LA或LD.

OSP 算法在行尾解鏈?zhǔn)孤?lián)合查找樹的高度不大于1，但在下一行中高度為1 的樹和另一棵樹合并將有可能產(chǎn)生高度為2 的樹. 在行尾之前，如果再次遇到樹的葉結(jié)點(diǎn)（等級(jí)為2），進(jìn)行一次查找將無法訪問到樹的根標(biāo)簽，這種葉結(jié)點(diǎn)對(duì)應(yīng)的標(biāo)簽稱為過期標(biāo)簽. 算法設(shè)置一個(gè)有效性標(biāo)記V（Valid tag）跟蹤標(biāo)簽是否為過期標(biāo)簽，過期標(biāo)簽將記錄在過期標(biāo)簽堆棧SLS（Stale Label Stack）中，隨后在解析過期標(biāo)簽操作中處理. 當(dāng)過期標(biāo)簽被分配給當(dāng)前像素時(shí)，特征數(shù)據(jù)將無法累加到正確的標(biāo)簽上，需要先把特征數(shù)據(jù)暫存起來，等過期標(biāo)簽的根標(biāo)簽進(jìn)入鄰域時(shí)再將特征數(shù)據(jù)累加到根標(biāo)簽上.

SLSP 算法的時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系，數(shù)據(jù)表、合并表和鏈堆棧大小都與圖像寬度W成正比.

4.1.3 DLSP算法

處理過期標(biāo)簽需要額外的操作步驟，這導(dǎo)致算法復(fù)雜度變高，處理速度變慢.Klaiber 等人［50］提出DLSP算法，采用雙重查找消除了過期標(biāo)簽，并證明雙重查找一定會(huì)找到根標(biāo)簽，這樣消除了和過期標(biāo)簽相關(guān)的任何操作，降低了算法復(fù)雜度，算法實(shí)現(xiàn)如算法5所示.

DLSP 算法以像素為掃描單元，以游程為標(biāo)記單元，把基于像素的處理與基于游程的處理統(tǒng)一起來，進(jìn)一步降低了算法計(jì)算復(fù)雜度. 同一游程的所有像素都有相同根標(biāo)簽，因此只需要對(duì)游程中第一個(gè)像素進(jìn)行雙重查找就可以找到整個(gè)游程的根標(biāo)簽，后續(xù)像素標(biāo)簽只需要傳遞而無需再次查找.

算法5 DLSP算法1234567 FOR y=0 TO H-1 DO FOR x=0 TO W-1 DO Label Propagate Update Data Structure END FOR Flatten END FOR

DLSP 算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系，在存儲(chǔ)空間上與SLSP算法相比減少了過期標(biāo)簽相關(guān)的數(shù)據(jù)結(jié)構(gòu).

4.1.4 ZZSP算法

DLSP 算法仍然存在鏈?zhǔn)叫?yīng)，需要消耗額外的時(shí)鐘解析標(biāo)簽鏈，Bailey 等人［51］提出的ZZSP 算法解決了這個(gè)問題. ZZSP 算法采用了“Z”字形（Zig-Zag）掃描替換光柵式掃描，交替采用如圖3（a）和圖3（c）所示的掃描窗口每隔一行以相反方向掃描，在下一行掃描中動(dòng)態(tài)解析鏈?zhǔn)叫?yīng)，也消除了行尾的展平操作. ZZSP 算法實(shí)現(xiàn)如算法6 所示，對(duì)每個(gè)像素只需執(zhí)行標(biāo)簽傳播（Label Propagate）和更新數(shù)據(jù)結(jié)構(gòu)（Update Data Struc?ture）兩個(gè)操作. 當(dāng)掃描從行尾進(jìn)入到下一行行首時(shí)，需要翻轉(zhuǎn)窗口以調(diào)整掃描順序，操作步驟如算法6 中第5～7行所示.

算法6 ZZSP算法1234567891 0 Line=FALSE FOR y=0 TO H-1 DO FOR x=0 TO W-1 IF y=even ELSE x=W-1 to 0 DO IF Line THEN 11 12 13 14 15 LA or D=0 LB=LX LC=LD Line=FALSE ELSE Label Propagate END IF Updata Data Structure END FOR Line=TRUE END FOR

與年齡平衡策略類似，ZZSP 算法依據(jù)掃描順序定義兩個(gè)像素之間的優(yōu)先級(jí)關(guān)系，如式（3）所示：

其中P1

在SLSP 和DLSP 算法中，活動(dòng)標(biāo)簽AT 只記錄與標(biāo)簽相關(guān)的行號(hào)，而ZZSP 算法在數(shù)據(jù)表DT（Data Table）中引入AT，記錄與每個(gè)標(biāo)簽相關(guān)的坐標(biāo)，如式（4）所示：

當(dāng)掃描窗口通過該坐標(biāo)，即確定該標(biāo)簽對(duì)應(yīng)連通域已經(jīng)標(biāo)記完成時(shí)，標(biāo)簽將回收重利用. 在標(biāo)簽復(fù)制和合并操作中，活動(dòng)標(biāo)簽會(huì)跟隨數(shù)據(jù)表一起更新，活動(dòng)標(biāo)簽的更新將遵循公式（3）的優(yōu)先級(jí)定義，對(duì)于兩個(gè)活動(dòng)標(biāo)簽AT1和AT2，當(dāng)AT1的優(yōu)先級(jí)高于AT2時(shí)，將會(huì)保留AT2，反之保留AT1.

ZZSP 算法時(shí)間復(fù)雜度與圖像大小呈線性關(guān)系，它需要額外的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)掃描順序的轉(zhuǎn)換.

4.2 基于游程的單次掃描CCA算法

一行連續(xù)連接的對(duì)象像素被稱為游程，這些像素必定有相同標(biāo)簽. 基于游程技術(shù)處理圖像，可以顯著減少標(biāo)簽總數(shù)，有效降低解析標(biāo)簽等價(jià)關(guān)系的復(fù)雜度，加快算法處理速度. 基于游程的算法把游程視作一個(gè)超級(jí)像素，不再檢測像素之間的連接關(guān)系，而是考慮游程之間的連接關(guān)系.

Trein 等人［52］提出基于游程長度編碼（Trein’s Run Length Encoding，TRLE）的CCA 算法，采用游程壓縮圖像，僅采用開始和結(jié)束位置描述每個(gè)游程，在一個(gè)時(shí)鐘周期內(nèi)只需要發(fā)送兩個(gè)位置就可以代表游程中所有對(duì)象像素，加快了算法處理速度. 算法為每個(gè)游程分配一個(gè)臨時(shí)標(biāo)簽，通過比較相鄰行之間的游程關(guān)系確定標(biāo)簽等價(jià)關(guān)系. 為了正確解析一些復(fù)雜圖像帶來的合并標(biāo)簽等價(jià)關(guān)系，作者使用一個(gè)從舊標(biāo)簽指向新標(biāo)簽的指針，當(dāng)試圖更新舊標(biāo)簽的特征數(shù)據(jù)時(shí)，會(huì)因?yàn)橹羔樦赶蛐聵?biāo)簽而最終把特征數(shù)據(jù)累加更新到新標(biāo)簽上.

Zhao 等人［53］提出了基于游程單次掃描（Zhao’s Run-based Single Pass，ZRSP）的CCA 算法，在實(shí)時(shí)自動(dòng)目標(biāo)識(shí)別系統(tǒng)上實(shí)現(xiàn)了對(duì)位流圖像數(shù)據(jù)的處理. 該算法以像素為掃描單元，以游程為標(biāo)記單元，結(jié)合了像素和游程的優(yōu)點(diǎn)，并設(shè)計(jì)多層索引結(jié)構(gòu)保持相鄰行之間標(biāo)簽的正確對(duì)應(yīng)關(guān)系，但是在某些更復(fù)雜的圖像中，仍然存在鏈?zhǔn)絾栴}.

4.2.1 TRSP算法

Tang 等人［54］提出的TRSP 算法采用如圖3（d）所示的掃描窗口標(biāo)記游程，并基于鏈表（Linked list）結(jié)構(gòu)解析標(biāo)簽等價(jià)關(guān)系，消除了鏈?zhǔn)叫?yīng). 為了降低內(nèi)存需求，算法采用了簡單且高效的標(biāo)簽回收策略，給游程分配的標(biāo)簽從0 到W/2（W為圖像寬度），當(dāng)標(biāo)簽到達(dá)最大值（W/2）時(shí)重新從0 計(jì)數(shù). 這種自動(dòng)回收標(biāo)簽技術(shù)無需額外的數(shù)據(jù)結(jié)構(gòu)跟蹤標(biāo)簽，也無需額外的控制邏輯判斷連通域是否標(biāo)記完成，減少了算法的內(nèi)存空間消耗并降低了算法計(jì)算復(fù)雜度. 算法實(shí)現(xiàn)過程如圖7 所示：首先為游程分配臨時(shí)標(biāo)簽，再基于鏈表結(jié)構(gòu)建立游程標(biāo)簽等價(jià)關(guān)系，然后根據(jù)標(biāo)簽等價(jià)關(guān)系計(jì)算對(duì)象特征數(shù)據(jù)，最后在標(biāo)簽失效前通過鏈表傳遞標(biāo)簽等價(jià)關(guān)系和特征數(shù)據(jù). 圖像填充過程為原始圖像填充額外對(duì)象像素，是個(gè)可選過程.

圖7 TRSP算法概述

TRSP 算法引入Next，Head，Tail和Data 四個(gè)表建立鏈表結(jié)構(gòu)，其中Head 和Next 是主表，Tail 和Data 是次表，次表只能由主表Head 索引. Data 表存儲(chǔ)連通域特征值數(shù)據(jù)，Head，Tail 和Next 表充當(dāng)指針構(gòu)建并處理標(biāo)簽等價(jià)關(guān)系. 其中Head 和Tail 指針將記錄前一行的游程標(biāo)簽，在后續(xù)掃描中通過指針的轉(zhuǎn)換實(shí)現(xiàn)游程標(biāo)簽轉(zhuǎn)換，表示兩行游程的標(biāo)簽等價(jià).Next 指針可以在游程列表中插入新標(biāo)簽，將新標(biāo)簽附加到游程列表末尾以表示標(biāo)簽等價(jià). 圖8 的示例說明指針的用法，圖中前一行有標(biāo)簽Lp，當(dāng)前行有等效游程列表L1→L2→L3，假設(shè)它們屬于同一個(gè)連通域，有以下定義：

圖8 Next,Head和Tail指針的用法

（1）前一行標(biāo)簽的Head 表示當(dāng)前行等效游程列表的第一個(gè)元素，有Head［Lp］=L1；

（2）標(biāo)簽的Tail 是等效游程列表的最后一個(gè)元素，有Tail［L1］=L3，也等價(jià)于Tail［Head［Lp］］=L3；

（3）Next 指向游程列表中下一個(gè)元素，對(duì)于當(dāng)前行等效游程列表，有Next［L1］=L2，Next［L2］=L3.

采用這種鏈表結(jié)構(gòu)，只需對(duì)Head，Tail 和Next 表進(jìn)行單次寫入即可完成標(biāo)簽等價(jià)關(guān)系解析，完全避免了鏈?zhǔn)叫?yīng)，實(shí)現(xiàn)了最大的吞吐量.

4.3 其它單次掃描CCA算法

本節(jié)主要分析兩種算法：（1）Gu 等人［56］提出的基于單元單次掃描（Cell-based Single Pass，CSP）的CCA 算法；（2）Jeong 等人［58］提出的單次掃描（Jeong’s Single Pass，JSP）CCA算法.

4.3.1 CSP算法

CSP 算法采用單元（Cell）壓縮圖像，與BCL［26］算法有相似之處，BCL算法采用2×2大小的塊替換像素，CSP算法的單元大小為n×n，并不局限于2×2. 對(duì)于每一個(gè)單元，只要單元中存在對(duì)象像素，那么整個(gè)單元就可以看成一個(gè)對(duì)象單元，當(dāng)單元被分配標(biāo)簽后，單元中所有像素（無論是否為對(duì)象像素）都會(huì)獲得相同標(biāo)簽.

當(dāng)N=nM時(shí)，CSP 算法把N×N大小的像素圖像壓縮成M×M大小的單元圖像.CSP 算法只考慮四連通性，假設(shè)b（x，y）表示坐標(biāo)（x，y）的單元，其中0≤x≤M-1，0≤y≤M-1，當(dāng)前單元b（x，y）對(duì)應(yīng)標(biāo)簽表示為LX，它上方單元b（x，y-1）對(duì)應(yīng)標(biāo)簽表示為Lup，它左邊單元b（x-1，y）對(duì)應(yīng)標(biāo)簽表示為Lleft，為當(dāng)前單元選擇標(biāo)簽如算法7所示.

算法7 CSP算法1234567891 0 11 IF b(x,y-1)=b(x-1,y)=0 THEN LX=Lnew ELSE IF b(x,y-1)=1,b(x-1,y)=0 THEN LX=Lup ELSE IF b(x,y-1)=0,b(x-1,y)=1 THEN LX=Lleft ELSE IF b(x,y-1)=b(x-1,y)=1,Lup=Lleft THEN LX=Lleft ELSE b(x,y-1)=b(x-1,y)=1,Lup ≠Lleft LX=Min(Lup,Lleft)END IF

CSP 算法采用重標(biāo)記存儲(chǔ)器（Relabeling Memory）記錄和解析標(biāo)簽等價(jià)關(guān)系，在每行行尾根據(jù)記錄結(jié)果從右到左將臨時(shí)標(biāo)簽替換成新標(biāo)簽進(jìn)行重新標(biāo)記.

當(dāng)n=1時(shí)，CSP算法與基于像素的CCA 算法有相同結(jié)果，當(dāng)n> 1 時(shí)，兩者的結(jié)果將并不完全一致，因?yàn)镃SP 算法中被認(rèn)為相互連接的對(duì)象單元中可能有并不相連的像素. 這是考慮算法計(jì)算復(fù)雜度和結(jié)果精確度之間的結(jié)果. 當(dāng)n>1時(shí)，CSP算法的計(jì)算復(fù)雜度和內(nèi)存消耗從O（N2）降低到O（M2）.

4.3.2 JSP算法

為了消除鏈?zhǔn)叫?yīng)，JSP 算法提出了一種無標(biāo)簽合并周期的硬件架構(gòu)，如圖9所示. 八連通檢查器（8-Con?nectivity Checker）采用如圖3（a）所示的掃描窗口，遵循OCL 算法的標(biāo)簽選擇策略為當(dāng)前像素選擇標(biāo)簽；信息提取器（Information Extractor）為標(biāo)記連通域累加更新特征數(shù)據(jù)；標(biāo)簽堆棧（Label Stack）用來管理和回收標(biāo)簽，新分配標(biāo)簽從堆棧頭部彈出，回收標(biāo)簽存放在堆棧尾部. 標(biāo)簽移位寄存器在合并發(fā)生后的下個(gè)時(shí)鐘周期里把所有舊標(biāo)簽直接替換成新標(biāo)簽，因此無需解析標(biāo)簽等價(jià)關(guān)系.

圖9 JSP算法的硬件架構(gòu),其中紅線表示S1的輸入和輸出

該架構(gòu)采用標(biāo)簽移位寄存器替換行緩沖區(qū)儲(chǔ)存標(biāo)簽信息，相鄰標(biāo)簽移位寄存器之間有一個(gè)條件選擇器S1，S1的輸入、輸出在圖9中用紅色標(biāo)出. 標(biāo)簽移位寄存器中儲(chǔ)存的標(biāo)簽在每個(gè)時(shí)鐘周期向左移動(dòng)，作為條件選擇器輸入標(biāo)簽LS. 八連通檢查器根據(jù)掃描窗口為當(dāng)前像素分配標(biāo)簽并儲(chǔ)存在標(biāo)簽移位寄存器R0中，同時(shí)生成event 信號(hào)和輸入標(biāo)簽Lmax，Lmin. 條件選擇器在event 信號(hào)控制下，動(dòng)態(tài)地從三個(gè)輸入標(biāo)簽中選擇輸出標(biāo)簽到下一個(gè)標(biāo)簽移位寄存器.

發(fā)生合并事件時(shí)，event 信號(hào)輸出1，合并中較大標(biāo)簽指定為Lmax，較小標(biāo)簽指定為Lmin，將它們輸入到條件選擇器中，對(duì)LS與Lmax進(jìn)行比較，如果相同說明LS是舊標(biāo)簽，輸出Lmin，不相同則輸出LS. 對(duì)于非合并事件，event信號(hào)輸出0，標(biāo)簽LS在移位時(shí)不改變.

5 比較與分析

本節(jié)對(duì)上述幾種CCA 算法進(jìn)行評(píng)估，這些算法都在它們提出的相應(yīng)硬件架構(gòu)中實(shí)現(xiàn)，在下文中提到算法簡稱即代表其硬件架構(gòu). 對(duì)于不同分辨率圖像，CCA硬件架構(gòu)的內(nèi)存消耗大小是評(píng)價(jià)該架構(gòu)實(shí)現(xiàn)位流圖像處理的重要指標(biāo)之一. 因此本文將從內(nèi)存消耗和最壞情況吞吐量等方面分析這些算法，并比較它們的硬件架構(gòu)性能. 這些算法數(shù)據(jù)都是根據(jù)它們報(bào)告的結(jié)果近似計(jì)算的，但不失一般性.

5.1 內(nèi)存需求分析

表2 比較了OSP［42］，IOSP［45］，SLSP［48］，DLSP［50］，ZZSP［51］，TRSP［54］和JSP［58］算法對(duì)W×H大小圖像的內(nèi)存需求；表3 比較了OSP 和JSP 算法對(duì)不同分辨率圖像的數(shù)據(jù)存儲(chǔ)所需內(nèi)存位數(shù)；圖10 比較了IOSP，SLSP，DLSP，ZZSP 和TRSP 算法對(duì)不同分辨率圖像的內(nèi)存總數(shù).

圖10 幾種CCA算法處理不同分辨率圖像的內(nèi)存位數(shù)比較

表2中為了進(jìn)行公平的比較，假設(shè)所有算法都是對(duì)W×H像素大小圖像進(jìn)行處理，提取特征數(shù)據(jù)包括面積（Area）和邊界框（Bounding box）. 標(biāo)簽數(shù)量NL是所有架構(gòu)的關(guān)鍵因素，它直接決定了存儲(chǔ)器的深度和寬度. 標(biāo)簽重用FIFO 儲(chǔ)存所有標(biāo)簽，它的大小為標(biāo)簽數(shù)量NL乘以標(biāo)簽寬度WL，標(biāo)簽寬度由WL=log2NL計(jì)算得到. 行緩沖區(qū)RB（Row Buffer）緩存一行像素的臨時(shí)標(biāo)簽，它的大小為W×WL. 合并表MT記錄標(biāo)簽之間的等價(jià)關(guān)系，它的深度為標(biāo)簽數(shù)量NL，寬度為標(biāo)簽寬度WL，大小為NL×WL. 數(shù)據(jù)表DT 儲(chǔ)存標(biāo)簽對(duì)應(yīng)連通域的特征數(shù)據(jù)，數(shù)據(jù)表深度為標(biāo)簽數(shù)量NL，寬度為特征數(shù)據(jù)寬度WD，大小為NL×WD. 由于提取的特征數(shù)據(jù)包括面積和邊界框，可以計(jì)算出特征數(shù)據(jù)寬度為WD=2 log2W+2 log2H+log2WH.

表2 不同單次掃描CCA架構(gòu)對(duì)于W×H大小圖像的內(nèi)存需求

OSP算法不回收標(biāo)簽，對(duì)標(biāo)簽的計(jì)數(shù)只需簡單的計(jì)數(shù)器而不采用FIFO 寄存器，因此標(biāo)簽數(shù)量取決于圖像大小，最大數(shù)目為WH/4.OSP 算法在行尾進(jìn)行反向解鏈，需要一個(gè)鏈堆棧S 記錄兩個(gè)合并標(biāo)簽，因此鏈堆棧寬度為標(biāo)簽寬度的兩倍，深度為一行圖像中存在的最大標(biāo)簽合并次數(shù)NM=（W-1）/ 2，鏈堆棧大小為2×WL×NM. 由于不考慮標(biāo)簽回收，OSP 算法的標(biāo)簽數(shù)量比其他算法大的多，對(duì)應(yīng)的合并表和數(shù)據(jù)表內(nèi)存占用也就很大，它的內(nèi)存位數(shù)量如表3所示.

JSP 算法采用標(biāo)簽移位寄存器實(shí)現(xiàn)行緩沖區(qū)，通過條件選擇器直接替換所有舊標(biāo)簽，無需解析標(biāo)簽等價(jià)關(guān)系. 根據(jù)文獻(xiàn)［58］的報(bào)告，JSP 算法雖然采用了標(biāo)簽回收技術(shù)，但只是回收合并中的較大標(biāo)簽，標(biāo)簽回收策略并不完整，使得標(biāo)簽數(shù)量可能與OSP算法一樣大. 如表3所示，JSP 算法的標(biāo)簽重用FIFO 和OSP 算法的合并表一樣大，但OSP算法還需要一個(gè)鏈堆棧S記錄合并標(biāo)簽，所以內(nèi)存需求上OSP 算法更大一些. 對(duì)比表3 和圖10 可以發(fā)現(xiàn)，這兩種算法的內(nèi)存需求遠(yuǎn)遠(yuǎn)大于其他算法（800M 對(duì)比900K），OSP 算法內(nèi)存需求是所有算法框架中最大的，JSP算法次之.

IOSP 算法采用激進(jìn)的重標(biāo)記方法使標(biāo)簽數(shù)量減少到W/2，但這種重標(biāo)記技術(shù)額外需要一個(gè)深度為NL，寬度為WL的轉(zhuǎn)換表TT（Translation Table）管理上一行和當(dāng)前行標(biāo)簽之間的關(guān)系，此外，還需要兩個(gè)合并表和數(shù)據(jù)表分別記錄兩行標(biāo)簽和特征數(shù)據(jù). 如表3 和圖10 所示，IOSP 算法與OSP 算法相比顯著減少了內(nèi)存需求，但在圖10所示的算法中，IOSP算法內(nèi)存需求仍是最大的.

表3 OSP和JSP算法架構(gòu)對(duì)不同分辨率圖像的內(nèi)存需求比較

SLSP算法通過回收標(biāo)簽使標(biāo)簽數(shù)量NL依賴圖像寬度W，額外的5個(gè)時(shí)鐘周期延遲用于補(bǔ)償標(biāo)簽回收處理操作. 增強(qiáng)標(biāo)簽使用行號(hào)擴(kuò)展了標(biāo)簽寬度，變?yōu)閃AL=WL+log2H. 算法的標(biāo)簽回收策略采用標(biāo)簽重用FIFO 寄存器管理標(biāo)簽，需要增加一個(gè)兩位比特的活動(dòng)標(biāo)簽AT跟蹤連通域標(biāo)記是否完成，還需要一個(gè)一位比特的有效性標(biāo)記V 跟蹤標(biāo)簽是否為過期標(biāo)簽，過期標(biāo)簽儲(chǔ)存放在過期標(biāo)簽堆棧SLS 中. 算法中證明過期標(biāo)簽的最大數(shù)量為W/ 10［48］，即SLS 深度也為W/ 10. 與IOSP 算法相比，SLSP算法只需要一個(gè)合并表和數(shù)據(jù)表，由于標(biāo)簽寬度變寬，合并表內(nèi)存大小幾乎相同，但數(shù)據(jù)表內(nèi)存縮小一半，總內(nèi)存需求顯著減少了約28%.

DLSP 算法通過雙重查找解決了過期標(biāo)簽問題，無需過期標(biāo)簽堆棧SLS 和有效性標(biāo)記V，進(jìn)一步減少內(nèi)存需求，但這兩個(gè)輔助數(shù)據(jù)結(jié)構(gòu)內(nèi)存消耗都比較小，因此提升有限，內(nèi)存需求只減少約2%.

ZZSP 算法需要額外的儲(chǔ)存器結(jié)構(gòu)實(shí)現(xiàn)“Z”字形順序掃描，在掃描期間動(dòng)態(tài)解析標(biāo)簽等價(jià)關(guān)系，避免了鏈堆棧S 的需要. 算法中采用更大的活動(dòng)標(biāo)簽AT 記錄橫坐標(biāo)x（最大為圖像寬度W）和縱坐標(biāo)y的最低有效位（一位比特）. 與DLSP算法相比內(nèi)存量減少了約6%.

TRSP 算法采用了兩個(gè)行緩沖區(qū)，但行緩沖區(qū)不儲(chǔ)存臨時(shí)標(biāo)簽，寬度僅為一比特. 算法中還采用了4 個(gè)表，每個(gè)表的深度最大為NL，由Head，Next 和Tail 表組成的鏈表結(jié)構(gòu)替換合并表解析標(biāo)簽等價(jià)關(guān)系，表位寬為WL，Data 表位寬為WD. 算法采用的標(biāo)簽回收技術(shù)避免了標(biāo)簽重用FIFO和活動(dòng)標(biāo)簽AT的需要，有效減少內(nèi)存需求，與SLSP 算法相比減少了大約30%，與ZZSP 算法比減少了大約25%.

5.2 硬件架構(gòu)比較

表4 比較了OSP［42］，IOSP［45］，SLSP［48］，ZZSP［51］，TRSP［54］以及JSP［58］硬件架構(gòu)的實(shí)現(xiàn)結(jié)果，由于各種架構(gòu)實(shí)現(xiàn)FPGA 技術(shù)不同、處理圖像分辨率不同和提取特征參數(shù)不同，為了實(shí)現(xiàn)公平比較，比較結(jié)果只包括CCA硬件架構(gòu)，不考慮圖像采集和外部接口模塊. 為了分析不同架構(gòu)的性能差異，采用如公式（5）所示的線性函數(shù)對(duì)原始數(shù)據(jù)進(jìn)行歸一化處理：

表4 幾種CCA硬件架構(gòu)的比較

其中X為原始數(shù)據(jù)，Xmax和Xmin為原始數(shù)據(jù)中最大值和最小值.

由于LUT（邏輯查找表）和寄存器都是由FPGA 內(nèi)部邏輯查找表綜合生成，所以衡量FPGA 寄存器資源消耗可以將二者累加綜合考慮. 歸一化結(jié)果在LUT、寄存器和BRAM方面越小越好，最大工作時(shí)鐘頻率越大越好.

在處理256×256 分辨率圖像時(shí)，SLSP 架構(gòu)消耗了最多BRAM，歸一化結(jié)果為1.0，LUT 和寄存器消耗為0.09，最大工作時(shí)鐘頻率為0.7. ZZSP 架構(gòu)采用LUT 作為分布式RAM 實(shí)現(xiàn)小型數(shù)據(jù)結(jié)構(gòu)需要消耗更多LUT，但顯著減少了BRAM，此外，它的最大工作時(shí)鐘頻率也是最高的，各項(xiàng)性能（LUT，BRAM 和最大工作時(shí)鐘頻率）歸一化結(jié)果分別為1.0，0.0 和1.0.TRSP 架構(gòu)采用簡化邏輯的鏈表結(jié)構(gòu)構(gòu)建標(biāo)簽等價(jià)關(guān)系，只需要很少的寄存器和LUT 資源，但是最大工作時(shí)鐘頻率最低，它的各項(xiàng)性能歸一化結(jié)果為0.0，0.6和0.0. 在這三種算法架構(gòu)中，ZZSP 架構(gòu)不僅有最少的BRAM 和最高的最大工作時(shí)鐘頻率，且在寄存器資源消耗上也不多，綜合性能是最優(yōu)的.

在處理640×480 分辨率圖像時(shí)，OSP 架構(gòu)消耗較少硬件資源是因?yàn)樘幚韴D像中僅包含255 個(gè)標(biāo)簽，消耗LUT 和BRAM 的歸一化結(jié)果為0.006 和0.0. IOSP 架構(gòu)需要兩個(gè)合并表和數(shù)據(jù)表記錄標(biāo)簽等價(jià)信息和數(shù)據(jù)信息，使得LUT 和寄存器單元消耗較OSP 架構(gòu)翻了一倍，它的各項(xiàng)性能（LUT，BRAM 和最大工作時(shí)鐘頻率）歸一化結(jié)果為0.04，0.737和0.0.JSP 架構(gòu)為了在合并期間替換所有舊標(biāo)簽，采用標(biāo)簽移位寄存器和多路選擇器實(shí)現(xiàn)標(biāo)簽更新，多路選擇器通過邏輯運(yùn)算輸出標(biāo)簽，導(dǎo)致架構(gòu)消耗的LUT 資源遠(yuǎn)遠(yuǎn)大于其他架構(gòu)，并降低最大工作時(shí)鐘頻率，它的各項(xiàng)性能歸一化結(jié)果為1.0，0.026和0.353.TRSP架構(gòu)在四種架構(gòu)中消耗最少的寄存器資源并有最高的最大工作時(shí)鐘頻率，各項(xiàng)性能歸一化結(jié)果為0.0，1.0 和1.0. 雖然TRSP 架構(gòu)也消耗了最多的BRAM，但是綜合性能超過了其他三種架構(gòu).

綜合上述分析，ZZSP 架構(gòu)的綜合性能是所有架構(gòu)中最優(yōu)的.

5.3 最差情況吞吐量

架構(gòu)的吞吐量分為兩部分：一部分為每個(gè)時(shí)鐘周期處理一個(gè)像素的靜態(tài)部分，這使得算法的吞吐量直接受限于硬件架構(gòu)工作時(shí)鐘頻率；另一部分為根據(jù)圖像內(nèi)容解析等價(jià)關(guān)系的數(shù)據(jù)相關(guān)部分，這將會(huì)影響架構(gòu)處理單個(gè)像素的平均周期. 各架構(gòu)在最差情況下處理像素的平均周期最大，決定了處理時(shí)間的上限，因此比較最差情況下架構(gòu)的吞吐量有一定意義. 圖11 給出了CCA 算法對(duì)應(yīng)最差吞吐量圖案. 如圖11（a）所示的階梯圖案將會(huì)產(chǎn)生最大的鏈堆棧，OSP［42］，SLSP［48］和DLSP［50］架構(gòu)在行尾解鏈會(huì)額外增加W/5 個(gè)時(shí)鐘周期消耗，這些架構(gòu)處理一個(gè)像素需要6/5個(gè)時(shí)鐘周期.

IOSP［45］架構(gòu)中許多合并是由轉(zhuǎn)換表決定的，使得創(chuàng)建最大鏈堆棧的模式變得更加復(fù)雜，如圖11（b）所示的羽毛圖案中兩行像素增加W/ 8 個(gè)時(shí)鐘周期消耗，IOSP架構(gòu)處理一個(gè)像素需要17/16個(gè)時(shí)鐘周期.

圖11 造成最差吞吐量的圖案

如圖11（c）所示的棋盤圖案限制了游程的優(yōu)勢，是所有基于游程算法的最差情況.TRSP［54］架構(gòu)雖然是基于游程算法，但它和ZZSP［51］、JSP［58］架構(gòu)都不需要額外時(shí)鐘周期處理標(biāo)簽等價(jià)關(guān)系，因此它們處理一個(gè)像素只需要一個(gè)時(shí)鐘周期. 如表4 所示，TRSP、JSP 和ZZSP架構(gòu)的吞吐量和工作時(shí)鐘頻率相同.

5.4 綜合分析

優(yōu)秀的處理算法不僅要實(shí)現(xiàn)實(shí)時(shí)處理，即需要以每個(gè)時(shí)鐘周期一個(gè)像素的速度處理位流像素，還要合理使用硬件資源.

在基于像素的CCA 算法中，OSP［42］，IOSP［45］，SLSP［48］和DLSP［50］算法解鏈延遲取決于圖像連通域的幾何復(fù)雜度，這導(dǎo)致算法吞吐量不一致. 對(duì)于一般圖像，解鏈延遲通常小于1%［51］；但對(duì)于最差情況，單行延遲可達(dá)50%，整幅圖像延遲為20%，使得算法無法實(shí)現(xiàn)實(shí)時(shí)處理. ZZSP［51］算法采用“Z”字形掃描避免解鏈延遲，實(shí)現(xiàn)了實(shí)時(shí)處理. 雖然采用“Z”字形掃描和多次查找合并表使得該算法需要比光柵式掃描算法更多的邏輯資源，但是總體資源消耗仍然較少. 因此ZZSP 算法是最優(yōu)的基于像素的單次掃描CCA算法.

TRSP［54］算法通過鏈表結(jié)構(gòu)操縱指針管理標(biāo)簽合并實(shí)現(xiàn)實(shí)時(shí)處理且消耗硬件資源較少，是最優(yōu)的基于游程的單次掃描CCA 算法. 然而，TRSP 算法是四連通域檢測算法，在檢測精度上落后于八連通的ZZSP 算法. 但四連通擴(kuò)展為八連通并不困難，因此TRSP 算法仍然是較優(yōu)的CCA算法.

JSP［58］算法也可以實(shí)現(xiàn)實(shí)時(shí)處理，但是與上述算法不同，它采用標(biāo)簽移位寄存器結(jié)構(gòu)進(jìn)行數(shù)據(jù)存儲(chǔ)消耗了大量邏輯資源并導(dǎo)致時(shí)鐘頻率較低，此外，算法中回收標(biāo)簽不完整，導(dǎo)致內(nèi)存需求很大，這使得JSP 算法的性能與ZSSP和TRSP算法相比相差較大.

6 結(jié)論與展望

本文分析了近十年以來國內(nèi)外發(fā)展的CCL 算法和CCA 算法，介紹了主要CCA 算法的實(shí)現(xiàn)策略和架構(gòu)，還介紹了適合CCA 算法的等價(jià)解析策略，并比較了幾種主要算法的內(nèi)存需求、硬件架構(gòu)和延遲. 在內(nèi)存方面，OSP 和JSP 算法的內(nèi)存需求遠(yuǎn)大于其他算法，TRSP 算法的內(nèi)存需求最小；在硬件架構(gòu)方面，ZZSP 算法實(shí)現(xiàn)了最大的工作時(shí)鐘頻率；在延遲方面，ZZSP，TRSP 和JSP 算法的每秒吞吐量和時(shí)鐘頻率相同，都可以實(shí)現(xiàn)實(shí)時(shí)處理. 綜上所述，ZZSP 和TRSP 算法是最優(yōu)的單次算法CCA 算法. 本文分析結(jié)論為實(shí)現(xiàn)基于FPGA 高速位流圖像的連通域檢測提供了理論依據(jù)和數(shù)據(jù)參考.

關(guān)于CCA 問題的相關(guān)工作，未來可以從以下幾個(gè)方面進(jìn)一步展開：

（1）尋找更加有效的標(biāo)簽等價(jià)關(guān)系解析方法，當(dāng)前聯(lián)合查找算法中的展平操作中會(huì)增加延遲，如果能夠在掃描過程中直接解析等價(jià)關(guān)系而不用等到行尾，那么就可以減少延遲，提高算法處理速度.

（2）在多塊FPGA 上并行實(shí)現(xiàn)CCA 算法，進(jìn)一步提高基于硬件架構(gòu)的CCA算法處理速度.

（3）對(duì)現(xiàn)有CCA 算法和硬件架構(gòu)進(jìn)一步改進(jìn)和融合，使其能夠更有效地提取圖像中連通域特征.

（4）在當(dāng)前CCA 算法中，提取連通域的特征只包括面積、邊界框和質(zhì)心，設(shè)計(jì)新的CCA 算法提取圖像的周長、圓度和歐拉數(shù)等更多特征.

（5）設(shè)計(jì)適用于超大分辨率圖像的處理算法，可以考慮將超大圖像分割成多塊，對(duì)分割的多塊子圖像進(jìn)行標(biāo)記處理.

（6）可以結(jié)合現(xiàn)代工業(yè)對(duì)三維圖像檢測的需要，將CCA 算法的設(shè)計(jì)從二值圖像處理擴(kuò)展到三維圖像處理. 通過研究分析三維圖像像素之間的連通關(guān)系，實(shí)現(xiàn)對(duì)三維圖像的CCA算法的高效并行化實(shí)現(xiàn).