A Neural Network Approach to Real-Time Discrete Tomography

K.J.Batenburg1,2andW.A.Kosters1

1

LeidenUniversity,Leiden,TheNetherlands

kosters@liacs.nl

2

CWI,Amsterdam,TheNetherlands

K.J.Batenburg@cwi.nl

Abstract.Tomographydealswiththereconstructionofthedensitydis-tributioninsideanunknownobjectfromitsprojectionsinseveraldirec-tions.InDiscretetomographyonefocusesonthereconstructionofobjectshavingasmall,discretesetofdensityvalues.Usingthispriorknowledgeinthereconstructionalgorithmmayvastlyreducethenumberofprojec-tionsthatisrequiredtoobtainhighqualityreconstructions.

Recentlythefirstgenerationofreal-timetomographicscannershasappeared,capableofacquiringseveralimagespersecond.Discreteto-mographyiswellsuitedforreal-timeoperation,asonlyfewprojectionsarerequired,reducingscanningtime.However,forefficientreal-timeop-erationanextremelyfastreconstructionalgorithmisalsorequired.

Inthispaperwepresentanewreconstructionmethod,whichisbasedonafeed-forwardneuralnetwork.Thenetworkcancomputereconstruc-tionsextremelyfast,makingitsuitableforreal-timetomography.Ourexperimentalresultsdemonstratethattheapproachachievesgoodre-constructionquality.

1Introduction

Tomographydealswiththereconstructionofthedensitydistributioninsideanunknownobjectfromitsprojectionsinseveraldirections[8].Figure1showsthebasicprinciple.Inthispaperwelookattransmissiontomography,wheretheprojectionsareobtainedbysendingabeam(e.g.,X-rays,neu-trons,etc.)throughtheobjectandmeasuringtheattenuatedbeamthathaspassedthroughtheob-ject.Tomographyisusedextensivelyinmedicalimaging,industrialimagingand,morerecently,in

Fig.1.Basicprincipleof

materialsscienceandbiology.Typically,alarge

tomography,2projections

numberofprojectionsisrequired(morethan100)toobtaingoodreconstructionquality.

Whenitisknowninadvancethatthescannedobjectconsistsofonlyafewdifferentmaterials,itmaybepossibletovastlyreducethenumberofrequired

U.Eckardtetal.(Eds.):IWCIA2006,LNCS4040,pp.389–403,2006.cSpringer-VerlagBerlinHeidelberg2006󰀁

390K.J.BatenburgandW.A.Kosters

projectionsbyusingthispriorknowledgeinthereconstructionalgorithm.Dis-cretetomographyfocusesonthetomographicreconstructionofobjectsforwhichthesetofpixelvaluesinthereconstructedimageisdiscreteandsmall.Inpar-ticular,thereconstructionofbinaryimages(i.e.,black-and-whiteimages)hasreceivedconsiderableattention[6].

Mosttomographicscannersacquirestaticimages,i.e.,asingleimage,either2Dor3D,oftheobjectisreconstructedfromtheprojectiondata.Thereforeitisnotpossibletodoimagingofdynamicprocesses,wherethescannedob-jectchangessignificantlyinashortperiodoftime.Recently,real-timemedicaltomographicscannershaveemerged[9],whicharecapableofacquiringseveralimagespersecond.Besidesmedicalimaging,real-timetomographycouldproveveryusefulinindustrialimaging.

Discretetomographyiswellsuitedforreal-timeimaging,sincethesmallnum-berofrequiredprojectionsresultsinasubstantialreductionofthescanningtime.However,tocomputealongseriesofreconstructionsinreasonabletime,averyfastreconstructionalgorithmisrequired.Severalauthorshaveproposedalgo-rithmsfordiscretetomography,usuallyforthereconstructionofbinaryimages.Allthesealgorithmsrequireatleastseveraldozensofsecondstoreconstructasingle2D256×256image[1,2,12,13].

Inthispaperwepresentanewreconstructionmethod,whichisbasedonafeed-forwardneuralnetwork.Theneuralnetworkisfirsttrainedonasetofrepresentativeimages,whichmaytakeasubstantialamountoftime.Afterthetrainingphase,thenetworkcanbeusedtocomputeareconstructionveryfast.WhenimplementedonaFieldProgrammableGateArray(FPGA),apieceofcomputerhardware,frameratesofseveralhundredspersecondarerealistic.Wefocusonthereconstructionofbinaryimagesfromparallelprojections.Additionalpriorknowledgeotherthanthebinaryconstraintthatispresentinthetrainingset,islearnedbytheneuralnetworkduringthetrainingphase,soitdoesnothavetobemodelledexplicitly.Besidesreal-timetomography,ourapproachcanalsobeusedtocomputeagoodstartsolutionformoreaccurate,time-consumingreconstructionalgorithms.

