CN1612111A - Data stream conversion method and buffer device - Google Patents

Abstract

The invention discloses a data stream conversion method, marking the mark position written corresponding to a plurality of blocks with the same size in sequence by a buffer memory, then writing an input data stream into each block in sequence according to each written mark position, then calculating the read mark position and the corresponding output sequence of the block to be read according to each written mark position and the corresponding writing sequence, finally reading data from the block corresponding to each mark position in sequence according to the output sequence to output an output data stream, therefore, the conversion between the input data stream (mainly by lines/mainly by image blocks) and the output data stream (mainly by image blocks/mainly by lines) can be carried out by a small amount of buffer memory space.

Description

Data stream conversion method and buffer device

technical field

The present invention relates to a data stream conversion method, in particular to a method capable of converting a line-based data stream into a block-based data stream for subsequent compression processing, or converting the block-based data stream into a line-based data stream for subsequent decompression processing.

Background technique

JPEG and MPEG are international standards for static image compression and dynamic image compression respectively. Taking MPEG as an example, as shown in Figure 1, its data structure is composed of one or at least one sequence (sequence), and in each The sequence contains a plurality of picture groups (picture of group, GOP).

Each picture can be subdivided into several slices, and the slice can be further divided into several macro blocks (MacroBlock, MB). The macro block can be composed of four Luminance blocks and several Chrominance blocks. Finally, each block has 8×8 bytes and is defined as MPEG data. A smallest coding unit in a structure.

Referring to Fig. 2, when an original image data is compressed with MPEG-1 or MPEG-2 format, the conversion of the data stream is carried out first, so that the input data stream is converted into a block-based data stream output, such as Step 201. Next, in step 202, discrete cosine transform (DCT) is applied to the pixel data of each block, that is, the pixel data is converted from the time domain to the frequency domain, and the high-frequency part which is less sensitive to human eyes is removed. In step 203, quantization is performed again, so that many DCT coefficients after DCT are quantized to zero.

In step 204, the quantized DCT coefficients are rearranged by zig-zag scan, so that the low-frequency coefficients are arranged in front and the high-frequency coefficients are arranged in the rear. Finally, among the DCT coefficients after interleaved scanning, the DC coefficients are subjected to differential signal modulation coding (DPCM), and the AC coefficients are subjected to dynamic length encoding (RLE), and finally the two are subjected to variable length encoding (VLC). , that is to complete the compression of the MPEG-1/MPEG-2 format, as shown in step 205. The compression process of JPEG is also similar to the above-mentioned practice, and when decompressing, the above-mentioned opposite method is adopted.

Referring to Fig. 3, since both JPEG and MPEG take the image block as its basic processing unit, in the above step 201, in order to convert the line-based data stream into an image block-based ( The block-based data stream output is generally performed by a buffer memory 7 and a buffer controller (buffer controller) 8 .

When the data stream is written into the buffer memory 7 under the control of the controller 8, it will be written in the buffer memory 7 one by one from left to right and from top to bottom. is the basic unit, so the controller 8 will take out the data vertically (for example, take out 8 bytes of output from the upper left corner sequentially from top to bottom, and the content of the output data stream is the first pixel), because of this One characteristic, so before the data in the buffer memory 7 is completely filled, the data cannot be taken out, and if the data is not taken out, the data cannot be written in again.

Therefore, the buffer memory 7 is generally divided into two parts, one part is used for data input, and the other part is used for data output. As shown in FIG. 3 , when the upper half 71 is filled with data, data output is performed in units of pixels, while the lower half 72 performs data writing at the same time. After the data output of the upper part 71 is completed, there is room for data writing. At this time, the lower part 72 can read data again because the data is written. However, although this method can increase the speed of data input and output, it requires a large amount of buffer memory 7 space to carry out.

Contents of the invention

The purpose of the present invention is to provide a method and a buffer device using the method that can quickly convert data streams with only a small amount of buffer memory space.

The feature of the present invention is that the buffer device of the present invention includes a buffer memory, a tag memory, and a buffer controller.

The buffer memory has a plurality of blocks of the same size for the input data stream to write into, and the blocks are marked with a plurality of writing mark positions according to a write order. The tag memory is used to store the physical tag positions corresponding to each block. The controller is used to calculate a read order and a read mark position of the blocks to be read according to the write order and the write mark positions, so as to further determine the entity of each block The marked position reads out the data of each block to become the output data stream.

In a first preferred embodiment, the present invention provides a data stream conversion method based on the above structure, which is capable of converting an input data stream mainly based on lines into an output data stream mainly based on blocks, The method includes the steps of: A) sequentially marking a buffer memory with write-in mark positions corresponding to a plurality of blocks with the same size. Step B) Write data into each block sequentially according to the position of each write mark. Step C) Calculate the read mark position and the corresponding output order of the block to be read according to the write mark position and the corresponding write order. Step D) According to the output order, sequentially read data from the blocks corresponding to the positions of the marks, so as to output the output data stream.

