Fast efficient window region coalescing in a two-pass auto-windowing environment

• US 7,277,191 B2
• Filed: 06/27/2001
• Issued: 10/02/2007
• Est. Priority Date: 06/27/2001
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Metcalfe, David J., Shiau, Jeng-nan
• Primary Examiner(s): Moore; David
• Assistant Examiner(s): Thompson; James A.
• Application Number:
  US09/894,160
• Publication Number:
  US 20030002087A1
• Time in Patent Office: 2,288 Days
• Field of Search: 358/1.9, 358/450, 358/453, 358/462, 358/538, 358/540, 358/1.12, 358/461, 382/165, 382/540, 345/501, 345/622, 711/202, 711/218
• US Class Current: 358/1.12
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone

Abstract

A method and apparatus are provided for the processing of an image, such as a document. The invention determines the location of differing content types within the document allowing specialized processing of various content types. The invention performs the identification of pixels having similar content characteristics into windows during the first scanning pass of the document by the use of an identifier equivalence table to update selected memory locations to a base identifier during processing. A second pass processing is available to enhance or alter the image by the use of the information gathered during first pass processing. The present invention benefits from a very low memory requirement while being able to determine windows extending the length or width of the image.

Claims

1. A method of processing content of an image, comprising the steps of:

automatically determining window regions in the image without user assistance by performing a first-pass processing of the image in a selected direction on a line by line basis, wherein the image content is organized in parallel lines of content, the first-pass processing comprising the steps of;

identifying a plurality of line segments of the image content, wherein said plurality of line segments are parallel to a first axis;

allocating line segment identifiers to the plurality of line segments, the allocating comprising;

determining a first segment tag for a first line segment of the plurality of line segments of the image content on a first line parallel to said first axis;

writing a first identifier into a first memory location of an equivalence table and assigning said first identifier to said first line segment;

determining a second segment tag for a second line segment of the plurality of line segments of the image content on a second line parallel and proximate to said first line when said second line segment overlaps a position of said first line segment along said first axis;

if said first segment tag equals said second segment tag, writing said first identifier to a second memory location of said equivalence table; and

if said first segment tag does not equal said second segment tag, writing a second identifier into said second memory location of said equivalence table and assigning said second identifier to said second line segment, wherein said second identifier is not equal to a previously used identifier;

updatinq said identifier number equivalence table, the updating comprising;

reading a past memory location of said equivalence table corresponding to a past identifier and having a corresponding past segment tag to determine a past memory location content;

reading a present memory location of said equivalence table corresponding to a present identifier and having a corresponding present segment tag to determine a present memory location content, wherein said past segment tag is equal to said present segment tag and said past identifier is not equal to said present identifier;

searching for a base identifier of said present identifier, the searching comprising;

determining if said present memory location content points to said present memory location and designating said present memory location as said base identifier if said present memory location content points to said present memory location; and

if said present memory location content does not point to said present memory location, utilizing said present memory location content as said present memory location and repeating said searching steps; and

writing said base identifier to said past memory location; and

storing a graphical representation of the image in a page storage buffer;

generating a windowed image by performing a second-pass processing of the stored graphical representation of the image based on the written identifiers of the first-pass processing; and

outputting the windowed image to at least one of a printed image and a digital image displayed on an output device.

2. The method of processing an image of claim 1, further comprising the step of determining a location of a third line segment by identifying said third line segment on one of said first line and said second line, as contiguous with one of the group of said first line segment and said second line segment extending a lesser distance in a first direction along said first axis such that said third line segment overlaps a position of the other of said group of said first line segment and said second line segment along said first axis.

3. The method of processing an image of claim 1, wherein said first line segment and said second line segment are contiguous.

4. The method of processing an image of claim 1, wherein said first identifier is stored in a first side of a ping pong memory and said second identifier is stored in a second side of a ping pong memory.

5. The method of processing an image of claim 1, wherein all line segments on said first line and all line segments on said second line are processed before processing line segments on a different line.

6. The method of processing an image of claim 1, further including performing an interdocument delay processing during an interdocument delay period following the first-pass processing and preceding the second-pass processing, the interdocument delay processing comprising the steps of:

reducing each of the memory location contents to a respective base identifier; and

producing a window retagging table for use in the second-pass processing, wherein the second-pass processing of the stored graphical representation of the image is based on the written identifiers of the first-pass processing and the produced window retagging table.

7. An apparatus for processing content of an image, comprising:

a memory adapted to store at least one of the group of a first identifier of a first line segment of the image content on a first line and a second identifier of a second line segment of the image content on a second line and storing the image in a page storage buffer portion of the memory;

