T 0109/15 01-09-2015

1. The appeal is admissible.

Main request - Inventive step (Article 56 EPC 1973)

2. Closest prior art

The appellant did not dispute that D7 may be considered to represent the closest prior art for the subject-matter of claim 1 (see page 2, last sentence, of the statement of grounds of appeal).

3. Disclosure of D7

3.1 The appellant did not dispute that D7 discloses a method of coding image data which operates as follows:

Image data is encoded one block at a time, with one block typically being an 8x8 array of pixels. Each block of 64 pixels is converted by a DCT transform into a block of 64 transform coefficients (see page 18, lines 14 to 18) which are then quantised (see page 21, lines 30 to 33). The block of quantised transform coefficients is divided into eight zones of eight coefficients each (see page 24, lines 1 to 5). The first zone to be scanned is called "zone 1". The arrangement of the zones depends on the scan order, which may be vertical, horizontal or zigzag (see figures 11A to 11D, and page 24, lines 5 to 23). In order to determine the most promising of these three scan orders, the numbers of non-zero quantised transform coefficients in zone 1 of each of the vertical, horizontal and zigzag scan orders are counted to determine which scan order yields the greatest number of non-zero coefficients in zone 1 (see figures 11A to 11D and 12, and from page 24, line 28, to page 25, line 35). The thus determined scan order is then selected for the subsequent step of coding the quantised transform coefficients of the whole block (see page 25, line 35, to page 26, line 1).

The step of coding the quantised transform coefficients of the whole block, in particular the creation of "bit vectors" (called "form vectors" in D7), is performed as follows (the reference numbers below refer to figure 13):

The eight quantised transform coefficients of "zone 1" are transferred, one at a time and in the selected scan order, from buffer 374 to detector 392. Detector 392 stores one bit for each coefficient in the 8-bit register 404, said bit having a value indicating whether the corresponding quantised transform coefficient of zone 1 is zero or non-zero. The eight bits stored in register 404 form a "form vector" for zone 1 (see page 26, lines 12 to 19). This 8-bit form vector is then sent to a PROM 406 associated with zone 1, where it is variable-length-coded (VLC) using Huffman coding into a "vector pattern VLC" (i.e. a Huffman-coded form vector) for zone 1 (see page 26, lines 16 to 24 and 31 to 33). The above steps are then repeated for each of "zone 2" to "zone 8", each time reusing register 404 and thus overwriting the (uncoded) form vector of the previous zone. In parallel to the creation of the form vectors, the non-zero quantised transform coefficients of the block are variable-length-coded by PROM 408 (see page 26, lines 24 to 29). Finally, the eight vector pattern VLCs (Huffman-coded form vectors) and VLC-coded non-zero quantised transform coefficients thus obtained are transmitted to the decoder (see page 26, lines 24 to 31, page 27, lines 15 to 17, and page 28, lines 10 to 21).

3.2 The appellant did not dispute that the following steps of the method of claim 1 are thus known from D7:

converting a block of image data into transform coefficients (see page 18, lines 14 to 18);

quantising the transform coefficients such that all, some or none of the transform coefficients become zero (see page 21, lines 30 to 33); and

coding values of the non-zero quantised transform coefficients in any fixed order (see page 26, lines 24 to 29).

3.3 The appellant also did not dispute that the eight 8-bit "form vectors", one for each of the eight zones of a block, together contained 64 bits indicating which quantised transform coefficients of the block are zero and which are non-zero.

However, the appellant disputed that these eight "form vectors" anticipated the "bit vector" of claim 1, because they did not form a "single entity" as specified in claim 1.

The board has some doubts that the rather vague expression "single entity" in claim 1 clearly excludes the eight "form vectors" of D7. However, since the presence or absence of inventive step does not hinge on this point, the board accepts arguendo, in the appellant's favour, that the eight "form vectors" of D7 do not form a "single entity" and thus also do not form a "bit vector" as defined in claim 1.

4. Distinguishing features

