CN101091186A - Segment and generate compact representations for digital images - Google Patents

Abstract

Methods (100), apparatuses, and computer program products for automatically generating compact representations of color documents are disclosed. In the method, digital images of a color document page are segmented (110) into connected components in a round in block raster order. A digital image of a page is divided into foreground and background images using layout analysis (120) based on compact, connected component statistics of the entire page. At least one portion of the background image is repaired in a block raster order in one pass at a location where the at least one portion of the foreground image obscures the background image (520). The foreground and background images are merged (130) to form a compact document. Methods, apparatuses, and computer program products for segmenting a digital image comprising a plurality of pixels are also disclosed.

Description

Segment and generate compact representations for digital images

Copyright Notice

This patent specification contains material that is protected by copyright. The copyright owner has no objection to the reproduction of this patent specification or related material from the relevant Patent Office file for reading purposes, but otherwise reserves all copyrights.

technical field

The present invention relates generally to the field of digital image processing, and more particularly to generating high-level descriptions of digital images.

Background technique

Image segmentation is the division or separation of an image into semantically or visually coherent regions. Each region is a group of connected pixels with similar attribute or attributes. A basic property used for segmentation is the magnitude of brightness for monochrome images, and color components for color images.

The proliferation of scanning technologies combined with ever-increasing computational processing power has led to many advances in the field of document analysis systems. These systems can be used to extract semantic information from scanned documents, usually by means of OCR techniques. Such a system can also be used to improve the compression of document images by selectively using the appropriate compression method according to the content of each part of the page. Improved document compression lends itself to applications such as archiving and electronic distribution.

Segmentation is a processing stage for document image analysis where low-level pixels must first be segmented into primitive objects before high-level processing such as region classification and layout analysis can be performed. Layout analysis classifies primitive objects into known object types according to some predetermined rules about the layout of the document. Typically, layout analysis does not analyze raw scanned image data, but works on alternative data sets, such as blobs or connected components from segments of pages. In addition to individual object properties, layout analysis can also use object groupings in order to determine their classification.

Several known methods for image segmentation are described below.

Thresholding is the simplest method for segmentation, and it can be fast and efficient if the image to be processed is two-level (eg black and white document image). However, if the image is complex, with regions of multiple brightness or color levels, some of these regions may be lost during the binarization process. More sophisticated thresholding techniques employ adaptive or multilevel thresholding, where threshold estimation and binarization are performed at a local level. However, these methods still cannot segment objects correctly.

Clustering-based methods, such as k-means and vector quantization, tend to produce good segmentation results, but they are iterative algorithms that require many rounds. Therefore, this approach can be slow and difficult to implement.

The split and merge image segmentation technique is based on a quadtree data representation, where a square image segment is split into 4 quadrants if the attributes of the original image segment are not consistent. If 4 adjacent squares are found to be identical, merge these squares into a single square made of these 4 adjacent squares. The splitting and merging process usually starts at the full image level. Therefore, processing can start only after the entire page has been buffered, which requires high memory bandwidth. Additionally, this approach tends to be computationally intensive.

Region growing is a well known method for image segmentation and is one of the conceptually simplest methods. Adjacent pixels with similar attributes or attributes are grouped together to form segment regions. In practice, however, rather complex constraints must be imposed on the growth pattern in order to achieve acceptable results. Existing region growing methods may have several undesirable effects, since these methods tend to be biased towards the location of the initial seed. Different seed choices may bring different segmentation results, and if the seed point is on an edge, there may be problems.

The proliferation of scanning technologies combined with ever-increasing computational processing power has led to many advances in the field of document analysis systems. These systems can be used to extract semantic information from scanned documents, usually by means of OCR techniques. This technique is used in an increasing number of applications, such as automatic form reading, and can also be used to improve the compression of documents by selectively using the appropriate compression method according to the content of each part of the page. Improved document compression lends itself to applications such as archiving and electronic distribution.

Some document analysis systems perform layout analysis to divide documents into regions classified according to their content. Typically, layout analysis does not analyze raw scanned image data, but instead works on alternative data sets, such as blobs or connected components from segments of pages. In addition to individual object properties, layout analysis can also use object groupings in order to determine their classification.

Typically, binary segmentation of the pages is performed to generate data for layout analysis, and this can be obtained by simply thresholding the original image. One advantage of this binary segmentation is that the segmented objects reside within a simple containment hierarchy that facilitates layout analysis. Unfortunately, the layout of many complex color documents cannot be fully represented in binary images. The reduction of information content inherent in the conversion from color to binary images can lead to the degradation of important features, and even to the loss of the detailed structure of the document.

Color segmentation for page document analysis therefore has advantages in preserving the content of the page, but also brings it additional complexity. First, segmentation analysis itself becomes trickier and increases processing requirements. Second, because segmented page objects do not form containment hierarchies, analysis of these segmented page objects is complicated. This limits the accuracy and effectiveness of layout analysis.

The document layout analysis system may also employ techniques for validating text classification of document regions. Some of these methods use histogram analysis of pixel sums, shadowing and projected contours. These methods are generally unreliable because it is difficult to apply robust statistics to this method, and it is difficult to adjust for text that may be a single line or many lines and does not know the character set and text alignment in the document.

Contents of the invention

According to a first aspect of the invention there is provided a method of segmenting a digital image comprising a plurality of pixels. The method comprises the steps of: generating a plurality of blocks of pixels from a digital image; and generating at least one connected component for each block using the blocks of pixels in a single round. The generating step further includes: segmenting the block of pixels into at least one connected component, each connected component comprising a set of pixels that are spatially connected and semantically related; and combining the at least one connected component of the block with previously processed at least one connected component segmented by at least one other block is merged; and the position of the connected component of the block in the image is stored in a compact form.

Semantically related pixels may include similarly colored pixels.

The generating step may comprise the sub-steps of: arranging the digital image into a plurality of bands, each band comprising a predetermined number of consecutive rows of pixels; and buffering and processing the bands one after the other. This processing step in turn includes the sub-steps performed for each currently buffered band: arranging the current band into blocks of pixels; and buffering and processing the blocks of the current band one by one for the generation step.

The storing sub-step may include storing M-1 binary bitmaps, wherein M connected components are in one block, and M is an integer.

The storing sub-step may include storing the index map.

The segmentation sub-step may include: estimating a number of representative colors for each block; quantizing each block into a representative color; and forming connected components from each quantized block. The segmenting sub-step may also include: merging the formed subsets of connected components. The merging substep may include collecting statistics on the connected components. Statistics may include one or more of bounding box, pixel count, border length, and mean color. The method may further comprise the step of deleting formed connected components considered to be noise. The noise may include connected components having a pixel count below a predetermined threshold and a boundary length to pixel count ratio above another predetermined threshold. The merging step may include: merging the connected components of the block with the connected components of the blocks to the left and above; and updating statistics of the combined connected components. Statistics may include one or more of bounding box, pixel count, fill ratio, and average color.

The estimating sub-step may include: forming a histogram associated with a plurality of color bins based on the YUV data of the pixels in each block; classifying each block based on the histogram statistics; and merging the bin colors based on the block classification to form a representative sex color. The method also includes the step of forming an index map for each pixel in one round. The quantizing step may include: quantizing the non-empty library to a representative color; creating a library map to the representative color; and remapping the index map to the representative color using the library map. The forming sub-step may include: determining a brightness band based on Y values; determining a color column based on U and V values; accumulating pixel colors into a map library; and incrementing a pixel count of the map library. The step of determining the luma bands may also include luma band anti-aliasing. The step of determining the color column may also include color column anti-aliasing.

The merging step may include the following sub-steps performed for each connected component within the current block that touches the left and upper boundaries: finding a list of connected components that touch the current connected component along a common boundary; and determining the best candidate for merging.

According to another aspect of the invention there is provided an apparatus comprising a processor and a memory for segmenting a digital image comprising a plurality of pixels according to any one of the preceding aspects of the method.

According to another aspect of the present invention, there is provided a computer program product comprising a computer readable medium having recorded therein a digital pixel comprising a plurality of pixels according to any one of the preceding methods. A computer program for image segmentation.

According to another aspect of the invention, a method of automatically generating a compact representation of a color document is provided. The method comprises the steps of: segmenting a digital image of a color document page into connected components in block raster order in one round; segmenting the digital image of the page using layout analysis based on a compact, connected component statistic for the entire page being the foreground and background images; inpainting at least a portion of the background image in block raster order in one pass where at least a portion of the foreground image obscures the background image; and merging the foreground and background images to form a compact document.

The method may also include the step of downsampling the background image. Furthermore, the method may comprise the step of compressing the background image. The compression step may involve lossy compression. Additionally, the method may include different compression of the lossy compressed background image.

According to another aspect of the invention there is provided an apparatus comprising a processor and memory for automatically generating a compact representation of a color document according to any one of the preceding aspects of the method.

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded thereon a compact representation for automatically generating a color profile according to any one of the preceding method aspects computer program.

According to another aspect of the invention, a method of analyzing a digital image comprising a plurality of pixels is provided. The method comprises the steps of: segmenting a digital image into objects, wherein the segments are represented by more than two labels; providing each object with a set of attributes; for a subset of objects, determining adjacent objects at a shared boundary using a containment measure whether there is a parent-child relationship between them; based on the attributes of the objects, forming groups of objects that share a common parent; and classifying objects according to their attributes and groupings.

Containment can be determined using a bounding box around each object and information describing touching relationships between objects. If two objects touch at the boundary, and one object's bounding box completely contains the other object's bounding box, then the object contains the other object.

The forming a group step may include: considering pairs of child objects in a list of children of a common parent; and using object properties, determining whether each pair should be grouped together. Only adjacent objects in a column of child objects with the same parent can be considered for grouping. Objects can be grouped based on bounding box and color information.

A group of objects may be classified as text based on a text-like quality test of the objects within the group. A test for text-like quality may include: identifying for each object a single value representing the location of the object; forming a histogram of these values; and identifying text according to attributes of the histogram.

The present invention may also include the step of adding other objects to the text classification group of objects according to their attributes, regardless of their parent-child attributes.

According to another aspect of the invention, a method of analyzing a digital image comprising a plurality of pixels of a document page is provided. The method includes the steps of: segmenting the digital image to form objects based on the image; forming groups of objects; and determining whether each group of objects represents text. The determining step includes: identifying a single value for each object based on the position of the object on the page; forming a histogram of the values; and identifying the text according to the properties of the histogram.

An attribute of the histogram may be the total number of objects in the library that have more than the specified number of objects in the histogram. Alternatively, the attribute may be the sum of squares of the counts within the histogram.

A single value per object representing the object's location may be the sides of the object's bounding box.

According to another aspect of the invention there is provided an apparatus comprising a processor and a memory for analyzing a digital image comprising a plurality of pixels according to a method according to any one of the preceding aspects.

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded thereon a method for analyzing a digital image comprising a plurality of pixels according to a method according to any one of the preceding aspects computer program.

According to another aspect of the present invention, a method of inpainting a digital image comprising a plurality of pixels is provided. The method includes the steps of: generating a plurality of blocks of pixels from a digital image; and varying pixel values of at least one run of pixels in raster order for at least one block. The altering step includes the following sub-steps performed for each block: determining the beginning and ending pixels of a string of pixels within the block associated with an object, the string comprising adjacent pixels grouped together; modifying at least one pixel value of an object within the string; and determining a measure of activity (acitivity) of a pixel within the block that does not correspond to an object; and if the measure of activity of the block is less than a predetermined threshold, All pixel values within each block having at least one string of pixels are changed to the set value.

The method further includes the step of modifying at least one pixel value of pixels of the enlarged object outside the object based on pixel values of pixels outside the enlarged object.

This generating step may comprise the sub-steps of: arranging the digital image into a plurality of bands, each band comprising a predetermined number of consecutive rows of pixels; and buffering and processing the bands one after the other. This processing step may comprise the following sub-steps performed for each current buffer band: arranging the current band into a plurality of pixel blocks; and buffering and processing the blocks of the current band one by one for the changing step.

The string comprises adjacent pixels in a raster row of pixels of the block.

The method also includes the step of compressing each block using a block-based compression method. The block-based compression method may be JPEG. The method may also include the step of further compressing the blocks based on the block compression using another compression technique.

At least one pixel value of the object may be modified according to pixel values of pixels outside the object, using a value interpolated from pixel values to the left and right of the string, or a value from a pixel to the left of the string.

All pixel values of each block having at least one string of pixels may be changed to the average value of previously processed blocks, or the average value of the visible pixels within the block.

The method may further comprise the step of, if the end of the enlarged object pixel string is not found, setting the color value of the pixel to the color value of a pixel not corresponding to an object to the left of the enlarged object pixel string.

Pixel values can be color values.

According to another aspect of the present invention, there is provided an apparatus comprising a processor and a memory for repairing a digital image comprising a plurality of pixels according to the method of any one of the preceding aspects.

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded therein a method for restoring a digital image comprising a plurality of pixels according to any one of the preceding aspects computer program.

According to another aspect of the present invention, there is provided a method of changing pixel values of a digital image comprising a plurality of pixels, at least some of which correspond to an object in the image, the method comprising the steps of arranging the digital image as a plurality of bands, each band comprising a predetermined number of consecutive pixel rows; and sequentially buffering and processing the bands one after the other. This processing step may comprise the following sub-steps performed on each current buffer strip: arranging the current strip into a plurality of pixel blocks; and processing these blocks sequentially one by one. The block processing step comprises, for each block, the following sub-steps: determining activity measures for pixels within the block that do not correspond to objects within the image; change to a pixel value; compress the block using JPEG; and compress the JPEG-compressed block using another compression method.

Each band may comprise 16 rows of pixels of the digital image, the blocks comprise 16x16 pixels, and the compression step is performed in a pipelined manner.

The step of changing the color values of all pixels within the block may include setting the color values of the pixels to color values obtained by linear interpolation between pixels not corresponding to objects immediately left and right of the expanded object pixel string , the expanded target pixels are pixels outside the string and adjacent to the string.

The method may further comprise the step of setting the color values of pixels within the block to an average color value of pixels not corresponding to objects within the block.

The method may further comprise the step of setting the color value of the pixels within the block to the average color of previous blocks.

The pixels of the dilated object may be determined by dilating the mask defining the location of the object.

Other compression methods may include ZLIB.

Pixel values can be color values.

According to another aspect of the present invention there is provided an apparatus comprising a processor and memory for altering the pixel values of a digital image comprising a plurality of pixels, at least some of which correspond to image objects in .

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded therein a method for altering a digital image comprising a plurality of pixels according to any one of the preceding aspects A computer program of pixel values at least some of which correspond to objects in an image.

According to another aspect of the invention, a method of segmenting a digital image comprising a plurality of pixels is provided. The method comprises the steps of: generating a plurality of pixel blocks from a digital image; and using the pixel blocks in a round to generate at least one connected component for each block. The generating step further includes: segmenting the block of pixels into at least one connected component, each connected component comprising a set of spatially connected and semantically related pixels; merging at least one connected component segmented from one other block; and storing the position of the connected component of the block in the image in a compact form.

Semantically related pixels may include similarly colored pixels.

The storing sub-step may include storing M-1 binary bitmaps, wherein M connected components are in one block, and M is an integer.

The storing sub-step may include storing the index map.

The segmentation sub-step may include: estimating a number of representative colors for each block; quantizing each block into a representative color; and forming connected components from each quantized block. The segmenting sub-step may also include: merging the formed subsets of connected components. The merging substep may include collecting statistics on the connected components. Statistics may include one or more of bounding box, pixel count, border length, and mean color. The method may further comprise the step of removing formed connected components considered to be noise. The noise may include connected components having a pixel count below a predetermined threshold and a boundary length to pixel count ratio above another predefined threshold. The merging step may include: merging the connected components of the block with the connected components of the blocks to the left and above; and updating statistics of the combined connected components. Statistics may include one or more of bounding box, pixel count, fill ratio, and average color.

The estimating sub-step may include: forming a histogram associated with a plurality of color bins based on the YUV data of the pixels in each block; classifying each block based on the histogram statistics; and merging the bin colors based on the block classification to form a representative sex color. The method also includes the step of forming an index map for each pixel in one round. The quantizing step may include: quantizing the non-empty library to a representative color; creating a library map to the representative color; and remapping the index map to the representative color using the library map. The forming sub-step may include: determining a brightness band based on Y values; determining a color column based on U and V values; accumulating pixel colors into a map library; and incrementing a pixel count of the map library. The step of determining the luma bands may also include luma band anti-aliasing. The step of determining the color column may also include color column anti-aliasing.

