|European Case Law Identifier:||ECLI:EP:BA:2007:T092903.20071130|
|Date of decision:||30 November 2007|
|Case number:||T 0929/03|
|IPC class:||H04N 7/30|
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||Method and apparatus for fast image compression|
|Applicant name:||AT&T Corp.|
|Relevant legal provisions:||
|Keywords:||Basis of decision - right to be heard (yes), inventive step (no)|
An examining division introducing a prior art document in oral proceedings need not necessarily adjourn the oral proceedings if the representative had sufficient time to study the document during an interruption in the oral proceedings (see section 2.4 of the reasons).
Summary of Facts and Submissions
I. The appeal is against the decision of the examining division to refuse European patent application No. 98 118 648.9.
II. On 27 July 2001 the examining division issued a first communication pursuant to Article 96(2) EPC referring, among others, to documents
D1: US 5 491 761 A
D2: VILLASENOR J. D. 'Alternatives to the Discrete Cosine Transform for Irreversible Tomographic Image Compression.' In: IEEE Transactions on Medical Imaging, Vol. 12, No. 4, December 1993, pages 803 to 811. XP000447028, ISSN 0278-0062;
D3: BRACEWELL R. N. et al. 'Fast Two-Dimensional Hartley Transform." In: Proceedings of the IEEE, Vol. 74, No. 9, September 1986, pages 1282 to 1283. XP000983354, ISSN 0018-9219;
D4: PAIK C. H. 'Fast Hartley Transforms for Image Processing.' In: IEEE Transactions on Medical Imaging, Vol. 7, No. 2, June 1988, pages 149 to 153. XP000006259, ISSN 0278-0062.
The examining division raised objections concerning, inter alia, a lack of inventive step (Article 56 EPC) having regard to the state of the art known from D1 and D2 or D1 and D4.
III. With a letter dated 23 April 2002 the applicant filed amended claims 1 to 53.
IV. On 21 October 2002 the examining division issued a summons to oral proceedings raising objections of lack of inventive step over a combination of D2 with D1 or D4 with D1.
V. With a letter dated 15 January 2003 the applicant filed further amended claims 1 to 50 as an auxiliary request.
VI. Oral proceedings before the examining division were held on 21 February 2003. According to the minutes of the oral proceedings, the examining division introduced the following document in the context of the debate on the inventive step of the subject-matter of claim 1 of the auxiliary request:
D7: HSIE S. HOU. 'The Fast Hartley Transform Algorithm.' In: IEEE Transactions on Computers, Vol. C-36, No. 2, February 1987, pages 147 to 156. XP000648633, ISSN 0018-9340
& 'Correction to 'The Fast Hartley Transform Algorithm.'' In: IEEE Transactions on Computers, Vol. C-36, No. 9, September 1987, pages 1135 and 1136. XP000648660, ISSN 0018-9340.
The minutes set out the examining division's opinion that "claim 1 of the auxiliary request is not inventive (Art. 56 EPC) with regard to D1 in combination with D4, especially with regard to a document cited in D4 as reference  " (namely document D7). The examining division also raised an objection under Article 84 EPC concerning the wording "reversible transform" in claims of the main and the auxiliary request and an objection under Article 123(2) EPC relating to a feature of claim 1 of the auxiliary request (requiring at most two distinct multiplication operations). According to the minutes, the examining division expressed the view that, although the objections under Article 84 EPC and 123(2) EPC might be overcome by amendments, it would be difficult to overcome the objection under Article 56 EPC. After an interruption of the oral proceedings, the representative announced that he would not file any new requests. He maintained the requests on file and submitted arguments in favour of inventive step. After deliberation, the decision to refuse the application was announced.
VII. The written decision and the minutes of the oral proceedings were posted on 25 March 2003.
VIII. The reasons of the decision under appeal can be summarized as follows.
The independent claims of the main and the auxiliary request lacked clarity because of the expression "reversible transform" (Article 84 EPC).
The subject-matter of all independent claims of the main request lacked an inventive step (Article 56 EPC) over a combination of D1 and D2. The term "irreversible" in D2 related to lossy compression, but the Hartley transform mentioned in D2, D3, D4 and D7 had the property of being reversible. The independent claims of the auxiliary request comprised an inadmissible generalization (Article 123(2) EPC) in the feature "wherein each pass of the one-dimensional row Hartley transform and the one-dimensional column Hartley transform is computed using a matrix representation requiring at most two distinct multiplication operations when multiplying with a vector". The subject-matter of the independent claims of the auxiliary request lacked an inventive step over the combination of D4 and generally used operations in the art of image processing, namely quantizing and entropy coding of transform coefficients. An example of such quantizing and entropy coding was disclosed in D1. For the implementation of the Fast Hartley transform D4 referred to D7, which disclosed the transform matrix, the corresponding data flow graph and that only two multiplication operations were required.
IX. In a letter dated 9 April 2003 the appellant requested that the minutes of the oral proceedings be corrected to include the appellant's request for adjournment of the oral proceedings in view of the late introduction of D7.
X. With the statement of grounds of appeal the appellant submitted new claims which were said to be "based on the claims of the auxiliary request" annexed to the decision under appeal. The appellant requested "only remitting of the case to the Examining Division" and reimbursement of the appeal fee.
XI. With a first communication dated 19 February 2007 the board drew the appellant's attention to the fact that the examining division was competent and obliged to decide on the request for correction of the minutes, but had not yet reacted to it. However there was also no reminder of the appellant with regard to his request for correction on the examination file. In this communication and a further communication accompanying the summons to oral proceedings the board further made observations concerning matters to be discussed in the oral proceedings.
XII. With a letter dated 30 October 2007 the appellant filed new claims 1 to 48 as an auxiliary request.
XIII. Claim 1 of the auxiliary request reads as follows:
"A method for compressing an image, comprising the steps of:
1. dividing the image (401; 601) into at least one image set (301; 402; 602), wherein each image set (301; 402; 602) is a two-dimensional array of pixels having a number of columns M and a number of rows N, said number of columns M being equal to said number of rows N; and
2. for each image set (301; 402; 602):
1. transforming (302, 305; 403; 608) the image set (301; 402; 602) into a set of coefficients using a two-stage Hartley transform comprising, in any order, one pass of a one-dimensional row Hartley transform and one pass of a one-dimensional column Hartley transform, wherein each pass of the one-dimensional row Hartley transform and of the one-dimensional column Hartley transform is computed using a matrix representation requiring at most two distinct multiplication operations when multiplying with a vector when N <= 8, and wherein the precision of at least one stage of the Hartley transform is controlled by limiting the number of bits used to represent each coefficient of the set of coefficients resulting from the at least one stage of the transform,
2. quantizing (303, 306; 404; 609) each coefficient of the set of coefficients; and
3. coding (405; 610) each quantized coefficient of the set of coefficients in accordance with an entropy code."
XIV. Oral proceedings before the board of appeal were held on 30 November 2007, at the end of which the board announced its decision.
XV. The appellant requested that the decision under appeal be set aside, the case be only remitted to the first instance and that the appeal fee be reimbursed because of a substantial procedural violation in the first instance proceedings (main request). Alternatively, the appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 48 of the auxiliary request filed with the letter dated 30 October 2007.
XVI. The appellant's arguments can be summarized as follows.
It was unfair towards the overseas applicant that D7 was introduced without giving the representative the possibility of getting advice from the applicant concerning D7, even though the feature disclosed in D7 was already present in a dependent claim filed with the letter dated 23 April 2002 and in an independent claim of the auxiliary request filed with the letter dated 15 January 2003, i.e. more than one month before the oral proceedings. This constituted a procedural violation because the applicant could not have expected that D7 would be introduced because D7 was only one of a large number of documents referred to in the documents previously introduced by the examining division. When confronted with D7 the representative had requested an adjournment of the oral proceedings, but the examining division had not taken this request into account. This also constituted a procedural violation. D7 had a major impact on the decision under appeal because the decision used D7 to show that an essential feature of the invention specified in the auxiliary request was known from the prior art. The applicant had not reacted to the objections under Article 84 EPC and 123(2) EPC in the oral proceedings before the examining division because the examining division had indicated that there was a lack of inventive step (Article 56 EPC) anyway. Because of these procedural violations the appellant's main request was remittal of the case to the first instance.
Concerning the inventive step of the subject-matter of the claims according to the auxiliary request, the appellant essentially argues as follows. The matrix HN of a Fast Hartley Transform (FHT) contained very few distinct values. This reduced the computation time and hardware requirements in comparison to other approaches utilizing a matrix with many more values, such as a discrete cosine transform (DCT). The feature of a precision control further reduced the computation load. The use of the Hartley transform for image compression, the limitation to N <= 8 and the precision control formed a whole package of features providing a synergistic effect which improved the compression and avoided distortion in the reconstructed image. The prior art did not use the FHT for image compression, but for image processing. In D2 only a selected portion of the image was transformed, and image data were lost. When the entire image was transformed D2 envisaged the DCT. In the invention the precision control led to a loss of data after the transform of the complete image. The appropriate starting point for the invention was D1 instead of D4 because D1 related to image compression. Starting from D1, the problem was to find the appropriate transform function. D4 did not teach the use of the Hartley transform for image compression but for image autocorrelation.
Reasons for the Decision
1. The appeal is admissible.
2. Main request: Remittal to the first instance
2.1 According to Article 10 of the Rules of Procedure of the Boards of Appeal of the European Patent Office (RPBA), OJ EPO 2003, 89, "[a] Board shall remit a case to the department of first instance if fundamental deficiencies are apparent in the first instance proceedings, unless special reasons present themselves for doing otherwise." In accordance with established case law (see the decisions referred to in the "Case Law of the Boards of Appeal of the European Patent Office", 5th edition 2006, VII.D.9), a substantial procedural violation, in particular a violation of the right to be heard enshrined in Article 113(1) EPC, may constitute a "fundamental deficiency" within the meaning of Article 10 RPBA.
2.2 In the board's understanding the appellant's argument that the first instance proceedings were unfair (see point XVI above) has, in the particular circumstances, the meaning that the applicant's right to be heard was allegedly violated because the applicant had not had an opportunity to present his comments on D7. Thus the board will first analyse whether the applicant had an opportunity to present his comments on D7.
2.3 In this context the appellant referred to two separate alleged procedural violations, namely introducing D7 in oral proceedings without adjourning them and not taking into account his request for adjournment of the oral proceedings. However these two alleged procedural violations cannot be dealt with separately from each other, because the introduction of D7 is the only factual reason why allegedly the oral proceedings before the examining division should have been adjourned.
2.4 In assessing whether the applicant had an opportunity to present his comments on D7 the board has in particular taken account of the following facts.
2.4.1 The applicant was represented at the oral proceedings
It is undisputed that the applicant's representative attended the oral proceedings. According to the minutes of the oral proceedings, the examining division expressed the provisional opinion that it would be difficult to overcome the objection of a lack of an inventive step. After an interruption of the proceedings the representative presented arguments in favour of inventive step which, according to the minutes, took D7 into consideration, but he filed no new request based on amended claims. Nor did the representative submit that the interruption of the oral proceedings was too short to react to the situation.
2.4.2 The subject-matter introduced in the oral proceedings
The application itself makes clear that the Discrete Hartley Transform (DHT) was a known transform (see paragraphs  to  of the application as published). Also documents D2, D3, and D4, all cited in the search report and referred to in the examination proceedings, disclose that the DHT and algorithms for its fast implementation (Fast Hartley Transform, FHT) had been considered as an alternative to known transforms used in image processing. The matrix H8 given in figure 1 of the present application shows the DHT kernel for N=8 (the case of transforming a vector having eight elements). Since it was common general knowledge that the speed of an algorithm is in particular dependent on the number of multiplications needed, which in turn depends on the order of the matrix (see paragraph  of the application as published), it was not surprising that this issue was raised in the oral proceedings. This issue became even more important in view of the feature "requiring at most two distinct multiplication operations" which had been included in claim 1 of the auxiliary request then on file (without specifying the number of rows N).
D7 shows the same DHT kernel (equation (7) on page 148) and also discusses the question of how many multiplications are needed in an FHT algorithm to perform the DHT represented by H8. D7 is relevant as to how the FHT may be implemented and how many nontrivial multiplications and additions are required (see Table 1 and corrected figure 1(c)). The board agrees with the appellant that D7 discloses a feature of the independent claims of the auxiliary request then on file. But this feature specifies essentially a parameter indicative of the speed of the algorithm, i.e. a property of algorithms implementing H8 which had been analysed in the prior art because of its practical importance. Both D4 and the decision under appeal refer to D7 as a secondary source of supplementary information concerning the fast implementation of the DHT. The reasons of the decision under appeal are mainly based on D4 and common general knowledge as exemplified in D1.
2.4.3 A small and limited part of D7 is relevant for the decision under appeal
D7 is a document of ten pages, including more than three pages of appendices. The only information contained in D7 which is used in the decision under appeal is the matrix H8 (equation (7) in D7) showing that the transform disclosed in D7 is the same as the one disclosed in the present application (and that it is suitable for implementing the FHT of D4), and a corrected figure 1(c) according to which only two multiplication operations are required as claimed in claim 1. Thus it could be reasonably expected that it was possible to read and understand during the interruption of the oral proceedings at least the parts of D7 which were relevant for the decision under appeal. As mentioned above, the appellant did not submit that the representative lacked sufficient time to analyse D7 during the interruption of the oral proceedings. In this context the board notes that it is not established whether an explicit request for adjournment of the oral proceedings was made, since the minutes on file do not indicate such a request and the request for correction has not been allowed by the examining division.
2.4.4 D7 was referred to in D4
It is uncontested that D4 mentions that the logical construction of the Hartley transform is particularly conducive to easy implementation in very large scale integrated circuits and in this context refers to D7, which discusses details of the Hartley transform.
The appellant's argument that it was not realistic to expect the applicant to analyze every document referred to in the documents present in examination proceedings has not convinced the board that it was unfair not to adjourn the oral proceedings in the present circumstances. D4 refers to D7 particularly in the context of easy implementation of the Hartley transform, and cites the title of D7, "The Fast Hartley Transform Algorithm". Thus it was not necessary to previously analyze all the documents referred to in D4 to realize that D7 might become relevant for the present application, in which the fast Hartley transform is applied to image compression.
2.4.5 In view of the above, the board judges that, since it was not unduly surprising that D7 cited in D4 became relevant for the application, the representative had sufficient time to study D7 and to prepare his comments during the interruption of the oral proceedings and the applicant was given an opportunity to present comments on D7 during the oral proceedings, there was no violation of Article 113(1) EPC.
2.5 The board also assessed whether a substantial procedural violation other than a violation of Article 113(1) EPC occurred in the first instance proceedings. In accordance with established case law (see "Case Law of the Boards of Appeal of the European Patent Office", 5th edition 2006, VII.D.15.4.1), procedural violations which do not adversely affect any party are not considered substantial. Thus the board also took into account in particular the following facts.
2.5.1 The effect of the alleged procedural violations on the decision to refuse the application
The decision under appeal gives several independent reasons for refusing the application (see point VIII above), one being lack of clarity (Article 84 EPC) because of the expression "reversible transform" in the independent claims of the main and the auxiliary request. This reason is independent of the introduction of D7 and would have been sufficient to refuse the application.
2.5.2 The objections under Article 123(2) and 56 EPC
According to the minutes of the oral proceedings, the examining division raised an objection under Article 123(2) EPC with respect to the amendment comprising the feature "requiring at most two multiplication operations when multiplying with a vector" in the independent claims of the auxiliary request. This feature was discussed in the context of inventive step because the examining division raised several objections against the auxiliary request. Hence the introduction of D7 was not decisive for the examining division's finding that the auxiliary request was not allowable.
The appellant argued that the examining division had indicated that there was anyway a lack of inventive step (Article 56 EPC), so that overcoming the other objections by amending the claims would not have changed the fact that the application would be refused. However, an examining division may only consider and decide on the text submitted to it (Article 113(2) EPC). The clarification of a feature or its limitation to what was actually disclosed in the application as filed will normally have an influence on the decision on inventive step. Therefore the introduction of D7 would only have been decisive for the decision to refuse the application, or for the reasons for refusing the application, if the other objections had been overcome.
2.5.3 The feature disclosed in D7 was present in previous versions of the claims
The appellant argued that the examining division was aware more than one month before the oral proceedings of the relevance of the feature relating to "requiring at most two distinct multiplication operations" disclosed in D7 and should therefore have informed the applicant before the oral proceedings of its intention to introduce D7. Although it would have been desirable for the applicant to have had more time to analyse D7 and to prepare amended claims, it has to be taken into account that the feature was only present in a dependent claim until the claims of the auxiliary request were filed with the letter dated 15 January 2003. Thus this feature would only have become decisive for the present case with its introduction into an allowably amended independent claim. This does not therefore change the board's conclusion set out above.
2.5.4 The request for correction of the minutes was not dealt with
Concerning the request for correction of the minutes of the oral proceedings dated 9 April 2003, there is no indication on file that the examining division, which is competent and obliged to decide on this request, has reacted to it. Thus either the request was not dealt with for more than four years or the examining division's reaction to the request has not been put on file.
However the applicant has not reminded the examining division of his request dated 9 April 2003 although the board indicated in its communication of 19 February 2007 that there was no such reminder on file. Furthermore the request was filed after the decision under appeal was posted. Thus if any procedural deficiency has occurred with regard to the request for correction of the minutes, it was only after the decision was posted and therefore had no impact on the decision under appeal.
2.6 In view of the above, the board judges that no fundamental deficiency within the meaning of Article 10 RPBA is apparent in the first instance proceedings. Furthermore, for the same reasons, the board judges that no substantial procedural violation within the meaning of Rule 67 EPC has occurred. Thus the main request is refused.
3. Auxiliary request: Inventive step (Article 56 EPC)
3.1 The closest prior art
It is uncontested that the following features of claim 1 reflect the steps of generally known and standardized transform-based image compression methods (for example JPEG, MPEG-1, and MPEG-2):
1. dividing the image into at least one image set, wherein each image set is a two-dimensional array of pixels having a number of columns M and a number of rows N, said number of columns M being equal to said number of rows N; and
2. for each image set:
1. transforming the image set into a set of coefficients,
2. quantizing each coefficient of the set of coefficients; and
3. coding each quantized coefficient of the set of coefficients in accordance with an entropy code.
In the judgement of the board, this common general knowledge constitutes the closest prior art for the subject-matter of present claim 1. Standard compression methods of this kind, which usually perform a discrete cosine transform (DCT) on blocks of 8*8 pixels, are referred to for instance in D1 (column 1, lines 5 to 29, and figure 1) and D2 (page 803, right-hand column, last paragraph).
3.2 The problems to be solved
The board agrees with the appellant that one problem underlying the invention is that of finding an appropriate alternative transform for efficiently compressing and expanding image data (see paragraph  of the application as published). The feature of controlling the precision of at least one stage of the Hartley transform, by limiting the number of bits used to represent each coefficient, solves a second problem, namely to either boost compression or minimize the amount of hardware by disregarding the least significant bits, for example by truncating or rounding the numbers (see paragraphs  to  of the application as published). Since such a precision control can be carried out on the coefficients of any transform, the two problems will be considered individually below.
3.3 Solutions to the first problem suggested in the prior art
It is uncontested that the Hartley transform has been considered for image compression (see paragraph  of the application as published). For instance D2 (see the abstract) discloses that the discrete Hartley transform (DHT) may outperform the discrete cosine transform (DCT) for the irreversible compression of tomographic images. In this context the board agrees with the decision under appeal that the contested term "irreversible" in D2 refers to irreversible (lossy) compression using the Hartley transform, which has the known property of being reversible in the intended meaning of the present application, namely where the forward and inverse transform are the same (within a constant; see paragraph  of the application as published).
The appellant's argument, that D2 disclosed image compression only on a selected portion of the image and that a person skilled in the art would not use a DHT for transforming an entire image, did not convince the board. Even if the wording of claim 1 justified such a difference being made, the teaching of D2 would not support such a conclusion. D2 mentions that, in contrast with video images, tomographic images have low- or zero-intensity bounding regions (see page 803, the paragraph bridging the columns). The block transform approach, which considers the image in blocks of 8*8 or 16*16 pixels, has become the standard for video compression, but may lead to blocking artefacts visible in the reconstructed image which are unacceptable for medical applications. Thus in medical applications the entire image is treated as a block (see the paragraph bridging pages 803 and 804). But the fact that blocking artefacts are unacceptable in tomographic (in contrast to video) images does not mean that the FHT should not be used for certain block sizes. Instead D2 specifies that the suitability of a given transform for image compression depends on the efficiency with which it can pack the energy of the image into a chosen number of coefficients (see page 804, left-hand column, penultimate paragraph).
3.3.1 For the implementation of the two-dimensional Hartley transform, D2 (see page 806, left-hand column, last paragraph) refers to D3, a two-page paper which discusses the problem that the kernel of the Hartley transform is not separable into a product of factors. The aim of D3 is to "report success in overcoming this apparent difficulty with generalizing the Hartley transform to more than one dimension" (D3, page 1282, left-hand column, third paragraph). One solution "takes the one-dimensional discrete Hartley transforms of the rows one by one, and then transforms the columns" (D3, page 1282, right-hand column, third paragraph). This temporary transform is followed by a conversion involving a sum of four of these temporary transforms. The temporary transform corresponds to the "separable variant of the Hartley transform" discussed in the present application (paragraph  of the application as published) and allows the two-dimensional DHT to be replaced by a number of "calls to a one-dimensional Hartley routine followed by some additions" (D3, page 1282, fourth paragraph from the bottom).
3.3.2 Other papers give more details on how the fast Hartley transform (FHT) may be implemented; see for instance the flowchart of a computer program to calculate a two-dimensional FHT in D4, figure 1, and D7, which is referred to in D4 as reference . In particular, D7 discloses the concrete matrix representations of the one-dimensional DHTs of order 2, 4, and 8, for example the matrix H8 of figure 1 of the present application (see T(8) in equation (7) in D7). D7 also discloses the corresponding signal flow graphs and indicates explicitly the number of nontrivial multiplications and additions required (see Table 1 and corrected figure 1(c)). In particular for H8 two nontrivial multiplications are required.
3.4 Concerning the second problem solved, it is uncontested common general knowledge that the number of bits representing each coefficient of a transform determines (together with other parameters) the precision of the transform, in the present case the Hartley transform, but also the amount and complexity of a hardware implementation. Thus the feature relating to the precision control on its own reflects common general knowledge.
The appellant's argument that there was a synergistic effect between the precision control and the selection of the Hartley transform of order 8 or smaller did not convince the board. Blocks of 8*8 pixels were generally used for block transform coding in standard image compression methods with a DCT (see point 3.1 above). Precision control could be carried out with a DCT (of order 8 or smaller) as well as with a DHT (of order 8 or smaller), and the coefficients of the DHT do not lend themselves better to precision control than the coefficients of a DCT. Thus the precision control and the particular Hartley transforms specified in claim 1 make independent contributions to the compression that can be achieved.
3.5 In the opinion of the board, the method of claim 1 as a whole constitutes a modification of standard image compression methods which a person skilled in the art would have considered to find an appropriate alternative transform for efficiently compressing an image, in particular for reducing the amount and complexity of hardware implementations. In view of the common general knowledge in the technical field of image compression and the knowledge about the Fast Hartley Transform, whose suitability for image compression and whose properties were known, for example from D2, D3, D4 and D7, the board considers the method of claim 1 to be obvious.
3.6 Thus the board judges that the method of claim 1 does not involve an inventive step (Article 56 EPC). Thus the auxiliary request is also to be refused.
For these reasons it is decided that:
The appeal is dismissed.