建筑图像中线段提取算法研究

赵 越,段忠祥

(1.吉林建筑工程学院 计算机科学与工程学院,吉林 长春 130021; 2.广西工商职业技术学院 财会系,广西 南宁 530003)

建筑图像中线段提取算法研究

赵 越1,段忠祥2

(1.吉林建筑工程学院 计算机科学与工程学院,吉林 长春 130021; 2.广西工商职业技术学院 财会系,广西 南宁 530003)

从图像中提取线段是建筑图像理解和分析研究过程中的一项重要工作。在已有的算法中,最具有代表性的是 Hough变换算法和基于连接的算法。本文在分析图像基本特征的基础上提出了一种改进的线段提取算法,将两种算法的优势较好的结合起来,为系统的设计与开发提供了强有力的支撑。

建筑图像;线段提取算法;边缘检测

0 引 言

图像中线段的提取是建筑图像理解和分析研究中的一项重要工作。对于线段提取的方法,人们提出了许多算法。在这些方法中,最具有代表性的是 Hough变换算法和基于连接的算法。基于 Hough变换的一类算法的特点在于使用直线与点之间的对偶关系,将线段的提取问题转化为像素点的计数问题。这一类方法具有全局性好,抗噪性好的优点,但同时也具有明显的不足：其时间和空间复杂度都比较高,对硬件有较高的要求,难以用于实时环境中。此外,由于算法缺乏局部性,没有考虑像素之间的空间位置关系,因此就容易产生“过度连接”的现象。

基于连接的算法则是另一类具有代表性的线段提取算法,包括启发式连接算法、相位编组算法等[1-2]。这一类算法大致分为三步：第一步为边缘提取,使用适当的边缘提取算子提取边缘像素点。第二步生成基本线段,将边缘像素点近似地组合成基本线段,通常的做法是按照某种规则和标准确定线段支持区,将线段支持区内的边缘像素点拟合成基本线段。这些线段的长度一般较短且数量较多。第三步是连接基本线段,使用适当的方法和标准连接基本线段作为最终的直线输出。

基于连接的算法可以克服 Hough变化算法的复杂度高、局部性差等不足。但是该算法的抗噪性和全局性较差,而且算法的效果与边缘提取结果的好坏有关。

1 改进的线段提取算法

上述两类算法是优势互补的,可以将二者结合起来得到一种更好的算法。本文提出一种改进的线段提取算法。此方法在传统的连接算法的基础上,增加了参考直线这一参数,用于反映图像的全局特征,并对基本线段的连接提供全局性的指导。整个算法分为以下几个步骤。

(1)提取边缘像素点

边缘提取的方法较多,也各具特色。常见的边缘提取算法分为三步走：第一步求出图像和最优滤波器的卷积;第二步对卷积图像求导;第三步求出图像的所有具有极大值的像素点,将其作为边缘点。

(2)基本线段的生成

生成基本线段的通常做法是按照某种规则或标准,确定线段支持区,将线段支持区内的边缘像素点拟合或连接成基本线段。我们不采用这种做法,而是采用八连通链码表示边缘像素点,并根据链码的特征提取基本线段[3]。这些基本线段反映了图像的局部特征。

(3)基本线段的局部性连接

基本线段的生成算法中没有考虑噪音的影响。事实上,由于各种干扰的存在,可能会出现误删、误断的情况。这里我们通过使用线段的局部性连接算法,用于连接间隔不超过 4个像素,且基本共线的基本线段,恢复大部分的误删和误断。

(4)基本线段的全局性连接

局部性连接算法只能将相距很近而且斜率相同的基本线段连接起来,对于相距较远或斜率有一定差别的基本线段,要决定是否将他们相连以及如何相连,需要全局性的指导,局部性算法难以胜任。为此,必须设计出某种基于全局性信息的指导线段连接的算法。

线段连接的全局性信息是指在一定的噪音干扰下,整个图像中基本线段之间的所有可能的共线关系[4]。有了这样的全局信息,我们就可以按一定的规则进行决策,从所有可能的共线关系中找到基本线段之间的合理连接。

为此,我们设计了一个参考直线的参数。这些参考直线不是真实的直线,而是用来反映图像的全局特征的直线。最后在参考直线的指导下,我们将可能共线的基本线段进行连接,生成并输出线段。

