CHAPTER19

PatternRecognition：ObjectMeasurementIntroductionThisChapterismainlyabouttheobjectmeasurementandidentifyingobjectbymeasurevalue.

1Sizemeasurements2Shapeanalysis3Textureanalysis4Curveandsurfacefitting5Summary1SizeMeasurements

1.1AreaandPerimeterPixelCountArea：Thesimplestareameasurementisjustacountofthenumberofpixelsinside(andincluding)theboundary.PerimeterofaPolygon:Theperimeterofanobjectis:AreaofthePolygon:Theareaofthepolygondefinedbypixelcentersisthatallpixelnumberssubtractonemorethanhalfnumberofboundarypixels;thatis:1.1AreaandPerimeter1.ComputingareaandperimeterThereisasimplewaytocomputetheareaofapolygonbysummingtheareasofalltrianglesintheboundaryofthepolygon.Figure19-1Computetheareaofapolygon

1.1AreaandPerimeterTheareaofatriangleis:

Theareaofapolygonis:0(x1,,y1)(x2,,y2)(x2,,y1)x2x1y2y1Figure19-2Computingtheareaofatriangle

1.1AreaandPerimeter2.BoundarySmoothingSimplyskipboundarypixelscanobscurethetrueshapeoftheobjectandreducetheaccuracyofthemeasurement.

Onecycleofparametricboundaryfunctioncanbelowpass-filteredinthefrequencydomainby1)aFouriertransform2)multiplicationbyaphaselesslowpasstransferfunction3)aninverseFouriertransformFigure19-3ParametricboundaryrepresentationStartingPointStartingPoint1.2AverageandIntegratedDensityTheIODisthesumofthegraylevelofallpixelsintheobject.Itreflectsthe‘mass”or“weight’oftheobjectandisnumericallyequaltotheareamultipliedbythemeangrayleveloftheobjectinterior.1.3LengthandWidthForobjectsofrandomorientation,itisnecessarytolocatethemajoraxisoftheobjectandmeasurerelativelengthandwidth.Thereareseveralwaystoestablishtheprincipalaxisofanobjectoncetheobjectboundaryisknown:

1)Computeabestfitstraight(orcurved)linethroughthepointsintheobject;2)Becomputedfrommoments;3)UsestheMinimumEnclosingRectangle(MER)aroundtheobject.2ShapeAnalysis

2.1RectangularityAmeasurementthatreflectstherectangularityofanobjectistherectanglefitfactor:R=A0/AR.RrepresentshowwellanobjectfillsitsMER.Therectanglefitfactorisboundedbetween0and1.Anotherrelatedshapefeatureistheaspectratio:A＝W／LwhichistheratioofwidthtolengthoftheMER.

Thisfeaturecandistinguishslenderobjectsfromroughlysquareorcircularobjects.

2.2CircularityCircularitymeasure:Thisfeaturetakesonaminimumvalueof4πforacircularshape.Morecomplexshapesyieldhighervalues.ThecircularityCisroughlycorrelatedwithcomplexityoftheboundary.2.2CircularityArelatedcircularitymeasurementistheboundaryenergy.Supposeanobjecthasperimeter

P

andwemeasuredistancearoundtheboundaryfromsomestartingpointwiththevariablep.Atanypoint,theboundaryhasaninstantaneousradiusofcurvaturer(p).ThecurvaturefunctionatpointpisThefunctionK(p)isperiodicwithperiodP.WecancomputetheaverageenergyperunitlengthofboundaryasForfixedarea,thecirclehasminimumboundaryenergy:Fig.19-4Radiusofcurvature2.2CircularityAthirdcircularitymeasuremakesuseoftheaveragedistancefromaninteriorpointtotheboundaryobject:wherexi

isthedistancefromtheithpixeltothenearestboundarypointinanobjectofNpoints.TheshapemeasureisFigure19-5Thedistancetransform2.3InvariantMoments

BackgroundInformationTheinvariantmomentswasadvancedbyHuin1962,whoprovedtheinvariabilitybyalgebramethod.Correlationliterature:[1]

