(12) United States Patent
`Andrew et al.
`
`USOO6259819B1
`(10) Patent No.:
`US 6,259,819 B1
`(45) Date of Patent:
`Jul. 10, 2001
`
`(54) EFFICIENT METHOD OF IMAGE
`COMPRESSION COMPRISING ALOW
`RESOLUTION IMAGE IN THE BIT STREAM
`
`(75) Inventors: James Philip Andrew, Waverton;
`Linda Chen, Epping, both of (AU)
`(73) Assignee: Canon Kabushiki Kaisha, Tokyo (JP)
`(*) Notice:
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/055,316
`(22) Filed:
`Apr. 6, 1998
`(30)
`Foreign Application Priority Data
`Apr. 4, 1997 (AU) ................................................... PO6008
`(51) Int. Cl. ................................ G06K 9/36; G06K 9/46
`(52) U.S. Cl. .......................... 382/248; 382/240; 382/247;
`382/166
`(58) Field of Search ..................................... 382/162, 166,
`382/167, 240, 247, 250, 251, 299, 248
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,563,960 * 10/1996 Shapiro ................................ 382/239
`5,739,920 * 4/1998 Nakajima et al. ...
`... 358/426
`5,748,786 * 5/1998 Zandi et al. ......
`... 382/240
`5,880,856
`3/1999 Ferriere ................................ 358/432
`
`5,982,938
`
`11/1999 Dube .................................... 382/240
`OTHER PUBLICATIONS
`“Coding of Still Pictures”, Boliek et al., ISO/IEC JTC 1/SC
`29/WG 1, Jun. 30, 1995.
`* cited by examiner
`Primary Examiner Phuoc Tran
`(74) Attorney, Agent, or Firm-Fitzpatrick, Cella, Harper &
`Scinto
`ABSTRACT
`(57)
`A method of providing a thumbnail-size colour digital image
`in a bit Stream of a larger Size colour digital image is
`disclosed. The bit Stream of the larger digital image is
`typically in a compressed format, and includes a thumbnail
`Size image in a Substantially uncompressed format. The
`method includes converting input colour values of the larger
`colour image from a first colour format to corresponding
`values in a Luminance, Chrominance-blue, Chrominance
`red (YCb,Cr) colour format, A transform is then applied to
`Said corresponding values to decompose the larger digital
`image into a DC Subband and one or more higher frequency
`Subbands. Typically the transform is a discrete wavelet
`transform. The DC Subband is then output to the bit stream
`in an uncompressed format. Then at least one of the one or
`more higher frequency Subbands is encoded into the bit
`stream in a substantially compressed format. The DC Sub
`band thus represents a thumbnail-size colour digital image in
`the bit stream.
`
`53 Claims, 14 Drawing Sheets
`
`100
`
`
`
`Code the rest of the subbands
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 1 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 1 of 14
`
`US 6,259,819 B1
`
`100
`A-1
`
`
`
`
`
`FIG,
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 2 of 31
`
`

