Informationen
Diese Entscheidung ist nur auf Englisch verfügbar.
T 1619/17 (Adaptive variable length coding/NOKIA TECHNOLOGIES OY) 26-02-2021
Download und weitere Informationen:
Adaptive variable length coding
Amendments - added subject-matter
Amendments - main request and first to third auxiliary requests (yes)
Amendment after summons - exceptional circumstances
Amendment after summons - fourth auxiliary request (no)
Summary of Facts and Submissions
I. The appeal lies from the decision of the examining division to refuse European patent application No. 03700323.3, which was filed as international application PCT/FI03/00055 published as WO 03/063360. In the decision under appeal, the examining division decided that a main request and first, second and third auxiliary requests added subject-matter extending beyond the content of the application as filed and that the subject-matter of claim 1 of each of the three auxiliary requests was not inventive over the disclosure of document
D4: JP H05 347710 A, 27 December 1993,
and related documents
A4: Abstract of JP H05 347710 A, and
T4: Translation by the Japanese Patent Office of JP H05 347710 A.
II. With the statement of grounds of appeal, the appellant filed an amended main request and amended first to third auxiliary requests.
III. In a communication accompanying a summons to oral proceedings, the board expressed its preliminary opinion that claims 1 and 3 of the main request were unclear and added subject-matter extending beyond the content of the application as filed and that claim 1 of the main request was not novel over document D4 and lacked inventive step over the prior art acknowledged in the background section of the application. The board found that the same objections applied to the first auxiliary request, that the second auxiliary request did not fulfil the requirements of Articles 56, 84 and 123(2) EPC, and that the third auxiliary request did not fulfil the requirements of Articles 56 and 84 EPC.
IV. In response to the board's preliminary opinion, the appellant requested that the oral proceedings be held by videoconference.
V. Oral proceedings were held by videoconference as scheduled, during which the appellant filed a fourth auxiliary request. At the end of the oral proceedings, the Chair announced the board's decision.
VI. The appellant's final requests were that the contested decision be set aside and that a patent be granted on the basis of the main request or one of the first to fourth auxiliary requests.
VII. Claim 1 of the main request reads as follows:
"A method of encoding a set of quantised transform coefficient values comprising a certain first number of zero valued quantised transform coefficients and a certain second number of non-zero valued quantised transform coefficients, wherein the method comprises:
forming a set of symbol pairs to be variable-length encoded from said set of quantised transform coefficient values, said symbol pairs comprising a first value indicative of the value of the non-zero-valued quantised transform coefficient and a second value indicative of a number of zero-valued quantised transform coefficients preceding or following the non-zero-valued quantised transform coefficient, and
variable-length encoding each said set of symbol pairs by using a set of variable-length codewords and a mapping between the first value and the second value and a variable length codeword in the set of variable-length codewords;
using the first number or the second number as a parameter; and
providing an indication of the parameter in an encoded bitstream;
characterised in that said mapping comprises using the parameter for:
using a fixed set of variable length codewords as a variable length coding table, and changing the mapping between possible values of the pairs of the first value and the second value, which may arise in the set of quantised transform coefficient values for an image block, and variable-length codewords in the fixed set of variable-length codewords in dependence upon the parameter."
VIII. Claim 1 of the first auxiliary request differs from that of the main request in that the text "a certain first number of" and "a certain second number of" was deleted and the text "using the first number or the second number as a parameter" was replaced with "using the number of non-zero valued quantised transform coefficients as a parameter".
IX. Claim 1 of the second auxiliary request differs from that of the first auxiliary request in that the text at the end of the claim starting from "using the number of non-zero valued quantised transform coefficients" was replaced with
"and
providing an indication of the number of non-zero valued quantised transform coefficients in an encoded bitstream;
characterised in that said mapping comprises using both the number of non-zero valued quantised transform coefficients and a type of frame or image block to which the quantised transform coefficients relate for:
using a fixed set of variable length codewords as a variable length coding table, and changing the mapping between possible values of the pairs of the first value and the second value, which may arise in the set of quantised transform coefficient values for an image block, and variable-length codewords in the fixed set of variable-length codewords in dependence upon both the number of non-zero valued quantised transform coefficients and a type of frame or image block to which the quantised transform coefficients relate."
X. Claim 1 of the third auxiliary request reads as follows:
"A method of encoding a set of quantised transform coefficient values comprising zero valued quantised transform coefficients and non-zero valued quantised transform coefficients, wherein the method comprises:
forming a set of run-level pairs to be variable-length encoded from said set of quantised transform coefficient values, wherein said level value indicates the value of the non-zero-valued quantised transform coefficient and the run value indicates a number of zero-valued quantised transform coefficients preceding or following the non-zero-valued quantised transform coefficient, and
variable-length encoding each said set of run-level pairs by using a set of variable-length codewords and a mapping between each run and level and a variable length codeword in the set of variable-length codewords; and
providing an indication of the number of non-zero valued quantised transform coefficients in an encoded bitstream;
characterised in that said mapping comprises using both the number of non-zero valued quantised transform coefficients and a type of frame or image block to which the quantised transform coefficients relate for:
using a fixed variable length codeword table, and changing the mapping between possible values of the run-level pairs, which may arise in the set of quantised transform coefficient values for an image block, and variable-length codewords in the fixed variable-length codeword table in dependence upon both the number of non-zero valued quantised transform coefficients and a type of frame or image block to which the quantised transform coefficients relate."
XI. Claim 1 of the fourth auxiliary request differs from that of the third auxiliary request in that
- "obtained from pixel values of an image block" has been added before ", wherein the method comprises";
- "mapping between each run and level" has been replaced with "mapping between each run and level pair"; and
- the text at the end of the claim following "characterised in that" has been replaced with
"said mapping comprises using both the number of non-zero valued quantised transform coefficients and a type of the image block to which the quantised transform coefficients relate for:
using a fixed set of variable length codewords, and changing only the mapping between possible values of the run-level pairs and variable-length codewords in the fixed set of variable-length codewords in dependence upon both the run value and the type of the image block to which the quantised transform coefficients relate."
XII. The appellant's arguments, where relevant to this decision, are addressed in detail below.
Reasons for the Decision
Application
1. The application concerns adaptive variable-length encoding of a set of quantised transform coefficient values, for instance for video compression.
1.1 Video coding systems reduce spatial redundancy using a technique known as "block-based transform coding", whereby a mathematical transformation is applied to the pixels of an image on a macroblock-by-macroblock basis. Transform coding translates the image data from a representation comprising pixel values to a form comprising a set of Discrete Cosine Transform (DCT) coefficient values (page 4, lines 17 to 27, of the international publication). In a video encoder, the DCT coefficients for each block are quantised (page 8, lines 16 to 27; Figure 1, transformation block 104 and quantiser 106) to form a sequence ("set" in the claims) of quantised coefficient values (page 8, line 29, to page 9, line 10; Figure 4).
1.2 The video encoder represents each non-zero quantised coefficient value in the sequence by two values: "level", which is the value of the quantised coefficient, and "run", which is the number of consecutive zero-valued coefficients preceding the coefficient in question (page 9, lines 12 to 19). For example, as described on page 20, line 27, to page 22, line 1, the sequence "0, 1, 2, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0" corresponds to the (run, level) pairs "(1, 1), (0, 2), (3, -1), EOB" (where the end-of-block symbol EOB indicates that there are no more non-zero values). The run and level values are further compressed using variable length coding (VLC). A variable number of bits is assigned to each (run, level) pair such that symbols which are more likely to occur are represented by VLC codewords having fewer bits. Look-up tables are used to define the mapping between each possible symbol and its corresponding variable length code (page 9, line 21 to page 10, line 14; page 22, lines 4 to 14).
1.3 In the method described in the application, VLC coding of the (run, level) pairs is performed by selecting one of a set of VLC coding (look-up) tables (or "assignment tables") stored in the encoder, where each coding table defines a set of variable-length codewords and a mapping between the codewords and the possible (run, level) pairs. A coding table is selected on the basis of either the number of non-zero-valued coefficients or the number of zero-valued coefficients in the array of quantised transform coefficients for the image block being coded (page 28, lines 11 to 25; page 34, line 22, to page 35, line 3).
Main request
2. Added subject-matter - claim 1
2.1 Both in the decision under appeal and in the board's communication, the feature "using a fixed set of variable length codewords as a variable length coding table" (emphasis added) of the characterising part of claim 1 was considered to infringe Article 123(2) EPC.
2.2 In line with the appellant's arguments discussed in the decision under appeal (point 1.1) and in the board's preliminary opinion (points 8.2 and 9.1, last paragraph), at the oral proceedings the appellant reiterated that the feature "using a fixed set of variable length codewords as a variable length coding table, and changing the mapping [...]" meant that a single list of VLC codewords, such as the list contained in the rightmost column of Table 1 on page 21 of the international publication, was used as the VLC table and that the mapping from (run, level) pairs to VLC codewords was changed in dependence on a parameter by selecting a mapping from (run, level) pairs to the VLC indices of the VLC codewords (second rightmost column of Table 1). Hence, the different mappings between (run, level) pairs and VLC codewords were implemented by storing the list of VLC codewords only once and by storing one list of VLC indices for each mapping. This solution for implementing the mappings reduced memory consumption.
2.3 The appellant argued that the feature "using a fixed set of variable length codewords as a variable length coding table" was disclosed in several passages of the application as published. It was clear from page 26, lines 13 to 16, and page 27, line 28, to page 28, line 2, that the mapping described in the application was a kind of assignment or relationship between the input values and the output values. Although assignment tables were mentioned in the application, for example on page 28, lines 11 to 18, there were other possibilities for implementing different mappings. Table 1 on page 21 showed an example of a look-up table including a mapping. The mapping could be done by using the VLC indices as specified in claim 1. The "fixed set of variable length codewords" of claim 1 was the fixed VLC table corresponding to the rightmost column of Table 1. This was disclosed on page 20, lines 16 to 25, and page 37, lines 11 to 14. It was clear from page 37, lines 11 to 14, that the fixed set of VLC codewords was used as a VLC table, and that only the mapping changed between image blocks.
2.4 The board is however of the opinion that it cannot be directly and unambiguously derived from the passages cited by the appellant that a "fixed set of variable length codewords" is used as a VLC table, nor that the fixed set of codewords and the mappings are used as specified by claim 1. The appellant argued (see point 2.2 above) that these features were to be interpreted as meaning that the VLC tables were implemented by storing a single list of VLC codewords and a plurality of lists of VLC indices, one for each mapping.
The passage on page 26 discloses that a relationship is established between the codewords and the mappings between the (run, level) pairs, the passage on page 27 discloses that the codeword is selected from a set of codewords, and page 28, lines 11 to 18, describes "assignment tables" which define assignments of pairs of values to codewords. But none of these passages defines the set of codewords as the VLC table or assignment table itself. The board could not find any passage describing the rightmost column of Table 1 as a VLC table.
Page 20, lines 16 to 25, refers to a "fixed look-up table" but does not explain how it is implemented. The "fixed set of VLC codewords" is mentioned on page 37, lines 11 to 14, which discloses that "a fixed set of VLC codewords is used and only the mapping [...] changes ...". However, that passage only refers to the fixed set of VLC codewords and mapping at an abstract level; it does not describe a concrete implementation of the set of VLC codewords and the mapping. From that passage it cannot be directly and unambiguously derived that the mapping is done by using the fixed set of VLC codewords as a VLC table, let alone that the fixed set of VLC codewords is stored only once.
2.5 Therefore, claim 1 does not fulfil the requirements of Article 123(2) EPC as it adds subject-matter extending beyond the content of the application as filed.
First and second auxiliary requests
3. Claim 1 of each of the first and second auxiliary requests also includes the feature of claim 1 of the main request objected to above. Therefore, for the same reasons as given for the main request, the first and second auxiliary requests do not fulfil the requirements of Article 123(2) EPC.
Third auxiliary request
4. Added subject-matter - claim 1
5. The characterising part of claim 1 of the third auxiliary request includes the following feature:
(a) "using a fixed variable length codeword table, and changing the mapping between possible values of the run-level pairs, which may arise in the set of quantised transform coefficient values for an image block, and variable-length codewords in the fixed variable-length codeword table in dependence upon both the number of non-zero valued quantised transform coefficients and a type of frame or image block to which the quantised transform coefficients relate".
5.1 In its communication under Article 15(1) RPBA 2020, the board expressed its preliminary opinion that, since the feature "using a fixed set of variable length codewords as a variable length coding table" of the higher ranking requests was no longer specified in claim 1 of the third auxiliary request, the objection against that feature had been overcome.
However, at the oral proceedings the appellant was heard on the question of whether feature (a) added subject-matter for reasons similar to those given for the main request, given that it still specified the use of a (single) fixed VLC codeword table.
5.2 The appellant's arguments as regards compliance of feature (a) with Article 123(2) EPC were essentially the same as those given for claim 1 of the main request. According to the appellant, claim 1 of the third auxiliary request should also be interpreted as specifying that a single occurrence of the codewords is stored, the lists of indices being used for the mappings. The appellant cited page 35, lines 16 to 20, and the tables on page 36 as further basis for the feature. In the statement of grounds of appeal, the appellant argued that changing the wording "a fixed set of variable length codewords as a variable length coding table" to "a fixed variable length codeword table" did not bring anything new to the claims.
5.3 The description on page 35, lines 13 to 30, discloses that the variation of the statistical properties of the (run, level) pairs with respect to the number of non-zero-valued coefficients may be obtained empirically. The tables on page 36 illustrate probability distributions of (run, level) pairs. According to page 35, lines 16 to 18, the VLC codewords and the mappings between the codewords can be designed and stored as one or more look-up tables in the encoder. In the board's opinion, this means that if there is one single mapping, only one look-up table is stored. It does not directly and unambiguously disclose that the list of VLC codewords is stored once as the VLC table separately from the mappings and that each mapping is implemented as a list of indices. Therefore, these passages do not disclose feature (a).
5.4 The board concludes that claim 1 of the third auxiliary request does not fulfil the requirements of Article 123(2) EPC.
Fourth auxiliary request
6. Admission of the request into the proceedings
6.1 The fourth auxiliary request was filed during the oral proceedings and hence in a late phase of the already advanced stage of the appeal proceedings after notification of a summons to oral proceedings as referred to in Article 13(2) RPBA 2020.
The appellant argued that the late submission of this auxiliary request was justified and that the request should be admitted because the objection of added subject-matter against the third auxiliary request had been raised for the first time at the oral proceedings. These were exceptional circumstances justifying admittance of the request. With regard to the question of whether this request addressed the outstanding objections, the appellant maintained its argument that, compared with the prior art, the claimed method had the technical effect of reducing memory requirements by storing only one occurrence of the fixed list of VLC codewords as the VLC table.
6.2 The board agrees that the objection of added subject-matter against the third auxiliary request was raised for the first time in the oral proceedings. However, the characterising part of claim 1 of the fourth auxiliary request still refers to "using a fixed set of variable length codewords, and changing only the mapping ..." and the appellant maintained its position that the claimed invention achieved the technical effect of reduced memory consumption due to the use of a single VLC codeword table. Since the appellant's case for the allowability of the fourth auxiliary request is still based on an alleged effect for which, in the board's opinion, there is no basis in the application as filed, the fourth auxiliary request is prima facie not allowable.
6.3 Furthermore, the amendments introduced with claim 1 of the fourth auxiliary request also try to address objections that had been raised before the oral proceedings. For example, the insertion of the text "obtained from pixel values of an image block" and of the word "pair" after "mapping between each run and level" concern clarity objections raised in the board's communication. The appellant could have tried to overcome these objections with amendments filed in advance of the oral proceedings and chose not to do so then.
6.4 Therefore, the board does not recognise the presence of any exceptional circumstances which would justify admitting the request at such a late stage. In view of this, in accordance with Article 13(1) and 13(2) RPBA 2020, the board does not admit the fourth auxiliary request into the appeal proceedings.
Conclusion
7. Since the main request and first to third auxiliary requests are not allowable, and the fourth auxiliary request is not admitted into the proceedings, the appeal is to be dismissed.
Order
For these reasons it is decided that:
The appeal is dismissed.