GENERATING AN OBJECT MAP FROM A PLURALITY OF BINARY IMAGES

• US 20170286815A1
• Filed: 03/31/2016
• Published: 10/05/2017
• Est. Priority Date: 03/31/2016
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Bradburn, Brent Michael, Xiao, Zuguang, Gao, Mengqi, Wang, Lu, Allebach, Jan P.
• Granted Patent: US 10,460,219 B2
• Time in Patent Office: Days
• CPC Class Codes: G06K 15/12 by photographic printing , e.g. by laser printers
• CPC Class Codes: G06K 15/14 by electrographic printing, e.g. xerography; by magnetographic printing G06K15/12 takes precedence
• CPC Class Codes: G06K 15/1855 Combining raster data and graphic primitives
• CPC Class Codes: G06K 15/1874 with provisions for treating some of the print data differently
• CPC Class Codes: G06K 15/1881 Halftoning halftoning of still images in general H04N1/405, H04N1/52

Abstract

In an example, a method is described that includes dividing an input image into a plurality of strips, where each strip is smaller than a whole of the input image. A plurality of binary images is then generated, where each of the binary images corresponds to one of the strips. Connected component labeling is performed on the binary images, one binary image at a time. An object map for the input image is then generated based on the results of the connected component labeling.

Claims

1. A method, comprising:

dividing an input image into a plurality of strips, where each strip of the plurality of strips is smaller than a whole of the input image;

generating a plurality of binary images, where each binary image of the plurality of binary images corresponds to a strip of the plurality of strips;

performing connected component labeling on the plurality of binary images, where the connected component labeling operates on the plurality of binary images one at a time; and

generating an object map for the input image based on results of the connected component labeling for the plurality of binary images.

2. The method of claim 1, wherein the plurality of binary images includes at least three binary images corresponding to each strip of the plurality of strips.

3. The method of claim 2, wherein the at least three binary images include a binary image in which edge magnitudes for all white pixels in the binary image are at least equal to a strong edge threshold.

4. The method of claim 2, wherein the at least three binary images include a binary image in which edge magnitudes for all white pixels in the binary image are less than a strong edge threshold.

5. The method of claim 2, wherein the at least three binary images include a binary image in which edge magnitudes for all white pixels in the binary image are less than a weak edge threshold.

6. The method of claim 1, wherein the performing comprises, for a first binary image of the plurality of binary images:

executing a first pass in which foreground pixels of the first binary image are assigned labels that identify connected components contained in the first binary image; and

executing a second pass, subsequent to the first pass, in which the connected components are classified as being of interest or not of interest according to a type of the binary image.

7. The method of claim 6, wherein the executing the second pass comprises:

freeing in memory any of the labels that correspond to connected components that exist entirely in the first binary image; and

freeing in memory any of the labels that correspond to connected components that are merged with other connected components and re-labeled.

8. The method of claim 7, wherein the first pass is performed for a second binary image of the plurality of binary images after the first pass is executed for the first binary image, but prior to executing the second pass for the first binary image.

9. The method of claim 8, wherein performing the first pass for the second binary image comprises:

reusing at least one of the labels that has been freed in memory by assigning the at least one of the labels to a foreground pixel in the second binary image having no previously identified neighbor pixels.

10. The method of claim 8, wherein at least one connected component of the connected components is an unbounded connected component that crosses a boundary between the first binary image and the second binary image and also crosses a boundary between the second binary image and a third binary image.

11. The method of claim 10, further comprising:

classifying the unbounded connected component as of interest or not of interest after the first pass is executed for the second binary image but before the second pass is executed for the second binary image.

12. The method of claim 6, further comprising:

classifying root components of the connected components as being of interest or not of interest, after executing the first pass but prior to executing the second pass.

13. A non-transitory machine-readable storage medium encoded with instructions executable by a processor, the machine-readable storage medium comprising:

instructions to divide an input image into a plurality of strips, where each strip of the plurality of strips is smaller than a whole of the input image;

instructions to generate a plurality of binary images, where each binary image of the plurality of binary images corresponds to a strip of the plurality of strips;

instructions to perform connected component labeling on the plurality of binary images, where the connected component labeling operates on the plurality of binary images one at a time; and

instructions to generate an object map for the input image based on results of the connected component labeling for the plurality of binary images.

14. The non-transitory machine-readable storage medium of claim 13, wherein the instructions to perform connected component labeling comprise, for a first binary image of the plurality of binary images:

instructions to execute a first pass in which foreground pixels of the first binary image are assigned labels that identify connected components contained in the first binary image; and

instructions to execute a second pass, subsequent to the first pass, in which the connected components are classified as being of interest or not of interest according to a type of the binary image.

15. The non-transitory machine-readable storage medium of claim 14, wherein the instructions to execute the second pass comprise:

instructions to free in memory any of the labels that correspond to connected components that exist entirely in the first binary image; and

instructions to free in memory any of the labels that correspond to connected components that are merged with other connected components and re-labeled.

16. The non-transitory machine-readable storage medium of claim 15, wherein the first pass is performed for a second binary image of the plurality of binary images after the first pass is executed for the first binary image, but prior to executing the second pass for the first binary image.

17. The non-transitory machine-readable storage medium of claim 16, wherein instructions to perform the first pass for the second binary image comprise:

instructions to reuse at least one of the labels that has been freed in memory by assigning the at least one of the labels to a foreground pixel in the second binary image having no previously identified neighbor pixels.

18. The non-transitory machine-readable storage medium of claim 16, wherein at least one connected component of the connected components is an unbounded connected component that crosses a boundary between the first binary image and the second binary image and also crosses a boundary between the second binary image and a third binary image.

19. An apparatus, comprising:

a buffer for dividing an input image into a plurality of strips, where each strip of the plurality of strips is smaller than a whole of the input image;

an edge detector coupled to the buffer, for generating a plurality of binary images, where each binary image of the plurality of binary images corresponds to a strip of the plurality of strips;

a connected component labeler for performing connected component labeling on the plurality of binary images, where the connected component labeling operates on the plurality of binary images one at a time; and

an object map builder for generating an object map for the input image based on results of the connected component labeling for the plurality of binary images.

20. The apparatus of claim 19, further comprising:

a component array coupled to the connected component labeler and to the object map builder, where each array element of the component array contains an index that corresponds to a label for use by the connected component labeler.