`

`U.S. Patent
`
`US 6,259,819 B1
`
`120
`
`122
`
`121
`
`130
`
`
`
`FIG, 3
`
`FIG, 4.
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 3 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 3 of 14
`
`US 6,259,819 B1
`
`
`
`155
`
`Video
`Interface
`
`Image
`Processor
`
`161
`
`160
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 4 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 4 of 14
`
`US 6,259,819 B1
`
`R
`ve
`
`CN
`N
`wn
`
`r
`
`ve
`
`cis
`L
`
`d5
`
`O
`C
`
`vm
`N
`vs.
`
`X
`
`s
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 5 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 5 of 14
`
`US 6,259,819 B1
`
`Input
`Image
`
`190
`
`Tronsform
`Coefficients
`
`
`
`Linear
`Transform
`
`Bt
`Rearrangement
`
`Coded
`Representation
`
`192
`
`196
`
`FIG, 7
`
`Region R
`200
`
`210
`
`N
`CH-O-
`
`212
`
`M
`
`Portition
`
`N
`
`cH--Op
`
`214
`
`216
`
`FIG, 8
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 6 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 6 of 14
`
`US 6,259,819 B1
`
`Stort
`
`302
`
`
`
`
`
`Linear Tronsform
`(preferably, discrete
`wavelet transform)
`
`
`
`
`
`Set maxBitNumber to the
`msb number of the largest
`(obsolute)coefficient value,
`ond set minbitNumber
`
`Output header
`
`Code subbands separately
`from low to high frequency
`as follows:
`
`504
`
`306
`
`308
`
`310
`
`312
`
`314
`
`Set region to each
`subbond in turn.
`
`
`
`Code region
`(maxBitNumber,
`minBitNumber)
`
`316
`
`End
`
`FIG, 9
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 7 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 7 of 14
`
`US 6,259,819 B1
`
`406
`
`412
`
`402
`
`404
`
`
`
`
`
`Is
`CurrentBitNumber
`KminBitNumber?
`
`Yes
`
`410
`
`ls region size
`1X1 pixels?
`
`Yes
`
`Code 1X1
`Pixel
`
`
`
`
`
`
`
`
`
`Output 0 and
`decrement
`CurrentBitNumber
`
`416
`
`
`
`
`
`
`
`No
`
`
`
`Is region
`significant?
`
`Yes
`
`Output 1
`
`418
`
`
`
`Partition region into 4
`Sub-regions:sub-region 1,
`..., sub-region 4
`
`420
`
`Code sign 1(currentBitNumber,
`minBitNumber),..., Code subregion 4
`(currentBitNumber, minBitNumber)
`
`422
`
`424
`
`FIG, IO
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 8 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 8 of 14
`
`US 6,259,819 B1
`
`502
`
`
`
`
`
`Input header(maxBitNumber,
`minBitNumber, image size,
`DC mean)
`
`Set region to each subband
`in turn.
`
`Decode region (maxBitNumber,
`minBitNumber)
`(ie. decode each subband)
`
`504
`
`506
`
`508
`
`Perform Inverse DWT
`
`510
`
`512
`
`FIG,
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 9 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 9 of 14
`
`US 6,259,819 B1
`
`606
`
`612
`
`602
`
`604
`
`Is
`CurrentBitNumber
`<minbitNumber?
`
`Yes
`
`
`
`
`
`
`
`618
`
`Decrement
`CurrentBitNumber
`
`
`
`
`
`610
`
`- Decode 1X
`Pixel
`
`Is
`
`reggie
`pixels?
`
`
`
`
`
`Input bit
`
`616
`
`620
`
`Yes
`
`Partition region into 4
`Sub-regions: sub-region 1,
`..., sub-region 4
`
`Decode sub-region 1(currentBitNumber,
`minBitNumber),..., decode subregion 4
`(currentBitNumber, minBitNumber)
`
`622
`
`FIG, 12
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 10 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 10 of 14
`
`US 6,259,819 B1
`
`10
`
`712
`
`750B
`
`750D
`
`750
`
`750A
`
`24
`FIG, 3B
`
`
`
`714
`
`FIG, 3A
`
`
`
`
`
`
`
`FIG, 3C
`
`FIG, 3D
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 11 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 11 of 14
`
`US 6,259,819 B1
`
`902
`
`904
`
`906
`
`908
`
`Output Header
`
`Decompose Image Into
`Blocks(or Form an Image
`Block).
`
`level Shift Eoch
`Block ond Perform
`DWT.
`
`
`
`910
`
`Code Block
`(maxBitNumber,
`minBitNumber)
`
`912
`
`End
`
`FIG, 4.
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 12 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 12 of 14
`
`US 6,259,819 B1
`
`1002
`
`1004
`
`Is
`CurrentBitNumber
`<rninBitNumber?
`
`Yes
`
`1006
`
`Is block
`significant?
`
`
`
`Yes
`
`Output 1
`
`Code DC Subband
`
`1008
`
`1012
`
`1014
`
`
`
`1010
`
`
`
`
`
`
`
`Output 0 and
`decrement
`currentBitNumber
`
`
`
`
`
`
`
`Code Block Detail
`(U, currentBitNumber, minBitNumber)
`
`1016
`
`1018
`
`FIG, .5
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 13 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 13 of 14
`
`US 6,259,819 B1
`
`1102
`
`1 104
`
`Is
`CurrentBitNumber
`kninbitNumber?
`
`Yes
`
`1106
`
`1108
`
`1110
`
`
`
`
`
`
`
`
`
`Output 0 and
`decrement
`CurrentBitNumber
`
`
`
`No
`
`Is block(detail)
`significant?
`
`1114
`
`1116
`
`
`
`
`
`
`
`Yes
`
`Output 1
`
`1112
`
`Code subband HL,
`Code subband LH,
`Code Subband HH
`
`Code Block Detail
`(J-1, currentBitNumber,
`minBitNumber)
`(If it exists)
`
`1118
`
`FIG, 6
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 14 of 31
`
`

`

`U.S. Patent
`
`Jul. 10, 2001
`
`Sheet 14 of 14
`
`US 6,259,819 B1
`
`1202
`
`1204
`
`Is
`currentBitNumber
`KminBitNumber?
`
`Yes
`
`s
`(subband)
`block size 1X1
`pixels?
`
`
`
`Yes
`
`1206
`
`1210
`
`Cage X
`Xe
`
`
`
`s
`(subband)block
`significant?
`
`1214
`
`1212
`
`
`
`
`
`
`
`
`
`1216
`
`
`
`
`
`
`
`
`
`Output 0 and
`Decrement
`currentBitNumber
`
`
`
`No
`
`Yes
`
`Output 1
`
`1218
`
`Partition(subband)block
`into 4 sub-blocks
`
`
`
`Code each sub-block
`(currentBitNumber,
`minBitNumber)
`
`1220
`
`1222
`
`1224
`
`FIG, 7
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 15 of 31
`
`

`

`US 6,259,819 B1
`
`1
`EFFICIENT METHOD OF IMAGE
`COMPRESSION COMPRISING ALOW
`RESOLUTION IMAGE IN THE BIT STREAM
`
`2
`an uncompressed format together with the compressed digi
`tal image. The Small duplicate likeness of the digital image
`makes available a representation of the digital image readily
`displayable on a display device without a requirement to
`decompress the entire digital image. However in current
`techniques the Small duplicate likeness of the digital image
`is typically Stored as an independent Stream of data and not
`as an uncompressed portion of a digital image. Thus with the
`known techniques, at least, Some disadvantages lie in a
`requirement to Store duplicate information inherent to a
`digital image, which reduces the compression efficiency.
`SUMMARY OF THE INVENTION
`In accordance with a first aspect of the present invention
`there is disclosed a method of providing a thumbnail-size
`colour digital image in a bit stream of a larger size colour
`digital image, the bit Stream of the larger digital image being
`in a compressed format, and comprising a thumbnail size
`image in a Substantially uncompressed format, the method
`comprising the Steps of:
`converting input colour values of the larger colour image
`from a first colour format to corresponding values in a
`Luminance, Chrominance-blue, Chrominance-red (YCb,Cr)
`colour format,
`applying a transform to the corresponding values to
`decompose the larger digital image into a DC Subband and
`one or more higher frequency Subbands,
`outputting to the bit stream the DC Subband in an uncom
`pressed format; and
`encoding at least one of the one or more higher frequency
`Subbands into the bit stream in a Substantially compressed
`format, wherein the DC Subband represents the thumbnail
`Size colour digital image in the bit Stream,
`In accordance with a Second aspect of the present inven
`tion there is disclosed a method of compressing a digital
`image, the digital image comprising pixels represented in
`primary colour red, green and blue (RG) format, the method
`comprising the Steps of:
`converting R, G and B components of the pixels from the
`RGB format to components in Luminance, Chrominance
`Blue, Chrominance-Red (YCbCr) format, the converting
`including Sub-Sampling of the Cb and Cr components,
`decomposing using non-integer based processing each
`YCbCr component of the pixels of the digital image into a
`DC Subband and a plurality of higher frequency Subbands;
`encoding into a bit stream the DC Subband for each
`component as a Substantially uncompressed raw bitmap
`image; and
`encoding into the bit Stream the plurality of high fre
`quency Subbands as a compressed bitmap image.
`In accordance with a third aspect of the present invention
`there is disclosed a method of compressing a digital image,
`the dig image comprising pixels represented in primary
`colour (RGB) format, the method comprising the steps of:
`converting the pixels from the RGB format to Luminance,
`Chrominance-Blue, Chrominance-Red (YCbCr) component
`format,
`decomposing using a non-integer based discrete wavelet
`transform each component of the YCbCr format of the
`digital image into a DC Subband and a plurality is of higher
`frequency Subbands,
`converting the DC Subband into RGB format;
`encoding into a bit stream tee convened DC Subband for
`each primary colour as a Substantially uncompressed raw
`bitmap image; and
`
`FIELD OF THE INVENTION
`The present invention relates to compression of digital
`image data and in particular to a method of encoding a raw
`bitmap of a low resolution version of an original image
`directly into a compressed bit stream. Further, encoding a
`raw bitmap into the pressed bit stream is achieved without
`Substantially affecting the compression efficiency or com
`putational efficiency of the compression and/or decompres
`Sion of the digital image.
`BACKGROUND ART
`In general, digital age compression comprises encoding
`an entire image, either as a whole or in a block-wise manner,
`to produce a bit-stream of data representing the image. Often
`the size, measured in bits, of the bit-Stream representing the
`image is reduced, by the compression process, when com
`pared with the number of bits required to represent the
`digital image in an uncompressed format.
`An advantage of compressing a digital image is that a
`compressed digital image data physically occupies leSS
`Storage space on a storage device (eg. RAM, Disk or
`Magnetic Tape storage). Another advantage lies in a trans
`mission of the digital images, a reduced bit-Stream, typically
`as a result of compression, requires leSS transmission time
`than does the transmission of the digital image in an uncom
`pressed format. At least one drawback of Storing or trans
`mitting a digital image in a compressed format is that the
`compressed image requires processing or decompressing
`before it can be displayed on a display device. Consequently,
`a compressed digit image cannot be displayed without
`investing costly time to decompress the compressed image.
`When browsing through a multitude of images, which are
`Stored in a storage device or transmitted to a user in
`compressed format, having to decompress each image and
`display the image to find a Select one of the images can pose
`a difficulty. In particular, the processing time required to
`decompress each image can render the browsing slow and
`cumberSome.
`A number of hierarchical techniques for image coding are
`known which involve coding a lower resolution version of
`an image within a bit Stream of a higher resolution version
`of the image. However, to display the lower resolution
`version of an image the compressed image or coded bit
`Stream must be decoded. Typically the lower resolution
`version of an image can not be gleaned off the coded bit
`Stream in a form Substantially ready for display without
`decoding the entire, or part of the image. Further, with many
`of the known techniques, a low resolution version of an
`image in an uncoded format (ie. a format Substantially ready
`for display) cannot be embedded in a bit stream of a coded
`higher resolution version of the image without Substantially
`affecting the compression efficiency, computational effi
`ciency or decoding complexity.
`In addition, for known techniques where a first (low
`resolution) image is stored together with a Second (high
`resolution) image, the first image typically being a small size
`likeness of the Second image, the first image generally
`duplicates information already inherent in the Second image.
`For example, a digital image can be duplicated and the
`duplicate image Sub-Sampled to provide a Small likeneSS
`(lower resolution) of the digital image. The digital image is
`compressed and the Small duplicate likeneSS can be stored in
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 16 of 31
`
`