The merging step may include the following sub-steps performed for each connected component within the current block that touches the left and upper boundaries: finding a list of connected components that touch the current connected component along a common boundary; and determining the best candidate for merging.

According to another aspect of the invention there is provided an apparatus comprising a processor and a memory for segmenting a digital image comprising a plurality of pixels according to any one of the preceding aspects of the method.

According to another aspect of the present invention, there is provided a computer program product comprising a computer readable medium having recorded therein a digital pixel comprising a plurality of pixels according to any one of the preceding methods. A computer program for image segmentation.

According to another aspect of the invention, a method of automatically generating a compact representation of a color document is provided. The method comprises the steps of: segmenting a digital image of a color document page into connected components in the order of a block raster in one round; using layout analysis to segment the digital image of the page dividing the image into foreground and background images; inpainting at least one portion of the background image in a single pass in a block-raster order where at least one portion of the foreground image obscures the background image; and merging the foreground and background images to form a compact document .

The method may also include the step of downsampling the background image. Additionally, the method may include the step of compressing the background image. The compression step may involve lossy compression. Additionally, the method may include different compression of the lossy compressed background image.

According to another aspect of the invention there is provided an apparatus comprising a processor and memory for automatically generating a compact representation of a color document according to any one of the preceding aspects of the method.

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded thereon a compact representation for automatically generating a color profile according to any one of the preceding method aspects computer program.

According to another aspect of the invention, a method of analyzing a digital image comprising a plurality of pixels is provided. The method comprises the steps of: segmenting a digital image into objects, wherein the segments are represented by more than two labels; providing each object with a set of attributes; for a subset of objects, determining adjacent objects at a shared boundary using a containment measure whether there is a parent-child relationship between them; based on the attributes of the objects, forming groups of objects that share a common parent; and classifying the objects according to their attributes and groupings.

Containment can be determined using a bounding box around each object and information describing touching relationships between objects. If two objects touch at the boundary, and one object's bounding box completely contains the other object's bounding box, then the object contains the other object.

The forming a group step may include: considering pairs of child objects in a list of children of a common parent; and using object properties, determining whether each pair should be grouped together. Grouping can only be considered for adjacent objects in a column of child objects that have the same parent. Objects can be grouped based on bounding box and color information.

A group of objects may be classified as text based on a text-like quality test of the objects within the group. A test for text-like quality may include: identifying for each object a single value representing the location of the object; forming a histogram of these values; and identifying text according to attributes of the histogram.

The present invention may also include the step of adding other objects to the text classification group of objects according to their attributes, regardless of their parent-child attributes.

According to another aspect of the invention, a method of analyzing a digital image comprising a plurality of pixels of a document page is provided. The method includes the steps of: segmenting the digital image to form objects based on the image; forming groups of objects; and determining whether each group of objects represents text. The determining step includes: identifying a single value for each object based on the position of the object on the page; forming a histogram of the values; and identifying the text according to the properties of the histogram.

An attribute of the histogram may be the total number of objects in the library that have more than a specified number of objects in the histogram. Alternatively, the attribute may be the sum of squares of the counts within the histogram.

A single value per object representing the object's position may be the edge of the object's bounding box.

According to another aspect of the invention there is provided an apparatus comprising a processor and a memory for analyzing a digital image comprising a plurality of pixels according to a method according to any one of the preceding aspects.

According to another aspect of the present invention, there is provided a computer program product comprising a computer readable medium having recorded therein a method for analyzing a digital image comprising a plurality of pixels according to a method according to any one of the preceding aspects. Image computer program.

According to another aspect of the present invention, a method of inpainting a digital image comprising a plurality of pixels is provided. The method includes the steps of: generating a plurality of pixel blocks from a digital image; and, for at least one block, varying pixel values of at least one series of pixels in a raster order. The altering step comprises the following sub-steps performed for each block: determining the start and end pixels of a string of pixels associated with an object within the block, the string comprising adjacent pixels grouped together; modify at least one pixel value of an object within the string; and determine an activity measure for a pixel that does not correspond to an object within the block; and if the measure of activity for the block is less than a predetermined threshold, will have at least one of the string All pixel values within each block of pixels are changed to the set value.

The method further includes the step of modifying at least one pixel value of pixels of the enlarged object outside the object based on pixel values of pixels outside the enlarged object.

This generating step may comprise the sub-steps of: arranging the digital image into a plurality of bands, each band comprising a predetermined number of consecutive rows of pixels; and buffering and processing the bands one after the other. This processing step may comprise the following sub-steps performed on each currently buffered band: arranging the current band into a plurality of pixel blocks; and buffering and processing the blocks of the current band one by one for the changing step.

The string comprises adjacent pixels in a raster row of pixels of the block.

The method may also include the step of compressing individual blocks using a block-based compression method. The block-based compression method may be JPEG. The method may also include the step of further compressing the blocks based on the block compression using another compression technique.

At least one pixel value of the object may be modified according to pixel values of pixels outside the object, using a value interpolated from pixel values to the left and right of the string, or a value from a pixel to the left of the string.

All pixel values of each block having at least one string of pixels may be changed to the average value of previously processed blocks, or the average value of the visible pixels within the block.

The method may further comprise the step of, if the end of the enlarged object pixel string is not found, setting the color value of the pixel to the color value of a pixel not corresponding to an object to the left of the enlarged object pixel string.

Pixel values can be color values.

According to another aspect of the present invention, there is provided an apparatus comprising a processor and a memory for repairing a digital image comprising a plurality of pixels according to the method of any one of the preceding aspects.

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded therein a method for restoring a digital image comprising a plurality of pixels according to any one of the preceding aspects computer program.

According to another aspect of the present invention, there is provided a method of changing pixel values of a digital image comprising a plurality of pixels, at least some of which correspond to objects in the image, the method comprising the steps of arranging the digital image as a plurality of strips, each strip comprising a predetermined number of consecutive rows of pixels; and sequentially buffering and processing the strips one after the other. This processing step may comprise the following sub-steps for each current buffer strip: arranging the current strip into a plurality of pixel blocks; and processing these blocks sequentially one after the other. The block processing step comprises, for each block, the following sub-steps: determining activity measures for pixels within the block that do not correspond to objects within the image; change to a pixel value; compress the block using JPEG; and compress the JPEG-compressed block using another compression method.

Each band may comprise 16 rows of pixels of the digital image, the blocks comprise 16x16 pixels, and the compression step is performed in a pipelined fashion.

The step of changing the color values of all pixels within the block may include setting the color values of the pixels to a color obtained by linear interpolation between pixels not corresponding to objects immediately left and right of the expanded object pixel string value, the pixels to be expanded are pixels outside the string and adjacent to the string.

The method may further comprise the step of setting the color values of pixels within the block to an average color value of pixels not corresponding to objects within the block.

The method may further comprise the step of setting the color value of the pixels within the block to the average color of the previous block.

The pixels of the dilated object may be determined by dilating the mask defining the location of the object.

Other compression methods may include ZLIB.

Pixel values can be color values.

According to another aspect of the present invention there is provided an apparatus comprising a processor and memory for altering the pixel values of a digital image comprising a plurality of pixels, at least some of which correspond to image objects in .

According to another aspect of the present invention there is provided a computer program product comprising a computer readable medium having recorded therein a method for altering a digital image comprising a plurality of pixels according to any one of the preceding aspects A computer program of pixel values, at least some of which correspond to objects in an image.

Description of drawings

Several embodiments are described below with reference to the accompanying figures, in which:

Figure 1 is a high-level flowchart providing an overview of segmenting, analyzing and compressing a digital image according to an embodiment of the invention;

Fig. 2 is the flow chart of the color segmentation step of Fig. 1;

Fig. 3 is a detailed flowchart of the steps of obtaining the next pixel in Fig. 2;

Fig. 4 is a flowchart of the layout analysis steps of Fig. 1;

FIG. 5 is a flowchart of the steps of generating a compressed output image of FIG. 1;

Figure 6 is a block diagram of an image including the character "i" and associated connected components;

FIG. 7 is a block diagram of a general-purpose computer system on which embodiments of the present invention may be implemented;

8 is a block diagram of a system for generating compressed output for scanned input pages according to an embodiment of the present invention;

Fig. 9 is a detailed flowchart of the color connected component analysis and spot statistics steps of Fig. 10;

Fig. 10 is a flowchart of the color segmentation step of Fig. 2;

Fig. 11 is a detailed flowchart of the color quantization step of Fig. 10;

Figure 12 is a detailed flowchart of the steps of forming new spots or growing existing spots of Figure 9;

Fig. 13 is a flowchart of the step of merging between tiles of Fig. 10;

Figure 14 is a flowchart of the steps of processing the best spots and CC pairs of Figure 13;

FIG. 15 is a block diagram showing an example of blob merging processing;

FIG. 16 is a block diagram illustrating the merging between the states of the current tile and two adjacent tiles;

FIG. 17 is a table showing the conditions for merging between tiles;

FIG. 18 is an example of the result of the CC mapping process of FIG. 14;

FIG. 19 is a flowchart of the intra-tile merging step of FIG. 10;

Fig. 20 is a flowchart of the grouping CC steps of Fig. 4;

FIG. 21 is a flowchart of the steps of checking the CC group of FIG. 4;

Fig. 22 is a flowchart of the steps of finding a child CC of a group in Fig. 20;

Figure 23 is a flowchart of the initial grouping step of Figure 20;

Fig. 24 is a flowchart of the check alignment step of Fig. 21;

Figure 25(a) is an image showing a simple example of segmentation based on more than two quantization levels;

Figures 25(b) and (c) are images showing the corresponding results of the binary segmentation of the image of Figure 25(a);

Figure 26 is an illustration of a region of a document containing two objects, the letters "g" and "h";

Figure 27(a) shows a histogram of the values of the base of the bounding box of the image of Figure 27(b);

Figure 27(b) shows a selection of irregularly arranged bounding boxes for a segmented portion from an image;

Figure 27(c) shows the corresponding histogram for the page of Figure 27(d);

Figure 27(d) shows the arrangement of bounding boxes on a page for text groups;

Fig. 28 is a block diagram of the color spot division system;

Figures 29(a) to 29(c) are images of the color histogram output, including the original patch, index map and palette, where the gray parts in the upper and lower parts of the palette represent empty libraries;

Fig. 30 is a flowchart of the steps of repairing the patch of Fig. 5;

Fig. 31 is a flow chart of the steps of forming a tile foreground bit mask in Fig. 30;

32 is a flowchart of the steps of inpainting pixels and measuring patch activity of FIG. 30;

Figure 33 is a flowchart of the patch planarization step of Figure 30;

Figure 34 is a block diagram of example pixels in a background image tile and the corresponding pixels inspected in the full-resolution foreground mask;

Figure 35 includes graphs of examples of one-dimensional repair;

FIG. 36 is a block diagram illustrating blob processing for an example using 6×6 tiles;

Figure 37 includes images showing an example of blob merging;

Figure 38 includes images showing raw tiles and merged blob outputs for comparison purposes;

Figure 39 is a block diagram illustrating merging spots on tiles in raster order;

FIG. 40 is a flowchart showing the steps of forming a 2D histogram and a first palette of FIG. 11;

FIG. 41 is a flow chart illustrating the steps of forming a second palette of FIG. 11;

Figure 42 is a flowchart illustrating the steps of generating a two-color palette of Figure 41;

Figure 43 is a flowchart showing the steps of generating a multi-color palette of Figure 41;

Figure 44 is a flowchart illustrating the step of associating pixels with a second palette of Figure 11;

FIG. 45 is a detailed flowchart illustrating the steps of mapping two-level tiles of FIG. 44;

FIG. 46 is a detailed flowchart illustrating the steps of mapping multi-color tiles of FIG. 44;

Figure 47 is a flowchart of the steps of analyzing the histogram of Figure 11 and classifying the tiles;

Figure 48 is a table showing CC and blob candidate counts before and after updating all operating conditions;

Figure 49 is a block diagram illustrating an example of merging blobs and CC candidates;

FIG. 50 is a flowchart illustrating the steps of the post-merge process of FIG. 10;

Figure 51 is a block diagram of a system according to another embodiment of the present invention;

Figure 52 is a block diagram of the color segmentation module of Figure 51; and

FIG. 53 is a diagram showing a Delaunay triangulation and a Voronoi diagram of a set point.

Detailed ways

Methods, apparatus and computer program products for processing and compressing digital images are disclosed. In the following description, several specific details are presented, including specific lossless compression techniques, color space, spatial resolution, tile size, etc. However, it will be apparent to those skilled in the art from this disclosure that modifications and/or substitutions can be made without departing from the scope and spirit of the invention. In other instances, specific details may have been omitted in order not to obscure the invention.

Where steps and/or features with the same reference number are referenced within any one or more of the drawings, for the purposes of this description, these steps and/or features have the same function(s) or operation ( multiple), unless a contrary intent appears.

In the context of this specification, the word "comprises" has an open-ended, non-exclusive meaning: "consisting essentially but not necessarily exclusively", but neither "consisting essentially of" nor "consisting only of.. .composition". Variations of the word "comprising", such as "comprise" and "comprises", have corresponding meanings.

The contents of the detailed description are organized into the following chapters.

1 Overview

2 color segments

2.1 Get the next patch of the input image

2.2 Form the color segmentation of the patch

2.2.1 Color Quantization

2.2.1.1 Form 2D histogram and first palette

2.2.1.2 Analyzing histograms and classifying images

2.2.1.3 Form the second palette

2.2.1.3.1 Generate 2 color palette

2.2.1.3.2 Generating a multi-color palette

2.2.1.4 Associating pixels with the second palette

2.2.1.4.1 Mapping two-level patches

2.2.1.4.2 Mapping multi-level tiles

2.2.2 Color CC Analysis and Blob Statistics

2.2.2.1 Formation of spots

2.2.2.2 Example of blob merging

2.2.3 Intra-patch merging

2.2.4 Merging between patches

2.2.4.1 Merging conditions between patches

2.2.4.2 Example of merging between patches

2.2.4.3 Dealing with Optimal Spots and CC Pairs

2.2.4.4 CC mapping results

2.2.5 Post-merge processing

2.3 Segmentation example

3 layout analysis

3.1 Grouping CCs

3.1.1 Finding the child of the father CC

3.1.2 Initialization grouping

3.1.2.1 Group test of two CCs

3.2 Check Grouping

3.2.1 Check alignment

3.2.2 Examples of Alignment

4 produces a compressed output image

4.1 Repair patch

4.1.1 Form patch foreground bit masking

4.1.2 Inpainting pixels and measuring patch activity

4.1.3 Repair example

4.1.4 Chip planarization

5 hardware embodiment

5.1 Color segmentation module

6 computer implementation

7 Industrial applicability

Hereinafter, the above parts are described in detail in the above order.

1 Overview

A first embodiment of the present invention is a process running on a general purpose computer. Figure 1 provides a high level overview of the process 100 of segmenting, analyzing and compressing digital images. The input to the process 100 is preferably an RGB image with a resolution of 300 dpi. However, with appropriate modifications to process 100, images in other color spaces may also be input. Likewise, images of different resolutions can be input. At step 110, color segmentation of the image into connected components (CCs) is performed using a single pass of processing on the input image. Using a single pass, digital images can be processed rapidly, allowing processing of large numbers of high-resolution images. A connected component is a group of similarly colored pixels that are all connected together (touching). For example, the pixels forming the body or backbone of the letter "i" printed in black ink on white paper form a connected component, the points on the "i" form another CC, and any white Pixels constitute another CC. FIG. 6 shows an image 600 including the character "i", where black dots represent black pixels and white dots represent white pixels. A backbone CC 610 for "i" and a point CC 612 for "i" are shown. Another result CC 614 for blank pixels is also shown.

As part of the segmentation, compact information and statistics describing the CCs are computed. The numbers are down-sampled and provided directly to step 130 . At step 120, placement analysis is performed on the CCs using this compact CC information and statistics. The layout analysis determines the layout of features on a page, including, for example, text characters, paragraphs, tables, and images. At step 130, one or more foreground images are created using the layout information. The foreground image is generally composed of the text characters identified in step 120, and is preferably a binary image. The foreground image may be stored at an input resolution (eg, 300dpi), while the background image may be stored at a lower resolution (eg, 150dpi). Foreground elements are removed from the background image. Then, the foreground and background are compressed using different techniques and stored in a composite image format. The composite format can be, for example, a PDF document. Each of color segmentation, layout analysis, and compressing digital images is described in separate sections below.

