Research Corp. Technologies, Inc. v. Microsoft Corp.

• Decision Date: 08 December 2010
• Docket Number: No. 2010-1037,2010-1037
• Citation: 97 U.S.P.Q.2d 1274,627 F.3d 859
• Parties: RESEARCH CORPORATION TECHNOLOGIES, INC., Plaintiff-Appellant, v. MICROSOFT CORPORATION, Defendant-Appellee.
• Court: U.S. Court of Appeals — Federal Circuit

627 F.3d 859

97 U.S.P.Q.2d 1274

RESEARCH CORPORATION TECHNOLOGIES, INC., Plaintiff-Appellant,

v.MICROSOFT CORPORATION, Defendant-Appellee.

No. 2010-1037.

United States Court of Appeals,Federal Circuit.

Dec. 8, 2010.

J. Michael Jakes, Finnegan, Henderson, Farabow, Garrett & Dunner, LLP, of Washington, DC, argued for plaintiff-appellant. With him on the brief were Susan Y. Tull; and Erika H. Arner, of Reston, VA. Of counsel on the brief were M. Miller Baker, Blair M. Jacobs, Paul E. Poirot and Natalia V. Blinkova, McDermott, Will & Emery LLP, of Washington, DC; and Michael J. Rusing, Rusing & Lopez, PLLC, of Tucson, AZ. Of counsel were Isaac Crum, Stephen K. Shahida and Bureden J. Warren, McDermott, Will & Emery LLP, of Washington, DC.

John D. Vandenberg, Klarquist Sparkman, LLP, of Portland, OR, argued for defendant-appellee. With him on the brief were Stephen J. Joncus, Todd M. Siegel, Kristin L. Cleveland and Salumeh R. Loesch. Of counsel on the brief were Stephen P. McGrath, Microsoft Corporation, of Redmond, WA; and Jeffrey Willis, Snell & Wilmer, L.L.P., of Tucson, AZ.

Before RADER, Chief Judge, NEWMAN and PLAGER, Circuit Judges.

RADER, Chief Judge.

Research Corporation Technologies, Inc. ("RCT") initiated this action against Microsoft Corporation ("Microsoft"), alleging infringement of six related patents: U.S. Patent Nos. 5,111,310 ("'310 patent"); 5,341,228 ("'228 patent"); 5,477,305 ("'305 patent"); 5,543,941 ("'941 patent"); 5,708,518 ("'518 patent"); and 5,726,772 ("'772 patent"). The United States District Court for the District of Arizona held that certain claims of the '310 and '228 patents were invalid under 35 U.S.C. § 101. The district court further held that certain claims of the '772 and '305 patents were not entitled to claim the benefit of earlier filed applications that led to the '310 and '228 patents.

Because the '310 and '228 patents claim patent-eligible subject matter, this court reverses the district court on that point. This court also finds that claim 29 of the '305 patent deserves the earlier filing date and thus reverses the district court's effective date ruling and remands. At the same time, this court affirms the district court's decision that claims 4 and 63 of the '772 patent are not entitled to the earlier effective filing date.

I

RCT's six patents relate to digital image halftoning. Digital images are, in fact, thousands of pixels arranged in arrays of rows and columns. Each pixel in a black-and-white image contains information about the gray level of the image at that particular position. A black-and-white image can have 256 shades of gray. A gray level 1 represents black and a gray level 256 represents white, with intervening numbers representing various shades of gray. For color images, a computer creates separate color-specific arrays of pixels, one array for each primary color. A color-specific array has pixels containing information about the shade level of that color at that particular position.

Digital images often show shades of gray and even a spectrum of colors. Nonetheless, computer displays and printerscan only use a limited number of primary colors to display these digital images. Halftoning bridges this gap by simulating a continuous tone image through the use of dots. Halftoning techniques allow computers to present many shades and color tones with a limited number of pixel colors. These techniques place the dots of primary colors in a formation that gives the viewer the illusion of many more shades of gray or varying colors. Black-and-white printers use only black dots to give the illusion of shades of gray. Color printers typically use four primary colors-cyan, magenta, yellow, and black-to give the illusion of a spectrum of colors. Color displays often use three primary colors-red, green, and blue-to achieve the same effect. Digital halftoning technology thus allows computer displays and printers to render an approximation of an image by using fewer colors or shades of gray than the original image. For the most part, this opinion discusses halftoning technology with reference primarily to a black-and-white image with varying shades of gray, rather than a color image. The principles, however, are the same.