Wherein, in the step C), it is based on the following relational expression:

_On (t)=I _n ((t%h)×w+t/h)

Calculate the read mark position, O(t) is the read mark position when the read order is t, the I(t) is the write mark position when the write order is t, and h is the image block height, w is the number of blocks in the total width of the buffer memory, "t%h" is the remainder obtained after dividing t by h, and "t/h" is obtained after dividing t by h business.

In a second preferred embodiment, the present invention also provides a method capable of converting a block-based input data stream into a line-based output data stream, unlike the first preferred embodiment What is, in aforesaid step C) in, be based on following relational expression:

O _n (t) = I _n ((t%w) × h+t/w)

Calculate the read mark position, O(t) is the read mark position when the read order is t, the I(t) is the write mark position when the write order is t, and h is the image block height, w is the number of blocks in the total width of the buffer memory, "t%w" is the remainder obtained after dividing t by w, and "t/w" is the quotient obtained after dividing t by w.

The effect of the present invention is that after adopting the above method, compared with the past, it only needs to add a small-capacity tag memory to store each tag position, and can complete the conversion action of the data stream with a small amount of buffer memory space

The present invention will be described in detail below in conjunction with the accompanying drawings and embodiments.

Description of drawings

FIG. 1 is a schematic diagram illustrating the data structure of MPEG.

Fig. 2 is a schematic diagram illustrating the general MPEG compression steps.

FIG. 3 is a schematic diagram illustrating a conventional buffer memory and a buffer controller.

Fig. 4 is a schematic diagram illustrating a preferred embodiment of the cushioning device of the present invention.

5 to 10 are schematic diagrams of operations, illustrating the reading and writing operations of a buffer memory when the present invention converts the line-based input data stream into a block-based output data stream.

11 to 15 are schematic diagrams of operations, illustrating the reading and writing operations of the buffer memory when the present invention converts the block-based input data stream into a line-based output data stream.

Detailed ways

Example 1

Referring to Fig. 4, 5, the first preferred embodiment of the buffer device 100 of the present invention can convert the input data stream based on lines into the output data stream based on blocks, and this preferred embodiment includes a buffer memory body 1, a tag memory 2, and a buffer controller 3.

The buffer memory 1 is used to store the input data stream received by the controller 3. In this example, a buffer memory 1 with a space of 640×8 bytes is used for illustration. In other words, the buffer memory 1 An image with a size of 640×8 can be stored at one time, but this should not be used as a limitation of the present invention. As shown in Figure 5, the buffer memory 1 can be logically divided into multiple blocks of the same size. In this example, the size of each block is 8×1 byte, so it is divided into 640 blocks in total. piece.

The starting position (address) of each block is marked to facilitate subsequent writing and reading operations. For the convenience of explanation, the marking position of each block will be specially used in the following according to writing and reading The different states are respectively expressed as the writing mark position I(t) and the reading mark position O(t). In fact, there is only one physical mark position in the same block. Wherein, t refers to a writing sequence or an output sequence, which are 0, 1, 2, 3...639 in sequence.

In this example, the image block size to be taken out is a minimum processing unit conforming to the MPEG or JPEG standard, so it is an 8*8 byte image block, so every 8 blocks in the present embodiment are a column ( column) just constitutes a block, and can be divided into 80 blocks from left to right.

In particular, the above-mentioned write mark position I(t) and read mark position O(t) both have the following specific relationship:

On(t)＝In((t%h)×w+t/h)(1)

Among them, h is the height of the image block, w is the number of blocks in each column of the buffer memory, and "t%h" refers to the remainder obtained after dividing t by h, and "t/h" refers to dividing t by The quotient obtained by h. Using formula (1), the corresponding position of the read mark and its read order can be obtained from the position of the write mark and its write order.

In this example, since h=8, w=640/8=80, so formula (1) further becomes:

On(t)＝In((t%8)×80+t/8)(2)

Therefore, the first read mark position O(0) is equal to the first write mark position I(0) [O(0)=I(0)], the second read mark position O(1)=I ((1%8)×80+1/8)=I(80), the third read mark position O(2)=I((2%8)×80+1/8)=I(160) , O(3)=I(240)..., so from formula (2), according to O(0), O(1), O(2)...O(7) respectively correspond to I(0), I (180), I(160)...I(560) in order to read each block sequentially, the first image block can be read, and the rest O(8), O(9)... can be Then read the remaining blocks.

