当前位置：文档库 > Automatic Centerline Extraction for Virtual Colonoscopy

Automatic Centerline Extraction

for Virtual Colonoscopy

Ming Wan,Zhengrong Liang*,Qi Ke,Lichan Hong,Ingmar Bitter,and Arie Kaufman Abstract—In this paper,we introduce a concise and concrete def-

inition of an accurate colon centerline and provide an efficient au-

tomatic means to extract the centerline and its associated branches

(caused by a forceful touching of colon and small bowel or a deep

fold in twisted colon lumen).We further discuss its applications on

fly-through path planning and endoscopic simulation,as well as its

potential to solve the challenging touching and colon collapse prob-

lems in virtual colonoscopy.Experimental results demonstrated its

centeredness,robustness,and efficiency.

Index Terms—Centerline extraction,distance mapping,

flight-path planning,virtual colonoscopy(VC).

I.I NTRODUCTION

V IRTUAL endoscopy is an integration of medical imaging

and computer graphics technologies,leading to a com-

puter-based alternative to the traditional fiberoptic endoscopy

for examining the interior structures of human organs[17],[19],

[24].It has many advantages compared with the traditional en-

doscopy procedures,such as being noninvasive,cost-effective,

highly accurate,free of risks and side effects(e.g.,perforation

and infection),and easily tolerated by the patient.Therefore,

many prototype systems have been developed for a variety of

clinical applications,including virtual colonoscopy(VC),vir-

tual bronchoscopy,virtual angioscopy,and others.We have been

developing a three-dimensional(3-D)VC system[12],[13]to-

ward a fast and accurate computer-aided screening modality for

early detection of colonic polyps,which are the major cause

(

1)Connectivity .The definition of connectivity is closely re-lated to the data presentation.In virtual endoscopy sys-tems,the acquired CT or magnetic resonance imaging (MRI)dataset is usually presented on a 3-D grid,called a volume .Each grid element is called a voxel ,which can have a cubic or rectangular shape.Two voxels are 6-,18-,or 26-connected if at most one,two,or three of their 3-D coordinates differ by one.If two voxels are 6-,18-,or 26-connected,they are said to be directly connected .Connectivity requires that an extracted centerline is a se-quence of directly connected voxels.Evidently,a 26-con-nected discrete centerline is the smoothest one among the three direct connections and,therefore,is the closest one to the actual continuous centerline in the continuous 3-D space.Given a colon

model

and the centerline

1

that are directly

connected to

voxel

.2)Centricity .The centerline should stay away from the colon wall as much as possible.This requirement guar-antees that the centerline is not only an accurately cen-tered object shape descriptor,but also a safe navigation guide that prevents the navigator from penetrating the colon wall (i.e.,always stays inside the colon lumen)and hugging the corners at sharp turns.

3)Singularity .The centerline should be a single path of one-voxel width,without any manifolds or self-inter-section.Such a sequential single-voxel chain is required for both navigation path planning and quantitative mea-surement in endoscopic simulations.More precisely,given any two directly connected centerline

voxels

should satisfy the

following

condition:

.

4)Detectability .Although a perfectly prepared colon has a single tubular shape without any branches or holes,colon touching with small bowel or by twist as well as colon col-lapse may occur,resulting in a complicated structure with holes and branches in the colon dataset.This problem be-comes even more complicated when one or more colon segments collapse fully,which may separate the colon tube into multiple segments and cut loops into branches if it occurs on looping areas.Therefore,the algorithms for extracting the defined centerline shall tolerate and/or de-tect such looping and branching topology in each colon segment.

1Centerlines mentioned in this paper are,by default,the discrete 26-connected

centerlines.

5)Robustness .In addition to detectability,the algorithms shall be robust,i.e.,they should perform consistently for clinically acquired CT colon datasets,regardless if it is a perfectly prepared tubular colon or a colon which is sep-arated into multiple segments with branches and loops.Furthermore,the extracted centerline should not vary for the location of the start and/or end points,or any 3-D transformation on the colon volume such as translation or rotation.

