T 1148/05 (Image classification / STMICROELECTRONICS) 27-05-2009
Download and more information:
Content-based digital-image classification method
Admissible amendment - yes
Enabling disclosure - yes
Inventive step - no
I. This appeal is against the decision of the examining division to refuse European patent application No. 00830029.5. The application is entitled "Content-based digital-image classification method" and has been published as
A1: EP-A1-1 102 180.
The refusal was based on Article 123(2) EPC 1973 as the examining division saw no direct and unambiguous basis for the expression "wherein said set of low-level features includes at least some of the following low-level features" in the amended claim 1 underlying their decision.
The examining division added a comment which amounts to an objection under Article 83 EPC 1973:
"the application as a whole fails to teach how to choose the set of features to use for building a tree-classifier specifically adapted to a given classification problem."
II. In the statement setting out the grounds of appeal, the appellant requested that the decision under appeal be set aside and a patent be granted on the basis of an amended set of claims 1 to 6. Oral proceedings were requested on an auxiliary basis.
Claim 1 reads as follows:
"1. Content-based image classification method for classifying digital images into the following classes: photographs, texts, and graphics; the method comprising:
- constructing a tree classifier from a set of training images each belonging to one of the classes involved in the classification, by using the Cart methodology and a set of low-level features describing the semantic content of images in the classes involved in the classification, said low-level features being quantities obtainable from the images by means of logico-mathematical expressions that are known beforehand, and
- classifying digital images in the classes involved in the classification by using said tree classifier;
wherein said set of low-level features includes the following low-level features:
a) the colour histogram in the 64-colour quantized HSV colour space;
b) the colour coherence vectors in the 64-colour quantized HSV colour space;
c) the 11-colour quantized colour transition histogram in the HSV colour space;
d) the moments of inertia of colour distribution in the non-quantized HSV colour space;
e) the moments of inertia and the kurtosis of the luminance of the image;
f) the percentage of non-coloured pixels in the image;
g) the number of colours of the image in the 64-colour quantized HSV colour space;
h) the statistical information on the edges of the image extracted by means of Canny's algorithm; in particular:
h1) the percentage of low, medium and high contrast edge pixels in the image;
h2) the parametric thresholds on the gradient strength corresponding to medium and high-contrast edges;
h3) the number of connected regions identified by closed high-contrast contours; and
h4) the percentage of medium-contrast edge pixels connected to high-contrast edges;
i) the histogram of the directions of the edges extracted by means of the Canny's edge detector;
j) the mean value and the variance of the absolute values of the coefficients of the subimages of the first three levels of the multi-resolution Daubechies wavelet transform of the luminance of the image;
k) the estimation of the texture characteristics of the image based on the neighbourhood grey-tone difference matrix (NGTDM), in particular coarseness, contrast, busyness, complexity, and strength;
1) the spatial-chromatic histogram of the colour regions identified by means of the 11-colour quantization process in the HSV colour space, and
in particular:
l1) the co-ordinates of the centroid of the colours; and
l2) the dispersion of the colour regions with respect to their centroids;
m) the spatial composition of the colour regions identified by means of the 11-colour quantization process, and in particular:
ml) fragmentation;
m2) distribution of the colour regions with respect to the centre of the image; and
m3) distribution of the colour regions with respect to the x-axis and with respect to the y-axis."
III. Having deleted the criticised expression "at least some of", the appellant argues that the amended claim 1 overcomes the objections under Articles 123(2) and 83 EPC 1973: since the whole library of image features is used to build the feature vector, the skilled person does not have to select any (potentially undisclosed) sub-combination of features.
The appellant submits that a combination of three features distinguishes the invention over all the prior art references cited by the examining division:
- the classes (photographs, texts, graphics) into which the images are to be classified;
- the methodology (Cart) used to construct the tree classifier, and
- the low-level image features suitable for discriminating those particular classes.
IV. The Board summoned the appellant to oral proceedings. In an annex to the summons, the Board expressed and substantiated serious doubts inter alia about the presence of an inventive technical contribution in the classification method of claim 1.
V. In response to the summons, the appellant withdrew its request for oral proceedings and announced that it would not attend the oral proceedings scheduled for 26 June 2009. In a telephone conversation with the Board's registrar on 13 May 2009, the appellant stated that it wished a decision according to the state of the file.
VI. Consequently, the Board cancelled the summons.
1. The application
1.1 Conventional heuristic methods implemented by expert systems (A1, paragraph 0006) present a number of drawbacks, in particular the computational complexity required for analysing the large number of pixels of an image (paragraph 0007). Another problem is touched on by the "impossibility of optimising analysis using parallel architectures" (A1, column 2, lines 10 to 12).
The invention aims to avoid those drawbacks (paragraph 0008).
1.2 The thrust of the application is for constructing a classification algorithm ("tree-structured classifier") which is both powerful in terms of class discrimination and efficient in terms of processing speed (paragraph 0014). The application lists a library of "low-level features" (paragraphs 0015/0016) from among which a vector of N features is chosen to build a binary tree classifier. Regions of the feature vector space are assigned to respective image classes (paragraph 0018).
According to paragraph 0056 of the application, its classification method "lends itself to an implementation through parallel architectural structures" (although no such architecture is set out).
1.3 The classification according to the claimed method requires a "much smaller exploit ation of computational resources" because "the only real computational effort is represented by the construction of the tree-structured classifier" which occurs only once before the classifier is used in regular practice (paragraph 0055). The classification algorithm is presented as reliable (paragraphs 0051 and 0053), "highly optimizable and modular" and "robust" (paragraph 0056).
2. Article 123(2) EPC - Admissibility of amended claim 1
The amended claim 1 sets out from claim 1 as filed, specifies the three image classes mentioned in paragraphs 0002 and 0046 of A1, incorporates the list of low-level features disclosed in paragraph 0015 (and original claim 2) of A1, and adopts the Cart methodology [Classification and regression trees] for building a tree classifier as emphasised in paragraphs 0019/0020/0021 and 0044 (and claim 5) of A1.
Therefore, the Board is satisfied that the subject-matter of claim 1 is within the content of the application as filed.
3. Article 83 EPC 1973 - Enabling disclosure
3.1 In the Board's judgment, the skilled person has no difficulty using all of the listed low-level features to construct a tree classifier according to the procedure and conditions set out in paragraphs 0017 to 0045 of A1, in particular when relying on the "known Cart methodology" (paragraphs 0019...0021). The total number of features may be considerable (e.g. 389 or 72, see paragraphs 0016 and 0052) but it is evident that
- not all conceivable features need to be used, and
- the reliability and resolution (and computational cost) of a classification algorithm will generally increase with the number of features which are taken into account.
3.2 The examining division has argued that the application does not disclose any specific example of a tree classifier adapted to a specific set of image classes. However, the application does disclose the "high-level classification problem" now addressed by the claim (i.e. to distinguish photographs from graphics and texts, see paragraphs 0002 and 0046) and it discloses that 72 low-level features have been chosen (from among 389 features, for example, see paragraphs 0016 and 0052) to carry out the test described in paragraphs 0047 to 0053. The background of that choice may lack detail but it still provides the general teaching that a (sub-)set of low-level features can be chosen according to general criteria (discrimination power and efficiency, column 3, lines 22 to 25) and managed in any combination (paragraph 0020) to build a classifier fulfilling a set of conditions (see e.g. paragraphs 0021/0022, 0039, 0042).
4. Article 84 EPC 1973 - Support by the description
Article 52(2)(3) EPC - Technical character
4.1 A question is whether claim 1 is supported by the description in that the claim does not explicitly refer to computing means. Computing means are essential for processing the volume of image features. The application confirms that even its improved method still exploits "computational resources", and the construction of the tree-structured classifier represents a "computational effort" (paragraph 0055). This effort is indeed plausible in view of the high number of image features (paragraph 0016: "389"; paragraph 0052: "72") and images to be processed (e.g. 4500, see paragraphs 0048 to 0052). Therefore, "computational resources" have to be present in claim 1 as an essential feature of the disclosed method (T 914/02, point 2.3.4) to ensure that the images are classified rapidly by digital processing (see A1, column 3, line 25).
4.2 However, even if this requirement is considered to be met because the term "digital images" may imply digital processing of the features expressing image properties and of the vectors representing image classes, and all features are assumed to contribute to the technical character of the claimed subject matter, the method does not involve an inventive step for the reasons set out below.
5. Article 56 EPC 1973 - Inventive step
5.1 Regarding relevant prior art, the application refers to extensive non-patent literature, notably in relation to its library of low-level features, and emphasises that it relies on the known "Cart" methodology (paragraphs 0019...0021, 0044; original claim 5).
The decision under appeal mentions the following documents:
D1: Giesen, R.J.B. et al., "Construction and application of hierarchical decision tree for classification of ultrasonographic prostate images", Medical and Biological Engineering & Computing, vol. 34, no. 2, 1 March 1996, ISSN 0140-0118; pages 105 to 109, XP000558404.
D2: Athitsos, V. et al., "Distinguishing Photographs and Graphics on the World Wide Web", Proceedings IEEE Workshop on Content-Based Access of Image and Video Libraries, San Juan, Puerto Rico, 20 June 1997; IEEE Computer Society, Los Alamitos, CA (US); pages 10 to 17, XP010252098.
D3: Vailaya, A. et al., "On Image Classification: City vs. Landscape", Proceedings IEEE Workshop on Content-Based Access of Image and Video Libraries, Santa Barbara, CA (US), 21 June 1998; IEEE Computer Society, Los Alamitos, CA (US); pages 3 to 8, XP010293880.
D4: Amit, Y. et al., "Randomized Inquiries About Shape; an Application to Handwritten Digit Recognition", Technical Report Number 401, Department of Statistics, University of Chicago, Chicago, IL (US), November 1994, pages 1 to 27.
5.2 The general aspects of processing and pre-classifying digital images are old, see e.g. D2 (Abstract). However, the claimed method derives novelty from the use of a large library of 22 specific technical image parameters (low-level features "a" to "m3") which are not disclosed in combination in any of the available prior art documents.
5.3 Article 56 EPC 1973 asks for an inventive technical contribution (T 641/00-Two identities/COMVIK, OJ EPO 2003, 352, Headnote I). The following line of argument guides the skilled person in an obvious manner from the prior art to the claimed method.
5.3.1 As acknowledged in the opening portion of the application (paragraph 0005), a classification of digital images for the adoption of the most suitable image-processing strategies has become "an indispensable need".
5.3.2 Even if the skilled person were not aware of the sub-classes mentioned in the present application (paragraphs 0003 and 0049), he would be expected to anticipate the need for at least a high-level or pre-classification into basic types of images. According to D2 (Abstract), which may be used as a starting point, Web images are classified into photographs and graphics. It is self-evident that these image classes have to be kept separate from texts.
5.3.3 In digital image processing, it is well-known (and inevitable) to construct a classification algorithm before it is used for classifying images, see e.g. D1 (page 109, left-hand column, paragraph 3, summary); D2, sections 5.2 and 5.3; D4 (page 15, section 4.7).
When constructing an algorithm for classifying digital images, it is well-known to accomplish this by way of a tree classifier using features or parameters which describe a digital image, see e.g. the prior art referred to in the application itself (A1, paragraph 0019: Cart methodology); or D1 which deals entirely with the construction of binary decision trees; D2, section 5.2; D3, page 4, second paragraph ("two-class classification"); D4, chapter 3.
5.3.4 Hence, the invention mainly differs from prior art classification methods, as described e.g. in D2, by the library of specific low-level features for improving the classification result.
However, it is evident that all the image features which are known to describe properties of digital images are natural candidates for distinguishing images, and classes of images, from each other. The skilled person has an expectation of improvement in that any low-level feature is prima facie suitable for discriminating image classes at least at a high level. The skilled person designing a binary classification tree obviously prefers features having a great power of discriminating two classes (see e.g. D3, page 4, second paragraph).
The application itself presents most of its low-level features as forming part of the prior art (A1, paragraph 0015). Regarding the few features for which no prior art has been cited in the application, the application still conveys the impression that those features represent usual parameters for describing and analysing digital images. Otherwise, if they were fundamentally new to the image processing person, they would have to be disclosed in much greater detail.
5.4 Therefore, the Board judges that the method of claim 1 does not involve an inventive step (Article 56 EPC 1973).
ORDER
For these reasons, it is decided that:
The appeal is dismissed.