章昕燁 童衛(wèi)青 李海晟

摘要：既有的圖像特征匹配算法比較適合于一般分辨率的圖像，且是在灰度圖像上進(jìn)行的.洞窟壁畫圖像的特點是分辨率非常高，并且還可能存在具有相同灰度紋理和不同顏色的區(qū)域.針對這類特殊圖像，提出了一種面向高分辨率壁畫圖像的高速化特征匹配算法（簡稱NeoKPM算法）.NeoKPM算法有2個主要特點：①通過降采樣圖像獲得原圖像粗配準(zhǔn)的單應(yīng)變換矩陣，極大地降低了后續(xù)特征匹配的時間復(fù)雜度;②提出了一種基于灰度和顏色不變量的特征描述符，能很好地區(qū)分具有相同灰度紋理和不同顏色的特征點，提高了特征匹配的正確性.在實際壁畫圖像庫上，對NeoKPM算法的性能進(jìn)行了實驗.實驗結(jié)果表明，NeoKPM算法在分辨率為8 000萬像素的壁畫圖像上，其每對圖像的正確匹配點數(shù)量平均比SIFT（Scale Invariant Feature Transform）算法高出了近10萬個;其特征點匹配平均處理速度是SIFT算法的20倍;其基于圖像單個像素的雙圖像平均誤差小于0.04像素.

關(guān)鍵詞：壁畫數(shù)字化;特征匹配;暴力匹配;顏色不變量

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：ADOI：10.3969/j.issn.l000-5641.2021.06.008

A fast key points matching method for high resolution images of a planar mural

ZHANG Xinye1，TONG Weiqing1，2，LI Haisheng1

（1. School of Computer Science and Technology. East China Normal University，Shanghai 200062. China;

2. Shanghai Commercial Digital Printing Co.，Ltd. Shanghai 200041，China）

Abstract：Existing methods of key points matching were invented for grayscale images and are not suitable for high resolution images. Mural images typically have very high resolution，and there may be areas with the same gray textures and different colors. For this special kind of image，this paper proposes a high-speed algorithm of key points matching for high-resolution mural images （NeoKPM for short）. NeoKPM has two main innovations：（1）first，the homography matrix of rough registration for the original image is obtained by downsampling the image，which substantially reduces the time required for key points matching;（2）second，a feature descriptor based on gray and color invariants is proposed，which can distinguish different colors of texture with the same gray level，thereby improving the correctness of key points matching. In this paper，the performance of the NeoKPM algorithm is tested on a real mural image library. The experimental results show that on mural images with a resolution of 80 million pixels，the number of correct matching points per pair of images is nearly 100 000 points higher than that of the SIFT （Scale Invariant Feature Transform）algorithm，the processing speed of key points matching is more than 20 times faster than that of the SIFT algorithm，and the average error of dual images based on a single pixel of theimage is less than 0.04 pixels.

Keywords：mural digitizing;key points matching;brute force matching;color invariance

0引言

洞窟壁畫是人類的藝術(shù)瑰寶，數(shù)字化保存是其重要的保護(hù)方法.根據(jù)我國國家文物局關(guān)于古壁畫的一級影像采樣分辨率不低于300 DPI（Dots Per Inch，每英寸點數(shù)）的技術(shù)要求[1]，目前任何高分辨率的相機(jī)都無法通過拍攝一幅圖像來保存大幅面的洞窟壁畫.因此，一般采用劃分壁畫采集區(qū)塊的方法，即把一幅大幅面的壁畫劃分成n×m大小的有重疊的采集區(qū)塊，然后對每一區(qū)塊用高分辨率相機(jī)進(jìn)行拍攝，再通過圖像拼接方法把這些采集區(qū)塊的圖像（一般有上百幅圖像）拼接成一幅全景圖像.圖像拼接的主流方法是通過尋找圖像匹配點，然后通過匹配點把圖像對齊后實行拼接處理.為此，如何找到2幅圖像的穩(wěn)定而可靠的特征點，并進(jìn)行有效的特征點匹配是圖像拼接中非常重要的處理環(huán)節(jié)，因為這直接影響著圖像拼接的精度和效果.

