[科普中国]-形状匹配

形状也是描述图像内容的一个重要特征。利用形状进行匹配有三个问题值得注意。首先，形状常与目标联系在一起，所以形状特征可以看作是比颜色或纹理要高层一些的特征。要获得有关目标的形状参数，常要先对图像进行分割，所以形状特征会受图像分割效果的影响。其次，目标形状的描述是一个非常复杂的问题，事实上，至今还没有找到形状的确切数学定义，使之能与人的感觉相一致。最后，从不同视角获取的图像中目标形状可能会有很大差别，为准确进行形状匹配，需要解决平移、尺度、旋转变换不变性的问题。

形状匹配简介形状匹配就是在形状描述的基础上，依据一定的判定准则，计算两个形状的相似度或者非相似度。两个形状之间的匹配结果用一个数值表示，这一数值称为形状相似度。形状相似度越大，表示两个形状越相似。非相似度也称为形状距离。与相似度相反，形状距离越小，两个形状越相似。

1．度量准则

采用SC形状描述子对获得的区域形状进行描述，依据z。统计一量作为形状距离的度量准则。若两个形状上的任一特征点P和q，对应的形状上下文分别为Hp和Hq，则两者之间的匹配代价为：

C（p，q）=X2（hp，hq）=1/2ΣK[hp（k）-hq（k）]2/hp（k）+hq（k）

式中：K为形状上下文描述子的总扇区数，K=S×T；hp（k）与hq（k）为点p和点q的归一化形状上下文，计算公式如下：

对于由点集表示的图像区域轮廓P和目标形状模板Q，P{pi，i =1，2，…，Np}，Q={qj，j=1，2，…，Nq}则形状P和形状Q之间的匹配代价矩阵C（P，Q）为：

形状之间的相似度可以转化为求形状P和形状Q之间的最小匹配代价问题。同时考虑轮廓点的顺序信息，使用动态规划解决形状匹配。1

2．动态规划
给定两个形状点集P ={p1，p2，…，pn}和Q ={q1，q2，…，qn}。按照上式计算P和Q之间的匹配代价矩阵。形状匹配的目标就是寻找一个匹配，令匹配代价之和最小，即

Mg（P，Q）=∑C（pi，g（pi））
M* =argminM（P，Q）
式中：g（pi）表示在形状点集P和形状点集Q的匹配g中与点pi相对应的Q中的特征点；C（pi，g（pi）），是它们之间的匹配代价。
计算形状距离的具体方法就是，在考虑采样点次序的前提下，寻找两个点集合P和Q中元素之间的对应关系。下图展示了一个简单的匹配例子，其中，n =8，m =7。在定义了匹配点对pi和qi之间的匹配代价C（pi，qi），以及非匹配点对的匹配代价ε的基础上，形状距离可通过图中最短路径问题解决。

假设G =（V，E）是一个有向图，节点集合和边集合分别为V和E。V中的节点对应（n+1）×（m+1）网格中的点。边E有两种类型：权重为E的边，如连接点（i，j）和点（i+1，j）的水平边，以及连接点（i，j）和点（i，j+1）的垂直边；权重为C（pi，qi）的对角边，连接点（i，j）和点（i+1，j+1）。采用动态规划解决匹配问题如图所示，行列中的各元素分别对应于两个形状轮廓线上的采样点，有向图G中从点（0，0）到点（n，m）的路径就对应形状P和Q之间的匹配：路径中从节点（i，j）出去的对角边，代表点pi与点qi相对应。匹配路径从第一行的某一个矩阵项开始，沿对角线方向到最后一行的某一矩阵项结束。 经过多尺度分割获得一系列图像块区域，采用形状描述方法对区域形状进行描述，得到各个区域的SC描述向量；同时，利用形状匹配衡量分割区域与目标模型之间的相似度，选取相似度高的区域作为目标的种子区域。1

形状匹配要素形状是描述图像内容的一个重要特征，因此，可以利用形状进行匹配。但采用形状进行匹配应综合考虑以下三个问题。

（1）形状常与目标特征相联系，与颜色特征相比，形状特征被认为是更高层次的图像特征。要获取目标的有关形状参数，一般应先对图像进行分割，所以形状特征会受图像分割结果精度的影响。

（2）目标形状的描述是一个非常抽象和复杂的问题，目前还没有与人的感觉一致且被大多数人所接受的关于图像形状描述的确切数学定义。

