三维图像重构的点云精简算法

孟祥林

(黑龙江科技大学 现代制造工程中心, 哈尔滨 150022)



三维图像重构的点云精简算法

孟祥林

(黑龙江科技大学 现代制造工程中心, 哈尔滨 150022)

为解决光学三维测量系统测量数据的精简问题,提出一种基于图像重构三维的点云精简算法。利用数字图像处理技术,建立数字图像像素点与三维数据点的对应关系表,采用分级方式建立查找表,根据建立的查找表对三维数据进行精简。实验结果表明:精简算法将数据从712 068个点有效地精简至132 064个点,文件大小也从21.6 M减小到4 M。该方法能有效对数据进行精简,兼具基于距离和曲率精简的优点。

图像处理; 查找表; 精简

0　引　言

光学三维测量技术具有数据获取速度快、数据丰富等优势,广泛应用于形貌测量、自动在线检测、产品质量分析和文物保护等领域。随着硬件技术的发展,相机的分辨率越来越高,一次测量获得的数据量可达几十万至几百万。为了获得被测物的全部的形貌数据,一般需要根据被测物的复杂程度对其进行多个角度的测量,导致最终的数据量大的惊人,但是,有些部分特征平缓大部分数据点是冗余的,而有些部分特征明显需要较大的数据量来描述。

目前,实现三维数据精简的方法主要有两种:一是基于距离精简[1-2]。根据图像与三维数据的对应关系,在重构阶段采用固定间隔计算三维数据,根据间隔大小不同使数据量成倍的减少。这种方法比较简单,但无法区分被测物上面的特征,导致棱角等细节特征丢失,而有些特征平缓的仍然有大量冗余数据。二是基于曲率精简[3-4]。这种方法只在三维数据获取结束后,计算出三维数据的曲率,达到精简的目的。利用曲率精简可使数据疏密有致,既保留了丰富的细节特征,也达到了减少数据量的目的。但这一方法舍弃了图像这一丰富的信息,仅仅利用三维数据计算,效率极低,并且只能在测量结束后才能处理,测量过程中,仍需要面对包含大量冗余信息的数据。因此,有必要在测量过程中对数据进行必要的精简处理,在不影响形貌特征的基础上用尽量少的数据点重现整个被测物。

1　点云精简算法

1.1向量内积

设两个非零单位向量a和b,则有a垂直于b、a平行于b、a与b成一定角度这三种情况。当向量a垂直于向量b时，有|a·b|=0;当向量a平行于向量b时，有|a·b|=1;当a与b成一定角度时，有0<|a·b|<1;其中符号“·”代表向量的内积或称为点积。事实上，向量a、b之间的内积与它们夹角的余弦成正比。|a·b|的值越大表明它们之间的夹角越小,其平行度越高。

1.2点云精简

图像在测量过程中为测量数据提供了丰富的附加信息,每一个数据点都对应于一个图像上的像素位置,这种关系反过来则不成立。由于拍摄图像的角度以及三维物体的空间遮挡等问题，导致图像上一些像素无法重构出三维数据,也就不存在对应关系,因此这种关系是单向的。为解决光学三维测量系统的测量数据精简问题,提出基于图像重构三维的点云精简算法,利用测量过程中拍摄的图像,以及对应本次测量的三维数据进行精简。由于一次测量的点云数据空间密度不会相差太远,因此，对于具有不同曲率特征的区域,其数据的冗余程度就不同,特征变化越平缓的区域冗余数据越多,特征变化越剧烈的区域冗余数据越少。基于以上分析,采用分等级精简策略,为了消除精简带来的精度下降,假设同一次测量特征变化越剧烈的区域不进行精简,将其精简等级设定为1,这样就达到了既能保证原来数据的精度,又能达到精简的目的。具体流程,见图1,算法如下。

图1　精简流程

Step 1设定精简区域的级别,不同的等级具有不同的精简率,此处以三个等级为例。特征平缓区域需要精简量大,设定精简级别为3;特征连续变化的区域设定精简级别为2;棱角、边界等区域需要全部保留,设定精简级别为1;对于没有对应点云的区域设定精简级别为0。在实际应用中可视情况设定更多的精简等级。

