IMAGE DATA PROCESSING

• US 20100014590A1
• Filed: 08/11/2006
• Published: 01/21/2010
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: RGB Systems Incorporated
• Original Assignee: Electrosonic Limited (Helectron Oy Ab)
• Inventors: Smith, Peter Lionel
• Granted Patent: US 9,204,170 B2
• Time in Patent Office: Days
• US Class Current: 375/240.190
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/174 the region being a slice, e.g. a line of blocks or a group of blocks
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/1883 the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• CPC Class Codes: H04N 19/33 in the spatial domain
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/423 characterised by memory arrangements H04N19/433 takes precedence
• CPC Class Codes: H04N 19/507 using conditional replenishment
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/645 by grouping of coefficients into blocks after the transform
• CPC Class Codes: H04N 19/647 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/66 involving data partitioning, i.e. separation of data into packets or partitions according to importance
• CPC Class Codes: H04N 19/68 : involving the insertion of resynchronisation markers into the bitstream
• CPC Class Codes: H04N 19/70 : characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/86 : involving reduction of coding artifacts, e.g. of blockiness
• CPC Class Codes: H04N 19/89 : involving methods or arrangements for detection of transmission errors at the decoder
• CPC Class Codes: H04N 19/91 : Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/96 : Tree coding, e.g. quad-tree coding

Abstract

Methods of spatial compression of image data using trees formed with logic gates are described. Data encoding is achieved using a five-level wavelet transform, such as the Haar or 2/10 transforms. A dual transform engine is used, the first engine being used for the first and second parts of the first-level transform, and the subsequent-level transforms being performed by the second engine within a time not more than that taken by the first transform engine to effect the part-transform. Each bit plane of the resulting coefficients is then encoded by forming a tree structure from the bits and logical OR combinations thereof. Redundant data are removed. Further data can be removed with a predetermined compression profile. The resulting blocks of compressed data are of variable length and are packaged with sync and index words for transmission so that the location and identity of the transformed data blocks can be determined.

Claims

1. A method of encoding an input sequence of data bits by forming a tree structure, the method comprising:

(a) forming groups of data bits from the input sequence of data bits and logically combining the data bits within each group to form a sequence of first-stage logic output bits;

(b) repeating step (a) iteratively, by forming groups of logic output bits from the first-stage logic output bits and logically combining logic output bits within each group to form a sequence of intermediate logic output bits, until there is a single final logic output bit; and

(c) generating an encoded output bit stream comprising said final logic output bit and any or all of the logic output bits and any or all of the data bits of the input data sequence, in dependence on at least a first exclusion condition that, if a given logic output bit is equal to a first predetermined value, which uniquely defines the data bits and any logic output bits which have been used to generate said given logic output bit, then said uniquely-defined data bits and said uniquely-defined logic output bits are excluded from said output bit stream, wherein

the input sequence of data bits comprises one of a plurality of rows of bits which collectively define a bit plane of a block of image data which has been transformed in accordance with a wavelet transform, a bit plane being defined as a plane formed from the respective bits of equal significance with the transformed block of image data.

2. A method as claimed in claim 1, wherein the data bits and the logic output bits are so combined using a logical OR combination, and wherein the first predetermined value is 0.

3. A method as claimed in claim 2, where it is expected that the number of data bits in the sequence which are equal to 0 will be sufficiently more than the number of data bits which are equal to 1, such that the resulting encoded output bit stream comprises fewer bits than the input sequence of data bits.

5. A method as claimed in claim 1, wherein steps (a) and (b) are applied to each of the rows of said bit plane, thereby generating, for each row, a respective single final logic output bit which constitutes a row output bit, the method further comprising forming a further row tree structure by:

(i) forming groups of said row output bits and logically combining the row output bits within each group to form a sequence of first-stage row logic output bits;

(ii) repeating step (i) iteratively, by forming groups of row logic output bits from the first-stage row logic output bits and logically combining the row logic output bits to form a sequence of intermediate row logic output bits, until there is only a single final row logic output bit;

and wherein the resulting output bit stream comprises;

said final row logic output bit;

any or all of the first-stage or intermediate row logic output bits; and

any or all of the row output bits,

in dependence on a second exclusion condition that, if a given row logic output bit is equal to said first predetermined value, which uniquely defines the row logic output bits and any row output bits which have been used to generate said given logic output bit, then said uniquely-defined row logic output bits and said uniquely-defined row output bits are also excluded from said output bit stream.

