Lizardtech, Inc. v. Earth Resource Mapping, Inc.

• Citation: 424 F.3d 1336
• Decision Date: 04 October 2005
• Docket Number: No. 05-1062.,05-1062.
• Parties: LIZARDTECH, INC., Plaintiff-Appellant, and Regents of the University of California, Plaintiffs v. EARTH RESOURCE MAPPING, INC., and Earth Resource Mapping Pty Ltd. (now Earth Resource Mapping Ltd.), DefendantsAppellees.
• Court: United States Courts of Appeals. United States Court of Appeals for the Federal Circuit

Page 1336

424 F.3d 1336

LIZARDTECH, INC., Plaintiff-Appellant, and Regents of the University of California, Plaintiffs v. EARTH RESOURCE MAPPING, INC., and Earth Resource Mapping Pty Ltd. (now Earth Resource Mapping Ltd.), DefendantsAppellees.

No. 05-1062.

United States Court of Appeals, Federal Circuit.

October 4, 2005.

Philip P. Mann, Mann Law Group, of Seattle, Washington, argued for plaintiff-appellant. Of counsel on the brief were Robert J. Carlson and Kevan L. Morgan, Christensen O'Connor Johnson & Kindness PLLC, of Seattle, Washington.

Stewart M. Brown, DLA Piper Rudnick Gray Cary U.S. LLP, of San Diego, California, argued for defendants-appellees. With him on the brief was Richard T. Mulloy.

Before LOURIE, SCHALL, and BRYSON, Circuit Judges.

BRYSON, Circuit Judge.

LizardTech, Inc., appeals the final judgment of the United States District Court for the Western District of Washington in this patent case. On the motion of defendants Earth Resource Mapping, Inc., and Earth Resource Mapping Pty Ltd. (collectively "ERM"), the district court granted summary judgment, holding that ERM did not infringe U.S. Patent No. 5,710,835 ("the '835 patent"), and that the patent was invalid. LizardTech, Inc. v. Earth Res. Mapping, Inc., No. C99-1602C, 2000 WL 34502412 (W.D.Wash. March 14, 2004). We affirm.

I

A

The technology at issue in this case involves what are known as "wavelet transforms." Wavelet transforms allow digital images to be greatly compressed with very little loss of information. In particular, they help in the image compression process because they can be used to transform image data into a form in which it is easier to determine what information in the data is relevant, so that irrelevant and redundant data can be filtered out. See Pankaj N. Topiwala, Introduction to Compression, in Wavelet Image and Video Compression 61, 61-63 (Pankaj N. Topiwala ed., 1998).

For purposes of digital image compression, the most useful type of wavelet transform is what is called a discrete wavelet transform ("DWT"). The DWT of the image can be calculated by repeatedly applying two algorithms to the image using functions known as high-pass and low-pass finite impulse response filters. See A. Jensen & A. la Cour-Harbo, Ripples in Mathematics: The Discrete Wavelet Transform 69 (2001). The high-pass filter contains certain values that change as a function of the distance from the center of the filter, where that distance is measured in terms of the pixels of the to-be-filtered image. Thus, the filter has one value at a distance of one pixel from the center, another value at a distance of two pixels from the center, and so on. The values of the high-pass filter are chosen so that when the filter is applied to the image the small, high-frequency information in the image is retained, while the large, low-frequency information is filtered out. The reverse is true for the low-pass filter. See Pankaj N. Topiwala, Time-Frequency Analysis, Wavelets and Filter Banks, in Wavelet Image and Video Compression 33, 50.

While the task of choosing the high-pass and low-pass filters may be complicated, their application to the image is not. See Time-Frequency Analysis, Wavelets and Filter Banks, supra, at 51-57. The high-pass filter (or, more precisely, the mirror image of what is normally referred to as the high-pass filter) is initially centered on the first pixel in the image. The value of the filter at each pixel along the row of the image that contains the first pixel is then multiplied by the data value of the digital image of each pixel in that row. The resulting products are added together, and the sum, called the DWT coefficient, is assigned to the original first pixel. The filter is then shifted to be centered on the next pixel in the row, the entire process is repeated, and the second coefficient is derived. That process is repeated to derive coefficients for the entire row of pixels and then for all the pixel rows constituting the image. The same operation is then applied to the original image using the low-pass filter (that is, the mirror image of the low-pass filter) instead of the high-pass filter.