For the above reasons, the board is prepared to accept the appellant's view that the method of claim 1 differs from that of D7 by the following distinguishing features:

(1) mapping all the quantised transform coefficients into a one-dimensional list of quantised transform coefficients in any fixed order;

(2) generating the bit vector as a single entity from the one-dimensional list of quantised transform coefficients; and

(3) coding the bit vector using an arithmetic coder.

5. Objective technical problem

The examining division formulated the objective technical problem as "how to provide an alternative coding for the bit vector to efficiently compress it".

The appellant submitted that the objective technical problem solved by distinguishing features (1) to (3) should be formulated more broadly as "how to provide an improved method of coding image data".

Since the board accepts that D7 does not disclose a single bit vector (see point 3.3 supra), the board concurs with the appellant that the bit vector should not be mentioned in the objective technical problem. Hence, the board accepts the appellant's formulation of the objective technical problem.

6. Obviousness

6.1 Re distinguishing features (2) and (3)

The appellant did not dispute that both Huffman coding and arithmetic coding were well known in the field of image compression/coding before the priority date of the application (28 February 2002), and that the following facts were common general knowledge:

Huffman coding and arithmetic coding were the two best-known types of variable-length coding (VLC). VLC mapped source symbols to a variable number of bits. Both Huffman coding and arithmetic coding were commonly used in image data compression. Arithmetic coding almost always resulted in better compression efficiency than Huffman coding (see, for instance, the abstract of D3, and page 857, right-hand column, of D4). Moreover, arithmetic coding had the further advantage over Huffman coding that it could more easily be made adaptive and context-dependent, which further improved the compression efficiency (see, for instance, page 857, right column, and page 858, left column, of D4, section IV on page 136 of D2, and figures 3 to 5 and pages 3 to 5 of the present application as filed). However, arithmetic coding required more computations and was more complex to implement than Huffman coding. As to how the actual coding was performed, it was well known that arithmetic coding differed from Huffman coding in that rather than separating the input into component symbols and replacing each with a code, it encoded the entire message into a single number.

In the method of D7, as explained under points 3.1 and 3.3 supra, eight bit vectors (called "form vectors" in D7) are created for each block of quantised transform coefficients, one for each of the eight zones of the block. Each bit vector comprises eight bits, the value of each bit indicating whether the corresponding quantised transform coefficient in the zone is zero or non-zero. Together, the eight bit vectors of a block thus comprise 64 bits, one for each quantised transform coefficient of the block. These 64 bits thus represent exactly the same information as the bits of the bit vector of claim 1. In D7, each bit vector is variable-length-coded (VLC) with Huffman coding (see page 26, lines 29 to 32).

As mentioned above, it was common general knowledge that arithmetic coding had a number of advantages over Huffman coding, most importantly a better compression efficiency. The board thus concurs with the examining division that these advantages would have given the skilled person a strong incentive to replace Huffman coding with arithmetic coding in D7 in order to achieve a better compression of the bit vectors.

For the skilled person, the most straightforward way of replacing Huffman coding with arithmetic coding in D7 would have been to apply arithmetic coding individually to each bit vector, because each bit vector is individually Huffman-coded.

However, as explained above, it was part of the skilled person's common general knowledge that arithmetic coding differed from Huffman coding in that rather than separating the input into component symbols and replacing each with a code, it encoded the entire message into a single number. In view of this common general knowledge, the board considers that the skilled person would also have regarded it as obviously desirable - because more suited to arithmetic coding - to arithmetically code all eight bit vectors of one block as one sequence of 64 bits instead of as eight component symbols (the eight bit vectors) of eight bits each. This change would have posed no particular technical difficulty to the skilled person.

The skilled person would thus have arrived at distinguishing features (2) and (3) without an inventive step.

6.2 Re distinguishing feature (1)

Distinguishing feature (1) essentially states that all the quantised transform coefficients of a block are mapped (i.e. copied) into a one-dimensional list of quantised transform coefficients in any fixed order. The one-dimensional list is subsequently used for generating the bit vector (see distinguishing feature (2)).

