T 2025/09 () of 19.4.2013

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the examining division refusing European patent application No. 04 785 030.0.

II. In the decision under appeal, the examining division found, inter alia, that claims 1 and 6 of the main request and of the auxiliary request were not clear within the meaning of Article 84 EPC. Furthermore, the subject-matter of claim 14 of both requests was not new with respect to the following prior art (Article 54 EPC):

D1: Held G.: "Data Compression; Techniques and Applications; Hardware and Software Considerations", Chichester, J. Wiley & Sons, GB, 1983, pages 49 - 51, XP002074977.

III. With the statement of grounds of appeal filed with a letter dated 9 September 2013, the appellant filed a new set of claims 1 to 17 and requested that the decision under appeal be set aside and a patent be granted on the basis of these claims. The appellant essentially argued that D1 did not teach or even suggest second and third codes to perform an encoding which produced lossless data compression, as specified in claim 1. Hence, the claimed method was new over D1 and also involved an inventive step within the meaning of Article 56 EPC.

IV. In a communication dated 4 February 2013 accompanying the summons to oral proceedings, the Board drew the appellant's attention to the following documents:

D2: Michael L. Rhodes et al.: "Locally Optimal Run-Length Compression Applied to CT Images", IEEE Transactions on Medical Imaging, Vol. MI-4, No. 2, June 1985, pages 84 to 90,

D3: US-A-5 521 641.

V. Oral proceedings were held before the Board on 19 April 2013.

VI. The appellant withdrew the main request filed with letter dated 9 September 2009 and requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 17 of the main request filed during the oral proceedings of 19 April 2013.

VII. Claim 1 according to the appellant's request reads as follows:

"A method for performing lossless data compression for an output display device comprising:

comparing the value of a set of data of one or more identical sequential data having said value with a previous value;

encoding the set of data of the one or more identical sequential data with a first code if the difference is outside a predetermined range;

encoding the set of data of the one or more identical sequential data with a second code if the difference is not zero but is within the predetermined range; and

encoding the set of data of the one or more identical sequential data with a third code if the difference is zero,

wherein the first code identifies said value of the set of data of the one or more identical sequential data,

wherein the second code identifies the difference between said value of the set of data of the one or more identical sequential data and said previous value, and indicates, when the set of data comprises at least two identical sequential data, a number of identical sequential data in the set of at least two identical sequential data,

wherein the third code indicates that said value of the set of data of the one or more identical sequential data is identical to said previous value, and

wherein the encoding utilizes the first code, second code and third code to perform the lossless data compression."

Claim 2 to 6 are dependent on claim 1.

Claim 7 reads as follows:

"An apparatus comprising:

a processor (113) to encode an incoming stream of data into a data stream of codes according to the method of one of the claims 1 to 6."

Claims 8 to 13 are dependent on claim 7.

Claim 14 reads as follows:

"An apparatus comprising:

a processor (103) to decode an incoming data stream of codes encoding a stream of data according to the method of one of the claims 1 to 6, in order to generate a binary output from, the data stream of codes including a set of codes that encode the binary output where a first code identifies a literal value to be generated in the binary output, a second code identifies a difference with a previous generated value to generate a set of values in the binary output, a third code identifies a set of matching values with a previous generated value to be generated in the binary output."

Claims 15 to 17 are dependent on claim 14.

VIII. The appellant argued essentially as follows:

Claim 1 related to a method for performing lossless compression of image data which combined three different types of encoding, namely "relative encoding", "category encoding" and "run-length encoding". "Relative encoding" consisted in identifying data values by their differences with respect to a "previous value". "Category encoding" categorized data into three different categories, namely "literal", "match" and "near match", and assigned a specific code format to each category. "Run-length encoding" avoided repetition of identical sequential values. Although similar encoding schemes might be separately known, none of the prior art documents related to a lossless data compression method which combined the different types of encoding specified in claim 1 and which, in particular, univocally specified the conditions the data had to satisfy for the selection of one of the three encoding schemes.

According to claim 1, a data value from a set of data comprising one or more identical sequential data was compared with a previous value. If the difference between the data value and the previous value was outside a predetermined range, "literal encoding" was used to identify the data value (first code). If the difference was not zero, but within a predetermined range, "relative encoding" with respect to a "previous value" was selected (second code). Furthermore, if a data value encoded by relative encoding was followed by one or more identical sequential data, relative encoding was combined with run-length encoding and the resulting code not only identified the difference between the data value and the previous value, but also indicated the number of identical sequential data. Finally, if the difference was zero, run-length encoding was used to indicate the number of identical sequential data.

