王 凱，黃 山，2，趙 瑜，張洪斌

（1.四川大學(xué) 電氣信息學(xué)院，四川 成都610065；2.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610065）

0 引 言

智能視頻監(jiān)控技術(shù)主要包含目標(biāo)檢測(cè)，目標(biāo)分類(lèi)，目標(biāo)跟蹤以及視頻內(nèi)容等過(guò)程。其中，目標(biāo)提取是從以像素為處理內(nèi)容的目標(biāo)檢測(cè)［1］轉(zhuǎn)向以區(qū)域?yàn)樽R(shí)別對(duì)象的目標(biāo)分類(lèi)的關(guān)鍵一環(huán)。連通域標(biāo)記算法［2］具體實(shí)現(xiàn)了由圖像像素點(diǎn)到待識(shí)別目標(biāo)區(qū)域的過(guò)渡，其處理性能直接影響到后續(xù)功能模塊和整個(gè)監(jiān)控系統(tǒng)的優(yōu)劣表現(xiàn)。

連通域標(biāo)記算法就是對(duì)運(yùn)動(dòng)檢測(cè)結(jié)果圖像進(jìn)行處理。通過(guò)將目標(biāo)圖像進(jìn)行二值化處理后，得到由白像素點(diǎn) （通常二值圖像用 “1”）和黑像素點(diǎn) （通常用 “0”來(lái)標(biāo)識(shí)）組成的點(diǎn)矩陣圖像。連通域標(biāo)記則將圖像中符合某種連通規(guī)則 （4領(lǐng)域連通或8領(lǐng)域連通）的像素標(biāo)識(shí)為同一目標(biāo)［3］。傳統(tǒng)連通域標(biāo)記算法以像素點(diǎn)為單位進(jìn)行處理，在處理過(guò)程中存在著明顯的缺陷：首先按像素點(diǎn)處理的方法處理速度不容樂(lè)觀，對(duì)噪聲敏感，若隨著圖像分辨率的增加，特別是現(xiàn)在高清圖像日益普及的情況下，傳統(tǒng)方法更顯劣勢(shì)；其次在區(qū)域合并時(shí)，每次都要從頭開(kāi)始掃描已經(jīng)掃描過(guò)的所有點(diǎn)，當(dāng)這種情況發(fā)生在整幅圖像的最后幾行時(shí)，處理量很大，這將嚴(yán)重影響到整個(gè)圖像的處理速度。

本文針對(duì)傳統(tǒng)連通域標(biāo)記算法中存在的主要缺陷，采用了圖像分塊技術(shù)，并通過(guò)預(yù)先記錄每個(gè)標(biāo)簽區(qū)域的開(kāi)始行以避免區(qū)域合并時(shí)全局重復(fù)掃描的方法，提出了一種面向圖像目標(biāo)提取的改進(jìn)連通域標(biāo)記算法。具體實(shí)驗(yàn)表明，該方法在提升處理速度以及抗噪性等方面都有良好的效果。

1 算法描述

1.1 術(shù)語(yǔ)定義

（1）鄰域：在數(shù)字圖像中與像素點(diǎn) （x，y）對(duì)應(yīng)的點(diǎn)集合 ｛I（x＋p，y＋q）； （p，q）是整數(shù)｝是此像素點(diǎn) （x，y）的鄰域。在數(shù)字圖像處理中常采用的鄰域是4鄰域和8鄰域，分別表示為

（2）連通：在像素點(diǎn)集合中，f（x，y）＝f（x＋i，y＋j），如果f（x，y）與f（x＋i，y＋j）之間又是4鄰域或8鄰域的關(guān)系，則點(diǎn)f（x，y）與f（x＋i，y＋j）之間是4連通或8連通的關(guān)系。連通性如圖1所示。

圖1 連通性

（3）連通域：二值圖像中的連通域就是互相連在一起的1－像素或0－像素區(qū)域。在前景圖像中，我們感興趣的運(yùn)動(dòng)目標(biāo)區(qū)域中互相連通的0－像素同樣構(gòu)成了連通成分，即連通域。

1.2 傳統(tǒng)連通域標(biāo)記算法

傳統(tǒng)連通域標(biāo)記算法分為4鄰域連通和8鄰域連通方法，文獻(xiàn) ［3］介紹了8鄰域連通的貼標(biāo)簽方法，算法流程如圖2（a）所示，具體處理過(guò)程如下：

