Goal: Optical Character RecognitionTasks involvedSegmentationFeature Extraction: Why do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?Feature Extraction: How to do it ?ClassificationSoftware ImplementationSample session: Loading OCR packageSample session: Creating Training dataSample session: Creating Training dataSample session: Creating Training dataSample session: Extracting FeaturesSample session: Training MLPSample session: OCR new imageResultsResults: section of OCR'd imageResults: OCR resultsConclusionsOptical Character Recognition usingNeural NetworksDeepayan SarkarUniversity of Wisconsin – MadisonECE 539 Project, Fall 2003Goal: Optical Character RecognitionThe problem of OCR is fairly simple:•Input: scanned images of printed text•Output: Computer readable version of input contentsThere are several existing solutions to perform this task forEnglish text. The potential benefits of this approach is itsflexibility, since it makesno prior assumptions on the language ofthe text, and it should be possible to extend it to other alphabets.Tasks involvedFrom the computational point of view, there are three majortasks involved in our approach to performing OCR.•Segmentation Given input image, identify individual glyphs•Feature Extraction From each glyph image, extract featuresto be used as input of ANN. This is the most critical part of thisapproach, since it is not at all clear how this can be done• Classification Train the ANN using training sample. Then,given new glyph, classify it.SegmentationSegmentation is important in two phases of the process.•Obtaining training samplesThe easiest way to obtain training samples is to segment an image andask a human supervisor to classify each glyph• Recognizing new image after trainingAs a first step for trying to recognize a new input image, it must besegmented into glyphs. An additional requirement here is to obtain theglyphs incorrect order as well.To make this easier, the input image is first divided into linesand then segmented into glyphs (details in project report).Feature Extraction: Why do it ?• Segmented glyphs are binary image matrices (very highdimension)• MLP needs moderately low-dimensional input feature vectorUnfortunately, there is no obvious way to reduce the dimensional-ity in a way guaranteed to preserve the distinctiveness of glyphs.Feature Extraction: How to do it ?There is no single obvious choice of features. I decided to basemy features on identifiable regular parabolic curves in the image.Step 1: Obtain boundary of imageFrom image matrix, flag asboundary points backgroud pixels (0) in the image which haveat least one neighbour in the foreground (1)Feature Extraction: How to do it ?Step 2 Loop through each of these boundary points, and figureout the ‘best’ parabola passing through that point fitting theboundary locally. For each point, this involves• Decide the ‘orientation’ of the boundary at that point byfitting a straight line through points in a small neighbourhoodof that point.Feature Extraction: How to do it ?Step 2 Loop through each of these boundary points, and figureout the ‘best’ parabola passing through that point fitting theboundary locally. For each point, this involves• Rotate the image by an angle to make this line horizontal,and fit a quadratic regression line to the previously identifiedneighbouring points.Feature Extraction: How to do it ?Step 2 Loop through each of these boundary points, and figureout the ‘best’ parabola passing through that point fitting theboundary locally. For each point, this involves• Determine points in the boundary that are ‘close’ to thisfitted quadratic curve (using a predetermined threshold).• Update the quadratic curve by refitting it using all the pointsthus identified.• Repeat this update using ‘close’ points 2 more times.Feature Extraction: How to do it ?Hope that the curve thus identified closely approximates thecurvature of the boundary at that point. Note that it is perfectlyall right if this doesn’t work as expected for all points, since forpoints common to a single curve, it is enough that this worksfor at least some of these points.Feature Extraction: How to do it ?Step 3: Identify ‘strongest’ curve Determine the three curvesthat are the ‘strongest’ in terms of how many points are ‘close’to those curves. To do this,• order the points by the number of other boundary points‘close’ to the best curve through that point• record the angle of rotation and the quadratic coefficientof the curve as features (the linear coefficient is close to 0because of the rotation)Feature Extraction: How to do it ?Step 3: Identify ‘strongest’ curve Determine the three curvesthat are the ‘strongest’ in terms of how many points are ‘close’to those curves. To do this,• We don’t want the same curve to be identified again, sowe leave out all points identified as being ‘close’ to the firstcurve, and re-evaluate the ‘strengths’ of the remaining pointsbased on the remaining points. Again choose the best curveand record the angle of rotation and the quadratic coefficient• Repeat this once more to get a total of 6 featuresFeature Extraction: How to do it ?Step 4: Finally, add the aspect ratio (width/height) of glyph asanother feature, making a total of 7ClassificationOnce the features are extracted, we can go ahead and train aneural network using the training data for which we already knowthe true classes. After training, recognizing a new scanned imageinvolves• reading in the image• segmenting the image into lines• segmenting each line into glyphs• classify each glyph by extracting the feature set and usingthe already trained neural network to predict its classSoftware ImplementationImplemented as an add-on package for a MATLAB-like program-ming environment called R (http://www.r-project.org). R is• Popular among statisticians(like me :-))• Open source, freely downloadable• Runs on Linux, UNIX, Mac, WindowsSample session: Loading OCR packageOnce R is started, the OCR package can be loaded by> library(rocr)Sample session: Creating Training dataA new collection of glyphs for training can be created, or anexisting one updated, by calling> updateTrainingSet(imagefile, datafile =
View Full Document
Unlocking...