图像最大内切圆求解算法的研究

2006年 工 程 图 学 学 报 2006第2期 JOURNAL OF ENGINEERING GRAPHICS No.2

图像最大内切圆求解算法的研究

李 伟， 周朝晖， 严承华

（海军工程大学机械系，湖北 武汉 430033）

摘 要：为了利用现有图片资料重建管道的三维形态，文中首先将图像数字化并提取了相关信息，然后应用了数学形态学中图像腐蚀处理的思想，提出利用逐层去除边缘的算法求解每张图片中图像最大内切圆，较好的解决了图像三维重建问题。算法中采用了改进的边缘检测算子，该算子能够适合于各种形状图像边缘检测。这一算法在实际求解过程中取得了令人满意的结果。

关 键 词：计算机应用；最大内切圆；腐蚀；管道重建 中图分类号：TP 391

文献标识码：A 文 章 编 号：1003-0158(2006)02-0117-05

Research on Algorithm for Solving Maximum Inscribed Circle of Image

LI Wei, ZHOU Zhao-hui, YAN Cheng-hua

( Department of Mechanical Engineering, Naval University of Engineering, Wuhan Hubei 430033, China )

Abstract: In order to use existing images to reconstruct the 3D shape of pipelines, the

images are digitized and the related information is extracted. Then the thought of image-erosion in mathematics morphology is applied. Finally an algorithm which is used to seek maximum inscribed circle by getting rid of image’s edges layer by layer is presented. This algorithm is preferable in solving problems of rebuilding 3D shape of pipelines from images. An improved operator of image edge detection is used, which is fit for all kinds of shapes. The satisfactory results on practical use are showed.

Key words: computer application; maximum inscribed circle; erosion; pipeline construction

断面可用于了解生物组织、器官等的形态。例如，将样本染色后切成厚约1µm 的切片，在显微镜下可观察该横断面的组织形态结构。如果用切片机连续不断地将样本切成数十、成百的平行切片，可依次逐片观察。根据拍照并采样得到的平行切片数字图像，运用计算机可重建组织、

收稿日期：2006-04-20 器官等准确的三维形态。

1 问题提出及分析

假设某些血管可视为一类特殊的管道，该管

道的表面是由球心沿着某一曲线(称为中轴线)

·118· 工 程 图 学 学 报 2006年

滚动的球包络而成。例如，圆柱就是这样一种管道，其中轴线为直线。针对2001年全国大学生数学建模竞赛A 题题目所给图像[1]，在建模时可作如下合理的假设：

（1）管道中轴线与每张切片有且只有一个交点；

（2）球半径固定；

（3）切片足够薄，其厚度对计算的影响可以忽略不计。

从而得到图像具有两个重要性质：

性质1 若半径固定滚动包络体的任意切面与其中轴线有且仅有一个交点，则此交点为切面最大圆圆心。

性质2 对图像进行离散化后，可能出现切片的最大内切圆不唯一的情况[2]。

对于解决血管立体图像重建问题，关键是找到轴线与每张切片的交点及半径，也就是图像的最大内切圆圆心及半径。目前求解最大内切圆的算法已经存在不少， 其算法思想及运用到血管三维重建中求得的最大内切圆平均半径R 如下：切线法[3]是根据外围轮廓线与最大内切圆有且仅有两个交点，经过这两点的外围轮廓线的两条切线平行且间距最大，求得的结果是最大内切圆半径R =29.529，但是从性质2可以分析出这种方法较为粗略，误差较大，且计算复杂；最大内切圆搜索法[4]是根据血管是连续的，相邻切片与中轴线交点变化也应是连续的，所以在较精确作出第一幅切片中心点的前提下，完全可以在从四周的规定范围内搜索第2个切片图像最大内切圆的圆心所在点，以此类推。最后求得的结果为R =29.8876。但是这种方法要求所求切片必须是连续的，如果只是其中任意的不连续图像时就很难得出正确的结果或者要花费大量时间探索比较大的周边区域；最值距离选取法[4]的基本方法是从边界内部集合取圆内任一点，求对边界每一点的距离，将所有距离的最小值与此点一同记下，遍历边界内部每一点，记录下每一点的对应最小距离放入集合MIN ，提取MIN 中的最大值，即为所求R ，其对应点就是圆心，结果为R =29.18841。这种方法要多次遍历图像各点，因此时间复杂度较高；预处理算法[5]是首先用Photshop 软件对提供的100张BMP 图像做初步分析，粗略估计最大内切圆的半径范围，求得的结果是29.76，但是这种算法中范围估计过程繁琐且主观性影响较大；柳海东等[6]提出将图像分为上下弧，即先把每张取定的截面图中所有像素点进行编号，根据编号将图的边界点划分为上弧、下弧．对于上弧上固定的一点a i ，求出该点到下弧上点b j 的距离d ij ，当遍历上弧中每一点，并得到其对应最短距离D ，则D 为由该截面所确定的管道直径，结果为R =29.5619。如果在程序中增大搜索范围则所得的结果会更为精确，但会增加运算量，同时难以将上、下弧精确分界；文献[7], [8]所述方法对近似圆形的凸形图像具有很好效果，但在处理凹形图像和细长型图像时迭代较为复杂，因为初始点的选择与内切圆的确定由很大关系，结果易于偏离理想位置。

