T 1482/19 (Scale space approximation/TELECOM ITALIA) 11-02-2022

The application

1. The application relates to identifying so-called keypoints in a digital image, for e.g. scene or object identification/matching.

1.1 It builds upon the known method of scale invariant feature detection (SIFT keypoints, see D4, cited in the application on page 2), which detects keypoints as extrema in the image "scale space" (D4, section 3). The image scale space is obtained by convolving (filtering) the original images with a Gaussian function of varying widths; its standard deviation defines the scale dimension of the image "scale space". The extrema are not detected in the scale space itself, but in the LoG space (Laplacian of Gaussian, second derivative with respect to scale), approximated in SIFT feature detection by the difference of two adjacent in a sequence of scale filtered images (difference of Gaussian - DoG, see D4, section 3).

1.2 The application proposes a method of approximating the scale space by a continuous function of scale, determined as a linear combination of filter responses at fixed scales sigma1 ... sigman (basis scales - see equation 1), the combination weights p(sigma) themselves being determined as a polynomial function of scale (equation 8). The determination of the polynomials entails two steps: first the basis scales and a set of scales of interest are selected (page 10, paragraph before equation 5, page 15, 1**(st) paragraph). The combination weights for expressing the filters at the scales of interest as a linear combination of the basis filters can be determined by solving a linear system (equations 4 and 5). Then, polynomials coefficients are determined to best approximate these weights as a function of scale.

1.3 Under this approximation, given an image, the responses to the basis filters are computed and treated as constants. Then, the scale space response can be approximated at each image point as a polynomial (equations 12 and 13). This allows the analytical computation of extrema points by computing the roots of the polynomial (page 16, paragraph 2: first derivative equals 0). The application proposes to select "global" extrema points, also verifying whether the local extrema are extrema in view of the end points of the scale range (page 16).

1.4 The application further proposes (page 17, first full paragraph) to select as keypoints only points in a restricted working range, where the behavior of the approximation function is known.

Rule 139 EPC

2. The Board accepts the request for correction under Rule 139 EPC. The error is obvious, at least because it is not consistent with the description in the paragraph following it, and with other equations, see e.g. equa­tion 11. The correction is unambiguous, as correctly explained by the appellant in its letter dated 4 Febru­ary 2022, and reflects what was originally intended.

The decision under appeal

3. The Examining Division refused the application on three main grounds. The first one (points 1.1 and 1.2), under Article 84 EPC, relates to the definition of the scale space in that the filtering function was not specified to be a LoG or DoG function (feature considered necessary to detect keypoints).

4. The second one (points 1.3 and 3.1) was related to the definition of the approximation function and it was found, essentially, that the application as filed only provides support for an approximation as provided in equation 12, read together with equations 5, 8 and 9 defining the polynomial coefficients and their computa­tion. The claimed generalizations were not allowable under Article 123(2) EPC. Furthermore, the attempts at formulating these equations (in text form) led to lack of clarity and conciseness (Article 84 EPC).

5. The third one was that the claimed subject-matter, even if considering the subject matter to be limited as de­fined in those equations (point 2), was obvious in view of a combination of D1 with D4 (points 2.1 to 2.6).

Admittance (Article 13 RPBA 2020)

6. The current request C - version 3 was filed during oral proceedings before the Board. Though it certainly could, and should, have been filed earlier, it also remedied to all objections brought forward in the preliminary opinion of the Board, by taking guidance on point 23 therein. The Board regards this as sufficient reasons for allowability under Article 13(1) RPBA 2020.

6.1 Regarding Article 13(2) RPBA 2020, the Board finds that exceptional circumstances are established in that a re­quest which is clearly allowable, as is the case here, brings the procedure to an end (see also T 1294/16, points 18.2 and 18.3).

Articles 123(2) EPC and 84 EPC

7. Claim 1 of the only request on file defines, in summary, a method of identifying keypoints in a digital image, comprising:

first claim feature: using an image scale space defined by a LoG or a DoG filter,

claim features a and b: defining, for each pixel, a polynomial approximation of this scale space (reciting equations 12 and 13) in a predefined range of scales, this approximation being obtained in two steps in accordance with equations 5 (approximation of the scale space as a linear combination of the base filters), 8 and 9 (approximation of the weights as polynomial functions of scale) and

last paragraph of claim feature b: identifying candidate keypoints in this scale space as global extremes of the approximation function which are found in a sub-range defined by its lower and upper ends so that the behavior of the approximation function is known in a sufficiently large neighborhood of the extremum

claim features c and d: comparing, for each pixel identified as candidate keypoint, the value of the approximation functions at said extremum with those of neighboring pixels to select the pixel or not.

