孟祥林

(黑龍江科技大學(xué) 現(xiàn)代制造工程中心, 哈爾濱 150022)

?

三維圖像重構(gòu)的點云精簡算法

孟祥林

(黑龍江科技大學(xué) 現(xiàn)代制造工程中心, 哈爾濱 150022)

為解決光學(xué)三維測量系統(tǒng)測量數(shù)據(jù)的精簡問題,提出一種基于圖像重構(gòu)三維的點云精簡算法。利用數(shù)字圖像處理技術(shù),建立數(shù)字圖像像素點與三維數(shù)據(jù)點的對應(yīng)關(guān)系表,采用分級方式建立查找表,根據(jù)建立的查找表對三維數(shù)據(jù)進行精簡。實驗結(jié)果表明:精簡算法將數(shù)據(jù)從712 068個點有效地精簡至132 064個點,文件大小也從21.6 M減小到4 M。該方法能有效對數(shù)據(jù)進行精簡,兼具基于距離和曲率精簡的優(yōu)點。

圖像處理; 查找表; 精簡

0　引　言

光學(xué)三維測量技術(shù)具有數(shù)據(jù)獲取速度快、數(shù)據(jù)豐富等優(yōu)勢,廣泛應(yīng)用于形貌測量、自動在線檢測、產(chǎn)品質(zhì)量分析和文物保護等領(lǐng)域。隨著硬件技術(shù)的發(fā)展,相機的分辨率越來越高,一次測量獲得的數(shù)據(jù)量可達幾十萬至幾百萬。為了獲得被測物的全部的形貌數(shù)據(jù),一般需要根據(jù)被測物的復(fù)雜程度對其進行多個角度的測量,導(dǎo)致最終的數(shù)據(jù)量大的驚人,但是,有些部分特征平緩大部分?jǐn)?shù)據(jù)點是冗余的,而有些部分特征明顯需要較大的數(shù)據(jù)量來描述。

目前,實現(xiàn)三維數(shù)據(jù)精簡的方法主要有兩種:一是基于距離精簡[1-2]。根據(jù)圖像與三維數(shù)據(jù)的對應(yīng)關(guān)系,在重構(gòu)階段采用固定間隔計算三維數(shù)據(jù),根據(jù)間隔大小不同使數(shù)據(jù)量成倍的減少。這種方法比較簡單,但無法區(qū)分被測物上面的特征,導(dǎo)致棱角等細(xì)節(jié)特征丟失,而有些特征平緩的仍然有大量冗余數(shù)據(jù)。二是基于曲率精簡[3-4]。這種方法只在三維數(shù)據(jù)獲取結(jié)束后,計算出三維數(shù)據(jù)的曲率,達到精簡的目的。利用曲率精簡可使數(shù)據(jù)疏密有致,既保留了豐富的細(xì)節(jié)特征,也達到了減少數(shù)據(jù)量的目的。但這一方法舍棄了圖像這一豐富的信息,僅僅利用三維數(shù)據(jù)計算,效率極低,并且只能在測量結(jié)束后才能處理,測量過程中,仍需要面對包含大量冗余信息的數(shù)據(jù)。因此,有必要在測量過程中對數(shù)據(jù)進行必要的精簡處理,在不影響形貌特征的基礎(chǔ)上用盡量少的數(shù)據(jù)點重現(xiàn)整個被測物。

1　點云精簡算法

1.1向量內(nèi)積

設(shè)兩個非零單位向量a和b,則有a垂直于b、a平行于b、a與b成一定角度這三種情況。當(dāng)向量a垂直于向量b時，有|a·b|=0;當(dāng)向量a平行于向量b時，有|a·b|=1;當(dāng)a與b成一定角度時，有0<|a·b|<1;其中符號“·”代表向量的內(nèi)積或稱為點積。事實上，向量a、b之間的內(nèi)積與它們夾角的余弦成正比。|a·b|的值越大表明它們之間的夾角越小,其平行度越高。

1.2點云精簡

圖像在測量過程中為測量數(shù)據(jù)提供了豐富的附加信息,每一個數(shù)據(jù)點都對應(yīng)于一個圖像上的像素位置,這種關(guān)系反過來則不成立。由于拍攝圖像的角度以及三維物體的空間遮擋等問題，導(dǎo)致圖像上一些像素?zé)o法重構(gòu)出三維數(shù)據(jù),也就不存在對應(yīng)關(guān)系,因此這種關(guān)系是單向的。為解決光學(xué)三維測量系統(tǒng)的測量數(shù)據(jù)精簡問題,提出基于圖像重構(gòu)三維的點云精簡算法,利用測量過程中拍攝的圖像,以及對應(yīng)本次測量的三維數(shù)據(jù)進行精簡。由于一次測量的點云數(shù)據(jù)空間密度不會相差太遠(yuǎn),因此，對于具有不同曲率特征的區(qū)域,其數(shù)據(jù)的冗余程度就不同,特征變化越平緩的區(qū)域冗余數(shù)據(jù)越多,特征變化越劇烈的區(qū)域冗余數(shù)據(jù)越少?；谝陨戏治?采用分等級精簡策略,為了消除精簡帶來的精度下降,假設(shè)同一次測量特征變化越劇烈的區(qū)域不進行精簡,將其精簡等級設(shè)定為1,這樣就達到了既能保證原來數(shù)據(jù)的精度,又能達到精簡的目的。具體流程,見圖1,算法如下。