特征點匹配包括3個處理過程：圖像特征點檢測、圖像特征點描述和圖像間的特征點匹配.關(guān)于特征點檢測和描述的研究比較成熟，經(jīng)典的方法有SIFT[2]算法、MSER（Maximally Stable Extremal Region）[3]算法、SURF（Speeded-Up Robust Features）[4]算法、ORB（Oriented FAST （Features from Accelerated Segment Test）and Rotated BRIEF （Binary Robust Independent Elementary Features））[5]算法等.文獻(xiàn)[6]對主流的特征點檢測算法做了全面的比較研究后指出，SIFT算法在旋轉(zhuǎn)和尺度不變性方面是最好的.主流的特征點檢測算法主要適用于灰度圖像，也就是說這些算法都沒有考慮如何處理具有相同灰度紋理卻有著不同色彩信息的圖像.MSER算法在理論上可以直接檢測到彩色圖像的特征斑點，但其檢測性能比從灰色圖像檢測要差許多.CSIFT （Colored SIFT）[7]算法是為了解決能從彩色圖像上直接檢測特征點而被提出來的，該算法通過把彩色圖像變換為基于顏色不變量的灰度圖像[8]，從而類似SIFT算法一樣實現(xiàn)了彩色圖像的特征檢測和描述.由于基于顏色不變量的灰度圖像紋理比彩色圖像的紋理要粗糙很多，所以導(dǎo)致了CSIFT算法檢測出來的特征點數(shù)量比用SIFT算法檢測出來的數(shù)量要少很多，而特征點數(shù)量又對后續(xù)的特征點匹配的精度影響比較大.與利用線性高斯金字塔來構(gòu)建多尺度空間以檢測關(guān)鍵特征點的SIFT算法和SURF算法不同，KAZE[9]算法采用加性算子分裂（Additive Operator Splitting，AOS）算法來進(jìn)行非線性的擴(kuò)散濾波，從而構(gòu)造出非線性尺度空間，具有比較好的特征點可重復(fù)檢測特性，但是也付出了高昂的計算成本.在后續(xù)研究中雖然提出了加速版的A-KAZE（Accelerated KAZE）[10]，但其特征檢測性能不如KAZE，其尺度不變性不如SIFT魯棒，不太適合應(yīng)用于高分辨的壁畫圖像.相較于SIFT利用高斯差分（Difference of Gaussians，DoG）算子檢測特征點，2020年Cho等[11]提出了一種特征檢測算法，該算法引入了高斯拉普拉斯（Laplacian of Gaussian，LoG）算子及其高階導(dǎo)數(shù)（HLoG）來構(gòu)造尺度空間，并對其特征檢測進(jìn)行了實驗驗證，取得了比較好的結(jié)果;但該算法對具體圖像的參數(shù)確定比較困難，穩(wěn)定性方面也存在問題，因而還達(dá)不到實用的要求.在深度學(xué)習(xí)領(lǐng)域中，近幾年也提出了一些新穎的特征檢測和描述算法[12-14]，但這些算法存在著兩個棘手問題：一是需要大量的訓(xùn)練樣本;二是泛化性還沒有解決，所以暫時還不適合應(yīng)用于樣本非常稀缺的洞窟壁畫上.

特征點匹配可以分為初匹配和匹配驗證兩個階段：第一階段比較主流的初匹配方法是暴力匹配法（Brute Force Matching，BFM），該方法對每個特征點生成一個特征描述向量（也稱特征描述符），對每個特征點用全遍歷方式從另一幅圖像里尋找與該特征點的特征向量最相似的特征點作為其匹配點對;第二階段的匹配驗證的目的是消除在初匹配中的誤匹配點對，通常使用隨機(jī)抽樣一致算法（Random Sample Consensus，RANSAC）[15]和最小二乘方回歸算法（Least Median of Squares，LMedS）[16].

從理論角度來說，如果初匹配中野點數(shù)（離群點）與內(nèi)點數(shù)之比較高時（一般為大于50%），那么基于上述兩種算法驗證后的匹配精度就會降低，甚至很差.后來又相繼提出了一些改進(jìn)的方法，例如，F(xiàn)otouhi等[17]根據(jù)特征描述最相近與次相近的匹配點之間的距離比來構(gòu)造一組可靠的特征匹配點，并用這些基準(zhǔn)點來區(qū)分正確點和離群點;Lin等[18]根據(jù)正確匹配點之間的相干性（Coherence Property），再通過一種非線性回歸的方法來去除離群點;Chou等[19]提出了一種分兩階段進(jìn)行抽樣和平面投票的匹配法，用于剔除離群點.但是這些方法幾乎都是針對驗證處理，不能減少第一階段的無效匹配，只能消除錯誤的對應(yīng)關(guān)系.另外，通過實驗還發(fā)現(xiàn)，在特征點匹配處理中，暴力匹配的計算時間成本占據(jù)了整個處理過程的80%.

根據(jù)以上分析，本文解明了目前圖像特征點匹配的主流算法中存在的問題：①特征點檢測算法對灰度圖像比較有效，但對彩色圖像效果不好;②初匹配的時間消耗占整個圖像匹配過程的80%左右;③當(dāng)野點較多時，RANSAC算法的效果會明顯下降.上述這些問題，當(dāng)2幅圖像的分辨率不高時，其對圖像拼接精度的影響基本上顯現(xiàn)不出來;但對大幅面壁畫圖像拼接來說，其對拼接精度和時間復(fù)雜度的影響就非常顯著了.

