T 1383/08 () of 11.9.2012

Summary of Facts and Submissions

I. The appeal, filed on 15 May 2008, lies from the decision of the examining division, dispatched on 06 March 2008, to refuse European patent application number 04 023 696.0. The appeal fee was paid on 06 May 2008. The statement setting out the grounds of appeal was filed on 04 July 2008.

II. The following document will be referred to in the present decision:

D1: ONISHI H. et al.: "Detection of rotation and parallel translation using Hough and Fourier transforms"; Proceedings, International Conference on Image Processing IEEE, New York, NY, USA; vol. 3, September 1996, pages 827-830.

III. The examining division refused the application for lack of clarity and lack of inventive step of the independent claims. In a communication issued in preparation of oral proceedings, the Board indicated that it agreed with these findings.

IV. During the oral proceedings before the Board on 11 September 2012, the appellant filed a set of claims intended to overcome the objections of lack of clarity and inventive step.

V. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1-3 and description pages 1-50 filed during the oral proceedings on 11 September 2012 and drawing sheets 1/16-16/16 as originally filed.

VI. Claim 1 reads as follows:

"An image matching method for matching a first image (RIM) and a second image (AIM), comprising the following steps:

performing image conversion processing (161, ST2; ST5) of said first image (RIM) and second image (AIM) according to a Hough transform to generate a first converted image (S1612) and a second converted image (S1611) in the two-dimensional rho-theta space of the Hough transform, whereby the pixels in the first converted image and the second converted image are assigned values representing the number of curves of the Hough transform passing through the respective pixel in rho-theta space;

extracting (162, ST3; ST6) first pixels (S1622) comprising those pixels of the first converted image having values greater than a predetermined threshold value, and extracting second pixels (S1621) comprising those pixels of the second converted image having values greater than the predetermined threshold value;

processing (ST7) the first and second extracted pixels (S1621, S1622) into a first and a second signal (S16311, S16312) by a Fourier transform,

combining (ST8) the first and second signals by multiplying the first signal with the complex conjugate of the second signal,

extracting (ST9) phase information of the combined signal, and

processing (ST10) the phase information by an inverse Fourier transform into a correlation strength image;

calculating (163, ST11) a correlation value from the correlation strength image, and

judging (ST12) whether or not said correlation value is above a certain threshold."

Claim 2 reads "Program adapted to perform the steps of the image matching method of claim 1 when run by an information processing apparatus."

Claim 3 reads "An image matching system comprising means to perform the steps of the image matching method of claim 1."

Reasons for the Decision

1. The appeal is admissible.

2. The invention

2.1 The invention concerns image matching and defines a number of processing steps to be carried out in order to determine a value representing the correlation of first and second images and to judge whether this value exceeds a certain threshold.

2.2 In particular, the image matching method defined in claim 1 involves performing a Hough transform on each of the first and second images so as to generate first and second converted images in the rho-theta space of the Hough transform. The values of each of the pixels in the rho-theta space represent the number of curves of the Hough transform passing though that pixel. In order to reduce the noise resulting from non-linear portions of the images, the pixels having values higher than a predetermined threshold are extracted from the converted images. It is these extracted portions of the images which are then processed further. Both of these first and second extracted portions are subjected to a Fourier transform and the resulting signals are combined by multiplying the first signal with the complex conjugate of the second signal. The phase information of this combined signal is then subjected to an inverse Fourier transform. From the resulting correlation strength image, a correlation value can be calculated which reflects how well-matched the two images are.

2.3 Claims 2 and 3 define a program and system respectively for performing the method of claim 1.

3. Article 123(2) EPC

3.1 The Board is satisfied that the amendments made to the claims and description do not infringe Article 123(2) EPC.

3.2 In particular, the wording of claim 1 reflects the steps performed in the first embodiment of the originally-filed application. The method of this first embodiment is illustrated in Figure 9 and described on pages 23 to 31, additional details of the method being derivable from the explanation of the system illustrated in Figure 6 and described on pages 16 to 21.

In concrete terms, the step of performing image conversion processing in claim 1 is based on the wording of original claim 1, the explicit reference to the Hough transform being derivable from the explanation of the mathematical operation in original claim 1 itself and the reference on page 31, line 16 to the "Huff (sic) conversion" which is described (page 31, lines 24 to page 32, line 16) as being used in both the first and second embodiments of the original disclosure.

The recitation in claim 1 that the pixels in the first and second converted images are assigned values representing the number of curves of the Hough transform passing through the respective pixel does not find a literal basis in the application as originally filed but is nevertheless directly and unambiguously derivable from page 16, lines 4 to 6 which states that "Values in accordance with the degrees of overlapping of patterns of curves are set in pixels in the [converted] images". From this it may be seen that the pixels are assigned values representing the number of curves of the Hough transform passing through the respective pixel: indeed this is the manner in which the results of a Hough transform are depicted.