6. A method as claimed in claim 5, wherein each group of said row output bits comprises five row output bits.

7. A method as claimed in claim 5, wherein not all of the row output bits are formed into groups, and the non-grouped row output bits are combined with other row logic output bits within the row tree structure.

8. A method as claimed in claim 7, wherein the resulting output bit stream additionally comprises some or all of the non-grouped row output bits, in dependence on an additional exclusion condition that, for each non-grouped row output bit, if the row logic output bit, which results from the logical combination of that non-grouped row output bit with the other row logic output bits with which they are combined in the row tree structure, is not equal to said first predetermined value, then that non-grouped row output bit is excluded from the output bit stream, but all of the intermediate logic output bits which were logically combined to form that non-grouped row output bit are included.

9. A method as claimed in claim 5, wherein the transformed block of image data has been transformed using a multi-level wavelet transform, and the row output bits are grouped in step (i) in accordance with the level of the transform to which they relate.

10. A method as claimed in claim 9, wherein only the row output bits of the first and second levels are grouped together in step (i).

11. A method as claimed in claim 10, wherein the row output bits of the third level are grouped with the first-stage row logic output bits.

12. A method of encoding a transformed image data block which comprises an array of transformed image coefficients configured as a plurality of bit planes, by forming the data bits from each of said bit planes as a respective sequence of data bits and applying a method in accordance with claim 5 to the bit sequences of each bit plane, starting with the most significant bit plane and ending with the least significant, so as to derive an encoded output bit stream representing the entire transformed data bock.

13. A method as claimed in claim 12, wherein the transformed image data block additionally comprises a bit plane in which the signs of the transformed image data have been encoded, and wherein the method further comprises incorporating in said output bit stream bits representing the respective signs associated with the most significant data bit of each of the transformed image coefficients.

14. A method as claimed in claim 12, subject to a further exclusion condition that, for each logic value which is equal to a second predetermined value, the corresponding logic values in the same position within the corresponding row tree structure associated with each succeeding bit plane are excluded from the encoded output bit stream, but wherein the logic values or data bits immediately preceding said corresponding logic values are retained, even if they would otherwise have been excluded by said first exclusion condition.

15. A method as claimed in claim 14, wherein the second predetermined value is 1.

16. A method as claimed in claim 12, wherein the encoded output bit stream is additionally subject to a compression exclusion condition in which bits occupying predetermined positions within the or each tree structure are excluded from said encoded output bit stream in accordance with a predetermined compression profile.

17. A method as claimed in claim 16, wherein said compression profile is defined for each of said bit planes and serves to exclude a greater number of bits from the bit planes of lower significance than those from the bit planes of greater significance.

19. A method as claimed in claim 13, wherein said output bit stream comprises, for each bit plane in sequence starting with the bit plane of greatest significance and ending with the bit plane of least significance:

the non-excluded row output bits, followed in sequence by;

(a) the row logic output bits;

(b) the non-excluded intermediate logic output bits; and

(c) the non-excluded data bits.

20. A method as claimed in claim 19, wherein said output bit stream further comprises, for each bit plane:

(d) said bits representing the respective signs associated with the most significant data bit of each of the transformed image coefficients.

21. A method of decoding a bit stream which has been encoded using a method as claimed in claim 1, the method comprising regenerating the bits which have been excluded by said or each exclusion condition, thereby to recreate the original input sequence of data bits from which the bit stream has been encoded.

84. A method as claimed in claim 1, wherein the encoded output bit stream is additionally subject to a compression exclusion condition in which bits occupying predetermined positions within the or each tree structure are excluded from said encoded output bit stream in accordance with a predetermined compression profile.

85. A method as claimed in claim 84, wherein said compression profile serves to exclude a greater number of row logic output bits generated in earlier stages of step (ii) than those generated in the later stages thereof.

4. (canceled)

18. (canceled)

22. A method of preventing the creation of blocking artefacts during the transformation of image data, the method comprising:

receiving an original set of data relating to an image in the form of an array of adjoining blocks; and

processing the data of each block, together with data of each immediately adjacent block within the array, in accordance with a predetermined transformation algorithm, thereby to create a respective block of transformed data which is substantially devoid of block boundary artefacts.

23. A method as claimed in claim 22, further comprising the step of compressing the transformed data in each of said blocks separately.

24. A method as claimed in claim 23, further comprising transmitting sequentially the blocks of compressed data.