One application for embodiments of the present invention is to analyze raster pixel images from a scanner and extract as much high-level information as possible. From this information, a high-level description of the page can be generated. For this purpose, the system can be designed to run faster by performing pixel analysis in hardware. However, as will be apparent from the description below, the system may also be implemented entirely in software. Also, while the specific output format PDF is described below, the system can be modified to utilize other page description formats as output formats.

FIG. 8 is a high-level block diagram of a system 800 for generating a compressed or compact representation 850 of a scanned input document 810 according to an embodiment of the invention. The system 800 includes a front-end module 820 , a middle module 830 and a back-end module 830 . Front-end module 820 is a patch-based front-end, preferably implemented in hardware, but could be a combination of an ASIC and software executed by an embedded processor. Tile raster order is a tile-based processing method in which tiles are processed one at a time, top-to-bottom and left-to-right. This module performs color segmentation on the input image and provides the background image of the tile to the backend module 840 (indicated by the arrow). The front-end module 820 performs color connected component analysis at full page resolution (eg, 300dpi). The front-end module 820 also generates connected components (CCs) from the digital image 810 and provides the CCs to intermediate modules that perform layout analysis. This module can be fully implemented in software. Front-end module 820 provides the downsampled image to module 840 . The output of the intermediate module 830 is provided to a backend module 840 which performs patch-based inpainting and generates a compact representation of the digital image 810 . Like the front-end module 820, the back-end module 840 may be implemented at least in part in hardware with software executing on an embedded processor and an ASIC. This compact output can include a lower spatial resolution digital image and a higher resolution foreground bitmap.

The front-end module 820 performs all the analytical work involved in examining each pixel and forming color CCs for regions of semantically related pixels. The output from the front end module 820 is information about all color CCs on the page. Information for each CC includes bounding box, mean color, contact list and number of pixels. When implementing an algorithm in hardware for best performance, the algorithm should be bandwidth efficient. For image processing tasks, the algorithm does not randomly access the entire scanned page. Instead, the algorithm works on small patches at a time.

2 color segments

FIG. 2 shows step 110 of FIG. 1 in more detail. The processing shown in Fig. 2 works on tiles of the input image, the size of these tiles may be, for example, 32x32 pixels. Tiles can be processed in raster order - ie, left to right, and top to bottom. The first tile to be processed is the top-left tile of the input image, and the last tile processed is the bottom-right tile of the input image. This tile division is done for efficiency purposes.

At step 210, the next tile of the input image to be processed is obtained. Each tile can be efficiently accessed using pointer information. Step 210 is described in more detail with reference to FIG. 3 . The processing of steps 220, 230, 240 and 250 is limited to the pixels of the current tile. In step 220, dehalfting is optionally performed on the current tile. For example, scanned input documents processed in this way may contain halftones from the print process. Halftones can make subsequent analysis difficult and may not compress well. Thus, halftones can be detected and removed using this step 220 . Merely as an example, the following dehalfting process can be performed. De-halfting works on 16x16 tiles. Each input tile of 32×32 RGB pixels can be divided into 4 tiles of 16×16 and each one processed separately. Halftone detection can work on one color channel (ie, R, G, and B) at a time. If halftone is detected in any channel, halftone removal can be performed on all channels. To detect halftones, each pixel in the tile is quantized to 4 levels. The range of input color channel values is 0-255. The 4 grades are the ranges 0-63, 64-127, 128-191 and 192-255. The number of level changes between pixels adjacent to each other can be measured. This measurement can be done both horizontally and vertically.

Since halftones are usually small dots, this detection requires that the number of changes be large, and that the number of horizontal changes be smaller than the number of vertical changes. This prevents a change in level caused by the edge of a text character from being detected as a halftone. A threshold for detection can be specified. If halftones are detected in a 16x16 tile, the halftones can be removed using, for example, spatial blurring. Halftone detectors can also use information from previously analyzed tiles. For example, if a tile touching the current tile has halftones detected in the tile, the current tile may also contain halftones. When using this information, the threshold can be adjusted to relax the halftone detection requirement or to make it more stringent.

In step 230, if the color space of the current tile is not already in the YUV color space, a conversion is performed to convert the pixels within the tile to the YUV color space. Therefore, this step optionally depends on the color space of the input image. Although the YUV color space is used in this embodiment, other color spaces may be employed without departing from the scope and spirit of the invention. The conversion formula used to convert from RGB to YUV may be the same as used, for example, in the Independent JPEG Group (IJG) JPEG library.

In step 240, color segmentation to form connected components (CCs) is performed on the current tile, and compact information and statistics about the CCs in the tile are computed. A color CC consists of one or more semantically related blobs spanning one or more tiles. For example, semantically related blobs can have similar colors. A blob is a group of connected pixels with similar shading properties in a single tile. Blob partitioning is a process of segmenting colors and forming connected component representations. Each CC has the following statistics: pixel size, mean color, binary mask, blob boundary length, and bounding box. Figure 10 shows this step in more detail.

At step 250, the current tile is down-sampled to form a corresponding portion of the background image. For example, bin filters could be used to downsample 2:1 in two dimensions, but other methods could be employed without departing from the scope and spirit of the invention. At decision step 260, a check is made to determine if any more tiles remain to be processed. If the result of step 260 is negative (ie, all tiles in the image have been processed), processing terminates. However, if the result of step 260 is yes, processing continues at step 210 .

2.1 Get the next patch of the input image

FIG. 3 shows step 210 of FIG. 2 in detail. Process 210 operates on a strip of input digital images. A strip of an image is a number of consecutive image lines. The height of each strip can be the same as the height of the patch. So, for example, the first 32 lines of the image form a band, and in this case the first band of the image; the next 32 lines of the image form the next band, and so on. The width of each band may be the width of the input image. At decision step 310, a check is made to determine if another tape needs to be read in. When all tiles of the current band have been processed, another band needs to be read in. Another time another tape needs to be read in is the first time step 310 is performed because the tape has not yet been read. If the result of step 310 is yes, processing continues at step 320 . Otherwise, processing continues at step 340 .

At step 320, the next strip of data is read from the input image, for example, from disk into a buffer in memory. The memory buffer may be arranged to contain each row of pixels of the band in consecutive memory locations. Additionally, a record is kept of the memory location where each row begins: ie, a pointer to each striped row. In step 330, a variable tx that determines the tile to be accessed—the current tile—is initialized (ie, set to 0). In step 340, the row pointer information is updated to point to the current tile. Other processes calling process 210 of FIG. 3 obtain new tiles by referencing the row pointer information updated in step 340 . The row pointer information may include a pointer for each tile row. Therefore, each tile can have 32 row pointers. The given row pointer points to the memory location of the first pixel of the tile in the given row. The row pointer information can be updated by stepping each row pointer along (tile width ^* tx) memory locations beyond the pointer pointing to the start of each corresponding strip line. At step 350, the variable tx is incremented by 1 so that the next time the process 210 of FIG. 3 is invoked, another tile is entered into the process.

2.2 Form the color segmentation of the patch

Color blob division is an image segmentation algorithm that works in tile raster order. A blob is a connected group of pixels of the same quantized label within a single patch. Each blob has the following statistics: pixel size, mean color, binary mask, blob boundary length, and bounding box. Its purpose is to segment a document image into a set of non-overlapping connected components, where each connected component contains a connected set of semantically related pixels, e.g., a set of pixels within a particular text letter forms a connected component, around Pixels within a portion of the image that bears the text form another connected component, and so on.

FIG. 28 is a block diagram of a color blob segmentation system 2800 with four modules 2810 , 2820 , 2830 and 2840 . The color quantization module 2810 receives an input color tile (eg, 24-bit pixel value for RGB color space), determines the number of dominant colors in the tile, and quantizes the tile according to the dominant color. The dominant colors and quantized tiles are provided as input to the connected components and blob statistics module 2820, which performs an 8-way connected components analysis on the quantized tiles in a single raster pass. In the same raster wheel, blob statistics such as pixel count, mean color, blob boundary length, and bounding box information are collected. The blobs and statistics are provided as input to the intra-tile merge module 2830, which reduces the number of spurious and small blobs within a tile by merging blobs based on color, size and boundary statistics. The resulting blobs and statistics from this module 2830 are provided as input to the inter-tile merge module 2840, which groups blobs within the current tile with touching blobs in adjacent (left and top) tiles according to the blob statistics together to form a connected component that is the output of the system 2800. This will be further described with reference to the processing of FIG. 10 .

Figure 10 is a detailed flowchart of step 240 for segmenting the image into colors CC. As part of the segmentation process, compact information and statistics describing the CCs are computed. The segmentation process begins by receiving an input tile of pixels from step 230 . At decision block 1005, a check is made to determine if the patch is flat. If the tile is flat, processing continues at step 1040 to the inter-tile merge stage. Otherwise, processing continues at step 1010. At step 1010, color quantization is performed on the tiles. Color quantization finds the dominant color within a tile using three main steps, regardless of pixel geometry: 1) color reduction, 2) tile classification, and 3) finding dominant color and quantization. Determine the dominant colors within the input tiles by a color histogram method. Creates color-labeled quantized tiles by quantizing input tile pixels according to dominant colors. A dominant color is the visually distinct color within a tile that is perceived by a human viewer. The algorithm is suitable for hardware (HW) implementation and is also quite fast in software (SW).

Step 1020 performs an 8-way connected component analysis on the quantized tiles in a single raster wheel to form blobs. In step 1030, an intra-tile merging process is performed to reduce the number of spurious and small blobs within a tile by merging blobs based on color, size and boundary information. At step 1040, merge between tiles is performed. The blobs identified in the quantized tile are compared with the blobs identified in the two previously processed tiles to the left and above the current tile for merging into a color CC. Thus, a color CC includes one or more similarly colored blobs across one or more tiles. Thus, the color CC has the same type of statistics described above for blobs, except for boundary information.

At step 1050, the blobs within the current tile and the color CC formed by those blobs are stored in a compact tile state data structure. This tile state does not contain pixel data. The patch state contains only the information needed to merge the newly created blob into an existing color CC. The inter-tile merge process 1040 can be performed with high memory efficiency because only two or fewer tile states are required for merging with the current tile at any stage of the segmentation process. Additionally, step 1050 updates the contact list for each color CC. A contact list describes which connected components are adjacent to each other. This contact list is generated in the front end as part of the color CC analysis. Step 240 in FIG. 2 generates a contact list. Processing then terminates.

2.2.1 Color Quantization

The purpose of color quantization is to reduce the entire color input to a reduced set of colors in preparation for connected component generation. To find the dominant color, each input pixel is checked once and a histogram is generated. Embodiments of the present invention employ a histogram that uses luma as the first dimension and combines the two chroma components as the second dimension. This is dissimilar to a traditional color histogram that divides the library into three dimensions based on axes of three color components. Embodiments of the present invention produce compact histograms that help find good dominant colors more easily. According to the characteristics of the histogram, the patches are classified into three categories - flat, two-level, multicolor. Generates palettes for tiles based on tile classification. After the palette is generated, each pixel is assigned a quantization label based on the palette color to which the pixel is mapped. The method is designed for high speed processing and low memory requirements. Flat patches have only one quantized label. Two-level patches have two quantized labels. Multicolor tiles have up to 4 quantization labels.

The color quantization step 1010 of FIG. 10 is further developed in FIG. 11 . A brief description of each step in Figure 11 is given here, followed by a detailed description of each step. At step 1110, a 2D histogram and an index map are simultaneously formed using the first palette. FIG. 40 provides further details of step 1110. In step 1120, tile classification is performed based on the statistics of the 2D histogram. FIG. 47 provides further details of step 1120. At step 1130, a second palette is formed based on the tile classification. This involves compressing the first palette. FIG. 41 provides further details of step 1130. At step 1140, the pixels are associated with the second palette. Remaps the index map to one of the second palette colors in order to produce quantized tiles with quantized labels. Then, the processing is terminated.

2.2.1.1 Form 2D histogram and first palette

FIG. 40 shows the processing of step 1110 of FIG. 11 in more detail. The entire color patch of the input is quantized into an indexed map in one round, in pixel raster order, by a predetermined mapping method. Fig. 29(a) shows an example of an input raw tile, and the resulting index map. Mapping can be configured to target 32 color banks organized into 8 luma bands and 4 color columns. Each color bank can have a color accumulator, a pixel counter, and a registration ID that is set with the YUV value of the first pixel placed within that bank. The predetermined mapping method may be changed according to the state of the 2D histogram. As a result, there is no predetermined color for each bin and the pixel color order can affect the composition of the first palette. Finally the average color of each non-empty bin constitutes the first palette. Figure 29(c) shows the resulting palette, where the upper and lower gray portions represent empty libraries.

At step 4010, pixels with color values (YUV) are obtained from the tile. A predetermined mapping is performed in step 4015 to map pixels to luma bands and color bins (ie, bin_mapped). A predetermined mapping can be as follows:

band=Y>>5, and

column=(|U-REF_U|+|V-REF_V|)*NORMALISING_FACTOR[band].

A chromaticity value of gray can be used for REF_U and REF_V: (ie, for 8-bit RGB input data, REF_U=128, REF_V=128). Precompute the NORMALISING_FACTOR for each band using REF_U and REF_V chosen to normalize each band to 4 bins in the RGB color space. The NORMALISING_FACTOR can be generated using the pseudocode of Table 1.

Table 1

                   

Set max_dist[0:7]to 0

for each r in 0 to 255

{

for each g in 0 to 255

{

for each b in 0 to 255

{

c = RGB2YUV(r, g, b);

Band=c.y＞＞5;

|c.u-128|+|c.v-128|;

If(dist＞max_dist[band])

max_dist[band]=dist;

}

}

}

for each band in 0 to 7

NORMALISING_FAGTOR[band]＝1/max_dist[band]*4

                   

Steps 4020 to 4025 perform optional "with anti-aliasing" for two-stage patch contour enhancement. At step 4020, if "band anti-aliasing" is enabled, and the difference in brightness between the mapped band and the upper or lower band does not exceed a specified threshold (eg, 16), at step 4025 "band anti-aliasing" is performed. ". Otherwise processing continues at step 4035.

In step 4025, band anti-aliasing is performed. Try to find a close non-empty library within the upper or lower sideband. The candidate library is the one mapped with band-1 or band+1. Replace the mapped library (bin_mapped) with the candidate library in either of the following two conditions:

1 Candidate library is not empty, and its registration ID (Y) distance is less than 16, and bin_mapped is empty.

2 The candidate library and bin_mapped are not empty, and Y is closer to the registration ID (Y) of the candidate library than the registration ID (Y) of bin_mapped.

Steps 4035 through 4055 perform a "library anti-aliasing" process. Step 4035 checks if the mapped library (bin_mapped) is empty. If the mapping repository is not empty, step 4040 checks for mapping errors as follows:

max(|U-registration ID(U)|, |V-registration ID(V)|)<MAX_BIN_ERROR[band],

where MAX_BIN_ERROR[band] is one-eighth of the max_dist within each band defined in the pseudocode above for generating normalization factors.

If step 4035 returns false (No), processing continues at step 4040. Otherwise, processing continues at step 4045. In decision step 4040, a check is made to determine if the mapping error exceeds a specified threshold, which is the maximum library error for the band.

If the mapping error is within the threshold, processing continues at step 4060. Otherwise, execute step 4055 to find a closer library. At step 4055, the search starts at column 0 and moves forward to column 3 in the map band. Terminate the search when any of the following conditions are met:

1 finds an empty library, and

2 Discover libraries with mapping errors within allowed thresholds

If the search of step 4055 terminates on condition 1, the (YUV) value is registered in an empty bin, and this empty bin replaces bin_mapped. If both conditions fail, replace bin_mapped with the library with the smallest mapping error. Processing then continues at step 4060.

After the test of step 4035, if the mapped repository is empty, processing continues at step 4045. In decision step 4045, a check is made to determine that an adjacent non-empty bank within the same band has been found. Step 4045 searches from columns 0 to 3 in an attempt to find a non-empty bank that satisfies the previously defined mapping error threshold. If such a library is found, bin_mapped is replaced in step 4052 with an empty library, and processing then continues at step 4052. Otherwise if step 4052 returns false (No), bin_mapped is recorded with the color (YUV) value in step 4050 and processing continues at step 4060.

At step 4060, the pixel color (YUV) is accumulated in the mapped library (bin_mapped), and the pixel count in bin_mapped is incremented. In step 4065, the location of bin_mapped is recorded for the current pixel. At step 4070, a check is made to determine if more pixels remain in the tile. If yes, processing continues at step 4010. Otherwise, it continues at step 4075, where each non-empty bin's pixel count is divided by its accumulated color. The average color of each non-empty bin forms the first palette. Processing then terminates.

2.2.1.2 Analyzing histograms and classifying images

