基于小波變換的邊緣檢測技術(完整)

第一章圖像邊緣的定義引言在實際的圖像處理問題中，圖像的邊緣作為圖像的一種根本特征，被經(jīng)常用于到較高層次的特征描述，圖像識別。圖像分割，圖像增強以及圖像壓縮等的圖像處理和分析中，從而可以對圖像進行進一步的分析和理解。由于信號的奇異點或突變點往往表現(xiàn)為相鄰像素點處的灰度值發(fā)生了劇烈的變化，我們可以通過相鄰像素灰度分布的梯度來反映這種變化。根據(jù)這一特點，人們提出了多種邊緣檢測算子：Roberts算子Prewitt算子Laplace算子等。經(jīng)典的邊緣檢測方法是構造出像素灰度級階躍變化敏感的微分算子。這些算子毫無例外地對噪聲較為敏感。由于原始圖像往往含有噪聲、而邊緣和噪聲在空間域表現(xiàn)為灰度有大的起落，在頻域那么反映為同是主頻分量，這就給真正的邊緣檢測到來困難。于是開展了多尺度分析的邊緣檢測方法。小波分析與多尺度分析有著密切的聯(lián)系，而且在小波變換這一統(tǒng)一理論框架下，可以更深刻地研究多尺度分析的邊緣檢測方法，MallatS提出了一小波變換多尺度分析為根底的局部極大模方法進行邊緣檢測。小波變換有良好的時頻局部轉化及多尺度分析能力，因此比其他的邊緣檢測方法更實用和準確。小波邊緣檢測算子的根本思想是取小波函數(shù)作為平滑函數(shù)的一階導數(shù)或二階導數(shù)。利用信號的小波變換的模值在信號突變點處取局部極大值或過零點的性質來提取信號的邊緣點。常用的小波算子有Marr算子Canny算子和Mallat算子等?！?.1信號邊緣特征人類的視覺研究說明，信號知覺不是信號各局部簡單的相加，而是各局部有機組成的。人類的信號識別〔這里討論二維信號即圖像〕具有以下幾個特點：邊緣與紋理背景的比照鮮明時,圖像知覺比擬穩(wěn)定；圖像在空間上比擬接近的局部容易形成一個整體；在一個按一定順序組成的圖像中，如果有新的成份參加，那么這些新的成份容易被看作是原來圖像的繼續(xù)；在視覺的初級階段，視覺系統(tǒng)首先會把圖像邊緣與紋理背景別離出來，然后才能知覺到圖像的細節(jié)，識別出圖像的輪廓，也就是說，首先識別的是圖像的大輪廓；知覺的過程中并不只是被動地接受外界刺激，同時也主動地認識外界事物，復雜圖像的識別需要人的先驗知識作指導；圖像的空間位置、方向角度影響知覺的效果。從以上這幾點，可以總結出待識別的圖像邊緣點應具有以下特征即要素：具有較強的灰度突變，也就是與背景的比照度鮮明；邊緣點之間可以形成有意義的線形關系，即相鄰邊緣點之間存在一種有序性；具有方向特征；在圖像中的空間相對位置；邊緣的類型，即邊緣是脈沖型、階躍型、斜坡型、屋脊型中哪一種?！?.2圖像邊緣的定義邊緣檢測是圖像處理中的重要內容。而邊緣是圖像中最根本的特征，也是指周圍像素灰度有變化的那些像素的集合。主要表現(xiàn)為圖像局部特征的不連續(xù)性，也就是通常說的信號發(fā)生奇異變化的地方。奇異信號沿邊緣走向的灰度變化劇烈，通常分為階躍邊緣和屋頂邊緣兩種類型。階躍邊緣在階躍的兩邊的灰度值有明顯的變化；屋頂邊緣那么位于灰度增加與減少的交界處。我們可以利用灰度的導數(shù)來刻畫邊緣點的變化，分別求階躍邊緣和屋頂邊緣的一階，二階導數(shù)。如圖可見，對于邊緣點A，階躍邊緣的一階導數(shù)在A點到最大值，二階導數(shù)在A點過零點；屋頂邊緣的一階導數(shù)在A點過零點，二階導數(shù)在A點有最大值。第二章傳統(tǒng)的邊緣檢測算子§2.1傳統(tǒng)的邊緣檢測算子邊緣檢測的實質是采用某種算法來提取出圖像中對像與背景間的交界線。我們將邊緣定義為圖像中灰度發(fā)生急劇變化的區(qū)域邊界。而灰度變化的情況可以用圖像灰度分布的梯度來反映，所以我們可以用局部圖像微分技術來獲得邊緣檢測算子。以下比照擬經(jīng)典的邊緣檢測算子進行了理論分析，并做出了比擬和評價。我們記為圖像的梯度，中包含局部灰度的變化信息。記：為梯度的幅度，可以用做邊緣檢測算子。常用的邊緣檢測方法有：差分邊緣檢測，Roberts邊緣檢測算子，Sobel邊緣檢測算子，Prewitt邊緣檢測算子,Robinson邊緣檢測算子,Lapalce邊緣檢測算子等等?！?.2差分邊緣檢測方法利用像素灰度的一階導數(shù)算子在灰度迅速變化處得到高值來進行奇異點的檢測。它在某一點的值就代表該點的“邊緣強度〞，可以通過對這些值設置閾值來進一步得到邊緣圖像。但用差分邊緣檢測必須使差分的方向與邊緣方向垂直，這就需要對圖像的不同方向都進行差分運算，增加了實際運算的繁瑣性。一般為垂直邊緣、水平邊緣、對角線邊緣檢測：圖2-1差分算法檢測邊緣的方向模板§2.3Roberts邊緣檢測算子Roberts邊緣檢測算子根據(jù)任意一對互相垂直方向上的差分可以用來計算梯度的原理，采用對角線方向相鄰兩像素之差，即：他們的卷積算子為：有了，之后，很容易計算出Roberts的梯度幅值，適當?shù)娜￠T限TH，作如下判斷：，為階躍邊緣點。為邊緣圖像。Roberts算子采用對角線方向相鄰兩像素之差近似梯度幅值邊緣檢測。檢測水平和垂直邊緣的效果好于斜向邊緣，定位精度高，對噪聲敏感。圖2-2：用Roberts算子進行邊緣檢測的Lena圖與原圖像§2.4Sobel邊緣檢測算子對數(shù)字圖像的每一個像素，考察它上，下，左，右鄰點灰度的加權差，與之接近的鄰點的權大。據(jù)此，定義Sobel算子如下：卷積算子為：圖2-3：Sobel邊緣檢測算子方向模板適當?shù)娜￠T限TH，作如下判斷：為階躍邊緣點，為邊緣圖像。Sobel算子很容易在空間上實現(xiàn)，Sobel邊緣檢測器不但產(chǎn)生較好的邊緣檢測效果，而且受噪聲的影響也比擬小。當使用大的領域時，抗噪聲特性會更好，但這樣做會增加計算量，并得出的邊緣也比擬粗。Sobel算子利用像素點上下，左右鄰點的灰度加權算法，根據(jù)在邊緣點出到達極值這一現(xiàn)象進行邊緣的檢測。Sobel算子對噪聲具有平滑作用，提供較為精確的邊緣方向信息，但它同時會檢測出許多的偽邊緣，邊緣定位精度不高。當對精度要求不是很高時，是一種較為常用的方法。圖2-4：用Sobel算子進行邊緣檢測的Lena圖與原圖像§2.5Prewitt邊緣檢測算子Prewitt算子是一種邊緣樣板算子。這些算子樣板由理想的邊緣子圖像構成。依次用邊緣樣板去檢測圖像，與被檢測區(qū)域為相似的樣板給出最大值。用這個最大值作為算子的輸出值，這樣就可以將邊緣像素檢測出來。定義Prewitt邊緣算子模板如下：圖2-5：Prewitt邊緣檢測算子模板8個算子樣板對應的邊緣方向如以下圖所示：圖2-6：樣板方向適當取門限TH，作如下判斷：為階躍邊緣點。為邊緣圖像。圖2-7：用Prewitt算子進行邊緣檢測的Lena圖與原圖§2.6Robinson邊緣檢測算子Robinson邊緣檢測算子也是一種邊緣樣板算子，其算法和Prewitt邊緣檢測算子相似，只是8個邊緣樣板不同。如下所示：圖2-8：Robinson邊緣檢測算子模板§2.7Laplace邊緣檢測算子Laplace算子是二階微分算子，是一個標量，屬于各向同性的運算，對灰度突變敏感。在數(shù)字圖像中，可以用差分來近似微分運算，的Laplace算子為Laplace算子的二種估算模板：圖2-9：Laplace的兩種估算模板對階躍邊緣，二階導數(shù)在邊緣點出現(xiàn)零交叉，即邊緣點兩邊二階導函數(shù)取異號。Laplace算子就是據(jù)此對的每個像素取它關于方向和方向的二階差分之和，這是一個與邊緣方向無關的邊緣檢測算子。而對屋頂狀邊緣，在邊緣點的二階導數(shù)取極小值，這時對的每個像素取它關于方向和方向的二階差分之和的相反數(shù)。Laplace算子有兩個缺點：其一是邊緣的方向信息喪失，其二是Laplace算子為二階差分，雙倍加強了圖像中的噪聲影響：優(yōu)點是各向同性，即具有旋轉不變性。因為在微分學中有：一個只包含偶次階導數(shù)和取偶次冪的奇次階導數(shù)的線形組合算子，一定是各向同性的。Laplace算子實際二階微分算子，利用邊緣點處二階導函數(shù)出現(xiàn)零交叉原理檢測邊緣。不具有方向性，對灰度突變敏感，定位精度高，不但檢測出了絕大局部的邊緣，同時根本上沒有出現(xiàn)偽邊緣。但他的檢測也存在一些缺點，如喪失一些邊緣，有一些邊緣不夠連續(xù)，對噪聲敏感且不能獲得邊緣方向的功能信息。圖2-10：用Laplace算子進行邊緣檢測的Lena圖與原圖§2.8檢測結果與結論通過對以上介紹的幾種邊緣檢測算子的算法公式和檢測的結果可以看出，Roberts算子簡單直觀，但邊緣檢測圖里存在有偽邊緣；Sobel算子、Prewitt算子和Robinson的檢測結果圖能檢測出更多的邊緣，但也存在有偽邊緣且檢測出來的邊緣線比擬粗，并放大了噪聲；Lapalce算子和改良的Laplace算子利用二階差分運算來進行檢測，但不可以檢測出較多的邊緣，而且還在很大程度上消除了偽邊緣的存在，定位精度高。但受噪聲的影響比擬大。第三章小波變換在圖像邊緣檢測中的應用§3.1小波思想的引入雖然邊緣提取已有梯度算子、Laplace算子、Sobel算子等方法，但這些算法都沒有自動變焦的思想。而事實上，由于物理和光照等原因，每幅圖像中的邊緣通常產(chǎn)生在不同的尺度范圍內，形成不同類型的邊緣，這些信息是未知的。另外圖像中還存在有噪聲，因此，根據(jù)圖像特性自適應地正確檢測出圖像的邊緣是非常困難的?？梢钥隙?，用單一尺度的邊緣算子不可能檢測出所有的邊緣，同時，為防止在濾除噪聲是影響邊緣檢測的正確性，用多尺度的方法檢測邊緣越來越引起人們的重視。由于小波變換具有良好的時頻局部化特性及多尺度分析能力，在不同尺度上具有“變焦〞的功能，適合于檢測突變信號。是檢測突變信號強有力的工具，得到了廣泛的應用。§3.1.1小波變換在圖像邊緣檢測中的優(yōu)勢用小波變換對信號做多分辨率分析非常適合提取信號的局部特征。這是因為小波變換的尺度因子和平移因子構成了一個滑動的時間-頻率窗，小尺度下的變換系數(shù)對應信號的高頻分量，大尺度下的變換系數(shù)對應信號的低頻分量。于是信號被分解成各個頻率下的分量，這樣就可以檢測對應不同頻率的信號局部特征。而圖像中的突變信息和噪聲都屬于高頻信號，可以利用小波變換后的高頻分量進行去噪和得到邊緣圖像。由于各種原因，圖像常常受到隨機噪聲的干擾。經(jīng)典的邊緣檢測方法由于引入了各種形式的微分運算，從而必然引起對噪聲的極度敏感，在其上執(zhí)行邊緣檢測的結果常常是把噪聲當作邊緣點檢測出來，而真正的邊緣也由于受到噪聲干擾而沒有被檢測出來。因而對于有噪聲圖像來說，一種好的邊緣檢測方法應具有良好的各種噪聲抑制能力，同時又有完備的邊緣檢測保持特性。小波變換可以提供一種很好的去噪方法。當取小波函數(shù)為平滑函數(shù)的一階導數(shù)時，信號的小波變換的模的信號突變點出取局部極大值，邊緣與噪聲的區(qū)別在于，隨著尺度的增加，噪聲引起的小波變換的模的極大值迅速減小；而邊緣的濾波模值不隨尺度的變化，故小波變換可以在低信噪比的信號中檢測噪聲和邊緣。通過計算在尺度和尺度上每一個在位置上最接近，且具有相同符號的系數(shù)最大值，我們可以找出不同尺度下小波幅度的變化，消除那些系數(shù)極值孤獨隨尺度減小而小波系數(shù)Mf在平均值上增加的序列。這些極值對應圖像噪聲奇異點，從而就得到了圖像邊緣的真正奇異點。同時，邊緣點具有較強的方向性。即在邊緣點上，其濾波值表現(xiàn)為較強的模值，而在垂直邊緣方向上，濾波模值較小；而噪聲點在各個方向的濾波模值相似。因而，在對信號進行不同方向的濾波時，邊緣點濾波模值會有較強與較弱的差異，而噪聲點濾波模值不會產(chǎn)生過大的差異，因此可以通過構造任意方向的小波濾波器來檢測出奇異信號和噪聲點。對于很大一類圖像來說，急劇變化點所對應的邊緣在圖像平面內是一些規(guī)那么的曲線，沿著這些曲線，圖像在一個方向是奇異的，而和該方向相垂直的方向卻是平滑的。由于實際得到的值是一些離散點，為了檢測出邊緣，可以利用沿曲線方向梯度矢量的模變化平緩特點以及不同尺度下梯度矢量幅角的信息，將位置及幅角十分接近的模極大值點連接起來形成模極大值鏈，這些鏈構成了圖像的邊緣?！?.1.2小波變換定義及特點小波(wavelet)，即小區(qū)域的波，是一種特殊的長度有限、平均值為0的波形。它有兩個特點：一是“小〞，即在時域都具有緊支集或近似緊支集；尺度二是正負交替的“波動性〞，也即直流分量為零。我們可以用小波和構成傅立葉分析根底的正弦波做一個比擬，傅立葉分析所用的正弦波雜時間上沒有限制，從負無窮到正無窮，但小波傾向于不規(guī)那么也不對稱。傅立葉分析是將信號分解成一系列不同頻率的正弦波的疊加，同樣小波分析是將信號分解成一系列小波函數(shù)的疊加，而這些小波函數(shù)都是有一個母小波函數(shù)經(jīng)過平移與尺度伸縮得來的。我們知道，用不同規(guī)那么的小波函數(shù)來逼近鋒利變化的信號顯然要比光滑的正弦曲線要好，同樣，信號局部的特性用小波函數(shù)來逼近顯然要比光滑的正弦函數(shù)來逼近要好。小波變換的定義是把某一被稱為根本小波〔也叫母小波〕的函數(shù)做位移后，再在不同尺度下與待分析的信號做內積：，等效的頻域表示是：可以這樣理解上面表達式的意義：打個比喻我們用鏡頭觀察目標〔即待分析信號〕，代表鏡頭所起的作用〔例如濾波或卷積〕。相當于使鏡頭對于目標平行移動，的作用相當于鏡頭向目標推進或遠離。由此可見小波變換有以下特點：●有多分辨率，也叫多尺度的特點，可以有粗及細地逐步觀察信號。●可以看成用根本頻率特性為的帶通濾波器在不同尺度下對信號濾波。由于傅立葉變換的尺度特性可知這組濾波器具有品質因數(shù)恒定，即相對帶寬〔帶寬與中心頻率之比〕恒定的特點。注意，越大相當頻率越低?！襁m當?shù)倪x擇基小波，使在頻域上也比擬集中，就可以使在在時、頻域都具有表征信號局部特征的能力，因此有利于檢測信號的瞬態(tài)或奇異點。正是由于上述特性，有人把小波變換稱為分析信號的數(shù)學顯微鏡。如上所述，小波分析的一個重要優(yōu)點就是能夠分析信號的局部特征。利用小波分析可以檢測出許多其他分析方法忽略的信號特性，例如，信號的趨勢，信號的高階不連續(xù)點、自相似特性?？傊〔ㄗ儞Q作為一種數(shù)學理論和方法在科學技術和工程界引起了越來越多的關注和重視?！?.2連續(xù)小波變換§3.2.1連續(xù)小波的定義及其變換定義3.1設,其傅立葉變換為滿足允許條件〔AdmissibleCondition，完全重構條件或恒等分辨條件〕我們稱為一個根本小波或母小波〔MotherWavelet〕。將母函數(shù)按此方式經(jīng)平移和伸縮后得到函數(shù)族：稱其為一個小波序列或連續(xù)小波。其中a為伸縮因子，b為平移因子。我們首先來看看連續(xù)小波在相空間中的局部化格式。假定是雙窗函數(shù)，記由于正頻和負頻討論類似，只對正頻進行討論。注意到因此的正頻窗口中心為其時窗寬，頻窗寬。由此可以看出，b僅僅影響窗口在相平面時間軸上的位置，而a不僅僅影響窗口在頻率軸上的位置，也影響窗口的形狀。當越小時，時寬越小，而頻寬越大，且窗口中心向增大方向移動，這說明高頻時連續(xù)小波的時間分辨率較高，頻率分辨率較低；反之，當越大時，時寬越大，而頻寬越小，窗口中心向減小方向移動，這說明低頻時連續(xù)小波的時間分辨率較差，頻率分辨率較高。這一特性正好符合低頻信號變化緩慢而高頻信號變化迅速的特點，決定了小波變換在突變信號處理上的特殊地位及功能。在這個意義上，小波變換被譽為數(shù)學顯微鏡。對于任意函數(shù)的連續(xù)小波變換為其重構公式〔逆變換〕為有時為了方便起見，小波變換也常用如下定義其中式和式定義形式有所不同，主要在于