GONZALEZRC,WINTZP.Digitalimageprocessing[M]London:Addison-WesleyPublishingCompany,1977.354—360.

Itdefinedtheinvariantmomentsbasedonthecentregeometrymoments,andapplytheinvariantmomentstodigitalimageprocessing.[2]

ABU-MOSTAFAYS,PSALTISD.Recognitiveas2pectsofmomentinvariants[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1984,6(6):698—706Itdiscusstheinformationlosing,informationcondensation,etc.ininvariantmoments.BackgroundInformation[3]RESISTH.Therevisedfundamentaltheoremofmomentinvariants[J].IEEETransactionsonPatternAnaMachineIntelligence,1991,13(8):830—834.ItmodifiedtheHu’stheory,eliminatethemistakes.[4]JIANGXY，BUNKEH。Simpleandfastcomputationmoments[J].PatternRecognition,1991,24(8):801-806.Itadvancedafastcalculationmethodofinvariantmoments.[5]BELKASIMSO,SHRIDHARM,AHMADIM.Pat2ternrecognitionwithmomentinvariants:acomparativestudyandnewresults[J].PatternRecognition,1991,24(12):1117—1138.Itsyntheticallyresearchedthevariousapplicationsofinvariantmoments,andprovedthatinvariantmomentscannotgiveidealresultinmanyinstance.TheoryofMomentsDefinition:

Thesetofmomentsofaboundedfunctionf(x,y)oftwovariablesisdefinedby:

f(x,y):densityoftheimagewithsubsectioncontinuumonlimitedplanes.PropertyofMoments

1.Asjandktakeonallnonnegativeintegervalues,theygenerateaninfinitesetofmoments.2.Theset{Mjk}isuniqueforthefunctionf(x,y),andonlyf(x,y)hasthatparticularsetofmoments.3.Theparameterj+kiscalledastheorderofthemoment.Thereisonlyonezero-ordermoment:anditisclearlytheareaoftheobject.Wecanmakeallfirst-andhigher-ordermomentsinvariantwithrespecttothesizeoftheobjectbydividingthemwithM00.TheoryofMomentsCentralMomentsThecoordinatesofthecenterofgravityofanobjectare:Theso-calledcentralmomentsarecomputedbythecenterofgravityastheorigin:Thecentralmomentsarepositioninvariant.

TheoryofMomentsPrincipalAxesTheangleofrotationθthatcausesthesecond-ordercentralmomentμ11tovanishmaybeobtainedfrom:

Thecoordinateaxesx’,y’atanangleθfromthex,yaxesarecalledtheprincipalaxesoftheobject.Iftheobjectisrotatedthroughtheangleθbeforemomentsarecomputed,orifthemomentsarecomputedrelativetothex’,y’axes,thenthemomentsarerotationinvariant.

Normalized

MomentsThenormalizedcentralmomentoff(x,y)is:

,j+k=2,3,...TheoryofMomentsTheoryofInvariantMomentsCentralmomentswhichrelativetoprincipalaxiscalculationandstandardizedbyarea,isinvariantwhentheobjectismagnified,paralleled,rotated.Simplexcentralmomentcantokenthegeometryshapeoftheplainobject,buttheyarenotinvariant.Invariantcanbeconstructedfromthesemoments.ThismethodisfirstadvancedbyHu.Heutilizedcentralmomentsconstructed7invariants.SevenInvariantMomentsFirst-ordermomentisrelatedtoshape;second-ordermomentdemonstratestheextenddegreeofcurveenclosebeelineaverage;Third-ordermomentisaboutsymmetrysurveyofaveragevalue.Fromsecond-ordermomentandthird-ordermomentcaneduceasetof7invariantmoments,whicharenotinfluentbytheparallel,rotateandproportionvaried.Fromnormalizedsecond-ordercentralmomentandthird-ordermomentcaneduce7invariantmoments:SevenInvariantMomentsCalculationofInvariantMoments

Asetofdifferentchangesfromasameimage,tovalidatethe7invariantsofmoments.(a)istheoriginalimage,(b)is(a)thatrotatedfor45°,(c)is(a)thatreducedby1/2,(d)isthemirrorsymmetryimage.a

bcdApplicationofInvariantMomentsinObjectRecognitionInvariantmomentsisthestatisticcharacterofimages,whichsatisfiedparalleled,flexed,rotatedinvariable,iswideapplicationinimageidentifydomain.Asdescribeshape,assumedf(x,y)inobjectis1andoutsideis0,thenitisonebyonecorrespondingtotheshapeoftheobject,anditsmomentreflecttheshapeinformationoftheobject.ApplicationofInvariantMomentsinObjectRecognitionTodistinguishsimilarbodiesneedaprodigiouscharactercollect.Theyieldhighdimensionclassimplementissensitivitytothenoiseandinnervariety.Insomesituation,severallow-ordermomentscanreflectaobject’snotableshapecharacter.Ifthereliableinvariantmomentswhichcandistinguishshapecharacterexist,theyusuallycanbediscoveredbyexperiments.AnArithmeticofObjectRecognitionInvariantMomentsInimageprocessing,thereareapproximatelytworecognitionmethodsoftheobjectimage:ImagematchingandImagecharactermatching.Imagematchingfortherotationandzoomobjectimagehaslowrecognitionability.Inobjectrecognitionsystem,whenmethodischoseforpick-upshapecharacteroftheimage,itisneedtodeterminantinwhichconditionthetwoimagesissimilar,incommonuseisdistancesimilarlevelmeasurementmethod.TheincommonusemeasurementisEucliddistance.AnArithmeticofObjectRecognitionInvariantMomentsDefinition:TheEucliddistancebetweenmodepatternvectorXandYis:

nischaracterspatialdimension.Aboveintroducedusingcentralmomentsoftheimagetogained7invariantmoments.This7invariantmomentsisparallel,rotated,andmeasureinvariant.Proceedingobjectrecognition,wecanuseimage’s7invariantmomentsrespectivebasedonregionandboundarycomposingthecharacteristicmoments.TheEucliddistanceofthetwoimagesastheirsimilarlevel.AnArithmeticofObjectRecognitionInvariantMomentsUseInvariantMomentsofobjectrecognitionarithmeticcanbecarriedoutthefollowing:1、Initialtargetimageandtestimageprocessingandthevalueofsomepreprocessing,thetargetseparatefromthebackground,gray-scaleimagetoachievetheamendment,noiseremoval,sharpeningtheedge.Thisarithmeticiscalculatedbytheimagehistogramvaluefromtheappropriatedomainrealizedsegmentation.AnArithmeticofObjectRecognitionInvariantMoments2.Edgedetectionortrackingprofiletargetsfromtheboundarymap.3.Momentofthetwocentresandthennormalized,inthenormalizationofHuonthebasisoftheuseofthesamemoment,sevenoutofthesamemomentofcommongoalsintheimageandobjectivesofthetestimageseigenvector;4.VectorcomputingtwoEuclideandistancebetweentheD,apre-setthresholdLtodeterminethesimilarityofthetwo,ifD<L,Imagetestsofthegoalsistofindthetarget,otherwisenot.ApplicationofInvariantMomentsTheinvariantmomentsanditscombinationshasbeenappliedsuccessfullyinmanyareas.Suchas:PrintedCharacterRecognitionChromosomalanalysisShipsRecognitionMedicalImageAnalysis2.4ShapeDescriptors1.TheDifferentialChainCodeThedifferentialchaincodereflectsthecurvatureoftheboundary.Convexitiesandconcavitiesshowupaspeaks.Theboundarychaincodeshowstheboundarytangentangleasafunctionofdistancearoundtheobject.

Figure19-6Thechaincodeanditsderivative2.4ShapeDescriptors2.FourierDescriptorsThreedifferentperiodicfunctionsthatcompletelydescribeanobject’sshape:theboundarychaincode,thepolarboundaryfunction,andthecomplexboundaryfunction.Againbecauseitisperiodic,eachoftheseboundaryfunctionshasadiscretespectrum.Requireonlylow-frequencyspectrumpulseamplitudeandphasecanbethebasicshapeofanobject.Therefore,thevalueoftheseoptionsfortheshapedescriptors.2.4ShapeDescriptors3.TheMedialAxisTransformAnotherdatareductiontechniquethatretainsshapeinformationisthemedialaxistransformationdiscussedinthepreviouschapter.

(a)(b)Figure19-7Themedialaxistransform:(a)digitalimage;(b)medialaxistransform;(c)Theeffectoforientation(c)3Textureanalysis

3.1Definitions

Thewordtextureoriginallyreferredtotheappearanceofwovenfabric,butageneraldefinitionis“thearrangementorcharacteristicsoftheconstituentelementsofanything,especiallyasregardssurfaceappearanceortactilequalities”.Atexturefeatureisavalue,computedfromtheimageofanobject,thatquantifiessomecharacteristicofthegray-levelvariationwithintheobject.Normally,atexturefeatureisindependentoftheobject’sposition,orientation,size,shape,andaveragegraylevel.。

3.2TextureSegmentationSometimesobjectsdifferfromthesurroundingbackground,andeachother,intexturebutnotinaveragebrightness.Inthatcase,imagesegmentationmustbebasedontexture.3.3StatisticalTextureFeaturesSimplestatisticalmeasuresofgray-levelvariationincludestandarddeviation,variance,skewness,andkurtosis.Thesecanbecomputedasmomentsofthegray-levelhistogramoftheobject,ascanthemodulefeaturewhereMisthenumberofpixelsintheobjectandNthenumberofgraylevelsinthegrayscale.3.3StatisticalTextureFeatures1.TheCo-OccurrenceMatrixSupposethatweestablishadirectionanddistanceinanimage.Thenthei,jthelementoftheco-occurrencematrixPforanobjectisthenumberoftimes,dividedbyM,thatfraylevelsIandjoccurintwopixelsseparatedbythatdistanceanddirectionintheobject,whereMisthenumberofpixelpairscontributingtoP.entropyinertiaenergy3.4OtherTextureFeatures1.SpectralFeaturesForagivenimage,thetwo-dimensionalFouriertransform,ofcourse,containscompleteinformationontheimage’stexture.。2.StructuralFeaturesThestructuralapproachtotextureanalysisassumesthatthetexturepatterniscomposedofaspatialarrangementoftextureprimitives.Forexample,somesmallobjects,constituteapatternofrepeatunits.Featureextractiontoidentifytheseelementsintoandquantitativeanalysisoftheirspatialarrangement.4CurveandSurfaceFitting

4.1MinimummeansquareerrorfittingGivenasetofpoints(xi,yi),acommonlyusedfittingtechniqueistofindthefunctionf(x)thatminimizesthemeansquareerror:where(xi,yi)arethedatapoints.Iff(x)istobeaparabola,itsequationis:andthecurve-fittingprocedureisusedtodeterminethebestvaluesofthecoefficientsc0,c1andc2.Inotherwords,thesefactorsthatdeterminethevalue,sothattheparabolatoagivenpointintheerrorofthemeansquareerrorsenseofthesmallest.4.2MatrixFormulationWebeginbyformingmatricesBcontainingthegivenx-values,Ycontainingthegiveny-values,andCcontainingthecoefficientsthataretobedetermined:thecolumnvectoroferrorvaluescanbewrittenasE＝Y－BCwherethematrixproductBCisthecolumnvectorofy-valuescomputedfromupeq.Meansquareerroris:4.2MatrixFormulationSubstitutingE=Y-BCintoupeq.，differentiatingwithrespecttotheelementsofC,C＝[BTB]-1[BTY]Whichisthevectorofcoefficientsthatminimizethemeansquareerror.[BTB]-1BTiscalledthepseudoinverseofB.Ifthenumberofpointsisequaltothenumberofcoefficients,Bisasquarematrixandcanbeinverteddirectly.C＝B-1YThus,theproblemistoincludetheunknownnumberoflinearequationstosolve.4.3One-DimensionalParabolaFitAsanumericalexample,letusfitaparabolathroughasetoffivepoints.Thechartbelowshowsthegroupbythispointandthemeanstodeterminethebestfitparabola.0xf(x)Figure19-8Fitt