Neuralnetworkreconstructionmethodsforothertypesoftomographicrecon-structionhavebeenconsideredintheliterature,e.g.,[10,11].Neuralnetworksarenotwellsuitedforgeneraltransmissiontomographyfrommanyprojections,asthenumberofvariablesinthereconstructionproblemisextremelylarge.Besidesthat,itisverydifficulttooutperformotheravailableapproaches.Indiscretetomographytheamountofprojectiondataismuchsmaller,makingthereconstructionproblemunderdetermined.Neuralnetworksarewellknownfortheirabilitytolearnadditionalpriorknowledge,whichmakesthemsuitablefordiscretetomography.

Section2containsashortdescriptionofthetomographicreconstructionprob-lem.InSection3wefirstproposeabasicneuralnetworkapproachanddiscussitsabilitiesandlimitations.Subsequentlywerefinetheapproach,obtainingaso-calledsingle-pixelneuralnetworkarchitecturethatiscapableofcomputingreal-timereconstructionsoflargeimages.InSection4weprovideexperimental

ANeuralNetworkApproachtoReal-TimeDiscreteTomography391

resultsoftheneuralnetworkapproachandabriefcomparisonwithacontinuoustomographyalgorithm.Section5concludes.

2ReconstructionProblem

Figure2showsthemainsettingofthebinarytomographyproblem.Weassumethattheobjectofinterestiscontainedinthedisc

A={(x,y)∈R2:x2+y2≤R2}

withradiusR.Wecallthisdisctheimagingarea.ForthesakeofconvenienceweassumethatRisapositiveinteger.

θ

O

(R,0)Fig.2.BasicsettingforthetomographyproblemindiscA;theanglebetweentheparallelbeamandthey-axisisdenotedbyθ

Theunknownbinaryimagethatwewouldliketoreconstructisconsideredasamappingf:R2→{0,1},where0isblackand1iswhite.Weassumethatthesupportoff,i.e.,theset{(x,y)∈R2:f(x,y)=1},isameasurablesetthatiscontainedinA.DefinethefunctionTθ:R2→Rasfollows:

Tθ(x,y)=xcosθ+ysinθ.

WecallTθ(x,y)thepointprojectionof(x,y)forangleθ.Projectionsaremea-suredalonglinesLθ,toftheform

Lθ,t={(x,y)∈R2:Tθ(x,y)=t}.

TheRadontransformPfoffisdefined(cf.[5],wherealsoRadon’soriginalpaperisreproduced)as

󰀺

f(x,y)dsforθ∈[0,2π),t∈R.Pf(θ,t)=

Lθ,t

392K.J.BatenburgandW.A.Kosters

Wecannowformulatethemainreconstructionproblem,wheretheparameterndeterminesthenumberofangles:

Problem1.LetD={θ1,θ2,...,θn}beagivensetofprojectionangleswith0≤θ1<θ2<...<θn<π,andletφ1,φ2,...,φnbegivenfunctions(themeasuredprojections)fromRtoR.Constructafunctionf:R2→{0,1}suchthatPf(θi,·)=φi(·)fori=1,2,...,n.

Whenthemeasuredprojectionsareobtainedthroughphysicalmeasurements,Problem1usuallydoesnothaveanexactsolution.Evenifthereconstructionproblemhasanexactsolutiontheoretically,weneedtoapproximateitssolutionbyrepresentingitonapixelgrid.

Inpractice,thefunctionPf(θ,·)isusuallynotmeasuredinsinglepointst.Instead,thetotalprojectioninastrip,coveringasmallt-interval(t󰁀,tr),ismeasuredas󰀺

tr

Sθ,f(t󰁀,tr)=

t=t󰁀

Pf(θ,t)dt.

Typically,thevalueSθ,f(t󰁀,tr)ismeasuredforconsecutivestripsoffixedwidth.Withoutlossofgeneralizationweassumethatallthesestripshavewidth1.Foranyangleθ,2Rstripprojectionsaremeasured.Thefirststripcorrespondstothet-interval(−R,−R+1),thelaststripto(R−1,R).InourneuralnetworkapproachwealsoneedtoevaluateSθ,f(t󰁀,tr)forothervaluesof(t󰁀,tr),oftenwithintegerwidthtr−t󰁀.Thesevaluesarecomputedbylinearinterpolationofthemeasuredprojectiondata.

