Optical character recognition by detecting geo features

Claim 3

The method of claim 1 wherein said step of detecting the occurrence of predetermined geographical features includes sensing the positions of said detected geographical features with respect to each other.

Claim 4

The method of claim 2 wherein said geographical features comprise bays and lagoons.

Claim 5

The method of claim 3 wherein a lagoon is an enclosed area and a bay is an open area.

Claim 6

The method of claim 4 wherein a bay is characterized by the direction to which it opens.

Claim 7

The method of claim 5 wherein said known characters are identified by the lagoons and types of bays from which said characters are formed, and the relative positioning of said lagoons and bays with respect to each other.

Claim 8

The method of claim 1 wherein said step of detecting the occurrence of predetermined geographical features includes sensing a break in the scanned character; and completing said break.

Claim 9

The method of claim 7 wherein said break comprises a "soft" break formed by at least two links of the scanned character which are separated from each other by less than a predetermined amount, and said break is completed by joining links in closest proximity.

Claim 10

The method of claim 7 wherein said break comprises a "hard" break formed by at least two portions of the scanned character which are separated from each other by more than a predetermined amount, and said break is completed by joining portions in closest proximity.

Claim 11

The method of claim 1 wherein said step of detecting the occurrence of predetermined geographical features includes sensing a connection between two characters; and disregarding the sensed connection in detecting said geographical features.

Claim 12

The method of claim 10 wherein said step of sensing a connection comprises determining when none of the stored combination of geographical features which identify known characters corresponds to the arrangement of detected geographical features.

Claim 13

The method of claim 11 wherein said step of disregarding the sensed connection comprises ascertaining which portion of the arrangement of detected geographical features corresponds to a stored combination of geographical features; and disregarding that portion of said arrangement of detected geographical features whose position is sensed after the ascertained portion.

Claim 16

The method of claim 13 wherein said step of scanning comprises generating pixel data representing the scanned character; identifying coordinates of said pixel data; and storing said coordinates.

Claim 17

The method of claim 14, further comprising the steps of identifying a link between at least two pixels, sensing the coordinate of the pixel which comprises an end point of an identified link or a beginning point of another link, storing the coordinates of each sensed end and beginning point, determining the number of links connected to each said sensed end and beginning point, and identifying the class of each said sensed end and beginning point as a function of the number of links connected thereto.

Claim 18

The method of claim 15 wherein said step of sensing predetermined geographical features comprises detecting the presence of a bay extending between the coordinates of two "class 1" points, detecting the presence of a lagoon formed by a "class 3" point, and determining the relative positions of the detected bays and lagoons as a function of the coordinates of which each is comprised.

Claim 19

The method of claim 16 wherein said step of detecting the presence of a bay comprises tracing a path from a selected "class 1" point and thence from link to connected link, in a predetermined direction, until arriving at another "class 1" point; sensing changes in the coordinates of the end point of a link relative to the coordinates of the beginning point of that link; and detecting the presence and orientation of a bay as a function of the sensed changes in the coordinates.

Claim 20

The method of claim 17 wherein said predetermined direction comprises the counterclockwise direction in tracing said path.

Claim 21

The method of claim 17 further comprising the steps of identifying each link connected to a "class 3" point, and arranging the identities of the links connected to said "class 3" point in a predetermined order; and wherein said step of tracing a path from link to link includes the step of arriving at a "class 3" point via one of said identified links, and leaving said "class 3" point via the identified link that next follows said one identified link in said arranged, predetermined order.

Claim 22

The method of claim 19 wherein said predetermined order is clockwise.

Claim 23

The method of claim 19 wherein said step of detecting the presence of a lagoon comprises tracing a path from a "class 3" point, said path including a link extending from said "class 3" point, which link had not been included in a previously traced path, and returning to said "class 3" point as said path is traced.

Claim 24

The method of claim 21 further comprising the steps of sensing if each link connected to each "class 3" point has been included in the traced paths; and concluding that all bays and all lagoons included in the scanned character have been detected if all links connected to all "class 3" points have been included in the traced paths.

Claim 25

The method of claim 15 further comprising the steps of detecting a separation between "filled" pixels as said character is scanned; determining that said separation should be filled in; and identifying the link in which said separation should be included.

Claim 26

The method of claim 23 wherein said step of determining that said separation should be filled in comprises detecting the relative distances between filled in pixels which form said separation; and sensing the shorter of the distances.

Claim 27

The method of claim 24 wherein said step of identifying the link comprises sensing the identity of the link which includes a filled in pixel having the smallest separation from a next closer filled in pixel; and identifying said separation as being included in said last-mentioned link.

Claim 28