既有的圖像特征點匹配算法比較適合于一般分辨率的圖像，且是在灰度圖像上進(jìn)行的.洞窟壁畫圖像的特點是分辨率非常高，并且可能存在具有相同灰度紋理而顏色不同的區(qū)域.針對這類特殊圖像，本文提出了一種面向大幅面、高分辨率壁畫圖像的高速化特征點匹配算法（簡稱NeoKPM算法）. NeoKPM算法有2個主要特點：①通過降采樣圖像獲得原圖像粗略配準(zhǔn)的單應(yīng)變換矩陣，極大地降低了后續(xù)特征點匹配的時間復(fù)雜度;②提出了一種基于灰度和顏色不變量的特征描述符，它能很好地區(qū)分具有相同灰度紋理不同顏色的特征點，提高了特征點匹配的正確性.

在實際人工壁畫圖像庫上，本文對NeoKPM算法的性能進(jìn)行了實驗.實驗結(jié)果表明，NeoKPM算法在分辨率為8000萬像素的壁畫圖像集上，其每對圖像的正確匹配點數(shù)量平均比SIFT算法高出近10萬個，其特征點匹配處理速度是SIFT算法的20倍，其基于圖像單個像素的雙圖像平均誤差小于0.04像素.

1NeoKPM算法

本章首先給出NeoKPM算法的原理和整個算法，然后用實驗考察降采樣率與圖像配準(zhǔn)誤差的關(guān)系，最后敘述顏色不變量在特征匹配中的作用.

1.1原理和算法

特征點匹配是圖像拼接中的關(guān)鍵處理環(huán)節(jié)，匹配準(zhǔn)確與否對后續(xù)無論是2維拼接還是3維重建都是至關(guān)重要的.本文提出的匹配算法分為特征粗匹配和特征精匹配兩個階段.

由于采集的原始壁畫圖像具有很高的分辨率（一般在8000萬像素以上），而既有的特征點匹配算法對這類圖像處理的時間復(fù)雜度很高（一般需要幾小時），其原因是高分辨率圖像會檢測出大量特征點，而特征點的匹配是采用暴力匹配法.為了提高特征匹配的速度，必須考慮把圖像的分辨率大幅度下降，但是分辨率下降的圖像又會影響特征匹配的精度.為了克服這一矛盾，我們先對2幅輸入圖像進(jìn)行降采樣處理.根據(jù)1.2節(jié)中的實驗數(shù)據(jù)，按10%的降采樣率進(jìn)行降采樣后的圖像（即比原圖像縮小了100倍）所獲得的平均配準(zhǔn)誤差在1像素左右，但其處理時間大幅度下降（約下降20倍）.為此，第一階段，先通過降采樣圖像獲得原圖像的單應(yīng)變換矩陣，即特征粗匹配;第二階段，先檢測出2幅輸入圖像的特征點，然后利用特征粗匹配的單應(yīng)變換矩陣來確定每個目標(biāo)圖像中的每個匹配點在參考圖像中的對應(yīng)位置，而后在一個5×5的矩形區(qū)域內(nèi)，搜索其匹配點，這樣就可以獲得既高速又高精度的特征點匹配.

下面給出完整的NeoKPM算法.

第一階段特征點粗匹配

（1）對輸入的2幅重疊圖像（分別為目標(biāo)圖像和參考圖像，目的是用目標(biāo)圖像去配準(zhǔn)參考圖像）進(jìn)行降采樣處理（一般降采樣率為10%，即對原始圖像縮小100倍），分別輸出目標(biāo)圖像的降采樣圖像T和參考圖像的降采樣圖像R.

（2）根據(jù)2幅圖像拍攝時的重疊率（對于同一幅壁畫，其拍攝重疊率是固定的）估算降采樣圖像T和降采樣圖像R間的粗略平移量和重疊區(qū)域，并依據(jù)圖像重疊率計算后續(xù)匹配模板的大小.

（3）在降采樣圖像T的重疊區(qū)域中央，選取指定大小的矩形區(qū)域作為匹配模板，在降采樣圖像R的重疊區(qū)域內(nèi)搜索與匹配模板最相似的區(qū)域的位置，據(jù)此得到降采樣圖像T和降采樣圖像R間的最大平移量.

（4）分別生成降采樣圖像T和降采樣圖像R的灰度圖像和顏色不變量圖像.

（5）分別從降采樣圖像T和降采樣圖像R的灰度圖像中檢測出SIFT特征點.

（6）根據(jù)SIFT特征點的位置，分別從降采樣圖像T和降采樣圖像R的灰度圖像與顏色不變量圖像中抽出基于SIFT描述符的聯(lián)合特征向量.

（7）對降采樣圖像T中每個特征點，根據(jù)最大平移量可以估計出它在降采樣圖像R_s上的對應(yīng)矩形范圍，然后進(jìn)行基于聯(lián)合特征向量的特征點匹配搜索，找到其對應(yīng)的匹配點.

