[發明專利]一種直接提取的k個最近鄰點搜索方法

有效

• 申請號: 201310717019.3
• 申請日: 2013-12-23
• 公開（公告）號: CN103744886A
• 公開（公告）日: 2014-04-23
• 發明（設計）人: 肖曉萍;李自勝
• 申請（專利權）人: 西南科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 成都九鼎天元知識產權代理有限公司 51214
• 代理人: 卿誠;吳彥峰

1.一種直接提取的k個最近鄰點搜索方法，其特征在于包括：載入模型的點云數據，針對點云數據中任意一點，從其反最近鄰點的最近鄰點中提取k1個最近鄰點，然后通過KNN算法搜索的最近鄰點中k-k1個最近鄰點，所述最近鄰點有k個最近鄰點，其中k是正整數，k1≤k。

2.根據權利要求1所述的一種直接提取的k個最近鄰點搜索方法，其特征在于所述從q_head的最近鄰點中提取k1個最近鄰點，然后通過KNN算法搜索q_head的最近鄰點中k-k1個最近鄰點具體步驟包括：

步驟1：根據模型的點云數據，建立點云數據鏈表PCDPointLink，q_head是點云數據中任意一點，pcdPoint是PCDPointLink中的一個節點，鏈表中的第一個節點指針為head，令鏈表遍歷變量q_head=PCDPointLink→head，即用變量指針q_head指向鏈表的第一個節點，q_head的最近鄰點集合kNN(q_head)、q_head的反最近鄰點集合rkNN(q_head)、指向下一個節點的指針Next，q_head與最近鄰點的最大距離d_max；

步驟2：判斷q_head的k個最近鄰點集合kNN(q_head)是否為空，若kNN(q_head)為空，則執行步驟3;否則，執行步驟7；

步驟3：判斷rkNN(q_head)是否為空，若rkNN(q_head)為空，則采用KNN算法進行搜索；否則，令遍歷變量q_data=rkNN(q_head)→head，計數變量k1=0，執行步驟4；

步驟4：判斷kNN(q_data)是否為空，若kNN(q_data)為空，則從q_head的反最近鄰點集合的下一個點去提取，因此q_data=q_data→Next,重復步驟4；若kNN(q_data)不為空，令遍歷變量p_data=kNN(q_data)→head,執行步驟5；

步驟5：判斷q_head的最近鄰點是否為p_data，若p_data是q_head的最近鄰點，則將p_data加入到q_head的最近鄰點集合中，將q_head加入到p_data的k個反最近鄰點集合，同時k1=k1+1；否則，p_data不是q_head的最近鄰點，則需要判斷q_data的最近鄰點集合中的下一個點，因此p_data=p_data→Next,并重復步驟5;

步驟6：當步驟5中，q_head的所有反近鄰點的遍歷完了后，比較k1與k的關系，如果k1<k，則q_head提取的最近鄰點個數不足k個，通過KNN算法為q_head點搜索k-k₁個最近鄰點，將q_head的k1個最近鄰點加入到集合kNN(q_head)中，將q_head加入到剩余的k-k₁個最近鄰點的反最近鄰點集合rkNN(p_i)中，其中p_i表示通過KNN算法搜索得到的k-k₁個最近鄰點；如果k1=k，說明算法為q_head直接提取到了k個最近鄰點，執行步驟7；

步驟7：q_head=q_head→Next，讓q_head指向鏈表PCDPointLink下一個節點，重復步驟2到步驟6，得到q_head的k個最近鄰點kNN(q_head)。