T 1369/11 (Automatic label placement/MICROSOFT TECHNOLOGY LICENSING) 02-02-2017
Download and more information:
System and method for automatic label placement on charts
I. The applicant (appellant), which at the time was Microsoft Corporation, appealed against the decision of the Examining Division refusing European patent application No. 05105313.0.
II. With effect from 2 February 2015 the EPO registered a transfer of the application to Microsoft Technology Licensing, LLC, which thereby acquired the status of appellant.
III. The decision under appeal cites the following documents:
D1: Edmonson S. et al.: "A General Cartographic Labeling Algorithm", Cartographica, Vol. 33, No. 4, 1997; and
D2: Asman P.: "Creating SVG Pie Charts through XSLT via a Web Service: An Experience Report", SVG Open 2003, 2nd Annual Conference on Scalable Vector Graphics, July 2003.
The Examining Division refused the then main request for lack of inventive step in the subject-matter of independent claims 1 and 13 in view of document D1 and for lack of inventive step in the subject-matter of independent claim 9 in view of a combination of documents D2 and D1.
With respect to the then auxiliary request I, it decided that the subject-matter of independent claims 1 and 11 was not new in view of document D1 and that the subject-matter of claim 8 lacked inventive step in view of a combination of documents D2 and D1. It reached the same conclusion with respect to the then auxiliary request II.
IV. With the notice of appeal and the statement of grounds of appeal, the appellant resubmitted the main request and auxiliary requests I and II considered in the contested decision.
V. In a communication accompanying a summons to oral proceedings, the Board expressed the preliminary view that the subject-matter of claim 1 of each request lacked inventive step in view of document D1 and that claim 1 of auxiliary request I was unclear.
VI. With a letter dated 2 January 2017, the appellant submitted an amended auxiliary request I.
VII. In the course of oral proceedings held on 2 February 2017, the appellant filed an amended auxiliary request II. At the end of the oral proceedings, the chairman pronounced the Board's decision.
VIII. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the main request filed with the notice of appeal or, in the alternative, on the basis of one of auxiliary request I filed with the letter dated 2 February 2017 and auxiliary request II filed in the oral proceedings.
IX. Independent claim 1 of the main request reads as follows:
"A computer-implemented method for automatically positioning labels associated with a visual data object, comprising:
determining a first layout for the labels;
scoring the first layout to determine a first score;
determining a second layout for the labels;
scoring the second layout to determine a second score;
comparing the first score with the second score;
proceeding with one of the first layout and the second layout as a selected layout for rendering the visual data object depending on the comparison of the first score to the second score; and
repeating determining an additional layout for the labels and scoring the additional layout until a layout is achieved that approaches an optimal layout,
wherein labels that are manually positioned are exempt from consideration during the optimization process."
X. Independent claim 1 of auxiliary request I differs from claim 1 of the main request in that the text following "proceeding with ...; and" has been replaced with
"repeating multiple iterations of determining an additional layout for the labels and scoring the additional layout until a layout is achieved that approaches an optimal layout;
wherein determining a second layout for the labels further comprises executing a perturb function, wherein the perturb function alters the first layout according to a set of constraints."
XI. Independent claim of auxiliary request II differs from claim 1 of auxiliary request I in that the following text has been added at the end of the claim:
"; and
wherein the score that is acceptable for a layout to be used depends on a termination condition, wherein the termination condition varies according to time limits for achieving a usable layout."
XII. The appellant's arguments as relevant to the decision are discussed in detail below.
1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.
2. The invention
The invention relates to the automatic positioning of labels associated with a visual data object. A number of possible label layouts are generated, starting with a first and a second layout. The first and second layout are compared on the basis of a "score" calculated for each layout. The layout with the higher score is retained. Additional layouts are generated until a satisfactory layout is achieved (a layout "that approaches an optimal layout").
3. Main request - inventive step
3.1 Document D1 discloses an algorithm for automatic label placement on maps (see abstract) and is therefore a suitable starting point for assessing inventive step for the subject-matter of claim 1. The algorithm can be used to label point, line and area features of a map (abstract and page 2, lines 7 to 11; page numbers refer to the copy of document D1 used by the Examining Division).
3.2 In a first step of the proposed algorithm, a number of candidate label positions are generated for each feature to be labelled (page 3, lines 4 to 6). A "labeling" is a set of label positions, one drawn from each feature's set of candidate positions. Such a "labeling" corresponds to a "layout" within the meaning of claim 1.
3.3 Given a layout or labeling, a score is computed "that indicates its quality with respect both to the position of labels relative to the tagged symbology, and to spatial contention between the label and other features and feature labels" (page 3, lines 7 to 9). These scores correspond to the scores of claim 1.
3.4 Document D1 proposes in section 3 an algorithm that, given a set of generated candidate positions for each label and an overall evaluation function, selects positions for all the labels so that the evaluation function is optimised.
Step 1 of this algorithm selects for each feature a candidate position at random.
Step 2 initialises a "temperature" T to a high value.
Step 3(a) decreases temperature T "according to an annealing schedule".
Step 3(b) randomly selects one of the features and changes the position of its label at random to one of the other candidate positions for the selected feature.
Step 3(c) computes DeltaE, which is the change in the overall evaluation of the layout caused by repositioning the label.
If the new labeling is worse (i.e. DeltaE is negative), then step 3(d) reverts the label repositioning with probability P = 1.0-exp(-DeltaE/T).
Step 3 is repeated until the rate of improvement falls below a given threshold.
3.5 The Board observes that step 1 results in a "first layout" and step 3(b) in a "second layout".
In step 3(c), the DeltaE value can obviously be computed by first calculating the overall evaluation of the first layout to determine a first score and of the second layout to determine a second score and then subtracting one score from the other.
Step 3(d) corresponds to proceeding with one of the first and the second layout depending on a comparison of the first score to the second score.
Repeating step 3 until the rate of improvement falls below a given threshold corresponds to the claimed step of "repeating determining an additional layout for the labels and scoring the additional layout until a layout is achieved that approaches an optimal layout".
3.6 The Board observes that both the application and document D1 in fact disclose the use of what is known as "simulated annealing" for optimising the layout (see Figure 6 and page 21, line 20, to page 22, line 10, of the application as filed and section 3 of document D1).
3.7 The only remaining feature of claim 1 is the feature specifying that labels that "are manually positioned" are "exempt from consideration" during the optimisation process.
The appellant argued that the method of document D1 did not allow for the manual positioning of labels at all. Even if a user were to manually position labels, these labels would then be repositioned during the subsequent optimisation process. That was inconvenient for the user and could impair the readability and visibility of the labels. In addition, computational resources were saved by exempting the manually positioned labels from consideration during the optimisation process.
3.8 According to the Examining Division, the user's wish to exempt manually placed labels from further optimisation was, from a technical point of view, an arbitrary choice. In addition, it was generally known to give a user control over automatic processing, one example being the automatic processing of page breaks in text processing programs in combination with allowing the user to manually insert page breaks.
3.9 The Board agrees with the Examining Division that giving a user control over automatic processes is generally known. And uncontestedly it is known that label placement can be performed both automatically and manually. In the Board's view, there is no inventive step in the idea of splitting this task: first let the user manually place a subset of the labels, then let the computer automatically place the remaining labels. When placing the remaining labels, it is obviously desirable that the manually positioned labels should not be repositioned. Thus, the manually positioned labels have to be "exempted from consideration" during the optimisation process.
The appellant is correct in saying that applying the automated optimisation process to fewer labels requires fewer computational resources, but it is self-evident that reducing the amount of work done also reduces the amount of resources needed. In other words, the reduction in computation achieved is not a surprising technical effect.
3.10 Thus, the subject-matter of claim 1 of the main request lacks inventive step (Article 56 EPC).
4. Auxiliary request I - inventive step
4.1 Apart from a minor rewording ("repeating multiple iterations of determining ..." instead of "repeating determining ..."), claim 1 of auxiliary request I differs from claim 1 of the main request only in that the feature related to manual positioning has been replaced with a feature specifying that determining a second layout involves executing a "perturb function" which "alters the first layout according to a set of constraints". In one embodiment, the perturb function "repositions a single label each time it is called" (page 2, lines 4 to 6, of the application as filed).
4.2 In document D1, the second layout is obtained from the first layout in step 3(b) by randomly selecting one of the features and moving its label to a new position randomly chosen from that feature's set of candidate positions. Thus, step 3(b) discloses a procedure that determines the second layout by "altering the first layout according to a set of constraints", the constraints corresponding to the restriction that each label's position is selected from that label's set of candidate positions.
4.3 The appellant argued that the procedure set out in step 3(b) is not a "function". A function was a mathematical object that mapped an input to an output. The perturb function of the invention did not require the initial generation of a set of candidate positions for each label.
In the Board's view, the term "perturb function" as it is used in the claim is fully defined by the claim itself: it is a computer-implemented "function" or procedure that "alters the first layout according to a set of constraints" (to determine a second layout). The procedure of step 3(b) of document D1, which is also computer-implemented, does exactly that. Therefore, it anticipates the "perturb function" feature added to claim 1.
As to the initial generation of sets of candidate positions in document D1, there is nothing in claim 1 that excludes the presence of such a preparatory step.
4.4 Since the computation of DeltaE disclosed in document D1 does not necessarily - but may obviously - involve separate determinations of the scores of the first and second layouts (see the discussion of step 3(c) in point 3.5 above), the subject-matter of claim 1 of auxiliary request I is new but lacks inventive step (Article 56 EPC).
5. Auxiliary request II - inventive step
5.1 Claim 1 of auxiliary request II adds to claim 1 of auxiliary request I the feature "wherein the score that is acceptable for a layout to be used depends on a termination condition, wherein the termination condition varies according to time limits for achieving a usable layout".
The Board understands this feature as meaning that the termination condition "until a layout is achieved that approaches an optimal layout" involves a time component. Instead of terminating when the rate of improvement falls below a given threshold, as in document D1, the optimisation process stops when a time limit expires.
5.2 It is well known that optimisation processes commonly involve a trade-off between optimisation time used and optimality of the solution. Thus, if the available time is limited, then it is obvious to stop the optimisation process early at the cost of a less optimal solution.
5.3 Hence, the subject-matter of claim 1 of auxiliary request II likewise does not involve an inventive step (Article 56 EPC).
6. Conclusion
Since none of the requests on file is allowable, the appeal is to be dismissed.
For these reasons it is decided that:
The appeal is dismissed.