System and method for connecting regions of image data having similar characteristics

BACKGROUND OF THE INVENTION

1.

Field of Invention

This invention is directed to organizing image data into regions having similar color characteristics.

2.

Related Art

Documents scanned at high resolutions typically require very large amounts of storage space. Furthermore, a large volume of image data requires substantially more time and bandwidth to manipulate, such as transferring over a local or wide area network, over an intranet, an extranet or the Internet, or other distributed networks.

Documents, upon being scanned using a scanner or the like, are typically defined using an RGB color space, i.e., in raw RGB format. However, rather than being stored in this raw scanned RGB format, the document image data is typically subjected to some form of data compression to reduce its volume, thus avoiding the high costs of storing such scanned RGB document image data.

Lossless run-length compression schemes, such as Lempel-Ziv (LZ) or Lempel-Ziv-Welch (LZW), do not perform particularly well on scanned image data or, in general, image data having smoothly varying low-spatial frequencies such as gradients and/or natural pictorial data, while lossy methods such as JPEG, work fairly well on smoothly varying continuous tone image data. However, lossy methods generally do not work particularly well on binary text and/or line art image data, or, in general, on any high spatial frequency image data containing sharp edges or color transitions, for example.

<patcit id="pcit0001" dnum="WO02056255A2"><text>WO 02/056255 A2</text></patcit> describes methods and apparatus for analyzing an image. A method analyzes an image to be scanned and analyzes at least part of the image pixel-by-pixel. Elements in the image are characterized according to a perceived characteristic and each image element having a given characteristic that is adjacent a similar or identical image element is identified. In one form, there are preferably at least three different characteristics, such as black, background and edge, by which the image elements can be characterized. In another form, image elements that are close enough to each other in physical location and close enough to each other in image characteristic are grouped together or included in a blob. Sub-blobs can be found to be part of a more predominant blob.

<nplcit id="ncit0001" npl-type="b"><text>ZUGAJ D ET AL: "A new approach of color images segmentation based on fusing region and edge segmentations outputs" PATTERN RECOGNITION, ELSEVIER, KIDLlNGTON, GB, vol. 31, no. 2, February 1998 (1998-02), pages 105-113, XP4101082, ISSN: 0031-3203-A</text></nplcit> cooperative strategy within a multi-resolution color image segmentation is presented, which attempt to extract the meaningful information (regions and boundaries), then fuse these two approaches in order to achieve an accurate, robust and suitable segmentation. A blob filling coloration algorithm allows to design, from the segmented image, a synthesis image which appears as a simplified but faithful copy with a chosen resolution of the original image.

<patcit id="pcit0002" dnum="US4718090A"><text>US 4,718,090</text></patcit> describes method and apparatus for high-speed processing of video images. Each pixel, in lines of bicolored pixels of a raster scanned video image containing at least one object, is identified as to the object of which the pixel corresponds. Adjacent bicolored pixels of the same color across a line are grouped into corresponding numbered pixel groups. Pixel groups of the same color are downwardly grouped into numbered blobs of pixel groups. When a next line pixel group occurs which is of the same color with more than one previous line pixel group, the next line pixel group is grouped as part of first occurring previous line blob. Additional pixel group matches occurring between pixel groups of a previous and next line are upwardly grouped to provide a common ancestor blob number to each blob of the pixel group in each additional pixel group match. Blobs having common ancestor blob numbers are grouped into numbered object with each blob belonging to an object so that each pixel, through a blob number, corresponds to an object number.

<nplcit id="ncit0002" npl-type="b"><text>LAMBERT P ET AL: "Symbolic fusion of luminence-hue-chroma features for region segmentation" PATTERN RECOGNITION, ELSEVIER, KIDLINGTON, GB, vol. 32, no. 11, November 1999 (1999-11), pages 1857-1872, XP004173548, ISSN: 0031-3203</text></nplcit> - An original segmentation method is applied to color images. The two key elements of this method are the use of a color space where hue is explicitly defined and processed according to its relevance which can be linked to chroma and the use of symbolic representations and rule-based systems combining color and luminance features in order to define homogeneity between pixels.

SUMMARY OF THE DISCLOSURE

It is the object of the present invention to improve method and apparatus for organizing image data into regions having similar color characteristics. This object is achieved by providing a method for identifying regions of pixels in image data according to claim 1 and an apparatus for identifying regions of pixels in image data according to claim 5. Embodiments of the invention are set forth in the dependent claims.

BRIEF DESCRIPTION OF DRAWINGS

