Method and apparatus for compressing and scaling thumbnails

Abstract

Disclosed are method and apparatus for the manipulation of thumbnail images as used in image-based browsing file management systems. Disclosed are arrangements whereby zooming in and out of thumbnail images can be performed without a continued need to decompress a true image thus providing for faster operation. Pixel interpolation and/or replication are used to generate intermediate images that are display to deliver to the user a perception of a transitory zoom yet are of sufficient detail to maintain user orientation. Aspect ratio zooming of thumbnail containment areas is also disclosed which facilitates ease of browsing. The compression of thumbnail type images using a discrete wavelet transform facilitates the fast zoom of thumbnails and their associated containment areas.

We claim:  
     
         1 . A method of displaying a representation of a plurality of images concurrently on a display device, each said image being encoded in a hierarchical compressed format, said hierarchical compressed format adapted to provide, without substantially compromising compression efficiency, a decoding of each said encoded image into one or more of a plurality of predetermined sizes, each size definable by a number of pixels, said method comprising the steps of: 
 decoding each encoded image of said plurality of images into at least one of said plurality of predetermined sizes, wherein a decode time for each encoded image at each one of said predetermined sizes is substantially proportional to the number of pixels of each decoded image; and    displaying each decoded image of said plurality of images concurrently on said display device.    
     
     
         2 . The method according to  claim 1 , wherein each said decoded image is a thumbnail representation of each said corresponding encoded image.  
     
     
         3 . The method according to  claim 1 , wherein each said encoded image is encoded using a compression technique employing a linear transform.  
     
     
         4 . The method according to  claim 3 , wherein said compression technique substantially encodes groups of coefficients representing a resolution of said linear transform substantially independently of coefficients representing another resolution.  
     
     
         5 . The method according to  claim 3 , wherein said linear transform is a discrete wavelet transform.  
     
     
         6 . The method according to  claim 1 , wherein said plurality of predetermined sizes comprises a set of sizes related by powers of 2.  
     
     
         7 . The method according to  claim 1 , wherein said plurality of predetermined sizes is the same for each decoded image in said plurality of images.  
     
     
         8 . The method according to  claim 1 , wherein said decoding step and said displaying step are interleaved for each image of said plurality.  
     
     
         9 . A method of displaying a plurality of images concurrently on a display device, said method comprising the steps of: 
 encoding each image in a hierarchical compressed format capable of providing a plurality of predetermined sizes of each said image without substantially compromising compression efficiency, wherein each image is encoded in a manner so that a decode time for each image at each of said predetermined sizes is substantially proportional to the number of pixels in each decoded image,    decoding each image of said plurality of images, and    displaying each decoded image of said plurality of images concurrently on said display device.    
     
     
         10 . The method according to  claim 9 , wherein each said decoded image is a thumbnail representation of each corresponding encoded image.  
     
     
         11 . The method according to  claim 9 , wherein each said encoded image is encoded using a compression technique employing a linear transform.  
     
     
         12 . The method according to  claim 11 , wherein said compression technique substantially encodes groups of coefficients representing a resolution of said linear transform substantially independently of coefficients representing another resolution.  
     
     
         13 . The method according to  claim 11 , wherein said linear transform is a discrete wavelet transform.  
     
     
         14 . The method according to  claim 9 , wherein said plurality of predetermined sizes comprises a set of sizes related by powers of 2.  
     
     
         15 . The method according to  claim 9 , wherein said plurality of predetermined sizes is the same for each decoded image in said plurality of images.  
     
     
         16 . The method according to  claim 9 , wherein said decoding step and said displaying step are interleaved for each image of said plurality.  
     
     
         17 . The method according to  claim 2  or  10 , wherein a predetermined size of each decoded image is equal to or greater than a desired size of said thumbnail.  
     
     
         18 . The method according to  claim 17 , further comprising the step of downsampling each decoded image to provide the desired-size thumbnail if the size of said decoded image is greater than said desired size of said thumbnail.  
     
     
         19 . The method according to  claim 17 , further comprising the step of upsampling the decoded image to provide the desired-size thumbnail if the size of said decoded image is less than the desired size of said thumbnail.  
     
     
         20 . The method according to  claim 2  or  10 , further comprising the step of decoding said image at two different adjacent sizes of a plurality of sizes to provide said image having a desired size.  
     
     
         21 . The method according to  claim 20 , further comprising the step of interpolating between the two decoded images having different adjacent sizes to provide the desired-size thumbnail if the size of one of said two decoded images is greater than the desired thumbnail size and the other of said two decoded images is less than the desired thumbnail size.  
     
     
         22 . The method according to  claim 5  or  13 , wherein each image is encoded by the steps of: 
 transforming said image to derive a plurality of coefficients, each coefficient represented by a predefined bit sequence;  
 selecting a portion of said plurality of coefficients as a region; 
 (a) scanning the significance of each bitplane of said selected region from a most significant bitplane towards a least significant bitplane and providing a first token in said coded representation for each insignificant bitplane until a significant bitplane is determined, wherein a second token is provided in said coded representation for said significant bitplane;  
 (b) partitioning said selected region into two or more subregions having a predetermined form, and setting each of said subregions as said selected region;  
 (c) repeating steps (a) and (b) commencing from said significant bitplane until said selected region has a predetermined size, wherein said coefficients of said selected region are coded and provided in said coded representation.  
 
 
     
     
         23 . The method according to  claim 22 , wherein said transforming step comprises applying a discrete wavelet transform to said image.  
     
     
         24 . The method according to  claim 22 , wherein said region comprises said entire plurality of coefficients.  
     
     
         25 . The method according to  claim 23 , wherein said portion comprises a subband of said plurality of coefficients.  
     
     
         26 . The method according to  claim 22 , wherein said first and second tokens comprise bit values of 0 and 1, respectively.  
     
     
         27 . The method according to  claim 22 , wherein said subregions are equally sized.  
     
     
         28 . The method according to  claim 27 , wherein said subregions are square.  
     
     
         29 . The method according to  claim 22 , wherein said predetermined size of said subregion is a 1×1 coefficient.  
     
     
         30 . The method according to  claim 29 , wherein said 1×1 coefficient is encoded by outputting bits of said corresponding bit sequence beginning with the respective significant bitplane.  
     
     
         31 . The method according to  claim 30 , wherein only bits of said corresponding bit sequence above a predetermined minimum bit level are output in said coded representation.  
     
     
         32 . The method according to  claim 22 , wherein, in step (c), steps (a) and (b) are repeated otherwise until each bitplane of said selected region has been scanned.  
     
     
         33 . The method according to  claim 32 , wherein each bitplane of said selected region above a minimum bit level has been scanned.  
     
     
         34 . The method according to  claim 5  or  13 , wherein each image is encoded by the steps of: 
 decomposing said image using a subband transform to provide a number of subbands;  
 for each subband, selecting said subband as an initial region and performing the following sub-steps: 
 (a) checking if a current bit level of the selected region is significant;  
 (b) if said current bit level is significant, outputting a first token in a coded representation and partitioning said selected region into a number of equally sized sub-regions, wherein each sub-region is processed as said selected region in turn;  
 (c) if said current bit level is insignificant, outputting a second token in said coded representation and selecting the next lower bit level of said selected region as said current bit level;  
 (d) repeating steps (a) to (c) until said current bit level is less than a specified minimum bit level, or said selected region has a predetermined size and coefficients of said selected region are coded in said coded representation.  
 
 
     
     
         35 . The method according to  claim 34 , wherein said coefficients of said selected region are coded by representing each coefficient by the bits between the corresponding current bit level and the minimum bit level.  
     
     
         36 . The method according to  claim 34 , wherein said subband transform comprises a discrete wavelet transform.  
     
     
         37 . The method according to  claim 5  or  13 , wherein each image is encoded by the steps of: 
 a) dividing each said image into a plurality of blocks;  
 b) applying a subband transform to each of said blocks to provide a plurality of AC subband regions, at one or more resolutions, and a DC subband region for each block;  
 c) selection said DC subband region as a selected region and performing the following sub-steps: 
 ca) checking if a current bitplane of the selected region is significant;  
 cb) if said current bitplane is significant, outputting a first token in a coded representation and partitioning said selected region into a number of sub-regions, wherein each sub-region is processed as the selected region in turn;  
 cc) if said current bitplane is insignificant, outputting a second token in the coded representation and selecting the next lower bitplane of the selected region as the current bitplane;  
 cd) repeating sub-steps ca) to cc) until said current bitplane is less than a specified minimum bitplane, or said selected region has a predetermined size and coefficients of said selected region are coded in said coded representation;  
 
 d) selecting substantially all uncoded AC subband regions as a remaining region of each block and scanning the significance of each bitplane of the remaining region from a most significant bitplane towards a least significant bitplane, and outputting the second token for each insignificant bitplane until a significant bitplane is determined;  
 e) setting one or more AC subband regions, of a current resolution level, as a selected region and performing the sub-steps ca) to cd);  
 f) repeating step e) until substantially all AC subbands of the current resolution level have been encoded; and  
 g) repeating steps d) to f) until all AC subbands of each block have been encoded.  
 
     
     
         38 . The method according to  claim 1  or  9 , further comprising the step of caching said encoded image and/or said decoded image.  
     
     
         39 . The method according to  claim 38 , further comprising the step of caching intermediate size versions of said decoded image.  
     
     
         40 . Apparatus for displaying a representation of a plurality of images concurrently on a display device, said apparatus comprising: 
 means for storing each said image, having being encoded in a hierarchical compressed format, said hierarchical compressed format adapted to provide, without substantially compromising compression efficiency, a decoding of each said encoded image into one or more of a plurality of predetermined sizes, each size definable by a number of pixels; and    means for decoding each encoded image of said plurality of images into at least one of said plurality of predetermined sizes, wherein a decode time for each encoded image at each one of said predetermined sizes is substantially proportional to the number of pixels of each decoded image; and    means for displaying each decoded image of said plurality of images concurrently on said display device.    
     
     
         41 . The apparatus according to  claim 40 , wherein each said decoded image is a thumbnail representation of each corresponding encoded image.  
     
     
         42 . The apparatus according to  claim 40 , wherein each said encoded image is encoded using a compression technique employing a linear transform.  
     
     
         43 . The apparatus according to  claim 42 , wherein said compression technique substantially encodes groups of coefficients representing a resolution of said linear transform substantially independently of coefficients representing another resolution.  
     
     
         44 . The apparatus according to  claim 42 , wherein said linear transform is a discrete wavelet transform.  
     
     
         45 . The apparatus according to  claim 40 , wherein said plurality of predetermined sizes comprises a set of sizes related by powers of 2.  
     
     
         46 . The apparatus according to  claim 40 , wherein said plurality of predetermined sizes is the same for each decoded image in said plurality of images.  
     
     
         47 . The apparatus according to  claim 40 , wherein said decoding step and said displaying step are interleaved for each image of said plurality.  
     
     
         48 . An image-based computerized file browsing system comprising: 
 a storage device for retaining a plurality of images at least group of which are stored in an encoded, hierarchical compressed format, said hierarchical compressed format adapted to provide, without substantially compromising compression efficiency, a decoding of each said image into one or more of a plurality of predetermined sizes, each size comprising a number of pixels,    a processor for running an operating system incorporating a file management arrangement wherein true images retained in said storage device are depicted as thumbnail representations when viewed via said file management system,    characterised by 
 an image manipulation arrangement whereby said images are decoded into at least one of said plurality of sizes, wherein a decode time for each image at each of said predetermined sizes is substantially proportional to the number of pixels of each decoded image.  
   
     
     
         49 . The system according to  claim 48 , wherein each said decoded image is a thumbnail representation of each said corresponding encoded image.  
     
     
         50 . The system according to  claim 48 , wherein each said encoded image is encoded using a compression technique employing a linear transform.  
     
     
         51 . The system according to  claim 50 , wherein said compression technique substantially encodes groups of coefficients representing a resolution of said linear transform substantially independently of coefficients representing another resolution.  
     
     
         52 . The system according to  claim 50 , wherein said linear transform is a discrete wavelet transform.  
     
     
         53 . The system according to  claim 48 , wherein said plurality of predetermined sizes comprises a set of sizes related by powers of 2.  
     
     
         54 . The system according to  claim 48 , wherein said plurality of predetermined sizes is the same for each decoded image in said plurality of images.  
     
     
         55 . The system according to  claim 48 , wherein said decoding step and said displaying step are interleaved for each image of said plurality.  
     
     
         56 . A computer program product comprising a computer readable medium having a computer program recorded thereon for displaying a representation of a plurality of images concurrently on a display device, said computer program product comprising: 
 means for storing said plurality of images having been encoded in a hierarchical compressed format, said hierarchical compressed format adapted to provide, without substantially compromising compression efficiency, a decoding of each said image into one or more of a plurality of predetermined sizes, each size comprising a number of pixels;    means for decoding each of said images into at least one of said plurality of sizes, wherein a decode time for each image at each of said predetermined sizes is substantially proportional to the number of pixels of each decoded image; and    means for displaying each decoded image of said plurality of images concurrently on the display device.    
     
     
         57 . The computer program product according to  claim 56 , wherein each said decoded image is a thumbnail representation of each said corresponding encoded image.  
     
     
         58 . The computer program product according to  claim 56 , wherein each said encoded image is encoded using a compression technique employing a linear transform.  
     
     
         59 . The computer program product according to  claim 58 , wherein said compression technique substantially encodes groups of coefficients representing a resolution of said linear transform substantially independently of coefficients representing another resolution.  
     
     
         60 . The computer program product according to  claim 58 , wherein said linear transform is a discrete wavelet transform.  
     
     
         61 . The computer program product according to  claim 56 , wherein said plurality of predetermined sizes comprises a set of sizes related by powers of 2.  
     
     
         62 . The computer program product according to  claim 56 , wherein said plurality of predetermined sizes is the same for each decoded image in said plurality of images.  
     
     
         63 . The computer program product according to  claim 56 , wherein said decoding step and said displaying step are interleaved for each image of said plurality.