王 偉，唐民麗，吳恒玉

(海南軟件職業(yè)技術(shù)學(xué)院 電子工程系，海南 瓊海 571400)

隨著三維掃描設(shè)備的廣泛應(yīng)用，點幾何元素受到越來越多的重視.對于復(fù)雜結(jié)構(gòu)的模型，使用點集表示比三角網(wǎng)格更能有效地表示和顯示該幾何形體[1].以曲率為準(zhǔn)則的簡化算法，能夠保留模型的特征，其繪制效率大大提高.另外，曲面模型重建得到越來越多的應(yīng)用和研究，點云數(shù)據(jù)分片技術(shù)是其過程的重要環(huán)節(jié).大多數(shù)分片技術(shù)采用點云上每個點的曲率作為曲面特征識別的重要依據(jù).

點云數(shù)據(jù)的曲率估算方法，國內(nèi)外已有一定的研究.Milroy[2]等采用局部坐標(biāo)系內(nèi)的二次參數(shù)曲面逼近點云，利用曲率的微分性在OCS(orthogonal cross section) 模型上估算點云數(shù)據(jù)的曲率值.Huang[3]等和劉勝蘭[4]等是在三角網(wǎng)格模型上進(jìn)行曲率估算.胡鑫等[5]采用了圖像處理中的梯度求解法，對點云中每一點處的曲率進(jìn)行估計，其對噪聲沒有抑制作用，同時對點云數(shù)據(jù)的組織方式有要求.Yang[6]等直接以點云模型為研究對象，但卻局限于對規(guī)則點云進(jìn)行曲率計算.這些方法都有其理論上的局限性，同時，對于大規(guī)模點云數(shù)據(jù)，由于曲率計算量龐大，普通的計算機(jī)難以實現(xiàn).

本文改進(jìn)了Yang的方法，直接在散亂點集模型上計算曲率.同時提出根據(jù)點云模型特征，進(jìn)行區(qū)域劃分，將整個點云數(shù)據(jù)劃分為若干個部分，分別計算其曲率，從而在普通計算機(jī)上實現(xiàn)大規(guī)模散亂點云數(shù)據(jù)的曲率估算.

1 區(qū)域劃分

對目標(biāo)物體進(jìn)行三維激光掃描后，能夠得到物體的三維數(shù)據(jù)信息，即三維激光掃描的初始點云數(shù)據(jù)，而這些數(shù)據(jù)在三維空間里必然是一個有限的數(shù)據(jù)點集.如果用一個封閉的空間可以將這些點集包圍起來，則稱這個封閉的空間為原始點云數(shù)據(jù)的最外區(qū)域.這個區(qū)域形狀、大小都可以根據(jù)點云數(shù)據(jù)的形狀、大小來確定.對本文將要處理的隧道的點云數(shù)據(jù)，可以將其最外域選擇為相對簡單的形狀，如長方體區(qū)域.

如果能找到原始點云數(shù)據(jù)中x、y、z軸方向上的最大值和最小值，就可以確定長方體區(qū)域的8個頂點的坐標(biāo)(xmax，ymax，zmax)、(xmax，ymax，zmin)、(xmax，ymin，zmax)、(xmax，ymin，zmin)、(xmin，ymax，zmax)、(xmin，ymax，zmin)、(xmin，ymin，zmax)、(xmin，ymin，zmin)，長方體最外域的范圍也就確定了.

將原始點云數(shù)據(jù)的長方體最外區(qū)域確定之后，對這個區(qū)域進(jìn)行細(xì)化，將它劃分為一個個更小的區(qū)域.假設(shè)將長方體最外區(qū)域沿x、y、z軸方向劃分成n×p×q個小長方體，如果小長方體的長、寬、高分別為a、b、c，就可以通過式(1)求得小長方體的個數(shù)為

對最外區(qū)域細(xì)化后的點云數(shù)據(jù)進(jìn)行觀察，可以發(fā)現(xiàn)每一個小長方體區(qū)域中可能會包含一個或者很多個點，有的甚至不包含點;但是每一個點只會被唯一的一個小長方體區(qū)域所包含.另外值得一提的是小長方體區(qū)域如果劃分得越細(xì)，壓縮的精度就越高;反之，壓縮的精度就越低.

2 曲率估算

本文用二次參數(shù)曲面逼近點云來估算曲率，具體步驟如下:

1) 對點云進(jìn)行空間劃分和K鄰近計算，把每個點xi的K鄰近包括該點記為N(xi)，每個N(xi)的隱含曲面用一個切平面逼近.N(xi)在切平面上的投影記做N(x'i)，各點的切平面計算可以通過各點的鄰近點關(guān)系和最小二乘原理[1]求得，且xi與x'i必須滿足一一映射關(guān)系.

2) 以x'i為基點，求出距離xj'最遠(yuǎn)的點xj'，xj'∈N(x'i).連接x'i，xj'兩點的直線方向作為u方向，垂直于u方向的直線方向作為v方向.

3) 將N(x'i)的每一點都與x'i相連，得到k個有向線段，把這些線段在u方向上的投影記為di，1≤i≤j.將di進(jìn)行排序，最大的記為dmax，最小的記為dmin，則N(x'i)每一點對應(yīng)的u參數(shù)值為

式中:2≤j≤k+1;U1=0.

4) 為了計算每一頂點的曲率，運用Yang所形成的二次參數(shù)曲面逼近法求得較為精確逼近散亂數(shù)據(jù)點的二次參數(shù)曲面.利用頂點xi的N(xi)建立二次參數(shù)曲面

3 計算機(jī)實現(xiàn)

以激光三維掃描儀掃描的隧道點云數(shù)據(jù)為基礎(chǔ)，運用Imageware和Matlab程序設(shè)計的方法實現(xiàn)對三維點云數(shù)據(jù)的處理.本文實驗是在CPU coreTM2，內(nèi)存2 G，硬盤250 G，Matlab 7.0.1和Imageware 12平臺環(huán)境下進(jìn)行的，點云數(shù)據(jù)數(shù)量為38 645.

具體實驗步驟如下:

1) 啟動Imageware逆向工程應(yīng)用軟件，打開三維激光掃描儀掃描后形成的.asc點云數(shù)據(jù)文件，原始點云數(shù)據(jù)顯示如圖1所示.

2) 使用Imageware打開點云信息對話框，可以方便地得到點云數(shù)據(jù)的基本信息，根據(jù)點云形狀進(jìn)行區(qū)域劃分，選擇長方形作為最外區(qū)域.區(qū)域劃分如圖2所示，長方形最外區(qū)域頂點坐標(biāo)如表1所示.

圖1 三維激光掃描原始點云數(shù)據(jù)

圖2 原始點云數(shù)據(jù)長方體最外區(qū)域坐標(biāo)

3) 最外區(qū)域細(xì)化.對本文要處理的點云數(shù)據(jù)，分析其特點后，初步設(shè)定小長方體區(qū)域的長、寬、高值分別為5、5、3，得到如表2所示的關(guān)于小長方體區(qū)域的數(shù)據(jù).

4) 使用Matlab編程實現(xiàn)曲率估算.

實驗結(jié)果表明，直接對點云做曲率估算，計算機(jī)會陷入死循環(huán)，無法得到曲率估算的結(jié)果.引入?yún)^(qū)域劃分后，能快速得到曲率估算的結(jié)果，同時處理結(jié)果能滿足后續(xù)工作的需要.

表1 長方體最外區(qū)域頂點坐標(biāo)

表2 小長方體區(qū)域的邊長與個數(shù)

4 結(jié) 論

對大規(guī)模點云數(shù)據(jù)進(jìn)行區(qū)域劃分后，可以在普通計算機(jī)上實現(xiàn)曲率估算.本文所采取的方法可以推廣到任意形狀的大規(guī)模點云數(shù)據(jù)的曲率估算，并不局限于點云的形狀，這對在普通計算機(jī)上實現(xiàn)散亂點云數(shù)據(jù)的曲率估算具有重大的推廣意義.

[1] PAULY M，GROSS M, KOBBELT L P.Efficient simp lification of point-sampled surfaces[C]//Proceedings of Visulization 2002.VIS 2002.IEEE.Boston: Is.n.I，2002: 163-170.

[2] MILROY M J，BRADLEY C，VICKERS G W.Segmentation of a wrap-around model using an active contour[J].Computer-Aided Design，1997，29(4):299-320.

[3] HUANG Jianbing，MENG Chiahsiang.Automatic data segmentation for geometric feature extraction from unorganized 3-D coordinate points[J].IEEE Transactions on Robotics and Automation，2001，17(3):268-279.

[4] 劉勝蘭，周儒榮，張麗艷.三角網(wǎng)格模型的特征線提取[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2003，15(4):444-448.

[5] 胡鑫，習(xí)俊通，金燁.基于圖像法的點云數(shù)據(jù)邊界自動提取[J].上海交通大學(xué)學(xué)報，2002，36(8):1118-1120.

[6] YANG M，LEE E.Segmentation of measured point data using a parametric quadric surface approximation[J].Computer-VIS 2002.IEEE Aided Design，1999，31(7):449-457.

[7] 朱心雄.自由曲線曲面造型技術(shù)[M].北京:科學(xué)出版社:2000:28-31.

[8] 張麗艷.逆向工程中模型重建關(guān)鍵技術(shù)研究[D].南京:南京航空航天大學(xué)機(jī)電學(xué)院，2001.