Real-time motion analysis with linear programming

ComputerVisionandImageUnderstanding78,32–52(2000)doi:10.1006/cviu.1999.0826,availableonlineat:[e-mail],[e-mail],[e-mail]2,1999;acceptedNovember5,1999Amethodtocomputemotionmodelsinrealtimefrompoint-to-linecorrespon-dencesusinglinearprogrammingispresented.Point-to-linecorrespondencesarethemostreliablemeasurementsforimagemotiongiventheapertureeffect,anditisshownhowtheycanapproximateothermotionmeasurementsaswell.Aner-rormeasureforimagealignmentusingtheL1metricandbasedonpoint-to-linecorrespondencesachievesresultswhicharemorerobustthanthoseforthecom-monlyusedL2metric.TheL1errormeasureisminimizedusinglinearprogram-ming.WhileestimatorsbasedonL1arenotrobustinthebreakdownpointsense,experimentsshowthattheproposedmethodisrobustenoughtoallowaccuratemo-tionrecoveryoverhundredsofconsecutiveframes.TheL1solutioniscomparedtostandardM-estimatorsandLeastMedianofSquares(LMedS)anditisshownthattheL1metricprovidesareasonableandefficientcompromiseforvariousscenar-ios.Theentirecomputationisperformedinreal-timeonaPCwithoutspecialhard-ware.c°2000AcademicPressKeyWords:motionanalysis;linearprogramming.1.INTRODUCTIONRobust,real-timerecoveryofvisualmotionisessentialformanyvision-basedapplica-tions.Numerousmethodshavebeendevelopedformotionrecoveryfromimagesequences;amongthemarealgorithmsthatcomputethemotiondirectlyfromthegreylevelvaluesorlocalmeasuresofthem[3,14,16,17,20].Asecondclassofalgorithmsusefeaturepointsoropticalflowtorecovermotion[1,9,15].Aprobabilisticerrorminimizationalgorithm[26]canbeusedtorecovermotioninthepresenceofoutliers.Anotherclassofalgorithmsuseexplicitprobabilitydistributionsofthemotionvectorstocalculatemotionmodels[23].BlackandAnandanpresented[7]aframeworkforrobustcalculationofopticalflowbased1ThisresearchwassupportedbyEspiritProject26247—Vigor.321077-3142/00$35.00Copyrightc°2000byAcademicPressAllrightsofreproductioninanyformreserved.MOTIONANALYSISBYLINEARPROGRAMMING33ontheLorentzianestimatorandaGraduatedNon-convexityalgorithmseekinganoptimalsolution.Bab-HadiasharandSuter[4]presentedarobustopticalflowcalculationbasedonLMedS(LeastMedianofSquares).Mostofthemethodscitedabovehaveproblemswhencomputinghigh-ordermotionmodels(e.g.,anaffinemotionmodelorahomography):eithertheyaresensitivetooutliers,ortheexecutionspeedisslow.AlgorithmsbasedoniterativereweightingM-estimatorshavetuningandinitialguessproblems,especiallyinmultiplemodelcases.TheLMedSfacescomplexityandaccuracyproblemswhenitisdifficulttoobtainagoodhypothesisbyrandomselection.Inthispaperanalgorithmtorecoverhigh-ordermotionmodelsfrompoint-to-linecorre-spondencesusinglinearprogrammingispresented.Point-to-linecorrespondencesarerobustinthesensethattheyarelargelyinsensitivetoapertureeffectsandtoT-junctions,unlikethecommonpoint-to-pointcorrespondences.Point-to-linecorrespondencescanalsoapproxi-mateothermeasurementsaswell,suchaspoint-to-pointcorrespondences,correspondenceswithuncertainty,andthespatiotemporalconstraint.TheL1metric(Pjai¡bij)canbeusedwiththepoint-to-linecorrespondencesandismuchmorerobustthentheL2metric(pP(ai¡bi)2).Forexample,themedianminimizestheL1metric,whilethecentroid(average)minimizestheL2metric.L1basedestimatorsarenotrobustinthesenseofbreakdownpoint[11,24,25]astheyaresensitivetoleveragepoints.However,ourexperimentsshowthatinmotionanalysistheL1errormeasureisrobustenoughtocomputeaccuratemotionoverhundredsofframes,evenwithlargemovingoutlierobjectsinthescene.Moreover,thisisdoneinrealtimeonaregularPC(300MHz).Thelinearprogrammingsolverdoesnotneedaninitialguessnoranoisescaleestimate,whicharerequiredforiterativereweightedleast-squarealgorithms(suchasM-estimators).ComparisonsbetweenestimatorsbasedontheL1metricandtherobustLMedSestimatorsshowthatglobalmotionanalysisusingtheL1estimatorisonlyslightlylessrobustthananalysiswiththeLMedSestimator,buttheL1computationismuchfaster.Themotionanalysisconsistsofcomputingamodelbasedalignmentbetweensuccessiveframes.Thealignmentprocessconsistsoftwosteps:(i)Computingcorrespondencesandrepresentingthemaspoint-to-linecorrespondencesisdescribedinSection2.(ii)Convertingthealignmentproblemintoalinearprogramusingthepoint-to-linecorrespondencesandsolvingitisdescribedinSection3.Section4describesexperimentalresultsandcomparisonswithothermethods.Section5givesconcludingremarks.TheAppendixdescribesapossibleexplanationfortheexperimentalinsensitivityofL1motionestimatorstoleveragepoints.2.POINT-TO-LINECORRESPONDENCESPoint-to-linecorrespondencesareusedduetotheirinsensitivitytotheapertureeffect.Thissectiondescribestheapertureeffect,pointselectionforthepoint-to-linecorrespon-dence,andtheuseofpoint-to-linecorrespondencestorepresentnormalflowandfuzzycorrespondences.2.1.ApertureEffectAmovinglineviewedthroughasmallaperturewillhaveanapparentmotionwhichisnormaltotheline.Thisphenomenaiscalledthe“apertureeffect.”Anexampleofthe