KR20040050070A - Compressed storage of data items - Google Patents

Abstract

Storing a data item in memory 31, dividing the data items into successive data pieces of decreasing significance, storing the data pieces in respective parts of memory 31, and all candidate memory parts When applying a data piece to the memory 31 when allocated to other data pieces; If the significance value of the applied data piece is lower than the low significance value of other data pieces, the applied data piece is ignored, and if the significance value of the applied data piece is higher than the low significance value, Store the applied data piece in one of the candidate memory parts at the expense of another given data piece with a low significance value; The significance value of the data piece is based on the total or absolute distortion value of the data item. Advantageous use of the invention is made in applications using a fixed storage device for storing a predetermined number of compressible data items such as video, image, audio, and voice.

Description

Compressed storage of data items {COMPRESSED STORAGE OF DATA ITEMS}

It is known to use a storage medium with a fixed size to store multiple objects that can be irreversible (lossy) compressed. Such applications include digital still cameras, where images are stored on flash cards, floppy disks or disk-drives. In addition, video cameras are known in which multiple records are stored on a hard-drive, optical disk or tape. In addition, storage devices such as embedded memories are known, where it is desirable to minimize the total storage used while maintaining the best possible image quality. Sometimes a limited number of settings are available to a user to change the tradeoff between quality and capacity. For example, video may be recorded in "standard play" or "long play" mode, or snapshots may be taken at "standard resolution" or "high resolution". Once it is determined which quality to use, the decision cannot be changed later even if Apple storage continues to be available.

Cormac Herley discloses the storage of digital camera images at "6th International Conference on Image Processing (ICIP'99), vol. 3, Kobe, Japan, 24-28 Oct. 1999." The camera is designed to store a fixed number of images and loss control compression is used so that each image fits into the space allocated to it.

It is an object of the present invention to improve the storage of data items. To this end, the present invention provides a method and apparatus for storing data items in a memory and a storage medium as defined in the independent claims. Advantageous embodiments are defined in the dependent claims.

The present invention relates to a method of storing data items in a memory and reading the data items from the memory, and a storage medium in which the data items are stored.

1 is a schematic diagram of an apparatus in which data items are stored in accordance with the present invention;

FIG. 2 is a detailed view of a portion of the apparatus shown in FIG. 1. FIG.

According to a first aspect of the invention, each data item is divided into successive data pieces that reduce the significance, the data pieces being stored in respective portions of the memory, and applying the data piece to the memory. When all candidate memory parts are allocated to different data pieces,

If the significance value of the applied data piece is lower than the lowest significance value of the other data pieces, the applied data piece is ignored,

If the significance value of the authorized data piece is higher than the lowest significance value of the other data pieces, then the applied data piece is one of the candidate memory portions at the cost of the other data piece given as the significance value lower than that of the authorized data piece. And the significance value of each data piece is based on the total or absolute distortion of the data item in the data piece. By considering the total or absolute distortions, the degradation of quality will always affect the (almost) highest quality data item. Global or absolute distortion is a measure of the absolute quality of a data item, where low distortion indicates high quality while high distortion indicates low quality.

The significance value associated with a given piece of data may be based on the total or absolute distortion of the data item up to and including the piece of data. In this embodiment, the data item with the highest quality at present will be reduced in quality.

Advantageously, the significance value associated with a given piece of data may be based on the total or absolute distortion of the data item that does not include the piece of data. In this embodiment, the quality of the data item is taken into account after the data piece is removed, so that the minimum data item quality is maximized. In other words, in this embodiment, after the quality reduction, the data item with the highest quality will be reduced in quality.

In a preferred embodiment of the invention, a record is maintained for each piece of data, and the record includes the data item to which the piece of data belongs and the significance of the piece of data. The significance value of each data piece represents the total distortion of the data item in that data piece. The record piece may be locally integrated into the memory part, for example with the data piece to which it belongs. Preferably, records are maintained in auxiliary memory, each record further comprising a pointer indicating a location in main memory in which the data piece is stored.