Althoughthereconstructionproblemisdefinedusingtheprojectiondata,theperformanceofreconstructionalgorithmsisoftenevaluatedbyconsideringaknownimagefanditsprojectionsPθ1,f,Pθ2,f,...,Pθk,f,andcomparingthereconstructiontotheoriginalimagef.Inpractice,resemblancetotheoriginalimageisoftenmoreimportantthanperfectcorrespondencetotheprojectiondata.Thisisparticularlyimportantiftheprojectiondatabyitselfisnotenoughtodeterminetheimagefandadditionalpriorknowledgemustbeusedinthereconstructionalgorithm,whichisthecaseifthenumberofprojectionanglesnisrelativelysmall:theproblemisthenunderdetermined.

3NeuralNetworkApproach

Inthissectionwewilldiscusstwoneuralnetworkapproachestothediscreteto-mographyproblem.Afeed-forwardneuralnetworkconsistsofneurons,groupedinlayers,whereneuronsfromonelayercanhaveaweightedconnectiontoneu-ronsfromthenextlayer.Theweightsaretrainedsimultaneously,hopefullyto-wardoptimalvalues,bypresentingthenetworkwithcorrectinput-outputpairs.Bothproposednetworksarefeed-forwardback-propagationnetworks(see,e.g.,[4,7])withoneinputlayer,onehiddenlayerandoneoutputlayer.Thenetworksarefullyconnected.Thefirstandprobablymostobviousversion(referredtoasafull-imagenetwork)hasoneoutputnodeforeachpixel.Thesecondversion(a

ANeuralNetworkApproachtoReal-TimeDiscreteTomography393

so-calledsingle-pixelnetwork)hasonlyoneoutputnode,toreconstructonepixel,butcanbeused—throughappropriateadaptation—toreconstructthewholeimage.Thistypeofnetworkhasseveraladvantagesoverthefull-imagenetwork.3.1

AFull-ImageNetworkforTomography

Theinputnodesofthenetworkcontainthevaluesoftheprojections,theoutputnodescontainthepixelvalues.Sothenumberofinputnodesequalsthenumberofprojections,whilethenumberofoutputnodesequalsthesizeoftheimagingarea,i.e.,approximatelyπR2.Thehiddennodesareconnectedtoallinputnodesandalloutputnodes.Outputvaluesareinterpretedasgrayvalues,yieldingthegraylevelreconstruction.Ifnecessary,thesevaluescanberoundedinapost-processingstepto0/1-valuesfora“crisp”or“rounded”reconstruction.Thesenetworkswerefirstintroducedandexaminedin[3].

Trainingisperformedasfollows.Theinputpattern,consistingoftheprojec-tionvalues,isofferedtotheinputnodes.Everyconnectionhasareal-valuedweight,thatisadaptedduringtraining.Thehiddennodesreceivetheweightedsumoftheirincomingconnections,andgenerateanoutputthroughthestandardsigmoidσ:x→1/(1+e−x).Outputnodesoperateinasimilarway.Ineachepoch,anumber(50,000,say)ofrandomimages(sampledfromacertaindistri-bution)withtheirprojectionsarepresentedtothenetwork;aftereachepochthelearningrateαissomewhatdecreased.Notethatsamplesareusedonlyonce,unlesstheyarebychanceregenerated.

Theweightsareadaptedusingthenormalback-propagationrule.Aweightwjifromhiddennodejtooutputnodeiisadaptedthrough

wji←wji+α·aj·Δi,Δi=σ󰀃(ini)·(ti−ni).

󰀰

Hereajistheoutputofnodej,ini=jwjiajistheweightedinputtonodei,ni=σ(ini)isitsoutput(foroutputnodesthisisthenetoutput)andtiisthedesiredtargetvalue,i.e.,thetruepixelvalue.Theupdateruleforweightwkjfrominputnodektohiddennodejisalittlemorecomplicated(cf.[4,7]):

󰀸

󰀃

wjiΔi.wkj←wkj+α·ak·Δj,Δj=σ(inj)·

i

Asusual,oneextrainputnodeandoneextrahiddennodeclampedto−1are

added,theso-calledbiasnodes.

In[3]hiddennodeswithonlyasmallnumberofconnections(so-calledlocalnodes,asopposedtothemorecommonglobalnodesmentionedabove)areadded.Theselocalnodesareconnectedtoafewinputnodesandoutputnodes;theykeeptrackoftheconstraintsthataffectapixelanditsimmediateneighbours.Eachlo-calnodecorrespondswithauniquepixel,receivesinputfromthelineprojectionsthatintersectwiththatpixel,andisconnectedtothe9outputnodescorrespond-ingwiththepixelanditsimmediateneighbours(6or4neartheboundaries).ThisgeneralnetworkarchitectureisdepictedinFigure3.Thoughthistypeofnetworkwasshowntoperhapshavesomeadvantages,inthesequelwewillforcomparisonpurposesjustreportontheversionwithonlyglobalnodes.

