Apparatus and method of coding/decoding video data

• US 5,467,086 A
• Filed: 06/18/1993
• Issued: 11/14/1995
• Est. Priority Date: 06/18/1992
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Jeong, Jechang
• Primary Examiner(s): Hoff, Marc S.
• Application Number:
  US08/078,343
• Time in Patent Office: 879 Days
• Field of Search: 341/50, 341/76, 348/400, 348/401, 348/402, 348/409, 348/415, 348/416
• US Class Current: 341/50
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A method and apparatus for coding and decoding video data including a still image or active image on an intraframe basis. The coding system defines a search area composed of reconstructed data blocks and determines which one of the blocks within the search area has a pattern similar to a present data block that is in the process of being coded. The system then computes the amount of displacement between the present data block and the reconstructed data block from the search area that has a pattern very similar to that of the present data block. The coded data is then stored in memory or transmitted. The decoding system implements a reverse process of the coding system to decode the coded data based on the displacement vector.

Claims

1. A coder for compressing data, comprising:

block dividing means for dividing a frame of data into blocks of predetermined sizes, and outputting original data blocks;

coding means, coupled to said block dividing means, for coding each of said original data blocks according to a predetermined algorithm, and outputting coded data blocks;

reconstruction means, coupled to said coding means, for reconstructing each of said coded data blocks, and outputting reconstructed data blocks corresponding to said original data blocks;

a frame memory, coupled to said reconstruction means, for storing a frame of data based on said reconstructed data blocks;

search area determining means, coupled to said frame memory, for selecting a predetermined number of said reconstructed data blocks stored in said frame memory so as to define a search area;

displacement estimation means coupled to said search area determining means for receiving said selected number of reconstructed data blocks, and coupled to said block dividing means for receiving a present data block, said displacement estimation means determining by estimation which one of said reconstructed data blocks has a pattern similar to said present data block, and calculating a displacement vector based on said estimation;

displacement compensation means, coupled to said frame memory and to an output of said displacement estimation means, for receiving and outputting the data block from said frame memory having the pattern similar to said present data block based on said output of said displacement estimation means;

a first adder, coupled to said block dividing means and said displacement compensation means, for calculating differential data based on said present data block and the data block output by said displacement compensation means;

mode determining means, coupled to said first adder and said block dividing means, for determining a mode by comparing said present data block with said differential data, and outputting a corresponding mode value; and

means, responsive to said mode value output by said mode determining means, for selecting one of said present data block and said differential data according to the mode value; and

inputting said selected one of said present data block and said differential data to said coding means for coding.

2. A coder as defined in Claim 1, further comprising a mode-displacement vector combiner, coupled to said mode determining unit and said displacement estimation means, for combining said displacement vector and said mode value.

3. A coder as defined in Claim 1, further comprising a second adder having a first input coupled to an output of said reconstruction means, and a second input;

and switching means having an input coupled to an output of said displacement compensation means, and an output coupled to said second input of said second adder, said switching means being responsive to said mode value; and

said second adder supplying the output of said reconstruction means or the sum of the outputs of said reconstruction means and said displacement compensation means to said frame memory in accordance with said mode value.

4. A coder as defined in claim 3, wherein said switching means is turned off when said mode value equals a first predetermined mode value, and is turned on when said mode value equals a second predetermined mode value.

5. A coder as defined in claim 1, wherein said coding means comprises:

an orthogonal transformer, coupled to said block dividing means, for transforming each data block into transformation coefficients;

a quantizer, coupled to said orthogonal transformer, for quantizing said transformation coefficients and outputting quantization coefficients; and

a variable length coder, coupled to an output of said quantizer, for coding said quantization coefficients according to a variable length coding technique.

6. A coder as defined in claim 1, wherein said reconstruction means comprises:

a dequantizer, coupled to said output of said quantizer, for dequantizing said quantization coefficients; and

an inverse-orthogonal transformer, coupled to an output of said dequantizer, for transforming said dequantized transformation coefficients.

7. A coder as defined in claim 1, wherein said search area is composed of data blocks positioned adjacent to said present data block within said frame of data.

8. A coder as defined in claim 1, wherein said mode determining means comprises:

means for comparing an energy level of said present data block with an energy level of said differential data; and

means for outputting a first mode value when the energy level of said present data block is less than that of said differential data, and a second mode value when the energy level of said differential data is less than that of said present data block data.

9. A coder as defined in claim 1, further comprising switching means having a first terminal coupled to an output of said displacement compensation means, and a second terminal, said switching means being responsive to said mode value;

and a second adder having a first input coupled to said block dividing means and a second input coupled to said second terminal of said switching means, said second adder supplying the output of said block dividing means or the sum of the outputs of said block dividing means and said displacement compensation means to said coding means in accordance with said mode value.

