三维扫描关键技术分析

三维扫描关键技术1 基于仿射不变矩的三维多面体特征匹配识别三维目标识别是通过分析二维图像来完成，首先建立三维模型，再比较二维 图像和三维模型间特征来判断二维图像中是否为正确目标。三维物体在二维平面上的成像过程在数学上可以用透视变换来描述，而当目 标距离摄像机的距离远远大于目标尺寸时，二维仿射变换可以作为透视变换的近 似。仿射不变矩由于具有对平移，旋转,尺度，以及仿射变换具有不变性。而广 泛运用到各种复杂条件下的目标识别。仿射不变矩对于识别三维空间中的二维平 面目标具有很好的效果，但是对于三维物体，由于无法知道目标深度信息,所以 仅使用仿射不变矩无法达到很好的效果。对于由多个平面围成的三维多面体，可 以使用仿射不变矩作为多面体的每一个平面的面特征，再构造三维多面体的特征 结构图作为目标的结构特征，通过结合两种特征来弥补仿射不变矩识别三维目标 的不足。1.1 仿射不变矩及不变矩标准化图像在几何上的各种变形用数学变换形式描述或是近似，对于由于二维平面在三维空间中旋转造成的几何变形用二维仿射变换来表示。正确识别三维空间的 二维平面目标，必须找出对二维仿射变换具有不变性的特征量。仿射不变矩作为一种基于矩特征的特征量，对于二维仿射变换具有不变性。具有仿射不变特性的 仿射矩是在几何矩的基础上导出的。基本几何矩的表达式：1)区域D内图像函数f (x + y)的p + q阶原点矩为M二JJxpyq f (x, y)dxdy。 pq 区域D内图像函数f (x + y)的p + q阶中心矩为 Du 二 x - x )p (y - y )qf (x, y)dxdy。pq00x = M / M2 01000y = M / M00100D其中 (x , y )为图像重心00所引用仿射矩的表达式为：F = (u u 一 u 2 )/u 4 ,1 20 02 11 00F = -u 2 u 2 + 6u u u 一 4u u 3 一 4u 3 u + 3u 2 u 2 / u 7 ,2 30 0330 21 0330 1221 0321 1200F = u (u u 一 u2) u (u u 一 u u ) + u (u u 一 u2)/ u7 ,3 20 21 03 12 11 30 03 21 12 02 30 21 21 00F = u 3 u 2 一 6u 2 u u u 一 6u 2 u u u + 9u 2 u 2 + 12u u 2 u u4 20 0320 11 12 0320 02 21 0320 1220 11 21 03+6u u u u u 一 18u u u u u一 8u 3 u u 一 6u u 2 u u20 11 02 30 0320 11 02 21 1211 30 0320 02 30 12+9u u2 u2 + 12u2 u u u 一 6u u2 u u + u3 u2 / uil20 02 2111 02 30 1211 02 30 1220 0300F = u u 一 4u u+ 3u 3 / u 6 ,5 40 04 i3 3i 2200F = u u u + 2u u u 一 4u u 2 一 4u u 2 一 u 3 / u 6 。6 40 04 22 3i 22 i3 40 i3 04 3i 2200仿射不变矩数量级标准化：各不变矩值的数量级往往存在较大差异，当图像灰度值提高九倍时，由式（1）可得中心矩，u会增大九，仿射不变矩也会根据 不变矩的阶数而发生一定的变化，因此，在利用仿射不变矩进行图像识别时，考 虑各种不变矩的数量级并把它们进行标准化是有必要的。针对这些问题，有一种 将普通不变矩进行数量级标准化的方法，定义如下：其中 sgn( x)二0x 0(3)（ 4 ）这样一来每一种不变矩都和九-1成正比，都处在同样的数量级，这对分类识别是十分有利的。以下的不变矩值都采用了式 （3）、（4）规定的数量级标准化1.2 多面体的识别1.2.1 多面体的结构图表示三维多面体定义：由有限个空间平面围成的三维物体。假定多面体目标为O，以特征集T表示目标O所有表面特征S （F, R）的集合。T= S (F,R) | i =1,.,n 。其中n为目标总面数，目标的每一个面特征S （F,R）包含了两个特征量，其中F表示面S的平面特征（在这里我们使用仿射不变矩F作为其平面特征），而R表示该平面S在多面体中的结构特征，即与该平面共线的平面的标号集。这样就可以通过该集合建立一个相应的多面体目标的特征结构图。1.2.2 多面体的识别步骤首先建立三维目标的标准模型，分别计算该模型各个面的仿射不变矩值得到 其每个面的面特征F,再根据每个面之间的结构特征得到其结构特征R ,从而得 到S (F, R)。然后画出多面体目标的特征结构图，得到目标特征集T。对待识别 i 二维图像：(1) 对图像进行边缘检测，得到图像的初步轮廓。(2) 利用图像的初步轮廓对原图进行分割，得到图像的各个组成面。(3) 计算得到各个面的仿射不变矩特征集F作为该面的面特征量。(4) 对分割结果进行分析得到各个面的特征结构R。(5) 分别将各个面的特征S (F,R)放到T中进行匹配，判断是否属于该集合。i(6) 根据各个面的匹配结果判断待识别目标。1.3 结论在不同视角，不同的尺度下甚至在部分面被遮挡的情况下，基于仿射不变矩 的识别算法都能很好对目标图像进行正确的判断，从二维图像中正确的识别出与 三维多面体目标匹配的部分。该算法有一定局限性，首先该算法只能针对多面体目标，其次对分割具有一 定要求，所以当图像光照强度不够，或者图像比较模糊的情况下就会对识别产生 很大的影响。2基于曲率仿射不变量的快速目标识别由于目标轮廓的识别过程更接近人眼的视觉效果，而且基于轮廓的识别相比 基于内容的识别用到更少的数据量，因此可以采用轮廓来识别目标。基于曲率不 变量的快速目标识别方法可以做到高性能且低复杂度的识别，其方法利用基于曲 率的仿射弧长参数构造仿射不变量，由于轮廓的曲率信息可以有效描述轮廓的特 征，这使得所构造的不变量具有很强的特征表示能力。为了实现快速识别，可以 对所构造不变量的极值点进行了轮廓起始点定位，进而调整不变量并通过相似度 比较最终实现目标识别。这样就避免了高复杂度的循环移位匹配。关于封闭轮廓的目标识别问题：令x , y t和x , y t分别表示目标轮廓0 0 m mC (x, y)和模板轮廓C (x, y)上的坐标点其中上标T表示向量的转置。如果轮廓OMC (x, y)和C (x, y)之间存在仿射变换，则可以表示为OMxx0=Am_ y _y _0m+ b1)维列向量，它包含了平移变换。图 1 显示了一个模板轮廓和它对应的一个仿射目其中A是一个2X2非奇异矩阵，它包含了尺度、旋转和扭曲变换；b是一个二图 1 模板轮廓及对应的仿射目标轮廓 仿射不变量是一个描述目标形状的仿射不变特征的函数，它在三维目标识 别中具有重要的作用。令Inv(t)为一个利用轮廓C (x, y)上的坐标点计算得到的 M不变量，Inv(t)为一个利用C (x, y)上的坐标点计算的不变量。如果式成立, O则Inv(t)和Inv(t)之间的关系可表示为Inv(t)=vnv(t)(2)其中，v主0为一个常量。如果v =1，Inv(t)就称为绝对不变量，否则称为相对 不变量。式(2) 给出的是目标轮廓与模板轮廓起始点配准好的情况下的关系，针 对一般情况，不变量Inv和Inv(t)之间是存在一定的循环移位量的。 作为一种简单且基本的不变量，仿射不变参数可以把轮廓映射成为一个参数。 仿射弧长参数T :c二 J x(t) y(t) - x(t) y(t) ddt( 3)m其中x(t儿y(t)和x(t), y(t)分别为x和y针对自变量t的一阶和二阶导数。 包围面积参数p：a2u4)这两种仿射不变参数主要用于参数化轮廓。其中，仿射弧长 p 是基于轮廓的曲 c率信息而构造的，所以它在描述轮廓特征(尤其是细节特征) 上更具优势，但由于它包含高阶导数使得它的抗噪性能较差。包围面积参数p是基于轮廓的包围 a面积所构造的，它具有更好的抗噪性，但描述轮廓特征的能力要弱于P。c2.1 基于曲率仿射不变量的目标识别在仿射目标的识别前需要构造一种基于曲率的仿射不变量。图 2 显示了采用 本方法的整个识别系统的流程图：图 2 基于曲率仿射不变量的仿射目标识别系统在构造不变量之前，需要进行一组预处理步骤。假设要处理的对象为某个感 兴趣区域的目标图(或轮廓图)。在接下来的预处理中需要参数化轮廓图，使二维 的轮廓图数据转化为一维的参数化数据。在参数化过程中，考虑到包围面积参数 T对噪声的不敏感性，可以选择T来参数化轮廓。为了去除仿射变换中的平移 aa分量，每一个待处理轮廓的质心都移至原点。然后，参数化的轮廓进行预滤波来 去除噪声。最后，轮廓以等仿射间隔(即，包围面积)进行重采样并以轮廓的总包 围面积对其进行归一化，以获得尺度不变性。令经过预处理后的轮廓参数化表示 为x (n),y (n)T (针对模板)和x (n), y (n)T (针对目标)，其中N为轮廓总采 m m O O s样点数。在上述预处理之后，轮廓就具有了平移不变性和尺度不变性。 仿射变换中的旋转变换和扭曲变换的去除就要依靠一个有效的仿射不变量 的构造了。参数T基于曲率信息，所以更擅长于描述轮廓特征。利用T的这个优cc 势来构造不变量：我们采取这样一种方式：针对每一个等间隔(即，等包围面积) 的轮廓段上，分别计算它所对应的T值。将这些分段计算的T值组合起来就构造 cc 出了该轮廓的仿射不变量，如下所示：5)f (n)=艺 3 xo (s) y (s) - x” (s) y (s)oooo(n)=迟3 xm (s) y (s) - xm (s) y (s)1mmn g 0,1,.,N 1(6)s其中，符号和分别表示相对于曲线弧长(而非包围面积参量s)的一 阶和二阶导数。这样构造的不变量可以保证针对移位、尺度和扭曲多具有不变性。起始点定位及目标识别：为了降低复杂度同时不损失识别性能，可以采用不变量函数的极值点来定位起始点，因为不变量(5)、(6)的极值点有效地描述了轮 廓的主要特征。令目标轮廓的极值点总数为 No ，模板轮廓极值点总数为 NM 。extext针对模板轮廓，这里直接选取f (n)中对应最大绝对值的极值点作为轮廓的起始 m点。这样保证了模板轮廓的起始点与轮廓的主要特征相对应。这里可以构造了一 个评价函数来描绘匹配度。为方便分析，假设， f (0) 为模板不变量中所选定的 m起始点。当然，如果 f (0) 不是选定的起始点，需要按照前述规则找到该点并对 m不变量进行循环移位使其位于 f (0) 。评价函数定义如下：mF (l) =11 R - R( i-i) II +WP - Pd - Dlll e 1,., No (7)mo2Um o2ext其中，R和P分别表示不变量函数极值点的幅值向量和位置向量，它们分别由极 值点的幅值和位置索引组成。这里的脚标(m )、( o)分别表示模板和 目标。R( i)为R的循环移位后的向量(循环移位量为/), P( i)为对于R (i)的新 o o o o 位置向量。 W 为权值。我们期望幅值和位置具有同等的重要性，所以这里选取 权值W为E(llR - R(l-1) ll )W =mo2E(II P -P(i-i)II )(8)m o2其中，E()表示均值。最优匹配情况就出现在评价函数F(l)达到最小的时候。在上述过程中，还有另外一个因素也是必须要考虑的，即：轮廓的走向 (顺时针或逆时针)。为了获得更合理的定位结果，有必要对相反轮廓走向的情况 再求一次评价函数。这一点其实并不难，只要将R和P首末倒置，再重计算式 oo(7) 即可。根据轮廓不同走向计算出来的两个评价函数中取最小值所对应的极值 点即为最终选定的f (n)的起始点。o事实上，并不需要计算式(7)中的所有l。从理论上说，作为模板轮廓起始点 的最优匹配点，目标轮廓的起始点的幅度也应该是一个比较大的值。因为待求解 的l仅选择为三个值l e l,l ,l ，其中，第l,l ,l个极值点为f (n)中对应前三个1 2 31 2 3o最大幅值的极值点。基于这种简化，式(7)的计算量很大程度上降低了，同时也 并没有损失匹配精度。式(7)其实给出的是一种理想情况 NM =NO 的表示。针对一般的情况extextNM工No，所述的匹配过程中还应当容许极值点一定的位置偏移量。这一点其extext实可以通过下述简单方式实现。如R与P构造方式不变，针对每一个待选的l， mm在构造R(l)和P(l)时，首先要对f (n)做循环移位调整，使调整后的第一个极值点 ooo刚好为调整前的第l个极值点。对于R(l)和P(l冲的第n个元素所对应的极值点，oo就选取为与模板第 n 个极值点在不变量函数对应位置上最接近的那个目标极值 点即可。在起始点定位完成之后，模板和目标的不变量函数f (n)和f (n)需要进行相 mo 应的循环移位调整，以保证调整后的不变量函数的第一个点刚好对应于选定的起 始点。令模板和目标调整后的新不变量分别为f new (n)和fnew (n)。目标即可通过 mo 直接比较其不变量和每个模板的不变量的相似度实现识别，即f new (n) fnew(n)omS (fnew(n)，/new(n) = V n V mo| f new ( n) |2| f new ( n) |2omnn2.3 结论经理论计算，这个算法的复杂度 (包括构造不变量函数和起始点定位 )为O(N + No + Nm )。通常，极值点的个数远低于采样点数，所以复杂度可简化为 s ext extO(N )。它与高效率的傅里叶描述子的复杂度O(N lgN )几乎是在同一数量级上 s s s的。这个算法还是比较可行的，在快速识别领域有应用潜力。