不规则物体形状匹配综述
物体识别是计算机视觉应用的一项基本任务。识别通常基于目标物体的灰度信息、颜色信息或形状信息。物体识别的目的就是要找到一个包含可以区分不同目标物体的有效信息的描述。由于要识别的物体是事先知道的，所以目标物体的几何特征可以被直接应用到识别任务中。
不规则物体的形状匹配是一种有效的利用物体几何特征进行识别的方法。根据匹配对象的不同，可以将不规则物体的形状匹配分为基于区域的匹配方法和基于轮廓的匹配方法。
一、基于轮廓特征的形状匹配
基于轮廓特征的形状匹配在实际中更为常用，这主要有两方面的原因：一是基于轮廓特征的匹配计算量小，可以较好的满足实时性要求；二是要识别的目标物通常是预先知道的，那么它的几何信息完全可以被用于识别过程中。为了识别不规则物体，主要任务就是设计一种基于（少量的）目标物几何约束先验知识的有效匹配方法。
1. 链码直方图(chain code histogram)
链码直方图将人眼看上去相似的物体归为一类。因此利用它不能进行精确的识别和分类。
方向链码（Freeman链码）是用来表示物体轮廓的典型链码表示法。一条离散曲线可以定义为Z2域内一组数量有限的8联通点。因此，一条数字化二值曲线可以用方向链码表示方向链码是相邻两像素连线的8种可能的方向值。一条曲线被网格离散化后形成n个链码方向，最终此曲线链码可表示为{ai}n，每条链指向8个方向重的一个方向，ai={0,1,2,3,4,5,6,7}，i为像素的索引值，ai是由像素(i)指向像素(i+1)的方向链码。
链码直方图的计算简单而且快速。计算公式如下：
其中，nk是一个链码中链码值k的数目，n是一个链码中的节点数。
(a)编码的方向示意，(b)简单物体形状，(c)形状的链码表示，(d)链码直方图
链码法的特点：
(1) 计算量小，可满足实时性要求；
(2) 具有平移、尺度不变性；
(3) 具有90度旋转不变性；
(4) 规格化链码直方图可以达到更好的旋转不变性。
2. 成对几何直方图(Pairwise Geometric Histogram)
成对几何直方图通过相对角和相对位置特征来描述目标轮廓，并采用关系直方图统计这对几何特征来进行形状索引。采用这种编码方式需要具备一定的前提，即对于一个不规则物体我们可以将其近似为一个几何多边形。这种编码方法可以很好地描述一个多边形物体。
将不规则形状近似为多边形，并将其定义为边缘点的集合。这样它所包含的轮廓边缘（线段）就可以由连续的边缘点来表示。接下来我们计算多边形的PGH：将每一个轮廓边缘视为其方向上的基准线，那么它与其他轮廓边缘间的相对角 以及最大最小垂直距离(dmin和dmax)可以被计算出来。边缘之间的角度定义了直方图的行，然后在其中增加对应的计算出来的最大和最小距离的所有直方块，就得到了当前多边形的PGH。
它具有如下特点：
(1) 计算简单，可满足实时性要求；
(2) 具有平移、尺度不变性；
(3) 具有360度旋转不变性。
3. 简单形状描述符的结合(Combination of Simple Shape Descriptors)
如图，它们是几种简单的形状描述符，分别代表了凹凸性、主轴、致密性、差异性和椭圆差异性。
凹凸性：轮廓凸包周长与原轮廓周长的比率。（所有凸起的覆盖轮廓称为凸包）
主轴：过物体质心的正交轴，主轴之间的比例可以由物体轮廓的协方差矩阵计算出来
致密性：物体区域面积与等面积的正方形周长的比例，也可以是圆。
差异性：表现为与模板比较的比例均方误差。
单独用这几种简单描述符的任何一种来表示形状进行匹配，都不能达到较好的匹配结果。但是如果我们将这五种简单形状描述符进行结合，同时用它们来描述一个形状，那么这个形状的描述信息就非常丰富了，匹配的结果也会很好。
这种形状描述方式具有如下的特点：
(1) 单独的任何一种简单描述符都不能用于精确识别物体，但是多种简单描述符的结合可以达到很高的识别效率；
(2) 计算简单，可以达到实时性；
(3) 具有平移、尺度不变性；
(4) 理论上360度旋转不变性。
4. 基于hausdorff距离的形状匹配
Hausdorff距离用来计算两个点集之间的匹配程度。给定两个有限集A={a1,a2,…,ap}和B={b1,b2,…,bq},A，B之间的Hausdorff距离定义如下：
其中：
Hausdorff距离H(A,B)取h(A,B)和h(B,A)的最大值，这样通过计算h(A,B)和h(B,A)就可以获得两个点集A，B之间的匹配程度。
为了减少计算量，可以取角点进行匹配。但这样匹配率将降低。基于hausdorff距离的形状匹配的特点;
(1) 对每个边缘点进行hausdorff距离计算，计算量稍大，但对不是过于复杂的轮廓（如小尺寸轮廓），可以满足实时性；
(2) 具有平移、尺度不变性；
(3) 具有旋转不变性；
二、基于区域特征的形状匹配
基于不变矩的形状匹配是典型的基于区域的匹配方法。其中，基于Hu不变矩的形状匹配应用最为广泛。
图像的矩函数在模式识别、目标分类中得到了广泛的应用。在1961年首先基于代数不变量引入矩不变量。通过对几何矩的非线性组合，导出了一组对于图像平移、尺度、旋转变化不变的矩，这种矩就成为Hu矩。
一幅大小为M×N的二维图像其中(p+q)阶矩：
对于二值图像，其零阶矩就是该形状区域的面积。因此，将面积归一化，每一个图像矩除以零阶矩得到的商具有形状的尺度变化无关性。
求图像的p+q阶中心矩，面积归一化，使得具有平移、尺度不变性。
(1)
(2)
计算图像的7个面积归一化的中心矩，{m11,m02,m20,m21,m12,m03,m30}Hu不变矩是关于这7个矩的函数。具有平移、旋转和尺度不变性。
彩色图像Hu不变矩的计算流程如下：
基于Hu矩的形状匹配所具有的特点：
(1) Hu不变矩只能用于对区域的检测，不能用于边界的检测，但由于计算简单，计算量不大，可以满足实时性；
(2) 具有平移、尺度不变性；
(3) 具有旋转不变性。
三、匹配方法间的比较
CCH（链码直方图）：是一种基于轮廓匹配方法。具有较强的平移不变性，尺度不变性一般，具有90度的旋转不变性。由于编码简单，执行速度快。计算量和所需内存都较小，适合差别明显的物体，对平滑和非平滑物体的识别并不明显；
PGH（成对几何直方图）：是一种基于轮廓匹配方法。具有较强的平移不变性和尺度不变性，具有360度的旋转不变性。执行速度快，可以较好地识别多边形物体和部分自封闭的物体，由于它的计算过程，对非多边形物体的识别可能会浪费计算量；
CFSS（五种简单形状描述符结合）：是一种基于轮廓匹配方法。具有较强的平移不变性和尺度不变性，具有360度的旋转不变性。执行速度处于CCH方法和PGH方法之间。识别率与PGH相当，但是比它需要更少的计算时间和内存。
HAUSDORFF距离：是一种基于轮廓匹配方法。具有较强的平移不变性，但是尺度不变性和旋转不变性都较差。由于处理的数据维数较多，执行效率是这五种方法中最慢的一个。可用于匹配部分重和形状物体。
Hu不变矩：是一种基于区域的形状匹配方法。具有较强的平移、尺度和旋转不变性，其中旋转不变性为360度。但由于匹配的数据量大，执行速度较慢。适合于进行一些更精确的匹配。