D2 dealt with the problem of compressing CT images and examined a number of compression schemes which could provide a locally optimum compression format. Although D2 suggested run-length encoding for a set of identical sequential data, the essential teaching of this document was directed to relative encoding. In particular, D2 examined different compression formats based on different ranges of allowed differences between runs of image data and a reference value. None of the relative compression schemes shown in D2 considered the possibility that a set of data to be compressed included at least two identical sequential data whose difference with respect to a reference value fell within a predetermined range. Hence, apart from not offering a clear scheme for categorizing all possible data values of the set of data to be compressed, D2 did not disclose the second code specified in claim 1.

In fact, the application of the differential encoding schemes shown in D2 (defined as absolute difference packing and relative difference packing) to a set of one or more identical sequential data whose difference with respect to a reference value was not zero but within a predetermined range would result in the use of a compression format as shown in Figure 8 of D2, whereby each data value following the reference value was identified by its difference with respect to this reference value. Alternatively, following the teaching of D2 relating to constant runs, the skilled person might choose to encode a sequence of identical data values by a run-length code which identified the value of the identical sequential data and indicated their number.

In particular, the skilled person would not find any incentive in D2 to combine differential encoding and run-length encoding so as to arrive at the second code of claim 1. On the contrary, the teaching of D2 relating to the selection of the optimum compression format among different differential formats would lead the skilled person away from the present invention.

As to D3, this document referred in its introduction to known methods for coding image data based on calculating a difference between input image data and delayed image data to output differential data. In other words, the compression schemes considered in D3 were based on the comparison of an image line with a preceding image line and not of sequential image data with a reference value. Hence, D3 was not relevant to the problem considered in the present application and offered no teaching which could be combined with D2.

In summary, the method according to claim 1 constituted a simple but comprehensive scheme for compressing a set of sequential image data based on the difference between their values and a previous value. As the claimed method was neither known from nor suggested by the prior art, the subject-matter of claim 1 satisfied the requirements of Articles 54 and 56 EPC.

Reasons for the Decision

1. The appeal is admissible.

2.1 Claim 1 according to the appellant's request relates to a "method for performing lossless data compression for an output display device". The compression is carried out on "a set of data" including "one or more identical sequential data" and comprises the step of "comparing" the values of the data in the set with "a previous value".

The gist of the claimed method consists essentially in encoding the "sequential data" in the set according to rules selected on the basis of the difference between the data values and the "previous value".

2.2 In particular, claim 1 specifies the following codes and corresponding encoding rules for the lossless compression of a set of data including one or more identical sequential data:

A) if the difference between a data value and the previous value is outside a "predetermined range", the code ("first code") identifies the data value to be encoded ("first code");

B1) if the difference between a data value and the previous value is within "the predetermined range", but not zero, the code ("second code") identifies that difference;

B2) furthermore, when at least two sequential data are identical and thus have the same difference with respect to the reference value, the code indicates "a number of identical sequential data", namely of sequential data whose values have the same difference with respect to "the previous value";

C) if the difference between a data value and the previous value is zero, the code ("third code") indicates that the value of one or more identical sequential data is identical to the previous value.

2.3 In other words, as pointed out by the appellant, the method of the invention combines three different types of encoding schemes which can be defined as "relative encoding" (differences in value are coded), "category encoding" (different categories of data are identified and corresponding codes applied) and "run-length encoding" (the number of sequential identical values are specified).

3.1 D2 deals with the lossless compression of CT and magnetic resonance image data. As observed in D2 (page 84, right-hand column, first full paragraph), run-length encoding techniques, which consist in storing "runs" of data as a single value and a count rather than the original run, are optimal for digital image files having low standard deviations between pixel values. Although CT and magnetic resonance image data demonstrate a wide variation in pixel values across an entire picture, local subpicture regions show relatively low standard deviation.

According to D2 (page 88, left-hand column, second paragraph), the disclosed "locally optimal run-length coding approach uses a reference pixel value followed by series of small differences. Since differences between one pixel and its neighbor are often small, only a few bits are needed for their representation. For a typical CT image, a large number of pixels can be represented if the range of allowed differences is large". However, large differences need more bits for their representation.

3.2 The compression ratio (CR) is defined in D2 as the ratio between the number of "words used in representation" and the number of "pixels represented". Thus, CR is a number between 0 and 1, where 1 represents no effective compression. The term "run" is used "to denote the set of raster pixels that can be represented by one compression format. Run size is the number of pixels represented" (D2, page 88, paragraph bridging the left-hand and the right-hand columns). In the same paragraph, D2 distinguishes between an "absolute" compression format and a "relative" compression format, whereby the former uses the first pixel in a run as the reference value and the latter uses the prior pixel, in raster sequence, as the reference value.

3.3 Figure 7 of D2 (page 88) shows the percentage of an image that can be represented by "difference runs" using different run-length format compression strategies and run sizes, namely different sets of raster pixels. It is evident that when a pixel in a set cannot be represented by means of the run-length compression strategy selected, its value must be represented "as is" (cf. D2, page 88, right-hand column, penultimate paragraph).