作者运用数学形态学的理论和方法，提出了逐层去除边缘的算法，并将此算法应用到三维血管重建中，得出了理想的结果。

2 实现的算法

2.1 基本思想

在图像处理时将图像离散为像素点，显然最大内切圆圆心是图像中心线上距离边缘最远的点。如果利用边缘收缩的方法，当各个方向上收缩速度一致时，理论上最后才能到达最大内切圆圆心所在点。这种边缘收缩的方法正是来自于数学形态学中的腐蚀思想。

腐蚀

：对集合元素采用向

[9]

量减法，将两个集合合并。设X 是原始图像，B ，腐蚀运算定义为

E (X )=X ={(x,y )|B xy 包含于X } 也就是说，由B 对A 腐蚀所产生的二值图像E(X)是这样的点（x,y ）的集合：如果B 的原点位移到（x,y ）点，那么B 将完全包含于X （以下符号意义相同）。

在腐蚀的过程中首先应该找到边缘元素。利用简单的直接扫描，然后与相邻点进行差值判断的方法，需要很大的时间开销，一般通过边缘判断算子来找到边缘即B 的元素[10]。Roberts 算子是最古老的算子之一，计算非常简单，但对噪声高度敏感；Sobel 算子通常用于水平和垂直边缘的一个简单检测；Laplace 算子是近似只给出梯度幅值的二阶导数的流行方法，但它对图像中的

第2期 李 伟等：图像最大内切圆求解算法的研究 ·119·

某些边缘产生双重响应，而导致腐蚀厚度具有不均匀性，经过一定步数后，会导致收敛点偏离理想位置[9]。通过试验发现，Laplace 算子产生的双重响应，是对方向敏感的。为解决这一问题，作者通过对Laplace 算子进行分解，用正测算子和斜测算子双重互补的方法进行精确运算，并且可以自主的控制腐蚀层的厚度，以改进该算法的精度和效率，最终取得理想的结果。分解后的边缘检测算子如下（8-邻域）

运行一次后未腐蚀像素点的个数，从而可以正确选择下一次腐蚀所用算子；

Max R min, i , j 用来判断程序运行过程中R min 最大的像素点对应的距离和该像素点在坐标系中的位置；

最终结果就是整个过程结束后保留的Max R min, i , j 。

3 运算过程及结果

运算过程中，首先要找到一个较为合理的Mum 阀值，因为Mum 阀值的选择直接影响到算法的可行性和精度。例如，当个别图像Mum 预留小于10时，在达到判断条件之前就可以将整个图形完全腐蚀掉，因而无法进行合理的判断。选择Mum 时，主要考虑运行后生成的表征图像处理精度的平均半径R ，同时考虑时间的开销t 。表1列出了部分图形（图号为0，1，49，50，98，99）对应的半径和整个过程结束后的平均半径R ，其中实际半径数据是对图像离散化后通过大量计算精确得出的。经过分析比较可以得出较为合理的Mum 值。从表中可以看出：当Mum 从10增加到100时，单张图片处理精度逐渐提高，并且时间开销相差不大。例如，当Mum =30时，t =3s，R =28.41613；Mum =60时，t =3s，R =29.427619；Mum =100时，t =3s，R =29.53230，在t 值均约为3秒时， Mum =100时的结果较好。如果继续增大Mum 值，对精度影响并不大，反而大大增加了时间开销，例如，当Mum =200时，t =4s，R =29.53230，t 增加1s 时R 却没有得到改善；Mum =500时，t =7s，R =29.62058；当Mum 增加到1000时，t =11s，R =29.73816，已经能够求得实际尺寸，证明了Mum =1000足以保护所有可能成为圆心的点，处理过程已经稳定。

综合考虑时间开销和精度要求，当不要求特别精确的数据时，就优先采用Mum =100。因为这时求得的数据已经很接近实际尺寸了，平均半径仅相差0.2个像素，考虑图像自身的粗糙性和噪声的存在，可以忽略这0.2个像素的偏差。只有在对数据的准确性要求特别高时，才可以不考虑时间的因素，取较大的Mum 值，或者不采用预留的方法，而是对图像上所有的像素进行直接判断。

101

1−41 0−40

101010

1

正测算子 斜测算子

2.2 算法流程

在三维重建时，逐张调取图片，采集轴线上的点，最后利用Matlab 工具将数据描述的点拟合出曲线。图1是处理单个图像的算法流程，其中：预处理图像时采用了二值化的方法，设置合适的门限值T ，对图像进行门限分割并存储。例如, 用1表示图像，0表示背景。

