Image analysis – Applications – Mail processing
Reexamination Certificate
1999-03-12
2002-01-29
Patel, Jayanti K. (Department: 2621)
Image analysis
Applications
Mail processing
C707S793000, C707S793000
Reexamination Certificate
active
06343139
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to automatic sorting, and specifically to automatic location of text or other well-defined features on material being sorted.
BACKGROUND OF THE INVENTION
A crucial problem in automatic sorting systems, well known in the art, is the location of desired fields on the surface of an object whose image is captured and analyzed. Typically the fields have some predefined visual structure having a geometric component, for example, a text field comprising sets of alphanumeric characters in a substantially linear layout. In the context of the present patent application and in the claims, such a field is referred to as a structured field. Existing approaches to this problem comprise binarization of an image as a first step, wherein a gray-scale image is first converted to binary form, and wherein, for the case of text location, domain-oriented heuristics are used as a second step. An example of this approach is described in an article titled “Postal Address Block Location in Real Time,” by Palumbo et al., in the July, 1992, issue of Computer, which is incorporated herein by reference.
Although binarization of images allows large volumes of image data to be processed quickly, methods involving binarization have several drawbacks, since no perfect binarization is known. As a result some image fields that are being searched for will be consistently discarded, since binarization reduces the available information about the image. Furthermore, for large images, such as images of postal packets, the time required for binarization is substantial.
In searching for a text field such as an address block in an automatic parcel sorting system, the text field must always be found, or else the entire sorting process fails. Also, the number of falsely identified blocks must be minimal, in order not to generate too much work for the rest of the modules of the sorting system.
SUMMARY OF THE INVENTION
It is an object of some aspects of the present invention to provide an improved method and apparatus for location of structured fields in an image.
It is a further object of some aspects of the present invention to provide an improved method and apparatus for location of text fields in an image.
It is an object of some aspects of the present invention to provide an improved method and apparatus for automatic sorting of mail.
In preferred embodiments of the present invention, a gray-scale image of an object having one or more structured fields, most preferably text fields, is generated. Preferably, the image is generated by a line imaging system, and the generated image is digitized and transferred in digital form to a central processing unit. Most preferably, the processing unit comprises dedicated hardware including a first and a second processing stage, described in more detail below, which operate on the digitized image sequentially in real time. Alternatively, the processing unit comprises a mixture of dedicated hardware and general-purpose, software-driven computing elements. After the stages have operated on the digitized image, the processing unit determines areas in the image where the results indicate there are text fields, according to predetermined conditions incorporated into the processing stages.
In some preferred embodiments of the present invention, the digitized image data of the object is processed by the first processing stage, which detects areas of the image having a high probability of containing text, herein termed “text kernels.” Most preferably, the algorithm operates on an array of image pixels, herein termed “anchor points,” which are separated by predetermined distances. Positions of text kernels are determined by locating points, herein termed “dominant points,” around the anchor points which have substantial gray-scale differences compared to horizontally or vertically adjacent points. Areas around the text kernels are analyzed, and those considered by the processing stage to have a high probability of containing text are grouped together. The first stage concludes by building a first map of text regions based around the text kernels.
The output of the first processing stage is processed by the second processing stage, wherein the text regions found in the first stage are analyzed and refined further. Preferably, each of the text regions has its anchor points reallocated, so that the anchor points are separated by distances substantially smaller than in the first stage. Preferably the anchor points separation for the second stage is half the separation of the first stage. As described for the first stage, regions having a high probability of containing text are identified. The second stage concludes by outputting positions of regions of interest (ROIs) likely to contain text, together with an associated ranking for each ROI, made in accordance with geometrical characteristics of the ROI.
In some preferred embodiments of the present invention, the gray-scale image comprises an image of an object, such as a parcel, to be sorted for mail delivery. Preferably, the parcel travels on a conveyor belt system comprising means for sorting parcels into appropriate groups. For example, the conveyer belt system is able to sort parcels into those with no identified text fields, those with one text field, and those with a plurality of possible text fields. Alternatively, other methods of sorting, as are known in the art, are used. After determination of regions on the parcel which include text fields, as described above, the parcel is sorted into the appropriate group by the processing unit operating on the sorting system. The text field is then read and interpreted, preferably using an optical character recognition algorithm, as is known in the art, and the parcel is routed for delivery accordingly.
The present invention enables very fast detection of fields within an image which have well-defined directional properties, with substantially greater accuracy, and with substantially fewer falsely identified blocks, compared to methods at present known in the art.
There is therefore provided, in accordance with a preferred embodiment of the present invention, a method for locating a structured field in a gray-scale image of an object, including:
choosing a plurality of anchor points in the image, each anchor point having a gray-scale value associated therewith;
determining for each anchor point a horizontal variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a horizontally neighboring anchor point and a vertical variation dependent on a difference between the gray-scale value of the anchor point and the gray-scale value of a vertically neighboring anchor point;
defining as vertically or horizontally dominant respectively those anchor points whose vertical and horizontal variations obey a first or a second predefined condition;
identifying one or more kernels in the image, each such kernel comprising a group of anchor points in predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group; and
locating the structured field in the image using the one or more kernels.
Preferably, the structured field includes an alphanumeric text field.
Alternatively, the text field includes an address field in a mailed object.
Preferably, the method includes sorting the object responsive to the structured field that is located.
Preferably, choosing the plurality of anchor points includes choosing the anchor points to be at the vertices of congruent contiguous rectangles.
Preferably, locating the structured field includes dividing the image into a plurality of regions and finding one or more of the regions which have large numbers of kernels therein relative to others of the regions.
Alternatively, finding the one or more of the regions includes assigning a ranking level to each of the regions indicative of a likelihood that the region has a desired characteristic.
Further alternatively,
Finkelstein Lev
Heilper Andrei
Wallach Eugene
Darby & Darby
International Business Machines - Corporation
Patel Jayanti K.
LandOfFree
Fast location of address blocks on gray-scale images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast location of address blocks on gray-scale images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast location of address blocks on gray-scale images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854687