经过这些步骤生成的线段同时具有局部特征和全局特征,实现了线段提取的优化。

2 基本线段提取算法的设计

算法采用先断后连的基本思路,主要分为以下几个步骤。

第一步,由边缘生成链码。考虑到边缘线可能会相交,因此,由边缘生成链码分为去交点和编码两个步骤。

(1)去掉边缘的交点。先考虑每个边缘点的八连通邻域,若某个边缘点的邻域中所包含的边缘点数超过两个,则从边缘点的集合中删除该边缘点,直到每个边缘点的邻域中所包含的边缘点数不超过两个。这样,就去掉了边缘的交点,由边缘点构成的每个八连通集合,要么是一条单链,要么是一个环。

(2)编码。对应每个单链或者环,由其边缘点的坐标生成八连通链码。每个用八连通链码表示的单链或环,由第一个像素的坐标、链码和结束标志三部分组成。

第二步,由链码生成基本线段。易见,凡是线段的链码都有其明显的特征,即要么只有一种码值,要么只交替出现编号相邻的两种码值,而且这两种码值各自的游程长度变化很小。由于八连通链码只有八个方向,对应每个用八连通链码表示的单链或环,如果仅仅分析链码方向的不同来描述直线的真实情况是不够的。我们必须借助于链码游程长度这一重要信息。游程长度变化越大,直线方向的改变也就越大。

根据这个特征,我们对每个用八连通链码表示的单链或环,从它的第一个像素开始,依次逐个观察每个码值,当某个码值的出现导致下述三种情况之一发生时,就将它从该码值所连接到两个像素中间断开：(1)出现第二种码值,且该码值与前面的码值编号不相邻。(2)两种编号相邻的码值交替出现,且任何一个码值的游程长度最大值与最小值之差超过 2。(3)出现第三种码值。

断开后,被截断链码的后一个像素自动成为另一个单链的第一个像素。这样的过程从截断处向后继续进行,直到最后一个单链。直观的看,就是对于原先的任何一个单链,如果它表示的是线段,则不被截断;如果表示的是曲线,则被切成若干段,而且,曲线弯曲的越厉害,就被切的越碎。

第三步,删除不满足规定长度的单链或环。这样,未删除的单链的形状可以是严格的线段,或者近似为线段。由链码求出每个单链的最后一个像素的坐标,连接每个单链的起点和终点,就得到所求的基本线段。

3 结束语

本文在已有算法的基础上提出了改进的线段提取算法。算法将 Hough变换的一些优点溶入其中,既有局部性,又有全局性。该算法被用于实现线段的检测与提取功能,将为系统的设计与开发提供强有力的支撑。

[1] D.Crevier and R.Lepage.Knowledge-Based Image Understanding Systems：A Survey[J].Computer Vision and Image Understanding,1997 (67)：163-166.

[2] H.Mayer.Automatic Object Extraction from Aerial I magery：A Survey Focusing on Buildings[J].Computer Vision and I mage Understanding, 1999(74)：140-143.

[3] 汪荣贵,张佑生,高隽,彭青松.房屋的三维几何特征在航空影像中的投影性质[J].工程图学学报,2005(1)：90-92.

[4] 程曦冉,张剑清,张祖勋.航空影像多直角平顶房屋的半自动提取[J].武汉大学学报(信息科学版),2004(12)：66-68.

责任编辑：吴旭云

Research on l ine extraction algorithm in architecture images

ZHAO Yue1,DUAN Zhong-xiang2
(1.College of Computer Science and Engineering,Jilin Institute ofArchitecture and Civil Engineering,Changchun 130021,China; 2.AccountingDepartment,GuangxiVocational College of Technology and Business,Nanning 530003,China)

To extract line segment from images is an important task in understanding and analyzing architecture images.Among the existing algorithms,Hough transform algorithm and the algorithm based on connectivity are the most representative.Based on analyzing the characteristicsof the image,the paper presents an improved line extraction algorithm,which combines the advantagesof the two algorithms and provides the strong support for designing and developing the system.

architecture image;line extraction algorithm;edge detection

TP391

A

1009-3907(2010)06-0073-02

2010-04-28

吉林建筑工程学院青年科技发展基金项目(J20091058)

赵越(1982-),男,吉林通化人,助教,硕士,主要从事人工智能方面的研究。