Tile classification is a method of discovering the dominant colors within a tile. Based on the distribution and color variation within the palette, patches were classified into 3 groups: flat, two-level, and multicolor. Flat patches have visually invariant colors to the human eye and generally form a cluster within the 2D histogram. A flat palette has up to 3 colors with little color variation. Two-level tiles have two unique colors and are usually arranged vertically within a 2D histogram. A two-level palette has colors that span a few lightness bands, but the color variation within each lightness band is small. Multi-color patches are usually unrolled over a large library within a 2D histogram. The multi-color palette includes patches that failed the first two tests.

Step 1120 of FIG. 11 analyzes the library distribution and color properties in the 2D histogram and classifies the tiles accordingly. Divide the patches into 3 groups: flat, two-level, and multi-colored. Figure 47 shows the processing of step 1120 in more detail. In step 4710, a flat patch test is performed. If yes, in step 4712 the tile is classified as flat. Otherwise, a second test is performed at step 4720 to determine if the tile is two-level. If the result of the two-level test is yes, at step 4722 the tile is classified as being two-level. Otherwise, at step 4724 the tile is classified as multi-colored. Steps 4710 and 4720 are described in more detail below.

Regarding step 4710, a first LumRange is defined as the range between the highest and lowest luminance bands for which the bank is not completely empty. For a patch to pass the flatness test, the patch must meet all 3 conditions below:

1 The number of non-empty libraries <= 3

2 LumRange <= 2; and

3 FlatColourVariance＜FLAT_COLOUR_VARIANCE

where FlatColourVariance is defined as the sum of pixel-count-weighted Manhattan distances between the largest bin and the remaining bins. The threshold parameter may be FLAT_COLOUR_VARIANCE=15.

Regarding step 4720 for a patch to pass the two-stage test, the patch must meet all 3 conditions below:

1 The number of non-empty libraries <= BILEVEL_MAX_BIN_CNT

2 LumRange > 2; and

3 MaxColourVariance＜BILEVEL_COLOUR_VARIANCE

MaxColourVariance is defined as max(ColourVariance[band]), where ColourVariance[band] is the sum of the pixel count-weighted Manhattan distances between the largest bin within a band and the remaining bins. The parameter values may be BILEVEL_MAX_BIN_CNT=16, and BILEVEL_COLOUR_VARIANCE=40.

2.2.1.3 Form the second palette

FIG. 41 shows the processing of step 1130 of FIG. 11 in more detail. Step 4110 tests whether the patch is flat. If the tile is, then step 4120 forms a flat color. This can be achieved by computing the weighted average of the non-empty bins. If the test result in step 4110 is negative, processing continues at step 4130, where it is tested whether the patch is classified as being two-level. If the test result is yes, processing moves to step 4140. At step 4010, a palette of two colors is generated. Otherwise, if step 4130 returns false, processing continues at step 4150. In step 4150, a multi-color palette is generated.

2.2.1.3.1 Generate a two-color palette

FIG. 42 provides further details of the two-color palette generated in step 4140 for the two-level tile. The purpose is to create contrasting colors to represent the image. Due to half-toning and registration errors in printing, the colors representing the original two contrasting colors are typically smeared. As a result, the average color of the foreground and background regions is not a good representation of the original image. Excluding colors in the transition area makes the image look sharper.

In step 4210, the darkest and lightest colors are selected to form an initial palette of dominant colors. In step 4220, a library list is generated using the 6 most populated libraries. Find the top 6 banks from this palette based on pixel count. Steps 4230 through 4270 process the colors in the list sequentially. In step 4230, the next library color C is obtained from the list. Decision step 4240 tests whether color C is already included in the initial palette, or whether the color is too far from the two extremes. If yes, the color is ignored and processing returns to step 4230 to fetch the next library color for processing. If the result of step 4240 is no, processing continues at step 4250. Decision step 4250 tests whether the color is suitable for merging into the initial palette. A color suitable for merging is one that lies near any color of the original palette. If the test result of step 4250 is yes, the color is merged into one of the initial palette colors based on the closer Manhattan color distance to the weighted pixel count. Increment the pixel count of C to the pixel count of the palette color to merge into. Processing continues at step 4270. If the result of step 4250 is no, the color is ignored, and the process proceeds to step 4270 to check if there are any unprocessed colors. If the test of step 4270 returns yes, processing returns to step 4230. Otherwise, processing terminates.

2.2.1.3.2 Generating a multi-color palette

Figure 43 expands on step 4150 of Figure 41, which generates a multi-color palette for a multi-color tile. In step 4310, the darkest and lightest colors are selected to form an initial color palette as initial dominant colors. In step 4320, a third color is added to the palette if the following two conditions are true:

1 LumRange > THIRD_COLOUR_MIN_LD; and

2 LargestVar > THIRD_COLOUR_MIN_VAR

LargestVar is defined as the maximum Manhattan color distance from the mean color of the brightest and darkest colors in the library between the darkest and brightest luminance bands. If the above test is true, add the color resulting in LargestVar as the third initial palette color. The thresholds may be THIRD_COLOUR_MIN_LD=4 and THIRD_COLOUR_MIN_VAR=40.

In step 4330, the top (ie, most populated) 6 bins are added to a bin list. Steps 4340 through 4395 sequentially process the colors of the list. In step 4340, the next library color C is obtained from the list. Step 4350 tests whether the color is already contained in the initial palette. If yes, the color is ignored and processing returns to step 4340. Otherwise, step 4360 attempts to merge the color into one of the palette colors. Merge the color into the palette with the closest Manhattan color distance if that distance is within BIN_MERGE_THRESHOLD1 (where the threshold may be BIN_MERGE_THRESHOLD1=10). If the attempt at step 4360 was successful, processing continues at step 4395 to check if there are more colors to process. Otherwise, the process proceeds to step 4370.

Step 4370 tests whether another color can be added to the palette. If step 4370 returns true (Yes), processing continues at step 4380. Additional colors are added in step 4380 if the test in the pseudo-code below is true.

Number_palette_colours＜MAX_NUM_PALETTE_COLOURS

&&

(

  minDist > BIN_MERGE_THRESHOLD2

" "

(

  minDist > BIN_MERGE_THRESHOLD3

&&

  (minDist*pCnt)＞BIN_NEW_MIN

&&

      pixel_count_closest_palette_colour > BFN_DONT_TOUCH_CNT

)

)

MinDist is the nearest Manhattan color distance from C to the palette color. PCnt is the pixel count of C. Pixel_count_closest_palette_colour is the pixel count of the palette color that yields minDist. The thresholds may be MAX_NUM_PALETTE_COLOURS=4, BIN_MERGE_THRESHOLD2=70, BIN_MERGE_THRESHOLD3=40, BIN_NEW_MIN=4000 and BIN_DONT_TOUCH_CNT=150.

From step 4380, processing continues at step 4395.

If the test in step 4370 is false, processing continues at step 4390. In step 4390, the library color C is merged with the palette color with the closest Manhattan color distance. Colors are merged at a weighted pixel count, and the pixel count of C is increased to the pixel count of the palette color to be merged into. Processing continues at step 4395. If there are no more colors to process at step 4395, processing terminates.

2.2.1.4 Associating pixels with a second palette

Once the dominant color is found, the pixels within the tile are quantized to one of the dominant colors. Produces quantization maps together with primary color lists for connected components analysis. The quantization process for each group is as follows:

1) flat - not quantized;

2) two-level - remap the palette to one of the two primary colors, or find a threshold to binarize the original pixels; and

3) Multicolored - Remaps the palette to one of the main colors.

Binarization produces sharper contours, but takes longer since binarization needs to find an appropriate threshold. The steps to find the threshold are: 1) perform a first derivative on the luminance channel, 2) identify edge pixels, and 3) use the average luminance value from the edge pixels as the threshold. Edge pixels are pixels where the 3x3 first derivative outputs around them are all above a predetermined threshold.

FIG. 44 provides further details of step 1140 of FIG. 11 . Step 4410 tests whether the tile is classified as two-level. If the test result is yes, processing continues at step 4420. In step 4430, multi-colored tiles are mapped. Otherwise, processing continues at step 4430. At step 4420 the two-level tiles are mapped.

2.2.1.4.1 Mapping two-level patches

FIG. 45 provides further details of step 4420. The overall process 4420 maps all non-empty bins to two colors within the second palette with quantization error checking. Steps 4510 through 4570 perform quantization and error checking on each non-empty bin. If no large quantization errors are found, the process remaps all pixels to the second palette after library quantization. If a large quantization error is found, the tile is reclassified as multi-color and subjected to multi-color tile mapping. The details of mapping the two-level tiles are explained below.

Step 4510 determines whether contour enhancement is required, and selects the preferred extreme colors for quantization for the bins undergoing contour enhancement. If the pixel count of one of the two palette colors exceeds the other by a factor of 4, contour enhancement is required. Let two colors in the second palette have a first color C1 and a pixel count P1 and a second color C2 and a pixel count P2. If (P1/P2) or (P2/P1) is greater than 5, outline enhancement is required and OUTLINE_ENHANCE is set to true. Preferred extreme colors may be those with smaller pixel counts.

Step 4515 gets the next non-empty bin with pixel count pCnt. Step 4520 calculates the quantization error for the two colors. Computes the Manhattan distance (D1 and D2) to two palette colors, and defines the smaller one as minDist. MinDist is the quantization error. Processing then continues at decision step 4525, where it is checked whether the quantization error is too large. The following pseudocode defines the conditions when the quantization error is too large:

(minDist*pCnt)＞BIN_NEW_BILEVEL_THRESHOLD

‖

(

minDist > BIN_NEW_BILEVEL_COLOUR_DIFF

&&

pCnt>BIN_MERGE_BILEVEL_CNT_MIN

)

Wherein the thresholds may be BIN_NEW_BILEVEL_THRESGOLD=6000, BIN_NEW_BILEVEL_COLOUR_DIFF=50 and BIN_MERGE_BILEVEL_CNT_MIN=100.

If the test at step 4525 is true, processing continues at step 4540. In step 4540, the current library is added to the list of additional primary colors. Processing then continues at step 4570. If the test in step 4525 is false, processing continues at decision step 4530, checking to see if the list of additional primary colors is empty. If the list is not empty (No), processing transitions to step 4570 to see if there are more non-empty libraries to process. Otherwise, if the result of step 4530 is yes, processing continues at step 4545, where it is determined whether contour enhancement is required, and whether the two distances are close. The test conditions are given in the following pseudocode:

OUTLINE_ENHANCE

&&

abs(D1-D2)<BILEVEL_THRESHOLD_MARGIN

The threshold may be BILEVEL_THRESHOLD_MARGIN=16.

If the test in step 4545 is true, processing continues at step 4550. In step 4550, the library is quantized into preferred colors. Processing continues at step 4570. Otherwise, processing continues at step 4555, quantizing the bins to closer colors based on D1 and D2. Processing then continues at step 4570, checking to see if there are more non-empty banks to process. If there are more non-empty banks, the process returns to step 4515. If there are no more non-empty banks, processing continues at step 4560, checking to see if the list of additional primary colors is empty. It determines whether there is a large quantization error during the library quantization process. If the list is empty, processing continues at step 4575 and all pixels are remapped to one of two palette colors according to the library mapping in step 4550 or 4555, as appropriate. Then, the processing is terminated. If the list is not empty at step 4560, processing continues at step 4565 with an additional color being added to the palette. The bank with the highest pixel count within the list of additional primary colors is selected as the tertiary palette color. In step 4430, the tiles are remapped as multi-color tiles. Processing then terminates.

2.2.1.4.2 Mapping multi-level tiles

Step 4430 of FIG. 44 is expanded on FIG. 46 . Step 4610 gets the next non-empty bank. Step 4620 quantizes the library to one of the palette colors. This can be done based on the nearest Manhattan color distance. Step 4630 checks if there are more non-empty libraries to process. If the test in step 4630 is true, processing continues at step 4610. If the test in step 4630 returns no, processing continues at step 4640. In step 4640, all pixels are remapped to one of the palette colors according to the library mapping in step 4620. Then, the processing is terminated.

2.2.2 Color CC Analysis and Blob Statistics

The present process 1020 of FIG. 10 takes quantized tiles from previous steps and forms blobs. Each blob has the following statistics: bounding box, size, mean color, bitmask, blob boundary length. Create spots in a single raster wheel in a fast and efficient manner. In raster order, adjacent pixels in quantized tiles belonging to the same color class are grouped so as to form "strings". At the end of each string (segment), the string is compared to the touching segment (in terms of 8-way connectivity) on the previous row for growing or merging. Growth occurs if the string to be given a blob label touches a blob of the same class. Instead, merging occurs when two blobs of the same class touch. If growth is not possible, new spots are formed. Update blob statistics at the end of each string.

FIG. 36 is an illustration of a color blob partitioning process 3600 using an example 6×6 input tile 3610 . Color quantization is applied to an input tile 3610 having several colors to produce a quantized tile 3620 . Quantization tile 3620 contains class labels corresponding to primary color classes. In this case there are two dominant colors in the patch, so class labels 0 and 1 are given. Connected components analysis starts by grouping adjacent labels of the same class together in a row to form strings. For example, in Figure 36, the first 4 "0"s of the first row form one string, and the next two "1"s form another string. Blobs are formed by joining together strings of the same class from consecutive rows in quantized tiles 3620 . Tile 3630 shows the strings within the tile. There are three possible behaviors when comparing the current segment with the contacted segment in the previous row:

1 grow the blob by adding the current segment to the existing blob;

2 Merge two blobs by unifying their statistics into one;

3 Form a new blob by initializing the blob with the current segment.

Tile 3640 shows the resulting blobs, blob 0 and blob 1 , where blob 0 has an outer bounding box and blob 1 has an inner bounding box. Accumulate blob statistics while forming strings and blobs. So, at the end of this processing stage, each blob has all the statistics shown in Figure 36 for blob 0 and blob 1 . Bit masks 3650 and 3660 are representative. Exemplary bit masks 3650 and 3660 are not actually formed at this stage. Use the quantized color as the mean color for the blobs. Alternatively, the mean color of a blob can be determined by accumulating actual pixel values in the blob rather than quantized colors. This gives a more accurate mean color. Again, blob statistics can include size, mean color, border length, bounding box, and bitmask.

FIG. 9 shows step 1020 of FIG. 10 in more detail. Step 1020 adopts a loop structure to form spots from quantized tiles, and processes one tile row at a time from top to bottom. In step 910, the current tile row is obtained for processing. In step 920, consecutive segments of pixels of the same quantization label are formed. This can be done by recording its start and end positions. This segment is the current segment S _c . The start position is the pixel to the right of the end position of the previous segment. In the case of a new tile row, the starting position is the first pixel of the row. The end position is the last pixel before the quantization label changes during a pixel-by-pixel inspection of the quantization label on the current tile row from left to right. In case the current tile row ends before a change is detected, the end position is the last pixel of the row. For the purpose of later re-estimating the color of a blob, the YUV value of each pixel within a segment within the original panchromatic tile is accumulated during inspection from its start to end position. Alternatively, the segment's quantized color can be used without color re-estimation.

In step 930, the segment is used to form new spots or grow existing spots. Figure 12 provides further details of this step. In decision step 940, a check is made to determine if there are unprocessed pixels remaining in the row. If decision step 940 returns true (Yes), processing returns to step 920 . This does not happen until all pixels within the current tile row have been processed. If step 940 returns false (No), processing continues at step 950 . In decision step 950, a check is made to determine if unprocessed rows remain. If step 950 returns true (Yes), processing continues at step 910 . This does not happen until there are no more pending patch rows. If step 950 returns false (No), processing terminates; each pixel within the quantized tile has been assigned a blob.

2.2.2.1 Formation of spots

Figure 12 shows step 930 in more detail. The process of FIG. 12 takes as input the current segment _Sc identified in step 920 of FIG. 9 . In step 1205, the variable k is initialized to 1. This value refers to the kth segment _Sk of the tile row above the current tile row connected to the current segment _Sc . Preferably, the connection is an 8-way connection. In step 1210, a comparison between S _k and S _c is performed. In decision step 1215, a check is made to determine if _Sc and _Sk are the same class. If the two segments S _k and _Sc have the same quantization label, processing moves from step 1215 to step 1220 . Otherwise, processing continues at decision block 1235 . In decision step 1220, a check is made to determine if _Sk is the first connected segment of the same class. Thus, if S _k is the first contiguous segment with the same quantization label as _Sc , processing continues at step 1225 . Otherwise, processing continues at step 1230 . In step 1225, the current blob is grown. Thus, the current segment is grown based on the blob to which the kth segment belongs. Growing a blob involves updating the blob's size, boundary information, bounding box, and accumulated YUV values. Processing then continues at step 1235. Conversely, if decision step 1220 returns false, this indicates that the current segment has been assigned a blob label, i.e. blob[i], and is in contact with another blob, blob[j], and processing continues at step 1230. If the two blobs have different blob labels, ie, i≠j, then at step 1230 the two blobs are merged together. The blob merging process in step 1230 is shown in FIG. 15 . Processing then continues at step 1235.