（1）對(duì)整幅圖像進(jìn)行從上到下，從左到右逐個(gè)像素點(diǎn)進(jìn)行掃描。

（2）采用從1開(kāi)始的連續(xù)自然數(shù)標(biāo)記各個(gè)物體連通域中的點(diǎn)。

（3）若當(dāng)前掃描點(diǎn)的左上點(diǎn)為前景目標(biāo)點(diǎn)，則當(dāng)前點(diǎn)跟左上點(diǎn)在一個(gè)連通域內(nèi)的情況下，將當(dāng)前點(diǎn)的值標(biāo)記為和左上點(diǎn)相同的值，同時(shí)將對(duì)應(yīng)區(qū)域的像素?cái)?shù)目計(jì)數(shù)單元加一。

（4）如果左上點(diǎn)不為前景目標(biāo)點(diǎn)，那么考察當(dāng)前點(diǎn)的正上點(diǎn)為前景目標(biāo)點(diǎn)。如果正上點(diǎn)為前景目標(biāo)點(diǎn)，則當(dāng)前點(diǎn)和正上點(diǎn)在同一個(gè)連通域內(nèi)，將當(dāng)前點(diǎn)的值標(biāo)記為和正上點(diǎn)相同的值，同時(shí)將對(duì)應(yīng)的所屬區(qū)域的像素?cái)?shù)目計(jì)數(shù)單元加一。

（5）若當(dāng)前點(diǎn)的左上點(diǎn)、正上點(diǎn)都不為前景目標(biāo)點(diǎn)時(shí)，則用上面兩個(gè)步驟判斷當(dāng)前點(diǎn)的右上點(diǎn)和右前點(diǎn)是否為前景目標(biāo)點(diǎn)，如果是前景目標(biāo)點(diǎn)，則當(dāng)前點(diǎn)和他們屬于同一個(gè)連通域，那么將他們的數(shù)值標(biāo)記為同一個(gè)數(shù)值。

（6）若當(dāng)前像素點(diǎn)的右上、正上、左上點(diǎn)以及左前點(diǎn)都不為前景目標(biāo)點(diǎn)的情況下，則將當(dāng)前已分配的連通域標(biāo)記值加一，以此標(biāo)記作為下一個(gè)前景目標(biāo)點(diǎn)所屬的新的物體連通域的標(biāo)記，同時(shí)將對(duì)應(yīng)的區(qū)域像素?cái)?shù)目計(jì)數(shù)單元置一。

（7）在標(biāo)記的過(guò)程中需要調(diào)整處理操作：如果當(dāng)前點(diǎn)是一個(gè)前景目標(biāo)點(diǎn)，同時(shí)當(dāng)前點(diǎn)的右上點(diǎn)和左前點(diǎn)又為不同標(biāo)記，正上點(diǎn)不為前景目標(biāo)點(diǎn)，則將當(dāng)前點(diǎn)標(biāo)記為同右上點(diǎn)相同的值，此時(shí)，從頭到尾掃描圖像，把所有的同左前點(diǎn)標(biāo)記相同的像素點(diǎn)都修改為與右上點(diǎn)相同的標(biāo)記值，即進(jìn)行兩個(gè)區(qū)域的合并。期間有多少個(gè)像素點(diǎn)轉(zhuǎn)換，那么所統(tǒng)計(jì)在右上點(diǎn)所屬區(qū)域的像素?cái)?shù)目計(jì)數(shù)單元就加多少；最后把統(tǒng)計(jì)左前點(diǎn)所屬區(qū)域的像素?cái)?shù)目計(jì)數(shù)單元置0。同理，對(duì)于當(dāng)前點(diǎn)是一個(gè)前景目標(biāo)點(diǎn)而正上點(diǎn)不為前景目標(biāo)點(diǎn)，同時(shí)當(dāng)前點(diǎn)的右上點(diǎn)和左上點(diǎn)又為不同標(biāo)記的情形也要做相同的標(biāo)記區(qū)域合并處理。

1.4 統(tǒng)計(jì)學(xué)分析 研究數(shù)據(jù)采用SPSS 23.0統(tǒng)計(jì)軟件進(jìn)行統(tǒng)計(jì)學(xué)分析，計(jì)量資料采用描述，組間比較實(shí)施獨(dú)立樣本t檢驗(yàn)；計(jì)數(shù)資料采用率(%)描述，χ2檢驗(yàn)；Kaplan-Meier法建立生存模型，Log-rank檢驗(yàn)分析生存率差異。此外，采用多因素Cox回歸分析EOC預(yù)后的獨(dú)立危險(xiǎn)因素，以P<0.05為差異有統(tǒng)計(jì)學(xué)意義。

