Image compression based on tiled wavelet-like transform using edge and non-edge filters

• US 6,549,674 B1
• Filed: 10/12/2000
• Issued: 04/15/2003
• Est. Priority Date: 10/12/2000
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Picsurf, Inc.
• Inventors: Zhong, Lefan, Chui, Charles K., Gao, Hong-Ye
• Primary Examiner(s): Johnson, Timothy M.
• Application Number:
  US09/687,467
• Time in Patent Office: 915 Days
• Field of Search: 382/232, 382/240, 382/239, 382/251, 382/260, 382/263, 382/264, 382/265, 382/266, 382/268, 375/240.02, 375/240.03, 375/240.11, 375/240.19, 348/398.1, 348/437.1, 348/438.1
• US Class Current: 382/240
• CPC Class Codes: G06F 17/148 Wavelet transforms
• CPC Class Codes: G06F 2203/04806 Zoom, i.e. interaction techniques or interactors for controlling the zooming operation
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06T 3/403 Edge-driven scaling; Edge-based scaling
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: G09G 2340/0407 Resolution change, inclusive of the use of different resolutions for different screen areas
• CPC Class Codes: H04N 19/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/124 Quantisation
• 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/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/18 the unit being a set of transform coefficients
• 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/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/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/59 involving spatial sub-sampling or interpolation, e.g. alteration of picture size or resolution
• 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/80 : Details of filtering operations specially adapted for video compression, e.g. for pixel interpolation H04N19/635, H04N19/86 take precedence
• CPC Class Codes: H04N 21/234327 : by decomposing into layers, e.g. base layer and one or more enhancement layers
• CPC Class Codes: H04N 21/235 : Processing of additional data, e.g. scrambling of additional data or processing content descriptors
• CPC Class Codes: H04N 21/25825 : involving client display capabilities, e.g. screen resolution of a mobile phone optimising the visualisation of content during browsing in the Internet G06F16/9577; processing of terminal status or physical abilities in wireless networks H04W8/22; authentication in wireless network security H04W12/06
• CPC Class Codes: H04N 21/2662 : Controlling the complexity of the video stream, e.g. by scaling the resolution or bitrate of the video stream based on the client capabilities
• CPC Class Codes: H04N 21/435 : Processing of additional data, e.g. decrypting of additional data, reconstructing software from modules extracted from the transport stream
• CPC Class Codes: H04N 21/443 : OS processes, e.g. booting an STB, implementing a Java virtual machine in an STB or power management in an STB
• CPC Class Codes: H04N 21/4621 : Controlling the complexity of the content stream or additional data, e.g. lowering the resolution or bit-rate of the video stream for a mobile client with a small screen arrangements for using the results of monitoring on user's side in broadcast systems H04H60/65; flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/4728 : for selecting a Region Of Interest [ROI], e.g. for requesting a higher resolution version of a selected region

Abstract

An image processing system tiles an image data array. Each tile of image data is processed by applying a family of transform layers to the tile of image data so as to generate successive sets of transform coefficients. Each set of transform coefficients include edge coefficients positioned at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients. The transform filters include a short edge transform filter that is applied to image data at boundaries of the tile and to coefficients positioned at and near boundaries of each of the earlier sets of transform coefficients so as to generate the edge coefficients, and a long interior filter that is applied to image data at interior locations of the tile and to coefficients at interior locations of the earlier sets of transform coefficients so as to generate the non-edge coefficients.

Claims

1. A method of processing an array of image data, comprising:

applying a predefined family of transform filters to the array of image data so as to generate successive sets of transform coefficients, each set of transform coefficients including edge coefficients at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients;

the sets of transform coefficients including a last set of transform coefficients and one or more earlier sets of transform coefficients; and

the applying including applying a short transform filter to image data at boundaries of the array and to coefficients positioned at boundaries of each earlier set of transform coefficients so as to generate the edge coefficients, and applying a long filter to image data at interior locations of the array and to coefficients at interior locations of the earlier sets of transform coefficients so as to generate the non-edge coefficients;

wherein the boundaries of the array and the interior locations of the array are predetermined without respect to content of the array;

wherein the short transform filter has a shorter filter support than the long transform filter, and both the short transform filter and the long transform filter are applied only to image data within the array and only to transform coefficients within the earlier sets of transform coefficients for the array while generating the sets of transform coefficients.

2. The method of claim 1, wherein the short transform filter includes a short low spatial frequency filter that generates low spatial frequency coefficients, and the short low spatial frequency filter weights the image datum closest to the boundary of the array and the transform coefficient closest to the boundary of each earlier set of transform coefficients so as to as enable regeneration of the image from the transform coefficients without array boundary artifacts.

3. The method of claim 2, wherein the short low spatial frequency filter weights the transform coefficient closest to the boundary of one of the earlier set of transform coefficients so that more than 50% of the edge transform coefficient generated by the filter for a next set of transform coefficients is attributable to the transform coefficient closest to the boundary of one of the earlier sets of transform coefficients, said next set of transform coefficients comprising one of said sets of transform coefficients.