Each time a new data item is stored, the new data item is preferably compressed by a scalable compression method to generate a scalable bit-stream. Advantageous methods are described in WO01 / 17268-A1. This scalable compression method has the property that when multiple bits are available, the resulting scalable bit-stream provides the best possible reconstruction quality for a given data item. When the scalable bit-stream is not cut off, the data item is (almost) lossless encoded, i.e., quality such as playback may be perceptually indistinguishable from the original. Scheduling coding mechanisms are known for video and audio. In a preferred embodiment, the scalable bit stream is truncated into pieces of data having the same sizes as the memory portions. Next, for each of these data pieces, a significance value is calculated. Preferably, the significance value is calculated as a distortion value that indicates the significance of the perceptual significance value. The significance value is used to compare the data pieces of the new item with the already stored data pieces. It is understood that the data pieces generated by dividing the scalable bit-stream have the property of reducing significance because the scalable coding methods generate the most significant bits. Then, the data pieces of the new item are compared with the data pieces already existing in the memory. When the new data pieces have the highest significance value, the previously stored data pieces are overwritten.

Although scalable coding methods are preferred, hierarchical coding methods can be used.

The present invention enables the storage of variable data items in a fixed storage space. These data items are preferably multimedia objects including audio objects, video objects, graphic objects, and the like. Data items are always stored at the optimum quality for a given amount of storage information. When additional data items are to be stored, the occupied storage amount of already stored data item (s) is reduced to fit the new data item so that all data items are stored at approximately the same quality (resulting in reduced quality).

Although in the preferred embodiment of the present invention all memory parts have the same size, this is not required. The size of the memory portions is chosen such that the storage capacity of the multiple memory portions is required for storing a single data item with high quality. For example, eight stored data pieces are practical for storing an image.

In a preferred embodiment of the present invention, the possibility is provided that a user can store any data items with a higher quality than other data items.

These and other features of the present invention will become apparent with reference to the accompanying drawings.

The drawings only show the components necessary to understand the invention.

1 shows an apparatus of the invention comprising an input unit 1, a scalable coder 2, a memory 3, a scalable decoder 4, and an output unit 5. The input unit 1 may be of any kind for obtaining data, such as an antenna, a camera, or a storage medium. Data can be applied directly to the output unit 5. The output unit 5 may be any kind of output unit, for example an antenna, a display or a storage medium. Before the data is applied to the memory 3, the scalable coder 2 processes the data to obtain scalable bit-streams. The scalable bit streams are then applied to the memory 3. In order to retrieve data from the memory 3, a scalable decoder 4 is provided which applies decoded data to the output unit 5 when desired. The memory 3 includes an auxiliary memory (AM) 30 and a main memory (MM) 31. If necessary, any control or processing unit may be included in the memory 3 to control the data flows.

In Fig. 2, an auxiliary memory 30 and a main memory 31 are described with an exemplary embodiment. Main memory 31 is divided into N memory portions to store N data pieces. In this example N = 11. Auxiliary memory is typically smaller than main memory and is used for management. The auxiliary memory contains N records, each record containing several fields. The first field is a main memory pointer P that contains a pointer to a location in main memory 31 that holds data associated with a given record. The second field is an object identifier (I) containing information describing the data item to which the data piece stored in the main memory belongs. The object identifier refers to one image of the set of images stored by the digital camera, for example. In a practical embodiment, no data item is assigned to the memory portion when the object identifier is zero, for example when the memory portion is empty. The third field contains a significance value (S). The S field provides a measure of the significance of the data piece stored in main memory 31 referred to by the record. The entries of the significance value fields are preferably nonnegative. The secondary memory 30 preferably has the property that the records are sorted by significant value. Alternatively, it is also possible to sort the records by another way, such as an identifier, to group all data pieces belonging to the same data item. Within each group of data pieces, the data pieces can be sorted by significance.

