基于特征匹配的算法.ppt

基于特征的匹配,一. 特征匹配過(guò)程 1 特征提取 2 特征描述 3 特征匹配 二. SIFT算法,Local features Detection:,2 x 2 matrix of image derivatives (averaged in neighborhood of a point).,（1）平移Translation （2）歐幾里德幾何（平移+旋轉(zhuǎn)） （3）相似性變換（平移+旋轉(zhuǎn)+尺度） （4）仿射變換 （5）投影變換,The need for invariance,1. 幾何變換,2. 光照變化,一. 特征匹配過(guò)程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測(cè) 1.3 仿射不變特征檢測(cè) 1.4 特征提取總結(jié) 2 特征描述 3 特征匹配 二. SIFT算法,（1）Harris detector (Harris, 1988),Second moment matrix/ autocorrelation matrix,公式由來(lái)說(shuō)明,影像信號(hào)的局部自相關(guān)函數(shù),給定點(diǎn)(x, y)及位移(x, y)，窗口為W，用差平方和(SSD)近似自相關(guān)函數(shù)，計(jì)算窗口W和位移窗口內(nèi)灰度的差別。,位移后影像函數(shù)通過(guò)一階泰勒展開式近似,重新計(jì)算 f(x,y):,“second moment matrix M”,Autocorrelation (second moment) matrix,M can be used to derive a measure of “cornerness” Independent of various displacements (x, y) Corner: significant gradients in 1 directions rank M = 2 Edge: significant gradient in 1 direction rank M = 1 Homogeneous region rank M = 0,Harris detector 流程 1. Image derivatives 2. Square of derivatives 3. Gaussian filter g( ) 4. Cornerness function 5. Non-maxima suppression cHarris tHarris,（2）Hessian detector ( Beaudet,1978),Taylor二階展開式,得到Hessian矩陣,I,Ixx,Ixy,Iyy,小總結(jié),Harris detector Rotation invariant ? Yes The eigenvalues of M reveal the amount of intensity change in the two principal orthogonal gradient directions in the window. Scale invariant ? No Hessian detector, Rotation invariant ? Yes, Scale invariant ? No,一. 特征匹配過(guò)程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測(cè) 1.3 仿射不變特征檢測(cè) 1.4 特征提取總結(jié) 2 特征描述 3 特征匹配 二. SIFT算法,1.2 尺度不變特征檢測(cè),(1) 尺度選擇 (2) The Laplacian-of-Gaussian (LoG) Detector (3) The Difference-of-Gaussian (DoG) Detector (4) The Harris-Laplacian Detector (5) The Hessian-Laplace Detector,1.2 尺度不變特征檢測(cè),(1) 尺度選擇,1.2 尺度不變特征檢測(cè),(1)尺度選擇,1.2 尺度不變特征檢測(cè),(2) The Laplacian-of-Gaussian (LoG) Detector 1 Laplacian filter Laplacian算子具有旋轉(zhuǎn)不變性，但對(duì)噪聲很敏感，因此常需進(jìn)行平滑操作 2 LoG filter 高斯濾波平滑，然后拉普拉斯濾波。,Laplacian-of-Gaussian (LoG)尺度空間的局部極大值點(diǎn),1.2 尺度不變特征檢測(cè),(3) The Difference-of-Gaussian (DoG) Detector 可用高斯差分函數(shù)(DoG)近似LoG,Computation in Gaussian scale pyramid,LoG and DoG Zero crossings “Mexican hat”, “Sombrero” Edge detector !,Lowes DoG keypoints Lowe Edge zero-crossing Blob at corresponding scale: local extremum ! Low contrast corner suppression: threshold Assess curvature distinguish corners from edges Keypoint detection:,1.2 尺度不變特征檢測(cè),(4) The Harris-Laplacian Detector 1 初始化：多尺度下的Harris角點(diǎn)檢測(cè) 2 基于Laplacian的尺度選擇,Harris points,Harris-Laplacian points,1.2 尺度不變特征檢測(cè),(5) The Hessian-Laplace Detector 思想與Harris-Laplacian Detector相同,圖：Hessian-Laplace算子應(yīng)用于具有尺度改變的影像結(jié)果,圖：Harris-Laplace算子在同一場(chǎng)景下不同尺度的兩幅影像上特征檢測(cè)結(jié)果，圓的半徑代表了特征尺度大小,一. 特征匹配過(guò)程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測(cè) 1.3 仿射不變特征檢測(cè) 1.4 特征提取總結(jié) 2 特征描述 3 特征匹配 二. SIFT算法,1.3 仿射不變特征檢測(cè),Harris/Hessian Affine,給定一組由Harris-Laplace算子得到其尺度特征的初始點(diǎn)，用橢圓形區(qū)域獲得仿射不變性。具體處理步驟如下： (1)由Harris-Laplace算子獲得興趣點(diǎn)初始區(qū)域 (2)由二階矩矩陣估計(jì)區(qū)域仿射形狀 (3)歸一化仿射區(qū)域成為圓形區(qū)域 (4)在歸一化的影像上重新檢測(cè)新的位置和尺度 (5)如果二階矩矩陣的特征值在新的點(diǎn)上不相等，則轉(zhuǎn)(2),圖：利用二階矩矩陣的特征值估計(jì)興趣點(diǎn)區(qū)域的仿射形狀，變換是用該矩陣的平方根進(jìn)行的，經(jīng)過(guò)歸一化的圖像XL和XR之間的變換是旋轉(zhuǎn)變換關(guān)系，只取決于一個(gè)旋轉(zhuǎn)因子，因子大小代表了特征值的比率,圖：Harris-Affine算子檢測(cè)的從不同視角得到的結(jié)果圖,圖：Hessian-Affine算子得到的不同視圖下的影像檢測(cè)結(jié)果,一. 特征匹配過(guò)程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測(cè) 1.3 仿射不變特征檢測(cè) 1.4 特征提取總結(jié) 2 特征描述 3 特征匹配 二. SIFT算法,Harris-Laplace (HRL) scale-adapted Harris (rotation invariant) Laplacian-of-Gaussian scale-space (scale invariant) detects cornerlike structures Hessian-Laplace (HSL) Hessian detector (rotation invariant) Laplacian-of-Gaussian scale-space (scale invariant) blob-like structures higher localization accuracy than DoG higher scale selection accuray than HRL Laplace kernel fits better to blobs than to corners Difference-of-Gaussian (DoG) local scale-space maxima of the DoG blob-like structures respond to edges (unstable) Harris-Affine (HRA) localization and scale estimated by HRL affine adaptation process based on second moment matrix Hessian-Affine (HSA) HSL + affine adaptation process,一. 特征匹配過(guò)程 1 特征提取 2 特征描述 2.1 概述 2.2 幾種特征描述方法 3 特征匹配 二. SIFT算法,2.1 特征描述概述,Extract vector feature descriptor surrounding each interest point. The ideal descriptor should be Repeatable Distinctive Compact Efficient Challenges Invariant： Illumination Scale Rotation Affine,Illumination,Scale,Rotation,Affine,一. 特征匹配過(guò)程 1 特征提取 2 特征描述 2.1 概述 2.2 幾種特征描述方法 3 特征匹配 二. SIFT算法,2.2 幾種特征描述方法,(1) Raw patches (2) Moment invariants (3) Filters (4) SIFT descriptor (5) SURF,(1) Raw patches 描述特征點(diǎn)鄰域的最簡(jiǎn)單方法是直接將鄰域的像素灰度強(qiáng)度構(gòu)成特征向量。 用相關(guān)系數(shù)估計(jì)兩個(gè)描述子 的相似程度 缺點(diǎn)： 1 對(duì)位置，尺度，姿態(tài)的變化敏感 2 弱區(qū)分性,(2) Moment invariants 1962年Hu提出了圖像識(shí)別的不變矩理論，即圖像的7個(gè)不變矩具有平移、旋轉(zhuǎn)、比例不變性。為圖像識(shí)別建立了一種統(tǒng)計(jì)特征提取方法，得到了廣泛應(yīng)用。 以下7個(gè)對(duì)平移、旋轉(zhuǎn)和尺度變換不變的矩是由歸一化的二階和三階中心矩得到的：,(2) Moment invariants General moments of order p+q and degree a: Central moments pq: invariant to translation,Normalized central moments,Translation, rotation, scale invariant moments 1 . 7 Hu,Geometric/photometric, color invariants vanGool et al., Computing the invariants reduces the number of dimensions, More suitable for color images,(3) filters, complex filters, differential invariants “l(fā)ocal jet”(一系列導(dǎo)數(shù)向量) 影像I在點(diǎn)X處的N階local jet定義為：, steerable filters,Which steer derivatives in a particular direction given the components of the local jet,影像導(dǎo)數(shù) 由高斯導(dǎo) 數(shù)的卷積 來(lái)獲得。,(a)高斯導(dǎo)數(shù)到4階,(b)6階復(fù)數(shù)濾波(complex filters),“l(fā)ocal jet”,L(x,)是由高斯導(dǎo)數(shù)和影像卷積而成,旋轉(zhuǎn)不變,(4) SIFT descriptor,(5) SURF,Approximate SIFT Works almost equally well Very fast,Fast approximation of SIFT idea Efficient computation by 2D box filters & integral images 6 times faster than SIFT Equivalent quality for object identification,見后面講解,一. 特征匹配過(guò)程 1 特征提取 2 特征描述 3 特征匹配 二. SIFT算法,3 特征匹配,3.1 基于局部灰度信息的特征匹配方法 局部區(qū)域灰度統(tǒng)計(jì)特性 3.2 基于特征向量的特征匹配方法 特征向量之間的距離 （1）歐氏距離 （2）馬氏距離,k-d樹是二叉檢索樹的擴(kuò)展，k-d樹的每一層將空間分成兩個(gè)。樹的頂層結(jié)點(diǎn)按一維進(jìn)行劃分，下一層結(jié)點(diǎn)按另一維進(jìn)行劃分，以此類推，各個(gè)維循環(huán)往復(fù)。劃分要使得在每個(gè)結(jié)點(diǎn)，大約一半存儲(chǔ)在子樹中的點(diǎn)落入一側(cè)，而另一半落入另一側(cè)。當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給定的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束。,K-d 樹,一.