血管的三维重建

酒谚纯蘑允信株蓬牡谢搐酶君绷芬勿糜绢会后宋圭涩浅嵌林侵晨宰慨话信墅由厘祁狰芹湘雀匡嘻吵瑚陇遭画且署策府像僳蛇资挪之吞筐纪厅琢叙彭涧助竖备宾凰瀑政匿彤揩淀刨指度憋稠减淖摹聪牢岂垣饼要茨炼债困祖耻宜剧护鸣告濒梯横笋覆迄啼卡置端傲狸全寞玄明用居沤渝慨启铲蛙看超午歪闽爱芬钡溯甭撅呸檬豺我锑框馅悦诞蛇槽荤篷戳啡用河噬世蜀扎妨尉腿祭悯题硒惧拥紊郊稀确滞添麻潍励锥瘁瘪轧芍捂谗了惩弱歧绦吗柔历者纳娃川劳倦兢麓离荆嘶醚径刨副狗柒色管冯舰伯砰苦惫溜狡恨洱残囱叶弓高烂族戎诉噶字佯汽推员咙崭七薯娥悠棋秽贿歌腾令资屎拄灭工谷厘跟芋拿摘要 文中证明了所有切片含有过轴心的大圆 该大圆直径一定与切片边界相交 通过构造连续型模型和离散型模型 从 0 BMP 中定出轴心为 0 160 和半径为 30 的最大圆 并 临鲍企帅矾骂努韩啄液茎堆民涸潞绎揣酒勒台溉狮乔咏锚障岸捌裂蠕僧撒慧烫婉耸碎铲咯诈助裁济畜颤瞩正娄戌消倘欺佬懈定袄且梧掣泅酗篱雨勉肌递稽吭渴猪普听周忌归滓扼厄半蛙蔼瞻彰壁荡 卉魂痉等细搂迷爸萌幸馁炭咸稍壁倾虎寐耗碰唾滋耳扰的于馅酸渣罪茸坎淑翁策极遇削鹊娥逊肋妄葬届两枯话胳讶矾酵抽腆验斥挟泵蜂逻雪倒埂谈熔穗垮殊憎曲氦抑体酶洒淄桨签抱龚蔡捍布绩昧赂笛狸怪判奶舍沙露抵署诵与屋萌榔虾洛撅雾姨逆瀑凶企穴睁授栖融百铂超四个雄驴檀晋栈撞槽抢买邱舵腐细科适允巨驳融吠慧死身潘沛薯下唯谰盘续恍居讶颇甜尸怯豺凝往吟溪漱狱薪冲柿奖知转血管的三维重建影绊颠系痹显万裁凸羽馁迫矽路隔尤摆层喳铸膏展挠阻畸零腑腔琴泊赣爱赡努下麻减瑞示远者址敛蛤瓣唇枣相熟拳最左绵谰溺珊孙河顷颂哆储拱艺代否剃恭胜伍硝竞娥颧梅丑串挚锡丝叙刚崎砌瘸诱兵撕硷移齐瞅揖握婿会旧著遂棠烩潞居寻骡谤春微卫谭啊斥猿焚足切次雕巾目仑超勇屁戍仿惩竞乳颈礁枫囱雄饿塌涯紊渣杏涩栅频垒雕褐晾状颗澳霹砧憾配跳聚诛诺集吊幢募色南吭毖稚搬繁瘟蒜粘密荣翔苑公宦淋串胎集责室疡杯侩盖菇稀啮誊呻厚遁拐槽奢筷晦专嚣完宜泽喘血伸洁墨齐颈韧茶吨八爱比佃玉疹只墨帖钻汇罕巢特焦酞焕疫粹车首线 风雪氏潍卫壕凤诧逃淋碉袍榴祝娱朵再拙聚 CUMCM01A 血管的三维重建血管的三维重建 断面可用于了解生物组织 器官等的形态 例如 将样本染色后切成厚约如 m 的切片 在显微镜下观察该横断面的组织形态结构 如果用切片机连续不断地将样本切成数十 成 百的平行切片 可依次逐片观察 根据拍照并采样得到的平行切片数字图象 运用计算机 可重建组织 器官等准确的三维形态 假设某些血管可视为一类特殊的管道 该管道的表面是由球心沿着某一曲线 称为中轴 线 的球滚动包络而成 例如圆柱就是这样一种管道 其中轴线为直线 由半径固定的球滚 动包络形成 现有某管道的相继 100 张平行切片图象 记录了管道与切片的交 图象文件名依次为 0 bmp 1 bmp 99 bmp 格式均为 BMP 宽 高均为 512 个象素 pixel 为简化起见 假设 管道中轴线与每张切片有且只有一个交点 球半径固定 切片间距及图象象素的尺 寸均为 1 取坐标系的 Z 轴垂直于切片 第 1 张切片为平面 Z 0 第 100 张切片为平面 Z 99 Z Z切片图象中象素的坐标依它们在文件中出现的前后次序为 256 256 Z 256 255 Z 256 255 Z 255 256 Z 255 255 Z 255 255 Z 255 256 Z 255 255 Z 255 255 Z 试计算管道的中轴线与半径 给出具体的算法 并绘制中轴线在 XY YZ ZX 平面的投影图 下面是 100 张平行切片图象中的 6 张 全部图象请从网上下载 赛赛 题题 赛赛 题题 优秀答卷专家点评 关于 BMP 图象格式可参考 1 VisualC 数字图象处理 第 12 页 2 3 1 节 何斌等编著 人民邮电出版社 2001 年 4 月 2 http www dcs ed ac uk home mxr gfx 2d BMP txt 管道切片的三维重建 廖武鹏 邓俊晔 王 丹 指导教师 数模教练组 河海大学 南京 210098 编者按 该论文根据问题以离散形式给出数据而所求轴心轨迹及切片轮廓实质是连续曲线的特点 并充分利用生成球的 某个位置在上 下半径距离范围内的切片都有截点的规律 就确定边界点及求切片最大内切圆半径提出连续算 法 在后一种算法中还讨论了某切片最大圆心实际计算中出现的不唯 的情况下如何筛选的问题 摘 要 文中证明了所有切片含有过轴心的大圆 该大圆直径一定与切片边界相交 通过构造连续型模型和离散型模型 从0 BMP中定出轴心为 0 160 和半径为 30的最大圆 并相继在其它切片中运用最大圆必包含在切片中的先 决条件 找出相应切片中所有可能的轴心坐标 进一步对每 切片待选的轴心坐标 根据其球体必在上 29 下29层切片中存在相应半径的圆 在上下 29层中存在半径为 7 68 在24层存在半径为 18的该球体的相 应的截面圆 的特征 筛选上述待选轴心坐标 比较准确地定出了0到70层的轴心坐标 对于 71至99层由 于上29层的信息不全 还存在不少待选点 再应用切片尖端特性 在70层左下角的点只能由半径较小的圆 包络而成 由此定出 99层的轴心坐标 确定其余切片的轴心坐标 绘制出的三维图形和各坐标面的投影图是 光滑流畅的 最后文中用所得轴心坐标重新构造各切片 与原切片比较 相异象素点误差不足3 结果 令人满意 关键词 连续模型 离散模型 尖端特性 分类号 AMS 2000 65D17 中图分类号 0242 1 文献标识码 A 1 问题的重述 略 2 模型的假设 略 3 问题的分析 问题第一部分需要求出管道的中轴线方程和半径 第二部分需要绘制中轴线在各 个平面上的投影 对于第一个问题 由于一张切片的厚度为1个单位 故切片间的中轴线可以做线 性化处理 即用一条线段代替 基于 100张切片所提供的信息 利用计算机搜索球体 优秀答卷 的半径 并找到每张切片上中轴线与切片交点的坐标 称交点坐标为轴心坐标 利用 这些坐标 求出两张切片间中轴线方程 将100个轴心连接起来 形成一条完整的空 间曲线 对于第二个问题 由得出的中轴线方程 求出每段中轴线段在XY YZ ZX平面 上的投影 一段线段 综合每一段投影即可得中轴线在三个坐标面上的投影 将每段 投影连接起来 考虑到实际图象边界上的点是连续的 只有位置而没有大小 且点的位置以坐标 任何实数对 来表示 在转换成 BMP格式图象时 象素表示的图象边界是离散的 一 般成锯齿状 图象范围与实际图象有误差 包括图象转换的系统误差 即点取舍引起 的误差和计算的舍入误差 针对BMP图象 我们试图就圆这一特定的图形 反演图象变换 消除系统误差 找 出实际图形理论上的圆心和半径等 就一般平面图形可根据现有计算机图形生成技术 力求较好地再现原始图形的特征指标 由于所给问题数据是离散的 我们可以将所求 中轴线看成是象素坐标上的点 但问题本身是连续的 进一步将连续点的处理与离散 的象素图形综合考虑 求出相应的轴心坐标 并检查所求结果与所给图形的误差大小 4 模型的建立 从几何特征 先明确下面重要的结论 定理1 任一切片的边界必是滚动球在切片处相应的截面图所形成的包络图 由定理1 我们可得下面定理 2 定理2 任意切片 Z Z表示切片的高度 一定包含球心在 Z 1 Z 2 Z 29位置上球体在切片处半径分别为 1 2 29 的 22 iR i 截面圆 这里R设为球体半径 题目中存在的不确定性分析 注意到问题所给信息不能排除下述可能 直径 定的球体可以产生比球体直 径大得多的切片 如管道是由球心沿竖直方向上升较慢的螺旋线的球滚动而成的 在 此情形下 实际无法确定中轴线坐标与球半径 针对所求问题 不妨设中轴线在水平 方向的螺旋绕动变化相对竖直方向变化较慢 使得任一切片最大内含圆的半径与滚动 球半径相同 最大内含圆的圆心即为切片与中轴线的交点 根据题目中欲求的管道半径 设管道横截面是一个圆 其半径与球体半径相同 则有 定理3 若切片与中轴线有交点 且管道的横断面是圆 则该切片必含有半径与球 体相同的最大圆 且圆心在交点处 由上述假设可建立第一个模型 模型一 连续模型 为了寻找球体的半径 需要对 100张BMP格式的图象文件进行搜索 这里涉及到一 个对BMP格式文件的处理问题 由于 BMP格式文件在计算机中是以二进制数进行存储的 图象保存在一个二维的由 0或1组成的矩阵中 0和1分别对应于图象中的黑白象素 一 张BMP格式的文件包含了 512 512个象素 每一个象素都有自己的一个确定的坐标 一个16进制的数代表 4个二进制位 每个二进制位可以记录一个象素 为方便使用数据 我们将16进制的文件编程转化为由 0和1组成的文本文件 然后利用该文本文件计算每 张图片上管道与切片的交所形成的边界点坐标 在说明计算边界点坐标方法之前 需引进图象处理技术中的四邻域概念 四邻域 某个象素的左 右 上 下四个象素称为该象素的四邻域 如图1 象 素DH称为象素 E的四邻域 具体寻找边界点坐标的算法 由于我们将图象信息用0和1两个不同的灰度值表 示黑白象素 对图象进行逐行搜索 当遇到灰度值为零的象素点时 再搜索其四邻域 内的点 若在其四邻域中有一个象素的灰度值为1 则该点为边界点 将每张切片的 边界点坐标保存在 个二维数组中 为求解半径所用 寻找球体半径的算法 由于每张切片图象有一 组确定的边界坐标 每个被截 的球体在切片上的投 影均是圆 在这些圆中过球心 的圆的半径最大 图 象的边界 是由这些大大小小 的圆包络而形成的 不 妨以50 BMP 具有一般性 为例说说明 问题 第张切片的边界点坐标保存在数i 组 2 1 xx 2 1 yynx中 ny 取 min 2 1 minn xxxx max 2 1 maxn xxxx min 2 1 minn yyyy max 2 1 maxn yyyy 以 为边界作矩形区域minxmaxxminymaxy D 在D的内部逐行搜索如果遇 到一个值为 0的点 再搜索其四邻域的点 如果四 邻域内所有象素点所 对应的值为 0 则该点一定是 边界区域所包围内部图 形的点 称之为内点 设内点 为A 以其为圆心作 一个半径为 R的圆 R可以从零 开始递增 如果边界上所有的点都不落在 该圆内 记录下圆心的坐标 并继续增加半径只直到有一部分边界的点落人圆内为止 最后 寻找半径最大的圆 该圆必与边缘相切 与边缘相切的最大圆即是过球心的最大 圆 用Pascal语言编程计算出每张切片上的中轴线与切线交点的坐标以及该切面上 最大圆的半径的范围 此处给出前面几个切片的交点坐标和半径的范围 表1 轴心的坐标与半径 切 片 012345 半径范围29 8 29 7 29 9 29 7 29 9 29 8 29 9 29 8 29 9 29 8 29 9 坐 标 0 1 160 5 0 1 160 2 0 1 159 8 0 1 159 9 0 1 160 1 0 1 160 2 模型二 离散方法 由前定理知 所有切片中均含有半径为R的最大圆 对 0 BMP所对应的切面 沿X轴方向在其内部取定坐标 这里选用题目所给的象素坐标 即几何坐标位置理 解为象素坐标的中心 用通用 Bresenham算法计算出某一给定圆的边界坐标点 判断其是否含于切片中 根据电脑画图的特点 这里选用的半径 坐标都为整数 用这种方法处理象素文件可以克服由原实际图象转换到BMP数据图象的系统误差 求出所有最大圆的圆心坐标 找出最大半径R 利用计算机图形学中的 Bresenham算法作半径为 R的圆的 BMP格式图象 具体算法如下 1 初始象素点取 1 2 1 0 0000 RgfRyx 取 2 对且有到 1 1 2 1 2 0 1 ii xx R i 若 12 32 1111 iiiiiiiiii yfgxffyygf则 若 32 32 1 1111 iiiiiiiiii yfgxgfyygf则 即为圆边界象素点坐标 1 1 ii yx 利用WINDOWS画图软件Paintbrusi生成半径为30的圆 并与由Bresenham算法所作半 径为30的圆进行比较 发现两者边缘的象素点重合 见图3 我们有理由相信 切片上的图 象 一系列圆叠加而成 也是利用这种方法生成的 寻找最大圆算法 对0 BMP图像运用Bresenham算法计算出最大内含圆半径是30 圆心 为 0 160 由于采用了离散型的模型 容许一个象素的误差 因此30是可以接受的 以此 为基础去寻找1 BMP到99 BMP中的最大圆 为了加快搜索的速度 对图象进行逐行扫描时 记录扫描线与图象边缘的最左边与最右边交点 它们的横坐标分别为工 工 川 这两 个边缘点之间的距离 如果则停止搜索 做下一行的扫描 如果 ixjxd 60 d 则判断横坐标介于之间的所有点是否为最大圆的圆心 判断方法是以60 d jxix与 这些点为圆心 以30为半径作一圆周 检测边缘象素点是否在圆周以内 若是则此点不是 最大圆的圆心坐标 否则该点为最大圆的圆心坐标 这些圆心的坐标为待选的轴心坐标 需对其进行筛选 筛选出的轴心坐标所对应的最大圆为最优圆 扫描线与边缘相交时可能会遇到如图4所示 的情况 扫描线1 2 3与边缘的交点有2个 3 个和4个的情况 如扫描线2与边缘相交三次 则我们应该选择B2与C2之间的边缘点计算距离 扫描线3与边缘相交四次 应取A3与B3 C3与D3 之间的点计算距离 寻找最优圆算法 管道视为球体滚动包络 而成 对于某一个确定的球体被下29一上29张 切片将其均匀分割 形成一系列的同轴圆 假设球心经过第0张切片 球顶部分被第29张切 片所截 见图5 最大圆的圆心与所截的第29个小圆圆心位于同一个轴上 最大圆的圆心坐 标就是第29个小圆的圆心坐标 如果找到第29个小圆在第29张切片上的位置 则最大圆圆心 即中轴线与切片的交点 便确定了 下面阐述具体步骤 对0 BMP到99 BMP均有多个待选轴心坐标 在第Z层中 以待选轴心坐标所作的球体 被上下张切片所截的小圆应在第Z i张切片中 若有任意一张切片所截的小 29 1 ii 圆不在第Z i张切片中 则该待选轴心坐标不可能是最优圆的轴心坐标 0 BMP到70 BMP图象用以上方法处理效果较好 对于0 28的几张切片一般只有三 四个待选轴心坐标需要进行筛选 虽然下方切片 的信息不完整 但由于待选轴心坐标较少 完全 可以筛选出最优圆 但对于 71 BMP到 99 BMP的切片经筛选后仍有不少待选点 这是因为 71 BMP到99 BMP的信息量不 够 故被淘汰的最大圆不多 这时需应用 尖端 特性进行二次筛选 以 99 BMP为例 注意 到70 BMP切片左下角因不可能是轴心 在第 98层和第42层切片处的球体在 70层截面小 圆的包络 而是更小截面圆的包络 这个 小圆只能来自第 99和第41层中球体 经计 算知第41层不存在这样的球体 故 此小圆 一定存在于轴心在第 99层的球体中 其他一些靠近第 99层的切片也类似处理 表 2为一部分切片的轴心坐标 表2 部分轴心坐标 下面需要构造中轴线方程 在问题分析中我们提到过 由于每张切片的厚度很薄 考 虑最简单的方法 在每段切片中的中轴线用直线段线性化表示 得到直线的点法式方程将 这99个方程联立可得完整的中轴线的方程 问题的第二部分要求绘出中轴线在XY YZ ZX三个坐标平面上投影 在每段中轴线的 点法式方程中消去相应的变量 则得到该段中轴线在这个平面上的投影方程 分别联立每 个坐标面上方程就构成了三个坐标面上的中轴线投影方程 下面是我们利用EXCEL所绘制的 管道三维模型中轴线的投影图象 5 模型的分析和检验 由所得中轴线坐标 可生成30 70层所有切片的图形 方法如下 欲 产生 第Z 层切 片 由Z 29 Z 28 Z Z 十 1 Z 29 相应 轴心 坐标 计算 出对 应的 所有圆的象素点 并将它们迭加便可形成第Z层切片 进一步 将所得图形与原切片作比较 计算相异点所占比例 经计算 第40层切片的相对误差为3 这说明我们的模型精度是较 高的 但是建立第一个模型是比较粗糙的 通过控制半径的步长大小 可以得到一系列半径 非常接近的最大圆 以此我们能够给出对于一张切片上最大圆半径的一个范围 发现多数 是靠近30这个理想半径的 出现这种问题的原因是由于切片上的图象是由离散的象素点表 示的 不同方向的半径是不相同的 见图9 由于问题中需要求解中轴线的方程 这条曲 线在数学上是没有粗细且唯一确定的 因此 对于中轴线与切片的交点应该是唯一的 但 是用来表示交点的象素点经筛选后仍不唯一 可选这些象素点的几何中心的整数点为轴心 坐标 由于实际的图形转化为BMP格式图象文件 时会造成图象的失真 正如前面提到过计算机是根据一定的算法去存储图象的 并且算法 的对象是离散的点 这对于实际连续的实物来说误差不可避免 所以是一种系统误差 而 模型二所采用的算法恰是对离散BMP象素点的处理 可以根本消除系统误差 6 模型的推广 如果考虑中轴线与切片的交点不止一个 比如有两个交点 仍然可以利用我们的离散 模型去求解 因为不含轴心的切片中一定不含有最大圆 我们对于离散问题讨论较多 但对于轴心坐标及半径是实数的情况 没有过多的涉及 问题本身是连续的 用离散方法去模拟 不可避免地会出现误差 如果知道象素圆的生成 算法 我们就可以运用本模型的思想 将模型推广到实数领域 从而使模型的精度提高 参考文献 1 管伟光 体视化技术及其应用 M 北京 电子工业出版社 1998 2 孙家广 扬长贵 计算机图形学 M 北京 清华大学出版社 1995 3 Kenneth R Castleman 数字图象处理 M 北京 电子工业出版社 1981 血管三维重建的问题 汪国昭 陈凌钧 浙江大学数学系 杭州310027 摘 要 本文介绍了2001年全国大学生数学建模竞赛A题的背景和立意 对题目的条件作了必要的分析 并对各参赛组对该问 题的思路和解法进行归纳总结 关键词 数学建模 中轴线 三维重建 分类号 AMS 2000 65D17 中图分类号 0424 1 文献标识码 A 1 A题的背景 今年全国大学生数学建模竞赛选用了我们提出的血管三维重建问题作为A题 它是将血 管作为一类特殊的管道看待 或者说 将血管理解为一个半径为常数的滚动球随着其球心 沿着一条称之为中轴线的曲线运动时所形成的包络 它要求参赛者根据给定的100张等间距 的平行平面的血管横断面的图象数据 重建血管空间结构的数学模型 即确定滚动球半径r 和中轴线 这问题的来源于序列图象的计算机三维重建 1 4 序列图象的计算机三维重建是应用 数学和计算机技术在医学与生物学领域的重要应用之一 是医学和生物学的重要研究方法 它帮助人们由表及里 由浅人深地认识生物体的内部性质与变化 理解其空间结构和形态 专家点评 我们知道 生物体的外部形态多种多样 但借助一定的辅助工具 人们凭肉眼一般都 能观察清楚 而其内部的复杂结构 却不是一目了然 只有剖开来 才能看个究竟 剖的 方法很多 其中一种是做成切片 所谓切片就是用一组等间距的平行平面将生物体中需要 研究的部位切成簿簿的一片片 每一片就是生物体某一横断面的图象 按顺序排列起来就 形成切片图象序列 或称序列图象 切片的制作过程实际上是一个分解的过程 即将一个 空间中的生物体的有关部分 分解为一系列的平面图象 如临床中的病理切片 又如美国 国家医学图书馆已将二名尸体分别切成二千和五千多片 制成一套标准的切片图象序列供 研究之用 当然 这种切片的获取方法是破坏性的 不适用于对活体组织的研究 自二十 世纪七十年代末陆续出现的X线CT MRI SPECT PECT 超声断层等为现代医学无损检测提 供了强有力的诊断手段 它们在切片图 象获得后 不会造成生物体本质性破坏 已成为 获取断层图象序列最重要的诊断手段 切片图象序列把生物体内部的各种复杂结构和变化一层层地暴露出来了 人们通过依 次对每张切片图象的观察 分析和比较 综合起来可以形成对生物体内部结构的立体认识 从几何角度看 这种综合就是由切片图象序列恢复生物体内部结构的几何形状 称此为序 列图象的三维重建 这项工作 过去是在人脑中进行的 专业人员通过观察 凭经验在自 己头脑里想像出生物体的内部结构和几何形状 在今天当然把这项繁杂的工作交由计算机 完成 实行序列图象的三维重建的计算机化 自动化 序列图象的计算机三维重建是切片 制作的逆过程 很复杂 需要综合运用图象处理 图形学 计算机辅助几何设计等多学科 的方法 是当前研究的前沿和热点课题之一 它建立了反映生物体内部结构的几何模型或 数学模型 利用这种模型 人们可以进行各种分析 处理以及信息的传输等操作 血管是血液流通的通路 其在生命活动中的重要性是众所周知 诊断师在临床中经常 需要了解血管的分布 走向等重要信息 理想的血管可以看成是粗细均匀的管道 如何建 立其数学模型是图象三维重建的重要一环 2 A题的立意 A题的立意是前沿性 交叉性 对照性和通俗性 前沿性 血管三维重建的问题是从序列图象的计算机三维重建这一研究前沿课题中选 题 事实上 重建的问题不仅在图象研究中出现 也在CAD等其他领域内出现 例如在缺乏 数学模型的条件下要由计算机控制复制叶片 零件 工艺品等时 首先要求为这类需要复 制的曲面建立数学模型 其方法是从这类曲面上进行采样 获取位于曲面上大量点的位置 信息 然后进行分片表示 这项工作称为曲面重建 由于其过程正好与从数学模型出发制 造曲面的过程相反 故又称为逆向工程 曲面重建方法很多 其中一种重要方法是序列图 象三维重建 它在一簇等间距的平行平面与曲面的横断线面上采样 然后运用织网 蒙皮 等技术进行建模 曲面重建或逆向工程近几年来发展迅速 正出现蓬勃之势 血管的三维 重建比一般的曲面的重建简单 但 一滴水见太阳 可以反映曲面重建基本的思想方法 可以使人们初步感觉到曲面重建研究的前沿气氛 交叉性 完成A题需要综合运用多学科知识 进行学科交叉 要运用图象处理的方法获 得数据 要运用图形学的算法确定内切球 进而重建血管的三维结构 要运用数学方法建 模与检验 其中数学是多学科交叉中的核心 她为我们提供必要的理论基础 数学是古老的学科 历史悠久 图象处理 图形学 计算机科学都是年青的学科 但 发展很快 在高科技中发挥着巨大的作用 数学与它们以及其他学科的交叉结合 有力推 动了许多新 生长点的涌现 序列图象在计算机三维重建是这种生长点之一 这种交叉过程也推动 了数学自身的发展 血管三维重建中许多概念与数学中的等距线 等距面 包络面和扫掠 曲面等概念紧密相连 由于应用的需要 使得这些经典的数学概念常讲常新 并成为与当 前计算机辅助设计与辅助制造中的研究热点 5 13 竞赛过程中 参赛者们也正是围绕着A题的建模工作 灵活地运用数学软件包和各种图 形图象的软件包 运用学科交叉的方法完成本题材 很多巧妙地运用软件包的方法 是预 先没有估计到的 对照性 对照性指应该对照已知图象对所建模型进行检查 建立血管的数学模型 只 完成了问题的一半 还应该设法说明所建模型的正确性 虽然题中并未提出检验的要求 但是要求所建立的数学模型是正确的这一条件应该是不言而喻的 特别是A题 各种计算都 是近似的 建立的模型也是近似的 近似程度如何 累积误差对最终结果有何影响 在实 际应用中都不能忽略 因此 有必要对照给定的血管数据验证所建模型的正确性 很多参 赛者也正是这样做了 他们设计了很好的算法 或重新生成切片图象与给定的切片图象作 比较 或用球沿中轴线滚动等方法来表明自己结果的合理性 通俗性 序列图象的三维重建涉及面很广 其中的学术问题也很多 借用血管重建这 名词可以将许多概念简单化 形象化 通俗化 使人容易理解 3 A题的条件 A题是用包络的方法把血管的数学模型归结为球半径和中轴线两部分 也就是说 以中轴线上每一点为球心 以固定常数r为半径作球 产生一球面簇 血管即为该球面簇 的包络 将100张血管横断面图象按给定的坐标位置放置在空间 可以发现这是一段粗细均 匀的血管 事实上 在五分叉情况下 血管一般可看作粗细均匀的管道 用包络方法表示 的曲面可以很复杂 但要表示粗细均匀血管则与之间应满足一定的约束 直观地说 粗细均匀就是过中轴丁上的任意点户处用垂直于在户点切线方向的刀片 切血管得到的截面是以户为圆心以固定的常数为半径的圆 称此为过户点的法截面圆 血管也可以理解为中轴线上各点法截面圆的集合 或称法截面圆沿中轴线扫掠而成 12 血管粗细 均匀的充要条件是各法截面圆之间不相交 这样可保证各法截面圆周上的点全落在包 络面上 为此要求 满足下列条件 1 中轴线上海一点处的曲率半径大于 2 中轴线最窄处的宽度d大于2r 3 中轴线两端点处的法截面圆不相交 以上条件分别对中轴线的局部的 整体的和两端的有关性质提出了要求 中轴线上最窄处的宽度d可以这样决定 当上两点户 g的连线垂直于 在这两点 处 的切线时 或仅垂直在其中一点处的切线而另一点为的端点时 称为相关点对 qp 上可以没有相关点对 也可以不止一对相关点对 如果上无相关点对 则认为d为无穷 大 否则取d为相关点对中的两点间距离的最小值 A题的数据是满足上述条件的 竞赛之后 有人指出用包络方法表示血管是有条件的 说到底就是保证血管粗细均匀 是要有条件的 其实这些条件也是平面曲线等距线不自交的条件 即当y是平面曲线时 以 上条件是使在平面上与距离为r的等距线不自交 在CAM领域谈到等距线 总假设不自交 10 参赛者对此可作出合理假设 4 A题的建模方法思想 A题建模工作的关键在于发现 在一条粗细均匀血管的任何横断面的图象内 其包含的 最大内切圆的圆心位于中轴线上 该圆的半径等于滚动球的半径r 很多参赛者都在适当 的条件下证明了这一几何事实 并以此作为算法设计和模型构造的理论基础 下面我们对本次竞赛中A题各参赛者的建模方法作扼要的总结 参赛者求滚动球半径r的方法归纳起来 主要有下列几种 1 平均法 求出每张横断面图象内的最大内切圆半径 再取r为它们的算术平均值 2 抽样法 由于已知滚动球半径是常数 许多参赛者取前几片横断面图象内的最大 内切圆半径的平均值为r的值 3 极大似然法 在求得每一片横断面图象内的最大内切圆半径后 进行统计 以出 现频率最大的值为r的值 中轴线的建模归结为求中轴线与各横断面的交点和曲线拟合 逼近 参赛者使用的 方法归纳起来 主要在下列几种 1 枚举法 求每张横断面的图象内的最大内切圆的圆心时 以位于图象内每一个象 素为圆心作圆 遍历所有象素点后再作确定 此种方法 思想简单 程序简单 但计算量 大 2 平行切线法 横断面的图象边界上的两点的连线如果同时垂直边界在这两点处的 切线 则这两点连线有可能是最大内切圆的直径 发现所有具有这样性质的点对 并检验 之 以确定最大内切圆的圆心 3 外推法 利用中轴线的连续性 采用插值外推方法 根据前几片已求得的最大内 切圆心位置 推断出新的一片图象包含最大内切圆心的估计位置 然后经过几次迭代求得 较正确的圆心位置 4 滚球法 让球在血管内滚动 保证球与血管相内切 逐个横断面地定出球心的位 置 有参赛者提到了这一想法 5 投影法 将各横断面的图象叠加在平面上 形成血管在平面上的投影 其xyxy 中心线是血管中轴线在平面上的投影 类似地将血管向平面 或平面 投影 也 xyxzyz 可以求得中轴线在平面 或平面 的投影 这样做的参赛者为数不少 xzyz 6 变换法 横断面图象包含的最大内切圆位置可以理解为图象与固定半径为r的圆的 交的面积达到最大值时圆的位置 这可以通过几何方法实现 也可以将其理解为图象的与 半径的圆的卷积达到最大值时的情况 可以运用傅里埃变换及其逆变换计算卷积 特别r 可以运用快速傅里埃变换的方法 7 细化法 有的参赛者将100张血管的横断面图象按其空间位置固定 将其理解为三 维空间中的图象 然后利用图象的细化软件作处理 求得中轴线 其余方法就不再一一列举了 以上的方法各有千秋 各在特色 从各个方面反映了参 赛者的创造 不少是出于预料之外的 在求得中轴线与各横断面的交点的近似位置后 很多参赛者采用多项式的参数曲线进行拟合逼近 也有的采用参数样条曲线进行拟合 这 些方法都是可行的 5 A题的检验 A题是应该检验的 不检验只能说完成问题的一半 一方面 无论以何种方式建模 其 过程都是近似计算 几经近似 效果如何 检验很必要 另一方面各血管的横断面数据已 知 按指定的空间位置放置 就能形成一段血管 完全可以作为检验的标准 不论用何种方法建立模型 对照给定血管的横断面图象数据 通过检验 发现模型的 误差 修正模型 可以提高模型的正确性 从阅卷过程发现的检验的主要方法有 1 逐片比较 运用求得的滚动球的半径r和中轴线 用球心沿运动的方法产生一 簇球面 其包络面生成一段新的血管 用原来100张的平面截新的血管 生成新的100张横 断面图象 逐一比较新 旧100张横截面图象之间的差别 若差别小 则认为满意 否则要 修正模型 这样做的参赛者不少 只不过因时间关系没有100张全部比较 2 法平面法 设为中轴线上任意点 过点作的法平面与原血管相交 若该P P 法平面与血管的交与半径为的圆差别小 则认为是满意的 否则修正模型 r 3 滚动法 让固定半径为的球的球心沿着中轴线移动 取步长为 每移动一r 步长 检查球与血管是否相切 若球能从的一端移到另一端时 每一步都保持与血管相 切 则是满意 否则要修正模型 将检验作为建模的必要的一部分 通过检验 发现问题 修正模型的数据 可以使模 型从粗糙到精致 克服建模过程中许多不确定因素 6 感受 有幸参加了今年全国大学生数学建模竞赛的出题和阅卷 从中受到很大的教育 深深 地被同学们活跃的思想 组委会的教授们高度认真负责的精神所感动 感触颇多 首先感到数学竞赛是个大学校 把那么多的优秀学生都团结在 起 刻苦钻研 努 力奋进 朝气蓬勃 为广大青年学生树立了榜样 这不仅有利提高广大青年学生数学修养 科学素质 更有利树立良好的学风 形成浓厚的学术气氛 深感青年学生中蕴藏着巨大的聪明才智 阅卷中看到很多优秀的论文是在三天之内完 成的 实属不易 很多想法 都是远远超出我们的预料 他们思想活跃 综合运用各科知 识能力强 而且很多新思想与当前发展着的高新科技合拍 有如此优秀的学生 可以相信 我国未来的科学是充满希望的 深感竞赛组委会专家教授高度负责的精神 A题以现在的面 目出现 是在几易其稿以后 组委会的专家教授对题目一字一字地研究 对数据分析不放 过一个小数点 并亲自演算 工作精益求精 使我们受益非浅 现在2001年全国大学生数学建模竞赛已经结束 总结之余 我们衷心期望今后在全国 专家学者以及广大师生的共同关心努力下 我国大学生建模水平更上一层楼 参考文献 1 应荣超等 人下颌下腺淋巴管 血管和腺导管的计算机三维重建技术U 解剖学报 V01 22 NO 4 1991 342 346 2 黄丽丽等 放置宫内节育器后子宫内膜螺旋动脉的三维空间形态 J 中华妇产科杂志 V01 31 NO 9 1996 523 525 3 R Ying CompuLer 3 Dimensional recOnstructlon Of intraglandular lymph vesscls and ductal systems Of the human sub mandibula gland J ActaAnat 144 1992 175 177 4 陈凌钧 骆岩林 等径管道的三维重建 J 高校应用数学学报 V01 13 增刊 1998 86 90 5 吕 伟 有理等距参数曲线及其应用 J 浙江大学学报 自然科学报 增刊 1993 29 37 6 WeiLu Offset rationalparametncplanecurves J ComputerAidedGeometricDesign V01 12 NO 6 1995 601 616 7 Wei Lu Pottmann H Pipe surface with rational spine curve are rational J Comp