在實(shí)際的運(yùn)算處理過(guò)程中發(fā)現(xiàn)傳統(tǒng)連通域標(biāo)記算法存在如下不足：

（1）對(duì)于物體區(qū)域標(biāo)記過(guò)程中的區(qū)域合并處理，每次都要從頭開(kāi)始掃描已經(jīng)掃描過(guò)的所有點(diǎn)，特別是這種情況發(fā)生在整幅圖像的最后幾行時(shí)，處理量較大，并且如果這種情況多次出現(xiàn)，將影響整個(gè)處理的速度，違背了實(shí)際運(yùn)算處理的快速性要求。

（2）標(biāo)記運(yùn)動(dòng)物體是以像素為單位，需要從上到下、從左到右進(jìn)行多次的掃描，圖像的大小直接決定了搜索的快慢。本文使用的圖像大小為320×240，即有76800個(gè)像素點(diǎn)，如果圖像中有少數(shù)的運(yùn)動(dòng)目標(biāo)，那么搜索的快慢不影響實(shí)時(shí)的處理，但是如果圖像中前景目標(biāo)的個(gè)數(shù)較多的話(huà)，搜索的快慢將直接對(duì)實(shí)時(shí)處理產(chǎn)生影響。

對(duì)于以上傳統(tǒng)連通域標(biāo)記算法中存在的主要缺陷，可以看出直接用這種方法在提取目標(biāo)連通域的處理過(guò)程中，無(wú)論是在處理的快速性和實(shí)時(shí)性都并不是十分理想，而且抗噪性能差，不能保證實(shí)時(shí)視頻的處理，違背了初衷，因此需要進(jìn)行改進(jìn)。

1.3 連通域標(biāo)記算法的改進(jìn)

針對(duì)傳統(tǒng)連通域標(biāo)記算法在處理過(guò)程中存在著的低效率和抗噪性能差等缺陷，本文在傳統(tǒng)連通域標(biāo)記算法的基礎(chǔ)上對(duì)其進(jìn)行了兩個(gè)方面的改進(jìn)，改進(jìn)前后連通域標(biāo)記算法的流程如圖2所示。

1.3.1 連通域的目標(biāo)提取優(yōu)化

針對(duì)傳統(tǒng)連通域的目標(biāo)提取算法按像素點(diǎn)處理而導(dǎo)致的處理效率低和對(duì)噪聲敏感等問(wèn)題，本文提出圖像分塊改進(jìn)的方法?？紤]到在目標(biāo)提取系統(tǒng)中，即使圖像中出現(xiàn)多個(gè)目標(biāo)物體，物體之間水平和豎直距離也是大于8個(gè)像素的。因此，320×240像素大小的圖將被等分成40×30（1200）個(gè)8×8像素大小的圖像塊。分別對(duì)圖像塊中的前景像素點(diǎn)進(jìn)行統(tǒng)計(jì)，如果圖像塊中的前景像素點(diǎn)個(gè)數(shù)占整個(gè)圖像塊的比例大于某個(gè)數(shù)值，我們就認(rèn)為這個(gè)圖像塊為前景目標(biāo)。確定了前景圖像塊后，我們?cè)谶M(jìn)行連通域的目標(biāo)提取時(shí)，我們就直接對(duì)圖像塊進(jìn)行連通域標(biāo)記為目標(biāo)區(qū)域。這種方法極大的減少了被貼標(biāo)簽掃描的數(shù)據(jù)量，有效減少了處理時(shí)間；同時(shí)，對(duì)圖像塊的分類(lèi)可以濾除雜散的噪聲點(diǎn)干擾，有效的提高了抗噪性。

假設(shè)，一幅圖像I（x，y）的大小為 M×N，我們可以將這幅圖像均等的分為P×Q個(gè)大小為m×n的圖像塊，基本單元為U（X，Y）。其中P＝M／m，Q＝N／n。根據(jù)基本單元U（X，Y）內(nèi)目標(biāo)像素點(diǎn)和基本單元內(nèi)總像素點(diǎn)的比例，可以確定圖像塊是否為前景目標(biāo)。表達(dá)式如下

