Advances in Computer Vision and Pattern Recognition Forfurthervolumes: www.springer.com/series/4205 A. Criminisi (cid:2) J. Shotton Editors Decision Forests for Computer Vision and Medical Image Analysis Editors A.Criminisi J.Shotton MicrosoftResearchLtd. MicrosoftResearchLtd. Cambridge,UK Cambridge,UK SeriesEditors Prof.SameerSingh Dr.SingBingKang ResearchSchoolofInformatics MicrosoftResearch LoughboroughUniversity MicrosoftCorporation Loughborough Redmond,WA UK USA ISSN2191-6586 ISSN2191-6594(electronic) AdvancesinComputerVisionandPatternRecognition ISBN978-1-4471-4928-6 ISBN978-1-4471-4929-3(eBook) DOI10.1007/978-1-4471-4929-3 SpringerLondonHeidelbergNewYorkDordrecht LibraryofCongressControlNumber:2013930423 ©Springer-VerlagLondon2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpub- lication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforany errorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespect tothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) In memory of Josh, a wonderful brother, dearlymissed Foreword Wearegratefultotheauthorsforinvitingustocommentontheevolutionofrandom decision forests. We will begin by recounting our participation in the history (and hope that the evoked memories are not randomized), continue with the recent and dramaticadvancesinbothresearchandscholarshipreportedinthebook,andfinish withsomespeculativeremarks. Forus,thestorystartsintheSpringof1994whenwewerefailingtoaccurately classifyhandwrittendigitsusingadecisiontree.Wewereprettyconfidentthatthe features,whichposedquestionsaboutthespatialrelationshipamonglocalpatterns, werediscriminating.Butwecouldnotasknearlyenoughofthemandthebestclassi- ficationratewasjustabove90%.TheNISTdatasethadabout6,000trainingimages perdigit,butasanybodyknowswhohasinducedadecisiontreefromdata,thesam- plesizegoesdownfastandestimationerrorstakeover.Sowecouldnotaskmore thansaytenquestionsalonganybranch.Wetriedtherecipesforpruningin[45]and elsewhere,andotherwaystomitigateover-fitting,butnoamountoffiddlingmade muchofadifference. Althoughbuildingmultipletreeswasthe“obvious”thingtodo,ithadn’toccurred tousuntilthen.Thefirsteffort,whichinvolvedmakingtentreesbydividingthepool ofquestionsamongthetrees,workedsplendidlyandlifteduswellabove95%.We sensed a breakthrough. Subsequently, we explored different randomization proce- duresandratherquicklysettledongeneratingasmallrandomsampleofthequestion poolateverynodeofeverytree,eventuallyexceeding99%accuracywithaforest ofmanytrees. Thefeatureswerebinaryqueriesabouttherelativelocationsoflocalfeaturesand hence did not require any normalization or preprocessing of the image. The space ofrelationalgraphsisverylargeandprovidedaveryrichsourceoflinkedqueries. Eachtreeprobedsomeaspectsofanessentiallyinfinitegraphofrelationships,with eachnewquestionrefiningtheaccumulatedstructure.Inthisway,growingthetrees providedagreedymechanismtoexplorethisspaceofrepresentations.Wealsoex- ploredclusteringshapespacebygrowinggenerictreeswithunlabeleddata[5],as well as initially growing trees with a small number of classes and then reestimat- ing leaf node distributions and possibly deepening the trees with additional data vii viii Foreword from new classes. The work on trees for density estimationand manifoldlearning describedinthisbookdevelopstheseideasinmultiple,fascinatingdirections. InOctober1994webothwenttoaworkshoponstatisticsandinformationthe- ory [169], where we met Leo Breiman. One of us (DG) spoke about “randomized trees”attheworkshop;thiswasthenameweusedinatechnicalreport[4].Atthe workshop,andcontinuingoverdinner,wediscussedtreeswithLeo,whodescribed “bagging” (re-sampling the training set). We were all excited about advancing in- ductive learning with randomized classifiers. Soon after we became aware of two closely related lines of research. One was boosting, introduced earlier by Freund andShapire.TheotherwastheworkofHo[165],alsopublishedinthemid-1990s, which independently introduced a variation on randomization. In 1999 DG spent timewithLeoatanotherconference[298]discussingthetradeoffsbetweensingle- treeaccuracyandtree-to-treecorrelationasthedegreeofrandomnesswasvaried. Fromourperspectivethesourceofsuccessofbothboostingandrandomization wastheabilitytocreatemoderatelyaccuratetreesthatareweaklycorrelatedcondi- tionalontheclass.Boostingachievesthisthroughtheincreasedweightsonthemis- classifiedtrainingsamples,andislargelyinsensitivetotheparticularre-weighting protocol.Randomizationachievesthisthroughsparsesamplingfromalargespace of queries. In fact, both methods effectively sample the trees from some distribu- tion on the space of trees; randomized trees do this explicitly and boosting in the limit cycle of a deterministic tree-generating process (see the discussion [113] of Breiman’s 1997 paper on ARCing). By the way, back in 1994 we had speculated with Leo that baggingmight be too stable,i.e. the distributionover trees resulting frommerere-samplingofthedatamightbetooconcentrated.Withwell-separated classes boosting can achieve lower error rates, but there is a risk of over-fitting; asdiscussedin[3], a combinationofboostingandrandomizationiseffectivewith multipleclasses. Random forests had very strong competition during the nineties from support vectormachines.Whereasinpracticetheresultsonstandardproblemsareaboutthe same,SVMshadtheappealofacleanoptimizationframework,well-understoodal- gorithmsandanarrayoftheoreticalresults.Morerecently,randomforestshavebe- comepopularincomputationalgenomics,probablyduetotherelativetransparency of the decision rules. Random forests have two other important advantages: speed and minimal storage. Nonlinear SVMs require storing large numbers of training samples, and computing large numbers of inner products. In contrast, it is hard to find something more efficient than storing and answering a series of simple ques- tions. This brings us to recent applications of decision and regression forests. Surely thebestknownisnowtheKinectskeletontracker;itisimpressivehowwellsimple depth-based comparison questions work. The Kinect solution is particularly inter- esting in that it synthesizes randomization with relational shape queries, the gen- eralized Hough transform and shape context, which has proven very powerful in shaperecognition.Themainproblemwiththeoriginalformulationofshapecontext in [24] was the intense computation; exploring the neighborhood of a pixel using randomizedtreesprovidesaveryefficientalternative.Alsorelatedistheapplication Foreword ix of regression forests to anatomy detection in 3D computed tomography (CT) im- ages;usingaformofgeneralizedHoughtransformthatistrainedwithapredictive machinesuchasrandomforestsopensupmanyinterestingpossibilities.Themany otherapplicationspresentedinthisbookfurtherandconvincinglydemonstratethat sequential,adaptivelearningandtestingcanprovideaunifyingframeworkformany ofthemajortasksofmoderncomputationallearning. Lookingahead,wehopetheseefficientandversatiletoolswillspreadintomore applications. Many theoretical questions also remain open, such as determining conditions under which randomized forests really provide an advantage, as well as guidelines for selecting parameters such as tree depth, forest size and sampling density. Finally, whereas a decision forest efficiently integrates evidence by ask- ing a great many questions in total, it still does not capture the full discriminating power of “20 questions” because the “line of reasoning” is broken with each new tree. In principle a single tree can develop a long series of linked questions which continuebuildingoneachother,progressingsystematicallyfromcoarsetofineand exploringsomeaspectoftheobjectunderstudyindepth.Forexample,incomputer vision,onemightneed100questionstoaccumulateadetailedunderstandingabout a complexeventinthe sceneinvolvingmultipleagentsand actions.However,this is impossible in practice with current methodology: how would one store such a deeptreeeveniftherewasenoughtimeanddatatolearnitoramodelunderwhich probabilitiescouldbeupdatedandnewqueriesscored?Perhapstheanswerisonline construction. After all, at run time (e.g. during scene parsing), only one branch of eachtreeistraversed—theonedictatedbythedatabeingprocessed.Consequently, onlinelearningmightbefeasibleinsomecases;atrackingexample,whichdoesnot scaleuptothecomplexproblemstreatedinthisbook,wasexploredin[123].Going furtherwillrequirelearninghowtomaintainaprobabilitydistributionoverstatesof interestconditionalonalltheaccumulatedevidence. Baltimore,USA YaliAmit DonaldGeman Preface This book discusses the theoretical underpinnings of decision forests1 as well as theirpracticalapplicationsinmanyautomaticimageanalysistaskstypicalofcom- putervisionandmedicalimageanalysis. Decisionforestshaverecentlybecomeanindispensabletoolforautomaticimage analysis,asdemonstratedbythevastliteratureonthesubject.Thisbookattemptsto organizetheexistingliteraturewithinashared,flexibleforestmodelthatiscapable ofaddressingalargeanddiversesetofimageanalysistasks.Theversatilityofdeci- sionforestsisalsoreflectedintheprovidedresearchcode:acompact,flexibleand userfriendlysoftwarelibraryaimedathelpingthereadertoexperimentwithforests inahands-onmanner. This book is directed at both students who wish to learn the basics of decision forests,moreestablishedresearcherswhowishtobecomemorefamiliarwithforest- based learning, and finally practitioners who wish to explore modern and efficient imageanalysistechniques.Thebookisdividedintothreeparts: • PartIpresentsourcoherentmodelofforests,itstheoreticalfoundations,andits applicationstovarioustaskssuchasclassification,regression,densityestimation, manifoldlearningandsemi-supervisedclassification. • PartIIcontainsanumberofinvitedchaptersthatdemonstratetheapplicationof foreststopracticaltaskssuchaspedestriantracking,humanbodyposeestimation, pixel-wise semantic segmentation of images and videos, automatic parsing of medical3Dscans,anddetectionanddelineationofbrainlesions. • Part III discusses practical implementation details, describes the provided soft- warelibrary,andpresentsconcludingremarks. We truly hope that this book can serve as a springboard to further exciting re- searchinautomaticimageandvideounderstanding. Cambridge,UK AntonioCriminisi JamieShotton 1Throughoutthebookweusetheterms“randomforests”,“randomizedtrees”,“decisionforests” or“randomdecisionforests”interchangeably. xi