（8）找到2幅圖像中對應(yīng)的點對集合，再根據(jù)降采樣圖像與原圖像之間的幾何關(guān)系，將降采樣圖像坐標(biāo)系下的匹配點集合中的所有特征點映射到原圖像坐標(biāo)系下，利用RANSAC算法估計原分辨率圖像間的初始單應(yīng)變換矩陣H，從而獲得目標(biāo)圖像和參考圖像間的單應(yīng)變換關(guān)系.

第二階段特征點精配準(zhǔn)

（9）對2幅輸入圖像分別生成參考圖像與目標(biāo)圖像的灰度圖像和顏色不變量圖像，記參考圖像的灰度圖像、目標(biāo)圖像的灰度圖像、參考圖像的顏色不變量圖像、目標(biāo)圖像的顏色不變量圖像分別為T、R、T、R.

（10）分別在圖像T、R上檢測其SIFT特征點.

（11）在目標(biāo)圖像的灰度圖像以及顏色不變量實數(shù)圖上，計算所有特征點的SIFT特征向量，然后把每個特征點的灰度特征向量和顏色不變量特征向量拼接成256維的聯(lián)合SIFT特征向量.

（12）在參考圖像的灰度圖像以及顏色不變量實數(shù)圖上，計算所有特征點的SIFT特征向量，然后把每個特征點的灰度特征向量和顏色不變量特征向量拼接成256維的聯(lián)合SIFT特征向量.

（13）對目標(biāo)圖像和參考圖像里的特征點按以下步驟進(jìn)行初匹配處理：對圖像T中每個特征點，根據(jù)第一階段得到的圖像粗配準(zhǔn)的單應(yīng)變換矩陣H可以估計出它在圖像R上位置;然后在以該位置為中心的5×5矩形范圍內(nèi)，用其對應(yīng)的聯(lián)合SIFT特征向量的相似度來尋找匹配點.

（14）用RANSAC算法對上述找到的所有匹配點進(jìn)行篩選，獲得真匹配點集合，然后根據(jù)這些真匹配點集合計算目標(biāo)圖像和參考圖像間的單應(yīng)變換矩陣H，完成輸入圖像的特征點匹配.

1.2圖像降采樣率與特征點匹配精度

當(dāng)前特征點的初匹配幾乎都是通過基于特征描述符距離的暴力匹配方法來完成的，其計算時間取決于圖像特征點的數(shù)目.SIFT特征點是在多尺度空間下的局部極值點[2]，其數(shù)量與圖像的尺寸和紋理復(fù)雜度相關(guān)聯(lián).在超高分辨率（一般在8 000萬像素以上）的原始壁畫圖像上檢測出的SIFT特征點數(shù)量可達(dá)到百萬級別，也就是說暴力匹配法需要計算多維特征向量距離的次數(shù)將高達(dá)萬億次，實驗中實際測得的處理時間約為3 h.圖像分辨率的減小會直接影響像素層級進(jìn)而導(dǎo)致原圖像紋理被壓縮，部分特征點將無法被檢測出來.表1所示為，對分辨率為（10 288×7 730）像素的超分辨壁畫圖像進(jìn)行多次降采樣處理后，降采樣圖像上檢測出的SIFT特征點數(shù)量的變化情況.表1的數(shù)據(jù)表明，特征點的數(shù)量隨著降采樣率的增大而顯著減少.

降低圖像分辨率可以大幅度降低特征匹配的時間復(fù)雜度，但同時也會影響特征匹配的精度.為了解決這一問題，需要對降采樣率與特征點匹配精度之間的關(guān)系進(jìn)行實驗考察：首先，對圖像庫A（見2.1節(jié)的圖像庫說明）中的所有參考圖像和目標(biāo)圖像分別按5%的遞減步長進(jìn)行降采樣;然后對降采樣后的參考圖像和目標(biāo)圖像，分別計算各個降采樣圖像以及原圖像的特征點匹配的處理時間和誤差.本文參考的基準(zhǔn)算法是SIFT，實驗中，基于圖像庫A中已知的單應(yīng)變換矩陣計算降采樣圖像和原圖像的特征點匹配誤差，并以兩者的相對雙向平均誤差來衡量因降采樣所產(chǎn)生的特征點匹配誤差.

表2所示是對圖像庫A中100對圖像進(jìn)行降采樣性能考察的實驗結(jié)果.實驗結(jié)果表明，在降采樣率為10%時，降采樣圖像的特征點匹配誤差與原圖像特征點匹配誤差的相對雙向平均誤差為0.82像素，降采樣圖像的平均匹配時間約為1.0s（原圖像的平均匹配時間為4 544s，約為原分辨率圖像特征點匹配時間的萬分之三）.

為了進(jìn)一步驗證上述實驗結(jié)論的一般性，本文對與圖像庫A中具有不同分辨率和紋理的另外200幅壁畫圖像進(jìn)行了相同的實驗，實驗結(jié)果如表3所示.從表3可知，在降采樣率為10%時，其特征點匹配誤差與原圖像的特征點匹配誤差的相對雙向平均誤差保持在1像素左右，降采樣圖像的平均匹配時間約為0.69s（原圖像的平均匹配時間為139.80 s，約為原分辨率圖像特征點匹配時間的千分之五）.根據(jù)以上兩個實驗數(shù)據(jù)，本外文認(rèn)為對高分辨率的圖像取10%的降采樣率比較合適.

