一、问题重述图形（或图像）在计算机里主要有两种存储和表示方法。

矢量图是使用点、直线或多边形等基于数学方程的几何对象来描述图形，位图则使用像素来描述图像。

一般来说，照片等相对杂乱的图像使用位图格式较为合适，矢量图则多用于工程制图、标志、字体等场合。

矢量图可以任意放缩，图形不会有任何改变。

而位图一旦放大后会产生较为明显的模糊，线条也会出现锯齿边缘等现象。

矢量图从本质上只是使用曲线方程对图形进行的精确描述，在以像素为基本显示单元的显示器或打印机上是无法直接表现的。

将矢量图转换成以像素点阵来表示的信息，再加以显示或打印，这个过程称之为栅格化（Rasterization），见图1。

栅格化的逆过程相对比较困难。

假设有一个形状较为简单的图标，保存成一定分辨率的位图文件。

我们希望将其矢量化，请你建立合理的数学模型，尽量准确地提取出图案的边界线条，并将其用方程表示出来。

二、问题分析本题的要求是完成位图的矢量化，通过建立合理的数学模型，将一个有一定分辨率的位图文件尽量准确地提取出图案的边界线条，最终将位图用方程的形式表示出来。

解决本问题的流程图见下图。

首先，通过MATLAB读取位图的各个像素的像素值（0-1），得到位图各个点的灰度值，通过最大类间方差法和最大熵法确定阈值，完成灰度的二值化，使各个像素点的灰度值全部由0或1表示。

其次，将位图的轮廓通过合适的算法提取出来，根据特征值对轮廓进行拟合。

最后，根据拟合的函数完成位图的矢量图，完成其矢量化过程，并通过对比矢量图和原始位图对应的。

三、问题假设及符号说明3.1问题假设3.2符号说明四、模型建立4.1模型准备本题要求将一个形状较为简单的图标，保存成一定分辨率的位图文件，即将位图矢量化。

阈值：指释放一个行为反应所需要的最小刺激强度，本文指像素点灰度值二值化的临界值。

4.2阈值的确定方法 4.2.1最大类间方差法最大类间方差法的基本思想是将待分割图像看作是由两类组成的整体，一类是背景，一类是目标[6]。

用各个像素点像素值的方差来衡量目标和背景之间额差别。

方差越大，即两像素值的区别越明显，不能分在同一类别中。

本问中，为使得目标和背景两类的类间方差最大的灰度级别即认为是最佳阈值。

一副大小为N M ⨯个像素、灰度级别为L 的图像，若设图像中灰度级为i 的像素个数为i N ，则灰度级i 的概率为MN N P ii ⨯=根据最大类间方差法的分割思想，最佳阈值公式为()()[]202010*max arg w w P w w P T b b a a L t -+-=-≤≤其中，∑==Ti i a P P 1∑+==LT i ib P P 1∑==Ti a ia P P iw 1 ∑+==LT i bib P P iw 1∑==Li i iP w 1一维最大类间方差法是建立在一维灰度值分布图基础上的确定阈值的方法，而一维灰度值分布图没有考虑图像的空间信息，仅仅表示出了各个像素点独立的灰度分布，但是图像中的每个像素与其相邻的像素是有相关性的，所以在以为灰度值分布图基础之上的阈值分割方法所建立的分割模型考虑的因素不全面。

因此，在对图像进行分割时，容易受到噪声的干扰，得到的分割结果和阈值结果不精确，将影响后续位图矢量化的准确度。

为了增强算法的抗噪性能、提高其确定阈值结果的精确度，本文将最大类间方差法从一维算法推广至二维算法。

二维最大类间方差法是建立在二维灰度值分布图的基础上计算阈值的算法，下面对其进行介绍。

设一幅大小为N M ⨯个像素的图像灰度级为L ，()y x f ,为图像在()y x ,的灰度值，()y x g ,是以()y x ,为中心，k k ⨯邻域内的平均灰度值，其表达式为()()∑∑=-==-=++=22222,1,k m k m k n k n n y m x f k y x g式中，k 为邻域的大小；()y x g ,为邻域内的平均灰度值；()n y m x f ++,为图像在点()n y m x ++,的灰度值； M 为图像的宽度； N 为图像的高度。

()y x f ,和()y x g ,即形成了一个二元组()()()y x g y x f ,,,，令ij N 为图像中()i y x f =,且()j y x g =,的像素的个数()1,0-≤≤L j i ，则其联合概率密度为NM N P ij ij ⨯=式中，ij P 为图像中()i y x f =,且()j y x g =,的像素联合概率密度； ij N 为图像中()i y x f =,且()j y x g =,的像素的个数。

由最大类间方差法求出的阈值向量()t s ,会将直方图分为四个部分，分别为目标部分、背景部分、边界部分、噪声部分。

在大多数情况下，近似的认为边界部分和噪声部分的概率为0，因此这种近似在多数情况下是合理的。

图像目标出现的概率为∑∑===s i tj ij P P 11图像背景出现的概率为∑∑+=+==L s i Lt j ijPP 111式中，ij P 为图像中()i y x f =,且()j y x g =,的像素联合概率密度； L 为图像灰度级。

