基于鄰域加權與RGB色彩分量的圖像匹配算法

金廣智，石林鎖，劉均超，司海峰，牟偉杰

?

基于鄰域加權與RGB色彩分量的圖像匹配算法

金廣智1，石林鎖1，劉均超2，司海峰3，牟偉杰1

（1.第二炮兵工程大學五系，陜西 西安 710025；2.中航工業(yè)西安航空動力控制科技有限公司，陜西 西安 700077；3.西安思源學院，陜西 西安 710038）

為了提高彩色圖像的立體匹配精度，結合格式塔心理學和像素的色彩信息，提出了一種基于RGB色彩空間的改進誤差絕對值累積匹配算法（SAD）。首先，通過相似性和鄰近性規(guī)則獲取鄰域窗內的像素權值，并同預先生成的線性查找表相結合來加快權值的計算速度。然后，利用RGB色彩分量的像素分布特點，生成對應的分量權值，來進一步增強匹配代價函數(shù)的穩(wěn)定性。經(jīng)實驗驗證表明，改進后的匹配算法較灰度SAD及標準彩色SAD算法在精度上有明顯的提高。

鄰域權值；色彩分量；彩色立體匹配；誤差絕對值累積；線性查找表

0 引言

基于區(qū)域的立體匹配算法[2]使用最為廣泛，該類算法對參考點局部鄰域窗口的像素信息進行操作，通過圖像對之間窗口匹配代價函數(shù)來搜索對應點，常用的匹配代價函數(shù)有SAD（sum of absolute differences）[3]、SSD（sum of squared differences）[4]和NCC（normalized cross correlation）[5]等。為了提高窗口匹配代價函數(shù)描述像素特征的準確性，人們提出了大量改進算法，文獻[6]使用窗口尺寸自適應的方法來區(qū)別對待位于不同紋理強度區(qū)域的像素；文獻[7]使用可以改變形狀的鄰域窗口來適應位于不同位置的像素；文獻[8]提出的基于格式塔原則的權值算法，精度提高明顯，但由于權值計算過程中使用了大量的指數(shù)運算，算法計算復雜度較高，實時性較差。文獻[9]、[10]使用了動態(tài)規(guī)劃的方法來加速匹配搜索過程，雖能在一定程度上加速，但加速效果有限。

采用根據(jù)設定參數(shù)預先生成查找表的方式，有效降低了立體匹配過程中大量指數(shù)運算量的負擔，同時統(tǒng)一采用RGB色彩空間來進行像素操作，減少了色彩空間轉換帶來的效率損耗，并且通過分量權值進一步描述像素特征，以充分利用彩色圖像包含的豐富顏色信息，最后通過RGB色彩空間的分布特性來生成對應權值，來進一步改進匹配代價函數(shù)，最終有效提高了匹配精度。

1 基于鄰域像素加權的立體匹配代價函數(shù)

基于像素灰度的SAD代價函數(shù)如式(1)，代表像素的灰度值。對于RGB色彩色空間，SAD代價函數(shù)可以改寫為公式(2)，、、分別代表RGB三通道值。該函數(shù)將鄰域窗內的所有像素以相同的權值進行誤差累積計算，未考慮像素間的差異信息：

圖1 基于局部鄰域窗口立體匹配示意圖

1.1 結合格式塔理論的鄰域像素加權

為了利用鄰域窗口像素之間的差異信息來進一步提高匹配的準確性，文獻[8]引入了格式塔心理學。格式塔心理學[11-12]是人類感知系統(tǒng)的研究領域，指人類視覺系統(tǒng)在未獲得先驗圖像內容時，從圖像中獲取相對的聚類和結構的能力，即人能從隨機分布的圖像元素中檢測出元素的對稱性、共線性、平行性和連通性等特性。在圖像立體匹配領域，通常是利用格式塔心理學的相似性和鄰近性規(guī)則及顏色空間正態(tài)分布特性，預先給鄰域內的像素賦予不同的權值[13]。

在相似性規(guī)則的指導下，鄰域像素與中心像素之間的色彩差異作為窗內權值的計算方法，如下：

式中：與為待匹配的像素區(qū)域。

以文學之舟涉渡：《巨流河》的女性成長主題探析………………………………………………… 袁玲麗（4．94）

在鄰近性規(guī)則的指導下，鄰域像素與中心像素之間的距離信息作為權值的計算方法，如下式：

可得歸一化后的改進匹配代價函數(shù)如下，對應的匹配算法稱為鄰域像素加權匹配算法：

式中：代表對應像素對的權值。

1.2 “線性查找表”加速的權值計算

立體匹配過程中最耗時的步驟是匹配代價函數(shù)的運算[13]，其需要將每個待匹配像素與右圖中對應行的預置視差范圍內的所有像素進行鄰域窗口的匹配計算；鄰域分量加權算法首先需要根據(jù)當前圖像數(shù)據(jù)為每一個待匹配像素生成對應的權值矩陣，采用先生成后使用的方法可以減少重復計算，但即便如此，該計算過程大量的指數(shù)和開方運算仍將消耗過多運算資源。為了提高匹配代價函數(shù)的運算效率，本文采用了預先生成線性查找表的方法。