式中：R（X，Y）——第 （X，Y）個(gè)圖像塊內(nèi)目標(biāo)像素點(diǎn)和總像素點(diǎn)的比例，如果這個(gè)值大于某個(gè)閾值θ，我們就將U（X，Y）的其標(biāo)記為前景目標(biāo)圖像塊，否則為非前景目標(biāo)單元，表達(dá)式如下

1.3.2 物體區(qū)域標(biāo)記的優(yōu)化

在傳統(tǒng)連通域的目標(biāo)提取算法中，針對(duì)物體區(qū)域標(biāo)記過(guò)程中的區(qū)域合并處理，每次都要從頭開(kāi)始掃描已經(jīng)掃描過(guò)的所有點(diǎn)，當(dāng)這種情況發(fā)生在整幅圖像的最后幾行時(shí)，會(huì)導(dǎo)致處理量劇增，并且如果這種情況多次出現(xiàn)，將嚴(yán)重影響整個(gè)處理速度。為此，本文使用一個(gè)與物體區(qū)域點(diǎn)數(shù)計(jì)數(shù)單元數(shù)組對(duì)應(yīng)的數(shù)組來(lái)存儲(chǔ)每個(gè)區(qū)域的開(kāi)始行數(shù)值，當(dāng)某個(gè)區(qū)域被其他區(qū)域合并時(shí)，從其對(duì)應(yīng)的起始行開(kāi)始處理，從而極大的縮小了合并標(biāo)簽的掃描范圍，提升了處理效率。

2 實(shí)驗(yàn)結(jié)果與分析

為了定量的驗(yàn)證本文采用的改進(jìn)連通域標(biāo)記算法在實(shí)際應(yīng)用中具有高效性，本實(shí)驗(yàn)分別通過(guò)在室內(nèi)和室外兩種不同的場(chǎng)景對(duì)傳統(tǒng)連通域標(biāo)記算法和改進(jìn)連通域標(biāo)記算法的處理時(shí)間進(jìn)行了統(tǒng)計(jì)對(duì)比。本實(shí)驗(yàn)中使用的計(jì)算機(jī)硬件配置為IBM PC兼容機(jī) （Intel Pentium （R）E5300 2.6GHz CPU，Kingston DDR 400 1G 內(nèi)存），軟件環(huán)境為 WindowsXP操作系統(tǒng)，VC6.0＋＋軟件編程環(huán)境。

首先，在室內(nèi)監(jiān)控應(yīng)用環(huán)境中進(jìn)行實(shí)驗(yàn)。由于該應(yīng)用的最終目的是為了識(shí)別行人人臉，因此圖像中的行人目標(biāo)較大。本實(shí)驗(yàn)采用改進(jìn)后的連通域標(biāo)記算法提取出的行人目標(biāo)如圖3所示。

圖3 室內(nèi)場(chǎng)景目標(biāo)連通域獲取

由圖3可以看出，小于8×8的噪聲和微小的擾動(dòng)已經(jīng)被屏蔽掉了，只剩下了主要行人目標(biāo)和背景中的少量稍大的干擾目標(biāo)殘留。我們只需要加上一個(gè)面積閾值濾掉，就可以將這些小面積干擾目標(biāo)排除掉，最終結(jié)果如圖4所示。

圖4 面積過(guò)濾后的目標(biāo)連通域

其次，在室外監(jiān)控應(yīng)用環(huán)境中進(jìn)行了同樣的實(shí)驗(yàn)，該應(yīng)用的最終目的是為了檢測(cè)行人的異常行為，因此行人目標(biāo)較小，同時(shí)伴隨著較多的噪聲。本實(shí)驗(yàn)在室外場(chǎng)景中目標(biāo)連通域提取的效果如圖5所示。同樣可以看出，改進(jìn)后的連通域標(biāo)記算法排除了噪聲干擾，提取出了主要行人目標(biāo)。

根據(jù)實(shí)際測(cè)試圖4所示在5分鐘室內(nèi)監(jiān)控場(chǎng)景視頻和圖5所示在8分鐘室外監(jiān)控場(chǎng)景視頻中目標(biāo)連通域獲取效果，通過(guò)對(duì)有實(shí)際目標(biāo)檢出的視頻幀的連通域標(biāo)記處理時(shí)間進(jìn)行了統(tǒng)計(jì)對(duì)比，得到了表1在兩種場(chǎng)景中不同算法的最大、最小以及平均處理時(shí)間統(tǒng)計(jì)數(shù)據(jù)。