圖1　精簡流程

Step 1設(shè)定精簡區(qū)域的級別,不同的等級具有不同的精簡率,此處以三個等級為例。特征平緩區(qū)域需要精簡量大,設(shè)定精簡級別為3;特征連續(xù)變化的區(qū)域設(shè)定精簡級別為2;棱角、邊界等區(qū)域需要全部保留,設(shè)定精簡級別為1;對于沒有對應(yīng)點云的區(qū)域設(shè)定精簡級別為0。在實際應(yīng)用中可視情況設(shè)定更多的精簡等級。

Step 2由三維數(shù)據(jù)與圖像有單向?qū)?yīng)關(guān)系,任一三維數(shù)據(jù)點與圖像的像素點都具有對應(yīng),反之不成立,即有些像素點并沒有參與計算三維數(shù)據(jù)點,忽略沒有對應(yīng)關(guān)系的像素點。建立數(shù)字圖像上所有參與計算三維數(shù)據(jù)的像素點與計算所得的三維數(shù)據(jù)點之間的對應(yīng)關(guān)系表。

Step4根據(jù)哈希表內(nèi)的數(shù)據(jù)點構(gòu)造協(xié)方差矩陣,利用反冪法計算矩陣的按模最小特征值對應(yīng)的特征向量,此特征向量即為對應(yīng)哈希表內(nèi)所有數(shù)據(jù)點的近似法線[4],單位化法線并按點的對應(yīng)順序存儲。

Step5建立與圖像等大小的精簡區(qū)域查找表,并初始化精簡區(qū)域等級為0。根據(jù)每個哈希表對應(yīng)的法線,分別計算其與周圍n×n范圍內(nèi)的哈希表對應(yīng)的單位法線的點積并取絕對值,最后求和。根據(jù)上述分析,和的大小越接近n×n,則表示該點與周圍小范圍內(nèi)的點平行度越高,該區(qū)域特征越平緩,精簡的級別適宜設(shè)置大些;反之,和的大小越接近0則表示該區(qū)域特征明顯,細(xì)節(jié)豐富,精簡的級別可設(shè)置小些,據(jù)此劃分出不同精簡區(qū)域。根據(jù)Step2所建立的對應(yīng)關(guān)系表,找到當(dāng)前哈希表內(nèi)的所有數(shù)據(jù)點對應(yīng)精簡區(qū)域查找表內(nèi)的位置序號,置精簡區(qū)域查找表中對應(yīng)的區(qū)域的等級為3、2或1。

Step6根據(jù)建立的精簡區(qū)域查找表,對相應(yīng)區(qū)域內(nèi)對應(yīng)的點云進行精簡。

2　實驗結(jié)果與分析

圖2為任意位置測量的一張折紙圖像,圖3為采用文中算法進行精簡的區(qū)域劃分情況,不同區(qū)域以顏色區(qū)分。圖4為精簡前的數(shù)據(jù),圖5為采用文中算法進行精簡后的數(shù)據(jù)。由圖5可見文中提出的精簡算法區(qū)域劃分明確,數(shù)據(jù)與區(qū)域的對應(yīng)十分精確,既較好的保留了邊界棱角和曲率變化大的特征,又達到了精簡的目的。利用文中提出的精簡算法有效地將數(shù)據(jù)從712 068個點精簡至132 064個點,文件大小也從21.6M減小到4M。對應(yīng)圖3中不同區(qū)域的精簡結(jié)果見表1。

圖2　任意位置圖像

圖3　精簡區(qū)域劃分

由表1可以看出區(qū)域0沒有點云,故不需要做精簡;區(qū)域1屬于邊界及棱角等特征豐富區(qū),沒有做精簡,但是這樣的區(qū)域在本例中比重較小,對整體的影響較小;區(qū)域2和區(qū)域3屬于精簡的重點區(qū)域,所占比例也最大,分別精簡掉了77.15%和93.46%的數(shù)據(jù)點,精簡效果十分明顯。

圖4　精簡前三維數(shù)據(jù)

