Determining the Orientation of a Painted Sphere from a Single Image A Graph Coloring Proble

SingleImage:AGraphColoringProblem

KevinM.Lynch

DepartmentofMechanicalEngineering

NorthwesternUniversity2145SheridanRd.Evanston,IL60208USAEmail:kmlynch@northwestern.edu

TEL:847-467-5451FAX:847-491-3915

November2001

1

Abstract

Inourworkonroboticmanipulation,werequiredamethodfordeterminingtheorientationofamarkedspherefromasinglevisualimage.OursolutionutilizesfeaturesofdifferentcolorspaintedonthesphereattheverticesofthePlatonicsolids.Themainresultofthispaperistheminimizationofthenumberoffeaturecolorsneededtosolvethecorrespondenceproblem.Theminimizationofcolorsisagraphcoloringproblem.

IndexTerms—Graphcoloring,featurecorrespondence,Platonicsolids,surfacemarkings,sphereorientation.

1Introduction

Weareinterestedinthefollowingproblem:Givenasphereofknownradiusataknownlocationwithanunknownorientation,paintthespherewithfeaturepointssotheorientationofthespherecanbedeterminedfromasinglevisualimage.

Thisproblemaroseinourresearchongrasplessroboticmanipulation,suchasthrowing,catch-ing,andcontrollingtheorientationofarollingball.Forfeedbackcontroloftheorientationofaball,wedecidedtopainttheballwithfeaturepointsandusevisionfeedbackfromasinglecam-era[3].Assumethefeaturesaredistinguishedbytheirdifferentcolors.(Differentshapesorsizeswouldalsowork.)Thenthequestionis:Whereshouldthefeaturepointsbeplacedonthesphere,andhowmanydifferentfeaturecolorsarenecessary?

Toanswerthisquestion,wemakethefollowingthreeobservations.(1)Assumingacalibratedcameraandaknownradiusandlocationofthecenterofthesphere,thespatiallocationofavisiblefeaturepointcanbedeterminedbysimplyintersectingtheline-of-sightoftheimagelocationwiththeknownspheresurface.(2)Thespatiallocationsoftwofeaturepointsaresufficienttodeterminetheorientation:onepoint(alongwiththeknowncenterpointofthesphere)fixesanaxisofrotationofthesphere,andtheseconddeterminestheamountofrotationaboutthataxis.Ifmorethantwopointsarevisible,standardalgorithms(e.g.,[4])canbeusedtofindthebest-fitorientationtothe

2

data.1(3)Ifeachfeaturepointhasauniquecolor,thecorrespondenceproblem(matchingfeaturesinthemodeltotheobservedfeatures)istrivial.Therefore,ananswertothequestionistopaintthefeaturepointssoatleasttwopointsarevisibleforanyorientationofthesphere,andtogiveeachpointauniquecolor.

Ourinterestisinminimizingthenumberoffeaturecolorsnecessarytosolvethecorrespon-denceproblem.Iffewercolors(orshapesorsizes)areneeded,thenthefeaturescanbemoreeasilydistinguishablefromeachother,increasingtherobustnessofthesystemtoproblemssuchasvaryinglightingconditions,whichchangestheperceivedcolorofthefeatures.Inthiswork,weminimizethenumberoffeaturecolorsbyexploitingtheinformationintheknownspatialre-lationshipofthefeaturepoints.Forinstance,aspheremayhavetwobluefeaturepoints,oneofwhichappearsnearred,yellow,andgreenfeatures,andoneofwhichappearsnearblack,orange,andpurplefeatures.Thenabluefeatureinanimagecanbedisambiguatedbythecolorsofitsneighboringfeatures.

Whilemanypatternsoffeaturesoverthespherecouldbeused,wechosetopaintthespherewithfeaturesattheverticesofoneofthefivemaximalinscribedPlatonicsolids(Figure1).Thisassuresequaldistributionoffeaturepointsoverthesphere.Treatingtheverticesandedgesofthepolyhedraasnodesandedgesofgraphs,weobtainthecorrespondencegraphsinFigure2.Defining

tobethenumberofverticesofthegraphs,wehave

forthetetrahedron(4faces),

fortheoctahedron(8faces),

forthecube(6faces),

fortheicosahedron(20

faces),andforthedodecahedron(12faces).Thecolors.

verticesofthecorrespondencegraph

arecoloredwith

Twoproblemsneedtobesolved:

(i)Findingthevisiblefeaturesubgraph.Manyofthefeaturepointswillbeoccluded,soonlyasubgraphofthefullcorrespondencegraphwillbevisible.Thevisiblesubgraphdependsontheorientationoftheballandthedistanceoftheballfromthecamera.

1

Inthispaper,wearenotconcernedwiththeaccuracyorerrorpropertiesofanyparticularfittingalgorithm.

3

dodecahedroncubetetrahedron

octahedron

icosahedron

Figure1:ThefivePlatonicsolids,andmarkingaspherewithfeaturepointsattheverticesofthemaximalinscribedcube.

52031tetrahedron11727384591010171283491318141926320451611610512614037octahedron

cube1510icosahedrondodecahedronFigure2:ThecorrespondencegraphsforthePlatonicsolids.

(ii)Uniquelycoloringthesubgraphs.Insteadofuniquelycoloringeachfeaturepoint,itisonly

necessarytouniquelycoloreachuniquevisiblesubgraphinthefullgraphtosolvethecor-respondenceproblem.Wewouldliketominimizethenumberofcolorsneededtosolvethis

4

881212122020202020

visiblerotationalsubgraphsymmetries

121

3212151

uniqueinstancesincoloringsfullgraph

81212

lowerbound

–6–

4

–7–5

20302030601260

34––9104532

33

Table1:Fortheviewinganglesindicated,theimageisguaranteedtocontainthesubgraphsshown.“Rotationalsymmetries”indicatesthenumberofindistinguishableorientationsofthesub-graph.Thenumberofuniquesubgraphcoloringsaregiven,ifcolorsareused,aswellasthenumberofinstancesofthesubgraphinthefullgraph.Basedonthese,itisstraightforwardtoderivealowerboundon.Therightmostcolumnrepresentsthemaincontributionofthepaper—theminimumnumberofdifferentcolorsneededtosolvethecorrespondenceproblem.Inmostrows,isgreaterthanthelowerboundduetocoloringconstraintsimposedbythetopologyofthecorrespondencegraph.

problem.

Thesecondproblemisagraphcoloringproblem.Inthispaper,wegivetheminimumnumberofdifferentfeaturecolors

neededtosolvethecorrespondenceproblemasafunctionofthe

Platonicsolidusedtogeneratethefeaturesandthevisualfieldofthecamera(howmuchofahemisphereisvisible).Arelatedproblemingraphtheoryisfindingthelocaldistinguishingnumberofacyclicgraph:theminimumnumberofcolorssuchthattherearenotwoisomorphicsubgraphs(ofaspecifiedsize)inthefullgraph[1].

ThemainresultsofthispaperaresummarizedinTable1.Therestofthepaperdescribesthecontentsofthetable.

Ourresultsweredevelopedfortrackingtheorientationofarotatingballbeingmanipulatedbyarobot.Acloselyrelatedproblemisthatofdesigninganabsoluteencoderforaspherical

5

dαRFigure3:Thevisualfieldofthecamera.

motor[2,5].Scheinermanetal.[6]haveproposedamethodfordeterminingtheorientationofarandomlypaintedblack-and-whitesphereusingmanyphotoreflectivesensorsscatteredaroundtheoutsideofthesphere,eachreturningavalueof0or1indicatingwhetherthesensorseesblackorwhitesurface.Basedonpreciseknowledgeofhowthespherewaspainted,theyproposeaniterativeoptimizationmethodthatquicklyconvergestoanestimateoftheorientationofthesphere.Intheirexperiments,errorwasontheorderof2degreesfor50sensorsand0.5degreesfor200sensors.

2VisibleSubgraphs

Apinholecameraisplacedadistancevisibleangleofthespherethatisvisible.As

fromthecenteroftheradius

sphere(Figure3).The

indicatestheamountofthehemisphere

increases,morefeaturesbecomevisible.

Table1indicatesthevisiblesubgraphtopology(vertexfeaturesandimpliededges)ascreasesforthecube,icosahedron,anddodecahedron.Thevaluesof

in-

giveninthetablearethe

minimumvaluesatwhichtheimageisguaranteedtocontainthegivensubgraphforanyorientationofthesphere.(Foranyparticularorientationofthesphere,morefeaturesmaybevisible.Thesub-graphsgiveninthetablearethosethatareguaranteedtobecommonforallsphereorientations.)Forboththetetrahedron(

)andtheoctahedron(

),thereisnoguaranteethatmorethan

