PERCEPTUALLY LOSSLESS COLOR COMPRESSION

• US 20090067709A1
• Filed: 09/08/2008
• Published: 03/12/2009
• Est. Priority Date: 09/07/2007
• Status: Active Grant

• Current Assignee: Foxit Software, Inc.
• Original Assignee: Cvision Technologies Incorporated (Foxit Software, Inc.)
• Inventors: GROSS, Ari David, MEYERS, Raphael, TINNA, Navdeep
• Granted Patent: US 8,155,437 B2
• Time in Patent Office: Days
• US Class Current: 382/166
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 1/40062 Discrimination between different image types, e.g. two-tone, continuous tone
• CPC Class Codes: H04N 1/41 Bandwidth or redundancy reduction by scanning H04N1/17 ; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A system and method of color data compression may perform variations of MRC compression including taking into consideration means and/or variances within k×k cells of an image, background texture, background smoothed color, and gradient components for determination of which parts of an image belong to the background and foreground MRC layers, for calculating thresholds values for such determinations, and determining correctness of determined thresholds and polarity, and may determine the background and foreground layer colors based on the variances, the gradient components, and neighboring pixels of non-color-assigned pixels of the background and foreground layers.

Claims

1. A method of segmenting a mask layer of an image, comprising:

forming gradient components;

using grayscale values of pixels adjacent to maximal gradient points within the gradient components to obtain respective threshold values for the gradient components;

for each of the gradient components, using a respective one of said threshold values to threshold all pixels within a bounding box of the respective gradient component to form a respective thresholded component; and

adding one or more of the thresholded components or an inverse of the one or more of the thresholded components to the mask layer.

2. The method of claim 1, wherein the gradient components are formed by:

selectively computing a set of maximal gradient points;

selectively removing certain maximal gradient points;

grouping remaining connected maximal gradient points into gradient components; and

merging selected gradient components together.

3. The method of claim 2, wherein the gradient components are removed if they are labeled as noise based on their area, height, width, stroke thickness, and Euler number.

4. The method of claim 2, wherein the gradient components are divided into k by k cells, each of which is treated as a separate gradient component if the gradient components are labeled as line art based on their area, height, width, stroke thickness, and Euler number.

5. The method of claim 2, wherein the maximal gradient points are only calculated if found in a k by k cell with a grayscale variance above a certain threshold.

6. The method of claim 2, wherein the maximal gradient points are removed by smoothing and recomputing the maximal gradient points within a k by k cell when said cell contains a weighting of endpoints, singletons, k-junctions and gradient points which is above a certain threshold.

7. The method of claim 2, wherein maximal gradient points which are closer to a first weakest peak than to a second weakest peak are removed, the first weakest peak being weaker than the second weakest peak.

8. The method of claim 2, wherein the maximal gradient points remaining after the removal are formed into gradient components when they are connected.

9. The method of claim 8, wherein overlapping gradient components are merged into a new gradient component.

10. The method of claim 1, wherein, for each of the thresholded components, the thresholded component is added to the mask layer if it matches a corresponding one of the gradient components.

11. The method of claim 10, wherein, if a thresholded component does not match any one of the gradient components, the method further comprising:

inversing the thresholded component; and

determining whether the inversed component matches a corresponding one of the gradient components;

wherein, if a match is found for the inversed component, the inversed component is added to the mask layer.

12. The method of claim 10, wherein matching criteria for the match is based on a bidirectional Rank Hausdorff between a perimeter of the thresholded component and the gradient component.

13. The method of claim 1, wherein the threshold value is determined by creating a light array and a dark array and finding a value which maximizes a sum of a number of dark array pixels below said value plus a number of light array pixels equal to or above said value, where said arrays are formed by:

traversing in a gradient direction of each of the maximal gradient points in the gradient component and identifying the lighter side and the darker side based on the value of the immediately adjacent neighbors of the corresponding pixel in grayscale space; and

of grayscale values of two pixels on the lighter side, the two pixels including a first pixel immediately adjacent to the maximal gradient point and the second pixel following the first pixel in the gradient direction away from the maximal gradient point, placing the lighter of the two grayscale values into the light array; and

of grayscale values of two pixels on the darker side, the two pixels including a first pixel immediately adjacent to the maximal gradient point and the second pixel following the first pixel in the gradient direction away from the maximal gradient point, placing the darker of the two grayscale values into the dark array.

14. The method of claim 1, further comprising:

for each of a plurality of k by k cells;

dividing the cell into quadrants, dividing the cell into four vertical strips, and dividing the cell into four horizontal strips; and

for the cell as a whole, for each quadrant, and for each strip, calculating a respective mean color value and a respective variance value;

wherein the maximal gradient points are calculated for the cell conditional upon that the calculated values are not within a predetermined range of each other.