A.VilanovaBartrol 1
,R.Wegenkittl 2
,A.Konig 1
,E.Groller 1
,andE.Sorantin 3
1
InstituteofComputerGraphicsandAlgorithms
ViennaUniversityofTechnology
2
TianiMedgraph
3
SectionofDigitalInformationandImageProcessing,
DepartmentofRadiology,UniversityHospitalGraz
Austria
Abstract. We present a new method to visualize virtual endoscopic
views. We propose to attenthe organ by the directprojectionof the
surfaceontoasetofcylinders.Twosamplingstrategiesarepresentedand
theintroduceddistortionsarestudied.Anon-photorealistictechniqueis
presentedtoenhancetheperceptionofthe images.Finally,anapproxi-
matebutreal-timeendoscopicy-throughispossible byusingthedata
obtainedbytheprojectiontechnique.
1 Introduction
Virtual endoscopy deals with the inspection of hollow organs and anatomical
cavitiesusing medical imaging(e.g. CTand MRI) and computervisualization
techniques.Virtualendoscopyhasthepotentialofbecomingasubstituteofreal
endoscopy for some diagnostic procedures. A real endoscopy is invasive and,
furthermore,involvesacertaindegreeofriskforthepatient.
Most of the virtual endoscopy techniques presented in the last years [1{3]
concentrate onsimulating the view of areal endoscope. This is the view that
the endoscopists are used to. It can be useful for certain applications, like in
anintraoperativescenario,butitis notnecessarilythebest wayto inspectthe
inner surfaceof an organ.Actually, areal endoscopeand organare subject to
physicallimitationsthatavirtualendoscopeandorgandonothave.Thispaper
considers virtual colonoscopy, which focuses on the examination of the colon.
Physicians are mainly interested in visualizing the inner surface of the colon
whichiswherepolypscan bedetectedwithendoscopy.Itisimportantthatthe
physiciancanestimate thesize of polyps, sincelargepolypsare morelikely to
developintomalignities.Theusualendoscopicviewvisualizesjustasmallpartof
thesurface.Furthermore,itisdiÆculttodetectpolypsthataresituatedbehind
thefoldsofthecolon.An eÆcientwaytoinspecttheinnersurfacewouldbeto
openandattenthecolonandthenexamineitsinternalsurface.Unfortunately,
thiscannotbedonein realityifwewantthatthepatientsurvives.Ontheother
hand,thereisnopatientdamageifthisdissectionoftheorgancanbeachieved
virtuallywiththemedicaldataobtainedbyCTorMRI(i.e.thevirtualorgan).
Someauthorsproposedatechniquetostraightenandunravelanorganvirtu-
each frame,a cross-sectionorthogonalto the path tangent iscalculated. Then
thecentralpathisstraightenedandthecross-sectionsarepiledtoformastack.
As alast step thestraightenedcolon is attened obtainingavolume model of
the attened colon. Themodel is displayedafterwards using standardvolume
rendering techniques.This method allowsto visualize the complete surface at
once.Oneofthemainproblemsofthistechniqueappearsinhighcurvatureareas
ofthecentralpath,i.e.atpathlocationswheretheradiusofcurvatureisbigger
thanthe organdiameter.Insuch casesorthogonal cross-sectionsintersecteach
other orarefar apartinsomeother regions(seegure1).As aconsequence,a
polypcan appear twice in the attened model orit canbe missed completely.
Wangetal.inalaterwork[6]trytoovercomethisproblem.Theyuseelectrical
eld lines generated by alocally charged path to governcurvedcross-sections
insteadofthe planarsections.Thecross-sectionstendto divergeavoidingcon-
icts, but the technique cannot ensure that they will notintersect. Hakeret
cross-sections
Central path
missed polyp
double polyp
Fig.1.Illustration ofthe possibleundersamplinganddoublecountingof polypsdue
to intersections of the cross-sections inhigh curvatureareas. The dashcross-section
lineproducesadoublecountingofthepolyp.
al.[7]useconformalmappingwhichisanglepreservingtoprojectthecolonsur-
facecoloredwiththegaussiancurvaturetoaplane.Oneofthemainproblemsof
thismethodisthat ahighly accuratesegmentationisnecessaryto ensuregood
resultsincasetheyareused fordiagnosis.
Paiketal.[8]proposeotherkindsofcameraprojectionsforvirtualendoscopy.
With anormalendoscopicviewjust 8%of thesolidangleofthecameraisseen
in each frame. Paiket al. projectthewhole solidangle of the cameraby map
projectiontechniquesused tomap theworldglobein charts.Theysuggestthe
use ofthe Mercatorprojectionto map thesolid angleto the nal image. This
techniquesamplesthesolidangleofthecamera,thenthesolidangleismapped
ontoacylinderwhichismappednallytotheimage.
All of these methods introducesome kind of deformationsince it is math-
gaussiancurvature.
Insection2,wepropose amethod to atten thecolonusing anewcamera
projectiontechnique. Section 3 presents dierent sampling options that cause
dierent deformationproblems. Aminimization ofthe rotationforthecamera
movement is described in section 4. Section 5 describes a non-photorealistic
techniquethatenhancestheperceptionoftheimage.Thenitispresentedhowan
approximatebutfastendoscopicviewcanbegeneratedwiththedatacalculated
fortheprojectionmethod.Finally,someresultsandstudieswithcolondataare
presented.
2 Method Overview
The methods proposed by Wang et al. [6] generate a at model of the colon
that lateronwill becarefullyinspected bythephysician.Ourmethod willnot
generateaatmodelofthewholecolon,but allowstoinspectlocally attened
regionssuch thatdoublecountingofpolypsdoesnotoccur.
Thepresentedmethodinvolvesmovingacameraalongthecentralpathofthe
colon. Thecentral pathcanbecalculatedusingoneofthe commontechniques
usedtoskeletonizeanobject.Weusedathinningalgorithmwhichensurestopo-
logicalpreservationoftheobject(seeVilanovaetal. [3]).Thepathissmoothed
andnallyapproximatedbyaB-splinecurve.
C(h, ) a
a h
I(u,v)
u v
Fig.2.Illustrationoftheprojectionprocedure.Aregionofthesurfaceisprojectedto
thecylinderC(h;).ThenthecylinderismappedtotheimageI(u;v)
Foreachcamerapositionasmallcylindertangenttothepathisdened.The
middlepointofthecylinderaxiscorrespondstothecameraposition.Thelength
ofthecylinderaxishasaconstantvalueforallcamerapositions.Thelengthis
denedbyinspectingthecamerapath,andcalculatingthedistancefollowingthe
tangentbetweenthepathposition andthecolon surface.Thelengthisdened
by thedistance that in any cameraposition ensuresthat theaxiswill notget
outofthecolon.
Raysstartingatthecylinderaxisandbeingorthogonaltothecylindersurface
are traced (seegure 2). For each ray, direct volume renderingcompositing is
toa2Dimage.Thisisdonebysimplyunfoldingthecylinder.
Theresultisavideowhereeachframeshowstheprojectionof asmallpart
oftheinnersurfaceoftheorganontothecylinder.Ifthecameraismovedslowly
enoughthecoherencebetweenframeswillbehighandtheobserverwillbeable
to followthemovementofthesurface.
Inhigh curvatureareasalsotheproblem which correspondstotheintersec-
tion ofcross-sections (seegure 1) appears. Inthe presentedmethod, possible
double sampling of polyps emergesjust between frames. However,it doesnot
cause a double counting of polyps since the human brain is able to track the
polypmovementduetothecoherencebetweenframes.Movingalongthecentral
pathin suchahigh curvaturearea,apolyp mightmoveupanddown (due to
doublesampling )but isclearlyidentiedasasingleobject.
a
r 2
l 1
a
l l 2 l l
r 1 r 1
r 2
r 3
a) b)
Fig.3.a)Constantanglesampling:itisshownthatdierentsurfacelengthsarerep-
resentedbythe samelengthinthecylinder.b)Perimetersampling:same lengthbut
dierentangle.
3 Projection onto a Cylinder
Theproposedprojectionis illustratedin gure2.Acylinder C(h;) isdened
foreachcameraposition.Thiscylinderiscoloredbytracingraysorthogonalto
the cylinder surface(i.e. projecting aregion of the surfaceonto the cylinder).
Then the cylinder is mapped to the nal image I(u;v) by a simple mapping
function f :(h;)!(u;v).
Thesamplingdistance(i.e.thedistancebetweentwoconsecutiverays)inthe
h-direction is constant,and it must be at most half of the size of avoxel(see
gure2).InthiswaytheNyquistfrequencyintheh-directionispreserved.
Foreachh-valuetheraysaretracedin radialdirections withrespect tothe
cylinderaxis.Theraysaredivergingfrom eachother,sothevolumedataisnot
thecylinderdependingonthesamplingofangle:constantanglesamplingand
perimetersampling.
3.1 ConstantAngle Sampling
Constant angle sampling means that the angle betweenconsecutive rays in
direction is constantfor rays with thesame h-value. Figure 3a illustrates how
thissamplingisdone.Usingthismethod,thecylinderissampleduniformlybut
thesurfaceitselfisnotuniformlysampled.
Theadvantageofthismethodisthattherelationbetweenbothdirectionsis
locallypreserved.Thereforetheanglesarelocallypreserved.Animagegenerated
bythismethodcan beseeningure4a.
On the other hand, the area of the projected region is not preserved (see
gure 3a). Therefore, the dimension of the projected polyps depends on the
proximityofthecylinderaxisandthediameterofthecavity.Consequently,the
physicianscannottrustthesizesofthepolyps.
Polyps can be missed with constant sampling (see gure 3a), if the angle
incrementistoolarge.Ifthesamplingdistance istoosmalltheraysaretraced
whereitwouldnotbenecessary.ThismakesthemethodineÆcient.
3.2 PerimeterSampling
Inthissectionweproposeasamplingstrategyin whichtheraysarecalculated
sothat the surfacelengththat theyrepresentis constant. A constantsample
a) b)
Fig.4.a)Resultingimageoftheprojectiontechniqueusingconstantanglesampling.
b) Same camera position as a) butwith a perimeter sampling.The bottom images
showagridwhichwas generatedbyxingaconstantanglevalue.
lengthlisdened.lmustbeatmosthalfthesizeofavoxeltokeeptheNyquist
frequency and therefore notto miss any important feature. l should have the
samevalueasthesamplingdistance in theh-directionto preservetheratio, or
planedenedbyacertainvalueofh.Theanglebetweenthecurrentrayandthe
nextoneiscomputedsuchthatthelengthofthesurfacesamplethatthecurrent
rayrepresentsislinthe-direction(seegure3b).Therstrayistracedalong
anarbitraryangle
0 .
0
mustbethesameforeachvalueofh.risdenedasthe
distance fromthecylinder axisto thesurfacepointhitby theray. Thesurface
sample length in the -directionthat aray representsis approximatedby the
arc withradius r. Therefore,the valueofthe angleincrementfor thenextray
isestimatedas l
r
radians.
This projection method projects the organ surface to a generalized cylin-
derwhose radii arenotconstantwithin thecylinder. Inthis casethemapping
function f mapsuniformly thecontoursand alsothesurfaceof thegeneralized
cylinder. Moving alongthe central path, contours of varying length are repre-
sentedbyvaryingnumbersofrays.Inthemappingtotheimageplanethisresults
inthefactthatinthev-direction(horizontalscanlines)typicallyonlypartofthe
pixelsarecoveredbyanunfoldedcontour.Therefore,thegeneralizedcylinderis
notmappedtothecompletedomainoftheimage(seegure4b).Thefunctionf
mapseachsampledraytoapixelin theimage(i.e.eachpixelcorrespondstoan
areaofllofthesurface).Theprojectedpointsthatcorrespondtotheraysat
angle
0
arepositionedonaverticallineinthecenterof theimage. Thenfrom
left torighttherayvaluesare mapped totheimage untiltheperimeterlength
isreached.
This projection has thearea preservation property. Sothe relative sizes of
surface elements are preserved in the image plane and do not depend on the
proximityofthecylinderaxisto thesurface.Ontheotherhand,adistortionis
introducedwithrespecttothehand-direction,sotheanglesarenotpreserved
anymore.Attheverticalcenterlineoftheimagethereis nodistortion, butthe
distortionincreasesprogressivelywhenwemovetotheleftandright.Figure4b
showsanimagegeneratedwithperimetersamplingwithasuperposedgridwhich
wouldcorrespondtoaregulargridinaconstantanglesamplingofthecylinder.
In this way, it canbe observedhow the horizontal lines are varying in extent
accordingto thevarying lengthofthecorrespondingcontour.
4 Minimally Rotating Frame
Intheprevioussection,atechniquehasbeenpresentedtoprojectthesurfaceof
theorganontothecylinderandthentotheimage.
Ateachpositionofthecamerainthecentralpathanorthogonalcoordinate
systemistakenwhichspeciesthelocationandorientationofthecylinder.One
coordinate axis is given by the tangent vector of the central path. The other
axes are in the plane orthogonal to the central path at the camera position.
TakingtheFrenetframeisnotagoodchoiceforthiscoordinatesystem.Firstly,
theFrenetframeisnotdenedin linearportionsof thecentralpath.Secondly,
bymovingalongthepaththetwovectorsorthogonaltothetangentvectorare
rotatingmorethannecessary,thusreducingcoherencebetweenadjacentframes.
Thecoordinateframeisobtainedbysolvingthefollowingdierentialequation:
z(s)= c
0
(s)
kc 0
(s)k
x 0
(s)= (c 00
(s)x(s)) c
0
(s)
kc 0
(s)k
(1)
y 0
(s)= (c 00
(s)y(s)) c
0
(s)
kc 0
(s)k
where c(s) represents the parametric central path and (x(s);y(s);z(s)) is
thecoordinateframewearelookingfor.Aninitial orthogonalframe(x
0
;y
0
;z
0 )
isdened.Thenthedierentialequationsaresolvedusingfourth orderRunge-
Kuttamethod.Theoretically,equations1produceorthogonalcoordinateframes.
To avoid accumulation of numerical errors (i.e. orthogonality is not ensured
anymore),wetakethefollowingapproach:z(s)andx 0
(s)arecalculatedaccording
totheaboveformulas.Theny(s)istakenasthecross-productofz(s)andx(s)
(y(s)=z(s)x(s)).Finallywealsocorrectx(s)bytakingitasthecross-product
ofy(s)andz(s)(x(s)=y(s)z(s))
5 Level Lines Enhancement
Usingthedistanceofthehitsurfacepointtothecylinderaxisr,wecangenerate
adepthimage(seegure6a).Thedepthimagetogetherwiththeshadedimage
represent a high eld, similar to a landscape in topography. A good way to
visualize landscapes in topographical maps is showing level lines, where each
line correspond to a level of depth. The level lines improve the perception of
depthand surfacechangesofthemap.
Thelevellines aregenerated from thedepth image. Firstly, thegradientof
the depth image is calculated using arst derivative of the Gauss lter. The
levellinesaredrawnbasedonthetechniquedescribedbySaitoetal.[10].
Inorder to improvetheperception, ahue shiftis applied to the level lines
color.Thecolorsofthelinesarecoded dependingonthelevelofdepth(seeg-
ure6c).Hueshifthastheadvantagethatitdoesnotinterferewiththehighlights
and darkareasof ashaded image. Technicalillustration artistscommonly use
thetemperatureofcolorsintheirdrawing.Thetemperatureofacolorisdened
as warm (red,orangeand yellow)and cool(blue, violet and green).The tem-
peraturealsogivesdepthcueinformationsincetheperceptionofthecoolcolors
recedeswhereastheperceptionofthewarmcolorsadvances.Thehueshifthas
beenchosenyellow-bluesincethesecolorshavealargeshiftrange,andred-green
isundesirableduetocolorblindness.Yellowcorrespondstocloserlevellinesand
blue tolevellinesfaraway.
Oncethelevellineshavebeenobtainedtheycanbecombinedwiththeorig-
inalshadedimage (seegure6d).Thecoloroftheshadedimageshould notbe
thecylinderaxis.
6 Endoscopic View Generation
Onceapolyphasbeendetectedinthevideooftheattenedcolon,thephysician
would be interested in seeing its location with an endoscopic view. Using the
already calculatedshaded images and depth images for each frame, afast y-
throughcanbegenerated eÆciently.
Togeneratetheinteractivenavigation,thehorizontalcenterlinesofthedepth
images ofthemovieoftheattened colon areused. Knowingthecameraloca-
tionforeachframe, thecenter linescanbebackprojectedtothe3D space(see
gure 5a). A polygonal surface can be easily generated using triangle stripes.
Each stripe corresponds to the triangles generated between onecenter line of
thedepthimageandthecenterlineofthenextframe.Weobtainafastrender-
ingsinceweusestripesandwerenderjustthesurfaceintheneighborhoodofthe
camera(seegure5).Thiscanbeachievedeasilysincethestripesaresortedby
pathposition.With thismethod weachieveframeratesaround30f.p.s. witha
PentiumIIat400MHzwithcommonOpenGLgraphicshardwareacceleration.
Each triangle can be coloredby OpenGL with acorrect lighting. Another
optionis to assignto eachtriangle vertex itscolorvalue calculatedin thecor-
responding shaded image of the video of the attened colon. The last option
producesincorrectlightingbutithasabettermatchingwiththeattenedcolon
images.
Obviously the resulting images are approximations and some artifacts ap-
pear due to thecross-section problem (see gure1). However,it gives agood
impressionof thestructureandit canbeusedbythephysicianto positionthe
cameratotheareathat theywantto visualizewithabetterqualitybut slower
rendering.
7 Results
The images presented in this paper correspond to a CT data set of a cadav-
eric colon with a resolution of 381x120x632. The colon is 50 cm long and 13
articial polyps were physically created in the cadaveric colon. These polyps
had a size between3.5x2.5 mm and 11.8x9.0 mm. Figure 6e shows anoutside
view of the segmented cadaveric colon and its central path together with the
camera. The cameraposition correspondsto the image in gure 6g. Figure 6f
is an endoscopic view moving the camera a bit backwards to show the same
regionas in gure6g. Itcan beobservedthatthe shapeof thepolyps ismuch
moreclearin theattenedimagesthanintheendoscopicviewgure6f(please
referto http//www.cg.tuwien.ac.at/research/vis/vismed/ColonFlattening/)for
thevideos).Thephysicianswhocollaboratein thisprojectcouldeasilyidentify
thepolypsinthecolonattened images.Figures4, 6b, 6d, 6g, and 6hshow
someofthepolyps.
Wealsotestedthismethodwitha256x256x311CTdatasetofacolon.Fig-
Fig.5.a)Endoscopicviewbackprojecting thelinesusingthedepthinformation and
thecameraframe.b)Endoscopicviewusingthebackprojectionofthegeneratedshaded
stripes.
generatedfromthesamecamerapositionbuttheprojectionwasdonewithcon-
stant samplingand perimetersampling respectively.Both sampling techniques
canbeusefultothephysician.Perimetersamplingpreservestheareaandallows
thephysiciantoevaluatethesizeofthepolyps.Whileconstantanglesampling
preservestheanglesandallowsabetterevaluationoftheshape.
8 Conclusions and Future Work
Wepresentedanewtechniquefor virtualcolonoscopywhichdoesnotsimulate
the usual endoscopic view. The images are generated with a projection tech-
nique that allows thephysicianto visualize most of the surface,and to easily
recognizepolypsthat inanendoscopicviewwouldbehiddenbyfoldsorwould
behardtolocalize.Thepresentedmethodavoidsdoublecountingofpolyps.We
presentedtwosamplingstrategiesthatrespectivelypreservetheangleorareaof
theprojectedsurfaceelements.Wemaximizedthecoherencebetweenframesby
minimizing the camera rotation. Theimages are also enhancedby calculating
levellineswhichrepresent thedepth. Finallywepresentedatechniqueto gen-
erateareal-time endoscopic viewnavigationbyusing the dataof the videoof
theattenedcolon.
Asfutureworkitisplannedthatthedoctorisabletogobacktotheoriginal
dataoncethepolyphasbeendetected.Thiscaneasilybedoneusingthecamera
positionofeachframeofthevideooftheattenedcolon.
Itisalsoimportantthatthecylinderaxesdonotgetoutsidetheorgan.The
cylinderheightcouldbeoptimizedforeachdatasetandevenadaptivelydened
dependingonthecameraposition.Thecameramovementhastobespeciedin
becauseunnecessaryimagesarecalculated.
Anothersubjectof future workis to extensivelytestthemethodwith data
of real patientswith pathologies,to observe how the algorithm performs. The
method mightalsobeappliedtootherorgans.
Acknowledgements
Theworkpresentedin thispublicationhasbeenfunded bytheV is
M ed
project.
V is
M ed
issupportedbyTianiMedgraph,Vienna(http://www.tiani.com),and
theForschungsforderungsfonds f urdie gewerbliche Wirtschaft,Austria.
Seehttp://www.vismed.at/forfurther informationonthisproject.
WethanktheDepartmentofRadiologyin Grazfortheircollaborationand
for providing the dataused in this paper. Wethank JirHladuvka for his col-
laborationconcerningimageprocessingtechniques.
References
1. L.Hong,S.Muraki,A.Kaufman,D.Bartz,andT.He.Virtualvoyage:Interactive
navigationinthehumancolon.InSIGGRAPH97ConferenceProceedings,Annual
Conferenceseries,pages27{34.ACMSIGGRAPH,AddisonWesley,August1997.
2. M. Wan,Q.Tang,A.Kaufman,Z.Liang,andM.Wax. Volumerenderingbased
interactivenavigationwithinthehumancolon. InIEEE Visualization'99,pages
397{400.IEEE,nov1999.
3. A.Vilanova,A.Konig,andE.Groller.VirEn:Avirtualendoscopysystem.Machine
GRAPHICS&VISION,8(3):469{487, 1999.
4. G. Wang and M.W. Vannier. GI tract unraveling by spiralCT. InProceedings
SPIE.,volume2434, pages307{315,1995.
5. E. Sorantin,E. Balogh,K.Palagy,G.Werkgartner,E. Spuller, andS.Loncaric.
MEDICAL RADIOLOGY - Diagnostic Imaging, chapter "Technique of Virtual
DissectionoftheColonbasedonSpiralCTdata". SpringerVerlagPress, 2001.
6. G. Wang, S.B. Dave, B.P.Brown, Z. Zhang, E.G. McFarland, J.W.Haller, and
M.W. Vannier. Colon unraveling based onelectrical eld: Recent progress and
furtherwork. InProceedingsSPIE,volume3660,pages125{132,May1999.
7. S. Haker, S.Angenent, Allen Tannenbaum, and R. Kikinis. Nondistorting at-
teningmapsandthe3dvisualizationofcolonCTimages. IEEE Transactionson
BiomedicalEngineering,19(7):665{671,July2000.
8. D.S.Paik,C.F.Beaulieu,R.B.Jerey,Jr.C.A.Karadi,andS.Napel.Visualization
modesforCTcolonographyusingcylindricalandplanarmapprojections. Journal
of ComputerTomography,24(2):179{188,2000.
9. F.Klok.Twomovingcoordinateframesforsweepingalonga3Dtrajectory. Com-
puter AidedGeometryDesign, 3:217{229,1986.
10. TakafumiSaitoandTokiichiroTakahashi.Comprehensiblerenderingof3-Dshapes.
InForestBaskett,editor,SIGGRAPH'90ConferenceProceedings,AnnualConfer-
enceSeries,pages197{206,August1990.
c) d)
e) f)
g) h)
i) j)
Fig.6.CadavericcolonCTdataset381x120x632.Forthesamecameraposition
andusingconstantanglesampling:a)depthimageb)shadedimagec)levellineswith
hueshift colorcodedd)combinationofthe levellinesand shadedimage.e)Outside
view and camera position for g). f) Endoscopy view movingthe camerain e)a bit
backwards.g)Constantanglesamplingshowing2polypswithlevellinesenhancement.
h)Constant angle samplingfrom anothercamerapositionsshowing 2polyps.Colon
CTdataset256x256x311:i)Constantanglesampling.j)Thesamecameraposition