6)Automation .In addition to robustness,the two end points of the colon shall be determined automatically,resulting in a fully automatic procedure,without any user participation.

7)Efficiency .The algorithms embedded in the fully auto-matic procedure shall be computationally efficient,so that the centerline extraction could be done in seconds on a PC platform (cost effectiveness).

Based on these requirements,we summarize existing centerline-extraction algorithms with a brief discussion on their strength and weakness.Then we propose a novel algo-rithm,which is capable of automatically delivering a colon centerline in a fast and robust manner and satisfies all the above requirements.

A.Brief Review of Existing Algorithms for VC

There has been extensive work on centerline extraction.Most of these methods can be divided into three categories:manual extraction,topological thinning,and distance mapping.

1)Manual Extraction:This method requires the user to manually mark the center of each colon region on each image slice of several hundreds in a dataset.When enough points are selected,a centerline is obtained using a linear or higher order interpolation (e.g.,[10]).This is time consuming and tedious,and the result is by no means more accurate than the results of other methods,for two reasons.First,a center point in a two-dimensional (2-D)slice may not lie along the medial axis in the 3-D space.Second,this does not guarantee that the interpolated line will always stay inside the colon lumen even though all the selected points are inside,as noted in [1],[5],and [23].

2)Topological Thinning:This technique is traditionally as-sumed to provide the most accurate result.It peels off a volu-metric object layer by layer iteratively until there is only one central layer left,which is essentially the skeleton of the object.During the iterative process,“simple points”need to be detected so that the removal of these points does not affect the topology of the object [20].Although the idea is very simple,the repetitive procedure is quite time consuming,especially for identifying the simple points.For example,Hong et al.[12]spent several hours extracting the centerline from a

512

colon region,which are caused by imperfect colon segmenta-tion,are removed before thinning.Third,the colon volume is downsampled to a much smaller size.Their method took about 8min on the original colon dataset and approximately 1min on the downsampled colon volume on an SGI R10000CPU.The removal of cavities may change the object topology,and the downsampling may affect the accuracy of the centerline [5].Paik et al.[18]proposed a more reliable acceleration ap-proach,which avoids the expensive evaluation of simple points by incorporating the shortest path method [9]into a parallel thinning procedure.Their method has three steps.First,it de-termines an initial shortest path along the outmost layer of the object.Second,it performs one step of a parallel unrestricted thinning and computes a new shortest path through the union of all the voxels on the newly exposed layer as well as those voxels in the previous path.Third,it repeats the second step until only one center path remains.This method was further ex-tended to extract branches in the object.It took about 10min to extract the centerline from a patient colon dataset on an SGI O2-R5000CPU.Evidently,this method guarantees the connec-tivity of centerlines and inherits precision from the thinning al-gorithm.However,the manual detection of branch tips needs to be improved,in addition to the computing time.

3)Distance Mapping:This method,first used in robotic path planning [15],is considered to be the fastest one among the three categories.It has two phases.The first phase computes the distance from a user-specified source point to each voxel inside the 3-D object,2which is called a DFS-distance (i.e.,the distance from the starting point)in this paper.Once this dis-tance map is generated,the second phrase extracts the shortest path from any starting voxel to the source point by descending through the gradient of the distance map.The shortest path can be rapidly extracted by a simple backtracing rather than the steepest descent,if Dijkstra’s shortest path technique [9]is used to create the distance map.Those centerline algorithms [1],[2],[5],[7],[10],[22],[23],[27],using distance mapping differ in how they specify the distances between orthogonal,2-D-diagonal,and 3-D-diagonal neighboring voxels.The most

accurate distance measure is the

1–

Euclidean metric [21].Unfortunately,most algorithms use the approximate distance transformation metrics [4]in order to reduce compu-tational expenses or to obtain some specific properties (such as clusters [27])from the generated distance map.The popularly used distance metrics include the

1–

colon dataset on an SGI Power Onyx-R10000CPU.