Various exemplary embodiments of systems and methods of this invention will be described in detail, with reference to the following figures, wherein:

<figref idref="f0001">Fig. 1</figref> illustrates an exemplary document image decomposed into multiple binary foreground image planes and a background plane;

<figref idref="f0002"><b>Fig.</b> 2</figref> illustrates one exemplary system in which the blob identifying module can operate;

<figref idref="f0003">Fig. 3</figref> illustrates in greater detail an exemplary embodiment of a blob identifying module;

<figref idref="f0004">Fig. 4</figref> illustrates in greater detail an exemplary embodiment of a bottom-to-top module;

<figref idref="f0005">Fig. 5</figref> illustrates an exemplary blob ID image, in which the regions indicated refer to the scan tables;

<figref idref="f0006">Fig. 6</figref> shows an exemplary scan table structure;

<figref idref="f0007">Fig. 7</figref> shows an exemplary scan table entry;

<figref idref="f0008">Fig. 8</figref> shows an exemplary temporary blob table ID stack allocation structure;

<figref idref="f0009">Fig. 9</figref> shows an exemplary temporary blob table entry;

<figref idref="f0010">Fig. 10</figref> illustrates an exemplary data flow diagram for the bottom-to-top module shown in <figref idref="f0005">Fig. 5</figref>;

<figref idref="f0011">Fig. 11</figref> illustrates how scan table entries are linked vertically; and

<figref idref="f0012">Fig. 12</figref> illustrates an exemplary blob ID image, in which the regions indicated refer to the temporary blob IDs; and

<figref idref="f0013">Fig. 13</figref> is a flowchart outlining one exemplary method for generating a global table of blobs and a blob ID image.

<figref idref="f0014">Fig. 14</figref> illustrates the structure of two translate tables;

<figref idref="f0015">Fig. 15</figref> is a flowchart outlining further detail of the select next scan table step of <figref idref="f0013">Fig. 13</figref>; and

<figref idref="f0016">Fig. 16</figref> is a flowchart outlining further detail of the translate scan table step of <figref idref="f0013">Fig. 13</figref>.

DETAILED DESCRIPTION

Various exemplary embodiments of systems and methods are disclosed that automatically process scanned and/or printed color documents to produce small, highly-compressed image data files that accurately capture the original document content. Data files are generated by scanning in documents, and analyzing the data in a given scan line to determine which pixels of the image can be grouped together because they have similar color and edge characteristics. The scan lines are then linked according to information in a link field, to generate two-dimensional regions of pixels of similar color, and defined by a closed curve boundary. These regions, or "blobs", are then clustered together by combining areas of similar color which overlap spatially. The combined areas (clustered regions) are then placed in one of a plurality of binary foreground layers, and may be compressed for output as a PDF file, for example.

<figref idref="f0001">Fig. 1</figref> shows image data of a document that is decomposed into a background continuous tone or grayscale layer (background layer) 210 and N binary foreground layers. In this example, there are six (N=6) binary foreground layers 220-270. The image data contains low spatial frequency color data that are separated into six distinct color values. Each of the six color values is associated with a particular one of the multiple binary foreground layers 220-270 which include spatial regions 220'-270' that contain one of the six colors. Data not included in one of the regions 220'-270' remains in the background layer 210. Systems and methods will be described for generating the spatial regions 220'-270' that will each be clustered into a binary foreground layer.

An input pixel can only be assigned to one of the multiple foreground planes or left in the background plane. Therefore, image data portion in any of the multiple binary foreground layers 220-270 does not overlap other image data portions in any of the other multiple binary foreground layers 220-270. As a result, each of the binary foreground layers 220-270 can be individually combined with the background layer 210 without regard to order or sequence. When all of the multiple binary foreground layers 220-270 are combined with the background layer 210, the reconstructed image 280 is obtained.

Systems and methods are described for identifying the blobs which will be clustered into regions 220'-270' that are to be assigned to each binary image plane.

<figref idref="f0002">Fig. 2</figref> shows an exemplary system for generating the N binary foreground layers from a scanned document image. <figref idref="f0002">Fig. 2</figref> shows a document 300, being scanned by a scanner 400 to generate image data in, for example, an RGB color space, and the image data is input to the N-layer image data generating system 1000. The N-layers produced by the N-layer image data generating system 1000 are then compressed by compress module 800 and output as a PDF file, for example.

