1
`
`Exhibit 2010
`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-01897
`
`

`
`compression of astronomical images because even though the sky is nearly constant, the noise in the sky
`ensures that only very short runs of equal pixels occur. The obvious way to make run-length coding more
`eective is to force the sky to be exactly constant by setting all pixels below a threshold chosen to be just
`above the sky to the mean sky value. However, then one has lost any information about objects close
`to the detection limit. One has also lost information about local variations in the sky brightness, which
`severely limits the accuracy of photometry and astrometry on faint objects. Worse, there may be extended,
`low surface brightness objects that are not detectable in a single pixel but that are easily detected when
`the image is smoothed over a number of pixels; such faint structures are irretrievably lost when the image
`is thresholded to improve compression.
`This paper describes an image compression algorithm that is well-suited to astronomical images. The
`method has steps:   an intensity mapping to generate an image that has roughly constant noise in
`each pixel,  an orthonormal wavelet transform, and   quadtree coding of the bit-planes of the wavelet
`coecients. The quadtree values may be further compressed by any standard compression technique, such
`as Human or arithmetic coding. This method is much better than techniques that keep only the wavelet
`coecients with the largest amplitudes.
`If the -D Haar transform is used as the wavelet transform, the calculations can be carried out
`using integer arithmetic, and the method can be used for both lossy and lossless compression. The Haar
`transform basis function are well-suited to most astronomical images because they are highly localized, and
`it is possible to adjust the coecients during decompression to reduce the blockiness that comes from using
`such functions. The performance of the algorithm using smoother, longer range wavelets is also shown;
`they can give slightly better lossy compression, but they are not eective for lossless compression using
`this scheme.
`This method is being used by the Space Telescope Science Institute to compress digitized versions
`of the Palomar and ESO Sky Survey plates for distribution on CD-ROM. Images compressed to about
` . bitspixel are equivalent to the original images under both visual inspection and quantitative analysis.
`Images compressed to . bitspixel are still useful, though some of the faintest objects are lost at such
`high compression factors.
`This technique has also been used as the basis of a progressive image transmission system that can
`be used for either remote observing or access to remote image archives. After less than  of the data
`have been received, the image is visually similar to the original, so it is possible to assess the quality of
`images very quickly. If necessary, the entire compressed data set can be sent so that the original image
`is recovered exactly. It is also possible to speed the transmission even further by transmitting rst only
`enough information to construct a version of the image that has been binned in blocks of    pixels; this
`is a natural feature of wavelet-based schemes.
`
`. THE H-TRANSFORM
`
`The -dimensional Haar transform also known as the H-transform or the S-transform can be used as
`the basis of an eective compression method for astronomical images(cid:0). The H-transform is calculated
`for an image of size N  N as follows:
`
` Divide the image up into blocks of    pixels. Call the  pixels in a block a, a , a , and a .
`
` For each block compute  coecients:
`
`h = a + a + a + a=
`hx = a + a (cid:0) a (cid:0) a=
`hy = a (cid:0) a + a (cid:0) a=
`hc = a (cid:0) a (cid:0) a + a=
`
` 
`
` Construct a N (cid:0)  N (cid:0) image from the h values for each    block. Divide that image up into
`   blocks and repeat the above calculation. Repeat this process N times, reducing the image in
`size by a factor of  at each step, until only one h value remains.
`
`2
`
`

`
`This calculation can be easily inverted to recover the original image from its transform. The transform
`is exactly reversible using integer arithmetic if one is careful with the low-order bits of the coecients.
`It is straightforward to extend the denition of the transform so that it can be computed for non-square
`images that do not have sides that are powers of ; the most eective way to do this is to assume reected
`boundary conditions at the edges of the image. The H-transform can be performed in place in memory
`and is very fast to compute, requiring about M = integer additions for a M  M image.
`The H-transform can be derived from the -dimensional Haar transform, which involves taking sums
`and dierences of pairs of adjacent elements in a vector. Apply a single sumdierence step of the -D
`transform along the rows of the images, then along the columns of the transformed image. Repeat this
`rowcolumn transform, using only the sum coecients   of the original image as input. Repeat until
`only a single element remains.
`
`. . Other wavelet transforms
`The H-transform is a simple -dimensional discrete wavelet transform. The compression scheme described
`here is easily adapted for use with other wavelet transforms. Any -dimensional discrete wavelet transform
`can be converted to a -D transform as outlined in the last section, and the coecients of that -D
`transform can be eciently coded using the schemes described below. In this paper, compression results
`are also shown for an algorithm based on the Daubechies D wavelet transform. The D transform has
`been modied so that it uses reected boundary conditions rather than periodic boundary conditions.
`The major advantage of the H-transform over the Daubechies and similar wavelet transforms is that the
`H-transform can be performed entirely with integer arithmetic, making it exactly reversible. Consequently
`it can be used for either lossless or lossy compression as indicated below and one does not need a special
`technique for the case of lossless compression as was required, e.g., , for the JPEG compression standard
`and by FITSPRESS. However, the smoothness aorded by higher-order transforms can be advantageous.
`
` . QUANTIZATION
`
`If the image is nearly noiseless, the H-transform is somewhat easier to compress than the original image
`because the dierences of adjacent pixels as computed in the H-transform tend to be smaller than the
`original pixel values for smooth images. Consequently fewer bits are required to store the values of the
`H-transform coecients than are required for the original image. For very smooth images the pixel values
`may be constant over large regions, leading to transform coecients that are zero over large areas.
`Noisy images still do not compress well when transformed, though. Suppose there is noise in each
`pixel of the original image. Then from propagation of errors, the noise in each of the H-transform coecients
`is also . To compress noisy images, divide each coecient by S , where S  is chosen according to how
`much loss is acceptable. This reduces the noise in the transform to :=S because the largest error is 
`the least signicant bit of the quotient, so that large portions of the transform are zero or nearly zero
`and the transform is highly compressible.
`Why is this better than simply quantizing the original image? As discussed above, if we divide the
`image by then we lose all information on objects that are within : of sky in a single pixel, but that
`are detectable by averaging a block of pixels. On the other hand, in dividing the H-transform by , we
`preserve the information on any object that is detectable by summing a block of pixels! The quantized
`H-transform preserves the mean of the image for every block of pixels having a mean signicantly dierent
`than that of neighboring blocks of pixels.
`If the noise is not constant across the image then this quantization method must be modied. The best
`approach we have found is to rst scale the data to force the noise to be approximately constant in each
`pixel, and then to apply the H-transform and quantization described above. For CCD data, for example,
`the noise is a combination of Poisson counting statistics and readout noise. If we replace the input image
`Iij by a scaled image Uij = qIij + N , where N is the readout noise in each pixel, then the image Uij
`has noise U ’ in each pixel. U can then be compressed eciently using the method described in this
`paper. Unfortunately, the use of this method for lossless compression is rather messy because considerable
`eort is required to make the square root transformation exactly reversible.
`
`3
`
`

