新的二維形狀描述方法與邊界平滑

(華中科技大學(xué) 控制科學(xué)與控制工程系， 湖北 武漢 430074）

摘 要：提出了一種新的二維形狀描述方法，該方法利用對目標(biāo)圖像邊界搜索的結(jié)果，將目標(biāo)邊界曲線像素的坐標(biāo)（x_i，y_i）分別用兩個(gè)數(shù)組x =X[i];y=Y[i] 描述。將一個(gè)二維圖像的問題轉(zhuǎn)換成兩個(gè)一維數(shù)組的分析問題，簡化了分析的復(fù)雜度。通過分別對兩個(gè)數(shù)組的處理可以對原目標(biāo)邊界進(jìn)行一系列處理，如邊界圓滑、銳化、拐點(diǎn)檢測等。介紹了該描述方法及其基本性質(zhì)，并利用該描述方法通過小波分解對工件目標(biāo)邊界的平滑進(jìn)行了具體分析。

關(guān)鍵詞： 形狀描述; 二進(jìn)制小波; 圖像處理; 邊界跟蹤

中圖法分類號： TP301.6文獻(xiàn)標(biāo)識(shí)碼： A

文章編號： 1001 3695(2006)08 0171 03



New Method of 2D Shape Representation and Edge Smoothing



ZHENG Xiao dong， ZHOU Ni na， HUANG Xin han

(Dept. of Control Science Engineering， Huazhong University of Science Technology ，Wuhan Hubei 430074， China)

Abstract: There is put forward a new methods of 2D(two dimensional) shape representation which stores the object borderline pixels coordinate value( x_i，y_i) into two arrays x=X[i];y=Y[i] by the sequence of object borderline tracking result. It changes a 2D image problem into two single dimension arrays’ problem. It lowers down the complexity of analysis. A series of processes about object borderline can be implemented such as smoothing， enhancement， corner detection etc.By operating on the two arrays. The representation of this method and its basic property are Introduced. And a concrete analysis has been done for the course of workpiece boundary smoothing based on this 2D shape representation by wavelet.

Key words: Shape Representation; Binary Wavelet; Image Processing; Boundary Tracking 

圖像經(jīng)過邊緣提取或閾值分割等處理后就得到了目標(biāo)封閉的輪廓線或輪廓線所包圍的區(qū)域形狀，因此描述物體二維圖像上的形狀特性并用于機(jī)器識(shí)別顯得非常重要。二維目標(biāo)形狀描述包括區(qū)域描述和邊界描述[1，2]。區(qū)域描述的一個(gè)經(jīng)典方法是以不變距的形式給出有關(guān)形狀的一個(gè)有限測度集[2]。邊界描述法又有鏈碼、傅里葉形狀描述子、玄分布等方法[1]，還有通過B 樣條函數(shù)進(jìn)行擬合[2，3]。對邊界進(jìn)行基元擬合[2，4]也是邊界描述的重要方法，對目標(biāo)邊界進(jìn)行一定分割，然后用特定的函數(shù)擬合，這些特定函數(shù)通常為圓弧和直線段。

為了能便于對目標(biāo)邊界進(jìn)行濾波等處理，本文提出了一種全新的二維形狀描述方法，其基本思路是先對圖像邊界跟蹤，根據(jù)跟蹤結(jié)果將邊界點(diǎn)依次存入兩個(gè)數(shù)組 X[i]，Y[i]。X[i]為邊界點(diǎn)的x軸坐標(biāo)，Y [i]為邊界點(diǎn)的y軸坐標(biāo)，i 為邊界點(diǎn)的排列序號。

X[i]，Y[i]可以被看作是以i為自變量的兩個(gè)函數(shù)：x= X[i]，y=Y [i]。 由于一元函數(shù)的分析處理方法多樣且簡單，因此通過對x=X[i]、y=Y [i]的處理可以方便地對原目標(biāo)邊界進(jìn)行處理。如對x=X[i]，y=Y[i]濾波可達(dá)到濾除目標(biāo)邊沿毛刺和噪聲并對目標(biāo)邊界進(jìn)行圓滑的目的，也可以加強(qiáng)邊沿來銳化拐點(diǎn)或采用其他的濾波方法對目標(biāo)邊沿進(jìn)行處理。 

由于整條曲線通過兩個(gè)函數(shù)表示，從理論上講對于 x= X[i]，y=Y [i]進(jìn)行函數(shù)擬合，只要參數(shù)足夠多就可以在滿足精度的同時(shí)不需要對曲線進(jìn)行分割。

本文重點(diǎn)介紹了該描述方法的性質(zhì)和利用該方法對圖像處理的一般過程。

1 基本思路

考慮在二維笛卡兒坐標(biāo)系中函數(shù)的表達(dá)形式 y=f(x)，當(dāng)橫坐標(biāo)x一旦確定后，則函數(shù)值也被確定。也就是說每一個(gè)x值對應(yīng)唯一的函數(shù)值。對給定點(diǎn)序列D={d_i(x_i，y_i)，i=1，…，n} 定義：

條件1 所有 d屬于D且依次連接構(gòu)成一條曲線段，該曲線段所有部分在x軸上的投影不重疊。

如果點(diǎn)序列滿足條件1那么就可以用y=f(x)函數(shù)來表達(dá)，也就可以用函數(shù)的方法來處理目標(biāo)邊界。 

二維目標(biāo)的外形輪廓是由曲線組成的，而在原始圖像的目標(biāo)外形圖中，這些曲線或線段都是由一系列的兩兩相互鄰接的像素構(gòu)成。目標(biāo)邊界曲線和函數(shù)曲線的最大區(qū)別就是函數(shù)曲線滿足條件1，而目標(biāo)曲線無法保證能夠滿足這一要求，并且在絕大多數(shù)場合都不滿足這一要求。為了能用函數(shù)描述目標(biāo)邊界，通常需要將原始的邊界圖像進(jìn)行分割，使得每一個(gè)局部能夠滿足這一要求。本文重點(diǎn)不是考慮用何種基元的組合來描述曲線，而是解決曲線本身無法用函數(shù)描述的問題。該方法將對目標(biāo)邊界搜索的過程理解為一個(gè)點(diǎn)沿著目標(biāo)的邊界移動(dòng)的過程。從 t=1開始到t=n時(shí)結(jié)束，以t為自變量分別記錄途經(jīng)點(diǎn)的x和y坐標(biāo)值，對于每一個(gè)t=i，有唯一的點(diǎn)與之對應(yīng)，即x=X(t)，y=Y(t) 均滿足條件1，并且包含了目標(biāo)邊界曲線的所有信息。在大大降低了存儲(chǔ)容量的同時(shí)方便了對目標(biāo)邊界的分析處理。

如果分析時(shí)進(jìn)行延拓，可以將兩個(gè)函數(shù)均看作是周期為 n （邊界的像素點(diǎn)個(gè)數(shù)）的函數(shù)。

2 X[n]，Y[n]的性質(zhì) 

根據(jù)搜索過程可知，當(dāng)搜索的下一個(gè)點(diǎn)為4鄰域點(diǎn)時(shí)移動(dòng)的距離為1，如果為非4鄰域的8鄰域點(diǎn)時(shí)移動(dòng)距離為 2 。但無論在 x還是y 方向每次要么不移動(dòng)，要么增加或減小1。

設(shè)目標(biāo)邊界曲線中某一段 （P_ι，P_m），ι、m為搜索的序號，在任意一點(diǎn)的斜率為k，如果能滿足｜k｜≤1。說明該邊界主要沿x軸方向延伸，那么在搜索時(shí)沿x軸方向變化的速度總是快于y軸方向。因此搜索時(shí)x軸方向會(huì)持續(xù)不斷地變化而沒有任何停頓，y軸方向則可能有停頓，所以x=X[t]表現(xiàn)為一條斜率為1或-1的直線，y=Y[t]則為目標(biāo)邊界圖像平移的結(jié)果。反之當(dāng)｜k｜≥1時(shí)y=Y[t]表現(xiàn)為一條斜率為1或 1的直線， x=X[n]為目標(biāo)邊界圖像旋轉(zhuǎn)90°后平移的結(jié)果。

圖1(a)為目標(biāo)邊界圖像，圖1(b)為 x=X(t)，y=Y(t) 。圖1(a)的虛線將二維曲線分割成 A、B兩段，A段斜率｜k｜ ≥1；在圖1(b)中可以看到 A段Y(t)為直線，X(t) 為圖1(a)中 A 段旋轉(zhuǎn)90°后平移的結(jié)果， B段｜k｜ ≤1，圖1(b)中 B段X(t)為直線，Y(t) 為圖1(a)中 B段平移的結(jié)果。因此描述方法可理解為當(dāng)邊界主要沿x軸方向延伸時(shí)，邊界用函數(shù)y=f(x)表示，x為自變量；當(dāng)邊界主要沿y軸方向延伸時(shí)，用函數(shù)x=f(y)表示，y 為自變量。

另一個(gè)重要特性是 x=X[t]，y=Y[t]的斜率均滿足 ｜k｜≤ 1。由于第i+1個(gè)點(diǎn)是第i個(gè)點(diǎn)的8鄰域點(diǎn)，所以 X[i+1]X[i]的值為 1，1或0，因此｜X[i+j] X[i]｜≤j， 即｜d x /d t ｜≤1。同理｜d y /d t ≤1。

3 處理步驟

利用該二維目標(biāo)形狀描述的圖像處理全過程可以由四部分組成：

(1)提取圖像邊界曲線像素點(diǎn)；

(2)創(chuàng)建數(shù)組 X[n]，Y[n] 并跟蹤曲線記錄邊界點(diǎn)坐標(biāo)值；

(3)對數(shù)組 X[n]，Y[n] 分析處理，例如濾波去噪等；

(4) X[n]，Y[n] 函數(shù)歸一化。

下面以邊界去噪為例，詳細(xì)介紹該描述方法的應(yīng)用。

3.1 提取邊界

二維目標(biāo)形狀描述的一個(gè)基礎(chǔ)條件就是精確提取目標(biāo)形狀邊界曲線，用于跟蹤的曲線像素集必須滿足的條件是：設(shè)邊界檢測的結(jié)果中邊界像素集合為 S，那么用于跟蹤的曲線是S的子集T，該子集是S 的連通分量，子集中除了兩個(gè)端點(diǎn)以外的每一個(gè)點(diǎn)都有且只有兩個(gè)鄰接點(diǎn)（端點(diǎn)僅有一個(gè)鄰接點(diǎn)）。一般邊界提取可采用對二值化圖提取邊界和邊緣加強(qiáng)再二值化，一般而言結(jié)果均不能直接滿足跟蹤條件，因此必須對邊界圖像進(jìn)行處理。先將二值化的邊界圖像細(xì)化，采用納克卡赫和欣格爾細(xì)化算法[1，5]可以完全滿足要求。為避免由于噪聲而引起的邊界間斷，必須加上諸如形態(tài)學(xué)等去噪方法和連接策略。



3.2 跟蹤曲線

創(chuàng)建數(shù)組 X[n]，Y[n]，對目標(biāo)曲線像素集進(jìn)行跟蹤，依次序?qū)⒏櫟狞c(diǎn)的x值存入X[i]，y值存入Y[i]，i為跟蹤像素的序號。如果圖像中目標(biāo)圖像不止一個(gè)則建立多個(gè)數(shù)組 X m[i]，Y m[i]分別存儲(chǔ)每一個(gè)目標(biāo)邊界。當(dāng)完成跟蹤過程之后，目標(biāo)邊界的信息就被全部記錄在數(shù)組X[n]，Y[n]中 。

