光柵式雙目立體視覺傳感器光條快速匹配算法

魏振忠 樊妍睿

(北京航空航天大學精密光機電一體化技術教育部重點實驗室，北京100191)

侯亞榮

(北京工業大學計算機學院，北京100022)

光柵式雙目立體視覺傳感器廣泛用于物體三維形貌的測量，而如何快速準確地實現光條匹配與識別是其一項關鍵技術.基于編碼方式的光條匹配識別方法研究較為廣泛，常用的有空間編碼方法［1－3］，時間編碼方法［4－5］，直接編碼［6－7］方法等，有些要投射多幅圖像，有些要分析圖像的灰度及顏色信息，給識別帶來了很大不便.文獻［8］提出一種基于空間搜索的識別方法，將光柵式雙目立體視覺傳感器看作兩個光柵結構光視覺傳感器，可分別測量各光條中心點的三維坐標，搜索不同光條中心點集之間的距離最小且模型編號相同的光條即為匹配光條.但該方法需將所有的可見光條都進行搜索，其中有許多情況是不可能出現的，造成大量冗余計算，當光條數量大且可見光條數較多的情況下，計算量非常大，速度較慢.本文改進了搜索方法，根據可見光條數目，排除了不可能的搜索計算情況，只將可能的情況代入模型進行搜索計算，從而有效減少了計算量.尤其是可見光條數較多時，計算量減少相當可觀.

1 光條匹配原理

光柵式雙目立體視覺傳感器可以看作兩個光柵結構光傳感器，分別由左、右攝像機和光柵投射器構成.對這兩個光柵結構光傳感器進行標定后，可完成對物體三維形貌的測量.顯然，同一光條上的光條點在兩個光柵結構光傳感器中得到的測量結果應該相同或很接近，而不同光條上的點則會差距很大.同時，如果光條點代入了錯誤的模型當中也會使測量結果出現較大偏差.因此，可通過計算兩光柵結構光傳感器所得各光條的測量結果之間的距離來實現光條的匹配和識別.

2 光條匹配算法

2.1 可能的可見光條組合模式分析及匹配算法

2.1.1 組合模式分析

假設投射光條數為n，光條從左到右依次編號為1，2，…，n，光條的組合模式如下:

1)左圖像可見光條數為m1，則左圖像中可能的光條組合模式有

2)右圖像可見光條數為m2，則右圖像中可能的光條組合模式有

3)設N1=n－m1+1，N2=n－m2+1，則列出左右圖像中所有可能的光條組合模式如表1.

由表1可知，共有N1×N2種，即(n－m1+1)×(n－m2+1)種可能的光條組合模式情況，即只在N1×N2種情況中搜索，可得到對應的匹配關系.而文獻［8］中方法需將所有可見光條都代入已標定好的n個結構光測量模型中進行計算和搜索，有許多情況根本不會存在，本文去掉了這些冗余的計算，且可見光條數越多，相對計算量就越小.

表1 光條組合模式

2.1.2 匹配算法

設左圖像中第 i根可見光條為 Li(i=1，2，…，m1)，右圖像中第i根可見光條為Ri(i=1，2，…，m2)，投射的n根結構光的測量模型分別為M1，M2，…，Mn.

對于模式1，即假設左圖像光條序列編號為1，2，…，m1，右圖像光條序列為 1，2，…，m2，當取左圖像中第1根可見光條L1和右圖像中第1根可見光條R1，并將其都代入第1個結構光模型M1中時，得到的兩光條中心點集合間歐氏距離應非常小，理論上為0，據此可作為其判斷標準.同理，其他情況也可以選擇相應的判斷方法，即選擇參加歐氏距離計算的光條及模型，全部列出如表2.

表2 光條組合模式及匹配方法

由表2可知，共有N1×N2種可能的情況.根據其對應的判斷方法，計算出所有光條間的歐氏距離，共有N1×N2個，從中選出最小值，并和規定閾值進行比較，若小于閾值則可判定其匹配，從而可以找出其對應的光條分布模式，即左右圖像中的光條序列，并識別出其模型號.

模型號的計算方法由算法決定，根據上述算法中的規律，假設左圖像第L根光條和右圖像第R根光條為匹配光條，則模型號的計算式為M=R+L－1.

