Image data processing of correlated images

• US 5,177,796 A
• Filed: 10/19/1990
• Issued: 01/05/1993
• Est. Priority Date: 10/19/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morgan, James H., Miller, Victor S., Feig, Ephraim
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/600,480
• Time in Patent Office: 809 Days
• Field of Search: 382/56, 358/433, 364/715.02
• US Class Current: 382/236
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]

Abstract

To encode data representative of correlated images, a sequence of arrays of source image data is provided in which each array is representative of an image. Each array of source image data is partitioned into a plurality of source image-data blocks. For each sequence of source image-data blocks, at least one prototypical image-data block is derived from at least a portion of the source image data of the sequence. For each source image-data block, a translation coefficient and a number of scaling coefficients equal to the number of prototypical image-data blocks associated with the sequence are determined. A difference image-data block is formed for each source image-data block from elements of the source image-data block minus the associated translation coefficient minus the sum in turn of each associated scaling coefficient multiplied by elements of the corresponding prototypical image-data block. Each difference image-data block is subjected to an image-data compression procedure to form a set of data-compression-encoded difference image-data elements. Each set of data-compression-encoded difference image-data elements may be stored in digital storage in association with the scaling coefficients and the translation coefficient associated with the corresponding source image-data block.

Claims

1. A method for encoding data representative of a sequence of images which includes correlated images, comprising:

(a) digitizing each image in the sequence of images to form a sequence of arrays of source image data, each array of source image data being representative of a corresponding one of the images of the sequence;

(b) partitioning each array of source image data into a plurality of source image-data blocks, each source image-data block having source image-data elements, each source image-data element of a block being indexably associated with a unique block data-element index, corresponding source image-data blocks associated in turn with each array of the sequence of arrays of source image data defining a sequence of source image-data blocks, the sequences of source image-data blocks so defined being equal in number to the number of source image-data blocks into which each array is partitioned;

(c) for each sequence of source image-data blocks, deriving at least one prototypical image-data block from at least a portion of the source image data of the sequence, each prototypical image-data block having prototypical image-data elements, each prototypical image-data element being indexably associated with one of the block data-element indices;

(d) for each source image-data block in each sequence of source image-data blocks, determining an associated translation coefficient and a number of associated scaling coefficients equal to the number of prototypical image-data blocks associated with the sequence, the scaling coefficients and the translation coefficient respectively having values to at least approximately minimize a first sum of squared summands, each summand being indexably associated with one of the block data-element indices and being the square in sum of the translation coefficient plus a second sum of each of the scaling coefficients in turn multiplied by an element indexably associated with the summand block data-element index of the prototypical image-data block associated with the scaling coefficient minus an element indexably associated with the summand block data-element index of the source image-data block, the first sum being taken over all of the block data-element indices of the source image-data block;

(e) for each source image-data block in each sequence of source image-data blocks, forming a corresponding difference image-data block having difference image-data elements, each difference image-data element being indexably associated with one of the block data-element indices which defines a difference-element index, each difference image-data element being derived from an element indexably associated with the difference-element index of the source image-data block minus the translation coefficient associated with the source image-data block minus the sum in turn of each scaling coefficient associated with the source image-data block multiplied by the element indexably associated with the difference-element index of the prototypical image-data block associated with the scaling coefficient;

(f) subjecting each difference image-data block to an image-data-compression procedure to form a set of data-compression-encoded difference image-data elements; and

(g) storing each set of data-compression-encoded difference image-data elements in digital storage in association with the scaling coefficients and the translation coefficient associated with the corresponding source image-data block.

2. The method of claim 1 further comprising:

(h) subjecting each prototypical image-data block to an image-data-compression procedure to form a set of data-compression-encoded prototypical image-data elements; and

(i) storing each set of data-compression-encoded prototypical image-data elements in digital storage.

3. The method of claim 2 in which each image block represented by a source image-data block is essentially rectangular.

4. The method of claim 1 in which each prototypical image-data block is obtained by averaging on a corresponding-element-by-corresponding-element basis elements of at least a subset of the source image-data blocks in the associated sequence of source image-data blocks.

5. The method of claim 1 in which each prototypical image-data block represents a source image-data block, the formation of difference image-data blocks being carried out sequentially in a telescoping fashion.

