Method and apparatus for compressing and decompressing a video image

• US 5,790,269 A
• Filed: 12/12/1995
• Issued: 08/04/1998
• Est. Priority Date: 12/12/1995
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Masaki, Ichiro, Horn, Berthold, Desai, Ujjaval, Chandrakasan, Anantha
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): Grant, II, Jerome
• Application Number:
  US08/570,765
• Time in Patent Office: 966 Days
• Field of Search: 382/112, 382/113, 382/159, 382/175, 382/181, 382/184, 382/193, 382/194, 382/199, 382/201, 382/209, 382/217, 382/221, 382/252, 382/266, 382/267, 382/258, 358/447, 358/448, 358/470, 358/525, 358/530, 358/539, 358/426, 358/425, 395/101, 395/114, 395/121, 395/143
• US Class Current: 358/447
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: H04N 19/20 using video object coding

Abstract

Edge or contour information is extracted from an image array by filtering and encoded. In order to improve reproduction accuracy, two separate filters are used to detect edge information. One of the filters detects "sharp" edges, or edges in which the discontinuity in pixel intensity values occurs over a range of a few pixels. The other filter detects "level" edges in which the pixel intensity value discontinuity occurs over a larger range of pixels than the "sharp" edges. The "smooth" areas between edges or contours are assumed to vary continuously between the contours, but for efficient implementation, a one-dimensional linear interpolation is used to regenerate the contour information between edges. In addition, to further improve performance, a line is fitted to the pixel intensity data. The end values of this line are then used for the pixel intensity data. In order to still further improve performance, the pixel intensity values associated with each contour are divided into groups and each group is then encoded. Another improvement is accomplished by mean coding the residual error.

Claims

1. Apparatus for compressing a video image comprised of a row and column array of image pixel values the apparatus comprising:

means responsive to the image pixel values for identifying a plurality of edges in the video image, each of the plurality of edges being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values;

means responsive to the contour pixels for encoding a location in the array of image pixel values for each of the contour pixels;

means responsive to the plurality of contour pixels for generating an approximation of the image pixel values between two consecutive ones of the plurality of edges wherein the means for generating an approximation comprises;

means responsive to the contour pixels and operable in each row of the array of image pixel values for detecting the column locations of a pair of consecutive contour pixels located in the each row; and

means responsive to the column locations of the detected consecutive contour pixels for determining a first linear approximation of row image pixel values located in the each row between the column locations;

means for using the approximation to produce first and second contour data values representing two image pixel values adjacent to the two consecutive ones of the plurality of edges wherein the approximation using means comprises means for determining the first and second contour data values by inserting the column locations into the first linear approximation; and

means for encoding the first and second contour data values.

2. Apparatus for compressing a video image comprised of a row and column array of image pixel values, the apparatus comprising:

means responsive to the image pixel values for identifying a plurality of edges in the video image, each of the plurality of edges being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values;

means responsive to the contour pixels for encoding a location in the array of image pixel values for each of the contour pixels;

means responsive to the plurality of contour pixels for generating an approximation of the image pixel values between two consecutive ones of the plurality of edges;

means for using the approximation to produce first and second contour data values representing two image pixel values adjacent to the two consecutive ones of the plurality of edges;

means for encoding the first and second contour data values;

means responsive to the contour pixels and operable in each column of the array for detecting the row locations of a pair of consecutive contour pixels located in the each column;

means responsive to the row locations of the detected consecutive contour pixels for selecting column image pixel values located in the each column between the row locations;

means responsive to the selected column image pixel values for determining a second linear approximation of the selected column image pixel values;

means for determining a third and a fourth contour data values by inserting the row locations into the second linear approximation; and

means for encoding the third and fourth contour data values.

3. Apparatus for compressing a video image comprised of a row and column array of image pixel values, the apparatus comprising:

means responsive to the image pixel values for identifying a plurality of first edges in the image, each first edge being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values over a first number of image pixel values;

means responsive to the image pixel values for identifying a plurality of second edges in the image, each second edge being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values over a second number of image pixel values;

means for combining the first edges with the second edges to generate a composite edge intensity map;

means responsive to the composite edge intensity map for encoding a location in the array for each of the contour pixels;

means responsive to the contour pixels for determining two contour data values for each pixel; and

means for encoding the two contour data values.

4. Apparatus according to claim 3 wherein the second number of image pixel values is greater than the first number of image pixel values.

5. Apparatus according to claim 3 wherein the means for identifying a plurality of first edges generates a first edge intensity map, the means for identifying a plurality of second edges generates a second edge intensity map and the combining means averages the first edge intensity map with the second edge intensity map.

6. Apparatus according to claim 5 wherein combining means comprises means for weighting the first and second edge intensity maps.

7. A method for compressing a video image comprised of a row and column array of image pixel values, the method comprising the steps of:

A. identifying a plurality of edges in the image, each edge being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values;

B. encoding a location in the array for each of the contour pixels;

C. generating an approximation of the image pixel values between two consecutive ones of the plurality of edges;

D. using the approximation to produce a first and a second contour data values representing two image pixel values adjacent to the two consecutive ones of the plurality of edges; and

E. encoding the first and second contour data values.

8. The method of claim 7 further comprising the step of:

detecting the row locations of a pair of consecutive contour pixels located in the each column;

selecting column image pixel values located in the each column between the row s locations of the detected consecutive contour pixels;

determining a second linear approximation of the selected column image pixel values;

determining third and fourth contour data values by inserting the row locations into the second linear approximation; and

encoding the third and fourth contour data values.

9. The method of claim 7 wherein the step of generating an approximation comprises the steps of:

detecting the column locations of a pair of consecutive contour pixels located in each row;

determining a first linear approximation of row image pixel values located in the each row between the column locations of the detected consecutive contour pixels.

10. The method of claim 9 wherein the step of using the approximation comprises the step of determining the first and second contour data values by inserting the column locations into the first linear approximation.

11. A method for compressing a video image comprised of a row and column array of image pixel values, the method comprising the steps of:

A. identifying a plurality of first edges in the image, each first edge being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values over a first number of image pixel values;

B. identifying a plurality of second edges in the image, each second edge being comprised of a line of contour pixels at which a value discontinuity occurs in the array of image pixel values over a second number of image pixel values;

C. combining the first edges with the second edges to generate a composite edge intensity map;

D. encoding a location in the array for each of the contour pixels;

E. determining two contour data values for each pixel; and

F. encoding the two contour data values.

12. The method of claim 11 wherein the second number of image pixel values is greater than the first number of image pixel values.

13. The method of claim 11 wherein:

the step of identifying a plurality of first edges includes the step of generating a first edge intensity map;

the step of identifying a plurality of second edges includes the step of generating a s second edge intensity map; and

the step of combining the first edges with the second edges includes the step of averaging the first edge intensity map with the second edge intensity map.

14. The method of claim 13 wherein the step of combining includes the step of weighting the first and second edge intensity maps.