FEATUREEXTRACTIONMETHODSFORCHARACTER
`RECOGNITION|ASURVEY
`(cid:31)IVINDDUETRIER,(cid:3)(cid:3)yANILK.JAIN,xandTORFINNTAXTy
`yDepartmentofInformatics,UniversityofOslo,P.O.Box Blindern,N- Oslo,Norway
`xDepartmentofComputerScience,MichiganStateUniversity,A WellsHall,EastLansing,
`MI{ ,USA
`RevisedJuly , 
`Abstract|Thispaperpresentsanoverviewoffeatureextractionmethodsforo(cid:11)-linerecog-
`nitionofsegmented(isolated)characters.Selectionofafeatureextractionmethodisproba-
`blythesinglemostimportantfactorinachievinghighrecognitionperformanceincharacter
`recognitionsystems.Di(cid:11)erentfeatureextractionmethodsaredesignedfordi(cid:11)erentrepre-
`sentationsofthecharacters,suchassolidbinarycharacters,charactercontours,skeletons
`(thinnedcharacters),orgraylevelsubimagesofeachindividualcharacter.Thefeature
`extractionmethodsarediscussedintermsofinvarianceproperties,reconstructability,and
`expecteddistortionsandvariabilityofthecharacters.Theproblemofchoosingtheappropri-
`atefeatureextractionmethodforagivenapplicationisalsodiscussed.Whenafewpromising
`featureextractionmethodshavebeenidenti(cid:12)ed,theyneedtobeevaluatedexperimentally
`to(cid:12)ndthebestmethodforthegivenapplication.
`FeatureextractionOpticalcharacterrecognitionCharacterrepresentation
`Invariance
`Reconstructability
`tion:Whichfeatureextractionmethodisthebest
` Introduction
`foragivenapplication?Thisquestionledusto
`characterizetheavailablefeatureextractionmeth-
`Opticalcharacterrecognition(OCR)isoneofthe
`ods,sothatthemostpromisingmethodscouldbe
`mostsuccessfulapplicationsofautomaticpattern
`sortedout.Anexperimentalevaluationofthese
`recognition.Sincethemid 's,OCRhasbeen
`fewpromisingmethodsmuststillbeperformedto
`averyactive(cid:12)eldforresearchanddevelopment
`selectthebestmethodforaspeci(cid:12)capplication.In
`[ ].Today,reasonablygoodOCRpackagescanbe
`thisprocess,onemight(cid:12)ndthataspeci(cid:12)cfeature
`boughtforaslittleas$ .However,theseare
`extractionmethodneedstobefurtherdeveloped.
`onlyabletorecognizehighqualityprintedtextdoc-
`umentsorneatlywrittenhand-printedtext.The
`Afullperformanceevaluationofeachmethod
`currentresearchinOCRisnowaddressingdoc-
`intermsofclassi(cid:12)cationaccuracyandspeedisnot
`umentsthatarenotwellhandledbytheavailable
`withinthescopeofthisreviewpaper.Inorderto
`systems,includingseverelydegraded,omnifontma-
`studyperformanceissues,wewillhavetoimple-
`chineprintedtext,and(unconstrained)handwrit-
`mentallthefeatureextractionmethods,whichis
`tentext.Also,e(cid:11)ortsarebeingmadetoachieve
`anenormoustask.
`Inaddition,theperformance
`lowersubstitutionerrorratesandrejectrateseven
`alsodependsonthetypeofclassi(cid:12)erused.Di(cid:11)er-
`ongoodqualitymachineprintedtext,sinceanex-
`entfeaturetypesmayneeddi(cid:11)erenttypesofclas-
`periencedhumantypiststillhasamuchlowererror
`si(cid:12)ers.Also,theclassi(cid:12)cationresultsreportedin
`rate,albeitataslowerspeed.
`theliteraturearenotcomparablebecausetheyare
`Selectionofafeatureextractionmethodisprob-
`basedondi(cid:11)erentdatasets.
`ablythesinglemostimportantfactorinachieving
`Giventhevastnumberofpaperspublishedon
`highrecognitionperformance.Ourowninterestin
`OCReveryyear,itisimpossibletoincludeallthe
`characterrecognitionistorecognizehand-printed
`availablefeatureextractionmethodsinthissurvey.
`digitsinhydrographicmaps(Fig. ),butwehave
`Instead,wehavetriedtomakearepresentativese-
`triednottoemphasizethisparticularapplication
`lectiontoillustratethedi(cid:11)erentprinciplesthatcan
`inthepaper.Giventhelargenumberoffeatureex-
`beused.Two-dimensionalobjectclassi(cid:12)cationhassev-
`tractionmethodsreportedintheliterature,anew-
`comertothe(cid:12)eldisfacedwiththefollowingques-
`eralapplicationsinadditiontocharacterrecogni-
`tion.Theseincludeairplanerecognition[],recog-
`(cid:3)Authortowhomcorrespondenceshouldbead-
`nitionofmechanicalpartsandtools[ ],andtissue
`dressed.ThisworkwasdonewhileTrierwasvisiting
`classi(cid:12)cationinmedicalimaging[].Severalofthe
`MichiganStateUniversity.ThepaperappearedinPat-
`featureextractiontechniquesdescribedinthispa-
`ternRecognition,Vol. ,No.,pp. {, 
`
`
`
`Page 1 of 24
`
`SAMSUNG EXHIBIT 1008
`Samsung v. Image Processing Techs.
`
`