8. This claim is based on original claim 1 modified in the first claim feature to define the LoG/DoG filters (see e.g. original claim 11), amended in features a and b to define the approximation used in accordance with equations 5, 8, 9, 12, 13, and further amended (last paragraph of feature b) to define the selection of candidate keypoints in a sub-range.

9. The first two amendments remedy the deficiencies noted by the Examining Division in terms of original disclosure, support and clarity (Articles 123(2) and Article 84 EPC).

10. The last amendment is based on page 17, lines 7 to 13, defining the lower and upper ends of the sub-range in respect of the highest and lowest value of the sub-range as follows:

wherein the difference between said lowest value and said lower end, and the difference between said highest value and said upper end, are such that only the maximum or minimum points that happen in sigmam of which the behavior of the approximation function is known in a neighborhood of sigmam that is sufficiently large are considered as candidate keypoints.

10.1 In the Board's view, this formulation follows unam­biguous­ly from the explanation provided in the said passage on page 17 that by restricting the selection to a sub-range, only the extrema that happen in a neigh­bourhood where the behavior of the approximation function are known are considered (in this way...). Though a verb is missing in the sentence on lines 12 and 13, it is clear that the discussion is about which keypoints are to be considered - see the beginning of the paragraph. Thus no objection under Article 123(2) EPC arises.

10.2 Though functional, the definition of the sub-range is clear to the skilled person, who, in the context of the application, is deemed to have expertise in applied mathematics, in particular in approximation functions. Analysing the behavior of polynomial approximations around the interpolating points and on the borders so as to appreciate the validity of the approximation (e.g. estimating the errors' order of magnitude) is a matter of routine in this context. Thus no objection under Article 84 arises either.

Inventive step (Article 56 EPC)

11. The Examining Division rejected the requests underlying their decision for a lack of inventive step starting from D1 in view of D4. These reasons are also pertinent for the current request and are discussed below.

12. Document D1 describes a method of scale space approxi­ma­tion which is the same as that of the application (see D1, equations 5 to 15). This was also stated in the decision at point 2 and was not denied by the appellant.

12.1 The purpose of D1 is (introduction, page 483, paragraph 2) to address the "main problem ... that exhaustive filtering with kernels over a wide range of fine­ly-sampled scales is computationally intensive and inefficient". The proposed method, by the formulation of what are called polynomial steering functions "lends itself well to the detection of global maxima by analytically finding the roots of the derivatives of the po­lynomials, rather than exhaustively performing ope­ra­tions over multiple scales to detect maxima as in the previous aforementioned works" (section 4, paragraph 1).

12.2 D1 uses global maxima over scales (section 4) to detect the scale of image structures in order to improve low-level feature detection and extraction by spatial filters (introduction). It is said though that the other polynomial roots "provide scale information about the other local energy maxima, minima and inflection points" (conclusion, last paragraph).

13. Document D4 represents the seminal work of Lowe regar­ding keypoint detection with scale invariant features. The method starts (section 3) by detecting local ex­trema in (DoG) scale space. These local extrema are obtained by comparing the value of a point with its neighbours both in the scale and the spatial direction (adjacent points - see figure 2). This raises the ques­tion of the sampling frequency in both scale and space domains (section 3.1). D4 uses experimentation in order to determine the frequency of sampling in the scale domain and "must settle for a solution that trades off efficiency with completeness" (end of section 3.1). To reduce computation, D4 further proposes to work on octaves (where the scale doubles), i.e. to repeat the method with the same set of scales, but on reduced versions of the image for each octave (see figure 1).

14. The Examining Division reasoned (2.4) that keypoint detection was a form of low-level feature detection and that it was commonly known to the skilled person that keypoint detection requires the same identification of scale space extrema. So the skilled person would use D1 for keypoint detection.

14.1 The keypoint selection (steps c) and d)) based on the spatial comparison with 8 adjacent points would be done by the skilled person because it was commonly known to do so for keypoint detection (presumably from D4). There was no need to also compare with the neighbours in scale, because the extrema in scale were already determined.

14.2 Accordingly, the Examining Division concluded that all claim features except for the last paragraph in feature b were obvious for the skilled person over the combination of D1 and D4.

14.3 Regarding the last feature - in its previous wording, defining a sub-range separated from the ends of the predefined range by a fixed value of 0.1 - the Examining Division noted (2.4.1 and 2.4.2) that the technical effect of eliminating unstable keypoint candidates was plausible, but could only be understood with hindsight, and could not be based on the corresponding disclosure on page 17. As a consequence, the Examining Division did not accept this feature to have the alleged effect (2.4.3, last sentence).

