Fast location of address blocks on gray-scale images

• US 6,343,139 B1
• Filed: 03/12/1999
• Issued: 01/29/2002
• Est. Priority Date: 03/12/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Finkelstein, Lev, Wallach, Eugene, Heilper, Andrei
• Primary Examiner(s): Patel, Jayanti K.
• Application Number:
  US09/268,137
• Time in Patent Office: 1,054 Days
• Field of Search: 382/100, 382/101, 382/135, 382/112-114, 382/169, 382/176, 382/181, 382/190, 382/218-219, 382/237, 382/201, 382/292, 382/365, 345/762, 345/776, 705/77, 705/76, 707/3, 707/516
• US Class Current: 382/101
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/147 Determination of region of interest
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

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. For each anchor point there is determined 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 there is also determined 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. Those anchor points whose vertical and horizontal variations obey a first or a second predefined condition are defined as vertically or horizontally dominant respectively. One or more kernels are defined in the image, each such kernel comprising a group of anchor points n predetermined mutual proximity and satisfying a third predefined condition relating the number of vertically-dominant and horizontally-dominant anchor points in the group. The structured field in the image is located using one or more kernels.

Claims

1. A method for locating a structured field in a gray-scale image of an object, comprising:

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.

2. A method according to claim 1, wherein the structured field comprises an alphanumeric text field.

3. A method according to claim 2, wherein the text field comprises an address field in a mailed object.

4. A method according to claim 1, and comprising sorting the object responsive to the structured field that is located.

5. A method according to claim 1, wherein choosing the plurality of anchor points comprises choosing the anchor points to be at the vertices of congruent contiguous rectangles.

6. A method according to claim 1, wherein locating the structured field comprises 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.

7. A method according to claim 6, wherein finding the one or more of the regions comprises assigning a ranking level to each of the regions indicative of a likelihood that the region has a desired characteristic.

8. A method according to claim 7, wherein assigning the ranking level comprises evaluating kernels in peripheral regions adjacent to the one or more regions.

9. A method according to claim 7, wherein assigning the ranking level comprises assigning a ranking responsive to respective numbers of vertically dominant points and horizontally dominant points in the one or more regions.

10. A method according to claim 6, wherein locating the structured field comprises using an iterative location method, comprising choosing additional anchor points in the one or more regions and repeating with respect to the additional anchor points the steps of determining the horizontal and vertical variations, defining the vertically- and horizontally-dominant points and identifying the one or more kernels.

11. A method according to claim 10, wherein choosing the additional anchor points comprises choosing anchor points mutually more closely spaced than the anchor points outside the one or more regions.

12. A method according to claim 1, wherein the first predefined condition comprises that the vertical variation be above a predetermined threshold and exceed the horizontal variation by a predetermined factor.

13. A method according to claim 1, wherein the second predefined condition comprises that the horizontal variation be above a predetermined threshold and exceed the vertical variation by a predetermined factor.

14. A method according to claim 1, wherein the third predefined condition comprises that there be at least one vertically dominant point and at least one horizontally dominant point within the group.

15. A method for locating a structured field in a gray-scale image of an object, comprising:

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-dominant those anchor points whose vertical variations exceed their horizontal variations by a predefined factor, and as horizontally-dominant those anchor points whose horizontal variations exceed their vertical variations by a predefined factor; and

locating the structured field in the image responsive to the locations of at least some of the vertically-dominant and horizontally-dominant anchor points.

16. A method according to claim 15, wherein locating the structured field comprises locating a text field.

17. A method according to claim 15, wherein locating the structured field comprises finding a region of the image including a mixture of horizontally- and vertically-dominant anchor points.

18. A method for sorting an object marked with information in a structured field thereon, comprising:

capturing a gray-scale image of the object;

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 those anchor points whose vertical and horizontal variations respectively 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;

locating the structured field using the one or more kernels;

deciphering information contained in the structured field; and

routing the object responsive to the deciphered information.

19. Apparatus for locating a structured field in a gray-scale image of an object, comprising:

an image capture device which forms the gray-scale image of the object; and

an image processing unit which;

chooses a plurality of anchor points in the image;

associates with each anchor point a gray-scale value;

determines 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;

defines as vertically or horizontally dominant respectively those anchor points whose vertical and horizontal variations obey a first or a second predefined condition;

identifies 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

locates the structured field in the image using the one or more kernels.

20. Apparatus according to claim 19, wherein the structured field comprises an alphanumeric text field.

21. Apparatus according to claim 20 wherein the text field comprises an address field in a mailed object.

22. Apparatus according to claim 19, and comprising an object sorter which sorts the object responsive to the structured field that is located.

23. Apparatus for locating a structured field in a gray-scale image of an object, comprising:

an image capture device which forms the gray-scale image of the object; and

an image processing unit which;

chooses a plurality of anchor points in the image;

associates with each anchor point a gray-scale value;

determines 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;

defines as vertically-dominant those anchor points whose vertical variations exceed their horizontal variations by a predefined factor, and as horizontally-dominant those anchor points whose horizontal variations exceed their vertical variations by a predefined factor; and

locates the structured field in the image responsive to the locations of at least some of the vertically-dominant and horizontally-dominant anchor points.

24. Apparatus for sorting an object marked with information in a structured field thereon, comprising:

an image capture device which forms the gray-scale image of the object;

an image processing unit which;

chooses a plurality of anchor points in the image;

associates with each anchor point a gray-scale value;

determines 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;

defines as vertically or horizontally dominant those anchor points whose vertical and horizontal variations respectively obey a first or a second predefined condition;

identifies 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;

locates the structured field using the one or more kernels;

deciphers information contained in the structured field; and

an object router which routs the object responsive to the deciphered information.