1.3顏色不變量

顏色是區(qū)分圖像紋理差異的重要信息，與視角、光照方向、光照強(qiáng)度、表面方向和菲涅爾反射系數(shù)等因素高度關(guān)聯(lián).這些因素導(dǎo)致了目標(biāo)物體上具有相同顏色的區(qū)域，但在圖像中卻呈現(xiàn)出顏色略微不同的幾個區(qū)域.為了解決這個問題，Geusebroek等[8]提出了公式（1）和公式（2）所示的顏色不變量H，公式具體為

公式（1）和公式（2）中，E、E、E分別是光譜能量、光譜能量的一次導(dǎo)數(shù)和光譜能量的二次導(dǎo)數(shù)，R、G、B是目標(biāo)物的顏色.Geusebroek等證明了在等能量的不均勻光照條件下，顏色不變量H是一個獨立于視角、光照方向、光照強(qiáng)度、表面方向和菲涅爾反射系數(shù)的物體反射不變量.

為了解明基于灰度信息和顏色不變量H的聯(lián)合SIFT特征向量（簡稱GHIFT特征向量）對顏色變化的辨別能力，本文設(shè)計了如下實驗方案.

（1）從圖像庫D中讀取1幅圖像，按照圖1（a）的方式拼接成上下2幅相同的圖像，并把該拼接后的圖像作為參考圖像，復(fù)制參考圖像得到目標(biāo)圖像.

（2）用SIFT算法分別從參考圖像和目標(biāo)圖像上檢測特征點.

（3）實驗中，始終保持參考圖像和目標(biāo)圖像的上半部不變，在保持灰度值I=0.3R+0.59G+0.11B基本不變的條件下，6次隨機(jī)改變目標(biāo)圖像下半部顏色的R、G、B分量值，并保證R、G、B分量值中至少有1個值的變化絕對值分別不小于5%、10%、15%、20%、25%、30%.

（4）每次目標(biāo)圖像的下半部的顏色發(fā)生變化時，用前面介紹過的聯(lián)合SIFT特征向量進(jìn)行特征點匹配處理，獲得當(dāng)前2幅圖像的匹配點數(shù)量.

（5）將當(dāng)前2幅圖像的匹配點數(shù)與原來2幅圖像的特征點數(shù)進(jìn)行比較，從而考察該顏色不變量的聯(lián)合SIFT特征向量對顏色變化的敏感度.

理論上，當(dāng)顏色沒有變化時，參考圖和目標(biāo)圖是完全一樣的，并且每幅圖的上半部與下半部也是完全相同的，因此，目標(biāo)圖上的每個特征點都可以在參考圖上找到2個匹配點;當(dāng)目標(biāo)圖的下半部的顏色變化時，目標(biāo)圖上的每個特征點都只能在參考圖上找到1個匹配點.

對圖像庫D（見2.1節(jié)的圖像庫說明）的100幅圖像進(jìn)行了實驗.實驗結(jié)果表明，基于灰度信息的SIFT特征向量不能去除下半部誤匹配點;而基于聯(lián)合SIFT特征向量幾乎可以去除所有下半部誤匹配點，如圖1（b）所示.圖2是顏色變化從5%變到30%時，聯(lián)合SIFT特征向量對誤匹配點的去除比例，其中橫軸表示顏色變化的比例，縱軸表示聯(lián)合SIFT特征向量對誤匹配點的去除能力.

2實驗評估

實驗環(huán)境為，Core i7-8700k處理器，32 GB內(nèi)存;Windows 10操作系統(tǒng);開發(fā)工具為Visual Studio 2015 community;使用OpenCV3.3.0.

2.1實驗圖像庫的制作

本文所有圖像庫的原始圖像均來自新疆龜茲洞窟的實際壁畫.

2.1.1圖像庫A

圖像庫A包含100對重疊圖像（即200幅圖像），其中100幅是原始壁畫圖像，記為參考圖像集（圖3（a）），A里有33幅分辨率為（10288×7730）像素的圖像，其余67幅圖像的分辨率為（5087×3703）像素.根據(jù)不同的單應(yīng)變換矩陣，將A里的每一幅圖像分別生成其對應(yīng)的重疊圖像，記為目標(biāo)圖像集A，如圖3（b）所示.

2.1.2圖像庫B

圖像庫B由50對具有不同重疊率的圖像組成（即100幅圖像），其中10對圖像的分辨率為（10288×7730）像素，其余40對圖像的分辨率為（5087×3703）像素.這100幅圖像中50幅是原始壁畫圖像，記為參考圖像集B（圖3（c））;另外的50幅是與B中有部分重疊的壁畫圖像，記為目標(biāo)圖像集B（圖3（d））.

