熊潤華，張啟燦

基于優(yōu)先度排序的3維數(shù)據(jù)缺失快速插補法

熊潤華，張啟燦*

（四川大學光電科學技術系，成都610064）

為了快速準確地對3維光學測量的缺失數(shù)據(jù)進行插值，以利于后期對比研究，提出了基于優(yōu)先度排序的3維數(shù)據(jù)缺失快速插補估算方法，并把該算法用于插補模擬實驗數(shù)據(jù)以及20幀振動揚聲器測試數(shù)據(jù)的驗證。結(jié)果表明，與其它常用缺失數(shù)據(jù)插補方法相比，該方法運算速度快、插補效果好，有利于處理3維測量結(jié)果的多幀和大量的數(shù)據(jù)。

信息光學；3維面形測量；優(yōu)先度；數(shù)據(jù)插補

引 言

在現(xiàn)代測量方法中，3維面形光學測量方法以其特有的眾多優(yōu)良特性，被廣泛地應用于眾多行業(yè)中?，F(xiàn)有的方法包含莫爾條紋法（Moiré technique，MT）［1］、傅里葉變換輪廓術（Fourier transformation profilometry，F(xiàn)TP）［2-3］、相位測量輪廓術（phasemeasuring profilometry，PMP）［4-5］、調(diào)制度測量輪廓術（modulation measurement profilometry，MMP）［6］、空間相位檢測（spatial phase detection，SPD）［7］和光學三角測量法［8-9］等。就其本質(zhì)而言，都是通過分析受物體表面面形調(diào)制的光場，解調(diào)出物體的高度信息。用基于條紋投影的3維面形光學測量方法對靜態(tài)物體進行3維測量時，如果待測量物體面形比較復雜，則會出現(xiàn)采樣不足或陰影現(xiàn)象，導致相位信息中出現(xiàn)極點［10］，進而使得局部數(shù)據(jù)缺失。在采用多角度測量方式重建物體3維面形時，通常需在物體表面附加標記點處通過輔助匹配來完成拼接［11］。由于附加了標記點，無法同時得到標記點覆蓋處的物體相位信息，因此也會導致標記點覆蓋區(qū)域數(shù)據(jù)的缺失。動態(tài)過程3維面形重建方法以FTP為基礎，通過結(jié)構(gòu)光照明和高幀頻的CCD攝像機快速獲?。?2］動態(tài)過程中的一系列變形條紋圖，再經(jīng)過傅里葉變換、頻譜濾波、逆傅里葉變換、3維相位展開等處理［13］后得到一系列重建的3維面形。一般情況下，需用高幀頻成像設備沿時間軸采樣量化，用重建的多幀3維數(shù)據(jù)結(jié)果表征不同瞬間的3維面形，為了將此動態(tài)過程集中對比分析，就需要將多幀3維數(shù)據(jù)統(tǒng)一映射到同一坐標系內(nèi)。在映射的過程中，由于物體的運動變化會導致不同坐標系向最終坐標系統(tǒng)一映射時，一些點上沒有數(shù)據(jù)值。如何快速和準確地插補，還原出這些缺失值點的3維坐標信息是本文中研究的主要問題。國內(nèi)外在圖像處理方面常用的插補方法有：鄰域均值法、鄰域加權(quán)平均法［14］、傅里葉變換迭代法［15］、八方向梯度估算法［16］。權(quán)重算法根據(jù)有效點與待插補點的距離遠近設置不同的權(quán)重，考慮到了距離對待插補點值的影響，在處理較大鄰域變化的數(shù)據(jù)時鄰域加權(quán)平均要優(yōu)于鄰域均值法［16］。由于鄰域加權(quán)平均法是依靠大量有效值點的加權(quán)平均值得到數(shù)據(jù)，在處理有少量尖刺數(shù)據(jù)時有一定的抗干擾能力。但是沒有充分考慮物體的局部變化趨勢，當待插補區(qū)域位于傾斜面上且具有一定面積時（如標記點處），會引起較大的誤差。八方向梯度估算的梯度算法是一種基于對數(shù)據(jù)變化趨勢進行分析得到的缺失點數(shù)據(jù)的方法。但確定梯度時在同一條梯度方向上至少要有兩個有效值，如果其中一個為尖刺干擾數(shù)據(jù)時，這種對趨勢的估算容易將干擾擴大。因此，作者的研究工作擬將二者結(jié)合起來，充分利用它們各自的優(yōu)點，對應處理不同情況下的數(shù)據(jù)缺失插補問題；同時，原有算法都是對插補數(shù)據(jù)區(qū)域采用“數(shù)據(jù)擠壓縫合”，每次插補邊沿點都需要做一次全局掃描，這樣將耗費大量的時間，而降低插補的速度。作者提出將梯度權(quán)重相結(jié)合的估算方法，并按優(yōu)先度大小排序先后對缺失數(shù)據(jù)進行插補，該算法能夠通過一次掃描就得到所有待插補點的插補順序，從而克服了現(xiàn)有方法的反復搜尋耗時，而且保持較快運算速度的同時，插補的數(shù)據(jù)更接近物體的實際形狀，能比較快捷地獲得理想的插補效果。

