Fast image decoder

• US 5,414,804 A
• Filed: 07/28/1992
• Issued: 05/09/1995
• Est. Priority Date: 10/16/1989
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: McWaid, Janet
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/921,424
• Time in Patent Office: 1,015 Days
• Field of Search: 382/43, 382/49, 382/54, 382/56, 382/45, 382/46, 340/747, 340/750, 395/129, 395/132, 395/133, 395/139, 345/133, 345/138
• US Class Current: 382/245
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

A fast image decoder 20 for decoding a compressed image encoded using the Poisson picture processing algorithm is disclosed. The invention includes a run length decoder 23 for run length decoding the compressed image, a processing circuit including a lookup table 24 for iteratively processing each pixel output by the run length decoder 23, a frame memory 26 for storing the reconstructed image and a feedback path 28 for providing image data from the frame memory 26 to the lookup table 24 for successive processing iterations. The reconstructed image from the frame memory 26 may be viewed on a display or further processed as required by the specific application.

Claims

1. A fast image decoder for producing a reconstructed image from compressed images encoded using the Poisson picture processing algorithm, said fast image decoder comprising:

run length decoder means for run length decoding said compressed image to form a sparse array of pixel values;

processing means coupled to said run length decoder means for receiving said sparse array of pixels and for iteratively processing pixels to produce said reconstructed image; and

frame memory means coupled to said processing means for receiving said reconstructed image and for successively storing said reconstructed image and feeding back pixels for said reconstructed image to said processing means for successive processing iterations, said processing means for iteratively receiving and processing pixels for said successive reconstructed images to increase the quality of said reconstructed image.

2. The invention of claim 1 wherein said run length decoder means is a special purpose integrated circuit for performing run length decoding.

3. The invention of claim 1 wherein said run length decoder means is a run length decoder implemented in software.

4. The invention of claim 1 wherein said processing means includes lookup table means for outputting a first value that is the value of the pixel of said sparse array when the value of said pixel is non-zero and outputting a second value that is the result of the sum of the pixels on the top, bottom, left and right sides of the pixel being processed divided by a multiplier value and then subtracting the value of the pixel being processed when the value of said pixel is zero in the sparse array.

5. The invention of claim 4 wherein said lookup table means is an image processing lookup table circuit.

6. The invention of claim 4 wherein said processing means further includes means for multiplying said second value by an overrelaxation constant to reduce said number of iterations necessary to produce a final version of said reconstructed image.

7. The invention of claim 4 wherein said lookup table means includes bit mask means for masking from processing said pixels of said sparse array with non-zero values.

8. The invention of claim 4 wherein said multiplier value corresponds to the multiplier value used in encoding said compressed image using said Poisson picture processing algorithm.

9. A video system comprising:

digitizing means for digitizing an image;

Poisson encoding means for encoding said image to produce a compressed image;

transmitter means for transmitting said compressed image in said video system;

fast image decoder means for producing a reconstructed image including

(a) run length decoder means for run length decoding said compressed image to form a sparse array of pixel values,

(b) processing means coupled to said run length decoder means for receiving said sparse array of pixels and for iteratively processing pixels to produce said reconstructed image, and

(c) frame memory means coupled to said processing means for receiving said reconstructed image and for successively storing said reconstructed image and feeding back pixels for said reconstructed image to said processing means for successive processing iterations, said processing means for iteratively receiving and processing pixels for said successive reconstructed images to increase the quality of said reconstructed image; and

display means for displaying said reconstructed image.

10. The invention of claim 9 including:

run length decoder means for run length decoding said compressed image to form a sparse array of image values;

processing means for iteratively processing each pixel of said sparse array to produce said reconstructed image; and

frame memory means for storing said reconstructed image and providing a feedback path to said processing means for successive processing iterations.

11. A method for decoding a compressed image encoded using the Poisson picture processing algorithm including the steps of:

a) run length decoding said compressed image to form a sparse array;

b) loading a lookup table with the value of a pixel from said sparse array, the values of the pixels on the top, bottom, right and left sides of said pixel and with a multiplier value;

c) masking said pixel from processing if the value of said pixel is non-zero;

d) outputting the value of said pixel if said pixel is non-zero pixel or;

e) if the value of said pixel is zero, outputting the result of the sum of the values of the pixels on the top, bottom, left and right sides of said pixel divided by said multiplier and then subtracting said pixel value;

f) after step e) above, storing said result in a frame memory; and

g) after step f) above, feeding said result back to said lookup table for successive processing iterations until the desired quality of image is increased.