The method of claim 23, wherein said step of scanning further comprises sensing successive columns of sequential pixels; and wherein said step of identifying said separation as being included in a link comprises changing the identity of the link in which said separation should be included if, when a successive column of pixels is sensed, the identified separation is detected as being included in a pattern of pixels which comprise a link of different identity.

Claim 29

The method of claim 26 further comprising the steps of determining that said separation should not be filled in and not including that separation in any identified link.

Claim 30

The method of claim 13 wherein the step of sensing the proximity of spaced apart pixel data comprises detecting the absence of filled in pixels within a predetermined neighborhood of a sensed filled pixel.

Claim 31

The method of claim 28 further comprising the steps of sensing the size of each block of thinned pixel data as a function of the coordinates of the pixels therein; and detecting the occurrence of an out of range block whose size differs substantially from the sizes of previously sensed blocks.

Claim 32

The method of claim 29 further comprising the step of joining an undersize block of thinned pixel data to an adjacent block to form a joined block of thinned pixel data representing a scanned character; and identifying the scanned character represented by the joined block of thinned pixel data in accordance with the geographical features of said joined block.

Claim 33

The method of claim 16 further comprising the steps of detecting at least one undesired link between two independent characters; ignoring said undesired link; and identifying said two independent characters.

Claim 34

The method of claim 31 wherein said step of detecting at least one undesired link comprises detecting bays and lagoons of the scanned characters that do not correspond to bays and lagoons of a known character; sensing bays and lagoons of a portion of the scanned characters that do correspond to bays and lagoons of a known character; ignoring links which extend from said portion; detecting bays and lagoons in the remainder of the scanned characters that follow the ignored link; and identifying the characters which precede and which follow said ignored link as a function of the detected bays and lagoons.

Claim 35

The method of claim 15 further comprising the steps of detecting artifacts in a block of thinned pixel data; and deleting said artifacts prior to identifying that scanned character.

Claim 36

The method of claim 33 wherein said artifacts include a "whisker" formed of a link comprising less than a predetermined number of pixels.

Claim 37

The method of claim 33 wherein said artifacts include a "puddle" formed of a lagoon of less than a predetermined size.

Claim 38

The method of claim 33 wherein said artifacts include a "beach" formed of links interconnected in relatively small changes of direction from one link to another.

Claim 41

The method of claim 37 wherein said step of arranging comprises determining the average X, Y coordinates of the pixels which represent the range of each respective picked up character; and arranging in a single line those identified characters having approximately the same average Y coordinate.

Claim 42

The method of claim 38 wherein said step of arranging further comprises the step of arranging said identified characters in a single line in left-to-right order in accordance with the average X coordinate of each said character.

Claim 45

The method of claim 40 wherein a relative concavity is sensed if said path which continues from said point extends into the first or second quadrant.

Claim 46

An optical character recognition system, comprising: scanning means for scanning a plurality of characters, which may not be disposed in uniform lines and which may overlap, to form image blocks of pixel data derived from and representative of each scanned character; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; detection means for detecting the occurrence of predetermined geographical features in an image block of thinned pixel data; storage means for storing particular geographical features of known alphanumeric characters; and comparison means for comparing the detected geographical features to the stored geographical features to identify a scanned character as the alphanumeric character whose geographical features correspond to said detected geographical features.

Claim 47

An optical character recognition system, comprising: scanning means for scanning a plurality of characters, which may not be disposed in uniform lines and which may overlap, to form image blocks of pixel data derived from and representative of each scanned character; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; detection means for detecting the occurrence of predetermined geographical features in an image block of thinned pixel data; storage means for storing particular geographical features of known alphanumeric characters; and comparison means for comparing the detected geographical features to the stored geographical features to identify a scanned character as the alphanumeric character whose geographical features correspond to said detected geographical features.

Claim 48

The system of claim 42 wherein said geographical features comprise bays having open areas and lagoons having closed areas; wherein said detection means includes means for determining the relative positioning of said lagoons and bays with respect to each other; and wherein said comparison means compares said relatively positioned bays and lagoons to stored bay and lagoon data.

Claim 49

An optical character recognition system, comprising: scanning means for scanning a plurality of characters, which may not be disposed in uniform lines and which may overlap, to form image blocks of pixel data derived from and representative of each scanned character; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; detection means for detecting the number of "class 1" and "class 3" points included in a block of thinned pixel data, wherein a "class 1" point is defined as a free end of a link included in said block, a "class 3" point is defined as a point formed by the juncture of three links, a "class 4" point is defined as a point formed by the intersection of four links, and each "class 4" point is detected as two "class 3" points; selection means for selecting as a function of the detected number of "class 1" and "class 3" points a set of characters in which a scanned character is included; feature sensing means for sensing predetermined geographical features of a block of thinned pixel data; storage means for storing geographical features of sets of known characters; and comparison means for comparing the sensed geographical features to the stored geographical features in the selected set to identify a scanned character as a particular character in said selected set in accordance with the compared geographical features.