In other words, distinguishing feature (1) effectively states that instead of creating the bit vector directly from the block of quantised transform coefficients, there is an intermediate step of copying these coefficients into a one-dimensional list. The bit vector is then created from this list.

As can be seen from figure 13 of D7, this intermediate step is not necessary because the bit vector can be created directly from the block of quantised transform coefficients by reading the coefficients in the block in the selected scan order.

The application as filed does not mention what advantage or technical effect is achieved by this additional intermediate step.

When asked during the oral proceedings, the appellant explained with reference to figures 7 and 8 that the advantage of creating this list was that the step of creating the bit vector (figure 7) and the step of selecting only the non-zero quantised transformed coefficients for coding (figure 8) could be performed one after the other without having to read twice the quantised transform coefficients from the block.

The board is satisfied that this obvious advantage may indeed exist; it is, however, offset by the equally obvious disadvantage that the additional step of creating the one-dimensional list requires some additional computational time.

The appellant did not dispute that figure 3 of the application as filed showed a prior-art method of coding quantised transform coefficients which comprised exactly this intermediate step of creating a one-dimensional list of quantised transform coefficients (see 304 in figure 3).

In the light of the above, the board considers that distinguishing feature (1) was a known prior-art design option which had obvious pros and cons and which the skilled person would have used in D7 depending on the circumstances and on various obvious design considerations.

Hence the skilled person would have arrived at distinguishing feature (1) without an inventive step.

7. The appellant's arguments

7.1 The appellant's case (summarised under point XIV supra) essentially rests on the argument that the skilled person would not have wanted to replace Huffman coding with arithmetic coding in D7, because the division of blocks into zones was a central teaching of D7. The creation of zones in D7 meant that the expected probability distributions were different for each zone, and Huffman coding could thus be finely tuned to each zone. Because of this synergy between zones and Huffman coding, arithmetic coding would not have provided a better compression efficiency. Moreover, it would have been more complex to implement and would have required more computations.

The appellant also filed an affidavit to prove that the invention had enjoyed considerable commercial success, which had to be viewed as an indication of the presence of an inventive step.

7.2 The appellant's arguments did not convince the board for the reasons presented below.

7.2.1 As explained under point 6.1 supra, it was common general knowledge before the priority date that arithmetic coding had a number of advantages over the older Huffman coding.

A first advantage was that arithmetic coding almost always resulted in better compression efficiency than Huffman coding (see, for instance, "Arithmetic coding results in better compression efficiency than Huffman coding" in the Abstract of D3, and "Arithmetic codes almost always give better compression than prefix codes" on page 857, right column, of D4).

A second advantage was that arithmetic coding could be adaptive, thereby further improving the compression efficiency: see "The main advantages of arithmetic coding for statistical data compression are its optimality and its inherent separation of coding and modeling [...]. The separation of coding and modeling is important because it permits any degree of complexity in the modeler without requiring any change to the coder. In particular, the model structure and probability estimates can change adaptively. (In Huffman coding, by contrast, the probability information must be built into the coding tables, making adaptive coding difficult)", and "The main usefulness of arithmetic coding is in obtaining maximum compression in conjunction with an adaptive model [...]. Arithmetic coding gives optimal compression [...]" in D4, page 864, section "VI. Conclusion", first, second and last paragraphs.

A third advantage was that the compression efficiency could be improved even further by taking account of the context, which would be difficult to do with Huffman coding: see the prior art shown in figure 5 of the present application as filed, and section "IV. ARITHMETIC CODING CONTEXT" on page 136 of D2.

The board considers that in view of these advantages, the skilled person would have had a strong incentive to replace Huffman coding with arithmetic coding in D7, in the expectation that it would improve the compression efficiency.

7.2.2 The appellant submitted that the compression efficiency was already excellent in D7 because Huffman coding used a different probability model for each zone, each finely tuned to the expected probability distribution for the zone.