10. A coder as defined in claim 9, wherein said switching means is turned off when said mode value equals a first predetermined mode value, and is turned on when said mode value equals a second predetermined mode value.

11. A decoder for decoding data which has previously been coded by a coder, said coder outputting coded data blocks having been coded according to a predetermined coding algorithm, and a mode value and a displacement vector for data being coded based on a similarity between first and second data blocks, said decoder comprising:

an input terminal for receiving the coded data blocks, the mode value, and the displacement vector;

decoding means, coupled to said input terminal, for decoding the coded data blocks according to a predetermined algorithm, and outputting decoded data blocks;

separation means, coupled to said input terminal, for separating said mode value and said displacement vector from said coded data blocks;

switching means having first and second terminals, said switching means being responsive to said mode value;

an adder having a first input coupled to an output of said decoding means and a second input coupled to said first terminal of said switching means;

a frame memory, coupled to an output of said adder, for storing a frame of data based on said decoded data blocks; and

a displacement compensation means, coupled to an output of said separation means and said frame memory, for receiving a data block from said frame memory corresponding to said displacement vector received from said separation means, and applying said data block to said second terminal of said switching means, wherein said adder selectively adds the output data block from said displacement compensation means to an output of said decoding means in accordance with said mode value.

12. A decoder as defined in claim 11, wherein said separation means outputs said mode value having a first predetermined mode value corresponding to data being coded in the coder according to the predetermined coding algorithm, and having a second predetermined mode value corresponding to data being coded based on a similarity between the first and second data blocks.

13. A method for compressing data comprising the steps of:

(a) dividing a frame of data into blocks of predetermined sizes, and outputting original data blocks;

(b) coding each of said original data blocks according to a predetermined algorithm, and outputting coded data blocks;

(c) reconstructing each of said coded data blocks, and outputting reconstructed data blocks corresponding to said original data blocks;

(d) storing a frame of data based on said reconstructed data blocks;

(e) selecting a predetermined number of said reconstructed data blocks stored in said frame memory so as to define a search area;

(f) determining, by estimation, which one of said reconstructed data blocks has a pattern similar to a present data block, and calculating a displacement vector based on said estimation;

(g) selecting, as a selected data block, the data block having the pattern similar to said present data block based on said displacement vector;

(h) calculating differential data based on said present data block and said selected data block;

(i) determining a mode by comparing said present data block with said differential data, and outputting a corresponding mode value; and

(j) coding one of said present data block and said differential data according to the mode value.

14. A coding method as defined in claim 13 further comprising the step of combining said mode value with said displacement vector into a data pack.

15. A coding method as defined in claim 13, wherein said search area is composed of data blocks positioned adjacent to said present data block.

16. A coding method as defined in claim 13, wherein said mode determining step (i) comprises the steps of:

comparing energy levels of said present data block and of said differential data;

setting said mode value to a first mode value when the energy level of said present data block is less than that of said differential data; and

setting said mode value to a second mode value when the energy level of said differential data is less than that of said present data block.

17. A coding method as defined in claim 16, wherein said coding step (b) comprises the steps of coding said present data block when said mode value equals said first mode value, and coding said differential data when said mode value equals said second mode value.

18. A coding method as defined in claim 16, wherein said storing step (c) comprises the steps of:

storing reconstructed data blocks when said mode value equals said first mode value, and storing differential data when said mode value equals said second mode value, said differential data equals to said reconstructed data plus the data block selected by selecting step (g).

19. A method for decoding data which has previously been coded by a coder, said coder outputting coded data blocks having been coded according to a predetermined coding algorithm, and a mode value and a displacement vector for data being coded based on a similarity between first and second data blocks, said method comprising the steps of:

(a) receiving the coded data blocks, mode value, and displacement vector;

(b) decoding the coded data blocks according to a predetermined algorithm, and outputting decoded data blocks;

(c) separating said mode value and said displacement vector from said coded data blocks;

(d) storing a frame of data based on said decoded data blocks in a frame memory;

(e) selecting a data block from said frame memory corresponding to said displacement vector; and

(f) adding, selectively in accordance with said mode value, said decoded data blocks to said selected data block to produce original data blocks.

20. A decoding method as defined in claim 19, wherein said separating step (c) comprises the steps of:

outputting said mode value having a first predetermined mode value corresponding to data being coded in the coder according to the predetermined coding algorithm, and outputting said mode value having a second predetermined mode value corresponding to data being coded based on a similarity between the first and second data blocks.

21. A decoding method as claimed in claim 19, further comprising the step of:

outputting said decoded data blocks when said mode value equals said first mode value, and outputting a sum of said decoded data block and selected data block when said mode value equals said second mode value.