4. The method of claim 1, wherein a plurality of the transform filters are asymmetric boundary filters, extending to a first extent to each array'"'"'s boundary, and extending to a second, longer, extent in a direction away from the array'"'"'s boundary, but not extending over the array'"'"'s boundary.

5. The method of claim 1, wherein the transform filters are wavelet or wavelet-like decomposition transform filters.

6. The method of claim 1, wherein the long filter includes a center filter, applied to image data at a predefined set of array locations within the interior locations, for generating a set of center high pass and low pass transform coefficients and the long filter furthermore includes first and second distinct interior filters, wherein the first interior filter is applied to array locations on a first side of the predefined set of array locations and the second interior filter is applied to array locations on a distinct, second side of the predefined set of array locations.

7. A method of processing an array of image data, comprising:

processing tiles of the image data in a predefined order, the tiles comprising nonoverlapping portions of the image data, so as to generate processed image data; and

storing the processed image data as a data image file;

the processing of each tile of image data comprising;

applying a predefined family of transform filters to the tile of image data so as to generate successive sets of transform coefficients, each set of transform coefficients including edge coefficients positioned at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients;

the sets of transform coefficients including a last set of transform coefficients and one or more earlier sets of transform coefficients; and

the applying including applying a short transform filter to image data at boundaries of the tile and to coefficients positioned at boundaries of each earlier set of transform coefficients so as to generate the edge coefficients, and applying a long filter to image data at interior locations of the tile and to coefficients at interior locations of the earlier sets of transform coefficients so as to generate the non-edge coefficients;

wherein the boundaries of the array and the interior locations of the array are predetermined without respect to content of the array;

wherein the short transform filter has a shorter filter support than the long transform filter, and both the short transform filter and the long transform filter are applied only to image data within the tile and only to transform coefficients within the earlier sets of transform coefficients for the tile while generating the sets of transform coefficients.

8. The method of claim 7, wherein the processing of each tile includes:

for at least two of the respective sets of transform coefficients, generating one or more parameters whose value is indicative of density of image features in the tile;

classifying the tile into one of a predefined set of categories in accordance with the values of the one or more parameters;

selecting a set of quantization factors for each respective tile in accordance with the category into which the tile has been classified; and

scaling the transform coefficients of the tile by the set of quantization factors to as to generate a set of quantized transform coefficients for the tile.

9. The method of claim 8, including

storing in the image data file an indication of the selected set of quantization factors for each tile of the image data.

10. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an image processing module that applies a predefined family of transform filters to the array of image data so as to generate successive sets of transform coefficients, each set of transform coefficients including edge coefficients positioned at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients;

the sets of transform coefficients including a last set of transform coefficients and one or more earlier sets of transform coefficients; and

the predefined family of transform filters including a short transform filter applied by the image processing module to image data at boundaries of the array and to coefficients positioned at boundaries of each earlier set of transform coefficients so as to generate the edge coefficients, and applying a long filter applied by the image processing module to image data at interior locations of the array and to coefficients at interior locations of the earlier sets of transform coefficients so as to generate the non-edge coefficients;

wherein the boundaries of the array and the interior locations of the array are predetermined without respect to content of the array;

wherein the short transform filter has a shorter filter support than the long transform filter, and both the short transform filter and the long transform filter are applied only to image data within the array and only to transform coefficients within the earlier sets of transform coefficients for the array while generating the sets of transform coefficients.

11. The computer program product of claim 10, wherein the short transform filter includes a short low spatial frequency filter that generates low spatial frequency coefficients, and the short low spatial frequency filter weights the image datum closest to the boundary of the array and the transform coefficient closest to the boundary of each earlier set of transform coefficients so as to as enable regeneration of the image from the transform coefficients without array boundary artifacts.

12. The computer program product of claim 11, wherein the short low spatial frequency filter weights the transform coefficient closest to the boundary of one of the earlier set of transform coefficients so that more than 50% of the edge transform coefficient generated by the filter for a next set of transform coefficients is attributable to the transform coefficient closest to the boundary of one of the earlier sets of transform coefficients, said next set of transform coefficients comprising one of said sets of transform coefficients.

13. The computer program product of claim 10, wherein a plurality of the transform filters are asymmetric boundary filters, extending to a first extent to each array'"'"'s boundary, and extending to a second, longer, extent in a direction away from the array'"'"'s boundary, but not extending over the array'"'"'s boundary.

14. The computer program product of claim 10, wherein the transform filters are wavelet or wavelet-like decomposition transform filters.

15. The computer program product of claim 10, wherein the interior filter includes a center filter, applied to image data at a predefined set of array locations within the interior locations, for generating a set of center high pass and low pass transform coefficients and the interior filter furthermore includes first and second distinct interior filters, wherein the first interior filter is applied to array locations on a first side of the predefined set of array locations and the second interior filter is applied to array locations on a distinct, second side of the predefined set of array locations.

16. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an image processing module that processes tiles of the image data in a predefined order, the tiles comprising nonoverlapping portions of the image data, so as to generate processed image data, and that stores the processed image data as a data image file;

the image processing module including instructions for processing of each tile of image data, comprising;

instructions for applying a predefined family of transform filters to the tile of image data, so as to generate successive sets of transform coefficients, each set of transform coefficients including edge coefficients positioned at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients;

the sets of transform coefficients including a last set of transform coefficients and one or more earlier sets of transform coefficients; and

the instructions for applying a predefined family of transform filters including instructions for applying a short transform filter to image data at boundaries of the tile and to coefficients positioned at boundaries of each earlier set of transform coefficients so as to generate the edge coefficients, and for applying a long filter to image data at interior locations of the tile and to coefficients at interior locations of the earlier sets of transform coefficients so as to generate the non-edge coefficients;

wherein the boundaries of the array and the interior locations of the array are predetermined without respect to content of the array;

wherein the short transform filter has a shorter filter support than the long transform filter, and both the short transform filter and the long transform filter are applied only to image data within the tile and only to transform coefficients within the earlier sets of transform coefficients for the tile while generating the sets of transform coefficients.

17. The computer program product of claim 16, wherein the image processing module includes:

instructions for generating, for at least two of the respective sets of transform coefficients, one or more parameters whose value is indicative of density of image features in the tile;

instructions for classifying the tile into one of a predefined set of categories in accordance with the values of the one or more parameters;

instructions for selecting a set of quantization factors for each respective tile in accordance with the category into which the tile has been classified; and

instructions for scaling the transform coefficients of the tile by the set of quantization factors to as to generate a set of quantized transform coefficients for the tile.

18. The computer program product of claim 17, including

instructions for storing in the image data file an indication of the selected set of quantization factors for each tile of the image data.

19. A method of processing an array of image data, comprising:

applying a predefined family of transform filters to the array of image data so as to generate successive sets of transform coefficients, including applying a first family of transform filters to the array of image data so as to generate a first set of transform coefficients and applying a second family of transform filters to the first set of transform coefficients so as to generate a second set of transform coefficients;

wherein applying the first family of transform filters includes applying a first short transform filter to image data at boundaries of the array and a first long transform filter to image data at interior locations of the array, and applying the second family of transform filters includes applying a second short transform filter to edge coefficients at boundaries of the first set of transform coefficients and a second long transform filter to coefficients at interior locations of the first set of transform coefficients;

wherein the boundaries of the array and the first set of transform coefficients, and the interior locations of the array and the first set of transform coefficients are predetermined without respect to content of the array and the first set of transform coefficients;

wherein the first family of transform filters have shorter filter supports than the second family of transform filters.

20. The method of claim 19, including applying the second family of transform filters to the second set of transform coefficients so as to generate a third set of transform coefficients and applying the second family of transform filters to the third set of transform coefficients so as to generate a fourth set of transform coefficients wherein applying the second family of transform filters includes applying the second short transform filter to edge coefficients at boundaries of the second and the third set of transform coefficients and applying the second long transform filter to coefficients at interior locations of the second and the third set of transform coefficients;

wherein the boundaries of the second and the third set of transform coefficients, and the interior locations of the second and the third set of transform coefficients are predetermined without respect to content of the second and the third set of transform coefficients.

21. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an image processing module that applies a predefined family of transform filters to the array of image data so as to generate successive sets of transform coefficients, each set of transform coefficients including edge coefficients positioned at outside boundaries of the set of transform coefficients and non-edge coefficients positioned at interior locations of the set of transform coefficients;

the predefined family of transform filters including a first family of transform filters applied by the image processing module to the array of image data so as to generate a first set of transform coefficients and a second family of transform filters applied by the image processing module to the first set of transform coefficients so as to generate a second set of transform coefficients;

wherein the image processing module applies a first short transform filter to image data at boundaries of the array and a first long transform filter to image data at interior locations of the array, and the image processing module applies a second short transform filter to edge coefficients at boundaries of the first set of transform coefficients and a second long transform filter to coefficients at interior locations of the first set of transform coefficients;

wherein the boundaries of the array and the first set of transform coefficients, and the interior locations of the array and the first set of transform coefficients are predetermined without respect to content of the array and the first set of transform coefficients;

wherein the first family of transform filters have shorter filter supports than the second family of transform filters.

22. The computer program product of claim 21, wherein the image processing module includes instructions for applying the second family of transform filters to the second set of transform coefficients so as to generate a third set of transform coefficients and for applying the second family of transform filters to the third set of transform coefficients so as to generate a fourth set of transform coefficients wherein applying the second family of transform filters includes applying the second short transform filter to edge coefficients at boundaries of the second and the third set of transform coefficients and applying the second long transform filter to coefficients at interior locations of the second and the third set of transform coefficients;

wherein the boundaries of the second and the third set of transform coefficients, and the interior locations of the second and the third set of transform coefficients are predetermined without respect to content of the second and the third set of transform coefficients.