形狀描述符抽取方法
2023-04-24 11:47:46 1
專利名稱：形狀描述符抽取方法
技術領域：
本發明涉及形狀描述符抽取方法，更具體地說，涉及基於圖像輪廓的形狀描述符抽取方法。
背景技術：
形狀描述符以使能自動抽取的低提取水平描述為基準，並且是人能夠從圖像中感知的基本描述符。正在研究描述一幅圖像內的特定對象的形狀以及基於該形狀估量匹配或相似性程度的算法。但是，這些算法僅描述特定對象的形狀，所以在感知一般對象的形狀方面存在很多問題。目前，為了解決上述問題，由比如MPEG-7的標準組建議的形狀描述符是通過查找給定對象的各種變形的特徵來獲得的。現有許多種類的形狀描述符。在MPEG-7的實驗模型(eXperimental Model，XM)1中採納的兩種形狀描述符，公知的為澤尼克(Zernike)動量(moment)形狀描述符和曲率尺度空間形狀描述符。對於澤尼克動量形狀描述符，定義關於多種形狀的澤尼克基函數，以勘察一幅圖像內的對象。然後，固定尺寸的圖像投影在基函數之上，並將產生的結果用作形狀描述符。對於曲率尺度空間描述符，抽取模型圖像的外形，並以尺度空間表示沿著外形曲率點的變化。然後，將峰值的位置用z維向量表示。但是，抽取前者的一描述符時，輸入圖像的尺寸受到限制。而且，抽取後一形狀描述符時，所抽取的形狀只能是一個對象。
發明內容
為了解決上述問題，本發明的一個目的是提供一種形狀描述符抽取方法，能夠有效地應用到活動視頻壓縮技術和基於該活動視頻壓縮技術的圖像搜索技術。
本發明的另一個目的是提供一種圖像搜索方法，使用通過形狀描述符抽取方法抽取的形狀描述符，在索引的圖像內搜索與查詢圖像相似的圖像。
本發明的另一個目的是提供一種相異性估量方法，使用通過形狀描述符抽取方法抽取的形狀描述符，估量將要索引的圖像間的相異性。
從而，為了實現上述目的，根據本發明的一個方面，提供一種形狀描述符抽取方法，包括(a)通過抽取圖像的輪廓確定基於抽取的輪廓的形狀描述符。
另外，為了實現上述目的，根據本發明的另一方面，提供一種形狀描述符抽取方法，包括(a)從輸入的圖像中抽取輪廓；(b)通過基於抽取的輪廓執行像素間的連線獲得一直線列表；以及(c)將通過規格化直線列表獲得的規則的直線列表確定為形狀描述符。
另外，步驟(a)最好包括(a-1)通過對輸入的圖像執行距離變換獲取一距離映射；以及(a-2)從獲得的距離映射中抽取輪廓。
另外，步驟(b)最好包括(b-1)稀疏(thin)抽取的輪廓；以及(b-2)通過連接稀疏的輪廓中的每一個像素抽取直線。
另外，步驟(c)最好包括(c-1)得出所連接的開始和終止點的列表；(c-2)通過徑直組合抽取的直線獲取第一直線列表；以及(c-3)確定通過基於每一條直線的端點間的最大距離規格化第一直線列表所獲得的第二直線列表。
另外，距離變換最好基於表示對象內側的每一點作為離開背景的最小距離值的函數。
另外，步驟(a-2)最好包括使用邊緣檢測方法獲取到距離映射的局部最大值。
另外，步驟(a-2)最好包括(a-2-1)使用局部最大值執行卷積檢測四個方向的掩碼(mask)以獲取局部最大值。
另外，在步驟(a-2-1)之後，最好進一步包括(a-2-2)將相應於具有最大尺寸的方向的卷標記錄在方向映射和幅度映射中。
另外，最好輸入圖像為二進位圖像。
另外，最好步驟(b-1)進一步包括留下在把相應的方向旋轉90度後的方向中的最大的像素，並移去餘下的像素。
另外，最好步驟(c-2)進一步包括使用具有四個方向的方向映射，通過連接方向映射中具有同一卷標的像素，得出每一條線段的開始和終止點的列表。
另外，最好步驟(c-2)進一步包括通過改變獲得的第一直線列表中的各直線間的角度、距離以及直線的長度的閾值，執行直線組合。
另外，最好一直重複直線組合，直到剩餘的直線數量等於或少於預定值為止。
同樣，為了實現上述目的，根據本發明，提供一種圖像搜索方法，包括(a)從查詢圖像的形狀描述符中獲取直線列表；(b)通過比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，獲取相異性。
同樣，為了實現上述目的，提供一種相異性估量方法，其中使用基於輪廓形成的形狀描述符用於估量索引的圖像間的相異性的方法包括(a)從查詢圖像的形狀描述符中獲取直線列表；以及(b)比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，並獲取相異性。
通過參照附圖對優選實施例的詳細描述，本發明的上述目的和優點將變得更加清楚，其中圖1為說明根據本發明的優選實施例的抽取形狀描述符的主要步驟的流程圖；圖2a至2d為說明用於檢測局部最大值的掩碼的示例圖；圖3a為說明二進位圖像的示例圖；圖3b為說明與黑-白圖像成比例的距離映射的圖；圖3c為說明輪廓圖像的圖；圖3d為說明稀疏後的輪廓圖像的圖；圖3e為說明直線近似結果的圖；圖4為說明根據本發明的優選實施例的基於形狀描述符的圖像搜索方法的主要步驟的流程圖；和圖5和6為說明為了評價根據本發明的圖像搜索方法的性能、對用作MPEG-7標準的實驗模型(XM)版本的實驗圖像的二進位圖像嘗試實驗的結果的圖。
具體實施例方式
下面將參照附圖詳細描述本發明的優選實施例。
根據本發明，定義了使用輪廓的形狀描述符。通過從給定形狀中抽取作為人類視覺基礎的直線並簡化所抽取的直線，獲得基於輪廓的形狀描述符。特別地，根據所述形狀描述符抽取方法，可以通過抽取輪廓而不抽取邊緣來簡化該形狀描述符。
圖1為說明根據本發明的優選實施例的形狀描述符抽取方法的主要步驟的流程圖。參照圖1，在根據本發明的形狀描述符抽取方法中，首先，輸入一圖像(步驟102)，並且對輸入的圖像執行距離變換以獲取距離映射(步驟104)。獲取該距離映射所使用的距離變換採用表示對象內各點作為到背景的最短距離值的函數。接著，從該距離映射中抽取輪廓(步驟106)。距離映射中的局部最大值是輪廓的一點是公知的。獲取距離映射所使用的距離變換是基於將對象內各點表示作為到背景的最短距離值的函數的。在一個優選實施例中，通過該距離變換將距離映射中的局部最大值確定為輪廓。為了從距離映射中獲得局部最大值，在一個優選實施例中，可以採用在「線性特徵值抽取和描述(Linear Feature Extraction and Description)」(R.Nevatia and K.R.Babu，Computer Graphics and Image Processing，Vol.13，pp.257-269，1980)中使用的、在此作為參考引用的邊緣檢測方法。圖2a至2d說明用於檢測局部最大值的掩碼的示例。參照圖2a至2d，將用於檢測四個方向的局部最大值的掩碼用來檢測局部最大值。圖2a是相應於0度方向的掩碼。圖2b是相應於45度方向的掩碼。圖2c是相應於90度方向的掩碼。圖2d是相應於135度方向的掩碼。然後使用這些掩碼執行卷積。結果，將相應於具有最大尺寸的方向的卷標記錄在方向映射和幅度映射中。這樣，基於從圖3a所示的二進位圖像通過距離變換獲得的距離映射，獲得局部最大值，從而抽取輪廓。
接下來，稀疏抽取的輪廓(步驟108)。稀疏可以通過比如將方向映射中相應的方向旋轉90度後的方向上具有最大尺寸的像素留下，並移去餘下的像素來執行。圖3d示出稀疏後的輪廓圖像的示例。
然後，通過連接所稀疏的輪廓內的各個像素抽取直線(步驟110)。即，將所稀疏的輪廓內的各個像素沿著一個方向連接，並通過生成線段的開始和終止點的列表抽取直線。在優選實施例中，使用了圖2a至2d所示的四個方向的方向映射，並且將方向映射中具有相同值的像素連接，生成各個線段的開始和終止點的列表。
接著，通過所抽取的直線的直線組合，獲取直線列表(步驟112)。即，改變獲得的直線列表中各直線間的角度、距離以及長度的閾值，執行直線組合。直線組合一直重複，直到剩餘的直線數量等於或少於預定數量為止。圖3e示出直線近似的結果。將基於各直線的端點間的最大距離通過規格化直線列表獲得的直線列表確定為形狀描述符(步驟114)。即，根據本形狀描述符抽取方法，抽取二進位圖像的輪廓，並將所抽取的輪廓用作形狀描述符。
根據本形狀描述符抽取方法，抽取二進位圖像的輪廓作為形狀描述符，並且所抽取的形狀描述符可以用於圖像組合。另外，在本形狀描述符抽取方法中，從二進位圖像中抽取輪廓，並將所抽取的輪廓近似為直線。此外，為了有效地抽取直線，將二進位圖像進行距離變換，並獲得局部最大值以抽取輪廓。使用邊緣抽取方法將抽取的輪廓近似為特定數量的直線。將近似的直線數量限制到特定數量，以便能夠執行更快速匹配。
下面描述從存儲通過形狀描述符抽取方法索引的圖像的資料庫中、搜索與查詢圖像相似的圖像的方法。將通過評價在包括使用參照圖1所描述的形狀描述符抽取方法抽取的形狀描述符進行索引的圖像的圖像資料庫之內、搜索與查詢圖像相似的圖像的性能，描述形狀描述符抽取方法的效果。
圖4為說明根據本發明的圖像搜索方法的主要步驟的流程圖。首先，從所查詢的圖像的形狀描述符中獲取直線列表(步驟402)。接著，通過比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，獲取相異性(步驟404)。
在優選實施例中，估量形成輪廓的直線的端點間的距離，並將估量的距離的最小值的和確定為相異性的值。在一個相異性的特定函數中，N、D1k和D2k分別為N＝min{NQ，NM}…………(1)D1k=ijmin{||QSi-MSj||+||QEi-MEj||}.....(2)]]>D2k=ijmin{||QSi-MEj||+||QEi-MSj||}.....(3)]]>D=k=0N-1min{D1k,D2k}........(4)]]>這裡，Q表示將被檢測的直線，M表示檢測到的直線，S表示每一條直線的開始點，E表示每一條直線的終止點，NQ為查詢圖像的形狀描述符所具有的直線總數量，NM為檢測到的圖像的形狀描述符所具有的直線總數量。
參照公式4，通過公式2和3估量的直線間的距離的最小值的和被確定為兩個描述符的相異性。即，公式4的計算值越小，認為兩個對象越相似。另外，通過以旋轉角的有規律的間隔執行估量，可能獲得不隨旋轉變化的值。
現在，基於在步驟404中獲得的相異性，搜索具有與查詢的圖像相似的形狀特徵的圖像。在搜索的圖像中將與查詢的圖像比較具有最小相異性的圖像確定為最終搜索的圖像。基於相異性的搜索方法稱作匹配方法，並將最終搜索的圖像稱作相匹配的圖像。
為了評價該方法的性能，對用作MPEG-7標準的實驗模型(XM)版本的實驗圖像的二進位圖像執行嘗試實驗。直線組合的各種不同閾值是通過實現判定的。直線組合僅在30度的角度下執行，而作為組合的直線，兩條直線的終點間的距離判定為實際圖像的寬度和長度中較小一個的5％，並且在直線組合判定為寬度和長度中較大一個的1％後忽略直線的長度。另外，每次重複執行時閾值增加10％，直到直線的數量等於或小於10。實驗結果示於圖5和6中。參照圖5，當從根本沒有分類的圖像中搜索具有與查詢圖像相類似形狀的圖像時，根據本發明的圖像搜索方法表現不出優越的搜索性能。這是因為在進行直線近似處理的過程中部分詳細信息丟失了。另外，參照圖6，當從相同種類的數據集合中搜索與查詢圖像具有相似形狀的分類圖像時，本圖像搜索方法表現出相當好的搜索性能。因此，形狀描述符抽取方法對於從相同種類的數據中抽取局部運動具有優越性。該方法對於抽取同類對象的局部運動具有優越性的原因在於，通過本發明的形狀描述符抽取方法抽取的形狀描述符具有有關於包括在圖像中的形狀的輪廓特徵的信息。
在上述優選實施例中，針對通過參照圖1描述的形狀描述符抽取方法索引的圖像，描述了搜索具有與查詢圖像相似形狀的圖像的方法。但是，在該圖像搜索方法中，估量查詢圖像和搜索到的圖像之間的相異性的步驟，也可以基於估量的相異性應用於將具有相似形狀的圖像分組。
也可以將該形狀描述符抽取方法應用於基於標準的活動圖像壓縮技術，比如基於對象的壓縮技術MPEG-4、MPEG-7和MPEG-21。另外，也可將其有效地應用於基於運動視頻壓縮技術的圖像搜索技術。
此外，可以將根據本發明的形狀描述符抽取方法和圖像搜索方法寫成在個人計算機或伺服器上運行的程序。本領域的電腦程式員可以容易地得出構成該程序的程序代碼和代碼段。另外，可以將該程序存儲在計算機可讀的記錄介質中。記錄介質可以為磁記錄介質、光記錄介質或無線介質。
由於根據本發明的形狀描述符抽取方法抽取的形狀描述符具有有關包括在圖像中的形狀的輪廓特徵的信息，所以能夠有效地從相同種類的數據集合中抽取局部運動。此外，當從分類的圖像中搜索與查詢圖像具有相似形狀的圖像時，本圖像搜索方法在通過形狀描述符抽取方法索引的圖像資料庫之內搜索具有與查詢圖像相似形狀的圖像，表現出相當好的搜索性能。
權利要求
1.一種圖像搜索方法，其中搜索具有與查詢圖像相似形狀的圖像的方法包括(a)從查詢圖像的形狀描述符中獲取直線列表；(b)通過比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，獲取相異性；以及(c)基於獲取的相異性檢測與查詢圖像具有相似形狀的圖像。
2.如權利要求1所述的方法，其中步驟(b)包括(b-1)估量形成輪廓的直線的端點間的距離；以及(b-2)將估量的距離的最小值的和確定為相異性的值。
3.如權利要求1所述的方法，其中步驟(b-1)包括當Q為要檢測的直線、M為檢測到的直線、S為任一條直線的開始點、E為任一條直線的終止點、NQ為查詢圖像的形狀描述符所具有的直線總數量、NM為檢測到的圖像的形狀描述符所具有的直線總數量、和N＝min{NQ，NM}時，根據D1k=ijmin{||QSi-MSj||+||QEi-MEj||}]]>和D2k=ijmin{||QSi-MEj||+||QEi-MSj||}]]>計算形成輪廓的直線的端點間的距離；以及步驟(b-2)包括使用按D=k=0N-1min{D1k,D2k}]]>定義的相異性特定函數估量相異性。
4.如權利要求3所述的方法，其中以旋轉角的有規律的間隔根據步驟(b-1)和(b-2)執行相似性估量以獲得不隨旋轉變化的值。
5.一種相異性估量方法，其中使用基於輪廓形成的形狀描述符用於估量索引的圖像間的相異性的方法包括(a)從查詢圖像的形狀描述符中獲取直線列表；以及(b)比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，並獲取相異性。
全文摘要
提供一種圖像搜索方法，其中搜索具有與查詢圖像相似形狀的圖像的方法包括(a)從查詢圖像的形狀描述符中獲取直線列表；(b)通過比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，獲取相異性；以及(c)基於獲取的相異性檢測與查詢圖像具有相似形狀的圖像。還提供一種相異性估量方法，其中使用基於輪廓形成的形狀描述符用於估量索引的圖像間的相異性的方法包括(a)從查詢圖像的形狀描述符中獲取直線列表；以及(b)比較檢測的圖像的形狀描述符的直線列表和查詢的圖像的形狀描述符的直線列表，並獲取相異性。
文檔編號G06T1/00GK1516077SQ20031011809
公開日2004年7月28日 申請日期2001年4月27日 優先權日2000年10月21日
發明者崔良林, 李宗河 申請人:三星電子株式會社