One method of generating a digital halftoned image is called "thresholding." The thresholding technique uses a two-dimensional array called a "mask" that is populated with predetermined threshold numbers, which are typically between 1 and 256. The thresholds do not relate at all to the image to be halftoned. The thresholding technique compares the gray level at each pixel of the image against the threshold that corresponds to the pixel's position. If the gray level exceeds the corresponding threshold, the pixel is turned on, i.e., the computer places a "1" in the appropriate memory space. The resulting halftone image is a two-dimensional array of zeros and ones.

This imaging field uses various ways to measure the quality of a halftoning process. One method examines the "dot profiles" produced by the halftoning process. A dot profile is a halftone image that would be produced if the original image were a single shade of gray, ( i.e., all of the pixels have the same gray level). A dot profile is essentially a pattern of black dots on a white piece of paper. A dot profile for an original image with a high gray level would have more ones and thus more black dots than a dot profile for an image with a low gray level. Closely spaced dots are said to occur at a high frequency, and those far apart are said to occur at a low frequency. Because the human visual system is more sensitive to low frequencies than to high frequencies, viewers consider dot profiles with few low-frequency dots visually pleasing.

Another way to observe the quality of a halftone is to use a power spectrum associated with each dot profile obtained from the halftoning process. A power spectrum is a graph showing the relative frequency of dots in the dot profile at a particular gray level. The shape of the power spectrum characterizes the type of "noise" that the dot profiles exhibit. For example, a dot profile with a "white noise" exhibits a power spectrum where the frequencies are approximately equal across the graph. In contrast, a dot profile with a "blue noise" exhibits a power spectrum with primarily high frequency components and negligible low frequency components.

Figure 1 of the '310 patent shows an ideal blue noise power spectrum, which is unattainable in the real world.

Image 1 (3.85" X 2.22") Available for Offline Print

'310 patent fig.1. The horizontal axis represents the radial frequency, which is the reciprocal of the average spacing between the dots in the dot profile. A blue noise power spectrum has negligible frequency components below the principal frequency and high frequency components above the principal frequency. The principal frequency, fg, varies from one gray level g to another:

Image 2 (2.49" X .83") Available for Offline Print

Id. col.6 ll.25-38. In this equation, R is the distance between addressable dots on the display and the gray level g is normalized from zero to one. The principal frequency assumes its highest value for 50% gray level because at this level there are equal numbers of black and white dots. Each dot profile exhibits a power spectrum with a different radial frequency because as the gray level increases, so does the number of dots in the dot profile.

Drs. Kevin J. Parker and Theophano Mitsa, the named inventors of the six RCT patents, conceived of an improved blue noise mask. The inventors' halftoning technique used a blue noise mask, which was stored in a computer's memory, to carry out a pixel-by-pixel comparison of the mask to the digital image. Their halftoning technique compares the gray level of each pixel in a digital image to the corresponding threshold number in the blue noise mask to produce a halftone image.

The claimed blue noise mask has unique first and second order properties. When thresholded at A% of the maximum level, exactly A out of every 100 pixels will be greater than the threshold value. For example, when the blue noise mask is thresholded at 50% of the maximum level, exactly half of the pixels will be turned on. In addition, the dots are distributed so that they form a blue noise pattern, which means that "the resulting dot profile is a locally aperiodic and isotropic binary pattern with small low-frequency components." Id. col.5 ll.60-63. The blue noise mask also has wraparound properties such that a smaller blue noise mask can be used to halftone a larger image by tiling the mask over an appropriate number of periods.

In constructing the claimed blue noise mask, one of skill in this art would first create a dot profile that corresponds to the 50% gray level. Next, the skilled artisan would sequentially construct the dot profilesfor other gray levels. The dot profile for the next gray level g + ? g is built from the dot profile for the gray level g by converting a given number of pixels. If the next gray level is higher, a certain number of zeros are converted into ones; if the next gray level is lower, a certain number of ones are converted into zeros. The pixel that was turned on for a gray level g remains turned on for all dot profiles with a gray level g or higher. As these pixels change value from one sequential profile to the next, the mask keeps track of those changes. The pixel-value conversion that occurs at every pixel location is encoded in a cumulative array. When all dot profiles are built, the cumulative array becomes the blue noise mask. Compared to prior art blue noise masks, Drs. Parker and Mitsa's inventive mask produces higher quality halftone images while using less processor power and memory space.

RCT alleges that Microsoft infringes all six patents. The following claims are at issue on appeal: claims 1 and 2 of the '310 patent; claim 11 of the '228 patent; claims 4 and 63 of the '772 patent; and...