`

`SCANNING
`
`PREPROCESSING
`
`FEATURE EXTRACTION
`
`CLASSIFICATION
`
`POSTPROCESSING
`
`PAPER
`DOCUMENT
`
`GRAY LEVEL
`IMAGE
`
`SINGLE
`CHARACTERS
`
`FEATURE
`VECTORS
`
`CLASSIFIED
`TEXT
`
`CLASSIFIED
`CHARACTERS
`
`TRIER,JAIN,andTAXT
`
`Figure:Stepsinacharacterrecognitionsystem.
`dependingonthespeci(cid:12)crecognitionproblemand
`availabledata.Afeatureextractionmethodthat
`provestobesuccessfulinoneapplicationdomain
`mayturnoutnottobeveryusefulinanotherdo-
`Figure :Agrayscaleimageofapartofahand-
`main.Onecouldarguethatthereisonlyalimited
`printedhydrographicmap.
`numberofindependentfeaturesthatcanbeex-
`tractedfromacharacterimage,sothatwhichset
`perforOCRhavealsobeenfoundtobeusefulin
`offeaturesisusedisnotsoimportant.However,
`suchapplications.
`theextractedfeaturesmustbeinvarianttothe
`AnOCRsystemtypicallyconsistsofthefollow-
`expecteddistortionsandvariationsthatthechar-
`ingprocessingsteps(Fig.):
`actersmayhaveinaspeci(cid:12)capplication.Also,
`thephenomenoncalledthecurseofdimensional-
` .Graylevelscanningatanappropriateresolu-
`ity[ , ]cautionsusthatwithalimitedtraining
`tion,typically { dotsperinch,
`set,thenumberoffeaturesmustbekeptreasonably
`.Preprocessing:
`smallifastatisticalclassi(cid:12)eristobeused.Arule
`ofthumbistouse(cid:12)vetotentimesasmanytraining
`(a)Binarization(two-level
`thresholding),
`patternsofeachclassasthedimensionalityofthe
`usingaglobaloralocallyadaptive
`featurevector[ ].Inpractice,therequirements
`method,
`ofagoodfeatureextractionmethodmakesselec-
`(b)Segmentationtoisolateindividualchar-
`tionofthebestmethodforagivenapplicationa
`acters,
`challengingtask.Onemustalsoconsiderwhether
`thecharacterstoberecognizedhaveknownori-
`(c)(Optional)conversiontoanothercharac-
`entationandsize,whethertheyarehandwritten,
`terrepresentation(e.g.,skeletonorcon-
`machineprintedortyped,andtowhatdegreethey
`tourcurve),
`aredegraded.Also,morethanonepatternclass
` .Featureextraction
`maybenecessarytocharacterizecharactersthat
`canbewrittenintwoormoredistinctways,asfor
`.Recognitionusingoneormoreclassi(cid:12)ers,
`example`'and`',and`a'and`a'.
`.Contextualveri(cid:12)cationorpostprocessing.
`Featureextractionisanimportant
`stepin
`Surveypapers[{],books[{ ],andevalua-
`achievinggoodperformanceofOCRsystems.How-
`tionstudies[ { ]covermostofthesesubtasks,
`ever,theotherstepsinthesystem(Fig.)alsoneed
`andseveralgeneralsurveysofOCRsystems[ ][ {
`tobeoptimizedtoobtainthebestpossibleperfor-
`]alsoexist.However,toourknowledge,nothor-
`mance,andthesestepsarenotindependent.The
`ough,uptodatesurveyoffeatureextractionmeth-
`choiceoffeatureextractionmethodlimitsordic-
`odsforOCRisavailable.
`tatesthenatureandoutputofthepreprocessing
`DevijverandKittlerde(cid:12)nefeatureextraction
`step(Table ).Somefeatureextractionmethods
`(page in[ ])astheproblemof\extractingfrom
`workongraylevelsubimagesofsinglecharacters
`therawdatatheinformationwhichismostrele-
`(Fig. ),whileothersworkonsolid-connected
`vantforclassi(cid:12)cationpurposes,inthesenseofmin-
`or-connectedsymbolssegmentedfromthebinary
`imizingthewithin-classpatternvariabilitywhile
`rasterimage(Fig.),thinnedsymbolsorskeletons
`enhancingthebetween-classpatternvariability."
`(Fig.),orsymbolcontours(Fig.).Further,the
`Itshouldbeclearthatdi(cid:11)erentfeatureextraction
`typeorformatoftheextractedfeaturesmustmatch
`methodsful(cid:12)llthisrequirementtoavaryingdegree,
`therequirementsofthechosenclassi(cid:12)er.Graph
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 2 of 24
`
`

`

`
`FeatureExtractionMethodsforCharacterRecognition|ASurvey
`Table :Overviewoffeatureextractionmethodsforthevariousrepresentationforms(graylevel,binary,
`vector).Grayscale
`Binary
`Vector
`solidcharacter
`outercontour
`(skeleton)
`subimage
`Templatematching
`Templatematching
`Templatematching
`Deformabletemplates
`Deformabletemplates
`UnitaryTransforms
`Unitarytransforms
`Graphdescription
`ProjectionhistogramsContourpro(cid:12)les
`Discretefeatures
`Zoning
`Zoning
`Zoning
`Zoning
`Geometricmoments
`Geometricmoments
`Splinecurve
`Zernikemoments
`Zernikemoments
`Fourierdescriptors
`Fourierdescriptors
`Figure:Digitsfromthehydrographicmapinthe
`Figure :Grayscalesubimages((cid:25) (cid:2) pixels)of
`binaryrasterrepresentation.
`segmentedcharacters.Thesedigitswereextracted
`fromthetopcenterportionofthemapinFig. .
`Notethatforsomeofthedigits,partsofotherprint
`objectsarealsopresentinsidethecharacterimage.
`descriptionsorgrammar-baseddescriptionsofthe
`charactersarewellsuitedforstructuralorsyntactic
`classi(cid:12)ers.Discretefeaturesthatmayassumeonly,
`say,twoorthreedistinctvaluesareidealfordeci-
`siontrees.Real-valuedfeaturevectorsareidealfor
`statisticalclassi(cid:12)ers.However,multipleclassi(cid:12)ers
`maybeused,eitherasamulti-stageclassi(cid:12)cation
`scheme[,],orasparallelclassi(cid:12)ers,wherea
`combinationoftheindividualclassi(cid:12)cationresults
`Figure:SkeletonsofthedigitsinFig.,thinned
`isusedtodecidethe(cid:12)nalclassi(cid:12)cation[,,].
`withthemethodofZhangandSuen[].Note
`Inthatcase,featuresofmorethanonetypeorfor-
`thatjunctionsaredisplacedandafewshortfalse
`matmaybeextractedfromtheinputcharacters.
`branchesoccur.
` . Invariants
`Inordertorecognizemanyvariationsofthesame
`character,featuresthatareinvarianttocertain
`transformationsonthecharacterneedtobeused.
`Invariantsarefeatureswhichhaveapproximately
`thesamevaluesforsamplesofthesamecharacter
`thatare,forexample,translated,scaled,rotated,
`stretched,skewed,ormirrored(Fig.).However,
`notallvariationsamongcharactersfromthesame
`characterclass(e.g.,noiseordegradation,andab-
`Figure:ContoursoftwoofthedigitsinFig..
`senceorpresenceofserifs)canbemodelledbyusing
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 3 of 24
`
`

`

`TRIER,JAIN,andTAXT
`
` .Reconstructability
`Forsomefeatureextractionmethods,thecharac-
`terscanbereconstructedfromtheextractedfea-
`tures[ , ].Thispropertyensuresthatcomplete
`(c)
`(b)
`(a)
`(d)
`informationaboutthecharactershapeispresentin
`theextractedfeatures.Although,forsomemeth-
`ods,exactreconstructionmayrequireanarbitrar-
`ilylargenumberoffeatures,reasonableapproxima-
`tionsoftheoriginalcharactershapecanusuallybe
`(e)
`(f)
`(g)
`obtainedbyusingonlyasmallnumberoffeatures
`withthehighestinformationcontent.Thehopeis
`Figure:Transformedversionsofdigit`'.(a)
`thatthesefeaturesalsohavehighdiscrimination
`original,(b)rotated,(c)scaled,(d)stretched,(e)
`power.Byreconstructingthecharacterimagesfromthe
`skewed,(f)de-skewed,(g)mirrored.
`extractedfeatures,onemayvisuallycheckthata
`su(cid:14)cientnumberoffeaturesisusedtocapturethe
`essentialstructureofthecharacters.Reconstruc-
`invariants.
`tionmayalsobeusedtoinformallycontrolthat
`theimplementationiscorrect.
`is
`easily
`andtranslationinvariance
`Size-
`achieved.Thesegmentationofindividualcharac-
`Therestofthepaperisorganizedasfollows.
`terscanitselfprovideestimatesofsizeandloca-
`Sections{giveadetailedreviewoffeatureex-
`tion,butthefeatureextractionmethodmayoften
`tractionmethods,groupedbythevariousrepre-
`providemoreaccurateestimates.
`sentationformsofthecharacters.Ashortsum-
`maryonneuralnetworkclassi(cid:12)ersisgiveninSec-
`Rotationinvarianceisimportantifthecharac-
`tion.Sectiongivesguidelinesforhowoneshould
`terstoberecognizedcanoccurinanyorientation.
`choosetheappropriatefeatureextractionmethod
`However,ifallthecharactersareexpectedtohave
`foragivenapplication.Finally,asummaryisgiven
`thesamerotation,thenrotation-variantfeatures
`inSection.
`shouldbeusedtodistinguishbetweensuchchar-
`actersas`'and` ',and`n'and`u'.Anotheral-
`ternativeistouserotation-invariantfeatures,aug-
`mentedwiththedetectedrotationangle.Ifthero-
`tationangleisrestricted,say,toliebetween(cid:0)(cid:14)
`FeaturesExtractedFromGrayScaleIm-
`and(cid:14),charactersthatare,say (cid:14)rotationsof
`ages
`eachothercanbedi(cid:11)erentiated.Thesameprinci-
`plemaybeusedforsize-invariantfeatures,ifone
`Amajorchallengeingrayscaleimage-basedmeth-
`wantstorecognizepunctuationmarksinaddition
`odsistolocatecandidatecharacterlocations.One
`tocharacters,andwantstodistinguishbetween,
`canusealocallyadaptivebinarizationmethodto
`say,`.',`o',and`O';and`,'and` '.
`obtainagoodbinaryrasterimage,andusecon-
`nectedcomponentsoftheexpectedcharactersize
`Skew-invariancemaybeusefulforhand-printed
`tolocatethecandidatecharacters.However,agray
`text,wherethecharactersmaybemoreorless
`scale-basedmethodistypicallyusedwhenrecogni-
`slanted,andmultifontmachineprintedtext,where
`tionbasedonthebinaryrasterrepresentationfails,
`somefontsareslantedandsomearenot.Invari-
`sothelocalizationproblemremainsunsolvedfor
`ancetomirrorimagesisnotdesirableincharacter
`di(cid:14)cultimages.Onemayhavetoresorttothe
`recognition,asthemirrorimageofacharactermay
`bruteforceapproachoftryingallpossiblelocations
`produceanillegitimatesymboloradi(cid:11)erentchar-
`intheimage.However,onethenhastoassumea
`acter.Forfeaturesextractedfromgrayscalesubim-
`standardsizeforacharacterimage,asthecombi-
`nationofallcharactersizesandlocationsiscom-
`ages,
`invariancetocontrastbetweenprintand
`putationallyprohibitive.Thisapproachcannotbe
`backgroundandtomeangraylevelmaybeneeded,
`usedifthecharactersizeisexpectedtovary.
`inadditiontotheotherinvariantsmentioned
`Thedesiredresultofthelocalizationorsegmen-
`above.Invariancetomeangrayleveliseasilyob-
`tationstepisasubimagecontainingonecharacter,
`tainedbyaddingtoeachpixelthedi(cid:11)erenceofthe
`and,exceptforbackgroundpixels,nootherobjects.
`desiredandtheactualmeangraylevelsoftheim-
`However,whenprintobjectsappearverycloseto
`age[ ].
`eachotherintheinputimage,thisgoalcannotal-
`Ifinvariantfeaturescannotbefound,anal-
`waysbeachieved.Often,othercharactersorprint
`ternativeistonormalizetheinputimagestohave
`objectsmayaccidentallyoccurinsidethesubim-
`standardsize,rotation,contrast,andsoon.How-
`age(Fig. ),possiblydistortingtheextractedfea-
`ever,oneshouldkeepinmindthatthisintroduces
`tures.Thisisoneofthereasonswhyeverycharac-
`newdiscretizationerrors.
`terrecognitionsystemhasarejectoption.
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 4 of 24
`
`

`

`
`FeatureExtractionMethodsforCharacterRecognition|ASurvey
`. Templatematching
`ExperimentsareneededtodecidewetherDjor
`^RZTjshouldbeusedforOCR.
`WearenotawareofOCRsystemsusingtemplate
`Althoughsimple,
`templatematchingsu(cid:11)ers
`matchingongrayscalecharacterimages.However,
`fromsomeobviouslimitations.Onetemplateis
`sincetemplatematchingisafairlystandardimage
`onlycapableofrecognizingcharactersofthesame
`processingtechnique[ , ],wehaveincludedthis
`sizeandrotation,isnotillumination-invariant(in-
`sectionforcompleteness.
`varianttocontrastandtomeangraylevel),andis
`Intemplatematchingthefeatureextractionstep
`veryvulnerabletonoiseandsmallvariationsthat
`isleftoutaltogether,andthecharacterimageit-
`occuramongcharactersfromthesameclass.How-
`selfisusedasa\featurevector".Intherecogni-
`ever,manytemplatesmaybeusedforeachcharac-
`tionstage,asimilarity(ordissimilarity)measure
`terclass,butatthecostofhighercomputational
`betweeneachtemplateTjandthecharacterim-
`timesinceeveryinputcharacterhastobecom-
`ageZiscomputed.ThetemplateTkwhichhas
`paredwitheverytemplate.Thecharactercandi-
`thehighestsimilaritymeasureisidenti(cid:12)ed,andif
`datesintheinputimagecanbescaledtosuitthe
`thissimilarityisaboveaspeci(cid:12)edthreshold,then
`templatesizes,thusmakingtherecognizerscale-
`thecharacterisassignedtheclasslabelk.Else,
`independent.
`thecharacterremainsunclassi(cid:12)ed.Inthecaseofa
`dissimilaritymeasure,thetemplateTkhavingthe
`.DeformableTemplates
`lowestdissimilaritymeasureisidenti(cid:12)ed,andifthe
`dissimilarityisbelowaspeci(cid:12)edthreshold,thechar-
`Deformabletemplateshavebeenusedextensively
`acterisgiventheclasslabelk.
`inseveralobjectrecognitionapplications[ , ].
`Acommondissimilaritymeasureisthemean
`Recently,DelBimboetal.[ ]proposedtouse
`squaredistanceD(Eq.. - inPratt[ ]):
`deformabletemplatesforcharacterrecognitionin
`Dj=MXi= (Z(xi;yi)(cid:0)Tj(xi;yi));
`grayscaleimagesofcreditcardslipswithpoor
`printquality.Thetemplatesusedwerecharacter
`( )
`skeletons.Itisnotclearhowtheinitialpositionsof
`thetemplateswerechosen.Ifallpossiblepositions
`whereitisassumedthatthetemplateandtheinput
`intheimageweretobetried,thenthecomputa-
`characterimageareofthesamesize,andthesum
`tionaltimewouldbeprohibitive.
`istakenovertheMpixelsintheimage.
`Eqn.( )canberewrittenas
`. UnitaryImageTransforms
`Dj=EZ(cid:0)RZTj+ETj;
`()
`Intemplatematching,allthepixelsinthegray
`whereEZ=MXi= (cid:0)Z(xi;yi)(cid:1);
`scalecharacterimageareusedasfeatures.An-
`drews[ ]appliesaunitarytransformtocharac-
`terimages,obtainingareductioninthenumber
`( )
`offeatureswhilepreservingmostoftheinforma-
`tionaboutthecharactershape.Inthetransformed
`RZTj=MXi= (Z(xi;yi)Tj(xi;yi));
`space,thepixelsareorderedbytheirvariance,and
`()
`thepixelswiththehighestvarianceareusedas
`features.
`Theunitarytransformhastobeap-
`ETj=MXi= (cid:0)Tj(xi;yi)(cid:1):
`pliedtoatrainingsettoobtainestimatesofthe
`()
`variancesofthepixelsinthetransformedspace.
`AndrewsinvestigatedtheKarhunen-Loeve(KL),
`Fourier,Hadamard(orWalsh),andHaartrans-
`EZandETjarethetotalcharacterimageenergy
`formsin  [ ].HeconcludedthattheKL
`andthetotaltemplateenergy,respectively.RZTjis
`transformwastoocomputationallydemanding,so
`thecross-correlationbetweenthecharacterandthe
`herecommendedtousetheFourierorHadamard
`template,andcouldhavebeenusedasasimilarity
`transforms.However,theKLtransformistheonly
`measure,butPratt[ ]pointsoutthatRZTjmay
`(mean-squarederror)optimalunitarytransformin
`detectafalsematchif,say,Zcontainsmostlyhigh
`termsofinformationcompression[ ].Whenthe
`values.Inthatcase,EZalsohasahighvalue,and
`KLtransformisused,thesameamountofinforma-
`itcouldbeusedtonormalizeRZTjbytheexpres-
`tionabouttheinputcharacterimageiscontained
`sion~RZTj=RZTj=EZ.However,inPratt'sformu-
`infewerfeaturescomparedtoanyotherunitary
`lationoftemplatematching,onewantstodecide
`transform.
`whetherthetemplateispresentintheimage(and
`OtherunitarytransformsincludetheCosine,
`getthelocationsofeachoccurrence).Ourproblem
`Sine,andSlanttransforms[ ].Ithasbeenshown
`istheopposite:(cid:12)ndthetemplatethatmatchesthe
`thattheCosinetransformisbetterintermsofin-
`characterimagebest.Therefore,itismorerele-
`formationcompression(e.g.,seepp. {  in
`vanttonormalizethecross-correlationbydividing
`[ ])thantheothernon-optimalunitarytrans-
`itwiththetotaltemplateenergy:
`forms.Itscomputationalcostiscomparabletothat
`^RZTj=RZTjETj:
`ofthefastFouriertransform,sotheCosinetrans-
`()
`formhasbeencoined\themethodofchoicefor
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 5 of 24
`
`

`

`TRIER,JAIN,andTAXT
`
`Hualsodevelopedmomentinvariantsthatwere
`supposedtobeinvariantundergenerallineartrans-
`formations:
`(cid:20)xy(cid:21)=(cid:20)a
`a(cid:21)(cid:20)xy(cid:21)+(cid:20)b b(cid:21);
`a 
`()
`a
`whereA=(cid:20)a
`a(cid:21);b=(cid:20)b b(cid:21):
`a 
`()
`(b)
`(a)
`a
`Reiss[ ]hasrecentlyshownthattheseHuinvari-
`Figure:Zoningofgraylevelcharacterimages.
`antsareinfactincorrect,andprovidedcorrected
`(a)A(cid:2)gridsuperimposedonacharacterimage.
`expressionsforthem.
`(b)Theaveragegraylevelsineachzone,whichare
`GivenagrayscalesubimageZcontainingachar-
`usedasfeatures.
`actercandidate,theregularmoments[ ]oforder
`(p+q)arede(cid:12)nedas
`mpq=MXi= Z(xi;yi)(xi)p(yi)q;
`imagedatacompression"[ ].
`( )
`TheKLtransformhasbeenusedforobject
`recognitioninseveralapplicationdomains,forex-
`amplefacerecognition[ ].
`Itisalsoarealistic
`wherethesumistakenoveralltheMpixelsinthe
`alternativeforOCRongraylevelimageswithto-
`subimage.Thetranslation-invariantcentralmo-
`day'sfastcomputers.
`ments[ ]oforder(p+q)areobtainedbyplacing
`Thefeaturesextractedfromunitarytransforms
`theoriginatthecenterofgravity:
`arenotrotation-invariant,sotheinputcharacter
`(cid:22)pq=MXi= Z(xi;yi)(xi(cid:0)x)p(yi(cid:0)y)q;
`imageshavetoberotatedtoastandardorientation
`ifrotatedcharactersmayoccur.Further,theinput
`( )
`imageshavetobeofexactlythesamesize,soa
`scalingorre-samplingisnecessaryifthesizecan
`where
`vary.Theunitarytransformsarenotillumination
`invariant,butfortheFouriertransformedimage
`x=m m
`y=m m:
`;
`( )
`thevalueattheoriginisproportionaltotheaverage
`pixelvalueoftheinputimage,sothisfeaturecan
`Hu[ ]showedthat(cid:3)
`bedeletedtoobtainbrightnessinvariance.Forall
`unitarytransforms,aninversetransformexists,so
`(cid:22)pq
`(cid:23)pq=
`(cid:22)( +p+q);p+q(cid:21)
`( )
`theoriginalcharacterimagecanbereconstructed.
`arescale-invariant,where(cid:22)=(cid:22)=m.From
`.Zoning
`the(cid:23)pq's,rotation-invariantfeaturescanbecon-
`ThecommercialOCRsystembyCaleradescribed
`structed.Forexample,thesecond-orderinvariants
`inBokser[]useszoningonsolidbinarychar-
`are
`acters.Astraightforwardgeneralizationofthis
`(cid:30) =(cid:23)+(cid:23);
`( )
`methodtograylevelcharacterimagesisgivenhere.
`(cid:30)=((cid:23)(cid:0)(cid:23))+(cid:23) :
`Ann(cid:2)mgridissuperimposedonthecharacterim-
`( )
`age(Fig.(a)),andforeachofthen(cid:2)mzones,the
`averagegrayleveliscomputed(Fig.(b)),giving
`Invariantsforgenerallineartransformationsare
`afeaturevectoroflengthn(cid:2)m.However,these
`computedviarelativeinvariants[ , ].Relative
`featuresarenotilluminationinvariant.
`invariantssatisfyIj=jATjwjjJjkjIj;
`( )
`.GeometricMomentInvariants
`whereIjisafunctionofthemomentsintheorigi-
`Hu[ ]introducedtheuseofmomentinvariants
`nal(x;y)space,Ijisthesamefunctioncomputed
`asfeaturesforpatternrecognition.Hu'sabsolute
`fromthemomentsinthetransformed(x;y)space,
`orthogonalmomentinvariants(invarianttotrans-
`wjiscalledtheweightoftherelativeinvariant,jJj
`lation,scaleandrotation)havebeenextensively
`istheabsolutevalueoftheJacobianofthetrans-
`used(see,e.g.,[ ,, ,,]).Li[]listed
`posedtransformationmatrix,AT,andkjistheor-
`Huinvariants,ofordersto ,thataretranslation-
`derofIj.Notethatthetranslationvectorbdoes
`,scale-androtation-invariant.Belkasimetal.[ ]
`notappearinEq.( )asthecentralmomentsare
`listed Huinvariantsofordersto.However,
`(cid:3)NotethatEq.( )iswrittenwithatypographical
`Belkasimetal.identi(cid:12)edfewerinvariantsoforders
`tothanLi.
`errorinHu'spaper[ ].
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 6 of 24
`
`

`

`
`FeatureExtractionMethodsforCharacterRecognition|ASurvey
`I andI:y
`independentoftranslation.Togenerateabsolute
`invariants,thatis,invariants jsatisfying
`J =(cid:22)(cid:22)(cid:0)(cid:22) (cid:22) + (cid:22)
`( )
`j= j;
`J=(cid:22)(cid:22)(cid:22)(cid:0)(cid:22) (cid:22)(cid:22)
`
`( )
`(cid:0)(cid:22)(cid:22) (cid:0)(cid:22)(cid:22) (cid:0)(cid:22) :
`( )
`Reiss[ ]used,forlineartransformations,
`Asabove,theserelativeinvariantsmustbedi-
`videdby(cid:22)(cid:11)=(cid:22)w+ktoobtainabsoluteinvariants.
`jATj=Jand(cid:22)=jJj(cid:22);
`( )
`Regretfully,BamiehanddeFigueiredodividedJi
`by(cid:22)w(implicitlyusingk(cid:17)),sotheirinvariants
`where(cid:22)=(cid:22):
`areincorrecttoo.
`Ij=jJjwj+kjIj
`( )
`forwjeven,
`Reiss[ ,]alsogavefeaturesthatareinvari-
`antunderchangesincontrast,inadditiontobe-
`Ij=JjJjwj+kj(cid:0) Ij
`( )
`forwjodd.
`inginvariantundertranslationandgenerallinear
`transformations(includingscalechange,rotation
`Then,itcanbeshownthat
`andskew).Thethree(cid:12)rstfeaturesare
` j=Ij(cid:22)wj+kj
`(cid:18)=I (cid:22)I ,
`(cid:18) =I I I
`(cid:18) =I(cid:22)I,
`()
`( )
`isaninvariantifwjiseven,andj jjisaninvariant
`Experimentswithotherfeatureextractionmethods
`ifwjisodd.
`indicatethatatleast - featuresareneededfor
`Forgenerallineartransformations,Hu[ ]and
`asuccessfulOCRsystem.Moremomentinvariants
`Reiss[ ,]gavethefollowingrelativeinvariants
`( j'sand(cid:18)j's)basedonhigherordermomentsare
`thatarefunctionsofthesecond-andthird-order
`givenbyReiss[].
`centralmoments:
`.ZernikeMoments
`I =(cid:22)(cid:22)(cid:0)(cid:22)
`( )
`Zernikemomentshavebeenusedbyseveralau-
`I=((cid:22) (cid:22) (cid:0)(cid:22) (cid:22) )
`thorsforcharacterrecognitionofbinarysolidsym-
`(cid:0)((cid:22) (cid:22) (cid:0)(cid:22) )((cid:22) (cid:22) (cid:0)(cid:22) )
`()
`bols[ , , ].However,initialexperimentssug-
`I =(cid:22)((cid:22) (cid:22) (cid:0)(cid:22) )
`gestthattheyarewellsuitedforgray-scalechar-
`actersubimagesaswell.Bothrotation-variantand
`(cid:0)(cid:22) ((cid:22) (cid:22) (cid:0)(cid:22) (cid:22) )
`rotation-invariantfeaturescanbeextracted.Fea-
`+(cid:22)((cid:22) (cid:22) (cid:0)(cid:22) )
`( )
`turesinvarianttoilluminationneedtobedeveloped
`I=(cid:22) (cid:22) (cid:0)(cid:22) (cid:22) (cid:22) (cid:22)
`forthesefeaturestobereallyusefulforgraylevel
`+(cid:22) (cid:22) (cid:22)((cid:22) (cid:0)(cid:22)(cid:22))
`characterimages.
`KhotanzadandHong[ , ]usetheampli-
`+(cid:22) (cid:22) ((cid:22)(cid:22) (cid:22)(cid:0)(cid:22) )
`tudesoftheZernikemomentsasfeatures.Asetof
`+ (cid:22) (cid:22)(cid:22)(cid:0) (cid:22) (cid:22) (cid:22)(cid:22) (cid:22)
`complexorthogonalpolynomialsVnm(x;y)isused
`(Eqs. { )z.TheZernikemomentsareprojec-
`+(cid:22) (cid:22) (cid:22)((cid:22) (cid:0)(cid:22)(cid:22))
`+ (cid:22) (cid:22)(cid:22)
`tionsoftheinputimageontothespacespannedby
`theorthogonalV-functions.
`(cid:0)(cid:22) (cid:22) (cid:22) (cid:22)+(cid:22) (cid:22) 
`()
`Vnm(x;y)=Rnm(x;y)ejmtan(cid:0) yx;
`( )
`Reissfoundtheweightswjandorderskjtobe
`wherej=p(cid:0) ,n(cid:21),jmj(cid:20)n,n(cid:0)jmjiseven,
`andRnm(x;y)=n(cid:0)jmjXs=((cid:0) )s(x+y)n(cid:0)s(n(cid:0)s)!
`w =;w=;w =;w=;
`()
`k =;
`k=;k = ;
`k=:
`()
`s!(cid:0)n+jmj(cid:0)s(cid:1)!(cid:0)n(cid:0)jmj(cid:0)s(cid:1)!:( )
`Thenthefollowingfeaturesareinvariantun-
`dertranslationandgenerallineartransformations
`(givenbyReiss[ ]in andrediscoveredby
`Foradigitalimage,theZernikemomentoforder
`FlusserandSuk[,]in ):
`nandrepetitionmisgivenby
`Anm=n+ (cid:25)XxXyf(x;y)[Vnm(x;y)](cid:3);
`; =I(cid:22) ;
` =I (cid:22)
`( )
`()
` =I (cid:22)
`; =I(cid:22) :
`yAnincorrectversionofIisgiveninBamiehand
`()
`deFigueiredo'spaper[].
`zThereisanerrorin[ ]inequation( ):In[ ],
`Hu[ ]implicitlyusedk(cid:17) ,obtainingincor-
`thesummationistakenfroms=ton(cid:0)jmj,how-
`rectinvariants.
`ever,itmustbetakenfroms=ton(cid:0)jmj
`toavoid
`BamiehanddeFigueiredo[]havesuggested
`(cid:0)n(cid:0)jmj(cid:0)s(cid:1)becomingnegative.
`thefollowingtworelativeinvariantsinadditionto
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 7 of 24
`
`

`

`TRIER,JAIN,andTAXT
`
`Figure :ImagesderivedfromZernikemoments.Rows {:Inputimageofdigit`',andcontributions
`fromtheZernikemomentsoforder { .Theimagesarehistogramequalizedtohighlightthedetails.
`Rows {:Inputimageofdigit`',andimagesreconstructedfromtheZernikemomentsoforderupto
` { ,respectively.
`Figure :ImagesderivedfromZernikemoments.Rows {:Inputimageofdigit`',andcontributions
`fromtheZernikemomentsoforder { .Theimagesarehistogramequalizedtohighlightthedetails.
`Rows {:Inputimageofdigit`',andimagesreconstructedfromtheZernikemomentsoforderupto
` { ,respectively.AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 8 of 24
`
`

`

`
`FeatureExtractionMethodsforCharacterRecognition|ASurvey
`wherex+y(cid:20) ,andthesymbol(cid:3)denotesthe
`Methodsforsegmentingtouchingcharactersare
`complexconjugateoperator.Notethattheimage
`givenbyWestallandNarasimha[],Fujisawaet
`coordinatesmustbemappedtotherangeofthe
`al.[ ],andinsurveys[,].However,thesemeth-
`unitcircle,x+y(cid:20) .Thepartoftheoriginal
`odsassumethatthecharactersappearinthesame
`imageinsidetheunitcirclecanbereconstructed
`textstringandhaveknownorientation.Inhydro-
`withanarbitraryprecisionusing
`graphicmaps(Fig. ),forexample,somecharacters
`touchoroverlaplines,ortouchcharactersfroman-
`f(x;y)=limN! NXn=XmAnmVnm(x;y);
`othertextline.Trieretal.[]havedevelopeda
`( )
`methodbasedongrayscaletopographicanalysis
`[ ,],whichintegratesbinarizationandsegmen-
`tation.Thismethodgivesabetterperformance,
`wherethesecondsumistakenoveralljmj(cid:20)n;
`sinceinformationgainedinthetopographicanal-
`suchthatn(cid:0)jmjiseven.
`ysisstepisusedinsegmentingthebinaryimage.
`ThemagnitudesjAnmjarerotationinvariant.
`Thesegmentationstepalsohandlesrotatedchar-
`ToshowthecontributionoftheZernikemoment
`actersandtouchingcharactersfromdi(cid:11)erenttext
`ofordern,wehavecomputed
`strings.Thebinaryrasterrepresentationofacharacter
`jIn(x;y)j=(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)XmAnmVnm(x;y)(cid:12)(cid:12)(cid:12)(cid:12)(cid:12);
`isasimpli(cid:12)cationofthegrayscalerepresentation.
`( )
`TheimagefunctionZ(x;y)nowtakesontwovalues
`(say,and )insteadofthe,say,graylevelval-
`wherex+y(cid:20) ,jmj(cid:20)n,andn(cid:0)jmjiseven.
`ues.Thismeansthatallthemethodsdevelopedfor
`thegrayscalerepresentationareapplicabletothe
`TheimagesjIn(x;y)j,n= ;:::; ,forthe
`solidbinaryrasterrepresentationaswell.There-
`characters`'and`'(Figs. and )indicate
`fore,wewillnotrepeatthefulldescriptionofeach
`thattheextractedfeaturesareverydi(cid:11)erentfor
`method,butonlypointoutthesimpli(cid:12)cationinthe
`thethirdandhigherordermoments.Ordersone
`computationsinvolvedforeachfeatureextraction
`andtwoseemtorepresentorientation,width,and
`method.Generally,invariancetoilluminationisno
`height.However,reconstructionsofthesamedigits
`longerrelevant,buttheotherinvariancesare.
`(Figs. and )usingEq.( ),N= ;:::; ,indi-
`Asolidbinarycharactermaybeconvertedto
`catethatmomentsofordersupto{ areneeded
`otherrepresentations,suchastheoutercontourof
`toachieveareasonableappearance.
`thecharacter,thecontourpro(cid:12)les,orthecharac-
`Translation-andscale-invariancecanbeob-
`terskeleton,andfeaturesmaybeextractedfrom
`tainedbyshiftingandscalingtheimagepriorto
`eachoftheserepresentationsaswell.Forthepur-
`thecomputationoftheZernikemoments[ ].The
`poseofdesigningOCRsystems,thegoalofthese
`(cid:12)rst-orderregularmomentscanbeusedto(cid:12)ndthe
`conversionsistopreservetherelevantinformation
`imagecenterandthezerothordercentralmoment
`aboutthecharactershape,anddiscardsomeofthe
`givesasizeestimate.
`unnecessaryinformation.
`Belkasimetal.[ ,]usethefollowingaddi-
`Here,weonlypresentthemodi(cid:12)cationsofthe
`tionalfeatures
`methodspreviouslydescribedforthegrayscalerep-
`Bn;n+ =jAn(cid:0); jjAn jcos((cid:30)n(cid:0); (cid:0)(cid:30)n );( )
`resentation.Nochangesareneededforunitaryim-
`Bn;n+L=jAn jjAnLjpcos(p(cid:30)nL(cid:0)(cid:30)n )
`agetransformsandZernikemoments,exceptthat
`( )
`graylevelinvarianceisirrelevant.
`whereL= ;;:::;n,p= =L,and(cid:30)nmisthe
`phaseanglecomponentofAmnsothat
` . TemplateMatching
`( )
`Amn=jAmnjcos(cid:30)mn+jjAmnjsin(cid:30)mn:
`Inbinarytemplatematching,severalsimilarity
`measuresotherthanmeansquaredistanceand
`correlationhavebeensuggested[].Todetect
` FeaturesExtractedFromBinaryImages
`matches,letnijbethenumberofpixelpositions
`wherethetemplatepixelxisiandtheimagepixel
`Abinaryrasterimageisobtainedbyaglobalor
`yisj,withi;jf; g:
`locallyadaptivebinarization[ ]ofthegrayscale
`inputimage.Inmanycases,thesegmentationof
`nij=nXm= (cid:14)m(i;j)
`charactersisdonesimplybyisolatingconnected
`()
`components.However,fordi(cid:14)cultimages,some
`charactersmaytouchoroverlapeachotherorother
`printobjects.Anotherproblemoccurswhenchar-
`where(cid:14)m(i;j)=(cid:26)
`actersarefragmentedintotwoormoreconnected
`components.Thisproblemmaybealleviatedsome-
`if(xm=i)^(ym=j)
`( )
`whatbychoosingabetterlocallyadaptivebinariza-
`
`otherwise;
`tionmethod,butTrierandTaxt[ ]haveshown
`thateventhebestlocallyadaptivebinarization
`i;jf; g,andymandxmarethem-thpixelsof
`methodmaystillnotresultinperfectlyisolated
`thebinaryimagesYandXwhicharebeingcom-
`characters.
`pared.Tubbsevaluatedeightdistances,andfound
`AppearedinPatternRecognition,Vol. ,No.,pp. {, 
`
`SAMSUNG EXHIBIT 1008
`Page 9 of 24
`
`

`

`TRIER,JAIN,andTAXT
`
`theJaccarddistancedJandtheYuledistancedY
`tobethebest.dJ=
`n
`()
`n +n +n
`dY=n n(cid:0)n n
`( )
`n n+n n
`However,thelackofrobustnessregardingshape
`variationsmentionedinSectionforthegrayscale
`casestillapplies.Tubbs[]triestoovercomesome
`oftheseshortcomingsbyintroducingweightsfor
`thedi(cid:11)erentpixelpositionsm.Eq.()isreplaced
`by
`nij=nXm= pm(kji)(cid:14)m(i;j);
`()
`wherepm(kji)istheprobabilitythattheinputim-
`ageYmatchestemplateXk,giventhatpixelnum-
`Figure :Horizontalandverticalprojectionhis-
`berminthetemplateXkisi.pm(kji)isapproxi-
`tograms.
`matedasthenumberoftemplates(includingtem-
`plateXk)havingthesamepixelvalueatlocation
`mastemplateXk,dividedbythetotalnumberof
`wherenisthenumberofbins,andy andyare
`templates.
`thetwohistogramstobecompared.However,it
`However,wesuspectthattheextra(cid:13)exibility
`ismoremeaningfultocomparethecumulativehis-
`obtainedbyintroducingp(kji)isnotenoughto
`togramsY(xk),thesumofthek(cid:12)rstbins,
`copewithvariabilitiesincharactershapesthatmay
`occurinhand-printedcharactersandmulti-font
`Y(xk)=kXi= y(xi);
`machineprintedcharacters.Amorepromisingap-
`()
`proachistakenbyGaderetal.[]whouseasetof
`templatesforeachcharacterclass,andaprocedure
`forselectingtempla