3.3 濾波去噪

X[n]，Y[n]分別是目標(biāo)邊界像素在X軸和Y軸上的投影，當(dāng)沿目標(biāo)邊界搜索時(shí)，X(t)，Y(t)的值在x，y軸上移動(dòng)。如果目標(biāo)邊界不光滑那么X[n]，Y[n]就會(huì)頻繁地往復(fù)運(yùn)動(dòng)，反映在x=X(t)，y=Y(t)函數(shù)上的特點(diǎn)就是高頻分量較大，反之亦然。對X[n]，Y[n]進(jìn)行低通濾波就可達(dá)到對目標(biāo)邊界進(jìn)行去噪的效果。 因此要濾除目標(biāo)邊界的噪音可以通過抑制函數(shù) x=X(t)，y=Y(t)的高頻分量的方法達(dá)到。

小波分析是對數(shù)據(jù)進(jìn)行頻域和時(shí)域分析的強(qiáng)有力的工具，可以根據(jù)高、低頻信號的特點(diǎn)，自動(dòng)調(diào)整時(shí)頻窗，是一種自適應(yīng)的時(shí)頻局部化分析方法[6，7]。利用小波對x=X(t)，y=Y(t)高頻分量抑制的同時(shí)，根據(jù)目標(biāo)的時(shí)頻特性保留目標(biāo)邊界尖銳的拐點(diǎn)。 