`

`3
`encoding into the bit Stream the plurality of high fre
`quency Subbands as a compressed bitmap image
`A number of other aspects of the invention including
`apparatus configured to perform one or more of the methods
`and corresponding computer readable media are also dis
`closed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Embodiments of the present invention will now be
`described with reference to the drawings, in which:
`FIG. 1. Shows a high level block diagram representing an
`overview of the embodiment of the present invention;
`FIG. 2. illustrates an example of Single level discrete
`wavelet transform (DWT) of a digital image;
`FIG. 3. illustrates a two level DWT of the image of FIG.
`2,
`FIG. 4. illustrates a four level DWT of the image of FIG.
`2,
`FIG. 5, is an example Schematic block diagram of a
`conventional apparatus (computer) for practising the
`embodiment of the present invention;
`FIG. 6. illustrates a conversion of an RGB image to a
`YChCr image in accordance with the embodiment of the
`present invention;
`FIG. 7 is a high-level block diagram illustrating the image
`representation technique according to the embodiments of
`SWEET;
`FIG. 8 is a diagram illustrating partitioning according to
`a preferred embodiment of SWEET;
`FIG. 9 is a flow diagram illustrating the method of
`representing, or encoding, an image according to the pre
`ferred embodiment of SWEET;
`FIG. 10 is a detailed flow diagram illustrating. He step of
`coding a region in FIG. 9;
`FIG. 11 is a flow diagram illustrating the method of
`decoding a coded representation of an image produced in
`accordance with the method of FIG. 9;
`FIG. 12 is a detailed flow diagram illustrating tie step of
`decoding a region in FIG. 11;
`FIGS. 13A to 13D are diagrams illustrating the processing
`of a two-dimensional, eight-efficient region In accordance
`with the encoding and decoding method of FIGS. 9 to 12;
`and
`FIGS. 14 to 17 are flow diagrams illustrating the method
`representing, or encoding, an image according to an alter
`nate embodiment of SWEET.
`
`DETAILED DESCRIPTION OF THE
`EMBODIMENTS
`Referring to FIG. 1 there is shown a high-level block
`diagram to provide an overview of the embodiments of the
`present invention. At a starting point 100 of the high-level
`block diagram a digital image is Subject to a hierarchical
`Subband decoding process 101 to produce a plurality of
`frequency Subbands of the image. For example, an 8 bit
`(grey Scale) 512x512 pixel digital image is transformed
`using a 4-level discrete wavelet transform, or an octave band
`filter bank, to produce a 32x32 pixel lowest frequency
`Subband, commonly referred to as a DC Subband, and a
`plurality of higher frequency Subbands. A next step 102 in
`the high-level block diagram is to output, as part of a
`bit-stream representation of the image, the DC (or lowest
`frequency) Subband as a raw bitmap.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,259,819 B1
`
`4
`Preferably, the transform used is a non-integer based
`transform, or an integer-based transform where the DC
`Subband has a different precision to that of the input image.
`Such transforms offer better low-pass filtering, and hence
`improved visual results, as well as better compression per
`formance than integer-based transforms whose DC Subband
`has the same precision as the input.
`Throughout this specification, unless otherwise noted, a
`reference to "raw bitmap' is to be construed as a reference
`to pixel based image data represented in a form Substantially
`ready (or with a minimal processing) for display on a display
`device. A raw bitmap is also often referred to as an uncom
`pressed format. For example, a raw bitmap can include pixel
`image data represented as R,G,B values which is readily
`adaptable for display on a device Such as a cathode ray tube
`(CRT). Optionally, a taw bitmap can be of a form readily
`displayable on a printer device Such a high quality colour
`printer.
`The high frequency Subbands are encoded, at step 103 of
`the block diagram in FIG. 1, into the bit-stream represen
`tation of the image using an encoding technique which can
`reduce the total number of bits require to represent the high
`frequency Subband resulting from a hierarchical Subband
`decoder. An example of a preferred encoding technique for
`encoding the high frequency Subbands is described later in
`this document and hereinafter referred to as "Structured
`Wavelet Encoded Embedding Tree". or simply "SWEET".
`Such a preferred arrangement uses non-integer based trans
`forms and to which a quantisation technique may be applied.
`Referring to FIG. 2, there is shown an example of a
`discrete wavelet transform 121, for a single level, of a digital
`image 120. The single level discrete wavelet transform
`(DWT) analyses an image into a plurality of Subbands or
`Sub-images, typically four Subbands, namely a Low-Low
`frequency Subband (LL1) 122, a High-Low frequency Sub
`band (HL1) 123, a Low-High frequency Subband (LH1) 124
`and a High-High frequency Subband (HH1) 125. The LL1
`Subband is a lowpass decimated version of the digital image
`120 and often referred to as the DC Subband for the single
`level. The numeral associated with a labelling of the Sub
`bands indicates a level of decomposition. For example the
`Subband label LL1 represents a Low-Low frequency at a
`level 1 or single level decomposition. HL4 therefore being
`a High-Low Subband at level 4 of a 4 level Subband
`decomposition (decoding).
`The LL1 Subband 122 of FIG. 2 can be further analysed,
`using a discrete wavelet transform, into a plurality of Sub
`bands resulting in LL2, HL2, LH2 and HH2 Subbands, as
`seen in FIG. 3 identified by reference numerals 130, 131,
`132 and 133 respectively, and together with the HL1, LH1
`and HH1 Subbands form a two-level discrete wavelet trans
`form of the image 120 as illustrated in FIG. 3. Repeating a
`discrete wavelet transform analysis on LL2 and then on the
`resulting LL3 Subband provides a 4-level DWT of the image
`120 as illustrated in FIG. 4. The DWT Subband analysis
`described with reference to FIGS. 2, 3 and 4 is often also
`known as an octave band filter bank decomposition. A
`4-level DWT of the image 120 is decomposed (analysed)
`into a single DC Subband LI4, 140, and a plurality of higher
`frequency Subbands including HL4, LH4, HH4, HL3, LH3,
`HH3, HL2, LH2, HR2, HL1, LH1 and HH1.
`In the preferred embodiment of the present invention the
`DC Subband 140 is incorporated into a bit stream as a raw
`bitmap image. That is, the DC Subband 140 is included into
`a bit Stream in a format which is readily displayable on a
`display device while the higher frequency Subbands are
`encoded into the bit Stream in a compressed format.
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 17 of 31
`
`

`

