DOC PREVIEW
UCSD CSE 190 - Recognition of Handwritten Names

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Recognition of Handwritten NamesDafna BittonDepartment of Computer ScienceUniversity of California, San [email protected] character recognition (OCR) is an important problem that has many ap-plications. It has been widely studied and in many cases solved. We propose anoffline method using a Hidden Markov Model (HMM) to take in as input an imageof a handwritten name and output the corresponding name from a given lexicon.1 IntroductionClass sizes at universities can be in the hundreds. The process of returning graded work to studentscan be time consuming and tedious. In order to avoid this process, we propose a method to returnwork to students online. This process provides feedback to students when it is available to themand avoids manual return of papers in class. The course staff will need to scan in all of the gradedhomework and tests, which can be automated, and label each document with the correspondingstudents’ name. The laborious part of this process is labeling the documents with the students’names. We propose a method to automate this process by performing OCR on the name and usingan HMM to determine which document belongs to which student.Our idea originated from Jaety Edwards and David Forsyth [1] who proposed a method to use anHMM to transcribe a handwritten script. Their work focuses on finding where the characters aresegmented and then transcribing the letters, using minimal training data.2 Our MethodIn order to simplify the process of finding and isolating the characters from the students’ names,we provide character boxes for the students to enter their names, with one character for each box.Figure 1 is what a cropped input image looks like.Figure 1: An example of a cropped quizIf the length of a student’s name exceeds the amount of character boxes available, we will just workwith what can fit in the character boxes provided. We provide 20 character boxes and hypothesizethat the first 20 characters are distinct enough to identify the students.Since we introduce character boxes, we need a mechanism for finding them. We run a linedetection algorithm, called the Hough transform, on the input image where we expect the nameto be, and infer where the character boxes are. We use prior knowledge that the lines from thecharacter boxes are either horizontal or vertical and take the following steps:1. Take the gradient of the input image.2. Run a variation of Canny edge detection (edge.m in Matlab) on the vertical gradient of theimage.3. Run the Hough transform on the result of the edge detection and find the top two linesdetected. From this infer where the horizontal character box lines are.4. Run a variation of Canny edge detection (edge.m in Matlab) on the horizontal gradient ofthe image.5. Run the Hough transform on the result of the edge detection and find the top lines detected.Infer where the 21 vertical lines of the character boxes are.6. Cut out each character.200 400 600 800 1000 1200Figure 2: An example of the character box lines that were detectedThe red lines in Figure 2 are the lines that were detected as a result of the steps taken above. Sincethe detected character box lines are often not exact, as in Figure 2, and the character box lines havea width, the cut out characters often have extra junk around the edges that needs to be removed.20 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 402040608020 4020406080Figure 3: An example of extra junk around the edges of the cut out charactersIn order to remove these extra lines, we expand a rectangle from the center of the characterimage until an optimal image is reached. We then center and scale the character image.10203040502040608010203040502040608020 402040608020 402040608020 40204060801020304050204060800 0.5 100.5120 402040608010010203020406020 402040608020 40204060801000 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.510 0.5 100.51Figure 4: The character boxes after the extra lines have been removedWe used the ABCDETC dataset from NEC Labs as training data. NEC Labs had individuals fillout sheets with space for 5 examples of each character. We used 18 such sheets; in total we had 90examples of each character a-z. We again used the Hough Transform to find the character boxesand cut out each training letter.Figure 5: An example of a completed sheet from NEC Labs3 The ModelWe used an HMM where the hidden states were the true ASCII representation of the characters andthe observations were the images of the characters. The transition probabilities we calculated fromthe class roster using a bi-gram model with the following equation:P (ct|ct−1) =Count(ct−1, ct)Count(ct−1)Where Count(ct) is the number of times character ctappears in the roster and Count(ct−1, ct) is thenumber of times the sequence ct−1, ctappears in the roster.The emission probabilities are supposed to be the probability of a character looking a certainway. For example, the probability of seeing some character image given that you know it is of an’a’. Instead of calculating this, for each character image we find the top 10 nearest neighbors fromthe training data. We then say that the probability that this character image is a particular characteris the number of votes for this character + 1 divided by 10 + 26. We add 1 to each vote tally becausethe nearest neighbor algorithm in this case is very flawed and cannot be trusted. We don’t want acharacter to not be considered just because it had no votes.With this framework in place we run the Viterbi algorithm to find the most likely sequenceof hidden states that produced the observations (character images). We then take this sequence ofcharacters we believe to be the truthful name and run nearest neighbor on it against all of the namesin the class roster. This way we guarantee that our guess of the name is actually in the roster. We alsorequire that the name that is returned as the nearest neighbor have the same length as the query name.4 ExperimentsWe had a test set with 12 different names, where each name was between length 9 and length 14,inclusive. 10 of the 12 names were classified correctly using our algorithm. The results would nothave been quite as good had all of the names in the test set been the same length. This is becausein


View Full Document

UCSD CSE 190 - Recognition of Handwritten Names

Documents in this Course
Tripwire

Tripwire

18 pages

Lecture

Lecture

36 pages

Load more
Download Recognition of Handwritten Names
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recognition of Handwritten Names and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recognition of Handwritten Names 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?