小波分解后低頻部分為目標(biāo)邊界大致形狀的信息，高頻部分為一些毛刺或噪音。目標(biāo)邊界的跳變也存在于高頻分量之中，要完整地提取出目標(biāo)邊界的同時(shí)抑制噪音就必須區(qū)分目標(biāo)邊界的跳變和噪音的區(qū)別。現(xiàn)假設(shè)：目標(biāo)邊界的噪音相對跳變幅度較小。假設(shè)是合理的，因?yàn)槿绻容^大就可以被認(rèn)為是邊界的一部分。因此處理的過程就被分成三步：①進(jìn)行小波分解；②單純對高頻分量進(jìn)行回復(fù)，對回復(fù)結(jié)果進(jìn)行閾值分割，抑制或除去小于閾值的部分；③回復(fù)低頻分量，與處理的高頻分量一起還原圖像。小波分解算法如下：

為了增加計(jì)算的有效性，采用二進(jìn)制小波進(jìn)行分解。式(1)和式(2)中 a以2^j 為伸縮步長。

因此二進(jìn)制小波只對尺度因子 a離散化，平移因子b 仍保持連續(xù)。二進(jìn)制小波具有變焦的同時(shí)仍保持時(shí)域的連續(xù)性。二進(jìn)制小波函數(shù)為