圖5　精簡后三維數(shù)據(jù)

區(qū)域點數(shù)量精簡前精簡后精簡比例/%000015033350333022357935387477.1534259422785793.46總計71206813206481.45

以文中精簡后剩余點數(shù)為目標(biāo),采用基于距離的精簡方式和基于曲率的精簡方式得到結(jié)果分別如圖6和7所示。這兩種方法對于特征區(qū)分不明顯,對物體表面變化不敏感。對比圖5、6和7中同一位置的處理結(jié)果,即箭頭所指的局部放大細(xì)節(jié)圖?；诰嚯x的精簡方法雖然效率高,但對所有數(shù)據(jù)都進行精簡,導(dǎo)致有的區(qū)域冗余度仍然很大,而有的區(qū)域必然會損失精度;基于曲率的精簡方法雖然能保留劇烈變化的過渡區(qū)域,但是不能對曲率連續(xù)變化的其他地方有效的區(qū)分;對比分析可知,文中所述方法在精簡的同時既能對不同區(qū)域進行相應(yīng)的精簡,同時保留邊界和曲率變化劇烈的區(qū)域的原貌以保證精簡后的數(shù)據(jù)和原來的數(shù)據(jù)有相同的精度,兼顧效率和區(qū)分處理兩個優(yōu)點,由于精簡分級可以靈活設(shè)定,其使用的靈活性也更大。

圖6　基于距離的精簡結(jié)果

圖7　基于曲率的精簡結(jié)果

3　結(jié)束語

文中所提出的圖像重構(gòu)三維的點云精簡算法,將數(shù)字圖像與三維數(shù)據(jù)結(jié)合起來,整個精簡過程中,有效地利用了圖像信息,提高了精簡計算的效率,同時對精簡區(qū)域可以根據(jù)預(yù)設(shè)的不同等級進行精確劃分,獲得理想的精簡數(shù)據(jù)。對精簡等級可靈活修改設(shè)置,由于是基于查找表的方式,不增加計算的復(fù)雜度,具有效率高、精簡區(qū)域劃分精確、精簡等級設(shè)置靈活、易于實現(xiàn)等優(yōu)勢。

[1]萬軍, 鞠魯粵. 逆向工程中數(shù)據(jù)點云精簡方法研究[J]. 上海大學(xué)學(xué)報, 2004, 10(1): 26-29.

[2]BUDAKI, HODOLIC J, SOKOVIC M. Development of a programme system for data point pre-processing in reverse engineering[J]. Journal of Materials Processing Technology, 2005, 162/163(5): 730-735.

[3]周綠, 林亨, 鐘約先, 等. 曲面重構(gòu)中測量點云精簡方法的研究[J]. 中國制造業(yè)信息化, 2004, 33(5): 102-104.

[4]朱煜, 康寶生, 李洪安, 等. 一種改進的點云數(shù)據(jù)精簡方法[J]. 計算機應(yīng)用, 2012, 32(2): 521-523.

[5]SUN W, BRADLEY C, ZHANG Y F, et al. Cloud data modeling employing a unified non redundant triangular mesh [J]. Computer Aided Design, 2001, 33(2): 183-193.

[6]LEEK H, WOOH, SUK T. Data reduction methods for reverse engineering [J]. The International Journal of Advanced Manufacturing Technology, 2001, 17(3): 735-743.

[7]LEEK H, WOO H, SUK T. Point data reduction using 3D grids [J]. The International Journal of Advanced Manufacturing Technology, 2001, 18(3): 201-210.

(編輯李德根)

Concise algorithm based on image reconstruction of 3D point cloud

MENGXianglin

(Modern Manufacture Engineering Center, Heilongjiang University of Science & Technology, Harbin 150022, China)

This paper seeks to streamline measurement data used for three-dimensional optical measurement system and proposes a novel algorithm for reducing measurement point cloud based on image. The algorithm begins by creating corresponding relation tables between digital image pixels and 3D data points by using image processing technique, proceeds to establish a lookup table by adopting hierarchical approach, and ends with streamlining 3D data according to the table. Experiment shows that the algorithm permits a point cloud to be reduced effectively from 712 068 points to 132 064 points using, and the file size to be reduced from 21.6 M to 4 M. The algorithm features a combination of an effective data reduction and simplification based on distance and curvature

image processing; lookup table; reduction

2013-06-06

國家科技重大專項項目(2020ZX04016-012);國家自然科學(xué)基金面上項目(51075128)

孟祥林(1982-),男,遼寧省凌源人,工程師,碩士,研究方向:逆向工程,E-mail:mxl3456@163.com。

10.3969/j.issn.1671-0118.2013.05.017

TP317.4

1671-0118(2013)05-0475-04

A