Image data encoder/decoder system which divides uncompresed image data into a plurality of streams and method thereof

• US 5,809,176 A
• Filed: 10/18/1995
• Issued: 09/15/1998
• Est. Priority Date: 10/18/1994
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Yajima, Akihiko
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/544,945
• Time in Patent Office: 1,063 Days
• Field of Search: 382/247, 382/233, 382/244, 341/51, 341/107
• US Class Current: 382/247
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

An image data encoder and decoder system which divides native or uncompressed image data into a plurality of streams for subsequent arithmetic encoding and decoding operations. Once each stream has been encoded, it may be relayed in its present format to a corresponding decoder unit or combined with other encoded streams to produce a composite encoded stream representing a compressed version of the original image data suitable for external transfer or storage. When stored in composite form, the decoder may include a distributing preprocessor that breaks it back down into its constituent encoded streams to facilitate parallel decoding. After decoding operations have produced plural decoded image streams, a final stage reintegrates them back to the original image data. The matched parallel encoder and decoder architectures permit pipelined processing of image data without necessarily increasing overall processing speeds.

Claims

1. An image data encoder system comprising:

a data division circuit to divide image data at least partially representing an image into a plurality of individual image data streams according to at least one of a format of the image data and a spatial relationship between the image data and the image;

a plurality of dedicated arithmetic encoders in communication with said data division circuit to encode the individual data streams in parallel as a corresponding plurality of coded data streams, each of said dedicated arithmetic encoders corresponding to and encoding one of the individual data streams into one of the coded data streams; and

a data integrator in communication with said arithmetic encoders to combine the coded data streams in accordance with prescribed rules to form a single integrated coded data stream;

wherein said data integrator means comprises;

a plurality of buffers in communication with said arithmetic encoders to temporarily store the coded data streams in sequence and perform carry transfer operations based on carry signals issued by said arithmetic encoder;

a code combining circuit in communication with said plurality of buffers to receive buffered coded data streams issued therefrom and sequentially combine the received coded data streams into a single, integrated coded data stream; and

a buffer controller in communication with said plurality of buffers and said code combining circuit to determine a probability of carry transfer based on the carry transfer operations performed by said plurality of buffers and to control transmission of the coded data streams stored in said plurality of buffers to said code combining circuit according to a predetermined order when the determined probability of carry transfer is low.

2. The image data encoder system of claim 1, wherein each said data integrator buffer is coupled to a selected one of said arithmetic encoders and comprises:

a first-in-first-out buffer memory in communication with said selected arithmetic encoder, said buffer controller, and said code combining circuit to sequentially store at least one of the coded data streams emanating from said arithmetic encoder;

a first-in-first-out code length memory in communication with said selected arithmetic encoder, said buffer controller, and said code combining circuit to sequentially store a corresponding code length for each coded data stream stored by said buffer memory; and

a carry transfer processor in communication with said selected arithmetic encoder and said buffer controller to perform carry transfer operations for the coded data stored in said buffer memory responsive to a corresponding carry signal issued by said selected arithmetic encoder; and

wherein, for each buffer, said buffer controller controls transmission of the coded data streams stored in the buffer memory and the corresponding code lengths stored in the code length memory to said code combining circuit according to the predetermined order.

3. The image data encoder system of claims 1 or 2, further comprising storage means in communication with said data integrator for storing the integrated coded data stream.

4. The image data encoder system of claim 1, wherein said plurality of dedicated arithmetic encoders encodes the individual image data streams concurrently.

5. The image data encoder system of claim 1, wherein said plurality of dedicated arithmetic encoders encodes said individual image data streams using pipelined parallel processing.

6. The image data encoder system of claim 1, further comprising a data integrator in communication with said arithmetic encoders to combine the coded data streams in accordance with prescribed rules to form a single, integrated coded data stream.

7. The image data encoder system of claim 1, further comprising a synchronizing controller in communication with each said dedicated arithmetic decoder for selectively sequencing encoding of each individual data stream.

8. An image data encoder system, comprising:

a data division circuit to divide image data at least partially representing an image into a plurality of individual image data streams according to at least one of a format of the image data and a spatial relationship between the image data and the image; and

a plurality of dedicated arithmetic encoders in communication with said data division circuit to encode the individual data streams in parallel as a corresponding plurality of coded data streams, each of said dedicated arithmetic encoders corresponding to and encoding one of the individual data streams into one of the coded data streams;

wherein each of said dedicated arithmetic encoders comprises;