The tag memory 2 is used to store the tag positions of each block. In other words, since the present invention is simultaneously reading and writing, it is necessary to record I(0)～I(639) and O(0 )～O(639) for each read and write mark position, so the mark memory 2 needs to have a space size of 2×2 ¹⁰ bits. In the tag memory 2, it can be mainly divided into two groups of space for storing tags. The first group of tags is used for reference by the controller 3 to perform the first writing and reading from a specific buffer memory 1 address. The second group is for the controller 3 to calculate the address of the buffer memory 1 pointed to by the second write and read action based on the first group, and the controller 3 uses the second group of marks to When reading and writing for the second time, the first group of tags can be updated to the tag address of the third reading and writing according to the second group of tags, and this is repeated, that is, the controller 3 can refer to the tag address at the same time. The mark in the memory 2 is read and written, and at the same time, the address to be read and written next time is updated.

In the following, for the convenience of explanation, the flags are directly marked in the buffer memory 1 . In fact, the flags are only stored in the flag memory 2 for reference by the controller 3 .

The controller 3 can control the data flow, and write each block sequentially with reference to the write mark positions I(0), I(1)...I(639) stored in the mark memory 2, and when reading The desired reading mark position will be calculated according to formula (2), and then the desired reading mark position will be retrieved from the mark memory 2, and the reading operation will be further performed. The writing and reading operations will be described in detail below. :

(1) Write for the first time

Referring to Fig. 5, the controller 3 refers to the write mark position stored in the mark memory 2, so that the input data stream is sequentially written in the order of I ₁ (0), I ₁ (1), I ₁ (2)... video material.

(2) Read for the first time

Referring to FIG. 6 , the present invention does not need to wait for all the space of the buffer memory 1 to be filled with data before reading data. It is possible but not limited to, for example, when the data is not yet written in the last row of blocks whose writing mark positions are I ₁ (560)-I ₁ (639), the reading of data can be started, that is, the data can be read while inputting data. Write operation while performing output operation of output data stream.

As mentioned above, the positions of the read marks in the read sequence O ₁ (0), O ₁ (1)... can be obtained by the controller 3 through formula (2), so the controller 3 refers to the mark memory After reading the position of the desired mark in 2, the data O ₁ (0), O ₁ (1), O ₁ (2) of the corresponding block is taken out from the buffer memory 1 [corresponding to the write mark Blocks whose positions are I ₁ (0), I ₁ (80), I ₁ (160)...].

In addition, while reading, blocks I ₁ (560) to I ₁ (639) are also continuously written, so there will be no interruption when sequentially reading from O ₁ (0) to O ₁ (8) .

(3) Second write

When the first write operation has reached I ₁ (639), as shown in Figure 7, there are also some blocks that have been read for the first time, so the continuous input data stream can continue to write action without interruption. By the following formula (3):

I _n+1 (t) = _On (t) (3)

It is known that the second writing sequence is the same as the first reading sequence, in other words, the first block O 1 (0) after reading is equal to the first block O ₁ (0) in the second writing The block position I ₂ (0), that is, the O ₁ (0), O ₁ (1) ... blocks are sequentially written with new data as I ₂ (0), I ₂ (1) ..., as shown in Figure 8 .

(4) The second read

When reading the O ₁ (639) block for the first time, as shown in Figure 9, the second reading can be continued [the second writing is still in progress], as shown in Figure 10, the second The position of each read mark in the sequence O ₂ (0), O ₂ (1) ... of the second read can still be calculated by the controller 3 through formula (2), which corresponds to the write position of each mark I (0) , I(180)... In other words, although the second writing is written sequentially from top to bottom, since the controller 3 still calculates the required fetch block O ₂ according to formula (2) (0), O ₂ (1) .

Therefore, the above-mentioned writing and reading operations are repeated, and the data stream can be continuously converted into pixel output. As the number of writing and reading increases, the changes become more and more complicated, so I will not go into details here. illustrate. However, it should be known that since a plurality of blocks of equal size are distinguished and the positions of each block are marked, even if the data of the input data stream are stored in non-adjacent blocks, the controller 3 can further use Equation (2) together with Equation (3) calculates the mark position of the data to be retrieved, and can output the desired data flow correctly.

In addition, for JPEG static image compression, the three primary colors of red (R), green (G) and blue (B) are processed separately, so there are usually three sets of the same buffer memory 1. In this example, for the sake of simplification , only a single buffer memory 1 is used for illustration, but those skilled in the art should know that the technology of the present invention can also be deduced to the state of multiple groups of buffer devices 100 in parallel.

