Block transform coder for arbitrarily shaped image segments

• US 5,422,963 A
• Filed: 10/15/1993
• Issued: 06/06/1995
• Est. Priority Date: 10/15/1993
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Chen, Homer H., Haskell, Barin G., Civanlar, Mehmet R.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US08/138,295
• Time in Patent Office: 599 Days
• Field of Search: 382/56, 382/21, 382/41, 382/48, 358/433, 348/395, 348/420, 348/416
• US Class Current: 382/232
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/48 using compressed domain processing techniques other than decoding, e.g. modification of transform coefficients, variable length coding [VLC] data or run-length data motion estimation in a transform domain H04N19/547; processing of decoded motion vectors H04N19/513

Abstract

A Transform Coder Unit (TCU) to transform an arbitrarily shaped image into optimal transform coefficients (OTC) for data transmission. The TCU comprises a forward transform which transforms the image to transform coefficients, and a TCS generator which generates a transform coefficient set (TCS) from the transform coefficients. The TCU also contains an inverse transform which transforms the TCS to a computed region block having computed pel values. Finally, the TCU comprises a replacer which replaces those computed pel values corresponding to the interior pel set with the original pel values to form a modified computed region block which is re-iterated until optimal transform coefficients are determined. The present invention is also directed at a process for determining optimal transform coefficients using the aforementioned device.

Claims

1. An apparatus for selecting image data representing an arbitrarily shaped image for optimizing transmission of said image data said apparatus comprising:

a. first means for transforming said arbitrarily shaped image to transform coefficients;

b. second means coupled to said first means for generating a transform coefficient set (TCS) from said transform coefficients, said TCS generator being configured to output said TCS when said TCS represents said selected image data, and to send said TCS to an inverse transform when said TCS does not represent said selected image data;

c. third means coupled to said second means for transforming said TCS to a computed region block having computed pel values; and

d. fourth means coupled to said third means for replacing computed pel values corresponding to art interior pel set of said arbitrarily shaped image with original pel values of said arbitrarily shaped image so as to form a modified computed region block (MCRB), said fourth means being configured to send a modified computed region block to a reiterative forward transform for re-iteration.

2. The apparatus of claim 1, wherein said second means includes a quantizer which generates said TCS by quantizing said transform coefficients.

3. The apparatus of claim 1, wherein said second means generates said TCS by selecting and retaining those transform coefficients which have high energy according to the energy compaction property of transform coefficients, and by zeroing all the non-selected transform coefficients.

4. The apparatus of claim 3 wherein said second means comprises a rate controller to establish a threshold energy level at which said TCS selector retains transform coefficients, said rate controller establishes said level based on the bit budget of an encoder and the size of said arbitrarily shaped image.

5. The apparatus of claim 3 wherein said second means comprises a TCS limiter to independently establish the number of transform coefficients to retain.

6. The apparatus of claim 1, wherein said re-iterative forward transform and said forward transform are one in the same, and further comprising:

e. an iteration controller which controls an iteration switch having a first position and a second position, said first position directs TCS from said TCS generator to said inverse transform when said TCS does not represent said selected image data, said second position directs said TCS from said TCS generator to output of said TCU.

7. The apparatus of claim 6, wherein said iteration controller comprises an iteration counter to independently establish the number of iterations to perform, after said apparatus performs the established number of iterations, said switch switches to said second position.

8. The apparatus of claim 6, wherein said iteration controller contains a convergence detector, and a frame buffer, said frame buffer stores the pel values of a previous iteration, said convergence detector switches said switch from said first position to said second position when the mean squared difference between said MCRB stored in said frame buffer and that of the current iteration reaches a pre-determined level.

9. The apparatus of claim 6, wherein said iteration controller contains a convergence detector, and a frame buffer, said frame buffer stores the TCS of a previous iteration, said convergence detector switches said switch from said first position to said second position when the mean squared difference between the TCS stored in said frame buffer and that of the current iteration reaches a pre-determined level.