`US 6,259,819 B1
`
`15
`
`25
`
`35
`
`40
`
`S
`Typically, a Subband resulting from a discrete wavelet
`transform comprises a set of coefficients representing the
`transform coefficient of the Subband. Depending upon a Set
`of basis functions associated with a discrete wavelet
`transform, each application of the discrete wavelet transform
`to an image or Sub-image (Subband) provides a resulting set
`of DC coefficients have a propensity of increasing in value
`when compared to a corresponding coefficient before the
`application of the discrete wavelet transform. Typically, the
`increase in value of the DC coefficients, upon each appli
`cation of the discrete wavelet transform, is in the order of
`magnitude of about a factor of 2. This increase in the DC
`coefficients typically results in an increase of average inten
`sity of the DC sub-image (subband) and therefore,
`preferably, a quantisation is performed on the DC coeffi
`cients. This quantisation nay be performed with each level of
`transfrorm, or alternatively the quantisation Step may be
`applied to the coefficients of the DC Subband before incor
`porating the DC Subband 140 into a bit stream as a raw
`bitmap image.
`A variety of quantisation techniques can be applied with
`out departing from the Scope and Spirit of the present
`invention. For example, quantising the coefficients of a DC
`Subband can be achieved by bit shifting the binary repre
`Sentations of the coefficients one place to the right
`(equivalent to dividing by 2) for each level or application of
`the DWT and truncating any fractional bits. That is for the
`4-level Subband decomposition of FIG. 4, coefficients of the
`DC Subband are divided by 16 (ie. shifting 4 places to the
`right of a binary representation of the coefficients) and
`truncating or ignoring a fractional component of the coef
`ficients. Typically, in an 8-bit representation per coefficient,
`a coefficient value greater than 255 (decimal) is set to 255
`(decimal), and a coefficient value less than Zero is set to Zero.
`Binary representations of the DC Subband coefficients are
`output into a bit Stream preferably in Scan line order, In the
`example illustrated by FIG. 4, and assuming an 8-bit/pixel
`grey Scale image of size 512 pixels by 512 pixel, a 4-level
`DWT results in a DC Subband comprising 32x32 coeffi
`cients. Hence 32x32 bytes, 8-bits/coefficient, are output as a
`raw bitmap to the bit stream.
`At least one of the Subbands, other tan the DC Subband,
`is encoded into the bit stream in a compressed format. The
`compressed format Substantially provides a compressed
`bitmap image of the higher frequency Sub-images
`(Subbands) into the bit steam. Preferably the compression
`format adopted for the at least one Subband, other than the
`DC Subband, substantially utilises the technique of Subband
`or Sub-image compression hereinbefore referred to as
`SWEET, Alternately, the at least one Subband can be
`encoded into the bit Stream by other known compression
`techniques including JPEG Standard coding, Huffman cod
`ing and Arithmetic coding.
`To display a low resolution version of the image (ie. a DC
`Subband or Sub-image) on a display device, a predetermined
`number of bytes are read directly from the bit stream and
`displayed on the display device. In the example referred to
`above, a 32x32 byte raw (grey Scale) bitmap image is read
`directly from the bit Stream, with Substantially no decoding
`and preferably the bytes are arranged So a minimal manipu
`lation of the bitmap is required before display of the low
`resolution version of the image. Often, a Small size version
`(ie. a copy of a digital image dimensionally Smaller than the
`original digital) of a digital image is referred to as a
`“Thumbnail' size image. For example a 32 pixel by 32 pixel
`digital image likeness, of a 512 pixel by 512 pixel digital
`image, is referred to as a thumbnail copy of the 512x512
`pixel digital image.
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`Preferably, to decode a full size image from a bit stream
`a reverse of the coding process, used to produce the bit
`Stream, is performed. A DC Subband is inverse quantised
`from raw bitmap data incorporated into a bit Stream as
`hereinbefore described. That is for the 4-level Subband
`decomposition example described above, each byte of raw
`bitmap image data (grey Scale) is multiplied by 16 (ie.
`shifting 4 places to the left each bit of the byte) to produce
`the coefficients of the DC Subband. Non-DC Subbands are
`decoded according to an inverse technique associated with a
`compression technique used in the encoding of the Non-DC
`Subbands. For example if o at least one of the non-DC
`Subbands is encoded into a bit stream using the SWEET
`technique, then the at least one non-DC Subband is decoded
`using an associated inverse SWEET technique. A resulting
`DWT image, or Set of Subbands, are Synthesised using a 4
`level inverse DWT to obtain the original digital image, or a
`good approximation thereof.
`Although the foregoing has been described with reference
`to the example of grey-Scale digital images, the preferred
`embodiment is implemented in relation to colour images. A
`grey-Scale digital image typically comprises pixels of a
`Single colour and each pixel is assigned an 8-bit
`representation, for the Single colour, which provides the
`pixel with 256 different shades of the single colour (referred
`to as grey-Scales). A digital colour image comprises pixels
`represented by a plurality of components including Red,
`Green and Blue (RGB) components or Cyan, Magenta,
`Yellow (CMY) components or Luminance, Chrominance
`Blue and Chrominance-Red (YCbCr) to name a few. The
`preferred embodiment Separately treats each component of a
`digital colour image as an independent grey-Scale image.
`For instance, a digital colour image represented in RGB
`format (components) can be treated as three independent
`grey-Scale images corresponding to the red, green and blue
`components. Conventionally, each pixel component, of a
`colour image, is represented by an 8-bit representation per
`component and therefore an image represented by pixels
`having three components, RGB, are referred to as 24-bit
`colour images.
`Preferably a digital image represented in Red, Green and
`Blue (RGB) components 170 is converted to luminance
`chrominance format (YCbCr) 171 as schematically illus
`trated in FIG. 6. The human visual system is typically less
`Sensitive to chrominance than it is to luminance therefore the
`chrominance components Cb 172 and Cr 173 are commonly
`Sub-Sampled providing leSS information to compress which
`results in a better compression than having to compress each
`component without Sub-Sampling. Sub-Sampling of the
`chrominance data provides “lossy compression Since Some
`information is ignored or discarded by the Sub-Sampling,
`however the degradation to the Image is generally not
`noticeable by the human eye. The luminance component Y
`174 and the two chrominance components 172, 173 of the
`digital image are each discrete wavelet transformed to
`provide a DC Subband for each YCbCr component of the
`image. The DC Subband (sub-image) of each YCbCr com
`ponent of the image can be converted back to RGB before
`outputting a raw bitmap of the DC Subband in ROB format
`into a bit stream. This may be performed in concert with the
`aforementioned quantisation of the DC Subband to provide,
`for example, 8 bits per colour for the DC Subband thus
`enabling the DC Subband to be displayed directly on a video
`display. Non-DC Subbands are encoded (compressed) into
`the bit stream as previously described. The bit stream,
`representing the compressed image, can then be Stored or
`transmitted as required.
`
`UNIFIED PATENTS EXHIBIT 1033
`UNIFIED PATENTS, LLC v. MEMORYWEB, LLC
`IPR2021-01413
`Page 18 of 31
`
`

`

`US 6,259,819 B1
`
`15
`
`7
`To decode the entire bit stream and obtain substantially a
`full Scale digital image an inverse process is followed The
`raw bitmap of the DC Subband in RGB format is extracted
`from the bit stream and converted to YCbCr format. The
`non-DC Subbands encoded into the bit stream are decoded
`(uncompressed) and the result, together with the DC Sub
`band in YCbCr format are inverse discrete wavelet trans
`formed a predetermined number of times to provide the
`desired full Scale digital image.
`If it is desired to reproduce only the thumbnail image
`representation, for example to assist in browsing operations
`in a database of images, the Stored bit Stream is located in
`memory and the DC Subband extracted. Because the DC
`Subband is in an RGB format, the DC Subband may be
`directly displayed, or displayed using only minimal
`processing, to reveal the thumbnail.
`Although a minor disadvantage in computational perfor
`mance is incurred by converting an RGB image into a
`YCbCr image, provided the DC Subband is small, the loss in
`computational performance is not Substantial compared with
`the compression advantage obtained by Sub-Sampling
`chrominance components of the YCbCr image.
`Preferably, a bit stream comprising a DC-Subband, as raw
`bitmap, and high frequency Subbands in a compressed
`format, further includes header information, usually at the
`beginning of the bit Stream, which provides information
`about the raw bitmap. For example, the header may include
`the length in bytes of a raw bitmap, a location pointer to a
`position within a bit stream for locating where in the bit
`Stream the raw bitmap is positioned, if the raw bitmap does
`not substantially follow the header information or if the raw
`bitmap is located in different positions in a plurality of
`images.
`Embodiments of the invention can preferably be practised
`using a conventional general-purpose computer System 150,
`such as that shown in FIG. 5, wherein the process described
`with reference to FIG. 1 to FIG. 4 is implemented as
`Software executed on the computer, system 150. The soft
`ware may be derived from a computer readable medium
`Such as a disk, tape, or a computer network Such as the
`Internet. The computer system 150 comprises a computer
`module 151, input devices including a keyboard 152 and a
`mouse 153, and a display device 154.
`The computer module 151 includes at least one processor
`unit 155, a memory unit 156 which typically include random
`access memory (RAM) and read only memory (ROM),
`interface devices including a Video interface 157, and an
`input/output interface, 15