基于特征匹配的算法.ppt

基于特征的匹配,一. 特征匹配過程 1 特征提取 2 特征描述 3 特征匹配 二. SIFT算法,Local features Detection:,2 x 2 matrix of image derivatives (averaged in neighborhood of a point).,（1）平移Translation （2）歐幾里德幾何（平移+旋轉） （3）相似性變換（平移+旋轉+尺度） （4）仿射變換 （5）投影變換,The need for invariance,1. 幾何變換,2. 光照變化,一. 特征匹配過程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測 1.3 仿射不變特征檢測 1.4 特征提取總結 2 特征描述 3 特征匹配 二. SIFT算法,（1）Harris detector (Harris, 1988),Second moment matrix/ autocorrelation matrix,公式由來說明,影像信號的局部自相關函數(shù),給定點(x, y)及位移(x, y)，窗口為W，用差平方和(SSD)近似自相關函數(shù)，計算窗口W和位移窗口內灰度的差別。,位移后影像函數(shù)通過一階泰勒展開式近似,重新計算 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,小總結,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,一. 特征匹配過程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測 1.3 仿射不變特征檢測 1.4 特征提取總結 2 特征描述 3 特征匹配 二. SIFT算法,1.2 尺度不變特征檢測,(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 尺度不變特征檢測,(1) 尺度選擇,1.2 尺度不變特征檢測,(1)尺度選擇,1.2 尺度不變特征檢測,(2) The Laplacian-of-Gaussian (LoG) Detector 1 Laplacian filter Laplacian算子具有旋轉不變性，但對噪聲很敏感，因此常需進行平滑操作 2 LoG filter 高斯濾波平滑，然后拉普拉斯濾波。,Laplacian-of-Gaussian (LoG)尺度空間的局部極大值點,1.2 尺度不變特征檢測,(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 尺度不變特征檢測,(4) The Harris-Laplacian Detector 1 初始化：多尺度下的Harris角點檢測 2 基于Laplacian的尺度選擇,Harris points,Harris-Laplacian points,1.2 尺度不變特征檢測,(5) The Hessian-Laplace Detector 思想與Harris-Laplacian Detector相同,圖：Hessian-Laplace算子應用于具有尺度改變的影像結果,圖：Harris-Laplace算子在同一場景下不同尺度的兩幅影像上特征檢測結果，圓的半徑代表了特征尺度大小,一. 特征匹配過程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測 1.3 仿射不變特征檢測 1.4 特征提取總結 2 特征描述 3 特征匹配 二. SIFT算法,1.3 仿射不變特征檢測,Harris/Hessian Affine,給定一組由Harris-Laplace算子得到其尺度特征的初始點，用橢圓形區(qū)域獲得仿射不變性。具體處理步驟如下： (1)由Harris-Laplace算子獲得興趣點初始區(qū)域 (2)由二階矩矩陣估計區(qū)域仿射形狀 (3)歸一化仿射區(qū)域成為圓形區(qū)域 (4)在歸一化的影像上重新檢測新的位置和尺度 (5)如果二階矩矩陣的特征值在新的點上不相等，則轉(2),圖：利用二階矩矩陣的特征值估計興趣點區(qū)域的仿射形狀，變換是用該矩陣的平方根進行的，經過歸一化的圖像XL和XR之間的變換是旋轉變換關系，只取決于一個旋轉因子，因子大小代表了特征值的比率,圖：Harris-Affine算子檢測的從不同視角得到的結果圖,圖：Hessian-Affine算子得到的不同視圖下的影像檢測結果,一. 特征匹配過程 1 特征提取 1.1 Harris and Hessian Detector 1.2 尺度不變特征檢測 1.3 仿射不變特征檢測 1.4 特征提取總結 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,一. 特征匹配過程 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,一. 特征匹配過程 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 描述特征點鄰域的最簡單方法是直接將鄰域的像素灰度強度構成特征向量。 用相關系數(shù)估計兩個描述子 的相似程度 缺點： 1 對位置，尺度，姿態(tài)的變化敏感 2 弱區(qū)分性,(2) Moment invariants 1962年Hu提出了圖像識別的不變矩理論，即圖像的7個不變矩具有平移、旋轉、比例不變性。為圖像識別建立了一種統(tǒng)計特征提取方法，得到了廣泛應用。 以下7個對平移、旋轉和尺度變換不變的矩是由歸一化的二階和三階中心矩得到的：,(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”(一系列導數(shù)向量) 影像I在點X處的N階local jet定義為：, steerable filters,Which steer derivatives in a particular direction given the components of the local jet,影像導數(shù) 由高斯導 數(shù)的卷積 來獲得。,(a)高斯導數(shù)到4階,(b)6階復數(shù)濾波(complex filters),“l(fā)ocal jet”,L(x,)是由高斯導數(shù)和影像卷積而成,旋轉不變,(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,見后面講解,一. 特征匹配過程 1 特征提取 2 特征描述 3 特征匹配 二. SIFT算法,3 特征匹配,3.1 基于局部灰度信息的特征匹配方法 局部區(qū)域灰度統(tǒng)計特性 3.2 基于特征向量的特征匹配方法 特征向量之間的距離 （1）歐氏距離 （2）馬氏距離,k-d樹是二叉檢索樹的擴展，k-d樹的每一層將空間分成兩個。樹的頂層結點按一維進行劃分，下一層結點按另一維進行劃分，以此類推，各個維循環(huán)往復。劃分要使得在每個結點，大約一半存儲在子樹中的點落入一側，而另一半落入另一側。當一個結點中的點數(shù)少于給定的最大點數(shù)時，劃分結束。,K-d 樹,一.