2.1.3圖像庫C

圖像庫C由200幅圖像構(gòu)成：從圖像庫A的參考圖像集A中，采用定位截取的方式構(gòu)造100幅大小為（640×480）像素的圖像，記為參考圖像集C（圖3（e））;另外100幅圖像是由C根據(jù)不同的單應(yīng)變換矩陣分別生成的，記為目標(biāo)圖像集C（圖3（f））.

2.1.4圖像庫D

從圖像庫A中的33幅分辨率為（10288×7730）像素的壁畫圖中，采用定位截取的方式截取100幅分辨率為（1 024×512）像素、紋理較為豐富的圖像作為圖像庫D，如圖3（g）所示.

2.2NeoKPM算法與SIFT算法、SURF算法、ORB算法和SC-RANSAC算法的性能比較

本節(jié)的實驗?zāi)康氖菍eoKPM算法與特征點匹配的經(jīng)典算法SIFT、SURF、ORB和在匹配驗證階段做出最新改進(jìn)的SC-RANSAC（Spatial Consistency RANSAC）[17]進(jìn)行比較，考察NeoKPM算法在特征匹配的時間、特征匹配點的數(shù)量和特征匹配的誤差方面的性能.

2.2.1在圖像庫A上的考察實驗

使用上述5種算法對圖像庫A中的100對重疊圖像進(jìn)行特征匹配，分別記錄各類算法在兩兩圖像對上特征匹配的時間、特征匹配點的數(shù)量和特征匹配的誤差.由于圖像庫A中兩兩圖像對之間的單應(yīng)變換矩陣已知，所以可以使用對稱轉(zhuǎn)移誤差[20]來評估各算法的匹配精度.這里計算了圖像中每一個像素的對稱轉(zhuǎn)移誤差.為了評估各算法的誤差分布情況，實驗中將（0.005～0.100）像素范圍以0.005為間隔分成19個等距的區(qū)間，如0.005～0.010，同時增設(shè)0.100～1.000、>1.000這兩個較大的特殊區(qū)間來統(tǒng)計離群數(shù)值，分別記錄5類算法在每對圖像上的平均誤差在各個區(qū)間的圖像數(shù)量百分比，如圖4所示.圖4中橫軸表示平均誤差統(tǒng)計區(qū)間，縱軸表示誤差分布的數(shù)量百分比.實驗數(shù)據(jù)表明，NeoKPM算法的誤差幾乎都小于0.04像素，并且比所有其他方法都要好.表4是5種算法在圖像庫A上獲得的最小平均誤差圖像的數(shù)量統(tǒng)計.數(shù)據(jù)表明，NeoKPM算法在大多數(shù)圖像上產(chǎn)生的特征匹配誤差比其他4種算法要小.

在圖像庫A上的5種算法的正確匹配點數(shù)和運行處理時間分別如圖5和圖6所示，其中橫軸為圖像庫A中圖像對的圖像索引編號.

由于圖像庫A中存在兩種分辨率的圖像，因此本文對實驗數(shù)據(jù)進(jìn)行了分類整理，圖5和圖6的上半部為在33對分辨率為（10288×7730）像素圖像上實驗得出的數(shù)據(jù)，下半部為在67對分辨率為（5087×3703）像素的圖像上實驗得出的數(shù)據(jù).從實驗中可以得出，NeoKPM算法能夠以最少的運行時間在紋理較為豐富的高分辨率（（10288×7730）像素）壁畫圖像上獲得最多數(shù)量的匹配點.結(jié)合表5和表6的數(shù)據(jù)可以得出，NeoKPM算法在紋理不明顯、分辨率較低（（5087×3703）像素）的圖像上，不僅可以較為穩(wěn)定地獲取精度和數(shù)量比較好的匹配點，并且其63.37s的平均處理時間低于其他4種算法.

2.2.2在圖像庫B上的考察實驗

2.2.1節(jié)考察了5種算法在2幅圖像的單應(yīng)變換矩陣已知條件下的匹配誤差情況.本節(jié)考察2幅圖像在其單應(yīng)變換矩陣未知條件下的匹配誤差情況，而圖像庫B就是符合這個條件的圖像庫.由于不知道2幅圖像的單應(yīng)變換矩陣，無法計算每個特征點的匹配誤差，所以本文采用肉眼觀察的方法：2幅有重疊的圖像通過匹配點對齊后，如果沒有明顯錯位就認(rèn)為是特征匹配成功.在圖像庫B上，5種算法的匹配成功的結(jié)果如表7所示.由表7可知，NeoKPM算法和SC-RANSAC算法能夠100%獲得成功匹配，而其余算法不能保證匹配成功.

