RECONSTRUCTIONALGORITHMSFORLIMITEDANGULARDIFFRACTIONTOMOGRAPHYByPavelRoyPaladhiADISSERTATIONSubmittedtoMichiganStateUniversityinpartialentoftherequirementsforthedegreeofElectricalEngineering|DoctorofPhilosophy2016ABSTRACTRECONSTRUCTIONALGORITHMSFORLIMITEDANGULARDIFFRACTIONTOMOGRAPHYByPavelRoyPaladhiTomographyisaubiquitousimagingmodalityappliedtonumerouslikemedicalimaging,geophysicalimaging,structuralhealthmonitoringetc.Itisaprocesstoviewcross-sectionalofanobjectorregionofinterestthroughsolvinganinverseproblem.Whensourcesareusedastheinterrogatingenergy,thesptomographicreconstructionistermed`Tomography'asthealgorithmaccountsforrac-tionAsaresult,thesealgorithmsaremorecomplexthanstraightraytomographyalgorithmsviz.computedtomographywhichhasbeenverysuccessfullyimplementedforX-raytomography,PETetc.Ideally,projectiondatacoveringfull360aroundtheregionofinterestisnecessaryforaccuratereconstruction.However,inmanypracticalapplications,thisisnotalwaysfeasible.Asaresult,reconstructionisperformedonlim-iteddatasets,essentiallymakingtheprocessarecoveryfromanunder-determinedsystem.Thisthesisfocusesondevelopmentofnovelandtmethodstohandlethechallengesonlimiteddataforimagereconstructionundertomography.Foramoderatelylimitedcoverage,someinherentredundanciesinctionTomographyprojectiondatacanbeusedtoreducetheoflimitedcoverage.Forhighlylimitedangularcoverage,theseredundanciesarenolongeravailableandcannotbeexploited.Recently,however,optimizationtechniquesinvolvingl1-normminimizationschemesunderthesocalled`com-pressedsensing'regimehaveshownpromise.Thesealgorithmsarecapableofalmostexactreconstructionoftheobjectevenwithhighlylimitednumberofprojections.Thisresearchhasexploredbothtechniquesformoderateandhighlylimitedangulartomography.Inthepartofthethesis,formoderateangularaccesslimitations,anoptimummethodforexploitingredundancywithinprojectiondatahasbeenformulated.Inthesecondpart,forhighlylimitedcoveragewithfurtherlimitationsonthenumberofavailablepro-jections,reconstructionschemesundercompressedsensingregimehavebeenexamined.Further,thisresearchdemonstratesreconstructionofcomplex-valuedobjectivefunctionundertheregimeofcompressedsensing.Thisgeneralizestheapplicationoftomographicreconstructionfornewerapplicationssuchasexaminingnewcomplexstructures(suchasmetamaterialandothersmartmaterialbasedstructures)whereknowledgeofcomplexpermittivityvaluesisessentialinevaluatingstructuralintegrityormorphologicalaber-rations.Thecompressedsensingmethodheavilyreliesonsparsityofthereconstructedsignalinsometransformationdomain.Inthisresearch,thesparsityhasmainlybeenexploitedthroughgradientmagnitudeofimages.Inavarietyofapplications,gradientmagnitudeofimagesarehighlysparse,eveniftheimagesthemselvesarenot.Sothegradientmagnitudeofimagescanbeelyusedasthesparsedomain.Further,in-corporationofmultiplesparsedomainsintothecompressedsensingframeworkhasbeenexplored.UsingHaarwaveletsinadditiontogradientmagnitudeofimagesasthesparsedomainhassuccessfullybeenemployedshowingpotentialfortimprovementsinimagereconstructionfromhighlylimiteddatathroughfurtherresearch.CopyrightbyPAVELROYPALADHI2016ToallthosewhopreparedmeforthisjourneyandwereapartofthisventurevACKNOWLEDGMENTSAPhDprogramisachallengingandrewardingjourney.Thisthesisisaculminationofonesuchjourney.Itwouldnothavecometofruitionhaditnotbeenforthegreatfamily,teachersandfriendsIwassofortunatetohave.ThisisachancetoexpressmythankstoallofthemandthegratitudeIfeeltohavethemaroundme.SpecialthanksandgratitudeareduetomyadvisorsProfs.LalitaandSatishUdpaaswithouttheirhelpthisthesiswouldnothavebeenpossible.Theyhavebeengreatmentors,knowledgeableandeagertosupportmyideas;inspiringmetocarryon,pullingmeupduringstressfultimesandhavingtheircontinuousfaithinme.Dr.AshokeSinha,Dept.ofStatisticsandProbability,MSUhadbeenagreatsourceofencouragement.Hisvisionandmathematicalinsightswereinstrumentaltowardsprogressinmultipleprojects.Mygrandparentsandparentsplayedapivotalroleinmouldingmyoutlookandpassionforeducationandresearch.TothemIowethecorevaluesIbelieveinandwhichhashelpedmetosurmountobstaclesandremainontrack.Iamfortunatetohaveagreatwifewhohasprovidedcontinuoussupportandinspiredmetopersevereagainstalloddsbypractisingthesame.TomyfriendsImadeatMSUandthoseIhavebackathome,thanksforprovidingallthehappyandmemorabletimesandthesupportIgotwheneverneeded,noquestionsasked.Lastly,IshouldnotforgettomentionMichiganStateUniversityforprovidingmeagreatplatformtolearn,growandevolveinmyunderstandingofthisworld.viTABLEOFCONTENTSLISTOFFIGURES..................................ixPart1Background...............................1Chapter1Introduction..............................2Chapter2TomographyandFilteredBackpropagationtech-nique...................................62.1Introduction...................................62.2TheHelmholtzEquation............................72.2.1BornApproximation..........................112.2.2RytovApproximation.........................122.3FourieractionProjectionTheorem(FDPT)...............132.4FilteredBackpropagationAlgorithm.....................14Part2AccurateReconstructionFromModeratelyLimitedProjectionData..............................16Chapter3DataRedundancyinTomography.........173.1GenerationoftWeightFunctions...................22Chapter4AccurateReconstructionsforModeratelyLimitedAngularMeasurements.............................294.1NoiselessReconstruction............................294.2ReconstructionwithNoisyData........................334.3Summary....................................37Part3Reconstructionfromhighlylimitedprojectiondata:Compressedsensingapproach....................40Chapter5Overview................................415.1Background...................................415.2CSTheory....................................435.2.1SparseBasisRepresentation......................445.2.2SensingMatrix:TheRestrictedIsometryProperty.........475.2.2.1Incoherentsampling.....................485.2.3ImageReconstruction..........................505.2.3.1l-2Minimization.......................505.2.3.2l-0Minimization.......................51vii5.2.3.3l-1Minimization.......................525.2.3.4GeometricalInsights.....................535.2.3.5Summary...........................55Chapter6CSbasedReconstructionforDT.................566.1ApplicationofCStosparseDTrecovery...................576.2Reconstruction.................................59Chapter7ReconstructionwithTotalVariationasl1penaltyterm...607.1ReconstructionwithTVasl1minimizer...................627.1.1ErrorAnalysis..............................647.1.2Reconstructionfromphantomswithrealisticpermittivitydistribution707.2Multiplesparsedomainincorporation.....................73Chapter8Conclusions...............................808.1Summary....................................808.1.1Exploitingdataredundancyformoderatelylimitedangulartiontomography............................818.1.2CompressedSensingbasedtomographyfromhighlysparsedata...................................818.2Contribution:Signiand....................828.3FutureWork...................................84APPENDICES.....................................86AppendixADistributionFunctionbasedweightgeneration............87AppendixBNon-linearOptimizationTechniques.................89BIBLIOGRAPHY...................................98viiiLISTOFFIGURESFigure2.1:Classicalscanof2DDT(left)andrelationofscat-tereddatawiththe2DFourierspaceoftheobjectivefunction(right)..................................14Figure3.1:(a)Fourierspacecoveragefor270angularaccessbysegmentOBin(b)sameforsegmentOAof(c)Superpositionofthetwocoveragesfrom(a)and(b).(d)TheFourierdata-spaceinalternateco-ordinatesystemwithangularcoveragealongy-axisandthefrequencyalongx-axis.....................19Figure3.2:DemonstrationoftheMS-FBPPconcept(a)realpartoforiginalimage,(b)FBPPreconstructionfrom360coverage(c)FBPPre-constructionfrom270coverageand(d)MS-FBPPreconstructionfrom270coverage..........................21Figure3.3:DemonstrationoftheMS-FBPPconcept(a)imaginarypartoforiginalimage,(b)FBPPreconstructionfrom360coverage(c)FBPPreconstructionfrom270coverageand(d)MS-FBPPre-constructionfrom270coverage...................22Figure3.4:Beta-cdfplotsfortvaluesoftheparametersaandb....25Figure3.5:ImagesshowingweightdistributionsinFourierdomaingeneratedbyparametricvariationofthebeta-cdf(usingtheparametersshowninFig.3.4).Frequencyisplottedalongabscissaandangularcov-eragealongordinate..........................26Figure3.6:ImagesshowingweightdistributionsinFourierdomaingeneratedbyparametricvariationofthebeta-cdf.Theparametersaandbusedforeachweightdistributionareinsetineachplot.Frequencyisplottedalongabscissaandangularcoveragealongordinate....27Figure3.7:CorrespondingreconstructionsfromusingtheweightdistributionsinFig.3.6...............................28ixFigure4.1:Reconstructedrealpartfromcomplextestimageundernoiselessconditions.Theleftcolumnshowsreconstructionfrom270cov-erageandrightcolumnshowsreconstructionfrom200coverage.(a)-(b)usingregularFBPP,(c)-(d)usingsine-sqweights,(e)-(f)usinggamma-cdfweights,(g)-(h)usingbeta-cdfweights......30Figure4.2:Reconstructedimaginarypartfromcomplextestimageundernoise-lessconditions.Theleftcolumnshowsreconstructionfrom270coverageandrightcolumnshowsreconstructionfrom200cov-erage.(a)-(b)usingregularFBPP,(c)-(d)usingsine-sqweights,(e)-(f)usinggamma-cdfweights,(g)-(h)usingbeta-cdfweights..31Figure4.3:Reconstructionofrealpartofimagefrom3dBawgnprojectiondatausingbeta-cdfweightsforangularcoverages(a)270(b)250(c)220(d)200...........................34Figure4.4:Reconstructionofimaginarypartofimagefrom3dBawgnprojec-tiondatausingbeta-cdfweightsforangularcoverages(a)270(b)250(c)220(d)200.........................35Figure4.5:MAEcalculatedattcoveragesforrealpartofreconstructedimagewithregularFBPPandMS-FBPPusingtweights.37Figure4.6:MAEcalculatedattcoveragesforimaginarypartofrecon-structedimagewithregularFBPPandMS-FBPPusingtweights.................................38Figure4.7:PercentageimprovementofMAEfromtweightsoverregu-larFBPPattcoveragesforrealpartofreconstructedimage38Figure4.8:PercentageimprovementofMAEfromtweightsoverregu-larFBPPattcoveragesforimaginarypartofreconstructedimage..................................39Figure5.1:(a)Sampleimage(b)zoomed-inview(c)Compressedimagebyre-taining<5%oflargestcotsinwaveletdomain.(d)zoomed-inviewofthecompressedimage...................46xFigure5.2:Visualinterpretationoftheenessoftnormsforsig-nalrecoverybyminimization[1]:(a)AsparsevectorsliesonaK-dimensionalhyperplanealignedwiththecoordinateaxesinRNandsoclosetotheaxes(b)Recoverythroughl2minimizationdoesnotthecorrectsparsesolutiononthetranslatednullspace(greenhyperplane),butanon-sparsesolution^swithleastenergy.(c)Withientmeasurements,recoverybyl1minimizationdoesthecorrectsparsesolutions...................53Figure7.1:Reconstructionsofrealpartofimagewith45viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..63Figure7.2:Reconstructionsofimaginarypartofimagewith45viewsfordif-ferentangularcoverageof:(a)180,(b)150,(c)120,and(d)90...................................63Figure7.3:Reconstructionsofrealpartofimagewith30viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..65Figure7.4:Reconstructionsofimaginarypartofimagewith30viewsfordif-ferentangularcoverageof:(a)180,(b)150,(c)120,and(d)90...................................65Figure7.5:Reconstructionsofrealpartofimagewith20viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..66Figure7.6:Reconstructionsofimaginarypartofimagewith20viewsfordif-ferentangularcoverageof:(a)180,(b)150,(c)120,and(d)90...................................66Figure7.7:Reconstructionsofrealpartofimagewith15viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..67Figure7.8:Reconstructionsofimaginarypartofimagewith15viewsfordif-ferentangularcoverageof:(a)180,(b)150,(c)120,and(d)90...................................67Figure7.9:PercentageincreaseofMAEforrealpartofimageasthecoverageisloweredforanumberofprojections.Graphsplottedfortnumberofprojections....................71xiFigure7.10:PercentageincreaseofMAEforimaginarypartofimageasthecoverageisloweredforanumberofprojections.Graphsplottedforentnumberofprojections..............71Figure7.11:PercentageincreaseofMAEforrealpartofimageasthenumberofprojectionsisloweredforacoverage.Graphsplottedfortcoverages...........................72Figure7.12:PercentageincreaseofMAEforimaginarypartofimageasthenumberofprojectionsisloweredforacoverage.Graphsplottedforentcoverages....................72Figure7.13:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..74Figure7.14:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortan-gularcoverageof:(a)180,(b)150,(c)120,and(d)90...74Figure7.15:Reconstructionsofrealpartofimagewith10views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..75Figure7.16:Reconstructionsofrealpartofimagewith10views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortan-gularcoverageof:(a)180,(b)150,(c)120,and(d)90...75Figure7.17:Reconstructionsofrealpartofimagewith15viewsand120cov-erage,whenrealandimaginarypartshavesimilarphysicalbound-aries,fortnoiselevels(measuredas%ofmeansignalen-ergylevel):(a)5%,(b)10%,(c)20%,and(d)50%........76Figure7.18:Reconstructionsofimaginarypartofimagewith15viewsand120coverage,whenrealandimaginarypartshavesimilarphysicalboundaries,fortnoiselevels(measuredas%ofmeansignalenergylevel):(a)5%,(b)10%,(c)20%,and(d)50%.......76Figure7.19:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90..78xiiFigure7.20:Reconstructionsofimaginarypartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fordif-ferentangularcoverageof:(a)180,(b)150,(c)120,and(d)90...................................78xiiiPart1Background1Chapter1IntroductionScienceandtechnologyhasundergoneahugetransformationoverthespanofthelastcenturyandhalf.Morerecently,thedevelopmentofbigcomputershavevastlyacceleratedthegrowthofnewgroundbreakingtheoriesandalsohaveservedasabridgebetweenthe-oryandexperiments.Hugeandhighlycomplexproblemswhichdonothaveclosedformanalyticalsolutionscannowbeeasilysolvedusingnumericaltechniques.Simulationscanbeusedtopredictoutcomesfromcomplexexperimentseliminatingtheneedforalargevarietyoftimeandlabourintensivecostlyprocedures.Withtheadventofcomputationaltechniquesandcapabilities,theoryandexperimenthavemergedalmostseamlesslypro-vidingagreatandexcitingpathtowardsscientadvancementandbettermentofthehumanrace.Agreatgiftofmodernsciencehasbeenthedomainofimagingsciencesin-cludingavarietyofimagingmodalities.Simultaneously,thecomputationaladvancementshaveprovidedmanyrobustschemesforimagereconstructionfromdataacquiredusingthesemodalities.Theapplicationshaverangedacrossmultipledisciplines:fromx-raycrystallographytomedicalimaging,geophysicalimagingtostructuralhealthmonitoringandnon-destructiveevaluationofmaterials.Oneofthemostpopularimagingtechniquesistomography.ThewordtomographycomesfromtheGreekword`tomo'meaningacutorsectionand`graph'meaningarepre-sentation.Sotomographyinvolvesgettingcrosssectionalimagesofstructures.Inavery2generalsense,itisachievedbyirradiatingtheobjectundertestwithsomeinterrogatingenergyandthenextractingthecross-sectionalinformationfromtheresultingscatteredenergyfromtheobject.Thustheschemeisatwo-stageprocess.Thestageinvolvesthedataacquisition,wheretheobjectisirradiatedandthescattereddatacollected.Thisdataisgenerallyreferredtoastheprojectiondata.Thesecondstageinvolvesextractingthecross-sectionalimagebyapplyingreconstructionalgorithmstotheprojectiondata.Basedonthetypeofinterrogatingenergy,tomographyisbroadlydividedintotwosub-categories.Whentheinterrogatingenergyfollowsstraightraypropagation,thenitiscalledComputedTomographyorCT.ThecommonexamplesareX-RayCT,SinglePhotonEmissionCT(SPECT),Positronemmissiontomography(PET)etc.Whentheinterrogatingenergydoesnotfollowstraightraypropagation,thenitiscalledactionTomographyorDT.ExamplesofDTareMagneticResonanceImaging(MRI),nearultrasonicandmicrowavetomography.X-RayisthemostubiquitousformofCT.SomuchsothatCTbyitselfmostlyconjurestheideaofanX-rayCTsystem.Ithascomealongwaysinceitsintroductionbyin1970sasacommerciallyviablesystem.Ithasalmostbecomeagoldstandardforfracturedetectioninmedicalaswellasindustrialapplications.ThehighresolutionofX-raysenabledetectionofminutedefects(with0.2mmresolution)andanomaliesinbones,metallicstructuresetc.Thestraightraypropagationalsoensuressimplerreconstructionalgorithmsasthenarenotconsidered.Inspiteofitspervasiveness,X-rayhastwomajordisadvantages.Firstly,thehighenergyofX-rayphotonsresultinradiationdamagesincaseofbiologicaltissues.Further,whilethesearetindetectingstructuresofstrongabsorberslikebonesandmetal,3X-raysarenotaseintiatingbetweenmanytypesofsofttissue.OtherCTscantechniquessuchasSPECT,PETetcalsohaveanumberofmedicalimagingapplications.Inmanyreallifescenarios,theinterrogatingenergythatisusedmightnotadheretostraightraypropagation.Dependingonthesamplebeinginspected,X-raysmightnotbethemosteformofinterrogation.Theoptimumtechniquetousemaybeultrasonics,microwavesorMRexcitation.MRIishighlysuccessfulinsofttissuetiationandisanothergold-standardimagingschemeinmedicine.Ultrasoundhasfoundapplicationsinsofttissueimaging,boneimagingaswellasintheNDTindustryfordefectdetectioninavarietyofmaterials.TheseareexamplesofDTandhencethereconstructionalgorithmsneedtotakeintoaccountthenatureoftheincidentwaveform.HenceDTreconstructionalgorithmshavealsobeenanactiveofresearch.Conventionally,theprojectiondataisgatheredallaroundthespecimenundertest.However,generatingafull360coveragehasitsownchallenges.Dependingontheapplication,generationoffull360coveragemightnotbepossible.Itmightbeduetolimitedaccessaroundthespecimenorthetimerequiredforfulldataacquisitionmightbetoolonginmanyscenarios.Further,forcostlierimagingmodalitieslikeMRI,iftheangularrequirementscanbelowered,thentheoverallcostofoperationcanalsobereduced.Theseissueshaveprovidedatimpetustowardsdevelopmentofalgorithmswhichcanreconstructimagesfromlimitedangularcoverageorincompleteprojectiondata.Thisresearchexploresalgorithmsforlimitedangletomography.Broadly,two4mainaimsarebeingexplored.TheisusingredundancieswithintheprojectiondatasettoreconstructcomplexvaluedimagesundermoderatelylimitedangularDT.Thesecondistoapplyvariousoptimizationanderrorminimizationschemesforreconstructionfromhighlylimitedangularprojectiondata.Thethesisisarrangedasfollows:inchapter2,abriefbackgroundoftomographyandtheFilteredbackpropagation(FBPP)techniqueforimagereconstructionisgiven.Inchapter3,thedataredundancyconceptinDTprojectiondataisintroduced.Further,optimalwaystoexploitthisphenomenoninimagereconstructionsisdiscussed.Resultsfromoptimumreconstructionsthroughexploitingredundanciesarealsopresentedinchapter4.ThelastpartofthethesisdealswithapplicationofanewtechniquefortomographicreconstructionChapter5introducesthenewareaofresearchviz.compressedsensing(CS).Followingabriefintroductiononthesubject,theframeworkforapplyingCStoimagereconstructionfromhighlylimitedangularDTprojectiondatasetsispresentedinchapter6.Resultsfromprojectiondatasetsfromvaryingsparsity,bothintermsofangularcoverageandnumberofprojectionshavebeenpresentedandanalyzedchapter7.Further,applicationofmultiplesparsedomainssimultaneouslyhasalsobeenexplored.TheimportanceofthisistashigherdatalimitationsthanthatallowedbyregularCSmightbeachievedifmultiplesparsedomainsareoptimallyexploited.TheresultsshowtheenessofCSasastablealgorithmtoreconstructcomplexvaluedimagesfromseverelylimitedDTprojectiondata.Chapter8concludesthedissertation,summarizingthecontributionsofthiswork,itsapplicationsandpossiblefuturedevelopments.5Chapter2TomographyandFilteredBackpropagationtechnique2.1Introductiontomography(DT)isapopularimagingmodality[2,3],usedinavarietyofapplicationssuchasmedicalimaging,non-destructiveevaluationofmaterials,struc-turalhealthmonitoring,geophysicse.g.[4{11].Inthedomainofopticalimagingthismethodhasbeenexploredindepthviz.opticaltomography(ODT)withmulti-disciplinaryapplications,seee.g.[12{18]etc.DTisabroadimagingtechniqueofwhichultrasoundandmicrowavetomographicimagingaresub-classes.Itisacomprehen-sivewayofcharacterizingthecomplexpermittivityorrefactiveindexofthetestsample.Thisisreferredtoastheobjectfunction.DTisapplicabletomicrowavetomographyoftissuesamplesandhasbeenofgreatinterestintomographicimagingforbreastcancerdetection[19{22].Thehighcontrastofdielectricpropertiesatmicrowavefrequenciesbe-tweenhealthyandcancerousbreasttissueprovidesopportunitiesforclearlyidentifyingmalignancieswithinbreasttissue.ThecontrastismuchhigherthanincaseofX-raysandhencemicrowavetomographyisadvantageousbothintermsoftruedetectionandavoidingradiationdamagefromX-rays.FurtherapplicationsareinofSARimaging.Vari-6ousbackprojectiontechniqueshavebeenexploredforuseinradarimagingandmoforbetterreconstructions[23{25].Fasterimplementationsforbackprojectionsalgorithmsarealsobeingexplorede.g.[25].Again,radarbasedmethodshavebeencombinedwithmicrowavetomographytogeneratehigherresolutionsformedicalimaging[21].Thus,anyimprovementinthetraditionalbackpropagationtechniquesisofpotentialinterestacrossmultipledisciplines.Inthepresenceofweakscatterers,assumingtheBornorRytovapproximations[3],theFourierProjectiontheorem(FDP)isapplied.TheFDPrelatesthescat-tereddatafromtheRegionofInterest(ROI)tothe2D-FourierSpaceoftheROI.Devaneydevelopedthebackpropagation(FBPP)algorithmforthisiontoreconstructalow-passimageoftheobjectfunction[2].Thetraditionalback-propagationtechniquerequiresprojectiondatafrom[0;2ˇ]angularcoverageforaccurateimagereconstructionofacompleximage.Eventhoughtheformulationappliestoweakscatterers,ithasfoundanumberofapplicationsandsinceitsintroduction,asteadyre-searchfocushasbeenmaintainedtoincreasetheextentofusageforbackpropagation-likealgorithmsforDTandmakingthemmoregeneralinapplicability,e.g.[26,27].SomebasicpreliminariesleadingtotheFBPPalgorithmareintroducedbelow.Someofthedetailedderivationsandexplanationscanbefoundin[3,28,29].2.2TheHelmholtzEquationThepropagationoflightorotherelectromagneticwavethroughspaceoranymediumobeysMaxwell'sequations.Propagationthroughanyhomogeneousmediumcanbede-7scribedthroughthewaveequation,wherethethevectorialdescriptionoftheistoascalardescriptionofwaves.Thegeneralformofthewaveequationisr2u(r;t)1c2@2@t2u(r;t)=0:(2.1)Thisequationhasbothspatialandtemporalvariables.Foranalysisoftimeharmonicsystems,wecanonlyconsiderthetimeindependentpart,whichgivesusthestandardgeneralformofthewaveequation:hr2+k2(r)iu(r)=0:(2.2)wherek(r)isthewavenumberdependingonthelocalpermitivityorrefractiveindexofthemedium.Ifofpolarizationetc.areignored,thenk(r)canbeconsideredasascalardependingontherefractiveindexn(r)ofthemediumalongwiththevariationsn(r):k(r)=k0n(r)=k0[1+n(r)]:(2.3)Inahomogeneousarea,inabsenceofscatterers,thewaveequationreducestothehomo-geneousHelmholtzequationhr2+k2iu(r)=0:(2.4)Inthepresenceofaninhomogeneityorscatterer,nrepresentsthedeviationsintherefractiveindexwithintheobject.Sonhasboundedsupportwithintheobjectandiszerooutsideit.Inthiscase,theformtakenbythewaveequationiscalledthe8inhomogeneousHelmholtzequationandisgivenby:hr2+k20iu(r)=k20hn(r)21iu(r);(2.5)wheren(r)istheelectromagneticrefractiveindexofthemediagivenby:n(r)=s(r)(r)00;(2.6)whereandarethepermeabilityanddielectricconstantvariables.Therighthandsideof(2.5)istheforcingfunctionofthatequation.Leto(r)=k20hn(r)21i,sothatthewaveequationcanbewrittenas:hr2+k20iu(r)=o(r)u(r):(2.7)Inordertodealwiththeinhomogeneityo(r),theuseofGreen'sfunctionisapplied[3].TheGreen'sfunctionisthesolutionto:hr2+k20iG(rr0)=(rr0):(2.8)Forthe2Dcase,itisazeroorderHankelfunctionofkindandtakestheform:G(rr0)=i4H(1)0(k0jrr0j):(2.9)Theobjectfunctionof(2.8)canbeconsideredasapointinhomogeneity.SotheGreen'sfunctionrepresentstheldfromapointscatterer.Itispossibletorepresenttheforcing9functionasanarrayofimpulses,i.e.o(r)u(r)=Zo(r0)u(r0)(rr0)dr0:(2.10)Here,theforcingfunctionoftheinhomogeneouswavefunctionisrepresentedassum-mationofimpulsesweightedbyo(r)u(r)andshiftedbyrr0.Asthegreen'sfunctionrepresentsthesolutionduetoasingleimpulsefunction,andthelefthandsideofthewaveequationislinear,thereforethetotalscatteredcanbeexpressedasasummationofthescatteredbyeachindividualpointscatterer.Usingthisidea,thetotalscatteredinthewaveequationcanbeexpressedasus(r)=Zo(r0)u(r0)G(rr0)dr0:(2.11)Thuswearriveatanintegralequationforthescatteredintermsofthetotalu=u0+us.Thescatteredcanbesolvedbyapplyingsomeapproximations.ThetwomostpopularapproximationsinthiseldaretheBornapproximationandtheRytovapproximation.BothcanbeusedtoderivetheFourieractionProjectionTheorem.Theseapproximationsarebintroducedbelow.102.2.1BornApproximationThetotalisthesumoftheincidentandthescatteredi.e.u(r)=u0(r)+us(r).Usingthisin(2.11),have:us(r)=Zo(r0)u0(r0)G(rr0)dr0+Zo(r0)us(r0)G(rr0)dr0:(2.12)InaBornapproximation,thescatteredisassumedtobemuchsmallerthantheincidentthen,ignoringthesecondtermoftherighthandsideoftheequationabove,itcanbeapproximatedas:us(r)ˇuB(r)=Zo(r0)u0(r0)G(rr0)dr0:(2.13)ThisisaorderapproximationwithrespecttocomputingthescatteredHigherorderapproximationscanbeappliedbyusingtheresultsofaBornapproximatedtocalculatethenextorderapproximation.tively,theithorderBornapproxi-mationcanbeevaluatedfromthe(i1)thBornapproximationresultas:u(i)B(r)=Zo(r0)hu0(r0)+u(i1)B(r0)iG(rr0)dr0:(2.14)Asmentionedbefore,theBornapproximationisvalidwhenthescatteredissmallerthantheincidentIftheobjectisahomogeneouscylinder,thenitbecomeseasytoevaluatetheboundsofvalidityoftheBornapproximation.Lettheradiusbeaandthechangeofrefractiveindexwithinthecylinderben.Thenforthiscylinder,thetotalphasechangeawavepassingthroughitwouldundergowouldbe:4˚=4ˇna,11whereisthewavelengthoftheincidentwave.FortheBornapproximationtobevalid,thenecessaryconditionisthatthetotalphasechangeshouldbeshouldbelessthanˇ.Thentherequiredboundbecomesan<4:(2.15)2.2.2RytovApproximationThisapproximationmethodappliesaslightlyntrestriction.Here,thetotalisrepresentedthroughacomplexphase:u(r)=e˚(r).Thenthehomogeneouswaveequationcanberewrittenas:hr2+k2iu=0or,r2e˚+k2e˚=0hence,r2˚+(r˚)2+k2=0andwithsource,r2˚+(r˚)2+k20=o(r):Allthe˚havetheirspatialargumentrdroppedforntoationalconvenience.Startinghereandassumingthat˚=˚0+˚s,where,u0=e˚0(r)andproceedingsimilsrlytotheBornapprox.scenario,thenecessaryconditionfortheRytovconditiontoholdisshowntobe:n>r˚s2ˇ2:(2.16)12Thisconnectsthechangeintherefractiveindexwiththegradientofphase.Amorepracticalformcanbederived:jrn(r)j<p2n0jn(r)n0j;(2.17)where,n0istherefractiveindexofthebackgroundmedium.Thisequationpresentsavalidityconditionwhichisdependentonthegradientofrefractiveindexchangewithinthesampleratherthantheabsolutevalueorthicknessofthesample.ThismakestheRytovapproximationapplicabletobiologicalsamples.2.3FourierProjectionTheorem(FDPT)Thefundamentaltheoryunderlying2D-DTistheFDPTwhichrelatesthescattereddatafromtheRegionofInterest(ROI)duetoincidentplanewavestothe2D-FourierspaceoftheROI[3].Itemploysconditionsofweakscatteringi.e.theBornorRytovapproximations.ThetraditionalisshowninFig.2.1.Iftheobjecto(x;y)isilluminatedwithamonochromaticplanewaveoffrequency0incidentatanangle˚tothehorizontalaxis,the1DFourierTransform(FT)ofthescatteredmeasuredalongthestraightline=lintheco-ordinatesystem(˘;)givesthevaluesofthe2DtransformoftheobjectO(x;y)alongasemi-circulararcAOBinthefrequencydomain,atangle˚asshownintherighthalfofFig.2.1.Thescattereddataand13theobjectfunctionarerelatedbythefollowingequation:U(;l)=j2q202ejq202lO;q2020;(2.18)whereU(;l)represents1DFTofthescatteredu(˘;)underBornapproximation(measuredatline=l),andliesintherange[0;0].Figure2.1:Classicalscanof2DDT(left)andrelationofscattereddatawiththe2DFourierspaceoftheobjectivefunction(right).2.4FilteredBackpropagationAlgorithmStartingwiththeFourierProjectiontheorem,Devaneydevelopedthewell-knownbackpropagationmethodin[2].Inpolarcoordinates,aspresentedin[30],14thebackpropagationintegraltakestheform:a(r;)=Z2ˇ˚=0Z0m=000jmjM(m;˚)e[j2ˇmcos(˚)]md˚:(2.19)In(2.19),a(r;)istheobjectfunctionbeingreconstructedinpolarspatialcoordinates(r;),0isthefrequencyoftheincidentmonochromaticplanewaveand˚beingtheincidenceangle,M(m;˚)isamo1DFTofthescattereddata,asM(m;˚)=U(m;˚)j02ˇ220ej2ˇ0l;(2.20)where0=q202m,a=sgn(m)q2m2,=j(00)and=sgn(m)arcsin120q2m2;(2.21)andalso,couldbefurtherto=12arcsinm0:(2.22)Inordertoreconstructacomplexobjectaccurately,afullknowledgeofM(m;˚)intherange[0;2ˇ]isnecessarytoperformtheintegrationin(2.19),[31].Usingtheprojectiondatafromafull360coverage,thebackpropagationintegralreconstructsalow-passversionofacomplex-valuedobjectfunction.ThenextpartofthethesispresentstheinherentredundanciesinafullprojectiondatasetinDTanddemonstratestwaystoexploitthat.15Part2AccurateReconstructionFromModeratelyLimitedProjectionData16Chapter3DataRedundancyinTomographyAmajorchallengeinmanyrealworldsituationsisthatprojectionmeasurementscannotbegatheredoverfull360viewaroundthetestobject.Withlimitedaccesstotheob-jectanddecreaseinangularcoverage,theavailabledataintheFourierspacedecreases.ReconstructionfromthispartialFourierspacedataleadstomanyartifactsandlossofimportantimagefeatures.Hencealternateschemesareneededforimagereconstructionfromlimitedangularcoverageprojectiondata.Forhighlysparsedataorlimitedan-gularaccessvariousminimization,regularization,estimationtechniquesandstatisticalapproachesarebeingsuccessfullyexploredtomakethereconstructionalgorithmsmorerobusttosparseandnoisydatae.g.[32{34].However,generallytheseareiterativemeth-odsandthetotalcomputationtimedependsontheconvergencerateofthealgorithm.Asinglestepmethodwouldalwaysbefastanddesirableprovideditcanhandlethelimitedavailabilityofdata.In[30,35,36],anovelalternativeapproachformoderatelylimitedangularaccesswasintroduced.Itwasshownthatusinginherentredundanciesintheprojectiondatafromtheconventionalsetup,exactreconstructionispossiblewithdatafrom[0;3ˇ=2]coverage.Thisredundancyandthereconstructionmethodfromlowercoverageutilizingthisis17explainednext.ConsiderthetwoarcsOAandOBinFig.2.1fromthesemicircleAOB.Thetwoarcsindividuallytraversethetransformspace(i.e.theFourierspace)astheprojectionanglechangesbetween[0;2ˇ].NowconsidertheirtraversalsintheFourierspaceindividuallyforangularcoverageof[0;3ˇ=2].ThisisillustratedinFig.3.1below.IndividuallyeachhalfdoesanincompletetraversaloftheFourierspaceasshowninFig.3.1(a)and3.1(b).However,ifsuperimposed,asseeninFig.3.1(c),theentireFourierspaceiscoveredwithsomeareasofoverlap.Thekeypointisthatat270thereisinacompletecoverageoftheFourierspace.Thisscanrangeof[0;270]isreferredtoastheminimalscanangleandistheminimalangularcoveragerequiredforexactreconstruction[30].Tobetterappreciatetheprinciple,theFourierspacedomainisre-plottedinamocoordinatesystem,wherethespatialfrequencyisplottedalongx-axisandtheangularcoveragealongy-axis.Physically,itcanbeviewedasstraighteningoutthearcsAOBfortprojectionanglesandstackingthemupontopofeachothersequentially.Inthislayout,theentireFourierdataspacecanbedividedintofoursub-regionsA;B;CandDasshowninFig.3.1(d)wheretheboundariesforthefourregionscanbeexpressedasA=[jmj0;0˚<2+ˇ=2],B=[jmj0;ˇ=2+2˚<2+ˇ],C=[jmj0;ˇ+2˚<3ˇ=2]andD=[jmj0;3ˇ=2˚<2ˇ].Asseenin(2.22),isafunctionofmandsotheregionshavenonlinearboundaries.FromFDPtheoremthefollowingperiodicityholds[37]:M(m;˚)=M(m;˚+ˇ2);(3.1)18Figure3.1:(a)Fourierspacecoveragefor270angularaccessbysegmentOBin(b)sameforsegmentOAof(c)Superpositionofthetwocoveragesfrom(a)and(b).(d)TheFourierdata-spaceinalternateco-ordinatesystemwithangularcoveragealongy-axisandthefrequencyalongx-axis.whichalsoimpliesthatforeverypointinregionA(orB),thereisapointhavingequalvaluefortheFouriercotinregionC(orD).Thus,theknowledgeofM(m;˚)inregionsAandB,makesinformationinCandDredundant.ThisredundancycanbehandledbynormalizingthedataspaceusingappropriateweightTheweighteddatasetM0(m;˚)canbeasM0(m;˚)=w(m;˚)M(m;˚),wherew(m;˚)theconditionw(m;˚)+w(m;˚+ˇ2)=1:(3.2)19ItshouldbenotedthatsinceregionDisunavailableina270coveragewesetw(m;˚)=0inregionDandcorrespondinglyw(m;˚)=1inregionB.ForregionsAandC,anyweightfunctionisvalidaslongasit(3.2).UsingtheweighteddatasetM0(m;˚)wecanapplytheregularbackpropagationalgorithmforreconstruction.ThisiscalledMinimal-ScanFilteredBackpropagation(MS-FBPP)whichinvolvesevaluatingthefollowingintegralaW(r;)=12Z3ˇ=2˚=0Z0m=000jmjM0(m;˚)e[j2ˇmcos(˚)]md˚:(3.3)Thisintegralcanintheoryexactlyreconstructanimagefroma270angularcoveragebyutilizingdataredundancyinprojectiondata.Theweightsw(m;˚)canthenbeusedtoclassesofbackpropagationalgorithmsforimagereconstruction.Anexampleofweightfunctionsintroducedin[30]isgiveninequationbelow:w(m;˚)=8>>>>>>>>>>>><>>>>>>>>>>>>:sin2hˇ4˚ˇ=4+i;inA;1;inB;sin2hˇ43ˇ=2˚ˇ=4i;inC;0;inD:(3.4)ThiswillbeusedasareferencelateroninSection4forcomparisonwiththeweightfunctionsthatareproposedinthisthesis.Theof(3.4)willbereferredtoasthesine-squaredhereon.ThisisaveryelegantandsimpledesignedtohavecontinuityacrosstheboundariesbetweenregionsA;B;CandD.Todemonstratetheof20Figure3.2:DemonstrationoftheMS-FBPPconcept(a)realpartoforiginalimage,(b)FBPPreconstructionfrom360coverage(c)FBPPreconstructionfrom270coverageand(d)MS-FBPPreconstructionfrom270coverageMS-FBPP,asamplereconstructionisperformedonaShepp-Logantypephantomwithcomplexparameterdistribution.TherealpartofthephantomisshowninFig.3.2(a)andtheimaginarypartinFig.3.3(a).ReconstructionfromregularFBPPandMS-FBPPusingweightsof(3.4)aregiveninFig.3.2andFig.3.3.TheimagesshowtheMS-FBPPalgorithmscapableofgeneratingaccuratereconstructionsfrom270(equivalenttofullcoverage),whereastheregularFBPPimageshowsconsiderabledistortionat270.WeightwhicharediscontinuousacrossboundariesofthefourregionsinFig.3.1(d)cangiverisetoartifacts,especiallyincaseofdiscretedata.Further,foreachclassofweights,itsdistributioninfrequencyspaceofFig.3.1(d)alsodeterminestheperformancewhentheavailablecoverageisbelow270.Thisisbecause,CandDare21Figure3.3:DemonstrationoftheMS-FBPPconcept(a)imaginarypartoforiginalimage,(b)FBPPreconstructionfrom360coverage(c)FBPPreconstructionfrom270coverageand(d)MS-FBPPreconstructionfrom270coveragecomplementarytoregionsAandBrespectively.AntweightfunctionsetwouldbethatwhichspansmostoftheregionsAandB,thuslimitingtherequirementtoaccessregionsCandD.Insuchweightscangenerategoodreconstructionsevenwhentheangularcoverageislessthan270.Thenextsectionexplainsasystematicapproachtogenerategeneralclassesofweightfunctions.3.1GenerationoftWeightFunctionsForlowerangularcoverages,thealgorithmusingsine-squaredweightsresultsintdistortions.InthissectionatechniqueisexploredthattlyusestheredundanciesintheFourierspacedatausingtheconventionalsetup[38].Thistechniquecanreconstruct22betterimages(thanregularFBPP)elyoveranyrangebetweenˇto3ˇ=2.Thisisacrucialdevelopment,asthedemandsonangularaccessforcomplexvaluedobjectreconstructionisloweredconsiderably.Theprojectiondatasetsareusedoptimallytogetenhancedreconstructionsfromlowerangularcoverages.Also,thisisadirectrecon-structionmethodwhichdoesnotemployanyerrorminimizationalgorithmsandhenceisfasterandaccurateoverangularcoveragesbetween180-270.Fromprevioussection,weseethattheweightsinregionsBandDare1and0respectively.NoticethatweightsinregionCcanbegeneratedfromweightsofregionA,becauseforanypoint(m;˚)inregionC,thepoint(m;˚+ˇ2)inAisequivalentdueto(3.1),andwegetw(m;˚)=1w(m;˚+ˇ2),using(3.2).ThusitisttogenerateweightsfortheregionAonly.Furthermorefrom(3.2),thenon-negativeweightsareboundedaboveby1.SoinregionA,foranym,thefunctionw(m;)=:F()ison[0;2+ˇ=2],andtakesvaluesbetween0and1.Howeveritisdesirabletohaveweightswhicharecontinuousattheboundariesbetweentworegions.Weightswhicharediscontinuousattheboundarieswillgenerateartifactsincaseofdiscretedatasetsasnoticedin[30].Hereweproposeanapproachtogeneratetheweights,byusingcumulativedistributionfunctions(cdf)tomodelF(),whichareguaranteedtobeboundedwithin0and1.Toobtaincontinuousweights,weusecontinuousFwithF(0)=0;andF(2+ˇ=2)=1:(3.5)ThiswillensurethatweightsarecontinuousattheboundarybetweenregionsAand23B,andconsequentlyattheboundariesbetweenregionsBandC,andCandD.Thisapproachwouldallowustochooseweightsfromanumberofcdfs.Inthisdissertation,weprimarilyusebeta-cdftogenerateweights.Thestandardbeta-cdfisas:F(xja;b)=Zxf(tja;b)dt:(3.6)Wherea>0,b>0,andfisthestandardbetaprobabilitydensityfunction:f(tja;b)=8>>><>>>:1B(a;b)ta1(1t)b1;0t1;0;otherwise;(3.7)andB(a;b)=R10ta1(1t)b1dt.Weobtainfamilyofbeta-cdf'sbychangingvaluesofaandbin(3.7),asshowninFig.3.4.Noticethat,thestandardbeta-cdfhassupport[0;1],whileinregionAforam,weneedtoweightsfor˚2[0;2+ˇ=2].Thiscanbeachievedbysubstitutingx=˚2+ˇ=2in(3.6).ThecorrespondingweightprointhefrequencydomainareshowninFig.3.5.TheplotsinFig.3.4canbeusedtounderstandhowtheweightswillbedistributedinRegionsAandC.Fig.3.5givesusefulinsightonchoosingoptimalparametervalues.Forexample,withcombinationsa=2;b=5ora=6;b=1,regionAisnotwellcovered,whereasfora=0:4;b=6,regionAhasbeenalmostfullycoveredwithnearunityweightsleavingRegionCwithmostlynear-zeroweights.ThiscombinationisexpectedtobetterutilizedataredundancythantheothercombinationsshowninFig.3.4.ThiscanbefurtherillustratedthroughFig.3.6andFig.3.7.Fig.3.6showssomeweightdistributionsintheFourierspace(inthemoco-ordinatesystem).Thebeta-24Figure3.4:Beta-cdfplotsfortvaluesoftheparametersaandbcdfparametersusedtogeneratetheseweightsareshownininsetwhitetext.Fig.3.7showsthereconstructedrealpartsoftheimagesbyusingtheseweights.TheweightswhichcoverregionAmorecompletelyalsogivebetterreconstructions.Itshouldbenotedthatespeciallyforcoverageslessthan270,wereceivelessinforma-tionfromC,henceanoptimumweightfunctionshouldspanmostofregionAwithnearunitweight.Sincetheweightsarecontinuousacrosstheboundariesoftheregions,thelowerboundaryofA(withregionD)startsfromzeroandendswithunityatthebound-arywithB.ThetransitionfromzerotounityshouldbeadequatetoretainasmuchinformationaspossiblewithinregionA.ThenthelossofinformationinregionCwouldnotthereconstructionquality.Inthisthesis,wedemonstratetheofusingcdfbasedweightsinimagereconstructionatsub-minimalangularcoverage.Todothis,optimumvaluesofparameterswereheuristicallydeterminedinthefollowingmanner:forthebeta-cdf,aparametricsweepovertherangeofa2[0:2;3];b2[1;6]wasperformedand25Figure3.5:ImagesshowingweightdistributionsinFourierdomaingeneratedbypara-metricvariationofthebeta-cdf(usingtheparametersshowninFig.3.4).Frequencyisplottedalongabscissaandangularcoveragealongordinate.thecorrespondingweightdistributionsweregenerated.Reconstructionswereperformedwiththeseweightsforasub-minimalcoverageof200.Theweightcombinationwhichgavetheleastdistortioninthereconstructionandmaintainedhighestcorrelationwiththeoriginalimagewaschosenastheoptimumset.Withinthisrange,thecombinationa=0:4;b=6gavebestresultsandisusedforimagereconstructioninthenextsection.Similarapproachcanbeusedtogenerateweightfunctionsfromothercumulativedistributionfunctionsaswell,forinstancewiththegamma-cdf.However,sincethegammadistributionhasunboundedsupport,asuitabletransformationoftheargumentisrequiredtoensurethattheweightsareconstructedwithcontinuitypropertiesattheboundaries26Figure3.6:ImagesshowingweightdistributionsinFourierdomaingeneratedbyparamet-ricvariationofthebeta-cdf.Theparametersaandbusedforeachweightdistributionareinsetineachplot.Frequencyisplottedalongabscissaandangularcoveragealongordinate.asdiscussedabove.Detailsaboutconstructingtheweightswithgamma-cdfaredescribedinappendix-A.Forthiscase,theparameterswerevariedintherangea2[0:1;3:1];b2[0:1;3:1].Thebestparametersetfoundfromthisrangewasa=2:1;b=0:1.Inthefollowingchapter,resultsfrombetaandgammadistributionsusingtheseoptimumparametersforeachdistributionwillbepresentedandcomparedwiththeresultsfromusingweightsgivenin(3.4).Theirperformanceunderthepresenceofnoisewillalsobeevaluated.27Figure3.7:CorrespondingreconstructionsfromusingtheweightdistributionsinFig.3.628Chapter4AccurateReconstructionsforModeratelyLimitedAngularMeasurementsInthischapterresultsfromsimulatedprojectiondataforDTarepresented.Thetestimageiscomplex.BoththerealandimaginarypartsoftheimageareinmoversionsoftheShepp-Loganphantom,astandardmodelusedtovalidatecomputedtomographyalgorithms.TherealandimaginarypartsofthetestimageareshowninFig.3.2(a)and3.3(a).Theprojectiondatafromthephantomwascomputedfollowing[30,37].Theimagematrixis128128pixelswithpixelsizeof8.Theimagehasanareaof1616.Theobjectiveofthissectionofthethesiswastoaproceduretogenerateoptimumweightswhichcanexploittheredundancyforangularcoveragesbelow270andupto180,whereredundancyisstillpresentintheprojectiondata.4.1NoiselessReconstructionProceedinginthemannerdescribedintheprevioussectiontogenerateweights,thefollowingoptimumparametersfortcdfswereused:forbeta-cdf,a=0:4;b=6;29Figure4.1:Reconstructedrealpartfromcomplextestimageundernoiselessconditions.Theleftcolumnshowsreconstructionfrom270coverageandrightcolumnshowsrecon-structionfrom200coverage.(a)-(b)usingregularFBPP,(c)-(d)usingsine-sqweights,(e)-(f)usinggamma-cdfweights,(g)-(h)usingbeta-cdfweights30Figure4.2:Reconstructedimaginarypartfromcomplextestimageundernoiselesscondi-tions.Theleftcolumnshowsreconstructionfrom270coverageandrightcolumnshowsreconstructionfrom200coverage.(a)-(b)usingregularFBPP,(c)-(d)usingsine-sqweights,(e)-(f)usinggamma-cdfweights,(g)-(h)usingbeta-cdfweights31forgamma-cdf,a=2:1;b=0:1.ReconstructedimageshavebeenplottedfromregularFBPPandMS-FBPPusingtweightfunctionsforcoverages270and200(anexampleofsub-minimalangularcoverage).BothrealandimaginarypartsareshowninFig.4.1and4.2respectively.Thereconstructionsshowthebeta-cdfandgamma-cdfbasedweightsgenerateaverystablereconstructioneveninlowerangularcoverageof200,withbeta-cdfperformingslightlybetteroverall.TocomparetheperformanceoftherentMS-FBPPalgorithmsquantitatively,weusetheirMean-Absolute-Error(MAE)withrespecttotheoriginalimage.TheMAEiscalculatedastheabsolutemeanpixel-by-pixelbetweentheoriginalandrecon-structedimage:MAE=1nPjimor(i)imre(i)j,whereimor(i)istheintensityoftheithpixelintheoriginalimageandimre(i),theintensityoftheithpixelinthereconstructedimageandnisthetotalnumberofpixelsintheimage.Theerrorsinrealandimaginarypartsofimagewerecalculatedseparately.At200coverage,fortherealpartoftheimage,thebeta-cdfbasedreconstructionhada30:77%lowererrorthanregularFBPP,whilethegamma-cdfbasedreconstructionyieldeda29:11%lowererror.Asimilartrendisseenfortheimaginarypartoftheimage.Thesine-squaredbasedweightsgiveaccuraterecon-structionsat270,butbelow270theyprogressivelydeteriorate.Theseareclearlynotoptimumchoicesforcoverage<270.Forexample,at200coverage,thequalityofrecon-structiondegradesforboththeregularFBPPandsine-squaredweightedFBPP.However,thelatterhasahighererrorthantheregularFBPPreconstruction(2:46%higherinrealpartofimage).Amoredetailederror-analysishasbeendonewithnoisydatainthenextsubsection.Below180coverage,theredundancydisappearsandusingweightsalone,inprinciplecannotproduceabetterreconstructionthanregularFBPP.So,reconstructed32imagesarenotshownforfurtherlowercoverage.However,itshouldbenotedthatforsuchlowercoverage,reconstructionfromun-optimizedweightswillgeneratehighererrorsthanregularFBPP.Thisisalsoevidentfromthesine-squareweightedreconstructionsforsub-minimalcoverage.4.2ReconstructionwithNoisyDataNoiseisanintegralpartofanymeasurementsystem.InaDTsetup,noisemayarisefromrandominhomogeneitiesinmediumormaybeintroducedbytheexperimentalprocedure.Toaccountforthese,noisyreconstructionhasbeenmodeledasastochasticprocessinliterature[39],[40].Reconstructionfromnoisydataisnecessarytoexaminethereliabilityofthesealgorithmswhenappliedtopracticalsystems.TheMS-FBPPalgorithmsareexpectedtorespondtonoisydatamodelstly.Toconsidertheofallnoisesources,itwasassumedasttoconsiderawhiteGaussiannoisedistributioninthescattereddata[37].AnadditivewhiteGaussiannoise(AWGN)withtvarianceshasbeeninjectedtotheanalyticallycomputedprojectiondatatogiveentnoiselevels.Toobservetheofnoise,wecomparedthereconstructionfromtheweightedMS-FBPPalgorithmswithregularFBPPusingtheprojectiondatainjectedwith3-dBAWGN.Thereconstructedimagesfromnoisydatausingbeta-cdfweightsfortangularcoveragesintherangeof[200;270]aregiveninFig.4.3andFig.4.4.Weusehereweightsbasedonbeta-cdfwitha=0:4,b=6,whichearliergavebestresultswithnoiselessdata.Thereconstructionsshowrobustnessofthealgorithmtonoiselevelsthatcanbeconsideredtobereasonableingoodexperimentaldata.33Figure4.3:Reconstructionofrealpartofimagefrom3dBawgnprojectiondatausingbeta-cdfweightsforangularcoverages(a)270(b)250(c)220(d)200Fig.4.3andFig.4.4showthatthebeta-cdfbasedweightsarecapableofmaintainingallthefeaturesandwithouttdistortionsupto220with43:1%improvementofMAEoverregularFBPPinrealpartand38:7%inimaginarypartoftheimage.Thereconstructionat200isalsoalmostdistortionlesswiththeerrorimprovementbeing27:8%and19:4%fortherealandimaginarypartsrespectively.TheresponsesarestableandtheimagesarenotnoticeablyduetothenoiseinjectionasseenintheseAdetaileddiscussionoftheperformanceintermsofMAEisgivennext.TheMAEcalculatedforthetweightsattangularcoveragesareplotted34Figure4.4:Reconstructionofimaginarypartofimagefrom3dBawgnprojectiondatausingbeta-cdfweightsforangularcoverages(a)270(b)250(c)220(d)200inFig.4.5andFig.4.6.Theplotsshowthatasthecoveragegoesfurtherbelow270,thebeta-cdfandgamma-cdfweightsareabletogenerateMAEswhichremainlowerthanregularFBPPandareverysteadyupto200.Forthebeta-cdfbasedreconstruction,asthecoveragedecreasesfrom270to200,thevalueofMAEincreasesbyonly2.33%intherealpartand1.45%intheimaginarypart.Forgamma-cdfbasedreconstruction,thenumbersare4.31%and2.64%respectively.Forcoveragesbelow200,astheredundancyislost,thesetwoMAEsincreaseandslowlyconvergetowardstheMAEofaregularFBPPreconstructionaround180.Forthesine-squaredbasedweights,theMAEsarealmost35equaltotheothertwoweights(betaandgammacdf)intheinterval[250;270],butrapidlyincreasesasthecoveragereduces,andbecomegreaterthantheregularFBPPandothertwocdfweightedreconstructions.At200coverage,theMAEoftherealpartoftheimageincreasesbyasmuchas46.05%ofitsvalueat270coverageandthatoftheimaginarypartby48.62%.TheMAEplotsfortheregularFBPPalgorithminFig.4.5andFig.4.6maylookcounterintuitive.Thisisbecausetheerrorincreasesastheangularcoverageincreasesfrom180to270.However,itshouldbenotedthatstartingfrom180coverageandabove,thereareregionsintheFourierspacewherethereisoverlapfromthetwohalvesOAandOBofthesemi-circulararcAOBinFig.2.1.TheregularFBPPdoesn'tapplyweightstothedataspacetoaccountforthesepartialoverlapsandhencegiveshighererrorsinreconstruction.At360coverage,asthereiscompletecoveragebyboththearcsOAandOB,weightingthedataspaceisnotrequired.Followingthis,itisfoundthaterrorincreasesfrom180coveragetoamaximumat270,wherethereismaximumasymmetrywithrespecttooverlappingcoverageinFourierspacebythetwohalfsemi-circles,OAandOB.Weightingbecomesmostimportantat270.Beyondthat,theimportancedecreasesagainandvanishesat360coverage.Forthisreason,anerrorincreaseisseenbetween180and270coverage.Thesolutiontothisprobleminthatcoveragerangeistonormalizetheprojectiondatawithoptimalweightsbeforeapplyingthebackpropagationalgorithm.ThepercentageimprovementsofMAEforallthethreeclasseswithrespecttotheregularFBPPareplottedinFig.4.7andFig.4.8.Alltheweightsshowmaximumimprovementat270,anditdecreasesasthecoveragegetsmorelimited.Thedegradationofsine-squaredismuchgreaterthanthecdfbasedTheplotsshowthatat36180,withthedisappearanceofredundancywithintheprojectiondata,theMAEsforregularFBPPandthatofbeta-weightedMS-FBPPconverge.Incontrast,forthesine-squaredweights,theMAEsteadilyincreasesandbecomesgreaterthantheMAEfromregularFBPP.Thisisexpectedanddemonstratestheenessofthebeta-cdfbasedweightsasanoptimalchoice.Thegamma-cdfbasedreconstructionbehavessimilarlywithaslightlyhigherMAE(1.66%higherthanbeta-cdfreconstructioninrealpartofimageand1.32%higherfortheimaginarypartoftheimageat200coverage).Figure4.5:MAEcalculatedattcoveragesforrealpartofreconstructedimagewithregularFBPPandMS-FBPPusingtweights4.3SummaryInthispartofthethesis,newapproachtoexploitdataredundancywithinthetraditional2DDTsetuphasbeenexplored.Usingcumulativedistributionfunctions,especiallythebeta-cdf,itwasshownthatdistortionlessreconstructionsofcomplex-valuedobjectfunc-37Figure4.6:MAEcalculatedattcoveragesforimaginarypartofreconstructedimagewithregularFBPPandMS-FBPPusingtweightsFigure4.7:PercentageimprovementofMAEfromtweightsoverregularFBPPattcoveragesforrealpartofreconstructedimagetionsarepossibleevenatangularcoverageof200.Theadvantagesofthisobservationarenumerous.Themajorbisthatitreducestheangularscanningrequirementsforaccuratereconstructions.Thisalsoimpliesshorteraccesstimesforcollectingrelevantprojectiondata.Inmedicalapplicationsthiscanmeanaloweramountofexposureto38Figure4.8:PercentageimprovementofMAEfromtweightsoverregularFBPPattcoveragesforimaginarypartofreconstructedimagetheinterrogatingenergyandalso,fewerartifactsduetotemporalvariationscausedbymovementsofthepatient.Forstilllowercoverages(<180),theredundancyinthetomo-graphicdatasetvanishesandalternateapproachesarebeingexploredforapplicationtoDTsetups.Inthenextpartofthethesis,reconstructionalgorithmsunderthecompressedsensingregimehavebeendeveloped.Thesefallunderiterativetechniquesandtheaimistosolveanoptimizationproblem,thesolutionofwhichisinagreementwiththeavailableprojectiondata.So,thesearenotfastone-stepreconstructionsasthoseofthispartofthethesis,however,atthecostofalgorithmiccomplexityverysparseorhighlylimiteddatarequirementscanbeachievedforfullimagerecovery.Thisisthetopicforthenextpartofthisthesis.39Part3Reconstructionfromhighlylimitedprojectiondata:Compressedsensingapproach40Chapter5OverviewRecentlyahugethrustareaofresearchhasbeeninthesocalled'compressedsensing'regime[1,41{43].Thestrengthofthisareaisthatithasgivenamathematicalbackgroundandstructurewhichensuresverylowerrorguaranteestosolutionsfromhighlyunder-determinedsystems.Itisaradicallynewwayofsamplingandrecoveringsignalsatsub-Nyquistrate.ThetraditionalboundsputbytheShannon-Nyquisttheoremscanbedefeatedundercertainconditions.Fortunatelytheseconditionsaremetinanumberofimagingandsensingapplications.Hencecompressedsensingbecomesaveryimportantnewrealmofsignalsamplingandrecovery.ThischaptergivesabriefbackgroundandintroductiontothisemergingTheimportanceofcompressedsensingformedicalimagingisalsodescribed.Themotivationtousethisframeworkformicrowaveimagingisexplained.Theproposedframeworkandapproachesarepresentedinthesucceedingsections.5.1BackgroundTraditionally,anyanalogsignalreconstructionislimitedbytheShannon-Nyquistthe-oremwhichputsalowerlimitontheminimumamountofinformationrequiredforre-constructingthesignalexactly[44].Whenasignalissampled,thistheoremstatesthatthesamplingratemustbeatleasttwicethehighestfrequencypresentinthesampled41signal.ThisisknownastheNyquistratewhichprovidestheoreticallimitsonsamplingrequirements.Thisimpliesthathigherthefrequencycomponentsinthesampledsignal,largerthenumberofsamplesormeasurementsnecessarytoretainadequateinformation.Thisinturnimplieshighertimeandacquisitioncomplexity.However,recentlyitwasfoundthatundercertainconditionssignalscanbesampledatratesmuchlowerthantheNyquistrequirementwithoutanyntlossofinformation[43,45{47].Thisremark-ablepossibilityislargelyduetothefactthatformostpracticalsignals,ofbandwidthsayB,allthecomponentswithintherangeBdonothaveequalamountofinformation.ThusthesamplingfrequencydictatedbytheNyquisttheoremismuchhigherformanyprac-ticalsignals.Compressedsensinghasivelyexploitedthisloopholewithgreatsuccess.TheofcompressedsensingwastriggeredbytwogroundbreakingpapersbyDonoho[43]and[45]andfollowedbyahostoffollowuppaperswhichmathematicallyformalizedthetheory.Theeldbfromfruitfulcombinationoftheoriesinappliedmathematics,statisticsandelectricalengineeringwithapplicationsintdisciplinesrangingfromimageprocessing[48],radartechnology[1],samplingtheory[49],medicalimaging[50].Infact[50]openeduptheCStheoryasagreattoolformedicalimaging.MRIprovedasagreattodemonstratethepotentialbofCSandaconsiderablevolumeofworkfollowedonCSbasedMRIreconstruction:[51{55]etc.tomentionafew.SoonahugeinterestwasgeneratedinapplyingCStotmedicalimagingschemesandtomographyingeneral:[56{60]etc.TheavailableliteratureprovestheusabilityoftheCSframeworkfortomographicreconstructions.TheaimofthisresearchistosetupaCSframeworktoreconstructcomplex-valuedobjectfunctionfromlimitedangularprojection42datainntomography.5.2CSTheoryCompressedsensingaimstoreducethenumberofminimummeasurementsrequiredtocompletelydescribeasignalbyexploitingitscompressibility.Thiscanbeexpressedintermsofsparsityofasignal.AS-sparsesignalf2RnisasignalwhichhasatmostSnon-zeroelements.ThegoalistobeabletocompletelyreconstructaS-sparsesignalfofdimensionnfromMmeasurementswhereMˇSormarginallymore.Todothis,themeasurement(ordataacquisition),signalhandlingandimagerecovery(reconstruction)hastobedoneinacertainframeworkandadheringtosomeconstraints.TheseareactuallytheveryconditionswhichenableustodefeattheShannonsamplingrateonagrandscale.Theserequirementsareenumeratedbelow:Thesignalofinterestfshouldbesparseorcompressibleinsomedomain.Astablemeasurementmatrixmustbeavailablewhichcantransformthesparsesignal,f2RNtoy2RMwithoutanylossofinformationduetothedimensionalreductionfromNtoM.ThisconditionofisoftenreferredtoastheRestrictedIsometryProperty(RIP).Areconstructionalgorithmwhichcanrecovertheoriginalsignalfromthemeasure-mentsy.Forcompressedsensingframework,l1-normminimizationisthede-factoalgorithmofchoice.43Thesepropertiesandrequirementsarediscussednext.Acuriousfactisthatmanyphysicalsignalsofinterestdoinfactabidebytheseconditions.Hence,compressedsensingisapplicabletoavarietyofscenarios.Thus,thedevelopmentofthisnewtheorygainedahugeimpetusoverthelastfewyears.Ithasbecomeoneofthemosthotlyresearchedtopicsunderimagereconstructionalgorithms.5.2.1SparseBasisRepresentationInthepresentworld,informationtravelsovertheinternetatanenormousrate.Largevolumesofdataarestoredinserversacrosstheworld.Allthiswouldreallyhavenotbeenpossiblewithouttheavailabledatacompressiontechniques.Ahugeamountofre-searchhasbeendoneinthisarea.Themostfamousworksinthisaspectareprobablythewavelettransformsanddiscretecosinetransforms(DCT),seee.g.[61,62].Thesetechniquesareroutinelyusedforreducingstorageoflargeimages.Thisisdonebyex-ploitingsparsityofimagesinthesebases.Anotherveryimportantsparserepresentationistheimagegradient.Inmanypracticalcases,especiallyinmedicalimages,theimagesthemselvesarenotsparse,however,theirgradientmagnitudeimageorGMIissparse.Waveletsareagreatexampleofsparsebasissetforimages.Thismeansthatwhenanimageistransformedtoitswaveletdomain,onlyaveryfewcotsinthatdomainhavenon-zeroortlyhighvalues.So,ifthesecotsarethresholded,theresultingvectorofcotsissparsewithpracticallynolostinformation.Tostateitmathematically,considerasignalvectorx2RNwhichcouldbeanimagewithNpixels.Letitbeexpressibleinsomeorthonormalbasis=[ 1; 2;:::: n],suchthat:44x(t)=NXi=1si i(t);(5.1)wheresi=<x; i>,arethecotsofxindomain.Here,tisthetimeindexorpixellocationdependingonwhetherthexisatimesignalorpicture.Thenxcanbereadilyexpressedasx=s;(5.2)wheresisthecotsequence.isamatrixwith 1; 2;:::: nascolumns.Nowtheimportanceofsparsitycanbeexplainedasfollows:sinceisasparsebasisofx,thelowvaluedcotsofscanbediscardedwithoutmuchlossofinformation(orimagequality).Letxk(t)betherecoveredsignalbykeepingtheKlargestcotsofs,i.e.,xk:=skwhereskisthecots'vector(si)withallbutKhighestcotssetto0.Thisvectorskissparsebecauseonlyafewofitsentriesarenon-zero,i.e.K<<n.Inliterature,avectorlikeskiscalledK-sparse,meaningthereareatmostKnon-zeroentriesintheentirevectorsk.beinganorthonormalbasis,thefollowingrelationholds:kxxkk2=ksskk2:(5.3)Ifthesortedmagnitudesofsdecayveryrapidly,thenskandswouldbealmostequivalent.Thus,theerrorkxxkk2wouldbesmallandxkwouldbeaveryaccurateapproximationofx.Asanexample,inFig.5.1thelossduetorejecting>95%ofthecotsinthewaveletdomainisvisuallyalmostimperceptible.Ontheleftistheoriginalgrayscaleimageandazoomed-insection.Ontheright,thecorresponding45Figure5.1:(a)Sampleimage(b)zoomed-inview(c)Compressedimagebyretaining<5%oflargestcotsinwaveletdomain.(d)zoomed-inviewofthecompressedimagecompressedimages(compressedinwaveletdomain)areshown.Thisdemonstratesthateventhoughtheoriginalimagebyitselfisnotsparse,itcanbeelysparsiinsomesuitabledomain.Thenwithrespecttothisdomain,thenumberofrequiredmeasurements(inourcase,projectiondata)wouldbefarlessthanintheoriginalcase.Apointtonotehereisthatcompressedsensingonlyclaimstoreconstructsparsesignals.Sointhesamplingtheoremisnotreallyviolated.Howeverthemainchallengeistoidentifythesparsitydomainandthendesignanesamplingandreconstruction46system.5.2.2SensingMatrix:TheRestrictedIsometryPropertyConsiderasensingmatrixrepresentingthedataacquisition.Forexample,intomog-raphy,istheFouriermatrix.Letdirectlycompressthesignalwhilesensingit.Thatis,asmallnumberofmeasurements(e.g.projectiondataintomography)retainalltheinformationwithintheoriginalsignal.Letitbealinearmeasurementprocessthatcol-lectsMdatapoints(M<N).ThenisaMNmatrixandtheoutputyisaninnerproductofxwiththecolumnsofThenusing(5.1),wecanwritey=x=s=s:(5.4)where:=isanMNmatrix.Themeasurementorsensingmatrixisandindependentofx.Intraditionaltheory,sinceM<N,thesystemin(5.4)isunderdeterminedandingeneralthesolutionisill-posed.However,thesparsityofxinthedomainalleviatesthisissue.ThenecessaryandtconditionforthisMNsystemtohaveguaranteedstabilityisthefollowing:ifforanyvectorvwhichhas3Ksparsity,ifthefollowingrelationholds:1kvk2kvk21+(5.5)thenastableinverseexistsforallK-sparseandcompressiblesignals.ThisisthesocalledRestrictedIsometrypropertyorsimplyRIP.ItmightbeanappropriatetointroducetheformalofRIPhere.Foreachintegerk=1;2;:::,theisometryconstantk0ofamatrix47asthesmallestnumbersuchthat(1k)kvk2kvk2(1+k)kvk2;(5.6)holdsforallk-sparsevectorsv.AmatrixhastheRIPoforderkaslongasKisnottooclosetoone[41].ItcanbesurmisedthatwhentheRIPholdsforthenforKsparsesignals,willapproximatelypreservetheEuclideandistanceduringsensing(oracquisition).ThisfurthermeansthattheK-sparsevectorscannotbeinthenullspaceofThisisbecause,ifthereisaK-sparsevectorinthenullspaceofthenx=0)kxk22=0.Thenin(5.6),wemusthavek1,whichgoesagainsttheofRIPwherek<1.Thisisbasotherwise,therewouldbenowayofpreservingthesesignals.AnimportantcorollaryisthatifRIPforK-sparsesignals,thenthesolutionxtothesystemy=xcanberecoveredandfurther,thesparsestsolutiontothesystemisuniqueandtheexactsolution[63].5.2.2.1IncoherentsamplingStabilityofthereconstructioncanalsobeensuredbyanotherapproach.Ifthemeasure-mentmatrixcanbeensuredtobeincoherentwiththesparsebasisi.e.Thecolumnsofcannotberepresentedbylinearcombinationsofcolumnsofandviceversa,thenandaresaidtobeincoherent.Anintuitiveexamplewouldbeimpulses(deltafunction)for˚iandFouriersinusoidsfor i.Formally,coherencebetweenthesensingmatrix48andsparsebasisisas;=pNmax1k;jNj<˚k; j>j:(5.7)Coherencegivesanestimateofthecorrelationbetweenthetwomatrices.So,foragoodsensingmatrix,thecorrelationwiththesparsifyingmatrixshouldbeminimum,i.e.shouldbesmall.Therangeforis:;2[1;pN].Theupperlimitisaresultofthefactthattheinnerproductj<˚k; j>1fortwounitvectors.ThelowerlimitisduetoParseval'srule,where,foreachj,PNk=1j<˚k; j>j2=jj jjj22=1,[41].Averysimpleexampleofsuchanincoherentpairwouldbethespikebasiswith˚(k)=(tk)andtheFourierbasiswith j(t)=n1=2ei2ˇjt=n.Herecanbeviewedastheclassicalsamplingschemeintimeorspace.Thetime-frequencypairgives;=1providingmaximumincoherence.Thisincoherenceisnotlimitedtoonedimension,andvalidforhigherdimensionsaswell.Intypicalpracticalapplications,randommatricesaremostlyincoherentwithanybasis[41].Ifanorthobasisisselectedrandomlyfromanuniformdistribution(e.g.bysamplingnvectorsontheunitsphereindependentlyanduniformly)andorthonormalized,thenwithhighprobability,thecoherencebetweenandwouldbelowandoftheorderofp2lognTosummarize,thesensingmatrixmusthaveRIPpropertyorbeincoherenttothesparsebasisforcompressedsensingtobesuccessful.HoweverprovingthataparticularmatrixdoesindeedhaveRIPisanNP-hardinverseproblem.Fortunately,someclassesofmatriceshavealreadybeenproventohaveRIP.Ifthesematricescouldrepresentparticularsensingordataacquisitiontechniques,thenthereconstructioncan49beperformedunderthecompressedsensingregime.AveryimportantcategoryofRIPmatricesisapartialFouriermatrix.ApartialFouriermatrixisformedwhentheMrowsofthematrixarechosenrandomlyfromafullNNFouriermatrix.ThenRIP.Thisimpliesthatthecompressedsensingframeworkcanbeappliedtotomographicreconstruction,astheprojectionsinatomographicacquisitionaredirectlyrelatedtotheFourierork-spaceoftheobjectbeingprobed.ThishasinfactgeneratedahugeinterestinapplyingCStechniquesforimagerecoveryfromhighlysparsetomographicdata.5.2.3ImageReconstructionTheRIPgivestheoreticalguaranteethataK-sparsesignalcanbefullyrecoveredfromMmeasurementsgivenbythemeasuredvectory.However,therecoveryprocesshasnotbeenaddressedthere.TherecoveryprocedureshouldbeabletoregeneratetheN-lengthsignalxorthesparserepresentations,wheny,andisgiven.WehaveM<Nin5.4.Sothereareintheorysolutions,thesolutionspacegivenbya(N-M)dimensionalhyperplane,H:=N+sinRN,whichisthenull-spaceNoftranslatedbythetruesolutions.Thishappenssincey=s)=s+r)for8rNTherequirementandchallengethenbecomesoneofingthesparsesignalsinthetranslatednullspace.5.2.3.1l-2MinimizationTheclassicalapproachtohandlethistypeofinverseproblemsisbymeansofaleast-squaresmethod.Here,thevectorinthetranslatednullspaceHwithsmallestl2norm50(i.e.minimumenergy)isselected:^s=argminjjs0jj2;suchthat;s0=y:(5.8)Theadvantageofthismethodisintheavailabilityofaclosedformsolutionoftheform:^s=TT)1y.UnfortunatelywhatisbeingsoughtisaK-sparsevector.Minimizingtheenergydoesnothelpasthesparsestsignalisnotboundtohaveminimumenergyaswell.l2minimizationisnotasparsitypromotingmethod.Asaresult,whatisrecoveredisanon-sparselowenergysignalwhichisnotthetruesolution.5.2.3.2l-0MinimizationSincel2minimizationdoesnotpromotesignalsparsity,alogicalalternativeistolocatethesparsestvectorinthetranslatednullspaceH.Thatistoperformal0minimization:^s=argminjjs0jj0;suchthat;s0=y:(5.9)Aswasmentionedbefore,ithasbeenshownthatthiscangeneratetheexactsolutionforak-sparsesignalfromM=K+1measurements[64],[63]whichmakestheschemeattractive.However,solving(5.9)isnumericallyunstablewithcomputationalcomplexityofanNP-completeproblemwhichrequiresexhaustiveenumerationofallNKpossiblecombinationstothenon-zeroentrylocationsins.515.2.3.3l-1MinimizationAsurprisingfactincompressedsensingisthatinmanyofitsrelevantpracticalproblems,al1normcanreplacethel0normintheminimizationschemedescribedabovetogetequivalentandstablereconstructionswithhighprobability.Mostofthesignalrecoveryrelatedworkincompressedsensingexplorestheuseofl1asasubstituteofl0norm.In[42],itwasshownthatforak-sparsesignal,ifthemeasurementsizeMMcKlog(N);(5.10)thenwithprobabilitymorethan1,thesolutiontothel1minimizationproblem:^s=argminjjs0jj1;suchthat;s0=y;(5.11)istherequiredoriginalsignal.Inthepresenceofnoise,theconstraintisjustjjs0yjj2"with"beingatoleranceparameter.Thel1minimizationproblemcanberecastasaconvexoptimizationproblemas:^s=argmin^Njjys0jj1:(5.12)Thiscanbeconvenientlysolvedasalinearprogramcalledbasispursuit,whichhasO(N3)computationalcomplexity[45],[43].Averywellresearchedminimizationproblemistominimizethefollowingfunctional:F˝(x)xyjj22+2˝jjxjj1;(5.13)52Figure5.2:Visualinterpretationoftheenessoftnormsforsignalrecoverybyminimization[1]:(a)AsparsevectorsliesonaK-dimensionalhyperplanealignedwiththecoordinateaxesinRNandsoclosetotheaxes(b)Recoverythroughl2minimizationdoesnotthecorrectsparsesolutiononthetranslatednullspace(greenhyperplane),butanon-sparsesolution^swithleastenergy.(c)Withtmeasurements,recoverybyl1minimizationdoesthecorrectsparsesolutions.with˝>0.Thisisanunconstrainedconvexoptimizationproblem.Ithasbeenshown[65]thatasolutionto(5.11)wouldalsominimize(5.13).Thusmanywellinvestigatedconvexoptimizationalgorithmscanbeappliedtosolveal1minimizationproblem.5.2.3.4GeometricalInsightsAgeometricviewpointgivesasimplerintuitiveexplanationastotheenessofusingthel1normoverthel2.Forthegraphicalrepresentation,Fig5.2isusedfrom[1].ThesetofallK-sparsesignalssinaN-dimensionalspace(RN)isanon-linearspaceconsistingofK-dimensionalhyperplanesalignedwiththecoordinateaxes(shownninFig.5.2(a)).Then,sparsevectorsarelocatedneartheco-ordinateaxesinRN.Whenl2minimizationisperformed,thetranslatednullspaceH=N+shasdi-mension(NM).Itisorientedatarandomangleduetotherandomnessinasshown53inFig.5.2(b)).Apointtonotehereisthatinreality,N;M;K>>3andhencesomeintuitiveimaginationisrequiredtoviewthesameinhigherdimensions.Thel2minimizer^sof(5.11)isthepointonHnearesttotheorigin.AsHhasarandomorientation,withahighprobability^swillbeneithersparsenorneartoanycoordinateaxesandhencetos.Anylpminimizationscheme(wherep=0;1;2...,etc.)canbegeometricallyviewedasprogressivelyenlargingthelpballfromtheorigintillittouchestheconstrainthyperplane(H).Thepointofcontactgivestheminimizerofthatlpproblem.Thegeneralofthelpunitballis:-ThelpunitballBofavectorspaceVisthesetofallvectorswithlpnormlessthanorequaltoone,i.e.B=fx2Vjjjxjjp1g:(5.14)Thel1ballisdiamondshapedwiththeverticesalignedalongthecoordinateaxes(Fig5.2(c)).ThespikinessalongthecoordinateaxesincreasewithincreasingN.Sowhenthel1ballisblownoutwards,ittouchesHatapointnearthecoordinateaxeswhichiswheretheactualsignalsislocated.Thuslpminimizationturnsouttobeasuitablesparsitypromotingminimizationscheme.545.2.3.5SummaryInshort,whatisseenisthattosetupacompressedsensingbasedsystem,onehastocomeupwithadataacquisitionschemefromrandommeasurements.Thesensingmatrixmusthavesomesppropertiesasdiscussed.Afteracquisition,signalisrecoveredthroughlinearprogrammingreconstructionscheme.Theerrortermtominimizewouldideallybethel0normbutduetocomputationalconstraints,thealternativeistousethel1minimization.Fortunatelythelatterperformsequallywellundercertainconditionsmentionedearlier.Thesegsleadtoahugeamountofresearchconductedonl1basedreconstructionschemesunderthecompressivesensingregime.Inthefollowingchapters,theCSbasedframeworkfortomographywillbedescribedandresultsthusobtainedwillbepresented.55Chapter6CSbasedReconstructionforDTTheprojectiondataacquisitionintomography(ref.chapter-2)canbeex-pressedasF=x)(6.1)whereisthedoperator,Fisthesampledataink-spaceandxistheobjectfunctionx(r).Iftheacquireddataishighlysparse,thenclassicalinterpolationmethodsarenolongerapplicableastheNyquistlimitisnotmet.FBPPaloneresultsinalotofartifactsinthereconstructedimageanddistortactualfeaturesintheimage.Usingmoreaccuratenon-uniformfastFouriertransforms,acompressedsensingframeworkcanbesetup,forhighqualityreconstructionfromsparseviewdata.Firstly,itisassumedthatxisapproximatelysparseinsomedomainsuchthatx=sasinprevioussections.Then,withtheavailabilityofF,knowledgeofandwecanformulateaconvexoptimizationproblemusingthefunctionalin(5.13):minsfjjsjj1+jjysjj22g;(6.2)whereistheregularizationparameter.566.1ApplicationofCStosparseDTrecoveryForultrasoundormicrowavebasedDT,thedataacquisitionmatrixisthepartialFouriermatrix.Thesparseviewdataisgeneratedbyrandomlychoosingviewangles.Thesesamplesgivethevectoryof(5.11)and(6.2).ForsettinguptheCSframework,thesensingmatrix=mustbeconstructedwithbeingthesparsebasisfortheobject.Lettheobjectfunctionbedenotedbyf,sothatf(x;y)canbeusedtorepresentthespatialdistributionoftheobjectfunction.Theobjecthasaboundedsupport,say[C;C][C;C],i.e.f(x;y)=0forjxj;jyj>C.Letfddenotethediscretizedobjectfunctionwhichistobereconstructed.fd2Cndnd,withnd=2[C=T])withTbeingthesampleperiod.Also,letF(u;v)andFd(u;v)betheFouriertransformsoff(x;y)andfd(n1;n2)respectively.Also,thereceiverarraywillhavelimitednumberofelements.Letthediscretebe^u=u(n˝),where˝beingthespatialsamplingintervalofthesystem.Let^U()andU()betherespectiveFouriertransforms.Inthelimit˝!0,boththesignalsbecomeequal.ApointtonotehereisthattheFouriertransformofthescatteredisrelatedtotheFourierspaceoftheobjectalongsemicirculararcsasmentionedinsection2.Here,givestheprojectionofapointonthesemicirculararctoitstangentattheorigin.Also,istheangleofincidence.Then,invokingtheFDP,wecanhave^U()ˇU()=F(u;v)ˇFd(u;v).Let1=1;2;::;N1bethesetofvieworprojectionanglesoverwhich^u(n˝)isobtainedandfromthat^U()iscalculatedfor822=1;2;:::;N2.Then,fdcanbereconstructedfromtheprojectiondataset57^U()j(;)21;2)as[66]:(T0)2U02jejldC=TeXn1=C=TcdC=TeXn2=C=Tcfdn1;n2e2ˇj(n1u+n2v)T=^U()+n():(6.3)Thisisexpressibleinacompactmatrixequationformasfd=F+n,where=1;2);2Cj(nd)2;fd2C(nd)2;(n1;n2)jnd=2j;F2Cjj.From(6.3),thefortheminimizationproblemisobtained.Essentially,thesummationexpressionin(6.3)givesthecocientsofaFouriermatrix.ByFDPT,thespatialfrequencysamplesaregatheredalongthearcAOB(seeFig.2.1).Astheangleofincidencevaries,thearcrevolvesaroundintheFourierspaceanddescribesacentereddiskofradiusp2k0.Sothereconstructionoftheobjectisalwaysalow-passversionoftheoriginalimage.ThefollowingstepswouldbeusedtoassurethattheCSframeworkismaintained:Incoherencewillbemaintainedbyusingarandomsetofanglesfortheprojectiondata.ApartialFouriermatrixwillbeused,whichensuresRIPofthesensingmatrix.Sparsitywillbeexploitedinitiallythroughimagegradientsinsection-7.1.Later,insection-7.2simultaneousexploitationofmultiplesparsedomainswillalsobeex-plored.LetthesparsebasismatrixbeCombiningl1normanddataconstraintsintheminimizationproblem,theinitialproblemisoftheform:minsfG(s)=jjFsjj22+jjsjj1g:(6.4)58Here,Fgivesthespatialfrequencysamples,sisthecotsoffdinthesparsebasisInthenextsection,thereconstructionalgorithmfromprojectiondatasetispresented.6.2ReconstructionAminimizationprobleminvolvesreducingacostfunctioninaseriesofiterativestepsstartingfromaninitialvalueofthecostfunction.Thekeyfeatureishowthecostfunctionisupdatedateachiteration.Atamountofliteratureonmethodsareavailabletominimizeacostfunction.Inthisresearch,astheminimizationproblemisessentiallyaconvexoptimizationproblem,optimizationtoolkitfromBoydandVanderbeghe[65]hasbeenused.Theoverallreconstructionalgorithmsequentiallyfollowsthesesteps:Generateprojectiondatafromrandomviewangles.Fourierspacedataalongsemi-circulartrajectoriesisfoundapplyingtheFDPT.Iterativereconstructionthroughl1minimizationinthesparsedomainisappliedwhilepreservingthedataconstraints.Inthefollowingchapter,reconstructionshavebeenperformedusingTVasthel1normofthesparsedomain.Theperformanceofthereconstructionundervaryingdegreeoflimiteddataandangularaccesshavebeenevaluated.59Chapter7ReconstructionwithTotalVariationasl1penaltytermMostphysicalsamplesinvestigatedtomographically,doinfactpossesspiecewisecon-tinuouspropertydistribution.Particularly,biologicalspecimenswouldfallunderthiscategory,whereregionsoverextendedareaswouldhavenovariationsbutrapidlyvaryincertainareas,suchasedgesoforgansorboundariesbetweennttissue.Theseimagesthemselvesarenotsparse,however,theirgradientimagesaresparse.ThisisoneformofsparsitythatcanbeexploitedinaCSframework.Thegradientmagnitudeimage(GMI)isintermsofderivativesintheverticalandhorizontaldirectionoftheimage.LetDhn1;n2andDvn1;n2denotetheoperatorsinthehorizontal(h)andvertical(v)directionsrespectively.Thegradientoftheimageisrfd=[Dhn1;n2;Dvn1;n2]fd=Dfd,whereD=[Dv;Dh]=isthesparsitypromotingop-erator.Thegradientmagnitudethenbecomesjrfdj=q(Dhn1;n2fd)2+(Dvn1;n2fd)2.Thel1-normofthegradientimagehasoftenbeentermedasthetotalvariation(TV)oftheimage,whichthencanbeasTV(fd)=Xn1;n2q(Dhn1;n2fd)2+(Dvn1;n2fd)2:(7.1)60TVcanbeemployedasameanstoexploitsparsityofpiecewisesmoothobjects.Ithasbeenalreadyusedasaregularizingtermbeforee.g.[32].TVcanbeeinsuppressingGibbswhilepreservingedges[67].TouseTVasthel1norm,intheminimizationproblemof(6.4),thesparsesignalsistheGMI,sothats=D(fd)whereDisthesparsityoperatorandbyjjD(fd)jj1=TV(fd).Inthiscase,(6.4)becomesminsfG(s)=jjFsjj22+jjsjj1=jjFDsjj22+TV(fd)g;(7.2)withbeingtheregularizationparameterfortheTVtermand=D.ToavoidazerodenominatorintheTVterm,anapproximationwhichisoftenemployedis:kDn1;n2fdkˇq(Dhn1;n2fd)2+(Dvn1;n2fd)2+,whereisasmallpositivenumber.Thesecondtermin(7.2)isthedataconstrainttermaddedtokeeptheproblemasanunconstrainedoptimizationproblem.Theparameterdeterminestherelativeweightageofthedataconstrainttermandthel1penaltyterm.Thevalueofneedstobecarefullychosen.InmostcasesthisvaluewouldbeapplicationspAstandardapproachistoplotaresponseofthetwotermsintheminimizationtermwithrespecttothevariationof.Asweepofoveralargerangewouldgenerallygiveinsighttowardsanoptimalvalue.Overtherangeofthesweepgenerallyasincreases,thel1-normdecreaseswhereastheerrornormincreases.Avalueofissochosenastomakethel1normlowenoughwithoutincreasingtheerrornorm.Forthereconstructionsperformedhere,thevalueofhasbeenat0:2.OncethereconstructionproblemissetupintheCSframeworkasshownhere,thel1minimizationisanoptimizationprobleminstandardform.Itist61touseanoptimizationtoolkitifapplicable.Forsolvingconvexoptimizationproblemsexpressedinstandardforms,ahostofoptimizationtoolsetsarealreadyavailable.Inthiswork,theminimizationproblemof(7.2)issolvedusingaconvexoptimizationtoolkitcvxbyBoyd&Vanderberghe,[65],[68].Aparticularadvantageofusingthistoolkitisthatitcanbeusedtosolvetheprimal-dualproblemwiththeMatlabbasedSeDumitoolkit[69].Thesolutioncomeswithaceofconvergenceintheformofthedistancefromthedualmaximumandthedualitygap.Sothedistanceofthesolution(i.e.minimumoftheobjectivefunctionachieved)fromthetheoreticallowerlimitisknown.7.1ReconstructionwithTVasl1minimizerAspartofthemainaimofthisresearch,reconstructionwasperformedonacomplex-valuedphantomstructuresimilartothatinPart2.ToseetheenessofTVasthel1penaltyterm,twotypesofdatavariationcouldbeanalyzed.Thebeingthenumberofprojectionswhentheangularaccessisxed.Thesecondbeingthevariationoftotalcoverageforanumberofprojections.Inthisexercise,theprojectiondatasetshavebeenxedat15,20,30and45views.Theangularcoveragelimitshavebeenxedat180;150;120and90.Inthebelow,reconstructionsofrealandimaginarypartofthephantomareshownseparatelyfortheseaforementionedvariations.Theofbothtypeofvariationsonthereconstructionerrorhavebeenpresentedseparately.InFig.7.1andFig.7.2,reconstructionsfrom45projectionshavebeenshown.Itcanbeseenthatforthethreecoverages,thequalityoftheimagesisalmostconstant.At90coverage,thereconstructionstartsshowingconsiderabledistortion.Thisishowevernot62Figure7.1:Reconstructionsofrealpartofimagewith45viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.2:Reconstructionsofimaginarypartofimagewith45viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)9063surprisingastherestrictionoftheavailabledatahasbeenlimitedonbothgrounds,thatofprojectionsaswellascoverage.Itisexpectedtoseebetterreconstructionsfromsamenumberofprojectionswhentheangularaccessishigherormorecomplete.Theinterest-ingobservationhereisthatasthecoveragedecreasesfrom180to120,thedegradationintheimagequalityismarginalandmostlywouldbeacceptablebasedontheapplication.Detailederroranalysishasbeendoneinthenextsectionofthischapter.FromFig.7.3toFig.7.8,thereconstructionsofrealandimaginarypartshavebeenshownseparatelyforangularsweepsasthenumberofprojectionsisprogressivelydecreased.Withhigherangu-larcoverage,thereconstructionqualityismaintainedatupto20projections.tdegradationisobservedat15projections.Thisillustratesthataslongasthecoverageishigh,therandomsamplingandl1minimizationcanperformgoodreconstructionsfromveryfewpeojections.Asthecoverageislowered,decentreconstructionismaintainedatupto120.Forevenlowercoverage,thel1minimizationaloneisnote.Thisisbecausetheminimumdatarequirementevenundersparsereconstructionstartstobeviolated.7.1.1ErrorAnalysisInordertoquantitativelyevaluatethereconstructionsperformed,theMeanAbsoluteError(MAE)describedinchapter4isusedagain.Forerrorperformanceadditionalreconstructionsforacoveragerangeof60hasalsobeenconsidered.Theaverageerrorinreconstructionforrealandimaginarypartshavebeencalculatedseparately.TherelativepercentagechangeinMAEfortprojectionnumbersandangularaccessareshowninFig.7.9-Fig.7.12.64Figure7.3:Reconstructionsofrealpartofimagewith30viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.4:Reconstructionsofimaginarypartofimagewith30viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)9065Figure7.5:Reconstructionsofrealpartofimagewith20viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.6:Reconstructionsofimaginarypartofimagewith20viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)9066Figure7.7:Reconstructionsofrealpartofimagewith15viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.8:Reconstructionsofimaginarypartofimagewith15viewsfortangularcoverageof:(a)180,(b)150,(c)120,and(d)9067Fig.7.9andFig.7.10showtheMAEincreaseforaangularcoverageasthenumberofprojectionschange.TheMAEfromthemaximumnumberofprojections(60)istakenasthebasereferencetowhichthepercentagechangeoferrorismeasuredasthenumberofprojectionsisprogressivelyloweredupto15.Thischangeisplottedfortangularcoveragesbetween60to180.Fig.7.9showstheperformancefortherealpartofthereconstructedimageandFig.7.10fortheimaginarypart.Asexpected,foreachangularcoverage,astheavailablenumberofprojectionsisreduced,theerrorincreases,asseenfromtheplots.Thepercentageincreaseremainsbelow20%forallcoveragesat30views.From20viewsorless,theerrorrateincreasessharply,e.g.intherealpartoftheimage,theMAEincreasefor180coverageat20viewsis18%and56:7%for15views.For120coverage,thevaluesarerespectively26:7%and43%.Withrespecttovisualidenoffeaturesordefectsfromreconstructedimage,thistranslatestogoodreconstructionsmaintainingallfeaturesupto30viewsandacceptablereconstructionat20views.At15views,thedegradationgetsconsiderablyhightodependontheimagesfordiagnosisorfaultdetectionwithhighAnimportantthingtonotehereisthatinFig.7.9andFig.7.10,eachlineshowthepercentageincreaseoferrorastheviewnumberisdecreasedwhilethecoverageisSo,althoughalltheplotsstartat0%errorincrease,theactualerrorvaluewouldbehigherforalowercoverage,andviceversa.Thetotalcoveragedeterminestheextentofdataavailabilityforreconstruction.Hence,thechangeinpercentageMAEincreaseismorestrikingforhigherangularcoveragesthanlowerones.Thisisillustratedthroughtheplotsthemselves.Thepercentagechangefor60ois10:5%inrealand12:4%inimaginarypartat15projectionswhichisthelowestchangeobserved.68Thisisbecausethestartingpointitselfisalreadymuchworseduetolimitedcoverageandindoesnotgetworsewithlowernumberofprojections.Theobservedpercentagechangeinerrorincreaseswithincreasingangularcoverage.TheMAEplotsshowthatwithhigheraccess,thereconstructionaccuracyincreases.Anotheravenuetoexploreistoobservetheoftheavailableangularaccessforanumberofprojections.ThisisillustratedinFig.7.11andFig.7.12.Here,foranumberofprojections,thepercentageMAEerroriscalculatedwithrespecttothemaximumangularcoverage(180).Thecoverageisdecreasedto60.Theprocessisrepeatedwhilevaryingthenumberofprojectionsfrom60to15.Asimilartrendisobservedasinthelastcase.Foreachprojectionnumber,theMAEerrorincreasesasthetotalcoveragedecreases.Thisisexpected.However,asurprisingandappealingfactisthattheincreaseinerrorismarginalirrespectiveoftotalnumberofprojectionsbetween180to120.ThisillustratesthestabilityandutilityofthisCSbasedreconstructionprocedure.Theprocedurewouldbehandyineitherlowerangularaccessorasparseprojectiondataset(anduptoacertainlimitwhenbothconstraintsaresimultaneouslypresent).ThisputsthisCSbasedframeworkinastrongpositiontohandlehighlyadversedataacquisitionconditions.Insummaryfromthesereconstructionsetsitcanbeconcludedthatat120coverage,aslittleas20projectionsmightbetforareasonablyaccuratereconstruction.Thisisagreatimprovementoverothertraditionaliterativemethods.Furtherrestrictionswouldbetoolimitingforreconstructioninageneralizedsetupofcomplexvaluedimagewithnopriorinformationorknownrestrictions.Howeverwhenwehavesomea-prioriknowledge,eitheraboutthestructureorsomepracticalinsightsabout69theimagedsystemorROI,tighterboundsmightbeachievableaswillbedemonstratedinthenextsubsection.7.1.2ReconstructionfromphantomswithrealisticpermittivitydistributionInpracticalscenarios,thephysicaldistributionofpermittivityvariationintherealandimaginarypartswouldbesame,i.e.therealandimaginarypartsofthecomplexvaluedimagewouldhavethesamespatialvariationsandwouldessentiallylooksame.Inthissectionsomereconstructionsfromamorerealisticphantomisshown.Theimaginarypartofthephantomiskeptsameastherealwithrespecttotheshape,asexpectedinpracticalmeasurements.Thusthedatarequirementwouldbelooserthaninthelastsection.Re-constructionsfrom15and10projectionsfromtangularcoveragearegiveninFig.7.13-Fig.7.16.Asisevident,for15views,thereisalmostdistortionlessreconstructionforallangles.Theimaginarypartshowsmoredegradationthanthetherealpartatlowercoverage.Thisisbecausethemagnitudeoftheimaginarycomponentshavebeenkeptathalfofthatintherealpartandassuch,ismoresusceptibletodegradationingeneralandespeciallyundersparsedatarecoveryconditions.For10views,therealpartiswellretainedupto120,however,below150,theimaginarypartdegradesconsiderably.Inconclusion,weseethatfor15projections,acceptablereconstructioncanbeachievedat120andfor10viewsat150.Atfull180,even10viewscangenerateaclearrecon-struction,maintainingallfeaturesdistinctly.Foranymeasurementsystem,noiseisanintegralpart.Therobustnessofanyreconstructionalgorithmisdependentonthenoise70Figure7.9:PercentageincreaseofMAEforrealpartofimageasthecoverageisloweredforanumberofprojections.GraphsplottedfortnumberofprojectionsFigure7.10:PercentageincreaseofMAEforimaginarypartofimageasthecoverageisloweredforanumberofprojections.Graphsplottedforrentnumberofprojections71Figure7.11:PercentageincreaseofMAEforrealpartofimageasthenumberofprojec-tionsisloweredforacoverage.GraphsplottedfortcoveragesFigure7.12:PercentageincreaseofMAEforimaginarypartofimageasthenumberofprojectionsisloweredforadcoverage.Graphsplottedfortcoverages72marginsitcanhandle.Sofar,inthischapter,reconstructionshavebeendonewith5%noise.However,toseetheofincreasingnoiseinthedata,reconstructionswereperformedundervariouslevelsofnoisydata.Thewasobservedonreconstructionfrom20viewsand120angularcoverage.ThecanbeseeninFig.7.17-Fig.7.18.Thereconstructionisgoodat10%noise.Therealpartisstillacceptableat20%noise,however,theimaginarypartisconsiderablydegraded.At50%noisebothrealandimag-inarypartsarehighlydegradedandunacceptableforvisualanalysis.However,itshouldbenotedthatthisistoohighanoisemargin,whichshouldrequireimprovementsinthephysicalacquisitionsystemratherthanthereconstructionalgorithmitself.Inconclusion,itcanbeinferredthatwithTVbasedCSreconstruction,acceptablereconstructionofcomplexvaluedobjectivefunctioncanbeachievedfrommoderatelynoisydatawithaslimitedcoverageas120andaslittlemeasurementsas15projections.Thisisacantfeatandhighlybinnumerousscenarioswitheitherhighlylimitedangularaccessorvariousconstraints(likeavailableacquisitiontime)limitingthetotalnumberofprojectionsthatcanbeobtained.Withanaimtoexploreotheravenueswhichmightalsohavepertinentttowardsloweringdatarequirementsintomographicreconstruction,ofincorporatingmultiplesparsitypromotingfactorsisexploredinthenextsection.7.2MultiplesparsedomainincorporationThefundamentalprinciplebehindcompressedsensingbasedsignalrecoveryistoexploitasparserepresentationofthesignal.Ifasignalcouldberepresentedinmultiplesparse73Figure7.13:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.14:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)9074Figure7.15:Reconstructionsofrealpartofimagewith10views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.16:Reconstructionsofrealpartofimagewith10views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)9075Figure7.17:Reconstructionsofrealpartofimagewith15viewsand120coverage,whenrealandimaginarypartshavesimilarphysicalboundaries,fortnoiselevels(measuredas%ofmeansignalenergylevel):(a)5%,(b)10%,(c)20%,and(d)50%Figure7.18:Reconstructionsofimaginarypartofimagewith15viewsand120coverage,whenrealandimaginarypartshavesimilarphysicalboundaries,fortnoiselevels(measuredas%ofmeansignalenergylevel):(a)5%,(b)10%,(c)20%,and(d)50%76domains,itwouldbeinterestingtoseeifthesedomainscouldbeusedsimultaneouslyforbetterreconstruction.TraditionallywaveletshavebeenaverypopularsparsedomaininimageprocessingandhasbeenusedinCSbasedreconstructionswithgreatsuccess.Itwouldbeinstructivetoseeifwaveletscouldbeincorporatedasanaddedsparsedomaininrecoveryofcomplexvaluedobjects.Ifabasicwaveletbasedpenaltytermcanbeincorporatedtogetadecentlevelofreconstruction,avastbankofwavelet(orcurvelet,etc.)basedopenupandprovideopportunityoffurtherresearchtowardsutilizingmultiplesparserepresentationsforincreasingreconstructionncyorloweringdatarequirementsfurther.Hereabasicwaveletbasedpenaltytermhasbeenincorporatedusinghaarwavelets.Themainaimistoexplorethepossibilityofincorporatingmultiplesparsedomainseasilyforcomplex-valuedimagereconstructionfromsparsedata.Toincorporatethewaveletsparsityterm,theoptimizationproblemof(7.2)ismodasminsfG(s)=jjFDfdjj22+TV(fd)+jjfdjj1g:(7.3)Intheaboveequation,isthehaarwaveletoperatorsothatfdisthewaveletdomainrepresentationoftheimagefd.istheregularizationparameterforthesecondl1penaltyterm.Inthefollowingreconstructions,=0:2and=0:1hasbeenused.InFig.7.19-Fig.7.20,reconstructionhavebeenperformedbysolvingtheoptimizationproblem(7.3)for15projectionsattangularcoverages.Itisinterestingtonotethatthereconstructionsarecomparableormarginallybetterfor180and150coveragebutdegradesmorerapidlythantheTVbasedreconstructionatlowercoverageandespeciallyfortheimaginarypart.Therearetwopossiblereasons77Figure7.19:Reconstructionsofrealpartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)90Figure7.20:Reconstructionsofimaginarypartofimagewith15views,whenrealandimaginarypartshavesimilarphysicalboundaries,fortangularcoverageof:(a)180,(b)150,(c)120,and(d)9078behindthis.Firstly,forthesesreconstructions,haarwaveletshavebeenusedforwaveletdomainrepresentation.Thisisthesimplestwaveletavailable.Furthersophisticatedwaveletswouldactuallybemuchmoreeinbettersparserepresentation.Secondly,onceabettersuitedwaveletisdetermined,thetheregularizationfactorscanbeoptimizedtosetupamoretoptimizationproblemwhichwillgeneratebetterreconstructionsbytrulyexploitingthesparsityinmultipledomainsinparallel.Thatmultiplesparsitypromotingtermscanbesimultaneouslyusedisapparentinthesesimpleexercise.However,thereisahugepotentialofimprovementbyusingmoreoptimalwaveletsthanthehaarwaveletusedhere.Thisisaninterestingfutureworkorextensionofthisresearch,anavenuetoexplorewithbacrossmultipledisciplines.79Chapter8Conclusions8.1Summarytomographyisanactiveofstudyinimagingwhichisusedinnonde-structiveevaluationandbiomedicalapplications.Inmanypracticalscenarios,amajorchallengeinDTisalimitedavailabilityofprojectiondata.Thelimitationsmightap-pearintheformofconstraintsinangularaccessortotalnumberofprojectionsoracombinationofboth.Thisessentiallymakestheavailablesetofmeasurementshighlylimitedorsparse.Thisthesisfocusesondevelopmentoftmethodstohandlethechallengesonlimiteddataforimagereconstruction.Imagereconstructionalgorithmsfortomographywithlimiteddatawereinvestigatedanddeveloped.Sparseto-mographicreconstructionhasbeenexploredundertwocategories:(a)themoderatelylimitedangularcoveragescenario,byexploitingredundancyinprojectiondataand(b)severelylimitedprojectiondata,bothintermsofangularaccessandnumberofprojec-tions,throughemployingsparserepresentationsofthetestimageandinvokingcompressedsensingframeworkforimagerecovery.808.1.1Exploitingdataredundancyformoderatelylimitedangu-lartomographyTraditionally,360coverageisrequiredforaccuratereconstructionofcomplexvaluedobjectfunctions.However,underangularcoveragerangebetween180270,redundan-ciesarepresentintheDTprojectiondata.Formulationstoexploittheseredundanciesoptimallyandinageneralizedapproach,wasshowntoprovideaccuratereconstruction,independentoftheimagecharacteristicsorfeatures.AnovelweightingfunctionfortheprojectiondatainitsFourierspacewasproposedusingcumulativedistributionfunctions.Algorithmsweredevelopedtoreconstructcomplexvaluedimageswiththisweightedpro-jectiondatasetusingbackpropagationtechniques.Thismethodyieldedrecon-structionsofcomplex-valuedobjectfunctionsthatwereshowntobesuperiortothestandardbackpropagationalgorithminthecoveragerangeof[180270].tdata-weightingresultedinrecoveringimagesfrom220coveragebutequivalenttofullcoverage(360)reconstruction.Robustnessofthealgorithmswithnoisyprojectiondatawasalsov8.1.2CompressedSensingbasedtomographyfromhighlysparsedataReconstructionfromhighlysparsedatawithlimitationsonangularaccessandnumberofprojectionswaswasdevelopedandevaluated.AcompressedsensingframeworkforDTimagereconstructionforcomplexvaluedobjectshasbeendeveloped.UsingTotalVariationasthesparsitynorm,accuratereconstructionofcomplexpermittivitydistri-81butionwasachievedfromseverelylimitedprojectiondataset.Accuratereconstructionsfromverylimiteddatasetsof15-20projectionswithangularaccessaslowas120wasachieved.Reconstructionfromnoisyprojectionsestablishedtherobustnessofthealgo-rithmsinpresenceofnoise.Thefeasibilityofusingmultiplesparsedomainswasalsoexploredbyaddingwaveletdomainl1-normasanaddedpenaltyfactorintheoptimizationproblem.AbasicHaarwaveletbasedpenaltytermwassuccessfullyimplementedintheoptimizationschemetogetreconstructionsinaCSframework,therebyopeningtheroadtofurtherexploringmultiplesparsedomainincorporationintheimagereconstructionprocess.8.2Contribution:andTheprimaryfocusofthisthesiswastodevelopreconstructionalgorithmstorecovercomplex-valuedimagesundertomographicregimewithvaryinglimitationsontheavailableprojectiondata.Inparticular,thisthesispresentsthefollowingcontribu-tions:AlgorithmsweredevelopedtoexploitredundancyinDTprojectiondata.Thisisantwaytoreconstructcomplexvaluedimagesaccuratelyundermoderatelylimitedangularconstraints.Totalvariationwassuccessfullyemployedasasparsitypromotingnormundercom-pressedsensingformulation.TheTValgorithmissimpletoimplement.Usingitasthel1-norminaCSframeworkprovidesantalternativeforimagerecovery.Reconstructionsfromasfewas15projectionsetsandlowcoverageof120has82beenachieved.Thealgorithmsperformedaccuratelyundernoisydataprovingtheirrobustnesstomeasurementerrorandrelatedperturbations.Useofmultiplesparsedomainsinimagerecoverywasexplored.Thisopensupahugepotentialoffurtherresearch.OptimalexploitationofmultiplesparsedomainswouldhaveapplicationsinscenarioswheretheavailabilityofprojectiondataislowerthanthatrequiredinageneralCSframework.Thebeofthisresearcharemanifold,thesalientonesare:Thealgorithmsareapplicableforreconstructionofcomplexvaluedobjectivefunc-tionsorimagesundertheDTregime.ThisincludesmodalitiessuchasultrasonicDT,microwavetomography,ODTetc.Thisresearchhasmulti-disciplinaryapplicationssuchasbiomedicalimaging,mate-rialcharacterizationandstructuralhealthmonitoring.Thecapabilitytoreconstructcomplexvaluedimagesisparticularlyofinterestinthepresentagewhensmartandmaterialsareincreasinginpopularity.Thesearebeingdesignedandfabricatedforuseacrossawidegamutofapplica-tions.Knowledgeofthecomplexpermittivitydistribution(orrefractiveindexetc.dependingontheapplication)isfastbecominganecessityforNDEapplicationsandmaterialcharacterization.838.3FutureWorkInthepartofthethesis,ageneralizedapproachtoexploitdataredundancyinDTwaspresented.ThemainideawastheintroductionofweightsbasedoncumulativedistributionfunctionstotheFourierspaceprojectiondata.Foragivendataset,asingledistributionfunctionwasusedwithasetofparameterstoexploitredundancy.Asaninterestingfuturework,multipleparametersetscanbeemployedbasedonfrequencylocations.AnoptimizationproblemcanbesetuptodetermineparametersetsbasedonaparticularminFig.3.1(d).Thiscanenableapplicationofindependentandtcdfsforeachvalueofmandcanleadtofurtherimageimprovementsinthelowerlimitsofoperationbelow220angularcoverage.Inthesecondpartofthethesis,DTreconstructionunderaCSframeworkwasper-formedtorecovercomplexvaluedimages.Incaseofmedicalimaging,TVhadbeensuccessfullyusedasaregularizationparameterforsparsereconstructions.Soinacom-pressedsensingbasedsetup,employingTVasthel1normwherethegradientmagnitudeisasparserepresentationoftheimageisanaturalchoiceandimplementationofthemethodhasbeendemonstrated.OutsideTV,waveletsingeneralhavefoundgreatsuc-cessinimagecompressionandrecovery.Ascanbeexpected,tapplicationsmightntformsofsparserepresentations.Asaresult,thesparsitypromotingl1normwouldalsohavetobechanged.Forspapplications,themostesparsedomainsisaninterestingandimportantresearchgoal.Thiscouldbestudiedunderthenextphaseofthisresearch.Generalizedmethodstoextractmostesparsedomainsforcomplex-valuedreconstructionwouldbeofvalueacrossmultipledisciplines.Asan84example,inthisresearch,Haarwaveletshavebeenusedtodemonstrateabasicplatformforusingmultiplesparsitypromotingnormsintheminimizingtermoftheoptimizationproblem.Numerouswaveletsanddatabasesareavailabletodaywhichcanbebroadlyintoafewstandardcategories.Itislogicaltoassumethatthemosttivewaveletcategorywouldactuallybedeterminedbythetypeofapplicationbeingdevel-opedandcanbedeterminedthroughinvestigationintothenatureofthedatafeaturesassociatedwiththeproblemathand.Thusaproceduretoselectoptimumwaveletsorbasedontheassociatedapplicationwouldbeaninterestingavenuetoexplorewithbacrossmultipledisciplines.85APPENDICES86AppendixADistributionFunctionbasedweightgenerationGamma-cdfbasedweighting:Thegamma-cdfisasF(x)=Rxf(t)dt,wherefisthegammaprobabilitydensityfunctionas:f(tja;b)=8>>><>>>:1a)bata1et=b;t0;0;t<0:(A.1)wherea>0andb>0areparameters,anda)=R10ta1etdtisstandardgamma-function.Aswecanseethatgamma-cdfhassupporton[0;1),F(2+ˇ=2)<1,whichdoesnotmeet(3.5).Thereforeweightscreatedusinggamma-cdfinitsoriginalformwillbediscontinuousattheboundarybetweenAandB,andconsequentlyattheboundarybetweenBandCofFig.3.1(d).Onepossiblewaytogetacontinuosweightisbyinputtingatransformedargument.Soform2[0;0],weshallconstructweightsbyusingw(m;˚)=Ftanˇ2˚2+ˇ=2;(A.2)87whereFisthegamma-cdfasabove.Normal-cdfbasedweighting:Incaseofnormal-cdf,weusedtruncationmethodasfollows:w(m;˚)=F(mj˙)F(0j˙)F(2+ˇ=2j˙)F(0j˙);(A.3)where2(;1)and˙>0areparametersandF(xj˙)=1p2ˇ˙Zxe(t)2=2˙2dt:(A.4)88AppendixBNon-linearOptimizationTechniquesWhenwehaveanunder-determinedsystem,i.e.thenumberofunknownsismorethanthenumberofmeasurements,thereisgenerallynouniquesolution.Atypicalexamplewouldbetheprojectiondatafromalimitedangle(˝360o)tomographyexperiment.Thegeneralapproachtosolvingthistypeofsystemsistondan`optimal'solutionfromthesetofallprobablesolutionswhileobeyingsomeconstraints.Theseconstraintsareeitherknownaprioriorknownthroughexperiment(i.e.measureddata).Thissolutionisapproximateandisreachedthroughaseriesofstepsoriterationswhichaimtominimizea'costfunction'or'objectivefunction'.Thisapproachofreachingthemostacceptablebutapproximatesolutionformsthebranchofcomputationalsciencecalledoptimization.Inourcase,whentomographicimagereconstructionisdonefromlimitednumberofprojectiondata,iterativetechniquesareusedwhichemploysomeformofoptimization.Thusthischapterisabriefnoteonoptimizationandsomeofthenon-linearoptimizationtechniquesusedinthisresearch.ConsiderasimplesystemoftheformAx=b:(B.1)Ifxbeanapproximatesolutiontotheproblem,thenoftenthecorrespondingresidualisasAxb.Theaimwouldbetominimizethisresidual.Theidealsolution89wouldproduceazeroresidual.Letthisresidualbeexpressedasf(x)=Axb.Inthiscase,thecostfunction(withoutanyotherconstraints)wouldbetheresidualandwehavetheminimizationproblemasminxf(x):(B.2)BasedonthecharacteristicsandcomplexityofthesystemrepresentedbyA,thismini-mizationproblemcouldbeanythingfromasimplelineartohighlynon-linearsystem.Formanypracticalscenarios,incorporatingalltherequirementsintothisobjectivefunctioncreatesacomplexfunctionwhichneedstobeminimizedwhileconformingtothe`known'orexperimentaldatapoints.Linearsystems:Traditionally,asystemissaidtobelinearifitobeysadditivity(superposition)andscalarmultiplication(homogeneity).Mathematically,afunctioncanbeexpressedinageneralformasf(x)=f(x);f(x+y)=f(x)+f(y)(B.3)herefrepresentsageneralfunctionoroperator.Ifasystemhowevercomplex,obeyslinearity,itcanthenbebrokenintoasumofmanysmallerandrelativelysimplerunits.Averycomplexproblemcanthenbedecomposedintoanaggregateofsmallertractableproblemsandsolvedindependently.Thusitisalwaysconvenientifasystemcanbemod-eledinalinearfashion.90Beyondlinearity:Manycomplexrealworldproblemsareinherentlynon-linearandcannotbeexpressedthroughlinearapproximations.Asaresult,non-linearmathematicaltheorieshaveseentremendousgrowthoverthelastfewdecades.Severalbranchesofmathematicse.g.fractaltheory,non-lineardynamics,chaosetc.havebeendeveloped.Thesetoolsinturnhavehelpedthedevelopmentofnewtheoriesinpureandappliedsciences.Thesedevelopmentscoupledwiththeadventofpowerfulcomputerswithhighcomputationalcapabilitiesledtothedevelopmentofmanymethodstotacklereal-worldproblems.Nonlinearoptimizationisoneoftheforemosttechniques.Anoptimizationproblemisgenerallyformulatedas:minxf(x);s:t:g1(x)=0;g2(x)=0::::;gn(x)0(B.4).Here,fisascalarvaluedfunctionwhichisbeingminimizedsubjecttotheconstraintequationsandinequalities:g1;g2etc.Thepresenceoftheseconstraintsinincorpo-rateaprioriinformationandtherebylimitthesearchspace.Thistypeofoptimizationiscalledconstrainedoptimizationandisoffundamentalimportanceinreconstructiontech-niques.Iftheconstraintsarenotpresent,thentheprocedureistermedunconstrainedoptimization.Optimizationisaprocessofanamenablesolutionfromthefeasiblespace.Basedonthesearchapproach,optimizationmethodscanbeintodirectandindirectmethods.Theformerenumeratethepossiblesolutionsandevaluatethe91objectfunctionforallsetstodeterminethebestsolutionset.Commondirectmethodsincludeexhaustivesearch,thesimplexmethod,randommethod,theFibonaccisearchandmore.Acompletetreatmentcanbefoundinstandardtexts,[70],[71]etc.However,directmethodsareonlytwhentherearesmallnumberofvariablesorincaseswithcountableinputs.Forcontinuousproblemswithcomplicatedobjectfunctions,theimple-mentationofthesemethodsisunpractical.Inthelastfewdecades,thegeneticalgorithmsbecameanentmemberofdirectoptimizationmethods.Thissearchingprocessex-ploitedanalogousconceptsofgenemutationsoforganismstoselectsmallerpopulationsforevaluatingtheobjectivefunction.Thisresultsinhighlyimprovedncyofdirectsearchprocess.Ithasbeenappliedtomanyrealworlddatasetsincludingmicrowaveimag-ing.Indirectmethodsmostlyinvolvegradientbasedtechniquesinprinciple.Ifanalyticalformsoftheobjectivefunctionexist,thentheoptimizationstepsareiterativelydirectedusingthegradientinformation.Thepopularmethodsunderthiscategoryincludethesteepestdescent(SD)method,Gauss-Newton(GN)method,conjugategradient(CG)method,Levenberg-Marquardt(LM)methodetc.Thesimplestamongtheseispossiblythesteepestdescentmethodwhereasthemethodofconjugategradientsisoneofthemostlyusedacrossmultipledisciplinesbecauseofitversatilityandquickconvergence.Inthiswork,bothSDandCGmethodshavebeenusedattphasesandhencetheyarebriedescribedbelow.Thetheoryandexplanationshavemostlybeensummarizedfrom[70]and[72]92SteepestDescentMethodOneoftheverywellestablishedmethods,thesteepestdescentmethodusesthenegativedirectionofgradientvectorasthedirectionofminimization.Intuitivelyandgeometricallyitmakessense.Thegradientgivesthedirectionofmaximumincreaseofthefunction.Thenegativegradientistheoppositedirectionandhencethedirectionwherethefuctionwillbeminimized.ThemethodstartswithaninitialtrialpointXianditerativelymovesalongthesteepestdescentdirectionstillanoptimumpointorconvergenceisreached.thealgorithmconsistsofthefollowingsteps:1.StartwithanarbitraryinitialpointXi.Setiterationnumberi=1.2.Findsteepestdescentdirectionas:Si=fi=f(Xi).3.Findtheoptimalsteplengthi:@f@j==04.SetXi+1=Xi+Si.5.CheckXi+1foroptimality.Ifso,iterationisstopped,otherwisetheloopisiteratedtillconvergenceisreached.Convergence:Thestoppingcriteriaofanydesignproblemdependsontheproblemitselfandthedesignrequirements.Theiterationsarestoppedwheneitheranyoracom-binationofthestoppingcriteriaareSometypicalstoppingcriteriacouldbe:1.Thechangeinfunctionalvaluebetweensuccessivestepsissmall:f(Xi+1)f(Xi)f(Xi)12.Whenchangeinthedesignvectorbetweensuccessivestepsissmall:jXi+1Xij23.Whenpartialderivativesoftheminimizingfunctionalaresmall.4.Themaximumnumberofallowediterationsisreached.93ConjugateGradientMethodSteepestdescentisaverysimple,fastandeasytoimplementalgorithm.Ithasfoundsuccessinalotofapplications.However,itisnotaveryfastalgorithmanditcangettrappedinalocalminimum.Anotherpopularandrobusttechniquewhichhasbeenofgreatimportanceintheldofoptimizationisthemethodofconjugategradients.Itextendsthemethodofsteepestdescentwithgreatimprovements.Thefundamentalprin-ciplebehindthismethodistheuseof`conjugatedirections'.Thisensuresthatthemethodwillbequadraticallyconvergent.Thisisverybasitimpliesthattheconvergencewillbereachedinnstepsorless.ConjugateDirections:Aconjugatedirectionsmethodcanminimizeaquadraticfunc-tionwithinanumberofiterations.Anygeneralnon-linearfunctioncanbewellapproximatednearitsoptimumpointbyaquadratic.Soanyquadraticallyconvergentmethodshouldbeabletoachieveaquickerconvergenceforgeneralnon-linearfunctions.-IfAbeannnsymmetricmatrix,thesetofnvectorsfSigissaidtobeconjugatewithrespecttoAifSTiASj=0,foralli6=j;i=1;2;:::;n;j=1;2;:::;nOrthogonaldirectionsorunitvectorsforcartesianco-ordinatesystemswouldbeaspeccaseofconjugatedirectionswithA=I.Sisasetofnlinearlyindependentvectorsandsotheycanformabasis,i.e.anyvectorXcanbeexpressedasalinearcombinationoftheelementsofS.LetusassumethatweneedtosolveforthesystemAx=b.LetX0betheinitialstartingsolutionandXbethetruesolution.Thecanalsobe94expressedintermsofS,i.e.:XX0=n1Xj=0jSj(B.5)MultiplyingbothsidesbySTkA,onthelefthandsidewehaveSTkA(XX0)=STk(bAx0)=STkr0andontherighthandsidewehaveSTkAn1Xj=0jSj=kSTkASk:andhence,wecangetk=STkr0STkASk:(B.6)ThenwecanhaveanalgorithmtosolveAX=b:1.PickXkandA-conjugatedirectionsSk.Setiterationnumberk=12.Setk=STkr0STkASk.3.SetXk+1=Xk+kSk.4.Continueforn-iterations.Afternsteps,thenweshouldhaveXn=X.TheprocesstogenerateasetofA-conjugatevectorsisnottoocomplex.ItcanbedonebystartingwithanysetoflinearlyindependentvectorsV=VkandthenapplyingaGram-SchmidttransformationwithrespecttoA.Astandardstablenumericalapproachisthefollowing:951.LetS=V.2.Then,compute8k;Sk+1=Sk+1Pkj=1STkASk+1STjASjSjTheconjugategradientmethodisaspecialcaseofthemethodofconjugatedirec-tions.HerethecalculationofXateachstageisinterlacedwiththecalculationofthenewSkvector.Thealgorithmcanbeappliedthroughthesesteps:1.LetX1betheinitialguess.Letr1=bAX1andS1=r1.2.Fork=1,2,..untilconvergence,(a)Computesearchparameterk,thenewiterateandresidualk=STkrkSTkASkXk+1=Xk+kSkrk+1=rkkASk(b)Computethenewsearchdirectionk=STkArk+1STkASkSk+1=rk+1+kxkAfterKnsteps,thealgorithmterminateswithrK=0andXK=X.Sincethedi-rectionSkusedhereareA-conjugate,theprocessshouldconvergeforquadraticfunctionsinn-cyclesorless.Butforill-conditionedquadratics,themethodmayrequiremorecyclesforconvergence.However,thismethodissuperiortothesteepestdescentmethodintermsoffasterconvergenceandlowererrorbounds.Thisalgorithmshasbeenresearchedandimplementedononavarietyofproblems.AsaresultmanyreadilyavailableCG-codescanbedirectlyincorporatedintoreconstructionalgorithms.TheCGiterationsaresuit-96ableforincorporatingintoTVminimizationforimagereconstruction.TocomputetheCGiterationsthegradientoftheTVtermhastobecomputedaswell.IntheexpressionforTVin(7.1),toavoidazerodenominatorintheTVterm,anapproximationwhichisoftenemployedis:kDn1;n2fdkˇq(Dhn1;n2fd)2+(Dvn1;n2fd)2+,whereisasmallpositivenumber.Itcanfurtherbeapproximatedas:rkDn1;n2fdk2=Dhn1;n2fdkDn1;n2fdk2+Dvn1;n2fdkDn1;n2fdk2Dhn1;n21fdkDn1;n21fdk2Dvn11;n2fdkDn11;n2fdk2:(B.7)97BIBLIOGRAPHY98BIBLIOGRAPHY[1]R.G.Baraniuk,\Compressivesensing,"IEEEsignalprocessingmagazine,vol.24,no.4,2007.[2]A.Devaney,\Abackpropagationalgorithmfortomography,"Ul-trasonicimaging,vol.4,no.4,pp.336{350,1982.[3]A.C.KakandM.Slaney,Principlesofcomputerizedtomographicimaging.SocietyforIndustrialandAppliedMathematics,2001.[4]W.Tabbara,B.Duch^ene,C.Pichot,D.Lesselier,L.Chommeloux,andN.Joachi-mowicz,tomography:contributiontotheanalysisofsomeapplicationsinmicrowavesandultrasonics,"InverseProblems,vol.4,no.2,p.305,1988.[5]G.S.Kino,\Acousticimagingfornondestructiveevaluation,"ProceedingsoftheIEEE,vol.67,no.4,pp.510{525,1979.[6]B.Duch^ene,D.Lesselier,andW.Tabbara,\Experimentalinvestigationofationtomographytechniqueinultrasonics,"Ultrasonics,Ferroelectrics,andFre-quencyControl,IEEETransactionson,vol.35,no.4,pp.437{444,1988.[7]S.Semenov,\Microwavetomography:reviewoftheprogresstowardsclinicalapplica-tions,"PhilosophicalTransactionsoftheRoyalSocietyofLondonA:Mathematical,PhysicalandEngineeringSciences,vol.367,no.1900,pp.3021{3042,2009.[8]A.Devaney,\Geophysicaltomography,"GeoscienceandRemoteSensing,IEEETransactionson,no.1,pp.3{13,1984.[9]E.Robinson,\Imagereconstructioninexplorationgeophysics,"UniversityofTulsa,Tulsa,OK,Tech.Rep.,1984.[10]E.V.MalyarenkoandM.K.Hinders,\Ultrasoniclambwavetomography,"Ultrasonics,vol.39,no.4,pp.269{281,2001.[11]M.H.Ritzwoller,N.M.Shapiro,M.P.Barmin,andA.L.Levshin,\Globalsurfacewavetomography,"JournalofGeophysicalResearch:SolidEarth(1978{2012),vol.107,no.B12,pp.ESE{4,2002.99[12]P.GuoandA.J.Devaney,\Comparisonofreconstructionalgorithmsforopticaltomography,"JOSAA,vol.22,no.11,pp.2338{2347,2005.[13]T.C.WedbergandJ.J.Stamnes,\Experimentalexaminationofthequantitativeimagingpropertiesofopticaltomography,"JOSAA,vol.12,no.3,pp.493{500,1995.[14]T.WedbergandW.Wedberg,\Tomographicreconstructionofthecross-sectionalrefractiveindexdistributioninsemi-transparent,birefringentJournalofMi-croscopy,vol.177,no.1,pp.53{67,1995.[15]W.GorskiandW.Osten,\Tomographicimagingofphotoniccrystalers,"Opticsletters,vol.32,no.14,pp.1977{1979,2007.[16]J.Y.ChengandA.J.Devaney,\Inversescatteringandtiontomographyincylindricalbackgroundmedia,"JOSAA,vol.23,no.5,pp.1038{1047,2006.[17]Y.Sung,W.Choi,C.Fang-Yen,K.Badizadegan,R.R.Dasari,andM.S.Feld,\Opticaldtomographyforhighresolutionlivecellimaging,"Opticsexpress,vol.17,no.1,pp.266{277,2009.[18]J.Kostencka,T.Kozacki,A.Kus,andM.Kujawinska,\Accurateapproachtocapillary-supportedopticaltomography,"Opticsexpress,vol.23,no.6,pp.7908{7923,2015.[19]I.Catapano,L.DiDonato,L.Crocco,O.M.Bucci,A.F.Morabito,T.Isernia,andR.Massa,\Onquantitativemicrowavetomographyoffemalebreast,"ProgressInElectromagneticsResearch,vol.97,pp.75{93,2009.[20]D.G.Drogoudis,G.A.Kyriacou,andJ.N.Sahalos,\Microwavetomographyem-ployinganadjointnetworkbasedsensitivitymatrix,"ProgressInElectromagneticsResearch,vol.94,pp.213{242,2009.[21]A.Baran,D.J.Kurrant,A.Zakaria,E.C.Fear,andJ.LoVetri,\Breastimagingusingmicrowavetomographywithradar-basedtissue-regionsestimation,"ProgressInElectromagneticsResearch,vol.149,pp.161{171,2014.[22]N.BayatandP.Mojabi,\Theofantennaincidentdistributiononmi-crowavetomographyreconstruction,"ProgressInElectromagneticsResearch,vol.145,pp.153{161,2014.100[23]X.Ren,X.Yin,R.Yang,andW.Yu,\Athree-dimensionalimagingalgorithmfortomographysar,"inGeoscienceandRemoteSensingSymposium,2009IEEEInter-national,IGARSS2009,vol.3.IEEE,2009,pp.III{184.[24]X.-Z.Ren,L.H.Qiao,andY.Qin,\Athree-dimensionalimagingalgorithmfortomographysarbasedonimprovedinterpolatedarraytransform1,"ProgressInElec-tromagneticsResearch,vol.120,pp.181{193,2011.[25]A.Capozzoli,C.Curcio,andA.Liseno,\Fastgpu-basedinterpolationforsarback-projection,"ProgressInElectromagneticsResearch,vol.133,pp.259{283,2013.[26]G.Tsihrintzis,A.J.Devaneyetal.,\Higher-order(nonlinear)tomogra-phy:reconstructionalgorithmsandcomputersimulation,"ImageProcessing,IEEETransactionson,vol.9,no.9,pp.1560{1572,2000.[27]A.T.Vouldis,C.N.Kechribaris,T.Maniatis,K.S.Nikita,N.K.Uzunogluetal.,\Three-dimensionaltomographyusingbackpropagationandmul-tipleilluminationplanes,"InstrumentationandMeasurement,IEEETransactionson,vol.55,no.6,pp.1975{1984,2006.[28]A.Devaney,\Acomputersimulationstudyoftomography,"BiomedicalEngineering,IEEETransactionson,no.7,pp.377{386,1983.[29]S.PanandA.C.Kak,\Acomputationalstudyofreconstructionalgorithmsfortomography:interpolationversusbackpropagation,"Acoustics,SpeechandSignalProcessing,IEEETransactionson,vol.31,no.5,pp.1262{1275,1983.[30]X.PanandM.A.Anastasio,\Minimal-scanbackpropagationalgorithmsfortomography,"JOSAA,vol.16,no.12,pp.2896{2903,1999.[31]A.J.Devaney,\Thelimited-viewprobleminditomography,"Inverseprob-lems,vol.5,no.4,p.501,1989.[32]S.J.LaRoque,E.Y.Sidky,andX.Pan,\Accurateimagereconstructionfromfew-viewandlimited-angledataintomography,"JOSAA,vol.25,no.7,pp.1772{1782,2008.[33]H.Ayasso,B.Duch^ene,andA.Mohammad-Djafari,\Bayesianinversionforopticaltomography,"JournalofModernOptics,vol.57,no.9,pp.765{776,2010.101[34]Y.SungandR.R.Dasari,\Deterministicregularizationofthree-dimensionalopticaltomography,"JOSAA,vol.28,no.8,pp.1554{1561,2011.[35]M.A.AnastasioandX.Pan,\Full-andminimal-scanreconstructionalgorithmsforfan-beamtomography,"Appliedoptics,vol.40,no.20,pp.3334{3345,2001.[36]X.Pan,M.Anastasioetal.,\Onalimited-viewreconstructionproblemintomography,"MedicalImaging,IEEETransactionson,vol.21,no.4,pp.413{416,2002.[37]X.Pan,dreconstructiontheoryfortomography,withconsiderationofnoisecontrol,"JOSAA,vol.15,no.9,pp.2312{2326,1998.[38]P.Paladhi,A.Sinha,A.Tayebi,L.Udpa,andA.Tamburrino,\Dataredundancyintomography,"inAppliedComputationalElectromagnetics(ACES),201531stInternationalReviewofProgressin,March2015,pp.1{2.[39]G.A.TsihrintzisandA.J.Devaney,\Stochastictomography:Theoryandcomputersimulation,"Signalprocessing,vol.30,no.1,pp.49{64,1993.[40]M.A.AnastasioandX.Pan,\Investigationofthenoisepropertiesofanewclassofreconstructionmethodsintomography,"InternationalJournalofImagingSystemsandTechnology,vol.10,no.6,pp.437{445,1999.[41]E.J.CandeandM.B.Wakin,\Anintroductiontocompressivesampling,"SignalProcessingMagazine,IEEE,vol.25,no.2,pp.21{30,2008.[42]E.CandesandJ.Romberg,\Sparsityandincoherenceincompressivesampling,"Inverseproblems,vol.23,no.3,p.969,2007.[43]D.L.Donoho,\Compressedsensing,"InformationTheory,IEEETransactionson,vol.52,no.4,pp.1289{1306,2006.[44]C.E.Shannon,\Amathematicaltheoryofcommunication,"ACMSIGMOBILEMobileComputingandCommunicationsReview,vol.5,no.1,pp.3{55,2001.[45]E.J.Candes,J.Romberg,andT.Tao,\Robustuncertaintyprinciples:Exactsignalreconstructionfromhighlyincompletefrequencyinformation,"InformationTheory,IEEETransactionson,vol.52,no.2,pp.489{509,2006.102[46]E.J.Candes,J.K.Romberg,andT.Tao,\Stablesignalrecoveryfromincompleteandinaccuratemeasurements,"Communicationsonpureandappliedmathematics,vol.59,no.8,pp.1207{1223,2006.[47]E.J.CandesandT.Tao,\Near-optimalsignalrecoveryfromrandomprojections:Universalencodingstrategies?"InformationTheory,IEEETransactionson,vol.52,no.12,pp.5406{5425,2006.[48]M.F.Duarte,M.A.Davenport,D.Takhar,J.N.Laska,T.Sun,K.E.Kelly,R.G.Baraniuketal.,\Single-pixelimagingviacompressivesampling,"IEEESignalProcessingMagazine,vol.25,no.2,p.83,2008.[49]M.MishaliandY.C.Eldar,\Fromtheorytopractice:Sub-nyquistsamplingofsparsewidebandanalogsignals,"SelectedTopicsinSignalProcessing,IEEEJournalof,vol.4,no.2,pp.375{391,2010.[50]M.Lustig,D.Donoho,andJ.M.Pauly,\Sparsemri:Theapplicationofcompressedsensingforrapidmrimaging,"Magneticresonanceinmedicine,vol.58,no.6,pp.1182{1195,2007.[51]H.Jung,K.Sung,K.S.Nayak,E.Y.Kim,andJ.C.Ye,\k-tfocuss:Ageneralcompressedsensingframeworkforhighresolutiondynamicmri,"MagneticResonanceinMedicine,vol.61,no.1,pp.103{116,2009.[Online].Available:http://dx.doi.org/10.1002/mrm.21757[52]M.Lustig,D.Donoho,J.Santos,andJ.Pauly,\Compressedsensingmri,"SignalProcessingMagazine,IEEE,vol.25,no.2,pp.72{82,March2008.[53]R.Chartrand,\Fastalgorithmsfornonconvexcompressivesensing:Mrireconstruc-tionfromveryfewdata,"inBiomedicalImaging:FromNanotoMacro,2009.ISBI'09.IEEEInternationalSymposiumon.IEEE,2009,pp.262{265.[54]U.Gamper,P.Boesiger,andS.Kozerke,\Compressedsensingindynamicmri,"MagneticResonanceinMedicine,vol.59,no.2,pp.365{373,2008.[55]H.Jung,K.Sung,K.S.Nayak,E.Y.Kim,andJ.C.Ye,\k-tfocuss:Ageneralcompressedsensingframeworkforhighresolutiondynamicmri,"MagneticResonanceinMedicine,vol.61,no.1,pp.103{116,2009.103[56]K.Choi,J.Wang,L.Zhu,T.-S.Suh,S.Boyd,andL.Xing,\Compressedsensingbasedcone-beamcomputedtomographyreconstructionwithadermethoda),"Medicalphysics,vol.37,no.9,pp.5113{5125,2010.[57]Z.Zhu,K.Wahid,P.Babyn,D.Cooper,I.Pratt,andY.Carter,\Improvedcom-pressedsensing-basedalgorithmforsparse-viewctimagereconstruction,"Computa-tionalandmathematicalmethodsinmedicine,vol.2013,2013.[58]H.YuandG.Wang,\Compressedsensingbasedinteriortomography,"Physicsinmedicineandbiology,vol.54,no.9,p.2791,2009.[59]J.ProvostandF.Lesage,\Theapplicationofcompressedsensingforphoto-acoustictomography,"MedicalImaging,IEEETransactionson,vol.28,no.4,pp.585{594,2009.[60]A.Hanif,A.Mansoor,andT.Ejaz,\Iterativetomographicimagereconstructionbycompressivesampling,"inImageProcessing(ICIP),201017thIEEEInternationalConferenceon,Sept2010,pp.4313{4316.[61]S.Mallat,Awavelettourofsignalprocessing:thesparseway.Academicpress,2008.[62]G.Strang,\Thediscretecosinetransform,"SIAMreview,vol.41,no.1,pp.135{147,1999.[63]E.J.CandesandT.Tao,\Decodingbylinearprogramming,"InformationTheory,IEEETransactionson,vol.51,no.12,pp.4203{4215,2005.[64]D.Baron,M.F.Duarte,M.B.Wakin,S.Sarvotham,andR.G.Baraniuk,\Distributedcompressivesensing,"CoRR,vol.abs/0901.3403,2009.[Online].Available:http://arxiv.org/abs/0901.3403[65]S.BoydandL.Vandenberghe,Convexoptimization.Cambridgeuniversitypress,2004.[66]S.Hua,M.Ding,andM.Yuchi,\Sparse-viewultrasoundtomographyusingcompressedsensingwithnonuniformComputationalandmathematicalmethodsinmedicine,vol.2014,2014.104[67]M.M.Bronstein,A.M.Bronstein,M.Zibulevsky,andH.Azhari,\ReconstructioninultrasoundtomographyusingnonuniformMedicalImaging,IEEETransactionson,vol.21,no.11,pp.1395{1401,2002.[68]L.LibertiandN.Maculan,Globaloptimization:fromtheorytoimplementation.SpringerScience&BusinessMedia,2006,vol.84.[69]J.F.Sturm,\Usingsedumi1.02,amatlabtoolboxforoptimizationoversymmetriccones,"Optimizationmethodsandsoftware,vol.11,no.1-4,pp.625{653,1999.[70]S.S.Rao,Engineeringoptimization:theoryandpractice.JohnWiley&Sons,1996.[71]K.Deb,Optimizationforengineeringdesign:Algorithmsandexamples.PHILearn-ingPvt.Ltd.,2012.[72]Y.Saad,Iterativemethodsforsparselinearsystems.Siam,2003.105