12. A fast image decoder for producing a reconstructed image from an image compressed using the Poisson picture algorithm comprising:

processing means for iteratively processing said compressed image, and a lookup table means for outputting a first pixel value that is the value of the pixel of a sparse array of pixel values when the value of said pixel is non-zero and outputting a second pixel value that is the result of the sum of the pixels on the top, bottom, left and right sides of the pixel being processed divided by a multiplier value and then subtracting the value of the pixel being processed when the value of said pixel is zero in the sparse array, whereby said second pixel values are iteratively processed and fed back to said processing means for further processing to increase the quality of the reconstructed image.

13. The invention of claim 12 wherein said processing means further includes means for multiplying said second value by an overrelaxation constant to reduce said number of iterations necessary to produce a desired reconstructed image.

14. The invention of claim 12 wherein said lookup table means includes means for masking from processing pixels with non-zero values.

15. A fast iterative image decoder for producing a final reconstructed image from a compressed image, which compressed image has been compressed using the Poisson picture processing algorithm, said fast iterative image decoder comprising:

run-length decoder means for receiving said compressed image and run-length decoding said compressed image to provide a sparse array of pixel values;

processing means for receiving said sparse array of pixel values and for iteratively processing pixels of said sparse array to provide at least a first intermediate reconstructed image and said final reconstructed image;

frame memory means for successively storing said first intermediate reconstructed image and said final reconstructed image, as well as any successive intermediate images which lead from said first intermediate reconstructed image to said final reconstructed image by successive iterations of said processing means, said frame memory means feeding back pixel values from said sparse array to said processing means for successive iterative processing; and

means for selecting the number of iterations to be performed by said processing means leading successively from said first intermediate reconstructed image to said final reconstructed image.

16. The fast iterative image decoder of claim 15 wherein said processing means further includes look-up table means for iteratively outputting as a value for a pixel of said sparse array either a first value or a second value dependent upon whether said pixel has a non-zero value or a zero value, respectively.

17. The fast iterative image decoder of claim 16 wherein said look-up table means outputs the non-zero value of said pixel as said first value for said pixel.

18. The fast iterative image decoder of claim 16 wherein said look-up table means outputs said second value for said pixel when said pixel has a zero value, said second value being equal to the quotient of the sum of the pixel values above, below, left and right of said pixel in said sparse array, which sum is divided by a selected value.

19. The fast iterative image decoder of claim 18 wherein said selected value corresponds to a multiplier value used in said Poisson picture processing algorithm.

20. The fast iterative image decoder of claim 18 wherein said processing means further includes means for multiplying said second value by an over-relaxation constant to provide a third value which is output as the value for said pixel to reduce the number of iterations necessary to provide said final reconstructed image.

21. The fast iterative image decoder of claim 20 wherein said over-relaxation constant is selected to be greater than one (1).

22. The fast iterative image decoder of claim 21 wherein said over-relaxation constant is selected to be substantially 1.5.

23. The fast iterative image decoder of claim 15 wherein said iteration number selecting means selects six (6) as the number of iterations performed from said first intermediate reconstructed image to said final reconstructed image.

24. A fast iterative image decoding method for decoding a compressed image produced by the Poisson picture processing algorithm to provide a series of intermediate reconstructed images leading by successive iterations of said process to a final reconstructed image, said method comprising the steps of:

run-length decoding said compressed image to provide a sparse array of pixel values;

iteratively loading a look-up table with pixel values from said sparse array, and successively outputting from said look-up table a next-successive value for a corresponding particular one of said pixels;

said next-successive value being equal to the value of said particular pixel when said value is non-zero, said next-successive value for said particular pixel being equal to the quotient of the sum of pixel values immediately above, below, left and right of said particular pixel in said sparse array, which sum is divided by a selected value to provide said quotient;

masking pixels having non-zero values from processing; and

processing zero-valued pixels of said sparse array to successively provide a first intermediate reconstructed image, each of said succession of intermediate reconstructed images, and said final reconstructed image.

25. The fast iterative image decoder method of claim 24 further including the step of multiplying said next-successive value for a zero-valued pixel by an over-relaxation constant.

26. The fast iterative image decoder method of claim 25 further including the step of selecting said over-relaxation constant to be greater than one (1).

27. The fast iterative image decoder method of claim 26 further including the step of selecting said over-relaxation constant to be substantially equal to 1.5.

28. The fast iterative image decoder method of claim 24 further including the step of using as said selected value a value substantially equal to a multiplier value which is used in said Poisson picture processing algorithm.