（3）从不同视角和方法获取的图像中目标形状可能会有很大差别，为准确进行形状匹配，应保证平移、尺度、旋转变换的不变性等。

目标轮廓在一定程度上可以表示目标物体的形状。轮廓是由物体的一系列边界点所形成的。因此根据图像分析的相关理论可知，在较大尺度下一般能较可靠地消除对物体边界点的误检。但却对边界的定位易产生不准确；相反，在较小尺度下，虽然增加了边界点误检的比例，但对物体或区域真正边界点的定位却比较准确。因此，可以结合两者的优点，即可先在较大尺度下检测出真正的边界点，然后在较小尺度下对边界点进行较精确的定位。

目前。常用的形状匹配法主要有不变矩法、几何参数法、特征模表示法、边界方向直方图法、小波重要系数法以及我国学者杨翔英、章毓晋于1999年发表的小波轮廓表示法等许多方法。有着数学显微镜之称的小波变换与分析作为一种多尺度、多分辨率的分析工具，比较适合于对图像进行多尺度的边界检测。2

形状匹配工具形状匹配工具（Register）通过使物体和目标物体尽量重合定义一个几何变换。

可以用一个常见问题作为例子，对旧车型外观故局部改动，有时在真实车体上用油泥进行。改动部分的数据如果和原始三维数据坐标有偏差，可以用形状匹配工具（Register）把测量数据移动到合适的位置。使用工具时，选取三对起始点和目标点，并根据情况选取匹配区域，通过三对点使物体初步移动到目标位置，然后进行若干次迭代运算，使匹配区域与目标物体形状尽可能贴合。

形状匹配工具通过点击几何变换工具箱中的按钮Register或下拉菜单Modify→Move→Register激活，弹出形状匹配工具窗口，有Register，lteration，Progress3个选项卡，如图所示是Register选项卡，定义几何变换参数。

1.Register选项卡

（1）Select：取消已有形状匹配定义，重新选取物体定义形状匹配。

（2）Obie****et：选取要进行形状匹配的物体。

（3）**Region：**在要匹配的扫描点云数据上选一块或几块匹配参考区城，选取特征明显的局部而不用全部数据能提高匹配速度和精度。最终移动的是物体全部而不只是这几块参考区域,不用该按钮则用扫描点云数据全体进行定位计算，点击按钮增加匹配参考区域，原始数据。

（4）Reference：选取目标物体。

（5）Manua：激活位置选取窗口，选取至少3对起始点和目标点，对物体进行初步定位。为便于操作，起始点在要移动的物体上，参考点在目标物体上。选取能准确定位的位置可以减少计算时间提高匹配精度，如图所示。

（6）Move：只有在形状匹配定义完成后才可用。上一次定义的形状匹配参数（匹配前后的位置关系）在定义新形状匹配或退出ICEM Surf前保持不变，随时选取要移动物体（可以使用工具后重新进人形状匹配工具），点击Move按钮即按上次定义的匹配关系移动物体。定义形状匹配移动数据后，用Move按钮把边界按同一几何变换参数移动到合适位置。

（7）Save：保存两个工作平面，分别代表物体形状匹配前后的位置，退出工具后用坐标映射工具（2 Planes）根据这两个工作平面定义几何变换，重新使用形状匹配结果。3

2. Iteration选项卡

如图所示，定义物体初步定位后的迭代参数。

（1）Iterations：定义在进行初步定位后形状匹配最大迭代次数。

（2）Angle、Translation：迭代过程中，通过一系列平移和旋转使物体与目标物体逐步接近贴合。达到最大迭代次数前已经满足匹配精度，迭代过程提前结束。Angle，Translation输人框定义角度和平移距离作为匹配精度准则：下一次计算后物体的角度、位置调整量小于Angle，Translation输人框中定义值，认为匹配精度满足要求，停止迭代过程。

3. Progress选项卡

如图所示，显示迭代进展情况。

（1）Range：在目标物体上定义一一个偏移量。偏移量越小，迭代结束后物体与目标物体偏差量小于该偏移量的区域百分比越大，表示匹配精度越高。

（2）状态条... %：显示迭代完成后，要移动物体上所选区域与目标物体偏差小于在Range输人框中定义偏差值区域的百分比。

（3）Dela... % ：每次迭代后，新增加与目标物体偏差小于在Range偏差值区域的百分比。3

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学