計算用於辨識的全局到局部度量的方法

2023-06-06 21:14:51

專利名稱：計算用於辨識的全局到局部度量的方法
計算用於辨識的全局到局部度量的方法
背景技術：
分類(classification)問題可被構想為如下驗證方案其中，目標是判斷一對點是正還是負，即在這些點屬於同一類的情況下為正而在其他情況下為負。假設給定一組被標記了的數據，我們可以嘗試對下述度量(metric)進行學習在給定的特徵空間中，該度量給定了對於此任務將會實現最佳性能的、區別性的距離，即在正的點對之間給予短距離並把長距離給予負的點對。此類方法的詳細說明可在I中找到。已經流行採用全局度量學習(global metric learning)來改進分類算法，例如K近鄰(K-nearest neighbors, KNN)分類算法2。它通常包括對將要用於分類的Mahanlobis距離的最優協方差矩陣進行估計。雖然這些種類的全局度量對於分類已經表現出令人印象深刻的改進，但是它們不捕捉特徵空間中的可能與複雜數據分布有關的局部屬性。為了克服此困難，通常採用兩步方法3、4。首先學習全局度量，並且對特徵空間中的訓練點進行相應的變換；其次，在各變換後的訓練點的鄰域中估計局部度量(local metric)。 這些局部度量允許對數據的更好的適應性，然而通常要求對位置的啟發式(heuristic)選擇。

發明內容
與上述不同，本發明是分層級的全局到局部(global-to-local)方法，其中通過使用數據分布本身，來迭代地對度量進行細化和學習。該方法開始於估計全局度量並對數據應用相應的(度量)變換。然後，變換後的點受到聚類(clustering)，以獲得K個集群(cluster)的集合。這兩個步驟被循環地應用於各個集群，直到滿足了關於集群終止的標準為止。這樣的標準例如可以是樹中的最大高度、集群中數據點的最小方差、或者集群中數據點的最小數目。這形成了樹，各節點有相關聯的度量。換言之，這裡提供了一種方法，其計算全局到局部度量以用於辨識(recognition)。基於具有特徵表示(feature representation)的訓練示例，該方法自動計算在特徵表示的空間上變化的局部度量，以優化辨識系統的辨別力和性能。給定任意特徵空間中的一組點，以分層級的方式學習局部度量，該分層級的方式在同一類點之間給出短距離並在不同類的點之間給出長距離。不是考慮全局度量、基於類的度量或基於點的度量，所提出的發明將連續的聚類應用於數據並且將度量關聯到集群中的每一個。


