European Case Law Identifier: | ECLI:EP:BA:2008:T111005.20081007 | ||||||||
---|---|---|---|---|---|---|---|---|---|
Date of decision: | 07 October 2008 | ||||||||
Case number: | T 1110/05 | ||||||||
Application number: | 98830522.3 | ||||||||
IPC class: | G06T 9/00 | ||||||||
Language of proceedings: | EN | ||||||||
Distribution: | C | ||||||||
Download and more information: |
|
||||||||
Title of application: | Fractal coding of data in the DCT domain | ||||||||
Applicant name: | STMicroelectronics S.r.l. | ||||||||
Opponent name: | - | ||||||||
Board: | 3.5.04 | ||||||||
Headnote: | - | ||||||||
Relevant legal provisions: |
|
||||||||
Keywords: | Claims - clarity (no) Decision re appeals - exercise of discretion Basis of decisions - opportunity to comment (yes) |
||||||||
Catchwords: |
- |
||||||||
Cited decisions: |
|
||||||||
Citing decisions: |
|
Summary of Facts and Submissions
I. The appeal is against the decision of the examining division to refuse European patent application No. 98 830 522.3.
II. The decision under appeal inter alia contained objections under Articles 84 EPC 1973 and 123(2) EPC 1973.
III. Furthermore the decision under appeal referred inter alia to documents
D2: BARTHEL K. U. et al. 'Adaptive fractal image coding in the frequency domain.' In: Journal on communications, Vol. 45, May 1994, pages 33 to 38. XP 000613711, and
D3: ARTIERI A. et al. 'A one chip VLSI for real time two-dimensional discrete cosine transform.' In: Proceedings of the international symposium on circuits and systems, Espoo, Finland, June 7 to 9, 1988, Vol. 1, 7 June 1988, pages 701 to 704. XP 000093138
and stated that the important features of the disclosure were:
(i) Discrete Cosine Transforms (DCTs)were performed using domain blocks and range blocks;
(ii) the range blocks were scalable;
(iii) calculations could be performed in parallel on a plurality of range blocks;
(iv) the size of the range blocks could be selected as a programmable choice.
According to the decision under appeal, D2 disclosed the basic method of fractal image coding in the frequency domain using DCTs (feature (i)) in which the size of the range blocks could be varied (feature (ii)). D2 also implicitly disclosed feature (iv). Starting from D2, a person skilled in the art would have been faced with the problem of how to implement the coding in practice. An obvious solution would have been to use a chip manufactured specially for this purpose, such as the chip known from D3, which was able to perform operations in parallel and used differently sized blocks. Thus the requirement of Article 56 EPC 1973 was not met.
IV. The applicant appealed and submitted the text of claim 1 of a main request and of first and second auxiliary requests, respectively, in the statement of grounds of appeal. Concerning one of the features objected to in the decision under appeal under Articles 84 EPC 1973 and 123(2) EPC 1973, the appellant submitted that it was the result of an inadvertent transcription error and had been corrected. Other corrections to the text of the application were requested. The appellant indicated parts of the application in which other features objected to under Article 123(2) EPC 1973 were in his view disclosed. The appellant also filed two affidavits in which two authors expressed their understanding of the application. Furthermore the appellant submitted arguments concerning the issue of inventive step and submitted that a substantial procedural violation justifying the refund of the appeal fee had occurred because the objection under Article 56 EPC 1973 appeared to have been dropped in examination proceedings and had surprisingly been used again in the decision under appeal.
V. In a communication annexed to a summons to oral proceedings the board expressed doubts that the application as originally filed disclosed all the features objected to under Article 123(2) EPC 1973 in the decision under appeal. The board also indicated that a particular hardware architecture, which could be configured according to the value of a size command parameter, seemed to be an essential feature of the invention and that relevant method steps which solved the underlying problem were missing from claim 1, contrary to Article 84 EPC 1973. Concerning the alleged substantial procedural violation, the board indicated that it had not found any indication in the file that the objection under Article 56 EPC 1973 had been withdrawn or dropped. The board noted that the reasons given in the decision under appeal did not appear to be relevant for the second auxiliary request, so that the board considered remitting the case to the first instance if the main and the first auxiliary request were not allowable.
VI. With a letter dated 28 August 2008 the appellant filed amended substitute claims according to a main request and first and second auxiliary requests and stated that he welcomed a remittal of the case to the first instance.
VII. Claim 1 of the main request reads as follows.
"A method of calculating the bidimensional discrete cosine transform (DCT) of blocks of N*N pixels of a picture, using hardware computational resources, comprising the steps of defining first subdivision blocks called range blocks having a fractional and scaleable size N/2**(i)*N/2**(i), where i is an integer number, in respect to a pre-defined maximum size of N*N pixels of blocks of division of said picture, referred to as domain blocks, characterized in that each domain block is superimposable on another domain block by step shifts each of N/2**(i) pixels and the bidimensional DCT is calculated either on a block of pixels of said predefined maximum size N*N or is calculated simultaneously in parallel on all 2**(i)*2**(i) range blocks of subdivision of a domain block of N*N pixels of said picture using the same hardware computational resources that are used for calculating the bidimensional DCT on a block of said maximum size N*N, by reconfiguring the computational resources according to a programmable choice."
Claim 1 of the first auxiliary request ("secondary alternative request") reads as follows.
"A method of calculating the bidimensional discrete cosine transform (DCT) of blocks of pixels of a certain size N*N of a picture, using hardware DCT computing resources for producing at an output N*N DCT coefficient values, comprising the steps of defining first subdivision blocks called range blocks having a fractional and scaleable size N/2**(i)*N/2**(i), where i is an integer number, in respect to a pre-defined maximum size of N*N pixels of blocks of division of said picture, referred to as domain blocks, characterized in that
each domain block is super imposable on another domain block by step shifts each of N/2**(i) pixels;
attributing a different value of a size selection variable, referred to as size, for said maximum or domain block size N*N and for the selectable different sizes N/2**(i)*N/2**(i) of said range blocks;
programmably selecting a value of said variable size for modifying the configuration of said hardware DCT computing resources for producing said N*N DCT coefficient values either by carrying out calculations on the whole block of N*N pixels of said domain block or simultaneously in parallel on all the 2**(i)*2**(i) range blocks of subdivision of the domain block of N*N pixels, using the same hardware computing resources."
Claim 1 of the second auxiliary request ("least acceptable alternative request") reads as follows.
"A method of calculating the bidimensional discrete cosine transform (DCT) of blocks of pixels of a certain size N*N of a picture, using hardware DCT computing resources for producing at an output N*N DCT coefficient values, comprising the steps of defining first subdivision blocks called range blocks having a fractional and scaleable size N/2**(i)*N/2**(i), where i is an integer number, in respect to a pre-defined maximum size of N*N pixels of blocks of division of said picture, referred to as domain blocks, characterized in that
each domain block is super imposable on another domain block by step shifts each of N/2**(i) pixels; and comprises the steps of
attributing a different value of a size selection variable, referred to as size, for said maximum or domain block size N*N and for the selectable different sizes N/2**(i)*N/2**(i) of said range blocks;
programmably selecting a value of said variable size for modifying the configuration of said hardware DCT computing resources for producing said N*N DCT coefficient values either by carrying out calculations on the whole block of N*N pixels of said domain block or simultaneously in parallel on all the 2**(i)*2**(i) range blocks of subdivision of the domain block of N*N pixels, the method comprising the steps of:
a) ordering the pixels in function of a subdivision in range blocks of a certain size by rearranging the input pixels in a number 2**(i) of sequences or vectors of 2**(i) components;
b) calculating in parallel 2**(i) monodimensional DCTs by processing said vectors defined in the preceding step a);
c) arranging the output sequences of the monodimensional DCTs relative to said 2**(i) vectors;
d) completing the calculation in parallel of 2**(i) bidimensional DCTs by processing said output sequences of monodimensional DCTs produced in step c); and
e) arranging the output sequences of bidimensional DCTs generated in step d) in a number 2**(i) of vectors of bidimensional DCT coefficients."
VIII. Oral proceedings were held on 7 October 2008. Nobody was present on behalf of the appellant. At the end of the oral proceedings the chairman pronounced the board's decision.
IX. The appellant had requested in writing:
- to set aside the decision under appeal;
- to reimburse the appeal fee and
- to grant a patent on the basis of the claims of
the main, first or second auxiliary request filed
with the letter dated 28 August 2008.
X. The appellant's arguments submitted in writing, insofar as they are relevant for the outcome of the appeal, can be summarised as follows.
Clarity (Article 84 EPC 1973)
The essential feature of the invention of a particular hardware architecture, which could be configured according to the value of a size command parameter, was reflected in claim 1 of the main request in the feature "by reconfiguring the computational resources according to a programmable choice".
Inventive step (Article 56 EPC 1973)
Claim 1 of all requests specified that the DCT was bidimensional. D3 did not disclose parallel calculations of DCT coefficient values on a plurality of two-dimensional blocks of pixels. Instead D3 disclosed a chip architecture that calculated the one-dimensional DCT of rows of pixels and the one-dimensional DCT of columns of pixels. The gist of the invention was the applicant's finding that the same hardware resources could be used for different modes of calculating the DCT on incoming N*N blocks by reconfiguring the hardware resources depending on a programmable choice.
Substantial procedural violation (Article 113(1) EPC 1973)
The communications and the summons to oral proceedings dispatched in examination proceedings did not provide a concretely reasoned interpretation of the cited prior art documents. They offered only a general and incorrect representation of the teachings contained in document D3. Because of the lack of precisely reasoned objections the applicant did not have the opportunity to effectively respond to the objections and had had to file an appeal.
Reasons for the Decision
1. The appeal is admissible.
2. Main request: clarity (Article 84 EPC 1973)
2.1 According to Article 84 EPC 1973, "[t]he claims shall define the matter for which protection is sought. They shall be clear and concise and be supported by the description." Furthermore, according to the opinion G 1/04 of the Enlarged Board of Appeal (OJ EPO 2006, 334, see Reasons 6.2), Article 84 EPC 1973 "signifies that an independent claim within the meaning of Rule 29 EPC [1973] should explicitly specify all of the essential features needed to define the invention, and that the meaning of these features should be clear for the person skilled in the art from the wording of the claim alone." According to established case law, all features which are necessary for solving the technical problem with which the application is concerned have to be regarded as essential features (see Case Law of the Boards of Appeal of the European Patent Office, 5th edition 2006, II.B.1.1.3).
2.2 The application relates to the calculation of the discrete cosine transform (DCT) of a block of pixels. In particular, the application is concerned with the technical problem of calculating in parallel the DCT on several blocks using a hardware architecture which provides for the scalability of the size of the blocks (see paragraphs [0008] to [0010] of the published application).
2.3 Hence method claim 1 should explicitly specify the configuration steps which configure the hardware computational resources and allow calculating in parallel the DCT on several blocks of a given size, the given size being scalable and thus having different values.
2.4 However claim 1 does not explicitly specify such features for the following reasons.
2.4.1 Claim 1 does not explicitly specify in structural terms the hardware computational resources which are used and how they are reconfigured.
2.4.2 The final feature "by reconfiguring the computational resources according to a programmable choice" in claim 1 implies that the hardware computational resources are programmable and allow a choice to be made. Claim 1 also specifies that the hardware computational resources can be used for two different types of calculations. The first type is the calculation of the bidimensional DCT on a block of size N*N and the second type is the simultaneous calculation in parallel of the bidimensional DCTs on all 2**(i)*2**(i) subdivision blocks of the N*N block, i being an integer number. The input values for both types of calculations are the N*N pixel values. But the output values of the different calculations are different and depend on the value of i (disregarding the degenerate case of i = 0). This implies that the hardware must be "configured" or "programmed" in a general meaning to perform the calculation according to the choice made from the different possible calculations. But these implications do not specify which steps are needed to reconfigure the used computational resources.
2.4.3 The remaining features in claim 1 do not specify the method of calculating the bidimensional DCT itself, but instead relate to aspects of fractal image coding. Features of this kind are the attribution of the names "range blocks" and "domain blocks" and the feature that each domain block is superimposable on another domain block by step shifts each of N/2**(i) pixels. These features relate to the generation of pixel blocks which are input to the computational resources but are not features in accordance with point 2.3 above.
2.5 In view of the above, the board judges that claim 1 of the main request is not clear (Article 84 EPC 1973).
3. First auxiliary request: clarity (Article 84 EPC 1973)
3.1 Claim 1 of the first auxiliary request differs from claim 1 of the main request essentially in that it comprises the following two features
- "attributing a different value of a size selection variable, referred to as size, for said maximum or domain block size N*N and for the selectable different sizes N/2**(i)*N/2**(i) of said range blocks" and
- "programmably selecting a value of said variable size for modifying the configuration of said hardware DCT computing resources for producing said N*N DCT coefficient values".
3.2 The configuration or programming of the hardware computational resources discussed in the context of the main request (see point 2.4.2 above) requires distinguishing the different block sizes (and thus the corresponding different calculations). Thus the two above features of claim 1 of the first auxiliary request have the technical meaning that the hardware computational resources are such that they can be "configured" or "programmed" by selecting a value of a size selection variable which distinguishes the different selectable block sizes. Since the claim does not specify any configuration or calculation steps which are dependent on the variable, these features do not specify the method steps more precisely than the features of claim 1 of the main request. In particular, the claim does not specify which steps are needed to reconfigure the computational resources for the calculation of the different size blocks using the same hardware computing resources. Thus the objection as to lack of clarity raised against claim 1 of the main request is also valid against claim 1 of the first auxiliary request.
3.3 Hence the board judges that claim 1 of the first auxiliary request is not clear (Article 84 EPC 1973).
4. Second auxiliary request
4.1 Claim 1 of the second auxiliary request differs from claim 1 of the first auxiliary request essentially in that it comprises the features a) to e) (see point VII above). These features specify that range blocks of a certain size are ordered, 2**(i) monodimensional DCTs are calculated in parallel and the output sequences of the monodimensional DCTs are processed to complete the calculation of the 2**(i) bidimensional DCTs. Hence the hardware computational resources have a two-stage functionality of calculating in a first stage a number of monodimensional DCTs depending on the value of the size selection variable and in a second stage the bidimensional DCTs based on the output of the first stage.
4.2 The application explains in detail the mathematical considerations which result in the conclusion that the 4*4 and the 8*8 bidimensional DCTs can be calculated by first calculating monodimensional DCTs and then calculating the bidimensional DCT starting from the monodimensional DCTs (see paragraphs [0050] and [0069]). This partition of the calculation in two stages also allows the calculation of four 4*4 DCTs in parallel (see paragraphs [0057] to [0062], [0083] to [0093] and figure 12).
4.3 Hence the size-dependent two-stage functionality of the hardware computational resources reflects the finding that certain bidimensional DCTs can be calculated in two stages as discussed in point 4.2 above. And since the partition in two stages also allows calculating certain DCTs in parallel, the two-stage functionality of the hardware computational resources is also one of the features which is described as solving the problem underlying the invention (see point 2.3 above).
4.4 Hence the argumentation developed in section 2.4 above is not valid for the second auxiliary request.
5. Remittal (Article 111(1) EPC 1973)
5.1 The reasons concerning Article 56 EPC 1973 given in the decision under appeal do not apply to the subject-matter of claim 1 of the second auxiliary request. For claim 1 of the second auxiliary request comprises not only the "important features of the disclosure" considered in the decision under appeal, but also essential features (see points 3.1 and 4.1 above) which are not discussed in the decision under appeal.
The board notes that the reasons given in the decision under appeal only concern claim 1. Nothing can be derived from the decision under appeal concerning the subject-matter of original claim 2, which is now in essence included in claim 1 of the second auxiliary request.
5.2 The other objections raised in the decision under appeal (see point II above) relate to features which are not present in claim 1 of the second auxiliary request ("least acceptable alternative request" as it is headed). No additional reasons are given in the decision under appeal for the statement that "[t]he examining division sees no patentable matter in the application". The examining division will have to examine whether claim 1 sets out in a sufficiently clear manner the size-dependent two-stage functionality which seems to find support in the description (see paragraphs 4.2 and 4.3 above) and whether it defines patentable subject-matter.
5.3 Hence the board judges the appeal to be allowable on the basis of the second auxiliary request.
5.4 It follows from points 5.1 and 5.2 that the amendments made in appeal proceedings require further substantive examination. Furthermore the amendments comprise apparent deficiencies such as an incomplete claim 2 of the second auxiliary request and references to "2i" DCTs and vectors in claim 3 of the second auxiliary request whereas claim 1 refers to 2**(i) DCTs or vectors.
5.5 In view of the above, the board has decided to remit the case to the first instance in application of Article 111(1) EPC 1973.
6. Reimbursement of the appeal fee (Rule 67 EPC 1973)
6.1 Rule 67 EPC 1973 applies for the reasons given in decision J 10/07 (to be published in the Official Journal), point 7. According to Rule 67 EPC 1973, "[t]he reimbursement of the appeal fee shall be ordered in the event of interlocutory revision or where the Board of Appeal deems an appeal to be allowable, if such reimbursement is equitable by reason of a substantial procedural violation."
6.2 The appellant has raised two distinct criticisms of the procedure before the first instance (see points IV and X above) which concern potential substantial procedural violations.
6.3 Concerning the first criticism (refusing the application on the basis of an allegedly dropped objection), there is no indication in the file that the objection under Article 56 EPC 1973 had been withdrawn or dropped. On the contrary, when issuing the summons to oral proceedings pursuant to Rule 71a(1) EPC 1973 the examining division informed the applicant as follows.
"In view of paragraph 1 above, the added features should be removed from the claims. However in this case, the claims would be the same as those already objected to in the communication of 25. 11. 03 so that the same objections still apply."
6.4 The communication of 25 November 2003 (see page 2, paragraph 2) had raised an objection under Article 56 EPC 1973 based on a combination of D2 and D3. The applicant presented his comments to this objection in a letter dated 6 May 2004. Hence the applicant objectively could expect that this objection could be raised in the oral proceedings before the examining division and could ultimately constitute a reason to refuse the application. Thus the decision under appeal was based on a ground on which the applicant had an opportunity to present his comments (Article 113(1) EPC 1973).
6.5 Concerning the second criticism (lack of reasoned communications), the appellant has substantiated why the reasoning in the communications pursuant to Article 96(2) EPC 1973 concerning lack of inventive step on the basis of D2 and D3 was allegedly insufficient. Lack of inventive step was a ground for refusing the application and was based on the factual reasons derived from D2 and D3 (see point III above).
6.6 The factual reasons concerning claim 1 were set out in the communication dated 25 November 2003 (page 2, paragraphs 1 and 2) as follows.
"In the reply of 2.4.03 it was argued that the subject matter of claim 1 is distinguished from the prior art because the computations are carried out in parallel. However parallel computation is a well-known technique for speeding up calculations and it would be obvious for the skilled person to use this technique here as well. Furthermore, if is not obvious exactly how to implement the parallel computations, then the features which make this possible should be included in the claim, otherwise the claim is missing essential features (Article 84 EPC).
A VLSI chip is known from D3 which can carry out computations on several different sized blocks (see "chip features", page 701). As is clear from "operative part" on page 703, the chip may calculate DCTs in parallel. It would therefore be obvious for the skilled person to use such a chip with e.g. the method disclosed in D2 and thus arrive at the subject-matter of claim 1. Claim 1 is therefore not allowable."
6.7 The applicant had indeed emphasised in the reply of 2 April 2003 the feature that the computations were carried out in parallel. The board sees nothing wrong in limiting the above analysis of D3 to the emphasised feature. Moreover the objection contained a refutable reason (the chip of D3 was able to calculate DCTs in parallel) why a person skilled in the art would have combined the teachings of D2 and D3. Thus the argumentation was brief but intelligible and gave the applicant an opportunity to provide his comments such as those submitted in the statement of grounds of appeal.
6.8 The question whether the above analysis of D3 is correct is a question of assessment of prior art. If the analysis is incorrect, this has to be regarded as a substantive error, not a procedural violation. Thus the merits of the above analysis need not be considered in the given context.
6.9 The first instance's reasoning in the communications pursuant to Article 96(2) EPC 1973 concerning other objections did not have a substantive effect on the outcome of the proceedings and therefore could not at any rate amount to a procedural violation that could be considered to be substantial.
6.10 In view of the above the board judges that no substantial procedural violation has occurred. Thus the request for reimbursement of the appeal fee must be refused.
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 for further prosecution.
3. The request for reimbursement of the appeal fee is refused.