The extraction step is derived from page 16, lines 14 to 18 which, however, makes reference to the extraction of "a region having a degree of overlapping of patterns of curves ... more than a threshold value set in advance ...". The Board considers that the passage on page 17, lines 5-9, which explains that this extraction is performed in order to eliminate "a noise component different from the linear component", reveals that the term "region" used in the original disclosure is not a region in the conventional sense of a single, closed, spatially-limited portion of the image but instead is intended to refer to the islands of pixels in the image which have values exceeding the threshold value. This finding is corroborated by Figures 5B, 5C, 5E and 5F, from which it may be seen - despite their lack of detail - that the region extraction does not result in the isolation of a single spatial portion of the image. Consequently, the Board considers it is justified to refer to the extraction of "first pixels comprising those pixels ... having values greater than a predetermined threshold value" and "second pixels comprising those pixels ... having values greater than the predetermined threshold value". Furthermore, in view of the fact that the "degrees of overlapping of patterns of curves" are reflected in the pixel values (as discussed in the previous paragraph), the Board considers it justified to define the extraction criterion in terms of pixel values.

The remaining steps concerning the signal processing in the Fourier domain and the subsequent inverse Fourier transform are derivable from page 18, line 24 to page 19, line 7; page 19, line 18 to page 20, line 4; and page 20, lines 19 to 23. The calculation of a correlation value is derivable from page 21, lines 7 to 15 and the step of judging whether the correlation value is above a certain threshold is derivable from page 23, lines 2 to 7.

3.3 Claim 2 relates to a program adapted to perform the steps of the image matching method of claim 1; claim 3 relates to an image matching system comprising means to perform the steps of the image matching method of claim 1. Basis for these claims may be found in original claims 8 and 15 and the passages discussed above with respect to claim 1.

4. Article 84 EPC 1973

4.1 In the contested decision the examining division held that the terms "extracting a first region" and "extracting a second region" in the independent claims were unclear.

As discussed above, the wording of claim 1 has been amended to express what was in fact intended by the term "region". In view of the amendments made to claim 1, the Board considers the claims in their present form to be clear, concise and supported by the description.

5. Articles 52(1), 56 EPC

5.1 The closest prior art is represented by D1. In this document a reference (first) image containing an arbitrary shape is compared to an input (second) image which contains the same shape but in a different orientation to the reference image. The method of D1 determines the amount of relative rotation and parallel translation between the first and second images (see the Abstract).

In this method, the first and second images are each subjected to a Hough transform. This converts the rotation features in the rotated input image into translation features in the rho-theta Hough parameter space. Each of the Hough-transformed images are then subjected to a one-dimensional Fourier transform to provide first and second power spectra in the rho direction for every theta. The normalised cross-correlation coefficients are calculated between the first and second power spectra while shifting the second power spectra in the theta direction. The value of theta giving rise to the maximum cross-correlation coefficient represents the relative rotation between the first and second images.

5.2 The subject-matter of claim 1 is distinguished from that of D1 in that the signals are treated differently once the Fourier transform has been carried out. In particular, instead of calculating the normalised cross-correlation coefficients at every value of theta, the method of claim 1 involves forming the cross power spectrum by multiplying the first signal with the complex conjugate of the second signal and then performing an inverse Fourier transform on the phase information derived from the cross power spectrum to provide a correlation strength image. If the images have some degree of congruence, the correlation strength image will display a distinct sharp peak, the amplitude of which is a direct measure of the degree of congruence.

5.3 Although the cross-correlation method used in D1 enables a conclusion on the congruence of the two images to be reached, the method proposed in claim 1 of the present application provides a clearer and unambiguous representation of the result.

5.4 None of the available prior art citations suggests modifying the method of D1 so as to combine a Hough transform with a phase correlation method as defined in claim 1. In fact, apart from document D1, none of the available prior art documents even discloses the combined use of Hough and Fourier transforms. For this reason, the image matching method defined in claim 1 cannot be considered to be obvious to a person skilled in the art when starting from the disclosure of D1.

5.5 Even if the skilled person were to start from a phase correlation method, which is a known technique for image matching, the available prior art contains no suggestion that a Hough transform could be performed prior to the phase correlation operation. The use of a Hough transform in this context has the advantage that the straight-line portions of the images can be extracted and the phase correlation can be performed using just the extracted image portions to reduce computational load.

5.6 In view of the fact that none of the available prior art citations point to an image matching method involving the combination of a Hough transform operation and a phase correlation operation, neither the image matching method defined in claim 1 nor the program and system defined in claims 2 and 3 respectively can be considered to be obvious to a person skilled in the art.

ORDER

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the examining division with the order to grant a patent in the following version:

- claims 1 to 3 as filed during the oral proceedings of 11 September 2012;

- description pages 1 to 50 filed during the oral proceedings of 11 September 2012;

- drawing sheets 1/16 to 16/16 as originally filed.