根據(jù)RGB色彩空間的定義可知像素RGB三個分量的值域都在0～255，且都為整數(shù)值，因此對應分量差值平方和的值域為0～195075，且全為整數(shù)，如式(6)、(7)：

D＝(Dc)2＝(r－r)2＋(g－g)2＋(b－b)2(6)

D?[0,195075]ü[(02＋02＋02),(2552＋2552＋2552)] (7)

因此，可以將式(3)改寫成式(8)：

式中：(D)表示線性查表過程。

僅需預先生成195076個對應的計算結果，即可以在使用時通過查表得到對應的浮點數(shù)值。生成查找表的計算可以放在算法初始化階段進行，這樣一個復雜的開方及指數(shù)運算就轉化為了一個快速的內存查表運算。

距離權值也可以采用類似的方法獲得，只是距離信息所需要的表數(shù)據(jù)更少，因此可以直接使用二維查找表的方式來得到，其中二維查找表的尺寸對應鄰域窗口的大小。

為了直觀地比較這個加速過程，我們將四種尺寸的圖像對分別用直接計算和查找表的方式進行匹配代價函數(shù)計算（僅測試權值生成過程，不考慮計算代價最小匹配過程，鄰域窗大小設定為11），由于查找表可以預先生成，故圖中耗時不需包括生成查找表的時間。耗時測試結果如圖2所示，可見該優(yōu)化方法能在不損失精度的情況下大大減少計算耗時。

圖2 權值生成耗時對比

2 色彩分量權值改進的匹配代價函數(shù)

為了提高圖像的匹配精度，充分利用圖像的色彩信息[14-15]，本文利用色彩色分量權值對像素的累積誤差計算公式進行改進，對每一個像素色彩分量根據(jù)該分量的大小分配權值。

2.1 RGB色彩分量特征

圖像中的像素因其各自呈現(xiàn)的顏色不同而形成一幅色彩圖像，較之灰度圖像，人們可以從色彩圖像獲取更多的視覺信息。對于單個像素而言，RGB三個分量的取值情況決定了其在RGB色彩空間的位置，比如明顯偏紅色的像素點，其G和B兩個通道的像素值就會遠遠小于紅色的值。因此，在匹配代價函數(shù)計算時，就可以根據(jù)這個特征來對顏色差異進行加權計算，而這個權值則由三通道的絕對比例決定，且有R＋G＋B＝1。同時設置了權值下限以防止因噪點像素而產(chǎn)生權值過小的情況，計算方法如下式：

2.2 色彩分量權值改進的匹配代價函數(shù)

色彩分量權值的計算一般放在匹配搜索之前，只需對左圖進行計算，預計通過該方法來進一步提高像素匹配的精度。色彩分量加權后的匹配代價函數(shù)為：

式(10)中的下式代表待匹配像素的色彩分量加權后的平均期望，式(10)與式(5)的區(qū)別僅體現(xiàn)在下式，通過引入各分量的權重可更真實體現(xiàn)相應像素的真實情況，避免誤差的不斷累積。

3 實驗驗證

3.1 算法流程

整個立體匹配算法主要包含以下3部分：

1）根據(jù)用戶輸入或預置參數(shù)生成色彩差異權值查找表與像素距離權重二維查找表，為增強實驗對比針對性，實驗過程中鄰域窗口統(tǒng)一設定為11×11。

2）載入圖像數(shù)據(jù)，并根據(jù)兩幅圖像生成各自的鄰域窗口權值與色彩分量權值；

3）利用改進后的匹配代價函數(shù)（式(10)），對后續(xù)輸入圖像數(shù)據(jù)逐一像素進行搜索匹配，以匹配代價函數(shù)最小的位置，作為最終匹配結果。

3.2 算法中參數(shù)的選擇

由于加入了鄰域窗口權值，其中的C，G兩個參數(shù)對于匹配結果影響很大，實驗過程中設置C為35，G為45，并統(tǒng)一采用尺寸為11×11的鄰域窗口進行匹配搜索。

3.3 實驗結果

實驗硬件條件為Intel 4核、CPU主頻為3.2GHz的電腦，通過安裝有OpenCV2.4.3的Visual C＋＋ 2010的軟件環(huán)境進行測試。對基于灰度的SAD（SAD_ GRAY）、標準RGB彩色空間的SAD（SAD_RGB）、鄰域窗加權的彩色（SAD_WCG_RGB）和綜合鄰域窗加權和色彩分量加權的SAD（SAD_WCG_WRGB）4種算法在450×375分辨率下分別進行了實驗測試。表1為4種算法的計算耗時及精度情況，采用的測試圖像由標準測試圖像中選取，故其真實視差已知，經(jīng)與其逐一對比便可知平均視差正確率。圖3是各算法得到的深度圖。

表1 對比算法的計算耗時及深度獲取正確率

圖3 視差圖測試對比

Fig.3 Results contrast disparity map