From steps 1215 , 1225 and 1230 , processing continues to decision block 1235 . In decision block 1235, a check is made to determine if the last connected segment has been processed. If the kth segment is not the last segment connected to the current segment, processing continues at step 1240 and k is incremented by one. Processing then returns to step 1210 to process the next contiguous segment. Otherwise, if decision step 1235 returns true, processing moves to decision block 1245 . In decision block 1245, a check is made to determine if no connected segments are of the same class (ie, same quantization label as the current segment). If step 1245 returns true (Yes), processing continues at step 1250 . In step 1250, a new blob is formed using the current segment. Forming a new blob involves assigning a new blob label to the current segment, incrementing the blob number by 1, and initializing blob statistics with information from the current segment. Processing terminates after step 1250. Similarly, if decision block 1245 returns false (No), processing terminates.

2.2.2.2 Example of blob merging

An example of blob merging 1500 is shown in FIG. 15 . Segments 1510 and 1520 both belong to spot[i], which is connected to segment 1530 which belongs to spot[j]. The current start and current end of segment 1520 are shown, as are the upper start and upper end of segment 1530 . Also shown in FIG. 15 is the overlap of segments 1520 and 1530 . The blob merging process 1500 involves combining the statistics of two blobs, mapping one blob label to the other, and reducing the number of blobs by one. For example, in Figure 15, label j is mapped to label i. Combine blob statistics using the following pseudocode instructions:

83 blob[i].boundingBox＝combine(blob[i].botmdingBox，blob[j].boundingBox)

83 blob[i].size+＝blob[j].size

83 blob[i].tileBorderPixelCount+＝blob[j].tileBorderPixelCount

overlap83 blob[i].horizontalEdges+=blob[j].horizontalEdges-2

overlap

83 blob[i].verticalEdges+＝blob[j].verticalEdges

83 blob[i].YUV+＝blob[j].YUV

2.2.3 Intra-patch merging

Once the patches of blobs have been formed by connected component analysis, the next stage is to merge semantically related blobs together using color, size, and blob boundary length statistics. From this stage, blobs can only be merged and not segmented. Thus, the tile goes from being over-segmented to being closer to the correct segmentation level. An example of intra-tile merging is shown in Figures 37 and 38, where blob statistics are used to evaluate whether to merge a given portion of blobs. In the example, there are 4 quantized colors, and the connected components analysis returns 10 blobs. Figure 37 shows the blob before merging 3710 on the left. Many of these spots are due to residual halftone patterns and the effects of color "bleeding" between areas of two different colors. After applying intra-tile merging, small blobs with relatively long boundary lengths are merged into larger blobs with smaller color features. The blob after merging 3720 is shown in example 3700 . FIG. 38 contains a comparison 3800 of the original tile 3810 with the merged blob 3820 .

Quantization and speckling processes often create many small unwanted or incorrect spots. They are in the form of small blobs caused by noise blobs within the input image, leftover halftones, or thin, high aspect ratio blobs caused by bleeding effects at the edges of larger connected components. Incorrect blobs can be removed by merging these blobs with blobs of a similar color touched by the incorrect blob.

Speed and memory usage can be improved by limiting the number of blobs within a tile resulting from segmentation and connected component processing. If there are too many blobs within a patch, the number can be reduced by merging similarly colored blobs, even if they are not touching. This produces blobs that have independent disconnected parts, but are treated as a single element. Since this only happens within tiles with a large number of small noise elements that are discarded in a later step, the quality is not affected.

FIG. 19 shows step 1030 of FIG. 10 in detail. In step 1905, blobs within the current tile are obtained. In step 1910, the perimeter to area ratio of the blob is checked to determine if it is tall. If the parameter is found to be above the threshold level, processing continues at step 1915 . Otherwise, if step 1910 returns false, processing continues at step 1930 . In step 1915, the ratio of pixels within the blob that touch the edge of the tile is checked. If the ratio is above the threshold, processing continues at step 1920 . In step 1920, the blob is marked as "forced to merge between tiles". A force-merge flag is set for this blob, which makes it more likely that the blob will be merged with connected components within adjacent tiles in step 1420 of FIG. 14 . After step 1920, processing continues at step 1930. If the patch edge ratio of the blob is below the threshold in step 1915 , processing continues at step 1925 . In step 1925, the blob is merged with neighboring blobs with the closest color. Find all blobs that touch the current blob and their color's distance from the current blob. The current blob is then merged with the adjacent blobs with the closest color. Processing then continues at step 1930 . In decision step 1930, a check is made to determine if there are more blobs in the tile to process. If step 1930 returns true (Yes), the process returns to step 1905 . Otherwise, processing continues at step 1935.

In decision step 1935, the current number of blobs within the tile is checked to determine if there are too many. If the number of blobs is found to be above the predetermined limit, processing continues at step 1940 . Otherwise, processing ends. In step 1940, blobs of the same quantized color class that do not touch the edge of the tile are merged together. This process is done for each quantized color class. Spots that touch the edge of the patch are not merged, as these can form part of a much larger CC, and merging them may have detrimental effects on quality. In step 1945, the current number of blobs within the tile is checked again to determine if there are still too many blobs within the tile. If the number is now found to be below the predetermined limit (No), the process is terminated. Otherwise, processing continues at step 1950 . In step 1950, the blobs of each color that touch the edge of the tile are merged. Step 1950 performs a process similar to step 1940, but takes into account blobs that touch the edge of the tile in order to reduce the number of blobs below the limit. Then, the processing is terminated.

2.2.4 Merging between patches

FIG. 13 shows the inter-tile merging process of step 1040 in detail. This process is repeated for each of the current tile's left and top borders, in no particular order. The following descriptions are suitable for merging along the left or top border of the current tile. For example, a 32×32 tile has a 32-pixel boundary with its neighboring tile states, and each pixel has a blob label. Adjacent tile states also have a 32-pixel boundary, and each pixel has a CC label. So, for each pixel step along the border, there is a blob label within the current tile, and a corresponding CC label within the neighboring tile state. Processing begins in step 1310 along a common boundary by obtaining the blob label in the current tile and the CC label in its neighboring tile state for the next tile boundary pixel.

A test is performed in decision block 1320 to detect changes in the CC label, blob label, or last pixel as processing moves along the boundary. If the current pixel is the last boundary pixel, decision block 1320 returns yes. If step 1320 returns false (No), processing continues at step 1380 . Otherwise, if step 1320 returns true (Yes), processing continues at step 1330 . Step 1330 checks the number of blobs and the number of CCs that can be used as merge candidates. In decision step 1340, a check is made to determine if the candidate count condition is met. Decision block 1340 returns yes if the merge candidate counts of the blob and CC satisfy the predetermined condition 1700 as shown in FIG. 17 and described below.

If decision step 1340 of FIG. 13 returns false (No), processing continues at step 1370 . Otherwise, processing continues at step 1350 . Step 1350 identifies the best blob and CC pair for merging among the merging candidates based on the color distance metric. Let (Y _cc , U _cc , V _cc ) and (Y _blob , U _blob , V _blob ) be the YUV color values of CC and blob candidate pairs, the color squared distance sd is given by:

sd=W _y (Y _cc -Y _blob ) ² +W _u (U _cc -U _blob ) ² +W _v (V _cc -V _blob ) ² ,

where W _y , W _y , W _y are the weights of the Y, U and V channels, respectively. The weights W _y , W _y , W _y can be set to 0.6, 0.2 and 0.2, respectively. The best blob and CC pair is the one with the smallest squared distance value.

This best blob and CC pair is processed by step 1360, which performs various merge operations and is described in more detail with reference to FIG. After step 1360, or no from decision block 1340, processing continues at step 1370, where the blob and CC candidate counts are updated. Figure 48 shows CC and blob candidate counts before and after updating for all operating conditions. If both CC and blob labels are found to have changed, CC and blob candidate counts are set to 1 for all possible combinations of counts before merging ("x" before update means "don't matter"). If only one label is found to have changed, and there are two candidates on either side of the tile boundary, the count can be set to 0 or 1 depending on which of the two candidates was merged. If the second blob is selected for merging (see 4920 in Figure 49), then both candidate counts are set to 0 after merging has occurred. However, if the first blob is selected or no blob is selected for merging, both counts are set to 1. In the remaining cases where a candidate count update is required, the count of labels that have changed is incremented by 1, while the count of labels that have not changed is set to 1.

After step 1320 or 1370, processing continues at step 1380. In decision block 1380, a check is made to determine if the current pixel is the last boundary pixel. If step 1380 returns false (No), processing moves to the next pixel location in step 1310 . Otherwise, processing terminates.

2.2.4.1 Merging conditions between patches

According to Figure 17, except when both the CC and the blob label change at the same time (in which case one candidate on each side is sufficient for merging), when there are two candidates on one side, and on Merging usually occurs when there is one on the other side. This avoids merging two adjacent candidates on one side into the same candidate on the other side. FIG. 17 shows conditions under which an inter-tile merge operation can be performed. If the current CC and blob count are (1, 1), then both labels must change at the same time for the merge to occur. However, if the current CC and blob count are (1,2) or (2,1), any label change is sufficient for merging to occur. Case (2, 2) never arises.

2.2.4.2 Example of merging between tiles

Figure 49 provides an example of merging between blobs and CC candidates. There are 3 cases: i) in 4910, there is only one candidate per side; ii) 4920 has one CC and two spots, and iii) 4930 has two CCs and one spot. In case 4920, the CC candidate is concatenated with two blob candidates. Suppose two spots are close in color to CC, but only one can be merged with CC. If merging is performed one candidate per side from top to bottom at a time, the top blobs are merged with the CC, leaving the bottom blobs unmerged. This may not yield the most desirable results when the bottom blob might be a better candidate for merging. Thus, for cases like in 4920 and 4930, two candidates are required on one side. Case 4910 requires only one candidate on each side, since for 4-connectivity there is no alternative merge combination.

Color-connected components spanning more than one tile are formed by inter-tile merging blobs in tile raster order. As shown in example 3900 of FIG. 39, this is performed in raster order, where blobs within tile 3910 are merged with blobs within either of two adjacent tiles 3930 and 3920 to the left and above tile 3910, respectively. .

Each CC is stored within a data structure that holds information about its bounding box, mean color, size in pixels, and CCs it touches. In the inter-tile merging process, a CC label is assigned to each blob within the current tile, and the corresponding CC data structure is updated with blob statistics. Merging is performed between the current tile 1630 and the states 1612, 1622 within the two adjacent tiles 1610, 1620 along the left and upper boundaries of the current tile 1630 as shown in FIG. 16 . The current tile 1630 is a block of pixel data that has been processed to form blobs, and has blob labels 1634 for pixels along a common boundary. In contrast, previous tile states 1612, 1614 contain no pixel data, only blob statistics and connected component information linked to those blobs. A tile state 1612, 1622 is a compressed data structure that contains information about the blobs along the boundaries in that tile 1610, 1620, and pointers to the CCs 1614, 1624 to which those blobs belong. Specifically, there are two tile states: the left tile state 1612 and the top tile state 1622; each has a common border along them with the current tile 1630 for merging with the tiles to their right and below, respectively CC tag information 1614, 1624 for each pixel of . The blobs in the previous patch are now part of the connected component.

2.2.4.3 Dealing with Optimal Spots and CC Pairs

FIG. 14 shows step 1360 of FIG. 13 in more detail, taking as input the best blob and CC pair identified at step 1350 . Processing begins in step 1410 . In decision step 1410, a check is made to determine if the blob has already been merged with another CC. If the blob identified in decision block 1410 has been assigned a CC label, processing continues at step 1440 . Otherwise, processing moves to decision block 1420 . In decision block 1420, the color distances between the identified blobs and CC pairs calculated in step 1330 are compared to a color binning threshold. The threshold may be 450. The threshold can be 900 if the force merge flag is set. If the color distance is less than the threshold, processing continues at step 1430 . Otherwise, processing continues at step 1460 . In step 1430, the blob is merged with the identified CC. This can be done by updating the CC's statistics with the blob's statistics, and assigning the CC's labels to the blobs. Processing then terminates. In step 1460, a new CC is formed for the current blob. Processing then terminates.

In decision block 1440, the color distance between the identified CC and the CC to which the identified blob belongs is compared to a color threshold for merging. If the color distance between the two CCs is below the threshold, processing continues at step 1450 . In step 1450, the CCs are mapped together. This can be done by combining their statistics together, and setting a "map to" pointer that links the CCs together. Processing then terminates. Similarly, if step 1440 returns false (No), processing terminates.

2.2.4.4 CC mapping results

FIG. 18 is an illustration of the results of the CC mapping process according to step 1450 of FIG. 14 . The figure shows that as a result of merging CCs 1805, 1810, 1820, 1830, a linked list 1850 of CCs may be formed. In this illustration, CC(k) 1830 has a mapped-to pointer 1832 to NULL 1840, which indicates that it has never been merged into another CC, so it is called the root CC. Additionally, statistics for the root CC are determined 1834 by accumulating individual CC statistics over several merges. For example, the final statistic of CC 1830 is the combined statistic of CC(h) 1805, CC(i) 1810, CC(j) 1820, and CC(k) 1830 before being merged together. The order in which these statistics are combined is not important. In FIG. 18 , CC(i) 1810 points to CC(j) 1820 , and CC(h) 1805 and CC(j) 1820 point to CC(k) 1830 .

2.2.5 Post-merge processing

FIG. 50 is a flowchart of the post-merge processing step 1050 of FIG. 10 . At step 5010, a new CC is formed for each unmerged blob in the current tile in the same process as step 1460 of FIG. 14 . In step 5020, a binary image storing the shape and appearance of the blob is output using the blob label. For a patch with n blobs, only n-1 binary images need to be output, since the n-th binary image is implicitly stored as the remaining region after removing n-1 regions. Therefore, a flat patch containing a single blob does not need to store any binary images. In an alternative embodiment, the binary image may be stored within a single compressed data structure such as an index map, where each pixel location has a blob index and is represented using log2(n) bits. For example, if the maximum number of blobs per tile is 16, use a 4-bit number to encode the blob index at each pixel location. In another alternative embodiment, a 1-bit bitmap can be used to store binary images for two-level tiles. In step 5030, the contact list for each CC within the current tile is updated. This can be done by identifying all adjacent CCs within the tile. In step 5040, the tile status is output. The color segmentation process stores blob and CC information within a compressed tile state data structure for merging with the next input tile. As mentioned above, there are two tile states, where the left tile state has CC label information along the right tile boundary, and the upper tile state has CC label information along the bottom tile boundary.

2.3 Segmentation example

Figure 25(a) shows a simple example showing the advantages of segmentation based on more than 2 quantization levels. The background 2510 is black and on it is placed a white triangle 2520 and the letters 2530 of the word "text" in gray. Binary segmentation of the image typically results in merging of text 2530 with background 2510 or triangles 2520 as shown in Figures 25(b) and (c). Neither of these segments can be used for document layout analysis for selecting text regions - the text features are lost.

At the same time, there are certain features of binary segmentation that allow simplifying the layout analysis of connected components. Consider the case of pages with connected outer boundaries and CCs formed by 4-way connectivity. In this case, except at the edge of the page, every CC that touches another CC at the boundary is either contained by that CC or contains that CC, and a CC can only be contained by one other CC. An explicit containment hierarchy can be generated and represented in a tree structure. Each successive level in the tree contains CCs of the opposite polarity to the preceding, and each branch consists of a set of CCs that share a unique parent. This hierarchy can be used to group CCs since it can be used to select a subset of CCs (those that share a single parent) that are candidates to be grouped together. This is beneficial in terms of processing speed and also in terms of accuracy since a small number of CCs need to be considered at a time. CCs from different regions of the page can be on different branches of the tree and are not grouped together. Additionally, the processing of CCs can be started at the top of the tree, and tree branches can be terminated for CCs below a certain category (eg, text) to further improve processing time.