context generating means in communication with said data distributor for generating reference pixel data from pixel data contained in the corresponding individual image data stream as a context signal;

index generating means in communication with said context generating means for producing an optimum transition destination index ST_i as a function of the context signal and a transition destination index ST₀ ;

probability estimator means in communication with said index generating means for composing table data corresponding to the optimum transition destination index ST_i, the table data being stored therein and including, for each table index ST, a symbol generating probability for at least one of the group consisting of major and minor symbols, a transition destination index NLPS when the minor symbol is generated, and a transition destination index NMPS when a major symbol is generated;

area register means for storing length data A of a new encoding line created every time pixel data is received;

code register means for storing a coordinate of the point included in the new encoding line created for each pixel data, as position coordinate data C; and

processing means in communication with said index generating means, probability estimator means, said area register means, and said code register means, for each pixel data received by said context generating means;

dividing the encoding line length A and position coordinate data C stored in the area and code registers, respectively, according to symbol generating probability for given pixel data included in the table data of said probability estimator means, in order to create a next new encoding line;

updating the encoding line length A and position coordinate data C stored in the area and code registers, respectively, according to the next new encoding line; and

transmitting to said index generating means one of the input transition destination index NLPS when the given pixel data is a minor symbol and transition destination index NMPS when the given pixel data is a major symbol as the next transition destination index ST0.

9. The image data encoder system of claim 8, wherein said processing means:

normalizes the length data A of the encoding line stored in the code register means relative to a predetermined standard value through bit shifting operations; and

outputs overflowing data from the code register as coded data included in the corresponding coded data stream.

10. An image data encoder/decoder system, comprising:

a data division circuit to divide original image data at least partially representing an image into a plurality of individual image data streams according to at least one of a format of the image data and a spatial relationship between the image data and the image;

a plurality of dedicated arithmetic encoders in communication with said first data division circuit to encode the individual data streams in parallel as a corresponding plurality of coded data streams, each of said dedicated arithmetic encoders corresponding to and encoding one of the individual data streams into one of the coded data streams;

a plurality of dedicated arithmetic decoders in communication with said arithmetic encoders, each of said dedicated arithmetic decoders in communication with one of said dedicated arithmetic encoders and decoding a corresponding one of the coded data streams as a decoded data stream; and

a data integrator in communication with said plurality of dedicated arithmetic decoders to combine the decoded data streams and reform the original image data;

wherein each of said dedicated arithmetic decoders comprises;

context generating means in communication with said data encoder for generating reference pixel data for an immediately succeeding code data contained within the corresponding coded data stream based on existing decoded data stream as a context signal;

index generating means in communication with said context generating means for producing an optimum transition destination index ST_i as a function of the context signal and a transition destination index ST₀ ;

probability estimator means in communication with said index generating means for table data corresponding to the optimum transition destination index ST_i, the table data being stored therein and including, for each table index ST, a symbol generating probability for at least one of the group consisting of major and minor symbols, a transition destination index NLPS when the minor symbol is generated, and a transition destination index NMPS when a major symbol is generated;

area register means for storing length data A of a decoding line;

code register means for storing a coordinate of the point included in the new decoding line as position coordinate data C; and

processing means in communication with said index generating means, probability estimator means, said area register means, and said code register means, for each pixel data received by said context generating means;

for dividing the decoding line specified with the data stored in the area register into major and minor areas according to a symbol generating probability for the pixel data included in the table data of said probability estimator means;

for defining a new decoding line depending on which area a given code data falls in;

for replacing the data stored in said area register with the new length data A;

for outputting the symbol used for selecting said divided area as the decoded pixel data corresponding to the given code data; and

transmitting to said index generating means one of the input transition destination index NLPS when the decoded pixel data is a minor symbol and transition destination index NMPS when the decoded pixel data is a major symbol as the next transition destination index ST0.

11. The image data encoder/decoder system of claim 10, wherein said plurality of dedicated arithmetic decoders decodes the coded data streams concurrently.

12. The image data encoder/decoder system of claim 10, wherein said plurality of dedicated arithmetic decoders decodes said coded data streams using pipelined parallel processing.

13. The image data encoder system of claim 10, wherein said processing means:

normalizes the length data A of the decoding line stored in the code register means relative to a predetermined standard value through bit shifting operations; and

outputs overflowing data from the code register as the code length of the next immediately succeeding code data of the corresponding coded data stream.

14. The image data encoder/decoder system of claim 10, further comprising a synchronizing controller in communication with each said dedicated arithmetic decoder for selectively sequencing decoding of each coded data stream.