1 本文中的算法原理

1.1梯度和權(quán)重相結(jié)合的估算方法

結(jié)合八方向梯度估算法和加權(quán)平均算法的優(yōu)點，在插補數(shù)據(jù)的時候既可以處理斜面大面積數(shù)據(jù)缺失值點的問題，又可以在一定程度上減弱由于各種干擾對待插補值的影響，在插補數(shù)據(jù)的準確性上相比單一算法有了較大的提高。本文中的算法通過對有效值點位置分布不同采用不同的方法取估算值。兩種算法的結(jié)合使用情況，以待插補點為對稱中心，若有效值點是對稱的，則進行權(quán)重相加運算，用有效值點的加權(quán)數(shù)據(jù)之和除以權(quán)重系數(shù)之和得到加權(quán)平均值w（x，y）。若有效值點不對稱則進行梯度運算，即用有效梯度值的和除以有效梯度個數(shù)得到梯度算法平均值g（x，y），再將兩個值相加求均值得到待插補數(shù)據(jù)的最終結(jié)果。具體計算過程如圖1所示，以待插補點（x，y）為對稱中心取一子窗口（5×5窗口），圖中淺灰色點和黑色點為有效數(shù)據(jù)點，白色點為沒有數(shù)據(jù)值的點，中間深灰色點（x，y）為待插補點。黑色點關于（x，y）點對稱，進行權(quán)重運算得到w（x，y），其中A（x，y）為點（x，y）的有效數(shù)據(jù)點。

Fig.1 Combination algorithm

淺灰色點關于（x，y）不對稱，對其進行梯度運算得到g（x，y），其中，

設（x，y）點缺失的數(shù)據(jù)估算值為V（x，y），則該條件下待插補點的數(shù)據(jù)估算值：

另外，當數(shù)據(jù)中只存在權(quán)重均值運算（或者既無對稱有效數(shù)據(jù)值點也無有效梯度值點），則用權(quán)重均值來獲得待插補點的數(shù)據(jù)估算值，即：

當數(shù)據(jù)中只存在梯度運算時，則用梯度運算值表示待插補點的數(shù)據(jù)估算值，即：

1.2缺失數(shù)據(jù)優(yōu)先度排序

如果多點插補缺失數(shù)據(jù)在空間坐標上相鄰成片，在這種情況下，為了盡量減小誤差常常采取“數(shù)據(jù)擠壓縫合”，從缺失數(shù)據(jù)區(qū)域的邊沿開始向中間逐次進行插補，這樣插補出來的結(jié)果的總體誤差最小，使誤差向中心堆積，能保證邊沿缺失點具有較高精度［12］。插補效果擁有漸變性，而且最大限度地使用了有效值點。在現(xiàn)有算法中，使用“數(shù)據(jù)擠壓縫合”方法在計算機上插補數(shù)據(jù)，每次選擇確定待插補邊沿點時，都需要對全局進行掃描，這樣的操作將耗費大量的時間，甚至超過了插補過程中本身計算耗費的時間。為了能夠通過一次掃描就得到所有待插補點的插補順序，提出了優(yōu)先度排序的算法，僅對全局數(shù)據(jù)進行一次掃描，確定它屬于第幾級邊沿點，并依次對不同缺失數(shù)據(jù)點賦予不同的優(yōu)先度，反映它們隨后被插值處理的先后順序，從而節(jié)省了今后再次掃描所要耗費的時間，加快了整個插值算法速度。具體判定令待插補點（x，y）優(yōu)先度的初始值為a＝1，判斷點（x，y）上下左右a（其中a＝1，2，3）點內(nèi)是否有有效數(shù)據(jù)點，如有則得到其優(yōu)先度是a。本文中采用的最大優(yōu)先度為3。取一子窗口（9×9窗口），采用該種判定方法其優(yōu)先度示意圖如圖2所示（黑色點為有效數(shù)據(jù)的點，非黑色部分為待插補點，數(shù)字表示此點的優(yōu)先度），這樣所有待插補點的優(yōu)先度可以確定下來。

Fig.2 Priority schematic diagram

1.3算法的整體流程

本文中算法的整體流程可分為前期數(shù)據(jù)處理部分和后期數(shù)據(jù)插補過程。算法過程描述如下。