394K.J.BatenburgandW.A.Kosters

outputs...global hidden nodes...−1biaslocal hidden nodes...−1bias...inputsFig.3.Generalstructureofthefull-imagenetwork.Globalhiddennodesareconnectedtoallinputnodesandalloutputnodes.Localhiddennodesareconnectedtoonlyafewinputandoutputnodes.

3.2AMoreEfficientArchitecture:TheSingle-PixelNetwork

AlthoughthenetworkfromSection3.1issuitableforreal-timereconstructiononcethetrainingphaseiscomplete,ithassomedisadvantages:

–Thenetworkcontainsalargenumberofinput/outputnodes;alargenumberofhiddennodesisrequiredtoobtainreasonablereconstructions.Duetothelargenumberofnodesandconnectionsbetweenthem,trainingthenetworktakesaverylongtime.

–Millionsoftrainingimagesandtheirprojectionsarerequiredtotrainthenetwork.Inpracticalapplicationsitisusuallyimpossibletoobtainsuchlargedatasets.Inthesequelweproposeanimprovementbyfocussingonthereconstructionofasinglepixel,insteadofthewholeimage.Thisvastlyreducesthenumberofhiddentooutputconnections.ReconstructingaSinglePixel

OneoftheprincipalgoalsofourneuralnetworkdesignisareductionofthenumberofinputnodesincomparisontothenetworkfromSection3.1.Whenreconstructingasinglepixelp=(xp,yp)withintheimagingareaA,itisclearthatprojectedlinesthatpassthroughparemoreimportantfordeterminingitsvaluethantheotherprojectedlines.Also,ifweassumethattheimageislocallysmooth,projectedlinesthatpassnearparemoreimportantthanlinesthatpassfarawayfromthispixel,asneighbouringpixelsofparehighlyrelevanttothevalueofp.

Weusethisintuitivenotionofrelativeimportancebetweenprojectedlinestopreprocesstheprojectiondata.TheinputsoftheneuralnetworkfromSection3.1

ANeuralNetworkApproachtoReal-TimeDiscreteTomography395

corresponddirectlytothemeasuredprojectionvalues.Inthenewsingle-pixelnetwork,eachinputcorrespondstoastripprojection.Stripsthatarefarawayfromparemuchbroaderthanstripsnearp.

Letkbeapositiveinteger.Let0d0/2+

k󰀸i=1

di≥2R.(1)

Definethestripboundariess−k,...,s0,...,sk+1asfollows:

s0=−d0/2;

si=si−1+di−1si=si+1−d−i

(i=1,...,k+1);(i=−k,...,−1).

Putτθ=Tθ(xp,yp),thepointprojectionofpforangleθ.ThesetIθofinputstripsforangleθcannowbedefinedas

Iθ=

k󰀻i=−k

{(θ,τθ+si,τθ+si+1)}.

EachelementofIθisa3-tuple,consistingoftheangleθandtheleftand

rightboundaryofat-interval,whichjointlydefineastripthroughtheimag-ingarea.TheconstraintinEquation(1)ensuresthatthestripsinIθcoveratleasttheentireimagingareaA,independentoftheposition󰀳ofp.Giventhe

n

anglesθ1,θ2,...,θn,definethesetIofallinputstripsasI=i=1Iθi.

Foreverytriple(θ,t󰁀,tr)∈Ithereisaninputnodeintheneuralnetwork,givingagrandtotalof(2k+1)·ninputnodes.TheinputforsuchanodeisSθ,f(t󰁀,tr),thestripprojectionforangleθinthet-interval(t󰁀,tr).

Figure4showsthreepossiblechoicesfortheset{d0,d1,...,dk}ofstripsizes.Settingd0=d1=...=dkyieldsequallyspacedstrips(Figure4a).Settingd0=1anddi=ifori≥1yieldsasetofstripsforwhichthesizeincreaseslinearlyasthedistancefromthepixelpincreases(Figure4b).InSection4wewillshowthatevenifwesetd0=1,di=2i−1fori≥1(Figure4c),theresultsarestillsatisfactory.Usingstripsizesthatgrowexponentiallywiththedistancetopyieldsalargereductioninthenumberofinputsoftheneuralnetwork.Trainingthesingle-pixelnetworkproceedsasinthecaseofthefull-imagenetwork.However,trainingaseparatenetworkforeachpixelwouldtakeahugeamountoftime.Also,theproblemthatthetrainingrequiresalargenumberoftrainingexamplesremains.Inthesequelwewillshowhowbothproblemscanbesolved.

