Summary
holding unpatentable a process for controlling objects to avoid collisions which described “nothing more than the manipulation of basic mathematical constructs, the paradigmatic ‘abstract idea’ ”
Summary of this case from Cybersource Corp.. v. Retail Decisions Inc.Opinion
No. 93-1294.
August 11, 1994.
David L. Schreiber, North American Philips Corp., of Tarrytown, NY, argued for appellant. With him on the brief was Jack E. Haken.
Lee E. Barrett, Associate Sol., Office of the Sol., Arlington, VA, argued for appellee. With him on the brief was Fred E. McKelvey, Sol.
Appeal from the United States Patent and Trademark Office Board of Patent Appeals and Interferences.
Before PLAGER, LOURIE, CLEVENGER, Circuit Judges.
Thomas P.H. Warmerdam and Bernard J.H. Verwer (collectively Warmerdam or appellants) appeal the January 28, 1993 decision of the Patent and Trademark Office Board of Patent Appeals and Interferences (Board), Appeal No. 92-3680. The Board affirmed the rejection of claims pending in U.S. Patent Application Serial No. 07/430,749 (the '749 application) in part for lack of statutory subject matter under 35 U.S.C. § 101 (1988), and in part for indefiniteness under 35 U.S.C. § 112 ¶ 2 (1988). We affirm-in-part and reverse-in-part.
BACKGROUND
Warmerdam filed the '749 application on November 1, 1989. That application is directed to a method and apparatus for controlling the motion of objects and machines, such as robotic machines, to avoid collision with other moving or fixed objects.
The technique requires determining the shape and position of the edges of the objects to be avoided. The prior art teaches that collision avoidance operations can be simplified by assuming that the objects are larger and more regularly shaped than they actually are. This can be done by treating the object as if it were a circle or sphere (called a "bubble") of sufficient size to enclose the object, and by assuming that any motion that impinges upon the circle would produce a collision.
Appellants' invention claims a further refinement of prior art bubble systems. The positions of objects are determined by measuring the locations of artificial circular boundaries, but the measurement process does not end if the machine determines that the circular boundary will be violated in a potential collision. Instead, if a potential collision is detected, appellants further refine the determination of the boundary position by replacing the spherical bubble zone with a set of smaller, more refined bubble zones.
Appellants refer to their set of increasingly better defined safety zones as a "bubble hierarchy". The claimed invention includes methods for generating a "data structure" — undefined as such but presumably including the measured dimensions and coordinates of the bubble hierarchy — and a machine (presumably a general purpose computer) having a memory containing data representing a bubble hierarchy as generated by any of the claimed methods.
The bubble hierarchy is conceived by appellants in the following manner. At the highest level of the hierarchy is a single "root" bubble, which entirely bounds the object and thus represents the contour of the object at a coarse level of detail. Lower levels of the hierarchy are associated with groups of bubbles of smaller diameter, each separately bounding only a portion of the object, such that the union of all bubbles at a particular level bounds the entire object. These groups of bubbles represent the contour of the object at progressively finer levels of detail.
Collision avoidance is accomplished through a technique known as "bubble-bursting." According to this technique, the anticipated path of a robot, for example, is first compared with the perimeter of the root bubble. If the two do not intersect, the procedure terminates because collision avoidance is necessarily established. However, if the two intersect, the root bubble is "burst", revealing the group of bubbles at the level immediately below it in the hierarchy. The anticipated path is then compared with the perimeters of each of these bubbles. Again, if an intersection is not detected, the procedure terminates because collision avoidance is necessarily established. If, on the other hand, an intersection is detected, the intersected bubble is burst, and the procedure then repeats itself until it is determined either that (1) the anticipated path does not intersect any of the bubbles at a particular level of the hierarchy, indicating collision avoidance, or (2) the anticipated path intersects one of the bubbles at the lowest level of the hierarchy, indicating that a collision will occur.
A bubble hierarchy is illustrated in the following reproduction of Figure 4 from the '749 application:
Warmerdam concedes that the use of bubble hierarchies for collision avoidance was known as of the '749 filing date. The asserted novelty of Warmerdam's method and apparatus derives from the generation and placement of the hierarchy of bubbles along the medial axis of the object. The medial axis of an object is defined in the specification to be "a line with the same topology as the object itself connecting points which lies midway between boundary centers of the object." With reference to Figure 1 of the '749 application, reproduced below, the medial axis of object O having contour C is represented by the group of lines B:
According to Warmerdam, generation and placement of the bubble hierarchy along the medial axis results in computational efficiency in relation to prior methods of bubble generation and placement.
As filed, the '749 application contained seven claims of which only claims 1-6 are at issue in this appeal. The other claim, claim 7, was indicated by the examiner as allowable. Claims 1-4 are method claims, of which claim 1 is the sole independent claim:
1. A method for generating a data structure which represents the shape of [sic] physical object in a position and/or motion control machine as a hierarchy of bubbles, comprising the steps of:
first locating the medial axis of the object and
then creating a hierarchy of bubbles on the medial axis.
Claims 2-4 recite both top-down and bottom-up procedures for creating the bubble hierarchy. Claim 2 is directed to the top-down procedure:
2. The method of Claim 1 wherein the step of creating the hierarchy comprises a top-down procedure of:
first placing a root bubble which is centered at the center of gravity of the object and has a radius equal to the maximum distance from the center of gravity to the contour of the object;
next, if the medial axis has a plurality of branch lines, placing a plurality of first successive bubbles each of which encompasses a distinct part of the object which is described by one of said branch lines; and
then successively dividing each line of the medial axis into two new line parts and placing a pair of next successive bubbles each of which encompasses a distinct part of the object which is described by one of said new line parts.
Claims 3-4, by contrast, are directed to the bottom-up procedure for creating the bubble hierarchy:
3. The method of Claim 1 wherein the step of creating the hierarchy comprises a bottom-up procedure of:
first representing the medial axis as [sic] large plurality of discrete points;
next placing the centers of a plurality of lowest level bubbles at said discrete points, where the radius of each bubble is equal to the minimum distance from the corresponding center point to the contour of the object; and
then successively creating new bubbles by merging the smallest bubble remaining with its smallest neighbor(s) to create a new bubble and repeating this step until only one root bubble remains.
4. The method of Claim 3 wherein two old bubbles are merged to yield a new bubble in accordance with the formulas:r' = (r1 + j + r2)/2, x' = 1/2(x1 + x2 + r1 — (x1 — x2)) ___ r2 ___ j y' = 1/2(y1 + y2 + r1 — (y1 — y2)) ___ r2 ___ j z' = 1/2(z1 + z2 + r1 — (z1 — z2)); ___ r2 ___ j
wherein r1 and r2 are the radii of the old bubbles, j is the distance between the centers of the old bubbles (x1, y1, z1) and (x2, y2, z2) are the coordinates of the center of the old bubbles, r' is the radius of the new bubbles, and x', y', z') are the coordinates of the center of the new bubble.
Claim 5 is directed to a machine:
5. A machine having a memory which contains data representing a bubble hierarchy generated by the method of any of Claims 1 through 4.
Claim 6 is directed to a data structure:
6. A data structure generated by the method of any of Claims 1 through 4.
The examiner rejected claims 1-4 and 6 for lack of statutory subject matter under 35 U.S.C. § 101, and claim 5 for indefiniteness under 35 U.S.C. § 112 ¶ 2. After the rejection was made final, Warmerdam appealed to the Board. On appeal, the Board sustained the rejections. With respect to claims 1-4, the Board was of the view that these claims recited no more than a mathematical algorithm in the abstract, and thus failed to comply with § 101. With respect to claim 5, the Board considered that claim to be indefinite under § 112 ¶ 2 because it left "unclear and unexplained how a memory is made or produced by the steps of generating recited in claims 1 through 4." With respect to claim 6, the Board determined that the claim failed to satisfy § 101 on the ground that a "data structure" is not within one of the categories of patentable subject matter listed in § 101, to wit, a process, machine, manufacture, composition of matter, or improvements thereof.
Warmerdam does not dispute the Board's finding that the patentability of the dependent claims (claims 2-4) was not argued separately from that of the independent claim (claim 1). Thus, these claims stand or fall together. See In re Schrader, 22 F.3d 290, 292 n. 3, 30 USPQ2d 1455, 1456 n. 3 (Fed. Cir. 1994); 37 C.F.R. § 1.192(c)(5) (1993).
Warmerdam appealed the decision of the Board to this court.
DISCUSSION
Despite the oft-quoted statement in the legislative history of the 1952 Patent Act that Congress intended that statutory subject matter "include anything under the sun that is made by man," S.Rep. No. 1979, 82d Cong., 2d Sess., 5 (1952), reprinted in 1952 U.S.C.C.A.N. 2394, 2399; H.R. Rep. No. 1923, 82d Cong., 2d Sess., 6 (1952), Congress did not so mandate. Congress included in patentable entable subject matter only those things that qualify as "any . . . process, machine, manufacture, or composition of matter, or any . . . improvement thereof . . . ." 35 U.S.C. § 101 (1988). Cf. In re Alappat, 33 F.3d 1526, 1542 (Fed. Cir. 1994) ( en banc) ("The use of the expansive term "any" in § 101 represents Congress's intent not to place any restrictions on the subject matter for which a patent may be obtained beyond those specifically recited in § 101 and the other parts of Title 35.")
To include some things is to exclude others. The chore of defining exactly what is excluded under § 101, and applying such definitions to specific cases, has caused courts to expend much effort in trying to find the right words to describe some rather abstract notions. In Diamond v. Diehr, 450 U.S. 175, 101 S.Ct. 1048, 67 L.Ed.2d 155 (1981), the Supreme Court summarized the scope of the § 101 exclusion and the Court's prior efforts at describing it by saying "[e]xcluded from such patent protection are laws of nature, natural phenomena, and abstract ideas. . . . Our recent holdings in Gottschalk v. Benson [ 409 U.S. 63, 93 S.Ct. 253, 34 L.Ed.2d 273 (1972)] and Parker v. Flook [ 437 U.S. 584, 98 S.Ct. 2522, 57 L.Ed.2d 451 (1978) ], both of which are computer-related, stand for no more than these long-established principles." Id. 450 U.S. at 185, 101 S.Ct. at 1056.
Within Supreme Court guidance, this court and its predecessor, as well as the Patent and Trademark Office (PTO), have sought to find more precise definitions for the things excluded, but without complete success. One notion that emerged and has been invoked in the computer related cases is that a patent cannot be obtained for a "mathematical algorithm." See In re Schrader, 22 F.3d 290, 30 USPQ2d 1455 (Fed. Cir. 1994) and cases discussed therein. That rule is generally applied through a two-step protocol known as the Freeman-Walter-Abele test, developed by our predecessor court, the first step of which is to determine whether a mathematical algorithm is recited directly or indirectly in the claim, and the second step of which is to determine whether the claimed invention as a whole is no more than the algorithm itself. See Schrader, 22 F.3d at 292, 30 USPQ2d at 1457.
The difficulty is that there is no clear agreement as to what is a "mathematical algorithm", which makes rather dicey the determination of whether the claim as a whole is no more than that. See Schrader, 22 F.3d at 292 n. 5, 30 USPQ2d at 1457 n. 5, and the dissent thereto. An alternative to creating these arbitrary definitional terms which deviate from those used in the statute may lie simply in returning to the language of the statute and the Supreme Court's basic principles as enunciated in Diehr, and eschewing efforts to describe nonstatutory subject matter in other terms.
Efforts to explain nonstatutory subject matter in other terms has bred such phrases as `method of doing business', Ex parte Murray, 9 USPQ2d 1819 (Bd.Pat.App. Inter. 1988), `transformation of subject matter', Cochrane v. Deener, 94 U.S. 780, 24 L.Ed. 139 (1877), and `reactions of an individual', Greenwalt v. Stanley Co., 12 USPQ 122 (2d Cir. 1931).
1.
Claims 1-4 and 6 are denominated as method claims. Understanding that the statute equates the term "method" with the term "process," see 35 U.S.C. § 100(b), the question is what is it that this process does, and in doing it is it other than what the Supreme Court must have understood to be "laws of nature, natural phenomena or abstract ideas"?
The Board concluded that each of the two steps recited in claim 1, i.e., the step of locating the medial axis of the object, and the step of creating the bubble hierarchy on the medial axis, involves the solving of a mathematical algorithm. The Commissioner asserts that these conclusions are sustainable on the ground that the preferred method of locating a medial axis identified in the '749 specification is a mathematical procedure known as Hilditch Skeletonization method, and on the ground that the top-down and bottom-up procedures identified in the specification (and claimed in the dependent claims) for creating the bubble hierarchy are likewise mathematical in nature. The Commissioner also points to several cases in which process steps similar to those recited in claims 1-4, i.e., steps such as "computing", "determining", "cross-correlating", "comparing", "selecting", "initializing", "testing", "modifying", and "identifying", were found to implicitly recite the solving of a mathematical algorithm.
E.g., In re Grams, 888 F.2d 835, 12 USPQ2d 1824 (Fed. Cir. 1989); In re Meyer, 688 F.2d 789, 215 USPQ 193 (CCPA 1982); and In re Johnson, 589 F.2d 1070, 200 USPQ 199 (CCPA 1978).
Warmerdam, by contrast, argues that the claims are broad enough to cover methods which involve physically measuring the contour of the object. Thus, according to Warmerdam, the claims do not essentially recite a mathematical algorithm as required by Ex parte Logan, 20 USPQ2d 1465 (Bd.Pat.App. Inter. 1991), but only incidentally do so.
Warmerdam has a point. Claim 1 is broad enough to cover methods for locating the medial axis of an object that include physically measuring the contour of the object with a ruler or simply by `eyeballing' the object, and then creating the bubble hierarchy by manually drawing it. In that sense, it does not necessarily recite the solving of a mathematical algorithm. The fact that the claim covers methods which are essentially mathematical in nature, as discussed infra, is not dispositive. Claims should be evaluated by their limitations, not by what they incidentally cover.
On the other hand, the preferred, and it appears the only practical, embodiment of the claimed method involves steps which are essentially mathematical in nature, i.e., utilization of the Hilditch Skeletonization method to locate the medial axis, followed by utilization of a top-down or bottom-up procedure for creating the bubble hierarchy. In this sense, at least, the claim is mathematical in nature.
The fact that the preferred method of performing the process steps at issue in Grams, Meyer, and Johnson involved the solving of a mathematical algorithm seemed to be the basis for the conclusions reached in those cases that the process steps implicitly recited a mathematical algorithm.
Compounding the difficulty of resolving the issue in "mathematical algorithm" terms is the lack of agreement, as previously noted, about the proper meaning of the label mathematical algorithm. See the discussion of this issue in Schrader, 22 F.3d at 293 n. 5, 30 USPQ2d at 1457 n. 5. We need not resolve the issue in these terms because we find that regardless whether the claim can be said to recite indirectly or directly a mathematical algorithm, and dispositive issue for assessing compliance with § 101 in this case is whether the claim is for a process that goes beyond simply manipulating "abstract ideas" or "natural phenomena".
This notion is sometimes phrased in terms of requiring a transformation or reduction of `subject matter.' In Schrader, we determined that the phrase `subject matter' is not limited to tangible articles or objects, but includes intangible subject matter, such as data or signals, representative of or constituting physical activity or objects. Id. 22 F.3d at 295, 30 USPQ2d at 1459 n. 12.
The body of claim 1 recites the steps of "locating" a medial axis, and "creating" a bubble hierarchy. These steps describe nothing more than the manipulation of basic mathematical constructs, the paradigmatic "abstract idea." As the Supreme Court has made clear, "[a]n idea of itself is not patentable," Rubber-Tip Pencil Co. v. Howard, 87 U.S. (20 Wall.) 498, 507, 22 L.Ed. 410 (1874); taking several abstract ideas and manipulating them together adds nothing to the basic equation.
Warmerdam's argument that the claim implies physically measuring the contour of an object misses the point. As a whole, the claim involves no more than the manipulation of abstract ideas. Moreover, from the standpoint of § 101, a physical measurement step is indistinguishable from the data gathering step which we held in In re Grams, 888 F.2d 835, 12 USPQ2d 1824 (Fed. Cir. 1989), was insufficient, standing alone, to impart patentability to a claim. Id. at 840, 12 USPQ2d at 1829.
Warmerdam's other argument, that the manipulation of data as described in the claims constitutes or represents a sufficient level of physical activity to impart patentability to the claim, is not convincing. It is true, particularly with ideas expressed in mathematical form, that if a claim requires more than the manipulation of ideas so that the process described in the claim produces something quite different, then the process might indeed describe statutory subject matter. The problem with Warmerdam's argument is that the claims here do not have that effect. It is the claims which define the metes and bounds of the invention entitled to the protection of the patent system. Zenith Lab. Inc. v. Bristol-Myers Squibb Co., 19 F.3d 1418, 1424, 30 USPQ2d 1285, 1290 (Fed. Cir. 1994). Thus, the argument is unavailing. We conclude the Board did not err in sustaining the rejection of claims 1-4 under § 101.
2.
Claim 5 is for a machine, and is clearly patentable subject matter. The Board denied patentability on the grounds it was indefinite, a fatal vice under 35 U.S.C. § 112, second paragraph. Warmerdam argues that claim 5 conforms to the conventional product-by-process format, and thus is definite. The Commissioner, by contrast, supports his assertion that the claim is indefinite with two arguments. First, he repeats the assertion of the Board: that the claim does not conform to the conventional format of a product-by-process claim because it is unclear how a memory is produced by the steps recited in claims 1-4. Second, the bubble hierarchy which is created in the recited steps is not "an exact, well-defined data structure. . . ."
The legal standard for definiteness is whether a claim reasonably apprises those of skill in the art of its scope. See Amgen Inc. v. Chugai Pharmaceutical Co. Ltd., 927 F.2d 1200, 1217, 18 USPQ2d 1016, 1030 (Fed. Cir.), cert. denied sub nom., Genetics Inst., Inc. v. Amgen, Inc., ___ U.S. ___, 112 S.Ct. 169, 116 L.Ed.2d 132 (1991) ( citing Shatterproof Glass Corp. v. Libbey-Owens Ford Co., 758 F.2d 613, 624, 225 USPQ 634, 641 (Fed. Cir. 1985)). The ultimate conclusion of indefiniteness is one of law, which we are free to review anew on appeal. Orthokinetics Inc. v. Safety Travel Chairs Inc., 806 F.2d 1565, 1576, 1 USPQ2d 1081, 1088 (Fed. Cir. 1986).
Claim 5 satisfies the Amgen test. It covers any machine (presumably including a known computer) having a memory which contains any data representing a bubble hierarchy determined by any of the methods of claims 1-4. The Commissioner's first argument is beside the point. There is no requirement that a claim for a machine which incorporates process steps, such as claim 5, must conform to the conventional definition of a product-by-process claim. The Commissioner's second argument, more to the point, is nevertheless unavailing. The Board considered claim 5 to leave unclear and unexplained how a memory is made or produced by the steps of generating recited in claims 1 through 4: "The broad exercise of geometrically representing the shape of an object with a hierarchy of bubbles on the medial axis of the object as recited in claim 1 simply does not produce a memory or data in memory . . . ."
Even if there were, we are not sure the claim fails to conform to this definition. Our predecessor court has recognized that the storage of data in a memory physically alters the memory, and thus in some sense gives rise to a new memory. See In re Bernhart, 417 F.2d 1395, 1400, 163 USPQ 611, 616 (CCPA 1969). In that sense, the claim does conform to the conventional format.
We are not persuaded. The ideas expressed in claims 1 through 4 are well known mathematical constructs, and lend themselves to manipulation through known computer technology. There has been no showing that one-skilled in the art would have any particular difficulty in determining whether a machine having a memory containing data representing a bubble hierarchy is or is not within the scope of claim 5. The Board's point, that the claim leaves unclear the technique of how the memory is configured with the data, has no bearing on this issue. The claim plainly covers all such techniques. Whether such a programmed machine is new, useful, unobvious, or otherwise patentable is not at issue in this appeal, and we express no opinion thereon. Accordingly, we conclude the Board erred in sustaining the rejection of claim 5 for indefiniteness.
3.
Citing In re Bradley, 600 F.2d 807, 202 USPQ 480 (CCPA 1979), aff'd, 450 U.S. 381, 101 S.Ct. 1495, 67 L.Ed.2d 311 (1981), Warmerdam argues that a "data structure" is one of the categories of patentable subject matter recited in § 101, and thus that the Board erred in sustaining the rejection of claim 6 under § 101. The Commissioner, by contrast, citing Kewanee Oil Co. v. Bicron Corp., 416 U.S. 470, 94 S.Ct. 1879, 40 L.Ed.2d 315 (1974), argues that the rejection should be sustained because the claim is not one of the categories of subject matter recited in § 101, to wit, a process, machine, manufacture, composition of matter, or an improvement thereof.
35 U.S.C. § 101 (1988) provides:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
The Commissioner is correct. The claim in its entirety reads: "6. A data structure generated by the method of any of Claims 1 through 4." While the term "data structure" is nowhere defined in Warmerdam's application, it is clear from its use in the specification that it refers to the ideas reflected in the process of making a bubble hierarchy. In IEEE Standard Computer Dictionary (1991), the phrase "data structure" is defined as "[a] physical or logical relationship among data elements, designed to support specific data manipulation functions." (Emphasis added). Since the "data structure" of claim 6 is nothing more than another way of describing the manipulation of ideas contained in claims 1-4, it suffers from the same fatal defect they do.
"In a typical bubble hierarchy, the top or root of the hierarchy is a single spherical bubble, the enclosing bubble which encloses an entire object. This is the most coarse level of detail in the data structure." Spec., p. 2.
Warmerdam's reliance on Bradley, 600 F.2d 807, 202 USPQ 480 (CCPA 1979), is misplaced. The "data structure" at issue in that case was a physical, interconnected arrangement of hardware and thus embraced by the term "machine". Id. at 812-13, 202 USPQ at 486. The same cannot be said of the data structure that is at issue in this case. Contrary to Warmerdam's assertion, the phrase does not imply a physical arrangement of the contents of a memory. Thus, Bradley is inapposite.
CONCLUSION
The decision of the Board, sustaining the rejection of claims 1-4, and 6 for lack of statutory subject matter, is affirmed, and the decision of the Board, sustaining the rejection of claim 5 for indefiniteness, is reversed.
COSTS
Each party to bear its own costs.
AFFIRMED-IN-PART AND REVERSED-IN-PART.