（1）前期數(shù)據(jù)處理部分，通過一次掃描加多次判斷得到所有待插補點的插補順序即優(yōu)先度，確定它屬于第幾級邊沿點并記錄下處理的先后順序。圖3為前期處理部分程序流程圖的主要部分，在此部分首先生成一個mask函數(shù)用來標記哪些位置的點是待插補點，令有效值點在mask中賦1，待插補點賦0。再將這些位置信息賦予（x（i），y（i））（其中i表示第i個待插補點）。取一個變量a＝1，再取一個待插補點，查看它上下左右4個方向有無有效值點，如果沒有則表示第1次插補時它不在邊沿點上，令a＝a+1，重復上述比較，直到有有效值點時為止，然后將現(xiàn)在的a值賦予優(yōu)先度記錄矩陣，得到此點的優(yōu)先度系數(shù)。在實際編程中，為了提高速度將最大優(yōu)先度值a設為一個合理的數(shù)，采用待處理數(shù)據(jù)中最大連續(xù)缺失值點數(shù)除以2然后向下取整，本文中使用的最大優(yōu)先度值是3。

Fig.3 Early part of the program

Fig.4 Late processing part of the program

（2）在后期插補的過程中，按照優(yōu)先度1～3的順序進行插補計算。圖4為后期處理部分主要程序流程圖。首先判斷是否存在待插補點，若存在則取一待插補點，查詢其優(yōu)先度值，為當前處理優(yōu)先度值則開始處理，否則查看下一待插補點；插補時取5×5鄰域，采用前文提到的梯度和權(quán)重相結(jié)合的估算方法進行計算，計算結(jié)束后將這個位置的mask值賦1，表示此位置已經(jīng)插補完成，然后再處理下一個待插補點。當優(yōu)先度為1的數(shù)據(jù)都計算結(jié)束后，開始計算優(yōu)先度為2的數(shù)據(jù)，直到計算全部完成，本文中只需將優(yōu)先度不大于3的數(shù)據(jù)全部計算完畢。

2 新算法的模擬實驗分析

實驗數(shù)據(jù)為生成的peaks函數(shù)，人為對其隨機刪除一些有效值點，形成一個帶有缺失值點的3維面形分布，如圖5a所示；數(shù)據(jù)缺失區(qū)域見圖5b；對此圖像前期進行優(yōu)先度判斷，后期梯度權(quán)重相結(jié)合估算法進行插補運算，如圖5c所示；用八方向梯度估算和加權(quán)平均算法處理圖5a，分別得到插補效果圖如圖5d和圖5e所示；3種估算算法的2維誤差圖分別見圖5f、圖5g和圖5h。幾種估算算法的插補標準差和運算時間如表1所示。由圖5和表1可知，無論是插補結(jié)果的標準差，還是運行時間上，基于優(yōu)先度排序的梯度權(quán)重相結(jié)合估算法都要優(yōu)于單獨的加權(quán)平均法和八方向梯度估算法。圖中，H表示高度。

Fig.5 Interpolation of simulation experiment data

Table1 The standard deviation and the computation time

Fig.6 Interpolation results

3 對動態(tài)3維測量多幀數(shù)據(jù)的插補分析

使用液晶顯示數(shù)字投影儀，投影正弦光柵周期為2.4mm，高速CMOS相機（Photonfocus MV2-D12 80-640-CL鏡頭焦距為50mm，系統(tǒng)測量精度為20μm），圖像采集卡采集圖像的速度為200frame／s，被捕獲的圖像的分辨率為1280像素×1024像素。對重建的振動揚聲器20幀3維面形數(shù)據(jù)進行插補，矩陣大小為531×521點陣（每點陣對應統(tǒng)一坐標的x-y面內(nèi)間隔為0.2mm），幾種算法在插補每一個點時所考慮的鄰域范圍同為5×5點陣。分別用本文中基于優(yōu)先度排序的權(quán)重梯度估算法、加權(quán)平均法和八方向梯度估算法進行插補，分析比較插補效果以及插補時間。圖6a和圖6b分別為第1幀、第14幀的原始數(shù)據(jù)，線框部分缺失數(shù)據(jù)比較多，容易出現(xiàn)插補誤差，可以用于分析比較幾種算法在誤差比較大時的插補效果；圖6c和圖6d為放大的線框區(qū)域；圖6e和圖6f為本文中算法插補后效果；圖6g和圖6h為鄰域加權(quán)平均算法插補后效果；圖6i和圖6j為八方向梯度算法插補后的效果。從圖6可以看出，即使是在插補誤差比較大的情況下本文中基于優(yōu)先度排序，并且權(quán)重梯度相結(jié)合的估算新算法插補出的數(shù)據(jù)更為連續(xù)光滑。表2為3種算法對20幀揚聲器數(shù)據(jù)處理的插補時間，從表2中可以看出，鄰域加權(quán)平均算法和八方向梯度估算法的插補時間是新算法插補時間的2倍。對以上各幀的插補可以看出，新算法能對揚聲器進行很好的插補，而且插補速度明顯優(yōu)于其它算法。