The first module in the N-layer image data generating system 1000 is the color conversion module 500. The color conversion module 500 may convert the RGB data to a YCC color space, for example. As is well known, the YCC color space includes a luminance component (Y) and two chroma components (CC). The chroma components may be subsampled at a 2:1 ratio, at least in one direction if not in both, so that there are half as many data points in the chroma components as there are in the luminance components. Other color spaces, such as Lab may also be used.

The image in the YCC color space may then be input to a blob identifying module 600 which generates a list of the regions, or blobs, appearing in the image. The blobs are identified based on color and edge characteristics. Blobs are regions having a continuous boundary, which encloses pixels having similar color values. The blob identifying module 600 assigns a blob ID to each pixel in the image, indicating to which blob, if any, the pixel belongs. Pixels which do not belong to blobs are assigned to the background layer. A map of the blob IDs for each pixel location is a blob identification (blob ID) image, and is generated by the blob identifying module 600.

The blob identifying module 600 also generates a global table of blobs (GTB) which is a list of all blobs found in the document image 280. The systems and methods described herein are for the generation of the blob ID image and the GTB. The blob ID image and the GTB will be described further below, along with examples, in reference to the blob identifying module 600.

The blob ID data, the GTB are then input to the blob cluster processing module 700. The blob cluster processing module 700 then organizes the blobs in the global table of blobs, associating blobs of similar color and which overlap spatially into clusters. The blob cluster processing module 700 assigns the clustered regions to one ofN foreground planes, depending on the color value of the combined region.

The blob cluster processing module 700 outputs the binary data for each of the binary foreground layers and the background layer to the compress module 800. The compress module 800 may compress each of the binary foreground layers and the background layers differently, using a compression routine that is appropriate for the particular type of data being compressed, to generate compressed image data for the binary foreground layers and the background layer. The compress module 800 may then output the compressed binary foreground and background layers in a suitable format, such as PDF format, to a downstream process.

<figref idref="f0003">Fig. 3</figref> shows further detail of an exemplary blob identifying module 600. The blob identifying module includes a top-to-bottom module 610 and a bottom-to-top module 620. The top-to-bottom module 610 examines each pixel in a scan line, along with a number of context pixels, and identifies to which blob the pixel of interest belongs. The top-to-bottom module 610 then outputs a scan table for each scan line, which includes an identification of up to 255 blobs, or other convenient number, which may appear in any particular scan line of the image. Since the blobs identified by the top-to-bottom module 610 are contained within a single scan line, the blobs in this situation are one-dimensional "linear" blobs. The top-to-bottom module 610 also generates a blob ID image, which assigns to each scanned pixel in the image the identification of the blob listed in the scan table, to which the particular pixel belongs. The operation of the top-to-bottom module 610, and the generation of the scan table, is described in detail in co-pending <patcit id="pcit0003" dnum="US2005180628A1"><text>U.S. Patent No. US 2005180628 A1</text></patcit> filed on an even date herewith and published on 18 August 2005.

An example of an initial blob ID image is shown in <figref idref="f0005">Fig. 5</figref>. The blob ID image has a blob identifier for each pixel in the image. The blob ID image shown in <figref idref="f0005">Fig. 5</figref> has a blob, roughly in the shape of an "A" character, whose extent and identity will be determined using the systems and methods according to this invention.

<figref idref="f0004">Fig. 4</figref> shows further detail of the bottom-to-top module 620. The bottom-to-top module 620 includes a CPU 655, and input/output port 660, a memory 665, a scan table translator 670, a blob content updater 675, and a global table of blobs generator 680. The above components 655-680 may be coupled together via a bus 685. While the bottom-to-top module 620 is illustrated using a bus architecture diagram, any other type of hardware configuration may be used such as using application specific integrated circuits (ASICs) to implement one or more of the components, or writing a computer program that executes in the CPU 655 to perform all the functions of the bottom-to-top module.

The bottom-to-top module 620 inputs the initial blob ID image, the current scan table for the current scan line, and the previous scan table for the previous scan line through the input/output port 660 from the top-to-bottom module 610, and stores the data in memory 665. The bottom-to-top module may receive the data for one scan line and a previous scan line at a time, or it may receive the data for an entire image, and store the data in memory 665.

Each line in the blob ID image of <figref idref="f0005">Fig. 5</figref> is associated with a scan table, which stores information relating to the blobs identified in each scan line. The scan table for the line marked "example" is shown in <figref idref="f0006">Fig. 6</figref>. The line marked "example" in <figref idref="f0005">Fig. 5</figref> has a number of pixels which are associated together. The scan table for this line has four scan table entries, one for blob #4, one for blob #3, one for blob #2, and one for blob #1, as identified in the blob ID image. (Blobs labeled "0" are referred to the background layer.) The pixels belonging to the blob need not be contiguous, and in fact for the example line, they are not. The blob IDs in the initial blob ID image refer to the blob IDs in the current scan table.

