孟祥林

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

?

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

孟祥林

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

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

圖像處理; 查找表; 精簡(jiǎn)

0　引　言

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

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

1　點(diǎn)云精簡(jiǎn)算法

1.1向量?jī)?nèi)積

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

1.2點(diǎn)云精簡(jiǎn)

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

圖1　精簡(jiǎn)流程

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

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

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

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

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

2　實(shí)驗(yàn)結(jié)果與分析

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

圖2　任意位置圖像

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

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

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

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

區(qū)域點(diǎn)數(shù)量精簡(jiǎn)前精簡(jiǎn)后精簡(jiǎn)比例/%000015033350333022357935387477.1534259422785793.46總計(jì)71206813206481.45

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

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

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

3　結(jié)束語

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

[1]萬軍, 鞠魯粵. 逆向工程中數(shù)據(jù)點(diǎn)云精簡(jiǎn)方法研究[J]. 上海大學(xué)學(xué)報(bào), 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)中測(cè)量點(diǎn)云精簡(jiǎn)方法的研究[J]. 中國(guó)制造業(yè)信息化, 2004, 33(5): 102-104.

[4]朱煜, 康寶生, 李洪安, 等. 一種改進(jìn)的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法[J]. 計(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

國(guó)家科技重大專項(xiàng)項(xiàng)目(2020ZX04016-012);國(guó)家自然科學(xué)基金面上項(xiàng)目(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