`
`Original
`
`   pixel section of image from digitized Palomar Sky Survey E-plate of Coma
`Figure .
`galaxy cluster. Image has -bits; a logarithmic gray scale is used to make the noise near the sky
`brightness level visible.
`
`. QUADTREE CODING
`
`The quantized H-transform has a rather peculiar structure. Not only are large areas of the transform image
`zero, but the non-zero values are strongly concentrated in the lower-order coecients. The best approach
`we have found to code the coecient values eciently is quadtree coding of each bit-plane of the transform
`array. Quadtree coding has been used for many purposes; the particular form we are using was suggested
`by Huang and Bijaoui for image compression.
`
` Divide the bit-plane up into  quadrants. For each quadrant code a ‘ ’ if there are any -bits in the
`quadrant, else code a ‘’.
`
` Subdivide each quadrant that is not all zero into  more pieces and code them similarly. Continue
`until one is down to the level of individual pixels.
`
`This coding which Huang and Bijauoi call hierarchic -bit one" coding is obviously very well suited
`to the H-transform image because successively lower orders of the H-transform coecients are located in
`successively divided quadrants of the image.
`We follow the quadtree coding with a xed Human coding that uses bits for quadtree values that
`are common e.g., , , , and  and uses  or  bits for less common values. This reduces
`the nal compressed le size by about  at little computational cost. Slightly better compression can be
`achieved by following quadtree coding with arithmetic coding , but the CPU costs of arithmetic coding
`are not, in our application, justied for  better compression. We have also tried using arithmetic
`coding directly on the H-transform, with various contexts of neighboring pixels, but nd it to be both
`computationally inecient and not signicantly better than quadtree coding.
`For completely random bit-planes, quadtree coding can actually use more storage than simply writing
`the bit-plane directly; in that case we just dump the bit-plane with no coding.
`
`4
`
`