To add a data item, the data item is coded in the coder 2 to generate a scalable bit-stream that is divided into data pieces. Next, the pieces are processed. The significance measure of each piece is first compared to the measure of the block (piece) with the low significance measure in the current memory. If the significance value of the new data piece is low, it is not stored in main memory. It is ignored. When the first piece is not stored, processing may stop because the additional data pieces have a lower significance value than the current data piece (which has the properties of a scalable coding mechanism). If the significance value is high, a new data piece is written to the main memory 31 at the position of the current minimum valid data piece (obtained from the last position of the auxiliary memory if records are stored as a significance value). Then, the last record of the auxiliary memory is replaced with the records data for the new data piece, and the records in the auxiliary memory 30 are rearranged to restore in order of significance. It is advantageous to start processing from the maximum valid data piece of the item (following processing of the next data pieces with a lower significance value). This is because the data pieces are in the order generated by the scalable coder 2 and because these data pieces are not overwritten by blocks belonging to the same item due to low significance.

To extract the data item, the records in the secondary memory 30 are then processed, and if the object identifier matches the identifier of the data item to be extracted, the data piece in the main memory 31 indicated by the record is a scalable decoder ( 4) is sent to. Since the auxiliary memory is penetrated starting with a high significance value, the data pieces are extracted on the right side, so that the decoder 4 performs good restoration.

To delete a data item, the records in auxiliary memory 30 are processed, and if the object identifier matches the identifier of the deleted data item, then the significant value of the record is any value that can be generated by the coder, i.e., zero. It is set to (predetermined) values. Preferably, the identifier is set to a (predetermined) value, such as 0, to indicate that the memory portion is not allocated to the data piece. The records in the auxiliary memory 30 are rearranged in order of significance, ie to restore the records of low significance to be placed at the end.

It is preferable to use the auxiliary memory 30. However, it is also possible to omit the auxiliary memory. In this case, the significant value of the data piece to which the data item belongs and the identifier must be stored in the main memory. Since pointers to data pieces arranged in order of significance are not available, it takes a long time to search main memory 31. In order to reduce the seek speed, the data pieces can be arranged in main memory at the expense of switching large amounts of data. In addition, content addressable memory can be used to execute the auxiliary memory, thereby eliminating the need for alignment and searching in the auxiliary memory by individual processors. Moreover, advanced data structures, such as generally known heaps or trees, can be used to perform management functions as an alternative to the desired auxiliary memory data structure. These alternatives may be particularly advantageous for large software portions, for example in software (or hardware with sufficient clock cycles available).

In a preferred embodiment of the present invention, any additional information is stored for each data item. The additional information may include name, information type, color, size, and the like. Such additional information may be stored in main memory, for example together with the first piece of data. Preferably, the additional information is stored in the auxiliary memory which can easily retrieve the additional information.

In addition to rate-distortion theory as well as scalable coding schemes, the first must transmit / store the bits that have the greatest impact when reducing distortion in reproduction made by the decoder. The distortion measure used is application dependent and typically uses other measures for video and audio, for example. However, all these distortion measurements correspond to the quality of the video / audio object sensed by the consumer during playback. The provision of these measurements is independent of the specific application.

The calculation of the significance of the present invention is discussed in connection with the calculation method included in European Patent Application No. 00200890.2 (our reference number PHNL000110). This method is designed to optimize the overall rate-distortion performance of the storage, ie to ensure low overall distortion of the stored media items. The method uses other distortion measures associated with the individual data pieces of the data item. In particular, the significance value is calculated by the encoder and is formally defined as follows:

[Equation 1]

Here, index i refers to a given object and index k represents the number of encoded blocks available at the encoder. Thus, D _i , _k-1 represents the distortion of reproduction when k-1 blocks following are received, and D _i , _k represents the reproduction distortion after k blocks are received. R _i , _k-1 represents the rate, that is, the total number of bits used for blocks following k-1, and R _i , _k represents the number of bits used for k blocks. D _i , ₀ is the initial distortion at the decoder when no bits are transmitted, and R _i , ₀ is the number of bits when no bits are transmitted, i.e., R _i , ₀ = 0. When all blocks in main memory have the same size, partitioning by block size is a constant partition and is preferably omitted as follows:

[Equation 2]

Thus, the significance value represents the distortion reduction achieved by adding the k-th block. This significance calculation method maximizes the overall rate-distortion performance of the storage medium to ensure low overall distortion of the stored data items.

One embodiment of the present invention provides an alternative method of calculating a significance value based on or representing the total or absolute distortion of a media item after the significant value for each block has decoded all data blocks comprising the current data block. use. Thus, given any distortion measure that can be calculated by the encoder, the significance value can be formally defined as follows.

[Equation 3]

S _{i, k} = D _{i, k}

Here, index i refers to a given object and index k represents the number of encoded blocks available at the decoder. Thus, D _i , _k represents reproduction distortion when k next blocks are received, and D _i , ₀ is the initial distortion at the decoder when no bits are transmitted.

An advantageous embodiment of the invention for maximizing the minimum item quality relates to a simple modification of the block significance value. Minimum image quality is second only to average quality because it provides the user with a guaranteed quality for each individual image. In addition, the overall image quality feeling / satisfaction is often determined by the lowest quality image. This is because the artifacts can be seen first or for the most part in a particular image. Instead of always reducing the quality of the media with the highest quality at present, a predictive power of one quality reduction step is used, each time the media item has the highest remaining quality after the next block of data has been removed from the media item. Will be reduced to quality. By taking into account the quality loss caused by eliminating the next data block, this embodiment provides good control of individual item quality and ensures the highest minimum item quality. Basically, the significance value for each block is the resulting absolute distortion of the media when the block is removed. All operations on the memory remain constant. In this example, the significance value is defined as follows:

[Equation 4]

S _{i, k} = D _{i, k-1}

Although no additional modifications are required to implement the new method, this implementation does not require the significance of the "next" block for each item in calculating the quality, so the actual quality for each item is obtained directly. However, there is no case where the blocks have already been overwritten or the item is completely stored. In fact, when compared with the distortion values used by the method of the previous embodiment, the current significant value is shifted down to one position of the next block, so that the last distortion value at the end of the chain is lost. In order to solve this problem (e.g., at least necessary for research purposes in order to generate PSNR values), it is satisfactory to store and update the "last" distortion value for each item during the memory operation. Optionally, instead of making the above modifications to memory operations, it is possible to store additional "lossy" distortion values for each block. This method is slightly less efficient in terms of memory usage (although the additionally required memory is negligible compared to the actual compressed data memory). Therefore, such a method is included in this embodiment.

Another method is the quality of the data after removal of the data piece with the lowest absolute distortion (lowest block of a given data item), using the full or absolute distortion of the data item up to and including the data piece according to equation (3). To determine the significance value of the current data piece to be removed, S _i , _k = D _i , _k , instead of checking _k , the significance value of the next data piece (one piece with low distortion) S _i , _k-1 = D _i , _k-1 is checked. In this way, the actual quality for each item remains available.

An example of distortion measurement often used in images / videos is a second order error measurement, which is the sum of squared pixel value differences between the original image and its reproduction. This secondary error measurement can be used as distortion measurement in the present invention. After encoding block k, the encoder must theoretically recalculate the error for each pixel of the image to obtain D _k , but in practice simple / easy methods of this calculation are usually possible.