ReconstructingAllPixels

Althoughthebinningapproachfromtheprevioussectiondrasticallyreducesthenumberofinputsofthenetwork,alargenumberofimagesisstillrequiredto

396K.J.BatenburgandW.A.Kosters

s−4s−3s−2s−1s0s1s2s3s4s5...d4d3d2d1d0d1d2d3d4...s−2s−1s0s1s2s3s4s5...d2

d1

d0

d1

d2

d3

d4

...Fig.4.Threedifferentstripsizeconfigurations;a,top:constant,b,middle:linear,c,bottom:exponential

performthetraining.Ifaseparatenetworkneedstobetrainedforeachpixelintheimage,thetotaltrainingtimemaybeevenlargerthanforthebasicnetworkfromSection3.1.

Notethatallinputsofthesingle-pixelnetworkarerelativetotheprojectionsofthecenterofthepixel.Therefore,thereisnoobviousreasonwhythenetworkcannotbeusedtoreconstructadifferentpixel,elsewhereintheimage.TheonlydifferencebetweentwodifferentpixelsisthattherelativepositionoftheimagingareaAisdifferent.However,ifweuseavaryingsetofpixelsfromthetrainingimages,insteadofusingthesamesinglepixelfromeachimage,itmaybepossibletotrainthenetworkwithoutprovidingadditionalinformationontherelativepositionoftheimagingarea.Thisreconstructiontaskisharder,sincelessinformationisofferedtothenetwork.InSection4weshowthatonesingle-pixelnetworkiscapableofreconstructingarbitrarilypositionedpixels.ThisofferssomemajoradvantagesoverthenetworkfromSection3.1:

–Ifexponentiallyincreasingstripsizesareused(seeFigure4c)boththenum-berofinputs(logarithmicinR)andthenumberofoutputs(constant,1)isvastlyreducedwhencomparedtothenetworkfromSection3.1,reducingtrainingtimeforthesingle-pixelnetwork.

–Onlyasinglenetworkhastobetrained,insteadofanewnetworkforeachpixel.

–Eachtrainingimage,withitsprojections,nowyieldsanewtrainingexampleforeachpixelintheimage.ThenetworkfromSection3.1requiresanewimageforeachtrainingexample.Andfinally,asweshallseeinSection4,thesingle-pixelnetworksseemmorecapableofreconstructingimagesfromtheirprojections,ratherthanlearningimagesfromcertainclasses.

ANeuralNetworkApproachtoReal-TimeDiscreteTomography397

3.3ComputationalComplexity

Forafeed-forwardneuralnetworkhavingNIinputnodes,NHhiddennodesandNOoutputnodes,thetimerequiredtopropagateaninputpatterntotheoutputnodesisO(NINH+NHNO).Thetimecomplexityfortrainingasingleinput-outputpatternisofthesameorder.

Forthefull-imagenetworkfromSection3.1wehaveNI=O(nR)andNO=O(R2),sothatpropagatingapatterntakesO(NH(nR+R2))time.(Rememberthatnisthenumberofprojectionanglesordirections,andRistheradiusoftheimagingarea.)TypicallyRismuchlargerthann.Oncethetrainingphaseiscomplete,thetimecomplexityofcomputingareconstructedimagefromasetofprojectiondataisofthissameorder.

Forthesingle-pixelnetworkwithlogarithmicstripsizesfromSection3.2wehaveNI=O(nlogR)andNO=1,yieldingatimecomplexityofO(nNHlogR)forpropagatingapattern.Tousethenetworkforreconstructionafterthetrain-ingphase,anewinputprojectionpatternhastobepropagatedthroughthenet-workforeverypixelintheimage,yieldingatimecomplexityofO(nNHR2logR).Also,forthisnetworktheprojectiondatamustbepreprocessedfirsttoobtaintheinputdataforthenetwork,withtimecomplexityO(R).Notethatthenum-berNHcanvaryheavilybetweendifferenttypesofnetworks.

Sincethevaluethatiscomputedateach(non-input)nodeofafeed-forwardnetworkonlydependsonthevaluesinthepreviouslayer,thevaluesforallnodesinalayercanbecomputedinparallel.Moreover,thecomputationthatneedstobeperformedateachnodeisverysimple.Thisallowsforveryefficientparallelimplementations.

4ExperimentalResults

Inthissectionwepresentexperimentalresultsforthefull-imagenetworkfromSection3.1andthesingle-pixelnetworkfromSection3.2.Werestrictourselvestotwoclassesofsyntheticimages.

Fig.5.Top:128×128imagesfromthe7-class;bottom:imagesfromthe50-class

