T 1370/18 (Entropy coding/FRAUNHOFER GESELSCHAFT) 02-12-2021
Download and more information:
Method for encoding a symbol, method for decoding a symbol, method for transmitting a symbol from a transmitter to a receiver, encoder, decoder and system for transmitting a symbol from a transmitter to a receiver
Fraunhofer-Gesellschaft zur Förderung der
angewandten Forschung e.V.
Claims - clarity after amendment (yes)
Amendments - added subject-matter (no)
Inventive step - (yes)
Remittal
I. The appeal lies from the decision of the examining division to refuse European patent application No. 09776891.5.
The following documents were cited in the decision under appeal:
D1: US 2006/0106870 A1, published on 18 May 2006;
D2: US 5 408 234 A, published on 18 April 1995;
D3: D.T. Hoang; P.M. Long; J.S. Vitter: "Multiple-Dictionary Compression Using Partial Matching", Proceedings of the Data Compression Conference, 1995, DCC '95., 30 March 1995, pages 272-281, Piscataway, NJ, USA;
D4: EP 0 286 719 A2, published on 19 October 1988.
The examining division decided that the subject-matter of independent claims 1 and 7 of a main request and first and second auxiliary requests lacked inventive step over document D1 in combination with one of documents D2, D3 or D4 or the common general knowledge, and also lacked inventive step over document D3 considered alone. The examining division further decided that claims 1 and 7 of the main request and claim 7 of the first and second auxiliary requests did not fulfil the requirements of Article 84 EPC.
II. With the statement of grounds of appeal, the appellant submitted copies of the main request and of the first and second auxiliary requests with an amended claim 7 in each of the requests.
III. The appellant was summoned to oral proceedings. In a subsequent communication sent in advance of the oral proceedings, the board expressed its preliminary opinion that the subject-matter of claims 1 and 7 of each of the requests was not inventive over either document D1 or the common general knowledge, and that neither claims 1 and 7 of the main request nor claim 7 of the two auxiliary requests was clear.
IV. With its letter of reply, the appellant filed amended claims according to a main request and first and second auxiliary requests.
V. Oral proceedings were held as scheduled. During the oral proceedings, the appellant filed amended claims of a main request, which were to replace all requests on file. At the end of the oral proceedings, the Chair announced the board's decision.
VI. The appellant's final requests were that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main request filed during the oral proceedings.
VII. Claim 1 of the main and sole request reads as follows:
"A method for encoding an original symbol comprising a predefined number of values (S0-SN-1), the method comprising:
(a) determining (S104) whether the symbol can be encoded by a codeword of a first codebook, the first codebook including codewords for a plurality of symbols and a predefined codeword indicating that a symbol cannot be encoded by a codeword of the first codebook;
(b) in case the symbol can be encoded by a codeword of the first codebook, selecting and transmitting (S106) the codeword associated with the symbol from the first codebook; and
(c) in case the symbol cannot be encoded by a codeword of the first codebook:
(c.l) selecting from the first codebook and transmitting (S108) the predefined codeword, and
(c.2) splitting (S118) the symbol into a plurality of first sub-symbols, each of the first sub-symbols comprising a predefined number of values of the original symbol, and selecting and transmitting (S106) a codeword for each of the first sub-symbols from a second codebook,
wherein the encoded symbol is represented only by the codeword selected in step (b) from the first codebook, or by the predefined codeword selected in step (c.l) from the first codebook and the plurality of codewords selected in step (c.2) from the second codebook."
VIII. Claim 7 reads as follows:
"A method for decoding from a bitstream one or more codewords encoding an original symbol comprising a predefined number of values, the method comprising:
(a) determining (S306) whether a first codeword can completely represent the original symbol using a first codebook, the first codebook including codewords for a plurality of symbols and a predefined codeword indicating that a symbol cannot be encoded by a codeword of the first codebook;
(b) in case the first codeword can completely represent the original symbol using the first codebook, selecting (S308) the original symbol from the first codebook using the first codeword; and
(c) in case the first codeword cannot completely represent the original symbol using the first codebook,
selecting (S316) a second codebook for decoding first sub-symbols of the original symbol, wherein each of the first sub-symbols comprises a predefined number of values of the original symbol, and
selecting an entry for each of the first sub-symbols from the second codebook using a second codeword,
wherein the original symbol is represented by the values associated only with the codeword from the first codebook, or associated with a combination of the predefined codeword selected from the first codebook and the plurality of codewords selected from the second codebook, and
wherein at step (c) the first codebook indicates for the first codeword that the original symbol cannot be decoded from the first codebook, and for each of the first sub-symbols an entry is selected from the second codebook."
1. The invention concerns audio and video coding in a telecommunication environment. The idea of the invention is to use multi-dimensional codewords to take advantage of the statistical dependencies between neighbouring symbols and to adapt the codeword length to symbol probabilities (see international publication, page 1, lines 9 to 22).
Admissibility - main request
2. Since the claims of the main (and sole) request address all of the outstanding objections, they can be dealt with in an efficient manner. These are exceptional circumstances which justify admitting the request under Article 13(2) RPBA 2020. Accordingly, the board admits the main request into the proceedings.
Added subject-matter and clarity - independent claims 1 and 7
3. Claim 1 includes essentially all of the features of claim 1 as originally filed and introduces a number of amendments.
3.1 In particular, the feature "an original symbol comprising a plurality of values (S0-SN)" of original claim 1 has been amended to specify that a symbol comprises "a predefined number of values (S0-SN-1)". This feature is based on page 10, lines 4 to 15, and Figure 1 of the application as filed, which disclose a symbol with N values. The amendment in the reference sign of the expression "S0-SN" to "S0-SN-1" is an obvious correction, given that the passage on page 10 describes an "original symbol" comprising N values.
3.2 Claim 1 additionally includes in features (a) a description of the first codebook as "including codewords for a plurality of symbols and a predefined codeword indicating that a symbol cannot be encoded by a codeword of the first codebook". This description was introduced for clarity reasons and is directly and unambiguously derivable from claim 1 as originally filed. It also finds a basis in the application as filed, for example, on page 12, lines 5 to 23, referring to the codebooks illustrated in Figures 2(a) and 2(b).
3.3 Claim 1 further adds that codewords and the predefined codeword are transmitted in (b), (c.1) and (c.2), as described for example on page 10, lines 21 to 37, and in steps S106 and S108 of Figure 1.
3.4 Features (c.2) additionally specify that each of the first sub-symbols comprises a predefined number of values of the original symbol, as originally disclosed on page 11, line 18, to page 12, line 10.
3.5 The additional feature at the end of the claim clarifies that the encoded symbol is represented only by the codeword selected in step (b) from the first codebook, or by the predefined codeword selected in step (c.l) from the first codebook and the plurality of codewords selected in step (c.2) from the second codebook. This is directly and unambiguously derivable from the description of the encoding method, for example on page 10, line 21, to page 11, line 7.
4. Claim 1 of the main (and sole) request is based on claim 1 of the first auxiliary request which was refused by the decision under appeal and against which no objections were raised under Articles 84 and 123(2) EPC in the decision under appeal or in the board's preliminary opinion. Compared to claim 1 of the refused first auxiliary request, claim 1 has been amended to specify that a symbol comprises "a predefined number of values (S0-SN-1)". This amendment restricts the claimed subject-matter to a method of encoding data consisting of symbols with a fixed number of values and corrects the reference sign, as explained above. The board has no objections relating to a lack of clarity of claim 1.
5. Therefore, the board is satisfied that claim 1 complies with Articles 84 and 123(2) EPC.
6. Claim 7 concerns a decoding method corresponding to the encoding method of claim 1. Claim 7 is based on claim 7 as originally filed and has been adapted to specify the decoding method in terms corresponding to those of claim 1. Therefore, for the same reasons as given for claim 1, the board is satisfied that claim 7 meets the requirements of Articles 84 and 123(2) EPC.
Technicality and inventive step - independent claims 1 and 7
7. Claim 1 specifies a method for encoding a symbol for transmission which achieves the technical effect of reducing the amount of data to be transmitted over substantially the whole scope of the claim. According to established case law, a compression algorithm contributes to the technical character of the claimed compression method if it is used for the purpose of reducing the amount of data to be stored or transmitted (T 107/87, reasons 3; T 650/13, reasons 6.3 and 6.4; T 817/16, reasons 3.11 and 3.12; T 697/17, reasons 5.2.3 to 5.2.5; G 1/19, points 29 and 85). The same holds true for an encoding method with the same technical effect.
8. Document D1 discloses a data compression method using a nested hierarchy of fixed phrase length dictionaries (see title). According to an example, a data stream is segmented into 8-byte blocks, each of which are successively processed. Separate dictionaries are maintained for phrases of lengths two, four and eight bytes.
8.1 As described in paragraphs [0025] and [0031] to [0033] with reference to Figure 1, when an 8-byte block is received, the encoder searches the 8-byte dictionary for a match of the current 8-byte block. If a full 8-byte match is found in the 8-byte dictionary, a pointer is retrieved from the 8-byte dictionary, where the pointer points to an item in a list. If there is no match in the 8-byte dictionary, the encoder searches the 4-byte dictionary for each of the 4-byte sub-blocks. For every 4-byte sub-block that has a match, a pointer is retrieved from the 4-byte dictionary. Finally, the encoder searches the 2-byte dictionary for each of the 2-byte sub-blocks.
8.2 The encoder of D1 transmits the pointers for every successful match, and "literals" for all unsuccessful matches (paragraph [0037]). A state table includes all the possible outcomes of encoding an 8-byte block based on the results of the 8-byte comparison R8, 4-byte comparisons R4a and R4b, and two byte comparisons R2a, R2b, R2c and R2d. States with a higher index are always chosen in preference to lower numbered states. The encoder may transmit the state index using a 5-bit encoding (paragraph [0036], Figure 3).
Therefore, the state index in the encoding scheme of D1 indicates which of the plurality of "partitions" was chosen for encoding a block (paragraphs [0013] and [0014], claims 1 to 4 and Figure 4). The compressed data for an 8-byte block (or "description") according to the encoding scheme of D1 includes the partition information (the index indicating the state), the pointers (for the matched sub-blocks) and the literals (for the unmatched sub-blocks) (Figure 4 and paragraphs [0030] and [0031]).
8.3 Document D1 thus discloses an encoding method which uses a first and a second codebook for encoding a symbol and sub-symbols in a similar way to that of claim 1. However, while the encoding method of claim 1 uses a predefined codeword or escape sequence "indicating that the symbol cannot be encoded by a codeword of the first codebook" to indicate to the decoder that a different dictionary was used for the sub-symbols of a symbol (features (c.1) and (d)), the method of document D1 uses partition information as described above.
8.4 The board agrees with the decision under appeal that it was well known at the time of priority of the present application to use an escape code for indicating the change of the dictionary in the context of multi-dictionary coding. Such a feature is also disclosed in document D2 (column 4, lines 53 to 59), document D3 (abstract; page 273, first full paragraph), and document D4 (column 1, line 52, to column 2, line 7; column 3, lines 17 to 43).
8.5 However, the board is not convinced that the skilled person starting from D1 would change the way the encoder of document D1 provides the necessary dictionary information to the decoder to providing the information with escape codes. Document D1 discloses a complete solution for encoding using multiple dictionaries (for 8-byte, 4-byte and 2-byte codes). When starting from document D1, it would not have been obvious for the skilled person to consider replacing the partition information of D1 with an escape code, even though they would have been aware of escape codes, since in order for that to work in the method of D1 the use of escape codes would have to be introduced between multiple levels. The board is not convinced that the skilled person would consider such a drastic overhaul of the encoding scheme of D1.
9. The board comes to the same conclusion when starting from the well-known multi-dictionary encoding schemes, which use an escape code to switch to a second dictionary (see also the passages cited above of documents D2, D3 and D4). Such schemes are well known in the context of text encoding, as for example in documents D3 and D4. In such well-known schemes, the symbols to be encoded do not have a predefined number of values, and the first dictionary is used to encode a sequence of values of a variable length. It is not common either that the sub-symbols have a fixed number of values (features (c.2)). The method of claim 1 differs from those well-known multi-dictionary encoding schemes at least in that the symbols have a predetermined number of values, the second codebook is used to encode sub-symbols of a symbol, where the sub-symbols are obtained by splitting the symbol into sub-symbols with a pre-defined number of values as defined in features (c.2), and the encoded symbol is represented by the plurality of codewords selected in step (c.2) from the second codebook. In the context of encoding symbols of variable length, it does not make sense, from a technical point of view, to split the symbols in this manner in order to encode the sub-symbols using a second dictionary. Therefore, the skilled person starting from such a well-known multi-dictionary encoding scheme would not arrive at the method of claim 1.
10. The same reasoning applies mutatis mutandis to corresponding independent claim 7. Therefore, the subject-matter of independent claims 1 and 7 is inventive over the cited prior art (Article 56 EPC).
Concluding remarks
11. In view of the above, none of the grounds for the refusal of the application can be upheld. However, the description and the other claims may need to be adapted to the independent claims 1 and 7. In view of that, and taking into account that the primary object of the appeal proceedings is to review the decision under appeal in a judicial manner (Article 12(2) RPBA 2020), the decision under appeal is to be set aside and the case is to be remitted to the department of first instance for further prosecution (Article 111(1) EPC).
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the examining division for further prosecution.