具體的光條匹配步驟歸納如下:

1)將左圖像中第1～N2根可見光條L1～LN2的中心點分別代入第i～i+N2－1個結構光測量模型 Mi～Mi+N2－1中，可得到 N2個光條三維中心點集合(i=1，2，…，N1);

2)將右圖像中第i根可見光條也依次代入第 i～i+N2－1 個結構光測量模型 Mi～Mi+N2－1中，得到N2個光條三維中心點集合;

3)計算前兩步中對應模型號相同的光條三維中心點集合之間的距離，可得到N2個距離;

4)令i=i+1，重復以上計算，直到i＞N1時停止計算，共得到N1×N2個距離;

5)在N1×N2個距離中搜索最小值，其對應的光條即為匹配光條，對應的模型號即為其測量模型.

2.2 光條三維中心點集合間距離的計算［8］

光條三維中心點集合間距離的計算可根據文獻［8］中所闡述的方法進行，具體如下:

對左右兩光柵結構光傳感器分別進行標定，得到兩傳感器中各線結構光傳感器測量模型集合，分別記為φLM和φRM.將兩圖像中的光條中心點集合中各點分別代入相應的測量模型中，可得到各點的三維坐標值，設兩光條三維中心點集合分別為 φLT和 φRT.

1)正向計算.取φLT中一點，計算其與φRT中所有點之間的歐氏距離.記錄其中的最小距離d及兩集合中對應的兩三維點.

2)反向計算.計算φRT中對應最小距離d的三維點與φLT中所有點之間的距離，記錄其中的最小距離d′及兩集合中對應的兩三維點.

上述計算中，若d=d′，且兩集合中對應的兩三維點相同，則該最小距離參與兩集合間最小距離和的計算.對φLT和φRT中所有點按上述方法計算最小歐氏距離，最終得到兩集合中三維點之間的最小歐氏距離和.因為各光條間參加計算的點數不同，最后應除以參加計算的總點數，算出平均距離.

3 方法性能分析

3.1 計算量比較

文獻［8］中方法是先在左圖像中取一根光條，和右圖像中所有可見光條代入所有模型中進行計算，需要計算n×m2次距離，而本文方法的計算量為N1×N2，即 (n－m1+1)×(n－m2+1)次距離計算.可見，在投射光條數很大，且可見光條數也很大的情況下，文獻［8］中方法的計算量將會變得很大.假設 n=32，m1=25，m2=26，則文獻［8］方法需計算32×26=832次，而本文的方法只需計算56次.所以，本文算法在可見光條數越多的情況下，相對計算量越小.

當可見光條數比較小時，本文算法會失去計算量優勢.假設左右圖像可見光條數相等為m，投射光條數為n=2N(N=1，2，…)，當本文算法的計算量和文獻［8］算法相等時，則

令m/n=a，a為比例系數，則 m=an，式(1)可寫為

展開化簡后，得

當n取不同值時，可解出不同的a值，即當m＜an時，本文算法的計算量將大于文獻［8］算法.N取不同值時各參數如表3.

表3 最少可見光條數計算

由表3可知，n越大，a越小，即保持計算量優勢的最少可見光條數比例越小.表中各m值均為舍去小數位后的光條數，當可見光條數小于等于m時，本文算法計算量將大于文獻［8］算法.

一般情況下，測量中可見光條數占總投射光條數比例至少達到一半以上，且n的取值在8以上，所以本文算法的計算量優勢在通常情況下都能充分發揮出來.

3.2 準確性比較

文獻［8］中方法是先取左圖像中某一光條，然后在右圖像所有可見光條中進行搜索尋找匹配光條，但如果右圖像的可見光條中根本沒有和其匹配的，則此次計算將不能得到結果.例如，當左圖像中分布模式為1，2，…，m1，右圖像中分布模式為2，3，…，m2+1，若取左圖像中第1根光條在右圖像中進行搜索，就得不到匹配光條.而本文所介紹的算法，分析了所有可能出現的情況，在一次搜索過程中，總可以找出一對匹配的光條.

4 實驗

