FR2851066A1 - Points of interest detecting method in digital image, involves detecting points in image at original resolution and when subsampled, comparing points, and storing points of subsampled image not corresponding to points of original image - Google Patents

Abstract

The method involves detecting first points of interest in a digital image at an original resolution and storing first points of interest. The image is then sub-sampled for detecting second points of interest. The first and second points of interest are compared with each other for determining a similarity between the points of interest. Second points of interest not corresponding to first points of interest are then stored. Detection of points of interest is done using precise Harris-type detection, or multiscale-type detection. Independent claims are also included for the following: (a) a device for detecting a point of interest in digital image (b) an apparatus for processing a digital image.

Description

The present invention relates generally to the detection

  points of interest in a digital image.

  A point of interest of an image is a point where the intensity of the image signal varies greatly and has singularities such as corners.

  The document "Comparing and evaluating interest points" by C. 15 Schmid, R. Mohr and C. Bauckhage, in International Conference of Computer Vision, pages 230-235, 1998, presents a comparative study of several point detection techniques interest.

  Points of interest are used, for example, for indexing and searching for images based on content. For this, local image signal characteristics are extracted in the vicinity of the points of interest.

  The images are compared by means of their local characteristics, typically by calculating local distances between the characteristics and by counting the number of paired points, that is to say the points for which the local distance is less than a given threshold.

  Techniques for local image characterization are described in the document "Local grayvalue invariants for image retrieval" by C. Schmid and R. Mohr in IEEE Transactions on Patterns Analysis and Machine Intelligence, Vol. 19, N0 5, pages 530 to 534, 1997, in the document "Use of color for image matching and indexing" by P. 30 Gros et al, INRIA research report, N0 3269 September 1997 and in the document "Object-based queries using color points of interest" by V. Gouet and N. Boujemaa, in Proceedings of the CBAIV conference, 2001.

  In addition, it is common to use the same image at different resolutions. For example, a small image, called a thumbnail, is created from an image to be published via the Internet. This thumbnail is obtained by subsampling the original image.

  It is desirable that the detection of points of interest be robust to an undersampling of the image.

  However, during a change in resolution obtained by digital sub-sampling of the image, high frequencies are created due to the aliasing of the spectrum generated when the Shannon sampling condition 10 is not respected.

  These high frequencies are manifested locally by significant variations in the image signal. These variations are interpreted as points of interest by point of interest detectors.

  Consequently, the points of interest of the image at its original resolution and the points of interest of the image at its lower resolution cannot be paired. The local characterization of the image will not allow the two images to be matched.

  The present invention aims to remedy the drawbacks of the prior art, by providing a method and a device for detecting 20 points of interest in a digital image which provide robust detection at the undersampling of the image.

  To this end, the invention proposes a method for detecting points of interest in a digital image, characterized in that it comprises the steps of: - detection of first points of interest in the image at the resolution of origin, - memorization of the first points of interest detected, - sub-sampling of the image, according to a factor of sub-sampling, - detection of second points of interest in the sub-sampled image, - comparison of the second points of interest with the first points of interest, to determine a correspondence between first and second points of interest, - memorization of second points of interest if they do not correspond to the first points of interest.

  The invention makes it possible to obtain a detection of points of interest in a digital image which is robust to the sub-sampling of the image.

  According to a preferred characteristic, the steps for detecting points of interest implement a precise Harris type detection.

  This type of detection gives good experimental results.

  According to a preferred characteristic, the steps of detecting points of interest implement a multi-scale type detection.

  Thus, the detection of points of interest is also robust to changes of scale, that is to say to optical zoom effects.

  According to a preferred characteristic, the steps of detecting points of interest implement a multi-scale type detection and comprise the detection of a characteristic scale for each point of interest.

  This is an improvement which makes it possible to retain only the points of interest at their characteristic scale, and consequently to reduce the number of points of interest.

  According to a preferred characteristic, the comparison includes a search for a correspondence in position between the first and second points of interest.

  According to a preferred characteristic, the storage of the first and second points of interest comprises the storage of the subsampling factor respectively for each point of interest. Thus, there is an association of each point of interest with the subsampling factor 30 for which the point was detected.

  According to a preferred characteristic, the storage of the first and second points of interest comprises the storage of the characteristic scale for each point of interest. This characteristic is implemented when the detection of the points of interest includes the detection of a characteristic scale for each point.

  According to a preferred characteristic, the comparison also comprises a search for correspondence between the respective products, characteristic scale by sub-sampling factor for the first and second points of interest. Again, this feature is implemented when the detection of points of interest includes the detection of a characteristic scale for each point.

  According to a preferred characteristic, the steps of subsampling, detection of second points of interest, comparison and storage are carried out iteratively a predetermined number of times and for increasing and predetermined subsampling factors, the second points of interest stored at a given iteration being considered as first points of interest for the following iteration.

  Correlatively, the invention relates to a device for detecting points of interest in a digital image, characterized in that it comprises: means for detecting first points of interest in the image at the original resolution, - means for memorizing the detected points of interest, - means for sub-sampling the image, - means for detecting second points of interest in the sub-sampled image, - means for comparing the second points of interest with the first points of interest, to determine a correspondence between first and second points of interest, means for storing second points of interest if they do not correspond to the first points of interest.

  The device according to the invention includes means for implementing the characteristics described above and has advantages similar to those previously presented.

  The invention also relates to a method and a device for local characterization of digital image which implements the characteristics described above. This method and this device have advantages similar to those previously presented.

  The invention also relates to a digital apparatus including the device according to the invention or means for implementing the method according to the invention. The advantages of the digital apparatus are identical to those previously exposed.

  An information storage means, readable by a computer or by a microprocessor, integrated or not in the device, possibly removable, stores a program implementing the method according to the invention.

  A computer program readable by a microprocessor and comprising one or more sequence of instructions is capable of implementing the methods according to the invention.

  The characteristics and advantages of the present invention will appear more clearly on reading a preferred embodiment illustrated by the attached drawings, in which: - Figure 1 shows an embodiment of a device implementing the invention, - figure 2 represents a device for detecting points of interest according to the invention, - figure 3 represents an embodiment of method for detecting points of interest according to the invention, - figure 4 represents an embodiment of a method for updating a list of points of interest according to the invention. According to the embodiment chosen and represented in FIG. 1, a device implementing the invention is for example a microcomputer 10 connected to different peripherals, for example a digital camera 107 (or a scanner, or any means of 'acquisition or image storage) connected to a graphics card and providing information to be processed according to the invention.

  The device 10 includes a communication interface 112 connected 5 to a network 113 capable of transmitting digital data to be processed or, conversely, of transmitting data processed by the device. The device 10 also includes a storage means 108 such as for example a hard disk. It also includes a disc drive 109. This disc 110 can be a floppy disk, a CD-ROM or a DVD-ROM, for example. The disk 110 10 as the disk 108 can contain data processed according to the invention as well as the program or programs implementing the invention which, once read by the device 10, will be stored in the hard disk 108. According to a variant , the program allowing the device to implement the invention can be stored in read-only memory 102 (called ROM in the drawing). In the second variant, the program can be received to be stored in an identical manner to that described previously via the communication network 113.

  The device 10 is connected to a microphone 111. The data to be processed according to the invention will in this case be an audio signal.

  This same device has a screen 104 making it possible to view the data to be processed or to serve as an interface with the user who can thus configure certain processing modes, using the keyboard 114 or any other means (mouse for example) .

  The central unit 100 (called CPU in the drawing) executes the instructions relating to the implementation of the invention, instructions stored in the read-only memory 102 or in the other storage elements. During power-up, the processing programs stored in a non-volatile memory, for example the ROM 102, are transferred to the RAM RAM 103 which will then contain the executable code of the invention as well as registers for storing the variables necessary for the implementation of the invention.

  More generally, an information storage means, readable by a computer or by a microprocessor, integrated or not in the device, possibly removable, stores a program implementing the method according to the invention.

  The communication bus 101 allows communication between the different elements included in the microcomputer 10 or connected to it. The representation of the bus 101 is not limiting and in particular the central unit 100 is capable of communicating instructions to any element of the microcomputer 10 directly or through another element of the microcomputer 10.

  With reference to FIG. 2, an embodiment of device 1 for detecting points of interest in a digital image I according to the invention receives a digital image.

  The device comprises: - means 11 for detecting first points of interest in the image at the original resolution, - means 12 for memorizing the detected points of interest, - means 13 for sub-sampling the image, - means 14 for detecting second points of interest in the subsampled image, - means 15 for comparing second points of interest with the first points of interest, to determine a correspondence between first and second points of interest, means 16 for storing second points of interest if they do not correspond to the first points of interest.

  The device according to the invention comprises means 17 for local characterization of the image. Local characterization is carried out from the list of points of interest determined previously, in a conventional manner which will not be described here.

  These means are implemented in the computer 10 of FIG. 1.

  The operation of the device according to the invention is detailed below.

  FIG. 3 represents an embodiment of a method for detecting points of interest in an image, according to the invention. This method is implemented in the device described above and includes steps E1 to E9.

  The method is carried out in the form of an algorithm which can be stored in whole or in part in any information storage means 10 capable of cooperating with the microprocessor. This storage means can be read by a computer or by a microprocessor. This storage means is integrated or not to the device, and can be removable. For example, it may include a magnetic tape, a floppy disk or a CD-ROM (compact disk with frozen memory).

  Step E1 is an initialization to which a set of K increasing values {S0, Sl, ..., Smax} of sub-sampling factors is defined by a user or automatically. The value So is for example chosen equal to one. The Smax value is chosen equal to the maximum subsampling value that will be applied to the image. This maximum value is for example equal to the size reduction factor when generating a thumbnail from an image for publication on the Internet.

  The sub-sampling factors follow a geometric law.

  The ratio Rs between two successive values of subsampling factors is chosen as a function of the intrinsic maximum robustness of the detection described below. For the so-called "precise Harris" detector which will be used below, the ratio Rs is typically less than two.

  The next step E2 is an initialization at which an integer parameter k is initialized to the value zero. The parameter k represents the index of the sub-sampling factors which will be considered one after the other in the following.

  The next step E3 is the sub-sampling of the image I according to the current sub-sampling factor Sk. Preferably, we choose S0 equal to one, so as to process the image at its original resolution during the first pass (k = 0).

  The result of step E3 is an image Ik sub-sampled with respect to the original image.

  For an initial image of size MxN pixels, the sub-sampled image Ik has a size of M / Sk x N / Sk pixels.

  The next step E4 is a detection of points of interest in the current image lk. One uses for example the detector known as "Harris precise" described in the document "Comparing and evaluating interest points" of C. 10 Schmid, R. Mohr and C. Bauckhage, in International Conference of Computer Vision, pages 230-235, 1998. The result is a set of points Pi, with i integer varying between 1 and an integer Nk. The integer Nk is either predetermined or dependent on the content of the image.

  The point Pi is characterized by its position pi = (xi, yi) in the image.

  According to a first alternative embodiment, the detection is of the multiscale type. This detection is based on a representation of the image obtained by smoothing the image signal by Gaussian nuclei with increasing standard deviation On.

  The detection of points of interest is then carried out at several scale values {a1, ..., amax}. We can choose the same geometric law of variation of scales as for the sub-sampling factors. There is thus the same ratio R8 between two successive values of scales as for the sub-sampling factors.

  According to a second variant, the detection is of the multi-scale type and the points of interest are only retained at their respective characteristic scale.

  This technique is described in the document "Indexing based on scale invariant interest points" by K. Mikolajczyk and C. Schmid, in Proceedings of the ICCV conference, 2001. The characteristic scale of a point of interest Pi is the value d the Cree scale for which a determined function of the image signal takes its maximum value in the direction of the scales. The determined function is for example the Laplacian. We show experimentally that the characteristic scale is characteristic of the local content of the image around the point of interest.

  Experimentally, it is possible to link scale and sub-sampling factor by assuming that the same point of interest detected on a first characteristic scale Cya and for a first sub-sampling factor Sv must be found on a second characteristic scale ib and for a second subsampling factor Sw, such as: /: a. Sv = ab. S, The characteristic scale product by sub-sampling factor is characteristic of the point of interest in the sense of the content of the image.

  A maximum value Pmax can be set for this product. The value Pmax is for example equal to Smax for co = 1. For each value of the sub-sampling factor Sk, the maximum scale value Gymax for the multi-scale analysis is determined by: cmax = Pmax / Sk.

  In other words, the range of scales is normalized by the value of the subsampling factor Sk so as to maintain a constant domain of analysis defined by the product between the maximum scale cimax and the factor of under- Sk sampling. The number of scales 20 and consequently the amount of calculation are thus reduced.

  According to this second variant, the redundancies between points of interest are limited and the number of points of interest retained is lower.

  The next step E5 is a test to determine whether the parameter k is equal to zero. It is thus determined whether this is the first pass for the image being processed.

  If the answer is positive, then step E5 is followed by step E6 at which a list L of points of interest is initialized. The list L comprises the points Pi with the subsampling factor Si = Sk and, where appropriate, with their respective characteristic scale ai.

  If the answer is negative in step E5, then this step is followed by step E7 in which the list L of points of interest is updated. This step is detailed below with reference to FIG. 4. it

  Steps E6 and E7 are followed by step E8 in which the parameter k is incremented by one to consider the next sub-sampling factor.

  The next step E9 is a test to determine whether the parameter k is equal to K, that is to say whether all of the sub-sampling factors have been considered.

  If the answer is negative, then this step is followed by step E3 previously described.

  If the answer is positive in step E9, all the sub-sampling factors have been considered.

  The detection of points of interest is then complete. It is for example followed by a local characterization of the image, carried out from the detected points of interest.

  Step E7 is detailed with reference to FIG. 4 in the form of an algorithm which includes steps E71 to E75.

  We consider here all the points of interest detected in the preceding step E4, for the current sub-sampling factor Sk. There are Nk points of interest to be considered.

  Step E71 is an initialization to which a parameter n is initialized to the value one to consider a first point of interest Pn. We consider a point Pn, with its subsampling factor Sk and possibly with its characteristic scale cyn.

  The next step E72 is a test to determine whether the current point Pn 25 is paired with a point from the list L. The list L contains at this step the points of interest detected at higher resolutions as well as the points of the corresponding resolution to the current sub-sampling factor Sk already processed and added to the list. It is assumed that the list includes N points of interest.

  For this, the position of the current point P, - is compared with the positions 30 of the points of interest in the list L, except for a localization error E. Let (xn, y,) be the coordinates of the point P, in the image at the resolution corresponding to the current sub-sampling factor Sk. We search if there exists a point Pj in an image at a resolution corresponding to a factor of subsampling Sj lower than the current subsampling factor Sk such that: Sk (Xn-ú) <Sj.Xj <Sk (Xn + E) Sk (Yn-E) <Sj.yj <Sk (Yn + F) Furthermore, when the detection of points of interest is of the multiscale type, it is checked that the ratio of the characteristic scale products by subsampling factor is kept to a value K. close, the value K. being close to the value one. We typically choose Ks <Rs.

  When the current point Pn is not paired with a point in the list L, then step E72 is followed by step E73.

  Step E73 is the addition of the current point Pn to the list L. The point of interest Pn, the sub-sampling factor Sn = Sk and if appropriate the characteristic scale an of the point P. are added to the list L. Step E73 is followed by step E74.

  When the response is positive in step E72, this means that there already exists a point in the list L which corresponds to the current point Pr. In this case, step E72 is followed by step E74.

  In step E74, the parameter n is incremented by one to consider a next point of interest.

  The next step E75 is a test to determine whether the parameter n is equal to (Nk + 1). If the answer is negative, then there remains at least one point Pn to be considered and this step is followed by step E72 previously described. When the response is positive in step E75, then all the points Pr detected in the previous passage in step E4 have been processed.

  Of course, the present invention is not limited to the embodiments described and shown, but encompasses, quite the contrary, any variant within the reach of ordinary skill in the art.

  For example, it is possible to use other detectors, such as those mentioned in the document "Comparing and evaluating interest 2851066 13 points" by C. Schmid, R. Mohr and C. Bauckhage, in International Conference of Computer Vision, pages 230-235, 1998.

  In addition, points of interest can be used to perform an image registration.

Claims (23)

  1. A method of detecting points of interest in a digital image, characterized in that it comprises the steps of: - detection (E4) of first points of interest in the image at the original resolution, storage ( E6) of the first points of interest detected, sub-sampling (E3) of the image, according to a subsampling factor, - detection (E4) of second points of interest in the sub-sampled image, - comparison (E7) of second points of interest with the first points of interest, to determine a correspondence between first and second points of interest, - storage (E7) of second points of interest if they do not correspond to the first points of interest. 20 2. Method according to claim 1, characterized in that the steps (E4) of detection of points of interest implement a precise Harris type detection.   3. Method according to claim 1 or 2, characterized in that the steps (E4) of detection of points of interest implement a multi-scale type detection.   4. Method according to claim 1 or 2, characterized in that the steps (E4) of detection of points of interest implement a multi-scale type detection and include the detection of a characteristic scale for each point d 'interest.   5. Method according to any one of claims 1 to 4, characterized in that the comparison step (E7) comprises a search (E72) for positional correspondence between the first and second points of interest.   6. Method according to any one of claims 1 to 5, characterized in that the steps of memorizing the first and second points of interest comprise memorizing the sub-sampling factor 10 respectively for each point of interest.   7. Method according to claim 4, characterized in that the steps of memorizing the first and second points of interest include memorizing the characteristic scale for each point of interest. 15 8. Method according to claim 7, characterized in that the comparison step (E7) further comprises a search (E72) for correspondence between the respective products characteristic scale by sub-sampling factor for the first and second points of interest . 20 9. Method according to any one of claims 1 to 8, characterized in that the steps of sub-sampling (E3), detection of second points of interest (E4), comparison (E7) and storage (E7) are carried out iteratively a predetermined number of times and for increasing and predetermined subsampling factors (Sk), the second points of interest stored in a given iteration being considered as first points of interest in the next iteration.   10. A method of local characterization of a digital image, characterized in that it comprises the method according to any one of claims 1 to 9.   11. Device for detecting points of interest in a digital image, characterized in that it comprises: - means (11) for detecting first points of interest in the image at the original resolution, - means (12) for memorizing the first points of interest detected, - means (13) for sub-sampling the image, according to a subsampling factor, - means (14) for detecting second points of interest interest in the subsampled image, - means (15) for comparing the second points of interest with the first points of interest, to determine a correspondence between first and second points of interest, - means (16) memorization of second points of interest if they do not correspond to the first points of interest.   12. Device according to claim 11, characterized in that the means (11, 14) for detecting points of interest are adapted to implement a precise Harris type detection.   13. Device according to claim 11 or 12, characterized in that the means (11, 14) of detection of points of interest are adapted to implement a multi-scale type detection. 25 14. Device according to claim 11 or 12, characterized in that the means (11, 14) of detection of points of interest are adapted to implement a multi-scale type detection and the detection of a characteristic scale for each point of interest. 30 15. Device according to any one of claims 11 to 14, characterized in that the comparison means (15) are adapted to implement a search for a position match between the first and second points of interest.   16. Device according to any one of claims 11 to 15, 5 characterized in that the means for memorizing the first and second points of interest are adapted to memorize the subsampling factor respectively for each point of interest.   17. Device according to claim 14, characterized in that the means for memorizing the first and second points of interest are adapted to memorize the characteristic scale for each point of interest.   18. Device according to claim 17, characterized in that the comparison means (15) are adapted to further implement a search for correspondence between the respective products characteristic scale by subsampling factor for the first and the second points of interest.   19. Device according to any one of claims 11 to 18, characterized in that the means for sub-sampling, detection of second points of interest, comparison and storage are adapted to operate iteratively a predetermined number of times and for increasing and predetermined subsampling factors (Sk), the second points of interest stored in a given iteration being considered as first 25 points of interest in the next iteration.   20. Device for local characterization of a digital image characterized in that it comprises the device according to any one of claims 11 to 19.   21. Device according to any one of claims 11 to 20, characterized in that the detection, storage, subsampling and comparison means are incorporated in: - a microprocessor (100), - a read only memory (102) comprising a program for processing the data, and - a random access memory (103) comprising registers adapted to record variables modified during the execution of said program.   22. Apparatus for processing (10) a digital image, characterized in that it includes means suitable for implementing the method according to   any one of claims 1 to 10.   23. Apparatus for processing (10) a digital image, characterized in that it comprises the device according to any one of claims 11 to 21.