onefeaturewillbevisibleintheimageforany

.Sinceatleasttwofeaturesarerequiredto

6

determinetheorientationofthesphere,wewillnotconsiderthetetrahedronoroctahedronfurther.ThevisiblesubgraphsarenotquitethesameasthevisiblefacesintheperspectiveaspectgraphsofthePlatonicsolids,asself-occlusionoccursforthespherewhereitdoesnotoccurforapolyhedron.

3Colorings

Iftheverticesofasubgrapharecoloredwith

colors,thesubgraphwillhave

unique

colorings,minusanyduplicatesduetosymmetry.Forinstance,ifthecolors1and2areusedtocolorthethreeverticesofanequilateraltriangle,thenthecolorings1-2-2,2-1-2,and2-2-1(rotatedversionsofeachother)areindistinguishable.(Theorientationofthesphereisnotknowninadvance;thisiswhatwearetryingtosolve.)Similarly,thecoloring1-1-1isnotavalidcoloring,sincetheverticesareimpossibletodistinguishfromeachother.ThenumberofuniquesubgraphcoloringsinTable1canbeobtainedbyanapplicationofBurnside’slemma.Thelowerboundon

inTable1isobtainedbyfindingthesmallestnumberofcolors

such

thatthenumberofuniquecoloringsofavisiblesubgraphisgreaterthanorequaltothenumberofsuchsubgraphsinthefullcorrespondencegraph.If

isgreaterthanorequaltothislower

bound,thenitmaybepossibletocolorthecorrespondencegraphsothateachsubgraphisdistinctlyrecognizableintheimage.

Coloringthefullgraphplacesstrongconstraintsonwhichuniquesubgraphcoloringscanbeused,however.Bycoloringonesubgraph,wehaveconstrainedthepossiblecoloringsofadjacentsubgraphs.Therefore,itisoftenthecasethattherequirednumberofcolorslowerbound.

InthesevenrelevantcasesinTable1,

islargerthanthe

isequaltothelowerboundinonecase,and

isone

greaterthanthelowerboundintheremainingsixcases.Forthreeofthesesixcases,theAppendixgivessimpleproofsthatthelowerboundisnotsufficient.Fortheremainingthreecases,wewrotecomputerprogramswhichenumeratedallpossiblecoloringsusing

equaltothelowerboundand

7

verifiedthatnoneuniquelycoloredallvisiblesubgraphs.Weareworkingonmoreconciselystatedproofsthatthelowerboundsdonotsufficeforthesethreecases.

Notethatthreeisthefewestnumberofcolorsthatallowthecorrespondenceproblem,forthedodecahedronwithatleastfiveverticesofafacevisible.Forthevaluesof

listedinTable1,wehavefoundcoloringsofthecorrespondencegraphs

thatsolvethecorrespondenceproblem.Someofthesecoloringscanbefoundsimplybyhand,andotherswerefoundbycomputerprograms.Allcoloringswereverifiedbycomputerprogramswhichcheckedthateachvisiblesubgraphwasuniquelycolored.Examplecorrespondencegraphcoloringsaregivenbelow,wheretheorderofthecolorscorrespondstothevertexassignmentsinthegraphsofFigure2.Cube(8vertices)

:7colors02314506

Icosahedron(12vertices)

:5colors221043132140:4colors321213201000

Dodecahedron(20vertices)

:10colors40123696917534820875:5colors41121302441300432203:3colors12012201211001212210

4Conclusion

Thespatialrelationshipofimagefeaturescanprovidevaluableinformationinsolvingthefeaturecorrespondenceproblem.InthispaperweusedthisinformationtofullysolvethecorrespondencegraphcoloringproblemforthespecialcaseofaspherepaintedwithfeaturesattheverticesofthePlatonicsolids.

8

Acknowledgments

ThisworkwassupportedinpartbyNSFgrantsIIS-9875469andIIS-9811571.ThankstoPrasunChoudhuryandMegLeefortheirimplementationoftheresultsofthispaper.

References

[1]C.ChengandL.Cowen,“Onthelocaldistinguishingnumbersofcycles,”DiscreteMathemat-ics,196(1-3):97–108,1999.

[2]G.S.ChirikjianandD.Stein,“Kinematicdesignandcommutationofasphericalstepper

motor,”IEEE/ASMETransactionsonMechatronics,4(4):342–353,Dec.1999.

