The Complexity and Enumerative Geometry of Aspect

TheComplexityandEnumerativeGeometryofAspectGraphsofSmoothSurfacesSylvainPetitjeanCrin-Cnrs&InriaLorraineBtimentLoriaBP23954506Vanduvre-les-Nancycedex,Franceemail:[e-mail]bjectofveryactiveresearchbythecomputervisioncom-munityinrecentyears,butmostofithasconcentratedonthedesignofalgorithmstocomputetherepresentation.Inthispaper,weworkonamoretheoreticalleveltogiveenumerativepropertiesofthedierententitiesenteringintheconstructionofaspectgraphsofobjectsboundedbysmoothsur-faces,namelythelociofsingularpointsandvisualeventsurfaces.Weshowhowtoolsfromalgebraicgeometryallowtocomputetheirelementaryprojectivecharactersandothernumericalinvariants.Themathematicsneededforourcomputationsuseresultsfromthreeoverlappingsubjectareas,i.e.multiple-pointtheory,enumerativegeometry,andintersectiontheory.1IntroductionInformally,theaspectgraph[KoenderinkandvanDoorn,1979](alsocalledviewgraph)isaqualitative,viewer-centeredrepresentationwhichenumeratesallpossibleappearancesofanobject.Moreformally,choosingacameramodel(orthographic-parallel-orperspective-central-projection)andaviewpointdeterminestheaspectofanobject(i.e.,thestructureoftheobservedline-drawing).Therangeofpossibleviewpointscanbepartitionedintomaximalconnectedsets(regions)thatyieldidenticalaspects.Thechangeinaspectattheboundarybetweenregionsiscalledavisualevent.Themaximalregionsandtheassociatedaspectsformthenodesofanaspectgraph,whosearcscorrespondtothevisualeventboundariesbetweenadjacentregions.Beforegoingfurtheron,letusgiveanexampleassumingorthographicprojection[Petitjeanetal.,1992].Figure1.ashowsashadedviewofasquash-shapedobjectdescribedbyaquarticsurfacewhoseimplicitequationis4y4+3xy25y2+4z2+6x22xy+2x+3y1=0:Figure1.bshowsaline-drawingofthesameobject.Parabolicandecnodalcurveshavebeendrawnonthesurfacetorevealitsstructurebyseparatingitsconvex,hyperbolicandconcaveparts.Aswillbeshowninthenextsections,thesecurvesplayacrucialroleintheconstructionoftheaspectgraph.Figure1.c-dshowstheaspectgraphofthetransparentsquash.Underorthographicprojection,therangeofpossibleviewpointsistwo-dimensionalandcanbemodeledasaunitviewsphere.Thisspherehasbeenpartitionedintoanumberofmaximalregionssuchthatpointswithinaregionseethesameaspectoftheobject.Theseregionsaredelineatedbyanumberofcurvescalledvisualeventcurves.ThecharacteristicaspectsassociatedwitheachregionareshowninFigure1.d.Here,weusedalongitude/latitudeparameterizationofthespheretodisplayalltheaspect-graphregionsinasinglepicture.Finally,theaspectgraphitselfisdisplayedinFigure2.Recently,algorithmshavebeenproposedandimplementedforconstructingtheaspectgraphofsmoothandpiecewise-smoothobjects.Someofthesealgorithmsrelyonnumericalmethodstosolvesystemsofpolynomialequations(likehomotopycontinuationforinstance[Morgan,1987]),theothersusesymbolicmethods(cylindricalalgebraicdecomposition[Collins,1975]andGrbnerbases[Buchberger,1985]).Sym-bolicmethodsprovideinniteaccuracyateverystage(whichisimportantsincecomputationsthatdealwithalgebraicorsemi-algebraicsetsareunstable),butattheexpenseofhighcomputationalcosts.Algorithmsforconstructingtheviewgraphofsolidsofrevolutionhavebeendescribedandimple-mented:[EggertandBowyer,1989,KriegmanandPonce,1990]usenumericalmethodsandmorerecently[RoyandvanEelterre,1992]useasymbolicapproach.Forobjectsboundedbysmoothsurfaces,itwasrecognizedearlythatsingularitytheoryoeredacompletecatalogofvisualevents[Kergosien,1981,Platonova,1981,Arnold,1983]whichcouldbeusedtoelucidatethestructureandformationofaspectgraphs[KoenderinkandvanDoorn,1979,CallahanandWeiss,1985].Assumingorthographicprojection,theseideashavebeenimplementedforsmoothobjectsboundedbyparameterizedalgebraicsurfaces2a.b.courbeparaboliquecourbeflecnodalec.abcdefghijklmd.abcdefghijklmFig.1.a.Asquash-shapedobject.b.Itsparabolicandecnodalcurves.c.Theaspectgraphofthetransparentsquashinparameterspace.d.Thecorrespondingaspects.in[PonceandKriegman,1990](numerical)and[Rieger,1992](symbolic).Forimplicitalgebraicsurfaces,[Petitjeanetal.,1992]reportsthefullimplementationofanalgorithmusingnumericalmethodsandas-sumingorthographicprojection,while[Rieger,1993a]presentsasymbolicalgorithmforbothparallelandcentralprojection.Thefullclassicationofthevisualeventsforthecaseofpiecewise-smoothalgebraicsurfaces1observedunderperspectiveprojectionhasonlybeencompletedveryrecently[Rieger,1993b],aftertheworksof[Rieger,1987]and[Tari,1991],andasymbolicalgorithmisreported.Mostoftheworkachievedthusfaronaspectgraphsmerelygiveslocal,oratmostsemiglobal,infor-mationaboutthevisualeventsurfaces,andbringsupmanytheoreticalquestionsofaglobalkind.Amongthesequestionsare:Isthereanupperboundforthenumberofnodesoftheaspectgraphofanobjectboundedbyasmoothalgebraicsurfaceintermsofthedegreedofitsdeningequation?Theanswerisyes,andthebestknownboundisO(d12)fororthographicprojectionandO(d18)forperspectiveprojec-tion[Rieger,1993b].Actually,thisresultcomesasaspecialcaseofaformulaobtainedforthenumberofnodesoftheviewgraphofapiecewise-smoothsurfaceXconsistingofnsmoothalgebraicsurfacesofdegreeat