[發明專利]一種基于空間索引及相鄰點信息的最近鄰點搜索方法

在審

• 申請號: 202010012526.7
• 申請日: 2020-01-07
• 公開（公告）號: CN113157688A
• 公開（公告）日: 2021-07-23
• 發明（設計）人: 余艷梅;杭鵬程;陶青川
• 申請（專利權）人: 四川大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明針對最近鄰點搜索在點的坐標為非整數時實現較困難的問題，提出了一種基于空間索引及相鄰點信息的最近鄰點搜索方法；主要發明內容包括創建所有散點的空間索引；在當前點的周圍近似搜索最近鄰點；進一步精確搜索最近鄰點；利用先前點的已知的最近鄰點簡化搜索過程。本發明所提的方法應用于圖像插值時，能夠有效地提高圖像質量。

技術領域

本發明涉及最近鄰搜索，尤其是涉及一種基于空間索引及相鄰點信息的最近鄰點搜索方法。

背景技術

隨著互聯網和多媒體技術的飛速發展，海量數據的產生和共享在日常生活中已經司空見慣。最近鄰搜索是大數據處理中基礎的問題之一，它在機器學習、圖像處理等領域有廣泛的應用。其主要流程是對數據預處理并建立索引，從而可以高效地找到和指定查詢最接近的數據對象。

最近鄰搜索就是根據數據的相似性，從數據庫中尋找與目標數據最相似的項目。這種相似性通常會被量化到空間上數據之間的距離，即數據在空間中的距離越近，則數據之間的相似性越高。

最近鄰搜索一般根據其查詢的精確度不同可分為精確查詢與近似查詢兩類：精確查詢一般應用于維度較低的數據，最簡單的方法是線性掃描，也就是平常所說的窮舉搜索，在數據庫中依次計算樣本與所查詢數據之間的距離，抽取出所計算出來的距離最小的樣本即為所要查找的最近鄰；近似查詢類似于近似解法，具體的算法基本上都是基于哈希算法，就是把任意長度的輸入，通過散列算法，變換成固定長度的輸出，該輸出就是散列值。簡單來說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

在圖像插值中，選擇距離待插值點距離越近的點作為插值點，圖像插值的效果越好，因此最近鄰搜索被運用于其中。但當圖像上的點坐標為非整數時，一般方法很難實現最近鄰搜索。如何在這種情況下實現最近鄰搜索，仍然是需要繼續研究的一個方向。

發明內容

針對最近鄰點搜索在點的坐標為非整數時實現較困難的問題，本發明提出一種基于空間索引及相鄰點信息的最近鄰點搜索方法。

本發明提出了一種基于空間索引及相鄰點信息的最近鄰點搜索方法，該方法通過空間索引找到最近的插值點，同時利用先前點的近鄰點來加速搜索。本發明所提的方法在保證被搜索到的最近鄰的準確性的同時，進一步減少整個過程的耗時。

本發明具體過程包括以下步驟：

為找到當前點G的k個最近鄰點，以整張散點圖(即圖中的點的坐標多為非整數)的中心為原點，用坐標軸網格將整張圖分成若干個小正方形區域，用位于每個網格左上角的格點(在直角坐標系中橫縱坐標為整數的點稱為“格點”)的坐標作為索引來檢索該網格區域內的各散點的所有信息(包括x、y坐標信息和其他信息)，也即各散點的所有信息被存儲在該網格左上角格點中。

(1)如果當前點G是每行的起始點，采用基于坐標空間的搜索：搜索范圍是以G為中心的正方形，正方形的半徑從1開始不斷增加，直到找到k個存有信息的格點后，將它們的坐標記錄在格點表中；

提取出k個格點中存儲的散點位置信息(x₁,y₁)、(x₂,y₂)……(x_k,y_k)，計算各(x,y)與點G的歐氏距離并求得其最大值d_max1，對d_max1通過公式(1)向上取整計算下一步的精確搜索正方形的半徑R₁：

接著開始精確搜索：在以G為中心、半徑為R₁的正方形區域內進行徹底搜索，為提高速度，只檢查該范圍內尚未被搜索過的格點是否存有散點信息；

計算這些存有信息的散點的位置(x,y)與點G的歐氏距離，并與精確搜索之前找到的k個散點到點G的歐氏距離進行比較，選出k個最近鄰點；