Bitter et al.[1]proposed a more efficient centerline algorithm using a different strategy,where the precision of the centerline is adjusted during the procedure of shortest path generation rather than afterward.In the distance map,the distance for each in-side voxel is defined as a heuristic combination of the DFS-dis-tance and the DFB-distance,which is called a penalty distance.However,the penalty distance could not completely prevent the shortest path from hugging the corners.Furthermore,this algo-rithm fails to extract a complete colon centerline when holes ap-pear on the colon wall,because it has a higher priority to enter these holes rather than span through the entire colon.For further speedups,they identified the center region of the object and ex-tracted object centerline within this region.Their method took about 5min on the

512

the minimum-cost paths in the penalized-distance field.There-fore,they could always extract the longest path as the center-line.Their second correction was for their branch-extraction al-gorithm[23].To extract a new branch,they computed a new penalty-distance field from all the voxels on the centerline and the branches detected so far,instead of always using the same penalty-distance field from a fixed source voxel[23].A compar-ison between this method and our algorithm will be given later in this paper.

B.Description of New Algorithm

This work aims to overcome the limitations of the previous methods and to develop a framework satisfying the seven re-quirements described above.Our centerline definition and ex-traction are based on the DFB-distance field,which contains the exact Euclidian distance from each voxel inside the colon to the nearest colon boundary.Most of the existing centerline methods do not use such an accurate Euclidian DFB-distance because of the assumption that“an accurate calculation of the Euclidian distance is neither efficient nor algorithmically trivial, especially for large high-resolution3-D volumetric data sets that include complicated objects”[27].However,this assumption is not true.We have implemented an efficient algorithm,proposed by Saito et al.[21],which rapidly calculates the exact Euclidian DFB-distance field.

Before describing our new centerline-extraction algorithm, we will introduce a concise and concrete definition of the center-line based on the DFB-distance field.The centerline is defined as the minimum-cost path spanning over the inversed-DFB-dis-tance field inside the colon.This definition has the following advantages.It is a concise and concrete definition,similar to the traditional description of the centerline given by Blum[3], but more practical for implementation.It is different from all of the previous explicit or implicit centerline definitions in the dis-tance mapping methods that are based on the shortest path in the DFS-distance field or its variations.Solely based on the accurate DFB-distance field,our centerline definition,for the first time, specifies a highly centered centerline for a distance-mapping method,without the tendency to hug the corners.Furthermore, it suggests a theoretically based,efficient and robust algorithm to extract the centerline and its branches from a minimum-cost spanning tree(MST tree)in the DFB-distance field as described below.The algorithm consists of two steps:1)constructing a MST tree in the DFB-distance field;and2)extracting the colon centerline and its branches(if any exist)from the tree.It is a fully automatic approach.

1)Construction of a MST tree:This step can be divided into two stages.First,it converts the CT volume with DFB-dis-tances to a3-D directed weighted graph.Second,it builds up a MST tree from the weighted graph using a modified Dijkstra’s shortest path technique.In the following,we assume that the colon interior is a26-connected region.If two or more colon re-gions occur due to colon collapse,we will build one MST tree for each region(see Section II-D.4for more details).

The conversion from a volumetric dataset to a3-D directed weighted graph is depicted in Fig.1.Each voxel forms a node in the graph.Edges represent the26-neighbor relations between voxels.Each edge has two directions pointing toward its

two Fig.1.Two-dimensional top view of the3-D directed weighted graph.

end points,respectively.Each direction has its own weight as the inverse of the DFB-distance,

say,

to which it points.3To distinguish the DFB-distance from its inverse,we call the latter DFB-cost.Although our directed DFB-based graph looks more complicated than the traditional nondirected graphs used in[1]and[26],its implementation is provably simpler and faster by using our modified Dijkstra tech-nique as described below.

The MST tree of the directed graph is defined as a tree that connects all the inside voxels at the minimum DFB-cost.In order to build up such a MST tree with minimal computations, we propose to modify the standard Dijkstra technique[9],be-cause we only care about the DFB-cost at each individual node when we build the MST tree,so that it does not accumulate the weights of the nodes during the region-growing iterations. Our modified Dijkstra technique consists of the following four steps,where a source

point

,

define

to the source point.

Step2)Put each of the unmarked26

