比較圖案的製作方法

2023-07-02 14:27:31

專利名稱：比較圖案的製作方法
技術領域：
本發明涉及將一種圖案與另一種圖案進行比較，雖然本發明也可應用於一維圖案以及三維或更多維的圖案，但是本發明尤其涉及諸如可視圖像的二維圖案的比較。
背景技術：
模式識別的標準方法使用模板來識別並分類圖案[1]。這些模板有多種形式，但通常通過訓練數據的統計分析來產生這些模板，並使用相似性度量與未見過的數據進行匹配[2]。統計分析通常基於看起來滿足識別任務需要的大量直觀選擇的特徵來執行。例如，在語音識別中，可以將模板封裝為在頻域獲得的隱馬爾可夫模型(Hidden Markov Models)，而在光學字符識別中，模板採用字符字體自身的形式。在面部識別的情況下，可以使用大量的直觀選擇的特徵(例如，肌理、膚色和面部特徵記錄來定義面部模板。在CCTV的監視應用中，通常通過幀消減(framesubtraction)和背景模板建模處理來檢測入侵者，該處理檢測運動並從該處理中去除背景效果[3]。在很多情況下，特徵的數量導致在計算方面難以處理的過程，在不會明顯降低性能的情況下，可以使用主成分分析和其它技術來減小問題的規模[http//WWW.partek.com/index.html]。在無噪聲環境中，這些方法獲得了極大的成功，但當圖案可變性和圖案分類數量增大時這些方法無效。
在我們以下的較早專利申請中描述了一些用於分析圖像或其它圖案的技術，其中將圖案與同一圖案的其它部分進行比較。
歐洲專利申請00301262.2(公開號No.1126411)(申請人卷號A25904EP#)；國際專利申請PCT/GB01/00504(公開號No.WO 01/61648)(申請人卷號A25904WO)；國際專利申請PCT/GB01/03802(公開號No.WO 02/21446)(申請人卷號A25055WO)；2001年10月16日提交的美國專利申請977,263/09(公開號No.20020081033)(申請人卷號A25904US1)；以及發明人發表的下列論文Stentiford F W M，「An estimator for visual attention throughcompetitive novelty with application to image compression」，Proc.Picture Coding Symposium 2001，Seoul，25-27 April，pp101-104，2001.
Stentiford F W M，「An evolutionary programming approach tothe simulation of visual attention」，Proc. Congress onEvolutionary Computation 2001，Seoul，pp851-858，27-30，May，2001.

發明內容
根據本發明的一個方面，提供了一種用於比較由第一有序單元集合(每一個單元具有一個值)表示的第一圖案和由第二有序單元集合(每一個單元具有一個值)表示的第二圖案的方法，該方法包括對所述第一有序集合的多個單元中的每一個單元執行以下步驟(i)從所述第一有序集合中選擇所考慮的單元附近的多個單元，在所述有序集合中，所選擇的多個單元相對於所考慮的單元各自具有相互不同的位置；(ii)在所述第二有序集合中選擇一個單元；(iii)將所述第一有序集合的所選擇的多個單元與所述第二有序集合的類似多個單元進行比較，所述第二有序集合的類似多個單元中的每一個單元在所述第二有序集合內相對於所述第二有序集合的所選擇的單元的位置與所述第一有序集合的所選擇的多個單元的各個單元相對於所考慮的單元的位置相同，所述比較包括根據預定的匹配標準，將所述第一有序集合的所選擇的多個單元中的每一個單元的值與所述第二有序集合的類似多個單元中對應位置的單元的值進行比較，以確定所述第一有序集合的所述多個單元與所述第二有序集合的所述多個單元是否匹配；(iv)使用所述第一有序集合的新選擇的多個單元和/或所述第二有序集合的新選擇的一個單元來重複所述比較；(v)為所考慮的單元生成作為比較次數的函數的相似性度量，對於該函數來說，比較表示匹配。
本發明的其它方面在權利要求書中限定。


現將結合附圖描述本發明的一些實施例，其中圖1是用於實施本發明的裝置的方框圖；圖2是表示本發明的操作的簡圖；圖3是根據本發明的一個實施例的由圖1的裝置執行的步驟的流程圖；圖4至圖9表示一些圖像以及對這些圖像獲得的數值結果。
具體實施例方式
圖1示出了一種裝置，該裝置包括被編程用來執行根據本發明第一實施例的圖像分析的通用計算機。該裝置具有總線1，中央處理單元2、可視顯示器3、鍵盤4、用於輸入圖像的掃描儀5(或其它設備，未示出)以及存儲器6與該總線1相連。
在存儲器6中存儲有作業系統601、用於進行圖像分析的程序602，以及用於存儲被稱為圖像A和圖像B的兩個圖像的存儲區域603、604。將每一個圖像存儲為多個值的二維陣列，每一個值表示陣列中的一個圖像單元(picture element)的亮度。
在圖2a和2b中示意性地示出了這些圖像陣列。圖像A由圖像單元x＝(x1，x2)的20×20陣列構成，其中，x1和x2是單元在圖像內的水平和垂直位置。每一個單元的亮度由對應的值a＝a(x)表示。類似地，圖像B由亮度值為b的圖像單元y＝(y1，y2)的20×20陣列構成。
根據圖3所示的流程執行由程序602執行的圖像分析方法。該方法的目的是生成圖像之間的相似性度量V；更具體地，高值的V表示圖像B包含與圖像A的內容相類似的可視素材(visual material)。
假定圖像的寬度為xmax1和ymax1，高度為xmax2和ymax2，則圖像單元的坐標為x1＝0…xmax1-1，x2＝0…xmax2-1。
在步驟100中，選擇圖像A中的圖像單元x。儘管可以以任意的順序對它們進行處理，但是下述處理是適宜的首先選擇單元x＝(ε，ε)，並且隨後以光柵掃描的方式對後繼單元進行迭代，直到對除了圖像邊緣ε內(即達到(xmax1-ε-1，xmax2-ε-1))的單元以外的所有單元都進行了處理為止。
在步驟101中，將分值V和計數器tries設置為0。
在步驟102中，在位置x的最大距離s內，從圖像B中隨機選取單元y＝(y1，y2)，即|xi-yi|≤s對所有的i這種可選的限制在圖2b中由虛線框S表示。如果已知兩個圖像中的對應對象的位置偏移在任何坐標方向上不會超過s個圖像單元，那麼這可以提高效率實際上，s表示兩個圖像之間的最大重合失調(misregistration)或局部失真。
y的選擇也受到限制，即其位於距離圖像邊緣不超過ε的位置，即ε≤yi≤ymaxi-ε-1 i＝1，2其中，ymaxi是以圖像單元為單位的圖像寬度或高度(本示例中為20)。
在步驟103中，在圖像單元x的鄰域N中選擇圖像單元x′的集合Sx，並與圖像單元x以及從圖像A中任意選擇的數量為m的至少一個另外的單元進行比較。其中鄰域N為以x為中心的2ε+1×2ε+1的正方形。也就是說，如果|xi′-xi|＜ε 對於所有的i則單元x′＝(x1′，x2′)位於N內。
優選地，鄰域集合Sx包括單元x本身，儘管這不是非常必要的。隨後在圖像B中限定鄰域集合Sy，鄰域集合Sy具有m+1個單元y＝(y1，y2)，每一個單元y相對於單元y的位置與Sx的對應單元x相對於x的位置相同，即yi-yi＝xi-xi對於所有的i(當然，上述邊緣限制的原因是為了避免選擇延伸到圖像區域外部的鄰域)。在步驟104中，計數器tries加1，在步驟105中，檢查tries的值以查看是否已進行了充分的比較。
假定目前不是這種情況，那麼在步驟106中比較這兩個集合Sx，Sy。如果集合Sx的單元x的值和集合Sy的對應位置的單元x的值之間的差值小於閾值δ，即|a(x)-b(y)|＜δ則認為兩個單元匹配。只有在集合Sx的每一個單元x都與集合Sy的對應單元y相匹配的情況下，才認為這兩個集合匹配。
如果集合不匹配，則放棄單元y，作為用於進一步比較的候選，並且使用選擇的新點y在步驟102繼續進行處理。另一方面，如果它們匹配，則保留y用於進一步的迭代。現在，略過步驟107，處理進行到步驟108，在步驟108中分值V加1。然後在步驟103產生不同的鄰域集合，並且從該點開始重複進行處理。
在步驟105中，當比較次數的計數tries超過閾值時，終止對當前x的處理在步驟109中，將V的值存儲在存儲器6中，隨後，在步驟110中，檢查是否處理了所有點x。如果處理了所有點x，則首先在步驟111中計算平均值Va(為圖像A中的多個圖像單元x的所有各個分值V的平均值)，並且在步驟112終止該處理；否則對新的點x從步驟100重複整個過程。
可以將在步驟105中使用的閾值設置為所期望的比較次數t，並且省略步驟107。然而，實際上我們發現，在初期的比較中往往不能找到匹配，而一旦找到了匹配，則會出現與同一y相匹配的大量不同鄰域集合。為了提供易於解釋的分值V，對最初的幾次迭代不進行記數；所示的處理包括防止該分值在最初的init次比較中增大的測試107。因此，在步驟105中使用的閾值增大了init，從而最大的可能分值為t。通過這種方式，我們發現獲得非常相似或相同的圖像的高分值或最大分值的機會大大增加。
在測試中所使用的各種參數的具體值如下圖像A的大小xmax1×xmax220×20圖像B的大小xmax1×xmax220×20鄰域參數ε4鄰域集合大小m3最大A-B偏移s7比較次數t50初始比較init20當然，對較高解析度的圖像，相應地選擇較大的ε值和s值。t和init的值也必須隨著s的增大而增大，以獲得同樣可靠和統計學上有意義的結果。
稍後給出這些測試的結果；應該注意，其中所使用的參數與上面引用的參數不同。
可以看出，如果許多隨機選擇的Sx與圖像B中的給定y的Sy相匹配，則圖像A中的單元x的分值較高。值得注意的是，如果Sx與Sy(其中y不是固定的，而是從圖案A中隨機選擇的)不匹配，則圖像A中的圖像單元x的視覺注意力(Visual Attention)分值(在我們較早的專利申請中已討論)較高。而視覺注意力不需要存儲器來存儲單個圖像A，本發明的方法還需要包含在圖案B中的信息以檢測共同性。
如果t個鄰域集合Sx的序列與圖案B中的某些y周圍的相同鄰域高比例地匹配，則位置x值得認知注意。在圖2中，在圖案A的圖像單元x的鄰域中選擇m＝3個圖像單元x，並且與圖案B的圖像單元y的鄰域中的3個圖像單元相匹配。這些圖像單元中的每一個可以具有三個顏色強度，所以a＝(ar，ag，ab)，如果所有m+1個對應圖像單元的顏色強度具有在彼此的δ之內的值，則第二圖像單元y的鄰域集合與第一圖像單元相匹配。對A中的圖像單元x(這些圖像單元x在t個鄰域集合Sx的範圍與B中的y周圍的鄰域集合Sy大量匹配)賦予高分值。這意味著將對具有出現在B中的結構的A中的鄰域集合賦予高分值。
一些圖像分析技術使用補丁(patch)來執行圖像之間的比較計算，補丁是其中採用了所有圖像單元的鄰域。當相關性度量超過特定閾值時，補丁匹配。除了在相關性度量被設計用來識別特殊紋理的情況以外，這種方法不能很好地利用小於補丁大小的細節。在本方法中使用的隨機圖像單元鄰域Sx沒有這種缺點。
通過在檢測到匹配時保留圖像單元位置y，並重新使用y與t個鄰域集合中的下一個鄰域集合進行比較，可以顯著提高得分機制(scoringmechanism)的收益(gain)。如果生成了匹配圖像單元構型，則其它構型將很有可能在同一點再次匹配，一旦找到並重新使用這種位置y，則將加速分值的升高，只要該序列不被後面的不匹配所中斷。
然而，如果Sx在該位置之後不匹配，則分值不增加。並且在圖案B中隨機選擇全新的位置y用於下一次比較。通過這種方式，根據圖案B中的競爭位置是否幾乎不含有與圖案A中的x的鄰域的共同性，來選擇這些競爭位置。
現將討論一些可能的變化。
a)對所有圖像單元x進行分析不是必要的因而，如果需要，可以選擇子集(可能在規則網格上)。
b)上述方法為圖像單元假定了單個(亮度)值。在彩色圖像的情況下，可以首先將圖像轉換為單色。另選地，如果將每一個圖像單元表示為三個值(例如紅、綠、藍)或者亮度加色差，那麼匹配測試將涉及3維單元值之間的距離。例如，如果兩個圖像的色彩分量值為a＝(ar，ag，ab)，b＝(br，bg，bb)，那麼匹配的標準為(ar-br)＜δ和|ag-bg|＜δ，以及|ab-bb|＜δ。下面將進一步討論距離度量。
c)將隨機選擇y的策略修改為假定當單元x＝(x1，x2)產生對於單元y的高分值V，並且要對相鄰單元x(例如，(x1+1，x2))進行處理，那麼要在圖像B中選擇的第一單元y可以是對應的相鄰單元(即(y1+1，y2))。與前面一樣，y的其它選擇可以是隨機的。如果產生單元x的高分值作為與一個以上的y進行比較的結果，則可以選擇與對該高分值作出最大貢獻的任何一個y相鄰的單元。為此，需要暫時跟蹤不同圖像單元y的坐標以及它們的部分分值。
d)不需對整個圖像執行該處理。例如，如果將圖像A的一個區域識別為特別關注的區域(也許使用以上引用的我們較早的專利申請之一中所述的方法)，則所處理的圖像單元x可以僅僅是位於所識別區域中的那些圖像單元。
這裡所稱的隨機選擇包括使用偽隨機過程的選擇的可能性。
該方法不僅可以應用於圖像，或三維圖案，而且可以用於1、2、3或更多維的任何有序值集合。
更一般地，假定希望生成兩個圖案A和B之間的相似性度量，其中這兩個圖案以及圖案內的值的各個模式可以為1、2或更多維。
在有界n維空間(x1，x2，x3，…，xn)中，設圖案A上的度量集合a與A中的位置x相對應，其中x＝(x1，x2，x3， …，xn)以及a＝(a1，a2，a3，…ap)定義函數F，以使得無論a存在於何處a＝F(x)都成立。注意到關於F的屬性(例如，連續性)沒有進行假設是很重要的。假設如果存在a則存在x。
考慮到x的鄰域N，其中{x』∈N iff|xi-xi′|＜εii}在N中選擇m+1個隨機點的集合，其中Sx＝{x1′，x2′，x3′，…，xm′}，並且定義了F(xi′)。
然而，其中優選地，將x′中的一個約束為等於x。實際上發現不需要對隨機選擇進行約束來避免兩次選擇相同的點即，xi′不必是唯一的。實際上xi′可以全部與x或x1′一致。
在圖案B中選擇與度量集合b相對應的位置y，為該位置y定義了F。
定義集合Sy＝{y1′，y2′，y3′，…，ym′}，其中存在x-xi＝y-yi和F(yi)。
如果|Fj(x)-Fj(y)|＜δj並且|Fj(xi)-Fj(yi)|＜δji，j則說x的鄰域集合Sx與y的鄰域集合相匹配。
通常，δj不是常量，而是依賴於比較的度量，即δj＝fj(F(x)，F(y)) j＝1…p注意，對於某些問題可能寧願對a和b之間的矢量距離(例如城市街區距離j|aj-bj|]]>或者歐幾裡得距離{j(aj-bj)2}]]>)應用閾值，而不是由於要求各個分量aj＝Fj和bj＝Fj相匹配而限定匹配。
將通過下面的測試結果來說明圖3的流程圖中所述方法的操作。
在這些測試中，使用20×20的黑白圖像(即a和b的值始終是0或1)。然而，這些測試與先前描述的不同在於僅對黑色圖像單元記分，即，匹配標準不僅僅是|a-b|＜δ，而且包括a＝b＝1。
在每一種情況下，附圖示出了第一圖像A以及多個與第一圖像進行比較的被標記為B1、B2等的第二圖像B(以前的情況是兩個第一圖像A1、A2與一個圖像B進行比較)。從左到右測量坐標x1，y1，從上到下測量坐標x2，y2。使用平均值Va標記各個第二圖像。一些附圖示出了圖像區域的各個分值V的三維圖形在每一種情況下，右手軸表示標記的水平軸，而前軸表示圖像的垂直軸。圖形的垂直軸表示V值(在示例2的嵌入式識別的情況下表示V值，而在其他情況下表示50-V)。
示例1 光學字符識別(圖4)將字母B的圖像A與字母A、B、C、D和E的圖像B1-B5進行比較。分級排序的平均分值Va與B、D、E、C、A相對應。使用t＝50、s＝3和ε＝2生成該結果。
示例2 嵌入式識別(圖5)將『X』形的圖像A與另一包含9個更小形狀(包括『X』)的圖像B1進行比較。還將該『X』形與具有相同9個形狀(除改變了小『X』以外)的圖像B2進行比較。平均值Va分別為27.5和11.9。這表示『X』特徵在第一圖像中出現較多，而在第二圖像中出現較少。在圖中示出了各個比較的各個分值V。使用t＝50、s＝7和ε＝2產生該結果。更複雜的嵌入式識別的示例是在一群人中識別已知的面部。
示例3 商標檢索(圖6)首先將特殊交叉形狀的圖像A與包括大交叉在內的基本形狀B1-B4進行比較，各個基本圖案表示相互之間具有高分值的相似形狀的簇。大交叉產生最大的平均值Va(43.6)。隨後將該相同的特殊交叉與包括其本身的小變體(B5)(其獲得了最大分值50)在內的4個不同的交叉B5-B8進行比較。該圖提供了與大交叉相比較的各個圖像單元的值(50-V)，高柱表示與該交叉下部腿的端部不一致。利用t＝50、s＝7以及ε＝2生成該結果。
示例4 指紋識別(圖7)如同在商標的示例中那樣，可以區分和檢索更複雜的圖案(某些圖案具有大量相似的素材)。簡化的拱形A與代表性的拱形B4匹配最好(49.3)，隨後與其它拱形中的相同圖案匹配得最好(49.9)。該圖提供了與代表性拱形圖案相比較的各個圖像單元的值(50-V)，高柱表示與脊端和邊界不一致。利用t＝50、s＝3以及ε＝2生成該結果。
示例5 面部識別(圖8)儘管對數據進行了極大的簡化，但是該示例表示面部識別的實現。將面部A與4個代表性的面部B1-B4進行匹配，隨後與由匹配最好的代表性的面部B2(45.7)表示的子簇B5-B8進行匹配。在該子簇中與不相同的面部B7匹配最好(49.6)。該圖提供了與第二最接近圖案B6(48.2)進行比較的各個圖像單元的值(50-V)，高柱表示嘴部區域不一致。利用t＝50、s＝3以及ε＝2生成該結果。
示例6 監視(圖9)本示例表示如何相對於可變背景來檢測入侵者。表示移動的雲、樹和柵欄的圖案A1相對於標準背景B獲得高分值Va(48.0)。而存在入侵者的版本(A2)獲得低得多的分值(33.1)。該圖提供了入侵者圖像(33.1)中的各個圖像單元的值(50-V)，最高的柱表示入侵者的位置。利用t＝50、s＝3以及ε＝2生成該結果。
本方法對兩幅圖像進行分析，識別感知上重要的共同特徵和差異，而不受比例差異、局部相對失真和位移的影響。這意味著該方法可以應用於其中要識別的對象嵌入在另一圖像中的識別問題。也意味著可以根據相互之間的特徵相似性度量來對圖像進行分類，並且可以將這些值用於定義多類識別系統和實例查詢(Query-By-Example)檢索系統。如同入侵者檢測或偽造品檢測的情況，通過相同的標記(token)，可以將該方法用於檢測不相似性。可以將該方法用於檢測圖像之間的不一致以檢測運動或視差(parallax)。該方法不需要依賴圖像內容的先驗知識(prior knowledge)，並且不需要訓練過程。該算法尤其適合於並行實施。
現將描述我們已說明的方法的各種優點。
模式識別模式識別的標準方法需要來自所有類別的大量代表性的圖案，以滿足分類器的訓練過程的需要。如果所選擇的特徵不能表徵未在訓練集中適當表示的未見過的圖案(unseen pattern)，則這種分類器仍將無效。本方法除了進行比較的兩個圖像以外，不需要訓練集。
對於模式識別技術，通常使用特殊的措施(provision)來標定所分類圖案的差異。由於投影和其它因素，可以導致在可視域中的這種差異。通常將先驗知識併入分類器以進行補償。只要ε不是太大，本方法就不需要這樣做。
另一個優點是能夠識別嵌入較大數據結構內的圖案而不受指數增長的計算需求的困擾或噪聲的影響。因此，本方法可以應用於檢測著作權侵權問題，其中部分素材是從較大的作品(例如藝術作品)中抄襲的，以及應用於縮減資料庫大小的任務，其中重複內容很普遍是公知的。本方法也可直接應用於識別犯罪現場指紋，其中全部指紋中只有一部分可以用於進行匹配。在面部識別的情況下，本方法根據未知面部的有限部分進行搜索，這意味著例如在下顎、兩頰及喉頭的鬍鬚(beard)和嘴唇上面的鬍鬚(moustache)可能導致不確定性的情況下，可以僅僅根據眼睛或鼻子區域進行搜索。
除非對特殊的圖案內容採取措施，否則在所比較的圖案由於局部失真或小的運動(例如，如搖動的樹、移動的雲、面部表情的變化、不規則表面上的犯罪現場指紋，或噪聲的可視情況)而不同時，用於模式識別的標準模板方法無效。這些措施需要應用先驗知識，並且如果未見過的圖案失真與系統設計要求不一致，則仍會導致系統無效。本方法能夠忽略局部失真的影響，而無需失真類型的先驗知識。
本方法可以應用於任意維的圖案，例如一維音頻信號、三維視頻數據(x、y、時間)或者從任何源(例如傳感器陣列)獲得的n維隨時間變化的矢量。在語音識別的情況下，可以處理語音速度的變化而不需要使用特殊的啟發式方法。雖然傳統方法使用動態時間重疊(Dynamic TimeWrapping)來克服該問題，但是會導致更大量的計算負擔，並且存在重疊處理導致錯誤分類增加(尤其對於大型多分類問題)的危險。如果在對話中使用的單詞是唯一的(例如，「yeah」而不是「yes」，省略了最後的摩擦音)，則使用本發明，對於單詞識別部分發音就足夠了。
本方法通過測量各個圖像中的多個鄰域的分值來處理這些問題。儘管如果單個圖像內的一圖像單元的鄰域與同一圖像內的大多數其它部分明顯不同，則該圖像單元在該單個圖像內是重要的(如在上述我們的較早專利申請中所討論的)，但是如果該圖像單元的鄰域與第二圖像中的鄰域非常相似，則該圖像單元在認知上很重要。由於在特定的範圍內分值不受影響，所以可以顯著減少重合失調和局部失真的影響。
可以將該分值用於相互之間具有高分值的圖案的簇分組。可以對從各個簇中提取的代表性圖案本身進行群集(clustered)，以形成高級簇，並且繼續該處理以構成非常大的圖案資料庫。可以通過測量各個最高級代表性圖案的分值，並且隨後測量與前一簇中分值最高的代表性圖案相對應的子簇中的各個代表性圖案的分值，來進行實例查詢檢索。很有可能某些代表性圖案表示重疊的簇(這些簇包含具有高分值的圖案以及那些代表性圖案)。本方法可以與視覺注意力機制相結合使用以快速限定圖案中的關注區域，並且隨後獲得該限制區域和基準圖案(B圖案)集合之間的分值。在航空背景下，可以使用視覺注意力迅速檢測飛行對象，並且隨後計算的分值可以表明該對象可能是鳥還是飛機。
不一致性檢測不一致性檢測的標準方法很大程度上依賴於兩個圖像之間的精確重合，從而在多個圖像單元(與繪製在兩個圖像中的原始目標的同一點相對應)之間進行消減(可以對整個圖像的小區域分段執行)。所得到的差別圖像突出了在與原始圖像中的差異相對應的那些區域。如果由於將不確定性引入正確重合位置的估算而導致存在噪聲，則這會變得非常困難，並會因此產生許多虛假的差異。
即使不存在噪聲，局部失真或輕微的主體移動也將導致重合失調，並且將會突出不關注區域的差異，除非對該失真合移動本身進行測量。在進行消減之前的線性或非線性數字圖像重合技術在大部分情況下可以部分地補償但不能消除該問題[4]。
傳統方法所面臨的嚴峻問題源自產生兩幅圖像的不同條件。這些差異可能來自照明、天氣條件、略微不同的視角、膠捲造成的差異，或者具有不同光學系統的不同相機。這些幹擾都會在圖像之間產生與內容無關的虛假差異。
由圖像獲取條件導致的兩個圖像之間的差異將不會影響本方法，因為該差異將均等地影響圖像所有部分的分值，並且不會影響各個分值的分級排序。通過採用用於圖像單元匹配的較大閾值(參見以上所述的δj)來補償兩個圖像之間的明顯照度(illumination)差異。例如，如果兩個圖像的X射線曝光時間不同，則該處理是必要的。
本發明還具有能夠檢測多個不一致(其中將圖像A與圖像B1、B2、B3等進行比較)的優點。在CCTV入侵者檢測(其中，圖像幀B1、B2、B3等是不同環境條件和其它正常背景狀態的典型示例)的情況下，這是有用的，並且僅當在所有正常圖像幀中都檢測到不一致時才發出警報。
可以看到，這些方法幾乎與所有要求圖像識別的應用相關面部識別、指紋識別、OCR、圖像檢索、商標識別、偽造品檢測、監視、醫學診斷等。
這些方法尤其與醫療行業(其中需要對非常易變並且有噪聲的圖像進行比較來跟蹤醫療狀態的進展)相關。例如，通常從在不同時間通過X光拍攝的乳房X光照片中識別可能的癌生長，並且任何自動輔助將提高放射科醫生的工作效率。在另一示例中，通常可以通過從對比注射後拍攝的圖像中消減去正常胸部的X光來增強對比。並且正確的重合不僅難於獲得，而且是成功處理的關鍵。我們已描述的方法可以提供更清楚的結果，而不需涉及重合問題。
用於乳房X光照片的先進軟體檢測系統(例如，http//www.r2tech.com.prd/)能夠準確定位與通常癌症相關的特定特徵(例如，微鈣化(microcalcification))，但是基本上沒有解決時間比較的問題。
參考文獻[1]Vailaya A et al.，Image Classification for Content-BasedIndexing，IEEE Trans on Image Processing，Vol 10，No 1，pp117-130，Jan 2001. Santini S Jain R，Similarity Matching，in Proc 2ndAsianConf on Computer Vision，pages II 544-548，IEEE，1995. IEEE Trans PAMI-Special Section on Video Surveillance，Vol 22 No 8，Aug 2000. Brown L G，A survey of image registration techniques，ACMComputing Surveys，Vol.24，No.4(Dec.1992)，pp.325-376.
權利要求
1.一種用於對由第一有序單元集合表示的第一圖案和由第二有序單元集合表示的第二圖案進行比較的方法，其中該第一有序單元集合中的每一個單元都具有一個值，該第二有序單元集合中的每一個單元都具有一個值，該方法包括對該第一有序集合的多個單元中的每一個單元執行以下步驟(i)從所述第一有序集合中選擇所考慮的單元附近的多個單元，在所述有序集合中，所選擇的多個單元相對於所考慮的單元各自具有相互不同的位置；(ii)在所述第二有序集合中選擇一個單元；(iii)將所述第一有序集合的所選擇的多個單元與所述第二有序集合的類似多個單元進行比較，所述第二有序集合的類似多個單元中的每一個單元在所述第二有序集合內相對於所述第二有序集合的所選擇的單元的位置與所述第一有序集合的所選擇的多個單元中的各個單元相對於所考慮的單元的位置相同，所述比較包括根據預定的匹配標準，將所述第一有序集合的所選擇的多個單元中的每一個單元的值與所述第二有序集合的類似多個單元中對應位置的單元的值進行比較，以確定所述第一有序集合的所述多個單元與所述第二有序集合的所述多個單元是否匹配；(iv)使用所述第一有序集合的新選擇的多個單元和/或所述第二有序集合的新選擇的一個單元來重複所述比較；以及(v)為所考慮的單元生成作為比較次數的函數的相似性度量，對於該函數來說，所述比較表示匹配。
2.根據權利要求1所述的方法，其中，所述第一有序集合的所述多個單元包括所述考慮的單元。
3.根據權利要求1或2所述的方法，其中，所述第一有序集合的所述多個單元的選擇是隨機的或偽隨機的。
4.根據權利要求1、2或3所述的方法，其中，所述第二有序集合的一個單元的選擇是隨機的或偽隨機的。
5.根據前述權利要求中的任意一項所述的方法，其中，在產生匹配判定的比較之後，使用所述第一有序集合的新選擇的多個單元與所選擇的所述第二有序集合的同一單元進行進一步的比較。
6.根據前述權利要求中的任意一項所述的方法，其中，在產生沒有匹配的判定的比較之後，使用所述第二有序集合的新選擇的一個單元與所選擇的所述第一有序集合的相同多個單元進行進一步的比較。
7.根據前述權利要求中的任意一項所述的方法，其中，各個值由多個分量組成。
8.根據前述權利要求中的任意一項所述的方法，其中，進行預定次數的比較。
9.根據前述權利要求中的任意一項所述的方法，其中，所述相似性度量是除了最初幾次比較之外的比較次數的函數，對於該函數來說，所述比較表示匹配。
10.根據前述權利要求中的任意一項所述的方法，其中，當所考慮的單元產生表明大量匹配的相似性度量並且要考慮所述第一有序集合的另一單元時，用於與其進行比較的所述第二有序集合的首選單元屬於所述第二有序集合中的下述單元，即在所述第二有序集合中相對於所述第二有序集合中產生所述大量匹配的單元的位置與所述第一有序集合的所述另一單元相對於前一所考慮單元的位置相同的單元。
全文摘要
第一圖像(或其他圖案)由第一有序單元集合A表示，第二圖案由第二有序單元集合表示，其中所述第一有序單元集合中的每一個單元都具有一個值，所述第二有序單元集合中的每一個單元都具有一個值。對所述兩個有序單元集合的比較涉及對所述第一有序集合的多個單元x中的每一個單元執行以下步驟從所述第一有序集合中選擇所考慮的單元附近的多個單元x′(103)；在所述第二有序集合中選擇一個單元y(102)；將所述第一有序集合的多個單元x′與所述第二有序集合的多個單元y′進行比較(y′中的每一個單元相對於所述第二有序集合的所選擇的單元y的位置與所述第一有序集合的所選擇的多個單元中的各個單元x′相對於所考慮的單元的位置相同)。所述比較本身(106)包括根據預定的匹配標準，將所述第一有序集合的所選擇的多個單元x′中的每一個單元的值與所述第二有序集合的類似多個單元中的對應位置的單元 y′的值進行比較，以確定所述第一有序集合的所述多個單元與所述第二有序集合的所述多個單元是否匹配。隨後使用所述第一有序集合的新選擇的多個單元x′和/或所述第二有序集合的新選擇的一個單元y重複所述比較，以產生作為匹配次數的函數的相似性度量V。優選地，在產生匹配判定的比較之後，使用所述第一有序集合的新選擇的多個單元x′和所選擇的所述第二有序集合的同一單元進行進一步的比較。
文檔編號G06K9/00GK1643540SQ03806736
公開日2005年7月20日 申請日期2003年3月21日 優先權日2002年3月22日
發明者弗雷德裡克·沃裡克·邁克·斯騰蒂福特 申請人:英國電訊有限公司