基于Shape Context形狀匹配的圖片檢索研究

基于ShapeContext形狀匹配的圖片檢索研究計算機應用唐良2007-1-9檢索的兩大核心問題1.匹配問題信息的相關度的度量2.索引問題B-tree,Hash等方法前人的工作我做的工作2007-1-9圖片相關度的度量方法ShapeMatchingandObjectRecognitionUsingShapeContextIEEETransactionsOnPatternAnalysisandMachineIntelligence,VOL.24NO.24,April20022007-1-9圖片的差異度計算圖片的差異度=兩張圖片中所有最佳匹配點的差異度之和2007-1-9點的差異度計算點的差異度=點的周邊點集分布的差異度之所有叫”Context”（上下文），就是這個周邊的意思2007-1-9一個點周邊點集的分布描述根據(jù)極坐標，劃分空間。平面分成m*n個bin，m個角度區(qū)間，n個logR距離區(qū)間。(R表示極坐標中的距離)作者在論文中取得m=12,n=52007-1-9點分布的差異度計算公式表示第i個點的第k個bin中的點數(shù)對應bin的點數(shù)越接近，函數(shù)值越小2007-1-9算法的缺陷計算量過大，O(N^3)的計算量。查找一個點的最佳匹配點所有點的差異度求和一個點的全部bins數(shù)據(jù)差異計算2007-1-9索引的建立目的和思路1.減支，分類2.壓縮搜索空間3.參考R-tree，Hash等常規(guī)索引建立的方法。2007-1-9搜索最佳匹配點的索引1.基于Hash的思想2.將圖片內(nèi)的所有點進行分類3.只在同類的點集中找到最佳匹配點2007-1-9按照角度來劃分區(qū)間將極坐標空間按照角度分成6個大區(qū)間2007-1-9對每個區(qū)間內(nèi)的點集個數(shù)劃分等級每個區(qū)間內(nèi)點集總數(shù)按照下列區(qū)間分級:Level1:[0,31]Level2:[32,79]Level3:[80,149]Level4:[150,-]求得6個區(qū)間的level整數(shù)值:X1,X2,…,X62007-1-9Hash值計算Hash值=X1*(4^5)+X2*(4^4)+X3*(4^3)+X4*(4^2)+X5*4+X6總共有4^6=4096個不同的hash值圖片內(nèi)的所有點就分布在了這4096不同的hashbucket(桶)內(nèi)。2007-1-9為什么這樣建立hash1.一個hash值，決定X1,X2,…,X6的6個取值。2.X1,X2,..,X6決定一個點周圍點集的大致分布3.最佳匹配的點，應該也是同樣的大致分布可以從前文中Cij的計算公式出發(fā)得到簡單的數(shù)學證明2007-1-9實際Demo的界面2007-1-9測試數(shù)據(jù)庫:15張200x200的圖片2007-1-9效率的測試結果測試圖片點集個數(shù)不用索引使用索引4684484.375ms15.625ms5874968.75ms15.625ms2412234.375ms0ms2742531.25ms15.625ms4463875ms15.625ms2582