通過表1與圖3可看出，SAD_WCG_WRGB算法在視差獲取精度上有較大的提高，有效地消除了無紋理區(qū)域的視差噪聲。SAD_WCG_RGB算法和SAD_WCG_WRGB使用查找表加速后的耗時明顯減少，說明查找表技術的使用在不損失精度的情況下有效的提高了算法效率。而SAD_WCG_WRGB算法雖然在計算耗時上有所增加，但其匹配精度較前3種算法有大幅提升，如圖3(f)，視差圖中的物體輪廓更加清晰準確，且誤匹配和無匹配點明顯減少。

4 結論

提出了一種基于鄰域加權與RGB色彩分量的圖像匹配算法。針對色彩圖像的特點，使用格式塔理論的相似性和鄰近性規(guī)則構造了顏色差異權值和像素距離權值，通過線性查找表技術加速了權值的計算過程，可有效節(jié)省計算耗時；引入RGB色彩分量通道加權，進一步增強了匹配代價函數(shù)描述像素差異的能力。實驗結果表明，該算法相比灰度SAD以及標準彩色SAD算法在精度上有較大提高。同時注意到，雖然使用線性查找表加速，但改進算法的耗時仍大大高出灰度SAD算法，可從GPU加速方面考慮以實現(xiàn)實時的彩色圖像立體匹配。

[1] Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]., 2012, 47(1): 7-42.

[2] Ambrosch K, Kubinger W. Accurate hardware-based stereo vision[J]., 2010, 114(11): 1303-1316.

[3] Yoon S, Park S K, Kang S, et al. Fast correlation-based stereo matching with the reduction of systematic errors[J]., 2013, 26(14): 2221-2231.

[4] Adhyapak S A, Kehtarnavaz N, Nadin M. Stereo matching via selective multiple windows[J]., 2007, 16(1): 013012-013012-013014.

[5] Stefano L Di, Mattoccia S, Tombari F. Speeding-up NCC-based template matching using parallel multimedia instructions[C]//, 2005: 193-197.

[6] Veksler O. Fast variable window for stereo correspondence using integral images[C]//, 2013: 556-561.

[7] Hirschmüller H, Innocent P R, Garibaldi J. Real-time correlation-based stereo vision with reduced border errors[J]., 2012, 47(1): 229-246.

[8] Yoon K J, Kweon I S. Adaptive support-weight approach for correspon- dence search[J]., 2006, 28(4): 650-656.

[9] Wang L, Liao M, Gong M, et al. High-quality real-time stereo using adaptive cost aggregation and dynamic programming[C]//3D,,, 2006: 798-805.

[10] Yang N C, Chang W H, Kuo C M, et al. A fast MPEG-7 dominant color extraction with new similarity measure for image retrieval[J]., 2013, 19(2): 92-105

[11] Nguyen V H, Nguyen T H B, Kim H. Reliable detection of eye features and eyes in color facial images using ternary eye-verifier[J]., 2012, 56(8): 254-266.

[12] Von Gioi R G, Delon J, Morel J M. The collaboration of grouping laws in vision[J]., 2012, 12(3): 289-301.

[13] Yoon K J, Kweon I S. Locally adaptive support-weight approach for visual correspondence search[C]//, 2014: 924-931.

[14] 陸凱, 李成金, 趙勛杰, 等. 一種快速的亞像素圖像配準算法[J]. 紅外技術, 2013, 35(1): 27-30.

LU Kai, LI Cheng-jin, ZHAO Xun-jie,et al. A fast sub-pixel image registration algorithm[J]., 2013, 35(1): 27-30.

[15] 王新華, 黃瑋, 歐陽繼紅. 多探測器拼接成像系統(tǒng)實時圖像配準[J]. 中國光學, 2015, 8(2): 211-219.

WANG Xin-hua, HUANG Wei, OUYANG Ji-hong. Real-time image registration of the multi-detectors mosaic imaging system[J]., 2015, 8(2): 211-219.

Stereo Matching Algorithm Based on Neighborhood Weights and RGB Color Components

JIN Guangzhi1，SHI Linsuo1，LIU Junchao2，SI Haifeng3，MU Weijie1

(1.,’710025,；2.’’,’700077,；3.’,’710038,)

In order to improve the accuracy of color image stereo matching, an improved sum of absolute differences (SAD) algorithm in color space is proposed in RGB color space employing Gestalt psychology and color information of pixels. Similarity of color and proximity of distance between pixels in the neighborhood window is adopted to produce the weight, and linear look-up table method is also used to accelerate the computing speed. The distribution characteristics of RGB components are considered to produce the component weights for every pixel, which furthermore improves the stability of the matching cost function. The result of the experiment shows the proposed algorithm significantly improves the precision compared with gray SAD and standard color SAD.

neighborhood weights，color components，color stereo matching，SAD，linear look-up table

TP391

A

1001-8891(2016)03-0225-05

2015-08-09；

2015-10-09.

金廣智（1987-），男，河北滄州人，博士研究生，主要從事模式識別、機器學習及計算機視覺方面的研究。E-mail：azhide1025@163.com。

國家自然科學基金項目（61501470）；多目主動相機智能監(jiān)控關鍵技術研究（61501470）。