A scan table can hold up to 255 entries, or other convenient number, with each entry using 2 bytes of memory for a 255-entry scan table. An example of a scan table entry is shown in <figref idref="f0007">Fig. 7</figref>. This scan table entry corresponds to the blob identified as #4 in the blob ID image. The two bytes of the scan table entry include the xlink field and the ylink field. The xlink field links each blob with pixels on the same line, which belong to the same blob. The xlink connections may be maintained as a circular list, so a blob that is not horizontally connected to any other blobs may be connected to itself, that is, the link points to itself. The ylink field links blobs identified on the current scan line, with blobs previously identified on the scan line below. Therefore, the scan table entry for blob #4 of the example line, has an xlink entry which points to the second occurrence of blob #4 on the same scan line, and a ylink entry which links blob #4 to blob #3 on the scan line below.

Each scan entry is 2 bytes in size, and each scan table contains up to 255 valid entries. Therefore the scan table for each scan line requires 256 entries * 2 bytes = 512 bytes of memory.

The bottom-to-top module 620 will take the scan table entries and link the blobs vertically, by giving the blobs another temporary ID, while the module is assembling the contents of the blob. Like the scan table, the temporary IDs are stored in a table containing up to 255 temporary blob IDs. An example of the temporary blob ID table is shown in <figref idref="f0006">Fig. 6</figref>.

An example of a temporary blob ID entry is shown in <figref idref="f0009">Fig. 9</figref>. As compared to the scan table ID entry, the temporary ID entry contains additional information related to the two-dimensional aspects of the temporary ID. In particular, the temporary ID entry contains four additional fields, min_x 735, max_x 740, min_y 745 and max_y 750, which are the x- and y-extents of a "bounding box" which surrounds the temporary blob. The bounding box is the smallest rectangle that completely encloses all of the pixels assigned to the blob. As additional pixels are added by the bottom-to-top module, the bounding box is continually updated to reflect the new boundaries after the additional pixels are added.

Like the scan table entries, the temporary blob ID may maintain information on the color value of the blob. This information may include the color sums sum Y 755, sum Cb 760 and sum Cr 765, for example. Finally, like the scan table entries, the temporary blob ID entries store a pixel count 770, and variance data 775. The temporary blob ID entry also identifies and later assigns a blob ID 780 to track the blob.

Each temporary blob ID entry is initialized with the following values: <ol id="ol0001" compact="compact" ol-style=""><li>(i) max_x and max_y are set to -1 (no max position),</li><li>(ii) min_x is set to image width + 1 (no min)</li><li>(iii) min_y is set to image height + 1 (no min)</li></ol> Count, var, sum Y, sum Cb, and Sum Cr, are all initialized to zero. The blob IDs are assigned in sequential order from a blob ID stack.

When the bottom-to-top module first encounters a new blob, it assigns a temporary ID to that new blob. The temporary ID is taken from a blob ID stack table that maintains the list of temporary IDs in use. The structure of the blob ID stack table is shown in <figref idref="f0008">Figure 8</figref>. The blob ID stack table can hold up to 256 temporary blob ID entries. One entry, such as the first entry, for example, is reserved for the background plane. The main purpose of the blob ID stack table is to recycle the temporary blob IDs. As soon as one blob is finished, it is outputted to a down stream process and the temporary ID associated with this blob is freed up and made available for reallocation to a new blob through the blob ID stack mechanism.

When the bottom-to-top module 620 determines that the blob is complete, i.e., is enclosed by a continuous boundary and no more additional pixels will be added, the bottom-to-top module 620 will output the contents of the temporary blob ID to the Global Table of Blobs (GTB). The bottom-to-top module 620 also incrementally updates the blob ID image to refer to the new blob identifiers, rather than those used in the local scan table. The updated blob ID image and the GTB are then output for further processing by the blob cluster processing module 700.

The bottom-to-top module 620 may perform essentially four steps on the scan table and blob ID image inputs: <ol id="ol0002" compact="compact" ol-style=""><li>1) Translate the scan table entries to temporary blob IDs in a translation table using the previous translation table on the line below.</li><li>2) A second pass on the translation table content may be performed if one or more entries is discovered to contain a terminal xlink value not pointing to itself in a circular manner.</li><li>3) Update the blob ID image to temporary blob table content to reflect additional pixels on the current scanline associated with these temporary blob entries.</li><li>4) Export to the GTB any closed temporary blob IDs and free up the resources allocated to a closed blob and make it available for allocation to a new temporary blob as needed.</li></ol>