25. A method as claimed in claim 24, further comprising receiving the transmitted bocks of compressed data and sequentially decompressing each block to recreate said transformed data.

26. A method as claimed in claim 25, further comprising processing said recreated transformed data in accordance with a reverse algorithm so as to recreate the original set of data.

27. A method as claimed in claim 22, wherein said original set of data constitute the pixels of an entire frame of an image signal.

28. A method as claimed in claim 27, wherein each block comprises 1,024 pixels.

29. A method of recreating an original set of data relating to an image in the form of an array of adjoining blocks which has been processed in accordance with a method as claimed in claim 22 to create blocks of transformed data, the method comprising processing each block of transformed data in accordance with an algorithm which is an inverse of said predetermined transformation algorithm, thereby to recreate the data of each block, together with data of each immediately adjacent block within the array, and combining the resulting processed blocks thereby to recreate the original image.

30. A method as claimed in claim 22, wherein the predetermined transformation algorithm comprises a wavelet transform.

31. A method as claimed in claim 30, wherein said wavelet transform is the 2/10 transform.

32. A method of performing a first transformation on each of a first and a second data group to generate first and second transformed data groups respectively, and performing a plurality of subsequent transformations on each of the first and second transformed data groups, the method comprising, in sequence:

performing said first transformation on said first data group using a first transform engine; and

performing all of said subsequent transformations on said transformed first data group using a second transform engine within a time interval which at least partly overlaps a time interval within which said first transform engine performs said first transformation on said second data group.

33. A method as claimed in claim 32, wherein the time taken to perform all of said subsequent transformations on a transformed data group is less than or equal to the time taken to perform the first transformation thereon.

34. A method as claimed in claim 32, further comprising storing the transformed data resulting from each transformation on said first data group in a first memory storage area, and storing the transformed data resulting from each transformation on said second data group in a second memory storage area.

35. A method as claimed in claim 34, applied to a plurality of further data groups, comprising storing the transformed data resulting from each transformation on the or each further odd-numbered data group in said first memory storage area, and storing the transformed data resulting from each transformation on the or each further even-numbered data group in said second memory storage area.

36. A method as claimed in claim 34, wherein after each of said subsequent transformations the resulting transformed data are stored in their respective memory storage area so as to overwrite at least some of the data already stored therein resulting from one or more previous transformations.

48. A method as claimed in claim 32, wherein the plurality of transformations comprise a multi-level wavelet transform.

49. A method as claimed in claim 48, wherein the multi-level wavelet transform comprises the Haar wavelet transform.

50. A method as claimed in claim 48, wherein the multi-level wavelet transform comprises the 2/10 wavelet transform.

51. A method as claimed in claim 32, wherein each data group comprises a frame of image data.

52. A method of performing a plurality of reverse transformations on first and second data groups which have been transformed in accordance with a method as claimed in claim 32, the method comprising, in sequence:

performing all but the last one of the reverse transformations on said first transformed data group using a first reverse transform engine;

performing the last reverse transformation on said first transformed data group using a second reverse transform engine within a time interval which at least partly overlaps a time interval within which said first reverse transform engine performs all but the last one of the reverse transformations on said second transformed data group.

53. A method as claimed in claim 52, wherein the time taken to perform said all but the last one of the reverse transformations on said first transformed data group is less than or equal to the time taken to perform the last reverse transformation on said first data group.

37. A method of performing a plurality of transformations on first and second data groups, the method comprising, in sequence:

(a) performing a first transformation on said first data group using a first transform engine, so as to generate a first once-transformed data group;

(b) storing said first once-transformed data group in a first memory storage area;

(c) reading said first once-transformed data group from said first memory storage area;

(d) performing a second-stage transformation thereon using a second transform engine, thereby generating a first twice-transformed data group; and

(e) writing said first twice-transformed data group into said first memory storage area so as to overwrite said first once-transformed data group;

the method further comprising, in sequence;

(f) performing said first transformation on said second data group using said first transform engine, so as to generate a second once-transformed data group;

(g) storing said second once-transformed data group in a second memory storage area;

(h) reading said second once-transformed data group from said second memory storage area;

(i) performing said second-stage transformation thereon using said second transform engine, thereby generating a second twice-transformed data group; and

(j) writing said second twice-transformed data group into said second memory storage area so as to overwrite said second once-transformed data group;

wherein step (f) commences after the completion of step (a) but before the completion of step (e).