6. The method of claim 2 in which the image-data-compression procedure is a differential pulse-code modulation scheme with arithmetic coding.

7. The method of claim 2 in which the image-data compression procedure is a differential pulse-code modulation scheme with Huffman coding.

8. The method of claim 1 in which two prototypical image-data blocks are derived for each sequence of source image-data blocks.

9. The method of claim 1 in which a single prototypical image-data block is derived for each sequence of source image-data blocks.

10. The method of claim 3 in which each image block is essentially square having a size of 64 pixels by 64 pixels.

11. The method of claim 3 in which each image block is essentially square having a size of 128 pixels by 128 pixels.

12. A method for encoding data representative of a sequence of images which includes correlated images, comprising:

(a) digitizing each image in the sequence of images to form a sequence of arrays of source image data, each array of source image data being representative of a corresponding one of the images of the sequence;

(b) partitioning each array of source image data into a plurality of source image-data blocks, each source image-data block having source image-data elements, each source image-data element of a block being indexably associated with a unique block data-element index, corresponding source image-data blocks associated in turn with each array of the sequence of arrays of source image data defining a sequence of source image-data blocks, the sequences of source image-data blocks so defined being equal in number to the number of source image-data blocks into which each array is partitioned;

(c) for each sequence of source image-data blocks, deriving at least one prototypical image-data block from at least a portion of the source image data of the sequence, each prototypical image-data block having prototypical image-data elements, each prototypical image-data element being indexably associated with one of the block data-element indices;

(d) for each source image-data block in each sequence of source image-data blocks, determining an associated translation coefficient and a number of associated scaling coefficients equal to the number of prototypical image-data blocks associated with the sequence, the scaling coefficients and the translation coefficient respectively having values to at least approximately minimize a first sum of squared summands, each summand being indexably associated with one of the block data-element indices and being the square in sum of the translation coefficient plus a second sum of each of the scaling coefficients in turn multiplied by an element indexably associated with the summand block data-element index of the prototypical image-data block associated with the scaling coefficient minus an element indexably associated with the summand block data-element index of the source image-data block, the first sum being taken over all of the block data-element indices of the source image-data block;

(e) for each source image-data block in each sequence of source image-data blocks, forming a corresponding difference image-data block having difference image-data elements, each difference image-data element being indexably associated with one of the block data-element indices which defines a difference-element index, each difference image-data element being derived from an element indexably associated with the difference-element index of the source image-data block minus the translation coefficient associated with the source image-data block minus the sum in turn of each scaling coefficient associated with the source image-data block multiplied by the element indexably associated with the difference-element index of the prototypical image-data block associated with the scaling coefficient;

(f) subjecting each difference image-data block to an image-data-compression procedure to form a set of data-compression-encoded difference image-data elements; and

(g) transmitting over a communications channel each set of data-compression-encoded difference image-data elements and the scaling coefficients and the translation coefficient associated with the corresponding source image-data block.

13. The method of claim 12 further comprising:

(h) subjecting each prototypical image-data block to an image-data-compression procedure to form a set of data-compression-encoded prototypical image-data elements; and

(i) transmitting over the communications channel each set of data-compression-encoded prototypical image-data elements.

14. The method of claim 13 in which each image block represented by a source image-data block is essentially rectangular.

15. The method of claim 14 in which each image block is essentially square having a size of 64 pixels by 64 pixels.

16. The method of claim 14 in which each image block is essentially square having a size of 128 pixels by 128 pixels.

17. The method of claim 12 in which each prototypical image-data block is obtained by averaging on a corresponding-element-by-element-corresponding basis elements of at least a subset of the source image-data blocks in the associated sequence of source image-data blocks.

18. The method of claim 12 in which each prototypical image-data block represents a source image-data block, the formation of difference image-data blocks being carried out sequentially in a telescoping fashion.

19. The method of claim 13 in which the image-data-compression procedure is a differential pulse-code modulation scheme with arithmetic coding.

20. The method of claim 13 in which the image-data compression procedure is a differential pulse-code modulation scheme with Huffman coding.

21. The method of claim 12 in which two prototypical image-data blocks are derived for each sequence of source image-data blocks.

22. The method of claim 12 in which a single prototypical image-data block is derived for each sequence of source image-data blocks.