（計算數(shù)學專業(yè)論文）小波變換及其在仿射不變目標識別中的應用.pdf

摘要 目標識別是計算機視覺的一個重要研究方向，在軍事、自動化領域有著廣泛 的應用前景。該文主要研究了利用物體的二維圖像識別物體的方法。同一個二位 景物，攝像機在不同的地點、從不同角度拍攝，得到的幾何形狀不同。任意兩幅 圖像問的幾何變形可用攝影變換來描述。當攝像機與景物之間的距離遠遠大于景 物的尺寸時，射影變換可用仿射變換來近似代替。 首先介紹基于內(nèi)容的圖像檢索發(fā)展和現(xiàn)狀，對形狀匹配的方法進行了回顧介 紹了一些形狀表示方法。其中主要是形狀簡化的方法形狀匹配的方法可以分為 基于各種變換不變量的形狀匹配方法和基于局部特征的形狀匹配方法，并根據(jù)這 一分類介紹了很多有代表性的匹配方法 小波分析是近十幾年在國際上掀起熱潮的一個前沿領域，它被認為是傅立葉 分析方法的突破性發(fā)展，是一種新的時頻分析方法?；谛〔ǚ治龅哪Ｊ阶R別研 究是當前十分活躍的研究領域并有廣闊的應用前景。該文著重對小波分析的基本 理論進行了介紹。同時從小波闕值函數(shù)與散度函數(shù)的關系入手進行研究，說明了 小波分析與偏微分方程之間的聯(lián)系。 尋找相對于平移、尺度、旋轉(zhuǎn)、扭曲不變的仿射不變量是現(xiàn)今多尺度分析在 模式識別中應用的關鍵性問題?？紤]到平穩(wěn)小波變換同時具有平移不變和多尺度 分析的優(yōu)越性，該章對物體輪廓參數(shù)化方程進行平穩(wěn)小波變換，研究了具有仿射不 變性的基于平穩(wěn)小波變換的特征不變量的構(gòu)造 關鍵詞：目標識別邊緣檢測仿射不變量小波變換偏微分方程 a b s t r a c t o b j e c tr e c o g n i t i o ni so n eo ft h ei m p m 恤n tp a r t so fc o m p u t e rv i s i o n ，a n dh a s b e e n w i d e l ya p p l i e di nt h ef i e l d ss u c ha sm i l i t a r ya f f a i r sa n da u t o m a t i z a t i o n i nt h i sp a p e r , w e s t u d yt h em e t h o do fr e c o g n i z i n go b j e c ti n i t s2 - di m a g e f o rt h es a m eo b j e c t , t h e g e o m e t r ys h a p eo fi m a g eo b t a i n e di s d i f f e r e n tw h e nt h ec a m e r ai sl o c a t e dd i f f e r e n t o r i e n t a t i o na n da n g l e t h eg e o m e t r yd i s t o r t i o no fa r b i t r a r yt w oi m a g e sc a nb ed e s c r i b e d w i t hp e r s p e c t i v et r a n s f o r m t h ep e r s p e c t i v et r a n s f o r mc a nb er e p l a c e da p p r o x i m a t e l y w i t ha 伍n et r a n s f o r mw h e nt h ed i s t a n c eb e t w e e nt h ec a n l e l aa n dt h eo b j e c ti sl a r g e rt h a n t h ed i m e n s i o no ft h eo b j e c t t h eb a c k g r o u n da n dd e v e l o p m e n to ft h ei m a g er e t r i e v a lb a s e do nc o n t e n ti s i n t r o d u c e d av i e wo fs h a p em a t c h i n gm e t h o d si s p r o v i d e da l s o s o m es h a p e r e p r e s e n t a t i o nm e t h o d sa r ep r e s e n t e d ，m a i n l yt h es h a p es i m p l i f i c a t i o nm e t h o d s s h a p e m a t c h i n gm e t h o d sc a nb ec l a s s i f i e di n t ot w og r o u p s ，m a t c h i n gb yk i n d so fi n v a r i a n t s a n dm a t c h i n gb yl o c a lf e a t u r e s , a n da c c o r d i n gt ot y p e s , a no v e r v i e wo ft h em o s t r e p r e n t a t i v em e t h o d si sp r e s e n t e d w a v e l e ta n a l y s i si san e wt i m e f r e q u e n c ya n a l y s i sm e t h o dw h i c hh a sr a i s e da r e s e a r c hu ps u r g ei n t e r n a t i o n a l l yi nr e c e n ty e a r s i ti sr e g a r d e da sab r e a k t h r o u g ho f f o u r i e ra n a l y s i s 0 b j e f tr e c o g n i t i o nu s i n gw a v e l e tt r a n s f o r mi sa na c t i v er e s e a r c h d o m a i na n dh a sw i d ea p p l i c a t i o na r e a s t h eb a s i so fw a v e l e ta n l y s i si sa d d r e s s e d t h e n t h er e l a t i o n s h i pb e t w e e nt h ew a v e l e ts h r i n k a g ea n dd i f f u s i o ne q u a t i o ni ss t u d i e d atl a s ts t a t i o n a r yw a v e l e tt r a n s f o r mh a sb e e nu s e dt od e r i v ea na f f i n ei n v a r i a n t f u n c t i o n i t sak e yp r o b l e mt os e a r c hf o ra f f i n ei n v a r i a n tw i t hr e s p e c tt ot r a n s l a t i o n ， s c a l i n g , r o t a t i o na n ds k e w i n gi nm u l t i - r e s o l u t i o na n a l y s i s c o n s i d e r i n gt h ea d v a n t a g e s o ft h es t a t i o n a r yw a v e l e tt r a n s f o r m ，an e wa f f i n ei n v a r i a n tf u n c t i o nb a s e do na n a l y z i n g t h eo b j e c tb o u n d a r yu s i n gt h es t a t i o n a r yw a v e l e tt r a n s f o r mi sc o n s t m f t e d e x p e r i m e n t r e s u l t sd e m o n s t r a t et h ed i s c r i m i n a t i n gp o w e ro ft h ep r o p o s e di n v a r i a n tf u n c t i o n k e y w o r d s ：o b j e c tr e c o g n i t i o ne d g ed e t e c t i o na f f i n ei n v a r i a n tw a v e l e t t r a n s f o r m p a r t i a ld i f f e r e n t i a le q u a t i o n 創(chuàng)新性聲明 本人聲明所呈交的論文是我個人在導師指導下進行的研究工作及取得的研 究成果。盡我所知，除了文中特別加以標注和致謝中所羅列的內(nèi)容以外，論文中 不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果；也不包含為獲得西安電子科技大學 或其它教育機構(gòu)的學位或證書而使用過的材料。與我一同工作的同志對本研究所 做的任何貢獻均已在論文中做了明確的說明并表示了謝意。 申請學位論文與資料若有不實之處，本人承擔一切的法律責任。 本人簽名：五島i 目 日期2 丑= 2 關于論文使用授權(quán)的說明 本人完全了解西安電子科技大學有關保留和使用學位論文的規(guī)定，即：研 究生在校攻讀學位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學。學校有權(quán) 保留送交論文的復印件，允許查閱和借閱論文；學?？梢怨颊撐牡娜炕颍悍?內(nèi)容，可以允許采用影印、縮印或其它復制手段保存論文。同時本人保證，畢業(yè) 后結(jié)合學位論文研究課題再攥寫的文章一律署名單位為西安電子科技大學。( 保 密的論文在解密后遵守此規(guī)定) 本人簽名：亞凰l 虱 刷磁轢別麓p | 砂虻“廣 日期塵翌! ! 翌 日規(guī)絲嗥一丕衛(wèi) 第一章緒論 第一章緒論 本章首先介紹基于內(nèi)容的圖像檢索發(fā)展和現(xiàn)狀，然后介紹了選題的依據(jù)和背 景，最后介紹本文所要研究的問題和所作的主要工作。 1 1 基于內(nèi)容的圖象檢索 當今世界是知識爆炸的時代，每個人、公司、機關每天都要閱讀和處理大量的 文獻和材料，其中包括了大量的文字、圖象和聲音的材料。同時當今世界是計算 機與信息的時代，所以應用計算機來存儲、傳輸和檢閱文獻成為當今最大的潮流。 并使文字輸入、組織、和檢索方面取得了飛速的進展。近十年來i n t e m e t 得到了廣 泛應用，它與上述技術的結(jié)合使數(shù)字圖書館變成流行的話題。然而數(shù)字圖書館面 臨的最大之一是“基于內(nèi)容”的檢索，尤其是對于大量的圖象數(shù)據(jù)，這是一個尚未成 熟的技術。 我們每天都會獲得以g 字節(jié)計的數(shù)字圖象、數(shù)字化的視頻信號、醫(yī)學圖象、 遙感圖象、新聞圖片，等等。對這些巨大量的數(shù)據(jù)如何組織、表達、存儲、管理、 查詢、檢索是對傳統(tǒng)數(shù)據(jù)庫技術提出的重大挑戰(zhàn)，以文字為對象的傳統(tǒng)數(shù)據(jù)庫無 法滿足圖象數(shù)據(jù)庫的要求，這是因為，一方面，圖象與視頻中包含的信息非常豐 富，很難用標準化的一些文字對它們進行精確、詳盡的描述，另一方面，由于圖 象與視頻數(shù)據(jù)的與日俱增，傳統(tǒng)手工建立關鍵字索引的方式己很不現(xiàn)實，我們希 望對進入數(shù)據(jù)庫的圖象視頻數(shù)據(jù)的描述可以由計算機快速、規(guī)范、自動地進行。 總之，沒有對圖象及視頻數(shù)據(jù)的自動和有效的描述，大量信息將淹沒在數(shù)據(jù)庫中， 無法在需要時被檢索出來。因此，如何將數(shù)字圖象處理、計算機視覺技術與傳統(tǒng) 數(shù)據(jù)庫技術相結(jié)合，建立基于對圖象及視頻內(nèi)容自動或半自動描述的新一代圖象 視頻數(shù)據(jù)庫就成為迫切的需求。 近十年來，基于內(nèi)容的圖象、視頻數(shù)據(jù)的檢索是當前計算機視覺，圖象數(shù)據(jù)庫 與知識挖掘( k n o w l e d g ed i s c o v e r y ) 等領域研究的最活躍的研究熱點之一。近幾年， 許多國際上重要的刊物，都以此內(nèi)容發(fā)表了?？?。目前，國內(nèi)外很多機構(gòu)都在進 行相關的研究工作，并產(chǎn)生了很多令人矚目的成就。國內(nèi)的一些研究單位，如中 科院自動化所國家模式識別實驗室，清華大學，上海交通大學，復旦大學等單位 也進行了研究并開發(fā)了一些實驗系統(tǒng)。圖1 是實驗系統(tǒng)的框圖。 2 平不變的小波變換及其在仿射不變目標識別中的應用 圖1 1 基于內(nèi)容的圖象檢索系統(tǒng) 所謂基于內(nèi)容的檢索( c b r ，c o n t e n t b a s e dr e t r i e v a l ) ，是指直接根據(jù)描述媒體對 象內(nèi)容的各種特征進行檢索，它能從數(shù)據(jù)庫中查找到具有指定特征或含有特定內(nèi) 容的圖象( 包括視頻片段) ，它區(qū)別于傳統(tǒng)的基于關鍵字的檢索手段，融合了圖象理 解、模式識別等技術，具有如下特點： 直接從媒體內(nèi)容中提取信息線索。基于內(nèi)容的檢索突破了傳統(tǒng)的基于表達式檢 索的局限，它直接對圖象、視頻進行分析，抽取特征。利用這些描述圖象內(nèi)容的 特征建立索引( i n d e x ) 基于內(nèi)容的檢索是一種近似匹配。在數(shù)據(jù)庫中，須使用模式識別的方法對圖象 庫中的圖象按不同索引特征分類，在檢索的過程中，它采用某種相似性度量對圖 象庫中的圖象匹配獲得查詢的結(jié)果。這一點與常規(guī)數(shù)據(jù)庫檢索的精確匹配方法有 明顯不同。 特征提取和索引建立可由計算機自動實現(xiàn)，避免了人工描述的主觀性，也大大 減少了工作量。但相似性度量與人的主觀感受有關( u p 任給一幅圖象，問數(shù)據(jù)庫中 的其他圖象中那些與它在觀感、風格，某些特定內(nèi)容上相似? 顯然，這與人的主觀 性有關1 ，因此，常需要用人機交互的方法，學習人的主觀相似度感受。 以圖象的特征作為索引( i n d e x ) ，對靜態(tài)圖象進行檢索是目前使用得最多的方 法。目前比較成熟的特征索引是顏色、紋理和一些低層的、簡單的形狀特征和物 體間方位關系【】。這些特征具有計算簡單，性能穩(wěn)定的特點，但這些特征都有一 定的局限性，因此，近幾年的研究則逐漸轉(zhuǎn)向基于區(qū)域、目標的圖象表示，語義 第一章緒論 3 描述等。檢索則引進用戶反饋等方法。 1 1 1 顏色 顏色是一種重要的視覺信息屬性，在圖象索引與檢索中是一種很有用的特 征相對于其他特征，顏色特征非常穩(wěn)定，對于旋轉(zhuǎn)，平移，尺度變化，甚至各 種形變都不敏感，表現(xiàn)出相當強的魯棒性，并且顏色特征計算簡單，因此成為現(xiàn) 有檢索系統(tǒng)中應用最廣泛的特征。 顏色檢索的基本思想是將圖象間的相似度歸結(jié)為圖象顏色直方圖之間的距離。 這方面奠基性的工作是s w a i n 和b a l l a d 4 1 提出的直方圖交集算法，它計算兩幅圖象 的三維顏色直方圖的每一個顏色單元，并進行細致的比較。m e h t r e | 5 1 等提出距離算 法和參考顏色表方法，實驗表明，每幅圖象只需保留很少幾種主要顏色，就能得 到很好的結(jié)果。 為了得到與人的感覺類似的相似性度量，一些研究者還提出采用其他的顏色空 間模型和距離測度。z h a n g 6 j 采用了符合人眼感覺的h s 1 模型。上述所有方法中 的距離測度均基于l l 距離，它們未考慮不同顏色間的相似性問題，這也使得度 量結(jié)果與人的感覺有差異。因此，h a r f n e r 7 】在進行直方圖匹配時弓l a y z 次型距離。 另外，在提高檢索對于光照的穩(wěn)定性i s ，空間分布信息的引入【9 】等方面，也出現(xiàn)了 很多算法。 1 i 2 紋理 紋理是與物體表面材質(zhì)有關的圖象特征，目前也是基于內(nèi)容檢索系統(tǒng)中的一條 重要線索。 紋理分析一直是計算機視覺的一個重要研究方向，其方法主要分為兩類：結(jié)構(gòu) 方法和統(tǒng)計方法。結(jié)構(gòu)方法假定圖象由較小的紋理基元排列而成。它采用句法分 析方法，只適用于規(guī)則的結(jié)構(gòu)紋理。統(tǒng)計方法又可進一步分為傳統(tǒng)的統(tǒng)計方法， 基于模型的方法，以及基于頻譜分析的方法。 傳統(tǒng)的統(tǒng)計分析方法始于7 0 年代早期h a r a l i c k l l 0 】等提出的基于二階灰度統(tǒng)計 特征的共生矩陣方法，其中計算了1 4 種特征，并用于衛(wèi)星圖象分類。t a m u r a “j 以人的主觀心理度量為標準，提出了六個基本的紋理特征，這些特征與人的感覺 較一致，在許多圖象檢索系統(tǒng)中得到應用，如q b l c 。馬頌德1 1 2 】等利用紋理的二階 灰度統(tǒng)計特征合成了與人的主觀感受一致的問題圖象證明了上述特征在視覺上的 重要性。 8 0 年代開始，基于隨機場模型的技術被用于紋理分析。k a s h y a p 等i ”】提出用 4 平不變的小波變換及其在仿射不變目標識別中的應用 c s a r ( c i r c u l a rs i m u l t a n e o u sa u t o r e g r e s s i v e ) 模型提取旋轉(zhuǎn)不變的紋理特征。c 0 h e n 【1 4 】 則采用t g m r f ( g a u s s i a nm a r k o vr a n d o mf i e l d ) 模型。m i t 的p h o t o b o o k ”】中采用 了隨機場的2 d 分解技術，得到p e r i o d i c i t y ，d i r e c t i o n a l i t y ，a n dr a n d o m n e s s 三種特 征，用于紋理圖象檢索。 多尺度的思想促進了基于頻譜分析的方法的發(fā)展，特別是基于g a b o r 濾波器的 技術在紋理分析中被廣泛采用【1 6 1 7 1 ，g a b o r 濾波器可以通過調(diào)整獲得圖象不同方向 和尺度的紋理信息。m a j u n a t h l l 8 l 等把它用于圖象檢索，并把它與m r s a r ( m u l t i r e s u l u t i o ns i m u l t a n e o u sa u t o r e g r e s s i v e ) 和小波變換等方法做了比較。 1 1 3 形狀 基于圖象內(nèi)物體形狀的檢索是基于內(nèi)容檢索當中一個最具挑戰(zhàn)性的問題之 一，因為尋找符合人眼感知特性的形狀特征不是一件簡單的工作。 首要的困難是要將不同物體從圖象中分割出來，這是計算機視覺的困難問題之 一。對形狀的描述也是困難的問題，提出的方法有付立葉描述子 1 9 1 、矩不變量【2 0 j ， 各種簡單的形狀因子【2 1 j ，瓣( a r e a ) ，圓度( c i r c u l a r i t y ) ，偏心度( e c c e n t r i c i t y ) ，主軸 方向( m a j o ra x i so r i e n t m i o n ) 等。 除這些幾何特征外，人們還提出了許多相對于變換不變的特征量，其中包括矩、 z e r n i k e 矩、l a g e n d r e 矩、f o u r i e r 描繪子、小波描繪子、形態(tài)描繪子等。人們還相 對仿射變換提出了許多不變量，弧長，輪廓所包含的面積，改進的f o u r i e r 描繪子。 由于基于簡單特征的方法無法對形狀作細致的匹配，也不能解決廣泛存在的 變形問題。因此實際系統(tǒng)中常常只用它們來作初步的過濾，最終的匹配結(jié)果由一 些更復雜的基于點對應的方法給出，如變形模板【2 2 1 ，彈性匹配【l 等，楊青【刎、 丁險峰等瞄j 提出了一種用基于許瓦茲變換的形狀匹配。 1 2 選題依據(jù) 仿射變換時一類重要的線性幾何變換，許多成像過程及其變化可以模型化為 一個仿射變換，如在圖像在平面中的平移或旋轉(zhuǎn)可以模型化為坐標系的平移或旋 轉(zhuǎn)，成像距離的改變可以模型化為坐標系刻度的縮放。此外，剪切變換、拉伸變 換等也都是仿射變換。 目標匹配是計算機視覺和模式識別的一個基本問題，它被應用到很多領域，如 目標識別、基于內(nèi)容的圖像檢索、文字識別、醫(yī)療診斷等尋找相對于平移、尺度、 旋轉(zhuǎn)和扭曲不變的仿射不變量是現(xiàn)今目標識別應用中的關鍵性問題。在目標匹配 的過程中需要處理各種各樣的變化，引起變化的原因主要有：信號中的噪聲；各種 第一章緒論 5 變換( 相似變換，仿射變換，射影變換，以及各種高階變換) ；遮擋( 自遮擋，互遮擋) ；變形 ( 局部變形和全局變形) 因此建立一個準確率高，具有抗幾何形變和抗噪聲性能的目標識別方案是有 著重大意義的。 1 3 本文的工作 本文的工作是平移不變的小波變換在仿射目標識別中的應用的研究，采用基 于模型的識別方法，即通過對待識別的目標與模型庫中的已知目標進行比較，來 確定待識別的物體。目標識別的步驟一般可分為：圖像預處理、特征提取和分類 識別。本文研究就是基于這三個步驟。全文共分六章。 第一章為緒論，介紹了模式識別的基本概念，以及本文的選題依據(jù)，并分析了 仿射目標識別的國內(nèi)外現(xiàn)狀。 第二章為形狀匹配及其簡介。 第三章為小波分析的基本理論，給出了由多分辨分析構(gòu)造正交小波函數(shù)的一般 框架及小波變換的快速實現(xiàn)算法m a l l a t 塔式算法，同時介紹了平移不變的小波變 換，主要有平穩(wěn)小波變換等。 第四章介紹了平移不變的小波變換與多尺度擴散的關系。 第五章為平移不變的小波變換在仿射不變物體識別中的應用，首先利用小波變 換給出了兩層和三層的仿射不變量，緊接著又在三層的仿射不變量的基礎上給出 了六層的仿射不變量。最后介紹了基于平穩(wěn)小波變換的仿射不變量，并于基于二 進小波變換韻仿射不變量進行了比較。 最后為本篇論文的結(jié)論。 第二章形狀匹配技術 7 第二章形狀匹配技術 形狀玨配是計葵規(guī)視覺和模式識別的一個基本翊題，農(nóng)過去的凡十年中，人 】研究和開發(fā)靜數(shù)零清的形狀囂配算法，毽蹩每一類算法部有其優(yōu)熹幫歃陲，麝 以在不同的場合下，不同的算法有著不同的性能。那么將其總結(jié)和歸擻就變得十 分熏隳了。本章對形狀匹配技術的研究方法避e 行了回顧，形狀匹配的方法在物體 識鬟、廷配、囂壤秘分輯豹系統(tǒng)孛都騫羞鬻重要豹終溺，經(jīng)零被瘟弱爨穰多領 域例如目標識別，基于內(nèi)容的圖像檢索，文字識別，醫(yī)療診斷等。形狀匹配研究 的開展，主要原因是對人們視徽形式感知系統(tǒng)的研究。給出了形狀分析方法的分 類方法，分類方法鼴結(jié)果，討論了形狹匹配巾最具代表餒方法豹總體臻法。 2 1 形狀匹配的基本概念 巍鼴察周匿琢凌瓣，久弱懿先注意到豹怒攜俸及葵竭爨懿顏色、紋理、形狀霸 空間關系等等，形狀是物體最蕊本的有感徽意義的特征之一。在計算機視覺和模 式識別中，形狀怒對目標范圍的二值圖像襲冪，可以看成是目標的輪廓，它是用 于爨稼識別豹重要特援。受了螢省存耱空翊、易子特征謗算，需要對形狀終進一 步的襲示，這些襲零通常可娃分為兩類：編碼方式，魏鏈弱、游程碼、f r e e m a n 碼等： 簡化方式，如樣條( b 樣條，3 次，5 次樣條) 、插值、多項掰= 、多邊形遇避、和特征 點檢測等。另外述可以使用形狀的骨架來描述形狀。 形狀箍述是遴遺一些方法黛裁數(shù)篷懿爨述予寒疆述形狀，接述子癜該在瑟可縫 區(qū)男i j 不同目標的藏礎上對目標的平移、旋轉(zhuǎn)和尺度變化不敏感。下面列出了一些 常用的形狀描述予。 1 ) 基于死拜牾縫：緊密度、突心發(fā)、臻心攀、不瘦雯g 凌等： 赫基于統(tǒng)計特征：粳糙度、均值、方差等： 3 ) 變換域特征：矩、f o u r i e r 描繪子、小波描繪子、形狀描繪子等： 仿射不變爨：簡比等； 5 ) 射影不變蘩：交篦等。 形狀匹配就是通過按一定的度量準則來衡量形狀間的相似性。在進行形狀匹配 時必須處理各種各樣的形狀變化。 彩坎匹配可渡擻據(jù)不囂掭攥送囂分類，麴：彤裝廷配爨基予形裝戇邊器還是內(nèi) 部。這里根據(jù)匹配方法處理形變的能力將形狀匹配方法分為兩大類。類只能處 理備種變換引起的形狀變化，像們通過搜索猩不同變換下的不變量： 8 平不變的小波變換及其在仿射不變目標識別中的應用 1 ) 相似不變量一距離、矩、角度、圓度、f o u r i e r 描繪子； 2 ) 仿射不變量一簡比、弧長、包圍面積、改進型f o u r i e r 描繪子； 3 1 透視不變量交比及其延伸。 另一類方法可以處理更加復雜的形變，它們通過尋找目標和模型之間局部特征 的對應來使得匹配誤差最小。為了獲得最小值，人們使用了很多方法，諸如廣義， h o u g h 變換、動態(tài)繪劃，神經(jīng)網(wǎng)絡、變形模板、遺傳算法、以及解析方法等。 2 2 形狀表示 形狀表示方法分為兩類，一類是編碼方式，一類是對輪廓的簡化表示形式。簡 化輪廓就是提取一些重要的有意義的關鍵點。當今兩大最流行的曲線近似方法是 多邊形近似和樣條近似，另外基于多尺度的特征點提取在最近二十年中得到了密 切的關注和研究。 2 2 1 鏈碼 鏈碼是一種非常常見的形狀表示方式，它不能簡化形狀，但是能有效的表示形 狀用鏈碼表示形狀是f r e e m a n l 2 6 1 在1 9 6 1 年引入的，并且推廣了原來的定義獲得了 廣義鏈碼，利用鏈碼來抽取關鍵點從而生成一種相對于平移、旋轉(zhuǎn)、尺度不變的 旋轉(zhuǎn)表示方法，他還總結(jié)了鏈碼的各種方法與算法吲鏈碼在第二代圖像編碼中 獲得了廣泛的應用r o s e n f e i d 【”l 也提出了一系列關于鏈碼的算法人們利用鏈碼來 計算各種不同形狀特征，輪廓平滑和相關也因此變得簡單了，f i s c h l e r i ”l 用它來檢 測關鍵點，m c k e e | 3 0 1 甚至利用鏈碼來識別目標 2 2 2 樣條 樣條曾經(jīng)在函數(shù)插值和曲線近似方面是非常流行的i k e b e 和m i y a m o t o 在文獻 1 3 1 1 中詳盡的描述了樣條在形狀設計、表示和恢復上的應用樣條有最小化曲率的優(yōu) 點，也就是用最小平均曲率的曲線近似給定的函數(shù)曲線樣條函數(shù)在插值問題上 的缺點是局部函數(shù)值的修改會影響整個樣條表示b 樣條的提出就是為了不將局部 函數(shù)值的改變傳播到其它間隔中去它也可以用作由參數(shù)方程確定的平面曲線間 的插值，這樣每一條參數(shù)方程都可以獨立插值 基于多項式的形狀簡化方法也得到了廣泛的應用，很多工作使用隱多項式來 表示形狀，然后用代數(shù)或幾何不變量來識別形狀開始時隱多項式被用來描述三 維光滑曲面的仿射不變量g t a u b i n 開創(chuàng)性的概括了關于如何利用隱多項式提取 第二章形狀膩配技術 9 形狀特征的關鍵技術髑當這熱特征值和男一條曲線的特征值相匹醚對，就確定 了一今“內(nèi)蘊參考羧兩條馥線酚多矮式系數(shù)胃在這令參考鯪下魄較文獻l 蠲舞 出了基于二次因予的新的因式分解的方法，從而解決了曲線之間的關鍵點對應問 題d a n i e lk e r c n 等人剛提出了商次隱多項斌的概念。增強了隱多項式描述復雜形 獲熬戇秀。囂麥歪交多瑗式不纛提珙孚移、旋轉(zhuǎn)、足度零燮量，襞以x u 等大潮 提出了廣義正交多項式，獲得了相似變換不變量 捅值既可以簡化形狀，也可以增加形狀的邊緣點數(shù)，從而達到調(diào)熬數(shù)據(jù)的目的 插德般可以分成如下凡大類：纂于f f t 麴輻值、最近鄰捶值、樣條攢值、線性 插德鐐 2 2 3 多邊形逼近 多邊形逼近怒用多邊形線段來近似形狀邊緣，即：是以鬣小誤差、鬣小多邊形 周長、最小多邊形內(nèi)部面積，或最小多邊形外部面積作為j 駐似準則這熄誤差度量 中最常用靜是最大誤差和平方積分誤差。邀類方法中最鬻用的是分裂翔合_ 莠法 在這個方法中，魏線分裂由凡個線段來表承藏剄誤差這瓣w 淤接受。弱時分裂酶 線段又有可能融合，如果融合麟的線段同原始曲線的誤麓在允許的最火誤差范圍 內(nèi)，線段即融合，p a v l i d i s l 3 4 1 使用平方和誤差函數(shù)的偏導數(shù)來引導牛頓法搜索最佳 藪患w 拄幫l e o u 撼懣了勇一秘零囂豹準鄹來獲取多逮形邋遙，魏褻嬡麓豹多透形 逼近準則是最大內(nèi)部面積、最小外部面積、最小面積偏藏b e n g t s s o n 帶1 e k l u n d h l 3 5 l 提出了一種層次化的多邊形逼j 廈方法分裂含并方法經(jīng)常用于多邊形邋近，尺度 空間豹方法 3 6 i 囂| j 囂常用于跟蹤熬線上的特縫點不夔尺瘦交詫茲特征才是穩(wěn)定的 形狀特征w i t h k i n 使用多項式邋 跬來信計邊緣點上的留線方自，蓯兩象成了瞎線 的多尺度表示c h u n g 7 l 等人開發(fā)了一種基予h o p f i e l d 神綴網(wǎng)絡的形狀多邊形逼近 方法，這種方法怒將多邊形逼邋定義為對神經(jīng)網(wǎng)絡能量函數(shù)的最小化閩題，就是 最小純鏊線窩多逑形翡器與弦之蠲熬穰差。 2 2 4 基于尺度綴間特征點提取技術 繁予尺度空闖豹特征熹提取方法是一種流行靜形狀 鴦純方法最常爝的尺度 空間主要有：高斯尺度空間、小波尺度空間、形態(tài)尺度空間 w i t k i n l 3 6 j 提出的基于g u a s s i a n 尺度空間襲示突出目標特征的方法，通過跟蹤不 磊尺波下特征熹豹位萋瑟給毫形狀熬麓純形式，菝然存在予籬豫表承彩式孛魏特 征點被認為是目標顯著的特征b a b a u d 3 8 l 等人1 t 正n ) t g a u s s i a n 核是唯一的線性核 具有非常良好的保留本征特征點的特性，當尺度增加時，即濾波器帶寬增加時， 1 0 平不變的小波變換及其在仿射不變目標識別中的應用 那些本征特征點依然存在g a u s s i a n 濾波器是唯一具有這一特性的濾波器a s a d a d l b r a d y l 3 9 l 基于m a r r 提出的想法提出了一種稱為曲率指紋圖的新方法，輪廓經(jīng)過 不同帶寬的g a u s s i a n 濾波器濾波從而獲得形狀邊緣的多尺度表示，然后在不同尺 度計算曲率并且獲得曲率指紋圖m o k h t a r i a n 和m a c k w o r t h i ”i 將尺度空間的方法應 用到形狀描述子中，沿著形狀的輪廓，用不同帶寬的g a u s s i a n 核來平滑輪廓，然后 計算曲率曲率函數(shù)在尺度空間中的圖像被用作形狀多層描述子，它具有平移、旋 轉(zhuǎn)、尺度不變性 多尺度的概念在形態(tài)學中也提出過基于形態(tài)學的形狀簡化方法主要分為兩 大類，一類是形態(tài)分解，另一類是形態(tài)細化c h e n g 和y a n l 4 1 l 使用可變尺寸的結(jié)構(gòu) 基元對圖像進行各種形態(tài)操作a n e l l i l 4 2 喀人運用了遺傳算法，并且試圖解決結(jié)構(gòu) 基元的選擇問題l a g a n i e r e l 4 3 i 則成功使用形態(tài)分解提取了角點m o i s a n l 4 4 j 提出的 仿射形態(tài)尺度空間，并且用仿射腐蝕來簡化形狀r e i n h a r d t l 4 5 1 等人比較了形態(tài)分 解和形態(tài)細化之間的差別相對于四種不同的代價函數(shù)，形態(tài)分解的效率比形態(tài) 細化的效率高四倍 基于小波尺度空間的形狀簡化方法和高斯尺度空間的原理一樣，對曲線進行 不同尺度的濾波不同之處在于小波尺度空間不是線性尺度空間，因此它無法保 證因果性，所以經(jīng)常會出現(xiàn)奇異的角點，因而得不到廣泛的應用 2 3 基于全局特征的形狀匹配方法 在幾何學和拓撲理論中，給出了很多關于各種變換的結(jié)果，據(jù)此人們提出了許 多處理各種變換的不變量。 2 3 1 基于全局性的幾何特征 在經(jīng)典的幾何理論中面積、周長、長軸、短軸、主軸方向、凹凸面積、緊密 度、實心度、偏心率這些特征得到了廣泛的應用m 在此簡單介紹緊密度、實心度、 偏心率緊密度是在一定程度上描述區(qū)域緊湊型的全局性形狀測度，當形狀為圓 時，緊密度為最小值1 它是一個旋轉(zhuǎn)、尺度、平移不變量，又是一個非矢量的數(shù)值 區(qū)域形狀的偏心率定義為它的主軸和次軸的比，它區(qū)分不同寬度目標的能力比較 強，長而窄的物體和短而寬的物體偏心率差別很大當形狀有一個或多個明顯的 凸凹時，實心度就是一個非常有用的特征，可以刻劃一個區(qū)域的凸凹性任意集合 o 的凸殼h 就是包含集合o 的最小凸包實心度定義為在h 同時也在集合。中 像素的數(shù)目的比例實心的目標和空心的目標在實心率上差別很大 第二章形狀聰配技術 1 1 2 。3 。2 基于變換域特征 人們喜歡將信號轉(zhuǎn)換到變換域，分解成對于不同的頻率或基來分析特征。作為 最經(jīng)輿的變換方法，各種不同的矩和f o u r i e r 撼繪子，小波描繪子、形狀描繪子在 過去鶼二年孛褥翻7 廣泛靜磷究。 2 3 2 1 矩 鬻像靜矩函數(shù)程模式識嗣、霹標分類中褥捌了廣泛靜成簇h u 釋q 纛1 9 6 1 年蘺 先戇予代數(shù)不變嫩引入矩不變照通過對幾何矩的非線性組合，導出了一組對于 圖像平移、旋轉(zhuǎn)、尺度變化不變的矩，但是這種矩不能恢笈圖像t e g l l e 郴堪于正交 多瑗茂攆密臻歪交楚來恢復形羧，勞曼雩l 入z e r n i k e 矩，纛鬟霉戮構(gòu)建經(jīng)意毒除耱 獨囊的矩不變量柱文獻陽i 中旋轉(zhuǎn)矩保證了商階矩的幅度不隨著階數(shù)的增加而明顯 降低。從而把矩的定義擴展到了任意階復數(shù)矩是一種虢得矩不變量的簡單而又 壹接瓣方法。矩方法懿優(yōu)點繇：它是一耱筒絳豹數(shù)學表承；缺點是要建立起贏除矩 和形狀特征間的聯(lián)系是困難的，。笳外它不能稔測形狀的弱部特征 2 3 2 2f o u r i e r 描繪予 f o u r i e r 描繪予( f d ) 是經(jīng)典的形狀描述方法早在文獻1 5 0 l 中就已給出f o u r i e r 描 繪予的詳細定義，后來p e r s o o n l 5 1 j 作了改進該方法先用角累加函數(shù)表示形狀邊界， 然黲辯角累熱露數(shù)進行f o u r i e r 交換，賜褥到戇系數(shù)來接述澎狀，藏是f o u r i e r 描述子。 在一定條彳牛下，寶藏有位移、旋轉(zhuǎn)、大小、越點等不變健菔用f d 可以對2 - d 益線 進行編碼、重建、或者分類它的主要優(yōu)點熄易于實現(xiàn)，并且建立在f o u r i e r 分析的 成熟理論之上：缺點是f o u r i e r 變換不提供局部形狀信息，角累加函數(shù)的表示對噪 聲援敏感。 2 3 2 3 小波描繪子 在穰多計算稅筏覺應用巾，為了改善嘏確率和提態(tài)辯噪聲的魯棒瞧經(jīng)常采用 多分辨率分析方法形狀的小波表示方式在粗尺度給出形狀的全局信息，在細尺 度上給出局部信慰由于小波變換提供了多分辨率表示，因此匹配或識別可以根 據(jù)輸入藩像或者瓣轢秀靈活調(diào)整。小渡交換戇最大蔌煮簸楚依贛于囂振莛線懿起 始點也就是說，岡一目標的兩條不同采樣曲線的小波襲示可能因為起始點的不 同而有很大差異在模式識別臌用中，盡管超始點可能會引起嚴重的問題，但是在 1 2 平不變的小波變換及其在仿射不變目標識別中的應用 任何文獻中都沒有完全闡述過這個問題c h u a n g 和k u 0 1 5 2 】假定輸入圖像已經(jīng)經(jīng)過 校正，l i 矛 1 k u o l 5 3 l 通過簡單的最小化曲線幅值函數(shù)的質(zhì)心來獲得起始點ti e n g 和 b o l e s 5 4 】使用小波系數(shù)的零交叉點來匹配模型和未知目標他們使用冗余小波變換， 即非十進小波變換來克服對起始點的依賴由于非十進小波表示方法需要的計算 量很大，系數(shù)的數(shù)目也非常大，所以用非十進小波進行形狀匹配非常慢在文獻【5 5 】 中將形狀先轉(zhuǎn)換到極坐標中，作f o u r i e r 變換抽取f o u r i e r 系數(shù)，然后對f o u r i e r 系數(shù)的 幅值抽取小波系數(shù)作為特征用于分類文獻【5 6 l 介紹了一種判斷起始點的方法，從 而保證了小波變換不受起點約束章毓晉教授等人【57 l 研究了小波描繪子在圖像查 詢中的應用 2 4 基于局部特征的形狀匹配方法 上一節(jié)主要介紹了基于全局特征進行匹配的方法，但是如果形狀發(fā)生形變或者 受到遮掩，那么全局特征就變得不可靠了。為了處理更加廣泛的形變問題和遮掩 問題，學者們提出了很多基于形狀局部特征的形狀匹配算法。這類方法主要是通 過搜索最優(yōu)點對應或者特征對應來判斷形狀是否匹配。它們的原始雛形就是廣義 h o u g h 變換，而傳統(tǒng)的動態(tài)規(guī)劃等優(yōu)化算法得到了廣泛的應用，現(xiàn)代優(yōu)化算法如 神經(jīng)網(wǎng)絡、遺傳算法的應用，使得許多有遮擋問題和變形問題得到了解決。當今 解決形變問題最流行的方法是變形模板。實際上形狀也可看作一維隨機信號，所 以在語音識別中取得成功的許多算法也被廣泛地應用到了形狀匹配中，如動態(tài)時 間規(guī)整、隱m a r k o v 模型、自回歸模型等。形狀的凹凸結(jié)構(gòu)也是決定形狀的視覺特 征，也受到了廣泛的關注。 2 4 1 廣義h o u g h 變換 h o u g h 首先提出了稱為h o u g h 變換的區(qū)域外形邊界變換的形狀描述方法h o t i g h 變換的目標是尋找種從區(qū)域邊界( 空間域) 到參數(shù)空間的變換，用大多數(shù)邊界點所 滿足的對應參數(shù)來描述這個區(qū)域的邊界文獻1 5 8 】提出了對于任意形狀曲線的廣義 h o u g h 變換( g h t ) 方法，并推廣了這一結(jié)果，經(jīng)典的廣義h o u i g h 變換是抽取曲線和 對曲線建模的傳統(tǒng)方法因為這類方法是基于投票數(shù)的累積，所以它們相對于噪 聲和遮掩不敏感實際上，如果噪聲是加性噪聲，如高斯白噪聲，廣義h o u g h 變換 可以通過模板匹配來實現(xiàn)，根據(jù)檢測誤差而言模板匹配是最優(yōu)的在復雜場景且 外點很多的情況下，這些方法對尺度變化處理得不太好g h t 只考慮全局匹配函數(shù)， 動態(tài)規(guī)劃則被廣泛地用于尋找點對應 第二章形狀匹配技術 2 4 2 基于自回歸模型和隱m a r k o v 模型 兩維的形狀可以用一維的實數(shù)或復數(shù)函數(shù)表示，把這個函數(shù)看成一個隨機過 程實現(xiàn)，通過估計得到的模型參數(shù)就可以作為形狀描述予 用自回歸模型1 5 9 1 分析閉合形狀是勛s i l y a p 和c h e l l a p p a 在1 9 8 1 年首先提出來的， 他們用自回歸系數(shù)作特征矢量來刻劃形狀在d u b o i s 和g l a n z 6 0 l 的實驗中得到了很 好的結(jié)果，在質(zhì)心與輪廓之間以等角間距采樣得到徑向量的長度序列，然后對此 序列應用a r 模型k a r t i k e y a n 6 1 增人認為線性a r 模型只適用于識別那些形狀明顯 不同的圖形而對形狀差別較小的圖形識別能力較差，為此構(gòu)造了非因果二次 v o l t e r r a 模型但是這種模型的計算量很大，模型階數(shù)不易選擇，從而使特征集的 形式很難統(tǒng)一并增大了模式分類的難度d a s l 6 2 1 等人采用了二維雙變量a r 模型，這 種方法要估計的模型系數(shù)是相應同階次一維模型的四倍。冗余性大另外，此模型 只是簡單地將直角坐標x ，y 作為雙變量來處理，忽視了它們之間的正交特性，導致 模型系數(shù)并不直接具備旋轉(zhuǎn)不變性為了克服雙變量a r 模型的固有缺點，s e k i t a l 6 3 1 等人提出了復數(shù)域a r ( c a r ) 模型。實驗研究表明識別效果優(yōu)于不變矩和傅立葉描 述符方法，尤其在有噪聲的情況下但是由于該模型是線性的，它不能反映圖形輪 廓的二維非線性封閉循環(huán)特性和局部特性，所以在識別某些相似圖形時效果不好 自回歸模型的主要缺點就是它只使用一個預測參數(shù)集來描述整個形狀，如果 形狀中有很多角點或者形狀變化非常劇烈，那么這個形狀就變得難以預測為 此，h e 和k u n d u i “l(fā) 把a r 模型和隱m a r k o v 模型結(jié)合起來用于形狀分析，把形狀邊界 分成若干段，每一段用a r 模型描述，所得到的向量再用隱m a r k o v 模型分析 第三章小波變換的基本理論 第三章小波變換的基本理論 小波理論 6 5 1 是- - f l 發(fā)展相當迅速的新興學科，一開始就引起了眾多數(shù)學家和 工程界人士的高度重視。經(jīng)過十多年的發(fā)展，其數(shù)學理論已基本成熟。本章介紹 了連續(xù)小波變換、二進小波變換、離散小波變換的基本概念、基本思想和基本結(jié) 論，并給出了它與多分辨分析、濾波器組之間聯(lián)系，給出了m a l l a t 分解與重構(gòu)算 法，同時介紹了平移不變的小波變換。 3 1 1 連續(xù)小波交換 3 1 小波變換 經(jīng)典的傅立葉變換在信號的分析與處理中發(fā)揮了重要的作用。但是，傅立葉 變換對信號的表示不能反映出隨時間變化的頻率；此外，為了從模擬信號，( f ) 中 提取譜信息，( ) ，需要取無限時間量，反之亦然。因此，傅立葉變換不能滿足大 多數(shù)的應用。 在實際應用中，人們需要確定時間間隔，使在任何希望的頻率范圍( 或頻帶) 上獲得頻譜信息。由于信號的頻率與它的周期成反比，因此對于高頻信息，時間 間隔變小，從而給出較好的精度；對于低頻信息，時間間隔變大，從而給出完全 的信息，也就是需要一個可變的時間頻率窗，似的在高中心頻率的時間窗自 動變窄，而在低中心頻率的時間窗自動變寬。小波變換具有這種類似調(diào)焦距的伸 縮功能。 定義1 1 ：設函數(shù)t p e l 2 僻) n r 俾) ，并且妒( 0 ) 一o ，由妒經(jīng)伸縮和平移得到一 族函數(shù) 咖南妒( 等) ( a , b e r ；a , 0 ， ( 3 _ 1 ) 稱緲。 為分析小波或連續(xù)小波，稱妒為基本小波或母小波。其中，口為伸縮因子， b 為平移因子。 由條件妒( 0 ) 一?？芍琷 三：o ) 出一0 。 1 6 平移不變的小波變換及其在仿射不變目標識別中的應用 定義1 2 ：設妒為基本小波，伽。 是由式( 3 - 1 ) 定義的連續(xù)小波，對于信號 廠e l 2 俾) ，其積分小波變換( 連續(xù)小波變換) 定義為 眠腆，6 ) l ( 助。，) l k | - ”2 j i 腳。( 學卜 2 ) 其中，妒o ) 表示l p ( t ) 的復共軛。 定義1 3 ：設* pe l 2 僻) n 工l 僻) ，且滿足條件 巳。正掣舨m 則妒稱為允許小波，條件式( 3 3 ) 稱為允許條件。 定理1 1 ：設妒為允許小波，對任意的f ，g l 2 ( r ) ，有 ( 3 3 ) j ! ：粥廠，b x w , 占) q ，6 ) 窘動一巳( ，g ) ( 3 - 4 ) 此外，如果，在工尺連續(xù)，則 m 。善觚觸州一；妒草) 爭 。6 ， 3 1 2