圖像的特征點匹配概述
特征點匹配原理
如果提取的兩個特征點描述矢量間距離很小伐弹，這兩個特征點在對應場景的同一位置，特征點匹配技術就是利用這個原理惨好，從兩組特征點集合中找到兩輛距離最近的特征點匹配對，這個匹配對對應的是場景同一個位置蔓腐。
特征點匹配問題可以歸結為一個通過<font color=blue>距離函數</font>在高維矢量之間進行相似性檢索的問題龄句。針對度量空間設計的索引結構算法在進行相似度查詢時只利用了距離函數的三角不等式性質散罕，所以使用更加普遍傀蓉。
特征匹配算子
- 窮舉法: 將數據集中的點與查詢點逐一進行距離比較。所以優(yōu)點是不需要進行任何的數據預處理硫椰，操作也很簡單萨蚕。但是它沒有利用數據集本身蘊含的任何結構信息，搜索效率相對較低岳遥。
- <font color=blue>建立數據索引</font>:先進行預處理即建立數據索引浩蓉，然后在進行快速匹配。因為實際數據一般都會呈現(xiàn)出簇狀的聚類形態(tài)捻艳，他通過設計有效的索引結構可以大大加快檢索的速度。
索引結構的算法舉例
- 索引樹結構：對搜索空間進行層次劃分绅络，如果劃分出的空間沒有重疊叫Clipping法嘁字，比如<font color=blue>K-d樹</font>，如果有重疊叫Overlapping法衷恭，比如R-樹
- Hash法
- 空間填充曲線法
相似性查詢的方式
索引結構中相似性查詢有兩種基本方式：
- 范圍查詢：從數據集中找出所有與查詢點距離小于給定距離閾值的數據纯续。
- <font color=blue>k-近鄰查詢</font>：從數據集中找到距離查詢點最近的k個數據，當k=1時牙丽，它就是最近鄰查詢兔魂。
kd-樹算法
kd-樹是對數據點在k維空間中劃分的一種數據結構举娩。是一個二叉樹构罗，每個節(jié)點表示的是一個空間范圍智玻。
構建二叉樹
kd-樹種每個結點的數據類型，kd-樹是一種二叉排序樹
節(jié)點數據結構
| 字段 | 數據類型 | 描述 |
|---|---|---|
| Node-data | 數據矢量 | 數據集中某個數據點,是n維矢量 |
| Range | 空間矢量 | 該節(jié)點所代表的空間范圍 |
| split | 整數 | 確定分割左右子節(jié)點的那個維度 |
| left | 左子樹 | 這棵樹上的data都小于Node-data |
| right | 右子樹 | 這棵樹上的data都大于Node-data |
構建kd樹的流程圖
start=>start: 特征點數據集
op1=>subroutine: 展開kd-樹
start->op1
op2=>operation: 選擇最大方差的維數賦給split
op1->op2
op3=>operation: 選取split維的中值作為閾值根節(jié)點
op2->op3
con=>condition: 數據小于中值
op3->con
op4=>operation: 左子樹特征數據
op5=>operation: 右子樹特征數據
sub1=>subroutine: 展開左子樹
sub2=>subroutine: 展開右子樹
con(yes)->op4->sub1
con(no)->op5->sub2