The flow of data within the bottom-to-top module 620 is illustrated by <figref idref="f0010">Fig. 10</figref>. As shown in <figref idref="f0010">Fig. 10</figref>, the scan table entries for the current line are input by the Scan Table Translator 670. The Scan Table Translator 670 translates the scan table entries to temporary blob IDs using the previous translate table of the line below. The blob ID image and enhanced color image ENH is input to the Blob Content Updater 675, which updates the temporary blob table information and blob BID image for all scan table entries on the current line. The GTB generator 680 then determines if any blobs can be closed, and if so, closes the blobs by outputting the blob information to the GTB. The closed blob information is appended to the current GTB, and the current temporary blob ID is replaced by the next available GTB entry in sequential order. Each of these steps will be described in detail below.

Upon receiving the current scan table from the top-to-bottom module 610, and preserving the previous translate table of the line below, the bottom-to-top module 620 evaluates each entry in the current scan table from 1 to 255, to check if it has a valid (non-zero) xlink field.

At this time the bottom-to-top module 620 has already processed the previous scan table of the line below because the module progresses upward. Therefore, the previous scan table entries have already been translated to temporary blob ids, and the same ids will be carried over to the current line when vertically linked. Since the very first scan line (the bottom line of the image) has no previous scan lines to which it can be linked, all ylink values for this first scanline are zero, and each valid blob entry in the first scan line is given an initial temporary blob ID. As this process continues one line at a time from the bottom upward, it "unravels" the vertical ylink connections and re-assigns unique temporary blob ids that are consistent from one line to the next.

The bottom-to-top module 620 maintains the assignment of temporary blob IDs by means of a translate table. The bottom-to-top module 620 uses two translate tables, one for the current line and one to maintain the previous translate table from the line below. <figref idref="f0014">Fig. 14</figref> shows the structure of the two translate tables. The two translate tables are alternated every line. At the end of the current line, the current translate table becomes the previous translate table for the next line, and the translate table on the line below, since no longer needed, is destroyed by being overwritten by the next line translate table data.

<figref idref="f0014">Fig. 14</figref> illustrates one example of a valid blob entry 27 in the scan table for the line below, which is vertically linked to a valid blob entry 21 in the current line scan table. As the line below was processed by the bottom-to-top module 620, the scan table entry 27 was translated to be assigned the temporary ID 33, for example. Since the current line entry 21 is vertically linked to 27 on the line below, the temporary ID 33 is copied and assigned to entry 21 in the translate table of the current line. This indicates that the two seemingly unrelated scan table entries belong to the same temporary blob, and thus are assigned the same temporary blob ID 33.

All subsequent scan lines which refer, via the ylink fields to a blob on an earlier scan line, will share the temporary blob ID from the blob on the earlier scan line. Therefore, the action of the bottom-to-top module is to establish the vertical associations between the identified blobs, transforming the essentially one-dimensional blobs from the scan tables into two-dimensional blobs listed in the temporary table of blobs.

The current blob entry in the scan table is considered to be valid when the xlink field is non-zero. Otherwise, if xlink = 0, it indicates that the current blob is linked to the background plane (id = 0).

For each valid blob entry, the ylink field is examined. If the ylink is non-zero, the current blob is vertically linked to another blob on the line below. The ylink is followed to the previous translate table for the line below, and the temporary blob ID content is retrieved and copied to the current line translate table blob entry.

However, if, on the other hand, the current blob does not have a vertical link (e.g., ylink = 0) to any previous blobs, then it may be a new blob that is encountered for the first time. A check is first made to see if the current scan table entry is horizontally linked to any other scan table entry on the current line. A valid blob not horizontally linked to any other blob has an xlink value pointing back to its own blob entry as implied by the circular xlink list. If the current blob is determined to be horizontally linked to other blobs, the corresponding blob entry is set to zero in the translate table, and a flag "HasTerminalX" is turned on, to indicate this condition occurred. In a subsequent step, the bottom-to-top module 620 may further examine such horizontally-linked translate table blob entries to determine whether to assign new temporary blob ID to them or not.