Step 2由三维数据与图像有单向对应关系,任一三维数据点与图像的像素点都具有对应,反之不成立,即有些像素点并没有参与计算三维数据点,忽略没有对应关系的像素点。建立数字图像上所有参与计算三维数据的像素点与计算所得的三维数据点之间的对应关系表。

Step4根据哈希表内的数据点构造协方差矩阵,利用反幂法计算矩阵的按模最小特征值对应的特征向量,此特征向量即为对应哈希表内所有数据点的近似法线[4],单位化法线并按点的对应顺序存储。

Step5建立与图像等大小的精简区域查找表,并初始化精简区域等级为0。根据每个哈希表对应的法线,分别计算其与周围n×n范围内的哈希表对应的单位法线的点积并取绝对值,最后求和。根据上述分析,和的大小越接近n×n,则表示该点与周围小范围内的点平行度越高,该区域特征越平缓,精简的级别适宜设置大些;反之,和的大小越接近0则表示该区域特征明显,细节丰富,精简的级别可设置小些,据此划分出不同精简区域。根据Step2所建立的对应关系表,找到当前哈希表内的所有数据点对应精简区域查找表内的位置序号,置精简区域查找表中对应的区域的等级为3、2或1。

Step6根据建立的精简区域查找表,对相应区域内对应的点云进行精简。

2　实验结果与分析

图2为任意位置测量的一张折纸图像,图3为采用文中算法进行精简的区域划分情况,不同区域以颜色区分。图4为精简前的数据,图5为采用文中算法进行精简后的数据。由图5可见文中提出的精简算法区域划分明确,数据与区域的对应十分精确,既较好的保留了边界棱角和曲率变化大的特征,又达到了精简的目的。利用文中提出的精简算法有效地将数据从712 068个点精简至132 064个点,文件大小也从21.6M减小到4M。对应图3中不同区域的精简结果见表1。

图2　任意位置图像

图3　精简区域划分

由表1可以看出区域0没有点云,故不需要做精简;区域1属于边界及棱角等特征丰富区,没有做精简,但是这样的区域在本例中比重较小,对整体的影响较小;区域2和区域3属于精简的重点区域,所占比例也最大,分别精简掉了77.15%和93.46%的数据点,精简效果十分明显。

图4　精简前三维数据

图5　精简后三维数据

区域点数量精简前精简后精简比例/%000015033350333022357935387477.1534259422785793.46总计71206813206481.45

以文中精简后剩余点数为目标,采用基于距离的精简方式和基于曲率的精简方式得到结果分别如图6和7所示。这两种方法对于特征区分不明显,对物体表面变化不敏感。对比图5、6和7中同一位置的处理结果,即箭头所指的局部放大细节图。基于距离的精简方法虽然效率高,但对所有数据都进行精简,导致有的区域冗余度仍然很大,而有的区域必然会损失精度;基于曲率的精简方法虽然能保留剧烈变化的过渡区域,但是不能对曲率连续变化的其他地方有效的区分;对比分析可知,文中所述方法在精简的同时既能对不同区域进行相应的精简,同时保留边界和曲率变化剧烈的区域的原貌以保证精简后的数据和原来的数据有相同的精度,兼顾效率和区分处理两个优点,由于精简分级可以灵活设定,其使用的灵活性也更大。

图6　基于距离的精简结果

图7　基于曲率的精简结果

3　结束语

文中所提出的图像重构三维的点云精简算法,将数字图像与三维数据结合起来,整个精简过程中,有效地利用了图像信息,提高了精简计算的效率,同时对精简区域可以根据预设的不同等级进行精确划分,获得理想的精简数据。对精简等级可灵活修改设置,由于是基于查找表的方式,不增加计算的复杂度,具有效率高、精简区域划分精确、精简等级设置灵活、易于实现等优势。

[1]万军, 鞠鲁粤. 逆向工程中数据点云精简方法研究[J]. 上海大学学报, 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]周绿, 林亨, 钟约先, 等. 曲面重构中测量点云精简方法的研究[J]. 中国制造业信息化, 2004, 33(5): 102-104.

[4]朱煜, 康宝生, 李洪安, 等. 一种改进的点云数据精简方法[J]. 计算机应用, 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);国家自然科学基金面上项目(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