`
`0.16 bits/pixel
`
`0.32 bits/pixel
`
`0.81 bits/pixel
`
`1.79 bits/pixel
`
`Eect of compression by H-transform and quadtree coding scheme described in this
`Figure .
`paper. This is also a sequence of images using the progressive transmission scheme; each image
`is the result of coding and transmitting another bit-plane from the H-transform.
`
`5
`
`

`
`0.16 bits/pixel
`
`0.32 bits/pixel
`
`0.81 bits/pixel
`
`1.79 bits/pixel
`
`Images from Fig.  decompressed using adaptive smoothing method to reduce block-
`Figure .
`ing artifacts.
`
`6
`
`

`
`. EXAMPLES
`
`As an example, Figure shows a  section :: arcmin from a digitized version of the Palomar
`ObservatoryNational Geographic Society Sky Survey plate containing the Coma cluster of galaxies. This
`is a -bit image with noise ’  in each pixel. Figure  shows the resulting image for S = ,  ,
` , and . These images are compressed by factors of , ,  , and  using the quadtree coding
`scheme. In all cases a logarithmic gray scale is used to show the maximum detail in the image near the sky
`background level; the noise is clearly visible in Figure . The image compressed by a factor of is hardly
`distinguishable from the original. In quantizing the H-transform we have adaptively ltered the original
`image by discarding information on some scales and keeping information on other scales. This adaptive
`ltering is most apparent for high compression factors, where the sky has been smoothed over large areas
`while the images of stars have hardly been aected.
`The adaptive ltering is, in itself, of considerable interest as an analytical tool for images. For
`example, one can use the adaptive smoothing of the H-transform to smooth the sky without aecting
`objects detected above the locally determined sky; then an accurate sky value can be determined by
`reference to any nearby pixel.
`The blockiness that is visible in Figure  is the result of dierence coecients being set to zero over
`large areas, so that blocks of pixels are replaced by their averages. It is possible to eliminate the blocks by an
`appropriate ltering of the image. A simple but eective lter can be derived by adjusting the H-transform
`coecients as the transform is inverted to produce a smooth image; as long as changes in the coecients
`are limited to S =, the resulting image will still be consistent with the quantized H-transform. The
`adaptively smoothed images corresponding to those in Figure  are shown in Figure .
`
`. . Astrometric and photometric properties of compressed images
`Astronomical images are not simply subjected to visual examination, but are also subjected to careful
`quantitative analysis. For example, for the image in Figure one would typically like to do astrometric
`positional measurements of point sources to an accuracy much better than pixel, photometric bright-
`ness measurements of objects to an accuracy limited only by the detector response and the noise, and
`accurate measurements of the surface brightness of extended sources.
`We have done some experiments to study the degradation of astrometry and photometry on the
`compressed images compared to the original images . Even the most highly compressed images have very
`good photometric properties for both point sources and extended sources; indeed, photometry of extended
`objects can be improved by the adaptive ltering of the H-transform. Astrometry is hardly aected by
`the compression for modest compression factors up to about a factor of  for our digitized photographic
`plates, but does begin to degrade for the most highly compressed images.
`These results are based on tests carried out with tools optimized for the original images; it is likely
`the best results will be obtained for highly compressed images only with analysis tools specically adapted
`to the peculiar noise characteristics of the compressed images.
`
`. PROGRESSIVE TRANSMISSION
`
`Note that by coding the transform one bit-plane at a time, the compressed data can be viewed as an
`incremental description of the image. One can initially transmit a crude representation of the image using
`only the small amount of data that is required for the sparsely populated, most signicant bit-planes. Then
`the lower bit-planes can be added one by one until the desired accuracy is achieved. This could be useful,
`for example, if the data is to be retrieved from a remote database | one could examine the crude version
`of the image retrieved very quickly and abort the transmission of the rest of the data if the image is
`judged to be uninteresting. A version of this progressive transmission algorithm has been developed for
`the Wisconsin-Indiana-Yale-NOAO WIYN telescope . It will be used for remote observing and transfer
`of data over networks.
`The improvement of the image during the progressive transmission is visible in Figure , where each
`successive panel represents the addition of another bit-plane from the H-transform. For comparison,
`
`7
`
`

`
`0.22 bits/pixel
`
`0.46 bits/pixel
`
`1.20 bits/pixel
`
`2.11 bits/pixel
`
`Progressive transmission of image by coding bit-planes of original image rather than
`Figure .
`H-transform using quadtree coding. Results are much inferior to those H-transform algorithm
`shown in Fig. .
`
`8
`
`

`
`0.13 bits/pixel
`
`0.28 bits/pixel
`
`0.73 bits/pixel
`
`1.67 bits/pixel
`
`Progressive transmission of image using Daubechies D discrete wavelet transform
`Figure .
`instead of H-transform. Results are slightly better than those shown in Fig.  for smooth objects,
`but show ringing artifacts around bright stars that might be objectionable for some applications.
`
`9
`
`

