文档介绍：一类管道三维重建的最佳算法
(理学院数学系数学及应用数学专业任飞)
(学号 1999144231)
内容提要:本工作给出了这样一类管道三维重建的最佳解决:对于一类沿任意逐段光滑
三维曲线滚动的可变半径球形成的管道,若已知它的一族平行切片上的离散化读数信息,重
建该三维管道。本文在得到在整数格点上的最佳估计后,进一步,逐步二次剖分,直至收敛
到离散化读数机器所能提供的全部可用信息下的最佳估计。可以证明本方法给出了该类问题
的完全解决。本质上讲,本算法不同于通常所建立的二维算法[1],而是利用顺序化的逐层信
息,因此可以证明精度远高于二维算法。对于整数格点上的计算,二维算法是ο(n 4 ) 算法,
其中 n 是管道在空间的特征尺度,而我们的算法仅是ο(n3 ) 算法。下一步为了进一步提高精
度,允许最佳估计是非整数的,我们采取的计算策略是进一步逐次剖分,而二维算法是没有可
靠的方法,,当剖分到 m 次时。涉及
到离散点数是 n3 ×8m ,经过分析可知,跟问题有关的计算量不可避免的是 n ×8m ,其中 m
是剖分的次数。为了达到这个计算量,提高运行效率,我们专门进行了优化,将重复运算的
部分转化查表法,降低复杂度。使得实际应用成为可能。另外,本算法还有其它优点,譬如,
管道的中轴线只需要逐段光滑,而且,滚动球的半径也允许是变半径的。
本算法具有很强的应用前景,作为说明,本文还给出了若干算例。
关键词:反问题三维重建指数复杂度对称群查表逐次二次剖分
教师点评:该生的数学基本功扎实,在毕业设计中充分的展示出来,熟悉编程,特别是
VC 的开发环境,比较擅长科学计算,协调能力也相当好,具有良好的合作精神。(点评教
师:黄德云,职称:副教授)
§1 引言
数学模型就是对实际问题的一种数学表述。具体一点说:数学模型是关于部分现实世界
为某种目的的一个抽象的简化的数学结构。更确切地说:数学模型就是对于一个特定的对象
为了一个特定目标,根据特有的内在规律,做出一些必要的简化假设,运用适当的数学工具,
得到的一个数学结构。数学结构可以是数学公式,算法、表格、图示等。数学建模就是建立
数学模型,建立数学模型的过程就是数学建模的过程。数学建模是一种数学的思考方法,是
运用数学的语言和方法,通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的
数学手段。
随着数字化时代的到来,数字化技术已经开始各个领域发挥重要的作用。这样一类问题
是有意义的。对于一类沿任意逐段光滑三维曲线滚动的可变半径球形成的管道,若已知它的
一族平行切片上的离散化读数信息,重建该三维管道。本问题的原始来源是受 2001 年全国
大学生数学建模竞赛 A 题[2]血管(见图 1)的三维重建启发,推广而成的。
这一类是一类反问题,管道的表面是沿逐段光滑的曲线变半径的球滚动形成的包络,而
我们现在是跟据管道的离散化的数字信息来反解出三维管道的中轴线和滚动球的半径。
1
这类管道可视为一类特殊的管道,该管道
的表面是由球心沿着任意逐段光滑三维曲线
(称为中轴线)的可变半径的球滚动包络而成
(见图 1)。例如圆柱就是这样一种管道,其
中中轴线为直线,由半径固定的球滚动包络形
成。
本文研究的是这样的一类反问题,基于该
类管道生成的一族已知连续平行切片的基础
上,通过建立数学模型和计算机的算法设计主
要研究重建三维管道,包括形态,给出中心轨
道方程和滚动球的半径。
查表法,由于切片的信息是以 bmp 图片的形式保存的,bmp 图片是点阵图,即象素图,
所以精确度到每个象素。基于切片的这个特点,把球的信息离散化,球的信息只有整数点的
信息,这些信息包括球面上的点 x,y,z 轴的坐标和半径的长度,也就是每个球面可以由若
干个特征点来表示,并且这些点满足对称群 Oh 群[3],所以只需要若干个点就可以表示整个
球的信息。然后把这些信息按半径的大小,生成表保存成文件,后来计算最大内切球直接查
表得到。
剖分法,由于球心的存在的空间就在切片上的象素点,就在整数格点上,在三维空间中,
该球心点只能表示以该点为中心前后左右上下 个格子里。为了在现有切片的基础上,提
高其精确度,更好的还原出管道的实际的中轴线的轨迹和半径。使球心能在突破整数坐标的
格点限制,(见图 2)采用二分法,进行剖分即细分格子。
指数复杂度,是在剖分的过程中,每一次二分,又因为是在三维空间中,研究的格点数
就变为原来 8 倍,所以实际的计算过程的计算复杂度就是 o(8m ) ,m 是剖分的次数。
对于此