摘 要

随着计算机技术的发展，数字图像处理技术在当今各个学科中的应用越来越广泛，距离变换作为数字图像处理中对二值图像处理的一种方法，现在已经被普遍应用于各种学科领域。如今，人类已经成功利用距离变换这一方法实现提取骨架，粘连物体的分离，机器人碰撞检测，模式匹配，求图像像素点之间的距离等。

距离变换可以原本的二值图像转换成一副灰度图像，原先图像像素的值为0或1，距离变换之后变为多级的灰度值，每个值等于该点到背景集的距离，这样使得分析图像更加方便。距离变换算法中描述距离的方法有如下两种：欧氏距离和非欧氏距离。

距离变换中蕴含了丰富的距离信息，这对求取图形或者物体的骨架特别有帮助，因此距离变换常常被用来求解图形的骨架。骨架具有这样一个性质，它一般都会位于图形的几何中心。距离变换恰好能够比较直观地将这种性质反映出来。距离变换不单单能够用来求取骨架，还能对求出的骨架结果进行优化，使其性质更加优良适用。

本文是在学习了近些年来一些学者对二值图像距离变换的研究成果的基础上，实现了Distance transformation 算法，在此基础上又学习了4SED算法,并实现了其MATLAB的程序。

关键字：数字图像处理 距离变换 4SED算法 MATLAB

Abstract

With the development of computer technology, the digital image processing technology is more and more widely used in various disciplines.Distance transform as one of the methods of the digital image processing on the two value's image , has now been widely used in various fields. Nowadays, People use it to extract the skeleton, separation of adhesion objects, collision detection ,pattern matching,get the distant between the two pixels of a picture.

Distance transform can translate the original binary image into the corresponding gray image,the original pixel value is 0 or 1 ,then they changed into multilevel gray values,each pixel are re-assignment and they corresponds to the distance to the nearest non feature points of value.This makes the analysis of image more convenient. Existing distance transform algorithm mainly has two classes of measures:Euclidean and non-Euclidean distance .

Distance transform,which contains the distance information to calculate the graphics object skeleton is especially useful. Therefore,it is widely used in skeleton algorithm researching. Skeleton of an important property is locating in the geometric center of the graphics,and distance transform can intuitively reflect the nature.Distance transform not only help search the skeleton but also optimization for the skeleton results,make its nature more excellent application.

In this article,I first study some achievements of some scholars in recent years.Then,I achieve the Distance transformation algorithm, on the basis of the study I learn 4SED algorithm, and realize the MATLAB program of that.

Key words: Digital image processing Distance transform 4SED algorithm MATLAB

目 录

摘要 I

Abstract II

1 绪论 1

1.1 研究背景 1

1.2 距离变换研究现状 2

1.3 本文要研究的内容 3

2 数字图像处理中的相关概念 4

2.1 二值图像 4

2.2 图像的量化 4

2.3 像素间的基本关系 4

2.3.1相邻像素 4

2.3.2邻接性和连通性 4

2.4 曲线和边界 5

2.5 距离 6

2.5.1 欧氏距离(Eculidean Distance) 6

2.5.2 城市街区距离(City Block Distance) 7

2.5.3 棋盘距离(Chessboard Distant) 7

2.5.4 八边形距离 7

2.5.5点到点集的距离 7

2.6 骨架 8

2.6.1 骨架的定义 8

2.6.2 骨架的解释模型 9

2.6.3 骨架的特性 10

2.7 本章小结 10

3 距离变换 11

3.1 距离变换的概念 11

3.2 距离变换与骨架的关系 12

3.3 距离变换算法回顾 14

3.3.1 近似模板方法 14

3.3.2 精确欧氏距离算法 14

3.4计算原理 15

3.5计算方法 16

3.5.1 Chamfer距离 16

3.5.2 向量法 17

3.5.3 有序传播(Ordered Propagation)算法 18

3.5.4 全局算法 18

3.6本章小结 19

4 距离变换算法的研究与实现 20

4.1 MATLAB基本函数介绍 20

4.1.1 二值图像的建立 20

4.1.2彩色图像的读取及其二值图像的转换 21

4.2 Distance transformation 算法 21

4.2.1 算法原理 21

4.2.2 算法实现 21

4.2.3 实验结果 22

4.2.4 实验结论 24

4.3 4SED算法的实现 24

4.3.1 4SED算法的原理 24

4.3.2 算法实现 28

4.3.3 试验结果 29

4.3.4 实验结论 29

4.4 本章小结 30

5 总结与展望 31

参考文献 32

附录A 34

致 谢 38

1 绪论

1.1 研究背景

21世纪是一个信息爆炸的时代，图像作为一种重要的手段，被人类利用以便获取，表达和传递信息。因此数字图像处理技术在各种学科如地理学科，计算机学科，生物科学，信息科学，数学中都被广泛研究应用。数字图像处理又可以叫做计算机图像处理，它能够将图像信号转化为数字信号然后再利用计算机来进行处理，这样做可以提高图像的可处理性，达到人们所要求的预期结果。它是计算机技术，信息论和信号处理等学科相结合的综合性研究。

数字图像处理的主要研究内容有图像增强，图像编码，图像复原，图像分割，图像分类等。图像（位图）一般可分为二值图像，索引图像，灰度图像和RGB图像。