分段匹配中的優先順序劃分的製作方法

2023-09-23 07:19:05 7

專利名稱：分段匹配中的優先順序劃分的製作方法
技術領域：
本發明有關一種方法，該方法符合權利要求1中的介紹部分。
背景技術：
兩個或多個圖像的匹配被用於圖像處理，其中包含確定連續圖像中的匹配部分。在圖像處理的若干領域(例如深度再現，圖像數據壓縮和運動分析)中，圖像匹配都是一個基本步驟。
匹配過程包括確定第一圖像的一個第一位置中的圖像特徵，並確定第二幅圖像中這些圖像特徵的位置。第一和第二圖像中圖像特徵間位置上的差異信息，例如平移或旋轉，可被用在以後的處理中。例如，兩個連續圖像間一個圖像特徵的平移可被用於獲得與該圖象特徵相關的一個物體的速度量值。
可以利用上下文無關處理來執行圖像匹配，在通用圖像處理硬體或軟體中實現，供MPEG(譯)編碼和電視掃描速率轉換使用。在這些應用中，匹配一個視頻流的連續數字圖像。這些處理過程中通用的方法如下需要匹配的是來自一個視頻流的兩個連續圖像；令這些圖像是2維數字圖像I1(x，y)和I2(x，y)。這兩個圖像的匹配包括計算一對函數M＝Mx(x，y)和M＝My(x，y)，按下面公式理想地將一個圖像I1上的每一個像素映射到圖像I2中的一個像素。
I1(x，y)＝I2(x+Mx(x，y)，y+My(x，y))這些函數M包含有關於像素或特徵怎樣在兩個圖像之間移動的信息。例如，函數M可被解釋為視頻流中像素的明顯運動，並給出每個像素的一個運動矢量。這一運動矢量可被用在2維圖像的深度重現中，電視中掃描頻率上調的自然運動中，以及MPEG壓縮中(舉例來說)。因此，圖像匹配包括找出函數M。
將M定義為一個對於所有像素來說都是獨立的函數，會使尋找M的提法是不適當的。構造M是非常有問題的，如果可以確定一個函數M，會招致巨大的成本，包括時間上和計算上的花費。為簡化尋找M的問題，已提出了函數M的規範化。US 5 072 293中提出一種方法，其中，在圖像中的預定決上，函數M被設定為恆定值，它相對於圖像幀來說是固定的。這種方案簡化了搜索M的問題，並減少了搜索M的費用。這種方法的缺點是，計算仍然費時費錢，而對於某些應用來說，所得到的M的解不夠精確。

發明內容
本發明的一個目的是提供一種方法，該方法能夠更快更有效地匹配連續圖像的部分。
為達到這一目的，在權利要求1的特性部分中定義了上述類型的方法。
按本發明的第一方面，在對第一圖像分段之後(其中每個圖像的像素都被分配給相應的圖段)，為一個圖段的至少部分像素確定一個像素重要性參數的值。該像素重要性參數代表每個像素對於匹配目的來說的相對重要性。匹配罰函數是基於該像素重要性參數的，其方法是，在估算罰函數時，為重要的像素分配較大的加權。
在一個實例中，像素重要參數是由一個像素相對於一個圖段的硬邊界部分的距離和可視度參數確定的。推薦只使用距一個相關邊界部分的距離。通過估算一個邊界部分對圖段所造成的圖段深度值，來確定該邊界部分的相關性。若該邊界部分與深度變化不一致，則很可能該邊界部分不體現匹配所需的重要信息。
另外，可見度函數處理的是第一圖像中的一個像素在第二圖像中是否有一個相對應的像素。該函數合併在罰函數中，將在隨後的圖像中模糊不清的像素移出處理過程。找出模糊不清的像素的方法是，確定第一和第二圖像的圖段深度值，根據該深度值確定哪些較高位置的圖段模糊了其它較低位置的圖段。
通過在匹配過程的罰函數中使用一個像素重要性參數，提高了匹配的精確度，並且減少了所需的計算資源。本發明還有關一個用於匹配數字圖像的設備。
在從屬權利要求中列出了本發明的有利之處。在以下的描述中，將會清楚本發明的進一步的目的，細節，改進和效果，在以下的描述中參照了以下附圖。


