Segmentation of text lines in digitized images

• US 6,934,413 B2
• Filed: 06/25/2001
• Issued: 08/23/2005
• Est. Priority Date: 06/25/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Navon, Yaakov
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Hung, Yubin
• Application Number:
  US09/887,475
• Publication Number:
  US 20020196977A1
• Time in Patent Office: 1,520 Days
• Field of Search: 382/101, 382/102, 382173-176, 382/195, 382/198, 382/202, 382/224, 382/225, 382/237, 382/257, 382/264, 382/270, 382/281, 382/289, 382/290, 358/462
• US Class Current: 382/176
• CPC Class Codes: G06V 20/62 Text, e.g. of license plates, overlay texts or captions on TV images
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/424 Postal images, e.g. labels or addresses on parcels or postal envelopes

Abstract

A method for locating symbols arranged in one or more rows in an image includes smearing the image, and fitting line segments through edge points of features in the smeared image. A group is found of the line segments that are in mutual proximity and are mutually substantially parallel. A region of the image that contains the group of the line segments is identified as a possible location of the symbols.

Claims

1. A method for locating symbols arranged in a plurality of parallel rows in an image, the method comprising:

smearing the image;

fitting line segments through edge points of features in the smeared image;

finding a group of the line segments in mutual proximity that are mutually substantially parallel, the group comprising at least a predetermined number of the line segments, which run along respective rows among the plurality of the parallel rows of the symbols at different, respective distances from a given origin; and

identifying a region of the image that contains the group of the line segments as a possible location of the symbols.

2. A method according to claim 1, and comprising binarizing the image before smearing it.

3. A method according to claim 2, wherein binarizing the image comprises applying selective binarization so as to preserve in the binarized image the features of the image that have stroke widths in a predetermined range that is associated with the symbols.

4. A method according to claim 1, wherein smearing the image comprises applying a morphological expansion operator to the features in the image.

5. A method according to claim 4, wherein applying the expansion operator comprises expanding the features in a plurality of different directions, and selecting one of the directions so as to minimize a number of runs of consecutive pixels in the smeared image.

6. A method according to claim 5, wherein fitting the line segments through the edge points comprises fitting the segments through end points of the runs.

7. A method according to claim 1, wherein fitting the line segments comprises applying a Hough transform to the edge points.

8. A method according to claim 1, wherein fitting the line segments comprises determining skew angles of the rows of symbols based on orientations of the line segments.

9. A method according to claim 1, wherein finding the group of the line segments comprises selecting the line segments for inclusion in the group based on numbers of the edge points that are located on each of the selected line segments.

10. A method according to claim 1, wherein finding the group of the line segments comprises finding end points of the line segments, and selecting the line segments for inclusion in the group such that all the end points of all the line segments in the group are within a predetermined range of one another.

11. A method according to claim 1, wherein identifying the region comprises selecting a plurality of regions containing respective groups of the line segments at different skew angles.

12. A computer-implemented method for reading characters arranged in a plurality of parallel rows on an object, comprising:

capturing an image of the object;

smearing the image;

fitting line segments through edge points of features in the smeared image;

finding a group of the line segments in mutual proximity that are mutually substantially parallel, the group comprising at least a predetermined number of the line segments, which run along respective rows among the plurality of the parallel rows of the symbols at different, respective distances from a given origin;

identifying a region of the image that contains the group of the line segments as a location of the rows of the characters; and

applying optical character recognition to read the characters in the region.

13. A method according to claim 12, wherein the object comprises a parcel, and wherein the one or more rows of the characters comprise address information for the parcel.

14. A method according to claim 13, and comprising sorting the parcel responsive to the address information.

15. Apparatus for locating symbols arranged in a plurality of parallel rows in an image, comprising an image processor, which is arranged to smear the image, to fit line segments through edge points of features in the smeared image, to find a group of the line segments in mutual proximity that are mutually substantially parallel, the group comprising at least a predetermined number of the line segments, which run along respective rows among the plurality of the parallel rows of the symbols at different, respective distances from a given origin, and to identify a region of the image that contains the group of the line segments as a possible location of the symbols.

16. Apparatus according to claim 15, wherein the image processor is arranged to binarize the image before smearing it.