實驗中，匹配成功所對應(yīng)的匹配點被認(rèn)為是正確匹配點，失敗時匹配點數(shù)記為0.在圖像庫B上的5種算法的正確匹配點數(shù)和運行時間分別如圖7和圖8所示，其中橫軸為圖像庫B中圖像對的圖像索引編號.由圖7和圖8可知，在紋理較為豐富、分辨率較高（（10288×7730）像素）的壁畫圖像上，NeoKPM算法的運行時間最少而匹配點數(shù)最多，其匹配點數(shù)要高出其余4種算法近1倍;在分辨率較低（（5087×3703）像素）的壁畫圖像上，NeoKPM算法相較于SIFT算法、ORB算法、SURF算法這3種經(jīng)典算法，即使在圖像重疊率不是很高的情況下也成功完成了所有的匹配任務(wù);相比于同樣完成全部匹配的SC-RANSAC算法，其平均匹配點數(shù)為7 577，高于SC-RANSAC算法的5 459.另外，如表8所示，NeoKPM算法的平均處理時間也遠(yuǎn)低于其他4種算法.

下面從圖像庫B里選兩對重疊圖像來觀察圖像在特征匹配后進(jìn)行對齊處理的實際效果.圖9（a）是來自圖像庫B的2幅有重疊的壁畫圖像，分別用SIFT算法、SC-RANSAC算法和NeoKPM算法對圖9（a）進(jìn)行特征點匹配處理后再進(jìn)行圖像對齊拼接處理，其拼接結(jié)果分別如圖9（b）、圖9（d）和圖9（1）所示.為了方便比較，把左側(cè)紅色矩形區(qū)域進(jìn)行放大后的局部圖像放在其右邊，如圖9（c）、圖9（e）、圖9（g）所示.從圖9（c）、圖9（e）、圖9（g）可以看到，SIFT算法和SC-RANSAC算法都有明顯錯位的紋理，而NeoKPM算法沒有明顯錯位的地方.

圖10（a）也是來自圖像庫B的2幅有重疊的壁畫圖像.分別用SC-RANSAC算法和NeoKPM算法對圖10（a）進(jìn)行特征點匹配處理后再進(jìn)行圖像對齊拼接處理，其拼接結(jié)果分別如圖10（b）、圖10（d）所示.圖10（c）、圖10（e）為把左側(cè)紅色矩形區(qū)域進(jìn)行放大后的局部圖像.由圖10（c）、圖10（e）可知，NeoKPM算法可以精確地對齊所有結(jié)構(gòu)區(qū)域，但SC-RANSAC算法會錯位紋理區(qū)域.

2.3NeoKPM算法與CODE算法的性能比較

CODE（Coherence based DEcision boundaries）[18]算法為近年來一種較為優(yōu)秀的特征匹配算法，但由于其采用A-SIFT[21]來檢測特征點，所以該算法只能處理最大為（640×480）像素的圖像.為了與CODE算法進(jìn)行比較，本文特地制作了分辨率為（640×480）像素的圖像庫C（參見2.1節(jié)圖像庫說明）.

在圖像庫C上，對CODE算法和NeoKPM算法進(jìn)行特征匹配處理的比較實驗，實驗結(jié)果如圖11和圖12所示，其中橫軸為圖像庫C中圖像對的圖像索引編號，縱軸分別為這兩種算法的特征匹配點的雙向平均誤差和運行處理時間.從圖11可知，NeoKPM算法的匹配點平均雙向誤差約為0.30像素，而CODE算法的平均雙向誤差約為0.21像素，CODE算法比NeoKPM算法要好，但差別微小.從圖12可知，NeoKPM算法的平均處理時間約為2.26s，CODE算法的平均處理時間約為5.04s，即使在這么小尺寸的圖像上，NeoKPM算法的速度都比CODE算法要快近50%;相比于CODE算法，NeoKPM算法對被處理的圖像沒有大小的限制，且能夠以較低的時間損耗完成高分辨圖像的高質(zhì)量匹配，匹配精度逼近CODE算法.

3結(jié)論

針對既有特征點匹配算法不適合高分辨率壁畫圖像的問題，本文提出了一種解決高分辨率壁畫圖像匹配的高速算法NeoKPM，該算法的主要特點如下：①針對具有高分辨率的壁畫圖像，采取降采樣策略;②根據(jù)先驗知識估算目標(biāo)圖像相對于參考圖像的平移量，減少了特征匹配的搜索空間，在降低了計算復(fù)雜度的同時也提高了匹配的正確率;③從降采樣圖像的特征點計算出原圖像的單應(yīng)變換矩陣，極大地提高了原圖像的特征點匹配的效率;④提出了基于灰度和顏色不變量的聯(lián)合SIFT特征向量，解決了SIFT算法不能識別具有相同紋理不同顏色區(qū)域的問題.在實際壁畫圖像庫上，本文對NeoKPM算法的性能進(jìn)行了實驗，實驗結(jié)果表明：在分辨率為8000萬像素的壁畫圖像上，本文算法每對圖像的正確匹配點數(shù)量平均比SIFT算法高出近10萬個，其特征點匹配處理速度是SIFT算法的20倍，其基于圖像單個像素的雙圖像平均誤差小于0.04像素.