3.4 X[n]，Y[n]歸一化

在對原目標(biāo)邊界進(jìn)行處理之后的 X′[n]和Y′[n] 并不一定滿足第3節(jié)所述的性質(zhì)，這是因?yàn)樵谔崛∵吔鐣r(shí)已經(jīng)要求了邊界的連續(xù)性，也就是每個(gè)的后續(xù)點(diǎn)一定是該點(diǎn)的8鄰域點(diǎn)。處理之后的邊界曲線可能出現(xiàn)三種情況：①后續(xù)點(diǎn)與當(dāng)前點(diǎn)不相連；②后續(xù)點(diǎn)與當(dāng)前點(diǎn)是同一個(gè)點(diǎn)；③多于兩個(gè)點(diǎn)與當(dāng)前點(diǎn)相鄰。由于用 X′[n]和Y′[n] 表示曲線是每一個(gè)點(diǎn)的順序已經(jīng)確定，因此對情況1只需將不連續(xù)的部分用直線連接即可。對于情況②則需要將重復(fù)的點(diǎn)刪除。情況③則需要對 X′[n]， Y′[n] 進(jìn)行細(xì)化。

4 實(shí)驗(yàn)結(jié)果

利用上述原理對提取到的目標(biāo)邊界進(jìn)行分析，結(jié)果如圖2所示。

圖2（a）為原始圖像。圖2（b）為跟蹤結(jié)果，從起始點(diǎn)開始 逆時(shí)針方向跟蹤。跟蹤結(jié)果能夠大致反映工件的形狀，但邊緣比較毛糙，噪音較大。圖2（c）為濾波之后的圖像邊緣。邊界的噪音得到了有效的抑制。圖2（d）為采用雙函數(shù)描述的原始邊界。圖2（e）為分別對 x=X(t)，y=Y(t) 進(jìn)行二進(jìn)制小波分解的結(jié)果。橫軸為時(shí)間，縱軸為頻率的對數(shù)，灰度值表示強(qiáng)度。

5 結(jié)論

與鏈碼和傅里葉形狀描述子一樣，它們都需要對邊界進(jìn)行跟蹤。鏈碼可看作是本文所述方法的差分形式， 與鏈碼相比較其描述方式更為直觀。傅里葉形狀描述子將每一個(gè)邊界點(diǎn)用復(fù)數(shù)描述，將搜索的序列進(jìn)行傅里葉變換，將變換后的表達(dá)式F(k)的傅里葉系數(shù)稱為傅里葉描述子。傅立葉形狀描述子的方法已經(jīng)將原始數(shù)據(jù)從時(shí)域變換到了頻域，可以清楚地反映邊界頻率狀況，但它無法在時(shí)域內(nèi)局部化，不便對原始邊界進(jìn)行其他處理。本文所提出的方法將二維的目標(biāo)邊界圖像轉(zhuǎn)換為兩個(gè)一維數(shù)組的形式，在方便了數(shù)據(jù)處理的同時(shí)大大降低了存儲(chǔ)空間。所述實(shí)例均使用VC實(shí)現(xiàn)，在工件識(shí)別時(shí)取得了良好的效果。 

參考文獻(xiàn)：

[1] 夏良正. 數(shù)字圖像處理[M]. 南京: 東南大學(xué)出版社，2002.

[2] 鄭南寧. 計(jì)算機(jī)視覺與模式識(shí)別[M]. 北京:國防工業(yè)出版社，1998.

[3] Rosenfeld R F. Application of B Spline Approximation to Geometric Problem of CAD[D]. Syracuse University，1973.

[4] J Roberge.A Data Reduction Algorithm for Planar Curves[J]. Compute Vision Graphics Image Processing， 1985，29(2):168-195.

[5] N J Naccache，R Shinghal. In Response to Comment on an Investigation into the Skeletonization Approach to Hilditch[J].Pattern Reco gnition ，1986，19(2):111-116.

[6] [美]崔景泰. 小波分析導(dǎo)論[M].程正興.西安:西安交通大學(xué)出版社，1996.

[7] 徐長發(fā)，李國寬.實(shí)用小波方法[M]. 武漢：華中科技大學(xué)出版社，2001. 

作者簡介：鄭曉東(1974 )，男，江蘇靖江人，博士研究生，主要研究方向?yàn)橹悄芸刂啤D像處理；黃心漢(1946 )，男，湖北咸寧人，所長，教授，博導(dǎo)，本科，主要研究方向?yàn)橹悄芸刂啤C(jī)器人、傳感技術(shù)、信息融合等。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。