398K.J.BatenburgandW.A.Kosters

Thefirstclassofexamplesconsistsofimageswithfourlargewhiteellipsesandthreesmallerblackonesinside,inadarkbackground.Thisclassisreferredtoasthe7-class,orjust“7”.Thesecondclassconsistsofimageswithfiftysmallwhiteellipsesinadarkbackground,andisreferredtoasthe50-class,orjust“50”.Figure5containssomeexamples.

Table1.Resultsfromexperimentsforthefull-imagenetwork;32×32and64×64images;trainingruntimeinhours

imagewidth323232323232323232323232646464646464646464646464

angles

imageclass777505050777505050777505050777505050

hiddengray0–1nodeserrorerror

averageover

500.0740.0521000.0580.0422000.0460.044500.0690.0441000.0560.0372000.0540.036500.1040.0761000.0660.0502000.0400.040500.0650.0421000.0440.0302000.0190.017500.1480.1091000.1180.0922000.0630.062500.1450.0981000.1310.0912000.1260.087500.1990.1511000.1450.1122000.0780.077500.1420.0971000.1180.0862000.0770.077

run-time

3runs2.155.059.852.155.0510.003.306.3012.103.406.3512.1512.8027.3058.3012.7527.2058.0014.8030.3063.1514.8030.2563.35

444444101010101010444444101010101010

Allexperimentswererepeatedthreetimes,andaveragesweretakenoverthesethreeruns.Becauseallimagesareinfactlocatedwithinacircle(theimagingarea),wedonotconsidererrorsoutsidethisarea;therefore,meanerrorvaluesarecomputedwithrespecttopixelswithintheimagingarea.Averageabsoluteerrorsarereportedonindependenttestsetsconsistingof1,000images,bothforgraylevelreconstructionandforroundedreconstruction(the0–1error).Table1showsresultsforthefull-imagenetworkfortwoimagesizes:32×32and64×64.Table2givesresultsforthesingle-pixelnetworkforthreeimagesizes:32×32,64×64and128×128.Theparametersareasfollows:threesizesofthehiddenlayer:50,100and200hiddennodes;andtwodifferentsetsofprojectionangles,

ANeuralNetworkApproachtoReal-TimeDiscreteTomography399

Table2.Resultsfromexperimentsforthesingle-pixelnetwork;32×32,64×64and128×128images;trainingruntimeinhours;(*)containsrunwith0–1errorequalto0

imagewidth323232323232323232323232646464646464646464646464128128128128128128128128128128128128

angles

imageclass777505050777505050777505050777505050777505050777505050

hiddengray0–1run-nodeserrorerrortime

averageover3runs

500.0380.0263.051000.0380.0254.952000.0370.0259.65500.0540.0343.101000.0540.0344.952000.0540.0349.55500.0040.0036.951000.0040.002(*)12.202000.0040.00321.65500.0160.0116.951000.0150.01112.102000.0150.01121.50500.0460.0293.701000.0440.0325.802000.0440.02911.10500.1160.0833.701000.1140.0835.802000.1180.08211.15500.0060.0058.951000.0060.00514.752000.0060.00525.20500.0510.0349.001000.0520.03314.652000.0510.03325.20500.0420.0284.751000.0410.0297.152000.0390.02813.35500.1300.0944.701000.1290.0927.102000.1290.10013.40500.0050.00312.201000.0050.00218.302000.0050.00330.50500.0570.03812.201000.0560.03918.152000.0550.04030.45

4

44444101010101010444444101010101010444444101010101010

consistingof4and10projections,equallyspacedintheinterval[0◦,180◦).Inallexperiments200epochs,eachconsistingof50,000examples(full-pixelnetwork)or2,300,000examples(single-pixelnetwork),wereusedfortraining.Thenumberofexamplesperepochwaschosensothatthetrainingofthetwonetworkstookthesameamountoftimeforthecaseof32×32imagesfromthe7-classusing4projectionsand100hiddennodes.Thereasonforusingmoreexamplestotrain

400K.J.BatenburgandW.A.Kosters

thesingle-pixelnetworkisthateachexampleonlycontainsinformationonasinglepixelinthatcase.Whenusingarealmeasureddataset,anewtrainingexamplecanbeconstructedfromeachpixelinthedataset.ExperimentswererunonasingleprocessorAMDAthlon2.2GHzPC.Runtimesinthetablesrefertothetrainingtimesofthenetworks;oncetrained,reconstructionofanewimageisalmostinstantaneously.Thelearningrateαstartedat0.5,andwasmultipliedby0.99aftereachepoch.