圖5 室外場(chǎng)景目標(biāo)連通域獲取

表1 連通域標(biāo)記算法的目標(biāo)區(qū)域提取時(shí)間對(duì)比

由統(tǒng)計(jì)結(jié)果可以得出，改進(jìn)后的算法大大縮短了圖像處理的時(shí)間，平均處理速度約為改進(jìn)前的212.36倍。

3 結(jié)束語(yǔ)

本文在傳統(tǒng)連通域標(biāo)記算法的基礎(chǔ)上，采用了圖像分塊改進(jìn)方法，極大地減少了待處理數(shù)據(jù)量，并且提高了抗噪性；同時(shí)，通過(guò)建立與區(qū)域標(biāo)簽對(duì)應(yīng)的標(biāo)簽起始行來(lái)統(tǒng)計(jì)數(shù)據(jù)，有效地優(yōu)化了圖像處理的速率。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的連通域標(biāo)記算法能夠高效地完成在不同場(chǎng)景下的圖像目標(biāo)提取任務(wù)，為后續(xù)的目標(biāo)識(shí)別等功能模塊的處理以及整個(gè)視覺(jué)監(jiān)控系統(tǒng)的準(zhǔn)確性、實(shí)時(shí)性奠定了良好的基礎(chǔ)。

［1］LIAN Xiaofeng，ZHANG Tao，LIU Zaiwen，et al.An improved method for moving human detection ［J］.Computer Simulation，2011，28 （2）：308－311 （in Chinese）.［連曉峰，張弢，劉載文，等.一種改進(jìn)的運(yùn)動(dòng)人體目標(biāo)檢測(cè)方法研究［J］.計(jì)算機(jī)仿真，2011，28 （2）：308－311.］

［2］ZUO Min，ZENG Guangping，TU Xuyan，et al.A connected domain labeling algorithm based on equivalence pair in binary image ［J］.Computer Simulation，2011，28 （1）：14－17 （in Chinese）.［左敏，曾廣平，涂序彥，等.基于等價(jià)對(duì)的圖像連通域標(biāo)記算法 ［J］.計(jì)算機(jī)仿真，2011，28 （1）：14－17.］

［3］XIE Fengying，ZHAO Danpei.Digital image proce－ssing［M］.Beijing：Publishing House of Electronics Industry，2008（in Chinese）.［謝鳳英，趙丹培.Visual C＋＋數(shù)字圖像處理［M］.北京：電子工程出版社，2008.］

［4］HE Lifeng，CHAO Yuyan，WU Kesheng.Fast connected component labeling ［J］.Pattern Recognition，2009，42 （1）：1977－1987.

［5］WU Kesheng，Ekow Otoo.Optimizing two－pass connectedcomponent labeling algorithms ［J］.Pattern Analysis and Applications，2009，12 （2）：117－135.

［6］XIE Yizhuang，TAN Xubin，CHEN He.A new algorithm for connected components labeling ［J］.Transactions of Beijing Institute of Technology，2012，32 （12）：1273－1277 （in Chinese）.［謝宜壯，譚許彬，陳禾.一種新的連通域標(biāo)記算法［J］.北京理工大學(xué)學(xué)報(bào)，2012，32 （12）：1273－1277.］

［7］QIN Fangtao，F(xiàn)ANG Bin.GPU accelerated parallel labeling algorithm of connected－domains in binary images ［J］.Journal of Computer Applications，2010，30 （10）：2274－2276 （in Chinese）.［覃方濤，房斌.GPU加速的二值圖連通域標(biāo)記并行算法.計(jì)算機(jī)應(yīng)用，2010，30 （10）：2274－2276.］

［8］AbuBaker A，Qahwaji R.One scan connected component labeling technique ［J］.IEEE International Conference on Signal Processing and Communications，2007，32 （20）：1283－1286.

［9］HE Lifeng，CHAO Yuyan，Suzuki K.Two efficient label equivalence based connected－component labeling algorithms for 3－D binary images ［J］.IEEE Transactions on Image Processing，2011，20 （8）：2122－2134.

［10］Flatt H，Blume S.A parallel hardware architecture for connected component labeling based on fast label merging ［J］.Architectures and Processors，2008，12 （26）：144－149.

［11］HE Lifeng，CHAO Yuyan，Suzuki K.A run－based two－scan labeling algorithm ［J］.IEEE Transactions on Image Processing，2008，17 （5）：749－756.