Method and apparatus for shuffling image data into statistically averaged data groups and for deshuffling the data

• US 5,301,018 A
• Filed: 08/16/1993
• Issued: 04/05/1994
• Est. Priority Date: 02/13/1991
• Status: Expired due to Term

• Current Assignee: Ampex Corporation (Delta Information Systems, Inc.)
• Original Assignee: Ampex Corporation (Delta Information Systems, Inc.)
• Inventors: Smidth, Peter, Coleman, Charles H., Miller, Sidney D.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US08/106,968
• Time in Patent Office: 232 Days
• Field of Search: 358/141, 358/138, 358/140, 358/12, 358/433, 358/453, 358/457, 358/458, 358/160, 358/133, 358/135, 358/136, 358/13, 382/56
• US Class Current: 375/240.24
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/85 using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/88 involving rearrangement of data among different coding units, e.g. shuffling, interleaving, scrambling or permutation of pixel data or permutation of transform coefficient data among different blocks
• CPC Class Codes: H04N 19/98 Adaptive-dynamic-range coding [ADRC]
• CPC Class Codes: H04N 5/907 using static stores, e.g. storage tubes or semiconductor memories H04N5/91 takes precedence
• CPC Class Codes: H04N 5/9201 involving the multiplexing of an additional signal and the video signal
• CPC Class Codes: H04N 5/9264 using transform coding

Abstract

In a data compression process such as employed to compress video or other data, it is preferable not to compress the image data representative of the video image in a sequential format, or to take the data from the same area of the image. To equalize the information content of the data prior to compression, the present shuffling/deshuffling technique divides the video image into a multitude of image representing blocks, and selects a predetermined number of the image blocks from different spatial locations in the image, to form a succession of data sets representative of the video image information. That is, the selection of the image representing blocks is such that the information content (complexity) in each data set is similar to the information content in each other data set and further similar to the average information content of the entire video image. Thus, the subsequent quantizing factor used in the compression process will tend to be similar for successive data sets, thereby reducing any distortion introduced by the compression process. The image representing blocks may be formed of sequentially scanned blocks of the video image, or of transform coefficients representing similar blocks of the video image. The shuffled data is deshuffled by the inverse process.

Claims

1. A method of conditioning data representing an image for recording the data onto a recording medium or for transmitting the data over a channel, said method comprising the steps of:

dividing the image data into a multitude of contiguous image blocks, each image block being associated with a corresponding spatial location of a portion of said image and defining one or more characteristics of said portion at the respective spatial location; and

,

shuffling said image blocks by selecting image blocks from preselected spatially diverse locations in the image as determined by a block selection pattern, wherein combined preselected image blocks in the resulting shuffled image contain a spatially equalized distribution of the information contained in the image.

2. The method of claim 1 further comprising the steps of:

grouping said shuffled image blocks to form successive pluralities of shuffled image blocks.

3. The method of claim 1 wherein the step of shuffling further includes assembling a plurality of sets of data each formed of a selected plurality of image blocks.

4. The method of claim 3 wherein:

the step of dividing the image data further includes dividing the image data in equally sized image blocks arranged into a preselected plurality of rows and columns of said image blocks; and

the step of shuffling includes taking only one image block from any one row or column of said image blocks when grouping to form each of said sets of data.

5. The method of claim 3 wherein the data representing an image further includes video image data.

6. The method of claim 5 further including:

transforming the video image, prior to the step of dividing, to define image blocks of transform coefficients; and

assembling a plurality of sets of data formed of selected image blocks of transform coefficients representative of a statistical average of information in the transformed video image.

7. The method of claim 5 wherein the step of shuffling includes:

storing said plurality of image blocks in a shuffled order relative to the original locations of said image blocks in said video image; and

retrieving the stored and shuffled image blocks in a raster scan block-by-block order.

8. The method of claim 7 wherein:

the step of shuffling is defined by the algorithm;

space="preserve" listing-type="equation">(x,y)=4c+v mod 4, (17c+25v) mod 61,

wherein

x=the horizontal block index,

y=the vertical block index,

v=the set of data number

c=an output image block number within a set of data; and

,

the data representing an image further includes 525-line video image data.

9. The method of claim 8 wherein the step of assembling includes selecting 23 image blocks from different spatial locations in the video image to form a data set, and assembling 244 successive data sets to define the video image.

10. The method of claim 1 wherein the step of shuffling includes:

assembling said image blocks from the spatially diverse locations in the image into a stream of image blocks containing a spatially equalized distribution of the information in the image.

11. The method of claim 10 wherein the step of assembling includes:

grouping said shuffled image blocks to form a plurality of groups of assembled image blocks; and

digitally compressing the image data by separately compressing the data in each of said groups of assembled image blocks.