17. Apparatus according to claim 16, wherein the processor is arranged to binarize the image by applying selective binarization so as to preserve in the binarized image the features of the image that have stroke widths in a predetermined range that is associated with the symbols.

18. Apparatus according to claim 15, wherein the processor is arranged to smear the image by applying a morphological expansion operator to the features in the image.

19. Apparatus according to claim 18, wherein the processor is arranged to expand the features in a plurality of different directions, and to select one of the directions so as to minimize a number of runs of consecutive pixels in the smeared image.

20. Apparatus according to claim 19, wherein the processor is arranged to fit the line segments through end points of the runs.

21. Apparatus according to claim 15, wherein the processor is arranged to fit the line segments by applying a Hough transform to the edge points.

22. Apparatus according to claim 15, wherein the processor is arranged to determine skew angles of the rows of symbols based on orientations of the line segments.

23. Apparatus according to claim 15, wherein the processor is arranged to select the line segments for inclusion in the group based on numbers of the edge points that are located on each of the selected line segments.

24. Apparatus according to claim 15, wherein the processor is arranged to find end points of the line segments, and to select the line segments for inclusion in the group such that all the end points of all the line segments in the group are within a predetermined range of one another.

25. Apparatus according to claim 15, wherein the processor is arranged to select a plurality of regions containing respective groups of the line segments at different skew angles.

26. Apparatus for reading characters arranged in a plurality of parallel rows on an object, comprising:

an image capture device, arranged to capture an image of the object; and

an image processor, which is arranged to smear the image, to fit line segments through edge points of features in the smeared image, to find a group of the line segments in mutual proximity that are mutually substantially parallel, the group comprising at least a predetermined number of the line segments, which run along respective rows among the plurality of the parallel rows of the symbols at different, respective distances from a given origin, to identify a region of the image that contains the group of the line segments as a location of the rows of the characters, and to apply optical character recognition to read the characters in the region.

27. Apparatus according to claim 26, wherein the object comprises a parcel, and wherein the one or more rows of the characters comprise address information for the parcel.

28. Apparatus according to claim 27, and comprising a sorting device, which is arranged to sort the parcel responsive to the address information.

29. A computer software product for locating symbols arranged in a plurality of parallel rows in an image, the product comprising a computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to smear the image, to fit line segments through edge points of features in the smeared image, to find a group of the line segments in mutual proximity that are mutually substantially parallel, the group comprising at least a predetermined number of the line segments, which run along respective rows among the plurality of the parallel rows of the symbols at different, respective distances from a given origin, and to identify a region of the image that contains the group of the line segments as a possible location of the symbols.

30. A product according to claim 29, wherein the instructions cause the computer to binarize the image before smearing it.

31. A product according to claim 30, wherein the instructions cause the computer to binarize the image by applying selective binarization so as to preserve in the binarized image the features of the image that have stroke widths in a predetermined range that is associated with the symbols.

32. A product according to claim 29, wherein the instructions cause the computer to smear the image by applying a morphological expansion operator to the features in the image.

33. A product according to claim 32, wherein the instructions cause the computer to expand the features in a plurality of different directions, and to select one of the directions so as to minimize a number of runs of consecutive pixels in the smeared image.

34. A product according to claim 33, wherein the instructions cause the computer to fit the line segments through end points of the runs.

35. A product according to claim 29, wherein the instructions cause the computer to fit the line segments by applying a Hough transform to the edge points.

36. A product according to claim 29, wherein the instructions cause the computer to determine skew angles of the rows of symbols based on orientations of the line segments.

37. A product according to claim 29, wherein the instructions cause the computer to select the line segments for inclusion in the group based on numbers of the edge points that are located on each of the selected line segments.

38. A product according to claim 29, wherein the instructions cause the computer to find end points of the line segments, and to select the line segments for inclusion in the group such that all the end points of all the line segments in the group are within a predetermined range of one another.

39. A product according to claim 29, wherein the instructions cause the computer to select a plurality of regions containing respective groups of the line segments at different skew angles.

40. A product according to claim 29, wherein the symbols comprise characters, and wherein the instructions cause the computer to apply optical character recognition to read the characters in the identified region.

41. A product according to claim 40, wherein the image comprises a parcel, and wherein the one or more rows of the symbols comprise address information for the parcel.

42. A product according to claim 41, wherein the instructions cause the computer to sort the parcel responsive to the address information.