图1 算法流程

Mum 用来设置保留不腐蚀像素点总数。因为边缘收缩时，难以保证仅仅留下一个孤立的点，所以在算法中采用了这种预留控制的方法。

R min 用来判断像素点到边缘的最小距离； m 和n 分别用来统计正测算子和斜测算子

·120· 工 程 图 学 学 报 2006年

表1 程序运行结果

（采用的计算机系统为Windows XP，CPU ：Pentium(Ⅳ)2.00GHz ，内存: 256M） Mum =10 (t ≈3s)

Mum =30 (t ≈3s)

Mum =60(t ≈3s)

Mum =100(t ≈3s)

Mum =200(t ≈4s)

Mum =500(t ≈7s)

Mum =1000 (t ≈11s)

图片标号 实际半径

0 29 29 29 29 29 29 29 29 1 29.15476 29.15476 29.1547649 28.84441 28.4441 29.41088

29.1547629.83287

29.1547629.8328729.20616

29.1547629.8328729.20616

29.15476 29.1547629.83287 29.8328729.20616 29.20616

30.8707 30.8707 30.36445 30.3644529.73816 29.73816

50 0 29 29 29.20616

98 0 27.20294 30 30 30 30.4630999 26.40076 27.29469 30 R

舍弃 28.41613 29.427619

30 29.53230

30 30.0665929.53230

29.62058

对该组数据进行分析，平均半径r =29.53230，方差σ2

=0.17667，部分图像的处理结果见图2和图3所示，内部白色圆为最大内切圆。

网状结构的图像处理结果。从而可以解决管道不理想状态下的重建问题。

(a) 处理前 (b)

处理后 图

2 对0号图的运算结果

(a) (b) (c)

图4 对单连通图像的处理结果

4 结 束 语

作者采用的思想就是连续去除边界，将最大内切圆圆心保留在最后的封闭图像内，然后在该范围内找到距离边界最小距离最大的点，该点即为圆心，其对应的最小距离就是最大内切圆半径。与参考文献[3]~[9]中所述方法相比，这样处理思路简单，避免了花较多的时间对图像上所有像素点进行判断，而是首先判断可能成为最大内切圆圆心的像素点，然后仅对这些像素点进行进一步判断。将这一算法运用到血管重建过程中，求得的结果合理，并且能够适应不同形状的图像，解决了复杂图像最大内切圆求解问题。因此，可以用于舰船上管道重建，板状余料再利用中的区域判定，和产品表面精度判定等，具有较好的推广意义。

(a) 处理前 (b) 处理后 图3 对49号图的运算结果

采用此算法能够较好解决凹形、细长形图像(如图3) 的最大内切圆求解问题，即使对形状较为复杂的图像也能高效的求解出最大内切圆，图4列出了部分图像的处理结果，原始图像如背景所示，白色圆为所求最大内切圆。其中，图4(a)是对具有凹形边缘的图像的处理结果，图4(b)

是

对环状结构的图像的处理结果，图

4(c)是对具有

第2期 李 伟等：图像最大内切圆求解算法的研究 ·121·

参 考 文 献

[1] 2001年全国大学生数学建模竞赛题目[EB/OL].

http://csiam.edu.cn/mcm/mcm01/AB01.doc. [2] 欧文华, 李 炯, 等. 血管的三维重建模型[J]. 暨南

大学学报(自然科学版), 2003, 24(5): 54-58. [3] 丁峰平, 周立丰, 等. 血管管道的三维重建[J]. 工程

数学学报, 2002, 19(2): 47-53.

[4] 金 建, 段 婿, 等. 平行切面三维重建[J]. 河北工

业大学学报, 2002, 31(4): 102-107.

[5] 饶从军, 钟绍军, 等. 血管的三维重建问题[J]. 延边

大学学报(自然科学版), 2003, 29(3): 170-173. [6] 柳海东, 陈 璐, 等. 血管切片的三维重建[J]. 工程

数学学报, 2002, 19(2): 41-46.

[7] Sun Yuqin, Che Rensheng. Novel method for solving

maxiMum inscribed circle [J]. Photology Precision Engineering, 2003, 11(2): 181-187.

[8] Israel Amir. Algorithm for finding the center of

circular fiducials [J]. Computer Vision, Graphics, and Image Processing, 1990, 49(3): 398-406.

[9] [美、捷、英] Milan Sonka, Vaclav Hlavac, Roger Boyle

著. 图像处理、分析与机器视觉[M]. 艾海舟, 武 勃等译. 北京: 人民邮电出版社, 2003.

389-390.

[10] Ribaric Slobodan, et al. Efficient edge detection

method by using focus of attention area [J]. IEEE International Symposium on Industrial Electronics, 1999, 3: 1218-1223.