On the other hand, compression "for image areas that hold no information can be represented by the most simple run-length format, that is, a reference value followed by a count that indicates the number of contiguous pixels having the same value" (D2, page 88, right-hand column, lines 23 to 27).

Finally D2 (page 88, right-hand column, lines 27 to 34) considers a compression format for pixel elements which represent textual information and thus can be represented by only two values (On/Off).

3.4 In summary, D2 (page 88, right-hand column, penultimate paragraph) discloses the following compression formats which are relevant to the present application:

i) use pixel as is,

ii) constant run,

iii) relative difference packing (with difference expressed by 4, 5 or 6 bits),

iv) absolute difference packing (with differences expressed by 5 or 6 bits).

3.5 It is evident that the compression format i) is to be used for data values that cannot be expressed by format iii) or format iv), because their difference to the preceding value or to a previous value taken as reference falls outside the interval that can be expressed by 4, 5 or 6 bits. Hence, the compression format i) corresponds to the "first code" specified in claim 1 (see A) in item 2.2 of the decision). It is also evident that format ii) corresponds to the "third code" (see C) above).

If the difference between a data value and the previous value is within a predetermined range, which can be expressed by 4, 5 or 6 bits, D2 teaches to use either the compression format iii) or iv), as specified by the "second code" of claim 1 (see B1) above).

3.6 However, D2 does not explicitly teach what kind of encoding scheme should be used to compress a run of two or more identical sequential data whose difference from the reference value falls within the predetermined range.

4.1 Hence, the method according to claim 1 of the appellant's request differs from the method known from D2 in that it defines an explicit rule for encoding runs of at least two sequential data which are identical and have the same difference with respect to the reference value. As indicated in item 2.2 of the decision (see B2)), this encoding format consists in identifying the difference between the value of the identical sequential data and the reference value (i.e. "the previous value"), and in indicating their number.

4.2 Starting from the teaching of D2, the problem solved by the method of claim 1 can be seen in further optimizing the compression of a run of identical sequential data.

4.3 As pointed out above, D2 (page 88, right-hand column, lines 23 to 27) teaches that a number of contiguous pixels having the same value can be represented by the most simple run-length format, that is, a reference value followed by a count that indicates the number of contiguous pixels having the same value (see item 3.4 of the decision, format ii)).

The appellant has argued that by applying the above compression format ii), the skilled person would start a new run and use the data value, and not the difference between this data value and the "previous value", to identify the following sequence of identical data. As more bits were required to express the absolute value, this would result in an encoding scheme less efficient than the one of the invention.

4.4 The particular case of a set of identical sequential data whose difference from a "previous value" falls within a predetermined interval can be regarded as being covered in D2 by both format ii) and format iii), in the sense that format ii) teaches not to repeat the same data value but to use "a reference value" followed by a count indicating the number of identical data and format iii) teaches to use the difference between a data value and a reference value, i.e. a "previous value" according to the language used in the application, whenever allowed by the available formats, as fewer bits are required to express a difference.

4.5 In light of the underlying teaching of D2, which seeks to find an optimum combination of different compression formats for encoding image data, a person skilled in the art would realize that there was no need to repeat a sequence of identical differential values, generated, for instance, by applying format iii), in order to encode a set of identical sequential data and that in this particular case relative encoding could be advantageously combined with run-length encoding (format ii)).

4.6 In the Board's opinion, the skilled person would find an incentive to combine the formats ii) and iii) taught in D2 in the general advice given in D2 (page 89, left-hand column, first full paragraph) to look for the most efficient compression scheme for a set of pixel data and also in the fact that it was well known before the priority data of the application (see D3, columns 1 and 2, description of the related arts) to code image data by counting up the same values of differential data obtained by comparing image data with delayed image data.

4.7 Hence, it would be obvious to a skilled person, starting from the teaching of D2 and looking for an efficient way for performing lossless compression of a set of data comprising, in particular, a run of identical data whose difference from a previous value was within a predetermined interval, to use as a reference value for the constant run (format ii)) not the absolute value of the identical data but their difference with respect to the previous value, as specified by the coding format iii). In doing so, the skilled person would arrive at a compression method falling within the terms of claim 1.

4.8 In summary, the Board comes to the conclusion that the subject-matter of claim 1 of the appellant's request does not involve an inventive step within the meaning of Article 56 EPC.

5.1 As the method claim according to the main request is not allowable, there is no need to consider the corresponding apparatus claims 7 and 14.

5.2 As the appellant's only request does not provide a basis for granting a patent, the appeal has to be dismissed.

ORDER

For these reasons it is decided that:

The appeal is dismissed.