一種運動捕獲系統中誤匹配點的剔除算法
2009-01-01 00:00:00陳燕軍鄭江濱史文波李秀秀
計算機應用研究 2009年2期
（西北工業大學 計算機學院， 西安 710072）
摘 要：在特征點的提取階段通過利用先驗知識的迭代法得到二值化閾值，然后依據輪廓特征排除非特征點。對于特征點的匹配，首先根據極線約束得到初始候選點對，再通過松弛匹配算法和三角測量法剔出誤匹配，得到最終的匹配點對；最后利用以上匹配算法給出了一種簡便的多攝像機間特征點匹配的策略。實驗結果表明算法匹配正確率高。
關鍵詞：運動捕獲;候選匹配點;松弛匹配;誤匹配點
中圖分類號：TP391.41 文獻標志碼：A
文章編號：10013695(2009)02042202
Algorithm for eliminating mismatching points in motion capture system
CHEN Yanjun，ZHENG Jiangbin，SHI Wenbo，LI Xiuxiu
(School of Computer， Northwestern Ploytechnical University， Xi’an 710072， China)
Abstract:Using the iterative method with prior knowledge，got the threshold at the stage of feature points， then excluded nonfeature points based on contour feature. For matching feature points，obtained initial candidates points according epipolar constraint， then through the relaxation matching algorithm and triangulation measurement exclued mismatching points， it would to be last matching points. Finally，by the above matching algorithm described a kind of feature points matching strategy in a multicamera system. Experimental results show that the algorithm has a high precise matching rate.
Key words:motion capture; candidate matching points; relaxation matching; mismatching points
近年來興起的運動捕獲技術在游戲動畫、影視制作、虛擬現實、體育訓練等領域有廣泛的應用前景和潛在的經濟價值。其中特征點的匹配是基于標記點的運動捕獲的關鍵技術之一，也是計算機視覺領域的一個瓶頸問題。數字圖像中的特征包括點特征、線特征、面特征等。由于點特征定位精確，更有利于三維信息的獲取，運動捕獲中通常采用標記點作為點特征，并且有許多人對點特征提取算法進行了研究[1，2]。
理論上，特征點在另一幅圖像上的匹配點一定在該特征點對應的極線上。文獻[3]中的運動捕獲首先在極線上搜索近似匹配點，然后選擇距離極線最近的點作為最終的匹配點。但是在運動捕獲中標記點相似性很大，并且距離極線最近的點不一定就是正確匹配點，這樣就會產生多組誤匹配點對，該匹配方法缺少一定的魯棒性。另外通過實驗發現，把標定后求出的基礎矩陣用于計算匹配點的極線方程，誤差很大；而利用當前兩幅圖像計算出的基礎矩陣誤差就很小，即匹配點與對應極線距離很近。原因在于前者計算出的基礎矩陣是全局最優，后者是局部最優。文獻[4]中采用手工抽取特征點，只達到像素級精度，影響三維重建的精度。針對以上問題本文采用在標記點輪廓提取后，通過質心法達到亞像素級精度；然后根據標記點的特征和極線約束快速選取候選點對；接著通過松弛匹配算法和三角測量法逐步剔除誤匹配點對。松弛匹配算法是利用匹配點對具有最大的相似性和相容性的原理來排除非匹配點的干擾，得到正確的匹配點對。
1 特征點的提取
1.1 預處理
二值化方法有固定閾值法、迭代法、自適應閾值法[5]等。本文利用標記點個數的先驗知識作為迭代結束的一個條件，大大減少了迭代的次數。設選擇的閾值為
T0=（Tmax+Tmin）/2(1)
其中：Tmax為初始最大閾值；Tmin為最小閾值。在運動捕獲中標記點的個數是事先知道的，設投影到圖像上的標記點個數最多為N。首先用閾值T0進行二值化，然后檢測輪廓的個數n0。若n0＞N，則更新Tmin=T0；若n0＜N，則更新Tmax=T0；若n0=N，則迭代結束，得到最終閾值T0。
1.2 特征點的識別和定位
二值化后進行輪廓提取，根據特征提取算法提取目標區域的形狀特征、尺寸特征。運動捕獲的標記點，經攝像機成像后為圓形(由于光照的影響，有時近似圓形)，所以可以根據形狀和面積特征剔除偽特征點，進而得到真正的標記點特征，為特征點匹配做好準備。
定位就是獲取特征點在圖像中的位置，這將用于下一幀特征點的預測和運動數據的三維重建，因此定位的精度是影響三維重建精度的重要因素。文獻[6]介紹了幾種常用的亞像素定位方法，其中質心法是一種常見的亞像素定位法，且定位精度高。本文就采用質心法對特征點進行定位。
經過上述特征點識別后得到特征點的輪廓，在輪廓區域內用質心法求取特征點的亞像素級位置。
2 特征點的匹配
2.1 初始候選點對
對于定標的攝像機拍攝的圖像而言，由于其對極幾何已知，本文用極線約束進行特征點的初始匹配，得到候選點對。根據下式得到Pi的候選匹配點集P：
Dij=dist(Pi，Pj，Li)(2)
若Dij＜D0，則Pj屬于P。其中：Li為特征點Pi在另一幅圖像上對應的極線；Pj為另一幅圖像上的任一特征點。
2.2 剔除誤匹配點
特征點Pi經過初始匹配后，存在多個匹配點，針對這種情況本文利用松弛匹配法和三角測量準則剔除這類模糊匹配。文獻[4]采用松弛匹配算法， 松弛法要求確定初始候選匹配點的相似性和相容性。
2.2.1 相似性計算
相似性是指候選對應點對(Pi，Pj)間的對應程度。根據文獻[7]，相似性Sij是候選點對(Pi，Pj)間距離dij的函數。dij的值越小， 相似性越高， 反之亦然。通常相似性Sij表示為
Sij=f(λ，dij)=γ/(λdij+1)(3)
其中：γ為一個歸一化常量；λ為一個與相似性Sij隨dij變化程度有關的正的常量。
相似性通常根據候選點對(Pi，Pj)的相關系數、梯度差、平均灰度差計算，分別表示如下：
Sccij=ωij，Sdiffij=f(λint，|Ij-Ii-(j-i)|)Sgradij=f(λgrad，|grad Pj-grad Pi|)
則初始相似性計算可用下式表示：
S0ij=SccijSdiffijSgradij(4)
其中：grad Pi、grad Pj分別為點Pi、Pj的梯度；Ii、Ij分別為圍繞特征點Pi、Pj的平均灰度；i、j分別為兩幅不同圖像的平均灰度。
本文把與極線約束有關的度量集成到相識性計算中，作為一種附加的度量，用下式計算：
Sepiij=f(λepi，Mf(F-，Pi，Pj))(5)
其中：F-為基礎矩陣，基礎矩陣求法有七點法、八點法[8]、改進的八點法[9]和RANSAC法[10]等。對于候選點對(Pi，Pj)而言，Mf的值與從點Pj到由點Pi確定的極線的距離或從點Pi到由點Pj確定的極線的距離成比例關系。因此該值可以作為一種與極線幾何有關的度量約束。此時相似性計算式表示為
S0ij=SccijSdiffijSgradijSepiij(6)
2.2.2 相容性計算
相容性常用鄰近點距離關系Cij計算，定義如下：
Cij=nk=1μ(Pi，Pj，P′i，P′j)/(1+dist(Pi，Pj，P′i，P′j))（7）
其中：μ(Pi，Pj，P′i，P′j)=e-r/εr，r=|d(Pi，P′i)-d(Pj，P′j)|dist(Pi，Pj;P′i，P′j)，dist=(Pi，Pj;P′i，P′j)=[d(Pi，P′i)+d(Pj，P′j)]/2
。μ(Pi，Pj;P′i，P′j)是一個高斯函數，
P′i，P′j分別是點Pi，Pj的鄰近點，dist(Pi，Pj)表示Pi和Pj的歐氏距離，r表示點的相對距離偏差，εr是相對距離偏差的一個閾值。
2.2.3 剔除誤匹配的準則
松弛過程結束后，采用以下幾個準則排除誤匹配：
a)相似性準則。令ε0為相似性閾值，若候選點對（Pi，Pj）的相似性度量Sij＜ε0，則候選點對(Pi，Pj)將被排除。
b)相容性準則。相容性Cij表示候選點對(Pi，Pj)和它們的鄰近點間的對應水平。令C0為相似性閾值，若候選點對(Pi，Pj)的相容性度量Cij＜C0，則候選點對(Pi，Pj)將從已求得的點對解中排除。
c)三角測量誤差準則。三角測量法建立在攝像機定標的基礎上的，由于匹配點必然對應空間中惟一點，誤匹配點存在三角測量誤差。三角測量誤差是指圖1中的矢量C1P1和CrPr間的歐氏距離Dtri大于0，若Dtri大于閾值D0，則候選點對(Pi，Pj)被剔除。P是用三角測量法經像點Pl和Pr求得的空間點。
2.3 多攝像機間特征點協調匹配的策略
上述過程是針對雙目下兩幅圖像間對應點的匹配。在多攝像機的運動捕獲中，每組雙目像都按照上述過程匹配。對于沒有找到最終匹配點的標記點，可以在鄰近的相機尋找匹配點，因為位置相近相機拍攝的圖像匹配點更多。具體過程（圖2）如下，假設有N組相機。
a)獲取每組相機拍攝的圖像Ik1和Ik2，分別按照第1章所述進行特征點提取。其中1≤k≤N。
b)對每組圖像對Ik1，Ik2，按照2.1和2.2節所述過程得到初始候選匹配點對，然后進行誤匹配點的剔除，得到最終匹配點對(Pk1，i，Pk2，j)。
c)對于圖像Ik1(Ik2)上未匹配的特征點Pk1，i(Pk2，j)，在相鄰的圖像
I(k+1)，1（I(k+1)，2）上尋找匹配點。 其中(Pk1，i，Pk2，j)為第k組相機1(2)圖像上的第i(j)個特征點。
3 實驗結果
本文的算法采用OpenCV和VC++實現。本實驗用四組相機同時對表演者動作進行捕捉，對每個相機的800幀序列圖像進行了測試。
對于正確的匹配點用同一種顏色進行標記。圖3和4分別是第一組相機和第三組相機第84幀的實驗結果。圖3左視圖中有一個未標記的點，是根據三角測量誤差準則排除了所有的候選點，因為右視圖的匹配點被遮擋。
為了說明匹配效果，本文用正確匹配的點數與運動捕捉對象的標記點個數比值定義正確匹配率。實驗對四組相機的800幀同步序列圖像的測試結果統計，得出正確匹配率達到74 683/80 000>93％。
4 結束語
本文提出了一種運動捕獲中誤匹配點的剔除算法，采用基于標記點個數的先驗知識得到二值化的閾值，對光照的變化有一定的適應性，用質心法定位特征點的亞像素位置。在匹配階段首先根據極幾何約束得到候選匹配點對，然后根據松弛匹配算法的相似性和相容性原理及三角測量準則排除誤匹配點對。本文最后提出了一種多攝像機間特征點匹配策略，當每組相機未找到匹配點時，可以利用相鄰相機的圖像信息最大可能地找到與之匹配的點。實驗結果表明，本文算法有效地提高了匹配正確率。
參考文獻：
［1］
SMITH S M.Feature based image sequence understanding [D]. Oxford:Oxford University，1992.
[2]HARRIS C G， STEPHENS M. A combined corner and edge detector[C]//Proc of the 4th Alvey Vision Conference.1988：147151.
[3]羅忠祥，莊越挺，潘云鶴，等.基于視頻的運動捕捉[J].中國圖象圖形學報，2002，8(8):752758.
[4]GALO M， TOZZI C L.Featurepoint based matching:a sequential approach based on relaxation labeling and relative orientation [J].Journal of WSCG，2004，12(1):18.
[5]LONGUESTHIGGINS H C.A computer algorithm for reconstructing a scene from two projections[J].Nature，1981，293(9):133135.
[6]SHORTIS M R，CLARKE T A，SHORT T.A comparison of some techniques for the subpixel location of discrete target images[C]//Proc of SPIE Videometrics.1994:239250.
[7]朱強，莊越挺，陳家實，等.基于色塊的人體運動跟蹤[J].模式識別與人工智能， 2001，14(4):487492.
[8]HARILEY R I.In defence of the 8point algorithm[C]//Proc of the 5th International Conference on Computer Vision.Washington DC:IEEE Computer Society，1995:10641070.
[9] BRANDT S.Maximum likelihood robust regression with known and unknown residual models[C]//Proc of Statistical Methods in Vedeo Proc Workshop.2002:97102.
[10] FAUGERAS O.Threedimensional computer vision:a geometric viewpoint[M].Cambridge:MIT Press，1993.
[11]SCHAFFALITZKY F， ZISSERMAN A. Viewpoint invariant texture matching and wide baseline stereo[C]//Proc of the 8th International Conference on Computer Vision.2001:636643.
[12]李豪杰，林守勛，張勇東.基于視頻的人體運動捕捉綜述[J].計算機輔助設計與圖形學學報，20006，18（11）：16451651.
[13]WEI Yichen，QUAN Long. Regionbased progressive stereo matching[C]//Proc of IEEE Computer Society Conference on Computer Vision and Pattern Recognitions.2004:106113.
[14]王付新，黃毓尉，孟偲，等.三維重建中特征點提取算法的研究與實現[J].工程圖學學報，2007，28(3):9196.
[15]OTSU N.A threshold selection method from graylevel histogram[J].IEEE Trans on Systems，Man and Cybernetics，1979，9(1):6266.
