基于Freeman链码的二维曲线匹配.docx

基于Freeman链码的二维曲线匹配
概述
二维曲线匹配（2Dcurvematching）是计算机视觉和模式识别领域的一个基础问题。该问题的基本思路是给定两个曲线，找到它们之间的匹配关系。本文主要介绍基于Freeman链码的二维曲线匹配。首先，介绍Freeman链码的原理和特点。然后，详细描述基于该链码的曲线匹配算法。最后，通过实验对该算法的性能进行评估。
Freeman链码
Freeman链码是一种用来描述2D图像的轮廓信息的有向运动链表。该链码由美国科学家Freeman于1974年提出，主要用于轮廓提取和边缘检测。其原理是将曲线上的每一个像素点都按照既定规则编号，然后把这些数字按照一定的规则进行编码。
具体地说，Freeman链码将像素点分为八个方向，用数字0~7表示每个方向。对于任意一点P(x,y)，定义其相邻的8个点位于偏移量(Ox,Oy)的位置，其中Ox，Oy是只能取{-1,0,1}中的任意整数。因此8个方向的编号如下：
0，右；1，右上；2，上；3，左上；4，左；5，左下；6，下；7，右下。
对于一个给定的像素点P(x,y)，将该点沿着其对应的方向进行移动，一直到达下一个非背景像素点，那么这个点的位置与-当前点位置可以表达为一个由链码组成的序列。例如，上图中的序列就是一个由Freeman链码得到的轮廓表示。
基于Freeman链码的曲线匹配算法
基本思路
基于Freeman链码的曲线匹配算法主要分为两个步骤。首先，提取出两个曲线的链码表示。其次，通过比较链码得到两个曲线之间的距离，从而得到它们的匹配关系。
链码提取
对于一张二维图像，可以将图像中的轮廓提取出来，得到一个由像素点组成的曲线表示。然后，可以使用Freeman链码将这个曲线表示为一个由链码组成的序列。
对于一个由链码组成的序列，例如P4,P5,P6,P7,P0,P1,P2,P3，在序列开头加上一个P0的起点坐标，再加上一个结束标志，得到如下序列：(P0,0),(P4,4),(P5,6),(P6,6),(P7,0),(P0,2),(P1,2),(P2,2),(P3,4),(P4,0)。
链码比较
对于两个曲线的链码序列，其中一个是参考序列，另一个是待比较序列。这两个序列的长度可能不一样。如果待比较序列的长度小于参考序列，那么可以在结尾部分添加结束标志，并将剩余部分以参考序列的最后一个码字填充。考虑到两个序列可能存在旋转和平移变换的情况，需要对待比较序列在不同的起点和旋转角度下进行匹配，并找到最小距离。
曲线距离的定义是曲线上相邻两个点的链码之差绝对值的平均值。在比较两个曲线的时候，可以先将待比较曲线进行旋转和平移，再计算两个曲线的距离。旋转和平移的过程可以通过移动待比较曲线的起点和旋转待比较曲线实现。
实验结果
使用Matlab和C++实现了基于Freeman链码的曲线匹配算法，并在使用多种测试曲线上进行了实验。实验结果表明，该算法能够准确地找到两个曲线之间的匹配关系。由于该算法简单、快速，可以应用于大规模的曲线匹配问题。
结论
本文介绍了一种基于Freeman链码的二维曲线匹配算法。该算法通过将曲线表示为由链码组成的序列，再通过比较链码找到曲线之间的距离，实现曲线匹配的过程。实验结果表明，该算法能够准确地找到两个曲线之间的匹配关系，而且具有较高的效率。