UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An expert system for the recognition of general symbols Ahmed, Maher M. 1999

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1999-463079.pdf [ 7.27MB ]
Metadata
JSON: 831-1.0065333.json
JSON-LD: 831-1.0065333-ld.json
RDF/XML (Pretty): 831-1.0065333-rdf.xml
RDF/JSON: 831-1.0065333-rdf.json
Turtle: 831-1.0065333-turtle.txt
N-Triples: 831-1.0065333-rdf-ntriples.txt
Original Record: 831-1.0065333-source.json
Full Text
831-1.0065333-fulltext.txt
Citation
831-1.0065333.ris

Full Text

An Expert System for the Recognition of General Symbols by Maher M . Ahmed M . Sc., Queen's University, 1994 M . Sc., Cairo University, 1988 B. Sc., Cairo University, 1984  A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E D E G R E E O F DOCTOR O F PHILOSOPHY in T H E F A C U L T Y O F G R A D U A T E STUDIES DEPARTMENT OFELECTRICAL AND COMPUTER  ENGINEERING  We accept this thesis as conforming to the required standard  THE UNIVERSITY OF BRITISH COLUMBIA © Maher M. Ahmed, 1999  In  presenting  degree  this  thesis  at the University  in partial  of this thesis  department publication  or  by  of this  and study.  thesis  the  requirements  I further agree that  for scholarly purposes  his  of  of  or  her  may b e granted  representatives.  It  is  by the head  understood  for financial gain shall not be allowed  C M y ^ l  «»ci  The University of British Columbia Vancouver, Canada Date  DE-6 (2/88)  O C J 4-j  l°v°v°\  advanced  permission for extensive  permission.  Department  for an  of British Columbia, I agree that the Library shall make it  freely available for reference copying  fulfilment  Co* fr* r  £  w  3  W  f  l  r  l  ^  that  without  of my  copying  or  my written  Abstract This thesis addresses the problem of automatic recognition of any hand written symbol. The number of different styles of handwritten symbols demonstrates the difficulties that an automatic recognizer must cope with. For example, Some handwritten styles of capital  A letters are: The main technical approaches for solving the problems in recognizing patterns are statistical pattern recognition and structural pattern recognition. Statistical pattern recognition systems use pixel-features for recognition. Some of these features are moments, histograms, Fourier transforms, and the percentage of ink pixels in different zones. Although statistical pattern recognition techniques, including Artificial Neural Networks (ANNs), carry a high recognition rate, there are some disadvantages that are in these systems. Disadvantages include the requirements of a very large number of training data, and the inability to justify its answer. In addition, the output is only a classification and not a description of the actual pattern. As opposed to statistical pattern recognition techniques, structural pattern recognition techniques extract commonly used descriptions of the patterns (structural-features). These features include loops, end points, and arcs. After extracting these similarities, the system then finds the common relationships among these structural-features (descriptions). In this research, the structural pattern recognition approach was used for developing an expert system that extracts structural-features (descriptions) from the symbol at each stage of recognition. The developed system enabled us to automatically recognize handwritten symbols, assuming that the symbols are in their isolated forms. This system is unique in that it is not limited for a specific application, but it can be used to recognize any general symbol of any language. To obtain a representation of a symbol the system performs four basic steps. First, the system adjusts the symbol by rotating it around its central point until its principal axis aligns with the vertical axis or having a multiple of 20° to the vertical axis. Second, the system scales the symbol to a predefined size. The third step is to thin the symbol. A novel rule-based system for thinning is developed in this research. The resultant thinned image is composed of the central lines of the image. Finally, the last step involves extracting and describing the thinned symbol in terms of strokes. These strokes will be approximated by a set of line segments. The resulting representation of the symbol is compared with different stored models of the different symbols in the system knowledge base. For each symbol many models are  stored. The results of our system depend on a certain threshold. Using a low threshold will decrease the space for this symbol, increase the rejection rate and increase the recognition rate. The system was tested with 5726 handwritten English characters. When the system learned an average of 97 models per symbol and used a low threshold, the recognition rate was 95% and the rejection rate was 16.1%. The tested data were all test data (binary data) taken from the Center of Excellence for Document Analysis and Recognition ( C E D A R ) database. When the threshold is 100, the recognition rate was 87.6% and the rejection rate was 0%. The recognition rate of our system can be increased by storing more models for each symbol or by increasing the rejection rate. The system is capable of learning new symbols by simply adding models for these symbols to the system knowledge base. The system is implemented using C++ running on a 120 M H z Pentium P C .  in  Table of Contents Abstract Table of Contents List of Tables List of Figures Chapter 1 Introduction 1.1 Motivation 1.2 Problem Definition 1.3 Applications 1.4 Thesis Objective 1.5 Recognition Methods 1.6 Contributions 1.7 Thesis Overview Chapter 2 Literature Overview 2.1 Introduction : 2.2 Different Pattern Recognition Tools 2.2.1 Expert Systems 2.2.2 Artificial Neural Networks 2.3 The Main Pattern Recognition Techniques 2.3.1 Statistical Pattern Recognition 2.3.2 Structural Pattern Recognition 2.4 Preprocessing 2.4.1 Thresholding 2.4.2 Noise 2.4.3 Overlapping 2.4.4 Rotation and Slant Correction 2.4.5 Segmentation 2.5 Postal code and Address Recognition 2.6 Summary Chapter 3 Thinning 3.1 Introduction 3.1 Thinning Algorithms Survey 3.2 Good Thinning Characteristics 3.3 The Central Line Thinning Rule-Based System 3.4 Edge Detection One-Pass Sequential Thinning 3.4.1 System Performance 3.4.2 Explanation of the Rules 3.5 Results 3.6 A Combined Thinning Method 3.7 The Speed of the Developed Thinning Algorithm 3.8 Summary Chapter 4 The Developed System 4.1 Introduction 4.2 The Developed System 4.2.1 The Rotation Stage a) The Central Point b) The Principal Axis 4.2.2 The Scaling Algorithm 4.2.3 The Thinning Algorithm 4.2.4 Symbols Representation  '•  •  ii iv vi vn 1 1 1 1 4 6 6 8 8 10 10 10 11 11 12 18 19 32 37 37 37 38 40 41 42 43 45 45 45 45 49 49 59 60 62 64 65 ••••• 68 69 70 70 70 71 74 74 74 74 77 78  iv  4.2.5 The System Mapping Rules 4.2.6 The System Models and Recognition 4.3. Results 4.4 The System's Execution Time 4.5 The Program Description 4.6 The System's Limitations and Future Work 4.7 Recognition Rate and The Number of Models 4.8 System Characteristics 4.9 Summary Chapter 5 Conclusion 5.1 Statistical versus Structural Pattern Recognition 5.2 System Characteristics 5.3 System Limitations 5.4 Contributions 5.5 Future Research References Appendix 1 The System Models Appendix II Symbols Before and After Recognition  80 82 86 91 92 95 96 98 101 103 103 103 103 104 104 105 106 112 112 125 125  v  List of Tables Table 1. The number of misrecognized symbols (handwritten English letters) for each method 32 Table 2 Thinning speed versus the maximum thickness of a symbol in a document of size 480 x 576 pixels. 68  Table 3 The accuracy obtained for each symbol and the number of test symbols Table 4 The accuracy obtained for each symbol and the number of test symbols Table 5 The error rate versus the rejection rate Table 6 Recognition rate in percentage versus the number of models for the letter 'A' when symbol rejection is not allowed Table 7 Recognition rate in percentage versus the number of models for the letter 'A' when symbol rejection is allowed Table 8 The percentage of the recognition rate versus the number of models for the digits when symbol rejection is not allowed Table 9 The percentage of the recognition rate versus the number of models for the digits when symbol rejection is allowed  87 88 88 97 97 97 97  vi  List of Figures Figure 1 Linearly separated classes Figure 2 Non-linearly separable classes Figure 3 An example of a digit written in 7x5 pixels Figure 4 An example of a 3-layer ANNs Percptron for digit recognition Figure 5 The symbol is divided into 16 regions Figure 6 Vertical and horizontal histogram distributions of the symbol are divided into 16 slots Figure 7 A symbol before thinning (a) and after thinning (b) Figure 8 An example of a transformational grammar Figure 9 An example of context sensitive grammar Figure 10 two overlapped objects and their distance transform  13 14 15 15 26 28 29 33 33 39  o Figure 11 The thinning rules with 0 = 0 Figure 12 The special case conditions relevant to 2-pixels thickness lines Figure 13 The original symbols  50 51 51  Figure 14 Thinning by applying the 16 rules with 0 = 0  52  o o Figure 15 Thinning by applying the 16 rules with 9 = 90 o Figure 16 Thinning by applying the 16 rules with 0 = 180 o  52 53  Figure 17 Thinning by applying the 16 rules with 0 = 270  0  0  o  53  Figure 18 Thinning by applying 4 passes (16 rules in each pass) with 9 = 90 ,180 , and 270 in second, third, and fourth pass, the 4 passes are repeated in each iteration 54 Figure 19 Thinning by applying 16X4 rules in each iteration without testing for the special cases of 2-pixels thickness lines 55 Figure 20 Thinning by using our new developed system which uses a parallel one-pass 16X4 rules and testing for the special cases of 2-pixels thickness lines 56 Figure 21 Step by step thinning 58 Figure 22 Thinning by using the ZS method 59 Figure 23 Thinning: (a) an image, (b) by applying the ZS method, and (c) by applying our developed parallel one-pass 16X4 rules 59 Figure 24 Different symbols 60 Figure 25 Symbols processed from left to right going from top to bottom and concerning: (a) a large number of branches, (b) a medium number of branches and (c) a small number of branches 61 Figure 26 Symbols processed from right to left going from top to bottom and concerning: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches 61 Figure 27 Symbols processed from left to right going from bottom to top and concerning: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches 61 Figure 28 Symbols processed from right to left going from bottom to top: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches 61 Figure 29 The sequential thinning rules 62 Figure 30 A document that has Arabic, English, and Chinese characters 65 Figure 31 (a) The document after thinning using the developed one-pass 16x4 rules parallel method, (b) part of the image is enlarged 66 Figure 32 (a) The document shown in Figure 31 after removing the extraneous pixels by applying the onepass sequential thinning algorithm, (b) part of the image is enlarged 67 Figure 33 Thinning of symbols that have different thickness 68 Figure 34 The 16 possible images in a zone of 10 xlO pixels 72 Figure 35 The structural pattern recognition steps 73 Figure 36 A symbol after scaling to different dimensions and using a scaling threshold = 0.2: (a) the original symbol, (b) 32X32 size, (c) 48X32 size, (d) 24X16 size, (e) 8X8 size, and (0 8X4 size 77 Figure 37 Scaling a symbol with different scaling threshold values and using 32x32 size: (a) the original symbol, (b) threshold = 0, (c) threshold = 0.2, (d) threshold = 0.4, (e) threshold = 0.6, (f) threshold = 0.8, and (g) threshold = 1.0 77 Figure 38 The different direction possibilities 78  vii  Figure 39 Processing of a symbol: (a) A symbol, (b) after rotation, (c) after scaling, (d) after thinning, (e) after marking the special pixels, and (f) after isolating the symbol strokes and coding each pixel 79 Figure 40 Different mappings of a symbol by using different segment lengths of: (a) 1-pixel, (b) 2-pixels, (c) 3-pixels, (d) 4-pixels, (e) 5 pixels, (f) 6-pixels, (g) 7-pixels, (h) 8-pixels, (i) 9-pixels, and (j) 10 pixels 80 Figure 41 Some models used by the system and the number of models used for each of these symbols 84 Figure 42 Some models used by the system for the letter A 86 Figure 43 A document processing 91 Figure 44 Recognition rate in percentage versus the number of models for the letter 'A' when symbol rejection is not allowed 97 Figure 45 Recognition rate in percentage versus the number of models for the letter 'A' when symbol rejection is allowed 97 Figure 46 The number of allowed symbols and the number of possible symbols versus the number of zones 99 Figure 47 Example of different symbols 99 Figure 48 The symbols after thinning 100 Figure 49 The symbols after thinning and removing the extraneous pixels 100 Figure 50 The processing time for extracting and coding the strokes of the symbols versus the number of strokes 100 Figure 51 The time required to convert the strokes of the eight symbols shown in Fig 47 versus the line segments 101  viii  Acknowledgements First and foremost, I would like to thank God for His everlasting mercy & compassion. I would like to take this opportunity to thank the many people who have helped me in big and small ways in the preparation of this thesis. I would like to acknowledge Dr. Rabab Ward for her invaluable comments and support during the course of this thesis. She has provided me with priceless suggestions and ideas that contributed a great deal in developing this thesis. She has given me her constant support and encouragement throughout the course of this thesis. Finally, I owe my parents a debt of appreciation that I will never be able to repay.  IX  Chapter 1 Introduction 1.1 Motivation It is  necessary  to develop  representational  and computational  automatic processing of a variety of symbols.  techniques  Such symbols  for  the  are widely used in  documents to communicate information including letters, digits and diagrams. Automated symbol recognition and understanding have great economical relevance, as evidenced by the  high  industry participation in many  recognition.  An  (1)  important  pattern  conferences  recognition  on  document  application  is  the  analysis  and  postal  code  recognition. ' Understanding a general symbol involves two activities: symbol recognition and symbol arrangement  analysis.  The  current  research  focuses  on  the  development  and  implementation of a system that can recognize any handwritten symbol. Examples of these symbols  are digits, characters, electrical  circuit symbols,  and mathematical  symbols.  In addition to the obvious advantage of such research, it will provide us with a machine to assist visually disabled individuals. The research is also valuable for converting a handwritten document into a clearer typed one.  1.2 Problem Definition Character Recognition or Optical Character Recognition ( O C R ) is the process  of  converting scanned images of machine printed or handwritten text (digits, letters, and symbols) into a computer processed format (such as ASCII).  There are two main pattern recognition problems: on-line and off-line pattern recognition depending on whether the characters are written before or during the recognition process. O C R falls under the off-line pattern recognition category.  1  The objective of on-line handwriting recognition is to recognize the symbols while they are being written. Such systems should be fast enough to keep up with the writing speed. A survey of a state of the art of on-line handwriting recognition is described by Tappert et al.  ( 3 )  Generally, each symbol consists of one or more strokes. A stroke is defined as the  writing from pen down to pen up.  The features in on-line pattern recognition might be based on the static as well as the dynamic properties of a character. A decision tree can be used to classify characters. For example, characters f, g, j , p, q, y, and z all have a descender. However, j is the only character that is associated with a dot. Other features include time sequence of zones, directions, extremes and curves. Curve fitting (as a function of time) is used for matching two symbols. Stroke codes are used to classify sub-parts of a character. The whole character is classified based on a unique sequence of classified sub-parts. Markov models are suitable for dynamic information. A first order Markov model uses eight states corresponding to  eight pen-tip  directions.  A n example  of  automatic  recognition of unconstrained on-line handwritten text by using hidden Markov models is described by Nathen et a l .  <4)  Off-line handwriting recognition is performed after writing is completed, typically on scanner images. Off-line data captures is the process that occurs when the data is captured some time after the writing is done. A survey of the state of the art of off-line character recognition (for Arabic) is provided by A m i n e .  (5)  On-line recognition has the following characteristics as opposed to off-line recognition:  •  It captures dynamic information of the writing process such as pen velocity, pressure,  and pen direction (up or down).  •  It uses a one-dimensional string of data and not a two-dimensional image as in the  case for off-line recognition.  2  •  The writing order of points is available.  •  The writing line has no width.  •  There is very little noise and no background to remove.  In This research, we are interested in studying off-line recognition of isolated symbols. Digital images consist of a set of pixels arranged in a two dimensional array. Each pixel has a value that represents the brightness or the color at this point of the image. Digital images are approximations of the scene being represented. The number of pixels reflects its resolution and the number of levels is called quantization. Bi-level images contain pixels with only two grey values: 1 (black) and 0 (white). Images in which the important information consists of lines are called bi-level line images. The lines' directions, lengths and the relationships among them contain the vital information in these images. Examples of line images are text, maps, graphs, charts, signatures and fingerprints. In these images, the geometry of the objects in the image conveys the information and not the relationship between the pixel grey levels (these grey levels are important in pictures). In this research, we are interested in analyzing bi-level line images.  Typical input to a recognizer system is a binary image (in a bit map ".bmp" format). Generally, these images are produced by compressing the range of grey levels to two levels. A binary image can be obtained by optically scanning a typical document page or by use of a camera. A typical scanning resolution that is suitable for text recognition is 300 dots per inch (DPI).  Recognition of unconstrained handwritten text can be difficult because of the large number of different styles of symbols. Some handwritten styles of capital A letters are  I. Characters may not be reliably isolated especially when  3  the  text  is  handwritten  cursively  Problems also arise from noise  I.  Other  as  for  example  Bi  problems  arise  , slant  from  and rotations  symbols  as well as discontinuous ones I  that  are  overlapped  I. Another problem is the  presence of graphics within the document. Thus, image separation from text may be useful in speeding up the process of recognition. Some characters and digits may look alike. Examples of these characters are {V,U}, {C,L}, {Z,2}, {n,h}, {1,1}, {S,5}, and {0,O}. The context sometimes provides the necessary information to distinguish between them.  There are some similarities between symbols and sentences. A sentence or a symbol consists of primitives. Examples of these primitives in a sentence include a verb, noun, subject and object. In a symbol, these primitives include an upper stroke, a left curve and a circle. A n y sentence or symbol has rules that determine the right place of each primitive. M y research concentrates on the recognition of general symbols by using models for these symbols.  1.3 Applications Hundreds of O C R systems have been  developed  since  the  1950s and some are  commercially available today. Most of the commercial O C R systems are  task-specific  readers. A task-specific reader handles only specific document types. High performance reading machines are described by S.N. Srihari.  (6)  Some of the most common task-  specific readers are:  4  •  Mail sorter: postal codes and addresses in mail.  •  Data entered in forms, e.g., tax forms, job applications.  •  Bills.  •  Bank cheques.  •  Detecting forged signatures.  •  Airline passenger tickets.  •  Passports.  These readers usually utilize custom-made image lift hardware that captures only a few predefined document regions. For example, a bank cheque reader may just scan the currency amount field and a postal O C R system may just scan the address block on a mail piece. Such systems emphasize high throughput rates and low error rates. The character recognizer in many task-specific readers is able to recognize machine-printed text and hand-printed text.  Many character recognizers are based on mathematical formalisms that minimize a measure  of  misclassification.  Artificial  neural  networks  employ  mathematical  minimization techniques and are used in commercial O C R systems. Recognition rates for machine-printed characters can reach over 99%, but handwritten character recognition rates are typically lower because every person writes differently, as reported by S. L a m in the Center of Excellence for Document Analysis and Recognition, State University of New York at Buffalo. A N N s have a type of error that is based on training with an inappropriate data, which is difficult to overcome.  Other more general systems capture an image of a document page and separate the page into text regions and non-text regions.  (7)  Non-text regions such as graphics and line  drawings are often saved separately from the text and associated recognition results. Text regions are segmented into lines, words, and characters and the characters are passed to  5  the recognizer. Recognition results are in a format that can be processed  by the  application software.  1.4 Thesis Objective There are many implemented systems for pattern recognition. Each system addresses one specific  language  or symbol  set  (e.g., English,  Arabic  or Chinese characters or  mathematical, musical or electrical symbols).  The purpose of this research is to develop a system that can recognize any general symbol by accessing the appropriate database models and using only one algorithm. Examples of these symbols are characters in any language, mathematical symbols or electrical circuit symbols.  The author uses structural pattern recognition techniques. Some symbols are described in the system knowledge base. Structural descriptions of symbols can be formulated by a set of rules. Hence, the suggested tool to implement this technique is an expert system.  (8)  Expert systems are used efficiently in many applications. The advantages of using expert systems (also known as rule-based systems) are their modularity and inference capability. The algorithm is independent from the database. The database contains rules. There could be more than one database. Each database  has rules that are suitable for certain  applications. The rules can be easily modified, deleted or added.  Expert systems can be easily implemented by using the P R O L O G language.  (9)  Examples  of expert systems previously implemented by the author are: an expert system for teaching students electrical circuits sentences.* ' 11  (l0)  and expert systems for understanding Arabic  12)  1.5 Recognition Methods Many algorithms and techniques are useful in analyzing document images. These include noise  filtering,  thinning,  line  detection,  segmentation,  feature  recognition  and  classification, pattern matching and semantic interpretations.  6  O C R is the process of converting scanned images of machine printed or handwritten text into a computer processed format (such as ASCII). The techniques for solving the O C R problems fall under two main approaches: statistical pattern recognition and structural pattern recognition.  Statistical  pattern recognition  systems use  some pixel-features  for  recognition.  (13)  Examples of these features include: moments, histograms, Fourier transforms, and the percentage of ink pixels in different zones. These systems have an upper limit of recognition rate determined by Bayes decision theory. Bayes theory minimizes the probability of error and determines the best boundary regions for each class in the feature space.  Statistical pattern recognition techniques, including Artificial Neural Networks (ANNs), have the following disadvantages: the requirement of a large number of training data and the inability of justifying the answer. In addition, the output is only a classification and not a description of the pattern.  A N N s have been used successfully for extracting and clustering symbol features. These networks are composed of several layers of interconnected elements. Each element (neuron) computes a weighted sum of its inputs and transforms it into an output using a nonlinear function. In the learning phase, the weight of each connection is modified until the desired outputs are obtained. A N N s have the disadvantage of requiring retraining (or redesigning the system) every time a new symbol is introduced to the system. A s for example, if a neural network is constructed for recognition of the digits 0 to 9, then it is very difficult to modify it to make it capable of recognizing letters. There is no guarantee of a certain recognition rate for any statistical pattern recognition method.  Structural pattern recognition techniques (descriptions)  of the patterns  extract commonly used structural features  such as loops, end points,  relationships among these descriptions.  (l4)  and arcs, then find  the  Structural pattern recognition techniques can  justify the answer similar to human reasoning by listing the reasons of why the symbol is recognized as such. Although they have a better recognition rate estimate, they are usually slower than statistical pattern recognition systems.  7  1.6 Contributions In  this research, the  author used  the  structural pattern recognition  developing an expert system for symbol recognition/  15)  approach for  The system extracts descriptions  from the symbol at each stage of the recognition. The system maps similar handwritten symbols to the same representation. The proposed system is not designed for a specific application but can be used for general symbol recognition. The system uses the structural pattern recognition technique for modeling symbols by a set of short straight lines (line segments). The system performs four basic steps before modeling the symbol. First, the system adjusts the symbol by rotating it around its central point (Cr, Cc) (where C r = 1/n X x, C c = 1/n £ y for an n x n image) until its principal axis aligns at a certain 0  o  angle with the vertical axis (0 or having a multiple of 20 ). Second, the system scales the symbol to a predefined size (selected by the user or calculated by the program). Third, thinning is performed. Thinning is accomplished by using a novel thinning algorithm developed by the author and R. Ward.  ( 1 6  '  l 7 )  After that, the system extracts and describes  the thinned symbol in terms of strokes. Finally, each stroke is approximated by a set of line segments. Analysis  and results  for the  recognition  of  a document  that has  5762  different  handwritten symbols are described. The tested data are all binary test data taken from the Center of Excellence for Document Analysis and Recognition ( C E D A R ) database. When the system has stored some models for each symbol (an average of 97 models/symbol), the recognition rate is 95% and the rejection rate is 16.1%. Storing more models will increase the recognition rate. The recognition rate can also be increased by increasing the rejection rate. The system is capable of learning new symbols by simply adding their models to the system knowledge base. The system is implemented using C++ running on a 120 M H z Pentium P C .  1.7 Thesis Overview The thesis consists of five chapters. The first chapter is an introduction. Chapter two presents an overview of different algorithms and techniques for symbol analysis and  8  recognition. Chapter three provides a study of various existing thinning algorithms as well as two novel thinning systems that were developed as a result of this research. Chapter four describes the details of the developed symbol recognition system and results. Finally, chapter five offers the conclusions and suggestions for future work.  9  Chapter 2 Literature Overview 2.1 Introduction The study of machine simulation of human understanding of images has been attracting researchers as early as 1929 images  and characters  The aim is to develop methods for computers to interpret  in particular. Character Recognition  or Optical Character  Recognition ( O C R ) is the process of converting scanned images of machine printed or handwritten text (digits, letters, and symbols) into a computer processed format (such as ASCII). Computer images are bi-level images, multi grey-level or coloured images. They can be stored in different formats. These formats include J P E G (Joint Photographic Experts Group), G I F (Graphics Interchange Format), T I F F (Tagged Image File Format), P B M (Portable Bit Maps), P P M (Portable Pix Maps), and P G M (Portable Gray Maps).  Different tools are used to implement pattern recognition systems. Recent tools for solving the pattern recognition problems include expert systems and Artificial Neural Networks (ANNs).  Different methods are used to recognize characters. Pattern recognition techniques fall under  two  main  categories:  statistical  pattern  recognition  and  structural pattern  recognition.  Pattern recognition methods typically have problems with eliminating noise from images, as well as segmenting connected and overlapped symbols. Noise reduction may be achieved by simply applying suitable filters to the original image. Segmentation on the other hand is an open problem and an active area of current research. Segmentation, technically speaking, is the breaking up of an image into meaningful sub-images or primitives. Segmentation can be used, as a preprocessing step, for example, for breaking up a connected word into its characters, or a human face into its parts (mouth, nose, etc).  10  In this research, an expert system (or a rule-based system) is used to solve the off-line symbol recognition problems. Structural pattern recognition techniques are utilized. Also, the image is assumed to be a noise-free bi-level image and to contain only isolated handwritten symbols.  2.2 Different Pattern Recognition Tools 2.2.1 Expert Systems Expert systems are suitable for solving pattern recognition problems.  <8)  They have the  advantages of flexibility and modularity. Knowledge is distributed over rules which are independent of each other. A n expert system is a computer program that performs a specific task normally carried out by a human expert. The system should be able to draw conclusions without examining all possible solutions. The system should learn and use new knowledge efficiently. The system should be able to interact with the user and show how the conclusion was reached.  Expert systems have the ability to manipulate problem statements and integrate relevant pieces of knowledge from the knowledge base using heuristic techniques. Expert systems are problem-solving programs that use their knowledge in flexible ways. Expert systems can reason with inexact knowledge which might be declarative or procedural. Expert systems could learn by being told, by induction from examples, by parameter adjustment, or by observation and discovery. Expert systems are only appropriate for situations when the human expertise can be written explicitly in a formal language. Applications not suitable for expert systems are those that are deterministic such as solving a quadratic equation. Expert systems should perform difficult tasks comparable to human experts. Expert systems can handle problems through symbolic manipulation. They select the best answer through a set of values called certainty factors. A central problem lies in establishing an inference mechanism utilizing the different rules and applying it to the knowledge base. The user can ask how the conclusion was reached and what rules were applied. The expert system should be able to answer and explain how the answer was derived.  11  A program containing knowledge about the problem is called a knowledge-based  system.  The difference between knowledge-based systems and other systems is that knowledgebased systems do not imbed the knowledge within, for example, a computer program, rather they represent the knowledge explicitly in higher-level forms. These forms include rules and facts. Knowledge-based systems are close to the way people perceive problem solving to be. They have an inference engine for reasoning with these rules and facts. The semantic network is one of the oldest scheme used in artificial intelligence for representing knowledge. A semantic network is described by a graph that is used for representing objects and the relations between them. The objects are called nodes. The relations between the objects are expressed as directed arcs.  Another method for representing knowledge is a data structure known as the frame. Frames perform the same function as semantic networks in addition to representing contextual information about objects, concepts, or events. A frame consists of a series of slots where each slot contains a fact.  2.2.2 Artificial Neural Networks The development of Artificial Neural Networks ( A N N s ) has progressed rapidly as a result of their ability to mimic natural intelligence. A N N s have been used successfully for recognizing symbols. Their drawbacks are that they cannot justify the answers, as well, if we want to teach the system new patterns, the whole training process would have to be repeated. Another disadvantage of using A N N s is that it is not easy to add existing preacquired knowledge to the system.  A neural network is a system composed of many simple processing elements operating collectively. The function of each element is determined by the network structure and connection strengths. Some basic A N N s are described by L i p p m a n n . neural networks are described by K u n g .  (18)  Digital artificial  ( 1 9 )  A N N s are classified into two main groups: supervised and unsupervised networks. While supervised A N N s use the output as well as the input values in the training process to adjust the weights of the links, unsupervised A N N s use only the input values. In addition,  12  there are networks that accept binary input while others accept continuous input. Examples of artificial neural networks include the Perceptron, the Hopfield network, the Hamming network, the probabilistic neural network, the radial basis-function network, the Carpenter/Grossberg classifier, the Kohonen network and the N e o c o g n i t r o n . ' (18  I9)  The Perceptron is a popular example of A N N s . A simple Perceptron consists of an input layer and an output layer. It can classify an input vector into classes. Assume we have three classes of handwritten letters a, b and c, and each is contained in a matrix. Assume we have defined two features, feature 1 is the density of black pixels in the upper half, and feature 2 is the density of black pixels in the lower half. The simple Perceptron will be able to correctly classify these classes if they are linearly separated as shown in Fig. 1. Classification of unclassified symbols can be determined by measuring the minimum distance between the unclassified symbol and all classes. Then, the unclassified symbol will be considered to belong to the closest class. feature 2 (2.1, 3.1) class a  3 d.9,2.7)  -fey-  2 1  (1-1,2.2)  class c  -Q-  d-2,1.2)  2  1 output b  a  feature 1  c  o ^w12^wis0 w11^  T.  input  y  Figure 1 Linearly separated classes. On the other hand, non-linearly separable classes, shown in Fig. 2. can not be solved by using a simple Perceptron because they are not linearly separated. However, such a problem can be solved by using a 3-layer or a multi-layer Perceptron.  13  feature 2  3 2 1  i  V  '  class 1  class 2  1*° V  AA A  A  A  class J A A A  class 2  A  '  1  ^  >  X  feature 1  output  Figure 2 Non-linearly separable classes. The Perceptron structure can be used to implement a Gaussian maximum likelihood classifier. However, neither the Perceptron convergence  procedure nor the Gaussian  classifier is appropriate when the classes can not be separated by hyper planes. N o more than three layers are required to implement any nonlinear function because a three-layer network  can  approximate  any  non-linear  function.  The backpropagation  training  algorithm is an iterative gradient algorithm designed and used to minimize the mean square error between the actual output of a multi-layer feed-forward Perceptron and the desired output.  A n example of a supervised 3-layer Perceptron is shown in Fig. 4. The backpropagation algorithm can be used to adjust the weights of the connections between the neurons. Assuming that digits are drawn in a 7x5 matrix of binary pixels (as shown in Fig. 3), there will be 35 input neurons (for the 35 pixels in the matrix) and 10 output neurons for digits 0 to 9. Assuming a single hidden layer, A N N s will look like the one shown in Fig. 4.  14  Figure 3 An example of a digit written in 7x5 pixels.  1  2  3  4  35  Figure 4 An example of a 3-layer ANNs Percptron for digit recognition.  The backpropagation algorithm involves the following steps: 1. Apply the input vector X to the first layer. 2. Calculate each input of the second layer Inp = X , W , , + X W , + ... + X W , 12  2  2  n  n l  Inp  22  Inp  m2  = X i W12 + X W 2  = X!W,  2 2  + X W  m  2  + ... + X W  2 m  n  n 2  + ... + X W n  ,  n m  .  Where Wjj is the value of the connection strength from neuron i in the first layer (the input layer) to neuron j in the second layer (the hidden layer).  3. Calculate the outputs from the second layer  Outi2 =  F(Inp, ), 2  Out 2 = F(Inp ), 2  22  ...,  Out  m 2  = F(Inp ). m2  Where F(y) is equal to 1/(1 -e~ ), the derivative is g(y) y  4. Calculate the inputs to the third layer  Inpn = Out! M n + O u t M i + ... + O u t M i , 2  Inp  23  2  = Out) M12 + Out M 2  m  2  2  m  + ••• + O u t M m  m 2  ,  * • * ?  InpB = Outi M n + O u t M 2  2 I  + ... + O u t M i . m  m  Where Mjj is the value of the connection strength from neuron i in the hidden layer to the neuron j in the output layer.  5. Calculate the outputs from the third layer  Outi3 = F(Inpi ), 3  Out  23  = F(Inp ), 23  * • • i  16  Outi = F(Inpi ). 3  3  6. Calculate the errors in the third layer  8 , 3 = ( Y 1 - Out, ) g(Inpi ), 3  8 3=(Y2-Out 3) 2  2  3  g(Inp ), 23  • • • J  6 i 3 = ( Y l - O u t , , ) g(Inp ). 13  7. Propagate the errors to the second layer  8 , = g ( I n p i ) (813 M n + 823 M , + ....+813 M n ) , 2  8  2 2  2  2  = g(Inp ) (813 M i + 8 22  2  2 3  M  + ... + 813 M ) ,  2 2  2 )  • • •»  S  m 2  = g(Inp ) (813 M i + 8 m2  m  2 3  M  m  2  + ... + 8  8. Update the weights M  M i 1 new = M ) 1 old + ri 813 O u t i , 2  M  ! 2  new = M12 old +  r\  8  2 3  Out 12,  ...,  M21 new = M i old + r| 813 Out 2, 2  2  ...,  M i new = M i old + rj 813 O u t . m  m  m2  Where r| is a learning factor e [0,1].  m 3  M i). 2  9. Update the weights W W u new = wu old + r\ 8i X | 2  W12 new = w  ) 2  old + r\ 822 X i ,  W21  old + r\ 812 X ,  • • • j  W21 new =  W  n m  10.  new = w  n m  2  old + r\ 8  m2  X . n  Calculate the error E = ((8, ) +(8, ) + ( 8 ) + ...+ (8 ) ) 2  3  2  3  2  23  2  !3  Stop when E is small enough (e.g. 0.01) else go to step 1. After training an A N N with enough samples, the weights M and W will be stable. For an unclassified input X , (e. g. 7x5 pixels), the neuron with the maximum output value will be selected and hence, the corresponding digit.  2.3 The Main Pattern Recognition Techniques Pattern recognition techniques, as mentioned earlier, fall under the following main categories: statistical pattern recognition and structural pattern recognition. In most statistical pattern recognition systems, symbol features are first defined, then the decision boundaries in the feature space are determined as shown by Duda and Hart.  (l3)  Many  methods based on statistical pattern recognition techniques have been developed and proved to be very effective. Statistical pattern recognition systems (including artificial neural networks) need a large number of training samples to select (or extract as in some ANNs) the features. If the features are not selected (or extracted) properly the feature space regions will overlap. As a result, some symbols that occur in the overlapped regions will be incorrectly classified.  18  Generally, statistical pattern recognition systems are developed for a specific application. For example, if an artificial neural networks is used for recognizing English letters and then it is required to recognize one or more new digits, this A N N would have to be retrained with the entire training data set. This tedious retraining must include both the new and the old symbols. In addition, the system may not function properly, especially, if one or more of the new symbol features are close to or overlap with other existing symbol features. In this case, the structure of the artificial neural network may need to be redesigned (e.g. by changing the number of neurons or the number of layers).  The second class of pattern recognition techniques is structural pattern recognition. In these techniques, complex patterns are divided into simpler ones, and the relations between the sub-patterns are described. Structural pattern recognition methods generally use rules and grammars to describe symbols as shown by F u .  ( 1 4 )  These methods require  few or no training samples. In addition, they can also justify their answers.  Pattern recognition problems that are also common arise when the characters overlap or when the writing is cursive. English characters can be written in isolated or connected forms. However, in the Arabic language, characters can only be written in cursive form. Hence, it is often necessary to segment a word into characters before recognition can be applied.  2.3.1 Statistical Pattern Recognition Statistical pattern recognition techniques are based on extracting features from symbols, then clustering these features, hence, recognizing the symbols. Various features as well as methods are described by Trier et a l .  (20)  The methods include template matching, image  transforms, zoning, and moments. Template matching is the simplest technique for symbol recognition. For some methods, the feature vector could be the symbol pixels themselves, or a mapping of them while other methods use short feature vectors. Such vectors  result from transformations such as the Fourier transform and the Cosine  transform. These methods use pixel by pixel manipulation which is not very suitable for the recognition of noisy or handwritten symbols, but is suitable for the recognition of typed symbols.  19  Methods which use the density of black pixels in different parts of the image (zones), directional histograms, and different types of moment-based invariant techniques have been proven to be useful in many statistical pattern recognition s y s t e m s / ' ' ' 21  22  23  24)  Statistical pattern recognition is useful in solving classification problems. N features lead to an N-dimensional space. There is no general method for defining the feature space. If the features are defined properly, then all feature vectors belonging to the same class will fall in the same cluster, therefore, enabling the cluster not to contain any feature vectors from any other class.  Classification is achieved by partitioning the feature space into regions, one (or more) region for each class. The decision boundary is chosen so as to minimize the probability of misclassification. A s a result, selection of the appropriate feature vector is probably the most important factor in achieving a high rate of recognition.  The distribution of the training samples and the probability density function can be estimated, either by determining the parameters of a suitable distribution function or by estimating the density function itself. These parameters can be adjusted either by using supervised or unsupervised methods. After studying many features, we found that selection of the appropriate feature vector is probably the most important factor in achieving a high rate of recognition. Bayes decision theory is the ultimate statistical pattern recognition technique for minimizing the probability of error. This upper limit determines the best boundary regions for each class in the feature space. In order to increase the recognition rate above this limit, the features themselves have to be re-selected which requires major changes in the system.  The clustering procedure is the most important step in recognition. Clustering relies on a similarity measure typically based on a distance measure defined over the feature space. The dissimilarity measure is the mean-square distance between the input vector and each of the stored classified vectors. Clustering may be performed by minimizing a criterion  20  function, such as the sum of the squared error criterion. The distance between clusters can be measured by determining:  •  The distance between the two closest points.  •  The distance between the two furthest points.  •  The average distance between points.  •  The distance between the means of the two clusters.  With each technique there are advantages and disadvantages. The main disadvantages of using the statistical pattern recognition techniques are:  •  They need a large number of training data.  •  There is a probability of mis-recognizing data, this probability can be determined by  using Bayes decision theory.  •  They can not justify the answer.  •  The output is only a classification and not a description of the pattern, and the  relations between the features are ignored.  The main advantage, however, of using statistical pattern recognition techniques is that the decisions  performed are based on a well-founded  mathematical  theory.  Some  statistical pattern recognition techniques have proved to be very useful for handwritten Arabic numeral recognition.  Artificial  Neural  Networks  (2I)  are the  most  successful  statistical  pattern  recognition  techniques with respect to the classification of symbols. Symbol features are extracted automatically from the training samples. In addition, classes can be created automatically by using supervised or unsupervised artificial neural networks.  21  However, A N N s have the following disadvantages: they can not justify the answer, they have to be trained (or even reconstructed) every time a new symbol is added, and there is no guarantee of a certain recognition rate.  A survey of some statistical pattern recognition techniques is conducted in the following section. These techniques used different features for the recognition of symbols. These features include:  •  The percentage of black pixels in different zones (the zoning method).  •  Various histogram based features such as the ratio between the vertical and the  horizontal histogram distributions and the directional histogram.  •  Moments.  •  Features extracted using A N N s .  2.3.1.1 T h e Z o n i n g M e t h o d Multiple expert systems have been shown to be a promising strategy for handwritten pattern recognition by Cao et a l .  (2l>  The image is divided into 4x4 rectangular zones. A  histogram is calculated for each zone. The contour direction takes one of four possible values. A n incremental clustering neural network algorithm with histogram feature extraction is used for recognition. Whenever a new training pattern is presented, a group of similarity distance measures between the current input feature vector and the existing weight vectors are calculated and examined. If the minimum distance is larger than a preassigned threshold, a new cluster is formed and its corresponding weight vector is set to the current input feature vector. Otherwise, the current input pattern is joined to the existing cluster closest to it. Following that, the current input vector and the weight vector are updated. A total of 13,200 handwritten digits were used. The system was trained using 6800 samples. The system was tested using 6400 samples. The lowest error rate achieved was 0.17%, and the rejection rate was. 14.5%.  22  Twenty triangular regions are defined by Burel et a l .  U i )  Each of these twenty regions  constitute a feature. A five-layer A N N Perceptron is used for clustering these and 76 other features. A recognition rate of 90 % was achieved.  2.3.1.2 The Histograms Other important pixel-features  are the histogram distributions. The histogram or the  description of the histogram (by the mean, variance, or other moments) can be used as features for symbols. Statistical features based on the description of the profile by a histogram is suggested by Burel et a l .  ( 2 2 )  2.3.1.3 The Moments A l - Y o s e f and U d p a  ( 2 3 )  implemented a histogram description method for Arabic character  recognition where a vector of nine features is used.  A recognition rate of 85.5% was  achieved for isolated printed character using a linear discriminate function.  First, the system identifies the connected regions in the image. Then, the vertical and horizontal histograms are calculated. The normalized moments of these histograms are used to describe the histogram distribution. Nine features are used to describe the symbol.  Features 1 and 2 measure the kurtosis, the flatness of distribution in the horizontal and vertical directions. Features 3 and 4 measure the skewness, the asymmetry of the distribution in the horizontal and vertical directions. Features 5 and 6 measure the normalized skewness and kurtosis, and relate the symmetry to flatness of the distribution in the horizontal and vertical directions. Features 7, 8 and 9 measure the relation between the moments of the vertical and horizontal projections of the same symbol.  Given that u = £ (XJ - x ) g(x) where g(x)= Z x in the vertical or horizontal directions and r  r  u  x is the mean value of x. u  Features 1, 2 are equal to U4/(u, )~  i  2  Features 3, 4 are equal to  (13/(02)  1 5  n  m  e  vertical and horizontal directions, respectively.  in the vertical and horizontal directions, respectively.  23  Features 5, 6 are equal to  " in the vertical and horizontal directions, respectively.  10.3/(^14)  Feature 7 is equal to pi vertical/pi horizontal. Feature 8 is equal to p vertical/p horizontal. 2  2  Feature 9 is equal to p,4 vertical/p horizontal. 4  During the training phase, the symbol features and the corresponding symbol are determined and stored in a database. Other methods of calculating geometric moment invariant have proved to be useful in many pattern recognition systems.  Cheng et a l .  (24)  introduced a hierarchical neural  network for electrical symbol recognition. Six invariant moment features are calculated, and a multi-layer Perceptron classifier with a back propagation learning model is used for recognition. The recognition rate for 340 training input symbols was 98.5%, and the rate for 170 test symbols was 89%. It is clear that the number of training and testing symbols is low. It is believed that the recognition rate will be much lower than 89% if a larger database is used. 2.3.1.4 Features Extracted By Using ANNs The Neocognitron is a neural network developed to recognize handwritten Latin characters by Fukushima et a l .  (25)  It is an attempt to imitate the human visual system. A  selective attention model has been extended by Fukushima  (26)  to perform both recognition  and segmentation of connected Latin characters. The Neocognitron consists of a sequence of simple layers followed by a complex layer. The system is designed to recognize the digits 0 through 9, regardless of where they are placed in the retina's field of view. On the simple layers (S), the cells on each plane are sensitive to simple features. Each layer of the simple cells acts as a feature extraction system that uses the layer preceding it as its input layer. Each S-cell on a single plane is sensitive to the same feature. The Complex cells C integrate the responses of groups of Scells. The C-cells' response is less sensitive to the exact location of the feature on the  24  input layer. This gives the Neocognitron the ability to identify characters regardless of their exact position or size in the field of view of the retina. The weights of each template window which relates complex layers to simple layers are calculated by using supervised techniques and updated by performing certain training samples for each cell. These training samples teach the network how to extract the features.  The process of pattern recognition in the multi-layer network can be summarized as follows.  In the first module, several features are extracted. In the next module, these  features are combined by observation over a larger range, and higher order features are extracted.  The recognition of connected characters can not be successfully performed by using the simple pattern matching technique. This is because the same character can be written in different ways. The model used for recognizing connected character has top down as well as bottom-up connections between the layers.  The signals through the forward paths  manage the function of pattern recognition while the signals through the backward paths manage the function of selective attention, segmentation  and associative  recall. The  routes of the backward signals are controlled by gate signals. Only one pattern is recognized at a time by this feedback path. Once a pattern has been recognized and segmented, the process of recognizing the second pattern begins.  2.3.1.5 Features Studied by the Author The author conducted the following experiments to study the effectiveness of some statistical features for handwritten character recognition. The initial results show that statistical pattern recognition is not useful for handwritten character recognition. A small set of data (40 samples/class), and 25 classes are used. It is found that the classes overlap in the feature space and each sample is far from the center of its class. Thus, it was concluded that statistical pattern recognition techniques, as have been shown in the previous sections, are likely successful for typed symbol recognition but are not as useful for handwritten symbols. Statistical pattern recognition is only applicable if the features are well clustered in the feature space. In addition, there will always be some mis-  25  recognized symbols.  The features that we used in our studies should be classified as  follows:  1.  The percentage of black pixels in different zones (the zoning method).  2.  Various histograms based features such as the ratio between the vertical and the  horizontal histogram distributions and the directional histogram. 3. Moments.  4.  Other miscellaneous features, such as the aspect ratio.  W e now describe the details of the features we considered and the results we obtained, a) The zoning method The percentage of the black pixels in each zone is used as a feature for this zone. During the training phase, symbol features are extracted, the corresponding symbol is determined and then both symbol and features are stored in the database. The symbol is divided into 16 (4x4) regions, as shown in Fig. 5. The corresponding feature vector is:  [0.79, 0.46, 0.51,0.42,  0.77,0.31,0.40,0.47,  0.72, 0.14, 0.20, 0.67,  0.80, 0.46, 0.47, 0.53]  m  I  I  w  j  I  Figure 5 The symbol is divided into 16 regions.  26  The normalized pixel density is determined in each zone. The feature vectors of 40 symbols are summed together, slot by slot (each vector has 16 slots). The mean vector for the forty symbols is determined for each of the 25 classes. The same data is used to determine how many symbols lie in the overlap regions. It was found that the percentage of the symbols lying in the overlap regions is 13.7% i.e. the substitution rate is 13.7%.  b) Ratios of histograms The experiment uses the histogram distributions as features. The symbol is divided into 256 (16x16) zones as shown in Fig. 6. Horizontal and vertical histogram distributions are calculated. Finally, the ratio between the two distributions is determined as follows: The value in slot [i] is equal to the ratio of the difference between the horizontal and vertical projections [i] to their summation. The resulting ratio constitutes a feature vector of the original symbol. This vector comprises of 16 slots. The mean vector for the forty symbols is determined for each of the 25 classes. The same data is used to determine how many symbols lie in the overlap regions. The percentage of the symbols in the overlap regions is 29.4%  i.e.  the  substitution rate is 29.4%.  For example, the features vector for the symbol shown in Fig. 6 is as follows:  [-0.15, -0.1, -0.4, -0.01, -0.01, -0.01, 0.16, 0.39, 0.35, 0.02, -0.05, -0.15, -0.31, -0.32, 0.19, 0.55]  27  Figure 6 Vertical and horizontal histogram distributions of the symbol are divided into 16 slots.  c) Directional histograms Another feature extraction method studied in this research is the directional histogram. This method can be used for pattern recognition, especially in signature recognition. The method is described by the following algorithm: 1. Thin the image as shown in Fig. 7. 2. Calculate the image area (the total number of black pixels in the thinned symbol). 3. Calculate an approximation of the direction of each pixel by fitting the best line passing through the pixel (using a 5x5 window and the least square method for minimizing the error). Define the slope of this line as the direction of the pixel.  28  4.  Calculate the number of pixels with different slopes. The number of slopes that are used in this experiment is 16 (i.e. a slope step =180/16 degree).  5.  Normalize each value by dividing it by the area (the total number of black pixels).  (a) (b) Figure 7 A symbol before thinning (a) and after thinning (b). A vector of length 16 is used to represent the symbol. Each one of the vector's 16 slots contains the percentage of pixels that have a certain slope. In this experiment, the slopes are [0.00, 11.25, 22.50, 33.75, 45.00, 56.25, 67.50, 78.75, 90.00, 101.25, 112.50, 123.75, 135.00, 146.25, 157.5, 168.75].  For example, the symbol shown in Fig 7(a) is described by the following vector:  [0.37, 0.020, 0.010, 0.020, 0.060, 0.020, 0.020, 0.000, 0.320, 0.02,00, 0.0200, 0.0300, 0.0500, 0.0200, 0.020, 0.00]  The mean vector for the forty symbols is determined for each of the 25 classes. The same data is used to determine how many symbols lie in the overlap regions. 62.5% of symbols lie in the overlap regions, i.e. the substitution rate is 62.5%.  d) Normalized moments  The first six features introduced by A l - Y o s e f and U d p a  ( 2 3 )  are used in the following  experiment. A n example of the feature vector for the symbol shown in Fig. 5 is as follows: [0.35, 0.35, 0.034, 0.14, 0.07 0.31]  29  The mean vector for the forty symbols is determined for each of the 25 classes. The same data is used to determine how many symbols lie in the overlap regions. 42.9% of the symbols lie in overlap regions, i.e. the substitution rate is 42.9%.  e) Moments invariant  1000 symbols are used to test the first four moments, which are used by Cheng et a l .  ( 2 4 )  The mean vector for the 40 symbols is calculated for each of the 25 classes. The same test symbols are used to determine how many symbols lie in overlap regions. It was found that 75.2% of the symbols lie in the overlap regions, i.e. the substitution rate is 75.2%. f) Miscellaneous features A combination of different features is used for pattern recognition. The following six features are defined:  1.  Density: the ratio of the number of black pixels to the total number of pixels in the  minimum rectangle that contains the symbol. 2.  Perimeter: the circumference of the minimum rectangle that contains the symbol.  3.  Centre of mass: if the origin of the entire image is considered to be the pixel at  location (0,0), then the center of mass of an object C is (Cr, Cc)  where C r = 1/n X x, C c = 1/n X y for n x n image.  4.  Form Factor: the form factor is the ratio between the square of the perimeter to the  symbol area.  5.  Directed Density: it is similar to the density calculated in the zoning method.  However, in this case the rectangle is oriented toward the principal axis.  The principal axis of a bi-level symbol is a line passing through the central point having a minimum total distance from all pixels belonging to the symbol. This is achieved as follows:  30  1.  Locate the central point.  2.  Locate the boundary pixels. A point in the boundary and the C point forms a line, one of these line is the principal axis.  3. 4.  Calculate the sum of the distance between all points and the assumed principal axis. Select the point that has a minimum sum. Then, find the oriented rectangle:  5.  Locate the principal axis and construct an oriented rectangle that encloses the object.  6.  Identify the two points that have the greatest distance from the principal axis (the minor axis).  7.  Identify the two points that have the greatest distance from the minor axis.  Although each feature by itself is suitable for describing the symbols, the combination of these features could cause a serious overlap among the regions of the classes. A n example of a vector of these 6 different features is defined for the symbol shown in Fig. 5 is [0.52, 0.04, 0.66, 0.34, 0.20, 0.5].  The mean vector for the forty symbols is determined for each of the 25 classes. The same data is used to determine how many symbols lie in the overlap regions. The percentage of the symbols in the overlap regions is 74.1%, i.e. the substitution rate is 74.1%.  2.3.1.5 Features S u m m a r y  The following table summarizes the results of using different statistical features for handwritten character recognition. Some characters will be recognized by applying a certain method. Others will be recognized by applying a different method. It was concluded that it is important to select the appropriate features to achieve a high recognition rate using statistical pattern recognition techniques.  31  zoning ratios of H norm moments directional H inv moments miscellaneous 2 7 23 17 35 29 5 4 14 34 27 22 0 0 11 31 28 35 2 9 12 34 33 18 1 3 13 24 33 37 10 14 30 35 29 40 0 12 10 38 34 35 g h 6 12 28 32 15 35 2 7 2 18 33 14 j k 3 17 10 14 39 24 1 39 5 27 4 13 12 m 8 2 23 39 33 12 n 4 14 28 37 37 26 0 2 6 21 18 16 35 4 7 10 31 34 35 P 3 16 4 34 34 34 q r 8 27 9 34 36 39 s 9 21 9 27 37 39 t 4 8 9 31 25 34 u 8 30 23 15 29 33 V 2 16 13 33 12 39 w 5 16 17 27 32 17 X 4 23 29 3 36 21 4 11 23 12 36 36 y z 2 7 31 3 36 40 SUM 137 294 429 625 752 741 Table 1. The number of misrecognized symbols (handwritten English letters) for each method. a b c d e f  The goal of this thesis work is the construction of a system for recognizing general symbols. The system should be able to justify the answer and have a recognition rate that can always be increased to any value (as close as possible to 100% with no misrecognized symbols, but with possible some rejected symbols). In the following section we will survey different methods of structural pattern recognition. 2.3.2 Structural Pattern Recognition Structural pattern recognition is quite different from statistical pattern recognition. The basic idea behind structural pattern recognition is that objects are constructed from smaller components using a set of rules. Syntactic pattern recognition techniques are a sub-set of structural pattern recognition. In syntactic pattern recognition, complex patterns are divided into simpler ones, and the  32  relations between the sub-patterns are described. The techniques are based on mathematical and formal language theories. However, these techniques are not powerful enough to handle real-world applications. An example of a syntactic pattern  recognition method is the two-dimensional  mathematical notation recognition developed by Anderson.  (27)  The recognition algorithm  starts with the ultimate syntactic goal which is partitioned into a set of sub-goals, these in turn are broken up into other sub-goals, and so on until either every sub-goal is reached or all possibilities have failed. A set of rules is used to describe the mathematical expressions. Different grammars can be used to describe a large set of complex patterns and to recognize them.  (14)  Examples of grammars are shown in Figs 8 and 9.  aba  » aaa  where a is —  and  >  b is  /  for example  Figure 8 An example of a transformational grammar.  a is . b is  •  i  c is  >  i  d is  then  >  <— <—> n n n n  abed  will be a square  Figure 9 An example of context sensitive grammar.  33  Four expert systems were developed for recognizing unconstrained handwritten digits by Suen et a l .  (28)  Different primitives are used in each system. The first expert system  obtains the skeleton by thinning, then determines the end points and the junction points. T o simplify the skeletons, branches less than 10% of the total pixels are removed. Freeman codes are used to code the skeletons. Then, the skeleton is simplified by an average direction of one code for few codes. The bounding box for a symbol is divided into nine regions: center, north-west, north, north-east, east, south-east, south, south-west, and west. The classification is performed by using eleven modules. The first module is dedicated to the recognition of one-branch symbol parts, the other ten modules are used for the recognition of multi-branch symbol parts. The recognition rate is 86.05%, and the substitution rate is 2.25%.  The second expert system performs the following steps:  •  Thinning.  •  Tracing the skeleton.  •  Approximating the curves by lines.  •  The arrangement of the line segments into primitives.  The recognition rate is 93.1% and the substitution rate is 2.95%.  The third expert system uses the following features:  •  the locations of the end points,  •  the junction points in each region of the digit,  •  a bend between two lines,  •  horizontal curves at top or bottom,  •  distance between two points,  34  •  location of special points in the digit,  •  direction of a stroke from a special point,  •  inflection between two points,  •  a curve at the left or right profile,  •  comparative lengths between two strokes,  •  straight stroke between two points,  •  width of the digit at different rows,  •  width of a stroke,  •  symmetry of character,  •  horizontal intersection at a row.  The system recognition rate is 92.95%, and the substitution rate is 2.15%. The fourth expert system relies on extracted features from the contours. The recognition rate is 93.9% and the substitution rate is 1.6%.  Another structural pattern recognition method for digit recognition is described by H . Jianming and Y . H o n g .  (29)  In this method, four points for bends (B), points for curves (D),  terminal points (T), and intersections (I) are defined. A primitive is defined as the skeleton segment which starts and ends at feature points. A feature code of 11 elements is used to describe the local information of the character and a five-element vector is used to describe the global information.  The eleven elements are:  1. the curvature of the primitive.  2. the orientation of the primitive,  35  3. to 9. the types and locations of the start and end points  10. the moving direction of the primitive,  11. the length of the primitive.  The five elements are: 1. the number of loops, 2. the number of paths from T to T points, 3. the number of paths form T to I points, 4. the number of paths from I to I points, 5. the number of T points. The recognition rate for the digits using prototype matching is 97.86%. While the recognition rate for neural networks is 97.29%, the substitution rate is 2.71%. A new technique integrating a neural network and a knowledge-based system for image recognition was introduced by K i m et a l .  (30)  The system was designed to recognize  handwritten digits. The model is capable of inductive learning from example data and logical inference from the rule base. The system has the ability to justify the answer, e.g., why a pattern is recognized as 5, and not 6 or 9. This system is well suited for applications where only partial knowledge is available. For a typical sample of 200 handwritten digits, the recognition rate ranges from 69.5% to 81.5% and depends on the number of rules.  Another system that integrates the use of neural networks with expert systems is reported (31)  by Amine et al.  The original image is transferred into a binary image using a parallel  thinning algorithm. The resulting skeleton is traced. Some primitives such as straight lines, curves and loops are extracted. Finally, a five-layer artificial neural network is used for classification. The neural network is trained with 2000 isolated Arabic characters and tested using 1000 new characters. The recognition rate is 92%.  36  A system by Burel et al.  ;  uses a combination of statistical and morphological features  and is successful in recognizing handwritten digits. The system divides a digit into twenty regions. Each region has a feature associated with it. This feature is the ratio of the number of black pixels in this region to the number of black pixels in some other region. The morphological features include cavities (west, east, north, south and center) and holes. A five-layer Perceptron neural network is used for classification.  The artificial  neural network is trained with 1414 digits and the evaluation is performed on 1175 digits. The recognition rate is 93.6%.  A structural feature extraction technique for English character recognition is described by Starzyk et a l .  (32)  A n effective method for thinning using a 3x3 template windows is used.  Although this method uses a 3x3 window, it also uses a non-boundary pixel that looks at pixels just outside this window. These windows  are applied sequentially and are  implemented by a hardware circuit. After thinning the image, critical points are marked, then the segments are determined. These segments are scaled, matched, and classified.  2.4 Preprocessing Preprocessing of off-line handwriting patterns is done prior to recognition. This usually involves cleaning and smoothing strokes.  2.4.1 Thresholding  Thresholding is used in the process of converting a grey-level image into a bi-level one.  (33)  It involves looking at each pixel and deciding whether it should be white or black.  In simple cases, the mean or median value of the gray levels over the entire image may be used as the threshold. This technique does not always produce good results. Using multiple thresholds and dividing the image into regions gives better results.  2.4.2 Noise  Noise manifests itself as random variations in the pixel levels caused by digitization or other processes applied to the image. There are different types of noise. One type of noise causes a black pixel to become white or a white pixel to become black, at random. For  37  this type smoothing filters are effective. A better tool is the median filter, which acts to minimize the edge-blurring effect.  2.4.3 Overlapping The steps in separating overlapping objects using the Watershed method are as follows: First, compute the distance transform, which is the minimum distance from each pixel to the background. The distances 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16, are marked by the characters 0,1,2,3,4,5,6,7,8,9,:,;,<,= >,?,@ in Fig. 10.  Locate the pixels with peak values '>' where K=14 and ' @ ' where K=16. These pixels are assigned a value of K . Pixels adjacent to the peaks are given a value of K - l . The regions will be identified by starting at the peaks and moving to the background pixels. Adjacent regions are not allowed to overlap or touch. This method can be effective for separating objects such as blood cells.  38  jOODOOGOGOOOooooooooGOOOOOOOOOOOoaoooQDOOOOOOOOOOOaoooooooGCGc:__ :.: 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 o o o o o a o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 3 O O O O O O O 0 O O 0 Q O 0 0 O O 0 0 O O O O O O O O O O 0 O O 0 O O O 0 0 O O O 0 O O O O O O 0 Q O 0 0 O O O 0 O O 0 0 O O O O O O O 0 O O Q O O O O O O 0 O O O Q O O O O O O 0 O O O O O 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 O O O O Q O 0 0 0 0 O 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 O O O 0 0 O Q O O Q G O O O O 0 O O O D O O O O O O O 0 O Q O O O O O O O O 0 O O O O O Q Q O Q O O O O Q O Q O Q O O O O O 3 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 0 0 O O O O O O O O Q 0 0 O Q O O 0 0 000 0 0 0 0 0 0 0 0 0 0 0 0 00 O O O O O O O O O O O O O O O O O O O 0 0 0 0 0 O O O O O O O O O O1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000 0 0 0 0 0 0 00 0 1 1 2 2 2 3 3 4 4 4 4 4 4 4 4 4 4 4 44 4 4 3 3 32 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 00 00 00 0 0 0 0 0 0 0 00 00 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 1 2 2 3 3 3 44 5 5 5 5 55 5 5 5 5 55 5 4 44 3 3 2 2 1 0 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 ^ C 'C 0 C 1 1 2 2 2 3 3 4 4 4 5 5 6 6 6 6 6 6 6 6 6 6 6 5 5 5 4 4 3 3 2 1 0 0 O 0 0 O O O 0 Q 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O 0 O O O O 0 0 0 0 O O O O 0 O O O O O O O O 0 0 O 0 O O 0 0 0 0 0 0 0 1 2 2 3 3 3 4 4 5 5 5 6 6 7 7 7 7 7 7 7 7 1 6 6 6 5 5 4 3 3 2 1 0 00 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O O O O O O O O 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 1 2 3 3 4 1 4 5 5 6 6 6 7 7 8 8 8 8 8 8 B 7 7 7 6 6 5 4 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00 0 0 0 0 0 0 00 00 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000 00 012 3 4 4 5 5 5 6 67 7 7 8 8 9 9 9 9 9 8 8 8 7 7 6 5 4 3 2 1 1 0 0 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 00 0 0 0 0 0 :OG:.0C 12344566677S8899 9 :9 9 8 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OQ00001233456777BB999 9 :::9 8 7 6 5 4 3 2 1 0 0 0 0 0 D O O 0 0 Q Q O 0 O O O 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 O 0 0 O 0 O O O O 0 O O O O O 0 0 0 0 0 0000001223456788899:: 9 :B 7 6 5 4 3 2 1 0 0 0 0 0 0 O O O O O O O O O O 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 0 0 0 O O O O O O O O O O O 0 0 0 0 0 300000112 34=678999::; 9 :8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0000000123456789 9 :8 7 G 5 4 3 2 1 0 0 Q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3000000123456789 9 :B 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 4 3 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0000000123456789 9 :8 7 6 5 4 3 2 1 0 0 0 0 0000 0 1 1 2 2 2 2 2 2 2 23 4 5 6 6 6 6 6 6 5 6 6 6 6 6 5 5 4 4 3 2 1 0 0 0 0 0 0 0 0 0 0 O O O O O O O O 30000001234=6789 9 :8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 1 2 2 3 3 3 3 3 3 3 3 4 5 6 7 7 7 7 7 7 7 7 7 7 6 6 5 5 4 3 2 1 1 0 0 0 0 0 0 0 O O O O O O O O O O 3000000123456789 9 :8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 1 1 2 3 3 4 4 4 4 4 4 4 4 5 6 7 B 8 8 8 8 8 B 8 7 7 6 6 5 4 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3000000123456789 9 :8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 1 2 2 3 4 4 5 5 5 5 5 5 5 5 6 7 8 9 9 9 9 9 9 8 8 7 7 6 5 4 3 3 2 1 0 0 0 0 0 0 0 0 0 O O O O O O O O 3000000123456789 9 87 65 4 3 2 1 0 00 0 0 0 0 0 1 2 3 3 4 5 5 6 6 6 6 6 6 66 7 8 99 9 8 8 7 6 5 4 4 32 1 0 0 30 0 0 00 0 0 0 0 0 0 0 0 0 3000000123456789 9 8 7 6 54 3 2 1 1 1 1 1 1 1 1 1 1 2 3 4 4 5 6 6 7 7 7 7 7 7 7 7 8 9 : 99 8 7 6 5 5 4 3 2 1 1 0 0 0 0 0 0 00 0 0 0 00 0 0 0 3000001123456789 9 9 9 9 9 9 9 9 9 9 9 8 7 6 5 4 3 2 2 2 2 2 2 2 2 2 2 2 2 3 4 5 5 6 7 7 B 8 8 8 8 8 8 8 9 ::9 87 6 65 43 2 2 1 0 0 0 0 0 0 0 0 O O O O O O O O 3000001223456789 9 8 8 8 8 8 8 8 B B 8 8 7 6 5 4 33 3 3 3 3 3 3 3 3 3 3 3 3 4 5 6 6 7 B B 9 9 9 9 9 9 9 9 9 :; 8 7 7 6 5 4 3 3 2 1 1 0 0 0 0 0 0 00 0 0 0 0 0 0 0 3000001233456789 9 8 7 7 7 7 7 7 7 7 7 7 7 6 5 4 4 4 444 4 4 44 4 4 4 4 4 4 5 6 7 7 8 99:::::::9 :; 8 8 7 6 5 4 4 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3000001234456789 9 8 7 6 6 6 6 6 6 6 6 6 6 6 5 55 555 5 5 5 5 5 5 5 5 5 5 5 5 6 7 889 : 9 :; 9 8 7 6 5 5 4 3 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30000012345=6789 987 6 5 5 5 5 5 5 55 5 5 5 5 5 5 5 5 55 66 6 6 6 6 6 6 6 6 6 7 899 : ; ; < « « ;::9 8 7 6 6 5 4 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30000012345S678999987654444444444444444567777777777789:;«.« 9 :; 8 7 7 6 5 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 1 2 3 4 5 = 6 7 8 8 8 9 9 8 7 6 5 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 5 6 7 B 8 S 8 8 8 8 8 8 8 8 9 < ;:= = > > > < 9 :; B 8 7 6 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 1 2 3 4 5 5 6 7 7 7 8 8 8 8 7 6 5 4 3 2 2 2 2 2 2 2 2 2 2 2 2 3 4 5 6 7 B 9 9 9 9 9 9 9 9 9 9 9 : ; « = »?? < 9 :; 9 8 7 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 00 1 2 2 3 4 4 5 6 6 6 7 7 7 7 7 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 8 9 <;:: 9 8 B 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 23 3 4 5 5 5 6 6 6 6 G 6 6 6 5 4 3 2 1 0 00 00 0 0 0 1 2 34 5 6 7 B 9 < 9 :; 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 01 1 2 2 3 4 1 4 5 5 5 5 5 5 5 5 5 5 4 3 2 1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 «,-:98765432100000000000QOOO 3 0 0 0 0 0 1 1 2 3 3 3 4 4 4 4 4 4 4 5 4 4 4 4 3 2 1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 -<;,-: 9 8 7 6 5 4 3 2 1 0 00 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 2 2 2 3 3 3 3 3 3 3 4 4 4 3 3 3 3 2 1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 -«,-: 9 8 7 6 5 4 32 1 0 0 0 0 0 0C O O Q O O O Q O 0 0 0 0 0 0 0 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 2 1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 9 :; B 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O 1 1 1 1 1 1 1 2 2 2 2 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 < < 9 :; 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OOOOOOOOOOO0 0 0 0 1 1 1 1 1 1 1 1 1 0 00 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 9 :; 9 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OOOOOOQQOOQOO00000000000000000000001234567B9 9 :8 8 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OOOOOOOOOOOOOOOOOOO00000000000000001234567B9 9 9 9 8 7 7 6 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 jQOOOOOOOOO3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 9 9 9 8 88 7 6 6 5 43 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 98 B 8 7 7 7 6 5 5 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 OOOOO0000003 0 0 0 0 0 0 0 0 G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 9 9 9 9 9 9 9 9 8 7 7 7 6 6 6 5 4 4 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 B B 8 8 B 8 B 7 6 6 6 5 5 5 4 3 3 2 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 B 8 B S 8 8 8 8 8 8 8 8 8 8 8 8 B B B 8 7 7 7 7 7 7 7 7 6 5 5 5 4 4 4 3 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 D O O O O O O O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 1 2 3 4 5 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 5 4 4 4 3 3 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 6 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 5 5 5 5 5 5 5 5 4 3 3 3 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 E 5 S 5 5 5 5 5 4 4 4 4 4 4 4 4 3 2 2 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 4 4 4 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 3 3 33 3 3 3 3 3 3 3 33 33 3 3 3 33 3 3 33 3 3 3 3 3 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 D 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 00 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 00 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O 0 O 0 0 0 3 0 O 0 0 0 O 0 0 O O O 0 0 0 0 O 0 0 0 0 0 O O 0 0 0 0 0 0 O 3 0 0 0 O O 0 0 0 0 O O 0 0 O 0 0 0 O 0 0 0 0 0 0 0 0 O 0 0 O 0 0 0 O 0 O O 0 0 0 0 O 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 00 0 0 00 00 00 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 30 000 00 00 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 00 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O O O O O O O O O O O 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 O O O O O O O O O O O O O O O O O O O 0 0 0 0 0 0 0 0 0 0 0 0 0 0  Figure 10 two overlapped objects and their distance transform  If the characters are touching such as  , then using the histogram  distribution in different directions may also help to separate them. The separating points will be the points that have low histogram values. Other methods are also suggested by Y. Lu and M . Shridhar.  <34)  The recognition problem becomes harder if the characters are  overlapped such as  39  2.4.4 Rotation and Slant Correction Slant is the angle in degrees measured in a clockwise direction from the vertical at which the characters were drawn. Many methods have been developed for the correction of  slanted symbols  B  . Other methods have been developed for the correction of tilted  B  (or rotated, skewed) symbols,  CD ,  in a document. A fast algorithm for tilt  correction in printed document images is presented by C . Sun and D . S i .  ( 3 5 )  T h e tilt angle  is obtained by searching for the histogram with a sharp peak in a set of histograms projected in different directions. The document is corrected by a geometric rotation operation. The algorithm is described below: •  Find the gradient at each dark pixel by using a Sobel filter.  •  Calculate the oriented histograms.  •  Search for the maximum in this histogram and hence calculate the tilted angle.  (36)  Slant correction is the process that tries to adjust the slant of the characters in a line or paragraph. After the slant angle is detected, a shear operation is applied to correct the slant characters. Slant can be determined to each line in the text by first finding the bounding box which is not a rectangle. Slant can be corrected by applying a shear operation to make the bounding box a rectangle. Slant can also be corrected by applying a shear operation using the chain code method suggested by Shridhar and K i m u r a .  (2)  Some methods for slant correction include:  •  Using projection profile, where the projection that gives the maximum variation  corresponds to the projection with the best alignment.  •  Using Hough transform where each point (x,y) is mapped to (p,9), the dominant lines  are found from the peaks in the Hough space.  40  •  Using the Fourier transform.  •  Using nearest neighbor clustering.  •  Using correlation.  2.4.5 Segmentation There are two general methods for the recognition of words. These two methods are recognition with segmentation and recognition without segmentation. Segmentation is the process of breaking down the word into sequences of smaller size units. A n example of this segmentation  process would be breaking a sentence into words, a word into  characters or characters into strokes. Segmentation can be done by determining the points that have a low value of histogram vertical projections. It can also be done by tracing the outer contour and calculating the distance between the extreme points of intersection of the contour with a vertical line. Segmentation is the process in which observed patterns are converted into units of patterns that seem to form characters. Segmentation is an active research area. A survey of different segmentation methods is conducted in  < 3 7  '  3 8 )  . For characters written in  predefined boxes, the writer does most of the segmentation.  A word recognition technique without segmentation is introduced by B . Al-Badr and R. Haralick.  (39)  The system is used for detecting typed Arabic words. The system detects the  word primitives, then matches them with the symbol models. The system uses thirteen primitives. The recognition rate is 99.4% for noise free text, and 73 % for scanned text.  A  lexicon-free  Shridhar.  (40)  handwritten word recognition  is  described by  G . Houle and M .  The system creates a hypothesis about the segmentation of the word into  characters, then the system selects the best hypothesis. Results on 12,968 numeric fields extracted from the Bureau of Census 95 database yielded a correct field rate of 92.7% with a 1.4% rejection rate. However, using 6785 character fields, the correct field performance was 51.7% with a 20.1 % rejection rate.  41  2.5 Postal code and Address Recognition A very important application of optical character recognition is found in postal code and address recognition. Significant research has been carried out. Kimura  (2)  ( 2  '  4 1  '  4 2 )  Shridhar and  introduced an address interpretation system developed for determining the  street number, the U S ZIP code, street name and P O Box number in mail pieces. The system carries out the following stages of processing:  •  Slant correction.  •  Line segmentation.  •  Recognition of ZIP code field, street number field, and P O Box field.  During recognition, this system uses a database to order the addresses, states, streets, and ZIP codes. There are two approaches to correct the slant problem. The first one is the estimation and correction of the slant prior to line segmentation. The second one is applied after line segmentation for each line. The basic strategy of slant estimation is to find the direction in which the projection of the document has maximum separability regarding the peaks and valleys. Once the slant of the image is estimated, slant correction is implemented as a shear transformation. Slant can be also corrected by using the Hough transform method.  Many word recognition algorithms attempt to segment words into characters and subcharacters. There are two fundamental  approaches  to word recognition. The first  approach uses a lexicon, which is used as a post processor to select the best match. The second approach matches pre-segmented word image against all the words of the lexicon to obtain the best match.  If the lines that make up words are separated and not tilted, the horizontal projection of the word will have clearly separated peaks and valleys. These often determine the location of boundaries between lines.  42  3540 images having ZIP codes and street numbers were used in the test. The top correct ZIP code recognition rate was 82.20%. The top correct recognition rate for the street number was 77.29 %.  2.6 S u m m a r y The objective of this thesis is to develop a method that can recognize any handwritten or typed symbol. T o determine a suitable approach we reviewed the representation of different pattern recognition techniques discussed in the literature. These techniques mainly fall under two major categories, the statistical pattern recognition techniques (including A N N ' s ) and the structural pattern recognition techniques. Several statistical pattern recognition techniques were discussed.  These techniques rely  on different features extracted from the patterns to be recognized and which we call pixel features. These features are based on pixel by pixel manipulation. It is shown that usually there will be symbols in the overlapped regions in the feature space. There is no way to avoid this problem in statistical pattern recognition techniques. Artificial neural networks are the best statistical pattern recognition techniques because  they achieve  a high  recognition rate. These high rates are achieved when A N N s finds the features implicitly. A N N s have been used for handwritten character recognition. Since the A N N s can not explicitly describe the features or the mechanism they used to arrive to their answers they can not justify the answer. They can not easily be modified to recognize newly added symbols. In addition, they require a large number of training samples.  Bayes decision theory is a statistical technique which minimizes the probability of error in classification. It determines the best boundary regions for each class in the feature space. In order to increase the recognition rate beyond that offered by this optimization process, the features themselves have to be re-selected.  Using some features and a small set of data (i.e. 40 samples and 25 classes), we have found that the classes overlap in the feature space. Statistical pattern recognition is only applicable if the features are well clustered in the feature space, but there will always be misclassified symbols.  |  43  The main disadvantages of using the statistical pattern recognition techniques are: they need a large number of training data and there will always be misclassified data limited by Bayes decision theory. In addition, these techniques can not justify the answer, and the output is only a classification and not a description of the pattern. Also, the relations between the features are ignored. The main advantage of using the statistical techniques is that its decision is based on a well-founded mathematical theory and the recognition rate is very high. The author believes that the structural pattern recognition techniques are the most suitable methods for handwritten symbol recognition since they are somehow similar in their operation to humans when recognizing patterns. The structural pattern recognition system which we developed is described in detail in chapter 4. Since this system relies on thinning the symbols, we discuss different thinning algorithms in chapter 3.  44  Chapter 3 Thinning In this chapter, a survey of different thinning methods will be discussed. Then, a novel parallel thinning rule-based system will be described. This system thins symbols to their central lines. Finally, we will describe a novel fast one-pass sequential thinning rulebased system for detecting certain edges of the symbol. These edges are sometimes sufficient to represent the thinned symbol. This one-pass system can also be used to delete any extraneous pixels resulting from the first thinning system.  3.1 I n t r o d u c t i o n Thinning is the process of reducing the thickness of each line of patterns to just a single pixel. Thinning algorithms can be classified  into two  general types,  parallel and  sequential. Parallel algorithms peel off the boundaries until the objects have been reduced to thin lines. The process is repeated until no further changes occur in the pattern. The number of iterations is approximately equal to half of the maximum line width of the objects. Pixels are examined for deletion based on the results of the previous iteration. However, in sequential thinning algorithms, the deletion of a current pixel depends on the results of the previously processed pixels.  Thinning is usually used as the first step in applications such as optical character recognition (OCR). A thinning algorithm is considered to be useful if it preserves the shape of the original image, preserves the connectivity, and does not leave extraneous pixels (branches).  3.1 T h i n n i n g A l g o r i t h m s S u r v e y A comprehensive survey of thinning algorithms is described by L a m et a l .  (43)  Templates  of 3X3 windows are usually used to perform the thinning and trimming of the extraneous pixels. The parallel processing of (3X3) windows simultaneously may cause the loss of connectivity. K i m et a l .  < 4 4 )  introduced 3X4 and 4X3 windows and added extra conditions  45  to perform parallel thinning which preserves connectivity. The above methods, however, do not always result in thinned patterns represented by their central lines.  A fast parallel algorithm for thinning digital patterns by deciding as to whether or not a pixel can be eroded is described by Zhang and S u e n .  (45)  This Z S algorithm is effective,  easy to use, and has been so far the most popular method. Assuming Pj is the bi-level value of the pixel written in a 3X3 window as:  p p p 9  2  3  p p, p p p p 8  4  7  6  5  the ZS algorithm uses 2 passes (sub-iterations) to obtain a central skeleton. In the first pass, the ZS algorithm deletes the pixel Pi if it satisfies the following conditions:  1.7>B(P,)>2, 2. A ( P , ) = 1, 3. P * P * P = 0 , 2  4  6  4. P * P * P = 0. 4  6  8  Where A ( P 0 is the number of 01  patterns in the ordered P , P 3 , 2  Ps, P 9 sequence and  B(P1) = P +P +...P . 2  3  9  In the second sub-iteration, the first two conditions remain the same as above, the third and fourth conditions are changed.  1.7>B(P,)>2,  2. A ( P , ) = 1, 3. P * P * P 2  4  8  =0,  4. P *P *Pg = 0. 2  6  46  The iterations are repeated until no change occurs. The ZS algorithm results in central lines of the image for the vast majority of cases. For the case of 4 5 ° and 1 3 5 ° diagonal lines that are 2 pixels wide only, the ZS algorithm reduces these lines irrespective of their lengths to a dot formed of 1 or 2 pixels. A solution for this case is suggested by Raju and Xu.  ( 4 6 )  A 2-pass parallel thinning algorithm with template matching is described by Zhang and Wang.  (47)  This algorithm preserves image connectivity, produces thinner results (less  number of pixels) than the above Z S algorithm, maintains fast speed, and also generates one-pixel wide skeletons.  A fast parallel thinning algorithm H S C P is described by Holt et a l .  The first two  ( 4 8 )  conditions of this method determine the pixels that can be deleted and are the same two conditions as (a) and (b) above for the ZS algorithm. A l l deletable pixels will be deleted except for those that satisfy any of the following conditions (a) P =P =1 and P 2  6  4  is  deletable, (b) P =P =1 and P 6 is deletable or (c) P , P and P are all deletable. 4  8  4  5  6  The H S C P algorithm is compared to the Z S algorithm by R. H a l l .  ( 4 9 )  Hall suggests  changing condition (a) to 7 > B(Pi) > 2 to solve the diagonal line problems in the Z S and H S C P algorithms.  Another parallel thinning algorithm which is based on weight values was described recently by Han et a l .  (50)  The weight values are the sum of the black pixels around the  tested pixel in a 3x3 window. The pixel is deleted if it satisfies certain conditions.  A n iterated parallel thinning algorithm that uses the 3x3 templates are implemented by C . Arcelli et a l .  (51)  The pattern is thinned down in an isotropic way using four passes per  iteration. The algorithm thins the pattern to its central lines. The thinned templates are as follows:  47  x__y 0  1 1_  x| y|1 | 0  J  l  I  0  0  y 1 y  O i l  0  1 1  0  0  x i x  I0I0I I  o__i__o_ i i  1  I  J)_J__o_ o IT o  1  0 0  I I I J  1  0  1  I0  i__o i "o~ o  where blank positions are "do not care" pixels, x and y are Boolean variables such that: (not(x) or y) = 1. Refer to L . L a m and C . Y . S u e n  (52)  for the study on the performance and  evaluation of 10 different thinning methods.  A n artificial neural network based on adaptive resonance theory ( A R T ) has been used successfully for thinning Arabic characters by Altuwaijri and Bayoumi.  ( 5 3 )  This thinning  algorithm clusters the data image, then the skeleton is generated by plotting the cluster centers. Finally, adjacent clusters will be connected by straight lines.  Our goal here is to implement a thinning system that is fast, rotation invariant, and can represent patterns by their central lines. The thinned pattern should be one pixel wide and should not have any discontinuity. Ideally the method should be invariant to rotation of the original pattern i. e. if the input is rotated by an angle 0 then the output is also rotated 0 by the same angle. W e relax the last condition to rotations of the original patterns by 90 , 1 8 0 ° , and 2 7 0 ° . W e have developed two knowledge-based thinning systems. The objective of the first system is to achieve a thinning system that can approximate patterns by their central lines, see Ahmed and W a r d .  (16)  The thinned pattern should be one pixel wide and should  not have any discontinuity. Several iterations may be used. Ideally the method should be invariant to rotation of the original pattern.  The second system uses the sequential thinning method. It is a fast knowledge based system that preserves  the symbol  connectivity, see Ahmed and W a r d .  shape ( 1 7 )  to some extent and also guarantees  the  This system has the advantage in that its rules are  applied in one sequential pass only, i. e. only one iteration is needed to obtain the thinned  48  image. This system can also be used to eliminate any unnecessary pixels in an image after thinning.  3.2 Good Thinning Characteristics Thinning reduces the binary image into one in which most dark pixels have one, two or three dark neighbors. A good thinning system should have the following characteristics:  •  It preserves and ensures the continuity of the symbol.  •  It preserves the shape of the symbol.  •  It preserves the end points.  •  It has the least possible number of pixels, however achieves the previous three  characteristics.  3.3 The Central Line Thinning Rule-Based System A s mentioned in section 2.2.1 a knowledge-based system is a computer program that performs a specific task normally done by a human expert. Knowledge based systems have the ability to manipulate problem statements and integrate relevant pieces of knowledge from the knowledge base using heuristic techniques. These systems are problem-solving computer programs that use their knowledge in flexible ways, and can reason with inexact knowledge which may be declarative or procedural. They have an inference engine for reasoning with rules and facts.  Prolog built-in features for backtracking, strong logic handling and rule manipulation have proved to be very helpful in implementing these systems. Prolog has the advantage of being a descriptive language; it solves the problem by describing it rather than showing how to solve it. The Prolog language is the most appropriate language for implementing knowledge-based systems. The C++ language has the advantages of being fast and capable of handling large documents.  49  The system should be able to draw conclusions about how the thinned output pattern was reached, and which rules were applied. The system should learn new rules if desired. Knowledge is distributed over the individual rules, which are independent of each other. An important goal is to establish an inference mechanism among these rules. A rule-based system for thinning that uses one parallel pass and 16X4 rules is introduced. O  O  O  o  The 16 rules are applied in the four directions 0 , 90 , 180 , and 270 . This results in the system being rotation invariant in these directions. The resultant thinned image is composed of the central lines of the image. The proposed method is an improvement of the ZS algorithm. The ZS algorithm requires twice the clock speed of our one-pass method, and the resultant thinned pattern may vary when the original pattern is rotated indicating that this algorithm does not always result in the central lines of the original pattern. Our system has 16 rules listed in Fig. 11. Rule 4  1  1  X  0  1  X  0  1  1  X  1  1  X  X  0  0  X  0  0  1  1  X  1  1  X  1  1  0  1  0  0  1  1  0  1  0  0  1  1 0  1  0  0  1  1  0  1  0  0  1  X  1  1  X  1  X  0  1  X  0  X  1  X  1  X  0  0  X  0  0  0  0  0  X  0  0  1  1  X  1  X  Then  ( X  Rule 7  X  0  0  X  0  0  1  X  0  1  X  0  1  1  X  1  1  X  0  0  0  1  1  0  1  0  0  1  1  0  1  0  0  X  1  0  X  0  0  X  1  0  1  X  0  X  0  X  0  0  X  0  0  0  0  0  0  0  0  1  1  X  Then  1  Rule 9  Rule  Then  10  1  1  1  1  1  1  1  1  1  1  1  1  X  1  1  X  1  1  X  1  I  X  1  1  X  1  1  X  0  1  1  1  X  1  0  X  0  1  1  0  0  1  0  1  X  0  0  X  0  0  X  0  0  X  X  0  0  X  0  0  0  0  X  0  0  X  ' 0 0  0  0  0  0  Then  1  Rule 13  Rule  Then  14  0  X  1  0  X  1  0  0  X  0  0  X  0  0  0  0  0  0  0  0  X  0  0  X  0  1  1  0  0  1  0  1  1  0  0  1  0  1  X  0  0  X  0  1  1  0  0  1  ' 0 0  X  0  0  X  1  X  X  1  X  X  1  1  X  1  1  0  X  1  0  X  1  1 X  Then  Figure 11 The thinning rules with 9 = 0 .  These rules aim at deleting the pixels which are north-west corner pixels or pixels that lie in the east boundaries or south boundaries. The conditions for 2-pixels thickness lines are given special attention. The conditions are listed in Fig. 12. The conditions are first  50  checked by the system before any rule is applied. If one of the eight conditions is satisfied, then the original 16 rules will applied without their rotations i.e. Only the 16 rules are applied and not the 16x4 rules. The pixel that will be deleted is marked by a darker square. Where 0 refers to a white pixel, 1 refers to a black pixel, and x is either a black or white pixel (i.e. don't care). This case will be referred to later in this section as shown in Figure 20.  0  Ul x  xJTlx  X  X  X  X  X  x \0\ x  X  X  X  X  X  X  X  x Q x  X  X  X | X  0 X  X  X  1  X  0  1  1  0  X  1  X  X  X  X  X  X  0  X  X  X  X  X  0  X  X  0  x  1  XX  0  X  X  X  X  X  X  X  X  0  X  X  X  X  X  0  X  1 X  X  X  X  X  X  X  1 X  X  X  X  1  X  X  0  0  X  1  X  X  1  Ix X  0  X  X  X  o  X  0  X | X  X X  T  X | X  -1  X | X  1*  X  X  Figure 12 The special case conditions relevant to 2-pixels thickness lines. A document that has English, Arabic, and Chinese characters as well as some geometric shapes is shown in Fig. 13. The thinned patterns resulting from applying the 16 rules are shown in Fig. 14. The rules are repeatedly applied to the patterns at every iteration until no further changes occur.  •  8r)Kcpv|/9  =o  • •  A B C D E F G HIJKLMNO P Q R S T U V W X Y Z 1 234 567890 abcdefghijklmn opqrstuvwxyz  Figure 13 The original symbols.  51  3/<^e  '2{^tw^UML^  ^  t  X  p  J 4  ^  ~ ^  L X  1  U  X  Y  X }l  \  ^ *^ , ^  i xl  ^  _ CL-3  < exop^vXa H h  \ / '  y  \  -  /  "^v^l  ^  X ^ ill — II ,  —  1  :DEFG A B C H 1J K L M N O P Q fRST UV wx Y Z 123 4 5 67 8 90 a b c d e f g h i j k l m n o p q r s ( u v v A / x y z  Figure 14 Thinning by applying the 16 rules with 8 = 0 The 16 rules listed in F i g . 11 are rotated by 90 , 180 , and 270 to produce 3 more sets of rules. The thinned patterns that resulted from applying each set of these three 16 rules are shown in Figs. 15, 16, and 17 respectively.  C  3Xte '2{j*xixefLajJ2f,  p  X  J^ *  I ft  >L  lxl  -  ^C  o  a *  £  >l  DEF  H IJ K C M MO P Q R S T  " A  . X  5 6  8r|KCp\j/B =cy  9 0  a b c d e f g h i j k l m n o p q r s t u v w x y z  Figure 15 Thinning by applying the 16 rules with 6 = 90 .  52  7 ^ '74j<u/&taoCcj  i  \} Z ^ »  \ / '  /  E F G H 1 J K LMN 0 PQRSTUV W X Y Z 1 2 3a 5 6 7 8 90  A B C D  abcdefghijklmn opqrstuvwxyz o  Figure 16 Thinning by applying the 16 rules with 0 = 180 .  DE F G HUKLMNO F Q R S T U V W X Y Z 123 4  A B C J " ^ o > l  i  & ^ C J  Y  \ \  < ^  ^ /  5 6 7 8 9 0  .  { exoC^vYoc H h * STJ Kicpvj/8 =o  _ C  V ^ -  1 — 1  a b c d e f g h i j k l m n  opqrstuvwxyz o  Figure 17 Thinning by applying the 16 rules with 0 = 270 . Although the results are good for the majority of the patterns, these figures show that as the 16 rules are rotated (which is equivalent to rotating the image and applying the original 16 rules), the resulting thinned patterns are not always the rotated version of the original patterns. Also, the thinned patterns that resulted from applying any of these sets of 16 rules set are not always the central lines of the original patterns.  Another method may use four passes in each iteration. In each pass the same 16 rules are O  0  applied but in the second, third, and fourth passes the rules are rotated by 90 , 180 , and  53  270 respectively. The thinned patterns that have resulted from this procedure, i. e. from applying four passes sequentially in the above order, in each iteration, are shown in Fig. 18.  A BC D E F G H 1 J KLMN 0 J ^ U >l \ \ ^ / P Q R S T U V ^ ^ L . \ / , W X Y Z 12 3 4 5 6 7 8 90 a  5 BTD^VACX H ((  1 —  or]KCp\|/9 =o  1  a b c c J e f g h i j k l m n o p q r s t u v w x y z o  o  o  Figure 18 Thinning by applying 4 passes (16 rules in each pass) with 0 = 90 ,180 , and 270 in second, third, and fourth pass, the 4 passes are repeated in each iteration. However, for this method, the order in which the rotated sets are applied affects the resulting patterns. Also, the resulting thinned patterns are not always the central lines. T o remedy the above problems we propose the following algorithm: W e use only one pass where the 64 rules (composed of the 16 rules and their rotated versions) are applied on every pixel in this one-pass. It is easy to show that if this method is used and the original o  o  o  image is rotated by 90 , 180 , or 270 the resultant thinned output will also be rotated by the same angle, i.e. this method is rotation invariant for these directions. Furthermore, the thinned patterns are always represented by their central lines but as Fig. 19 shows, when a pattern in any iteration is 2-pixels wide, there may be a discontinuity. The rules in Fig. 12 are used to solve the discontinuity problem.  54  Figure 19 Thinning by applying 16X4 rules in each iteration without testing for the special cases of 2pixels thickness lines. The central line of 2-pixels thickness line lies between these two pixels. Therefore, the central line can approximately pass through any of these 2 pixels. When a pattern is formed which is 2-pixels wide in any direction, we modify our procedure and we only apply the original 16 rules and not their rotated versions. Thus, the modified system first checks if the pattern at the pixel of concern is two pixels wide. If this is true the 16 rules are applied otherwise the 64 rules are used. The thinned patterns that have resulted from this modification are shown in Fig. 20. The conditions a pixel should satisfy to be considered to belong to a 2-pixels thick line are listed in Fig. 12. Fig. 20 shows that our method results in the central lines, which are connected (no discontinuity) and are rotation invariant.  55  k  -  d  If  ^  ^ £  l Y i ^  '  , C  A BC D E F G H 1 J K1M N O 1 1 1V 1 1 " P Q R SGGV ' v \ / • W X Y Z 1 2 34 5 6 7 8 90  i  1  >-  < -  >  ( eTUC/dvXa H h (  OYK.Cp\[/B  =o  S"T^  1I  KJ  1  \  J  ^  _  a b c d e f g h i j k l m n  ~ "  opqrstuvwxyz  Figure 20 Thinning by using our new developed system which uses a parallel one-pass 16X4 rules and testing for the special cases of 2-pixels thickness lines.  The following example shows the different iterations to thin a symbol. It took four iterations by using our central thinning algorithm to thin the symbol ' A ' .  The system peels off the boundaries until the objects are reduced to thin lines of one pixel thickness.  Another example is shown in Fig. 21. The original pattern is shown in Fig. 21 (a). The pattern after applying the 16 rules without rotations is shown in Fig. 21(b) where the deleted pixels are shown in black. Notice that the east and south boundaries are deleted, the north west corners are also deleted.  When the 4x16 rules are applied, all the boundary pixels are deleted as shown in Fig. 21(c). The next iteration is shown in Fig. 21(d). After few iterations the pattern is thinned to the central lines as shown in Fig. 21(e).  56  (e) Figure 21 Step by step thinning. W e can also show that the ZS algorithm outlined previously can be derived using the same rules shown in Fig. 11 that we have developed for our thinning algorithm. Rule 3  should be changed to rule 3-  and rule 14 should be changed to rule  444  The main difference between the Z S algorithm and our algorithm is that the Z S algorithm requires two passes in each iteration and our algorithm requires only one pass in each iteration. The first pass uses the 16 rules (with rules 3- and 44 instead of rules 3 and 14) O  0  with 6 = 0 and the second pass uses the same 16 rules with 0 = 180 . After changing rules 3 and 14 as described above an exact equivalence of the Z S algorithm is obtained. The ZS algorithm has problems of reducing 2-pixels wide 45 ° and 0  135  diagonal lines to just 1 or 2 pixels see Fig. 23(b). T o address these problems we can  58  show that if our rules 3 and 14 are used instead of rules 3-and 44, then these problems are solved. The thinned patterns that resulted from using the Z S algorithm are shown in Fig. 22. The patterns which are not thinned properly using the Z S method are shown in Fig. 23(b). These patterns are better thinned using our new rule based system as shown in Fig. 23(c).  i C l ^  1 3  { -  )  ~  \ eioc^vAa n h (  orjKCpii/0  =o-  _ S-r^  1 — 1  A B C DE FG H J K L M' M 0 P Q R S T GG W X Y Z 1 2 34 5 67 89 0 abcdefghijklmn opqrsfuvwxyz  Figure 22 Thinning by using the ZS method.  (a) (b) (c) Figure 23 Thinning: (a) an image, (b) by applying the ZS method, and (c) by applying our developed parallel one-pass 16X4 rules.  3.4 Edge Detection One-Pass Sequential Thinning Most of the knowledge in any digitized pattern is contained in a small fraction of pixels. These pixels are mainly formed of the central lines of the patterns. However, many iterations are required to determine the central lines as explained in the description of the  59  previous system. As an alternative to thinning the symbol to their central lines, we suggest to represent the symbol strokes by their edges. Our goal is to determine pixels in a symbol that can be used for the purpose of identifying this symbol. We introduce an algorithm that produces 12 different outputs, the edges of the symbol. Generally, one output will be sufficient to identify the symbol, however, more than one output can be requested. This method also has the advantage of speed. Our algorithm requires only one iteration to thin i.e. represents the symbol by its edges. However, there may be more than one edge in a stroke (e.g., for a thick straight line there will be right, left, top, and bottom edges). Thus, we shall represent the stroke by one (or more) of these edges. A knowledge-based system that detects certain edges of the symbol is developed. There are different outputs depending on the processing direction and the rules that are selected by the user. The user will select the edges of concern (e.g. left top, right top, left bottom, right bottom) which depend on the processing direction. The user also selects the degree of having branches (3 degrees), low number of pixels, medium number of pixels and large number of pixels. The system rules guarantee the connectivity, hence can be used for eliminating any extraneous pixels resulting from using other thinning algorithms. 3.4.1 System Performance Five different symbols are shown in Fig. 24. Processing each line of the pattern (pixel by pixel) in the direction going from left to right and top to bottom will preserve the right and bottom edges as shown in Fig. 25. Alternatively, processing the pattern from right to left and top to bottom will preserve the left and bottom edges as shown in Fig. 26. Similarly, processing the pattern from left to right and bottom to top will preserve the right and upper edges as shown in Fig. 27. Processing the pattern from right to left and bottom to top will preserve the left and upper edge as shown in Fig. 28.  IBAHB Figure 24 Different symbols  60  B A H B _BAHB  BAHB  (a) (b) (c) Figure 25 Symbols processed from left to right going from top to bottom and concerning: (a) a large number of branches, (b) a medium number of branches and (c) a small number of branches.  L B A ; HR _ B A H B  BAHB  (a) (b) (c) Figure 26 Symbols processed from right to left going from top to bottom and concerning: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches.  BAHB "B^HB  BAHB  (a) (b) (c) Figure 27 Symbols processed from left to right going from bottom to top and concerning: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches.  r & A : HR  HB  BA H B  (a) (b) (c) Figure 28 Symbols processed from right to left going from bottom to top: (a) a large number of branches, (b) a medium number of branches, and (c) a small number of branches.  It is usually desired to have a small number of branches in the output pattern (Figures 25(c), 26(c), 27(c), 28(c)), however, some strokes may vanish as shown above for the letter A .  It is possible to remedy this problem by superimposing the results from two different directions. The first direction is processing the pattern from top to bottom and from left to right. The second direction is processing a copy of the original pattern from top to bottom and from right to left. Then, a union of the two outputs will have the following image:  61  . Generaly, the selected thinning method depends on the application.  X1X X XX  0  51  XX11 XX 0  0  «  X XX Xi101 \  XXX1X0 X01  XX11)XX XI)X  XX XX XX  0X1(X11XXX  (X10XXXX  0  fXi XX0XX \  ]  0 ]  (.)  ]  1  Figure 29 The sequential thinning rules.  3.4.2 Explanation of the Rules The system has 12 rules listed in Fig. 29. The rules are applied to the pattern in a specific order (rule 1, 2, 3 and so on). Rule 1 prevents the system from creating unnecessary holes. The rules that preserve the connectivity are rules 4, and 7 through 11. The rules that preserve the shape and the end points are rules 2, 3, 5 and 6. Finally, rule 12 deletes the pixel if none of the previous rules are applied.  62  Rule 4 describes the pattern  X  X  X  0  1  0  X  X  X  where the middle pixel should not be deleted in  order to maintain the connectivity. For this pattern, only if we have X  X  X  0  1  0  0  0  0  0  0  0  0  1  0  X  X  X  or  we could delete the middle pixel without losing the connectivity. The last two conditions (patterns) must be checked before applying rule 4, they are described by X  0  X  X  1  X  0  X  rules 2 and 3. Similarly, rule 7 describes the pattern I  I  X  I  I where the middle pixel  should not be deleted in order to maintain the connectivity. For this pattern, only if we have these conditions  0  0  X  X  0  0  0  1  X  X  1  0  0  0  X  0  X  or  i  0  1  1  1 we should delete the middle pixel without losing the  connectivity. W e have to check the last two conditions (patterns) before applying rule 7; they are described by rules 5 and 6. Consequently, rules 2, 3, 5 and 6 (shown in Fig. 29) are responsible for the number of branches (extraneous pixels) in the output pattern. Each of these rules has two shaded squares. If we replace one of these shaded squares by x (don't care), we will get thinned symbols that have a lower number of branches (strokes). If we replace both shaded squares by x, we will get thinned symbols that have an even lower number of branches (strokes). Hence, the system, produces three outputs. Rule 8  addresses the pattern  1  0  X  0  1  X  X  X  X  where to maintain the connectivity, we can not delete the  63  middle pixel. Rules 9, 10, and 11 are similar to rule 8. Finally, rule 12 deletes the middle pixel if none of the previous 11 rules were applied.  Some symbols before thinning are shown in Fig. 24. The symbols after thinning and without changing rules 2, 3, 5 and 6 (i.e. having ones in the shaded squares) are shown in Figs. 25(a), 26(a), 27(a) and 28(a). The symbols after thinning and changing rules (3, 4, 6 and 7) by having one x in either one of the two shaded squares are shown in Figs. 25(b), 26(b), 27(b) and 28(b). The symbols after thinning and changing rules (3, 4, 6 and 7) by having two x in the shaded squares are shown in Figs. 25(c), 26(c), 27(c) and 28(c). W e conclude that the processing direction and the selected rule method will affect the results to some extent. One of the advantages of our knowledge-based system is that we can determine which output is correct, and what rules are suitable for each application. The default scanning method processes the pattern from left to right, going from top to bottom. The default thinning rules (2, 3, 5 and 6) are the ones that have one don't care in the shaded squares.  3.5 Results A document that has Arabic, English, and Chinese characters is shown in Fig. 30. The document after thinning by using the developed central line rule-based system presented in section 3.2 is shown in Fig. 31. There are extraneous pixels in the resultant image. A n extraneous pixel is a pixel whose deletion will not affect the continuity of the thinned pixel and it has more than one neighbor black pixel (i.e. it is not an end pixel). These extraneous pixels are located in special positions. Examples of these pixels are as •  •  • • • • •  follows:  a r  " ^ :  *  • • •  *  . The extraneous pixels can be deleted from the thinned  image by applying our sequential thinning algorithm (processing from left to right going from top to bottom and having a large number of branches) discussed in the previous section. The resulting thinned patterns after deleting the extraneous pixels will be •  •  +  *  . Fig. 32 shows the document (shown in Fig. 31) after deleting  the extraneous pixels. 64  3.6 A C o m b i n e d T h i n n i n g M e t h o d In section 3.3 we have discussed our novel parallel thinning algorithm. In section 3.4 we have discussed our new sequential thinning algorithm. In order to take advantage of both methods, we apply the parallel algorithm first, then we apply the one-pass sequential thinning algorithm to remove the extraneous pixels. The developed combined method has proved to be useful in thinning different symbols including Arabic characters in a database Kharma et a l .  T  3  ( 5 4 )  1SJ 51% m HI  1  i f IS)  Figure 30 A document that has Arabic, English, and Chinese characters.  65  >  cb  ro  5 ^  A _  /i^Ti c o = ffl  411  B  PI 3  fee  >"1  DcqR  FL.OwerCHLD (a)  Figure 31 (a) The document after thinning using the developed one-pass 16x4 rules parallel method, (b) part of the image is enlarged.  66  d y t . ^ j 4_U JJ I Lc u  JJ | J ysjC^—.  dUS ^  dJ I ^j—i, j'L*,Lo \  L r  ,\  - \  "B  i s  PLOWOTHLD t - e . a c H e . R  (a)  Figure 32 (a) The document shown in Figure 31 after removing the extraneous pixels by applying the one-pass sequential thinning algorithm, (b) part of the image is enlarged.  67  3.7 The Speed of the Developed Thinning Algorithm Using C++ running on a 120 M H z Pentium PC, the fast one-pass sequential thinning algorithm (discussed in section 3.4) thins the symbols in the document shown in Fig. 30 in 2 seconds. Our central line algorithm (introduced in section 3.3) thins the same symbols in 3.18 seconds. On the other hand, using the ZS algorithm, the system thins the same symbols in 6.21 seconds. The document size is 480 x 576 pixels (12.66 x 15.24 centimeters). All the symbols including the thick upper part of the frame in the document (Fig. 30) were thinned and the width of that part of the frame is 20 pixels. For all parallel thinning algorithms, the speed of thinning depends on the maximum thickness of any part of any symbol in the document. For example, if the thick part of the frame shown in the top of Fig. 30 were not included in the document, then our central line rule-based system thins the document in 2 seconds (instead of 3.18 seconds). We have performed experiments to find the relationship between the speed of thinning using the central line method and the thickness of the widest part of any symbol in a document. The results show that this relationship is almost linear. A n example of this relationship is shown in Fig. 33 and table 2.  i—  o -I  1  1  20  1  1  40  1  60  80  Thickness Figure 33 Thinning of symbols that have different thickness. Thickness in pixels time in seconds  20 3.13  40 6.26  60 9.72  80  13.9 Table 2 Thinning speed versus the maximum thickness of a symbol in a document of size 480 x 576 pixels.  The speed of thinning symbols in a page, for example page 69 in this thesis is 2.2 seconds. The speed of thinning the first line in the same page is 0.38 second.  68  3.8 S u m m a r y A novel rule-based system for parallel thinning is implemented in this research. The system has 16 rules. These rules and their rotated versions are applied in parallel on every pixel in each iteration. The number of iterations depends on the maximum thickness part of the pattern. The resultant thinned pattern is formed of the central lines of the pattern. Moreover, as the original image is rotated in four directions, the resulted thinned image is also rotated in the same directions. Experimental results show that the developed method is very fast, effective and solves some of the problems inherent in the ZS algorithm.  A novel fast sequential thinning algorithm is also presented. The later method can be used to detect certain edges of the symbol. These edges depend on the processing direction and the selected rules (three options that determines the number of branches). This system is very fast and needs only one pass and one iteration. It has 12 independent thinning rules that preserve the connectivity and the shape of the symbol to some extent. This system also has the advantage that it eliminates extraneous pixels in any symbol that has been thinned by another thinning algorithm.  Extraneous pixels are pixels whose  deletion will not affect the connectivity of the thinned symbol and they pixels are not end pixels.  A combined thinning system that uses the central lines parallel thinning method followed by the fast sequential thinning algorithm are shown to be effective in producing thinned symbols which was represented by their central lines and have no extraneous pixels. The combined system is used in the thinning stage in our developed O C R algorithm, see next chapter.  69  Chapter 4 T h e D e v e l o p e d System In this chapter, a novel expert system for symbol recognition will be described. The system is used for a general two-dimensional bi-level symbol analysis and recognition. The system uses the structural pattern recognition technique for modeling symbols by a set of straight lines referred to as line segments. The system rotates, scales and thins the symbol, then extracts the symbol strokes. The pixels in these strokes are represented by a chain of codes in eight directions. Finally each stroke is transferred into segments. The system is shown to be able to map similar symbol styles to the same representation.  A system that has learnt an average of 97 models per symbol, using a low threshold (radius = 15), was tested with 5726 handwritten English characters, was resulting in a recognition rate of 95% and rejection rate of 16.1%. The tested data were all the test data (binary  one)  taken  from  Recognition ( C E D A R )  the  Center of  database.  When  Excellence  for Document  the threshold is  100  Analysis and  (radius =  100),  the  recognition rate was 87.6% and the rejection rate was 0%.  The recognition rate of our system can be increased by simply storing more models for each symbol or by increasing the rejection rate. The system is capable of learning new symbols by simply adding models for these symbols to the system knowledge base. The system is implemented by using the C++ language and is running on the 120 M H z Pentium P C .  4.1 I n t r o d u c t i o n A new general structural pattern recognition system was developed.  (15)  While successful  existing pattern recognition methods are designed for a specific application e.g. Chinese symbols, or Arabic numerals recognition, our system is general in that it is designed to recognize any symbol whether it is an English character, an Arabic numeral, or languageindependent, e.g. an electrical symbol.  70  Our system has the following characteristics: it describes the symbol itself by models. It does not use syntactic grammars but rules to rotate, scale, thin, and model symbols. One advantage of our system is that it has the capability of recognition even when few model samples are used. It measures the similarities as well as the differences between the representation of the symbol to be recognized and those of the stored models. Our system can justify its answer. Another advantage is that if a new symbol is added, our system can easily be updated by simply adding the models of the new symbol to the  system  knowledge base.  Our system uses different stages for analyzing and recognizing symbols. Each stage reduces the symbol details until the symbol is described by one or more representation which contain the most necessary knowledge needed to enable the symbol recognition. Not many models of a symbol are required to achieve high recognition rate. These models are stored in the system knowledge base.  4.2 T h e D e v e l o p e d System Pattern recognition problems and chess problems are quite similar in that there is no unique solution. Methods of artificial intelligence can be applied to solve these kind of problems. Expert systems are the most suitable tools for implementing structural pattern recognition techniques because there is no exact solution for the pattern recognition problems. People use their expertise to recognize patterns. Complex patterns can be described in terms of simpler ones and simple patterns are described by sub-patterns. Expert systems help solve difficult pattern recognition problems. More rules and human experience can be added easily using rule-based systems. Hence, the system performance could be improved without rebuilding the system.  As  mentioned  above  an expert  system  for two-dimensional  symbol analysis  and  recognition is developed. Our system is a general method for recognition of bi-level symbols. Our system is not application-specific and can be used for the recognition of any symbol. These include the recognition of mathematical symbols, electrical circuit symbols, and characters such as English, Chinese, Arabic, etc.  71  The basic idea behind our system is that a symbol can be constructed from smaller components. Here, four basic components are used. These components are the horizontal O  line ' — ', the vertical line ' I ' , the 45  0  diagonal line ' /' , and the 135  diagonal line '  V. These components are from now on referred to as line segments. The system transforms the symbol into a set of line segments. A l l these segments have the same length (in pixels). The symbol area is partitioned into square zones all of the same size. In every zone one of 16 possible configurations of segments is allowed. Fig. 34 shows the 16 different allowed configurations (including the empty zone).  ••••••  Figure 34 The 16 possible images in a zone of 10 xlO pixels. A symbol can be handwritten in a lage number of different ways in the same space. Our system maps this enormous number of different representations of a handwritten symbol to a smaller number of possible representations. W e partition the symbol into a number of square zones. There are 2  ( L x W )  possible symbols for an image that has W pixels in width  and L pixels in length. W e map this large number ( 2  (LxW)  ) of symbols to just 16  N  = 2  4 N  symbols, where N is the number (integer) of zones used to model the symbol. This is achieved by allowing a limited number of sub-symbols in a zone as shown in Fig. 33. A s an example, consider a symbol in an 10x10 pixels area which is partitioned into one zone (N=l), L=10 pixels and W=10 pixels. For this zone there will be 16 shown in Fig. 34 instead of 2  1 0 0  1  allowed symbols as  possible one. A s another example, assume that a symbol  is written within a 30 x 20 pixels where each zone is 10x10 pixels. This area will have 6 zones. Since each zone has 16 possible sub-symbols, there are 16 allowable models 6  instead of 2  6 0 0  possible ones. As an example, consider the letter ' B ' . One possible model  72  for the letter ' B ' is  zones are  The top two zones are  I, the middle  , and the bottom zones are  model has 2 zones in each row and 3 zones in each column.  i.e. the Our system stores the  models as vectors in the system knowledge base. When a symbol is presented to the system for recognition, the different steps that the system performs are shown in Fig. 35.  An input symbol Rotation Scaling Thinning  Transforming the symbol to strokes Representing the strokes as a chain of codes  Apply the mapping rules to transfer the strokes to segments (straight lines)  Final representation as vectors  Figure 35 The structural pattern recognition steps. After rotating, scaling, and thinning, the system decomposes the symbol into strokes. After that, each stroke is decomposed into short straight lines (segments). A vector is used to store these segments and to represent the symbol. The distance between two  73  vectors enables the system to measure the differences and similarities between the two symbol representations.  4.2.1 The Rotation Stage The objective of the first stage is to adjust tilted symbols. Symbols may be written or drawn tilted in different directions. This problem is solved by rotating the symbols. The central point (defined below) is considered as the origin of the symbol. The symbol direction is considered to be zero when its principal axis (defined below) is vertical (or having a multiple of 20  0  to the vertical direction). Each symbol will be rotated (by an  o  angle < 20 ) around its central point until the symbol direction, i.e. its principal axis, is at a certain direction which is vertical or having a multiple of 20  0  to the vertical axis.  a) The Central Point The physical concept of the center of mass refers to that point in an object that has the same amount of matter around it in any direction. If the origin for the entire image is considered to be the pixel at location (0,0), then the center of mass of an object C is (Cr, Cc) Where C r = 1/n S x, C c = 1/n X y for an n x n image.  b) The Principal Axis The principal axis of a bi-level object is a line passing through the object's center of mass having a minimum total distance from all pixels belonging to the object.  4.2.2 The Scaling Algorithm Scaling by reducing the symbol size is useful for mapping some of the  different  handwritten styles of the same symbol to the same representation. A straight line  and  representation  lines  with  some  deformation  will  have  the  same  after scaling them to a certain length. Consequently, this can be  useful if the above three lines represent the same symbol.  74  There are two types of documents. The first type includes documents that have symbols of similar sizes (such as documents of English text typed or printed by a machine). The second type includes documents that have symbols of different sizes (such as documents containing graphs, mathematical symbols, electrical circuit elements and handwritten text).  If the document has symbols of similar sizes, our system will scale the symbols so that all the symbols have the same dimensions. The new dimensions of the symbols may be selected by the user or defaulted to 32 pixels width and 48 pixels height symbol. The new dimensions are usually smaller than the dimensions of the symbols in the original document. For the case of a document that has symbols of different sizes, the new dimensions of each scaled symbol will also be the same for all symbols but these dimensions will determined by the program. Hence, the system will automatically choose certain values for the symbol height and width. Examples of these values are 32, 48, 64, 72, or 96 pixels for each of the width and the height. The new symbol dimensions are determined by the following algorithm: Let st = 16; if (old_height < st) then new_height = st;  if (old_height>=st+(i*d) & & old_height<st+((i+l)*d)) then new_height = (i+2)*st; A symbol height (or width) less than 16 will be mapped to 16. A symbol height (or width) between [16, 96] will be mapped to 32, and between [96, 176] will be mapped to 48, ... The value of d determines the mapping size; in our program it is set to 80. Using a large value of d will map more heights to the same height.  Scaling i.e. reducing the symbol size, usually deletes some of its details but keeps the global shape, this tends to increase the opportunity of matching the considered symbol with the stored models. However, when the information in the small details is of relevance then reducing the symbol dimensions will decrease the opportunity of correct matching. Hence, the choice of the new symbol dimensions is important.  75  Assume that the document contains symbols with different symbol sizes. After rotation, the system scales the symbols to some predefined size (as mentioned above). The scaling algorithm is described by the following steps:  1.  For each symbol, create a new empty (generally smaller) image with the predefined dimension values.  2.  Find (Sr,Sc), the row and column scale values as the ratios of the original and the new symbol dimensions.  3.  Use a sliding window of size (Sr,Sc) on the original symbol to determine the gray level of each pixel in the new symbol image. The window used to transform Fig. 36(a) to Fig. 36(b) has (Sr.Sc) = (2.28,1.31), the original dimensions are (73,42), the new ones are (32,32).  4.  The new grey level value of a pixel in the scaled version is equal to the area of all ink (black) inside the window (normalized by the area of the window) in the original version, thus it is a value between 0 and 1 inclusive.  5.  Since the obtained new value of the pixel according to the previous algorithm falls between 0 and 1, we use a threshold value ' T h ' to determine whether the final value of the pixel will be black or white. If the calculated value > T h , the pixel will be black otherwise it will be white. Possible values of the threshold are in the range [0,1]. Experiments show that a value for T h = 0.2 is a good choice. Results when using threshold values of 0, 0.2, 0.6, 0.8 and 1.0 are shown in Fig. 37. If the original symbol is thin, using a high threshold value may cause discontinuity. However, if the original symbol is not thin, all values between [0,1] can be used.  Increasing the threshold  value tends to thin the pattern but preserve its shape.  76  (d)  (f)  (e)  Figure 36 A symbol after scaling to different dimensions and using a scaling threshold = 0.2: (a) the original symbol, (b) 32X32 size, (c) 48X32 size, (d) 24X16 size, (e) 8X8 size, and (f) 8X4 size.  ft  ft  ft  ft (a)  ft  (b)  ft  (c)  (d)  ft  (e) (f) (g) Figure 37 Scaling a symbol with different scaling threshold values and using 32x32 size: (a) the original symbol, (b) threshold = 0, (c) threshold = 0.2, (d) threshold = 0.4, (e) threshold = 0.6, (f) threshold = 0.8, and (g) threshold = 1.0.  4.2.3 The Thinning Algorithm Thinning, as discussed in chapter 3, is the process of reducing the thickness of each line of patterns to just a single pixel. The thinning algorithm that has been developed and described in the previous chapter has been used. Alternatively, any other effective thinning algorithm can also be used. Using our thinning method will have the advantages of better speed and rate of recognition. In addition, less models will be needed when using our thinning method.  77  4.2.4 Symbols Representation The objective of this stage is to represent a symbol by a vector. The length of the vector is proportional to the details required to describe the symbol. Similar symbols will be closer to each other in the N-dimensional space.  After thinning, each symbol is described by its strokes. A stroke is a sequence of pixels that starts and ends at special pixels. A special pixel is a pixel that has three or more neighbours or exactly one neighbour. Each special pixel is marked by the letter ' A ' as shown in Fig. 39(e). After marking all the special pixels, the symbol is decomposed into strokes. Then, each of the unmarked pixels in every stroke is marked by a code (an integer number that takes a value between 1 and 8 inclusive); the code in each directions is shown in Fig. 38. The code indicates the direction between the present pixel and the following one. The marked pixels are shown in Fig. 39(f).  LU  Figure 38 The different direction possibilities. After isolating the symbol strokes and marking each pixel by a code Fig. 39(f), a set of rules is applied to each symbol stroke to transfer it into segments (straight lines), each of fixed length. A l l segments have the same length in pixels. Depending on the chosen length of the segments, a stroke may be converted to one or more segments or may vanish. These segments are the symbol primitives. A vector of the primitives will be used to represent the symbol. Using shorter segments to represent a stroke preserves all details of the stroke, including unnecessary ones, while using long segments may delete important details. However, if very short segments are used then many more stored models will be needed.  78  ft  ft (a)  (b)  fl  (c)  (d)  1 1 1 A A A 1  (e)  (f)  Figure 39 Processing of a symbol: (a) A symbol, (b) after rotation, (c) after scaling, (d) after thinning, (e) after marking the special pixels, and (f) after isolating the symbol strokes and coding each pixel.  The use of different segment lengths (2 through 10 pixels) is shown in Fig. 40. The rules used to represent a stroke by segments are described in the following section.  79  fl  fl  (a)  fl  fl  (b)  (c)  ft  ft  fl  fl  (d)  (e)  -R  +1  (0 (g) (h) (i) (j) Figure 40 Different mappings of a symbol by using different segment lengths of: (a) 1-pixel, (b) 2pixels, (c) 3-pixels, (d) 4-pixels, (e) 5 pixels, (f) 6-pixels, (g) 7-pixels, (h) 8-pixels, (i) 9-pixels, and (j) 10 pixels. 4.2.5 T h e System M a p p i n g Rules In this section, we will see how different styles for a symbol, for example the letter ' A '  A are all mapped to  AA  A  A A  A  i.e. to  the same representation.  We will show how we transfer each stroke into one or more segments. A l l of these segments will have the same length T . In forming a segment, consecutive pixels are processed one at a time. T o form a segment of length T pixels, T or more pixels are processed and converted to a segment (except at the end of the stroke, where T/2 pixels are here sufficient).  A set of rules that map a symbol stroke into segments of fixed length T is developed. T o find the direction of the line segment, the consecutive pixels of each stroke are analyzed pixel by pixel. For each pixel, a certain probability is assigned for each of the eight possible directions. Then, the sum of the probabilities over the previous pixels and the present one is calculated for each of the eight possible directions. If one of these sums exceeds the threshold value ' T ' (the segment length), then, a complete segment is formed and the segment direction is assumed to be the direction of that of the largest probability  80  sum. Next, the same analysis for the remaining pixels in the stroke continues so as to form new line segments and so on. For the remaining pixels between the end of the last formed segment and the end of the stroke, if any of the eight values exceeds half the value of the threshold it will be considered as a segment otherwise, no segment is formed. The following algorithm describes the mapping rules in more detail:  1.  Select the segment length e.g. 10 pixels, which is the same as the threshold ' T ' .  2.  Find the code for every pixel of the stroke as shown in Fig. 38.  3.  Consider the first pixel after the special pixel of the stroke.  4.  For i =1 to 8, initialize the eight directions that the segment can take s[i] to 0.0 .  5.  Assign a probability 1 for the direction of the considered pixel, a probability 0.7 for its 2 adjacent directions, a probability 0.49 for the next two adjacent directions, and a probability 0 for the remaining directions. For example if the code of the pixel is 5 then p[5] = 1, p[4] = 0.7, p[3] = 0.49, p[6] = 0.7,  p[7] = 0.49, and p[2] = p[l] = p[8]  = 0. These probabilities were determined experimentally. For i = 1 to 8, update s[i] by adding the new p[i] to the old s[i].  6.  Calculate the maximum of s[l],  s[8], if it is greater than or equal to the threshold  ' T ' then we form a segment of length T pixels in that direction. The length of the segment formed is always equal to T pixels. Then, consider the next pixel of the stroke, and go to step 4 to process the remaining pixels of the stroke.  7.  If the end of the stroke is not reached, consider the next pixel of the stroke and go to step 5 (note that each of the s[i] is still less than 'T').  8.  At this point, the end of the stroke has been reached. Determine the maximum of all of s[ 1] through s[8], if it is greater than or equal to half of the threshold ' T ' , then form a segment in that direction.  9.  End of a stroke analysis. The result is a new stroke consisting of segments (straight lines), each has one of 8 directions.  81  10. After processing all the symbol strokes and finding all the segments, the segments are grouped so that each group corresponds to one of the 16 zones shown in Fig. 34.  11. The number of zones in each row and column will be determined and each zone shape will be determined as one of the 16 zones shown in Fig. 34.  4.2.6 The System Models and Recognition Models for each symbol are stored in the system. Each model is represented by a vector that defines the contents of the different zones of the symbol. The number of zones is determined by the prior choice of the segment length T (straight line). The model vector contains the number of zones in each row and each column, and the total number of zones followed by a series of integers. Each of these integers  (0 through 15) represents  one of the 16 possible segment images (shown in Fig. 34). Our system can use one of two methods for constructing the models. The first method uses training to extract the models. In the second method, the human designer constructs the different shapes representing the symbol, i.e. for each fixed number of zones in a row and column, the different possible representations of the symbol should be found. Then, these models are stored as vectors in the system knowledge base. In our present implementation, we used the second method but we did not include all possible representations for each symbol. The number of zones in each row ranges from 1 to 8, similarly, the number of zones in each column ranges from 1 to 8. The size of any zone in the models is irrelevant as we only need the shape of its content for later comparison with the vector representing the symbol to be recognized. The symbol to be recognized is compared with the stored models with the same number of zones in a row and column.  Models that use a large number of zones are suitable for representing symbols that have small strokes as in the case of most Arabic characters and electrical symbols. For symbol with short strokes, it is more appropriate to use short segments (i.e. a large number of zones). This, however, will increase the number of models necessary to represent the symbol. In the ultimate case, when using a 1-pixel length segment, the number of  82  possible representations of a symbol will be enormous and equal to that of all the possible combinations of writing the thinned symbol, which is impractical.  In this work, as mentioned above, we used the second method for constructing the system models with the guide of the first method. In our present implementation, an average of 97 models for each symbol was used. Some models are shown in Fig. 41. The first model for the letter 'a' is of size 2x2 i.e. two zones in each row and two zones in each column, a total of four zones.  83  FH  a a.-  aj  3:  p;  b v.  F  A  rr  Fii  s;  !^  FF  1;  re  ns;  FV  i^j  raj  ra:  a:  a:  r&j  F,:  V. s  b:  y;  B:  E  E  H:  H-:  F>  CJ  E  0  SJ  CJ  CJ  E  :^ri  Hi  E"  i*i  CV  HF  aj  a:  F:  :* c  ;  E  &  r;  E  E  &  EJ  <c  E  E  Fi  £  E  E  F-:  E  i>:  H:  C F  cc  d  *  e  c  E f  E  F  :-F  FT:  HF  E  Fi  99  3;  5  ;3i  E>:  K  9:  a:  Si  g:  h  *  i*  F.  E  H;  X:  k  H  HH  H;  FH:  i  h+ m nr '£\  u: w:  I  I  sr  I  J *  j:  k *  K  ;  £  L ^ !ri m ro; ^ V77. 777. n •sr.~SS.ns N • * > • • ite ^ ; z;  :  n :  P  r-  5  q9 * r b v.  n n:  r  s;  s5 ^ H- : 1  V v.  ^F  ij>  a:  Fi  E  fr.  fH  HH  E  y-  LJ_  <  r>K  rn  rss. /->:  m:  rE  i~:  FJ:  E  [TF  f:  n:  fi:  ^:  fH:  a: FH  <?•  FT:  m  V:  F:  :i:  r  F  fi  H  F  y  b:  y;  •j  E  s  tr  iTi  iTi  E  k ;  ifi  *i  t ^ u  F.;  ^H:  ii  u: E  :  s:  rr  -r-  :~F  Fi  L_J :  HVi  F*  u;  -  u:  ^:  i,  v.\  Fi  KK.  w.  fs:  LU :  x if: y if: oO  * in: a;  Y:  it:  s:  i-H:  •:  ii  •M;  •A\  t> n:  q:  i; z_  z=  ru  : ru  iHJ  W  1  N:  >r s>:  1 ,: 5  B8^  E,;  -Of Fti  £t-i  J*H  >e h^i  Ci  r  4- *  Lif:  *  #  :  3 *  4* 6 f 7 *  #i  $:  nfi _a: JS: a: :  3  I  Hi  V:  HF  F  S:  S:  *7:  ^  Fi  n *!  :  Br  ?fi  rr,:  sii:  fT:  h<  E;  ' i i~i :  s^:  ;-f?ii -Si *:  Fv  F>:  &:  f^  ^ .  LC*  ^  fiS:  :  h^i It;  ^ !  -fl:  ^ :  F4=: ^  it:  3i  i^  ;  ^;  k'  E  i  3i  L  m:  i^  ii  i^:  . 1...  J5: i:  L3:  H4J  b:  6:  :Ti:  Fi?:  Figure 41 Some models used by the system and the number of models used for each of these symbols.  84  Ideally, the stored system models should include all possible shapes for each symbol. The length of the segment controls the detail descriptions of the symbol. Using long segment length, hence few zones (such as 2x2 or 2x3) result in a fewer number of models for a symbol, but may not preserve some important symbol details. On the other hand, using short segments (hence, many zones such as 4x5 or 5x5) to model symbol will preserve the symbol details but results in a large number of models.  The system models for different symbols are shown in Fig. 41. These models include  Latin letters, digits 0 to 9, the electric symbol for a diode  , the Arabic digit  r  , Arabic letters In our present implementation, for each input symbol to be recognized we use three representations (vectors). Each vector corresponds to using segment length T equal to 6,10, or 14 pixels. Depending on the segment length T used, each tested vector will have a certain number of zones in each row and column. Each vector will only be compared to the stored model vectors which have the same number zones in each row and column. The distance between the input vector and the stored vectors is calculated by comparing each zone in the input symbol vector with the corresponding zone in the stored symbol vectors. If there is a missing or extra segment, then there is a distance equal to the length of a segment. The total distance between two models is the sum of the total length of mismatching segments.  Finally, the stored vector which has the minimum distance with the input vector will be selected as long as the minimum distance is less than a certain "rejection" threshold. If the minimum distance is larger than the threshold then the system rejects the symbol as unrecognizable (the symbol does not correspond to any of its stored models).  In case of  a tie, the model with the larger number of zones (i.e. with more details) will be chosen.  Some models for the character ' A ' are shown in Fig. 42. The complete models that are used by the system are included in Appendix I.  85  R  FT-  fi:  R\  Bi  H:  /fli  xX  xr  /x  F T  -n;  m  rx n:  i  n! m; ^  R-i  FX  HX  ri;  ^  *  fX  XH  -ri:  Fl:  /R  A  R;  FI  ^  3 ; ^1  ft  Figure 42 Some models used by the system for the letter A.  4.3. Results A s mentioned above an average of 97 models were stored per symbol. The system was tested with 5726 handwritten English characters. When a rejection threshold value of 15 was used the recognition rate was 95% and the rejection rate was 16.1%. When a higher rejection threshold value of 100 was used, the recognition rate was 87.6% and the  86  rejection rate was 0%.  The tested (input) data were constituted of all the different  handwritten bi-level English characters data available in the Center of Excellence for Document Analysis and Recognition ( C E D A R ) database as well as another 120 symbols representing Arabic letters, Chinese characters, and mathematical and electrical symbols.  The accuracy obtained for each symbol and the number of test symbols are shown in tables 3 and 4. In table 3 states the results when the program is allowed to reject symbols i.e. to reject the symbols that are not recognized. In table 4 the rejection rate is zero.  The symbol  0  1  2  3  4  5  6  7  8  147  163  138  106  90  70  103  121  123  85  428  116  12  12  41  19  9  8  16  54  32  5  79  14  0  0  4  4  0  2  2  9  7  4  11  2  The recognition rate in percentage  100  100  96  95  100  97  98  87  92  95  97  98  The rejection rate in percentage  8.2  7.4  30  18  10  11  16  45  26  5.9  18  12  h  H  I  I  k  I  L  m  n  O  The number of symbols The number of rejected symbols The number of misrecognized symbols  B  b  c  d  E  e  f  99  107  127  109  156  96  136  29  26  0  13  18  11  2  9  0  2  9  97  89  100  98  29  24  0  12  P  r  q  104  s  g  J  9a  A  103  103  71  186  44  95  135  241  113  98  150  192  7  18  9  7  7  0  11  21  11  4  20  4  48  7  2  9  7  9  7  2  0  11  7  14  9  7  3  93  92  98  89  93  86  96  95  100  90  97  87  88  95  98  12  11  5.1  17  8.7  9.9  3.8  0  12  16  4.6  3.5  20  2.7  25  t  u  V  X  w  z  y  r  JP  SUM  4>  103  179  164  113  179  164  95  126  91  111  43  50  43  44  31  35  23  26  7  13  16  55  18  13  29  10  13  35  4  33  18  9  33  920  7  9  7  11  2  11  18  7  4  0  7  0  0  0  0  0  0  244  91  88  96  93  98  91  88  91  96  100  93  100  100  100  100  100  100  95  22  25  3.9  7.9  14  31  11  14  23  11  12  81  8  77  41  29  94  16.1  5726  Table 3 The accuracy obtained for each symbol and the number of test symbols when the rejection is allowed.  87  The symbol The number of symbols  0  1  2  3  4  5  6  7  8  147  163  138  106  90  70  103  121  123  85  428  0  4  18  7  4  4  9  38  20  4  44  2  100  98  87  93  96  94  91  69  84  95  90  98  h  H  I  I  k  I  L  m  n  O  The number of misrecognized symbols The recognition rate in percentage  b  B  c  d  e  E  f  99  107  127  109  156  96  136  9  18  0  7  20  15  91  83  100  94  87  84  P  s  r  q  t  J  A 116  103  103  71  186  44  95  135  241  113  98  150  192  9  15  13  20  15  2  7  29  31  29  22  11  22  93  85  87  72  92  95  93  79  87  74  78  93  89  V  u  g  9 a  w  X  s  z  y  r  SUM  4>  104  103  179  164  113  179  164  95  126  91  111  43  50  43  44  31  35  24  22  11  22  11  29  29  13  31  4  18  13  0  13  7  4  9  708  77  79  94  87  90  84  82  86  75  96  84  70  100  70  84  87  74  87.6  5726  Table 4 The accuracy obtained for each symbol and the number of test symbols when the rejection is not allowed.  The error versus the rejection rate is shown in the following table: Error in percentage  12.4  5  The rejection rate in percentage  0  16.1  Table 5 The error rate versus the rejection rate.  A subset (101 symbols) of this database is shown in Fig. 43(a). After rotating the symbols, some of its similar symbols become closer in shape as shown in Fig. 43(b). Next, the system scales the symbols to a predefined size as shown in Fig. 43(c). As mentioned earlier, the user has the option of selecting the size, however, here, we select the option where the system selects the new size automatically (according to the original symbol size). Then the symbols are thinned as shown in Fig. 43(d). Next, the special pixels are marked and the strokes of the symbols are isolated. At this stage, the system transfers the strokes into segments where all segments have one fixed length T. The symbol representations using segment lengths equal to 6, 10, and 14 pixels are shown in Fig. 43(e), 43(f), and 43(g) respectively. Most symbols are recognized by the system as shown in Fig. 43(h) when a threshold "rejection" distance of 100 was used. There are 5 substitutions i.e. the recognition rate is 95.04% and the rejection rate is 0%. Using a small  88  "rejection" distance value, as shown in Fig. 43(i), increases the recognition rate to 100%. However, it also increases the number of symbols rejected by the system to 13 symbols, so the rejection rate is 12.87%.  Generally, if a symbol is mis-recognized but a high recognition rate is required, then more models with a larger number of zones for that symbol should be added. After studying the mis-recognized symbols we found that a symbol may be recognized incorrectly due to one of the following reasons:  1.  The symbol is written in such a way that it closely resembles another symbol. In this case, the human may also be confused about the meaning of the symbol and has to study the syntax or the semantic to understand the symbol and select the closest meaningful symbol.  2.  The symbol model is not in the system. This model then should be added to the system to improve the recognition rate.  3.  The final models for different symbols may be similar if we use long segments (as for some handwritten u's and v's). In this case, we should use short segments to keep as much details  as required to differentiate  between them so  as to increase  the  recognition rate.  89  0  (12,23*33  OO  0  l  l  "  S  <° <° 6  A  /}  «"> M 9  d i d //.UO  *'  - K  " ,•3 0  V,'  ',J  ri-  .< .ii ;< / * c ci  a =  x  ;_.  O  a  o  - <»  ?  3  U  d  J>  *  A <A  ^_ e y  cn  A  Z- U O  i  i  ,  *  ^  ©  o  w  t  i i  --•  -  J.  •  ^ T  %  r  'J  L  ^  ,/  "1  .?  s  O H «  s  c  i  ^  /  f  I,  _y  '''  ^"  •  e  ' i \  Vr  J  "3 -  iV  ^  S»  C <i *  3.  s  I  1-7  £!  s  C C  (c) The symbols after scaling.  (b) The symbols after rotation.  * f s r "  6.  ^ K x. W  <" *  5  7  -3  33  ^  (a) A document.  3  3  88  ft  °^vJ  *  3  e  2-7 £88 7^7  %7 c?M97l  6  3  t j  ?  9  '  & S i .-< 4  iJ  t-j  O x  0 K '  H  hi- H hr  11  >••  '  c  r  i  l_  L. O 1  •Ch  (d) After thinning,  (e) After modeling using 6-pixels segment length.  (f) 10-pixels segment length.  90  oo  666  27  5555-,4 4  888 99  4  AA/\ gBCcJ aaeehhinm A  £  ,  y < I \  /  -  \ ° 4 <=>  f 6  L|  _  * £>  H ,1 fi  H- H H-  E E E f f f f nn nn imgggsssooHHH  •7  888 99 •  AA/\ BBCCD aaeeh mm E E E f f f f nn nn imggnsssooHHH Hzkkkkxnxrr A  D  W W d dd L L U V  WWd dd L L U V r (h) Recognition with rejection distance =100.  4  e  JzkkkkXtxrr  (g)14-pixels segment length.  0 3 33  D555D4 4  666  9  e c  1122  •o  3333  1122  r^  •  •= |J  (i) rejection distance =15.  Figure 43 A document processing.  4.4 T h e System's E x e c u t i o n T i m e  The system is presently implemented using C++ running on a 120 M H z Pentium PC which is a relatively less expensive PC. The software code is at present not optimized. The following describes the results of the speed performance of the system. The system converts the symbols into structural feature vectors. Using the 64 symbols (the English letters shown in the middle of the document in Fig. 43) the system, on average, converts each symbol into its structural feature vector representation (final representation of the symbols by line segments) in 1.9 seconds. This includes rotating the symbol, scaling, thinning, decomposing it into strokes, coding each stroke, mapping each stroke into line segments of three different lengths and finding the representation of the line segments by zones. This results in three representations  of the symbol. Each representation  corresponds to using a segment length. After finding the structural feature vectors for a tested document symbols, the system finds the stored model which has the shortest distance to each feature vector. The searching algorithm, at present, is implemented in a sequential search fashion and is not  91  optimized. It takes an average of 1.51 seconds per symbol to output the typed symbol answer. However, this stage is expected to take only milliseconds if the searching algorithm is optimized and the data representing the stored models are sorted.  4.5 The Program Description The software program size is 9800 lines written in C++ without code optimization. The program includes many utilities. After compiling the program, its size becomes 257 K bytes. The system variables are stored in another text file. Its size is I K bytes. The system knowledge base consists of different files. Each file stores models for a certain symbol. The file size that we have used ranges from 2 K to 10 K bytes. A n example of a knowledge base file that is used to store the models for the letter 'a' is described below. The knowledge base file is an A S C I I file and its size is 3 K bytes. The first line of the file has four entries. The first two entries for this model are '43' and '50', which are the width and height of the bit map pattern for the letter 'a'. The third entry is '40' which is the length of each feature vector (model). The fourth entry is '38' which is the total number of models in the file. The following lines contain the bit map pattern for the letter 'a'.  Below the bit map pattern are the models for the letter 'a'. Each line has a different model (feature vector). The length of the feature vector is defaulted to 40 and can be changed by the user in the system variable file (the 1 K text file). Each vector represents a model representation of the letter 'a'. The first entry in the vector represents the length of the line segment. This length can be changed by the user (in the I K text file). The second and third entries are the number of zones in each row ' i ' and the number of zones in each column 'j'. The fourth entry is the total number of zones = i x j . The following entries are the codes of the possible 16 shape combinations of the zones.  The first model for the letter 'a' in the knowledge base file is the vector [14 2 2 4 2 1 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0], where the line segment length is 14, the number of zones in each row is 2 and the number of zones in each column is 2, and the total number of zones is 4. These four zones have the following  92  codes 2, 1 , 6, and 1. The corresponding zone shapes are Combining the four zones will have the following representation for the letter 'a'  Adding, editing, and deleting a model can be simply performed in the knowledge base file directly or through the program menu under the option "adding a model". In the later case, the user enters the name of the file that has certain symbols (the file should has the same symbols but may contain different styles), then select the knowledge base file name corresponding to that symbol or select the option 'new' for a new symbol. Then, the program extracts the models for these symbols and adds them to the knowledge base. The user controls the model size by changing the line-segment length in the system variable file (the 1 K text file).  93  43 50 40 38 0000000000000000000000000000000000000000000 0000000000000000 00000000000000 000000000000 00000000000 0000000000 11000000000 00000000 0000000 000000 00000 00001 00001 00011 00011 00011 00111 00111 000000  0000000 000000 00000 00000 10000 000000000 10000 1111100000000000000 10000 11I100000000000000000 11000 11100O0O0O000O0O0O0O0O 11000 1100000000000000000000 11000 110O0O0OO000O0O0O00000011 11000 1000000000000000000000011 11000 1000000000000000000000011 11000 0000000000000000000000000000000011 11000 0000000000000000000000000000000011 11000 0000000000000000000000000000000011 11000 000000000000000000000000000000 11000 0000000000000000000000000011111111 11000 00000000000000000000 11000 0000000000000 11000 0000000000 11000 000000001 11 11000 000000 I 11 111 111111111]11 11 11 11! 1 11000 00000 on 11000 0000 i l i i i i n i i m i n liooooooii 11000 0001 111 111 11II1100000000000011 11000 0001 n u n loooooooooooooooooi i 11000 0011 11110000000000000000000011 11000 0011 11100000000000000000000011 11000 0111 11000000000000000000000011 11000 0111 10000000000000000000000111 11000 0111 10000000000000000000000111 11000 0111 10000000000000000000000111 11000 0111 1000000000000000000000 11000 0111 10000000000000000000011111 11000 0111 1100000000000000000011 11000 Olil 1110000000000000000111 11000 0011 11110000000000000111111111 11000 0011 1111110000000011111111 11000 0001 11100 0001 1111111111111111111111 (:<0111 11100 0000 I I I I I I 111 I 111 I I I I I I 1 1 0 0 0 1 1 1 11100 00000 111111111111111111110000011 11100 000000 111111111111111111000000011 11110 00000000111 111 1 111 1 111 1100000000001 OOOOOOOOOOO1111111111 oooooooooooooooooooooo 0000000000000000000000000000000000000000000 14 2 2 4 2 1 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 2 2 4 2 111 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 2 2 4 2 4 0 II 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 2 2 4 2 4 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14236240061000000000000000000000000000000 14 2 3 6 2 2 I 0 6 I 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 2 3 6 2 2 1 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 3 2 6 2 13 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 3 2 6 2 1 8 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 103 3 9 2 4 0 0 3 4 0 2 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14339240081020000000000000000000000000000 14 3 3 9 2 4 0 0 3 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14339221031020000000000000000000000000000 10339821821220000000000000000000000000000 10 3 3 9 2 2 1 8 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10339021821220000000000000000000000000000 10 3 3 9 2 2 1 3 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 3 3 9 2 4 0 8 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 3 3 9 2 4 0 3 2 1220000000000000000000000000000 10 3 3 9 2 4 0 6 2 1020000000000000000000000000000 104 2 8 4 0 0 1 3 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 2 8 2 1 0 1 3 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1043 122210 0 1 32 1 4 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 12 2 2 1 0 0 I 8 2 1 4 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 12 2 2 1 0 0 I 0 3 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 12 2 2 1 0 0 1 3 2 I 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1043 1 2 2 4 0 0 0 13 2 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 1 2 2 4 0 0 0 I 0 3 I 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 12 2 4 0 8 2 1 4 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1O43I222132I1OI220OO000OO00OO0000000OO000O 10 4 3 12 2 2 1 8 2 1 4 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 4 3 12 2 2 1 8 2 I 1 O I 2 2 0 0 0 0 0 O O 0 0 0 0 0 0 0 0 0 0 O 0 O O 0 0 0 0 104 3 1 2 0 2 18 2 I 4 0 I 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 5 3 15 2 2 1 0 0 1 3 2 1 1 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 5 3 15 2 2 1 0 0 I O O I 3 2 1 2 2 O 0 0 O 0 0 0 O 0 0 0 0 O 0 0 0 O O 0 0 O O 10 5 3 15 2 2 1 0 0 1 0 0 1 3 2 1 4 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 105420222100013221100122200000000000000000 10 5 5 25 2 2 2 2 1 0 0 0 0 1 3 2 2 2 1 1 0 0 0 1 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0  94  4.6 The System's Limitations and Future Work Our system has the main advantage of being capable of recognizing any symbol in any language. It can also justify its answer. On the other hand, in our system, the following characters have the same models (c, C ) , (u, U ) , (v, V ) , (k, K ) , (p, P), (s, S), (t, T ) , (w, W ) , (x, X ) , (y, Y ) , (f, F), (m, M ) , and (z, Z), i.e. for these characters it is at present not possible to determine whether or not it is written in lower or upper case. This problem can be solved by comparing the size and location of the symbols to determine whether the symbol is in the lower or upper case. Also, since our system performs the recognition at different stages, thus for some English characters, the scaling stage can be useful in determining whether a character is in its upper case or lower case.  In our system, we also use the same models for the following symbols (1 and 1), (2,z), (5,s), (0, o, O), (q, 9), (8, B), and (g, 9). Note that, the models used for q are also used for the digit '9', and the models used for the letter 'g' are also used for the digit '9'. However, the models used for the letter 'q' and 'g' are different.  Having some prior knowledge about the symbols will help to solve the previous problem. For example, in the case of the Canadian postal code, the symbol sequence is always letter, digit, letter, the hyphen symbol ' - ', digit, letter, digit.  The current system is so general that some models for the handwritten letters ' A ' and 'R' are similar. The same applies for the handwritten letters O , Q and D . This problem arises because our system may omit small strokes and approximate small changes in the strokes by straight segments. T o remedy this problem, further checks may be used to determine the final decision. For example, for the case of handwritten letters ' A ' and ' R ' , after the system recognition process, if the symbol is assumed to be A or R, then we can examine the direction and straightness of certain strokes. If the left stroke is vertical with respect to the right stroke, then it is the letter 'R'. Otherwise it is the letter ' A ' .  Similarly, after the recognition of the handwritten letters ' O ' , ' D ' , and ' Q ' , if there is a small stroke in the bottom-right part, then it is the letter ' Q ' . Otherwise, it is the letter ' O ' or the letter ' D ' . If there is a straight stroke in the left part then it is the letter ' D ' and not  95  the letter ' O ' . The final decision will be determined after these tests have been carried out.  In future work, the employment of basic components which are different from the currently used four basic straight lines segments (/, \, I, - ) will be considered to recognize more complicated symbols. These components will include symbols. Then, the symbols will be described by sub-symbols. Examples of such complicated symbols are maps, roads, and pictures.  For large symbols, e.g. symbols with many strokes such as a Chinese character, the algorithm which measures the distance can be improved by including the possibilities of deleting a row or adding a column. (The idea here is similar to that used in spell checking algorithms). In the later if a word, e.g. book was presented as bok, boak, or boook to the spell checker, then the checker would suggest adding, changing or deleting a letter. In our case, the algorithm would also suggest adding, changing or deleting a zone or more.  4.7 Recognition Rate and The Number of Models The results of the following experiments  show that it is possible  to improve the  recognition rate by increasing of the number of stored models. It is always possible to transfer a handwritten symbol written without any constraints into a model that consists of only line segments. The line segments lie in a limited number of zones. The zones have only 16 possible shapes. The relation between the number of models and the recognition rate for the handwritten letter ' A ' is shown in Fig. 44 and 45 and table 6 and 7. This experiment was also repeated for the digits 0 to 9. The results are shown in table 8 and 9. The input handwritten data that we have used were extracted from the C E D A R database. The number of inputs for all digits was 1146 and for the handwritten letter ' A ' was 139.  96  Figure 44 Recognition rate in percentage versus the number of models for the letter ' A ' when symbol rejection is not allowed. Number of Models Recognition rate %  9 24.47  31  34 67  52 75.54  64 76.98  108 132 88.49 95 Table 6 Recognition rate in percentage versus the number of models for the letter ' A ' when symbol rejection is not allowed. 64.03  100 11 80 60 40 20  77 80.58  •Recognition rate - * -  i' 0  Rejection rate  50  100  150  number of models Figure 45 Recognition rate in percentage versus the number of models for the letter ' A ' when symbol rejection is allowed. Number of Models Recognition rate % Rejection rate %  9 47.15 49.64  31 77.78 28.77  34 79.42 26.6  52 83.02 23.74  64 83.81 24.46  77 85.72 19.42  108 92.99 17.98  132 96.73 12.23  Table 7 Recognition rate in percentage versus the number of models for the letter ' A ' when symbol rejection is allowed. Average Number of Models/digit Recognition rate %  128.55 143.99 87 95.72 Table 8 The percentage of the recognition rate versus the number of models for the digits when symbol rejection is not allowed. Average Number of Models/digit Recognition rate % Rejection rate %  128.55 96.91 23.65  143.99 98.17 14.13  Table 9 The percentage of the recognition rate versus the number of models for the digits when symbol rejection is allowed.  The previous experiments show that it is possible to increase the recognition rate by simply adding more models to the system knowledge base. It is also possible to teach the  97  system new models by using the symbols which were unrecognized by the system. The user in this case will simply select the symbol from the knowledge base that corresponds to the unrecognized symbol. Then, the system will add the symbol model to the appropriate knowledge base. The system will then automatically learn the new symbol and the models for this new symbol and add them to its knowledge base. For example, the average recognition rate for the characters, section 4.3, was 95.0%, however for the letter ' A ' the recognition rate was 92.99%. W e then added the models corresponding to some of the unrecognized symbols to the system's stored knowledge base. W e then reran our experiment after increasing the number of models for the letter ' A ' from 108 to 132, and the recognition rate increased from 92.99% to 96.73% as expected.  4.8 System C h a r a c t e r i s t i c s A s mentioned in section 4.2, the number of all possible handwritten symbols in a zone of N x N pixels is 2  N x N  . This includes discontinuous symbols, however, for connected  symbols, the number of possibilities is less than 2  N x N  but it is still a very large number.  Our system maps this large number of possibilities into 16, since only 16 shapes are allowed in a zone. However, to represent a symbol meaningfully, we need more than one zone. Fig. 46 shows the reduction in the number of possible handwritten symbols and the number of allowed symbols versus the number of (10x10) pixels zones. W e have found that using 3x3 and 4x4 zones are sufficient to achieve a high recognition rate for the English characters and digits. Thus, we can use a feature vector of length 4+(3x3) or 4+(4x4) where the first four entries are:  •  the segment length,  •  the number of zones in each row of the model,  •  the number of zones in each row of the model,  •  the total number of zones in the model.  98  The entries that follow the first four entries are for the code descriptions of the zones. In our implementation, the default value for the length of the feature vector is 40. This allows for larger number of zones up to 7x5, 5x7 and 6x6.  —HO-  M  1E+255 1E+204 1E+153 1E+102 1E+51 3  5  7  9  •  # of allowed symbols  •—#  of possible handwritten symbols  number of zones Figure 46 The number of allowed symbols and the number of possible symbols versus the number of zones.  An experiment was conducted to determine the time required to extract and code the symbol strokes as a function of the number of strokes. First, the document shown in Fig. 47 is thinned to that shown in Fig. 48 by applying our novel central line thinning algorithm in 2.09 seconds. Then, extraneous pixels are deleted by applying our one-pass sequential thinning algorithm (Fig. 49) in 1.27 seconds. The image size is 768x384 pixels (20.26x10.16 centimeters). The experiment indicates that the time required to extract and code the symbols shown in Fig. 49 is approximately linearly dependent on the number of strokes as shown in Fig. 50. It is not easy to find this relationship mathematically. However, it is expected that symbols that have more strokes would require more processing time to be recognized than symbols with fewer strokes.  Figure 47 Example of different symbols.  99  Figure 48 The symbols after thinning.  Figure 49 The symbols after thinning and removing the extraneous pixels.  Figure 50 The processing time for extracting and coding the strokes of the symbols versus the number of strokes.  Another experiment was conducted to show how that the time required to map the thinned symbols vary with the length of the line segment which is specified by the user. The thinned symbols in Fig. 49 are used. It is shown that mapping the symbol strokes into short line segments is faster than mapping them into longer length segments. The time is approximately linearly dependent on the segment length as shown in Fig. 51. In our system we have used the default values of 6, 10 and 14 pixels for the segment lengths.  100  0  10  20  30  40  segment length  Figure 51 The time required to convert the strokes of the eight symbols shown in Fig 47 versus the line segments.  4.9 Summary A rule-based system for the recognition of any 2-D bi-level line symbol has been introduced. Examples of these symbols are typed or handwritten mathematical and electrical symbols and characters such as Greek, Arabic, English or Chinese.  The system performs the recognition in different steps. The first step adjusts the tilted symbols by rotation, the second step scales the symbols to predefined sizes. This is followed by the thinning step. After thinning, each symbol is described by its strokes. Then, apply rules to transform each symbol stroke into a combination of straight lines (segments). A vector representing these segments is used to model the symbol. The distance between this vector and the vectors of stored models is used to identify the input symbol.  The system was tested with different symbols. The tested data symbols consisted of bilevel 5726 English characters taken from the Center of Excellence for Document Analysis and Recognition ( C E D A R ) database. In addition, there were 120 other arbitrary symbols. The recognition rate was 95.0% with a rejection rate 16.1%. In order to increase the recognition rate and decrease the rejection rate, more models should be used for each symbol.  In future, different basic components  than the four basic  line segments will  be  considered. The components will include symbols, i.e. the symbols will be described by  101  sub-symbols. For large symbols, the algorithm which measures the distance can be improved by including the possibilities of deleting or adding a row or a column.  102  Chapter 5 Conclusion W e have developed a system for general symbol recognition. Examples of these symbols are characters in any language, mathematical symbols or electrical circuit symbols. The system can be extended to achieve a 100% recognition rate by having enough models stored in its knowledge base. We have developed a novel method for thinning symbols to their central lines. The system preserves the shape of symbols.  5.1 Statistical versus S t r u c t u r a l P a t t e r n R e c o g n i t i o n Statistical pattern recognition techniques are based on pixel by pixel manipulations. Examples of these techniques are template matching, measurements of density of points, moments, characteristic loci, and mathematical transforms (Fourier, Walsh, Hadamard). Alternatively, structural pattern recognition techniques  are aimed at capturing the  essential shape features of characters, generally from their skeletons or contours. Such features include loops, endpoints, junctions, arcs, concavities, convexities, and strokes.  5.2 System C h a r a c t e r i s t i c s W e have developed a structural method for recognition of symbols formed of mainly curved lines. These symbols include characters in any language, and mathematical, electrical or other symbols.  The system is rule-based and has different rules for scaling, rotating, and thinning symbols. It has also rules for simplifying the skeleton of the symbol and representing them by a set of line segments.  Symbols are described by a set of models in the database. There is a database for each application but only one algorithm for all applications. Symbols are described by short line segments. The system measures the distance between the unclassified symbol and all stored models, then, the system selects the symbol that has the closet model to the  103  unclassified symbol. Our system has the advantages of justifying the answer and can be error free if enough models for each symbol are stored. The system justifies the answer by stating the rules which were applied and the model which was retrieved. The model which was retrieved is the closet model to the tested symbol. 5.3 System L i m i t a t i o n s  The system is capable of modeling symbols that have a limited number of strokes as in the case of English characters. If this number is large, as for Chinese characters, the number of models needed to be stored for the symbol will be also large and hence the recognition speed will be low. In our system, we have 16 possible shapes in each zone. We have used a maximum of 5x7 zones to model English characters. These models were good enough to achieve a high (95%) recognition rate. If a symbol has few strokes but some of them are too short and others are too long and both types are important for describing the symbol, then a large number of models will be needed to describe the symbol. 5.4 C o n t r i b u t i o n s  We have developed a novel parallel thinning algorithm. This algorithm is implemented by using a rule-based system. The system has 16 rules. The system thins symbols to their central lines. The system produces better results than the well-known ZS algorithm. If after thinning, some extraneous pixels remain, these pixels may be deleted by applying our new one-path sequential thinning algorithm. We have developed a novel rule-based algorithm for handwritten symbol recognition. The algorithm rotates, scales, and thins symbols to their central lines. Then, it marks the special pixels which determine the start and end points of each stroke in the symbol. Finally, the algorithm simplifies the strokes by a set of line segments and the line segments are grouped in zones. A group of zones is used to model the symbol. The system was tested with different symbols. The test data are the binary test data (5726 English characters) taken from the Center of Excellence for Document Analysis and  104  R e c o g n i t i o n ( C E D A R ) database. (representing  In addition, w e have added other arbitrary  an A r a b i c letter, an A r a b i c digit, an electric s y m b o l , a  s y m b o l , and a general  symbols  mathematical  s y m b o l ) as examples. T h e r e c o g n i t i o n rate is 9 5 . 0 % w i t h a  rejection rate 1 6 . 1 % . In order to increase the r e c o g n i t i o n rate and decrease the rejection rate, more m o d e l s s h o u l d be used for each s y m b o l .  5.5 F u t u r e R e s e a r c h In this research, w e have d e v e l o p e d a rule-based system for general s y m b o l r e c o g n i t i o n . H o w e v e r , we assumed that s y m b o l s are i n their isolated f o r m . F o r future  w o r k , the  p r o b l e m o f c u r s i v e handwritten character r e c o g n i t i o n s h o u l d be addressed. C u r r e n t l y , the system can be used for applications such as postal code r e c o g n i t i o n w h i c h are written i n boxes. In future, w e a i m at i m p r o v i n g the system so it can read the c u r s i v e addresses as well.  Different a p p l i c a t i o n w i l l be c o n s i d e r e d i n future. E x a m p l e s o f these a p p l i c a t i o n s are data entered i n forms, e.g., tax forms, j o b applications, b i l l s , bank cheques, a i r l i n e passenger tickets, and passport verifications.  105  References  1. S. Mori, C. Suen, and K. Yamamoto, "Historical Review of OCR Research and Development," Proceeding of the IEEE, 80 (7), pp. 1029-1058, (1992). 2. M . Shridhar and F. Kimura, "Handwritten Address Interpretation Using Word Recognition With and Without Lexicon" 1995 IEEE International Conference on Systems, Man and Cybernetics, Vol 3. pp. 2341-2346, (1995). 3. C. Tappert, C. Suen, and T. Wakahara, "The State of The Art in On-Line Handwriting Recognition," IEEE Trans. Pattern Anal. Mach. Intell, 12 (8), pp. 787-803, (1996). 4. K . Nathan, H. Beigi, J. Subrahmonia, G. Clary, and H. Maruyam, "Real-Time On-Line Unconstrained Handwriting Recognition Using Statistical Methods," International Conference on Acoustics, Speech, and Signal Processing, vol 4. pp. 2619-2622, (1995). 5. A . Amine, "Off-Line Arabic Character Recognition: The State of The Art," Pattern Recog. 31 (5), pp. 517-530, (1998). 6. S.N. Srihari, "High-Performance Reading Machines," Proceedings of the IEEE, 80(7), pp. 1120-1132, (1992). 7. K . Kise, O. Yanagida and S. Takamatsu, "Page Segmentation Based on Thinning of Background," Proceeding oflCPR IEEE, pp. 788-792, (1996). 8. A . A . Hopgood, "An Introduction to Expert Systems," IEE Expert Systems for NDT, Conference, London, UK, 1-2, (1989). 9. A . Walker, M . McCord, J. Sowa, and W. Wilson, Knowledge Systems and Prolog, Addison-Wesly, 1990. 10. M . Ahmed and M . Bayoumi, " A n Artificial Intelligent Instructor for Electrical Circuits," 37 Midwest Symposium on Circuits and Systems, Lafayette, Louisiana, vol 2, th  pp. 1362-1365,(1994).  106  11.0.  Eldessouki, A . Eldessouki, A . Nazif, and M . Ahmed, "An A T N Approach for  Understanding Arabic Sentences," 11 NCC, KFU, Dahran,  Saudi Arabia,  (1989).  12. A . Eldessouki, M . Ahmed, A . Nazif, and O. Eldessouki, "An Expert System for Understanding Arabic Sentences," Proceedings  of the 10  King Abdulazziz  pp. 745-759, (1988).  University, Jedda, Saudi Arabia,  13. R. Duda and P. Hart, Pattern Classification  th  National  Computer  Center,  and Scene Analysis, John Wiley & Sons,  New York, 1973.  14 K . F u , Syntactic Pattern Recognition  and Applications,  Prentice-Hall, Englewood  Cliffs, New Jersey, 1982.  15. M . Ahmed and R. Ward, " A Novel Intelligent System for Defining Similar Symbols," IEEE Pacific (PACRIM'99),  Rim Conference  on Communications,  Computers and Signal  Processing  University of Victoria, BC, Canada, A u g 23-25, (1999).  16. M . Ahmed and R. Ward, " A Rule-based System for Thinning Symbols to their Central Lines," submitted to the IEEE journal of PAMI in June, (1998). 17. M . Ahmed and R. Ward, " A Fast One Pass Knowledge-Based System For Thinning," Electronic  Imaging, 7 (1), pp. 111-116 (1998).  18. R. P. Lippmann, An Introduction to Computing with Neural Nets, I E E E A S S P M a g , 1987.  19. S. Y . Kung, Digital Neural Networks, Prentice-Hall, Englewood Cliffs, New Jersey, 1993.  20. O. Trier, A . Jan, and T. Taxt, "Feature Extraction Methods for Character Recognition - A Survey," Pattern Recog. 29 (4), pp. 641-662, (1996).  21. J. Cao, M . Ahmadi, and M . Shridhar, "Recognition of Handwritten Numerals with Multiple Feature and Multistage Classifier," Pattern Recog. 28 (2), pp. 153-160, (1995).  107  22. G. Burel, I. Pottier and J. Catros, "Recognition of Handwritten Digits by Image Processing and Neural Network," International Conference on Neural Networks, Vol. 3, pp. 666-671,(1992). 23. H . Al-Yosef and S. Udpa, "Recognition of Arabic Characters, " IEEE Trans. Pattern Anal. Mach. Intell., 14 (8), pp. 853-857, (1992). 24. T. Cheng, J. Khan, H . Liu, and D. Yun, " A Symbol Recognition System," International Conference on Document Analysis, pp. 918-921, (1993). 25. K . Fukushima, "Necognitron: A Hierarchical Neural Network Capable of Visual Pattern Recognition," Neural Networks, 1 (2), pp. 119-130, (1988). 26. K . Fukushima, "Connected Character Recognition with a Neural Network," Neural Networks, pp. 240-243, (1993). 27. R. H . Anderson,  "Two-dimensional Mathematical Notation," in Syntactic Pattern  Recognition Applications (K. S. Fu, ed.), Springer-Veriag, Berlin, Heidelberg, New York, pp. 147-177, (1977). 28. C. Suen, C. Nadal, R. Legault, T. A . Mai and L. Lam, "Computer Recognition of Unconstrained Handwritten Numerals," Proceedings of the IEEE, 80(7), pp. 1162-1180, (1992). 29. H . Jianming and Y . Hong, "Structural Primitive Extraction and Coding for Handwritten Numeral Recognition," Pattern Recognition, 31 (5), pp. 493-509, (1998). 30. H . Kim and H . Yang, " A Neural Network Capable of Learning and Inference for Visual Pattern Recognition," Pattern Recog. 27 (10), pp. 1291-1302, (1994). 31. A . Amine, H . Sadoun, and S. Fischer, "Hand-Printed Arabic Character Recognition System Using an Artificial Network", Pattern Recog. 29 (4), pp. 663-675, (1996). 32. J. Starzyk and Y . Jan, "Algorithm and Architecture for Feature Extraction in Image Recognition," Southeastern Symposium on System Theory, pp. 448-452, (1994).  108  33. J. Parker, "Gray Level Thresholding in Badly Illuminated Images," IEEE Trans. Pattern Anal. Mach. Inteli, 13(8), (1991). 34. Y . Lu and M . Shridhar, " Character Segmentation in Handwritten Words - An Overview," Pattern Recog. 29 (1), pp. 77-96, (1996). 35. C. Sun and D. Si, "Skew and Slant Correction for Document Images Using Gradient Direction, " International Conference on Document Analysis and Recognition, Vol 1. pp. 142-146, (1997). 36. P.E. Danielsson and O. Seger, Generalized and Separable Soble Operators, In H . Freeman, Editor, Machine Vision for Three-dimensional Scenes, pp. 347-279, Academic Press, 1990. 37. H. Fujisawa and K. Kurino, "Segmentation Methods for Character Recognition: From Segmentation to Document Structure Analysis", Proceeding of the IEEE, 80(7) 10791092(1992). 38. R. Casey and E. Lecolinet, " A Survey of Methods and Strategies in Character Segmentation," IEEE Trans. Pattern Anal. Mach. Inteli., .18(7), 690-706, (1996). 39. Badr Al-Badr and Robert M . Haralick, "Recognition Without Segmentation: Using Mathematical Morphology to Recognize Printed Arabic," Proc, 13 National Computer th  Conf. Riyadh, Saudi Arabia, pp. 700-702, (1992). 40. G. Houle and M . Shridhar, "Handwritten Word Recognition With OCR-base Segmenter," Document Image Analysis, pp. 51-58, (1997). 41. G. Dzuba, A . Filatov, and A . Volgunin, "Handwritten ZIP Code Recognition," IEEE Int. Conf. Document Analysis and Recognition, Vol. 2, pp. 766-770, (1997). 42. F. Kimura, Y . Miyake, and M . Shridhar, "Handwritten ZIP Code Recognition Using Lexicon Free Word Recognition Algorithm," IEEE Int. Conf. Document Analysis and Recognition, Vol. 2, pp. 906-910, (1995).  109  43. L . Lam, S. Lee, and C . Suen, "Thinning Methodologies - A Comprehensive  Survey,"  IEEE Trans. Pattern Anal. Mach Intell. 1 4 (9), 869-885 (1992).  44. Y . K i m , W . Choi, and S. K i m , "High-Speed  Thinning Processor for Character  Recognition System," IEEE Transactions on Consumer Electron. 3 8 (4), 762-766 (1992).  45. Y . T . Zhang and C . Suen, " A Fast Parallel Algorithm for Thinning Digital Patterns," Comm. A C M , 2 7 (3)236-239, (1984).  46. G .  Raju and Y . X u , "Study of Parallel Thinning Algorithms," in Proc. IEEE  Int.  Conf. Systems, Man, and Cybernetics, V o l . 3, 661-666, (1991). 47. Y . Y . Zhang and P. S. Wang, " A Parallel Thinning Algorithm with Two-subiteration that Generates One-Pixel-Wide Skeletons," IEEE Int. Conf. Pattern Recognition,  Yo].  4,  pp. 457-461, (1996).  48. C . M . Holt, A . Stewart, M . Clint, and R. H . Perrott, "An Improved Parallel Thinning Algorithm," Comm. A C M 3 0 ( 2 ) 156-160, (1987).  49.  Richard W . Hall,  "Fast  Parallel  Algorithms:  Parallel  Speed and  Connectivity  Preservation," Comm. A C M , 3 2 (1) 124-131, (1989).  50. N . H . Han, C . W . L a , and P. K . Rhee, "An Efficient Fully Parallel Thinning Algorithm," in Proc. IEEE  Int. Conf. Document Analysis  and Recognition,  V o l . 1, pp.  137-141,(1997).  51. C . Arcelli, P. C . K . Kwok, G . Sanniti di Baja, "Medial Lines by Parallel Wise Erosion of  Successive Contour Pairs," IEEE  Int.  Conf. TENCON,  Technology  Enabling  Tomorrow, V o l . 1, pp. 66-70, (1992).  52. L . L a m and C . Suen, " A n Evaluation of Parallel Thinning Algorithms for Character Recognition," IEEE Trans. Pattern Anal. Mach Intell. 1 7 (9), 914-919 (1995).  110  53. M . Altuwaijri and M . Bayoumi, " A New Thinning Algorithm for Arabic Characters Using a Self-Organizing Neural Network," in Proc. IEEE  Int. Symp.  Circuits  and  Systems, V o l . 3, pp. 1824-1827, (1995).  54. N . Kharma, M . Ahmed, and R. Ward, " A New Comprehensive Database of Handwritten Arabic Words, Numbers, and Signatures used for O C R Testing," IEEE Conference on Electrical  & Computer Engineering,  Edmonton, Alberta,  Canada,  Canadian May 9  - 12, 1999.  ill  Appendix I T h e System M o d e l s We have used the following models for the recognition of English characters. The model size ranges from l x l to 7x7 zones. The models for (1,1), (2,z), (5,s), 0,o), and (8,B) are the same. The models for 9 are the same as those for g and q, but the models for the letter 'q' are different from the models for the letter 'g'. The following pages include all the stored models used in our system.  112  o  a.  ?  e>  a.  k  P: Cr £>.  pi  a  6; E  Z S  B\ ~mo:.a: i?i  a;  E > i  <?i  0;  ^;  W ¥\ :4f: Pi W\ Q; &• M ii lis: &. is* m G; M M\ M <li M  E > i  !a i  Si  !?  0:  Eri  C3i  © i© £>  <£>;  ;  O  Si  LJ  0 0 0 o  O  Q  %  a  <J  n;  Si  iii  1  Cj  Q  CJ  O  ^ §  Q  O  O  : 7 V  !•:  :|i  * >\  iS-i  '/\ iSi  p  iU  fi;  •2  *  JL :  f?i  1: 0  5-:  :_2J  pi  fi.;  :  %  n i  i?i  ?i i?  2: •1;  iW.^i  'iNi  ! L ; re  El;  i!i  •  r\  ?i I Ii i; F; y % iTi si * iii ^  11 £>i 0] m o D 6 0 0 0 L) 0 0 l> o- 0 O T) O O <? D D O o o O O o C o t> o o D  Ii  s o :1 ;  2_i  rru  . " Z  >4i  ^i i^i Ri 2  '%.  i?i  W.?\ E M rs; i^i [TZJ 'M W.ii-i m M M 1  il is I 1 Ii I il il il  rai;  •^i  IR-: M  % % i* li  it;  Z L ;Z i  i  w.i il  i*i  M i^ il il M  1 1 iii iii  '91  Si  Wr  m  1  y.  i  3  •3  v.  a;  y  ^1  S'  P.  Si fS-  :">>:  3:  3:  ^'  3: :H'  U; '^.\  iy.  <tl  i?  :?l  3  i5: 13  3  rssi  Pi  ^ :  E  iii  <3-: ifV:  *;  ft:  <T#i m  Hi  i  ii  i  ii  i i  i  i i  i i  ii  Pi Pi Pi i  T:  r  5:  Ln  5:  L£  y  3:  s  •J  s  5.  c  5":  a;  LE  s  S  •X  ^  s:  !?l  SL  ?:  iS:  S  LiT:  15  •ST: LT*: S:  LT:  S;  LIT: !•?:  LiT:  LG  LSI  5j:  LP;  hif;  S"; SL  :  jK  is  Si:  >J: |Sj  3:  :^  5:  Lif:  m Sri  ii  i 1 1 1  m mm i  Si  5  s  LSI  Lip  Si  if;  p  p  li  p  Pi  p  ni  iii  i?i  i^i  i-jl!  Pi  p  Si  m m 1 1m  EP  iE  $  rP  i  i i  i l  i  i  1  Si  E IS  ii  LSI L*T;  111  L5|  IM fn-i  Pi  ••  LE  LS  **;  Pi P P P P  ?.;  .=.  s  <SI  g;  *i :  lit;  S;  Pi Pi  3 3 3: 1 i ; il i i i i H 1 Si  w. m  Si;  i  s i LUI Pi  5':  SI  *.  $;  4-:  A\ H:  LS|  M P Pi P  Pi Pi :  iS S 1 ii 1 :^n i l i i P i :  i  Ii 1 1  114  V.  f.  s:  s:  :TT:  V:  g  j.;  D  I,  6:  li:  fi-i b;  is;  §:  s:  ^:  fe  Sz  &l S=i i£i S i  4. % ^  ••/ t-i  ii  IS  iii  iii  Iii  tli &  is: 1  i*i  Hi: bi: Si  1  P  P  P  P  i=  P  P  ip  M  &i  1 ip  ii  i i li  i i fi  ii  1  sP Ii-; 6:  p: i i  i  i  iiii I i i l i  l i l i  Hi iii l i  ;  .li i i ;  ii  1  &  % l' Hi  1 1  I I  I  1 1  1  1 1  Ii Ii  1 1  1 ii  li  i i 1  i i  l i l i  i i  l i l i  Hi m m  1 i i  1  p  P'  1  1  m  Si  i  i i  Si l i 1~  n>i  ?i  :TH! ;T5!; i2i  '/:':  I  3>i £1  m  iii  m m  01 ^ii  -<::  m  i^  i?i iT>i -2 >'  ?:  a;  il?:'  ;  iPi  ;Tli ;TS;  Bi S  1  3  ii  iff;  M  ip  ii  1  P  pi  m  y^i  Si 1  ii  1  1  1  1  1  1  1  li  ii  1  i  1  l i l i  l i  i  ii£ (oii iil i  1  I  i  i  i  i  a:  ST:  "5:  a  :^  6:  LB:  EiL  iH:  ?!  ?:  Bi  *:  Gi- gi  if'i  *i  :^  «  :'4f  LJ>:  rn;  i^i  & ^ : s  ?f:  m 1  :  gi  i-Si Sii  i^i Pi;  ^i  s>i i  ii?'  '&  ihl  ^  1  '?i  1  iff:  r*i  ii  if? i l  s':  W  i3i p i  ii  ii  Pi  ^i  >1 s>: S i ia: ©i ii? i  Si  il  Pi i  i^i i i  (fii - 1 i i i  ?j &  Si  a  B  <}  Is  8  t?  S  V J  l i  c»-  o  hs  1  li  B  r  Q  :CV  Sr (T  v  :^7r. &  Qi  2.  b  B  1  <P  D  li  ill l i  li  L&  &  iSi l i  I 6 ft  5  B  Of  l i  a  •1  6  1 1  .H;  is- :7:  lb:  il?i ; i i  1 l i i i  ro: Si  a:  i  P  ii  i  O-i  f?:  ;  i?i  li  1  jfri a  T-  i?i"i ai  Si  1  l i l i l i  i  FtL-1  ^:  Ld:  B*  i  ii  l i l i l i l i l i  K  Si  li  7  FS:  li  1  fi :  a;  iii iii i i  m m ii 1  i?T;  si; e>: |s; LBTL  m m  e.  •a: si  e.\  §t;  P'  a;  ES;  pa S i  iii  23:  B:  if  1  m  #  .?:  :  1 i  m= 5!; :7T;  I*  E  tfi rf>  l i i 1 i  i?:  BJ  m:  if  iii  £  rn; rr*  1771 i rrp;  P 1  <Pi i^i  in;  rm;  §  i  w.  i  rH:  ST:  ft n b  m j  M  115  CK  ,<H  Si  Qi  S Ri  Ri  5*  :<?•:  Qi  LU  Hi  is  3;  ft ft  .w;  fl; ^  K g.  Oi  CL;  Cj;  a.;  CL;  is.;  ft fti ft  k.;  a.  ft  ft ft ft ft ft 9; Si ft Si; ft ft ft ft Oi Si Hi Si ft ft ft ft ft a: ft ft ft E2  ft>i ftli ET:  S i !ft: fft  g;  ?;  ft ft ft ft ft ft ft ft ft ft: ft ft ft: ft ft ft ft a: ft ft ft ft ft ft ft ft ft i^: % ft  .ft  ft ft ft ft ii 1; iji « ft i 31 ft' ft' ft Ii ft ft ft'  !* ft ft  iii  ft:  aHi  i;  I  II  PI  ^i  |i  iii  RJ  ;1  i  ft'  i  Ii  1  ft'  ft'  II  II  Ii  II  Ii  Ii l l  ft ft ai i^i ft ai ft ai  1 m  a i 3 : i3: 3 ; a ;  "Lftii  ft"  a.;  Q;  CH Bi  i  l  ft ft P  l  ft'  ai  ft'  ai  ft'  1  IS  ft'  m  P  P  P  P  Cft Eli  p p  p  PI P  m P  a; i  S g;  m  P  m  P  1 ft i 1! i 1  ft  a  p  p ail: m  ;  (ft p  Pi P  1 I  m m P P  ft!  ft  :  p  p  ECU P p <^ m tftim m Qi m P P i i S S P i m\P i P i m P I P I ii W. i I M i i i i m i i 1 i 1 i i i ' m. m p<Pf m i 1 1' i i i i i i i i i 1 1 1 1 i  m  it* PI  P  <P P)i O i  i i  PI (H£i  i  116  Ri  tfi  di  (N  (Bi  Ri  rH:  (t\  (is;  xii  HI;  (iSi  hi  '#':  n-:  ft  ?  '•<&. '*.  'rhl  195 iii; s:  iv  HK  Hi  Hi  k  'ii  u  Bi  Ui  6i  'A':  >?>i iTi  t*i  ift  ft  6!  fl;  (iii  ft!  ft  .ft  m\  (ft  hi :  (ft  ifti  iftli ifti ifti  >* I :  m ^  Eft  ft-; ft'  Krii i l  H  i i fl  kTH  P A  n i  m iP  i  ft'  If  P  Hi  P  m  fft'  Km;  p  Pf  IP p i  P  P  P Pi  i  il  i  p PI  &i  &  f  fi  ft"  ft'  !>i  t?i  ti  it;  !f;  ft ft  ii  PI P i P i PI  P  P  ft'  f  p  ft I  PI  ft  ill  PI PI  P  P  P  E;  P  ft'  <Ei  fft  ft":  Pi  P PI  PI  PI  fi  Ei  fl  f;  fl  S-l  fi  i  i  i  fi  ft  1  ft'  1  ft  W.1  p  £  i i ii  i  P  il  1  ii  ii  ii  i  it?:  ft'  if'  £i  fl  ft'  ii  ii  ii  ii  ii  ii  i  PI  P  P  P  P  P  ii  I i  1  P  P  P  P  P  i i  i i  ip  iP  PI  iii l i i i  £•!  i i i i i i i i  mm,  | l Pi  P. IP  ii  1  i  PI  i i  i i  i  Pf  i i  i  £ tni  p  i  i  i  i  Pi  P  p  i  11  ft  ft'  fl  P  P  eft  i  P  i  fi  i  i  I 1 1 1 ii 1  i i  i l  i i  fl  f-!  eft  P  (0 i  i i  fi  pftiCft.  i i  I  £.;  ft-i ft-i ft-i ti;  i  ii  E;  fti  i  i i  Ci  ft ft ft ft ft ft ft ft ft ft. ft ft ft ft  (iii  i  i l  i  I?:  1  i  1 I 1  i l  Li  e;  i l P  PI  P  •ii P I  y  pi  ii  ft'  m fft mP  ft  EJ  P  i  ft ft P P  : ^:  ft ftft  ft ft  ft ift  F.  1 P l i 1! M i i  p  i i  i i  i i i P  i i i  117  C <E  t;  i t  14; *  ;  it  :  1^  ft  Ei  Si  E  a.  if:  ift  ai  Ej  D;  £  e;  1  ft'  Hi ft  Hi  <ll  Si  ft'  ft'  ft  1 M  a; s-:  fti ftli m  P i P:  Pi  cH i  i  1 1 i  yj  iii  M  i  i i  l  l  i l l l i  iii  ii  i  m  1: i  P  i l l ii i i I I I  i  1 ii 1 ftj 1" 1  ft' I  i  1 Si  I  ft ft  E-:  a  Si;  ifti  ft  E-l  ft'  1ft'  P P P P  ii  1  M  1111  1  I  E  i  e  e  E  f  i  e  E  E  E  ;  El  :  ft'  HK  S;  ^  E  2  E  (EJi  i^i  ET:  HEi  I  Hi  E  Ei  i  ft'  ft'  <2i !Ui  PI PI M M P P p PI P M P PI Si ei ei  m m m m P IP IP IP P PI ftp  1 1 1 1 i ii P @  <fft  iI p  t>:  ft ft ft ft ft ft ft ft  E?i  f  E=.  fti^iftiSftftftift'ftftift .€  Ei  ii  L  gi  sp 1  m  p  gii  di  m •®  118  F  5  F  ST:  F  F:  F  Fl  F":  Fl  F":  FT:  F  F~i  ;f  if:  <?:  Fi-  F  F:  fi  F  f:  S  3:  9i  9:  a;  s;  a;  *i  IF'  s  S:  3:  Lbi  s;  a;  3;  ?3  a:  a:  3  ;i  «:  gi  j  s;  Fa;  SH  :^  F ?!  a:  >:  iii  LR:  is;  FF HF'  3:  FF  ET: bii  s:  ia;  s ; ii* LF>;  F *  F  3;  P  P  li Si | ;  li  P  P  3:  P  (T;  S  £: <F  F~:  m  FT: lEI (TTT:  F;  F~: ifi iFT:  Si  FT FT i>F  Ifi i  ifi  Si ET:  7  P  3 ; iSi  ST;  l i m m i P i P P i i p p i FT P i i i  iP  S i P i P i W: m ifi  fli M  •HP PP  PPi-Pi  ^  il  1 1 1 i  l  I i  l  1 1  1  ii  1  F:  3;  F.  Ef|: ii3;  P  P  li  ^i  i  F  hi  if:  IF. IF  LF  F  Fi Xii  IF!  Fi  Hi: HF  F.i  i*  LF:  Ri  Hli  KS! ISi  ft  Pi itii  P  Si l i  1  li  1  In:  F'  hi:  hi!  Si  iSi  «i  ?!i; *1  'tf;  IF £:  HF IF  &  *S; Si  fei  :  Fi'i  FF  Si  iirii i*i riSi  I *  P  P  P  P  P  P  P  P i P i |F; i i ; P i l i  1  P i P i iHii Pi  s  iltS IFF: hi :  hi  P  Fli  P  P  iii  I  s Pi Pi pi i P PS iPi i *  I l i i i  ii i i  I  FF FF  F  Fx  P  l i Ii  i  li l i  i i i iPii l i i Pii FP  M M  ii  L3:  HF  i-irii HS!  l i l i i i i IS! l i  Ii  s;  HF  i>>: Si  Si P i Si l i i i l i IFF FF' i P P i  1 Si P 1 1 1 H  :  F  li  l i  1  i  Fp  PP i i i Ps:  P  Hi!  LFP  ^li  Hi! 1  i  M  frii  I  mi P  m I  li ii li  P'  i  I I 1  1:1:  1  I  119  Hi ^i : -  >H;  Bi  :*<:  kr  :  (H: KH:  s;  :-H:  IS  ¥: ih -  IS  rsH  hi:  m  •m -B. m m sh  m mi Hfi  P  id i2T;  ^  E  F  .-ri  '4  £  fe  ,2.  1_J  iti  ti  '<¥.  ii-i fe' fe  e p:  fe :  ,Z  ;<j  2-i  1 | 1 1 |  p  11  ii  «??i ii  120  ,TN  TOm:  rrr.  rrr.  rr>: nr.  HT:  rTT:  HF. HF  m:  m:  r>: rri:  IB; HI: m:  rr.: m;  IF  m:  j»:  m: HF  m:  HF  rr;: ins:  hi:  fr,:  IF: m;  HF  C:  <A\  rtn  FH: rTTi; •M: FI; IFF Fn: Fri; rTF F F  ITF m FTF IFF rn: :YYF  HF Hi  mi  Hi  rfii  hni  hn: lrii  ni;  Hii  Hi  Hi  rfl i hni  hii  Si; IT!;  .hi;  ;FH  Hi 'hsi  Hi  r"i  Hi  *"  ">  r  ti:  n:  c:  j:  m: m: Fl:  FH in;  nn:  :YF  irn Fn:  hi  !V:  Hi  hii  hii  hii  Si  hii  hni hlii Si: F F  m  Fn:  (iii  Hi  hii  r:  r>;  n: a:  FF  HF  FI:  a:  rn N:  HF rf:  FF  HF  r>:  rF  FF  rh  Hi  fH:  F": Fi:  si;  ihii  hii  jlF  HJ; hii  ini hi:  m di  hii  hi:  hii  Hi  Hi  n:  h:  IF.'  (Ii  Pi  hh'i Iii;  F,:  h?i  FF F F Ihli Fli  Hii  in;  hii  •Y:l: Kli » :  HF  FF:  P  FF Pi  Pi  hni  P  P  Pi  Pi  Pi  Pi  hPi F l  r-i  P>i Pi  mP  Pi  Pi  HF  HJ: HF FI: ni;  HCF FT: ISF FJ:  P  hHi hii  •Si rtTTi! iFF P  /ni: F F  HF  hii liii  hii  hi FF';  hii  p  FJ;  hsii Hii rili  mi ihii  hii  fir":  ihii hii  Pli  S i hlii in; Hii rrni (ISi ITS rTTii Ihii hiii rm Pi hvi; S i 11: hii  n:  .m: HI: m; .T:  yn: rm: .til: riTi; nm: m: IFF :TT>: KF;: :"TF  (Hi  -"•  m.  l!H  Kl: rhi  n:  P  P  P  Pli HP  :  nPi Vn In V^i nrn; Hii Itli hTiii  ,Ff,  l i  i i  m.  ^  rn m [n  rf  til  [H  n  rili  P  hi  hi  P  ii  riTi i  ^ >  tP - p  A  hi hi  m  m  "hi  P  1  Itiii Pi  H i PP Pli hirii  Pi  fifl  mn m  T>1  Yfl  YnYn !hl  1 I  1  121  »:  X-  ft ft  ft ft  F. St  fi-  .^:  iT:  <S:  fft  :-5  p.  tft  p.  R:  r>:  S:  R; +!:  R  ft is;  P.\  •A.  *f  Eft  ^  ;•?:  n:  FT: IT:  <?.  ^:  F.:  .tv  p.:  Z:  ft  st: FT F  a;  n:  :>:  fn  :  ft Si fit  F  ft  f=t  ift 1ft  (t?  ft  H?i  ift  (ft  ;-?;  ft  (ft  (ft  m fft  ft?  (5;  s; ift; e;  <ft  ii?!  I P ift fft: d 1; fff>: if:! np p;  ft  tr  ft  F:  :Y  F  its  ift  ^f  ift;  Ri  ft  ft  ft  .T:  :ft  (Ff  /:  <t  ft  n; ?: SS Si % i>; ?: tr; f5 fi t:ft ft 1 : " " ; ft' ft 9': ft ft ft ft F>; ft <?; ft ft ft rr; ft; XI ft ift; ft (ft fxf ft «?; ®. ffti ei; ft ft ift": Ift": fft; fft; ft> 'ft: a; m frtft r^; ^ ; fti; FJ; • f t ; ft? 1 1 1 1 ll fft fft 1 1 if 1  ^;  ft-;  ft":  ^;  fft  ^;  ft;  ft>:  sft r^;  If  f=ft  Hft;  fi! f e  p  r  ft  :  (TT: <rt  <?:  1  K  fit  ;  F:  pv  f^rt  <£>;  r rr  r  :?  p P P P P 1 ft ft 1 1 1 1 fl 1 1 1 Pi Pi  ft. ft' ft f; 1 ft' P f l m 1; P P fft: 1 m P i l P f l P i l ri=: P m P FS: m 1! l i l i if>: Pi (1 m P m p m m ft m 1: m P P P l i ii p w m fl! i l ! m 1; Hi  3; P p P l i l i 1; mli li il P  1 ff 1 1  p Pi Pi P  ft<i  B E  1  ft'  m  1 i  1 1  1  mi1 i '  Hi!  1 1  122  rr.  >J:  T: H-  iiSi  H:  T:  :T:  HH  :TT:  H-:  ft ft  iH  b  Lili  if  i-t-'  ii:  IS  ft: ;t;  ft ft  ft fEL  ;  |t  T fTTl  ri;  if  if  ;t;  ft  iiii  m rri ft  Lii !LJi  Si  ft"  ft":  P  m  Pi p itti P  Pi pi P  Oft l i •it!  li  1 1 1 1 1 1 1 I 1 1  ft.  •  :  ft ft ft  LiL  ii:  (ii Ui  ilE  <S. ^L  LJ  :  ft  ii^i :V:  iT:  iv:  rri  fi  Wi  :V:  :Vi  N:  ii?i  Ift  ^J;  Ki  ft;Hft  ft'  ft'  i ft'  P  P  P  P p  P  P P Pi  P p  ft" ft' ft'  p  ft'  p p  mft;  lift  ii ii i  li ii  1  Hi ii i i i  iHft  iVi  ft ft ift  Ift  iift  iii: iftii  ift?  ftftftft  i^ft  Iii  I/O [ft i  iift  ftfti  ft'  1'  N:  ft ft ft ft  ift  ftft  OP i l  u: Ui Si  li  'I 00 Pi P fft P  !+: li  Ui L*  H.  II  :|:  ft"  Hi  ft'  ft PI  :T:  Hi  p  p  0(1  m  P! iii P  m  P p p p i IPO PI OP OP pi OP 0P1 Pi  p  p  p  i  i 1 ii ii  I  1  123  FH  ¥  -: Fi  in.  FH HF  SH FH HF  IV:  iw:  LF  IF; FJ;  CHi.  LF  LF:  Wi  HF  LJ;  IFF HF:  HF!  ivl  H*i  HFH  FF  H-L F; FF  IF-: HF F ^i :Vi;  FJ:  Fii  FF  Lyi  k  v- k  |f  k  k-  lui  LJi  LF  -i  Ui  m  II  1^  LFH  L/  'kl  LLF  V  k'  t'/  KF  H  ^  CL'  k)  H  KF  Ul 1  3F  -*i  fF~i  U  KJ  iV  WH  P  FJ  » kJ  -V  kl iJ  l-l  ki  H!  Lli  •J:  !£i  X  F  F  HC  i-H  iiP  F  F  HC  X-  X  Fk  Xi  F HF  F:  W.  *  FH  X  :HH  Hk  is-i  iHiF  ivi  p  P  i l Pfi HP  PI  i l pH  *i  !* Iii  Pni HP i * PP HP  Y:  :Y:  fn iii !>!!  iy  Ha':  HF  Hii  a:  ;H3':  ;Y;  Y\  HI:  HF:  HF -  iiii  HF  Fi):  Hdi  > iri  W\  -y.  m  Bi  FF  Hi  :FH  V;  F":  FF  H-|:  :  HP iii p Pii Pi ifi  l i Pi  HF Fl:  Pi 1  :  m  l i iP  p i  Pi l i  ^i  FH'  nPi PtH  Pi Pi irk; Pi i i i IFF  w  kJ  kl  Pi  LF  kx  IV  kJ  11  l.Fl  s-i  K  un P  \  lu  P  r"  IH W  P-  P p  F HF  iji b':  HF  m Pi m m Hp iXi m m PF  F  FF  P^i  P  (ii!  N P  l,J  wl  P  Kl  LJ  Hii  LJ  'V  g  h-  K  P  w  IP  1  FP  Pi Pi l i  IV  hi W  iHF|i  Fji;  1  l i  M li  Ii  Ii  ii ii  p  iii  Iii Pii PP  li Ii  m  ;  l i PPd;  Pi;  M  Iii  FiH  I  ip-i  PI l i  IFF. JTJ: i l  Ii  i  H  IAJ iV 1'/  hi KJ  u  nc":  p  HFF: Wi  £  :"<  Vr XJ  IF) F J  1  k-l  XXI l ^ , 1V-J L V -LV s£,  ^ lJ P- K iJ-' iii r  nil  124  A p p e n d i x II S y m b o l s Before a n d A f t e r Recognition The symbols in the left column are some binary data taken from the C E D A R database. The symbols in the middle are the recognized symbols using a threshold of 15. The symbols in the right column are the recognized symbols using a threshold of 100.  OOtfOOOdOOCOOOC cacao  OODOOOOOOOOOooooooo  OOOOOOOOOOOOooooooo  COObOO&OOOOOooooo  O O D O O O D O O O O O o o o o o  O O O O O O O O O O O O o o o o o  0D DOOOOOOOOoooc  Oo  Oo  \OOOQQOCoo  OOOODOOooooooooo  O O O O O O O o o o o o o o o o  \AJ\/1/U/U/VAI/I/;/I>  1l011111D11111[]11111llii  "1l211111211111111111llii  /l/l/l///U//l/\W/\/\///  1111111111111111411111-111  1111111111111111411111111  \\tl\/(/U/\W//n/\ll/,  01111111111111111111111,  11l11111111111111111111i  2222222D2aD22  222222222^222  22nD2DD2-l2-i22a  22522-122-12-1222  •2222U2D2D22r_i2  02222222222222  22222222 2 D 2 D 2  22222222 222-12  222D2D222  222221222  O O O O O O O O O o o o o  O O O O O O O O O o o o o  125  3333333333D333  33333333333333  3D3333331D333333  3533333313333333  23D333D333D33  2333333333333  3 3 3 3 D  3 3 3 3 3  4D444444444D4  4144444444444  ^4444444444444444  4  4  4 4 44444  •  4 4  5 S 55~S~ S'SSSs-ss- 5 S 5 5 S 5 5 5 5 5 5 5  4  4 4 4 4 4 44444444444 4 4 44444  4 4  I  5555£55555555  555555555-155  555555555155  S55L_]555D  s55  6666666666656666  6666666666656666  6666G66666666666  6666066666666666 666661666661666  66666D6666DD6DD  5555-i  37777111^71777 ,711^771177171?^  °\J tf7 lf \<7l/<\<?lf (  c  c  dafl*Adctaa.iiAtta<» d t i a o o  0.4(1  DDD77D17D777D77  222777177777777  •D7DD177D-ID777D  9  17111777-I77771  7 7 D 1 1 7 7 D D 7 7 D 7 7 7 D  7  7 71177  • 7DD7-I7DD  7 7 2 1 7 1 7 7 1  777777771  88888880DD88888n 88DD888D88n8n88  8888888018888885  D889D88D88888888  5889588888888888  •86D88888  "186088888  9 9999 9 9 999-19799  99999 9 9 9991 9 7 9 9  9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9  9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9  [j9999999  9  DDnaabaaDDoaaa  d d n a a b q a c a n s S a  aaDaonaaaaaadaaa  aaaaaaaaaaaanaSa  anannaoanddaaaara  aaacaaoa jddaaadfa  aaanci  aaaae  8 8 8 8 8 8 8 8 8 8 6 8 1 8 8  9999999  aa2.a.Q.^3.4aa^AlaEL3.  a^aa3E9aaac39'c3c?a  ••aaaaaa a3aaDD a  aaaaaaaaaSdaaaq  aaSaaaaDaaaajana  aadaaaaaaaaajaaa  aa33n3aaDa  aaddd3aaaa  aDdaaaaaaadddaa aaaa aa38l laaa 33  adaaaaaaaadaaaa aaaa,aaddaaaaaadd  aa aal  aaaaaaaaaaaaadaaaa  a  aa  aaaaaaa 3aaaaaa a  a3aaaSaa.ciaa3aaa3fl3c9  Iaaaaaaa8aaaa  aaaaaaa aaaaaaa  aaoaaaaaaaaaanaaaaa  aaaaaaaaaaaaaaaaddd  aaDa oaaaaaDDa a  aajagodaaaazgaaa  a  n  •  AAAAAAADAAAAAD  PIAAAAAAAAAAAAAA  AAAAAAADAPAAAAA  AAAAAAAAAPAAAAA  ADAAAAAAAAAADAA  AAAAAAAAAAAAAAA  AAAAAAA  AAAAAAA  A  A  b^bbLVabbbbbbbbt  DbbbbDbbbbbbbbb  bbbbbbbbbbbbbbb  bbbbbbbb£bbbbbkbb  bbbbbbbbbnntDbbDb  bbbbbbbbbdbtbbbbb  bbObbbbbbbbd  bbfbbbbbbbbf  • PBDBDDBaBBBB  Btf$r3o~B$e>/3d  BBBBBBBBOBBBB B  s  BDonDBcin  •  tPBBBBBBaBBBB  BBBBBBBBOBBBB B  BnoBBBBn  B  BBaDBBBoBOB  BBnBBBBoBZB  B  B  CCCCCCCCCCcccc  CCCCCCCCcccccc  CCCCCCCCCCccc  CCCCCCCCCCccc  CCCCCCCCcccccc,:,  CCCCCCCCCcccccc  CCCCCCCCCCCCccc  CCCCCCCCCCCCccc  CC CCCCCCCCCCccc CCCCCCCccccccac dCCCCCCCCCcc^  dc\rj/d</ddd<Jddc/d ddDl  dddDdddddd  dddl  dddOdddddd  dddddddciddddria  DdddDdddddDdDd  addddddddddddd  addddddddddcU  ddddddddddddd  ddddddddddddd  iddddcidd  dddddddd  dddddddd  eeeeeneeeaeaeoLeLe  eeeeeoeeeaeceii_ei_e  .J  —M 6cceeoeeeeeeeec  QQ.£e*.e£.e<?eete?eeee ee  Bcceeooeeeeeeec  66eeeeeeneeeeencec  66eeeeeeceeeeeccec  eoeneeeeeeeeeeee  ejeceeeee eeeeee  ee  ee  e  129  £ £ E £- B e £ B £ £ s eie E  £~  E  E  C  E  I  -  E  E  E  E  E  E E E C E r E E E E e E  E  E E£.E E D E E E E D E E E  E E E E O E E E E P E E E  EECEEEaEEEDEDnE  EECEEE-T  EEE  EEE  ft 3 1 9 3 ^ 3 ^ 9 9 9 9 9 9  UhhhhhKhhhhhhhhh  E E  fffffffffffff 1 fffff f f f ffffff f f fffffffDfffffffffff rffDfDfffff  fffffffffffff,  •QgDgrSQgDgggggg QOggggsggngggggo gggggggraggggo  dggggrsggogggggg goggggsggggggggg gggggggsgggggg  hhhhhlhhhLDhhLhh  hhhhhlhhhLhhhLhh,  hhhDhhhhi_hhhhhD hhhhhhhhhhhhhhhhh nhhhhnhDhhhhhhhhh  hhhhhhhhLhhhhhh  f  rP^fffFffr  EEECEf  1 fffff f f f fffff-f f f  fffffffefffffffffff rffPfSfffff  hhhhhhhhhhhhhhhhh nhhhhnhhhhhhhhhhh  HHHHHHHHHHDHH HHHHHHHHHHHHH JyHNnH JyHN-tH  A H H D H A H  A H H A H A H  N H H P H H  1JI I I * I •; • I • I • I • /•/im/\l/('l///l//i<l/M/l/l///i  r  N H H P H H  III  h u m  IDllllllirrillllllllJJii  Ijiaiiinm.,JIIII  r  h u m  II IlllllirnllllllllJJii  iilllliilllGIIIII  nlllliilllllllll  I I l l I I l I I l I I  I I l l I I l I I l I I  l l l l l l f l  l l l l l l f l  Jc^aJJJjjJJJJjJJjJJjjj  DnaJJJjjjJjJjjjjjjjjj  JaaJJJjjJJJJjJjjJjjjj  i J U J j j J j J j J l J j J j J J J J  DJJJjJJjJDJjJjJjJJJJ  ajijjjJJjJjJjjJjJjJJJJ  Dktkrkkkkkkh  tktkrkkkkkkh  kkknk-t-tkaok  k^kkVk-t* fk  •kDkkkkkkkkkkkk  hkCkkkkkkkkkkkk  kkkkkDnkkkkkxkk  kkkkkknkkkkkxkk  KKKKkKkK  kkkkkDkk  kkkkkkkk  ll(/ll/inw.il\/Ui//(w..(l/f///  lllDiiinziinili i II  //IMI/VI/(\/n\iiu\\l\/\ntn\  r  \Alni  IilllllilllDlllllllrllllJIIlll  IllllllllllllllllllrllllJIIlll  D i i n i i j,nJi  X i l l l i i jIJi  LCLLLLLLLCLLLLL  LCLLLLLLLCLLLLL  CLLLCLCLLLLCLLLL  CLLLCLCLLLLCLLLL  tl\)/\\\\II\I\KI\\\U/i  Y-LILJLILLLLL^LLL  h u m  ••InillllllriillllllllJJli  • cLl_i_*i_"t  CLLLLLLCC  LCD  HlfflTl  m m m H m m L  AIMS* »t'Mth  Ijlclllll: r  I I 1 I I III limIII  mi  II I l l l l l i n i J I l l l l l l J J i i  I C L L l _ t i _ t  CLLLLLLCC  LCD  _innmmmnmmm n 'M'/VX^lm  k L  NUlmi mmm  Hmm  Ammmmmmmmm_ in 1 ITImmmmNAn  IITImmmmnnn mlTlnmmDmmn« mn mlTinmmmmmn« mn  «/? n *\  n-CN «  n  tN  n h n \n n n  £>£>Q()OG<Dooeo  o  OOOOOdOOOOOPQ&oe  OOOOQOOOO  U'  P?WP?P/PPH  SR'\ ISq9 7 \9q l9q^9 c  <  t  [  c  ?9999 hq9q? ) e  c  rinhnnnnnnnnnnnnnnn  rinhnnnnnnnnnnndnnn  nnhnhnnnnnnnnhnn  nnnhnhnnnnnnnnhnn  n  nhPlnnnnnnnhnnnnnn  nhnnnnnnnnhnnnnnn  nnnnhnnnnnnDhnnn  nnnnhnnnnnnwhnnn  •  OOOODOODDO  aoooooooouo  o  OOEDOOOOOODOn  o  OOOOOOOoooooo  o  O O O O a D O O O O o o o o a o  o  OOOOauooooooojoo  OOODOOOODODOUOOODO  oOOOOOOOaooouooouo  •OODOOOODODODOOOoo  oOOOOOOO jouojaoooo  000O00OO0  000O00OO0  P P P P P D D P P P D  P P P P P P A P P P t  PPPOhPPPPlOPPa  PPPOhPPPPlOPPn  qqqqDqoqD^Dqqqqqq  qqqqaqoqz^qqqqqq  qDqqqqoqqnnqDDqqD  qq qq  qqqDqOqqqoSq  qqqqq3qqqoSq  Pnnpnpppppppn PPipnpppppppp PPPDP PPPOP PPPD PPPm  q  q 0  qqjnqzqqqq  frrrrrrrarrrrirrrrr  frrrrrrrnrrrrirrrrr  frrrrr  rrrrrrrrrrrir  rrrrrrrrrrrrrrrrr«r  rr/rrrrv-rrfrrrrrrrr  frarrrrrrrrrr rrrrrr  frfrrrrrrrrrrrrrrrr  rrrrrrrrrrrCrrrrrr  rrrrrrrrrrrCrrrrfr  rrrrrrrrrrrcrrrrfr  rrrrr  rrrrr  rrrrrr  Crcc/VM-r/rrrrr  f rrf  r  r  D S S S S S S S S S D S s  SSSSSSSSSSJSS  S s i ~ SCsssrosssss  S  SDSSSCJSSSSSSSSSS  S S S S S C J S S S S S S S S S S  SSSSSSSSSDSSSDss  SSSSSSSSSSSSSJSS  SSSSSSSSSSIgs  SSSSSSSSSSigs  s  r SCsssrosssss  E U t t t t i itt-tt t n t t t t t t t t t t t o  Yttttttttt  t"tttttt1:tDDi:*  t-ttttttttcft*  t t t t t r t t t t t t * *  t t t t t r t t t t t t * *  ULnuvnnionDvnuu  Vl_VUVkruoucvuuu  vULIDonnnvnunauvu  vUUCOOayVhuvauvu  ^V)U£/oyunuUUUuUUUu  UUUDDVUDUUUUUUDUU  uUUUovuauUuUuUUUu  UUUUUUUUUULIUUUU.UU  UuuDUUuuuuUuuuUuU  uuuUlluuuuuUuuuUuU  •UUUUUUUDCODUU.U  UUUUUUUULCOUUUUU  TTrr-r-trrr ~T 7  Kt+\r-rr<r*,T-n  ~fTVTtTt/rT1-r7-r  t t t t t t t t t t t t t L  VVVVVVUVVVUUVUOUD  VvVVVVUWvuuvuauy  1 VVVVVUVVUUDUV  VVVWvuvvuuuuv  V V V V V V D S V V V Z V V V  vvVVVvusvvvzVW  i/l/vll/vvi/yvvVNi'vV  vVvVvvvDvvVvVvV  VVVVVVVVWVvVvV  VVVv/VvWVVVVv  VrrjvvVvvvvva  VrrjVvVvvvvv  IA) V_A3 LO VO V u v » ^ oo  WWWUDwwwww  IWwuqwwwww  (/} &/ tc^ u/ w  WWWwWDwwwwwu  WWWWWW W W W W w u  w  4/  u> ^ ^ ^  L  W vv IAJ ^ to <-o w ^ WWWnnwwwww  WWWH  LO b3 i/O w "W Www W \H  WW W . wWWw WWW  WWW.wWWwwWW  ••XDDXQxxDXXDDxy  VtXrrxtxxLxxtyxy  DxXXXXxXxXXXxXX  yxXXXXxXxXXXxXX  XxXXXXXXXfXXXx  Xxxxxxxxx^XXXx  XXXXXXXxnxaa  XXXXXXXxkxfZ  yyyyyy yyyyyyyyy  yyyyyyyyyyyyyyyyy  yayyyyyyyyyyyyynD  yyyyyyyyyyyyyyycg  yyyyyyy  yyyyyyy  w  yy  N / W W W W W  ZZ2ZZZLZ_^Z.^2\Z  X.Z-L-LIZT.ZZ.'ZZ.  ZDZZZDLzzazZZ  Zczzzei_zz zZZ  DIZZZZZZZCZZ  Z i z z z z Z z z c z z  ZzDZZZZZzzZZzn  ZznzzzzzzzzZzn  zZzzZZZZZZZ  zZzzZZZZZZZ  B  * j? J? <b j? j? j? r _u ••J»nj,j»nn_bn  J?  rVYYTrrrrrrrr  rTrrrrrrrrrrr  MDffl  J,  J,  J, J, 43  Cj> J ,  J,  ap $ dp 4> dp dp 4* <\> 4> 4>4> d  3  C^CjpC^CJ>cj>CJ>_i3Cj>cf)Cj> J , 4 >  - s ^ ? -s<=> i = ; - s ^  -v?  • ••••••• -tX- -fcf -P+ -CV - £ + - t » -  -J*1>  ••••HX-OHX-D  -^-W-W-tt-HX-W-W-M  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065333/manifest

Comment

Related Items