Electronic image compression method and apparatus using interlocking digitate geometric sub-areas to improve the quality of reconstructed images

• US 5,093,872 A
• Filed: 05/02/1989
• Issued: 03/03/1992
• Est. Priority Date: 11/09/1987
• Status: Expired due to Term

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: Interand Corporation
• Inventors: Tutt, Timothy T.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/349,959
• Time in Patent Office: 1,036 Days
• Field of Search: 382/56, 382/54, 382/50, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/427, 358/432, 358/433, 358/470
• US Class Current: 382/243
• 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
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals

Abstract

A method and apparatus for compressing digital image data using interlocking digitate geometric sub-areas. The digital picture elements, or PELs, representing the image are divided into interlocking digitate sub-areas, which, in the preferred embodiment, are of substantially the same size and shape. Data compression is achieved for the PELs within a sub-area by first sorting the values of the PELs within the sub-area by magnitude. Depending upon the magnitudes of the PELs in the sub-area relative to the magnitudes of the other PELs in the sub-area, the PELs in the sub-area are either coded solid tone, with each PEL in the sub-area having the same tone, or coded bi-tonal, with each PEL in the sub-area having either one of two tones. A smoothing process is utilized to reduce undesireable effects at the edges of the sub-area.

Claims

1. In an image processing system wherein images are represented by grey scale image data consisting of a collection of digital picture elements, a method of compressing the image data comprising the steps of:

dividing the image data into interlocking subareas containing a plurality of picture elements, wherein the interlocking subareas are of substantially uniform size and shape and interlock with each adjacent subarea; and

coding each of the picture elements of each interlocking subarea with a digital value, where the coding comprises sorting the values of the picture elements in each subarea, and wherein the digital value coded for a particular picture element is dependent upon the magnitudes of the picture elements of the interlocking subarea containing the particular picture element.

2. The method as claimed in claim 1 where the step of sorting comprises sorting the values of the picture elements contained in each interlocking subarea into an array ordered by relative magnitude of the picture elements within the interlocking subarea, wherein the digital value coded for a particular picture element is dependent upon the magnitudes of the values of the picture elements in the array.

3. The method as claimed in claim 1 further comprising the step of modifying one or more of the digital values coded for the picture elements contained within one or more of the interlocking subareas, wherein the value of a particular modified digital value for a picture element contained within a particular interlocking subarea is dependent upon the coded digital values of the picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea.

4. The method as claimed in claim 3 wherein the modified digital values coded for the picture elements contained within one or more of the interlocking subareas are equal to the sum of two times the assigned value of the picture element plus the values of two picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea, divided by four.

5. The method as claimed in claim 1 wherein the interlocking subareas are substantially in the shape of a cross.

6. The method as claimed in claim 1 wherein substantially all of the interlocking subareas contain twelve picture elements.

7. The method as claimed in claim 1 wherein the interlocking subareas are substantially in the shape of a cross and wherein substantially all of the interlocking subareas contain twelve picture elements.

8. The method as claimed in claim 1 wherein the step of coding each of the picture elements of each interlocking subarea with a digital value comprises the steps of:

sorting the values of the picture elements contained in each interlocking subarea into an array ordered by relative magnitude of the picture elements within the interlocking subarea;

determining the minimum value of the picture elements in the ordered array for each interlocking subarea;

determining the maximum value of the picture elements in the ordered array for each interlocking subarea;

comparing the difference between the maximum value and minimum value of the picture elements in the ordered array to a first predetermined constant value;

coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the difference between the maximum value and minimum value of the picture elements in the ordered array is less than or equal to the first predetermined constant value;

performing the following steps for each interlocking subarea in which the difference between the maximum value and minimum value of the picture elements in the ordered array is greater than the first predetermined constant value;

determining the mean of the maximum value and the minimum value of the picture elements in the ordered array;

sorting the values of the picture elements in the ordered array into an upper array segment and a lower array segment, wherein the values of the picture elements in the upper array segment are greater than or equal to the mean of the maximum value and the minimum value of the picture elements in the ordered array and the values of the picture elements in the lower array segment are less than the mean of the maximum value and the minimum value of the picture elements in the ordered array;

determining the median value of the values in the upper array segment and the median value of the values in the lower array segment;

comparing the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment to a second predetermined constant value;

coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the diffference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is less than or equal to the second predetermined constant value; and

coding each picture element within the interlocking subarea with one of two digital values for each interlocking subarea in which the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is greater than the second predetermined constant value.

9. In an image processing system wherein images are represented by grey scale image data consisting of a collection of digital picture elements, an apparatus for compressing the image data, comprising:

means for dividing the image data into interlocking subareas containing a plurality of picture elements, wherein the interlocking subareas are of substantially uniform size and shape and interlock with each adjacent subarea; and

means for coding each of the picture elements of each interlocking subarea with a digital value, where the coding means comprises sorting means for sorting the values of the picture elements in each subarea, and wherein the digital value coded for a particular picture element is dependent upon the magnitudes of the picture elements of the interlocking subarea containing the particular picture element.

