Method for line and word segmentation for handwritten text images

• US 10,643,094 B2
• Filed: 07/23/2018
• Issued: 05/05/2020
• Est. Priority Date: 09/29/2016
• Status: Active Grant

• Current Assignee: Konica Minolta Laboratory U.S.A., Inc. (Konica Minolta Inc.)
• Original Assignee: Konica Minolta Laboratory U.S.A., Inc. (Konica Minolta Inc.)
• Inventors: Yang, Duanduan
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US16/043,010
• Publication Number:
  US 20180330181A1
• Time in Patent Office: 652 Days
• Field of Search: None
• CPC Class Codes: G06V 30/153 using recognition of characters or words
• CPC Class Codes: G06V 30/2264 using word shape
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method for segmenting an image containing handwritten text into line segments and word segments. The image is horizontally down sampled at a first ratio. Connected regions in the down-sampled image are detected; horizontal neighboring ones are merged to form lines, to segment the original image into line images. Each line image is horizontally down sampled at a second ratio which is smaller than the first ratio. Connected regions in the down-sampled line image are detected to obtain potential word segmentation positions. A path is a way of dividing the line at some or all of the potential word segmentation positions into multiple path segments; for each of all possible paths, word recognition is applied to each path segment to calculate a word recognition score, and an average word recognition score for the path is calculated; the path with the highest score gives the final word segmentation.

Claims

1. A method implemented on a computer for segmenting an input image into line segments and word segments, the input image being a binary image containing text, the method comprising:

(a) down sampling the input image along a first direction using a first down-sampling ratio;

(b) detecting connected regions in the down-sampled image obtained in step (a);

(c) identifying neighboring connected regions that are neighbors of each other along the first direction that belong to same lines to form line lists containing such neighboring connected regions;

(d) segmenting the input image into a plurality of line segments of the input image, each line segment of the input image being a region of the input image that corresponds to a bounding box in the down-sampled image containing all connected regions in a corresponding line list obtained in step (c); and

for each of the line segments of the input image obtained in step (d),

(e) down sampling the line segment of the input image along the first direction using a second down-sampling ratio;

(f) detecting connected regions in the down-sampled line segment obtained in step (e); and

(g) segmenting the line segment of the input image obtained from step (d) into word segments at one or more word segmentation positions using the connected regions obtained in step (f), wherein the word segmentation positions are a subset of positions corresponding to locations in gaps between the connected regions in the down-sampled line segment of step (e) that have been detected in step (f).

2. The method of claim 1, wherein the first down-sampling ratio is calculated from the input image, and the second down-sampling ratio for each line segment is calculated from the line segment.

3. The method of claim 2, further comprising, before step (a), calculating the first down-sampling ratio, which comprises:

(h1) detecting connected regions in the input image;

(h2) calculating a distance along the first direction between each pair of adjacent connected regions detected in step (h1) that are adjacent to each other along the first direction;

(h3) calculating a first average distance which is an average of all distances calculated in step (h2); and

(h4) setting the first down-sampling ratio based on the first average distance calculated in step (h3).

4. The method of claim 3, wherein in step (h4), the first down-sampling ratio is equal to three times the first average distance.

5. The method of claim 4, further comprising, before step (e), calculating the second down-sampling ratio, which comprises:

(i1) detecting connected regions in the line segment obtained in step (d);

(i2) calculating a distance along the first direction between each pair of adjacent connected regions obtained in step (i1) that are adjacent to each other along the first direction;

(i3) calculating a second average distance which is an average of all distances calculated in step (i2); and

(i4) setting the second down-sampling ratio based on the second average distance calculated in step (i3).

6. The method of claim 5, wherein in step (i4), the second down-sampling ratio is equal to the second average distance.

7. The method of claim 1, wherein step (c) comprises:

(c1) putting all connected regions detected in step (b) in a set;

(c2) selecting one of the connected regions from the set;

(c3) searching for first-direction neighbors of the selected connected region, a first-direction neighbor being a connected region that (1) has a position along a second direction non-parallel to the first direction that is offset from that of the selected connected region by an amount smaller than a predetermined threshold, and (2) among all of the connected regions that meet criterion (1), is located closest along the first direction to the selected connected region;

(c4) adding any first-direction neighbors found in the search of step (c3) to a line list that contains the selected connected region, and removing the first-direction neighbors from the set;

(c5) for the first-direction neighbors found in step (c3), repeating the searching step (c3) and the adding and removing step (c4), until no first-direction neighbors are found in a search, whereby a line list is generated; and

(c6) selecting another connected region from the set, and repeating steps (c3), (c4) and (c5) to generate another line list, until the set is empty,

whereby a plurality of line lists are generated.

8. The method of claim 1, wherein step (g) comprises:

based on the connected region detected in step (f), determining a plurality of potential word segmentation positions for the line segment, each potential word segmentation positions corresponding to a location in a gap between connected regions in the down-sampled line segment;