12. The method of claim 10 wherein random segments of said stream also contain the spatially equalized distribution of the information in the image.

13. The method of claim 10 wherein:

the step of dividing the image data further includes dividing the image data into equally sized image blocks arranged into a preselected plurality of rows and columns of said image blocks; and

the step of assembling includes taking only one image block from any one row or column of said image blocks to form said stream of image blocks.

14. The method of claim 10 wherein:

the data representing an image includes fields and frames of video image data; and

said stream of image blocks includes a field worth of video image data.

15. The method of claim 14 further including:

transforming the video image, prior to the step of dividing, to define image blocks of transform coefficients; and

assembling a stream of shuffled image blocks of transform coefficients containing a spatially equalized distribution of the information in the transformed video image.

16. The method of claim 14 wherein the step of assembling includes:

storing said field of image blocks in a sequential order corresponding to the original locations of said image blocks in said video image; and

retrieving the stored image blocks in a shuffled order.

17. The method of claim 14 wherein each image block comprises a group of (4×

8) pixels of a luminance component, and groups of (4×

4) pixels of chrominance components, of said video image.

18. A method for shuffling data defining at least a portion of a video image, wherein the information contained in the video image varies from more complex through less complex areas of the image, comprising the steps of:

representing said video image by a multitude of image blocks, each of which is associated with a corresponding spatial location of a contiguous portion of said video image and defines one or more characteristics of said portion at the respective spatial location; and

scrambling a minimum plurality of said image blocks by assembling preselected image blocks from said more complex areas of the image with image blocks from said less complex areas, to form a group of image blocks containing a statistical average of the video image information, wherein said scrambled group of image blocks define the shuffled data.

19. The method of claim 18 wherein:

the step of representing includes dividing the video image into a preselected array of said multitude of image blocks; and

the step of scrambling includes assembling a plurality of said groups of image blocks taken from non-contiguous spatial locations in the video image.

20. The method of claim 19 wherein the step of assembling includes:

selecting said groups of image blocks with all image blocks selected once, wherein each of said groups contain a statistically averaged sampling of the video image complexity.

21. The method of claim 19 wherein:

the step of representing includes dividing the video image into a preselected plurality of rows and columns of said image blocks; and

the step of scrambling includes taking only one image block from any one row or column of said image blocks when assembling each of said data sets.

22. The method of claim 19 further including:

transforming the video image prior to the step of dividing to define the preselected array in the form of image blocks of transform coefficients; and

assembling a plurality of groups of selected image blocks of transform coefficients representative of a statistical average of information in the transformed video image.

23. The method of claim 19 including:

storing said groups of image blocks in a shuffled order relative to the original locations of said image blocks in said video image; and

retrieving the stored and shuffled groups of image blocks in a raster scan block-by-block order.

24. The method of claim 19 further including deshuffling of the shuffled data, including the steps of:

storing the groups of image blocks of the shuffled data in a shuffled order; and

retrieving the stored deshuffled image blocks in a sequential order to provide the deshuffled data.

25. The method of claim 19 wherein the step of scrambling includes:

storing said plurality of groups of image blocks in the sequence that they are selected from the video image; and

retrieving the stored plurality of groups of image blocks in a shuffled sequence other than that used in the step of storing.

26. The method of claim 25 wherein the step of retrieving is defined by the algorithm:

space="preserve" listing-type="equation">(x,y)=4c+v mod 4, (17c+25v) mod 61,

wherein,

x=the horizontal block index,

y=the vertical block index,

v is a group number 0, 1, 2, . . . 243, and

c is an output image block number 0, 1, 2 . . . 22 within a group.

27. The method of claim 25 wherein the step of assembling includes selecting 23 image blocks from different spatial locations in the video image to form a data set, and assembling 244 successive data sets to define the video image.

28. The method of claim 19 wherein the step of assembling includes:

writing into memory means a first group of image blocks defining a field worth of video data;

writing into the memory means a second group of image blocks defining a second field worth of video data; and

reading the first group of image blocks from the memory means simultaneously while writing said second group of image blocks, wherein the image blocks of the first group are read out in an order other than that in which they were written.

29. An apparatus for shuffling data representing at least a portion of an image, comprising:

means for dividing the data representing the image into a preselected plurality of image representing blocks; and

means for assembling groups formed of the image representing blocks selected from non-contiguous spatial locations in the data image in accordance with a predetermined block selection algorithm which statistically averages the image information contained in the assembled groups.

30. The apparatus of claim 29 wherein said data representing the image are sequentially scanned image blocks formed of a plurality of pixels in the image.

31. The apparatus of claim 29 including:

means for transforming the image into image representing blocks of transform coefficients; and

wherein said data representing the image are formed of a succession of said image representing blocks of transform coefficients.