Example 2

Referring to FIG. 3 and FIG. 11 , the structure of the second preferred embodiment of the present invention is the same as that of the first preferred embodiment, so it will not be described in detail again. However, this embodiment is used to convert the input data stream mainly based on blocks into an output data stream mainly based on lines, that is, this embodiment is the reverse engineering of the first preferred embodiment, and can be used in MPEG, JPEG, etc. Last segment during decompression.

In this example, a buffer memory 1 with a size of 640×8 bytes is also used for illustration, and each block is also divided into 8×1 bytes. The specific relationship between the write mark position and the read mark position then becomes the following:

_On (t)= _In ((t%w)×h+t/w) (4)

Among them, h is the height of the image block, w is the number of blocks in a column of the buffer memory, and "t%w" refers to the remainder obtained after dividing t by w, and "t/w" refers to dividing t by The quotient obtained by w. That is, using formula (4), the corresponding position of the read mark and its read order can be known from the position of the write mark and its write order.

Since w=80, h=8, so formula (4) becomes:

On(t)＝In((t%80)×8+t/80)(5)

The following will describe the process of writing data and the process of reading data using formula (5):

(1) Write for the first time

Referring to FIG. 11 , when writing, since the input data stream is mainly based on blocks, the controller 3 refers to the write-in mark position in the mark memory 2, and sequentially follows I ₁ (0), I ₁ ( 1)...I ₁ (639) sequentially write data into each block.

(2) Read for the first time

Referring to FIG. 12 , it is possible, but not limited to, to start reading data when data has not been written in the last line of the buffer memory 1 (the write mark positions are I ₁ ( 632 )˜I ₁ ( 639 )). The read block position and order can be calculated by the controller 3 according to (5) O ₁ (0)=I ₁ (0), O ₁ (1)=I ₁ (8), O ₁ (2) =I ₁ (16)..., so after the controller 3 refers to the desired tag reading position in the tag memory 2, the data in each block can be read from the specific tag position, and the data taken out in sequence , just constitutes a line-based output data stream.

On the other hand, the operation of writing blocks I ₁ ( 632 )˜I ₁ ( 639 ) is also continued until the last block I ₁ ( 639 ).

(3) Second write

At the same time when the first writing is completed, since the previously read blocks O ₁ (0), O1(1)...etc. can be written into data again, according to the above formula (3): I _{n+ 1} (t)=O _n (t) and then write data, that is, write data in the blocks whose read mark positions are O ₁ (0), O ₁ (1), O ₁ (2) in sequence, so that These become block positions I ₂ (0), I ₂ (1), I ₂ (2), . . . to be written for the second time, as shown in FIG. 13 .

(4) The second read

Referring to FIG. 14 , after the first read of the O ₁ (639) block, the second read can be continued, as shown in FIG. 15 , the order of the second read O ₂ (0), O ₂ (1) ... each reading mark position can be obtained from the mark memory 2 after being calculated by the controller 3 through formula (5), which corresponds to each mark writing position I ₂ (0), I ₂ ( 8), I ₂ (16).... Therefore, although the blocks are sequentially written from left to right during the second writing, the controller 3 still calculates the required blocks O ₂ (0), O ₂ ( 1) The corresponding mark positions of ... are I(0), I(8) ..., so the read data is still decoded from the block-based to the line-based data flow and then output.

Therefore, the controller can know the order of the blocks to be written and the sequence of the blocks to be read according to the above formula (3) and formula (5), even if the blocks to be taken out are no longer adjacent, the sequence can be correct read and write data in a timely manner.

Claims (12)

1. a data stream translation method can be changed to one based on the output information stream as piece with an input data circulation based on line, it is characterized in that:

This method comprises the following steps:

A) buffer memory is marked in regular turn the mark position that writes corresponding to the identical block of a plurality of sizes;

B), write this input data in proper order and flow to respectively in this block according to respectively this writes mark position;

C) according to respectively this writes mark position and the corresponding order that writes, calculate desire to read block read mark position and corresponding output order; And

D) according to this output order, in regular turn from reading data, to export this output information stream corresponding to the block of this mark position respectively.

2. method according to claim 1 is characterized in that:

This step C) be by one first following particular kind of relationship formula:

O _n(t)＝I _n((t％h)×w+t/h)

Calculate this and read mark position, O (t) is that this reads mark position when reading order and being t, this I (t) is that this writes mark position when writing order and being t, h is this height as piece, w is these number of blocks that this buffer memory overall width is had, " t%h " be t divided by h after the remainder of gained, " t/h " be t divided by h after the merchant of gained.