Claim 50

An optical character recognition system, comprising: scanning means for scanning a plurality of characters, which may not be disposed in uniform lines and which may overlap, to form image blocks of pixel data derived from and representative of each scanned character; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; detection means for detecting the number of "class 1" and "class 3" points included in a block of thinned pixel data, wherein a "class 1" point is defined as a free end of a link included in said block, a "class 3" point is defined as a point formed by the juncture of three links, a "class 4" point is defined as a point formed by the intersection of four links, and each "class 4" point is detected as two "class 3" points; selection means for selecting as a function of the detected number of "class 1" and "class 3" points a set of characters in which a scanned character is included; feature sensing means for sensing predetermined geographical features of a block of thinned pixel data; storage means for storing geographical features of sets of known characters; and comparison means for comparing the sensed geographical features to the stored geographical features in the selected set to identify a scanned character as a particular character in said selected set in accordance with the compared geographical features.

Claim 51

The system of claim 44 wherein said geographical features comprise bays and lagoons; and wherein said feature sensing means comprises means for detecting the presence of a bay extending from the coordinates of at least one "class 1" point, means for detecting the presence of a lagoon formed from a "class 3" point, and means for determining the relative positions of the detected bays and lagoons as a function of the coordinates of which each is comprised.

Claim 52

The system of claim 45 wherein said feature sensing means further includes means for identifying each link connected to a "class 3" point, and means for arranging the identities of the links connected to said "class 3" point in a predetermined order; and wherein said means for detecting the presence of a bay includes means for tracing a path from link to link by arriving at a "class 3" point via one of said identified links, and leaving said "class 3" point via the identified link that next follows said one identified link in said arranged, predetermined order.

Claim 53

The system of claim 46 wherein said means for detecting the presence of a lagoon comprises means for tracing a path from a "class 3" point via a link which had not been included in a previously traced path and returning to said "class 3" point as said path is traced.

Claim 54

The system of claim 44 wherein said feature sensing means further comprises means for detecting at least one undesired link between two independent characters, and means for ignoring said undesired link, thereby resulting in two independent characters.

Claim 55

The system of claim 44 wherein said detection means comprises means for sensing a "soft break" in a link, and means for filling in said "soft break".

Claim 56

The system of claim 49 wherein said means for sensing a "soft break" comprises means for sensing a separation between a "class 1" point and a link that is less than a predetermined distance; and said means for filling in said "soft break" comprises joining said "class 1" point to a link that is closest thereto.

Claim 57

The system of claim 44 further comprising means for sensing a "hard break" in the scanned character; and means for filling in said "hard break".

Claim 58

The system of claim 51 wherein said means for sensing a "hard break" comprises means for detecting blocks in which portions of the scanned character that are separated by said "hard break" are respectively contained; and means for determining a block of relatively small size.

Claim 59

The system of claim 52 wherein said means for filling in said "hard break" comprises means for joining a block of relatively small size to a block adjacent thereto to form a joined block which contains the scanned character.

Claim 60

The system of claim 44 wherein said feature sensing means includes smoothing means for detecting and removing artifacts in a block of thinned pixel data.

Claim 61

The system of claim 54 wherein said artifacts include one or more of "whiskers", "puddles" and "beaches".

Claim 62

An optical character recognition system comprising: scanning means for scanning plural lines of characters, including optical pick-up means that may pick-up characters disposed in different lines; pixel generating means for generating image blocks of pixel data representing the picked up characters, each pixel being located by X, Y positional coordinates; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; sensing means for sensing predetermined geographical features of each image block of thinned pixel data; identifying means for identifying a scanned character as a particular character in accordance with the sensed geographical features; and re-arranging means for arranging the identified characters in the same lines in which the scanned characters were disposed notwithstanding the order of the characters represented by said pixels.

Claim 63

An optical character recognition system comprising: scanning means for scanning plural lines of characters, including optical pick-up means that may pick-up characters disposed in different lines; pixel generating means for generating image blocks of pixel data representing the picked up characters, each pixel being located by X, Y positional coordinates; means for thinning the pixel data included in each said image block to reduce the thickness of the pixel data representing the scanned characters; means for sensing the proximity of spaced apart pixel data to determine the beginning and ending of image blocks of thinned pixel data; sensing means for sensing predetermined geographical features of each image block of thinned pixel data; identifying means for identifying a scanned character as a particular character in accordance with the sensed geographical features; and re-arranging means for arranging the identified characters in the same lines in which the scanned characters were disposed notwithstanding the order of the characters represented by said pixels.