32. The apparatus of claim 29 wherein the assembling means includes:

means for storing said image representing blocks of said groups in an order corresponding to the original locations in said data image of the image representing blocks; and

means for retrieving said image representing blocks of said groups from said storing means in an order in which the image representing blocks are shuffled relative to their original locations in said image.

33. The apparatus of claim 29 wherein the assembling means includes:

means for storing said image representing blocks of said groups in an order in which the image representing blocks are shuffled relative to their original locations in said image; and

means for retrieving said image representing blocks of said groups from sequential memory locations in said storing means.

34. The apparatus of claim 29 wherein:

said dividing means includes means for dividing the image into a multitude of said image representing blocks, each having a respective spatial location in the image; and

said assembling means includes means for storing the image representing blocks in a sequentially scanned order, and means for retrieving the stored image representing blocks in a predetermined shuffled order which provides successive groups of blocks of statistically averaged image information.

35. The apparatus of claim 34 wherein the image representing blocks of each group are retrieved in accordance with the algorithm:

space="preserve" listing-type="equation">(x,y)=4c+v mod 4, (17c+25v) mod 61,

where,

x=the horizontal block index,

y=the vertical block index,

v is a group number 0, 1, 2, . . . 243, and,

c is an output image block number 0, 1, 2 . . . 22 within a group.

36. The apparatus of claim 34 wherein the assembling means includes:

means for providing a timing signal related to the sequentially scanned order of the image;

memory means responsive to said providing means for alternately storing selected groups of the image representing blocks in said sequentially scanned order; and

readout means responsive to said providing means for alternately retrieving said selected groups of stored image representing blocks in said predetermined shuffled order.

37. The apparatus of claim 36 further including:

write address generator means coupled to said memory means for supplying thereto a write address for storing the image representing blocks in shuffled memory locations which statistically average the image information in the subsequently recovered groups; and

read address generator means coupled to said memory means for supplying thereto a read address which retrieves the image representing blocks of each group from sequential memory locations.

38. The apparatus of claim 36 further including:

write address generator means coupled to said memory means for supplying thereto a sequential write address; and

read address generator means coupled to said memory means for supplying thereto a read address which retrieves the stored image representing blocks in a selection pattern which statistically averages the image information contained in successive groups.

39. The apparatus of claim 34 for further deshuffling the data representing at least a portion of the image, comprising:

means for recovering the shuffled data as a stream of successive groups formed of the shuffled image representing blocks;

means for storing the recovered stream of image representing blocks in the predetermined shuffled block order; and

means for retrieving the deshuffled stored image representing blocks in the sequential order, to provide the deshuffled data.

40. The method for shuffling data representative of an image, comprising the steps of:

dividing said data representative of the image into a multiplicity of image representing blocks of random complexities and having respective spatial locations within the image; and

assembling groups of selected pluralities of said image representing blocks taken from predetermined non-contiguous spatial locations in the image such that all the image blocks in the image are selected once and each group of image representing blocks contains statistically averaged information substantially similar to the statistical average of the information contained in the image.

41. The method of claim 40 including:

determining quantizing parameter values for said groups which provide a substantially consistent compression of the data contained in the assembled statistically averaged groups; and

adjusting the step of assembling in response to inconsistencies in the quantizing parameter values determined by the step of determining.

42. The method of claim 41 wherein:

the step of assembling includes selecting the image representing blocks in accordance with a predetermined algorithm; and

the step of adjusting includes modifying the predetermined shuffling order to maximize the uniformity of the statistically averaged information content of the shuffled data sets.

43. A method of shuffling data representing an image, comprising the steps of:

dividing the data representing the image into a multiplicity of contiguous image blocks of random complexities ranging from high to low complexities, and having respective spatial locations within the image; and

assembling a stream of said image blocks selectively derived in accordance with a predetermined algorithm, to combine non-contiguous image blocks of said high to low complexity from locations throughout the image such that the statistical average of the information contained in a random, statistically significant plurality of image blocks in said stream is substantially the same as the statistical average of the information contained in the image.

44. The method of claim 43 wherein the data includes fields and frames of video image data, wherein:

said step of dividing includes electronically dividing the video image into an array of the image blocks; and

said step of assembling includes selecting the non-contiguous image blocks from throughout the array to form a field worth of shuffled image blocks.

45. The method of claim 43 wherein:

said step of dividing includes electronically dividing the data image into a selected array of the image blocks; and

said step of assembling includes selecting all image blocks in the array once to assemble the selected stream of image blocks.

46. The method of claim 43 for further deshuffling data which is being recovered as the stream of the selected pluralities of shuffled image blocks representative of the image, comprising the steps of:

storing the assembled image blocks in the shuffled order; and

retrieving the stored deshuffled image blocks in a sequential order, to deshuffle the data.