T 0190/94 26-10-1995
Download and more information:
Image rotating system having an arbitrary angle
Exclusion from patentability (no) - different mathematical algorithm has technical effect on physical entity
Inventive step - yes
I. The appeal contests the Interlocutory Decision of the Opposition Division stating that, taking into consideration the amendments made by the proprietor of the European patent No. 0 216 931 during the opposition proceedings, the patent and the invention to which it relates would meet the requirements of the Convention.
II. The patent is based on European patent application No. 86 901 506.5, which had been filed, as an international (PCT) application, on 25 February 1986 mentioning prior art document
D0: JP-A-55-94 145 (1980).
It was granted concluding an examination procedure in which the following prior art document was considered:
D1: DE-A-3 419 063.
III. The opposition filed against that patent invoked the ground of lack of novelty or, at least, inventive step (Article 100(a), 54 or 56 EPC) and the ground of insufficient disclosure (Article 100(b) EPC).
In support of the former ground, the following prior art documents were cited:
E1: Architecture and Data Processing Alternatives for the Tse Computer, Vol. 4: R. E. Bodenheimer and M-H. Kao: Image Rotation Using Tse Operations, Final Report NSG-5002, Technical Report TR- EE/CS-76-4, NASA, Greenbelt MD, US, October 1976;
E2: IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 9 to 11 April 1980, T. A. Kriz and D. F. Bachman: A Number Theoretic Transform Approach to Image Rotation in Parallel Array Processors, p. 430-433.
During the opposition proceedings, these grounds were supplemented by the ground of exclusion from patentability (Article 100(a), 52(2)(a) EPC).
IV. In the decision under appeal, the Division concluded that the opposition was admissible but, with the amendments made to the patent, not well-founded.
More particularly, the Article 100(b) ground was considered to have been met by deletion of Claim 2, and the other grounds were considered not to prejudice the maintenance of the patent on the basis of the Claim filed on 29 November 1993. In respect of Article 56, E1 was considered as the starting point and E2, D0 and D1 were additionally taken into consideration.
An auxiliary request claim 1 filed on 3 June 1993 was not, in the circumstances, considered.
V. The appeal against this decision, which was announced in oral proceedings and issued with full reasons on 24. January 1994, was lodged by the opponent on 2 March 1994 with a request that the patent be revoked in its entirety.
The appeal fee was paid on 28 March 1994.
On 2 June 1994, the appellant filed a statement of grounds.
VI. In the appeal procedure, the appellant maintained the objection that the claimed matter would be excluded from patentability (Article 52(2)(a)) and the objection that, while being novel (Article 54), it would not involve an inventive step (Article 56).
In support of the former objection, he relied on the Board's case law, in particular T 38/86 (OJ 1990, 384). In support of the latter objection, he relied on E1 and D1.
VII. In response, the respondent (patentee) maintained that the appellant's objections were not justified.
In respect of the first-mentioned objection, the respondent relied on the Boards' earlier decisions T 208/84 (OJ 1987, 14) and T 26/86 (OJ 1988, 19). In respect of the second objection, it was submitted that the reasons therefor were not sound.
VIII. In an Annex to the summons for oral proceedings, the Board raised the objection that some of the amendments made to the patent would appear inadmissible (Article 123(2) EPC), the claim would appear unclear (Article 84 EPC), and the description would seem not to support this claim (Article 84 and Rules 27 and 29 EPC).
IX. In response, the respondent filed, in the oral proceedings held on 26 October 1995, a new claim and page 3 (allegedly having been filed also, as requested, a month ago) and requested that the decision under appeal be set aside and the patent maintained on the basis of the following documents:
description: page 2 and new part replacing column 2 lines 34-47, both filed on 2 April 1992, page 3 filed on 26 October 1995, page 4 as published;
claims: one claim filed on 26 October 1995;
drawing: sheet/Figure 1 to 4 as published.
X. The claim reads as follows:
"A system for rotating an image by an arbitrary angle comprising;
an image memory for storing two-dimensional image data (121);
a transformation angle determining section (111) for determining both a skew angle ( x) in a horizontal direction and a skew angle ( y) in a vertical direction of the original two-dimensional image data stored in said image memory, based on a desired rotation angle ( );
a first X-axis skew transformation section (112) for obtaining second two-dimensional image data (122) which results from skewing first two-dimensional image data stored in said image memory as the original two- dimensional image data in a horizontal direction by the angle as determined by said transformation angle determining section;
a Y-axis skew transformation section (113) for obtaining third two-dimensional image data (123) which results from skewing said second two-dimensional image data in a vertical direction by the angle as determined by said transformation angle determining section; and
a second X-axis skew transformation section (114) for obtaining fourth two-dimensional image data (124) which results from skewing said third two-dimensional image data in a horizontal direction once again by the angle as determined by said transformation angle determining section (111);
- wherein the skew transformation for implementing the rotation processing is performed with skew transformation matrices represented by the following equations without needing arithmetic operations of affine transformation:
(FORMULA)
- where 1, 3 represent the first and second skew transformation in the X-direction and where 2 represents the skew transformation in the Y- direction and
wherein the rotation angle ( ) is determined from the equations:
(FORMULA)
XI. The appellant maintained his request that the decision under appeal be set aside and the patent revoked.
XII. In support of these requests, the parties relied, in effect, on their written submissions and drew attention to these in the oral proceedings.
1. The appeal (cf. paragraph V) is admissible.
2. Both parties requesting, albeit for different ends, that the decision under appeal be set aside (IX and XI), this request is to be allowed.
For their further requests, aiming at a decision under Article 102, either (1) or (3), EPC, the main issue to be resolved is whether the subject-matter claimed is, or is not, patentable (Article 100(a)).
3. As a precondition for the resolution of this issue, the amendments made to the statement of claims and (in view of Article 69 EPC) also those made to the description must be admissible (Article 123(2) and (3) EPC).
3.1. As to substance, the claim (cf. X) is identical with the claim (main request) on which the Opposition Division's decision was based. The Division accepted this claim for consideration implying that the amendments made to it were admissible.
The appellant did not dispute this view and also the Board agrees with it. The introduced reference to no affine transformation operations being needed is based on the description (column 2 line 65 to column 3 line 2).
3.2. Granted claim 2 was cancelled in the opposition proceedings, and no objection arises from that.
3.3. The amendments made, in the opposition procedure, to page 2 (column 2) were tacitly accepted by the Opposition Division as admissible, and the Board sees no reason to dispute this.
3.4. The amendments made to page 3 (columns 3 and 4) in the oral proceedings before the Board were necessary to remove any statements inconsistent with the claim and, moreover, to remove an inadmissible amendment made in the opposition proceedings (column 4 line 15).
3.5. The respondent's withdrawal of the amendments made in the opposition proceedings to page 4 (column 6 lines 19/20) was also necessary for this latter reason.
4. Turning now to the four requirements for patentability mentioned in Article 52(1) EPC, in principle, the first, viz. that the claimed subject-matter must not relate to subject-matter or activities as such (Article 52(3)) which are not to be regarded as inventions (Article 52(2)), and the other ones, viz. that it must be susceptible of industrial application, be new and involve an inventive step (Articles 54 to 57), are independent from each other.
However, there is nevertheless some relationship between the issues to be decided in the present case, viz. the issue of exclusion or not from patentability (Article 52(2)/(3)) and the issue of lack or not of inventive step (Article 56). This is illustrated best by the appellant's reference, with respect to the former issue, to the prior art, E1, for instance, as in its letter of 15 September 1995, relying on the Board's decision T 38/86.
On the other hand, this does not detract from the necessity to consider the two issues separately, one after the other.
5. Invention vs. subject-matter or activity excluded as such
5.1. Article 52(2) in conjunction with (3) EPC excludes a variety of subject-matter or activities, if the claim relates to such matters "as such", from patentability, "in particular" those listed in sub-paragraphs (a) to (d). Even though these matters are thus presented as examples, no common criterion is mentioned. With some justification, however, they all can be regarded as being of an abstract rather than of a technical kind. Some support for this may also be derived from Rules 27(1) and 29(1) EPC mentioning the "technical field", the "technical problem" and the "technical features" of an alleged invention.
5.2. According to the Board's case law, of which T 38/86 is an example, it appears to be the intention of these provisions "to permit patenting only in those cases in which the invention involves a contribution to the art in a field not excluded from patentability" (T 38/86, Reason 12).
For instance, in the case referred to it was considered that "once the steps of the method for performing the mental acts in question have been defined, the implementation of the technical means to be used in those steps ... involves no more than the straightforward application of conventional techniques and must therefore be considered to be obvious to a person skilled in the (technical) art, so that the method according to claim ... does not contribute to the art anything involving an inventive step within the meaning of Article 56 EPC in a field not excluded from patentability by Article 52(2)(c) EPC" (Reason 13). That is also the meaning of the Headnote cited by the appellant: "if the technical implementation of such a [technical; cf. Headnote III] method is obvious to a person skilled in the technical art, once the steps of the method for performing the mental acts have been defined, so that there is no inventive contribution in a field not excluded from patentability under Article 52(2)(c) EPC, such method does not involve an inventive step within the meaning of Article 56 EPC" (Headnote IV).
5.3. The appellant submitted that this would be true in the present case as well.
The "method" of the earlier decision would correspond to the algorithm for calculating the skew distances and the "technical implementation of the method" would correspond to the three-step skew system. This system would be completely disclosed, including the exact skew distances to be applied on each row/column of image data, in E1. The "technical implementation" would thus not only be obvious but even known in detail to the person skilled in the technical art. Accordingly, there would be no inventive contribution in a field not excluded from patentability under Article 52(2) EPC.
In the oral proceedings, the appellant in effect reiterated, and emphasized, these submissions.
5.4. Although the Board agrees with the principles on which the appellant's submissions are based, it came, on the basis of the facts of the present case, in the end, to a different conclusion than the appellant.
In its view, the contribution made to the art by the claimed system is not only a different mathematical algorithm for the same skew steps as in E1, as will be explained subsequently.
5.5. In the claimed system, first the horizontal image lines are slid in the X direction (as illustrated in the Figures, eg. at 122, 206-211, 308 and 305); then the resulting vertical image columns are slid in the Y direction (123, 309 and 306); and finally the resulting horizontal image lines are again slid in the X direction (124, 310 and 307).
In the system of E1, as exemplified (on pages 51-67), first the vertical image columns are slid in the Y direction (Figure 26); then the resulting horizontal image lines are slid in the X direction (Figure 27); and finally the resulting vertical image columns are again slid in the Y direction (Figure 28). However, in addition to this Y-X-Y sequence of skew transformations, reference is made (on pages 32/36) to an equivalent X-Y- X sequence of skew transformations, this latter sequence corresponding to the claimed sequence. In the following comparisons, the claimed system will therefore be compared with a system according to E1 in which the skew transformations are of this latter kind and which would be illustrated in Figures 26 to 28 if it is assumed that the "vertical" or "Y" direction is from right to left and the "horizontal" or "X" direction is from bottom to top.
5.6. According to the claim, "the skew transformation ... is performed with skew transformation matrices ...". This is understood as meaning that the pixel coordinates () of the original image are to be multiplied with the matrices recited in the claim.
(Incidentally, it is noted at this point that the description of the skew transformations in the positive horizontal (X) direction with reference to Figure 1 (122, 124), Figure 2 (211) and Figure 3 (305, 307) appears inconsistent with the claim in so far as the minus sign of the tangent term is concerned, and the description of the skew transformation in the positive horizontal (X) direction with reference to Figure 4 (401) appears inconsistent with the equation (2) in the same respect, in D1 the minus sign designating a skew transformation in the negative horizontal (X) direction; however it will be clear to the skilled reader that skew transformations in the positive and in the negative direction are, in principle, equivalent and will both fall under the claim as well as under the prior art. Furthermore, it will be clear to the skilled reader that in column 1 line 47 the term -tan0 is but a clerical error and should read -tan .
Matrices and their multiplication with image pixel coordinates are mentioned also in E1 (page 5). The equation (2) there corresponds to equation (1) mentioned in the patent in the context of known affine transformation (column 1 lines 6-24).
However, according to Table 4, matrices are not used in the three skew transformation steps proposed on pages 51 to 67.
5.7. Nevertheless, the three skew transformations with matrices as claimed are qualitatively equivalent to the three skew transformations ("Step 1" to "Step 3") with equations as shown in one of the columns of Table 4 of E1 in so far as they have generally the same effect of rotating columns or lines as said before (5.5).
This does not, however, mean that they are quantitatively equivalent as well. On the contrary, as will be explained, they are not.
5.8. In the claimed system, each of the first and third skew transformations results in a rotation of pixel columns by an angle /2 (eg. 22.5°), this being expressed by the matrix mentioned first in the Claim (it being clear to the skilled reader of the patent, that the term -tan /2 as written in the Claim must not be interpreted as - (tan )/2 but as -tan( /2)). Since (as long as the skew is small enough) the second skew transformation does not add, to this rotation of an originally vertical pixel column, a substantial further rotation (cf. Figure 3 at 305/306), the three skew transformations will result in an overall rotation of the original pixel columns by the sum of the first and third angles of rotation, ie. by an angle of (viz., in the example, 45°).
This is not so in E1. Nothing in that document, in particular nothing in Table 4, would point to an equivalence of the algorithm used in "Step 3" (whichever of the four columns concerning different techniques and different senses of rotation is considered), comprising sub-steps (a) to (d), with the algorithm used in "Step 1". Nothing would therefore point to the angle of rotation of pixel columns resulting from the third skew transformation being necessarily equal to the angle of rotation resulting from the first (and thus to cause an overall rotation of double the value resulting from the first skew transformation).
5.9. It is true that the factor (cos -1)/sin in the equation used, according to Table 4 of E1, in the first skew transformation ("Step 1") of the known system can (as is well-known to mathematicians) be written as -tan( /2), which is identical with the member determining, according to the matrix of the first skew transformation in the claim, the first skew angle of the claimed system.
However, apart from the fact that this disregards the second factor in this equation, this mathematical equivalence of said first factor and said matrix member does not detract from the fact that, as said before, "Step 3" is not identical or equivalent to "Step 1", and therefore does not, or at least not necessarily, yield the same quantitative result in terms of rotation (cf. 5.8).
5.10. Apart from that, in the Board's view, the "technical implementation" of the third of the three skew transformations as claimed is not the same as in the known system. In the claimed system the image pixels are transformed applying the relatively simple equations based on the single matrix which is identical with the one used in the first skew transformation, whereas in the system of E1 they are transformed applying the more complicated four equations of the "Step 3" algorithm in (one of the columns of) Table 4 which appears not at all identical with the equation used in "Step 1" (in particular because it comprises a "smoothing" and a "filling" substep not present in any other step).
5.11. The appellant has argued that the contribution made to the art by the difference between the claimed and the known system would be of a mathematical kind only, excluding the claimed system from patentability (Article 52(2)(a) EPC).
The Board is not convinced by that submission. It is agreed that, had the difference in algorithm between the third skew transformation in the claimed and the third skew transformation in the known system the only effect that necessarily the same angle of rotation would be gained by an equivalent mathematical formula, then the appellant might be right. However, as follows from the above (5.8-5.10), at least in the third skew transformation neither the algorithms appear equivalent nor the angles of rotation achieved would appear necessarily to be the same.
Since, therefore, the quantitative effects on the image pixels in terms of rotation angles, in the third skew transformation and consequently in its quantitative relationship with the other two transformations within the overall rotation of the image, do not appear to be the same in the claimed as in the known system, the difference between these two systems manifests itself in the real world in a technical effect on a physical entity in the sense of decision T 208/84, supra.
5.12. The claimed system thus making a contribution to the art in a field not excluded (by Article 52(2)/(3) EPC) from patentability, the subject-matter of the Claim is to be regarded as an invention within the meaning of Article 52(1) EPC.
6. Inventive step
6.1. In the context of its argumentation concerning exclusion from patentability, the appellant suggested that no "inventive" contribution (in a field not excluded) would be made to the art by the claimed system because the "technical implementation" would not only be obvious but even known from E1.
The Board cannot agree with this view. Since E1 does not suggest using any algorithm other than the one described and shown in Table 4, in particular not the one used in the claimed system, this system cannot be regarded as being rendered obvious by E1 (alone).
6.2. In a second approach, the appellant submitted that a person skilled in the art of mathematics and its application, knowing that a rotation transformation matrix (known from D1) can with advantage be decomposed into a product of simpler transformation matrices, and realising that the E1 method would provide the ideal composition, would arrive at the claimed system.
It is agreed that the skilled person would realise that matrices such as those used in the method disclosed in D1 could be applied in a system as known from E1, resulting in a system performing the three-step skew transformation of E1 using, instead of the formulas in Table 4, equivalent matrices.
6.3. However, the second transformations differ by the fact that in E1 it is a vertical (Y) skew transformation (as supposed above; cf. point 5.5) but in D1 it is a scaling transformation; and the third transformations differ by the fact that in E1 it is a horizontal (X) skew transformation (as supposed in point 5.5) but in D1 it is a vertical (Y) skew transformation.
The matrix T1 of D1 is therefore not really equivalent to the equation used in "Step 1" of E1 because the argument of the tangent is in the said matrix but it would be /2 in a matrix which is equivalent to the first factor in the equation of "Step 1" in E1. Furthermore, the matrix T2 representing a scaling transformation of D1 is clearly not equivalent to the equation used in "Step 2" of E1 representing a skew transformation, and the matrix T3 of D1 is clearly not equivalent to the equation used in "Step 3" of E1, ie. these matrices of D1 could not be used in the three-step skew transformation process of E1.
It follows therefrom that it would be obvious to the skilled person that the equations in Table 4 of E1 would have to be replaced by matrices other than those known from D1 but it would not be readily apparent from either D1 or E1 what these other matrices would have to look like so as to be equivalent to the equations in Table 4 of E1, in particular in the case of "Step 3".
6.4. It is noted, in this context, that, contrary to the triple skew transformation of E1, the transformation process of D1 is in effect a double skew transformation in the X and Y directions, just as is the one acknowledged in the patent as prior art (column 1 lines 25 to 42) and illustrated in Figure 4, with the only difference that a scaling transformation is made between the two skew transformations.
(Incidentally, the Board was not able to verify whether D0 (cf. point II above) discloses a relevant image rotating system or not, a JP-A-document having this number concerning an optical system falling within Int. Cl. G01N 21/88 and G01B 11/30; but, in the presence of D1, it is nevertheless clear that image rotating systems using a double skew transformation are prior art.)
However, as said before (6.3), the process of D1 uses quite a different algorithm from that in E1, and the particular matrices of D1 could neither be used in E1 nor suggest what other matrices would have to be used.
6.5. In this situation it has to be concluded that, even though D1 would suggest the introduction of matrices in the system of E1, the matrices to be applied in this latter system would have to take quite a different form, different not only from those used in D1 but also, at least in "Step 3", not the one proposed in the patent either, as follows from the considerations above (points 5.8-5.10).
An "obvious combination" of D1 and E1 would not therefore, in the Board's view, lead to the claimed system.
6.6. Summarizing this finding, the subject-matter of the claim is considered to involve an inventive step.
7. Conclusions
7.1. The appellant's request for revocation of the patent cannot be allowed.
7.2. The conclusion in the decision under appeal, that the claimed subject-matter is an invention not excluded from patentability and that it involves an inventive step, is to be confirmed and the respondent's request for maintenance of the patent as amended, therefore, to be allowed.
ORDER
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the first instance with the order to maintain the patent as amended, viz. on the basis of the documents recited in paragraph IX.