`
`Image by pixel
`Image by bitplane
`H-transform
`D4
`
`0.01
`
`0.10
`Bits/pixel
`
`1.00
`
`10.00
`
`4
`
`3
`
`2
`
`1
`
`0
`
`Normalized RMS Error
`
`Figure . Mean square error in compressed images as a function of compression factor for various
`progressive transmission methods. The top curve shows the results from simply transmitting the
`pixels one by one with no compression. Other methods use quadtree coding on bit-planes of the
`image itself, the H-transform, and the D transform.
`
`Figure  shows the performance of a progressive transmission scheme based on quadtree coding of the bit-
`planes of the image itself rather than a transformed version of the image. This method is a big improvement
`over simply sending the image pixel by pixel with no compression, but the results are not nearly as good
`as those obtained using the H-transform.
`On the other hand, it may be possible to improve on the H-transform using other wavelet transforms.
`The results of progressive transmission using the Daubechies discrete wavelet transform D are shown in
`Figure . Here the results appear slightly better than for the H-transform, especially for smooth objects.
`This is expected since the D wavelets form a smoother basis than the Haar functions. However, the
`D-compressed images do show some ringing around bright stars visible as holes" or ears" around the
`stars.
`The D transform has been used previously for astronomical image compression by Press, though in
`that application he simply retained the largest wavelet coecients rather than coding bit-planes. Press’s
`version of the two-dimensional D transform also has the drawback that it includes basis functions that are
`high frequency, hence localized, in one direction but low frequency, hence global, in the other direction. The
`D transform used here has only approximately isotropic basis functions. Keeping the largest coecients
`exactly is less ecient than keeping bit-planes of all coecients; the dierence is especially noticeable when
`one attempts to construct high delity compressed images, where the largest coecients" method requires
`
`10
`
`

`
` times as much data as the bit-plane method.
`Figure  summarizes the performance of various algorithms using the mean square dierence from
`the original image as a measure of image quality. This measure does not always correlate well with
`visual quality, but it is appropriate for these astronomical images where quantitative analysis is important.
`The gure shows the RMS error normalized by the noise in the original image versus the compression,
`expressed as the number of bits per pixel required to store the image. A normalized RMS error of unity
`means that the original and compressed images are consistent to about the noise level in the data.
`Sending the image pixel-by-pixel is never competitive with these methods. Quadtree coding of the
`original image results in reasonably good results for lossless compression  .  bitspixel but poor quality
`for the early versions of the image constructed from the rst few bit-planes. The D image is slightly
`better than the H-transform image at high compressions in agreement with the visual assessment, but is
`considerably worse for lossless compression  . bitspixel for D versus . bitspixel for H-transform.
`Interestingly, the best lossless compression of these images is achieved by quadtree coding the dierence
`of adjacent pixels along rows of the image  . bitspixel. However, these dierence coecients are
`absolutely useless for lossy compression because a slight change in any dierence translates to a long streak
`across the image.
`
`. CONCLUSIONS
`
`The algorithms described in this paper, based on either the H-transform or the Daubechies D wavelet
`transform, have been shown to be capable of producing highly compressed images that are very faithful
`to the original. Algorithms designed to work on the original images can give comparable results on object
`detection, astrometry, and photometry when applied to the images compressed by a factor of or more.
`Further experiments will determine more precisely just what errors are introduced in the compressed data;
`it is possible that certain kinds of analysis will give more accurate results on the compressed data than on
`the original because of the adaptive ltering of the H-transform.
`The D-compressed images are slightly superior to the H-transform images at high compression factors,
`though the D images do show some artifacts that might cause trouble for some image analysis programs.
`For lossless compression the H-transform method is better. For progressive transmission the H-transform
`leads to a very clean implementation that does not require any residual image to be transmitted to get a
`perfectly reconstructed image.
`This work was supported by grant NAGW-  from the Science Operations Branch of NASA head-
`quarters. The Space Telescope Science Institute is operated by AURA with funding from NASA and
`ESA.
`
`REFERENCES
`
` . Haar, A. , Math. Ann.  , .
`. Fritze, K., et al. , Astronomische Nachrichten,  ,  .
` . Richter, G. M. , Astronomische Nachrichten,  ,  .
`. Capaccioli, M., et al. , Astronomische Nachrichten, ,  .
`. Blume, H., and Fand, A.  , SPIE Vol. , Medical Imaging III: Image Capture and Display, p. .
`. Daubechies, I. , Comm. Pure and Appl. Math.,  , .
`. Press, W. H. , in Astronomical Data Analysis Software and Systems I, eds. D. M. Worrall et al.,
`San Francisco: Astronomical Society of the Pacic, p. .
`. Samet, H. , ACM Computing Surveys, , .
` . Huang, L, and Bijaoui, A. , Experimental Astronomy, , .
` . Witten, I. H., Radford, M. N., and Cleary, J. G. , Communications of the ACM, , .
` . White, R. L., Postman, M., and Lattanzi, M. G. , in Digitized Optical Sky Surveys, eds. H. T.
`MacGillivray & E. B. Thomson Amsterdam: Kluwer, p. .
` . Percival, J. W., and White, R. L. , in Astronomical Data Analysis Software and Systems II, eds.
`R. J. Hanisch et al., San Francisco: Astronomical Society of the Pacic.
`
`11