15. The appellant disagreed with the choice of D1 as star­ting point (see the grounds of appeal, point 1.3.1). There was no mention of keypoint detection in D1, so using D1 for that purpose was not apparent to the skilled person starting from D1. D4 should be taken as the "closest prior art", because it addressed the same problem as the claimed invention, namely keypoint detection.

15.1 Further, the appellant argued (see the grounds of appeal, point 1.3.3) that the skilled person would not have combined D4 with D1, because D1 was about features such as edges and ridges (D1, abstract), whereas D4 stated that edges were not good candidates for inclu­ding keypoints (D4, section 4.1). Moreover, D1 provided a 12th degree polynomial (see, e.g., equation 10), which - although being a polynomial - was clearly too complex to handle for keypoint identifica­tion. Even if the two documents were combined, the combined method would have resulted in computing the approximation of D1 at each considered point in D4 and comparing it with the 9-8-9-neighborhood as per D4 (figure 2).

16. The Board remarks that document D4 is commonly known in the field of image analysis. A person skilled in this art, i.e. the intended addressee of D1, would see that D1, although it mentions edges and ridges, proposes a general method of scale space approximation, which is said to be more computationally efficient than computa­tion by discretization of the scale space. Furthermore, D1 teaches that with this approximation, for each image point, local and global extrema in scale can be compu­ted analytically in an efficient way. So the skilled person would consider employing the method of D1 to improve the commonly known keypoint detection method of D4, which uses the standard scale space discretization.

17. That said, the Board accepts that this way of presen­ting the argument does not follow the established (but not mandatory) problem-solution approach, according to which the starting point would be the prior art to be improved and the objective technical problem to achieve that improvement. One does not, however, come to a different conclusion that way.

17.1 Starting from D4, the skilled person would set out to improve the efficiency of the keypoint detection method, a matter already discussed in D4, section 3.1. In doing that, the skilled person would come across D1 which discloses a solution to this problem. As explained above, even though D1 does not expressly mention keypoints, the skilled person would not have any difficulty in realising that D1 can be employed to increase efficiency of the method of D4.

17.2 Since D1 emphasises the importance of global extrema, the skilled person would also identify, for each considered point, the global extremum among the local extrema.

17.3 Following the D4 structure, this extremum will be com­pared with those of the neighbours. However, using the continuous polynomial scale space approximation of D1, the comparison with the upper and lower 9 scale layer neighbors (figure 2 of D4) has no meaning, as those layers are not defined. But the spatial compa­ri­son with the 8 neighbors, as carried out in D4, remains valid.

18. The appellant also asked the Board to further consider (i) that the invention responded to a long-felt need and was included in the MPEG-7 standard, and (ii) that, although D1 and D4 were published in 2004, no one had the idea the inventors had up until 2013.

18.1 Regarding the first point, the appellant has not elabo­rated on any specific "long-felt need" or demonstrated any failed attempts in the art to address it. For this reason alone, the appellant's argument must fail.

18.2 Regarding the second point, the Board notes that the obviousness of the claimed invention is assessed in an "objective" manner, i.e. irrespective what actually happened, by reference to what a fictitious skilled person "would have done". The Board believes that the link between D4 and D1, provided by the problem of efficiency, would have led the skilled person to con­sider their combination, irrespective of whether that had actually happened in the cited period.

19. Thus the Board agrees in essence with the reasoning of the Examining Division regarding the combination of D1 and D4, though indeed the natural starting point accor­ding to the problem-solution approach is D4 rather than D1, because D4 is improved by D1 and not vice versa. It follows that all the claimed features but the last in feature b are obvious in view of said combination.

20. Regarding this last feature, the Examining Division and the appellant agree that this step solves a technical problem in that it allows to eliminate spurious or unstable candidate keypoints, due to the effects of the approximation.

20.1 The Board also notes that the Examining Division did not find this feature obvious over D1 and D4 but did not accept that the alleged technical effect could be acknowledged based on the application documents as filed.

20.2 The Board accepts this as a legitimate concern but finds to the contrary. The skilled person understands from page 17 that by keeping only the points for which "the behavior of the approximation functions are known in a neighborhood ... that is sufficiently large", the points outside the validity range of the approximation are eliminated, and that these are potentially not true extrema, and hence no real keypoints, but are due to errors in the approximation. Thus the technical problem of eliminating "false" extrema is clear from the application.

21. The Board concludes that claim 1 of the sole request involves an inventive step.

Other issues

22. The Board has no objections as to the content of the dependent claims, or of the description.