河北大学数学与计算机学院课程名称：数据仓库与数据挖掘成绩：综合实验题目基于正交最小二乘拟合算法的图像矢量化课程号：课序号：02任课教师：邢红杰班级：2011软工姓名：连冰川学号：填写日期：5月18日河北大学数学与计算机学院基于正交最小二乘拟合算法的图像矢量化2011软件工程连冰川1.实验问题形图形（或图像）在计算机里主要有两种存储和表示方法。

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

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

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

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

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

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

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

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

问题分析与建模（或所使用方法的算法描述及算法流程）2.1问题分析题目要求我们针对形状较为简单的位图，通过建立合理的数学模型，将其矢量化，并准确地提取出图案边界线条，找出线条的曲线方程。

初步分析可知：由于位图放大后较为模糊，其线条将会出现明显地锯齿边缘，为了转换为精确、可以任意放缩的矢量图，我们需要通过对二值化图像进行矢量化和有效地拟合。

基于以上分析，为了得到有效地二值化图像，我们需要采取多种方法对图像进行分割，在多种分割的图像结果的比较中，选出作为完美的分割结果。

然而，图像有效地分割需要我们首先对扫描后的灰度图像进行处理，即进行多尺度边缘检测。

在采取多种边缘检测算子的基础上，我们通过对灰度图像的膨胀与腐蚀的处理，得到较为完美的多尺度边缘检测结果，作为图像分割的基础。

从而实现从位图到矢量图的完美转化。

2.2问题假设（1）假设原位图是二维的、简单的图像；（2）假设原图像是单色图；（3）假设所采用的边缘检测方法抽取到最佳线类型特征；（4）假设细化后的图像不会造成原先连续图形的断裂，从而不破坏图形的连通性；（5）假设细化后保持了原图形的基本特征，不会破坏图形间的拓扑关系；（6）假设运用的细化算法具有稳定性和收敛性；（7）假设经过预处理的二值图是确切的矢量图；（8）假设基于模糊识别的非线性系统的参数收敛性最佳；（9）假设基于正交最小二乘的非线性系统模糊识别得到的矢量化方程误差最第1页小。

2.3模型建立与求解（一）基于图像腐蚀、膨胀的多尺度边缘检测我们在扫描位图得到的灰度图像的基础上，通过采取图像腐蚀、膨胀的方法对灰度图像进行多尺度边缘检测的初步处理。

1.边缘检测算子的选取针对本文选取简单的位图进行图像分割、目标区域识别、区域形状提取等处理，从而实现边缘检测算子的提取，将选取的算子作为图像腐蚀、膨胀的基础。

在进行边缘检测时，求出梯度(x,y)f 梯度的局部最大值和方向:cos sin x y f f x f y f f r x r y r θθ∂∂∂∂∂=⋅+⋅=+∂∂∂∂∂ 由导数的算术意义可知当0f r θ∂⎛⎫∂ ⎪∂⎝⎭=∂时，f r∂∂达到最大值，扫描得到的灰度图像的方程设为si n cos 0x g y g f f θθ+=，根据导数中最大值的求法可知a r c t a n x g y f f θθ⎛⎫= ⎪ ⎪⎝⎭或者表示为g θπ+。

由此，得到梯度模max f g r ∂⎛⎫== ⎪∂⎝⎭梯度模算子具有位移不变性和各方向的良好性质，对于灰度变化的方向，即边界的方向，我们可以通过arctan x g y f f θ⎛⎫= ⎪ ⎪⎝⎭得到。

（1）边缘算子图像处理为了加强图像处理的效果，我们通过六种边缘算子处理的比较，选出最优的表现结果。

1）Roberts 边缘算子()(){}1222,G f x y =+(1)在本式中我们采取平方根运算使该处理更为精准，运用此算法实际上是求旋转45两个方向上微分值的和。

通过Roberts 边缘算子得到的结果如下图所示：河 北 大 学 数 学 与 计 算 机 学 院第3页图CRoberts （罗伯特）边缘算子定位精度高，在水平和垂直方向效果好，但对噪声敏感。

2）Sobel 边缘算子'(x,y)(x 1,y 1)2(x,y 1)(x 1,y 1)(x 1,y 1)2(x,y 1)(x 1,y 1)x f f f f f f f =-++++++------+-'(x,y)(x 1,y 1)2(x 1,y)(x 1,y 1)(x 1,y 1)2(x 1,y)(x 1,y 1)y f f f f f f f =--+-+-+-+--+-++ ()()'',(x,y)(x,y)x y G f x y f f =+ (2)在求出梯度后，我们设定T 为一个常数，当()(),G f x y T >时，标出该点为边界点，将其像素值设定为0，其他的设定为255，适当调整常数T 的大小来达到最佳效果。

通过Sobel 边缘算子得到的结果如下图所示：图 DSobel 算子通常对灰度渐变和噪声较多的图像处理得较好。

3）Prwitte 边缘算子'(x,y)(x 1,y 1)(x 1,y 1)(x 1,y)(x 1,y)(x 1,y 1)(x 1,y 1)x f f f f f f f =+----++---++--+'(x,y)(x 1,y 1)(x 1,y 1)(x,y 1)(x,y 1)(x 1,y 1)(x 1,y 1)y f f f f f f f =-++--++---++-+- ()(),G f x y =(3) 求出梯度后，可设定一个常数T ，当(x,y)f T >时，标出该点为边界点，其像素值设定为0，其他的设定为255，适当调整常数T 的大小来达到最佳效果。