In the board's view, it is uncertain whether this is true, because the only sentence hinting at this, on page 26, lines 20 to 24 of D7, is rather ambiguous. In any case, even assuming that the appellant is right on this point, Huffman coding in D7 would only be tuned to the expected probability distributions in the various zones, but not to the actual probability distributions in these zones. Indeed, the actual probability distributions depend on the type of images being compressed and may evolve in time. Hence, if not a basic arithmetic coder, at least an adaptive arithmetic coder, which adjusts the probability model to the actual probability distribution of quantised transform coefficients in the block, would have been expected by the skilled person to achieve a better compression efficiency than the zone-based Huffman coding used in D7. It would, of course, have been even more true if the arithmetic coder had been still further improved by also taking the context into account, as was known from common general knowledge.

For the above reasons, the board does not share the appellant's view that the skilled person would have expected no significant improvement in compression efficiency from the use of arithmetic coding in D7.

7.2.3 The appellant also argued that arithmetic coding would not have been used in D7 because it had some drawbacks compared to Huffman coding, namely that it was more complex to implement and would have required more computations.

The board concurs with the appellant that arithmetic coding was more complex to implement than Huffman coding and would have required more computations. This was common general knowledge. However, regarding the complexity, the appellant did not dispute that the skilled person would nevertheless have known how to implement arithmetic coding. Otherwise, the method of claim 1 of the main request would not have met the requirements of sufficiency of disclosure of Article 83 EPC 1973, because the application as filed disclosed few technical details as to how arithmetic coding was to be implemented. Regarding the higher computational requirements of arithmetic coding, the board is of the view that at least in the years before the priority date, electronic circuits were sufficiently fast to perform real-time arithmetic coding on image data, so that it was no longer an important issue which would have dissuaded the skilled person from using arithmetic coding instead of Huffman coding. Documents D2, D3 and D4, all published several years before the priority date, provide evidence of this (see, in particular, D4, page 864, section "VI. Conclusion", last paragraph).

7.2.4 Finally, regarding the affidavit filed by the appellant, the board does not dispute that US and Canadian patents related to the present invention may have had an impressive number of licensees and have generated substantial licence income. It might reasonably be inferred from this that at least some of the claims of these patents covered inventions which enjoyed considerable commercial success.

The appellant attributes the high licence income - and inferred commercial success - to the inventiveness of the subject-matter claimed in those patents.

However, it is established jurisprudence of the boards of appeal that commercial success is only a secondary indication in the assessment of inventive step. Where, as in the present appeal, a technical examination of the claimed subject-matter leads to the reasoned conclusion that the claimed subject-matter does not involve an inventive step, commercial success is generally not a sufficient basis for overturning that conclusion, even if it can convincingly be shown that the commercial success is due to technical features of the claimed subject-matter and not to other factors. See Case Law of the Boards of Appeal of the European Patent Office, 7th edition, 2013, section I.D.10.5, in particular decision T 110/92 cited therein.

8. Conclusion on the main request

For the above reasons, the board considers that the subject-matter of claim 1 according to the main request does not involve an inventive step (Article 56 EPC 1973) in view of D7 and the skilled person's common general knowledge.

Hence the appellant's main request is not allowable.

First and third auxiliary requests - Inventive step (Article 56 EPC 1973)

9. Claim 1 according to the first auxiliary request essentially adds to claim 1 of the main request the feature that the arithmetic coder is adaptive.

Claim 1 according to the third auxiliary request essentially adds to claim 1 of the first auxiliary request the feature that the arithmetic coder comprises coding the bit vector according to a context for the bit vector.

10. As explained under points 7.2.1 and 7.2.2 supra, the skilled person would have wanted arithmetic coding that was adaptive and context-dependent, because it was common general knowledge that the best compression efficiency was obtained with this kind of arithmetic coding.

Hence the subject-matter of claim 1 according to the first and third auxiliary requests does not involve an inventive step (Article 56 EPC 1973) in view of D7 and the skilled person's common general knowledge.

Conclusion

11. Since none of the appellant's requests is allowable, the appeal must be dismissed.