3. the method for claim 1 is characterized in that:

This first particular kind of relationship formula also meets one second particular kind of relationship formula:

I _n+1(t)＝O _n(t)

I.e. this mark position that reads of block after reading writes mark position for write fashionable this next time, and this order that reads of this block after reading is this order that writes next time.

4. a data stream translation method can be changed to an output information stream based on line based on the input data circulation as piece with one, it is characterized in that:

This method comprises the following steps:

A) buffer memory is marked in regular turn the mark position that writes corresponding to a plurality of big or small same block;

B), write this input data in proper order and flow to respectively in this block according to respectively this writes mark position;

C) according to respectively this writes mark position and the corresponding order that writes, calculate desire to read block read mark position and corresponding output order; And

D) according to this output order, in regular turn from reading data, to export this output information stream corresponding to the block of this mark position respectively.

5. method as claimed in claim 4 is characterized in that:

This step c) is by following one the 3rd particular kind of relationship formula:

O _n(t)＝I _n((t％w)×h+t/w)

Calculate this and read mark position, O (t) is that this reads mark position when reading order and being t, this I (t) is that this writes mark position when writing order and being t, h is this height as piece, w is these number of blocks that this buffer memory overall width is had, " t%w " be t divided by w after the remainder of gained, " t/w " be t divided by w after the merchant of gained.

6. the method for claim 1 is characterized in that:

The 3rd particular kind of relationship formula also meets one the 4th particular kind of relationship formula:

I _n+1(t)＝O _n(t)

I.e. this mark position that reads of block after reading writes mark position for write fashionable this next time, and this order that reads of this block after reading writes order for next time this.

7. a snubber assembly becomes one based on the output information stream as piece in order to change the input data stream based on line, comprises a buffer memory, a mark memory body and a buffer control unit, it is characterized in that:

The block that this buffer memory physical efficiency is partitioned into logically that complex magnitude equates and writes for this input data stream, these blocks also write order according to one and are labeled out plural number and write mark position;

This mark memory used for storing is the pairing entity mark position of this block respectively;

This buffer control unit is in order to write order according to this and these write mark position, calculate and desire to read one of these blocks and read order and and read mark position, the data of this block becomes this output information stream further to read out respectively by the entity mark position of this block respectively.

8. snubber assembly as claimed in claim 1 is characterized in that:

This buffer control unit is according to following one first particular kind of relationship formula:

On(t)＝In((t％h)×w+t/h)

Calculate this and read mark position, O (t) is that this reads mark position when reading order and being t, this I (t) is that this writes mark position when writing order and being t, h is this height as piece, w is these number of blocks that this buffer memory overall width is had, " t%h " be t divided by h after resulting remainder, " t/h " be t divided by h after resulting merchant.

9. snubber assembly as claimed in claim 8 is characterized in that:

This first particular kind of relationship formula also meets one second particular kind of relationship formula:

I _n+1(t)＝O _n(t)

I.e. this mark position that reads of block after reading writes mark position for write fashionable this next time, and this order that reads of this block after reading is this order that writes next time.

10. snubber assembly becomes an output information stream based on line in order to change one based on the input data stream as piece, and this snubber assembly comprises a buffer memory, a mark memory body and a buffer control unit, it is characterized in that:

The block that this buffer memory physical efficiency is partitioned into logically that complex magnitude equates and writes for this input data stream, these blocks also write order according to one and are labeled out plural number and write mark position;

This mark memory used for storing is the pairing entity mark position of this block respectively;

This buffer control unit is in order to write order according to this and these write mark position, calculate and desire to read one of these blocks and read order and and read mark position, the data of this block becomes this output information stream further to read out respectively by the entity mark position of this block respectively.

11. snubber assembly as claimed in claim 10 is characterized in that:

This buffer control unit is according to following one the 3rd particular kind of relationship formula:

O _n(t)＝I _n((t％w)×h+t/w)

Calculate this and read mark position, O (t) is that this reads mark position when reading order and being t, this I (t) is that this writes mark position when writing order and being t, h is this height as piece, w is these number of blocks that this buffer memory overall width is had, " t%w " be t divided by w after resulting remainder, " t/w " be t divided by w after resulting merchant.

12. snubber assembly as claimed in claim 11 is characterized in that:

The 3rd particular kind of relationship formula also meets one the 4th particular kind of relationship formula:

I _n+1(t)＝O _n(t)

I.e. this mark position that reads of block after reading writes mark position for write fashionable this next time, and this order that reads of this block after reading writes order for next time this.

Images