通过Prwitte 边缘算子得到的结果如下图所示：图 EPrewitt 算子不仅能检测边缘点，而且能抑制噪声的影响，因此，对灰度和噪声较多的图像处理得较好。

4)LoG 边缘算子Laplacian 算子22222f f f x y ∂∂∇=+∂∂。

将上式以差分方式表示，得到： ()()()()()()2(x,y)1,j 1,j i,j 1i,j 14,j f f i f i f f f i ∇=++-+++--(4)然后我们通过模板形式表示常用的算子：2010141010⎛⎫ ⎪∇=- ⎪ ⎪⎝⎭2f ∇算子能突出反映图像中的角线和孤立点，从图像结果中我们可以看出其在边缘和孤立点的幅值都比较大。

但是，因为一阶导数对噪声敏感，因而呈现不稳定性，这样我们选取二阶导数对噪声的反映将会更加敏感，更为不稳定。

所以，在作Laplacian 变换之前需要作平滑。

同时，又因为卷积是可变换、可结合的，所以先作高斯卷积，再用Laplacian 算子作滤波器LoG （Laplacian of Gaussian ）滤波器，即为()()()2(x,y),*,f G x y M x y =∇式中，(),M x y 是图像。

()22221,exp 22x y G x y πσσ⎛⎫+=- ⎪⎝⎭ (5) ()()()222222222222242211,,exp 2exp 2222x y x y x y LoG x y G x y x y πσσπσσσ⎛⎫⎛⎫⎛⎫⎛⎫∂∂+-++=∇=+-=-- ⎪ ⎪ ⎪ ⎪∂∂⎝⎭⎝⎭⎝⎭⎝⎭(6)通过LoG 边缘算子得到的结果如下图所示：河 北 大 学 数 学 与 计 算 机 学 院第5页图 F（5)零交叉方法首先我们运用指定的滤波器对图像进行滤波，然后寻找零交叉点作为边缘。

通过零交叉方法得到的结果如下图所示：图 G6)Canny 边缘算子在边缘算子检测中，我们还可以采用Canny 边缘检测算子进行边缘检测。

首先，取二维高斯函数：()22221,exp 22x y G x y πσσ⎛⎫+=- ⎪⎝⎭ 然后，求高斯函数 在某一方向n 上的一阶方向导数为(),n G x y G n ∂=∂，cos sin n θθ⎛⎫= ⎪⎝⎭，(),G x G x y G y ∂⎛⎫ ⎪∂ ⎪∇=∂ ⎪ ⎪∂⎝⎭由于本文中选取的对象是二维简单位图，而且Canny 算子是建立在二维()(),,G x y f x y ∇⨯基础上，其边缘强度由()(),,G x y f x y ∇⨯和 ()()()(),,,,G x y f x y n G x y f x y ∇⨯=∇⨯方向来决定。

为了提高Canny 算子的运算速度，将(),G x y ∇的二维卷积模板分解为两个一维滤波器，则有()()()221222,exp exp 22G x y x y kx h x h y x σσ∂⎛⎫⎛⎫--=⋅= ⎪ ⎪∂⎝⎭⎝⎭()()()221222,exp exp 22G x y y x ky h y h x y σσ∂⎛⎫⎛⎫--=⋅= ⎪ ⎪∂⎝⎭⎝⎭式中，k 为常数，其中 ()212exp 2x h x σ⎛⎫-=⋅ ⎪⎝⎭，()222exp 2y h y σ⎛⎫-=⋅ ⎪⎝⎭()212exp 2x h y σ⎛⎫-=⋅ ⎪⎝⎭，()222exp 2y h x σ⎛⎫-=⋅ ⎪⎝⎭得到：()()12h x xh x = ()()12h y yh y =然后将这两个模板分别与图像 进行卷积，得到 (),(x,y)x G x y E f x ∂=⋅∂(),(x,y)y G x y E f x ∂=⋅∂ ()A ,i j =()()(),,arctan ,y x E x y i j E x y αθ⎛⎫= ⎪ ⎪⎝⎭式中，()A ,i j 反映了图像上(),i j 点处的边缘强度；(),i j α为垂边缘的方向。

通过零交叉方法得到的结果如下图所示：图H（2）在这里我们实验了上述几种边缘算子，得出的图像如下图所示：河 北 大 学 数 学 与 计 算 机 学 院第7页通过对以上六图进行比较，发现利用Prewitt 边缘算子的得到图像最好，它不仅能检测边缘点，而且能抑制噪声的影响。

2.对图像进行先腐蚀后膨胀的开运算（1）腐蚀与膨胀1)腐蚀腐蚀：集合A 被结构元素B 腐蚀，表示为{}X :X A B B A Θ=+⊂ 上式表明腐蚀运算由将B 平移x ，但仍然包含在A 内的所有点x 组成。

2)膨胀是腐蚀运算的对偶运算,可以通过对补集的腐蚀来定义。