基于骨架的断层间复杂轮廓线的三角片曲面重构.docVIP

基于骨架的断层间复杂轮廓线的三角片曲面重构摘要 基于断层间轮廓线进行曲面重构是科学计算可视化的一个重要内容。本文提出一个基于轮廓线骨架点的三角片曲面重构的算法。首先对散乱骨架点进行拓扑连接，然后分析骨架多边形得到所需的特征骨架点，进而得到断层间轮廓线的相似特征部分，把断层间轮廓线分割为相对应的简单曲线段，最后，重构的曲面由这些分片构造的三角片曲面拼接而成。这样把复杂的断层间轮廓线的曲面重构问题分解为较简单的曲面重构问题。关键词：轮廓线 骨架 曲面重构Skeleton-based Triangular Surface Reconstruction from Complex Contour LinesWang Qiang Ma Lizhuang and Bao Hujun(State Key Laboratory Of CAD&CG, Zhejiang University, Hangzhou, 310027)Abstract It is an important branch of scientific visualization to reconstruct surface from contours cross-sections. An approach was proposed for surface reconstruction from contours based on analysis of skeleton points. We obtained a kind of topology connection of skeletal points, and then skeletal points with specific features are detected. Based on correspondence of such skeletal points, the contour lines are divided into several correspondent segments. Finally, the surface is composed of the pieces reconstruction from these contour segments.Keyword: contour, skeleton, surface reconstruction1. 引言从平行层面的轮廓线重构物体的3-D曲面是科学计算可视化的主要内容之一，具有非常广泛的用途，如医学可视化、生物、地质、无损探伤、地下结构监测等领域9。目前，曲面重构有以下几类方法：a) 三角化曲面方法9；b) 粒子系统方法12；c) 超二次曲面13；d) 隐函数曲面15,14。迄今为止，断层间的曲面重构研究的最多的还是三角片曲面重构。一开始的研究也是这方面的方法研究。由轮廓线构造物体表面的3-D曲面的算法研究自70年代就开始了2,3。Keepei在文章2中提出以重建的三角片构成的表面所包围的体积最大为目标函数，求取最佳逼近。与此相似，Fuchs提出了表面积最小法3。上述的两种方法是全局最优的表面重构方法，计算量太大，数据量大时不适用。为了提高速度可采用局部路径的判定方法，最短对角线法3就是一种常用的方法。Cook在文章5中提出了一个利用轮廓线采样点中心方向角度相近的程度来构造三角片的局部优化方法。这两种局部优化方法在某些复杂情形时会产生畸变。Ganapathy在文献中提出了一种有向图的启发式搜索模型和相关模型方法，该方法是基于轮廓线相关性的一种启发式算法。有两种启发式规则：一是加入的三角片应满足上、下边之差保持最小的要求，二是要求加入的三角片是基于访问过的累加周长。Barequet等在1中提出一种新的方法，他们把轮廓线分为相似部分和不相似部分，对于相似部分，采用最短对角线法等已有的方法，而对于不相似部分，则引入不同的优化目标（如最小面积或使表面积平方+周长最小），并应用动态规划方法加以解决。该方法首次在考虑三角片的连接方式时考虑了两层以上的轮廓线。但是其相似部分的识别是把轮廓线投影到同一平行平面上在依据采样点的最短距离来判别，这种方法对于较为复杂的轮廓线来说是不适合的。本文提出的曲面重构方法也是属于局部优化方法，主要考虑轮廓线的特征部分的对应，比如复杂轮廓线的突出部分之间的对应。2. 对轮廓线骨架的分析医学图像的体数据如CT、MRI数据是由一幅一幅的图像层叠而成，或称为断层扫描图像，是医疗器械对人体某部分的平行层面进行扫描而得到的图像。然而，人体的有些器官的轮廓线较为复杂，直接分析各层之间的轮廓线的对应部分较难。我们注意到，物体图像的骨架能反映物体的形状特征，因此我们可以通过分析骨架的属性来推知轮廓线的属性，而骨架点的数量远远少于轮廓采样点的数量，这给我们的分析带来了极大的便利。要得到图像的骨架点，方法有两类，一是对图像进行细化，逐次去掉物体的边界点，同时必须保证区域的连通性不被破坏，最后保留的点组成物体的骨架，这种方法多采用模板方式来实现，这种方法得到的骨架可以保留物体的拓扑结构，但是计算量往往很大，而且短的分支易被抹去，有时还会产生畸变。二是对图像进行滤波处理得到散乱的骨架点，先对原图像进行距离变换，找出每个象素与最近边界点的距离，将距离相对最大的点抽取出来，作为骨架点，这种方法易于实现，效率较高，但由这种方法得到的骨架点离散分布，不知道它们的的拓扑结构。由于对图像进行细化时有时会产生畸变，对分析轮廓线的形状产生干扰8。本文采用后一种方法，即先求散乱骨架点然后进行拓扑连接进而分析轮廓线的特征的方法。但是要分析骨架所反映的特征，对骨架点进行拓扑连接是有必要的，对于散乱的骨架点的拓扑连接一直是一个较为棘手的问题，至今没有圆满的解决方法8，11。在下面我们提出一个对骨架点进行拓扑连接的方法。图1 几种简单图形的骨架以下有两种求骨架点的方法：2.1 骨架点的获得为了提取骨架点，先将物体从背景中分离出来，转换成二值图像，然后采用距离变换，找出每个象素与最近边界点的距离，将距离相对最大的点抽取出来作为骨架点。a) 利用轮廓线来求骨架记点e到空间点集合P的最短距离为，其中d(e, m)为点e到点m的距离，这里的距离可以是欧氏距离（Euclidean distance）、城市街区距离（city block distance）、chamfer距离或八角距离（octagonal distance）等距离定义，其中chamfer距离和八角距离可以认为是欧氏距离的逼近。如果采用欧氏距离，在下面求骨架点的算法中可以用最短距离平方来代替最短距离以避免开方运算，因为下面算法中只涉及到距离的大小比较。算法：基于轮廓线采样点和物体区域二值图像来求骨架输入：轮廓线采样点集合P，物体区域二值图像f输出：骨架点集合SFor 物体象素f(i, j) doMinDist(i, j) = d(f(i, j), P);For 物体象素f(i, j) doBeginIf MinDist(i, j)是f(i, j)邻域中的极大值 ThenS = S + (i, j)End;图2 人体大脑及其所占区域的轮廓线和骨架点b) 用滤波算子来求骨架另外还可以采用滤波方法来得到散乱骨架点，这种方法可以在一定程度上在三维的体数据中应用，但当断层间距离较大时，这种推广就不合适了。前向滤波：对于所有象素从后向前、从左至右进行滤波：for j = top to bottomfor i = left to rightf(i, j) = 其中为（i, j）的前向邻域，即在（i, j）之前遍历到的象素。为到（i, j）的距离权值，根据情况分别取为1、1.314、1.628。后向滤波：过程与前一次相似，只是方向相反：for j = bottom to topfor i = right to leftf(i, j) = 其中为（i, j）的后向邻域，即在按前向遍历时在（i, j）之后遍历到的象素。2.2 骨架点的拓扑连接散乱骨架点的拓扑连接是一个较为棘手的问题。在中，作者采用以骨架点为中心的元球来构造曲面，这对于想血管类的器官来说是适合的，这样做不需要进行骨架点之间的拓扑连接。本文基于骨架点与轮廓线的关系提出一个将散乱骨架点连成多边形的算法，作为曲面重构的基础。在以下的讨论中我们都假设在抽取轮廓线时，其采样点都依逆时针排列。由于骨架点基本反映轮廓线的形状，因此若将各个轮廓线上的采样点与其最近的骨架点相连，则轮廓线上各采样点依次形成一个个扇形，扇形的中心为骨架点，我们称之为骨架扇形，每个骨架扇形有一个起始轮廓线采样点和一个终止采样点。我们记一个骨架扇形为一个三元组，其中s为骨架点，为起始采样点，为终止点，从到之间的采样点都与s相连。由于骨架的性质，一般来说每个骨架点最多有两个扇形与其相连。这样我们根据多边形上个采样点的走向依次将扇形的中心连起来就得到一个由骨架点组成的多边形。算法：骨架点的拓扑连接输入：轮廓线采样点多边形，骨架点集合输出：骨架多边形Ps1) 把轮廓线上个采样点与最近的骨架点相连；2) 计算出各个骨架扇形；3) 依照轮在轮廓线上的排列顺序（逆时针方向）将各个扇形中心相连，得到骨架多边形。a) 轮廓线及其骨架点b) 骨架扇形c) 拓扑连接后的骨架多边形，其中我们看到在物体左边的伸出部分的骨架多边形退化成连接的线段图3 骨架的拓扑连接，图中轮廓线上有126个采样点，35个骨架点3. 基于骨架的曲面重构对于复杂形状的轮廓线，如果计算相似点或初始点时不考虑整个轮廓线的形状，比如用投影距离最短来找相似点，则往往得到扭曲的曲面。由于轮廓线的骨架多边形刻画了它的主要形状特征，如图2中的伸出部分就有一个骨架点，采用上节所述算法计算出来的骨架多边形在A处退化为一线段（内角为零），我们可以通过分析骨架多边形的性质来辅助识别轮廓线之间的相似部分，特别是那些具有明显特征的部分。由于骨架点远少于轮廓线采样点，因此这样做大大减小了分析难度。算法：两个轮廓线之间的三角化输入：轮廓线、及相应的骨架多边形、输出：三角片集合Ta) 计算骨架多边形的各内角的余弦值，i=1, 2；b) 找到匹配的骨架点。给定阀值，确定其中，i=1, 2；c) 匹配特征骨架点所对应的扇形轮廓采样点；d) 采用最短对角线法（或其它方法，如动态规划）对分段的轮廓线进行三角片曲面重构。对于特征骨架点的匹配，可以采用全局的方法，由于特征骨架点的数量很少，这采用采用全局方法用的时间很少。对于比如狭长形的物体，可采用直线拟合，位于直线两端的特征骨架点即为匹配的骨架点。以上算法在找到了轮廓线上的特征点了，把轮廓线分成了较简单和较短的一段一段，从而减小了三角化的难度。找到的特征点对越多，三角化的难度就越小，最终的曲面也越可被接受。4. 实验结果根据以上提出的算法，我们对人体的耳朵器官的耳廓部分进行重建，耳廓的轮廓线来自对MRI医学图像的分析。(a) 轮廓线1 (b) 轮廓线2(c) 从轮廓线1和轮廓线2重构的三角片曲面图4 两个断层轮廓线间的三角片曲面重构在上图中，对于轮廓线1和轮廓线2的三个对应的突出部分，我们的方法能正确地找到它们对应的骨架点（A，A），（B，B），（C，C）。图5 从断层间轮廓线重建的耳廓在上述实验中，一些用到的数据如下：表1 试验数据轮廓线序号采样点数骨架点数特征骨架点数030821128324218219432261934202265从上表可以看出，复杂轮廓线的匹配问题通过引入骨架点进行辅助从而将有效特征匹配的难度逐步降低，为最后的曲面重构提供正确的轮廓线分割匹配，最后输出的三角曲面还可以作为磨光多边形曲面的输入16，17。5. 结论本文提出了一个从断层间轮廓线进行三角片曲面重构的算法，该算法利用骨架点来找出复杂轮廓线的一些特征点，从而把问题分而治之，实验表明该算法能够找出正确的对应特征点，从而构造出较真实的曲面。对刘新国博士和方向博士提供的帮助表示感谢。参考文献1. Barequet, Gill, Daniel Shapiro, Ayellet Tal, History Consideration in Reconstructing Polyhedral Surface from Parallel Slices, Proceeding of Visualization 96, San Francisco, California, Oct. 27 - Nov. 1, 1996, pp. 149-156.2. Keepei, E., Approximating Complex Surface by Triangulation of Contour Lines, IBM J. R&D, Vol. 19, 1975.3. Fuchs, H., Kedem, Z., et al., Optimal Surface Reconstruction from Plannar Contours, CACM, Vol. 20, 1977.4. Christiansen, H. N., Sederberg, T. W., Construction of Complex Contours Line Definition into Polygonal Element Mosaics, Computer Graphics, 12(3), 1978.5. Cook, L. T., Dwyer, S., A Three Dimensional Display System for Diagnostic Imaging Applications, IEEE CG&A, 3(4), 1983.6. Shinagawa, Y., Kunii, T. L., Constructing a Reeb Graph Automatically from Cross Section, IEEE CG&A, Vol. 11, 1991.7. Ganapathy, S., Dennely, T. G., A New General Triangulation Method for Planar Contours, Computer Graphics, 16(3), 1982.8. Guo H. H., Study of Basic Algorithms for Medical Visualization, Ph.D. thesis, Zhejiang University, 1997.9. Shi J. Y., Cai W. L., Visualization in Scientific Computing: Algorithm and System, Science Publishing House, 1996.10. Ferley, E., Gascuel, M. P., Attali, D., Skeletal reconstruction of branching shapes, In Implicit Surface96, 2nd International Workshop on Implicit Surface.11. Masotani, Y., Masamune, K., et al., Region-Growing Based Feature Extraction Algorithm for Tree-Like Objects, Proceeding of Visualization in Biomedical Computing96, 1996, pp. 161-171.12. Jaillet, F., Shariat, B., and Vandorpe, D., Deformable Volume Object Modeling with a Particle-based System for Medical Applications, In N. M. Thalmann and V. Skala, edi