38. A method as claimed in claim 37, wherein step (f) commences before the completion of step (c).

39. A method as claimed in claim 37, wherein steps (a) to (j) are repeated using a multiplicity of data groups, wherein steps (a) to (e) are applied to odd-numbered data groups and steps (f) to G) are applied to even-numbered data groups.

40. A method as claimed in any one of claims 37, further comprising, in sequence, after step (e):

(e₁) reading a sub-group of said first twice-transformed data group from said first memory storage area;

(e₂) performing a third-stage transformation thereon using said second transform engine, thereby generating a first three-times-transformed data sub-group; and

(e₃) writing said first three-times-transformed data sub-group into said first memory storage area so as to overwrite said sub-group of said first twice-transformed data group;

and, after step (j);

(j₁) reading a sub-group of said second twice-transformed data group from said second memory storage area;

(j₂) performing a third-stage transformation thereon using said second transform engine, thereby generating a second three-times-transformed data sub-group; and

(j₃) writing said second three-times-transformed data sub-group into said second memory storage area so as to overwrite said sub-group of said second twice-transformed data group.

41. A method as claimed in claim 40, wherein the time taken to perform the combination of steps (c) to (e₃) is less than or equal to the time taken to perform step (a), and the time taken to perform the combination of steps (h) to (j₃) is less than or equal to the time taken to perform step (f).

42. A method as claimed in claim 40, further comprising, in sequence, after step (e₃):

(e₄) reading said first three-times-transformed data sub-group from said first memory storage area;

(e₅) performing a fourth-stage transformation thereon using said second transform engine, thereby generating a first four-times-transformed data sub-group;

(e₆) writing said first four-times-transformed data sub-group into said first memory storage area so as to overwrite said first three-times-transformed data sub-group;

and, after step (j₃);

(j₄) reading said second twice-transformed data group from said second memory storage area;

(j₅) performing a fourth-stage transformation thereon using said second transform engine, thereby generating a second four-times-transformed data sub-group; and

(j₆) writing said second four-times-transformed data sub-group into said second memory storage area so as to overwrite said second three-times-transformed data sub-group.

43. A method as claimed in claim 42, wherein the time taken to perform the combination of steps (c) to (e₆) is less than or equal to the time taken to perform step (a), and the time taken to perform the combination of steps (h) to (j₆) is less than or equal to the time taken to perform step (f).

44. A method as claimed in claim 42, further comprising repeating steps (e₃) to (e₆) and steps (j₃) to (j₆) a plurality of times, using the transformed sub-groups stored in the respective memory storage areas, wherein each even-numbered transformation is performed on only a sub-group of the data stored in the memory and each odd-numbered transformation is performed on all of the data generated in the preceding even-numbered transformation step.

45. A method as claimed in claim 44, wherein the data groups are subjected to ten transformations.

46. A method as claimed in claim 45, wherein the time taken to perform all of the second and higher-levels transformations on each group of data is less than that taken to perform the first transformation.

47. A method as claimed in claim 44, wherein the first and second memory storage areas comprise respectively two storage areas of a double data rate memory.

54. A method of transmitting data comprising:

grouping the data into a sequence of frames comprising a first frame and at least one subsequent frame, each frame comprising a predetermined plurality of data blocks;

transmitting the first frame in its entirety; and

transmitting only those data blocks within the or each subsequent frame which are significantly different from the corresponding data block within the first frame, each such data block being transmitted in combination with a respective index number which defines the position of the block within the frame.

55. A method as claimed in claim 54, further comprising:

processing each of said data blocks in accordance with a predetermined algorithm to evaluate a parameter for that data block;

for each data block within the or each subsequent frame, determining if the value of the associated parameter is significantly different from the corresponding data block of the preceding frame within the sequence;

wherein the step of transmitting only those data blocks which are significantly different comprises transmitting only those data blocks within the or each subsequent frame for which there has been a positive determination.

56. A method as claimed in claim 54, wherein the step of grouping the data comprises grouping the data into a plurality of said sequences, each containing n frames, where n is a predetermined number, such that at least one entire frame is transmitted within each sequence of n consecutive frames of data.

57. A method as claimed in claim 56, further comprising transmitting an additional entire frame at regular intervals.

58. A method as claimed in claim 56, further comprising transmitting an additional entire frame on receipt of a demand signal.

59. A method of compressing data comprising:

grouping the data into a sequence of frames comprising a first frame and at least one subsequent frame, each frame comprising a predetermined plurality of data blocks;

compressing the first frame in its entirety; and

compressing only those data blocks within the or each subsequent frame which are significantly different from the corresponding data block within the first frame, each such data block being compressed in combination with a respective index number which defines the position of the block within the frame.

60. A method as claimed in claim 59, further comprising:

processing each of said data blocks in accordance with a predetermined algorithm to evaluate a parameter for that data block;

for each data block within the or each subsequent frame, determining if the value of the associated parameter is significantly different from the corresponding data block of the preceding frame within the sequence;

wherein the step of compressing only those data blocks which are significantly different comprises compressing only those data blocks within the or each subsequent frame for which there has been a positive determination.

61. A method as claimed in claim 59, wherein the step of grouping the data comprises grouping the data into a plurality of said sequences, each containing n frames, where n is a predetermined number, such that at least one entire frame is compressed within each sequence of n consecutive frames of data.

62. A method as claimed in claim 61, further comprising compressing an additional entire frame at regular intervals.

63. A method as claimed in claim 61, further comprising compressing an additional entire frame on receipt of a demand signal.

64. A method as claimed claim 59, wherein the data to be compressed has been subjected to a wavelet transform, and wherein the parameter is evaluated on the basis of only the most significant coefficient within each sub-band in each data block.

65. A method as claimed in claim 64, wherein the parameter is evaluated on the basis of the position within the data block of the most significant coefficient.

66. A method as claimed in claim 64, wherein the parameter is evaluated on the basis of only the n most significant coefficients selected from the group comprising the most significant coefficient within each sub-band in each data block, where n is a predetermined number.

67. A method as claimed in claim 66, wherein n is equal to 8.

68. A method as claimed in claim 64, wherein the wavelet transform is a five-level transform resulting in 16 sub-bands.

69. A method as claimed in claim 59, further comprising transmitting only the compressed data.

70. A method as claimed in claim 59, wherein the data comprises colour image data, and wherein only the luminance component of the colour image data is processed in order to evaluate said parameter.

71. A method as claimed in claim 59, wherein only those components of the data within each data block having values higher than a predetermined threshold are processed to evaluate the parameter for that data block.

72. A method of configuring a plurality of variable-length data blocks into a data stream from which each data block can subsequently be retrieved, wherein each data block maps to a block of pixels within a frame of image data, the method comprising:

for each data block, forming a respective indexed data block comprising;

a sync word which is identical for each indexed data block;

an index number which uniquely identifies the data block within said plurality of data blocks; and

the respective data block.

73. A method as claimed in claim 72, wherein each indexed data block comprises, in sequence, said sync word, said index number and said respective data block.

74. A method as claimed in claim 72, wherein the sync word comprises a sequence of 16 bits.

75. A method as claimed in claim 72, wherein the sync word comprises a sequence of bits each equal to 1.

76. A method as claimed in claim 72, wherein all of the index numbers comprise bits sequences of equal length.

77. A method as claimed in claim 76, wherein each of the index numbers is 11 bits in length.

78. A method as claimed in claim 72, wherein each of said data blocks comprises a data block which has been transformed in accordance with a wavelet transform.

79. A method of retrieving variable-length data blocks from a data stream, the data blocks having been configured in accordance with a method as claimed in claim 72, the method comprising locating said sync word within said data stream thereby to identify said data blocks;

and

retrieving the resulting identified data blocks from said data stream.

80. A method as claimed in claim 79, wherein each of said data blocks has a characteristic which enables it to be verified as a valid data block, the method comprising searching sequentially within the data stream for a data sequence which is identical to said sync word, thereby to identify a potential indexed data block comprising a potentially valid data block, and validating said data block only:

(a) if it is verified by said characteristic to be a valid data block; and

(b) if the potential indexed data block is followed immediately within the data stream by a further potential indexed data block comprising a data sequence which is identical to said sync word.

81. A method as claimed in claim 80, further comprising selecting for a subsequent processing step only those data blocks which have been validated.

82. A method as claimed in claim 81, wherein said data stream comprises data corresponding to an image to be displayed, and wherein said processing step comprises displaying the resulting selected data blocks.

83. A method of selecting a region of interest from within a plurality of variable-length data blocks which have been retrieved in accordance with claim 79, the method comprising selecting only those retrieved variable-length data bocks which are associated with one or more predetermined index numbers.