practical59ddd.com

W.
SteveG.
Mann"ComparametricTransformsforTransmitting.
.
.
"TheTransformandDataCompressionHandbookEd.
K.
R.
Raoetal.
BocaRaton,CRCPressLLC,2001Chapter3ComparametricTransformsforTransmittingEyeTapVideowithPictureTransferProtocol(PTP)W.
SteveG.
MannUniversityofTorontoEyeTapvideoisanewgenreofvideoimagingfacilitatedbyandfortheapparatusoftheauthor'seyeglass-based"wearablecomputer"invention[1].
Thisinventiongivesrisetoanewgenreofvideothatisbestprocessedandcompressedbywayofcomparametricequations,andcomparametricimageprocessing.
Thesenewmeth-odsarebasedonanEdgertonianphilosophy,insharpdeparturefromthetraditionalNyquistphilosophyofsignalprocessing.
Anewtechniqueisgivenforestimatingthecomparameters(relativeparametersbetweensuccessiveframesofanimagese-quence)takenwithacamera(orEyeTapdevice)thatisfreetopan,tilt,rotateaboutitsopticalaxis,andzoom.
Thistechniquesolvestheproblemfortwocasesofstaticscenes:imagestakenfromthesamelocationofanarbitrary3-Dsceneandimagestakenfromarbitrarylocationsofaatscene,whereitisassumedthatthegazepatternoftheeyesweepsonamuchfastertimescalethanthemovementofthebody(e.
g.
,anassumptionthatimageowacrosstheretinainducedbychangeineyelocationissmallcomparedtothatinducedbygazepattern).
3.
1Introduction:WearableCyberneticsWearablecyberneticsisbasedontheWearCompinventionofthe1970s,originallyintendedasawearableelectronicphotographer'sassistant[2].
3.
1.
1HistoricalOverviewofWearCompAgoaloftheauthor'sWearComp/WearCam(wearablecomputerandpersonalimaging)inventionsofthe1970sandearly1980s(Fig.
3.
1)wastomakethemetaphoroftechnologyasanextensionofthemindandbodyintoareality.
Insomesense,theseinventionstransformedthebodyintonotjustacamera,butalsoanetworkedcyberneticentity.
Thebodythusbecamepartofasystemalwaysseekingthebestpicture,inallfacetsofordinaryday-to-dayliving.
Thesesystemsservedtoillustratetheconceptofthecameraasatrueextensionofthemindandbodyofthewearer.
FIGURE3.
1PersonalImaginginthe1970sand1980s:Earlyembodimentsoftheauthor'sWearCompinventionthatfunctionedasa"photographer'sassistant"foruseintheeldofpersonalimaging.
(a)Author'searlyheadgear.
(b)Author'searly"smartclothing"includingcyberneticjacketandcyberneticpants(continued).
3.
1.
2EyeTapVideoEyeTapvideo[3]isvideocapturedfromthepencilofraysthatwouldotherwisepassthroughthecenterofthelensoftheeye.
TheEyeTapdeviceistypicallywornlikeeyeglasses.
FIGURE3.
1(Cont.
)(c)Author's1970schordingkeyboardcomprisingswitchesmountedtoalightsource,similartothemid1980sversiondepictedinauthor'srighthandin(b).
3.
2TheEdgertonianImageSequenceTraditionalimagesequencecompression,suchasMPEG[4,5](see,forexample,theMovingPictureExpertGroupFAQ),isbasedonprocessingframesofvideoasacontinuum.
Theintegrityofmotionisoftenregardedasbeingmoreimportantthan,oratleastasimportantas,theintegrityofeachindividualframeoftheimagesequence.
However,itcanbearguedthattemporalintegrityisnotalwaysoftheutmostimportanceandcan,infact,oftenbesacricedwithgoodreason.
3.
2.
1EdgertonianversusNyquistThinkingConsidertheverytypicalsituationinwhichtheframerateofapictureacquisi-tionprocessvastlyexceedstheframerateatwhichitispossibletosendpicturesofsatisfactoryqualityoveragivenbandwidth-limitedcommunicationschannel.
Thissituationarises,forexample,withWeb-basedcameras,includingtheWearableWire-lessWebcam[6].
Supposethatthecameraprovides30picturespersecond,butthechannelallowsustosendonlyonepicturepersecond(ignoreforthemomentthefactthatwecantradespatialresolution,temporalresolution,andcompressionqualitytoadjusttheframerate).
Inordertodownsampleour30picturespersecondtoonepicturepersecond,the"Nyquistschoolofthought"wouldsuggestthatwetemporallylowpassltertheimagesequenceinordertoremoveanytemporalfrequenciesthatwouldexceedtheNyquistfrequency.
Toapplythisstandard"lowpasslterthendownsample"approach,wemightaverageeach30successivepicturestoobtainoneoutputpicture.
Thus,fastmovingobjectswouldbeblurredtopreventtemporalaliasing.
Wemightbetemptedtothinkthatthisblurringisdesirable,giventemporalalias-ingthatwouldotherwiseresult.
However,cinematographersandotherswhoproducemotionpicturesoftendisregardconcepts'temporalaliasing.
Mostnotably,HaroldE.
Edgerton[7],inventoroftheelectronicashandknownforhismoviesofhighspeedeventsinwhichobjectsare"frozen"intime,hasproducedmoviesandotherartifactsthatdefyanyavoidanceoftemporalaliasing.
Edgerton'smoviesprovideuswithatemporalsamplingthatismorelikeaDiraccomb(downsamplingofreality)thanalowpass-lteredandthendownsampledversionofreality.
Fortheexampleofdown-samplingfrom30framespersecondtooneframepersecond,anEdgertonianthinkerwouldlikelyadvocatesimplytakingevery30thframefromtheoriginalsequenceandthrowingalltheothersaway.
TheEdgertoniandownsamplingphilosophygivesrisetoimagesequencesinwhichpropellerbladesorwagonwheelspokesappeartospinbackwardsorstandstill.
TheNyquistphilosophy,ontheotherhand,givesrisetoimagesequencesinwhichthepropellerbladesorwagonwheelspokesvisuallydisappear.
Theauthorbelievesthatitispreferablethatthepropellerbladesandwagonwheelspokesappeartospinbackwards,orstandstill,ratherthanvisuallydisappear.
Moregenerally,animportantassumptionuponwhichthethesisofthischapterrestsisthatitispreferabletohaveaseriesofcrispwell-dened"snapshots"ofreality,ratherthantheblurofimagesthatonewouldgetbyfollowingtheantialiasingapproachoftraditionalsignalprocessing.
Theauthor'spersonalexperiencewithhiswearableEyeTapvideocamerainven-tion,wearingthecameraoften8to16hoursaday,ledtoanunderstandingofhowtheworldlooksthroughWeb-basedvideo.
Onthissystem,itwaspossibletochoosefromamongvariouscombinationsofEdgertonianandNyquistsamplingstrategies.
Itwasfoundthatexperiencingtheworldthrough"Edgertonianeyes"wasgenerallypreferabletotheNyquistapproach.
3.
2.
2FramesversusRows,Columns,andPixelsThereisatrendnowtowardprocessingsequencesofimagesasspatio-temporalvolumes,e.
g.
,asafunctionf(x,y,t).
Withinthisconceptualframework,motionpicturesaretreatedasstaticthree-dimensionalvolumesofdata.
So-calledspatio-temporalltersh(x,y,t)areappliedtothesespatio-temporalvolumesf(x,y,t).
However,thisuniedtreatmentofthethreedimensions(discretizedtorow,col-umn,andframenumber)ignoresthefactthatthetimedimensionhasamuchdif-ferentintuitivemeaningthantheothertwodimensions.
Apartfromtheprogressive(forward-only)directionoftime,thereisthemoreimportantfact(evenforstoredimagesequences)thatasnapshotintime(astillpictureselectedfromthesequence)oftenhasimmediatemeaningtothehumanobserver.
Asinglerowofpixelsacrossapictureorasinglecolumnofpixelsdownapicturedonotgenerallyhavesimilarsignicancetothehumanobserver.
Likewise,asinglepixelmeanslittletothehumanobserverintheabsenceofsurroundingpixels.
Notwithstandingtheirutility,slicesoftheformf(x,y0,t)oroftheformf(x0,y,t)areoftenconfusingatbest,comparedtothestillpicturef(x,y,t0)thatremainsasanextractionfromapicturesequencewhichisfarmoremeaningfultoatypicalhumanobserver.
Thustheauthorbelievesthatdownsamplingacrossrowsordownsamplingdowncolumnsofanimageshouldbeprecededbylowpassltering,whereastemporaldownsamplingshouldnot.
Thereis,therefore,aspecialsignicancetothenotionofa"snapshotintime"andtheprocessing,storage,transmission,etc.
ofamotionpictureasasequenceofsuchsnapshots.
TheobjectofthischapteristobetterunderstandtherelationshipbetweenindividualsharplydenedframesofanEdgertoniansequenceofpictures.
3.
3PictureTransferProtocol(PTP)Whenapplyingdatacompressiontoastreamofindividualpicturesthatwillbeviewedinreal-time(forexample,invideoconferencing,suchastherst-person-perspectivevideoconferencingofthewearableEyeTapdevice),itishelpfultocon-siderthemannerinwhichthedatawillbesent.
Mostnotably,picturesaretypicallysentoverapacket-basedcommunicationschannel.
Forexample,WearableWirelessWebcamusedtheAX25AmateurRadio[8]protocol.
Accordingly,packetstypicallyarriveeitherintactorcorrupted.
Packetsthatarecorrupttraditionallywouldberesent.
Aninterestingapproachistoprovidedatacompressiononaper-imagebasis,andtovarythedegreeofcompressionsothatthesizeofeachpictureintheimagesequenceisexactlyequaltothelengthofonepacket.
Togetherwiththepriorassumption(thatimagesareacquiredataratethatexceedsthechannelcapacity),itwillgenerallybetruethatbythetimeweknowthatapacket(whichisacompletepicture)iscorruptatthereceiver,anewerpicturewillhavealreadybeenacquired.
Forexample,iftheroundtriptime(RTT)were100ms(whichisequaltothetimeittakestogeneratethreepictures),therewouldbelittlesenseinresendingapicturethatwastakenthreepicturesago.
ThecommonlyarisingsituationinwhichpicturesarecapturedataratethatexceedstheRTTsuggeststhattherewillalwaysbenewerpictureinformationatthetransmitsitethanwhatwouldberesentintheeventofalostpacket.
ThisapproachformsthebasisforthePictureTransferProtocol(PTP)proposedbytheauthor.
Inparticular,PTPisbasedontheideaoftreatingeachsnapshotintimeasasingleentity,inisolation,andcompressingitintoasinglepacket,soitwillhaveeitherarrivedinitsentiretyornotarrivedatall(andthereforecanbediscarded).
ItshouldbeclearthatthephilosophicalunderpinningsofPTParecloselyrelatedtothoseofEdgertoniandownsampling.
3.
4BestCaseImagingandFearofFunctionalityAdirectresultofEdgertoniansamplingisthatasinglepicturefromapicturesequencehasahighdegreeofrelevanceandmeaningevenwhenitistakeninisolation.
Similarly,adirectresultofPTPisthatasinglepacketfromapacketsequencehasahighdegreeofrelevanceandmeaningevenwhenitistakeninisolation(forexample,whenthepacketsbeforeandafterithavebeencorrupted).
Itisthereforeapparentthatifasystemwerehighlyunreliable,totheextentthatpicturescouldbetransmittedonlyoccasionallyandunpredictably,thentheEdgertoniansamplingcombinedwithPTPwouldprovideasystemthatwoulddegradegracefully.
Indeed,ifweweretorandomlyselectjustafewframesfromoneofEdgerton'smotionpictures,wewouldlikelyhaveagoodsummaryofthemotionpicture,sinceanygivenframewouldprovideuswithasharppictureinwhichsubjectmatterofinterestcouldbeclearlydiscerned.
Likewise,ifweweretorandomlyselectafewpacketsfromastreamofthousandsofpacketsofPTP,wewouldhavedatathatwouldprovideamuchmoremeaningfulinterpretationtothehumanobserverthanifallwehadwererandomlyselectedpacketsfromanMPEGsequence.
Personalimagingsystemsarecharacterizedbyawearableincidentalist"alwaysready"modeofoperationinwhichthesystemneednotalwaysbefunctioningtobeofbenet.
Itisthepotentialfunctionality,ratherthantheactualfunctionality,ofsuchasystemthatmakesitsodifferentfromotherimagingsystemssuchashand-heldcamerasandthelike.
Accordingly,anobjectofthepersonalimagingprojectistoprovideasystemthattransmitspicturesinharshorhostileenvironments.
Oneapplicationofsuchasystemisthepersonalsafetydevice(PSD)[9].
ThePSDdiffersfromotherwirelessdatatransmissionsystemsinthesensethatitwasdesignedfor"bestcase"operation.
Ordinarily,wirelesstransmissionsaredesignedforworstcasescenarios,suchasmightguaranteeacertainminimumlevelofperformancethroughoutalargemetropolitanarea.
ThePSD,however,isdesignedtomakeithardforanadversarytoguaranteetotalnonperformance.
ItisnotagoalofthePSDtoguaranteeconnectivityinthepresenceofhostilejammingoftheradiospectrumbut,rather,tomakeitdifcultfortheadversarytoguaranteetheabsenceofconnectivity.
Therefore,anotherwisepotentialperpetratorofacrimewouldneverbeabletobecertainthatthewearer'sdevicewasnonoperationalandwouldthereforeneedtobeonhisorherbestbehavioratalltimes.
Traditionalsurveillancenetworks,basedonso-calledpublicsafetycamerasystems,havebeenproposedtoreducetheallegedlyrisinglevelsofcrime.
However,buildingsuchsurveillancesuperhighwaysmaydolittletoprevent,forexample,crimebyrepresentativesofthesurveillancestate,orthosewhomaintainthedatabaseofimages.
Humanrightsviolationscancontinue,orevenincrease,inapolicestateoftotalstatesurveillance.
Thesamecanbetrueofownersofanestablishmentwheresurveillancesystemsareinstalledandmaintainedbytheseestablishmentowners.
AnexampleisthefamousLatashaHarlinscase,inwhichashopperwasfalselyaccusedofshopliftingbyashopkeeperandwasthenshotdeadbytheshopkeeper.
Therefore,whatisneededisaPSDtofunctionasacrimedeterrent,particularlywithregardtocrimesperpetratedbythosefurtheruptheorganizationalhierarchy.
Sincethereisthepossibilitythatonlyonepacket,whichcontainsjustonepicture,wouldprovideincriminatingevidenceofwrongdoing,individualscanwearaPSDtoprotectthemselvesfromcriminals,assailants,andattackers,notwithstandinganypublicorcorporatevideosurveillancesystemalreadyinplace.
Animportantaspectofthisparadigmisthefearoffunctionality(FoF)model.
Thebalanceisusuallytippedinfavorofthestateorlargeorganizationinthesensethatstate-orcorporate-ownedsurveillancecamerasaretypicallymountedonxedmountpointsandnetworkedbywayofhighbandwidthlandlines.
ThePSD,ontheotherhand,wouldbeconnectedbywayofwirelesscommunicationchannelsoflimitedbandwidthandlimitedreliability.
Forexample,inthebasementofadepartmentstore,theindividualhasalesserchanceofgettingareliabledataconnectionthandoesthestore-ownedsurveillancecameras.
Justasmanydepartmentstoresuseamixtureoffake,nonfunctionalcamerasandrealones,sothecustomerneverknowswhetherornotagivencameraisoperational,whatisneededisasimilarmeansofbestcasevideotransmission.
Notknowingwhetherornotoneisbeingheldaccountableforhisactions,onemustbeonhisbestbehavioratalltimes.
Thus,anewphilosophy,basedonFoF,canbecomethebasisofdesignforimagecompression,transmission,andrepresentation.
Fig.
3.
2(a)illustratesanexampleofacomparisonbetweentwosystems,SYSTEMA,andSYSTEMB.
Thesesystemsaredepictedastwoplots,inahypotheticalpa-rameterspace.
Theparameterspacecouldbetime,position,orthelike.
Forexample,SYSTEMAmightworkacceptably(e.
g.
,meetacertainguaranteeddegreeoffunc-tionalityFGUAR)everywhereatalltimes,whereasSYSTEMBmightworkverywellsometimesandpoorlyatothers.
Muchengineeringismotivatedbyanarticulabilitymodel,i.
e.
,thatonecanmakeanarticulablebasisforchoosingSYSTEMAbecauseitgivesthehigherworstcasedegreeoffunctionality.
Anewapproach,however,reversesthisargumentbyregardingfunctionalityasabadthing—badfortheperpetratorofacrime—ratherthanagoodthing.
Thusweturnthewholegraphonitshead,and,lookingattheprobleminthisreversedlight,cometoanewsolution,namelythatSYSTEMBisbetterbecausetherearetimeswhenitworksreallywell.
Imagine,forexample,auserinthesub-basementofabuilding,insideanelevator.
SupposeSYSTEMAwouldhavenohopeofconnectingtotheoutsideworld.
SYS-FIGURE3.
2FearofFunctionality(FoF):(a)Giventwodifferentsystems,SYSTEMAhavingaguaranteedminimumleveloffunctionalityFGUARthatexceedsthatofSYS-TEMB,anarticulablebasisforselectingSYSTEMAcanbemade.
Suchanarticulablebasismightappealtolawyers,insuranceagents,andotherswhoareinthebusinessofguaranteeingeasilydenedarticulableboundaries.
However,athesisofthischapteristhatSYSTEMBmightbeabetterchoice.
Moreover,giventhatwearedesigningandbuildingasystemlikeSYSTEMB,traditionalworstcaseengineeringwouldsuggestfocusingonthelowestpointoffunctionalityofSYSTEMB(continued).
TEMB,however,throughsomestrangequirkofluck,mightactuallywork,butwedon'tknowinadvanceonewayortheother.
Thefactofthematter,however,isthatonewhowashopingthatthesystemwouldnotfunction,wouldbemoreafraidofSYSTEMBthanSYSTEMAbecauseitwouldtakemoreefforttoensurethatSYSTEMBwouldbenonfunctional.
TheFoFmodelmeansthatifthepossibilityexiststhatthesystemmightfunctionpartofthetime,awould-beperpetratorofacrimeagainstthewearerofthePSDmustbeonhisorherbestbehavioratalltimes.
Fig.
3.
2(b)depictswhatwemightdotofurtherimprovethe"fearfactor"ofSYS-TEMB,toarriveatanewSYSTEMB.
ThenewSYSTEMBischaracterizedbybeingevenmoreidiosyncratic;theoccasionaltimesthatSYSTEMBworks,itworksverywell,butmostofthetimeiteitherdoesn'tworkatallorworksverypoorly.
Othertechnologies,suchastheInternet,havebeenconstructedtoberobustenoughtoresistthehegemonyofcentralauthority(oranattackofwar).
However,animpor-FIGURE3.
2(Cont.
)(b)Instead,itisproposedthatonemightfocusone'seffortsonthehighestpointoffunctionalityofSYSTEMB,tomakeitevenhigher,attheexpenseoffurtherdegradingtheSYSTEMBworstcase,andevenattheexpenseofdecreasingtheoverallaverageperformance.
ThenewSYSTEMBisthussharplyserendipitous(peakedinitsspaceofvarioussystemparameters).
tantdifferencehereisthattheFoFparadigmisnotsuggestingthedesignofrobustdatacompressionandtransmissionnetworks.
Quitetheoppositeistrue!
TheFoFparadigmsuggeststheoppositeofrobustnessinthatSYSTEMBisevenmoresensitivetomildperturbationsintheparameterspaceabouttheoptimaloperatingpoint,POPT,thanisSYSTEMB.
Inthissense,ourpreferredSYSTEMBisactuallymuchlessrobustthanSYSTEMB.
Clearlyitisnotrobustness,inandofitself,thattheauthorisproposinghere.
ThePSDdoesn'tneedtoworkconstantlybutrathermustsimplypresentcriminalswiththepossibilitythatitcouldworksometimesorevenjustoccasionally.
Thisscenarioformsthebasisforbest-casedesignasanalternativetotheusualworst-casedesignparadigm.
Thepersonalimagingsystemthereforetransmitsvideo,butthedesignofthesystemissuchthatitwill,attheveryleast,occasionallytransmitameaningfulstillimage.
Likewise,thephilosophyfordatacompressionandtransformsneedstobecompletelyrethoughtforthisFoFmodel.
Thisrethinkingextendsfromthetransformsandcompressionapproachrightdowntothephysicalhardware.
Forexample,typicallythewearer'sjacketfunctionsasalargelowfrequencyantenna,providingtransmissioncapabilityinafrequencybandthatisveryhardtostop.
Forexample,the10-meterbandisagoodchoicebecauseofitsunpredictableperformance(owingtovarious"skip"phenomena,etc.
).
How-ever,otherfrequenciesarealsousedinparallel.
Forexample,apeer-to-peerformofinfraredcommunicationisalsoincludedto"infect"otherparticipantswiththepossibilityofhavingreceivedanimage.
Inthisway,itbecomesnearlyimpossibleforapolicestatetosuppressthesignalbecauseofthepossibilitythatanimagemayhaveescapedaniron-stedregime.
ItisnotnecessarytohavealargeaggregatebandwidthtosupportanFoFnetwork.
Infact,quitetheopposite.
Sinceitisnotnecessarythateveryonetransmiteverythingtheysee,atalltimes,verylittlebandwidthisneeded.
Itisonlynecessarythatanyonecouldtransmitapictureatanytime.
Thispotentialtransmission(e.
g.
,fearoftransmission)doesnotevenneedtobedoneontheInternet;forexample,itcouldsimplybefromonepersontoanother.
3.
5ComparametricImageSequenceAnalysisVideosequencesfromthePSDaregenerallycollectedandassembledintoasmallnumberofstillimages,eachstillimagebeingrobusttothepresenceorabsenceofindividualconstituentframesofthevideosequencefromwhichitiscomposed.
Processingvideosequencesfromtheapparatusoftheauthor'sEyeTapcamerarequiresndingthecoordinatetransformationbetweentwoimagesofthesamesceneorobject.
Whethertorecovergazemotionbetweenvideoframes,stabilizeretinalimages,relateorrecognizeEyeTapimagestakenfromtwodifferenteyes,computedepthwithina3-Dscene,oralignimagesforlookpainting(high-resolutionenhance-mentresultingfromlookingaround),itisdesiredtohavebothaprecisedescriptionofthecoordinatetransformationbetweenapairofEyeTapvideoframes,andsomeindicationastoitsaccuracy.
Traditionalblockmatching[10](suchasusedinmotionestimation)isreallyaspecialcaseofamoregeneralcoordinatetransformation.
Thischapterproposesasolutiontothemotionestimationproblemusingthismoregeneralestimationofacoordinatetransformation,togetherwithatechniqueforautomaticallyndingthecomparametricprojectivecoordinatetransformationthatrelatestwoframestakenofthesamestaticscene.
Thetechniquetakestwoframesasinputandautomaticallyoutputsthecomparametersoftheexactmodeltoaligntheframes.
Itdoesnotrequirethetrackingorcorrespondenceofexplicitfeatures,yetitiscomputationallypractical.
Althoughthetheorypresentedmakesthetypicalassumptionsofstaticsceneandnoparallax,theestimationtechniqueisrobusttodeviationsfromtheseassumptions.
Inparticular,thetechniqueisappliedtoimageresolutionenhancementandlookpaint-ing[11],illustratingitssuccessonavarietyofpracticalanddifcultcases,includingsomethatviolatethenonparallaxandstaticsceneassumptions.
Acoordinatetransformationmapstheimagecoordinates,x=[x,y]T,toanewsetofcoordinates,x=[x,y]T.
Generally,theapproachtondingthecoordinatetransformationreliesonassumingthatitwilltakeoneofthemodelsinTable3.
1,andthenestimatingthetwototwelvescalarparametersofthechosenmodel.
AnillustrationshowingtheeffectspossiblewitheachofthesemodelsisgiveninFig.
3.
3.
Table3.
1ImageCoordinateTransformationsDiscussedinthisChapter:TheTranslation,Afne,andProjectiveModelsAreExpressedinVectorForm;e.
g.
,x=[x,y]TisaVectorofdimension2,andA∈R2*2isaMatrixofDimension2by2,etc.
ModelCoordinatetransformationfromxtoxParametersTranslationx=x+bb∈R2Afnex=Ax+bA∈R2*2,b∈R2Bilinearx=qxxyxy+qxxx+qxyy+qxy=qyxyxy+qyxx+qyyy+qyq∈RProjectivex=Ax+bcTx+1A∈R2*2,b,c∈R2Pseudopers-x=qxxx+qxyy+qx+qαx2+qβxypectivey=qyxx+qyyy+qy+qαxy+qβy2q∈RBiquadraticx=qxx2x2+qxxyxy+qxy2y2+qxxx+qxyy+qxy=qyx2x2+qyxyxy+qyy2y2+qyxx+qyyy+qyq∈RFIGURE3.
3PictorialeffectsofthesixcoordinatetransformationsofTable3.
1,arrangedlefttorightbynumberofparameters.
Notethattranslationleavestheoriginalhouseunchanged,exceptinitslocation.
Mostimportantly,onlythethreecoordinatetransformationsattherightaffecttheperiodicityofthewindowspacing(e.
g.
,in-ducethedesired"chirping"whichcorrespondstowhatweseeintherealworld).
Ofthese,onlytheprojectivecoordinatetransformationpreservesstraightlines.
The8-parameterprojectivecoordinatetransformation"exactly"describesthepossiblecameramotions.
Themostcommonassumption(especiallyinmotionestimationforcodingandopticalowforcomputervision)isthatthecoordinatetransformationbetweenframesisatranslation.
Tekalp,Ozkan,andSezan[12]haveappliedthisassumptiontohigh-resolutionimagereconstruction.
AlthoughtranslationistheleastconstrainingandsimplesttoimplementofthesixcoordinatetransformationsinTable3.
1,itispoorathandlinglargechangesduetocamerazoom,rotation,pan,andtilt.
ZhengandChellappa[13]consideredasubsetoftheafnemodel—translation,rotation,andscale—inimageregistration.
Otherresearchers[14,15]haveassumedafnemotion(sixparameters)betweenframes.
Fortheassumptionsofstaticsceneandnoparallax,theafnemodelexactlydescribesrotationabouttheopticalaxisofthecamera,zoomofthecamera,andpureshear,whichthecameradoesnotdoexceptinthelimitasthelensfocallengthapproachesinnity.
Theafnemodelcannotcapturecamerapanandtiltand,therefore,cannotaccuratelyexpressthe"chirping"and"keystoning"seenintherealworld(seeFig.
3.
3).
Consequently,theafnemodeltriestotthewrongparameterstotheseeffects.
Whentheparameterestimationisnotdoneproperlytoaligntheimages,agreaterburdenisplacedondesigningpost-processingtoenhancethepoorlyalignedimages.
The8-parameterprojectivemodelgivestheexacteightdesiredparameterstoac-countforallthepossiblecameramotions.
However,itsparametershavetraditionallybeenmathematicallyandcomputationallytoohardtond.
Consequently,avarietyofapproximationshavebeenproposed.
Beforethesolutiontoestimatingtheprojec-tiveparametersispresented,itwillbehelpfultobetterunderstandtheseapproximatemodels.
Goingfromrstorder(afne)tosecondordergivesthe12-parameterbiquadraticmodel.
Thismodelproperlycapturesboththechirping(changeinspatialfrequencywithposition)andconverginglines(keystoning)effectsassociatedwithprojectivecoordinatetransformations,although,despiteitslargernumberofparameters,thereisstillconsiderablediscrepancybetweenaprojectivecoordinatetransformationandthebest-tbiquadraticcoordinatetransformation.
WhystopatsecondorderWhynotusea20-parameterbicubicmodelWhileanincreaseinthenumberofmodelpa-rameterswillresultinabettert,thereisatradeoffwherethemodelbeginstotnoise.
Thephysicalcameramodeltsexactlyinthe8-parameterprojectivegroup;therefore,weknowthat"eightisenough.
"Hence,itisappealingtondanapproximatemodelwithonlyeightparameters.
The8-parameterbilinearmodelisperhapsthemostwidelyused[16]intheeldsofimageprocessing,medicalimaging,remotesensing,andcomputergraphics.
Thismodeliseasilyobtainedfromthebiquadraticmodelbyremovingthefourx2andy2terms.
Althoughtheresultingbilinearmodelcapturestheeffectofconverginglines,itcompletelyfailstocapturetheeffectofchirping.
The8-parameterpseudo-perspectivemodel[17]does,infact,captureboththecon-verginglinesandthechirpingofaprojectivecoordinatetransformation.
Thismodelmayrstbethoughtofastheremovaloftwoofthequadraticterms(qxy2=qyx2=0),whichresultsina10-parametermodel(theq-chirpofNavabandMann[18])andthentheconstrainingofthefourremainingquadraticparameterstohavetwodegreesoffreedom.
Theseconstraintsforcethechirpingeffect(capturedbyqxx2andqyy2)andtheconvergingeffect(capturedbyqxxyandqyxy)toworktogetherinthe"right"waytomatch,ascloselyaspossible,theeffectofaprojectivecoordinatetransfor-mation.
Bysettingqα=qxx2=qyxy,thechirpinginthex-directionisforcedtocorrespondwiththeconvergingofparallellinesinthex-direction(andlikewiseforthey-direction).
Therefore,ofthe8-parameterapproximationstothetrueprojective,wewouldexpectthepseudo-perspectivemodeltoperformthebest.
Ofcourse,thedesired"exact"eightparameterscomefromtheprojectivemodel,buttheyhavebeennotoriouslydifculttoestimate.
TheparametersforthismodelhavebeensolvedbyTsaiandHuang[19],buttheirsolutionassumedthatfeatureshadbeenidentiedinthetwoframes,alongwiththeircorrespondences.
Inthischapter,asimplefeaturelessmeansofregisteringimagesbyestimatingtheircomparametersispresented.
Otherresearchershavelookedatprojectiveestimationinthecontextofobtaining3-Dmodels.
FaugerasandLustman[20],ShashuaandNavab[21],andSawhney[22]haveconsideredtheproblemofestimatingtheprojectiveparameterswhilecomputingthemotionofarigidplanarpatch,aspartofalargerproblemofnding3-Dmotionandstructureusingparallaxrelativetoanarbitraryplaneinthescene.
Kumar,Anan-dan,andHanna[23]havealsoeuggestedregisteringframesofvideobycomputingtheowalongtheepipolarlines,forwhichthereisalsoaninitialstepofcalculatingthegrosscameramovementassumingnoparallax.
However,thesemethodshavereliedonfeaturecorrespondencesandwereaimedat3-Dscenemodeling.
Ourfocusisnotonrecoveringthe3-Dscenemodel,butonaligning2-Dimagesof3-Dscenes.
Featurecorrespondencesgreatlysimplifytheproblem;however,theyalsohavemanyproblemswhicharereviewedbelow.
Thefocusofthischapterisasimplefeature-lessapproachtoestimatingtheprojectivecoordinatetransformationbetweenimageframes.
Twosimilareffortsexisttothenewworkpresentedhere.
Mann[24]andSzeliskiandCoughlan[25]independentlyproposedfeaturelessregistrationandcompositingofeitherpicturesofanearlyatobjectorpicturestakenfromapproximatelythesamelocation.
Bothuseda2-Dprojectivemodelandsearchedoverits8-parameterspacetominimizethemeansquareerror(ormaximizetheinnerproduct)betweenoneframeanda2-Dprojectivecoordinatetransformationofthenextframe.
However,inboththeseearlierworks,thealgorithmreliesonnonlinearoptimizationtechniqueswhichweareabletoavoidwiththenewtechniquepresentedhere.
3.
5.
1Camera,Eye,orHeadMotion:CommonAssumptionsandTerminologyTwoassumptionsarerelevanttothiswork.
Therstisthatthesceneisrelativelyconstant—changesofscenecontentandlightingaresmallbetweenframes,relativetochangesthatareinducedbycamera,eye,orheadmotion(e.
g.
,apersoncanturnhisorherhead,henceturninganEyeTapcamera,andinduceamuchgreaterimageoweldthanthatinducedbymovementofobjectsinthescene).
Thesecondassumptionisthatofanidealpinholecamera—implyingunlimiteddepthofeldwitheverythinginfocus(inniteresolution)andimplyingthatstraightlinesmaptostraightlines.
1ThisassumptionisparticularlyvalidforlaserEyeTapcameraswhichactuallydohaveinnitedepthoffocus.
Consequently,thecamera,eye,orheadhasthreedegreesoffreedomin2-Dspaceandeightdegreesoffreedomin3-Dspace:translation(X,Y,Z),zoom(scaleineachoftheimagecoordinatesxandy),androtation(rotationabouttheopticalaxis,pan,andtilt).
Inthischapter,an"uncalibratedcamera"referstooneinwhichtheprincipalpoint2isnotnecessarilyatthecenter(origin)oftheimageandthescaleisnotnecessarilyisotropic.
Itisassumedthatthelm,sensor,retina,orthelikeisat(althoughweknowinfactthattheretinaiscurved).
Itisassumedthatthezoomiscontinuallyadjustablebythecamerauser,andthatwedonotknowthezoomsettingorifitchangedbetweenrecordingframesoftheimagesequence.
Wealsoassumethateachelementinthecamerasensorarrayreturnsaquantitythatislinearlyproportionaltothequantityoflightreceived.
33.
5.
2VideoOrbitsTsaiandHuang[19]notedthattheelementsoftheprojectivegroupgivethetruecameramotionswithrespecttoaplanarsurface.
Theyexploredthegroupstructureassociatedwithimagesofa3-Drigidplanarpatch,aswellastheassociatedLieal-gebra,althoughtheyassumethatthecorrespondenceproblemhasbeensolved.
Thesolutionpresentedinthischapter(whichdoesnotrequirepriorsolutionofcorrespon-dence)alsoreliesonprojectivegrouptheory.
Webrieyreviewthebasicsofthistheory,beforepresentingthenewsolutioninthenextsection.
ProjectiveGroupin1-DForsimplicity,thetheoryisrstreviewedfortheprojectivecoordinatetransforma-tioninonedimension:4x=(ax+b)/(cx+1),wheretheimagesarefunctionsofonevariable,x.
Thesetofallprojectivecoordinatetransformationsforwhicha=0formsagroup,P,theprojectivegroup.
Whena=0andc=0,itistheafnegroup.
Whena=1andc=0,itbecomesthetranslationgroup.
Ofthesixcoordinatetransformationsintheprevioussection,onlytheprojective,afne,andtranslationoperationsformgroups.
Agroupofoperatorstogetherwiththesetof1-Dimages(operands)formagroupoperation.
5Thenewsetofimages1Whenusinglowcostwide-anglelenses,thereisusuallysomebarreldistortionwhichwecorrectusingthemethodofCampbellandBobick[26].
2Theprincipalpointiswheretheopticalaxisintersectsthelm,retina,sensor,orthelike,asthecasemaybe.
3Thisconditioncanbeenforcedoverawiderangeoflightintensitylevels,byusingtheWyckoffprinci-ple[27,28].
4Ina2-Dworld,the"camera"consistsofacenterofprojection(pinholelens)andaline(1-Dsensorarrayor1-D"lm").
5AlsoknownasagroupactionorG-set[29].
thatresultsfromapplyingallpossibleoperatorsfromthegrouptoaparticularimagefromtheoriginalsetiscalledtheorbitofthatimageunderthegroupoperation[29].
Acameraataxedlocation,andfreetozoomandpan,givesrisetoaresultingpairof1-Dframestakenbythecamera,whicharerelatedbythecoordinatetransformationfromx1tox2,givenby[30]:x2=z2tan(arctan(x1/z1)θ),x1=o1=(ax1+b)/(cx1+1),x1=o1(3.
1)wherea=z2/z1,b=z2tan(θ),c=tan(θ)/z1,ando1=z1tan(π/2+θ)=1/cisthelocationofthesingularityinthedomain.
Weshouldemphasizethatc,thedegreeofperspective,hasbeengiventheinterpretationofachirp-rate[30].
ThecoordinatetransformationsofEq.
(3.
1)formagroupoperation.
Thisresultandtheproofofthisgroup'sisomorphismtothegroupcorrespondingtononsingularprojectionsofaatobjectaregiveninMannandPicard[31].
ProjectiveGroupin2-DThetheoryfortheprojective,afne,andtranslationgroupsalsoholdsforthefamiliar2-Dimagestakenofthe3-Dworld.
Thevideoorbitofagiven2-Dframeisdenedtobethesetofallimagesthatcanbeproducedbyapplyingoperatorsfromthe2-Dprojectivegrouptothegivenimage.
Hence,werestatethecoordinatetransformationproblem:givenasetofimagesthatlieinthesameorbitofthegroup,wewishtondforeachimagepairthatoperatorinthegroupwhichtakesoneimagetotheotherimage.
Iftwoframes,sayf1andf2,areinthesameorbit,thenthereisagroupoperationpsuchthatthemeansquarederror(MSE)betweenf1andf2=pf2iszero,wherethesymboldenotestheoperationofpactingonframef2.
Inpractice,however,wendwhichelementofthegrouptakesoneimage"nearest"theother,fortherewillbeacertainamountofparallax,noise,interpolationerror,edgeeffects,changesinlighting,depthoffocus,etc.
Fig.
3.
4illustratestheoperatorpactingonframef2tomoveitnearesttoframef1.
(Thisguredoesnot,however,revealthepreciseshapeoftheorbit,whichoccupiesan8-Dspace.
)Theprimaryassumptionsinthesecasesarethatofnoparallaxandofastaticscene.
Becausethe8-parameterprojectivemodelis"exact,"itistheoreticallytherightmodeltouseforestimatingthecoordinatetransformation.
Theexamplesthatfollowdemonstratethatitalsoperformsbetterinpracticethantheotherproposedmodels.
Inthenextsection,anewtechniqueforestimatingitseightparametersisshown.
FIGURE3.
4Videoorbits.
(a)Theorbitofframe1isthesetofallimagesthatcanbeproducedbyactingonframe1withanyelementoftheoperatorgroup.
Assumingthatframes1and2arefromthesamescene,frame2willbeclosetooneofthepossibleprojectivecoordinatetransformationsofframe1.
Inotherwords,frame2liesneartheorbitofframe1.
(b)Bybringingframe2alongitsorbit(whichisnearlythesameorbitastheorbitofframe1),wecandeterminehowcloselythetwoorbitscometogetheratframe1.
3.
6Framework:ComparameterEstimationandOpticalFlowBeforethenewresultsarepresented,existingmethodsofcomparameterestimationforcoordinatetransformationsarereviewed.
Comparametersrefertotherelativeparametersthattransformoneimageintoanother,betweenapairofimagesfromanimagesequence.
Estimationofcomparametersinapairwisefashioncanbedealtwithgloballybasedonthegroupproperties,assumingtheparametersinquestiontraceanorbitofagroup.
Weclassifyexistingmethodsintotwocategories:feature-basedandfeatureless.
Ofthefeaturelessmethods,considertwosubcategories:methodsbasedonminimizingMSE(generalizedcorrelation,directnonlinearoptimization)andmethodsbasedonspatio-temporalderivativesandopticalow.
Notethatvariationssuchasmultiscalehavebeenomittedfromthesecategories;multiscaleanalysiscanbeappliedtoanyofthem.
Thenewalgorithmdevelopedinthischapter(withnalformgiveninSection3.
7)isfeaturelessandisbasedonmultiscalespatio-temporalderivatives.
Someofthedescriptionsbelowarepresentedforhypothetical1-Dimagestakenina2-Dspace.
Thissimplicationyieldsaclearercomparisonoftheestimationmethods.
Thenewtheoryandapplicationswillbepresentedsubsequentlyfor2-Dimagestakenina3-Dspace.
3.
6.
1Feature-BasedMethodsFeature-basedmethods[32,33]assumethatpointcorrespondencesinbothimagesareavailable.
Intheprojectivecase,givenatleastthreecorrespondencesbetweenpointpairsinthetwo1-Dimages,wendtheelementp={a,b,c}∈Pthatmapsthesecondimageintotherst.
Letxk,k=1,2,3,.
.
.
bethepointsinoneimage,andletxkbethecorrespondingpointsintheotherimage.
Then,xk=(axk+b)/(cxk+1).
Rearrangingyieldsaxk+bxkxkc=xk,sothata,b,andccanbefoundbysolvingk≥3linearequationsinthreeunknowns:xk1xkxkabcT=xk(3.
2)usingleastsquaresiftherearemorethanthreecorrespondencepoints.
Theextensionfrom1-Dimagesto2-Dimagesisconceptuallyidentical;fortheafneandprojectivemodels,theminimumnumberofcorrespondencepointsneededin2-Disthreeandfour,respectively.
Amajordifcultywithfeature-basedmethodsisndingthefeatures.
Goodfeaturesareoftenhand-selectedorcomputed,possiblywithsomedegreeofhumaninterven-tion[34].
Asecondproblemwithfeaturesistheirsensitivitytonoiseandocclusion.
Evenifreliablefeaturesexistbetweenframes,thesefeaturesmaybesubjecttosignalnoiseandocclusion.
Theemphasisintherestofthischapterisonrobustfeaturelessmethods.
3.
6.
2FeaturelessMethodsBasedonGeneralizedCross-CorrelationCross-correlationoftwoframesisafeaturelessmethodofrecoveringtranslationmodelcomparameters.
Afneandprojectivecomparameterscanalsoberecoveredusinggeneralizedformsofcross-correlationbetweentwoimages(e.
g.
,comparingtwoimagesusingcrosscorrelationandrelatedmethods).
Generalizedcross-correlationisbasedonaninner-productformulationwhiches-tablishesasimilaritymetricbetweentwofunctions,suchasgandh,whereh≈pgisanapproximatelycoordinate-transformedversionofgbutthecomparametersofthecoordinatetransformationpareunknown.
6Wecannd,byexhaustivesearch(applyingallpossibleoperators,p,toh),the"best"pastheonethatmaximizestheinnerproduct:∞∞g(x)p1h(x)∞∞p1h(x)dxdx(3.
3)wherewehavenormalizedtheenergyofeachcoordinate-transformedhbeforemakingthecomparison.
Equivalently,insteadofmaximizingasimilaritymetric,wecanminimizeananti-similaritymetric,suchasMSE,givenby∞∞g(x)p1h(x)2dx.
SolvingEq.
(3.
3)hasanadvantageoverndingMSEwhenoneimageisnotonlyacoordinate-transformedversionoftheotherbutisalsoanamplitude-scaledversion,asgenerallyhappenswhenthereisanautomaticgaincontroloranautomaticirisinthecamera.
6InthepresenceofadditivewhiteGaussiannoise,thismethod,alsoknownas"matchedltering,"leadstoamaximumlikelihoodestimateoftheparameters[35].
In1-D,theafnemodelpermitsonlydilationandtranslation.
Givenh,anafnecoordinate-transformedversionofg,generalizedcorrelationamountstoestimatingtheparametersfordilationaandtranslationbbyexhaustivesearch.
Thecollectionofallpossiblecoordinatetransformations,whenappliedtooneoftheimages(say,h)servestoproduceafamilyoftemplatestowhichtheotherimage,g,canbecompared.
Ifwenormalizeeachtemplatesothatallhavethesameenergyha,b(x)=1√ah(ax+b)thenthemaximumlikelihoodestimatecorrespondstoselectingthememberofthefamilythatgivesthelargestinnerproduct:g(x),ha,b(x)=∞∞g(x)ha,b(x)dxThisresultisknownasacross-wavelettransform.
Acomputationallyefcientalgorithmforthecross-wavelettransformhasrecentlybeenpresented[36].
(SeeWeiss[37]foragoodreviewonwavelet-basedestimationofafnecoordinatetrans-formations.
)Justlikethecross-correlationforthetranslationgroupandthecross-waveletfortheafnegroup,thecross-chirpletcanbeusedtondthecomparametersofaprojectivecoordinatetransformationin1-D,searchingovera3-parameterspace.
Thechirplettransform[38]isageneralizationofthewavelettransform.
Theprojective-chirplethastheformha,b,c=hax+bcx+1(3.
4)wherehisthemotherchirplet,analogoustothemotherwaveletofwavelettheory.
Membersofthisfamilyoffunctionsarerelatedtooneanotherbyprojectivecoordinatetransformations.
With2-Dimages,thesearchisoveran8-parameterspace.
Adensesamplingofthisvolumeiscomputationallyprohibitive.
Consequently,combinationsofcoarse-to-neanditerativeorrepetitivegradient-basedsearchproceduresarerequired.
Adaptivevariantsofthechirplettransformhavebeenpreviouslyreportedintheliterature[39].
However,therearestillmanyproblemswiththeadaptivechirpletapproach;thus,featurelessmethodsbasedonspatio-temporalderivativesarenowconsidered.
3.
6.
3FeaturelessMethodsBasedonSpatio-TemporalDerivativesOpticalFlow—TranslationFlowWhenthechangefromoneimagetoanotherissmall,opticalow[40]maybeused.
In1-D,thetraditionalopticalowformulationassumeseachpointxinframetisatranslatedversionofthecorrespondingpointinframet+t,andthatxandtarechosenintheratiox/t=uf,thetranslationalowvelocityofthepointinquestion.
TheimagebrightnessE(x,t)isdescribedbyE(x,t)=E(x+x,t+t),(x,t).
(3.
5)Inthecaseofpuretranslation,ufisconstantacrosstheentireimage.
Moregenerallythough,apairof1-Dimagesarerelatedbyaquantity,uf(x)ateachpointinoneoftheimages.
ExpandingtherightsideofEq.
(3.
5)inaTaylorseriesandcancelling0thordertermsgivethewell-knownopticalowequationufEx+Et+h.
o.
t.
=0,whereExandEtarethespatialandtemporalderivatives,respectively,andh.
o.
t.
denoteshigherorderterms.
Typically,thehigherordertermsareneglected,givingtheexpressionfortheopticalowateachpointinoneofthetwoimages:ufEx+Et≈0.
(3.
6)AfneFitandAfneFlow:aNewRelationshipGiventheopticalowbetweentwoimages,gandh,wewishtondthecoordinatetransformationtoapplytohtomakeitlookmostlikeg.
Wenowdescribetwoapproachesbasedontheafnemodel:(1)ndingtheopticalowateverypointandthenttingthisowwithanafnemodel(afnet),and(2)rewritingtheopticalowequationintermsofanafne(nottranslation)motionmodel(afneow).
WangandAdelsonhaveproposedttinganafnemodeltoanopticaloweld[41]of2-Dimages.
Webrieyexaminetheirapproachwith1-Dimages(1-Dimagessim-plifyanalysisandcomparisontoothermethods).
Denotecoordinatesintheoriginalimage,g,byx,andinthenewimage,h,byx.
Supposethathisadilatedandtranslatedversionofg,sox=ax+bforeverycorrespondingpair(x,x).
Equiva-lently,theafnemodelofvelocity(normalizingt=1),um=xx,isgivenbyum=(a1)x+b.
Wecanexpectadiscrepancybetweentheowvelocity,uf,andthemodelvelocity,um,duetoeithererrorsintheowcalculationorerrorsintheafnemodelassumption.
Accordingly,weapplylinearregressiontoobtainthebestleast-squarestbyminimizing:εfit=xumuf2=(um+Et/Ex)2.
(3.
7)Theconstantsaandbthatminimizeεfitovertheentirepatcharefoundbydiffer-entiatingEq.
(3.
7),andsettingthederivativestozero.
Thisresultsintheafnetequations[42]:xx2,xxxx,x1a1b=xxEt/ExxEt/Ex.
(3.
8)Alternatively,theafnecoordinatetransformationmaybedirectlyincorporatedintothebrightnesschangeconstraintequation(3.
5).
Bergenetal.
[43]haveproposedthismethod,whichhasbeencalledafneowtodistinguishitfromtheafnetmodelofWangandAdelsonEq.
(3.
8).
Letusshowhowafneowandafnetarerelated.
Substitutingum=(ax+b)xdirectlyintoEq.
(3.
6)inplaceofufandsummingthesquarederrorεow=x(umEx+Et)2(3.
9)overthewholeimage,differentiating,andequatingtheresulttozerogivesalinearsolutionforbothaandb:xx2E2x,xxE2xxxE2x,xE2xa1b=xxExEtxExEt.
(3.
10)ToseehowthisresultcomparestotheafnetwerewriteEq.
(3.
7)εfit=xumEx+EtEx2(3.
11)andobserve,comparingEqs.
(3.
9)and(3.
11),thatafneowisequivalenttoaweightedleast-squarest,wheretheweightingisgivenbyE2x.
Thustheafneowmethodtendstoputmoreemphasisonareasoftheimagethatarespatiallyvaryingthandoestheafnetmethod.
Ofcourse,oneisfreetoseparatelychoosetheweightingforeachmethodinsuchawaythatafnetandafneowmethodsbothgivethesameresult.
Practicalexperiencetendstofavortheafneowweighting,but,moregenerally,perhapsweshouldask,"whatisthebestweighting"Forexample,maybethereisanevenbetteranswerthanthechoiceamongthesetwo.
LucasandKanade[44],amongothers,haveconsideredweightingissues.
AnotherapproachtotheafnetinvolvescomputationoftheopticaloweldusingthemultiscaleiterativemethodofLucasandKanade,andthenttingtotheafnemodel.
Ananalogousvariantoftheafneowmethodinvolvesmultiscaleiterationaswell,butinthiscasetheiterationandmultiscalehierarchyareincorporateddirectlyintotheafneestimator[43].
Withtheadditionofmultiscaleanalysis,thetandowmethodsdifferinadditionalrespectsbeyondjusttheweighting.
Experienceindicatesthatthedirectmultiscaleafneowperformsbetterthantheafnettothemultiscaleow.
Multiscaleopticalowmakestheassumptionthatblocksoftheimagearemovingwithpuretranslationalmotion,andthen,paradoxically,theafnetrefutesthispure-translationassumption.
However,tprovidessomeutilityoverowwhenitisdesiredtosegmenttheimageintoregionsundergoingdifferentmotions[45],ortogainrobustnessbyrejectingportionsoftheimagenotobeyingtheassumedmodel.
ProjectiveFitandProjectiveFlow:NewTechniquesAnalogoustotheafnetandafneowoftheprevioussection,twonewmethodsareproposed:projectivetandprojectiveow.
Forthe1-Dafnecoordinatetrans-formation,thegraphoftherangecoordinateasafunctionofthedomaincoordinateisastraightline;fortheprojectivecoordinatetransformation,thegraphoftherangecoordinateasafunctionofthedomaincoordinateisarectangularhyperbola[31].
Theafnetcaseusedlinearregression;however,intheprojectivecasehyperbolicregressionisused.
ConsidertheowvelocitygivenbyEq.
(3.
6)andthemodelvelocity:um=xx=ax+bcx+1x(3.
12)andminimizethesumofthesquareddifferenceparallelingEq.
(3.
9):ε=xax+bcx+1x+EtEx2.
(3.
13)Forprojective-ow(p-ow)weuse,asforafneow,theTaylorseriesofum:um+x=b+(abc)x+(bca)cx2+(abc)c2x33.
14)andagainusetherstthreeterms,obtainingenoughdegreesoffreedomtoaccountforthe3comparametersbeingestimated.
Letting=(h.
o.
t.
)2=((b+(abc1)x+(bca)cx2)Ex+Et)2,q2=(bca)c,q1=abc1,andq0=b,anddifferentiatingwithrespecttoeachofthe3comparametersofq,settingthederivativesequaltozero,andverifyingwiththesecondderivatives,givesthelinearsystemofequationsforprojectiveow:x4E2xx3E2xx2E2xx3E2xx2E2xxE2xx2E2xxE2xE2xq2q1q0=x2ExEtxExEtExEt(3.
15)InSection3.
7weextendthisderivationto2-Dimagesandshowhowarepetitiveapproachmaybeusedtocomputetheparameters,p,oftheexactmodel.
Afeedbacksystemisusedwherethefeedforwardloopinvolvescomputationoftheapproximateparameters,q,intheextensionofEq.
(3.
15)to2-D.
Aswiththeafnecase,projectivetandprojectiveowEq.
(3.
15)differonlyintheweightingassumed,althoughprojectivetprovidestheaddedadvantageofenablingthemotionwithinanarbitrarysubregionoftheimagetobeeasilyfound.
Inthischapteronlyglobalimagemotionisconsidered,forwhichtheprojectiveowmodelhasbeenfoundtobebest[42].
3.
7MultiscaleProjectiveFlowComparameterEstimationIntheprevioussection,twonewtechniques,p-tandp-ow,wereproposed.
Nowwedescribeouralgorithmforestimatingtheprojectivecoordinatetransformationfor2-Dimagesusingp-ow.
Webeginwiththebrightnessconstancyconstraintequationfor2-Dimages[40]whichgivestheowvelocitycomponentsinthexandydirections,analogoustoEq.
(3.
6):ufEx+vfEy+Et≈0.
(3.
16)Asiswellknown[40],theopticaloweldin2-Disunderconstrained.
7Themodelofpuretranslationateverypointhastwocomparameters,butthereisonlyoneequation(3.
16)tosolve.
Thusitiscommonpracticetocomputetheopticalowoversomeneighborhood,whichmustbeatleasttwopixelsbutisgenerallytakenoverasmallblock,3*3,5*5,orsometimeslarger(e.
g.
,theentireimage,asinthischapter).
Ourtaskisnottodealwiththe2-Dtranslationowbutwiththe2-Dprojectiveow,estimatingtheeightcomparametersinthecoordinatetransformation:x=xy=A[x,y]T+bcT[x,y]T+1=Ax+bcTx+1.
(3.
17)Thedesiredeightscalarparametersaredenotedbyp=[A,b;c,1],A∈R2*2,b∈R2*1,andc∈R2*1.
Aswiththe1-Dimages,wemakesimilarassumptionsinexpandingEq.
(3.
17)initsownTaylorseries,analogoustoEq.
(3.
14).
IfwetaketheTaylorseriesuptosecondorderterms,weobtainthebiquadraticmodelmentionedinSection3.
5.
Asmentionedthere,byappropriatelyconstrainingthetwelveparametersofthebi-quadraticmodel,weobtainavarietyof8-parameterapproximatemodels.
Inouralgorithmforestimatingtheexactprojectivegroupparameters,wewilluseoneoftheseapproximatemodelsinanintermediatestep.
8Weillustratethealgorithmbelowusingthebilinearapproximatemodelsinceithasthesimplestnotation.
9First,weincorporatetheapproximatemodeldirectlyintothegeneralizedtorgeneralizedow.
TheTaylorseriesforthebilinearcasegivesum+x=qxxyxy+(qxx+1)x+qxyy+qxvm+y=qyxyxy+qyxx+qyy+1y+qy(3.
18)Incorporatingtheseintotheowcriteriayieldsasimplesetofeightscalar"linear"7Opticalowin1-Ddidnotsufferfromthisproblem.
8Useofanapproximatemodelthatdoesnotcapturechirpingorpreservestraightlinescanstillleadtothetrueprojectiveparametersaslongasthemodelcapturesatleasteightdegreesoffreedom.
9Thepseudo-perspectivegivesslightlybetterperformance;itsdevelopmentisthesamebutwithmorenotation.
(correctlyspeaking,afne)equationsineightscalarunknowns,for"bilinearow":x2y2E2x,x2yE2x,xy2E2x,xyEx,x2y2EyEx,x2yEyEx,xy2EyEx,EyxyExx2yE2x,x2E2x,xyE2x,xE2x,x2yEyEx,x2EyEx,xyEyEx,EyxExxy2E2x,xyE2x,y2E2x,yE2x,xy2EyEx,xyEyEx,y2EyEx,EyyExxyE2x,xE2x,yE2x,E2x,xyEyEx,xEyEx,yEyEx,EyExx2y2ExEy,x2yExEy,xy2ExEy,ExxyEy,x2y2E2y,x2yE2y,xy2E2y,xyE2yx2yExEy,x2ExEy,xyExEy,ExxEy,x2yE2y,x2E2y,xyE2y,xE2yxy2ExEy,xyExEy,y2ExEy,ExyEy,xy2E2y,xyE2y,y2E2y,yE2yxyExEy,xExEy,yExEy,ExEy,xyE2y,xE2y,yE2y,E2yqxxyqxxqxyqxqyxyqyxqyyqy=[EtxyEx,EtxEx,EtyEx,EtEx,EtxyEy,EtxEy,EtyEy,EtEy]T(3.
19)Thesummationsareovertheentireimage(allxandy)ifcomputingglobalmotion(asisdoneinthischapter),oroverawindowedpatchifcomputinglocalmotion.
Thisequationlookssimilartothe6*6matrixequationpresentedinBergenetal.
[43],exceptthatitservestoaddressprojectivegeometryratherthantheafnegeometryofBergenetal.
[43].
Inordertoseehowwellthemodeldescribesthecoordinatetransformationbetween2images,saygandh,onemightwarp10htog,usingtheestimatedmotionmodel,andthencomputesomequantitythatindicateshowdifferenttheresampledversionofhisfromg.
TheMSEbetweenthereferenceimageandthewarpedimagemightserveasagoodmeasureofsimilarity.
However,sincewearereallyinterestedinhowtheexactmodeldescribesthecoordinatetransformation,weassessthegoodnessoftbyrstrelatingtheparametersoftheapproximatemodeltotheexactmodel,andthenndtheMSEbetweenthereferenceimageandthecomparisonimageafterapplyingthecoordinatetransformationoftheexactmodel.
Amethodofndingtheparametersoftheexactmodel,giventheapproximatemodel,ispresentedinSection3.
7.
1.
3.
7.
1FourPointMethodforRelatingApproximateModeltoExactModelAnyoftheapproximationsabove,afterbeingrelatedtotheexactprojectivemodel,tendtobehavewellintheneighborhoodoftheidentity,A=I,b=0,c=0.
In1-D,weexplicitlyexpandedtheTaylorseriesmodelabouttheidentity;here,althoughwedonotexplicitlydothis,weassumethatthetermsoftheTaylorseriesofthemodelcorrespondtothosetakenabouttheidentity.
Inthe1-Dcase,wesolvethethreelinearequationsinthreeunknownstoestimatethecomparametersoftheapproximatemotionmodel,andthenwerelatethetermsinthisTaylorseriestotheexactcomparameters,10Thetermwarpisappropriatehere,sincetheapproximatemodeldoesnotpreservestraightlines.
a,b,andc(whichinvolvessolvinganothersetofthreeequationsinthreeunknowns,thesecondsetbeingnonlinear,althoughveryeasytosolve).
Intheextensionto2-D,theestimatestepisstraightforward,buttherelatestepismoredifcultbecausewenowhaveeightnonlinearequationsineightunknowns,relatingthetermsintheTaylorseriesoftheapproximatemodeltothedesiredexactmodelparameters.
Insteadofsolvingtheseequationsdirectly,wenowproposeasimpleprocedureforrelatingtheparametersoftheapproximatemodeltothoseoftheexactmodel,whichwecallthefourpointmethod:1.
Selectfourorderedpairs(suchasthefourcornersoftheboundingboxcontain-ingtheregionunderanalysis,orthefourcornersoftheimageifthewholeimageisunderanalysis).
Heresuppose,forsimplicity,thatthesepointsarethecornersoftheunitsquare:s=[s1,s2,s3,s4]=[(0,0)T,(0,1)T,(1,0)T,(1,1)T].
2.
ApplythecoordinatetransformationusingtheTaylorseriesfortheapproximatemodel[e.
g.
,Eq.
(3.
18)]tothesepoints:r=um(s).
3.
Finally,thecorrespondencesbetweenrandsaretreatedjustlikefeatures.
Thisresultsinfoureasy-to-solvelinearequations:xkyk=xk,yk,1,0,0,0,xkxk,ykxk0,0,0,xk,yk,1,xkyk,ykykaxx,axy,bx,ayx,ayy,by,cx,cyT(3.
20)where1≤k≤4isresultingintheexacteightparameters,p.
Weremindthereaderthatthefourcornersarenotfeaturecorrespondencesasusedinthefeature-basedmethodsofSection3.
6.
1,but,rather,areusedsothatthetwofeaturelessmodels(approximateandexact)canberelatedtooneanother.
Itisimportanttorealizethefullbenetofndingtheexactparameters.
Whiletheapproximatemodelissufcientforsmalldeviationsfromtheidentity,itisnotadequatetodescribelargechangesinperspective.
However,ifweuseittotracksmallchangesincrementally,andeachtimerelatethesesmallchangestotheexactmodelEq.
(3.
17),thenwecanaccumulatethesesmallchangesusingthelawofcompositionaffordedbythegroupstructure.
Thisisanespeciallyfavorablecontributionofthegroupframework.
Forexample,withavideosequence,wecanaccommodateverylargeaccumulatedchangesinperspectiveinthismanner.
Theproblemswithcumulativeerrorcanbeeliminated,forthemostpart,byconstantlypropagatingforwardthetruevalues,computingtheresidualusingtheapproximatemodel,andeachtimerelatingthistotheexactmodeltoobtainagoodness-of-testimate.
3.
7.
2OverviewoftheNewProjectiveFlowAlgorithmBelowisanoutlineofthenewalgorithmforestimationofprojectiveow.
Detailsofeachstepareinsubsequentsections.
Framesfromanimagesequencearecomparedpairwisetotestwhetherornottheylieinthesameorbit:1.
AGaussianpyramidofthreeorfourlevelsisconstructedforeachframeinthesequence.
2.
Thecomparameterspareestimatedatthetopofthepyramid,betweenthetwolowest-resolutionimagesofaframepair,gandh,usingtherepetitivemethoddepictedinFig.
3.
5.
3.
Theestimatedpisappliedtothenexthigher-resolution(ner)imageinthepyramid,pg,tomakethetwoimagesatthatlevelofthepyramidnearlycongruentbeforeestimatingthepbetweenthem.
4.
Theprocesscontinuesdownthepyramiduntilthehighest-resolutionimageinthepyramidisreached.
FIGURE3.
5Methodofcomputationofeightcomparameterspbetweentwoimagesfromthesamepyramidlevel,gandh.
Theapproximatemodelparametersqarerelatedtotheexactmodelparameterspinafeedbacksystem.
3.
7.
3MultiscaleRepetitiveImplementationTheTaylor-seriesformulationswehaveusedimplicitlyassumesmoothness;theperformanceisimprovediftheimagesareblurredbeforeestimation.
Toaccomplishthis,wedonotdownsamplecriticallyafterlowpasslteringinthepyramid.
How-ever,afterestimationweusetheoriginal(unblurred)imageswhenapplyingthenalcoordinatetransformation.
Thestrategywepresentdiffersfromthemultiscaleiterative(afne)strategyofBergenetal.
inoneimportantrespectbeyondsimplyanincreasefromsixtoeightparameters.
Thedifferenceisthefactthatwehavetwomotionmodels,the"exactmotionmodel"Eq.
(3.
17)andthe"approximatemotionmodel,"namelytheTaylorseriesapproximationtothemotionmodelitself.
Theapproximatemotionmodelisusedtoiterativelyconvergetotheexactmotionmodel,usingthealgebraiclawofcompositionaffordedbytheexactprojectivegroupmodel.
Inthisstrategy,theexactparametersaredeterminedateachlevelofthepyramid,andpassedtothenextlevel.
ThestepsinvolvedaresummarizedschematicallyinFig.
3.
5,anddescribedbelow:1.
Initialize:seth0=handsetp0,0totheidentityoperator.
2.
Iterate(k=1.
.
.
K):(a)Estimate:estimatethe8ormoretermsoftheapproximatemodelbe-tweentwoimageframes,gandhk1.
Thisresultsinapproximatemodelparametersqk.
(b)Relate:relatetheapproximateparametersqktotheexactparametersusingthe"fourpointmethod.
"Theresultingexactparametersarepk.
(c)Resample:applythelawofcompositiontoaccumulatetheeffectofthepk's.
Denotethesecompositeparametersbyp0,k=pkp0,k1.
Thensethk=p0,kh.
(Thisshouldhavenearlythesameeffectasapplyingpktohk1,exceptthatitwillavoidadditionalinterpolationandanti-aliasingerrorsyouwouldgetbyresamplinganalreadyresampledimage[16].
)Repeatuntileithertheerrorbetweenhkandgfallsbelowathreshold,oruntilsomemaximumnumberofrepetitionsisachieved.
Aftertherstrepetition,theparametersq2tendtobenearidentitysincetheyaccountfortheresidualbetweenthe"perspective-corrected"imageh1andthe"true"imageg.
Wendthatonlytwoorthreerepetitionsareusuallyneededforframesfromnearlythesameorbit.
Arectangularimageassumestheshapeofanarbitraryquadrilateralwhenitun-dergoesaprojectivecoordinatetransformation.
Incodingthealgorithm,wepadtheundenedportionswiththequantityNaN,astandardIEEEarithmetic[46]value,sothatanycalculationsinvolvingthesevaluesautomaticallyinheritNaNwithoutslow-ingdownthecomputations.
Thealgorithm,runninginMatlabonanHP735,takesaboutsixsecondsperrepetitionforapairof320x240images.
AClanguageversion,optimized,compiled,andrunningonthewearablecomputerportionofvariousPSDsbuiltbytheauthor,typicallyrunsinafractionofasecond,insomecasesontheorderof1/10thofasecondorso.
AXilinxFPGA-basedversionofthePSDiscurrentlybeingbuiltbytheauthor,togetherwithProfessorJonathanRoseandothersattheUniversityofToronto,andisexpectedtoruntheentireprocessinlessthan1/60thofasecond.
3.
7.
4ExploitingCommutativityforParameterEstimationAfundamentaluncertainty[47]isinvolvedinthesimultaneousestimationofpa-rametersofanoncommutativegroup,akintotheHeisenberguncertaintyrelationofquantummechanics.
Incontrast,foracommutative11group(intheabsenceofnoise),wecanobtaintheexactcoordinatetransformation.
Segman,Rubinstein,andZeevi[48]consideredtheproblemofestimatingtheparametersofacommutativegroupofcoordinatetransformations,inparticular,the11Acommutative(orAbelian)groupisoneinwhichelementsofthegroupcommute.
Forexample,translationalongthex-axiscommuteswithtranslationalongthey-axis,sothe2-Dtranslationgroupiscommutative.
parametersoftheafnegroup[49].
Theirworkalsodealswithnoncommutativegroups,inparticular,intheincorporationofscaleintheHeisenberggroup12[50].
Estimatingtheparametersofacommutativegroupiscomputationallyefcient,e.
g.
,throughtheuseofFouriercross-spectra[51].
Weexploitthiscommutativityforestimatingtheparametersofthenoncommutative2-Dprojectivegroupbyrstestimatingtheparametersthatcommute.
Forexample,weimproveperformanceifwerstestimatethetwoparametersoftranslation,correctforthetranslation,andthenproceedtoestimatetheeightprojectiveparameters.
Wecanalsosimultaneouslyestimateboththeisotropic-zoomandtherotationabouttheopticalaxisbyapplyingalog-polarcoordinatetransformationfollowedbyatranslationestimator.
ThisprocessmayalsobeachievedbyadirectapplicationoftheFourier-Mellintransform[52].
Similarly,iftheonlydifferencebetweengandhisacamerapan,thenthepanmaybeestimatedthroughacoordinatetransformationtocylindricalcoordinates,followedbyatranslationestimator.
Inpractice,werunthroughthefollowingcommutativeinitializationbeforeesti-matingtheparametersoftheprojectivegroupofcoordinatetransformations:1.
Assumethathismerelyatranslatedversionofg.
(a)EstimatethistranslationusingthemethodofGirodandKuo[51].
(b)Shifthbytheamountindicatedbythisestimate.
(c)ComputetheMSEbetweentheshiftedhandgandcomparetotheoriginalMSEbeforeshifting.
(d)Ifanimprovementhasresulted,usetheshiftedhfromnowon.
2.
Assumethathismerelyarotatedandisotropicallyzoomedversionofg.
(a)Estimatethetwoparametersofthiscoordinatetransformation.
(b)Applytheseparameterstoh.
(c)Ifanimprovementhasresulted,usethecoordinate-transformed(rotatedandscaled)hfromnowon.
3.
Assumethathismerelyanx-chirped(panned)versionofgandsimilarlyx-dechirpedh.
Ifanimprovementresults,usethex-dechirpedhfromnowon.
Repeatfory(tilt.
)Compensatingforonestepmaycauseachangeinchoiceofanearlierstep.
Thusitmightseemdesirabletorunthroughthecommutativeestimatesrepetitively.
However,ourexperienceonlotsofrealvideoindicatesthatasinglepassusuallysufcesand,inparticular,willcatchfrequentsituationswherethereisapurezoom,purepan,puretilt,etc.
bothsavingtherestofthealgorithmcomputationaleffort,aswellasaccountingforsimplecoordinatetransformationssuchaswhenoneimageisanupside-down12WhiletheHeisenberggroupdealswithtranslationandfrequency-translation(modulation),someoftheconceptscouldbecarriedovertoothermorerelevantgroupstructures.
versionoftheother.
(Anyofthesepurecasescorrespondstoasingleparametergroup,whichiscommutative.
)Withoutthecommutativeinitializationstep,theseparameterestimationalgorithmsarepronetogettingcaughtinlocaloptimaandthusneverconvergingtotheglobaloptimum.
3.
8Performance/Applications3.
8.
1AParadigmReversalinResolutionEnhancementMuchofthepreviousworkonresolutionenhancement[14,53,54]hasbeendi-rectedtowardmilitaryapplications,whereonecannotgetclosetothesubjectmatter;therefore,lensesofverylongfocallengthsweregenerallyused.
Inthiscase,therewasverylittlechangeinperspectiveandthemotioncouldbeadequatelyapproxi-matedasafne.
Budgetsalsopermittedlensesofexceptionallyhighquality,sotheresolvingpowerofthelensfarexceededtheresolutionofthesensorarray.
Sensorarraysinearlierapplicationsgenerallyhadasmallnumberofpixelscom-paredtotoday'ssensors,leavingconsiderable"deadspace"betweenpixels.
Conse-quently,usingmultipleframesfromtheimagesequencetollingapsbetweenpixelswasperhapsthesinglemostimportantconsiderationincombiningmultipleframesofvideo.
Wearguethatinthecurrentageofconsumervideo,theexactoppositeisgenerallytrue:subjectmattergenerallysubtendsalargerangle(e.
g.
,iseithercloser,ormorepanoramicincontent),andthedesireforlowcosthasledtocheapplasticlensesthathaveverylargedistortion.
Moreover,sensorarrayshaveimproveddramatically.
Accuratesolutionoftheprojectivemodelismoreimportantthaneverinthesenewapplications.
Inadditiontoconsumervideo,therewillbealargemarketinthefutureforsmallwearablewirelesscameras.
Aprototype,thewearablewirelesswebcam(aneyeglass-basedvideoproductionfacilityuplinkedtotheInternet[11])hasprovidedoneofthemostextremetestbedsforthealgorithmsexploredinthisresearch,asitcapturesnoisytransmittedvideoframes,grabbedbyacameraattachedtoahumanhead,freetomoveatthewilloftheindividual.
Theprojectivemodelisespeciallywell-suitedtothisnewapplication,aspeoplecanturntheirheads(camerarotationaboutanapproximatelyxedcenterofprojection)muchfasterthantheycanundergolocomotion(cameratranslation).
Thenewalgorithmdescribedinthischapterhasconsistentlyperformedwellonnoisydatagatheredfromtheheadcam,evenwhenthesceneisnotstaticandthereisparallax.
FourWaysbywhichResolutionMaybeEnhanced:1.
Sub-pixel—"Fillinginthegaps.
"2.
Scenewidening—Increasedspatialextent;stitchingtogetherimagesinapanorama.
3.
Saliency—Supposewehaveawideshotofascene,andthenzoomintooneperson'sfaceinthescene.
Inordertoinsertthefacewithoutdownsamplingit,weneedtoupsamplethewideshot,increasingthemeaningfulpixelcountofthewholeimage.
4.
Perspective—Inordertoseamlesslymosaicimagesfrompanningwithawideanglelens,imagesneedtobebroughtintoacommonsystemofcoordinatesresultinginakeystoningeffectonthepreviouslyrectangularimageboundary.
Thus,wemustholdthepixelresolutionconstantonthe"squashed"sideandupsampleonthe"stretched"side,resultinginincreasedpixelresolutionoftheentiremosaic.
Therstofthesefourmayarisefromeithermicroscopiccameramovement(induc-ingimagemotionontheorderofapixelorless)ormacroscopiccameramovement(inducingmotionontheorderofmanypixels).
However,asmovementincreases,errorsinregistrationwilltendtoincrease,andenhancementduetosub-pixelswillbereduced,whiletheenhancementduetoscenewidening,saliency,andperspectivewillincrease.
ResultsofapplyingtheproposedmethodtosubpixelresolutionenhancementarenotpresentedinthischapterbutmaybefoundinMannandPicard[31].
3.
8.
2IncreasingResolutioninthe"PixelSense"Fig.
3.
6showssomeframesfromatypicalimagesequence.
Fig.
3.
7showsthesameframestransformedintothecoordinatesystemofframe(c);thatis,themiddleframewaschosenasthereferenceframe.
Giventhatwehaveestablishedameansofestimatingtheprojectivecoordinatetransformationbetweenanypairofimages,therearetwobasicmethodsweuseforndingthecoordinatetransformationsbetweenallpairsofalongerimagesequence.
Becauseofthegroupstructureoftheprojectivecoordinatetransformations,itsufcestoarbitrarilyselectoneframeandndthecoordinatetransformationbetweeneveryotherframeandthisframe.
Thetwobasicmethodsare:1.
Differentialcomparameterestimation:thecoordinatetransformationsbe-tweensuccessivepairsofimages,p0,1,p1,2,p2,3,estimated.
2.
Cumulativecomparameterestimation:thecoordinatetransformationbe-tweeneachimageandthereferenceimageisestimateddirectly.
Withoutlossofgenerality,selectframezero(E0)asthereferenceframeanddenotethesecoordinatetransformationsasp0,1,p0,2,p0,3,.
.
.
Theoretically,thetwomethodsareequivalent:E0=p0,1p1,2pn1,nEn—differentialmethodE0=p0,nEn—cumulativemethod(3.
21)FIGURE3.
6Receivedframesofimagesequencetransformedbywayofcomparameterswithrespecttoframe(c).
Framesfromoriginalimageorbit,sentfromtheapparatusoftheauthor'sWearComp("wearablecomputer")invention[1],connectedtoeyeglass-basedimagingapparatus.
(Notetheapparatuscapturesasidewaysviewsothatitcan"paint"outtheimagecanvaswithawider"brush,"whensweepingacrossforapanorama.
)Theentiresequence,consistingofall20colorframes,isavailable(seenoteatendofthereferencessection),togetherwithexamplesofapplyingtheproposedalgorithmtothisdata.
FIGURE3.
7Receivedframesfromimagevideoorbit,transformedbywayofcomparameterswithrespecttoframe(c).
Thistransformedsequenceinvolvesmovingthemalongtheorbittothereferenceframe(c).
Thecoordinate-transformedimagesarealikeexceptfortheregionoverwhichtheyaredened.
Notethattheregionsarenotparallelograms;thus,methodsbasedonthetraditionalafnemodelfail.
However,inpracticethetwomethodsdifferfortworeasons:1.
Cumulativeerror:inpractice,theestimatedcoordinatetransformationsbe-tweenpairsofimagesregisterthemonlyapproximately,duetoviolationsoftheassumptions(e.
g.
,objectsmovinginthescene,centerofprojectionnotxed,cameraswingsaroundtobrightwindowandautomaticiriscloses,etc.
).
Whenalargenumberofestimatedparametersarecomposed,cumulativeerrorsetsin.
2.
Finitespatialextentofimageplane:theoretically,theimagesextendinnitelyinalldirections,but,inpractice,imagesarecroppedtoarectangularboundingbox.
Therefore,agivenpairofimages(especiallyiftheyarefarfromadjacentintheorbit)maynotoverlapatall;hence,itisnotpossibletoestimatetheparametersofthecoordinatetransformationusingthosetwoframes.
TheframesofFig.
3.
6werebroughtintoregisterusingthedifferentialparameterestimationand"cemented"togetherseamlesslyonacommoncanvas.
Cementinginvolvespiecingtheframestogether,forexamplebymedian,mean,ortrimmedmean,orcombiningonasubpixelgrid[31].
(Trimmedmeanwasusedhere,buttheparticularmethodmadelittlevisibledifference.
)Fig.
3.
8showsthisresult(projec-tive/projective),withacomparisontotwononprojectivecases.
Therstcomparisonistoafne/afnewhereafneparameterswereestimated(alsomultiscale)andusedforthecoordinatetransformation.
Thesecondcomparison,afne/projective,usesthesixafneparametersfoundbyestimatingtheeightprojectiveparametersandignor-ingthetwochirpparametersc(whichcapturetheessenceoftiltandpan).
ThesesixparametersA,baremoreaccuratethanthoseobtainedusingtheafneestimation,astheafneestimationtriestotitsshearparameterstothecamerapanandtilt.
Inotherwords,theafneestimationdoesworsethanthesixafneparameterswithintheprojectiveestimation.
Theafnecoordinatetransformisnallyapplied,givingtheimageshown.
Notethatthecoordinate-transformedframesintheafnecaseareparallelograms.
3.
9SummarySomenewconnectionsbetweendifferentmotionestimationapproaches,inpar-ticulararelationbetweenafnetandafneowhavebeenpresented.
Thisledtotheproposaloftwonewtechniques,projectivetandprojectiveowwhichestimatetheprojectivecomparameters(coordinatetransformation)betweenpairsofimages,takenwithacamerathatisfreetopan,tilt,rotateaboutitsopticalaxisandzoom.
Anewmultiscalerepetitivealgorithmforprojectiveowwaspresentedandappliedtocomparametrictransformationsforsendingimagesoveraserendipitouscommuni-cationschannel.
Thealgorithmsolvesforthe8parametersofthe"exact"model(theprojectivegroupofcoordinatetransformations),isfullyautomatic,andconvergesquickly.
Theproposedmethodwasfoundtoworkwellonimagedatacollectedfrombothgood-qualityandpoor-qualityvideounderawidevarietyoftransmissionconditions(noisycommunicationschannels,etc.
)aswellasawidevarietyofvisualconditions(sunny,cloudy,day,night).
Ithasbeentestedprimarilywithaneyeglass-mountedPSD,andperformssuccessfullyeveninthepresenceofnoise,interference,scenemotion(suchaspeoplewalkingthroughthescene),andparallax(suchastheauthor'sheadmovingfreely.
)FIGURE3.
8FramesofFig.
3.
7"cemented"togetheronsingleimage"canvas,"withcom-parisonofafneandprojectivemodels.
Notethegoodregistrationandniceappearanceoftheprojective/projectiveimagedespitethenoiseintheserendipi-toustransmitterofthewearablePersonalSafetyDevice,wind-blowntrees,andthefactthattherotationofthecamerawasnotactuallyaboutitscenterofpro-jection.
Toseethisimageincolor,seehttp://wearcam.
org/orbitswhereadditionalexamples(e.
g.
,somewherethealgorithmstillworkeddespite"crowdnoise"wheremanypeoplewereenteringandleavingthebuilding)alsoappear.
Selectingjustafewofthe20framesproducesapproximatelythesamepicture.
InthiswaythemethodologymakesitdifcultforacriminaltojamorpreventtheoperationofthePersonalSafetyDevice.
Notealsothattheafnemodelfailstoproperlyestimatethemotionparameters(afne/afne),andevenifthe"ex-act"projectivemodelisusedtoestimatetheafneparameters,thereisnoafnecoordinatetransformationthatwillproperlyregisteralloftheimageframes.
Bylookingatimagesequencesascollectionsofstillpicturesrelatedtooneanotherbyglobalcomparameters,theimageswereexpressedaspartoftheorbitofagroupofcoordinatetransformations.
Thiscomparametricphilosophyfortransforms,imagesequencecoding,andtransmissionsuggeststhatratherthansendingeveryframeofavideosequence,wemightsendareferenceframe,andthecomparametersrelatingthisreferenceframetotheotherframes.
Moregenerally,wecansendaphotoquanti-graphicimagecomposite[1],alongwithalistingofthecomparametersfromwhicheachimageinthesequencemaybedrawn.
Anewframeworkforconstructingtransforms,basedonanEdgertonianratherthanaNyquistsamplingphilosophy,wasproposed.
ConcomitantwithEdgertoniansampling,wastheprincipleofFearofFunctionality(FoF).
Byputtingourselvesintheshoesofonewhowouldregardfunctionalityasundesirable,anewframeworkemergesinwhichunpredictabilityisagoodthing.
WhiletheFoFframeworkseemsatrstparadoxical,itleadsthewaytonewkindsofimagetransformsandimagecompressionschemes.
Forexample,theproposedcomparametricimagecompressionisbasedonabestcaseFoFmodel.
Thismodelofcomparametriccompressionisbestsuitedtoawearableserendipitouspersonalimagingsystem,especiallyonethatnaturallytapsthemind'seye,withthepossibilitythatatanytimewhatgoesintheeyemightalsogointoanindestructible(e.
g.
,distributedontheWorldWideWeb)photographic/videographicmemoryrecallsystem.
Inthefuture,itisexpectedthatmanypeoplewillwearpersonalimagingdevices,andthattherewillbeagrowingmarketforEyeTap(TM)videocamerasoncetheyaremanufacturedinmassproduction.
Thefundamentalissueoflimitedbandwidthoverwirelessnetworkswillmakeitdesirabletofurtherdevelopandrenethiscompara-metricimagecompressionandtransmissionapproach.
Moreover,arobustbest-casewirelessnetworkmaywellsupplantthecurrentworst-caseengineeringapproachusedwithmanywirelessnetworks.
PTP,alossy,connectionless,serendipitouslyupdatedtransmissionprotocol,willndnewapplicationsinthefutureworldofubiquitousEyeTapvideotransmissionsofrst-personexperiences.
3.
10AcknowledgementsThisworkwasmadepossiblebyassistancefromKodak,DigitalEquipmentCor-poration,XybernautCorp.
,CITO,NSERC,CLEARnet,andmanyothers.
Theauthorwouldalsoliketoexpressthankstomanyindividualsforsuggestionsandencouragement.
Inparticular,thanksgoestoRozPicard,JonathanRose,WillWaites,RobertErlich,LeeCampbell,ShawnBecker,JohnWang,NassirNavab,UjjavalDesai,ChrisGraczyk,WalterBender,FangLiu,ConstantineSapuntzakis,AlexDrukarev,andJeanneWiseman.
Someoftheprogramstoimplementthep-chirpmodelsweredevelopedincollaborationwithShawnBecker.
JamesFung,JordanMelzer,EricMoncrieff,andFelixTangarecurrentlycontribut-ingfurtherefforttothisproject.
MuchofthesuccessofthisprojectcanbeattributedtotheFreeSourcemovementingeneral,ofwhichtheGNUprojectisoneofthebestexamples.
RichardStallman,founderoftheGNUeffort,deservesacknowledgementforhavingsetforththegeneralphilosophyuponwhichmanyoftheseideasarebased.
FreecomputerprogramsdistributedundertheGNUGeneralPublicLicense(GPL)toimplementtheVideoOrbitsworkdescribedinthisarticleareavailablefromhttp://wearcam.
org/orbits/index.
htmlorhttp://wearcomp.
org/orbits/index.
html.
Thisworkwasfunded,inpart,bytheCanadiangovernment,usingtaxpayerdollars.
Accordingly,everyattemptwasmadetoensurethatthefruitsofthisla-bormadearefreelyavailabletoanytaxpayer,withouttheneedtopurchaseanycomputerprogramsorusecomputerprogramsinwhichtheprincipleofoperationoftheprogramshasbeendeliberatelyobfuscated(seehttp://wearcam.
org/publicparks/index.
html).
Accordingly,theabovecomputerprogramsweredevelopedforuseundertheGNUX(GNU+Linux)operatingsystemandenvironmentwhichmaybedownloadedfreelyfromvarioussites,suchashttp://gnux.
org.
ThismanuscriptwastypesetusingLaTeXrunningonasmallwearablecomputerdesignedandbuiltbytheauthor.
LaTeXisfreeandrunsunderGNUX.
ThecomputerprogramstoconductthisresearchandproducetheresultscontainedhereinwerealsofreeandrunundertheGNUXsystem.
References[1]Mann,S.
,Humanisticintelligence/humanisticcomputing:"wearcomp"asanewframeworkforintelligentsignalprocessing,ProceedingsoftheIEEE,86,2123–2151,Nov.
1998,http://wearcam.
org/procieee.
htm.
[2]Mann,S.
,Anhistoricalaccountofthe"WearComp"and"WearCam"projectsdevelopedfor"personalimaging,"inInternationalSymposiumonWearableComputing,IEEE,Cambridge,MA,October13–14,1997.
[3]Mann,S.
,Eyeglassmountedwirelessvideo:computer-supportedcollabora-tionforphotojournalismandeverydayuse,IEEEComSoc,144–151,1998,specialissueonwirelessvideo.
[4]Movingpicturesexpertgroup,mpegstandard,http://www.
wearcam.
org/mpeg/.
[5]Rosenberg,J.
,Kraut,R.
E.
,Gomez,L.
,andBuzzard,C.
A.
,Multimediacom-municationsforusers,IEEECommunicationsMagazine,20-36,1992.
[6]Mann,S.
,WearableWirelessWebcam,1994,http://wearcam.
org.
[7]Edgerton,H.
E.
,Electronicash,strobe,MITPress,Cambridge,MA,1979.
[8]TerryDawson,V.
,Ax.
25amateurpacket-radiolink-layerprotocol,andax25-howto,amateurradio,1984,http://www.
wearcam.
org/ax25/.
[9]Mann,S.
,Smartclothing:thewearablecomputerandwearcam,PersonalTechnologies,1(1),21–27,1997,[10]Xu,J.
B.
,Po,L.
M.
,andCheung,C.
K.
,Adaptivemotiontrackingblockmatch-ingalgorithmsforvideocoding,IEEETrans.
Circ.
Syst.
andVideoTechnol.
,97,1025–1029,1999.
[11]Mann,S.
,Personalimagingandlookpaintingastoolsforpersonaldocumen-taryandinvestigativephotojournalism,ACMMobileNetworking,4(1),23–36,1999,specialissueonwearablecomputing.
[12]Tekalp,A.
,Ozkan,M.
,andSezan,M.
,High-resolutionimagereconstructionfromlower-resolutionimagesequencesandspace-varyingimagerestoration,inProc.
oftheInt.
Conf.
onAcoust.
,SpeechandSig.
Proc.
,III-169,IEEE,SanFrancisco,CA,Mar.
23–26,1992.
[13]Zheng,Q.
andChellappa,R.
,Acomputationalvisionapproachtoimagereg-istration,IEEETransactionsImageProcessing,2(3),311–325,1993.
[14]Irani,M.
andPeleg,S.
,Improvingresolutionbyimageregistration,CVGIP,53,231–239,1991.
[15]Teodosio,L.
andBender,W.
,Salientvideostills:contentandcontextpre-served,Proc.
ACMMultimediaConf.
,39–46,August1993.
[16]Wolberg,G.
,DigitalImageWarping,IEEEComputerSocietyPress,LosAlamitos,CA,1990,IEEEComputerSocietyPressMonograph.
[17]Adiv,G.
,Determining3Dmotionandstructurefromopticalowgeneratedbyseveralmovingobjects,IEEETrans.
PatternAnal.
MachineIntell.
,PAMI-7(4),384–401,1985.
[18]Navab,N.
andMann,S.
,Recoveryofrelativeafnestructureusingthemotionoweldofarigidplanarpatch,Mustererkennung1994,Tagungsband.
,1994.
[19]Tsai,R.
Y.
,andHuang,T.
S.
,Estimatingthree-dimensionalmotionparame-tersofarigidplanarpatchI,IEEETrans.
Accoust.
,Speech,andSig.
Proc.
,ASSP(29),1147–1152,1981.
[20]Faugeras,O.
D.
andLustman,F.
,Motionandstructurefrommotioninapiece-wiseplanarenvironment,InternationalJournalofPatternRecognitionandArticialIntelligence,2(3),485–508,1988.
[21]Shashua,A.
andNavab,N.
,Relativeafne:theoryandapplicationto3Dreconstructionfromperspectiveviews,Proc.
IEEEConferenceonComputerVisionandPatternRecognition,1994.
[22]Sawhney,H.
,Simplifyingmotionandstructureanalysisusingplanarparallaxandimagewarping,ICPR,1,403–8,1994,12thIAPR.
[23]Kumar,R.
,Anandan,P.
,andHanna,K.
,Shaperecoveryfrommultipleviews:aparallaxbasedapproach,ARPAImageUnderstandingWorkshop,Nov.
10,1994.
[24]Mann,S.
Compositingmultiplepicturesofthesamescene,inProc.
46thAnnualIS&TConference,50–52,TheSocietyofImagingScienceandTech-nology,Cambridge,MA,May9–14,1993.
[25]Szeliski,R.
andCoughlan,J.
,Hierarchicalspline-basedimageregistration,CVPR,194–201,1994.
[26]Campbell,L.
andBobick,A.
,Correctingforradiallensdistortion:asimpleimplementation,TR322,M.
I.
T.
MediaLabPerceptualComputingSection,Cambridge,MA,1995.
[27]Wyckoff,C.
W.
,Anexperimentalextendedresponselm,S.
P.
I.
E.
Newsletter,16–20,1962.
[28]Mann,S.
andPicard,R.
,Being"undigital"withdigitalcameras:extend-ingdynamicrangebycombiningdifferentlyexposedpictures,Tech.
Rep.
323,M.
I.
T.
MediaLabPerceptualComputingSection,Cambridge,MA,1994.
(AlsoinIS&T's48thannualconference,422–428,May7–11,1995,http://wearcam.
org/ist95.
htm,Washington,DC.
)[29]Artin,M.
,Algebra,Prentice-Hall,EnglewoodCliffs,NJ,1991.
[30]Mann,S.
,Waveletsandchirplets:time-frequencyperspectives,withapplica-tions,inAdvancesinMachineVision,StrategiesandApplications,Archibald,P.
,Ed.
,WorldScienticSeriesinComputerScience,32,WorldScientic,Singapore,NewJersey,London,HongKong,1992.
[31]Mann,S.
andPicard,R.
W.
,Virtualbellows:constructinghigh-qualityimagesfromvideo,inProc.
IEEEFirstInternationalConferenceonImageProcessing,363–367,Austin,TX,Nov.
13–16,1994.
[32]Tsai,R.
Y.
andHuang,T.
S.
,Multiframeimagerestorationandregistration,inAdvancesinComputerVisionandImageProcessing,JAI,1,317–339,1984.
[33]Huang,T.
S.
andNetravali,A.
N.
,Motionandstructurefromfeaturecorrespon-dences:areview,Proc.
IEEE,82(2),252–268,1984.
[34]Navab,N.
andShashua,A.
,Algebraicdescriptionofrelativeafnestructure:connectionstoeuclidean,afneandprojectivestructure,MITMediaLabMemoNo.
270,1994.
[35]VanTrees,H.
L.
,Detection,Estimation,andModulationTheory(PartI),JohnWiley&Sons,NewYork,1968.
[36]Young,R.
K.
,WaveletTheoryandItsApplications,KluwerAcademicPub-lishers,Boston,1993.
[37]Weiss,L.
G.
,Waveletsandwidebandcorrelationprocessing,IEEESignalPro-cessingMagazine,13–32,1994.
[38]Mann,S.
andHaykin,S.
,Thechirplettransform—ageneralizationofGabor'slogontransform,VisionInterface'91,June3–7,1991.
[39]Mann,S.
andHaykin,S.
,Adaptivechirplettransform:anadaptivegeneral-izationofthewavelettransform,OpticalEngineering,31,1243–1256,1992.
[40]Horn,B.
andSchunk,B.
,Determiningopticalow,ArticialIntelligence,17,185–203,1981.
[41]Wang,J.
Y.
andAdelson,E.
H.
,Spatio-temporalsegmentationofvideodata,inSPIEImageandVideoProcessingII,120–128,SanJose,CA,February7–9,1994.
[42]Mann,S.
andPicard,R.
W.
,Videoorbitsoftheprojectivegroup;asimpleapproachtofeaturelessestimationofparameters,TR338,MIT,Cambridge,MA,seehttp://hi.
eecg.
toronto.
edu/tip.
html1995.
(AlsoappearsinIEEETrans.
ImageProc.
,Sept1997,6(9),1281–1295.
)[43]Bergen,J.
,Burt,P.
J.
,Hingorini,R.
,andPeleg,S.
,Computingtwomotionsfromthreeframes,inProc.
ThirdInt'lConf.
Comput.
Vision,27–32,Osaka,Japan,December1990.
[44]Lucas,B.
D.
andKanade,T.
,Aniterativeimage-registrationtechniquewithanapplicationtostereovision,inImageUnderstandingWorkshop,121–130,1981.
[45]Wang,J.
Y.
A.
andAdelson,E.
H.
,Representingmovingimageswithlayers,ImageProcessingSpec.
Iss:ImageSeq.
Compression,12,625–638,1994.
[46]Hennessy,J.
L.
andPatterson,D.
A.
,ComputerArchitecture:AQuantitativeApproach.
MorganKauffman,2nded.
,1995.
[47]Wilson,R.
andGranlund,G.
H.
,Theuncertaintyprincipleinimageprocessing,IEEETransactionsonPatternAnalysisandMachineIntelligence,6,758–767,1984.
[48]Segman,J.
,Rubinstein,J.
,andZeevi,Y.
Y.
,Thecanonicalcoordinatesmethodforpatterndeformation:theoreticalandcomputationalconsiderations,IEEETrans.
onPatt.
Anal.
andMach.
Intell.
,14,1171–1183,1992.
[49]Segman,J.
,Fouriercrosscorrelationandinvariancetransformationsforanoptimalrecognitionoffunctionsdeformedbyafnegroups,JournaloftheOpticalSocietyofAmerica,A,9,895–902,1992.
[50]Segman,J.
andSchempp,W.
,TwomethodsofincorporatingscaleintheHeisenberggroup,JMIVspecialissueonwavelets,1993.
[51]Girod,B.
andKuo,D.
,Directestimationofdisplacementhistograms,OSAMeetingonImageUnderstandingandMachineVision,1989.
[52]Sheng,Y.
,Lejeune,C.
,andArsenault,H.
H.
,Frequency-domainFourier-Mellindescriptorsforinvariantpatternrecognition,OpticalEngineering,27,354–7,1988.
[53]Burt,P.
J.
andAnandan,P.
,Imagestabilizationbyregistrationtoareferencemosaic,ARPAImageUnderstandingWorkshop,Nov.
10,1994.
[54]Hansen,M.
,Anandan,P.
,Dana,K.
,vanderWal,G.
,andBurt,P.
J.
,Real-timescenestabilizationandmosaicconstruction,ARPAImageUnderstandingWorkshop,Nov.
10,1994.