張 萍

（上海大學巴士汽車學院，上海 201314）

0 引言

逆向工程可以把成品轉換為工程模型和概念模型。逆向設計過程中，借助激光掃描數(shù)據(jù)技術，可以獲取包含物體信息的離散點云數(shù)據(jù)。根據(jù)離散點云數(shù)據(jù)中點的排列、密度、組織和分布特點，點云數(shù)據(jù)常被分為如下幾部分離散的數(shù)據(jù)：掃描調(diào)運數(shù)據(jù)線、網(wǎng)格點云和多邊形點云[1]。而數(shù)據(jù)處理的過程通常包括點云合并、降噪、數(shù)據(jù)消減和表面識別等。數(shù)據(jù)處理將直接影響后續(xù)數(shù)據(jù)的重構的質(zhì)量和效率[2]。將小波變換應用于離散點云的數(shù)據(jù)處理正處于研究中。

小波分析是當前應用數(shù)學和工程學科中一個迅速發(fā)展的新領域，經(jīng)過近10年的探索研究，重要的數(shù)學形式化體系已經(jīng)建立，理論基礎更加扎實。與Fourier變換相比，小波變換是空間(時間)和頻率的局部變換，因而能有效地從信號中提取信息。通過伸縮和平移等運算功能可對函數(shù)或信號進行多尺度的細化分析，解決了Fourier變換不能解決的許多困難問題[3]。小波變換是時間—尺度分析和多分辨分析的一種新技術，它在信號分析、語音合成、圖像識別、計算機視覺、數(shù)據(jù)壓縮、地震勘探、大氣與海洋波分析等方面的研究都取得了有科學意義和應用價值的成果[4-5]。

1 點云數(shù)據(jù)的小波表示方法

通?？梢允褂脃i=f(xi)來表示二維的離散點云數(shù)據(jù)，很顯然離散點云數(shù)據(jù)信號的能量是有限的。因此我們可以把小波變換理論應用到離散點云數(shù)據(jù)的處理當中。

L2（R）空間，即平方可積的函數(shù)空間，它可以被分解為無限個正交直和的形式，如下公式

因此可以唯一展開離散點云數(shù)據(jù)yi=f(xi)，yi∈L2（R）為：

小波變換通常使用函數(shù)空間L2（R）中的基來表現(xiàn)其中的任意一個信號的，對于離散點云數(shù)據(jù)的處理需要確定母小波函數(shù)。通過伸縮和平移母小波函數(shù)，可以使用如下所示的公式來定義離散點云的小波分析函數(shù)

式1.3中,參數(shù)s為尺度參數(shù)，參數(shù)τ表示平移參數(shù)，*表示取共軛函數(shù)?？梢酝ㄟ^小波變換將一維函數(shù)的離散點云數(shù)據(jù)(xi,yi)映射成二維函數(shù)Wf（s,τ）。同樣，逆連續(xù)小波變換離散點云數(shù)據(jù)則能通過ψ(s,τ)可以得出。

2 離散點云數(shù)據(jù)的小波分解

將給定的數(shù)據(jù)點坐標值展開成小波的平移和伸縮之和，該方法本質(zhì)上是將離散點云數(shù)據(jù)空間轉換成小波基的表示形式。點云數(shù)據(jù)的小波構造塊不僅需要滿足小波的正交性，還應該滿足小波平移和伸縮系的正交性，這樣就可以按照尺度將離散點云數(shù)據(jù)展開成不同的特征成分。

使用尺度函數(shù)的線性組合，即近似函數(shù)，來近似的表示離散的點云數(shù)據(jù)，使用級來定義近似的精度，并且第0級的精度最高。

由于尺度函數(shù)以及小波的組合組成了更高一層空間的基，即V0+W0構成了W1的基，以此類推得出下式：

從式2.3中，我們可以看出，可以通過相加第J級的近似函數(shù)fJ(xi)和粗略近似所累計的丟失成分，恢復離散點云數(shù)據(jù)f0(xi)的原始點云數(shù)據(jù)f0(xi)。此外，可以使用的線性組合表示離散點云數(shù)據(jù)的尺度函數(shù)?(x)，式2.4被稱為尺度函數(shù)的二尺度關系。

類似有小波函數(shù)的二尺度關系如下式：

cj（k）可以由第j級的小波函數(shù)的點積和點云數(shù)據(jù)信號得到

綜合式2.4、2.5和2.6可以得到如下兩式：

