Memory usage scheme for performing wavelet processing

• US 20020168112A1
• Filed: 02/15/2001
• Published: 11/14/2002
• Est. Priority Date: 02/15/2001
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Wu, Kok Gi
• Granted Patent: US 6,898,323 B2
• Time in Patent Office: Days
• US Class Current: 382/240
• CPC Class Codes: G11B 27/036 Insert-editing
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/117 Filters, e.g. for pre-processing or post-processing sub-band filter banks H04N19/635
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/17 the unit being an image region, e.g. an object
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream
• 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/426 : using memory downsizing methods
• CPC Class Codes: H04N 19/45 : performing compensation of the inverse transform mismatch, e.g. Inverse Discrete Cosine Transform [IDCT] mismatch
• CPC Class Codes: H04N 19/46 : Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/593 : involving spatial prediction techniques
• CPC Class Codes: H04N 19/61 : in combination with predictive coding
• CPC Class Codes: H04N 19/619 : the transform being operated outside the prediction loop
• 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/64 : characterised by ordering of coefficients or of bits for transmission
• 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/70 : characterised by syntax aspects related to video coding, e.g. related to compression standards
• CPC Class Codes: H04N 19/85 : using pre-processing or post-processing specially adapted for video compression
• CPC Class Codes: H04N 19/86 : involving reduction of coding artifacts, e.g. of blockiness

Abstract

A system comprising a memory and wavelet processing logic is described. The memory is sized to include lines to store a band of an image and additional lines. The wavelet processing logic comprises a wavelet transform and access logic. The wavelet transform generates coefficients when applied to data in the memory. The access logic reads data from the memory into the line buffers to supply data stored in the memory to the wavelet transform and to store coefficients in the memory, such that after data stored at a first pair of lines is read from memory into the buffers of the access logic. The access logic reuses the first pair of lines to store coefficients generated by the wavelet transform that are associated with a second pair of lines different from the first pair of lines.

Claims

1. A system comprising:

a memory sized to include lines to store a band of an image and additional lines;

a wavelet processing logic comprising

a wavelet transform to generate coefficients when applied to data in the memory;

access logic to read data from the memory into the line buffers to supply data stored in the memory to the wavelet transform and to store coefficients in the memory, such that after data stored at a first pair of lines is read from memory into the buffers of the access logic, the access logic reuses the first pair of lines to store coefficients generated by the wavelet transform that are associated with a second pair of lines different from the first pair of lines.

2. The system defined in claim 1 wherein the access logic stores coefficients in contiguous lines of memory with coefficients from the same subband and decomposition level adjacent each other.

3. The system defined in claim 1 wherein a first line of each of the first and second pairs of lines are located in the memory at an offset with respect to each other.

4. The system defined in claim 3 wherein the access logic stores the first outputs of the wavelet transform for each coefficient level in the additional lines within a distance of the offset.

5. The system defined in claim 3 wherein size of the offset is different for each transform level.

6. The system defined in claim 3 wherein the size of the offset is equal to:

2^{(transform level of coefficient being stored)}.

7. The system defined in claim 6 wherein, during decomposition, the offset for storing the first rows of each pair of rows of L1 coefficients in the memory is two lines from the first row of data of the image associated with said each pair of rows of the L1 coefficients, and the offset for storing the first row of each pair of rows of L2 coefficients if four lines from the first row of L1 coefficients associated with said each pair of rows of the L2 coefficients.

8. The system defined in claim 1 wherein the access logic stores coefficients associated with a decomposition level greater than level three in the lines of the memory that previously stored the band of the image.

9. The system defined in claim 3 wherein the addition lines relating to the offset are above the line storing the band of the image.

10. The system defined in claim 1 wherein the wavelet transform is a forward wavelet transform.

11. The system defined in claim 1 wherein the wavelet transform is an inverse wavelet transform.

13. The method defined in claim 12 further comprising access logic reusing a first pair of lines to store coefficients generated by a wavelet transform, that are associated with a second pair of lines different from the first pair of lines, after data stored at a first pair of lines is read from memory into the buffers of the access logic, and wherein a first line of each of the first and second pairs of lines are located in the memory at an offset with respect to each other.

14. The method defined in claim 13 further comprising the access logic storing the first outputs of the wavelet transform for each coefficient level in additional lines within a distance of the offset.

15. The method defined in claim 13 wherein size of the offset is different for each transform level.

16. The method defined in claim 13 wherein the size of the offset is equal to:

2^{(transform level of coefficient being stored)}.

17. The method defined in claim 16 wherein, during decomposition, the offset for storing the first rows of each pair of rows of L1 coefficients in the memory is two lines from the first row of data of the image associated with said each pair of rows of the L1 coefficients, and the offset for storing the first row of each pair of rows of L2 coefficients if four lines from the first row of L1 coefficients associated with said each pair of rows of the L2 coefficients.

18. The method defined in claim 12 further comprising access logic storing coefficients associated with a decomposition level greater than level three in the lines of the memory that previously stored the band of the image.

19. The method defined in claim 13 wherein the addition lines relating to the offset are above the line storing the band of the image.

12. A method comprising:

reading data from a memory into line buffers to apply a wavelet transform thereto; and

storing coefficients created by applying the wavelet transform at lines in the memory so that each set of coefficients generated from data stored at each pair of lines in the memory is stored in the memory at lines that are at an offset with request to said each pair of lines in the memory.

20. An article of manufacture comprising at least one recordable media storing executable instructions thereon which, when executed by a processing device, cause the processing device to:

read data from a memory into line buffers to apply a wavelet transform thereto; and

store coefficients created by applying the wavelet transform at lines in the memory so that each set of coefficients generated from data stored at each pair of lines in the memory is stored in the memory at lines that are at an offset with request to said each pair of lines in the memory.

21. The article of manufacture defined in claim 20 further comprising instructions, which when executed by the processing device cause the processing device to reuse a first pair of lines to store coefficients generated by a wavelet transform, that are associated with a second pair of lines different from the first pair of lines, after data stored at a first pair of lines is read from memory into the buffers of the access logic, and wherein a first line of each of the first and second pairs of lines are located in the memory at an offset with respect to each other.

22. An apparatus comprising:

means for reading data from a memory into line buffers to apply a wavelet transform thereto; and

means for storing coefficients created by applying the wavelet transform at lines in the memory so that each set of coefficients generated from data stored at each pair of lines in the memory is stored in the memory at lines that are at an offset with request to said each pair of lines in the memory.