neighbors

, and calculate

its

and

is the number of elements in the current heap.Because we process each object only once, our algorithm is completed

in

is the number of voxels inside the colon.Each inside voxel obtains a pathlink pointing toward its neighboring voxels, through which it reaches the source point with a minimum 3Of course,we could directly use the DFB-distance itself as the weight;then we would have to say“maximum-cost spanning tree.”

4For simplicity,we implicitly assume that each voxel V has all its26 neighbors available at V:neighbors in our flowcharts in this paper.In fact,if a neighbor is not available,we simply ignore it in our algorithm.

Fig.2.Flowchart of constructing an MST tree from a source voxel.A fast heap-sorting technique is adopted so that the heap is sorted in O(log M)time when a new element is inserted,where M is the number of elements in the current heap.As a result,the algorithm is completed in O(N log M)time, where N is the number of voxels inside the colon.

DFB-cost.It also obtains a DFS-distance to record the length of this minimum DFB-cost path toward the source point.Our MST tree is represented by the collection of all the pathlinks. The DFS-distances will help us to find the other end of the cen-terline,and will also contribute to quantitative measurements, as discussed in Section II-D.2.

2)Extraction of Colon Centerline and Branches:The cen-terline-extraction algorithm contains two steps.First,if the user does not specify the end

point

to

is the noncenterline voxel that can reach C through pathlinks.The voxel chain from T

is the voxel directly connected to C along this branch.

rithm,based on the same MST tree and the same centerline-ex-

traction algorithm.

Before we describe our branch extraction algorithm,we give

a formal definition of a pathlinked relationship between two

inside voxels.Given two

voxels

is pathlinked to

voxel

;or

2)

;o r3)m o r e

g e n e r a l l y ,

t h r o u g h o n e o r m o r e v o x e l s.I n t h e f i r s t c a s

e

i s i n d i r e c t l y

p a t h l i n k e d t o

a l o n g t h e p a t h l i n k s.

S t e p2)F o r e a c h c e n t e r l i n e v o x e l

.

S t e p3)F o r e a c h v o x e l

t h r o u g h i t s n e i g h b o

r

i s l a r g e r t h a n a u s e r-s p e c i f i e d o r s y s

d e f a u l t t h r e s h o l

d

i s t h e n u m b e r o f v o x e l s i n s i d e t h e c o l o n

c a p a b l e o f

d

e t e c t i n g a l l b r a n c h e s a t t a c h e d t o t h e c

c l u

d i n g t h o s

e l i n k e d t o t h e s a m e c e n t e r l i n e v o x e l

m a t i o n o f t h e c l o s e s t c e n t e r l i n e v o x e l f o r e a c h i n s u s e d l a t e r f o r e n d o s c o p i c s i m u l a t i o n s(s e e S e c t i o n o u r e x p e r i e n c e,t h e s e f i r s t-l e v e l b r a n c h e s p r o v i d

f o r m a t i o n f o r f l i

g

h t-p a t h p l a n n

i n g a n d e n d o s c o p i c

Fig.4.Flowchart of the branch-detection algorithm along the centerline.A total of24neighbors are checked at each centerline voxel to detect all potential branches connected to the centerline voxel through its noncenterline neighbors.

during the exploration of the tubular colon structure,although it is straightforward to extend the algorithm to detect all the higher level branches by recursively performing such a branch-detec-tion procedure on each detected branch.Similar to the detection of the first-level branches,each object voxel is accessed only once for detection of higher level branches.Assuming that there

are a total of

Second,our method performs global sorting of DFB-distance

values for all the voxels inside the colon.Therefore,it is more

accurate than algorithms that only consider a downsampled

colon[5],[11]or part of the colon[1],[2],[22]for speedups.

Furthermore,we perform a complete sorting rather than a

partial sorting,for example,as used in[1]and[2],where if

the difference of two costs is less than a default threshold,

no sorting is conducted between them for speedups,and the

sorting task is simply treated using an ordinary first-in-first-out

(FIFO)queue.

3)High Performance:The new algorithm does not trade ac-