If the current blob is valid, has a zero ylink, and has an xlink value that points back to itself in a circular manner, then it may considered to be a valid new blob encountered for the first time. The next available temporary ID is assigned to it from the ID Stack, and is inserted in the current translate table to indicate that the current scan table entry is now associated with this new temporary ID. At the same time, the ID Stack counter will be decremented by one, now pointing to the next available free temporary ID. The current temporary ID will remain in use until freed by the GTB generator 680, as will be described below. The bottom-to-top module 620 maintains the temporary blob ID and updates the temporary blob information as it continues to assign scan table entries to temporary blobs.

Finally, if the current blob xlink field is zero, then it is considered to be linked to the background plane. The corresponding translate table entry is set to zero.

After the scan table translation process completed a first pass through the scan table entries to create an initial translate table, a second pass may be performed if the "HasTerminalX" flag is turned on, indicating that at least one blob was determined to be horizontally linked to another blob on the current line. In this second pass, only blob entries in the translate table which were previously set to zero are examined. For each such blob entry in the current translate table, the xlink and ylink values are again retrieved from the current scan table. If ylink=0, and xlink is nonzero, a new temporary ID is obtained from the ID stack as described above, and is assigned to the current entry in the translate table. In addition, the xlink field is followed to the next horizontally linked blob entry, if any, and the corresponding translate table entry for this blob is also assigned the same new temporary ID number. This process repeats through all the horizontally linked blobs, until it reaches a next xlink value that points back to the very first starting blob ID. This process ensures that the entire chain of horizontally linked blobs is consistently assigned the same new temporary ID number.

When the scan table translator 670 completes its task with up to 2 passes per line, all valid blobs in the current scan table will have valid temporary blob ID numbers in the translate table entries. These values are referred to as the temporary blob ID numbers, since they will be used only until the blob is closed and exported to the GTB by the GTB generator 680.

Returning to the example illustrated by <figref idref="f0005">Fig. 5</figref>, for the example line shown in the figure, the fourth scan table entry is shown in <figref idref="f0007">Fig. 7</figref>. The xlink field is valid (4.xlink &gt;0) and is vertically connected to blob 3 on the line below. When the ylink field is followed down to the scan table on the line below, it is found that 3.ylink = 1, that is, temporary blob id #1 in the first (bottom) line of the blob is vertically linked to scan table blob ID #3. The new ylink value of 1 is copied to the current translate table entry of the current blob id #4 in the scan table, so that now 4.ylink = I (temporary ID). Since the two scan table blobs in this example are vertically linked, the temporary blob ID assignment from the translate table of the line below is copied into the current translate table entry. By extending this process upward, the first temporary blob ID associated with this group of pixels forming a blob (as allocated to the bottom most scan table blob) will be propagated upwards and be the same for all of the vertically connected blobs.