In a practical embodiment, a certain number is added to the significance value of the first data piece of each data item number after reception so that the first data piece of each data item is not normally overwritten. This has the advantage that one piece of data is always kept in memory, which can represent a data item such as a "concise" image for each data item. For example, to prevent the first block of items from being overwritten, the significant value of the first block is set to a "infinite value", that is, a constant value greater than any distortion that may occur for other blocks in memory. In a practical embodiment, the value 2 ³¹ is used as a constant and the distortion values are absolute constant errors. The constant 2 ³¹ is large enough for images of 768x512 pixels, but must be increased for large image sizes (eg, up to 2 ³⁹ or 2 ⁴⁷ ). Instead of increasing the constant, it is possible to scale below the distortion values (by dividing the distortion values into other constant values, such as 2 ⁸ or 2 ¹⁶ ).

In EP00200890.2, difficulty arises when the sequence for data pieces of a scalable coded data item does not have a strictly reduced distortion difference. In practice, this requires the processing of block significance values so that subsequent blocks in the bit string have lower distortion reduction than the initial blocks (ie, the actual rate-distortion is convex). This convex constraint is not required for the present invention because it requires that the total media item distortion is reduced for each additional block in the sequence.

In another embodiment, the combination of the method of the present invention and the method of EP00200890.2 provides that the significance value is a weighted sum of the distortion difference value of EP00200890.2 and the total or absolute distortion value of the present invention.

It is possible to combine and store other types of objects, such as audio and video, in memory using suitably weighted perceptual significance measurements and / or suitably selected block sizes.

Advantageous use of the invention is made in an application using fixed storage for storing compressible data such as video, images, audio, voice and the like. As data items always attempt to have the highest possible data quality, an unknown / variable amount of data must be stored and / or approximately the same quality is maintained between the data items.

Examples of advantageous embodiments are as follows:

Digital still camera. The first image can be stored in high quality. The next pictures are stored in the fixed memory while replacing some of the data of the previous pictures. According to the total number of pictures in the memory, any quality of the pictures is achieved. The more images, the lower the average quality. In doorbell applications, an image can be taken every time someone pushes the button on the doorbell.

Response machine / voice mail. The audio data item stores an audio data item for each person calling and leaving a message. When the memory is completely used, new audio items can be stored by reducing the quality of already stored audio items.

Video recorder. A new feature provided in the video recorder is, for example, variable recording time. One application is the ability to store more related programs at a lower quality instead of recording a program because the storage capacity of the tape or disk is used in its entirety.

PIP playback. The user instructs the PIP playback period of an arbitrary program by, for example, pressing a button while watching TV. Since a given PIP-memory has a fixed capacity, the user can exchange the quality and duration of PIP playback.

Buffer control for onboard image memory. The entire image is subdivided into parts that are individually coded using scalable coding techniques. The individual parts are divided into blocks and entered into the memory. The advantage of this new method is that small memory is required for the same image quality or good image quality is obtained for the same memory size. (The conventional method encodes (and stores) the entire image first before combining the individual parts. Optionally, a predetermined number of bits are assigned to each part of the image, but this is a suboptimal method).

All these embodiments are preferably provided with any kind of quality indicator to the user.

It should be noted that the foregoing embodiments do not limit the invention and that those skilled in the art can design many alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The term "comprises" does not exclude the presence of elements or steps other than those listed in the claims. The invention can be implemented by means of hardware comprising several individual elements and by a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The simple fact that any measurements are cited in the different dependent claims does not indicate that a combination of these measurements cannot be used to advantage.

In summary, data items are stored in memory, the data items are divided into successive data pieces that increase the significance value, the data pieces are stored in respective parts of the memory, and when all data pieces are applied to the memory, Candidate memory portions are allocated to other data pieces; If the significance value of the authorized data piece is lower than the low significance value of other data pieces, the applied data piece is ignored. If the significance value of the authorized data piece is higher than the low significance value, it is lower than the significance value of the authorized data piece. Align the data piece applied to one of the candidate memory parts at the cost of another given data piece with a significant value. Preferably, for each data feed, a record is maintained that includes the data item to which the data piece belongs and the significance of the data piece. Data items are preferably coded by a scalable coding mechanism. The scalable bit-stream is truncated into pieces of data having a size equal to the size available in memory. Next, for each of these small pieces, a significance value is calculated. The significance value is calculated as a total or absolute distortion value that represents the total distortion for successive blocks of the data item containing the current block. The significance value is used to compare the data pieces of the new item with the already stored data pieces. Since scalable coding methods produce most significant bits, it can be readily understood that the data pieces generated by dividing the scalable bit-stream have the property of decreasing significance. Then, the data pieces of the new item are compared to the data pieces already in memory. When new data pieces have a high significance value, previously stored data pieces are overwritten. Advantageous use of the invention is made in an application using a fixed storage device for storing a predetermined number of compressible data items such as video, images, audio and voice.