采用兩臺分辨率為1600×1200的AVT Pike F505B攝像機，15 mm鏡頭，可投射8個光平面的光柵結構光投射器，構建了光柵式雙目立體視覺傳感器測量系統，如圖1所示.

圖1 實驗系統

4.1 攝像機參數標定結果

左攝像機內部參數:

右攝像機內部參數:

兩攝像機之間的旋轉矩陣和平移矢量:

4.2 光平面方程標定結果

左光柵結構光視覺傳感器光平面方程:

右光柵結構光視覺傳感器光平面方程:

4.3 光條匹配

用上述系統拍攝一組光柵圖像對算法進行實驗驗證，如圖2.

圖2 光柵圖像

n=8，m1=6，m2=6，N1=n －m1+1=3，N2=n－m2+1=3，所以 N1×N2=9.得到各光條中心點集合間的平均距離如表4.

表4 光條中心點集合間距離 mm

從表4數據看出，L3和R3之間距離明顯小于其他值，由此可知，左圖像第3根光條和右圖像第3根光條為匹配光條，且對應模型號為5，匹配結果正確.

5 結論

在原有三維空間搜索方法的基礎上，根據可見光條數目和光條序列間的關系，分析了各種可能的光條組合，提出了一種快速的光條匹配算法，排除了冗余計算，大大減少了計算量.在實現光條匹配的同時，也實現了模型號的識別.實驗表明:該算法在保持了原算法魯棒性的前提下，大大減少了算法的運算量，實現了光柵光條的快速匹配與識別.

References)

［1］陶國智，邾繼貴，葉聲華.光柵式結構光傳感器的編碼方法［J］.航空精密制造技術，1999，35(3):18 －20 Tao Guozhi，Zhu Jigui，Ye Shenghua.Coding method of the grate structure sensor［J］.Aviation Precision Manufacturing Technology，1999，35(3):18 －20(in Chinese)

［2］Pages J，Salvi J，Forest J.A new optimised de bruijn coding strategy for structured light patterns［C］//Josef K，Marin E，Mark N.Proceedings of the 17th International Conference on Pattern Recognition .Los Alamitos:IEEE Computer Society，2004:284 －287

［3］Chen S Y，Li Y E，Zhang W.Vision processing for realtime 3-D data acquisition based on coded structured light［J］.IEEE Transactions on Image Processing，2008，17(2):167 －176

［4］孫軍華，魏振忠，張廣軍.一種高密度光柵結構光編碼方法［J］.光電工程，2006，33(7):78 －82 Sun Junhua，Wei Zhenzhong，Zhang Guangjun.A coding method for high-density grating structured light［J］.Opto-Electronic Engineering，2006，33(7):78 －82(in Chinese)

［5］于曉洋，關叢榮，吳海濱，等.高采樣密度彩色結構光三維測量技術仿真研究［J］.系統仿真學報，2011，23(2):346 －350 Yu Xiaoyang，Guan Congrong，Wu Haibin，et al.Research of high sampling density color structured light 3D measurement technique simulation［J］.Journal of System Simulation，2011，23(2):346－350(in Chinese)

［6］Lu C，Cho G.Accurate 3D scanning of swaying human body parts by one projection based on OIMP technique［C］//Tang Y Y，Wang S P，Loettem G，et al.Proceedings of the 18th International Conference on Pattern Recognition.Los Alamitos:IEEE Computer Society，2006:1 －4

［7］Gorthi S S，Lolla K R.A new approach for simple and rapid shape measurement of objects with surface discontinuities［C］//Wolfgang O，Christophe G，Erik L N.Proceedings of SPIE.Bellingham:SPIE，2005:184 －194

［8］謝光輝，魏振忠，劉震，等.一種光柵式雙目立體視覺傳感器光條匹配方法［J］.北京航空航天大學學報，2008，35(1):113－116 Xie Guanghui，Wei Zhenzhong，Liu Zhen，et al.Light-stripes matching method for raster binocular stereo vision sensor［J］.Journal of Beijing University of Aeronautics and Astronautics，2008，35(1):113 －116(in Chinese)

［9］張廣軍.機器視覺［M］.北京:科學出版社，2005 Zhang Guangjun.Machine vision［M］.Beijing:Science Press，2005(in Chinese)