图像总均值矢量为()'⎪⎪⎭⎫⎝⎛='=∑∑∑∑====L i L j L i L j ij ij T T T jP iP 111110,,μμμ图像目标和背景额均值矢量为()'⎪⎪⎭⎫⎝⎛='=∑∑∑∑====s i t j s i t j ij ij jP iP 111101000,,μμμ()'⎪⎪⎭⎫⎝⎛='=∑∑∑∑+=+=+=+=L s i L t j L s i L t j ij ij jP iP 111111101,,μμμ因为假设边界区域和噪声区域的概率为0，因此有110≈+p p1100μμμp p T +=式中， 0μ和1μ分别为目标区域和背景区域的均值矢量。

类间方差定义为()()()()⎥⎦⎤⎢⎣⎡'--+⎥⎦⎤⎢⎣⎡'--=T T r r B p p S μμμμμμμμ111000取类间方差的迹作为测度，有()()()002112001p p p p trS T j T i B --+-=μμμμ式中，∑∑===s i tj ij i iP 11μ∑∑+=+==Ls i Lt j ijj jP 11μ式中，ij P 为图像中()i y x f =,且()j y x g =,的像素联合概率密度；L 为图像灰度级。

最佳阈值公式为()()t s trS t s BLt L s ,max arg ,11**≤≤≤≤=式中，B trS 为测度。

遍历图像的灰度级，求使目标和背景的类间方差的迹最大的灰度级，即得最佳分割阈值()**,t s 。

4.2.2最大熵法由熵的定义可知，当一个信息源中所有的事件以相同的概率出现时，这时候信息熵大，因为信息源的不确定性大，所以信息熵大。

用最大熵法求最佳阈值，就是求一个分割阈值使得目标和背景两类的信息熵之和最大，一幅大小为N M ⨯个像素、灰度级为L 的图像，设图像中灰度级为i 的像素个数为i N ，则灰度级i 的概率为MN N P ii ⨯=图像目标区域的熵和图像背景区域的熵可以表示为∑=-=Ti ti t i f P P P P H 1log ∑+=---=LT i t i ti b P PP P H 11log 1 式中，f H 为图像目标区域的熵； b H 为图像北京区域的熵； ∑==Ti i t P P 1最大熵法的最佳阈值公式为()()[]T H T H T b f +=max arg *遍历图像的灰度级，求目标区域的熵和背景区域的熵的和最大的灰度级，即得最佳分割阈值*T 。

4.2.4 确定阈值方法总结将以上提出的累积剩余熵阈值分割算法用于实际图像分割，将分割结果与经典的最大类间方差法和最大熵法进行了比较。

实验中用了人、直升机、车、帆船、船和发电站图。

表1是对分割结果的主观评价，表2是三种阈值分割方法的最佳分割阈值的比较。

表1 分割结果主观评价表图像 最大类间方差法最大熵法 最大累积剩余熵法人 差 好 好 直升机 差 好 好 车 差 好 好 帆船 一般 一般 一般 船 差 一般 好 发电站差一般好表2 最佳分割阈值比较表图像 最大类间方差法最大熵法 最大累积剩余熵法人 129 165 153 直升机 82 94 94 车 65 85 77 帆船 134 156 137 船99126144发电站 100 177 165由上表分析可知，图像的不同对应的最佳分割阈值的确定方法不同，如：当图像为人、直升机或者汽车时，最大熵和最大累积剩余熵确定阈值的方法比最大类间方差法结果更精确。

4.3二值化根据像素点的灰度值()y x f ,和阈值T ，可将图像二值化。

()()()⎩⎨⎧<≥=Ty x f T y x f y x f ,0,1,式中，()y x f ,为像素的灰度值，T 为最佳分割阈值。

4.4基于细化算法的轮廓提取 4.4.1基础术语为简便的描述图像中像素之间的相互关系，本文引用了邻域和连通的概念[8]。

●4邻域和4相邻对于图像中的某个像素点()n m p ,，则与之在水平方向（左和右）和垂直方向（上和下）相邻的4个像素点坐标分别为()n m ,1-，()n m ,1+，()1,-n m ，()1,+n m ，则这4个像素点组成了像素点()n m p ,的4邻域，表示为()p N 4。

而这4个像素点在位置上就与像素点()n m p ,相邻。

● ●○● ●图 4邻示意图 图 4邻坐标关系图●8邻域和8相邻若取像素()n m p ,四周的8个像素点作为相邻点，则像素点()n m p ,的这8个相邻点就构成了8邻域，用()p N 8表示。

● ● ● ● ○ ● ●●●图 8邻示意图 图 8邻坐标关系图●像素间的邻接像素的相邻仅说明了两个像素在位置上的关系，若再加上取值相同或相近，则称两个像素邻接。

①两个像素点p 和q 邻接的条件像素点()n m p ,和()t s q ,位置上满足相邻，即 4相邻：()()q N n m 4,∈或者()()p N t s 4,∈ 8相邻：()()q N n m 8,∈或者()()p N t s 8,∈且像素点()n m p ,和()t s q ,灰度值相近，即称为灰度值相近（似）准则，即V p ∈ 和V q ∈，其中{},...,21v v V =②邻接的类别4邻接： V q p ∈,且()()p N t s 4,∈，则称像素点()n m p ,和()t s q ,4邻接，记为q p −→−4；8邻接： V q p ∈,且()()p N t s 8,∈，则称像素点()n m p ,和()t s q ,8邻接，记为q p −→−8。