Unique Recovery of Motion and Optic Flow via Lie Algebras
Proceedings of the Ninth International Joint Conference on Artificial Intelligence. Perception. Pages 889-890.
© 1985 International Joint Conferences on Artificial Intelligence
Abstract
Wc use "ome ideas from thc thcory of Lic groups and Lic algcbras to study the problcm of rccovcring rigid motion from a timc-varyiog picturc. Wc are ablc to avoid thc prohlcm of finding corrcsponding points hy considcring only what can bc dctcrrnincd from picturc point valucs and thcir time derivatives. We do not assumc that we can track individual point.• in tbc imagc, nor that wc are given any of their velocit.ics (i.c., thc optic flow) . Among our rcsults are: Thc 6 point df I dt theorem, showing that generically* •• the valucs of df I dt at Ii points of thc monochrome image I arc neccssary aud sufncicut to spccify the motion of a given ohject. The 2-co\or theorem for optic flow, which states that the optic flow vcctor is uniquely spccificd at a gencric point of the image if there arc 2 or morc color dirncnsions. Also, wc gct the color vcrsion of the 6 point theorem, thc 2 colors, 3 points corollary, which reduccs the numbcr of points rcquired to 3, if there arc at least 2 color dimensions.
- Dallard and Drown 1982]
- Ballard, Dan a Harry and Chrisl.ophcr M. Brown, Computer Vision, l'rentice-llall, Englewood Clilfs, 191!2. [TA l!i32 .ß31, ISBN 0-1 :1-165:!16-1].
- Blicher, A. Pctcr, "The Stereo Matehing Problern frorn thc Tnpological Viewpoint," l'rocccdings of the Ilighth International Joint Confcrence on Artijicial fntclligenc e, 1983, 1016 -1049.
- lllichcr 1981
- Blicher, A. !'der, "fo;dge Detcdion and Geometrie Mcthods in Computer Vision," Ph.D. thcsis, Mathcrnatics Departrncnt, Univcrsity of California, Bcrkeley, Dccernber I !181. Also Stanford Univcrsity Compute r Scicnce Dcpartrnent tcchnical report STAN- CS-85-1011 and Al rncrno AIM-352, February 1985.
- Bruss and Horn 1983]
- Bruss, Anna R. and fierthold K.P. Horn, "Passive Navigation," Computer Vi.•ion, Craf>hic.•, and fmage Proces.•ing, 21, 1983, 3~20. [llorn and Sdounck 1980]
- llorn, Berthold K .P. and Brian G. Scbunck, "Determining Optical Flow," MIT Al Memo 572, MIT Artificial lntelligence Laboratory, April 1!180; also Arlijiciallntclligcnc e, 17, 1981, 185 -203.
- Nagel 1983]
- Nagel, l!ans-llellrnul,, "Displacerncnt Vcctors Dcrivcd from Second- Order lnknsity Variations in Image Setjucnces," Computer Vision, Graphics, and Image Proce.•••ing, vol. 21, 198:!, 85--117. [Prazdny t!l8:l
- Prazdny, K., "On thc Information in Optical Flows," Computer Vi.>ion, Cr,lphics, and fmage Proce.•.•ing, vol. 22, 1983, 239 ~259. [Tsai and lluang 198-1]
- Tsai, Rog,cr Y. and Thornas S. lluallg, "Uitiquc!lcs.' and Estimation of Thrce-Dirncnsional Motion Parametcrs of Rigid Objccts with Curved Surfaccs,'' fHHR Tran.<~action,., on J>a,ttern Analysis and Machine lntclligcnce, vol. I'AMI-fi, no. I, 198~, 13~27.
- UIIman 1979]
- Ullrnan, Shirnon, The Interpretation of Visual Motion, MIT Press, Carnbridgc, 1!179. [UF21l.U1:l ISIIN 0-2ti2-21007-XJ.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
UNIQUE RECOVERY OF MOTION AND OPTIC FLOW VIA LIE ALGEBRAS
A. Peter Blicher ·
Computer Scicnce Departrnent, Stanford Univcr.,ity, Stanford, CA 9-{:105 and M<lthematic,, Department, Univer8ity of Californifl, ßerkeley
and
Stephen M. Omohundro *'
Physics Department, University of California, Berkeley
tion is then given hy 1 : R -> /1'(:l), i.e., :L" a patlr in tlrc trarrsfor mation group. Irr fad, 1 deiirres a I-parameter family of trarrsforma tions . Since wc arc intcre><tcd only irr srnall .:hangcs frorn tlre currcnt statc, wc take 1(0) = 1, the idcntity in /~(:!) (wc eould have donc this anyway hy usirrg tlre group structurc to translatc baek to tlre idcn tity ). l·'or evcry t, 1 givcs a rigid motion of R: 1 , sirrr.e we are idcntify ing E(3) witlr tlre rigid nrotions of R 3 , i.e. 1(t) : R 3 -+ R 3 · Each point of R 3 is carricd along with this motion, and dcscribes a path in R 3 (dcfincd by 1p(t) = ("t(t))(p), p E R 3 ). !11 particular, evcry point of our surfacc of interest, enrhcddcd in R 3 , has such a path. Now apply the imaging projedion, and restriet attcnt.ion only to the visible surfaec of the enrhcdded objcct . ßy composit.ion, tlris Ieads to a path through each point tlrat gcts lrit in tlre irnage. (delined by .:Yq(t) = 7r(("t(t))(p)), q E M 2 ). Nowconsidcronly asirrglctirne, t = 0. The structure wc have presentcd thus l'ar is surnnrarized irr Fig. (flow).

Fig. (1\ow)
Each such path in the picturc has a vclocity vcctor, and cach point in thc irnage has a path, so tlrcre is a vedor lidd delincd on thc imagc, This is usually callcd tlre optic jlow, but it is morc t:onsistcnt witlr rnatlrematieal terrni11ology to call its integral, i.e. tlrc paths in thc irnage, the optic jlow. Wc will rescrvc tlrc tcrm OTJtic jlow for this irrtegral, i.c. the rnap 'Pt : U -+ H 2 wlridr specil1es tlre paths of corresponding poiuls in lhe piclun~ wilh inilial poinls in Lhc rcgion U, while using optic velor.ity jield or optic vrctor jir.ld for its irrstarrtancous vclocitics, thc vectors d<pt/dt. Sinrilarly, tlre paths in R" definc a vector field on R 3 , and tlre path 1 in B(:l) dcfines a tangent vcctor at thc idcntity in E(3).
Thc availablc data, howcver, is not tlre optic Ilow or vcctor fielt!, but. t.hc Lirne-varying picture furrction lt which is just Ure projection of Uw intrinsic Rurfacc funcLion fi', which wc a..~sumc is earricd along with tlrc rnotion, i.e. wc ncglcct changcs irr I duc purcly to plrotometric clfccts, such as spccular rellection. Since wc are considcring orrly the dilfcrential theory, we regard our data as telling ua only thc instan talleous value lo, and all the time derivatives at t = 0. This is the same as knowing the Taylor scrics for lt· Wc will orrly use tlre lst
ABSTRACT
Wc use "ome ideas from thc thcory of Lic groups and Lic algcbras to study the problcm of rccovcring rigid motion from a timc-varyiog picturc. Wc are ablc to avoid thc prohlcm of finding corrcsponding points hy considcring only what can bc dctcrrnincd from picturc point valucs and thcir time derivatives. We do not assumc that we can track individual point.· in tbc imagc, nor that wc are given any of their velocit.ics (i.c., thc optic flow) . Among our rcsults are:
Thc 6 point df I dt theorem, showing that generically* ·· the valucs of df I dt at Ii points of thc monochrome image I arc neccssary aud sufncicut to spccify the motion of a given ohject.
The 2-co\or theorem for optic flow, which states that the optic flow vcctor is uniquely spccificd at a gencric point of the image if there arc 2 or morc color dirncnsions.
Also, wc gct the color vcrsion of the 6 point theorem, thc 2 colors, 3 points corollary, which reduccs the numbcr of points rcquired to 3, if there arc at least 2 color dimensions.
I INTRODUCTION
For lhc past scvcral ycars, rnany rcsearchers have becn invcstigat ing prohlcms of rnoving ohjects and obscrvcrs (sec c.g., [Tsai and Huang l!J!l~J, [l'razd11y 1983], [Nagel 1983], [Horn and Schunck 1980], [ßruss and llorn l !1~3], [UIIrnan l !J7!J]). A convcntional paradigrn is to consider 2 suhproblcms: finding thc optic !low in the irnage, thcn cornputing 3dirnensional motion . Finding thc optic flow in monochrome imagcs by poi11t tracking is, howcver, degcncratc cxccpt for spccial point.·, just as for thc pointmatehing prohlem [lllichcr 198:!, lllichcr 198~]. Kg. at a single poi11t, thc imagc function and its time derivative teil us nothing about motion pcrpendicular to the gradient of thc imagc function.
Wc considcr a rigid ohjcct uiulergoing an arbitrary motion in space. Our data is a time-varying imagc, i.e. a map I : I X M 2 -+ Rn, whcrc I is a time intcrval, M 2 is somc 2-dirnensiona\ manifold, specifically thc irnagc plane, and n is the nomher of indcpcndcnt color dilncnsions; n = 1 for monochrome picturcs. Wc conccrn oursclvcs herc with the problern of !inding the rnotion of the ohject, particularly, how rnuch data iM nccessary and suflicient. Rather than rnakc a.·sump tiolls ahout lirst !inding point corrcsporuknces or optic Jlow, wc con sider thc full situation ol' a rnap frorn the rigid rnotion group to the lime-varying image {huL only for t.hc inlerior of a. Mingle ohjccL), and we dcvdop tlrc dillcrcntial thcory, h:L·cd on t.hc data of tlrc picturc and it.M time derivative.
We rcgrct tlrat spar.c lirnitations precludc dc!ining rnathcmatical l.crrns. II fuller prcsentation, a.· wdl a.· morc extensive r<,fcrcnces, can hc found in IBiiclrer 1981].
II ]'HE MATII]l:_MATICAL STRUCTURE
Tlrc sii,uat.ion is tlrat. ol' l<'ig. (·'), just <L· in [lllidrer 198:1], cxccpt now thc nature of tlrc trarrsfornr:üion y will hc pararnount.
Wc· a.re intrt~f(!!il.<~d iu ri~id molioiiH in 1{ 3 , MO !I E /~'{:!), thc l·:udidt·an (rigid nrotiorr) group ol' R". The tinre cvolutiorr of tl~t> moderivative. AL a point p of thc imagc, call thc optic flow vector v. Then in a frame with vclocity v at r· in Lhe image, 11 docs not appcar Lo changc; (.hc optic flow ·pc<:ific· the motion of corrcsponding points. Thu· if wc lcave the fmmc lixcd, wc sec Lhat
*This work wos ""l'l'ortcd in I'BrL by DARI'A couLrads N00039-82-C-0250 and N0003V-84-C-02ll.
**Prct~ent. addrcslt: Thiuking Mnci1incs, Cambridt(c, MMrt.
**. A generic prop(·rt.y iH one whir.h iN t.rne ror n ty]}iCfll clc.mcnt. or 8 spacc, i.c ror a vcry dcnKC suhsd or Lhc HIJß<".c. l·'or Lhi~ papcr, wc t.nkc t.hiK t.o mcnn nn opcn d-cnee tmbtwL. Set~ !lllidwr IUH-1) for n dh~cussion of gt:ncricity.
where D. mcan· diiTcrentiation hy thc vcctor v, <:quivalcnt to v · V. (ThiH iH wdl-known in the CO!Il.<!XL of Of>Lic ßow; Hel! e.g. [IJorn and Sdnmc·k 1!180], [llallard and llrown IH!12J.) (·;quation (·) shows how it i· Lhat w<: only have partial information about 11: we only know I c·ornponenL. We can im rnediatdy sc·e, also, that if I Ioad multiple dimt·n!iions, i.e. if Uu~ r<: were mure Lhan I t:olor dinwnsion, wc would hav<: informatinn about multiple - r.omp<>IH! nt...~, and tJ would hc uniquc1y determin<:d for generic I · ThiH is the diiTercntial verHion of the 2-color theorC'III we have prov<:cl earlier [lllir.her 1!1!1:1, lllidoer 1!1!1~] . Finding opti<: llow, like rnatching, is rnuch ea.~i<:r with c:olor. We forrnalizc this in
Theorem. (2-color l.heorc!ln for optoc flow) l·'or a gencric tirne varying irnage funr.tion lt: M 2 -+ ll.", U.., opti<: flow v<:d.or is uniqudy Mpcc·. ilic ~d a.l a ~eneric·. point or Lhe ima.ge if n ~ 2, i.c~ . fur 2 or mnrc c ~ulor dimt~m~inns.
Whcn we fixt = 0, e:1<:h Hid<: of equation (·) iH just a nounbcr, so for eado 71 we havc· a map D.(/)(7') : 11 ._.. a real numbl'r. W<: have Ums ddined astring of linear rnappings ( v.f. stand· for vcctor jicld, 11.6. for vcctor bund/e ): .
tangent vector on H(3) >-+ 11. b. ·cction on object >-+
(We rnu·t consider .cction· of a vcc:L<>r bundlc on thc ohjc!et rather l.han vecL<>r jicld., (·cdions of thc tangerot hnrulle) hcc:au·e thc vcctors wc '"" intcrcsted in arc tangcnt vcctors to paths in R 3 going through poinl.s of the ohj<:d. Since thc path· gl!ncrally do not lic in thc objcct, lhcir tan!(cnt vectors ""'"ln't hc in thc l.angcnt spacc of Llw ohjcct, but rathN arl! rncrdy l.angent vecL<>rs in R 3 .)
Tloc Lic algchra 0 of a Lic grou p G is a vcd.or space which can b., icfcontilicd wi!.h Lhc Langen!. SJ>:ICe of G ·at LI"' identity. 11'(3) is a Lie group, and Lhcreforc associatcd with it is thc Lie algchra r(:l}; and sincc E(:!) is a 6-dimcnsional manifold, r(3) is a 6-dimcnsional vector spacc. Thc tangent vcctor 1'(0), which is the instantancous motion, r.an thcrdorc he thought of as an dcmcnL of thc Lie algchra f{3).
Wc can do tllis for cvcry path ')', hcnec f~r cvcry clcrncnt of r(3), giving us a homomorphism from thc Lic algchra r(3) to scctions of thc vcctor hundle on thc objcct, and likcwisc again to a Lic algebra of vector ficlds on thc irnagc of thc ohject in the image plane. Tbe cornposition of these is a Lic algcbra homomorphisrn . Thc sequencc of linear rnaps can thereforc bc written
This defines a map r(3) -+ R,k c. an clcmenL of r'(3), the dual of !{3). Now wc havc cnough rn~chinery to attack some qucstions. Tbe first qucstion is whether therc is cnough information in dl / dt to uniqucly spccify thc instantancous motion, for gencric I. Thc instan taneous motion is an elcmcnt of r(3). As wc just saw, for cach point p of thc imagc, thc gcomctry dcllncs an clcment of r'(3). Tbc qucstion then becomcs whdhcr we can span all of r'(:!) by rauging over all points of thc irnagc, for knowing Lhc valuc of applying a dual ha..·is in e'(3) uniqucly spccilics thc ,original vcctor in r(~!) . e'(3) is 6-dirncnsional, so if this is possiblc, it is possible for 6 points corrcsponding to a dual basis. This docsn'L say anything yct ahout finding thc shapc or position of the ohjcct; wc only want to know whethcr wc can recovcr the rnotion for lixcd shape and position.
Theorem (6 poinL dl /dt thcorcm). Let
be a tirne-varying picturc for somc time intcrval I around 0, and some ncighborhood U in Lhc imagc plane of rcgular values of thc imaging projcction of somc 2-dimcnsiorml ohject (Le. a 2-rrianifold) crnhedded in R 3 . lf I cornc· from Lhc projection of a gcncric intrinsic function Oll an object undcrgoing rigid ·moLion in R 3 , tlocn thc valucs of ()I /llt (0, p) at Ii genNie point.~ p E U arc rH!cessary and sullidcnL to uniquely spccify t.Jw in~t.f\rJl,arH~OtiM moLiOll or t.hc objcct..
Proof. We arc in dTcct rnc:1.~uring thc optic vdrx:ity lidd with our image function; t.his is whaL equation (·) ""Y"· To bc ahlc to tcll the dilfcrl!ncc bctwccn different d<!mcnl..~ of r(:l), i.c. diiTcrl!nt rnotions, thc rnapping from r(3) to vclociLy liclds on the picture mu·L he 1-l. Sinr.c Lhe mapping is a vccL<>r spar:e hornornorphisrn, this is thc sarne as saying it has no (nontrivial) kernet. Th<! hornornorphisrn r(3) -+ v.b. ·ection., on nbjr.ct h:1.~ no kcrncl , h<!cansc any kcrnd wonld leave Lhc enLire objcd lixed, hnL a rigid rnol.ion of R 3 can lcavc at rnost a linc lixc"l. So r(:!) is rnapJ>crl 1- I l<> ""dion" of hnndl"" on the ohjcct. Now we ""'"(, show that !.Iu· k."-nc·l uf t.he locuroomorphisrn v.b. ·cr.tion· on objr.ct-+ 11.1. '· on imllgt: dcx!lln't r.ontain anyt.hing timt comes frorn Lh<! previous rnap frnrn r(:l). The kernd of the cnrrc!llt map is just thc sections whose vecL<>rs lic along the ray· of projcction to the picturc. l·'or orthogonal projecLion, verLical tran·lation would of course bc in this kcrncl, but we are :1.~surning a proj.,ctivc projcction, i.e. LlmL Lhe ray· all mcct at a point; for a pf'anar ·retina this is the usual pcr·pcdiv" projection.


Wc havc to show that any such rnotion , whcrc point.~ move only along rays, cannoL r.ornc frorn a rigid rnol.ion. This is C''-"Y to "''c; take :! point.s a, b, c on thc objcd not all on thc sarnc linc in R 3 . Since a rigid rnotion of R 3 can ooily lcavc a single linc axis ( nr nothing) lixed, at lca.~L I of Lloe point.~ rnust movc, say a. lf a rnovcs down (t.oward thc irnagc plane), b rnust rnovc up, to kccp thdt distance constant (rigid rnotion) . Sincc b is rnoving np, c rnust rnove down. Jlut thcn a and c arc hoth rnoving down ancl therdorc narrowing thcir distancc, showing that thc motion cannot bc a rigid motion, .i.c. the kcrncl of v.b. ·ections on object -> v.f. '· on image is not in the image of r(3)-+ v.b. ,ection., on object (cxccpt for 0, of coursc). So we know that Lhc composition r{;J) -+ v.l. '· on. image ha.~ no kerncl, i.c. is 1-1. This mcans Lhat cvcry rigid motion gives. a unique optic vclocity ficld, and the vector spacc of such liclds is 6-dimensional.


Actually, wc showcd more than that. Wc showcd that a generic sct of 3 points cannot stay fixcd in thc imagc- we didn't even have to considcr thc wholc vector Held. The set of vedors at :l such points in thc image make up a 6-dimensional vector space, so what we showcd is that the map e(3) -> vectors at :J given point.· in irnage has no kerne!, i.c. is l-1.
That rncans that to spccify a motion, i.e. an clcrncnt of e(3), we only havc to figurc out thc optic velocity vcctors at :l points. A gencric function, via cquation (·), teils us l cornponcnt of cach of the vectors (by gcnericity, thc gradicnt is nonzcro at all 3 points). rr wc had 2 gcncric fu ncl.ions, then we could rccovcr both corn poncnts of each of thc 3 vcctors by using cquation ( ·) for both functions (gencrically, the gradicnts will bc lincarly indepcndent, i.c. in different dircctions at thc 3 points). ParenUoctically, we have just proved
Coroll.!lry (2 r:olors, 3 points). For gencric f taking values in 2 or morecolor dirncnsions, thc values ol' Df /Dt(O, p) at :l noncollincar points p E I! arc nccessary and suflicient to uniqucly specify the instantaneous rnotion of thc objcct.
Now wc rnust show that I componcnt at each of 6 point.~ is as good as 2 cornporocnts at cach of 3 points. We saw earlicr that df ddincs an clerncnt of e'(3). Thus thc gcornctry delincs a map 1"R 2 -> t'(3). What wc saw earlicr is
Lemma (3 fihcr Iemma). lf wc choosc 3 gcncric points in R 2 , and 2 lincarly indcpcndcnt covcctors in cadt libcr ovm thosc points, the 6 rcsult,ing points of T'R 2 arc mappcd to a spanning sct in t'(3).
What wc will now show is that wc can choosc any 6 gcncric points in 7"R 2 , i.c. ·6 gcncric points in the imagc, and 6 gcncric valucs of df at l.hosc points (i.c. a gcncric f) . This is prctty '"""Y by rnaking use of Uoe :l fih<'r Iemma. Thc Iemma still aJ>plies for any ncighborhood of R 2 , i.c. wc can choosc thc :l poinL· arhitrarily closc togcther. This givcs us
l,cnuna (local spanning). Evcry neighborhood of cvcry point in T'R 2 c.ontains fi poinl.· whido arc rnappcd to a spanning sct in t'(:l).
Proof. Choosc a point and ncighborhood in 7"H 2 · lt projccts to a neighhorhood of R 2 , in which we can choosc 3 gcneric points. We can thcn dooosc Ii points in T'R 2 , 2 to a libcr, by Lhc 3 liber Iemma. QED (local spanning).

Now wc can sec what happcns when wc choose 6 points in the imagc. df J;ives us Ii points in 7''R 2 . Wc can pcrturb thcse points to guaranke that df 0 0. Now siru:c evNy ncighborhood of cach point map~ l.o a. Mpa.nnin~ Mei of t·(:q (local Hpannin~ Iemma), we <~an a.lways p··rl,urh i.l11· nl.h l"'i11t so t.loat il, iH mappcd l,o somdhi11g oul.·ide thc span of l,he fi~st n - - I poiul.s (al. lc:L·t through n = Ii, auyway). This gives a periurha.tion of the () pointH whid1 ma.ps io a spanning Hct. Sincc spa11niug sel.s arc open, i.hcse poinL· will still span under sullicienUy small perturhation. (ln gencral, onc rnight necd a pcrturbation of both the location of thc poinl.· and of f to guaranke a span uiug scL. The dq~cnNat" situal.iou occurs whcn thc optic vclocity vcctor is in the dir.,dion of constant /.) QEDI
ill A.FTERWORD
By virtuc of t,J,., local spauning Iemma and Uoc 3 lihcr ).,rnrna, our rcsults '"" local, i.c. i.h"y hold iu an arbitrarily small ncighborlrood gcnerically cvery rwighborhood ha.· Ii poinl.~ yiclding suflicicnt data. This is signifkant b.,cause it implics Lhat an csl.irnat" of thc rnotion can Iw nht.ained from auy ""ighborhood. ln prad.ic.,, of coursc, usiug a vcry small neighhorhood wnuld Iead to a vcry bad l'stimatc. Onc would rather use many points ovcr a large rcgion to obtain a least squarcs estim:üc. Hut thc localncss rneans Umt cstirnates can hc made over a mnge of scales, and that a proccd.ure for segrnentation hascd on local estirnat.cs is well-founded,
ACKNOWLEDGMENTS
Wc are grateful to Tom llinford for his hclp and encouragement throughout the period of this work.
@inproceedings{ijcai1985p177,
title = {Unique Recovery of Motion and Optic Flow via Lie Algebras},
author = {Blicher, A. Peter and Omohundro, Stephen M.},
booktitle = {Proceedings of the Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-85}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Aravind Joshi},
pages = {889--890},
year = {1985},
note = {Perception},
url = {https://ijcai.org/proceedings/1985/177},
}
TY - CPAPER TI - Unique Recovery of Motion and Optic Flow via Lie Algebras AU - Blicher, A. Peter AU - Omohundro, Stephen M. T2 - Proceedings of the Ninth International Joint Conference on Artificial Intelligence, IJCAI-85 PB - International Joint Conferences on Artificial Intelligence PY - 1985 SP - 889 EP - 890 UR - https://ijcai.org/proceedings/1985/177 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
Welcome
Future Conferences
AI Journal Division
IJCAI Proceedings
About IJCAI
IJCAI Awards