Experimentswiththefull-imagenetworkshowthatthenetworkiscapableofreconstructingsmallimageswithacceptablequality,e.g.,32×32images.Thisrequiresareasonablylargenumberofhiddennodes,e.g.,200,givingahugenumberofconnections.Forlargerimageshowever,qualitydropsdown,whilecomputingtimeincreasesheavily(therefore,noexperimentson128×128imageswereperformed).Theresultssuggestthatafurtherincreaseinthenumberofhiddennodesmightimprovereconstructionquality.Figure6showssomeexamplesfromarunofthefull-imagenetworkfor10projectionsonthe7-classfor64×64images,using100hiddennodes.Theaverageabsolutepixelerrorforthisparticularrun(using1,000,000trainingexamples)was0.133(graylevelreconstruction)and0.102(roundedreconstruction).

Fig.6.Fromlefttoright:64×64original,graylevelreconstructionandroundedrecon-structionusingafull-imagenetwork,withabsolutetotalerrors413.7and291,respectively

Asanotherexample,weshowresultsfor64×64imageswithinthe50-class,using10projections,and100hiddennodes,seeFigure7.Thefigureshowsbestandworstreconstructionfromarandomsetof25imagesfromthe50-class.

Fig.7.Fromlefttoright:twopairsof64×64originalandroundedreconstructionusingafull-imagenetwork,withabsolutetotalerrors235and310,respectively

Clearly,theresultsforthe50-classarenotsatisfactory.AswecanseeinTable2,single-pixelnetworksgivemuchbetterreconstructions.Wenowconsiderthesingle-pixelnetworkexclusively.

ANeuralNetworkApproachtoReal-TimeDiscreteTomography401

ForalltestcasesinTable2thenumberofhiddennodeshashardlyanyeffectonthequalityofthereconstructions.Thissuggeststhatarelativelysmallnumberofhiddennodessuffices.StructuralRiskMinimizationmightbeusedtofindasuitablesizeforthehiddenlayer.The50-classisclearlymoredifficulttolearnthanthe7-class.

Figure8comparesthesingle-pixelnetworkandfilteredbackprojection(FBP),whichisthefastestalgorithmavailableforcontinuoustomographyandtheonlyonethatcanbeusedforreal-timereconstruction.TheFBPreconstructionswerecomputedwiththeMATLABImagingToolbox,usingtheRam-Lakfiltermul-tipliedbyaHannwindow.Thesingle-pixelreconstructionsareclearlybetter.Otherdiscretetomographyalgorithmsmightbecapableofproducingmoreac-curatereconstructions,perhapsevenusingfewerprojections.However,toourknowledgethesealgorithmsarefartooslowforreal-timereconstruction.

Fig.8.Fromtoptobottom:three128×128imagesandtheirreconstructionsusingfilteredbackprojection,roundedfilteredbackprojectionandthesingle-pixelnetwork,respectively;topandmiddleimagefromthe7-class,with10projections;bottomimagefromthe50-class,with18projections.Absolute0–1errorsforthesingle-pixelnetworkreconstructionsare101,84and153,respectively.

Anaturalquestiontoaskiswhetherthenetworkiscapableofreconstructingimagesoutsidetheclassitwastrainedon.Figure9showsthereconstructionresultsoftwosuchimages,whichareclearlynotinanyofthetrainingclasses.Thoughnotperfect,theresultsaresurprisinglygood.

Thoughresultsfrom[3]suggestthatlocalnodesmightgivesomeimprovementforthefull-pixelnetwork(puttingmorecomplexityintothenetwork),thiswasonlyshownforrelativelysmallimages.Inthecurrentpaperwehavechosen

402K.J.BatenburgandW.A.Kosters

Fig.9.Fromlefttoright:twopairsofa128×128imageanditsreconstruction;originalimagesarenotfromthe7-classforwhichthesingle-pixelnetworkwastrained.Absolute0–1errorsare189and291,respectively.

Fig.10.Fromlefttoright:32×32originalandreconstructionusingafull-imagenetworkandasingle-pixelnetwork,respectively;onlyoneprojection

forglobalnodesonly,toallowforbettercomparisonbetweenfull-imageandsingle-pixelnetworks.