a processor coupled to said memory and adapted to automatically determine window regions in the image without user assistance by, in a first-pass processing while the image is being received on a line by line basis, forming and frequently updating an identifier equivalence table by comparing said first identifier to said second identifier, determining a first segment tag for said first line segment, determining that said first line segment is eligible for a base identifier search if said first identifier does not equal said second identifier when said first segment tag equals a second segment tag for said second line segment and when said first line segment and said second line segment are neighboring line segments, and conducting a base identifier search for said first line segment, the processor also adapted to store received portions of the image in a page storage buffer portion of the memory thereby generating a stored graphical representation of the image, and further adapted to perform a second-pass processing to produce a windowed image based on the stored graphical representation of the image and determinations and searches of the first-pass processing; and

an output device adapted to receive the windowed image and produce at least one of a printed image and a digital image displayed on the output device;

wherein said first line and said second line are parallel to a first axis and said first line segment overlaps said second line segment.

8. The apparatus for processing an image of claim 7, wherein said base identifier search comprises the steps of:

reading a first memory location of said memory to determine a first memory location content;

pointing to a further memory location of said memory, corresponding to said first memory location content;

if said first memory location content does not point to said first memory location, read a further memory location content of said further memory location;

continuing to point to succeeding memory locations of said memory until a memory location content points to its own memory location and designating said memory location as a base identifier; and

writing said base identifier to said first memory location.

9. The apparatus for processing an image of claim 7, wherein a first scan line of a page of said image is said first line and a last scan line of said page of said image is said second line and all remaining scan lines of said page of said image are selectively, alternatively designated as said first line and said second line during processing.

10. The apparatus for processing an image of claim 7, wherein said first line segment and said second line segment are contiguous.

11. The apparatus of claim 7, further comprising an input device coupled to said processor to enable said processor to determine said first segment tag.

12. The apparatus of claim 11, wherein said input device is a scanner.

13. The apparatus for processing an image of claim 7, the processor further adapted to, in an interdocument delay processing during an interdocument delay period following the first-pass processing and preceding the second-pass processing, reduce each of a plurality of memory location contents to a respective base identifier, and produce a window retagging table for use in the second-pass processing, wherein the second-pass processing of the stored graphical representation of the image is based on the determinations and searches of the first-pass processing and the produced window retagging table.

14. A method for processing content of an image comprising parallel rows of pixels, the method comprising the steps of:

automatically determining window regions in the image without user assistance by performing a first-pass processing of the image content in a selected direction on a row by row basis, the first-pass processing

comprising the steps of;

for each row of the image, allocating pixel identifiers to the pixels, the allocating comprising;

determining a pixel tag corresponding to a pixel content type of a pixel of a present row;

determining a pixel identifier based on said pixel tag and pixel identifiers and pixel taps of neighboring pixels in said present row and in a previously allocated row, wherein said determined pixel identifier is selected from a neighboring pixel having an equal pixel tag or a new pixel identifier not equal to a previously used pixel identifier; and

forming line segments of neighboring pixels of said present row having common pixel identifiers;

reviewing said line segments to associate neighboring line segments having common pixel tags but having differing pixel identifiers by associating said differing pixel identifiers; and

storing a graphical representation of the image in a page storage buffer;

performing a second-pass processing of the stored graphical representation of the image based on identifiers and associations of the first-pass processing to produce an enhanced image; and

outputting the enhanced image to at least one of a printed image and a digital image displayed on an output device.

15. The method of claim 14, further comprising the step of, in the first-pass processing, assigning a line segment identifier to each of said line segments, wherein said line segment identifier corresponds to said pixel identifiers of said pixels forming each of said line segment.

16. The method of claim 15, further comprising the step of, in the first-pass processing, storing said line segment identifiers for each of said line segments in said present row and said previously allocated row in a line segment memory.

17. The method of claim 14, further comprising the step of, in the first-pass processing, forming an identifier equivalence table to store said associations of said line segments of said previously allocated row neighboring line segments of said Present row and having common pixel tags.

18. The method of claim 17, further comprising the step of, in the first-pass processing, performing a base identifier search to update said identifier equivalence table and associate line segments of at least a third row, the base identifier search being performed selectively during an inter-scanline delay time between each scan line, or during alternate scan lines.

19. The method of claim 18, further comprising the step of, following the first-pass processing and preceding the second-pass processing, processing said identifier equivalence table to assign window labels during an interdocument delay period, wherein each window label is associated with an area of said image having pixels of a common content type.