1〕伸縮系數(shù)不同。

2〕由卷積代替了相關。但事實上，它們之間是可以相互轉換的。由根本小波生成的小波在小波變換中對被分析的信號起著信號觀測窗的作用，所以還應滿足一般函數(shù)的約束條件故是一個連續(xù)函數(shù)。這意味著，為了滿足允許條件，在原點必須等于零，即小波只有在實軸上取值有正有負才能保證上式的積分為零，所以應具有振蕩性，也就是說是一個“波〞。同時，的定義域是具有緊支撐的，即在一個很小的區(qū)間之外，函數(shù)值為零，應是一個迅速衰減的“小〞波。小波因此得名。如果使下式成立，那么說為階消失距小波〔Vanishingmoments〕這時在＝0處是次可微的，即。而時就是容許條件，隨著的增加，小波的振蕩性就越來越強烈。連續(xù)小波變換具有以下重要性質：1、線形性：一個信號的小波變換等于各個分量的小波變換之和。2、平移不變性：假設的小波變換為，那么的小波變換為3、伸縮共變性：假設的小波變換為，那么的小波變換為4、自相似性：對應不同尺度參數(shù)和不同平移參數(shù)的連續(xù)小波變換之間是自相似的。5、冗余性：連續(xù)小波變換中存在信息表述的冗余度?！?.2.2離散小波變換在實際運用中，特別是在計算機實現(xiàn)上，往往需要把上面提到的連續(xù)小涉及其變換離散化。需要注意的是，這一離散化是針對連續(xù)的尺度參數(shù)和連續(xù)的平移參數(shù)的，而不是針對時間變量的。這一點和我們在離散傅里葉變換中熟悉的時間離散化是不同的。在連續(xù)小波中，考慮函數(shù)：這里，。為方便起見，在離散化中，總限制只取正值，即且，是容許的，這樣相容性條件就變成通常，把連續(xù)小波變換中尺度參數(shù)和平移參數(shù)的離散公式分別取作，這里，擴展步長是固定值。為了方便起見，總假定。所以對應的離散小波函數(shù)即可寫作而離散化的小波變換系數(shù)那么可表示為其重構公式為是一個與信號無關的常數(shù)。顯然，和決定了信號重構的精度，即網(wǎng)格點應盡可能地密〔和盡可能小〕，才能保證一定的重構精度。如果網(wǎng)格點越稀疏，使用的小波函數(shù)和離散小波系數(shù)就越少，信號重構的精確度也就會降低。§3.3常用小波函數(shù)介紹§3.3.1Haar小波Haar小波是在小波分析中最早用到的一個具有緊支撐的正交小波函數(shù)，同時也是最簡單的一個函數(shù)。Haar函數(shù)的定義為§3.3.2Daubechies小波系Daubechies函數(shù)是由世界著名的小波分析學者InridDaubechies構造的小波函數(shù)，提供了比Haar小波更有效的分析和綜合。除了dbl(即Haar小波)外，其它小波沒有明確的表達式。但轉換函數(shù)h的平方模是很明確的。假設其中，為二項式的系數(shù)，那么有其中：小波函數(shù)和尺度函數(shù)的有效支撐長度為，小波函數(shù)的消失矩階數(shù)為N,且具有正交性。常用的Daubechies小波函數(shù)有db4和db8兩種小波?！?.3.3Morlet小波Morlet函數(shù)定義為它的尺度函數(shù)不存在，且不具有正交性?！?.3.4MexicanHat小波MexicanHat函數(shù)為它是Gauss函數(shù)的二階導數(shù)，像墨西哥帽的截面，也稱為墨西哥函數(shù)。它在時間域和頻率域都有很好的局部化，并且滿足。由于它的尺度函數(shù)不存在，所以不具有正交性?！?.3.5Meyer小波Meyer小波的小波函數(shù)和尺度函數(shù)都是在頻率域中進行定義的，是具有緊支集的正交小波。其中，為構造Meyer小波的輔助函數(shù)，具有圖3-1：幾種常見的小波函數(shù)圖形第四章小波分析中的多尺度思想和邊緣檢測算子§4.1多尺度邊緣檢測思想圖像在不同尺度上的小波變換都提供了一定的邊緣信息。當小尺度時，圖像的邊緣細節(jié)信息較為豐富，邊緣定位精度較高，但易受到噪聲的干擾；大尺度時，圖像的邊緣穩(wěn)定，抗噪性好，但定位精度差。在實際應用中經(jīng)常存在著去除噪聲和準確定位之間的矛盾。多尺度邊緣檢測的根本思想就是沿梯度方向，分別用幾個不同尺度的邊緣檢測算子在相應點上檢測模極大值的變換情況，并通過對閾值的選取，再在不同尺度上進行綜合得到最終邊緣圖像，可以較好的解決噪音和定位精度之間的矛盾。在信號的時頻局部化分析中，雖然Fourier變換能較好地刻畫信號的頻率特性，但不能提供信號在時域上的信息，為此，Gabor首先提出加窗Fourier分析，但加窗不能敏感地反映信號的突變。小波理論與變換方法能彌補上述缺乏，主要表現(xiàn)在高頻處的時間分辨率高，低頻處的頻率分辨率高，即具有變焦特性，小波變換是一種非平穩(wěn)信號分析方法，它是通過一個根本小波函數(shù)的不同尺度的平移和伸縮構成一族小波函數(shù)系表示來逼近一信號。在小波多尺度分析中，引入了尺度函數(shù)，其伸縮與平移系數(shù)構成矢量空間的正交基，構成空間在分辨率上組成逼近空間。尺度函數(shù)具有低通濾波作用，并滿足雙尺度方程而與尺度函數(shù)相對應的小波函數(shù)的平移與伸縮構成矢量空間的正交補空間，小波函數(shù)具有高通濾波的作用，并滿足方程對任意一平方可積函數(shù)或信號，在尺度下的離散小波變換為平滑信號為小波變換與平滑分量滿足遞推公式其中；信號的多分辨率分解與重構可由上式完成，推廣至二維圖像空間，在圖像被分解成1個輪廓圖像和3個細節(jié)圖像。其中代表了圖像的低頻成分，低頻圖像還可以進一步分解成4個子帶，設分解層數(shù)為，那么總的子帶數(shù)為代表了圖像的垂直高頻成分〔水平邊界〕；代表了圖像的水平高頻成分〔垂直邊界〕；代表了圖像的對角線上的高頻成分。MallatS提出了離散小波變換的一種快速算法，即用低通濾波器H和高通濾波器G對原始數(shù)據(jù)進行逐步分層分解。其結果是產(chǎn)生一個低頻圖像，1個水平方向的細節(jié)圖像，1個垂直方向的細節(jié)圖像和1個對角方向的細節(jié)圖像。另外小波變換的多尺度分析(或多分辨率分析)是建立在函數(shù)概念上的，其創(chuàng)立者MallatS正是在研究數(shù)字圖像處理的問題時建立此理論的.隨著尺度由大到小變化,在各尺度上可以由粗及精地觀察圖像的目標.大尺度時,觀察到的是圖像的根本特征;在小尺度的空間里,那么可以看到目標的細節(jié).把二維圖像信號所占據(jù)的總頻帶定義為空間,用理想的低通濾波器和高通濾波器在行、列方向將它分別分解成低頻局部和高頻局部,每一方向的兩局部分別反映出該圖像信號在剖分方向上的概貌和細節(jié);對于經(jīng)第二級(a=21)分解后又被剖分成低頻、水平方向的高頻、垂直方向的高頻、以及對角線方向的高頻在這種空間剖分過程中,反映的是圖像信號在空間中沿方向概貌的低頻子空間，反映的是圖像信號在空間中沿方向細節(jié)的高頻子空間。從多分辨率分析可以看出,空間的每次剖分包含兩局部:一局部是圖像信號通過低通濾波后得到的低頻概貌;另一局部是通過帶通濾波(小波變換)得到的圖像高頻細節(jié);對于低頻概貌,重復以上過程,最終把圖像信號分解成多個等級的高頻細節(jié)與最后一次低通濾波后的低頻概貌之和。在剖分過程中,這些子空間具有以下的特性：單調性:2)逼近性:3)伸縮規(guī)那么性:4)平行不變性:滿足的上述性質稱為多尺度分析即:任意函數(shù)應用多尺度分析將其分解為細節(jié)局部或是某一方向上的細節(jié)局部和的根本特征局部然后將進一步分解,可得到任意尺度下的的根本特征局部以及細節(jié)局部之和。按照多尺度分析理論,描述函數(shù)分解過程如下圖圖4-1§4.2常用的幾種邊緣檢測算子近年來受到廣泛關注的邊緣檢測方法是Canny算子以及Mallat邊緣檢測算子。下面就簡單地作以介紹：Canny邊緣檢測算子Canny算子使用一階導數(shù)的極大值表示邊緣。其根本思想是先將圖像使用Gauss函數(shù)進行平滑，再由一階微分的極大值確定邊緣點。二階導數(shù)的零交叉點不僅對應著一階導數(shù)的極大值也對應著一階導數(shù)的極小值，也就是說，灰度變化劇烈的點與灰度變化緩慢的點都對應著二階導數(shù)零交叉點不僅對應著一階導數(shù)的極大值也對應著一階導數(shù)的極小值。在用高斯函數(shù)對圖像進行濾波得到，其中為相應的尺度因子。計算其梯度矢量的模和方向：圖像邊緣點即為在方向上使取得局部極大值的點。2Mallat小波邊緣檢測算子基于Canny邊緣檢測算子的主要思想，Mallat在1992年提出了小波變換極大值方法，并用于分析信號的奇異性和圖像的邊緣檢測，使其成為圖像檢測的重要工具。在邊緣提取中，一般取小波函數(shù)為其中為平滑函數(shù)，滿足，且。那么相應的二進小波變換為§4.2小波變換中尺度參數(shù)確實定及有效邊緣判定進行邊緣檢測時，濾波尺度參數(shù)的選取取決于當前象素點所處的區(qū)域是紋理區(qū)〔平滑區(qū)〕還是邊緣區(qū)，如果是紋理區(qū)〔平滑區(qū)〕,那么取大的濾波尺度,以抑制噪聲；如果是邊緣區(qū)，那么取小的濾波尺度，以準確定位邊緣?！?〕判斷紋理區(qū)〔平滑區(qū)〕和邊緣區(qū)計算兩個尺度下的小波變換結果和，對于坐標為的象素點，在兩個尺度下的小波變換模值分別為和,假設滿足,那么判斷為脈沖噪聲,其中是閾值，的取值可以去掉一局部噪聲和一些弱的細節(jié)，其取值受圖像中噪聲強度的影響，假設圖像噪聲強度較弱，那么較?。环衲敲摧^大。假設圖像中噪聲分布為，可取,這樣可以去掉較多噪聲點。將整幅圖像中所有這樣的脈沖去掉，然后將剩下的,中的局部極值點〔候選邊緣點〕進行線形連接，得到各候選邊緣點的鏈長，將鏈長大于某一閾值的候選邊緣點定義為大輪廓的邊緣點，然后計算其它候選邊緣點距離最近的大輪廓邊緣點的距離，得到邊緣點要素中的參量，候選邊緣點的方向參數(shù)可使用文獻中的方法來計算，這樣，可以得到整幅圖像中所有候選邊緣點的邊緣特征。〔2〕濾波尺度參數(shù)的選取范圍邊緣準確定位時，濾波尺度應盡可能小，取最小尺度。最大濾波尺度的選取應考慮抑噪能力和計算復雜度的折衷,選取能夠充分抑制噪聲的所有尺度中最小者為。由于使用的小波函數(shù)是平滑函數(shù)的一階導數(shù)，檢測到的邊緣點是小波變換的局部極值點，在滿足下式時那么判定為局部極值點，其中是局部極值點，是的鄰域，是閾值。理論上是不需要閾值的，但具體實現(xiàn)時，閾值可以抑制噪聲的影響，同時閾值在一定范圍內時〔不引起有效邊緣的喪失〕，決定著相應的最大濾波尺度，閾值越大，越??；閾值越小，越大?！?〕利用有效邊緣測度調整濾波尺度假設判定當前象素點處在紋理區(qū)〔平滑區(qū)〕，那么應取最大的濾波尺度；假設判定為邊緣區(qū)，那么應取最小濾波尺度；假設不能確定時，選取尺度為，這樣在一定程度上可以抑制噪聲，同時又不會使邊緣定位誤差過大，如果圖像噪聲的強度較大，這個尺度可以取，以進一步抑制噪聲。第五章利用小波變換進行邊緣檢測§5.1利用小波變換進行邊緣檢測的根本原理設上一適當光滑的二元函數(shù)，并滿足條件：引進記號：用函數(shù)對進行光滑得?，F(xiàn)在取二維小波根本函數(shù)如下：，作相應的小波變換如下：，由，的定義，易得：顯然，向量的模取極大值的點對應函數(shù)〔即按尺度光滑后的圖像〕的突變點。當很小時，用對光滑化的結果對的突變部位的位置形態(tài)影響不大，而當稍大時，那么此光滑過程會將的一些細小突變〔有噪聲引起的不是圖像的真正突變〕消去，剩下尺寸較大的突變〔圖像真正的突變〕。對參數(shù)取二進數(shù)列，那么二維函數(shù)序列為的二維二進小波變換。在尺度下，的梯度的模正比于：它與水平方向的夾角等于：顯然，取極大值的點對應的突變點，那么給出了梯度方向。根據(jù)前面的分析可以知道，用小波系數(shù)的局部極大值點可刻畫出圖像信號突變點的位置，即圖像邊緣的位置。因此，利用小波變換的極大值檢測可以探測出圖像的邊緣點?！?.2利用小波變換進行邊緣提取的兩種方法根據(jù)上面所述的利用小波變換進行邊緣提取的根本原理，對于數(shù)字圖像可設計出下述計算機實現(xiàn)方法：選擇MRA濾波器、邊界拓展方式、分解尺度J和閾值T小波變換，設原始圖像為，變換得到、計算：確定與O點相鄰的兩點、。如圖：同時滿足以下三式，那么O點為模極大值點：〔1〕；〔2〕；〔3〕或。假設那么令，否那么。將顯示出來即為所求邊緣圖像。重復步驟2-5，直至分解尺度J。對于上述方法還有以下簡化算法，該算法把二維邊緣檢測問題轉化為小波變換來處理，簡化了算法的復雜度，其實現(xiàn)方法如下：選擇MRA濾波器、邊界拓展方式、分解尺度J和閾值T。對圖像的每一行像素做一維小波變換，并取絕對值。對圖像的每一列像素做一維小波變換重復步驟2。分別求取行列小波變換的模值極大值點，其余點置0。假設，那么令，否那么。將顯示出來即為所求邊緣圖像。重復步驟2-5，直至分解尺度J。按上述方法分別對Lena圖進行邊緣檢測，使用B樣條小波，得到以下圖的邊緣圖像。圖5-1:用小波變換得到的圖像第六章結論這種多尺度不僅改變了以前的高斯算法計算量大的缺陷,而且以較少的運算便可得到理想的圖像處理結果.與傳統(tǒng)的高斯尺度空間算法相比擬,得到如下結論:(1)與傳統(tǒng)的經(jīng)典的邊緣檢測算法相比,此小波變換具有定位精確和計算量小的優(yōu)點;而傳統(tǒng)的和經(jīng)典的邊緣檢測算法不僅不夠精確,而計算量大,對噪聲的敏感程度也遠遠高于小波變換的算法;(2)利用小波的多尺度空間信息,識別圖像邊緣特性的能力比高斯尺度空間強.由于小波變換有多尺度的特點,可以利用多尺度特性,通過細節(jié)和粗節(jié)的逼近,將圖像的空間信息較好的描述,與傳統(tǒng)的和經(jīng)典的邊緣檢測算法相比,在識別邊緣特征方面,強于它們.(3)在邊緣和噪聲的取舍中,由于二者均為高頻信號,很難用頻帶劃分.小波變換的方法,使得在大尺度下抑制噪聲,小尺度下,得到邊緣的真實位置;而傳統(tǒng)的和經(jīng)典的邊緣檢測算法那么在此問題上不能提供有效的解決方法.致謝：為期三個月左右的畢業(yè)設計結束了，在這次設計中使我對數(shù)字圖像處理有了進一步的認識與研究，充實了自己的專業(yè)知識，并且在本次設計中得到了桂志國老師的大力幫助，給我提出了珍貴的意見和修改建議。在此衷心感謝桂志國老師對我的幫助，使我的畢業(yè)論文能夠順利完成。參考文獻：李勇，徐震等，MATLAB輔助現(xiàn)代工程數(shù)字信號處理，西安電子科技大學出版社2002飛思科技產(chǎn)品研發(fā)中心，MATLAB6.5輔助小波分析與應用，電子工業(yè)出版社2003樓順天，李博菡，基于MATLAB的系統(tǒng)分析與設計——信號處理，西安電子科技大學出版社1998胡昌華，張軍波，夏軍，張偉，基于MATLAB的系統(tǒng)分析與設計——小波分析1999胡昌華，張軍波，夏軍，張偉，基于MATLAB的系統(tǒng)分析與設計——小波分析，西安電子科技大學出版社1999楊福生，小波變換的工程分析與應用，科學出版社2001譯文：一種改良的邊緣檢測與邊緣等級排列技術摘要本文說明了一種精簡的Canny邊緣檢測的方法,隨后從邊界的角度排列了他們相對距離上的邊緣.這促進了計算機視覺的適宜細節(jié)選擇,特別是對有連接的物體.第一個議題是對有錯誤的縫隙與偽邊緣中用已經(jīng)存在的Canny算法只選擇一條邊緣相互交叉的路徑.說明了一種有效,實用的Canny技術處理過程,這種算法能夠系統(tǒng)、適宜的連接邊緣，最后一個命題是邊緣的等級排列。1、動機與介紹這項工作的原理與根底理論需要一個可以連接的具有多種邊緣細節(jié)的周界提取器。這需要產(chǎn)生一個圖像預處理的可以進行手動跟蹤系統(tǒng)的平臺，為了實現(xiàn)這個結論，使用精確模板的幾何學技術來瀏覽圖像。他能夠來為圖像重要局部的邊界提取效勞，并能夠很好的分辨出周界上的邊緣細節(jié)的區(qū)別于不同。第二局部簡明的說明了Canny邊緣檢測的算法。第三局部說明了周界提取出的邊緣排列與縫隙連接。第四局部提出了這種技術市怎樣為后期精確的3D物體圖像的處理與重現(xiàn)，第五局部是總結與結論。2、Canny邊緣檢測一種尋找物體邊界的標準后簡單方法是得到它的輪廓，并且對單一的，的可控制的背景輪廓能夠很容易的被計算出來。然而輪廓邊界的精確位置隨著計算閾值的選擇，源方向與邊界附近的光線水平有關。一種更加精簡的方法-幾乎可以克服所有的缺點-是用邊緣檢測，正如我們處理低分辨率圖像時，精確的算法用來抵消粗糙的缺乏，另外一種優(yōu)點是能夠計算出內部細節(jié)而不是一個單點，這對多關節(jié)的物體追蹤是十分重要的。在計算機視覺根底上的邊緣檢測，被定義用來計算圖像的每一個像素值，并按比例計算兩種不同邊界值的像素Canny邊緣檢測算法，被用于openCV，選擇它是因為他的快速運算結果〔與重要的邊緣檢測技術相比擬〕，與它的高效率實行技術。2.1如何工作的第一長圖是被高斯盤旋所平滑的，然后用2D的衍生操作器對平滑圖象的亮光局部檢測。邊緣表示在圖像的梯度極大值上，算子跟蹤檢測那些梯度變化的點，并將不變化的值賦0，所以輸出即為一條線。兩種閾值限制了這種算法，T1與T2<T2，計算時只從值大于T2的點開始。然后想兩個方向計算直到值小于T1。這種滯后現(xiàn)象使得噪聲不會干擾多邊緣的細節(jié)。2.2Y-邊緣連接點效果基于Canny操作器的一個問題是：“Y-連接〞：這種情況發(fā)生在梯度圖象的3個邊緣或者更多的邊緣相交時。當一個邊緣被另外一個物體所融合或交合時，這種算法會把兩個邊緣認作為同一條線，并且第三條極大值邊緣作為一條直線來接近他，但是并沒有連接上另外兩個邊緣。圖1：Canny檢測算子和它的“Y-連接〞效果左：影像圖像，右：Canny邊緣檢測。注意到兩條垂直的顯示怎么樣接近的但是并沒有與中心的水平線相接，產(chǎn)生了水平的兩個偽邊緣。2.3邊緣等級邊緣等級與下面的法那么有關。周界上的邊緣并不是0等級的并且截止在周界上的邊緣。N不是小于N等級的，并且截止在N-1的邊緣后來平臺的處理含有圖像的各種邊緣等級構造起來的框架，有益于選擇適宜的邊緣細節(jié)。3.1周界提取從上面的邊緣檢測發(fā)現(xiàn),周長被提取出來。雖然比擬瑣碎，可能會〔通常都會〕在物體重要局部上有偽造的噪聲，而且周長大體上都不再連續(xù)。首先圖像從內部框架的外邊緣進行掃描，由于任何有界圖形的像素將會從外部接近〔盡管圖形沒有連接〕〔實際上，有一種間接的可能性，即這種掃描可能先連接內部物體的重要局部，但事實上并沒有干擾到運算的成功。最壞打算它只是對低等級的邊緣減慢了檢測進程。然后，檢測邊界的根底圖形，當考慮到其他的邊界像素時對圖形的外界一定要注意，這個可以用下面的實現(xiàn)：當我們對每一個像素沿著周長追蹤時，要保持“最后外部像素〞的觀點。從與痕跡的方向一致的圖形最后的最外面的像素開始旋轉。換句話說，每一次我們找出另外的一個周長像素,我們記錄最后的非周長像素。(在外部)為了要找下一個周長像素，我們替換了立即相鄰像素〔從最后外部像素開始，與旋轉的方向相同〕。我們假設物體重要的外部邊緣在處理的過程中已經(jīng)被移動或者無視。盡管它可能與其他邊緣相接，也可以用測量長度等技術來實現(xiàn)。這不在是一個沒有原形的問題。3.2縫隙連接現(xiàn)在如果我們試著向前追蹤我們已經(jīng)發(fā)現(xiàn)的形狀外部，我們會發(fā)現(xiàn)通常痕跡只出現(xiàn)在物體周界周圍的一局部，因為Canny邊緣檢測留下了縫隙。圖3:維持“最后的外部圖素〞。周長的每個圖素被一個正方形表現(xiàn)，借由從它的中心到它的最后外部的圖素中心的一個直線局部,逆時針旋轉。這種縫隙以各種不同的形式出現(xiàn)，所以需要解決他們的一般的技術。從圖4中拿出一些現(xiàn)實的可觀察的數(shù)據(jù)來，這種技術按照以下各項來解決各種問題：從第一個邊界像素開始，按逆時針方向持續(xù)追蹤?！瞐〕如果痕跡描述一個完全的線路,那么我們完成追蹤。〔b〕否那么紀錄結束像素和最后最外部的像素。從起始像素，按照順時針方向追蹤。對于所有的結束點，試著連接他們。從外部到內部替換，按照一個適宜的尺寸的半徑來掃描。如果另外一個片斷被縮定，連接到與它相連的最近的像素。如果這個新的片段已經(jīng)是在結束的目錄上，用他的新的邊緣合并它，否那么追蹤新的片斷范圍，更新他的結束數(shù)據(jù)。如果有任何的片斷剩余〔暗示所有的片斷結束在偽邊界〕，試著連接他們?！策@一個情形在實際中很少地發(fā)生〕反面-痕跡沿著片段遠離結束局部，從外部的縫隙到內部開始測試，否那么按照3的步驟進行。如果沒有找到連接，便刪除這些結束點〔例如噪音〕。圖4：連接周界的縫隙。內部的縫隙是相似的。圖5：一個實例解釋了為什么必須向后旋轉，而不能通過邊緣向前旋轉〔會在洞中附著〕。3.3等級排列如果所需要的等級比零等級要好，那么所有的周長等級首先被設置為他們的零等級。然后使用上面的縫隙連接技術〔但是不用注意去保持一個外部的意識，并且把所有的求得的半徑內的邊緣連接起來〕，所有的鄰近邊緣被給等級一這一個程序被反復使用直到到達所需要的等級。所有的邊緣與其他的現(xiàn)有N等級相連，那些沒有被分配一個正確的等級，現(xiàn)在被給予等級N+1。4有關節(jié)物體的3D重建試著用照相機的圖像重構一個有關節(jié)的物體，對有折痕的關節(jié)連接處是非常有用的，這確定了連接點的位置，并且促進了連接點的彎曲點角度變化的發(fā)覺。然而，較好的水平細節(jié)，在這個階段通常是不受歡送的，如同它只是引導噪聲或者將不需要的復雜局部成為進一步的處理的平臺。然而在關節(jié)連接的三維物體，二維圖像來看，一些〔或更多〕的三維物體的外部邊緣在投射之后成為內部的邊緣。圖6：注意手指(對三度空間的手外部)的邊緣如何變成內在的邊緣的在那二維空間圖像。在這一個圖像中，手指的所有看得見的邊緣是等級3,并且四指的末尾的白色光芒連接處與拇指末尾的關節(jié)黑暗連接處的折痕是2或者3。因此等級3是這個圖的最正確等級。邊緣的兩邊可以用閾值〔T1，T2〕精確的設定。這樣的話，用這項技術可以正確的給定周長的邊緣和等級，而且知道了粗糙物體的位置/方向〔比方以前的框架，速度和模型限制〕，他相對的變?yōu)檫x擇那些三維物體的邊緣使用技術，和其他的有關節(jié)折痕的物體的重要特征。5摘要與結論這種技術可以簡潔高效的論證附加在已存在的邊緣檢測算子上的錯誤的實時表現(xiàn)。借由提供這些邊緣等級，適當程度的細節(jié)局部立刻被帶到焦點里去〔包括聯(lián)系的方式，周長提取〕，因此，直接促進了有關節(jié)物體模型的協(xié)調，重要的減少了將來計算機視覺處理過程中的冗余。圖7：使用這項技術進行圖像預處理片斷的截圖。注意在左邊〔Canny邊緣〕上的圖像如何被去除，只表現(xiàn)在右邊次圖像的周長上。C++源代碼可以自由的從網(wǎng)上下載，并且手式圖形的追蹤報告也可以在那里發(fā)現(xiàn)。譯文原件：AnImprovedEdgeDetectionandRankingTechniqueDeclanMurphyComputerScienceDept,CopenhagenUniversityAbstractAmethodispresentedforrefiningtheCannyedgedetectionalgorithm,andsubsequentlyrankingtheresultingedgesrelativetotheirdistance(inatopologicalsense)fromtheperimeter.Thisfacilitatestheselectionoftheappropriatelevelofdetailforcomputervision,particularlyofarticulatedobjects.ThefirstissueisthewayinwhichtheexistingCannyalgorithmchoosesonlyonepathwhereedgescrosseachother,resultinginerroneousgapsandspuriousdoublingofedges.Anefficientpragmaticpost-processingoftheCannytechniqueispresented,whichsystematicallybridgesthesegapsappropriately.Thenextissueistheautomaticrankingoftheedges.1MotivationandIntroductionTherationaleandmotivationbehindthisworkwastherequirementforaconnectedperimeterextractorwithavariableamountofedgedetail,tracinginfromtheperimeter.Thisneedaroseasanimagepre-processingstageofahandposturetrackingsystem,inordertofacilitateadeterministic,geometricaltechniqueforreconcilingimageviewswithanarticulatedmodel.(Forfurtherdetailsofthis,see[6].)Itshouldserveusefulinanysituationinwhichperimeterextractionoftheforegroundimage,alongwithaspecifiablelevelofedgedetailinfromtheperimeter,wouldbeadvantageous.Section2brieflydescribestheCannyedgedetectionalgorithm.Section3coverstheedgerankingwithadescriptionoftheperimeterextraction,§3.1,andgapbridging,§3.2.Section4pointstowardshowthistechniqueservesthefurtherstageofprocessingofreconcilingimageviewstoamodelofanarticulated3Dbody.Section5windsupwithasummaryandconclusion.“MostofthisworkwascarriedoutwhiletheauthorwasvisitingthecARTlabofCNR,Pisa,withsubsequentrefinementandwrite-upattheInfoMuslabofDIST,UniversityofGenoaandatDAIMI,UniversityofoArhus.2CannyEdgeDetectionOnestandard,orsimple,approachtofindingtheperimeterofanobjectistotakeitssilhouette,whichisveryeasytocomputeif(asinthecasemotivatingthiswork)thereisasingleforegroundobjectofinterestwithaknownorcontrolledbackground.However,theexactpositionofthesilhouettebordervarieswiththethresholdinglevelusedtocomputeit,andwithboththesourcedirectionandtheleveloftheambientlighting.Amoreaccurateapproach{almostimmunetotheseweaknesses{istouseedgedetection.Aswemaybedealingwithlowresolutionimages(toenhancereal-timeperformance),suchaccuracyisdesirabletooffsetcoarsediscretisationinaccuracy.Anothersignificantadvantageistheabilitytomakeoutsomeoftheinnerdetailinsteadofperceivingjustasingleblob.Thisbecomesparticularlyimportantifanarticulatedobjectisbeingtracked,asexplainedin§4.Edgedetection,incomputervision,isdefinedastheprocessofassigningavaluetoeachpixelofanimageinproportiontothelikelihoodthatthepixelisontheboundarybetweentworegionsofdifferentintensityvalues.TheCannyedgedetectionalgorithm[1]isused{asimplementedintheIntelOpenComputerVisionPerformanceLibrary(OpenCV)[2].Thiswaschosenforitssharpresults(incomparisontorivaledgedetectiontechniques),andforitsefficientimplementation(whichwasreadilyavailable).2.1HowitWorksFirsttheimageissmoothedbyGaussianconvolution;thenasimple2Dfirstderivativeoperatorisappliedtothesmoothedimagetohighlightregionsoftheimagehavinghighfirstspatialderivatives1.Edgesgiverisetoridgesinthegradientmagnitudeimage.Thealgorithmthentracksalongthetopoftheseridgesandsetsallpixelsthatarenotontopoftheridgetozero,soastogiveathinlineintheoutput.Twothresholdslimitthetracking:t1andt2,witht1<t2.Trackingcanonlybeginatapointonaridgehigherthant2.Trackingthencontinuesinbothdirectionsoutfromthatpointuntiltheheightoftheridgefallsbelowt1.Thishysteresishelpstoensurethatnoisyedgesarenotbrokenupintomultipleedgefragments.2.2TheY-JunctionEffectOneproblemwiththebasicCannyoperatoristhatofso-called`Y-junctions':placeswherethree(ormore)ridgesmeetinthegradientmagnitudeimage.Suchjunctionsoccurwhereanedgeispartiallyoccludedbyanotherobject.1Spatialderivativesimplyreferstohowmuchtheimageintensityvalueschangeperchangeinimageposition.Seee.g.[3,ch.5]or[4]forfurtherbackgroundonedgedetection.Thetrackerwilltreattwooftheridgesasasinglelinesegment,andthethirdoneasalinethatapproaches,butdoesn'tquiteconnectto,theothertwo.Seefigure1.Figure1:CannyEdgeDetectionandits`Y-Junction'effect.Left:cameraimage;right:Cannyedgeimage.Notehowthetwoverticallinesapproachbutfailtocontactthecentralhorizontalline,resultinginaspuriousdoublingupofalengthofthehorizontaledge.3EdgeRankingArank(lownon-negativeinteger)isassociatedwitheachedgeaccordingtothefollowingrule:0correspondstoedgesontheperimeter,1correspondstoedgesterminatingontheperimeterwhicharenotofrank0,ncorrespondstoedgesterminatingonanedgeofrankn-1whicharenotofrank<n.Seefigure2.Laterstagesofprocessinghavetheoptionofhavinganimageframecomposedofalledgesuptoaspecifiedrank,therebyselectingtheappropriatelevelofdetail.Figure2:Anexampleofsomeedgeranks.3.1PerimeterExtractionTakingtheedgedetectionfromabove,x2,theperimeterisinturnextracted.Whilethismaysoundtrivial{asindeeditistoourhumaneyes{itisnotsoforthecomputer:theremaybe(andingeneralwillbe)somespuriousnoiseoutsideoftheobjectofinterest,andtheperimeterwillnotbecontinuousingeneral.Firsttheimageisscanned,fromanouteredgeoftheframeinwards,forany“blob〞2insuchamannerthatanyenclosedshapewillbeapproachedfromtheoutside(evenifthisshapeisnotconnected3).(Actually,thereisaveryremotepossibilitythatthescanmayfirstencountertheobjectofinterestfromtheinside,butinfactthisdoesnotinterferewiththesuccessofthealgorithm.Atworst,itwillonlymarginallyslowtheprocessinthecasethatonlylowrankedgesarerequired.)Next,theperimeterofthefoundshapeistraced,payingcarefulattentiontoalwayskeeptotheoutsideoftheshapewhileconsideringthenextpixelalongtheperimeter.Thisisachievedby:1.maintainingtheconceptof\thelastouterpixel",foreachpixelaswetracealongtheperimeter,2.rotating,fromthelastouterpixeltothenextpixeloftheshape,inadirection(alwaysclockwiseoralwaysanticlockwise)consistentwiththeangularpolarityofthetrace.Inotherwords,everytimewelocateanotherperimeterpixel,werecordthelastnon-perimeterpixel(ontheoutside).Inordertofindthenextperimeterpixel,werotateabouttheimmediateneighbouringpixels{startingwiththenextpixelafterthelastouterpixel,inaconsistentdirectionofrotation.Seefigure3.Weareassumingfromhereonthatedgesoutsideoftheobjectofinterest(ifany)havebeenremovedoraredisregardedintheprocessing.Thismaybeachievedbysuchtechniquesasgaugingthelength,whetheritliesclosetootheredges,etc.,asdescribedin,forexample,[5].Thishasnotbeenaproblemintheprototype.3.2BridgingGapsNowifwetrytotracealongtheoutsideoftheshapewehavefound,wewillfindthat,veryoften,thetraceonlyrunsaroundasectionofthedesiredobjectperimeterbecauseofgapsleftbytheCannyedgedetection(x2.2).2Here,a\blob"simplymeansanumberofpixelsallaboveacertainintensityvalue,eachoneofwhichisadjacenttoatleastoneothersuchpixel.3Thetermconnectedisborrowedfromtopology:hereitsimplymeansthattheshapeinquestioncanbyentirelytracedthroughadjacentpixels.Figure3:Maintainingthe\lastouterpixel".Eachpixeloftheperimeterisrepresentedbyasquare,withastraightlinesegmentfromitscentretothecentreofitslastouterpixel,rotatinganticlockwise.Suchgapscomeinvariousforms,sothatageneraltechniquetobridgethemallisrequired.Someexamplestakenfromobservationofrealdataappearinfigure4.Thetechniquefoundtocoverallcases,testedwithreal(hand)data,isasfollows:1.Startingwiththefirstperimeterpixelfound,continuetracinganticlockwise.(a)Iftracedescribesafullcircuit,thenwearefinished.(b)Otherwiserecordtheendpixelandthelastouterpixelofthesecond4fromendpixel.2.Fromtheinitialpixel,traceclockwise.(a)Recordtheendpixelandthesecond4fromendlastouterpixel.3.Forallends,trytojointhem.(a)Rotatefromoutsidetoinside,scanningalongaradiusoftheappropriatesize6.(b)Ifanothersegmentislocated,jointothenearestpixelonit.4Weusethelastouterpixelofthesecondtoendpixelbecausethatoftheendpixelwillhaveswungaroundintotheinside.Recoveryoftheoutsidemaybemadebyrotatingback5(ifthesegmentstendtobelong)orbyplacingthelastouterpixelsinatwocellLastInFirstOut(LIFO)buffer(ifthesegmentstendtobeveryshort).5Inrotatingbackwards,thetemptationtotaketheshortcutofrotatingonthroughtheedgemustberesisted!Seefigure5.6Thereisacertainradius(oraperture)sizeobservedtobebothlargeenoughtobridgeallY-junctionsandsmallenoughtonotinterferewithotheredgesinthevicinity,foragivenimageresolutionandagivendistancefromcameratosubject.(c)Ifthisnewsegmentisalreadyonthelistofends,mergeit(onthelist)withitsnewpartner;otherwise,tracetheextentofthenewsegment,updatingitsenddata.4.Ifanysegmentsremain(implyingthatallsegmentsendinspuriousdiversions),trytojointhem.(Thiscaseoccursonlyveryrarelyinpractice.)(a)Back-tracealongthesegmentawayfromtheend,testingwithintheaperturefromoutsidetoin,andotherwiseproceedasin3.(b)Ifnojoinisfound,deleteendfromlist(considerasnoise).Figure4:Bridgingtheperimetergaps.Internalbridgingissimilar.Figure5:Acounterexampleofwhyrotationmustbebackwards,notonwardsthroughtheedge(whichwouldgetstuckinthehole!).3.3RankingIfthedesiredrankisgreaterthanzero,thenallperimeterranksarefirstassignedtheirzerorank.Then,usingtheabovegapbridgingtechnique(butwithoutfurtherheedtomaintainingasenseofoutside,andjoiningtoallotheredgeswithintheseekradius),alladjoiningedgesaregivenrankone.Thisprocessisiterateduntilthedesiredrankisattained:alledgesadjoiningthoseofthecurrentrank,nsay,whichhavenotyetbeenassignedapositiverank,arenowgivenrankn+1.43DReconstructionofArticulatedObjectsIntryingtoreconcileamodelofanarticulatedbodywithcameraimages,itisgenerallyusefultotakenoteoftheedgesarisingfromcreasesalongthearticulationjoints,thusyieldingcuestothelocationofthejoints,andfacilitatingrecognitionoftheanglesofflexionofthejoints.Finerleveldetail,however,isgenerallyundesirableatthisstage,asitonlyintroducesnoiseorneedlesscomplicationintofurtherstagesofprocessing.Moreover,inviewingtheprojectionofarticulated(or,indeed,non-concave7)threedimensionalbodiestotwodimensionalimages,some(o