If the segments are not binary, a clear hierarchical structure cannot generally be helpfully generated. Consider the letter "e" in Figure 25(a). The outer border of the letter touches both the black background and the white triangle, so either the background or the triangle can be considered the parent of the CC. The case of a triangle is even more complicated, since its outer border touches the background and all letters. Despite this uncertainty, the benefits of using a hierarchy when grouping objects can be realized. This is done by defining the parent-child relationship properties between two CCs that touch at the boundary, without requiring a unique parent for each child. For example, a parent-child relationship can be defined between two CCs if these CCs touch at the border and the bounding box of one CC (parent) completely surrounds the bounding box of the second (child). Using this definition for the example shown in Figure 25(a), the triangle and all letters of the word "text" are defined as children of the background CC.

3 layout analysis

Layout analysis is part of this system, in which the foreground content of a page is identified. The middle (layout analysis) module takes as input a list of connected components and a "contact list" from the front-end module. The output of layout analysis is basically a decision about which connected components in the scanned image represent foreground content (ie, text, tables, bullet points). Layout analysis is based on color segments rather than binary images. This has several benefits in terms of classification of foreground objects that may be found, but there is no clear containment hierarchy like that exists for binary images. For efficiency, layout analysis uses only bounding boxes and a few other general connected component statistics as the basis for its grouping. Layout analysis does not access raw pixel data or even bit-level segmentation.

The main steps of layout analysis are: forming containment hierarchies based on contact lists, grouping CCs based on their bounding boxes and colors, and testing these groups to determine whether CCs are well aligned like lines of text. Hierarchies are provided for CC using contact lists, which are the multi-color equivalent of a two-level containment hierarchy. A given CC can be thought of as the parent of a subset of its contact list elements. Specifically, a given CC may be the parent of those CCs that are touched by the given CC and whose bounding boxes are completely contained within the parent CC's bounding box.

FIG. 4 shows step 120 of FIG. 1 in detail, which takes as input compressed CC information, statistics, and "contact list" information produced by step 110. FIG. The contact list describes which CCs are adjacent to each other - that is, which CCs share a boundary. The process of Figure 4 does not access the input image. Part of this information is a list of all CCs in the input image.

In step 410, the CCs are sorted based on their statistics, thereby forming a color inclusion hierarchy from the list of CCs. A color containment hierarchy is a structure in which each node is a CC. A parent node has as its children CCs that are touched by the parent node and whose bounding boxes are completely contained within the parent CC's bounding box. A child node can have more than one parent node. Analysis can be based only on bounding box size and shape. CCs with width and height less than 1/100 inch (eg, 3 pixels of 300dpi resolution) are considered noise and are removed. Connected components with a width or height greater than 1 inch, or both width and height greater than 8/15 inch are classified as images. Anything else is classified as potential text. Alternative embodiments may include classifications involving other document layout features (such as tables, number of pixels in connected components), and other values may be used.

In step 420, latent text CCs are grouped together, representing text regions. CCs are usually grouped together with nearby CCs, and efficient grouping algorithms exploit this fact by finding neighboring CCs before determining the grouping. The high-resolution color segmentation method used in the front end can find the thousands of siblings considered when grouping on a typical scanned document. In these cases, finding neighboring CCs using a simple pairwise comparison, an O(N2) method, may be slow, and more complex methods of determining neighbors must be used. Triangulation can be performed on nodes whose colors contain a hierarchy. If the center of the bounding box of the CC on the page defines the node on the plane, efficient triangulation methods can be used for this purpose, such as Delaunay triangulation. These methods are usually O(NlogN) processing.

Figure 53 shows an example 5300 of a Delaunay triangulation (indicated by dashed lines) and a Voronoi diagram (indicated by solid lines) of a set of nodes in a plane. A Voronoi diagram is a segmentation of pages into regions that are closer to a given point than to other points. A Delaunay triangulation is a dual Voronoi diagram that can be produced by connecting together points that share a boundary in the Voronoi diagram. In this triangulation, a typical point in the plane has about 5 points connected to it among randomly placed points in the plane. These points can be considered as good neighbor candidates in the grouping phase.

The output of triangulation makes it suitable as a method of forming CC groupings. These CCs are grouped together based on a pairwise comparison of the bounding boxes of those CCs that are adjacent within the Delaunay triangulation. Subsequent rounds are then performed on adjacent CC pairs after this initial grouping in order to join the groups together, or to place ungrouped CCs within existing groups. Processing can also look for different types of groupings (text, table, etc.) through the data in a single round. Groups of text CCs generally have the following characteristics: similar colors; similar sizes of bounding boxes; roughly aligned along the horizontal or vertical axis (depending on text alignment); and close together along the alignment axis relative to the size of the CCs.

In step 430, the CC groups are checked or verified to determine which CC groups are text characters. Information about group content and merges produced during the grouping phase is stored by the processor. Information about each individual group can be stored in a data structure that includes the color, bounding box, and content of the group. These structures are updated during the grouping phase when the content of the group changes. In an alternative embodiment, group markers are included within the CC data structure, and data such as group colors and bounding boxes can be reconstructed from the CC data. In step 430, an alignment test is performed on the text character CC as an additional check to ensure that CC is text.

The formed group typically includes the entire text, but may also include parts of the image that are not desired to be classified as text. To mitigate this problem, the groups are examined to see whether the connected components in the group are arranged in neat rows (or columns) like text, or randomly like noise or similarly colored regions of images tend to exhibit.

This can primarily be done by forming 4 histograms of the sides of the bounding box, one for each side (ie left, top, right or bottom). One of them should be full, the baseline of the text is there, and the other is empty. To check this, the sum of squares of these histogram bins can be found and compared to the expected value. If any of the 4 histogram bins were found to be much higher than expected from a randomly placed bounding box, the group was considered to be text. Uses all 4 sides of the bounding box, allowing pages to be scanned sideways or top-to-bottom, or text arranged in columns rather than rows.

3.1 Grouping CCs

FIG. 20 shows step 420 of FIG. 4 in detail, grouping the set of CCs segmented by step 110 . Processing begins at step 2010 by obtaining a root CC. A root CC is one that is not merged into other CCs during the color segmentation stage. In step 2020, the child CCs of the root CC are found. A list of child CCs of the root CC is formed. A child can be defined as a CC whose bounding box is completely contained within the bounding box of the current root CC, and touches that bounding box at the border. Step 2020 is described in more detail with reference to FIG. 22 .

From step 2020, processing moves to step 2030. In step 2030, neighbor analysis is performed on the children of the current CC. For each child, find a set of adjacent CCs that are close on some defined path. This can be achieved by, for example, Delaunay triangulation to find the center of the bounding box of each child CC. The edges in the triangulation represent the connectivity between adjacent CCs. Alternative methods can define approximations using bounding box data and different elements of the color information of the CC list. In step 2040, initial grouping is performed using the neighbor data. This processing step 2040 forms groups of objects of similar attributes (eg, geometry and color) within the same child list in order to characterize the layout of the document. Figure 23 describes step 2040 in more detail.

In decision step 2050, a check is made to determine if there are more root CCs remaining to process. If there are more root CCs, processing returns to step 2010, and the next root CC is obtained, and processing follows. Otherwise, the grouping phase (420) terminates.

3.1.1 Finding the child of the father CC

Figure 22 shows the step 2020 of finding child CCs and forming a list of children for a given parent CC. In step 2210, the contact CC is obtained from the contact CC list of the parent CC. In step 2220, the root CC is found. This can be done using any merge information from the color segmentation stage associated with this contact CC. In decision step 2230, the CC classification from step 410 of FIG. 4 is checked to determine whether the CC satisfies the class test (ie, whether it is appropriate to store the CC in a child list). All CCs except the noise size CC may be stored, but alternative embodiments may store other combinations of classes, eg only latent text. If the Class of Contact CC is suitable, processing continues at step 2240 . Otherwise, processing continues at step 2260. In decision step 2240, the CC is checked for inclusion with the parent CC. The containment test involves checking that the CC's bounding box is completely covered by the parent CC's bounding box, but alternative approaches are also possible. If the inclusion test is met, processing continues at step 2260. The CC may be included in the children list in step 2250 and processing continues to step 2260. Any CC should only appear once in the child list, so step 2250 includes checking that the CC is not included in the list. These checks can be done using a hash table. Processing then continues at decision step 2260 . Step 2260 tests whether there are any more elements in the father's contact list. If yes, processing continues at step 2210. Otherwise, the current CC's child list is complete, and processing terminates.

3.1.2 Initial grouping

FIG. 23 shows step 2040 of FIG. 20 performing initial grouping using neighbor data from step 2030 of FIG. 20 . The method may be designed to group text only, but in alternative embodiments the method may also classify or group other document objects such as tables. The initial grouping may be a two-round process, where the first round combines CCs into groups, and the second round combines groups together into larger groups. In step 2305, the counter PASS is set to 1. In step 2310, children are obtained. In step 2320, the child's neighbors are obtained. In step 2330, a check is made to determine if the child and neighbor satisfy the grouping test. These objects are tested in groups using a series of tests. Tests can be based on initial classification, geometry, and color, and can be different in the first and second rounds. Figure 26, described below, provides an extraction of a region of the document in which the grouping test of step 2320 is explained.

Referring to Figure 23, if the grouping test is met, at step 2340 the child and neighbor CCs are grouped together. Processing then continues at step 2350. Otherwise, if step 2330 returns false, processing continues at step 2350. If two CCs are grouped together, mark each as belonging to the same group. The group in which CCs are marked depends on the previous grouping of these two CCs. If neither is grouped yet, a new group is formed containing both CCs. If only one of the two has been grouped, the other CC is included in the group. If two are already grouped, and the groups are the same, no action is taken. Finally, if two are already grouped, and the groups are different, merge the two groups into a single group, and mark the other group as empty.

At step 2350, a check is made to determine if there are more neighbors of the current CC. If there are more neighbors, processing continues at step 2320. Otherwise, processing continues at step 2360. In step 2360, the process checks the parent CC for more children. If there are more children, processing continues at step 2310. Otherwise, processing continues at step 2370. In step 2370, a test is made to determine if two rounds have been completed (PASS > 1?). If this is the case, processing terminates. If only the first round has been completed, processing continues at step 2380 and the counter PASS is incremented. Processing continues at step 2390. In step 2390, processing returns to the beginning of the child list. Processing then returns to step 2310, and the second round begins.

In an alternative embodiment, the process 2040 loops through the edges of the triangulation data rather than child CC and neighbor pairs. This is slightly more efficient since each neighbor pair is only considered once.

3.1.2.1 Group testing of two CCs

To illustrate a preferred grouping test for two adjacent CCs, Figure 26 shows a simple extraction from a region of the document containing exactly two objects - the letters "g" and "h". Dashed lines indicate the coordinates of the bounding box of each letter. The left and right x coordinates and the upper and lower y coordinates of the i-th CC are located at x _i ¹ , x _i ^r , y _i ^t , and y _i ^b , respectively. Subscripts 1 and 2 indicate the first and second CCs (ie, the letters "g" and "h"), respectively. The processing of this embodiment also uses the color [y _i , u _i , V _i ] of each CC in the YUV space and the width w _i and height h _i of the bounding box.

Define the horizontal overlap distance of two CCs as the length of the horizontal portion covered by the two CCs, or 0 if the CCs do not overlap. The vertical overlap distance dy _ov is similarly defined and shown in FIG. 26 . The horizontal overlap is 0 in FIG. 26 and is thus not labeled. The overlap distance can be expressed as follows:

${\mathrm{dx}}_{\mathrm{ov}}=\max (0,\min (x_1^r,x_2^r)-\max (x_1^l,x_2^l)),$ (1)