Table 2 The computation time

4 結(jié) 論

在3維面形測量中，針對缺失數(shù)據(jù)的處理，提出了前期優(yōu)先度排序，后期權(quán)重和梯度相結(jié)合估算的新算法。用模擬實驗數(shù)據(jù)和20幀揚聲器振動數(shù)據(jù)驗證了該方法可以快速、準確地插補出這些缺失數(shù)據(jù)。新算法在保證數(shù)據(jù)質(zhì)量的前提下提高了處理速度，不僅便于靜態(tài)3維面形缺失數(shù)據(jù)的插補，而且利于動態(tài)測量中的多幀、大量數(shù)據(jù)的插補處理。

［1］ TAKASAKIH.Generation of surface contours by Moire pattern［J］.Applied Optics，1970，9（4）：942-947.

［2］ SU X Y，LIJ，GUO L R.An improved Fourier transform profilometry［J］.Proceedings of SPIE，1988，0954：32-35.

［3］ TAKEDA M，MUTOH K.Fourier transoform profilometry for the auto measurement of 3-D object shapes［J］.Applied Optics，1983，22（24）：3977-3982.

［4］ SRINIVASAN V，LIU H C，HALIOUA M.Automated phase measuring profilometry of 3-D diffuse object［J］.Applied Optics，1984，23（18）：3l05-3108.

［5］ SU X Y，ZHOU W S，Von BALLY C，et al.Automated phasemeasuring profilometry using defocused projection of a Ronchigrating［J］.Optics Communications，1992，94（6）：561-573.

［6］ SU L K，SU X Y，LIW S.Application ofmodulation measurement profilometry to objects with surface holes［J］.Applied Optics，1999，38（7）：1153-1158.

［7］ TOYOOKA S，IWASA Y.Automatic profilometry of 3-D diffuse objects by spatial hhase detection［J］.Applied Optics，1986，25（10）：3012-3018.

［8］ CHENG X X，SU X Y，GOU L R.Automaticmeasurementmethod for 360°profilometry of 3-D diffuse objects［J］.Applied Optics，1991，30（10）：1274-1278.

［9］ LUO X H，JU Y，WANG X，et al.3-D foot profile measurement through light section method［J］.Laser Technology，2001，25（4）：308-311（in Chinese）.

［10］ GOLDSTEIN R M，ZEBKER H A，WERNER C L.Satellite radar interferometry：two dimensional phase unwrapping［J］.Radio Science，1988，23（4）：713-720.

［11］ MA Y B，ZHONG Y X，DAIX L.A method for 3-D scanning and reconstruction based on coded points［J］.Optical Technique，2006，32（6）：865-868（in Chinese）.

［12］ XIAO Y S，SU X Y，ZHANGQ C，etal.3-D surface shape restoration for the breaking surface of dynamic process［J］.Laser Technology，2006，30（3）：258-261（in Chinese）.

［13］ WU Ch C，SU X Y.Dynamic 3-D shape detected［J］.Journal of Optoelectronics＆Laser，1996，7（5）：273-278（in Chinese）.

［14］ RAFAEL CG，RICHARD EW.Digital image processing［M］.2nd ed.Beijing：Publishing House of Electronics Industry，2003：91-95（in Chinese）.

［15］ QIAN K.A simple phase unwrapping approach based on filtering by windowed Fourier transform：the phase near edges［J］.Optics＆Laser Technology，2007，39（7）：1364-1369.

［16］ HOU Zh L，ZHANGQ C，SU X Y.A novel missing phase interpolation algorithm for the branch cut and the marked point［J］.Optical Technique，2009，34（7）：502-505（in Chinese）.

Estimation method of fast interpolation of 3-D data based on priority

XIONG Runhua，ZHANG Qican
（Department of Opto-electronics，Sichuan University，Chengdu 610064，China）

In order to interpolate these missing data of 3-D measurement quickly and accurately and achieve further comparison study，the estimation method of fast interpolation of 3-D data based on priority was proposed.This algorithm was used to interpolate both the data of simulation experiment and twenty frames vibrating speaker.Compared with other common interpolation algorithm，this new algorithm is time-saving and its result is much better.It can be used to handle large amounts of data of 3-D shape measurement.

information optics；3-D measurement；priority；interpolation data

0438

A

10.7510／jgjs.issn.1001-3806.2014.01.007

1001-3806（2014）01-0030-05

教育部新世紀優(yōu)秀人才支持計劃資助項目（NCET-11-0357）

熊潤華（1987-），女，碩士研究生，現(xiàn)主要研究光信息處理及3維傳感技術。

*通訊聯(lián)系人。E-mail：zqc＠scu.edu.cn

2013-04-01；

2013-05-10