按照如上兩式所示，如果濾波器的系數(shù)h0和h1已經(jīng)確定了，則可以發(fā)現(xiàn)第j-1級的尺度系數(shù)和小波系數(shù)可由第j級的尺度系數(shù)計算出，依次類推，所有較低分辨率下的系數(shù)就可以計算出來，一共可以獲得1個尺度系數(shù)和2n+1個小波系數(shù)；類似的重構過程為上述過程的逆過程。綜上所述，可以用第1級到第J級的一共J個分辨率的小波表示離散點云數(shù)據(jù)f0(xi)。

經(jīng)過上述的過程分解離散點云數(shù)據(jù)，加上利用小波變換的兩個方向上的聯(lián)合分析的特征，能自動的把點云數(shù)據(jù)按照尺度關系分解成不同的特征部分[6-7]，從而能夠在后續(xù)進行進一步的應用。

3 二維離散點云的特征識別算法

二維的離散點數(shù)據(jù)是以某一個坐標軸為自變量的離散函數(shù)yi=f(xi),可以將一維的小波變換應用到此數(shù)據(jù)集上。連續(xù)信號在重構的時候需要基于尺度參數(shù)和基于平移參數(shù)的無限積分，而離散的小波變換的這兩個參數(shù)需要二值化。

對參數(shù)s和τ進行二進制分割，即可對連續(xù)小波進行離散化后的二階小波

對二維的離散點進行小波變換時，一般要求等間距的偶數(shù)個采樣點，為了方便后面進行的的分解和重構。基于小波變換的基本理論，本文提出了如下步驟對二維的離散點進行小波變換：

（1）選擇對應的小波基以及相應的濾波器；（2）確定需要達到的尺度閾值；（3）依據(jù)離散點的個數(shù)來確定初始分解的級數(shù)，同時，把這個采樣值作為尺度系數(shù)的初始值；（4）依據(jù)一定的順序?qū)?shù)據(jù)進行排序；（5）求解y坐標的數(shù)據(jù)值和小波的相關值；（6）重復執(zhí)行第5步，直到整個數(shù)據(jù)域被覆蓋時才停止；（7）對下一級的尺度，重復步驟5和步驟6；（8）繼續(xù)分解，直到達到預先設定的尺度閾值，然后再執(zhí)行步驟5和步驟6，至此小波的分解過程才完成；（9）可以利用第j-1級的尺度系數(shù)和小波系數(shù)構造出第j級的尺度系數(shù)；（10）重復執(zhí)行步驟9，直到完成所有數(shù)據(jù)的重構；

4 三維離散點云的特征識別算法

三維離散點云數(shù)據(jù)和二維離散點數(shù)據(jù)極其相似，可以把三維離散點云數(shù)據(jù)看作是以兩個坐標軸為自變量的二維離散函數(shù)zi=f(xi,yi)，然后就可以將二維的離散點云數(shù)據(jù)的小波變換應用到三維的離散點云數(shù)據(jù)集上。然而對二維的離散點進行小波變換時同樣需要尺度參數(shù)和小波參數(shù)的二值化，也就事要求在x和y方向上分別滿足按照2j和2k進行等間距采樣，為了方便后續(xù)的分解和重構。

二維小波變換就是將二維信號展開成的四種小波和尺度的張量級數(shù)的形式，具體的分解過程如下∶

首先進行水平方向上的離散小波變換，其中pk和qk分別表示低通濾波器和高通濾波器，具體如下所示

然后對系數(shù)進行垂直方向上的離散小波變換，得到如下四個表達式：

然后將4.2式和4.3式代入4.4，4.5，4.6，4.7這四個式子中，并展開成可以完成分解。三維離散點云數(shù)據(jù)的一次分解會產(chǎn)生4個子帶,重復分解低頻子帶，可得到多尺度二維小波的子帶。

基于上述理論，本文提出了按照以下步驟進行對三維離散點云數(shù)據(jù)的分解和重構：

(1) 選定相應的小波、濾波器和尺度閾值；(2) 對離散點云數(shù)據(jù)在兩個坐標軸方向上分別進行等間距方式的采樣，然后確定初始分解的級數(shù)； (3) 按照一定順序?qū)Σ蓸狱c進行排序；(4) 在水平方向上利用離散小波變換可以求出水平方向上的小波系數(shù)和尺度系數(shù)；（5）再對求解出的系數(shù)進行垂直方向上的離散小波變換，可以得到分解后的4個尺度和小波的聯(lián)合系數(shù)；(6) 重復執(zhí)行第5步，直到整個數(shù)據(jù)域完全被覆蓋為止；(7) 對下一級的尺度，重復進行步驟4，5，6；(8) 繼續(xù)分解直到達到所選定的尺度閾值為止，然后進行步驟4，5，6，7完成分解小波的過程；(9)由第j-1級的尺度系數(shù)和小波系數(shù)構造第j級的尺度系數(shù)；(10)重復第9步，直至完成所有數(shù)據(jù)的重構；