Anotherissuewiththefull-imagenetworksisthattheyaremoreinclinedtolearnlocationdependentinformation,inparticularwhenthereareveryfewprojections.Inthatextraordinarycasetheybehavequitedifferentlyfromthesingle-pixelnetworks.Asanexample,inFigure10weshowsomeresultsforthereconstructionofa32×32imageusingonlyprojectioninonehorizontaldirec-tion.Thesingle-pixelreconstructionshowsthedensitydistributionofthe0–1intensityintheprojectiondirection,asanytwopixelsonthesamehorizontallinecannotbedistinguishedbythenetwork.Theimagingareaisclearlyvisible.Asmentionedbefore,thefinal0–1imageisgeneratedfromthegraylevelre-constructionbysimplyrounding,givingacrispfigure,cf.Figure6.Experimentssuggestthaterrorsoftenoccurforpixelsthathavearawreconstructionvaluenear0.5.Itispossibletoslightlyimprovethefinalreconstructedimageby(forthosepixels,inparallel)tryingboth0and1asreconstructionvalue,meanwhilecomparingwiththeprojections.Timerestrictionsclearlyallowjustafewpixelstobetoggledsimultaneously.Thequalityofthereconstructionmayalsobeim-provedbyintroducingastochasticmodeloftheimageclassandcomputinganimage(inapostprocessingstep)thatcorrespondswellwithboththeoutputoftheneuralnetwerkandthemodeloftheimageclass.

5Conclusions

Weconcludethatthesingle-pixelnetworkfromSection3.2iscapableofgen-eratingverygoodqualityreconstructionsofimagesfrombothclasses,given

ANeuralNetworkApproachtoReal-TimeDiscreteTomography403

sufficientlymanyprojectiondirections.Oncetrained,suchanetworkcancom-putenewreconstructionsalmostinstantaneously,makingitverysuitableforreal-timereconstruction.Thefull-imagenetworksfromSection3.1performlesssatisfactory,butbehavewellifonlyveryfewprojectiondirectionsareavailableandtheimagesaresmall.

Althoughweusethenetworksforthereconstructionofbinaryimages,thereisnoapparentreasonwhytheycouldnotbeusedforthereconstructionofimagesthatcontainalargersetofgrayvalues,orevenacontinuousrange.Weintendtoexplorethepossibilityofusingourneuralnetworkapproachforcontinuousto-mographyinfutureresearch.Forcontinuoustomographythesizeofthenetworkwillincreasesignificantly,asthenumberofprojectionsthatisrequiredtoob-tainagoodreconstructionistypicallymuchlargerthanfordiscretetomography.Thiswillincreasethetrainingtimeandthereconstructiontimeaftertraining.Forcontinuoustomographyalgorithmsarealreadyavailablethatarebothaccu-rateandfast.Fordiscretetomography,however,thecurrentapproachseemstoprovidecompetitivealgorithms,inparticularforreal-timereconstruction.

References

1.Batenburg,K.J.:ReconstructingBinaryImagesfromDiscreteX-rays,CWIRe-searchReportPNA-E0418(2004)

2.Batenburg,K.J.:AnEvolutionaryAlgorithmforDiscreteTomography.DiscreteAppliedMathematics151(2005)36–54

3.Batenburg,K.J.,Kosters,W.A.:NeuralNetworksforDiscreteTomography.Pro-ceedingsoftheSeventeenthBelgium-NetherlandsConferenceonArtificialIntelli-gence(BNAIC),21–27(2005)

4.Bishop,C.M.:NeuralNetworksforPatternRecognition.OxfordUniversityPress(1995)

5.Helgason,S.:TheRadonTransform.Birkh¨auser,Boston(1980)

6.Herman,G.T.,Kuba,A.(eds.):DiscreteTomography:Foundations,AlgorithmsandApplications.Birkh¨auser,Boston(1999)

7.Hertz,J.,Krogh,A.,Palmer,R.G.:IntroductiontotheTheoryofNeuralCompu-tation.Addison-Wesley(1991)

8.Kak,A.C.,Slaney,M.:PrinciplesofComputerizedTomographicImaging.SIAM(2001)

9.Keat,N.:Real-timeCTandCTFluoroscopy.TheBritishJournalofRadiology74(2001)1088–1090

10.Kerr,J.P.,Bartlett,E.B.:NeuralNetworkReconstructionofSingle-photonEmis-sionComputedTomographyImages.JournalofDigitalImaging8(1995)116–12611.Lampinen,J.,Vehtari,A.,Leinonen,K.:ApplicationofBayesianNeuralNetwork

inElectricalImpedanceTomography.Proceedingsofthe1999InternationalJointConferenceonNeuralNetworks(1999)

12.Liao,H.Y.,Herman,G.T.:ACoordinateAscentApproachtoTomographicRecon-structionofLabelImagesfromaFewProjections.DiscreteAppliedMathematics151(2005)184–19713.Sch¨ule,T.,Schn¨orr,C.,Weber,S.,Hornegger,J.:DiscreteTomographybyConvex-concaveRegularizationandD.C.Programming.DiscreteAppliedMathematics151

(2005)229–243