${\mathrm{<span\; class="notranslate">\; dy</span>}}_{\mathrm{<span\; class="notranslate">\; ov</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span>$

The horizontal internal distance of two CCs is defined as the shortest distance between the left side of one CC and the right side of the other, or 0 if the horizontal overlap distance is not 0. Define the vertical interior distance in the same way using the top and bottom sides of the CC. The horizontal distance dx _in is shown in Figure 26, while for this example the vertical inner distance is 0 and is not represented. These internal distances can be expressed as follows:

${\mathrm{dx}}_{\mathrm{in}}=\max (x_2^l-x_1^r,x_1^l-x_2^r,0)$ (2)

${\mathrm{<span\; class="notranslate">\; dy</span>}}_{\mathrm{<span\; class="notranslate">\; in</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span>$

In the first round, if two adjacent CCs meet the requirements of 3 conditions based on color, size and alignment, these CCs are grouped together as text. if:

$\sqrt{{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

Then the color condition is satisfied, wherein the threshold parameter may be Tc=500.

if:

$\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}<span\; class="notranslate">\; ,</span>\frac{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}}{{\mathrm{<span\; class="notranslate">\; h</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ></span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

Then the size test is satisfied, where w _min is the minimum width of the two CCs, w _max is the maximum width, h _min is the minimum height, and h _max is the maximum height. The threshold parameter may be T _R =0.55.

An alignment condition is met if any of the following conditions are met:

[(dx _ov >0) and (dy _in /max(w _min , h _min )<T _s )],

or

[(dy _ov >0) and (dx _in /max(w _min , h _min )<T _s )], (5)

The threshold parameter may be T _s =0.65.

The second round uses parameters based on groups rather than individual CCs. The mean color [Y _i , U _i , V _i ], width W _i and height _Hi of each group of elements may be used. For the case of ungrouped CCs, set these values as the individual CC's color, width and height parameters. The test also uses the distance D between the centers of the CCs under consideration, which is defined as follows:

$\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; =</span>\sqrt{{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; l</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; r</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; b</span>}}}{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$

As for the first round, groups are merged if a series of conditions are met. These conditions relate to color similarity T _c , size T _R and spacing T _o , and are described by:

$\sqrt{{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; Y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; C\; g</span>}}<span\; class="notranslate">\; ,</span>$

max(W _min /W _max , H _min /H _max )>T _R ,

  (7)

min(W _min /W _max , H _min /H _max )>T _R2 ,

D/max(W _min , H _min )<T _D ,

where the parameter values may be: T _Cg =500, T _R =0.55, T _R2 =0.3, and T _D =1 if any group contains 3 or less elements, and T _Cg =100, T _R =0.55 otherwise , T _R2 =0.3, and T _D =2. Alignment testing is not used in the second grouping stage.

The threshold may depend on the characteristics of the CCs being group tested, for example, the pixel count per CC.

3.2 Inspection Team

FIG. 21 shows in detail step 430 of FIG. 4 for checking groups. This process determines whether each group consists of text. This decision is made primarily based on whether the objects within the group are found to be aligned on rows or columns. Assuming the group is text, it is tested for text-like properties, and if the group fails those tests, it is rejected.

In step 2110, the next group formed in step 420 is obtained. In step 2120, the size of the text characters within the group is estimated. The estimated size is based on statistics of the length of individual characters. These lengths can be defined as the maximum of the width and height of the object's bounding box. This measurement is fairly insensitive to slant and alignment of text on the page, and uniform enough for character sets within a typical font at a given size. In alternative embodiments, bounding box area, pixel count, and/or stroke width may be used as measures of length. A histogram of character lengths may be formed, and the estimated size may be based on the maximum length associated with a histogram bin having more than a threshold number of elements in the bin. The threshold used was a minimum of 3 subjects and at least 15% of the number of subjects in the group. If no such library exists, no estimate is returned.

In decision step 2125, a check is made to determine if the size of the character was found. If a suitable character size cannot be found, the group is rejected and processing continues at step 2160. Otherwise, processing continues at step 2130.

Step 2130 processes the CCs within the group and other CCs contained within the group's bounding box that are suitable but are not yet assigned to any group. This process 2130 is beneficial for augmenting text that might have been missed by the initial grouping, as well as small objects such as punctuation that might have been omitted from the initial grouping based on classification. Only objects that share a parent with objects in the group and are sufficiently similar in color can be added to the group. The color similarity condition for a group and contained CCs is met if the following conditions are met:

$\sqrt{{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>{<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; <</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; C\; g</span>}\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

where [Y, U, V] is the color of the group and [y, u, v] is the color of the CC. The parameter value may be T _Cg2 =500.

Alternatively, a geometric test may be applied in step 2130, and the requirement that the CC's bounding box is completely contained within the group's bounding box may be relaxed, thereby incorporating objects close to the group into the group. Other alternatives to step 2130 may combine certain objects to form characters. This is aimed at scripts with complex characters, such as Chinese, which may be segmented into more than one single object, and is useful for improving the accuracy of alignment tests in later processing. Two objects can be merged only if their bounding boxes overlap. If the merging would create an aspect ratio greater than 1.6, or create a merging object larger than the character size estimated in step 2120, then restrict merging from occurring.

In step 2150, the alignment of the objects within the group is checked. This test distinguishes groups of text from other groups and is described in more detail below. After this step, a test is performed at step 2160 to determine if there are more groups to process. If there are more groups, processing returns to step 2110. Otherwise, process 430 ends.

3.2.1 Check alignment

FIG. 24 shows step 2150 of FIG. 21 in more detail. During this step, a subset of CCs within a group is defined as characters. Characters may be those objects having a size greater than half the size of the character estimated in 2120, and less than twice that size.

Steps 2430 to 2450 conduct an acceptance test of the group based on a histogram analysis of a series of parameters for the group elements. These parameters are the left, top, bottom and right of each character's bounding box. Using multiple parameters allows different alignments of text to be recognized, since the alignment of text on a page depends on many factors, such as language and the inclination of the text on the page. Alternatively, a wider range of text alignments can be identified using various combinations of horizontal and vertical bounding box parameters.

In step 2430, a histogram is formed for the group element values of the next parameter. The size of the bins within the histogram can be scaled according to the size of the group characters. You can use a value of 1/5 of the average height of the characters in the group (rounded) for the top and bottom bounding box sides, and you can use 1/5 of the average width of the characters in the group (also rounded) for the left and right bounding box sides ). Sets the bin range within the histogram such that all data is included in non-empty bins at each end of the range. The lowest value of the histogram coverage can be set to the lowest value of the parameter within the group.

Decision step 2440 tests whether the values within the histogram are well aligned, forming discrete clusters (ideally representing baselines of different lines of text), rather than randomly spreading out. Step 2440 tests whether the number N of characters in the group is greater than a threshold T with a preferred value T=7.

For small groups (N<T), step 2440 checks 3 parameters AL1, AL2 and OV. AL1 is the count of the largest bin within the histogram. AL2 is the count of the second largest library within the histogram. OV is the size of the largest subset of overlapping characters within a group. The pseudocode in Table 2 describes the tests used for this set. If the pseudocode returns Y, the group passes the alignment test, and if the pseudocode returns N, the test fails.

Table 2

                 

IF(N<3)

return N

ELSE IF(N＝3)

IF(AL1＞＝2 and OV＞＝3)

return Y

END

ELSE IF(N＝4)

IF(AL1＞＝2 and OV＞＝4 and AL2＞＝2)

return Y

ELSE IF(AL1＞＝3 and OV＞＝4)

return Y

END

ELSE IF(N＝5)

IF(AL1＞＝4 and OV＞＝5)

return Y

END

ELSE IF (N=6)

IF(AL1＞＝2 and OV＞＝6 and AL2＞＝2)

return Y

ELSE IF (AL1＞＝4 and OV＞＝6)

return Y

ELSE IF(AL1＞＝3 and AL2＞＝3)

return Y

END

ELSE IF (N=7)

IF(AL1＞＝2 and OV＞＝6 and AL2＞＝2)

return Y

ELSE IF(AL1＞＝6)

return Y

  ELSE IF(AL1＞＝3 and OV＞＝4 and AL2＞＝3)

returnY

END

END

return N

                   

For large groups, a test was performed comparing the sum of squares of the histogram bin to the expected value of CCs randomly placed within the group. The equations used for this test are given below:

$\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; m</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{{\mathrm{<span\; class="notranslate">\; <figure-callout\; id="2"\; label="h\; i"\; filenames="A20058004397900911.png,A20058004397900971.png"\; state="\{\{state\}\}">h</figure-callout></span><figure-callout\; id="2"\; label="h\; i"\; filenames="A20058004397900911.png,A20058004397900971.png"\; state="\{\{state\}\}">\; </figure-callout>}}_{\mathrm{<span\; class="notranslate">\; </span>}}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; \&times;</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; m</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

where m is the total number of histogram bins, n is the total number of characters, and _hi is the fill rate of the ith bin of the histogram. The term on the right-hand side of this equation is 2 times the expected value (mean), and for sufficiently large m and n, approximately the value for which there is a 0.1% probability that a randomly placed character will be accepted. An example of this processing is shown in FIG. 27 described below.

Referring to FIG. 24, if the group is accepted according to this test, and processing continues at step 2470. In step 2470, the group is maintained and the alignment check ends. Processing then terminates. Otherwise, if step 2440 returns false (No), processing continues at step 2450 . Decision step 2450 checks if there are more parameters to test. If so, processing continues at step 2430 for the next parameter. Otherwise, if all parameters have been tested, processing continues at step 2480 where the group is rejected. Processing then terminates.

The preceding description exposes a test based on one parameter and rejects groups where all tests fail. However, in view of this disclosure, it will be apparent to those skilled in the art that alternative approaches to combined testing of different parameters can be practiced without departing from the scope and spirit of the invention, such as accepting that almost But align groups in similar parameters (such as top and bottom bounding box), or create an overall score for the group based on many parameters.

3.2.2 Alignment example

FIG. 27( b ) shows a selection of irregularly arranged bounding boxes 2710 , 2712 , 2714 , . Figure 27(b) shows connected components arranged randomly. Figure 27(a) shows a histogram 2720 of the values of the base of the bounding box of the graph. FIG. 27( d ) shows the arrangement on a page of the bounding boxes 2740 , 2742 of text groups with well-aligned connected components, and FIG. 27( c ) shows the corresponding histogram 2730 . As shown, the histogram 2730 for text has a few large clusters of values, while the other histograms 2720 have more evenly spread values. Using the sum of squares of the values of the histogram bin as measurements, Figure 27(a) gives a value of 19, and Figure 27(c) gives a value of 47. The entry on the right hand side of the test above for m=19 and n=13 is 45. According to this test, therefore, the image data of Fig. 27(b) is rejected and the text data of Fig. 27(d) is accepted. Alternatively, the acceptance test may be based on other statistics, such as the total number of values within the library that are significantly greater than the average count.

4 produces a compressed output image

The backend module uses an inpainting process to make the background image more compressible by painting over the foreground region with the estimated background color. Inpainting is preferably performed on a lower resolution (eg 150dpi) background image. The inpainting algorithm is a single-round, patch-based algorithm and strives to enhance compressibility. The color of each pixel is chosen by interpolating from surrounding pixels on the left and right, rather than using one average color over a large area.

The algorithm performs the following steps: 1) Combine the masks for all foreground components to form one foreground mask for the tile; 2) Dilate the mask, thereby inpainting a small additional area around the foreground component; 3) ) in raster order on the tile:

a If the pixel is not masked, update the activity of the patch; and

b if the pixel is masked, draw the pixel with the color interpolated from the colors of the nearest unmasked pixels on the left and right;

4) if the activity of the unmasked region is below a certain threshold, paint the whole patch with the mean color of the unmasked pixels (this gives improved compression with ZLib compressed JPEGs); and 5) if the whole patch is masked, Paint the entire patch with the mean color of the previous patches. Step 2) above removes bleeding effects and improves compression and sharpens output quality.

FIG. 5 shows step 130 of FIG. 1 in detail. Steps 510 to 540 use a tile-based processing system similar to that described in FIGS. 2 and 3 . In step 510, the next tile to be processed is obtained. In step 520, an inpainting process is performed on the current tile to remove any foreground CCs identified in step 120 of FIG. 1 and to flatten any tiles that visually appear close to flat. In step 530, the current tile is compressed. This can be done using JPEG in YCrCb color space with 2 chroma channels subsampled 2:1 horizontally and vertically. Each tile of the reduced-resolution background image consists of 16×16 pixels, which means that these pixels can be encoded directly as four 8×8-pixel JPEG blocks for the Y channel, and for each of the Cr and Cb channels. 1 8x8 JPEG block of one without any buffering required between tiles.

In step 540, a check is made to determine if there are more tiles to process. Processing returns to step 510 if there are any more tiles to repair and compress. Otherwise, processing continues at step 550 . In step 550 the foreground is compressed, which involves compressing the foreground elements identified in step 120 . Groups foreground elements by color and creates a binary image at the full input resolution for each similarly colored group of foreground elements. Each created image can then be encoded as a CCITT G4 Fax if the image is large enough that the encoding yields a compression advantage in the output document.

In step 560, an output document is generated. Store compressed background and compressed foreground images in a composite compressed format. The format can be, for example, a PDF document. JPEG-encoded background images can also be further compressed using Flate (Zlib) compression. For JPEG images containing a large number of repeated flat blocks resulting from steps 520 and 530, this results in significant space savings. Composite documents can be written containing Flate and JPEG compressed background images, and page descriptions containing details of size, position, order and - in the case of binary foreground images - the color to draw each image on the page.

4.1 Repair patch

FIG. 30 shows step 520 of FIG. 5 in detail. This process modifies the downsampled background image in order to increase compressibility and enhances the sharpness of the foreground CCs by removing them from the background and flattening the image tiles with low visual activity. A small area around the foreground CC is also repaired in order to remove bleeding effects, thereby enhancing the image and increasing compressibility.

The process 520 shown in FIG. 30 removes the selected foreground CC from the low-resolution background by rendering the selected foreground CC in a color estimated by interpolating between the colors of the pixels to the left and right of the selected foreground CC. This increases compressibility. A small area around the outside of the CC is also repaired to further increase compressibility and enhance the appearance of the image. Compressibility is further increased by identifying tiles with background images that have low visual activity, and setting all their pixels to the same color.

The inputs to the process of FIG. 30 are the downsampled background image created in step 250 of FIG. 2 , the CC list from step 240 of FIG. 2 , and the foreground or background selection information from step 120 of FIG. 1 . In step 3010, the tile is checked to see if the tile is marked as "flat". If so, processing continues at tile flattening step 3040, otherwise processing continues at step 3020, where a full resolution foreground bit mask is formed for the tile. It has a bit set at each position corresponding to a foreground CC. In step 3030, regions of the background image corresponding to foreground CCs and small regions surrounding them are removed by inpainting them with colors interpolated from the colors of the pixels to the left and right of the CC. The activity of uninpainted pixels within the patch is also measured. In step 3040, if the tile activity is found to be low enough to be visually flat, the entire tile is flattened to a constant color. Processing then terminates.

4.1.1 Form patch foreground bit masking

FIG. 31 shows step 3020 of FIG. 30 for forming the tile foreground bit mask in more detail. In step 3110, an initial bit mask for the tile is created. The bitmask is the same width as the tile, and one row taller than the tile. The first line of this bitmask is set to be the same as the last line of the tile above, unless the tile is the first band in the document, in which case the first line of the bitmask is set to null. This allows the inpainted area to extend under the foreground CC with a bottom edge aligned with the tile border.

In step 3120, the next CC within the tile is obtained. In step 3130, the CC is checked to determine if the CC is a foreground CC (in step 120). If the CC is a foreground CC, processing continues at step 3140. Otherwise, processing continues at step 3150. In step 3140, the bitmask corresponding to the CC and the current tile is combined with the bitmask created in step 3110 using a bitwise OR operation. Processing then continues at step 3150. In step 3150, a check is made to determine if there are more CCs within the current tile. If so, processing returns to step 3120. Otherwise, if all CCs within the tile have been processed, the result of step 3150 is NO, and processing continues at step 3160 . In step 3160, the last row of the formed mask is saved so that it can be used in step 3110 when processing the tile directly below that tile on the page. The bitmask created in process 3020 of Figure 31 is the full resolution of the input image.

4.1.2 Inpainting pixels and measuring patch activity

FIG. 32 shows step 3030 of FIG. 30 in more detail. Each pixel is checked in raster order until one is found that should be inpainted, which marks the beginning of a string of pixels to inpaint. Subsequent pixels are checked until the end of the string of pixels to be repaired is found. This horizontal string of pixels is then colored with a color that is linearly interpolated between the colors of the pixels to the left and right of the repair string.

Referring to FIG. 32, step 3210 gets a row of a tile. In step 3220, the start of the next string of pixels is found based on the row's cumulative pixel activity. Each pixel within a row is examined in raster order, and pixel activity within a tile is accumulated until a pixel that should be repaired is found. Pixel activity for unrepaired pixels is recorded by accumulating pixel values and squaring these pixel values, and keeping a count of the number of pixels measured. To decide whether each pixel should be inpainted, the pixel location is compared to the corresponding location within the tile foreground bitmask created in step 3020 of FIG. 30 . Since the tile bitmask has twice the resolution of the background image, there are 4 pixels in the mask corresponding to the area covered by one pixel within the background image. To improve compression and remove bleeding edge effects from foreground CCs, a small additional area around the edges of foreground CCs is repaired. To do this, 8 pixels in the full resolution foreground mask are examined in order to decide whether to inpaint the current background pixel. FIG. 34 shows example pixels 3410 in a background image tile 3430 , and the corresponding full-resolution masked pixels 3420 inspected. If any of these 8 pixels indicated by 3420 are set in the mask 3440, ie corresponding to the location of the foreground CC, the pixel is repaired 3410. Since the bitmask 3440 is stored as a matrix of bit vectors, these 8 pixels 3420 can be checked quickly using a bitwise AND operation. Alternatively, this can be accomplished by upscaling the set pixels within bitmask 3420, and then downsampling. Records the color of the last pixel checked that was not repaired on each row, and uses that color as an internal if the first pixel of the same row of the next tile is to be repaired so that it is available when processing the next tile to the right. interpolation.

Referring to FIG. 32, in decision step 3230, a check is made to determine whether any pixels to be repaired were found before the end of line. If a pixel to be repaired is found, processing continues at step 3250. Otherwise, processing continues at step 3240. In step 3250, the remaining pixels in the row are checked in raster order to find the end of the string of pixels in the row that should be repaired. The same test as used in step 3220 is used here to determine whether a pixel should be repaired. In step 3260, a check is made to determine if the end of the string of pixels to be repaired is found before the end of the row. If the end of the string of pixels to be repaired is found before the end of the row is reached, processing continues at step 3270. In step 3270, each pixel within the string of pixels to be inpainted is set to a color that is linearly interpolated between the colors of the nearest uninpainted pixel on the left and right. If the pixel string to be inpainted extends to the left-hand side of the tile, the last value saved for the same row in the previous tile is used as the left interpolated value. Processing then continues at step 3220 and a search is made for the next string of pixels to be repaired. If in step 3250 the end of the line is reached without finding any pixels that should not be repaired, decision step 3260 directs processing to continue at step 3280 . In step 3280, each pixel within the string of pixels to be inpainted is set to the value of the nearest uninpainted pixel to the left, which may be the value saved for the same row in a previous tile. After step 3280, processing continues at step 3240.

In step 3240, a check is made to determine if there are more rows within the tile to process. If there are more rows within the tile, processing continues at step 3210. Otherwise, if there are no more rows, processing ends.

4.1.3 Repair example

Figure 35 shows some examples of one-dimensional repairs. Two examples 3510, 3520 are provided with before and after graphs where pixel intensity is plotted as a function of position X. In the first example 3510, the string of pixels to be inpainted is entirely within the tile, and the value of the inpainted pixel is replaced by a value that is linearly interpolated between the values of the immediately left and right uninpainted pixels (diagonally hatched instruct). The inpainted area is slightly larger than the foreground component in order to remove any bleeding effects; this is shown as the enlarged masked area. Find and fix the color of each pixel by interpolating between the left and right unmasked pixel colors. In the second example 3520 of FIG. 25 , the pixel string to be repaired crosses the patch edge 3530 . When processing left-handed tiles, replace the value of the pixel to be inpainted with the value of the uninpainted pixel immediately to the left. When processing the right-hand tile of example 3520, the value of the repaired pixel is set to the value of the linear interpolation between the value of the last unrepaired pixel recorded for the row and the value of the first unrepaired pixel to the right.

4.1.4 Chip planarization

FIG. 33 shows step 3040 of FIG. 30 in more detail. In decision step 3310, a check is made to determine if all pixels have been repaired. In particular, the number of inpainted pixels recorded in step 3220 is checked. If all pixels within the tile are repaired, then the viewable area of the tile is considered low, and processing continues at step 3320. In step 3320, all pixels within the current tile are colored (set) to the mean color of previous tiles in raster order. This significantly increases the compressibility of the background image when using block-based compression techniques such as JPEG. Processing then terminates. If step 3310 determines that not all pixels within the tile were repaired, processing continues at decision step 3330 . In step 3330, the activity of the unrepaired pixels measured in step 3220 is checked against a predetermined threshold. If the activity is found to be less than this threshold, the active visible area of the patch within the reconstructed image is considered to be close to flat. In this case, processing continues at step 3340 and the tile is rendered completely flat by painting all pixels within the tile with the mean color of the uninpainted visible pixels within the tile. This significantly improves the compressibility of background images. After step 3340, or after step 3330 if the activity within the patch is found to be above a threshold, the process of Figure 33 ends.

5 hardware embodiment

Figure 51 shows a system 5100 according to a second embodiment of the invention. System 5100 features efficient data flow between different stages of the processing pipeline. This design greatly reduces memory bandwidth and enables the system 5100 to run very fast.

Scanners typically acquire scan data in a raster order of pixels. The pixel data is then stored and usually compressed for further image processing. In traditional scan-to-document applications, scan data typically needs to be retrieved from a storage device, decompressed, and then held in memory for segmentation and layout analysis in order to process the image data. This is often the case with high-speed scanners, simply because segment processing cannot keep up with the speed at which the scanner streams the raster data page by page.

This not only requires a large memory buffer, but also requires high memory bandwidth since each image pixel must be written and read at least twice. First the pixels must be written to memory by the scanner, and then the compressor reads the data from memory and compresses the data. Later, the decompressor must read the compressed data and decompress the data into memory. Finally, the image processor can segment the decompressed data. For each raw image pixel, there is at least one redundant memory read and write, not to mention compressed data. For high resolution scanners (eg, 600dpi), this means over 200MB of additional data.

This embodiment of the invention employs high speed, automatic segmentation that works directly on the raster data streamed page by page from the scanner 5105 in real time. As a result, redundant memory reads and writes are completely eliminated, and the memory buffer size is also greatly reduced.

Bus 5110 carries scanned raster data from scanner 5105, which is written to module 5115 (line buffer). In this example, a 64-line buffer is used, but other sizes may be used depending on the height of the band explained later. The line buffer 5115 stores data strips processed by the code segmentation module 5125 while new incoming scan data strips are collected. Module 5125 reads data tiles from line buffer 5115 over bus 5120 and color-segments the data into connected components on a tile basis. When module 5125 ends a data stripe, a new data stripe is read from line buffer 5115 for processing. The old strip buffer is then used to collect new incoming raster data. The height of the strip is determined by the height of the tile, and the line buffer 5115 needs to be twice the height of the strip. In this embodiment, the preferred tile size is 32x32.

Module 5125 is implemented in hardware in this embodiment so that the processing speed of the tape can keep up with the speed at which the scanner 5105 can generate new data tapes. The outputs of module 5125 are compressed connected components (CC) on bus 5135 to layout analysis module 5140 and uncompressed or compressed downsampled images on bus 5130 to inpainting module 5150 . Data on the bus 5135 can be written to memory until a distinct region of the page or the entire page of the CC is generated. Module 5140 performs layout analysis using only compact connected components data. Since the data is compact, the processing power required to perform layout analysis is small. Therefore, the layout analysis module can be implemented as software (SW) executed by an embedded processor in real time. The output of the layout analysis module is foreground information provided on bus 5145 , which follows the data from bus 5135 . Data on bus 5130 may also be written to memory until a distinct area of a page or an entire page of CCs is generated.

The inpainting module 5150 performs foreground removal on the downsampled image (provided via the bus 5130 ) on a tile-by-tile basis. This module 5150 can be implemented on the same embedded processor that runs the layout analysis software 5140, or alternatively, it can be implemented in hardware (HW). Module 5150 then inpaints the foreground region with the estimated background color on the downsampled image to produce a background image. The foreground-removed background image is output on bus 5155 and the foreground mask is generated on bus 5175.

Output generation module 5160 creates a layout analyzed document, such as a PDF file, from the foreground image generated on bus 5175 and the background image generated on bus 5155 . Module 5160 can be implemented in software running on the same embedded processor.

In a second embodiment, modules 5115 and 5125 work on real-time page-by-page scan data and produce compact connected components and downsampled images on page N. Modules 5140, 5150, and 5160 work sequentially using the data produced by module 5125 on page N-1. Thus, the system can deliver layout-analyzed documents in real-time from real-time data from high-speed scanners.

Blocks 5125, 5140, 5150 and 5160 may be implemented in the manner described for the corresponding steps in the first embodiment.

5.1 Color segmentation module

Figure 52 shows module 5125 in detail. Components of the Color Segmentation CC module 5125 include the Dehalftoning module 5220, which takes the pixel stream in tile order and removes any artifacts caused by scanning material printed using a printed halftoning system such as an inkjet printer. Dehalfting module 5220 is a hardware embodiment of the software embodiment described above. Internally the block can use static RAM and pipelining to achieve the required speed.

The pixels output from the dehalfting module 5220 are passed to the color conversion module 5230, which converts the pixels from the input color space (typically RGB) to the YCbCr luma/chrominance space. This module 5230 performs the necessary multiplication and addition for each pixel according to the following formula:

These arithmetic operations are performed in scaled fixed point arithmetic in order to reduce complexity and increase the speed of the module 5125 . The output from the color conversion module 5230 is passed to two modules, the scan down module 5240 and the connected components analysis module 5260 . The downscan module 5240 performs a simple averaging of a set of 4 (within a 2x2 square) or 16 (within a 4x4 square) colors to form each output pixel. The pixels output from the downscan module 5240 are then compressed by the hardware JPEG compressor 5250 .

6 computer implementation

Methods according to embodiments of the invention may be implemented using one or more general purpose computer systems, printing devices, and other suitable computing devices. The processes described with reference to one or more of Figures 1-52 may be implemented as software, such as an application program executed within a computer system or embedded in a printing device. Software may include one or more computer programs, including applications, operating systems, procedures, rules, data structures, and data. Instructions may be structured as one or more code modules, each for performing one or more specific tasks. The software may be stored on a computer readable medium (including, for example, one or more storage devices described below). The computer system loads the software from the computer readable medium and then executes the software.

FIG. 7 shows an example of a computer system 700 on which embodiments of the invention may be implemented. A computer-readable medium having such software recorded thereon is a computer program product. Use of the computer program product within a computer system may implement advantageous means for carrying out one or more of the methods described above.

In FIG. 7, a computer system 700 is coupled to a network. An operator may provide input to the computer 750 using a keyboard 730 and/or a pointing device such as a mouse 732 (or, for example, a touch pad). Computer system 700 may have any number of output devices, including line printers, laser printers, plotters, and other rendering devices connected to the computer. Computer system 700 may be connected to one or more other computers through communication interface 764 using a suitable communication channel 740 such as a modem communication path, router, or the like. Computer network 720 may include, for example, a local area network (LAN), a wide area network (WAN), an intranet, and/or the Internet. Computer 750 may include a processing unit 766 (e.g., one or more central processing units), memory 770 (which may include random access memory (RAM), read only memory (ROM), or a combination of both), input/output (IO ) interface 772, graphical interface 760, and one or more storage devices 762. Storage devices 762 may include one or more of the following: floppy disks, hard drives, magneto-optical drives, CD-ROMs, DVDs, data cards or memory sticks, flash RAM devices, magnetic tape, or several other non-volatile memory devices known to those skilled in the art. Volatile storage device. Although in FIG. 7 the storage device is shown as directly connected to the bus, such a storage device may be connected through any suitable interface, such as a parallel port, a serial port, a USB interface, a Firewire interface, a wireless interface, a PCMCIA slot wait. For purposes of this description, the memory unit may include one or more of memory 770 and storage 762 (as indicated by dashed boxes surrounding these elements in FIG. 7 ).

Each component of computer 750 is typically connected to one or more other devices by one or more buses 780 shown generally in FIG. 7, which in turn include data, address, and control buses. Although a single bus 780 is shown in FIG. 7, those skilled in the art will appreciate that a computer, printing device, or other electronic computing device may have several buses, including processor bus, memory bus, graphics card bus, and peripheral bus. one or more. Suitable bridges may be used to interface communications between these buses. Although a system using a CPU is described, those skilled in the art will appreciate that other processing units capable of processing data and performing operations may be used without departing from the scope and spirit of the invention.

Computer system 700 is provided for purposes of illustration only, and other configurations may be employed without departing from the scope and spirit of the invention. Computers on which the embodiments may be implemented include IBM PC/AT or compatibles, laptop/notebook computers, one of the Macintosh(TM) family of PCs, Sun Sparcstation(TM), PDAs, workstations, and the like. The above are merely examples of the types of devices in which embodiments of the invention may be practiced. Typically, the processes of the embodiments described below reside as software or a program recorded on a hard disk drive as a computer-readable medium, and are read and controlled using a processor. Intermediate storage of programs, intermediate data, and any data fetched from a network can be implemented using semiconductor memory.

In some cases, the program may be provided encoded on a CD ROM or floppy disk, or alternatively, the program may be read from a network by, for example, a modem device connected to the computer. Additionally, data may be read from other computer-readable media, including magnetic tape, ROM or integrated circuits, magneto-optical disks, wireless or infrared transmission channels between a computer and another device, computer-readable cards such as PCMCIA cards, and the Internet and intranets ( Including e-mail transmissions and information recorded on the website etc.)) The software is loaded into the computer system. The foregoing are merely examples of related computer-readable media. Other computer readable media may be used without departing from the scope and spirit of the invention.

7 Industrial Applicability

Embodiments of the invention are applicable to the computer and data processing industries. The foregoing has only described a small number of methods, apparatuses and computer program products for processing and compressing digital images according to embodiments of the present invention, and modifications and/or changes may be made thereto without departing from the scope and spirit of the present invention, these embodiments are illustrative rather than restrictive.

Claims (44)

1. method of giving the digital image segmentation comprise a plurality of pixels, the method comprising the steps of:

Produce a plurality of block of pixels from described digital picture; And

Use described block of pixels to be communicated with component for each piece generates at least one in the mode of single-wheel, described generation step comprises:

A block of pixels is segmented at least one is communicated with component, each is communicated with component and comprises continuous and semantic one group of relevant pixel on the space;

With described described at least one be communicated with component with from least with pre-treatment

At least one connection component merging that other piece segmentation goes out; And

The position of described connection component in described image with described of the form of compactness storage.

2. method as claimed in claim 1, the pixel that wherein said semanteme is relevant comprises similar painted pixel.

3. method as claimed in claim 1, wherein said generation step comprises substep:

Described digital picture is arranged as a plurality of bands, and each band comprises the pixel column that links up of predetermined number; And

Cushion and handle described band one by one, wherein said treatment step comprises the following substep that the band of each current buffering is carried out:

Described current band is arranged as a plurality of block of pixels; With

Cushion and handle described current band one by one for described generation step described.

4. method as claimed in claim 1, wherein said storage substep comprises store M-1 bitonal bitmap, and wherein M is communicated with component in a piece, and M is an integer.

5. method as claimed in claim 1, wherein said storage substep comprises the storage key map.

6. method as claimed in claim 1, wherein said segmentation substep comprises:

Estimate some representative colors of each piece;

Each piece is quantified as described representative colors; With

Form the connection component from the piece of each quantification.

7. method as claimed in claim 6, wherein said segmentation substep also comprises: the subclass of the described connection component that will form merges.

8. method as claimed in claim 7, wherein said merging substep comprises the statistic of collecting described connection component.

9. method as claimed in claim 8 also comprises the step of the connection component of removing the described formation be considered to noise.

10. method as claimed in claim 9, wherein said noise comprise having the pixel counts that is lower than predetermined threshold and be higher than the boundary length of another predetermined threshold and the component that is communicated with of pixel counts ratio.

11. method as claimed in claim 8, wherein said statistic comprise in bounding box, pixel counts, boundary length and the average color any one or a plurality of.

12. method as claimed in claim 8, wherein said combining step comprises:

The connection component of a piece is merged with the component that is communicated with of the piece of the left side and top; Described statistic with the connection component of upgrading described merging.

13. as the method for claim 12, wherein said statistic comprises all any one in the color or a plurality of of bounding box, pixel counts, filling ratio peace.

14. method as claimed in claim 6, wherein said estimator step comprises:

Based on the yuv data of the pixel in each piece, form the histogram relevant with a plurality of color libraries;

Based on the statistics with histogram amount to each block sort; With

Merge the storehouse color based on described block sort, so that form described representative colors.

15., also be included in one and form the step of key map for each pixel in taking turns as the method for claim 14.

16. as the method for claim 15, wherein said quantization step comprises:

The non-NULL storehouse is quantified as representative colors;

Be created to the storehouse mapping of described representative colors; With

Use the mapping of described storehouse that described key map is remapped to described representative colors.

17. as the method for claim 14, wherein said formation substep comprises:

Determine the brightness band based on the Y value;

Determine the color row based on U and V value;

Pixel color is accumulated to described mapping library; With

Increase progressively the pixel counts of described mapping library.

18. as the method for claim 17, the step of wherein said definite brightness band comprises that also the brightness band is anti-aliasing.

19. as the method for claim 17, the step of wherein said definite color row comprises that also the color row are anti-aliasing.

20. as the method for claim 12, wherein said combining step is included as the following substep that each interior connection component of contact the current block left and coboundary is carried out:

Searching is communicated with component along the row that described public boundary touches described current connection component; With

Determine the optimal candidate of merging.

21. a device that comprises processor and storer is used for giving the digital image segmentation comprise a plurality of pixels according to any one method of claim 1 to 20.

22. a computer program that comprises computer-readable medium, this computer-readable medium have the computer program that is used for giving according to any one method of claim 1 to 20 digital image segmentation comprise a plurality of pixels that is recorded in wherein.

23. a method that produces the compact representation of color document automatically, described method comprises step:

In one takes turns by the piece raster order, with the digital image segmentation of color documentation page for being communicated with component;

Based on the compactness of described whole page or leaf, be communicated with the component statistic, use topological analysis that the described digital picture of described page or leaf is divided into prospect and background image;

In the position that at least one part of described foreground image has been covered described background image, in one takes turns, repair at least one part of described background image with the piece raster order; With

Store described foreground image and background image, to form compact document.

24., also comprise step to described background image down-sampling as the method for claim 23.

25., also comprise the step of compressing described background image as the method for claim 23 or 24.

26. as the method for claim 25, wherein said compression step relates to lossy compression method.

27., also comprise difference compression to the background image of described lossy compression method as the method for claim 26.

28. a device that comprises processor and storer is used for producing automatically according to any one method of claim 23 to 27 compact representation of color document.

29. a computer program that comprises computer-readable medium, this computer-readable medium have the computer program that is used for producing automatically according to any one method of claim 23 to 27 compact representation of color document that is recorded in wherein.

30. an analysis comprises the method for the digital picture of a plurality of pixels, described method comprises step:

With described digital image segmentation is object, wherein to represent described segmentation more than two labels;

For each object provides one group of attribute;

Be the subclass of described object, use to comprise to measure to determine between the adjacent object of sharing the border, whether there is father-child's relation;

Object-based attribute forms many group objects of sharing common father; With

Object class is given in attribute and grouping according to object.

31., wherein use the bounding box around each object and the information of the relation of touching between description object to determine described comprising as the method for claim 30.

32. as the method for claim 31, if wherein two objects contact on the border, and the bounding box of an object comprises the bounding box of another object fully, then described object comprises described another object.

33. as the method for claim 30, wherein said formation group step comprises:

Consider common father's the child object of row among the child right; With

Use described object properties, determine whether each is to being grouped into together.

34., wherein only consider the adjacent object in the row child object with identical father is divided into groups as the method for claim 33.

35., wherein divide into groups to object based on bounding box and colouring information as the method for claim 33.

36., wherein, a group objects is categorized as text according to the test of the text class quality of described object in described group as the method for claim 30.

37. as the method for claim 36, the wherein said test that is used for text class quality comprises:

The single value of representing the position of described object for each object identification;

Form the histogram of described value; With

According to described histogrammic Attribute Recognition text.

38. as the method for claim 30, comprise that also the attribute according to other object adds them the text classification group of object to, and no matter their father-child's attribute step how.

39. an analysis comprises the method for digital picture of a plurality of pixels of documentation page, described the method comprising the steps of:

Give described digital image segmentation, so that form object based on described image;

Form the group of described object; With

Whether each that determine described group of objects represents text, and described determining step comprises:

According to the position of described object on described page or leaf, for each object is discerned single value;

Form the histogram of described value; With

According to described histogrammic Attribute Recognition text.

40. as the method for claim 39, wherein said histogrammic described attribute is the sum that has in the described histogram more than the object in the storehouse of the object number of appointment.

41. as the method for claim 39, wherein said attribute is the quadratic sum of the counting in the described histogram.

42. as the method for claim 39, wherein the described single value of the position of the described object of expression of each object is the limit of the bounding box of described object.

43. a device that comprises processor and storer is used for comprising according to any one methods analyst of claim 39 to 42 digital picture of a plurality of pixels.

44. a computer program that comprises computer-readable medium, this computer-readable medium have the computer program that is used for comprising according to any one methods analyst of claim 39 to 42 digital picture of a plurality of pixels that is recorded in wherein.

Images