国内图书分类号：TP391.41
国际图书分类号：681.39
工学博士学位论文
基于遗传优化的非参数曲线识别算法研究
博 士 研究生：魏 玮
导 师：王 祁教授
申 请 学 位：工学博士
学 科、专 业：仪器科学与技术
所 在 单 位：自动化测试与控制系
答 辩 日 期：2005 年 12 月
授予学位单位：哈尔滨工业大学
Classified Index: TP391.41
U.D.C: 681.39
Dissertation for the Doctoral Degree in Engineering
NONPARAMETRIC CURVE RECOGNITION
ALGORITHM RESEARCH BASED ON
GENETIC OPTIMIZATION
Candidate:
Supervisor:
Academic Degree Applied for:
Speciality:
Affiliation：
Date of Defence:
Degree-Conferring-Institution:
Wei Wei
Prof. Wang Qi
Doctor of Engineering
Instrument Science and Technology
Department of Automatic Measurement
and Control
December, 2005
Harbin Institute of Technology
摘 要
- -
I
摘 要
曲线识别是一种图像识别领域非常重要的基本识别技术。现行图像识别
算法总是先通过图像预处理消除噪声，再进行图像分割，然后提取曲线特
征，最后进行识别。由于图像的复杂性和多样性，以及分割算法的局限性，
分割后的二值图像总是存在大量的噪声，曲线往往也存在断点。人类视觉有
连接断点、滤除噪声的功能，所以能在存在大量噪声的二值图像中，识别出
存在断点的任意形状的曲线。Hough 变换也具有从存在大量噪声的二值图像
中，识别出具有断点的曲线的能力。其特点是必须事先预知被测曲线的曲线
方程或曲线的形状，由此构造相对应的参数空间，并将其参数空间离散化后
应用点线投影，通过表决判定出最有可能的曲线。Hough 变换的优点是能够
在存在大量的噪声的二值图像中，提取存在断点的已预知曲线方程或形状的
曲线，本文称为参数曲线。而对在曲线识别前，没有曲线方程或形状先验知
识的曲线，Hough 变换无法识别，这类曲线称为非参数曲线。
实际图像中的曲线在许多情况下均是非参数曲线。如在识别路面图像中
的裂纹、遥感图像中的河流等自然纹理的过程中，均无法预知其曲线方程或
曲线形状，其二值化后也存在大量的噪声和曲线上的断点，当然也无法用
Hough 变换来提取。本文将二值图像中非参数曲线的识别问题，归结成二值
图像中非零像素的组合优化问题，并采用遗传算法选出最优，识别出非参数
曲线。本文的主要研究内容和取得的成果包括如下几个方面：
1. 系统而较全面地介绍了用 Hough 变换识别参数曲线的理论方法，研
究了图像中参数曲线和非参数曲线的概念。阐明了基于组合优化理论的非参
数曲线识别的基本框架，并根据其优化是离散性优化的特点，采用遗传优化
来识别非参数曲线，并取得成功。
2. 为有效地设计遗传优化的适应值函数，本文引入了非参数曲线识别视
觉模型。在该模型中，对非参数曲线上非零像素的线密度、最大相邻非零像
素的间隔、非闭合曲线的跨度、闭合曲线的面积等与曲线分辨率相关的特征
作出相应的规范，在此基础上定义了 5 种适应于不同情况的适应值函数，并
进行了系统的对比实验。
3. 为适应非参数曲线特征的提取，在遗传优化的设计中提出了如下技
术：为使字符集满足 Goldberg 的最小字符集原理，采用了基于行-列的编
码，并从理论上证明了当像素的维数增加时，改进的基于排列编码的字符串
哈尔滨工业大学博士学位论文
- II -
集相对于行-列编码的字符串集按指数增加；为加速形成适应值高的建筑模
块，提出了位串段适应值积累型遗传算法交叉点和变异位的概率确定技术；
为解决基于遗传优化的非参数曲线提取中收敛到局部最优的问题，引入了小
生境技术，独立提出了适用于该问题的共享函数、相似性判别式、罚函数
等；针对不同的编码、适应值函数、曲线的形状进行了大量的实验，结果表
明算法是有效的。
4. 为了在基于行-列编码遗传优化提取的特征中识别非参数曲线，本研
究设计了基于二分法的决策折线，通过先验样本的训练可以有效地获得该决
策折线。该方法能从含有噪声的图像中识别非参数曲线，同时又避免了训练
决策超曲面的复杂运算。实验表明对路面裂纹的识别率可达 93.0%。
5. 为进一步提高基于行-列编码遗传优化的非参数曲线的识别效率，本
文引入了多种群竞争小生境遗传算法。该算法能以更高的效率识别路面的
横、纵裂纹，识别时间将只是基于行-列编码遗传算法所用时间的 30%～
50%。本文还探讨了应用多模态优化遗传算法分别识别非闭合非参数多曲线
和闭合非参数曲线问题，也取得良好效果。实验表明这两种算法均有效。
6. 在路面图像的分割方面，提出了灰度奇阶矩动态阈值分割法，并从理
论和实验两方面论证了该方法的有效性。本研究还提出了均值动态阈值及
agent 搜索滤波分割法，取得良好的效果。
关键词：非参数曲线识别；视觉模型；小生境遗传算法；多种群竞争；行-
列编码
Abstract
- -
III
Abstract
Curve recognition is an important basic recognition technique in the image recognition field.
The image recognition algorithm used in the recent decades is usually composed of the
following 4 steps: image preprocessing to eliminate noise, image segmentation, curve feature
extraction, and recognition. There are always large noise pixels in the binary images segmented
from original images and break points on the curve for the complexity and variety in the images
and the limitation of the segmentation algorithm. Human vision can identify curves in any shapes
with break points on them in binary images with large noise, because it has the ability to link the
broken curve and eliminate the noise pixels. Hough Transform (HT) also has the ability. HT first
has to own the knowledge of the curve function or shape, then create the parameter space and
discretize it for point-to-line mapping, determine the most possible curve by voting at last. HT
has the advantage to extract the parametric curve with break points on it, which its function or
shape is a priori knowledge, from the binary image with large noise. The curve which its function
or shape is not a priori knowledge can not be recognized by HT and is called nonparametric
curve.
The curves in actual images are usually nonparametric crves in the most cases. For instance
the natural feature curves, such as cracks in pavement distress images and rivers in remote
sensing images, can not own a priori knowledge about their functions and shapes when they are
recognized, so HT can not be used to extract the nonparametric curve with break points in noise
images. In this dissertation, nonparametric curve recognition is considered as a kind of
permutation-based optimization problem. The approach proposed in this dissertation can
recognize nonparametric curves by using genetic algorithms(GAs) optimization to solve the
permutation-based optimization problem. The main contents and contributions of this
dissertation are as follows:
1. Academic nonparametric curve recognition approaches using HT are systematically
introduced in this dissertation. The parametric curve recognition approaches using HT are
introduced according to their development and characteristics. The definition of parametric curve
and nonparametric curve are defined correspondingly. The basic nonparametric curve
recognition frame based on permutation-based optimization theory is expressed, and GAs
optimization is successfully used to recognize the nonparametric curves because the optimization
is discrete.
2. Nonparametric Curve Recognition Vision Model (NCRVM) is stated in the dissertation