10. The apparatus as claimed in claim 9 where the means for sorting comprises sorting means for sorting the values of the picture elements contained in each interlocking subarea into an array ordered by relative magnitude of the picture elements within the interlocking subarea, wherein the digital value coded for a particular picture element is dependent upon the magnitudes of the values of the picture elements in the array.

11. The apparatus as claimed in claim 9 further comprising means for modifying one or more of the digital values coded for the picture elements contained within one or more of the interlocking subareas, wherein the value of a particular modified digital value for a picture element contained within a particular interlocking subarea is dependent upon the coded digital values of the picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea.

12. The apparatus as claimed in claim 11 wherein the modified digital values coded for the picture elements contained within one or more of the interlocking subareas are equal to the sum of two times the assigned value of the picture element plus the values of two picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea, divided by four.

13. The apparatus as claimed in claim 9 wherein the interlocking subareas are substantially in the shape of a cross.

14. The apparatus as claimed in claim 9 wherein substantially all of the interlocking subareas contain twelve picture elements.

15. The apparatus as claimed in claim 9 wherein the interlocking subareas are substantially in the shape of a cross and wherein substantially all of the interlocking subareas contain twelve picture elements.

16. The apparatus of claim 9 wherein the means for coding each of the picture elements of each interlocking subarea with a digital value comprises:

means for sorting the values of the picture elements contained in each interlocking subarea into an array ordered by relative magnitude of the picture elements within the interlocking subarea;

means for determining the minimum value of the picture elements in the ordered array for each interlocking subarea;

means for determining the maximum value of the picture elements in the ordered array for each interlocking subarea;

means for comparing the difference between the maximum value and minimum value of the picture elements in the ordered array to a first predetermined constant value;

means for coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the difference between the maximum value and minimum value of the picture elements in the ordered array is less than or equal to the first predetermined constant value;

means for determining the mean of the maximum value and the minimum value of the picture elements in the ordered array;

means for sorting the values of the picture elements in the ordered array into an upper array segment and a lower array segment, wherein the values of the picture elements in the upper array segment are greater than or equal to the mean of the maximum value and the minimum value of the picture elements in the ordered array and the values of the picture elements in the lower array segment are less than the mean of the maximum value and the minimum value of the picture elements in the ordered array;

means for determining the median value of the values in the upper array segment and the median value of the values in the lower array segment;

means for comparing the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment to a second predetermined constant value;

means for coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is less than or equal to the second predetermined constant value; and

means for coding each picture element within the interlocking subarea with one of two digital values for each interlocking subarea in which the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is greater than the second predetermined constant value.

17. In an image processing system wherein images are represented by image data consisting of a collection of digital picture elements, a method of compressing the image data comprising the steps of:

dividing the image data into interlocking subareas containing a plurality of picture elements, wherein the interlocking subareas are of substantially uniform size and shape;

sorting the values of the picture elements contained in each interlocking subarea into an array ordered by relative magnitude of the picture elements within the interlocking subarea;

determining the minimum value of the picture elements in the ordered array for each interlocking subarea;

determining the maximum value of the picture elements in the ordered array for each interlocking subarea;

comparing the difference between the maximum value and minimum value of the picture elements in the ordered array to a first predetermined constant value;

coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the difference between the maximum value and minimum value of the picture elements in the ordered array is less than or equal to the first predetermined constant value;

performing the following steps for each interlocking subarea in which the difference between the maximum value and minimum value of the picture elements in the ordered array is greater than the first predetermined constant value;

determining the mean of the maximum value and the minimum value of the picture elements in the ordered array;

sorting the values of the picture elements in the ordered array into an upper array segment and a lower array segment, wherein the values of the picture elements in the upper array segment are greater than or equal to the mean of the maximum value and the minimum value of the picture elements in the ordered array and the values of the picture elements in the lower array segment are less than the mean of the maximum value and the minimum value of the picture elements in the ordered array;

determining the median value of the values in the upper array segment and the median value of the values in the lower array segment;

comparing the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment to a second predetermined constant value;

coding each picture element within the interlocking subarea with the same digital value for each interlocking subarea in which the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is less than or equal to the second predetermined constant value; and

coding each picture element within the interlocking subarea with one of two digital values for each interlocking subarea in which the difference between the median value of the values in the upper array segment and the median value of the values in the lower array segment is greater than the second predetermined constant value.

18. The method as claimed in claim 17 wherein the interlocking subareas are substantially in the shape of a cross.

19. The method as claimed in claim 17 wherein substantially all of the interlocking subareas contain twelve picture elements.

20. The method as claimed in claim 17 wherein the interlocking subareas are substantially in the shape of a cross and wherein substantially all of the interlocking subareas contain twelve picture elements.

21. The method as claimed in claim 17 further comprising the step of modifying one or more of the digital values coded for the picture elements contained within one or more of the interlocking subareas, wherein the value of a particular modified digital value for a picture element contained within a particular interlocking subarea is dependent upon the coded digital values of the picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea.

22. The method as claimed in claim 17 wherein the modified digital values coded for the picture elements contained within one or more of the interlocking subareas are equal to the sum of two times the assigned value of the picture element plus the values of two picture elements within one or more of the interlocking subareas in proximity to the particular interlocking subarea, divided by four.