US5301018A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for shuffling image data into statistically averaged data groups and for deshuffling the data
Assignee: Ampex Corp
•
Filing: 1993-08-16
•
Granted: 1994-04-05
•
Expires: 2013-08-16
Abstract
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.
Inventors
- 👤 Peter Smidth
- 👤 Charles H. Coleman
- 👤 Sidney D. Miller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 22:25
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/12; H; H04; H04N; H04N5/00; H04N5/76; H04N5/91; H04N5/92; H04N5/9201; H04N19/00; H04N19/10; H04N19/102; H04N19/124; H04N19/134; H04N19/136; H04N19/14; H04N19/169; H04N19/17; H04N19/176; H04N19/60; H04N19/85; H04N19/88; H04N19/90; H04N19/98; H04N5/907; H04N5/926; H04N5/9261; H04N5/9264; H04N19/146; H04N19/149; H04N19/15
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
117 words
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.
Claim 2
Independent Claim
117 words
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.
Claim 3
Dependent Claim
23 words
The method of claim 1 further comprising the steps of: grouping said shuffled image blocks to form successive pluralities of shuffled image blocks.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
68 words
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.
Claim 6
Dependent Claim
16 words
The method of claim 3 wherein the data representing an image further includes video image data.
Claim 7
Dependent Claim
52 words
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.
Claim 8
Dependent Claim
48 words
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.
Claim 9
Dependent Claim
57 words
The method of claim 7 wherein: the step of shuffling is defined by the algorithm: (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.
Claim 10
Dependent Claim
39 words
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.
Claim 11
Dependent Claim
40 words
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.
Claim 12
Dependent Claim
46 words
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.
Claim 13
Dependent Claim
23 words
The method of claim 10 wherein random segments of said stream also contain the spatially equalized distribution of the information in the image.
Claim 14
Dependent Claim
65 words
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.
Claim 15
Dependent Claim
33 words
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.
Claim 16
Dependent Claim
48 words
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.
Claim 17
Dependent Claim
44 words
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.
Claim 18
Dependent Claim
31 words
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.
Claim 19
Independent Claim
136 words
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.
Claim 20
Independent Claim
136 words
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.
Claim 21
Dependent Claim
49 words
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.
Claim 22
Dependent Claim
38 words
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.
Claim 23
Dependent Claim
55 words
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.
Claim 24
Dependent Claim
56 words
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.
Claim 25
Dependent Claim
45 words
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.
Claim 26
Dependent Claim
46 words
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.
Claim 27
Dependent Claim
53 words
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.
Claim 28
Dependent Claim
60 words
The method of claim 25 wherein the step of retrieving is defined by the algorithm: (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.
Claim 29
Dependent Claim
39 words
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.
Claim 30
Dependent Claim
90 words
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.
Claim 31
Independent Claim
69 words
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.
Claim 32
Independent Claim
69 words
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.
Claim 33
Dependent Claim
25 words
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.
Claim 34
Dependent Claim
38 words
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.
Claim 35
Dependent Claim
71 words
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.
Claim 36
Dependent Claim
58 words
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.
Claim 37
Dependent Claim
74 words
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.
Claim 38
Dependent Claim
65 words
The apparatus of claim 34 wherein the image representing blocks of each group are retrieved in accordance with the algorithm: (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.
Claim 39
Dependent Claim
71 words
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.
Claim 40
Dependent Claim
72 words
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.
Claim 41
Dependent Claim
60 words
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.
Claim 42
Dependent Claim
73 words
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.
Claim 43
Independent Claim
94 words
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.
Claim 44
Independent Claim
94 words
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.
Claim 45
Dependent Claim
50 words
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.
Claim 46
Dependent Claim
48 words
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.
Claim 47
Independent Claim
110 words
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.
Claim 48
Independent Claim
110 words
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.
Claim 49
Dependent Claim
58 words
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.
Claim 50
Dependent Claim
46 words
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.
Claim 51
Dependent Claim
56 words
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.
References Cited (Backward Citations)
US4175270A
Cited
US3795763A
Cited
US3803348A
Cited
US4068258A
Cited
US4023199A
Cited
US4025950A
Cited
US4204227A
Cited
US4394774A
Cited
US4302775A
Cited
US4383272A
Cited
US4504860A
Cited
US4447886A
Cited
US4541012A
Cited
US4494144A
Cited
US4580134A
Cited
US4698694A
Cited
US4682248A
Cited
US4656511A
Cited
US4672467A
Cited
US4654696A
Cited
US4694336A
Cited
US4775897A
Cited
US4743960A
Cited
US4626829A
Cited
US4797741A
Cited
US4768082A
Cited
US4802003A
Cited
US4783841A
Cited
US4837724A
Cited
US4740832A
Cited
US4679094A
Cited
US4862167A
Cited
US4774562A
Cited
US4764805A
Cited
US4758881A
Cited
US4868653A
Cited
US4847677A
Cited
US4849807A
Cited
US4857991A
Cited
US4941044A
Cited
US5031038A
Cited
US5136371A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-04-04 | 1997-10-04 | 1998-04-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-04-04 | 2001-10-04 | 2002-04-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-04-04 | 2005-10-04 | 2006-04-05 | $7700.00 | Window Closed / Lapsed |