5 實例分析

根據(jù)提出的流程圖和算法，本文通過對帶有兩個半圓弧的連續(xù)曲線上等間距采樣128個采樣點后得到原始測試數(shù)據(jù)，其中，點的采樣間距為0.2，定義域為[0.352 26.652]。數(shù)據(jù)具體坐標如下表。

表5.1二維離散點數(shù)據(jù)

由于存在128個數(shù)據(jù)點數(shù)，這里記y坐標為c7k，確定初始尺度閾值為4，即把離散點數(shù)據(jù)依據(jù)3個尺度分成若干頻率域，測試目標是將原始數(shù)據(jù)依據(jù)頻率域分解成不同的成分，此處將兩個半圓弧視為噪音數(shù)據(jù)。

計算步驟具體如下：尺度系數(shù)g7初始值為選取排序好的離散點云數(shù)據(jù)的yi；根據(jù)公式14的二尺度關系式，通過低通濾波器h0和c7的卷積計算c6

根據(jù)上式可計算出c6( 0)= 0.4540823，然后依次計算c6的其余分量，類似的可計算出d6的其余分量，根據(jù)以上方式迭代計算，可分別計算出c5和d5，以及c4和d4，直到符合尺度閾值要求。每次向下級尺度分解，新的小波系數(shù)和尺度系數(shù)分量的大小減少為一半，照此步驟計算，可以完成對離散點云數(shù)據(jù)的特征分解。

圖5.1 離散點三個精度級的分解和重構

為實例在matlab7.0下進行測試，依據(jù)流程圖所示，分別計算可得到離散點云分解后的3個精度級的小波系數(shù)和尺度系數(shù) c6、d6、c5、d5、c4和d4，如圖5.1、圖5.2和圖5.3所示，其中每一幅圖中的第一子圖表示初始的原始數(shù)據(jù)，第二子圖表示重建后的數(shù)據(jù)，第三子圖表示當前級別的低頻分量，第四子圖表示目前級別的高頻分量∶

根據(jù)上述3圖可以看到，對輸入離散點云數(shù)據(jù)進行的第一次小波分解后，識別特征不甚明顯，未達到目標值，則對此級別的尺度系數(shù)第二次分解，到第3次的分解，c4基本去除了噪聲數(shù)據(jù)，完全達到了分解的目的，由于達到試驗的目標，分解停止。此時，重建后的數(shù)據(jù)和初始的數(shù)據(jù)較好的重合，一些局部誤差由舍入誤差造成。

6 結語

本文參考小波變換的基本處理算法，將小波變換引入離散點云的處理中。通過應用小波變換，在處理過程中將點云數(shù)據(jù)劃分成不同的頻率特征信息，可以按照后期點云數(shù)據(jù)的不同應用，減少后期的離散點云數(shù)據(jù)的三維可視化過程中需要處理的數(shù)據(jù)量，具有一定的科學研究和工程應用價值。本文的研究雖然取得了初步的成功，但依然任重道遠，尚有許多有待進一步深入進行的研究工作。

[1]張萍.基于逆向工程的轎車引擎蓋設計[J].現(xiàn)代機械 ,2010,(01)

[2]鄒鴻儒,劉占兵,周鋒,鞠魯粵.逆向工程中分層點云數(shù)據(jù)的拼合及精簡[J].機電一體化 , 2006,(06).

[3]張宗平,劉貴忠,候興松.一種改進的三維小波視頻編碼[J].西安交通大學學報∶自然科學版,2001,35(6)∶595.

[4]邵政,曾理, Hunziker Patrick R.高維圖像的小波壓縮方法[J].微機發(fā)展,2005,15(2)∶6.

[5]Daubechies I, Orthonormal I.Bases of compactly supported wavelets [J].Commun on Pure and Appl Math, 1988, 41(7)∶909.

[6]Mallat S.A theory for mult-i resolution approximation∶ the wavelet approximation[J].IEEE Trans,1989,11(7)∶674.

[7]Mallat S.Wavelet tour of signal processing [M].London∶ Academic Press,1998.