<figref idref="f0011">Fig. 11</figref> illustrates the before and after values of the translate table for the example shown in <figref idref="f0005">Fig. 5</figref>. As can be seen by comparing the before and after values, the effect is that the temporary blob ID (#1) associated with the link on the line below, as indicated in the translate table of the line below, is inserted as the current translate table entry. This process will repeat itself for all vertically connected blobs on the lines above, thereby assigning the same temporary ID to all of them in their corresponding translate tables.

Therefore, the task of the bottom-to-top module 620 is to create two-dimensional blobs from the essentially one-dimensional scan table information generated by the top-to-bottom module 610, by linking the one-dimensional blobs together either vertically or horizontally using the translate table entries. The two-dimensional blobs are each identified by the temporary blob ID which is the temporary list of two dimensional blobs being assembled by the bottom-to-top module 620. Each time a new blob is encountered on a scan line, which is not already linked vertically, it is given a new temporary blob ID. If it is a new blob that is horizontally linked to other blobs on the current line, the same new temporary blob ID is consistently assigned to all such horizontally linked blobs. As this ID is referred to by subsequent scan lines, the new pixels are associated with the same temporary blob ID..

The blob content updater 675 process begins after the scan table translation 670 has finished processing the current line. The blob content updater 675 maintains a blob structure with multiple fields for each temporary blob ID. At the end of each line, the blob content updater 675 updates the blob structures for each active temporary blob ID to include the information of new pixels from the current line associated with each open ID. For each valid blob entry in the current scan table, the blob content updater 675 looks up the translate table to determine the corresponding temporary blob ID number. The blob content updater 675 then updates the various fields associated with the particular temporary blob ID entry in the blob table.

The blob content updater 675 then scans the BID image from left to right (in raster order), for the current scan line, one pixel at a time. For each pixel, the initial BID value indicates the local scan table blob ID associated with the current pixel. This scan table ID entry is looked up in the current scan table (for the current line), and is followed to the corresponding temporary blob ID by looking up the current translate table entry.

The blob structure entries corresponding to the temporary blob ID are updated to include any new pixels associated with this temporary blob ID on the current line. Specifically, the fields in the temporary blob table entry are updated as follows: <ol id="ol0003" compact="compact" ol-style=""><li>(i) min_y is set to the current line (if line number &lt; min_y)</li><li>(ii) max_y is set to the current line (if line number &gt; max_y)</li><li>(iii) min_x is set to the current pixel (if pixel &lt; min_x)</li><li>(iv) max_x is set to the current pixel (if pixel &gt; max_x)</li><li>(v) The number of pixels in the local scan table blob is added to count</li><li>(vi) The variance in the local scan table blob is added to var</li><li>(vii) The color sums in the local scan table blob are added to sum Y, sum Cb, sum Cr, respectively.</li></ol> This effectively adds the content of the pixels associated with this local scan table blob to the corresponding temporary blob fields, and updates the temporary blob bounding-box with respect to the current pixel location.

To prevent overflow of the YCC sum fields (sum Y, sum Cb, sum Cr) of each valid (non-background) blob entry in the temporary blob table, these fields may be re-normalized each time the value of any one of them becomes too large. This can be accomplished by dividing the YCC sum fields by 2 and also dividing the count number of pixels by 2, such as to maintain the same ratio.

Finally, the blob content updater 675 updates the blob ID of the current pixel to point to the temporary blob (that has just been updated) instead of the original local scan table blob. This process updates the BID image to refer to the temporary blob ID numbers instead of the original scan table blob segments. <figref idref="f0012">Fig. 12</figref> is the blob ID image from <figref idref="f0004">Fig. 4</figref>, wherein the blob ID for all pixels in the blob forming the letter "A" have been substituted with the temporary blob ID #1 from the temporary blob ID table, according to the temporary blob ID information of each of the scan lines which constitute a portion of the letter "A". The min_x, max_x, min_y, and max_y are the coordinates of the bounding box surrounding blob #1 as shown in the <figref idref="f0012">Fig. 12</figref>. Blob #1 can now be closed, because the next line up contains no further pixels associated with blob #1.

The temporary blob ID is kept in effect until a determination is made that the temporary blob can be "closed", that is, that no more pixels on a current scan line are associated with the temporary blob. A temporary blob ID can be closed if (1) the blob does not reach the current scan line (min_y &gt; current line); and (2) the blob has a non-zero count (total number of pixels). In addition, if the current line is the last scan line (line = 0), then the blobs are closed because there are no more lines to process. Since the bottom-to-top module 620 works from the bottom of the page to the top, the last scan line is the first line of the image.

For each blob that meets the above conditions, the GTB generator 680 may normalize the temporary blob information by dividing the YCC sums by the count, etc. As the blob entry is exported to the final GTB, blob information content is appended to the GTB, and the temporary blob ID is replaced by the next available ID from GTB (the final blob ID assignment). Thereafter, the temporary blob entry and associated information are removed from the temporary blob table. The export process may include the following steps: <ol id="ol0004" compact="compact" ol-style=""><li>1) Divide the three temporary blob color sums (sum Y/Cb/Cr) by the blob pixel count, and round the result to the next integer value. This operation produces the average blob color. To avoid time consuming operations, the division may be implemented using a lookup table multiply and shift-right operation.</li><li>2) Check to make sure there is room for more blobs in the GTB. If there is no space, allocate a new GTB that can hold twice as many blobs, copy the old table content to the new table, and then delete old table. Use the new GTB from this point on. This step may be necessary as the GTB size is variable based on page content and the number of blobs is not known in advance. Step 2 allows the GTB size to dynamically grow (by powers of 2 in this example) as GTB is created.</li><li>3) Add a new blob to the GTB by incrementing the GTB count by 1.</li><li>4) Copy the content of all fields of the temporary blob entry from the temporary blob table to the GTB under the latest new entry.</li></ol> When the closed blob is exported to the GTB. it is assigned a new sequential blob id number in the GTB. Unlike the temporary blob table that is limited to 256 entries at most, the blob number in GTB is not restricted and may contain thousands of blobs for a complex page.