10. The apparatus of claim 1 wherein said re-iterative forward transform comprises a forward transform of a succeeding apparatus, said succeeding apparatus connected in series with said apparatus.

11. The apparatus of claim 1 wherein said forward transform is a discrete cosine transform (DCT) chip.

12. An apparatus for selecting image data representing an arbitrarily shaped image for optimizing low-date rate transmission of said image data, said apparatus comprising:

(a) generating means for generating original pel values, said generating means including;

(i) circumscribing means for circumscribing said arbitrarily shaped image with a rectangular region block, thereby creating an internal pel set which lies within said arbitrarily shaped image and within said region block, and an external pel set which lies outside said arbitrarily shaped image within said region block; and

(ii) initializing means for initializing pel values of said external pel set by extrapolating the pel values of said internal pel set;

(b) operating means for operating a transform coder unit (TCU) which calculates optimal transform coefficients, said operating means including;

(i) means for performing a forward transform on said region block to generate transform coefficient;

(ii) means for generating a transform coefficient set (TCS) from transform coefficients;

(iii) means for performing an inverse transform on said TCS thereby generating a computed region block having computed pel values;

(iv) means for replacing those computed pel values corresponding to said internal pel set with original pel values to form a modified computer region block (MCRB);

(v) means for determining whether said TCS represents said OTC;

(vi) means for reiterating steps (i) and (ii) on said modified computed region block and outputting said TCS when said TCS represents OTC; and

(vii) reiterating steps (i) through (vii) on said modified computed region block when said TCS values do not represent said OTC.

13. The apparatus as recited in claim 12, wherein said means for performing a forward transform includes a discrete consine transform (DCT) chip.

14. The apparatus as recited in claim 12, wherein said means for generating said TCS is configured to quantize said transform coefficients.

15. The apparatus as recited in claim 14, wherein said means for generating said TCS is further configured to select and retain those transform coefficients which have high energy according to the energy compaction property of transform coefficients, and zeroing the non-selected transform coefficients.

16. The apparatus as recited in claim 15, wherein said TCS includes a rate controller to establish a threshold energy level at which transform coefficients are retained, said rate controller being configured to establish said level based upon the bit budget of an encoder and the size of said arbitrarily shaped image.

17. The apparatus as recited in claim 15, wherein said means for generating said TCS is further configured to independent establish a number of transform coefficients to retain.

18. The apparatus as recited in claim 12, wherein said means for determining whether said TCS represents said OTC is configured to independently establish the number of iterations to perform.

19. The apparatus as recited in claim 18, wherein said means for determining whether said TCS represents said OTC is further configured to determine when the means squared difference between said MCRB of one iteration and that of a subsequent iteration reaches a predetermined threshold.

20. An apparatus for selecting image data representing an arbitrarily shaped image for optimizing transmission of said image data, said apparatus comprising:

(a) means for generating original pel values, said means including;

(i) means for circumscribing said arbitrarily shaped image with a rectangular region block, thereby creating an internal pel set which lies within said arbitrarily shaped image and within said region block, and an external pel set which lies outside said arbitrarily shaped image and within said region block; and

(ii) means for initializing pel values of said external pel set by extrapolating the pel values of said internal pel set;

(b) means for operating a transform coder unit (TCU) for calculating optimal transform coefficients, said means for operating a TCU including;

(i) means for performing a forward transform on said region block to generate transform coefficients;

(ii) means for generating a transform coefficient set (TCS) from said transform coefficients;

(iii) means for determining whether said TCS represents optimal transform coefficients (OTC);

(iv) means for outputting said TCS when said TCS represents said OTC;

(v) means for performing an inverse transform on said set TCS when said TCS does not represent said OTC, said inverse transform generates a computed region block having computed pel values;

(vi) means for replacing those computed pel values corresponding to said internal pel set with original pel values so as to form a modified computed region block; and

(vii) means for reiterating steps (i) through (vii) on said modified computed region block.