curacy for speed,or vice versa.Its high performance is ascribed

to its low computational complexity.It builds up the MST tree

in

branches in an

object,the computational complexity of branch detection would

be

is always smaller than

The repulsive force prevents collision on the colon wall and the attractive force guides the navigation.Unfortunately,this camera model suffers from the local minimum problem [15],which is frustrating to the user.For example,when the camera is approaching a narrow region inside the colon,it would always be pushed back due to the rapidly increasing repulsive force near that region.

Since our centerline is based on the DFB-distance field,it enables a more efficient camera-control model that combines the benefits of both the planned and the interactive navigations,and successfully eliminates the local minimum problem [26].Our camera model combines two navigation modes:automatic fly-through and interactive walk-through.In the automatic fly-through mode,our camera flies automatically from the current position (which can be an arbitrary place inside the colon)to-ward the destination (the end point)along the centerline,ac-cording to the pathlinks generated by our centerline algorithm.Whenever necessary,the user can take over the control at any time by clicking the mouse to switch to the interactive walk-through mode.The user can then freely adjust the camera move-ment in the interior colon region for a more detailed inspec-tion.The camera only receives repulsive force when it is too close to the colon wall to avoid colliding with or penetrating the wall.When the user wants to return from the interactive walk-through—for instance,to pass a local-minimum area or just to speed up the exploration—the user simply releases the mouse button and lets the camera fly in the automatic mode.Our technique results in a smooth navigation by implementing a seamless switch between the two modes.The immediate visual feedback during navigation is guaranteed by our fast volume-rendering techniques [25],which have reached more than 10Hz on a low-cost PC platform with a single processor,and more than 20Hz with dual processors,as shown from our most re-cent experimental results [8].

2)Quantitative Measurements for Endoscopic Simula-tions:Another important use of the centerline in our VC system is to provide accurate measurements of abnormality locations.For example,once a polyp is detected during naviga-tion,the physician immediately knows its location and distance from the rectum for surgery registration.It is noted that the DFS-distance at each voxel on the inner colon wall may not be the same distance from that of the voxel to the rectum,as compared to the measurement of optical colonoscopy,which is correlated to the measurement on the centerline.The distance from each voxel to the rectum must be “mapped”onto the centerline.Our centerline and its associated DFB-distance field provide an effective means for this mapping using the closest centerline point (voxel)at each voxel inside the colon.

Fig.6shows an example of how to accurately measure the dis-tance (location)of a polyp from the rectum.Assume

that

’s closest centerline voxel

