Kernel Methods in Computer Vision

FoundationsandTrendsRinsampleVol.xx,Noxx(xxxx)1–96cxxxxxxxxxxxxxDOI:xxxxxxKernelMethodsinComputerVisionChristophH.Lampert11MaxPlanckInstituteforBiologicalCybernetics,72076Tübingen,Germany,@tuebingen.mpg.deAbstractOverthelastyears,kernelmethodshaveestablishedthemselvesaspow-erfultoolsforcomputervisionresearchersaswellasforpractitioners.Inthistutorial,wegiveanintroductiontokernelmethodsincomputervi-sionfromageometricperspective,introducingnotonlytheubiquitoussupportvectormachines,butalsolessknowntechniquesforregression,dimensionalityreduction,outlierdetectionandclustering.Additionally,wegiveanoutlookonveryrecent,non-classicaltechniquesforthepre-dictionofstructuredata,fortheestimationofstatisticaldependencyandforlearningthekernelfunctionitself.Allmethodsareillustratedwithexamplesofsuccessfulapplicationfromtherecentcomputervisionresearchliterature.Contents1Overview11.1TheGoalsofthisTutorial11.2WhatthisTutorialisnot22IntroductiontoKernelMethods42.1Notation42.2LinearClassification52.3Non-linearClassification132.4TheRepresenterTheorem152.5Kernelization172.6ConstructingKernelFunctions212.7ChoosingtheKernelFunctionanditsParameters223KernelsforComputerVision263.1DesigningImageKernels273.2IncorporatingInvariance283.3Region-BasedImageRepresentations37iiiContents4Classification444.1MulticlassSupportVectorMachines444.2Example:OpticalCharacterRecognition474.3Example:ObjectClassification474.4Example:SceneClassification484.5Examples:ActionClassification485OutlierDetection505.1GeometricOutlierDetectioninRd515.2SupportVectorDataDescription525.3One-ClassSupportVectorMachines535.4Example:Steganalysis545.5Example:ImageRetrieval546Regression556.1KernelRidgeRegression566.2SupportVectorRegression576.3Example:PoseEstimation597DimensionalityReduction607.1KernelPrincipalComponentAnalysis607.2KernelDiscriminantAnalysis637.3KernelCanonicalCorrelationAnalysis647.4Example:ImageDenoising657.5Example:FaceRecognition668Clustering678.1Kernel-PCAClustering678.2KernelVectorQuantization688.3SupportVectorClustering718.4Example:UnsupervisedObjectCategorization738.5Example:ClusteringofMulti-ModalData73Contentsiii9Non-ClassicalKernelMethods749.1StructuredPrediction749.2DependencyEstimation769.3Example:ImageSegmentation789.4Example:ObjectLocalization799.5Example:ImageMontages7910LearningtheKernel8010.1KernelTargetAlignment8110.2MultipleKernelLearning8110.3Example:ImageClassification8510.4Example:MulticlassObjectDetection851OverviewComputervisionhasestablisheditselfasabroadsubfieldofcomputerscience.Itspansallareasforbuildingautomaticsystemsthatextractinformationfromimages,coveringarangeofapplications,fromtheor-ganizationofvisualinformation,overcontrolandmonitoringtasks,tointeractiveandreal-timesystemsforhuman-computerinteraction.De-spitethisvariability,someprincipledalgorithmshaveemergedoverthelastyearsanddecadesthatareusefulinmanydifferentscenariosandtherebytranscendtheboundariesofspecificapplications.Onerecentlyverysuccessfulclassofsuchalgorithmsarekernelmethods.Basedonthefundamentalconceptofdefiningsimilaritiesbetweenobjectstheyallow,forexample,thepredictionofpropertiesofnewobjectsbasedonthepropertiesofknownones(classification,regression),ortheidenti-ficationofcommonsubspacesorsubgroupsinotherwiseunstructureddatacollections(dimensionalityreduction,clustering).1.1TheGoalsofthisTutorialWiththistutorial,weaimatgivinganintroductiontokernelmethodswithemphasisontheiruseincomputervision.Inthechapter“Intro-12OverviewductiontoKernelMethods”weusetheproblemofbinaryclassificationwithsupportvectormachinesasintroductoryexampleinordertomoti-vateandexplainthefundamentalconceptsunderlyingallkernelmeth-ods.Subsequently,“KernelsforComputerVision”givesanoverviewofthekernelfunctionsthathavebeenusedintheareaofcomputervision.Italsointroducesthemostimportantconceptsoneneedstoknowforthedesignofnewkernelfunctions.Althoughsupportvectormachines(SVMs)arethemostpopularexamplesofkernelmethods,theyarebyfarnottheonlyusefulones.Intherestofthistutorial,wecoveravarietyofkernelmethodsthatgobeyondbinaryclassification,namelyalgorithmsfor“MulticlassClassification”,“OutlierDetection”,“Regression”,“DimensionalityReduction”,and“Clustering”.Wealsoincludesomerecentnon-standardtechniques,namely“StructuredPre-diction”,“DependencyEstimation”andtechniquesfor“LearningtheKernel”fromdata.Ineachcase,afterintroducingtheunderlyingideaandmathematicalconcepts,wegiveexamplesfromthecomputervisionresearchliteraturewherethemethodshavebeenappliedsuccessfully.Itisourhopethatthisdouble-trackedapproachwillgivepointersintobothdirections,theoryandapplication,forthecommonbenefitofre-searchersaswellaspractitioners.1.2WhatthisTutorialisnotThisworkisnotmeanttoreplaceanintroductionintomachinelearn-ingorgenerickernelmethods.Thereareexcellenttextbooksforthispurpose,e.g.[SchölkopfandSmola,2002]and[Shawe-TaylorandCris-tianini,2004].Incontrasttoaformalintroduction,wewillsometimestakeshortcutsandappealtothereader’sgeometricintuition.Thisisnotoutofdisrespectfortheunderlyingtheoreticalconcepts,whichareinfacton