圖I圖不出全局到局部度量樹的不意性布局。圖2圖示了系統，這些系統包括相機和使用全局到局部度量的計算單元。
具體實施例方式以下是對本發明的詳細描述。
給定一組被標記了的點Ixi, i = l... N}，將全局度量學習算法連續地應用於受到分層級聚類的點的集合。這具有形成度量樹的效果。為了簡化表述，假設用於聚類算法的各實例的集群數目為常數並且等於K。令Iii,」表示層級i處的第j個集群，並且令Auj表示
相關聯的度量變換矩陣。基於變換後的點的集合}來對度量進行學
習，例如但不限於使用5中提出的信息理論度量學習算法。在將聚類算法應用於節點nq之前，將與該節點的度量相關聯的變換應用於由其父節點給出的點。現在可以使用度量樹來評估任意兩個數據點之間的距離，例如圖像描述符、臉部特徵向量或其他特徵表示。首先，每個點被投放到樹中，並且其路徑被重新獲得。具體地，識別樹中的包含兩個點的最後一個節點。然後，這些點之間的距離是使用與此節點相關聯的度量而得到的距離，此度量可能與父節點的度量相混合(compound)。在最壞的情況下，最後一個公共節點是樹的根，因而該距離將使用全局度量。公共節點在樹中越深，則度量越局部。與純局部或純全局方法相比，該方法的優點是根據終止標準(例如最大葉子大小、最大葉子方差、最大高度限制)改善了在稠密或複雜區域中的度量。此構想可能存在的一個問題是對聚類邊界的高度依賴性。點可以彼此接近並且在聚類樹中很早就分開。為了減輕此判決的影響，可以構建多個度量樹並對由它們中的每一個給出的距離進行平均。本發明的優選實施例給出了用於全局到局部度量學習的方法，該方法包括以下步驟對度量樹進行學習(可以像圖I中圖示出的那樣)，使用此度量樹來對測試數據進行分類或比較。在本發明的另一實施例中，一種電腦程式存儲在計算機可讀存儲介質中並且在計算單元中運行以進行全局到局部度量學習，該電腦程式包括以下步驟對度量樹進行學習，使用此度量樹來分類或比較測試點。本發明的又一實施例，用於全局到局部度量學習和分類的系統包含用於全局到局部度量學習的電腦程式，該電腦程式包括以下步驟學習度量樹，使用此度量樹來分類或比較測試數據。在本發明的又一實施例中，系統或設備被用於獲得圖像、進行分析、並對使用全局到局部度量的分類所得的結果做出響應，可以如圖2中看到的那樣。這樣的系統可以包括至少一個圖像獲取設備101並包括計算設備100。已經描述了用於本發明的潛在方法以及一系列實施例。上述發明的可能應用領域包括但不限於從對象辨識和臉部辨識到圖像內容分類。參考文獻[I]D. Ramanan, S. Baker. " Local Distance Functions A Taxonomy,New Algorithms, and an Evaluation " International Conference on Computer Vision(ICCV)Kyoto, Japan, Sept. 2009.[2]K. Weinberger, J. Blitzer, L. Saul. " Distance Metric Learning forLarge Margin Nearest Neighbor Classification" Advances in Neural InformationProcessing Systems 18，MIT Press，Cambridge，MA，pp. 1473-1480，2006.
[3]C. Domeniconi and J. Peng and D.Gunopulos, " Locally Adaptive MetricNearest Neighbor Classification " IEEE Transactions on Pattern Analysis andMachine Intelligence，vol. 24，pp.1281-1285，2002.[4]T. Hastie, R. Tibshirani, " Discriminant Adaptive Nearest NeighborClassification， " IEEE Transactions on Pattern Analysis and MachineIntelligence，vol. 18，no. 6，pp. 607-616，June，1996.[5] J. V. Davis, B. Kulis，P. Jain, S. Sra, and I. S. Dhillon. " Information-theoretie metric learning" In Proceedings of the 24th international Conference onMachine Learning，Corvalis，Oregon，June 20-24，2007.
權利要求
1.一種用於全局到局部度量學習以進行分類和辨識的方法，包括以下步驟 使用在每一層級處通過聚類算法而構建的樹結構，以及 將度量關聯到樹的節點中的每一個節點。
2.根據權利要求I所述的方法，其中，所述聚類算法是K-均值聚類。
3.根據權利要求I所述的方法，其中，所述度量是通過ITML算法得到的對稱矩陣。
4.根據權利要求I所述的方法，其中，所述聚類算法在每個節點處使用局部度量。
5.一種電腦程式，存儲在計算機可讀存儲介質中，並在計算單元中運行以進行根據權利要求I所述的全局到局部度量學習。
6.根據權利要求5所述的電腦程式，還包括以下步驟 找到用於給定特徵比較的相應局部度量，以及 將此局部度量用於分類或辨識。
7.一種用於辨識的系統，包括根據權利要求5所述的電腦程式，還使用特徵表示，這些特徵表示是通過根據權利要求6所述的方法而受到比較的。
8.根據權利要求7所述的系統，其中，所述特徵表示代表圖像中的對象。
9.根據權利要求8所述的系統，其中，所述對象是臉。
全文摘要
一種計算用於辨識的全局到局部度量的方法。基於具有特徵表示的訓練示例，該方法自動計算在特徵表示的空間上變化的局部度量以優化辨識系統的辨別力和性能。給定任意特徵空間中的一組點，局部度量被以分層級的方式學習，該分層級的方式給出同一類點之間的短距離和不同類點之間的長距離。不是考慮全局度量而是考慮基於類的度量或基於點的度量，所提出的發明將連續的聚類應用於數據並將度量關聯到聚類中的每一個。
文檔編號G06N7/00GK102648478SQ201080055760
公開日2012年8月22日 申請日期2010年10月4日 優先權日2009年10月7日
發明者傑羅姆·皮奧瓦諾, 簡·艾瑞克·索姆, 米卡艾爾·羅森 申請人:蘋果公司