[

is very close

to

and

reach

has the same distance from source S as P does.We use the distance from C to S rather than the distance from P to S as a conservative measurement to the location of the

polyp.

(a)

(b)

Fig.7.

Touching area detected by branch extraction.

see the polyp.An adequate measure on the distance should

be

Fig.8.Patient dataset with two disjointed segments due to colon collapse.The colon tube collapses at the area marked by the dashed circle at the center of the picture.Two dots inside the circle indicate two new end points from these two separated colon segments.

In the first case,our branch-extraction algorithm could ignore

the branches by enlarging the user-specified threshold

TABLE I

E XPERIMENTAL R ESULTS O

F O UR C ENTERLINE A LGORITHM ON F OUR C OLON D ATASETS

time in Table I includes the time for building the MST tree,but

excludes the time for creating the DFB-distance field.5

The fast speed of our centerline algorithm is mainly ascribed

to its low computational complexity.As we mentioned before,it

builds up the MST tree in

of voxels inside the colon occupies only

about3%–5%of the total volume.Furthermore,due to the long

and narrow shape of the human colon,

is the max-

imum number of voxels that actually appear in the sorting heap.

For example,

[16]Z.Liang,F.Yang,M.Wax,J.Li,J.You,A.Kaufman,L.Hong,H.Li,and

A.Viswambharan,“Inclusion of a priori information in segmentation

of colon lumen for3-D virtual colonoscopy,”in Proc.IEEE Nuclear Science Symp.,vol.2,1997,pp.1423–1427.

[17]W.Lorensen,F.Jolesz,and R.Kikinis,“The exploration of cross-sec-

tional data with a virtual endoscope,”in Interactive Technology and the New Medical Paradigm for Health Care,R.Satava and K.Morgan, Eds.Washington,DC:IOS Press,1995,pp.221–230.

[18] D.Paik,C.Beaulieu,R.Jeffery,G.Rubin,and S.Napel,“Automatic

flight path planning for virtual endoscopy,”Med.Phys.,vol.25,no.5, pp.629–637,1998.

[19]T.Parkins,“Computer lets doctors fly through the virtual colon,”J.Nat.

Cancer Inst.,vol.86,pp.1046–1047,1994.

[20]T.Pavlidis,“A thinning algorithm for discrete binary images,”Comput.

Graph.Image Processing,vol.13,pp.142–157,1980.

[21]T.Saito and J.Toriwaki,“New algorithm for euclidean distance trans-

formation of an N-dimensional digitized picture with applications,”Pat-tern Recognit.,vol.27,no.11,pp.1551–1565,1994.

[22]Y.Samara,M.Fiebrich,A.Dachman,J.Kuniyoshi,K.Doi,and K.Hoff-

mann,“Automatic calculation of the centerline of the human colon on CT images,”Acad.Radiol.,vol.6,pp.352–359,1999.[23]M.Sato,I.Bitter,M.Bender, A.Kaufman,and M.Nakajima,

“TEASAR:Tree-structure extraction algorithm for accurate and robust skeletons,”in Proc.8th Pacific http://www.wendangku.net/doc/0437af1ec281e53a5802ff6f.htmlputer Graphics and Applications,2000,pp.281–289.

[24] D.Vining,D.Gelfand,R.Bechtold,E.Scharling,E.Grishaw,and R.

Shifrin,“Technical feasibility of colon imaging with helical CT and vir-tual reality,”in Proc.Annu.Meeting American Roentgen Society,1994, p.104.

[25]M.Wan,W.Li,A.Kaufman,Z.Liang,D.Chen,and M.Wax,“3-D

virtual colonoscopy with real-time volume rendering,”Proc.SPIE Med.

Imag.,vol.3978,pp.165–170,2000.

[26]M.Wan,F.Dachille,K.Kreeger,http://www.wendangku.net/doc/0437af1ec281e53a5802ff6f.htmlkare,M.Sato,A.Kaufman,

M.Wax,and Z.Liang,“Interactive electronic biopsy for3-D virtual colonoscopy,”Proc.SPIE Med.Imag.,vol.4321,pp.483–488,2001.

[27]Y.Zhou and A.Toga,“Efficient skeletonization of volumetric objects,”

IEEE http://www.wendangku.net/doc/0437af1ec281e53a5802ff6f.htmlput.Graph.,vol.5,pp.196–209,July/Sept.1999.

- 罗田一中2014-2015学年下学期高一地理试题(二)
- 【解析版】辽宁省锦州市2015届九年级上第一次月考数学试卷
- (员工管理)简易版DISC人才性格测试
- 人教版七年级语文上册各课教案汇总
- 二年级下学期数学计划
- 餐饮员工绩效考核标准
- 创建文明校园倡议书
- 预防诈骗
- 英美式英语区别
- PA66美国杜邦70G13L物性表
- 护理教育导论试题第六章
- 生活中的化学知识精品PPT课件
- 第1章11~12信息与微电子技术
- 生管SWOT分析
- LED系统设计方案
- 外贸函电翻译中的常见问题分析
- 信息技术应用成果
- 中国林业绿色就业估算统计体系构建
- 23例内镜下硬化剂联合组织胶治疗食管胃底静脉曲张的护理
- 勇者斗恶龙9中文版炼金合成表完全版
- 弟子规(一) Microsoft PowerPoint 演示文稿
- 设计说明2
- 湖北十堰东风实习报告(参考必备)
- 【2016年12月】四季度_广泽股份(600882)_分析报告
- 模拟电子技术课程设计bs208haf调频调幅两波段收音机组装与调试大学论文
- 航天梦 中国梦
- 浅议农行金融风险的防范和化解