Generating an object map from a plurality of binary images

• US 10,460,219 B2
• Filed: 03/31/2016
• Issued: 10/29/2019
• 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.)
• Inventors: Bradburn, Brent Michael, Xiao, Zuguang, Gao, Mengqi, Wang, Lu, Allebach, Jan P.
• Primary Examiner(s): Chen, Huo Long
• Application Number:
  US15/087,246
• Publication Number:
  US 20170286815A1
• Time in Patent Office: 1,307 Days
• Field of Search: None
• 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, by a processor element, 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, by the processor element, a plurality of binary images, where each binary image of the plurality of binary images corresponds to a strip of the plurality of strips, wherein the plurality of binary images comprises at least three binary images corresponding to each strip of the plurality of strips and wherein the at least three binary images each comprise a respective binary image in which edge magnitudes for all white pixels in the respective binary image are at least equal to at least one of;

a strong edge threshold and a weak edge threshold;

executing, by the processor element, for a first binary image of the plurality of binary images,

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

a second pass, subsequent to the first pass, in which;

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

any of the labels that correspond to connected components that are merged with other connected components are re-labeled to reduce a number of labels stored in a memory data structure; and

generating, by the processor element, 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 executing the second pass further comprises classifying as being of interest or not of interest according to a type of the first binary image.

3. The method of claim 2, 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.

4. The method of claim 1, 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.

5. The method of claim 4, wherein executing 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.

6. The method of claim 4, 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.

7. The method of claim 6, 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.

8. A non-transitory machine-readable storage medium encoded with instructions that when executed by a processor cause the processor 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;

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, wherein the plurality of binary images comprises at least three binary images corresponding to each strip of the plurality of strips and wherein the at least three binary images each comprise a respective binary image in which edge magnitudes for all white pixels in the respective binary image are at least equal at least one of;

a strong edge threshold and a weak edge threshold;

execute, for a first binary image of the plurality of binary images,

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

a second pass, subsequent to the first pass, in which;

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

any of the labels that correspond to connected components that are merged with other connected components are re-labeled to reduce a number of labels stored in a memory data structure; and

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

9. The non-transitory machine-readable storage medium of claim 8, wherein to execute the second pass, the instructions are further to cause the processor to:

classify the connected components as being of interest or not of interest according to a type of the first binary image.

10. The non-transitory machine-readable storage medium of claim 8, 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.

11. The non-transitory machine-readable storage medium of claim 10, wherein to execute the first pass for the second binary image, the instructions are further to cause the processor 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.

12. The non-transitory machine-readable storage medium of claim 10, 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.

13. 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;

a processor; and

a memory on which is stored machine readable instructions that when executed by the processor, cause the processor 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, wherein the plurality of binary images comprises at least three binary images corresponding to each strip of the plurality of strips and wherein the at least three binary images each comprise a respective binary image in which edge magnitudes for all white pixels in the respective binary image are at least equal to at least one of;

a strong edge threshold and a weak edge threshold;

execute, for a first binary image of the plurality of binary images,

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

a second pass, subsequent to the first pass, in which;

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

any of the labels that correspond to connected components that are merged with other connected components are re-labeled to reduce a number of labels stored in a memory data structure; and

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

14. The apparatus of claim 13, wherein the instructions are further to cause the processor to:

implement the object map in an electrophotography operation to print the input image.