[3]P.ChoudhuryandK.M.Lynch,“Rollingmanipulationwithasinglecontrol,”Conferenceon

ControlApplications,MexicoCity,Mexico,September2001.

[4]B.K.Horn,“Closedformsolutionofabsoluteorientationusingunitquaternions,”Journalof

OpticalSocietyofAmerica,4(4):629–2,1987.

[5]K.-M.LeeandC.-K.Kwan,“Designconceptdevelopmentofasphericalstepperforrobotic

applications,”IEEETransactionsonRoboticsandAutomation,7(1):175–181,Feb.1991.[6]E.Scheinerman,G.S.Chirikjian,andD.Stein,“Encodersforsphericalmotionusingdiscrete

opticalsensors,”inAlgorithmicandComputationalRobotics:NewDirections,B.R.Donald,K.M.Lynch,andD.Rus,eds.Natick,MA:A.K.Peters,2001.

Appendix

Lemma4.1.Fortheinscribedcube(cannotbesolvedwith

)withtwoverticesvisible,thecorrespondenceproblem

colors.

9

Proof.If

,thenatleasttwocolorsareusedtwice,oronecolorisusedthreetimes.Assume

twocolorsareusedtwice.Thetwoverticescolored0mustnotbeadjacenttoeachother,orelsetheywillnotbedistinguishablewhentheyaretheonlytwoverticesvisible.Thereforetheymustbeplacedatoppositecornersofthecube.Similarly,thetwoverticescolored1mustalsobeatoppositecornersofthecube.Inthiscase,theywillbothbeadjacenttoavertexcolored0,sothisisnotavalidcoloring.

Ifonecolorisusedthreetimes,twoverticeswiththesamecolorwillbeadjacent,whichisnotavalidcoloring.ThecorrespondenceproblemcannotbesolvedwithLemma4.2.Fortheinscribedicosahedron(

colors.

)withatriangle(threevertices)visible,thecolors.

correspondenceproblemcannotbesolvedwithProof.For

,thereare20possiblecoloringsofthevisiblesubgraphtrianglebyTable1.Since

thereare20instancesofthetriangleintheicosahedron,eachcoloringmustappearonceinthecorrespondencegraph.Thismeansthetriangles0-0-1,0-0-2,and0-0-3mustappear.Therefore,thegraphmustcontaintwoadjacentverticescolored0.Thisformsoneedgeoftwotriangles,andthethirdvertexofthesetwotrianglesmustbecolored1and2togetthetriangles0-0-1and0-0-2.Togetthetriangle0-0-3,another0mustbeplacedadjacenttooneofthefirsttwo0’s,sinceonlyoneofthefirsttwo0’scanappearinanewtrianglewithtwo0’s.However,a0adjacenttooneofthefirsttwo0’swillalsobeadjacenttothe1or2,resultinginanothertriangle0-0-1or0-0-2.ThecorrespondenceproblemcannotbesolvedwithLemma4.3.Fortheinscribedicosahedron(

colors.

)withadoubletriangle(fourvertices)visible,

thecorrespondenceproblemcannotbesolvedwith

colors.

Proofisbyenumerationofallpossiblecoloringsbycomputer.Lemma4.4.Fortheinscribeddodecahedron(denceproblemcannotbesolvedwith

)withtwoverticesvisible,thecorrespon-

colors.

10

Proof.If

,atleasttwocolorsmustappearthreeormoretimes.Assumethecolor0appears

threetimes.Thethree0’smustbeplacedsotheyarenotadjacenttoeachother,orelsetheywouldbeindistinguishablewhenonlytwoverticescolored0arevisible.Eachofthethreeverticescolored0musthavethreeuniquecolorsadjacent,sothateachofthepairsisdistinguishable.Thisimpliesnineotheruniquecolors,inadditiontothecolor0,sothecorrespondenceproblemcannotbesolvedwith

colors.

)withthreeverticesvisible,thecorrespon-

Lemma4.5.Fortheinscribeddodecahedron(denceproblemcannotbesolvedwith

colors.

Proofisbyenumerationofallpossiblecoloringsbycomputer.Lemma4.6.Fortheinscribeddodecahedron(

)withsevenverticesvisible(verticesofone

pentagonalfaceplustwoverticesofanadjacentface),thecorrespondenceproblemcannotbesolvedwith

colors.

Proofisbyenumerationofallpossiblecoloringsbycomputer.

11