This process generates two coefficients for each pixel. Since no new information is created as a result of this oversampling, the coefficients from every other pixel can be discarded with no loss of information. After completing this "down-sampling," the same high-pass and low-pass filtering is performed on the down-sampled coefficients in the column direction. Finally, upon down-sampling the results of the filtering in the column direction, three types of coefficients are obtained: those multiplied by a high-pass filter in both directions ("the high-high decomposition"), those multiplied by low-pass filters in both directions ("the low-low decomposition"), and those multiplied by a low-pass filter in one direction and a high-pass filter in the other. Those coefficients can then be easily compressed, resulting in a minor loss of information relating to the original image, but using much less storage space than was necessary to store that image. In practice, the low-low decomposition has most of the relevant information, which is the reason that compression of the image is easier to perform after applying a DWT on the image. See Pankaj N. Topiwala, Wavelet Still Image Coding: A Baseline MSE and HVS Approach, in Wavelet Image and Video Compression 95, 96. However, the fact that the low-low decomposition contains most of the data also means that the entire process can be rerun on the low-low decomposition with a different set of filters, creating three more sets of data. The low-low decomposition of that set can in turn be selected and decomposed. Furthermore, the processes of filtering and down-sampling can be inverted with no loss of information. By using both the final, uncompressed coefficients from the transform and the original filters, the original image can be recreated. Only if the coefficients are compressed is there a loss of information. Additionally, if a low-low decomposition is inverted, it will produce an image that retains all the low-bandpass information of the original image, but is one quarter the size of the original image (or 1/16, 1/64, etc., of the original size depending on how many times transforms have been applied to the low-low decompositions and which of those low-low decompositions is inverted). Therefore, by choosing the appropriate low-low decomposition to invert, images with different resolutions can be created.

One problem with this method of calculating a DWT is that an image has edges, while the filter functions do not.¹ That means that for distances beyond the edge of the image, the product of the filter function and the image data must be set to an artificial value, usually zero. When the coefficients produced by using those artificial values are inverted, the recreated image will often have "defects," since fake information was used in the process of calculating the DWT.

A second problem with this method of calculating a DWT on a computer is that the entire image must be placed in the computer's memory, which can be difficult in the case of very large images. Therefore, prior art computer programs broke up the image into pieces, or "tiles," and calculated the DWT of each tile separately so that only the data within a single tile needed to be in the computer's memory at once. However, breaking the image into tiles creates boundaries between the tiles within the image. If the outside of the tiles is artificially set to zero during the DWT process, the product of the filter function and the image data outside the tile will be zero, and a large number of edge artifacts may be created. Reducing edge artifacts while performing a DWT on individual tiles of an image for compression purposes is the object of the '835 patent.

The '835 patent solves the boundary problem by taking account of the fact that the values of the image pixels outside a given tile are known. See '835 patent, col. 2, ll. 53-57. That is, breaking the image into tiles is simply a useful means of making the DWT calculation practical on a computer with limited memory; the rest of the image outside the tile is not lost even if it is temporarily set to zero for the purpose of calculating the DWT of the tile. The '835 patent uses this fact by calculating DWT coefficients outside the boundary of the tile. See id., col. 7, ll. 42-45 ("Note that DWT 120 effects an expansive transform, that is, the number of non-zero coefficients emanating from the routine is generally greater than the number of pixels that are input to it.") For pixels outside the tile that are set to zero, the high-pass and low-pass filters are still shifted to be centered on those pixels, multiplied by the value of the pixels in the row or column direction, and added together. That process results in non-zero DWT coefficients because, even though the filters are centered over a zeroed pixel, the filters still have a non-zero value within the tile where the pixels have not been zeroed. The coefficients in the zeroed region are then saved. See id., col. 7, ll. 54-57. Later, when the DWT is performed on the adjoining tile, and the pixels within that tile are no longer zeroed, the resulting DWT coefficients of the pixels in that tile are added to the previously saved coefficients corresponding to those pixels. See id., col. 7, ll. 46-51. That summation results in final DWT coefficients for those pixels that are exactly the same as if there had never been any tiling or zeroing of those pixels at all. That is, the process produces a "seamless" DWT. See id., col. 6, ll. 6-13 (it "effectively produces the same output as the DWT routine would output if applied to the entire image").

B

LizardTech, the exclusive licensee of the '835 patent, brought this action alleging that ERM's geospatial imaging software product, ER Mapper, infringed claims 1, 13, 21, 22, 23, 24,...