Claims (11)

Method for storing data items in the memory (3), Dividing each data item into successive data pieces of decreasing significance, Storing the data pieces in respective portions of the memory 31; When all candidate memory portions have been allocated to other data pieces, when applying a data piece to the memory 31, If the significance value of the applied data piece is lower than the lowest significance value of the other data pieces, discarding the applied data piece; If the significance value of the applied data piece is higher than the lowest significance value of the other data pieces, one of the candidate memory portions is sacrificed at the expense of another given data piece having a significance value lower than the significance value of the applied data piece. Storing the authorized data piece, The significance value of each data piece is based on total or absolute distortion of the data item in the data piece. The method of claim 1, And wherein the total or absolute distortion is the total or absolute distortion of the data item up to and including the data piece. The method of claim 1, And wherein the total or absolute distortion is the total or absolute distortion of the data item up to the data piece but not including the data piece. The method of claim 1, For each data piece, a record (30) is maintained comprising a significant value (S) of the data piece and a data item (I) to which the data piece belongs. The method of claim 4, wherein The data items are stored in main memory 31, the record is held in auxiliary memory 30, and each record is a pointer P indicating a position in the main memory 31 in which a given piece of data is stored. Further comprising). The method of claim 1, The significance value of each data piece comprises a weighted sum of the distortion difference value for the data piece and the total distortion of the data item in the data piece. The method of claim 1, The significance value of the first data piece of each data item is increased. CLAIMS 1. A method for reading data items from memory (3), comprising dividing data items into successive data pieces of decreasing significance, storing the data pieces in respective memory portions (31), wherein A method for reading data items from a memory, wherein an indication of a significance value of a data piece is available in a memory, the method comprising: Reading the consecutive data pieces from the memory 31 for each data item, wherein the data pieces belong to the data item; Constructing (4) the data item from the consecutive data pieces, The significance value of each data piece is based on total or absolute distortion of the data item in the data piece. In the device for storing data items in the memory (3), Means for dividing each data item into successive data pieces of decreasing significance, Means for storing the data pieces in respective portions of the memory 31; Means for applying a piece of data to said memory (31), The applying means, if all candidate memory portions are allocated to different data pieces, If the significance value of the applied data piece is lower than the lowest significance value of the other data pieces, discard the applied data piece, If the significance value of the applied data piece is higher than the lowest significance value of the other data pieces, one portion of the candidate memory portions at the expense of another given data piece having a significance value lower than the significance value of the applied data piece. Store the applied data piece at And the significance value of each data piece is based on total or absolute distortion of the data item in the data piece. A device for reading data items from memory (3), which divides the data items into successive data pieces of decreasing significance, stores the data pieces in respective memory portions 31, and stores the respective data. An apparatus for reading data items from a memory, wherein an indication of a significant value of a piece is available in the memory, wherein: Means for reading the consecutive data pieces from the memory 31 for each data item, the data pieces belonging to the data item; Means (4) for constructing the data item from the consecutive data pieces, And the significance value of each data piece is based on total or absolute distortion of the data item in the data piece. A storage medium 3 in which data items are stored, Dividing the data items into successive data pieces of decreasing significance, storing the data pieces in respective memory portions 31, and indicating an indication of the significance value of each data piece on the storage medium. And a significance value of each data piece is based on total or absolute distortion of the data item in the data piece.