本文所提出的NeoKPM算法是針對于高分辨圖像提出的，其在低分辨率圖像上的效果并不明顯;同時如果在低分辨率圖像上進(jìn)行降采樣處理，過少的特征點也將難以支持計算出一個相對準(zhǔn)確的初始對應(yīng)關(guān)系.根據(jù)壁畫圖像的拍攝方式和匹配精度的需要，本文算法主要支持兩圖像重疊率不低于20%的精準(zhǔn)匹配.目前本文算法是在CPU上實現(xiàn)的，為了進(jìn)一步提高處理速度，如何將本算法推導(dǎo)到并行算法并在GPU上進(jìn)行實現(xiàn)是今后的課題.

致謝上海商務(wù)數(shù)碼圖像技術(shù)有限公司對本文的研究工作，不僅提供了全額資金支持，還提供了洞窟壁畫圖像供實驗之用，在此表示衷心的感謝.

[參考文獻(xiàn)]

[1]中華人民共和國國家文物局.古建筑壁畫數(shù)字化測繪技術(shù)規(guī)程：WW/T 0082—2017 [S].北京：文物出版社，2017.

[2]LOWE D G. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision，2004，60（2）：91- 110.

[3]MATAS J，CHUM O，URBAN M，et al. Robust wide-baseline stereo from maximally stable extremal regions [J]. Image and VisionComputing，2004，22（10）：761-767.

[4]BAY H，ESS A，TUYTELAARS T，et al. Speeded-up robust features （SURF）[J]. Computer Vision and Image Understanding，2008，110（3）：346-359.

[5]RUBLEE E，RABAUD V，KONOLIGE K，et al. ORB：An efficient alternative to SIFT or SURF [C]// 2011 International Conference on Computer Vision. IEEE，2011：2564-2571.

[6]MUKHERJEE D，WU Q M J，WANG G H. A comparative experimental study of image feature detectors and descriptors [J]. Machine Vision and Applications，2015，26（4）：443-466.

[7]ABDEL-HAKIM A E，F(xiàn)ARAG A A. CSIFT：A SIFT descriptor with color invariant characteristics [C]// 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition （CVPR'06）. IEEE，2006：1978-1983.

[8]GEUSEBROEK J M，VAN DEN BOOMGAARD R，SMEULDERS A W M，et al. Color invariance [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（12）：1338-1350.

[9]ALCANTARILLA P F，BARTOLI A，DAVISON A J. KAZE features [C]// Computer Vision-ECCV 2012，ECCV 2012，Lecture Notes in Computer Science. Berlin：Springer-Verlag，2012：214-227.

[10]ALCANTARILLA P F，NUEVO J，BARTOLI A. Fast explicit diffusion for accelerated features in nonlinear scale spaces [C]// Proceedings of British Machine Vision Conference. BMVC，2013：13.1-13.11.

[11]CHO Y J，KIM D，SAEED S，et al. Keypoint detection using higher order Laplacian of Gaussian [J]. IEEE Access，2020（8）：10416- 10425.

[12]SAVINOV N，SEKI A，LADICKY L，et al. Quad-networks：Unsupervised learning to rank for interest point detection [C]//2017IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE，2017：3929-3937.

[13]DE TONE D，MALISIEWICZ T，RABINOVICH A. SuperPoint：Self-supervised interest point detection and description [C]// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops （CVPRW）. IEEE，2018：337-349.

[14]ONO Y，TRULLS E，F(xiàn)UA P，et al. LF-Net：Learning local features from images [C]// 32nd Conference on Neural Information Processing Systems （NIPS 2018）. 2018：6234-6244.

[15]FISCHLER M A，BOLLES R C. Random sample consensus：A paradigm for model fitting with applications to image analysis and automated cartography [J]. Communications of the ACM，1981，24（6）：381-395.

[16]ROUSSEEUW P J. Least median of squares regression [J]. Journal of the American Statistical Association，1984，79（388）：871-880.

[17]FOTOUHI M，HEKMATIAN H，KASHANLNEZHAD M A，et al. SC-RANSAC：Spatial consistency on RANSAC [J]. MultimediaTools and Applications，2019，78（7）：9429-9461.

[18]LIN W Y，WANG F，CHENG M M，et al. CODE：Coherence based decision boundaries for feature correspondence [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2018，40（1）：34-47.

[19]CHOU C C，SEO Y W，WANG C C. A two-stage sampling for robust feature matching [J]. Journal of Field Robotics，2018，35：779- 801.

[20]HARTLEY R，ZISSERMAN A. Multiple View Geometry in Computer Vision [M]. 2nd ed. New York：Cambridge University Press，2003.

[21]MOREL J M，YU G S. ASIFT：A new framework for fully affine invariant image comparison [J]. SIAM Journal on Imaging Sciences，2009，2（2）：438-469.

（責(zé)任編輯：李藝）