defining all possible paths for the line segment, each path being a division of the line segment at all or some of the potential word segmentation positions that divide the line segment into a plurality of path segments;

for each path, applying word recognition to each path segment to calculate a word recognition score for the path segment, and averaging word recognition scores for all the path segments to calculate an average word recognition score for the path;

determining a path among all the possible paths for the line segment that has a highest average word recognition score; and

segmenting the line segment into word segments according to the determined path.

17. The method of claim 1, wherein the second down-sampling ratio is smaller than the first down-sampling ratio.

18. The method of claim 1, wherein the first direction is a horizontal direction.

9. A computer program product comprising a computer usable non-transitory medium having a computer readable program code embedded therein for controlling a data processing apparatus, the computer readable program code configured to cause the data processing apparatus to execute a process for segmenting an input image into line segments and word segments, the input image being a binary image containing text, the process comprising:

(a) down sampling the input image along a first direction using a first down-sampling ratio;

(b) detecting connected regions in the down-sampled image obtained in step (a);

(c) identifying neighboring connected regions that are neighbors of each other along the first direction that belong to same lines to form line lists containing such neighboring connected regions;

(d) segmenting the input image into a plurality of line segments of the input image, each line segment of the input image being a region of the input image that corresponds to a bounding box in the down-sampled image containing all connected regions in a corresponding line list obtained in step (c); and

for each of the line segments of the input image obtained in step (d),

(e) down sampling the line segment of the input image along the first direction using a second down-sampling ratio;

(f) detecting connected regions in the down-sampled line segment obtained in step (e); and

(g) segmenting the line segment of the input image obtained from step (d) into word segments at one or more word segmentation positions using the connected regions obtained in step (f), wherein the word segmentation positions are a subset of positions corresponding to locations in gaps between the connected regions in the down-sampled line segment of step (e) that have been detected in step (f).

10. The computer program product of claim 9, wherein the first down-sampling ratio is calculated from the input image, and the second down-sampling ratio for each line segment is calculated from the line segment.

11. The computer program product of claim 10, wherein the process further comprises, before step (a), calculating the first down-sampling ratio, which comprises:

(h1) detecting connected regions in the input image;

(h2) calculating a distance along the first direction between each pair of adjacent connected regions detected in step (h1) that are adjacent to each other along the first direction;

(h3) calculating a first average distance which is an average of all distances calculated in step (h2); and

(h4) setting the first down-sampling ratio based on the first average distance calculated in step (h3).

12. The computer program product of claim 11, wherein in step (h4), the first down-sampling ratio is equal to three times the first average distance.

13. The computer program product of claim 12, wherein the process further comprises, before step (e), calculating the second down-sampling ratio, which comprises:

(i1) detecting connected regions in the line segment obtained in step (d);

(i2) calculating a distance along the first direction between each pair of adjacent connected regions obtained in step (i1) that are adjacent to each other along the first direction;

(i3) calculating a second average distance which is an average of all distances calculated in step (i2); and

(i4) setting the second down-sampling ratio based on the second average distance calculated in step (i3).

14. The computer program product of claim 13, wherein in step (i4), the second down-sampling ratio is equal to the second average distance.

15. The computer program product of claim 9, wherein step (c) comprises:

(c1) putting all connected regions detected in step (b) in a set;

(c2) selecting one of the connected regions from the set;

(c3) searching for first-direction neighbors of the selected connected region, a first-direction neighbor being a connected region that (1) has a position along a second direction non-parallel to the first direction that is offset from that of the selected connected region by an amount smaller than a predetermined threshold, and (2) among all of the connected regions that meet criterion (1), is located closest along the first direction to the selected connected region;

(c4) adding any first-direction neighbors found in the search of step (c3) to a line list that contains the selected connected region, and removing the first-direction neighbors from the set;

(c5) for the first-direction neighbors found in step (c3), repeating the searching step (c3) and the adding and removing step (c4), until no first-direction neighbors are found in a search, whereby a line list is generated; and

(c6) selecting another connected region from the set, and repeating steps (c3), (c4) and (c5) to generate another line list, until the set is empty,

whereby a plurality of line lists are generated.

16. The computer program product of claim 9, wherein step (g) comprises:

based on the connected region detected in step (f), determining a plurality of potential word segmentation positions for the line segment, each potential word segmentation positions corresponding to a location in a gap between connected regions in the down-sampled line segment;

defining all possible paths for the line segment, each path being a division of the line segment at all or some of the potential word segmentation positions that divide the line segment into a plurality of path segments;

for each path, applying word recognition to each path segment to calculate a word recognition score for the path segment, and averaging word recognition scores for all the path segments to calculate an average word recognition score for the path;

determining a path among all the possible paths for the line segment that has a highest average word recognition score; and

segmenting the line segment into word segments according to the determined path.

19. The computer program product of claim 9, wherein the second down-sampling ratio is smaller than the first down-sampling ratio.

20. The computer program product of claim 9, wherein the first direction is a horizontal direction.