After the content of the current temporary blob is entered into the GTB, the temporary blob may be removed from the temporary blob table. The removal process may include the reset of the various blob fields to their default (initial) values. After initialization, the current temporary blob ID is pushed back onto the temporary blob ID Stack. This causes the temporary blob ID to be added as the last stack entry and the stack counter to be incremented by one. As a result, the blob ID is available for re-use. If no additional blob IDs are freed before a new blob is found, the blob ID may be immediately re-allocated to a newly found blob.

Thus, the closed temporary blob is transferred to the GTB, by copying the contents of the associated temporary blob entry. The GTB stores the final list of blobs, as determined by the blob identifying module 600, along with the associated blob information for each blob in the GTB.

The GTB and blob ID image BID are subsequently used by the blob cluster processing module 700, which clusters the blobs in the GTB according to color similarity and spatial overlap. The clusters are then assigned to the binary foreground planes, which may then be output to the compress module 800, and wrapped into a PDF file for further manipulation.

Although the previous description was given with reference to a hardware embodiment, the blob clustering process can also be implemented as software executing on a microprocessor. In this case, each of the steps of the method is carried out by a suitably programmed microprocessor, or by a combination of hardware and software.

<figref idref="f0013">Fig. 13</figref> is a flowchart outlining an exemplary method for linking blobs identified in a line scan device. The method begins in step S 100, wherein a first or next scan line is selected. The process proceeds to step S200, wherein the scan table is translated. The process then proceeds to step S300, wherein a determination is made whether Has TerminalX been set to 1. If so, the process proceeds to step S400, wherein a new ID is assigned to all horizontally linked blobs. If not, the process proceeds to step S500, wherein a determination is made whether xlink is greater than zero. If so, the process proceeds to step S600. In step S600, the ylink field of the scan table is retrieved, and followed to the previous line. The process proceeds to step S700, wherein the ylink of intervening lines are followed until the bottom line is reached, wherefrom the temporary blob ID is retrieved. The process proceeds to step S800, wherein the blob ID image is substituted with the temporary blob ID in place of the scan table blob ID. The process proceeds to step S900, wherein the temporary blob ID entry is updated to reflect the additional pixels added to the blob from the current scan line. In step S1000, the temporary blob table is evaluated to see if any blobs can be closed. If so, the temporary blob ID entries are normalized by dividing their color sums by the pixel count, in step S 1100. The process continues to step S 1200, wherein the temporary blob entry is copied to the GTB. In step S 1300, the temporary blob ID is initialized and returned to the temporary blob ID table, for further use. The process proceeds to step S 1400, wherein a determination is made whether the present scan line is the last scan line. If not, the process jumps back to step S 100. If so, the process ends.

<figref idref="f0015">Fig. 15</figref> is a flowchart outlining further detail of step S200 of <figref idref="f0013">Fig. 13</figref>. The process begins in step S210, in which the flag "HasTerminalX" is set to zero. The process then proceeds to step S215, wherein the next blob entry in the scan table is selected. In step S220, a determination is made whether xlink equals zero. If so, the process proceeds to step S240, wherein the current translate table is set to zero. If not, in step S225 a determination is made whether ylink equals zero. If not, the current entry from the translate table of the line below is copied into the ylink field. If ylink does equal zero in step S225, then a determination is made in step S230 whether xlink equals the current blob entry. If not, the process proceeds to step S250, wherein the current translate table is set to zero, and HasTerminalX is set to one. If xlink does equal the current blob table entry in step S230, then a new ID is assigned in step S235. The process proceeds to step S255, wherein a determination is made whether the entry is the last blob entry in the scan table. If not, the process jumps back to step S215. If so, the process ends in step S260.

<figref idref="f0016">Fig. 16</figref> is a flowchart outlining further detail of step S100 of <figref idref="f0013">Fig. 13</figref>. The process begins in step S110, wherein the next scan table entry is selected. The process proceeds to step S115, wherein xlink and ylink are looked up in the scan table. In step S120, a determination is made whether xlink equals zero. If not, the process proceeds to step S125, wherein a determination is made whether ylink equals zero. If so, the process proceeds to step S130, wherein a determination is made whether the translate table entry equals zero. If so, a new ID is assigned from the ID stack. The process then proceeds to step S140, wherein xlink is followed to the next blob entry. In step S145, the same new ID is assigned to the blob entry. In step S150, a determination is made whether the last xlink has been evaluated. If not, the process jumps to step S 140, wherein the xlink is followed to the next blob entry. If so, the process proceeds to step S155, wherein a determination is made whether the last scan table entry has been evaluated. If not, the process jumps to step S110, wherein the next scan table entry is selected. If the last scan table entry has been evaluated, the process ends in step S160.