圖1概略描述了一個圖段匹配處理的例子，圖2概略顯示了一個用於匹配數字圖像的設備。
具體實施例方式
在以下的一個本發明實例中，將解釋兩個圖像的匹配。這些圖像可以是來自一個視頻流的連續圖像，但本發明並不局限於此。這些圖像是包含圖像像素的數字圖像，並被定義為兩個2維數字圖像I1(x，y)和I2(x，y)。其中x，y表明圖像中各獨立像素的坐標。
這兩個圖像的匹配包括計算一對函數M＝Mx(x，y)和M＝My(x，y)。M的定義和以前一樣，即，按下面公式將圖像I1中的每一個像素映射到圖像I2中的一個像素。
I1(x，y)＝I2(x+Mx(x，y)，y+My(x，y))按本發明，修改了M的構造方法，使得對於具有相似運動的像素組來說，函數M是恆定的，將M的以前定義修改為I1(x，y)＝I2(x+Mx(G(x，y))，y+My(G(x，y)))函數G的作用是，使M對於一組具有相似運動的像素來說保持恆定。函數G的引入是對匹配問題的一個規範化，這一修改能明顯減少尋找M所需的工作量。
M值恆定的一組像素是由具有類似運動的一些像素組成的。為找出這些像素組，通過分段機制將圖像劃分為圖段。一個圖像的分段等同於，為該圖像中的每個像素確定一個對有限的圖段集合之一的唯一的成員資格，其中的圖段是一個相關聯的像素組合。一個有利的分段方法是準分段，其中，根據一個像素的圖像相關屬性(例如顏色，亮度，紋理)確定該像素是否是一個圖段的成員，其中圖段邊界是由一個確定的值標記的。準分段得到的圖段不必直接與圖像物體對應，不過，某一圖段內的像素仍有很大的可能具有類似的運動。在共同未決題為「Segmentation of digital images」的專利申請中，描述了一種準分段方法，其中的內容在此引用以供參考。利用準分段方法，可以快速有效地對圖像分段。
利用前面提到的準分段方法，將圖像I1劃分為圖段，所得到的圖段包含以定義各圖段的邊界為邊界的像素。作為準分段的結果，圖段是由硬邊界部分和軟邊界部分定義的。硬邊界部分由圖像分析得出，很有可能是一個相關的圖段邊界。軟邊界部分是通過計算距所檢測到的硬邊界部分的距離確定的，因此，是一個相關的圖段邊界的可能性較小。一個邊界部分與圖像內容對應得越好，該邊界部分越相關。按本發明，表現形式為圖段匹配的圖像匹配是按優先次序進行的，即，根據相應圖段的期望信息內容，匹配具有較高重要性的像素。
在圖1中，顯示了圖像I1的一個圖段10，該圖段是通過準分段確定的，以硬邊界部分11(由一個實線表示)和一個軟邊界部分12(由一個虛線表示)為邊界。為確定圖像I1和I2間圖段10的位移函數，需要在圖像I2中找出與圖段10匹配的圖段10的投影，從而產生位移函數M。首先在圖像I2中挑選一些有可能與圖段10匹配的候選圖段，為每個候選圖段計算一個匹配準則，並挑選一個匹配結果最好的圖段。該匹配準則是第一圖像的圖段與第二圖像中的一個投影相匹配的確定性的一個量度。如以前所提到的，圖段的硬邊界部分與軟邊界部分相比，有更高的確定性因子。
在圖1中，與圖段10相匹配的圖像I2的候選圖段是圖像I2的投影20，30，40，分別以硬邊界21，31，41和軟邊界22，32，42為邊界。每一個投影20，30，40的函數M都由相應的箭頭M1，M2和M3表示。因此，M1，M2和M3可被認為是函數M的候選值。為確定哪一個候選投影20，30，40與圖段10最匹配，必須為每個投影20，30，40計算一個匹配準則。按照本發明，在估算候選投影和M的候選值時，匹配準則給圖段的某些像素更高的加權。對於在定義真實的物體邊界時意義重大的像素，分配更大的加權。
該匹配準則被用於數字圖像處理中，其實現方式是使一個匹配誤差或匹配罰函數最小。這種通過使一個匹配函數最小來進行匹配的函數和方法本身在本技術中是已知的，其例子見於De Haan和Biezen所著文章「Sub-pixel motion estimation with 3-Drecursive searchblock-matching」中，該文章發表於信號處理圖像通信6(1994年)229-239。
具有i個候選Mx和My的有限集合定義如下，其中Mx和My是x和y坐標上的函數M{(Mxj，Myj)|i＝1，2，3，...}有限候選集合Mx和My的挑選本身在本技術中是已知的，例如，從以上提到的De Haan和Biezen的文章中可以查到。候選集合最好保持很小，以減少估算每個候選所需的計算量。對於每個候選，都有一個候選投影與之相聯繫。
一個圖段中的像素集合被記為Ω。第i個候選的匹配處罰MPi被定義為MPi=(x,y)|I1(x,y)-I2(x+Mx,i,y+My,i)|---(1)]]>該匹配罰函數給一個圖段中的每個像素相等的加權。如以前所提到的，在匹配處理中，一個圖段中的像素並非具有相同的意義，有些像素代表實際的物體邊界，因此具有較高的重要性，而有些像素只與紋理有關，因此對於匹配來說不是重要的。一個圖段中各個像素的重要性可以是不一樣的，這是由它們相對於該圖段最近邊界的位置或距離，紋理和/或特性的數量，噪聲引起的。另外，可能出現閉塞，其中，一些圖段部分地遮住其它圖段，其結果是，一些像素在第一幅圖像中是可見的，而在隨後的圖像中是不可見的，反之亦然。在隨後的圖像中模糊的像素不應被用於匹配，因為對於這些像素來說，在隨後的圖像中沒有與之相匹配的像素，因此它們是不能匹配的。將無法匹配的像素考慮在內會增加匹配處理的計算量，並會導致不精確的結果。
因此，按本發明，提供了一種匹配處理，其中，考慮像素的重要性，並排除不可見的像素。
利用以上設計的工具，將各個像素的重要性考慮在內，匹配處罰函數被修訂為MPi=(x,y)PIM(x,y)|I1(x,y)-I2(x+Mx,i,y+My,i)|---(2)]]>加權函數PIM(x，y)是一個像素重要性函數，它為每個像素分配一個因子，該因子代表一個像素相對於所期望信息內容的重要性。在該例中，加權函數PIM(x，y)為PIM(x，y)＝w(x，y)v(x，y) (3)其中w(x，y)是一個加權函數，v(x，y)是一個可見度函數。一個像素的重要性由P IM(x，y)函數控制，在該實例中，該函數由可見度映像(即v(x，y))，加權函數和邊沿或邊界所屬關係(即w(x，y))確定。其結果是，不可見像素的重要性為零，並且其它的像素被分配一個重要性參數，該參數是根據該像素與該像素所屬邊界之間的距離確定的，其唯一的條件是該邊界被認為是相關的。
為將以上所描述的由一個圖段的深度值所表示的重要性差異考慮在內，加權函數w(x，y)定義為w(x，y)＝dist(x，y)own(x，y)因此，加權函數包含兩個因素函數dist(x，y)和own(x，y)。dist(x，y)對加權函數w(x，y)起作用，並由一個像素與一個邊界之間的距離確定，own(x，y)有關該邊界的重要性。
根據一個像素到一個邊界的距離，函數dist(x，y)為該像素分配一個加權函數，因此，具有高確定性的像素在估算罰函數時起的作用更大。在函數dist(x，y)中，使用了一個像素到該圖段的一個硬邊界部分的距離d(x，y)，因此，加權函數w(x，y)隨著到一個硬邊界部分的距離的增大而減小。這代表著這樣的假設，即，硬邊界段是圖像的最確定特性，並且，一個像素距離最近的硬邊界越遠，其重要性越低。對於dist(x，y)，可以選擇任何合適的函數，只要函數值隨著距離一個圖段邊界的距離的增大而減小就行。
以下顯示了一些函數，不過，所使用的函數可以不局限於這些函數1.dist(x，y)＝l/d(x，y)，2.dist(x，y)＝l/d(x，y)23.dist(x，y)＝1若d(x，y)＜1.5；dist(x，y)＝0若d(x，y)≥1.5；且4.dist(x，y)＝(5-d(x，y))/4若d(x，y)＜5；dist(x，y)＝0若d(x，y)≥5應指出，所有這些函數都使dist(x，y)的值隨著像素到一個硬邊界部分距離的增加而減小。在函數3的情況下，在一個預定距離內，函數值恆定，超過該距離，函數值為零，這也使函數值隨距離的增加而減小。函數3和4將計算限制在固定數量的最近像素上；這又進一步減小了所需的計算量。如果圖像的分段是利用推薦的準分段方法執行的，則在分段處理過程中，已經知道一個像素距離該像素所屬圖段的最近硬邊界部分的距離，其形式是一個距離陣列。這就顯著減小了匹配處理的計算量。
利用這樣一個距離參數，能很好地表示一個確定像素的顯著性。儘管硬邊界分段與一個實際物體邊界相關的概率很高，但還希望有其它的選擇方式，以獲得一個圖段內像素顯著性的更好的表示。特別的，並非所有的硬邊界分段對匹配的目的來說都是同等相關的。為選擇最相關的硬邊界分段，可以使用由一個硬邊界分界的相鄰圖段的深度值。在確定一個硬邊界時，很可能有兩種情況1.該硬邊界對應於一個紋理特性，其特點在於相鄰圖段具有同樣的深度值。這類硬邊界是與實際物體邊界相對應的邊界的可能性很小，對於匹配目的來說，不是非常相關的。因此，不應根據距離函數增加這些硬邊界部分的值。
2.該硬邊界與深度上的不連續相對應，其表現是，該硬邊界的兩邊深度值不等。這種硬邊界很有可能是與一個實際物體邊界相關的邊界，因此，對匹配來說是非常相關的。對於這些邊界來說，應保持以前所定義的距離函數。為此，所有權函數own(x，y)定義如下own(x，y)＝1，若像素(x，y)與類型2的邊界相關，own(x，y)＝0，若像素(x，y)與類型1的邊界相關。
對於以上所提到的估算來說，需要估算一個圖段的深度值。確定一個圖像中圖段深度值的方法本身在本技術中是已知的。在使用本發明時，可以使用任何合適的方法，以確定圖段的深度值。一般，這種方法比較連續的圖像並得出一個圖像的每個圖段的深度值。
這一加權函數w(x，y)只考慮與第二組硬邊界相對應的硬邊界部分的種子點，該第二組硬邊界表示深度的不連續性。在估算該函數時，對於每一個硬邊界，都要確定它是否屬於以上提到的類型1或2。類型1的邊界部分，即，不相關的紋理邊界，被分配一個低的或零距離值。類型2的邊界部分，即相關的物體邊界部分，被分配一個高的或最大的距離值。利用該加權函數w(x，y)，可以做到在匹配期間只考慮與一個相關硬邊界圖段相關的像素。
另外，如以前所述，在匹配估算時，必須將不可見的像素排除在外。為此，引入了一個可見度函數v(x，y)。若一個像素在下一圖像中是不可見的，則該可見度函數的值為零，若一個像素在下一圖像中是可見的，則該可見度函數的值為1。為確定可見度函數，必須考慮連續的圖像。可以用任何合適的方法實現該可見度函數。一般，確定可見度函數需要為連續圖像的圖段確定深度值，並根據該深度值確定哪些更高位置的圖段使其它較低位置的圖段模糊不清。由於圖段的深度值還用於確定上述的加權函數w(x，y)，因此在確定w(x，y)和v(x，y)的處理過程中可以共享所需的計算資源。因此，可以選出不可見像素，以使得在匹配計算中不使用這些像素。
如以上所描述的，不能在一個單獨的圖像的基礎上計算可見函數v(x，y)，因此，為了啟動本發明所介紹的估算過程，最好進行以下的進程。在第一次匹配迭代期間，為v(x，y)計算第一組深度值。這些計算出的深度值使得能夠按從最近到最遠的順序排列圖段。如以上所描述的，可以使用任何確定深度值的方法。
在使用過程中，本發明方法在第一迭代步驟中要求一個深度值的估算量，以使用公式3。為啟動該過程，必須估算初始深度值，可以使用任意合適的值。在估算初始深度值之後，在隨後的迭代中，可以使用以前計算出的深度值。依照本發明的方法是，按照公式(3)，在像素的基礎上計算加權函數PIM(x，y)，並隨後確定公式(2)所定義的罰函數。
在實例中可見，PIM(x，y)函數與一個像素到一個硬邊界部分的距離和可視度函數相關。不過，本發明並不局限於該實例；也可以使用其它為每個像素分配重要值的方法。在這種情況下，必須用每個像素的加權因子來填寫一個確定度陣列(x，y)，該陣列與前面提到的距離陣列相對應，該確定度陣列與相應的像素所屬的圖段相關。特別地，本發明可以只使用加權函數w(x，y)，不考慮可視度函數。儘管損失了一些效率，但減少了所需的計算量。
本發明還可被用於匹配一個單幅圖像中的圖像部分，例如用於模式或圖像識別。
本發明還有關一個電腦程式產品，當在計算機上運行時，該產品的電腦程式代碼部分執行本發明方法的步驟。本發明的電腦程式產品可被存儲在一個合適的信息載體上，例如一個硬碟、軟盤或CD-ROM上，或存儲在一個計算機的存儲部分中。
本發明還有關一個圖2中所顯示的設備100，該設備用於匹配數字圖像。設備100配有一個處理單元110，用於按上述方法匹配數字圖像。處理單元110可被設計為至少部分上可編程的設備，或被設計為用硬體來實現上述一個或多個算法。處理單元10與一個輸入部分120相連，通過輸入部分120來接收數字圖像並送入單元110。單元110還與一個輸出部分130相連，通過它可以輸出圖像間所找到的匹配。
設備100可被插入一個顯示設備中，例如一個電視中，特別是一個用於顯示3-D圖像或視頻的三維(3-D)電視中。設備100還可被包含在一個解碼裝置的運動估算器中。另一個有利的應用是3-D瀏覽器。
應指出，上面提到的實例只起舉例說明的作用，並不限定本發明，本技術專業人員可以不脫離附加權利要求範圍，設計出許多不同的實例。在權利要求中，括號內的任何參考符號並不限制本發明。「包含」一詞並不排除出現權利要求所列出的元件或步驟之外的元件或步驟。本發明可通過包含若干分立元件的硬體實現，並可通過一個適當編程的計算機實現。在一個列舉了若干元件的設備聲明中，這些元件中的若干個可由同一個硬體實現。有些方法是在互相不同的非獨立權利要求中聲明的，這並不意味著不能使用這些方法的組合。
權利要求
1.一種用於匹配數字圖像的方法，該方法包括規格化一個第一數字圖像(I1)的圖像特性，該數字圖像由像素構成，提供一個第二數字圖像(I2)，由像素構成，定義一個有限的候選值集合(Mx，i，My，i)，其中，一個候選值代表所述第一圖像的圖像特性和所述第二圖像的圖像特性間的一個可能匹配的候選，建立一個匹配罰函數(MP′i)，以估算所述候選值(Mx，i，My，i)，為每個候選值(Mx，i，My，i)估算所述罰函數(MP′i)，根據匹配罰函數的估算結果，挑選一個候選值(Mx，i，My，i)，其特點在於通過將所述第一圖像(I1)分段，規格化所述第一圖像，該步驟包括將所述圖像(I1)的至少部分像素分配給各自的圖段(10)，為一個圖段(10)的至少部分像素確定一個像素重要度參數(PIM(x，y))，所述像素重要度參數(PIM(x，y))代表每個所述像素的相對重要性，並使匹配罰函數(MP′i)至少部分上是根據像素重要度參數(PIM(x，y))確定的。
2.權利要求1中的方法，像素重要度參數(PIM(x，y))包含一個加權參數(w(x，y))(該參數由一個像素到一個圖段(10，20，30，40)的硬邊界部分(11)的距離(d(x，y))確定)，和一個可視度參數(v(x，y))。
3.依照前面任一權利要求的方法，還包括確定邊界部分(11)的相關性，其中，加權參數(w(x，y))是由像素到一個相關邊界部分(11)的距離確定的。
4.依照權利要求3的方法，其中一個邊界部分(11)的相關性的確定途徑是，估算該邊界部分(11)所造成的圖段(10，20，30，40)的圖段(10，20，30，40)深度值。
5.依照權利要求2的方法，其中可視度參數(v(x，y))表明第一圖像(I1)中的一個像素在第二圖像(I2)中是否有一個相對應的像素。
6.依照權利要求5的方法，其中確定可視度參數(v(x，y))的步驟包括確定第一圖像和第二圖像(I1，I2)的圖段的深度值，並根據該深度值確定哪個更近位置的段模糊了另一個更遠位置的段。
7.依照權利要求1-2中任一個的方法，其中的分段是利用準分段獲得的。
8.包含程序代碼部分的電腦程式產品，當在一個計算機上運行時，執行依照權利要求1-2中任一個的方法。
9.用於匹配數字圖像的設備，包含一個處理單元(110)，用於按權利要求1-2中任一個的方法，匹配數字圖像，該處理單元配有一個用於接收數字圖像(I1，I2)的輸入部分(120)，及一個用於輸出匹配結果的輸出部分(130)。
10.包含權利要求9中所描述設備的裝置。
全文摘要
一種用於匹配數字圖像的方法，包括將由像素組成的第一數字圖像的圖像特徵規格化，提供一個由像素組成的第二圖像，定義一個有限的候選值集合，其中，一個候選值代表第一圖像的圖像特性和第二圖像的圖像特性間一個可能匹配的候選，建立一個匹配罰函數，以估算該候選值，為每個候選值估算匹配罰函數，根據匹配罰函數的估算結果挑選一個候選值，通過對第一圖像分段來規格化第一圖像，該規格化步驟包括向相應的圖段分配至少部分圖像像素，為一個圖段的至少部分像素確定一個像素重要度參數，該像素重要度參數代表每個像素的相對重要性，並使匹配罰函數部分上由該像素重要度參數確定。
文檔編號H04N7/26GK1520695SQ02812930
公開日2004年8月11日 申請日期2002年6月20日 優先權日2001年6月29日
發明者P·維林斯基, P 維林斯基, A M 範奧弗維爾德, C·W·A·M·范奧弗維爾德, F·E·埃恩斯特, 埃恩斯特 申請人:皇家菲利浦電子有限公司