T 1855/08 () of 5.9.2012

European Case Law Identifier: ECLI:EP:BA:2012:T185508.20120905
Date of decision: 05 September 2012
Case number: T 1855/08
Application number: 00310521.0
IPC class: H04N 7/30
H04N 7/34
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 330.960K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Methods and apparatus for context selection of block transform coefficients
Applicant name: Alcatel Lucent
Opponent name: -
Board: 3.5.04
Headnote: -
Relevant legal provisions:
Rules of procedure of the Boards of Appeal Art 13(1)
European Patent Convention 1973 Art 84
European Patent Convention 1973 Art 54(1)
European Patent Convention 1973 Art 56
Keywords: Clarity and support (yes - after amendments)
novelty and inventive step (yes - after amendments)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The appeal is against the decision of the examining division refusing European patent application No. 00 310 521.0 published as EP 1107608 A2.

II. The following prior art documents cited during the proceedings before the examining division are of relevance to the present decision:

D1: Memon, N: "Adaptive coding of DCT coefficients by Golomb-Rice codes", Proceedings of 1998 International Conference on Image Processing (ICIP98) held from 4 to 7 October 1998 in Chicago, IL (USA), 1998, pages 516-520

D2: Weinberger, M. J. et al: "LOCO-I: A Low Complexity, Context-Based, Lossless Image Compression Algorithm", Proceedings of 1996 Data Compression Conference (DCC'96) held from 31 March 1996 to 3 April 1996 in Snowbird, UT (USA), pages 140-149

D3: ISO/IEC JTC 1/SC 29/WG 1, "FCD14495, Lossless and near-lossless coding of continuous tone still images (JPEG-LS)", public draft date: 1997/7/16

III. The application was refused on the grounds that the subject-matter of claims 1 and 13 according to the main request was not novel in view of D1 (Article 54(2) EPC 1973) and lacked clarity and support by the description (Article 84 EPC 1973). Furthermore, claims 2 to 12 and 14 to 18 did "not add anything of inventive significance".

IV. With the statement of grounds of appeal the appellant filed amended claims according to first and second auxiliary requests.

V. In a communication annexed to the summons to oral proceedings the board expressed the preliminary opinion that it tended to concur with the reasons for the decision. The board also raised additional objections of lack of clarity and support.

VI. With a letter of 3 August 2012 the appellant submitted sets of amended claims according to a main request and first to fourth auxiliary requests, replacing all previous sets of claims on file.

VII. Oral proceedings were held before the board on 5 September 2012. During the oral proceedings the appellant's representative submitted a new set of claims 1 to 9 according to a sole request replacing all previous sets of claims on file.

VIII. The appellant's final request is that the decision under appeal be set aside and that a patent be granted on the basis of:

- description pages 1 to 13 received during oral proceedings,

- claims 1 to 9 received during oral proceedings, and

- drawings sheets 1/3 to 3/3 as originally filed.

IX. Claims 1 to 9 according to the appellant's sole request read as follows:

1. A method for use in a decoder of a block transform-based video and/or image compression system of processing one or more block transform coefficients associated with at least one block of visual data, the method comprising the steps of:

identifying one or more previously decoded block transform coefficients associated with the visual data;

computing a context selection value for selecting a context, for use in decoding a current block transform coefficient associated with the at least one block, the context selection value computation using the one or more previously decoded block transform coefficients, said computation not taking into account the value of the current block transform coefficient; and

decoding the current block transform coefficient using the selected context; wherein the computing need not use context dependent coding parameter information transmitted by an encoder.

2. The method of claim 1, wherein the context selection value is computed as a function of one or more values respectively associated with one or more previously decoded block transform coefficients in near proximity, with respect to a scanning order, to the block transform coefficient to be processed.

3. The method of claim 2, wherein the one or more previously decoded block transform coefficients are a, b and c wherein said coefficients are determined by a first equation: a=(i+1,j-1), b=(i,j-1) and c=(i-1,j) during an upward scan, or by a second equation: a=(i-1,j+1), b=(i-1,j) and c=(i,j-1) during a downward scan, wherein (i,j) corresponds to a position of the current block transform coefficient.

4. The method of claim 1, wherein the previously decoded block transform coefficients are inverse-quantized block transform coefficients.

5. The method of claim 1, wherein the context selection value is used to update parameters used in decoding the block transform coefficient.

6. The method of claim 5, wherein the updated parameters are used in a Golomb decoding process.

7. A decoder for use in a block transform-based video and/or image compression system for processing one or more block transform coefficients associated with at least one block of visual data; the apparatus comprising:

at least one processing device operative to: (i) identify one or more previously decoded block transform coefficients associated with the visual data; and (ii) compute a context selection value for selecting a context, for use in decoding a current block transform coefficient associated with the at least one block, the context selection value computation using the one or more previously decoded block transform coefficients, said computation not taking into account the value of the current block transform coefficient; and decode the current block transform coefficient using the selected context; wherein the computing need not use context dependent coding parameter information transmitted by an encoder.

8. The decoder of claim 7, wherein the previously decoded block transform coefficients are inverse-quantized block transform coefficients.

9. The decoder as claimed in claim 7, wherein the at least one processing device is operative to carry out a method as claimed in any of claims 4 to 6.

X. The examining division's reasoning in the decision under appeal (concerning the claims then on file) can be summarised as follows:

Novelty

The applicant argued that the computed context selection value in claim 1 was based on only previously reconstructed block transform coefficients, which was not the case in D1 because it included the DC value of the current block (DCij).

The alleged distinguishing feature is, however, not present in claim 1. Claim 1 recites "computing a context selection value ... based on the one or more previously reconstructed block transform coefficients". This wording of claim 1 thus does not exclude the possibility that the context selection value is also based on other coefficients.

Hence the subject matter of claim 1 is not novel (Article 54(1) EPC 1973).

The same reasoning applies mutatis mutandis to the corresponding apparatus claim 13 (largely corresponding to present claim 7), which therefore also lacks novelty.

Clarity, support and essential features

Claims 1 and 13 do not meet the requirements of Article 84 EPC 1973 in combination with Rule 29(1) and (3) EPC 1973 because they lack a feature which is essential to the definition of the invention. Indeed, the description highlights that the feature that the context selection value is based on only previously reconstructed block transform coefficients is essential to the definition of the invention, i.e. it is necessary for solving the problem of avoiding the transmission of coding parameters to the decoder (see, for example, page 3, lines 7 to 9; page 4, lines 1 to 5 and page 5, lines 24 to 29).

Furthermore, claims 1 and 13 are not supported by the description, and thus do not meet the requirements of Article 84 EPC 1973, for the following reasons:

Claims 1 and 13 contain the broad feature that the context selection value is computed for use in processing a block transform coefficient associated with at least one block. The description however is confined to context-based coding of transform coefficients (as evident, e.g., from the field of the invention on page 1 and the technical problem mentioned on page 2, which exclusively arises in coding). Claim 1, as it is worded, is thus not limited to coding but also covers other types of processing used in transform-based coding systems (such as various types of filtering). This applies also to the apparatus of claim 13, which, in addition, is only required by the wording of the claim to be suitable for use in a block transform-based coding system.

Finally, claims 1 and 13 do not meet the requirement of clarity of Article 84 EPC 1973 for the following reasons:

The expression "context selection value" used in claims 1 and 13 is unclear because, absent any details as to the type of processing in which this value is used, it is not apparent what is selected and how. The expression has, as such, no well-recognised meaning in the art, and merely means that some unspecified type of selection takes place.

Dependent claims 2 to 12 and 14 to 18 do not add anything of inventive significance (reference made to the communication of 7 March 2006).

Additional observations

As additional observations not forming part of the decision, the examining division indicated that even if claims 1 and 13 were limited by specifying that the context selection value is computed based on only previously reconstructed coefficients, the claimed subject-matter would still be fully anticipated by D1.

XI. The appellant's arguments regarding the present set of claims can be summarised as follows:

Admission of the amended claims and description pages filed during the oral proceedings

The amended claims filed during the oral proceedings were submitted in reaction to objections under Article 84 EPC 1973 raised by the board for the first time either in the communication annexed to the summons to oral proceedings or during the oral proceedings. These amendments overcome all those objections and do not raise fresh issues. They should thus be admitted into the proceedings. The amendments are based inter alia on the following passages of the application as filed: page 1, lines 8 to 11, page 9, lines 20 to 22, page 11, line 10 to page 12, line 14, and figure 5. As to the amended description pages, they are a straightforward adaptation of the description to the final set of claims, thus raising no new issue.

Clarity, support and essential features

The amendments to the claims overcome all the objections raised in the decision under appeal or by the board.

Novelty and inventive step

D1 does not disclose the feature of claim 1 of computing a context selection value for selecting a context, for use in decoding a current block transform coefficient associated with the at least one block, the context selection value computation using the one or more previously decoded block transform coefficients, and said computation not taking into account the value of the current block transform coefficient.

Instead of selecting one context, D1 proposes determining an adequate number of contexts, for instance using 16t different contexts, for computing the value of a parameter k for internal optimisation of the Golomb-Rice encoder. This parameter k depends on coding parameters NC and AC, which both depend on the context C, but D1 is silent on how a given context is determined out of the 16t possible contexts. Rather, D1 assumes that one of these contexts is given, i.e. that it was encoded by the encoder and transmitted.

The method of claim 1 achieves the technical effect that there is no need to transfer information about the context from the encoder to the decoder because the decoder can compute the context of a current block transform coefficient from one or more previously decoded block transform coefficients.

Even if the skilled person were to combine the teachings of D1 with those of either D2 or D3, he would not arrive at the method of claim 1 because both D2 and D3 determine a context based on surrounding pixels (see figure 1 of D2 and figure 3 of D3), whereas the method of claim 1 relies on one or more previously decoded block transform coefficients (representing horizontal and vertical frequencies in the spatial frequency domain as opposed to pixel values in the spatial domain).

Hence the method of claim 1 and the decoder of claim 7 involve an inventive step.

Reasons for the Decision

1. The appeal is admissible.

Procedural matters

2. Admission of the amended claims filed during the oral proceedings

According to Article 13(1) RPBA (Rules of Procedure of the Boards of Appeal, OJ EPO 2007, 536), any amendment to a party's case after it has filed its grounds of appeal may be admitted and considered at the board's discretion. The discretion shall be exercised in view of inter alia the complexity of the new subject-matter submitted, the current state of the proceedings and the need for procedural economy.

In the present case, the appellant filed during the oral proceedings a set of amended claims 1 to 9 according to a sole request replacing all previous requests on file and an amended description.

The board is satisfied that at least some of the amendments filed during the oral proceedings were submitted in reaction to objections under Article 84 EPC 1973 raised by the board for the first time during the oral proceedings.

The amendments did not raise fresh issues and the new subject-matter could be examined as to novelty and inventive step without increased complexity on the basis of the facts and arguments already on file.

For the above reasons the board decided to exercise its discretion under Article 13(1) RPBA to admit the amended claims into the proceedings.

Article 123(2) EPC

3. The board is satisfied that the amended claims filed by the appellant comply with the requirements of Article 123(2) EPC. The amendments are based inter alia on the following passages of the application as filed: page 1, lines 8 to 11, page 9, lines 20 to 22, page 11, line 10 to page 12, line 14, and figure 5.

Article 84 EPC 1973

Regarding the amendments to claim 1, the following observations are made:

- The expression "context selection value" has been clarified as to what is selected by adding that this value is "for selecting a context". Further amendments to claim 1 address the objection as to how it is selected and used.

- The method of claim 1 has been limited to the technical field of the invention by the statement that the method is "for use in a decoder of a block transform-based video and/or image compression" and by an additional step of "decoding the current block transform coefficient using the selected context".

- The word "reconstructed", which the board regarded as insufficiently clear, has been replaced by the word "decoded". In the board's view, the expression "decoded block transform coefficients" in a decoder necessarily implies that these coefficients are the coefficients which are reconstructed by decoding the received compressed data.

- For the sake of clarity, the technical effect that "the computing [in the decoder] need not use context dependent coding parameter information transmitted by an encoder" has been added in claim 1.

- Claim 1 now specifies that the computation of the context selection value does not take into account the value of the current block transform coefficient, which is essential for achieving the above technical effect. The board considers that the further limitation demanded by the examining division that the computation is based only on the previous block transform coefficients was too limiting and unnecessary because other parameters may be taken into account (see e.g. equation (8) on page 11 of the description) as long as the computation uses previously decoded block transform coefficients and need not use transmitted context dependent coding parameter information.

For the above reasons, the board is satisfied that claim 1 meets the requirements of Article 84 EPC 1973.

The same conclusion applies to claim 7 (a decoder having features corresponding to the steps of the method of claim 1). The board is also satisfied that dependent claims 2 to 6, 8 and 9 also meet these requirements.

Novelty (Article 54(1) and (2) EPC 1973)

4. Disclosure of D1

4.1 D1 discloses a method in the field of image compression for efficiently coding DCT block transform coefficients by using optimised Golomb-Rice coding techniques.

The method applies different coding techniques to the DC and AC block transform coefficients.

The DC coefficients of an image are treated as a smaller image which is encoded using JPEG-LS (a standard described in D3), which uses adaptive coding and requires only one pass through the data (see Section 2 of D1).

The AC coefficients are encoded with a Golomb-Rice encoder (see section 3 of D1). As stated in D1, a key factor behind the effective use of Golomb-Rice codes is the estimation of the coding parameter k to be used for a given coefficient or block of coefficients. The parameter k is estimated on the fly by maintaining in each context C, the count NC of the number of times the context C has been encountered so far and the accumulated sum AC of magnitudes of prediction errors within this context C. The coding parameter k is then computed as a function of NC and AC (see page 517, right column). A challenge for efficiently computing the parameter k in the above manner is to reduce the number of contexts (see page 518, left column, first full paragraph). The method of D1 achieves this by (1) comparing the DC coefficient of the current block with the DC coefficient of four adjacent blocks, which yields 16t contexts, where t is the number of quantisation levels, and (2) using a scaling factor s for further reducing the number of contexts to a small number, such as only eight contexts (see page 518).

4.2 The method of D1 thus does not disclose the following features of the method of claim 1:

(a) computing a context selection value for selecting a context;

(b) the context selection value computation using the one or more previously decoded block transform coefficients;

(c) said computation not taking into account the value of the current block transform coefficient;

(d) decoding the current block transform coefficient using the selected context; wherein the computing need not use context dependent coding parameter information transmitted by an encoder.

Indeed, D1 is silent on how the encoder selects a particular one of the small number of contexts for a given block transform coefficient (features (a) to (c)). There is also no disclosure as to whether the decoder receives the context information from the encoder or generates it itself (feature (d)).

4.3 In the reasons (under point 2) for the decision the examining division considered that D1 (see page 518) implicitly disclosed the computing of a context selection value.

The board is not convinced that this feature of claim 1 is implicitly disclosed because D1 only discloses how to determine an adequate number of contexts, not how to compute a value for selecting a context (see page 518).

4.4 For the above reasons, the method of claim 1 is novel in the sense of Article 54(1) and (2) EPC 1973 in view of D1. The same conclusion applies to the decoder of claim 7 and to the subject-matter of dependent claims 2 to 6, 8 and 9.

Inventive step

5. As already set out above, D1 is silent as to how a context for a given block transform coefficient is selected. It is left undisclosed in D1 whether the selected context is one from the small number of contexts determined for calculating the parameter k or whether it is based on more specific context information.

Moreover, the board notes that D1 contains multiple references to D2 (reference [8] in D1) and to JPEG-LS of D3 (reference [1] in D1, which refers to the Working Document corresponding to D3), which both teach to select a context based on previous pixels surrounding the current pixels (see the "Context determination" on page 143 and 144 and figure 1), thereby teaching away from computing a context selection value based on one or more previously decoded block transform coefficients (i.e. based on horizontal or vertical frequencies in the spatial frequency domain, as opposed to based on pixel values in the spatial domain). Since D1 refers to an improvement of the coding techniques disclosed in D2 and D3 and is silent as to how a particular context is selected, the board sees no convincing argument as to why a person skilled in the art would have changed the selection of the context to avoid the shortcomings of the known techniques, in particular a high amount of overhead information (see page 2, last paragraph, of the description).

For the above reasons, the method of claim 1 is not rendered obvious by the disclosures of D1, D2 and D3 (Article 56 EPC 1973).

The same conclusion applies to the corresponding decoder of claim 7 and to the subject-matter of dependent claims 2 to 6, 8 and 9.

Conclusion

6. The board is thus satisfied that the European patent application and the invention to which it relates meet the requirements of the Convention.

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the department of first instance with the order to grant a patent in the following version:

Description:

Pages 1 to 13 received during the oral proceedings.

Claims:

Nos. 1 to 9 received during the oral proceedings.

Drawings:

Sheets 1/3 to 3/3 as originally filed.

Quick Navigation