OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 15, Iss. 10 — May. 14, 2007
  • pp: 6140–6145
« Show journal navigation

Regularity based descriptor computed from local image oscillations

Leonardo Trujillo, Gustavo Olague, Pierrick Legrand, and Evelyne Lutton  »View Author Affiliations


Optics Express, Vol. 15, Issue 10, pp. 6140-6145 (2007)
http://dx.doi.org/10.1364/OE.15.006140


View Full Text Article

Acrobat PDF (877 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

This work presents a novel local image descriptor based on the concept of pointwise signal regularity. Local image regions are extracted using either an interest point or an interest region detector, and discriminative feature vectors are constructed by uniformly sampling the pointwise Hölderian regularity around each region center. Regularity estimation is performed using local image oscillations, the most straightforward method directly derived from the definition of the Hölder exponent. Furthermore, estimating the Hölder exponent in this manner has proven to be superior, in most cases, when compared to wavelet based estimation as was shown in previous work. Our detector shows invariance to illumination change, JPEG compression, image rotation and scale change. Results show that the proposed descriptor is stable with respect to variations in imaging conditions, and reliable performance metrics prove it to be comparable and in some instances better than SIFT, the state-of-the-art in local descriptors.

© 2007 Optical Society of America

1. Introduction

This paper presents a novel region descriptor based on the concept of Hölderian regularity. By approximating the pointwise Hölder exponent, also known as the Lipschitz exponent, using local signal oscillations around each image point, we are able to construct discriminative feature vectors. Our proposed descriptor is invariant to several types of changes in viewing conditions, exhibiting high and stable performance. As such, the main contribution of this work is that it introduces novel concepts to the field of feature extraction algorithms, using formal mathematical tools and corroborated by high performance on standard tests.

2. Related work

It is not our intention to give a comprehensive summary on the subject of local descriptors, such a discussion can be found in Ref. [5

5. C. Schmid and K. Mikolajczyk, “A performance evaluation of local descriptors,” IEEE Trans. on Patt. Ana. and Mach. Int. 27, 1615–1630 (2005). [CrossRef]

]. Hence, we will only focus on presenting the basic strategies followed by the most common type of region detectors, distribution based descriptors, and discuss the SIFT strategy.

3. Hölder regularity

DEFINITION 1. Let f: ℜ→ℜ, s ∈ ℜ+*\N and x 0 ∈ ℜ. Then, fC s(x 0)⇔∃η ∈ ℜ+*, a polynom P of degree < s and a constant c such that

xBx0η,f(x)P(xx0)cxx0s.
(1)

The pointwise Hölder exponent of f at x 0 is αp = sups {fCs(x 0)} (see Fig. 1).

Fig. 1. Hölderian envelope of signal f at point x0.

3.1. Estimating the Hölder exponent with oscillations

The most natural way to estimate the Hölder exponent, because it follows from its definition, consists in studying the oscillations around each point. This method gives accurate results, better than those obtained using wavelet analysis inmost cases [9

9. P. Legrand, “Debruitage et interpolation par analyse de la regularite Hölderienne. Application a la modelisation du frottement pneumatique-chaussee,” P.h.D. thesis, Université de Nantes (2004).

], hence it will be the technique of choice to compute our proposed descriptor. A brief description of this technique will now be given, for a more detailed analysis please see Ref. [10

10. C. Tricot, Curves and Fractal Dimension (Springer-Verlag1995). [CrossRef]

]. It is pointed out that the Hölder exponent of function f (t) at t is αp ∈ [0,1], if a constant c exists such that ∀ t′ in a vicinity of t,

f(t)f(t)cttαp.
(2)

In terms of signal oscillations, this condition can be written as: a function f(t) is Hölderian with exponent αp ∈ [0,1] at t if ∃c ∀τ such that osc τ (t) ≤ cταp, with

oscτ(t)=supttτf(t)infttτf(t)=supt,t[tτ,t+τ]f(t)f(t).
(3)

An estimation of the regularity will be built at each point by computing the slope of the regression between the logarithm of the oscillation and the logarithm of the dimension of the neighborhood at which one calculates the oscillation. From an algorithmic point of view, it is preferable not to use all sizes of neighborhoods between two values τmin and τmax. Hence, we calculate the oscillation at point t only on intervals of the form [tr : tr], where τr =baser. Here, we use least squares regression, with base = 2 and r = 1,2, … ,7. For a 2D signal, t defines a point in 2D space and τr a radius around t, such that the Euclidian distances d(t′, t) and d(t′′, t) are ≤τr.We can visualize this process in Fig. 2. The method is reliable under three conditions: that αp< 1, the regression converges, and it converges towards a valid slope.

Fig. 2. Estimating the Hölder exponent with oscillations. Left: the region of interest λ, and three of the seven neighborhoods around point t, when r = 1,2, ⋯,7. Center: the neighborhood of radius τ5 = 32 pixels, with base = 2. Right: computing the supremum of the differences within radius τ5, where d denotes the Euclidian distance.

4. Hölder descriptor

Now that we have described a method to accurately characterize the pointwise signal regularity, we can now move on to describe how we use this information to build our local descriptors. The process, described in Fig. 3, is as follows. First, a set Λ of regions of interest are extracted from an image. Second, the dominant gradient orientation ϕλ is computed, this preserves rotation invariance. Finally, our feature vector δλ contains the Hölder exponent αpof the region center and of 128 concentric points, ordered according to ϕλ.

Fig. 3. Descriptor building process. First, a region detector extrats a set Λ of interesting regions. Then, ∀λ ∈ Λ we compute a decriptor δλ . A descriptor contains the Hölder exponent at the region center (x λ, y λ), and of 32 points on the perimeter of four concentric rings, each ring with radii of 14sλ,12sλ,34sλ and s λ respectively.

Region extraction: The first step in the process requires stable detection of salient image regions. The type of regions to be extracted will depend on the requirement of the higher level application with respect to invariance. For instance, an interest point detector will suffice when the scale of the imaged scene is not modified. In our work, we use a detector optimized for geometric stability and global point separability, the IPGP2 detector which is the determinant of the Hessian matrix smoothed by a 2D Gaussian kernel [2

2. L. Trujillo and G. Olague, “Synthesis of interest point detectors through genetic programming, ” in Proceedings from GECCO 2006, Mike Cattolico, eds., Vol.1, (ACM Press2006), pp. 887–894.

, 3

3. L. Trujillo and G. Olague, “Using Evolution to learn how to perform interest point detection,” in Proceedings from ICPR 2006, X.Y. Tang, et al., eds., Vol. 1, (IEEE2006), pp. 211–214.

]. All regions extracted with an interest point detector are assigned the same scale, w λ = 2.5 pixels. For images where scale is a factor, we use the Hessian-Laplace detector presented in Ref. [11

11. K. Mikolajczyk and C. Schmid, “Scale and affine invariant interest point detectors,” Int. J. Comput. Vision 1, 63–86 (2004). [CrossRef]

], which searches for extrema in a linear scale space generated with a Gaussian kernel. After this step we are left with a set Λ of circular regions, the scale is set to s λ = 5 ∙ w λ, and w λ is the scale given by the detector.

Dominant orientation: In order to preserve rotation invariance, the dominant gradient orientation is computed and used as a reference for the subsequent sampling process. For the scale invariant detector, all image regions are normalized to 41×41 bit size using bicubic interpolation. An orientation histogram is constructed using gradient orientations within the interest region, similar to what is described in Ref. [4

4. D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” Int. J. Comput. Vision 2, 91–110 (2004). [CrossRef]

]. The histogram peak is obtained and thus ∀λ∈ Λ a corresponding dominant orientation ϕ λ is assigned. In this way, each region is described by a set λ = {x λ,y λ, s λ, ϕλ}, the region center, scale and orientation of the region.

5. Experimental results

In order to effectively evaluate and compare our results, we use standard image sequences provided by the Visual Geometry Group [12]. From each sequence there is one reference image and a set of test images. Due to prior knowledge of the transformation between the reference and test images, we can quantify a matching score. Sample images and experimental results using the following performance metrics are shown in Fig. 4. We evaluate with threshold based matching, where two image regions λ1 and λ2 are matched if the following relation holds: δ(δλ1, δλ2) < δ. The value of δ is varied to obtain two types of performance curves: one plots Recall versus 1-Precision, characterizing the matching between one test image and the reference image (row 3) [5

5. C. Schmid and K. Mikolajczyk, “A performance evaluation of local descriptors,” IEEE Trans. on Patt. Ana. and Mach. Int. 27, 1615–1630 (2005). [CrossRef]

]; the other, is a double y-axis plot, one axis for average Recall and the other for average 1-Precision, that characterizes the performance of the descriptor on a complete sequence (rows 4 & 5). Recall/1-Precision gives the number of correct and false matches between two images. Recall is the number of correctly matched regions with respect to the number of corresponding regions between two images of the same scene. The number of false matches relative to the total number of matches is represented by 1-Precision. A perfect descriptor would give a Recall equal to 1 for any Precision. Recall and 1-precision are defined as in Ref. [5

5. C. Schmid and K. Mikolajczyk, “A performance evaluation of local descriptors,” IEEE Trans. on Patt. Ana. and Mach. Int. 27, 1615–1630 (2005). [CrossRef]

]: Recall=#correctmatches#correspondences, and 1Precision=#falsematches#correctmatches#falsematches. Note that the second type of plot, includes errorbars to visualize the stability of the descriptor. The performance of our descriptor is compared against SIFT. To compute SIFT descriptors, the Harris and Harris-Laplace detectors were used to extract image regions (executables obtained from Ref. [12]). Figure 4 exhibits the following patterns. Rotation: the Hölder descriptor outper-forms SIFT, with higher Recalland better Precision. Illumination & JPEG : very comparable overall performance. Scale: both exhibit the same performance patterns with SIFT consistently better.

Fig. 4. Columns, left to right: 1) Rotation (36 images in sequence), 2) Illumination change (10 images), 3) JPEG compression (6 images), and 4) Scale change (first 6 images of sequence). Rows, top to bottom: 1) Reference image, 2) Test Image, 3) Performance between test and reference with Hölder in green and SIFT in red, plotting Recall vs. 1-Precision, 4) & 5) Average performance on the complete image sequence for SIFT and Hölder respectively (y-axis with Recallin blue and 1-Precision in green and threshold on x-axis).

6. Conclusions and future work

References and links

1.

H. P. Moravec, “Towards automatic visual obstacle avoidance,” in IJCAI, pp. 584 (1977).

2.

L. Trujillo and G. Olague, “Synthesis of interest point detectors through genetic programming, ” in Proceedings from GECCO 2006, Mike Cattolico, eds., Vol.1, (ACM Press2006), pp. 887–894.

3.

L. Trujillo and G. Olague, “Using Evolution to learn how to perform interest point detection,” in Proceedings from ICPR 2006, X.Y. Tang, et al., eds., Vol. 1, (IEEE2006), pp. 211–214.

4.

D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” Int. J. Comput. Vision 2, 91–110 (2004). [CrossRef]

5.

C. Schmid and K. Mikolajczyk, “A performance evaluation of local descriptors,” IEEE Trans. on Patt. Ana. and Mach. Int. 27, 1615–1630 (2005). [CrossRef]

6.

K. Falconer, Fractal geometry Mathematical Foundations and Applications (Wiley, 1990).

7.

J. Lévy Véhel, “Fractal Approaches in Signal Processing,” Fractals 3, 755–775 (1995). [CrossRef]

8.

P. Legrand and J. Lévy Véhel, “Local regularity-based interpolation,” in WAVELET X, Part of SPIE’s Symposium on Optical Science and Technology, SPIE 5207 (2003).

9.

P. Legrand, “Debruitage et interpolation par analyse de la regularite Hölderienne. Application a la modelisation du frottement pneumatique-chaussee,” P.h.D. thesis, Université de Nantes (2004).

10.

C. Tricot, Curves and Fractal Dimension (Springer-Verlag1995). [CrossRef]

11.

K. Mikolajczyk and C. Schmid, “Scale and affine invariant interest point detectors,” Int. J. Comput. Vision 1, 63–86 (2004). [CrossRef]

12.

Visual Geometry Group: http://www.robots.ox.ac.uk/ vgg/research/

OCIS Codes
(100.5010) Image processing : Pattern recognition
(100.5760) Image processing : Rotation-invariant pattern recognition
(110.2960) Imaging systems : Image analysis

ToC Category:
Image Processing

History
Original Manuscript: September 18, 2006
Revised Manuscript: December 14, 2006
Manuscript Accepted: February 26, 2007
Published: May 3, 2007

Citation
Leonardo Trujillo, Gustavo Olague, Pierrick Legrand, and Evelyne Lutton, "Regularity based descriptor computed from local image oscillations," Opt. Express 15, 6140-6145 (2007)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-10-6140


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. H. P. Moravec, "Towards automatic visual obstacle avoidance," in IJCAI, pp. 584 (1977).
  2. L. Trujillo and G. Olague, "Synthesis of interest point detectors through genetic programming, " in Proceedings from GECCO 2006, M. Cattolico, ed., (ACM Press 2006), Vol. 1, pp. 887-894.
  3. L. Trujillo and G. Olague, "Using Evolution to learn how to perform interest point detection," in Proceedings from ICPR 2006, X.Y. Tang et al., eds., (IEEE 2006), Vol. 1, pp. 211-214.
  4. D. G. Lowe, "Distinctive Image Features from Scale-Invariant Keypoints," Int. J. Comput. Vision 2, 91-110 (2004). [CrossRef]
  5. C. Schmid and K. Mikolajczyk, "A performance evaluation of local descriptors," IEEE Transactions on PatternAnalysis and Machine Intelligence. 27, 1615-1630 (2005). [CrossRef]
  6. K. Falconer, Fractal geometry, Mathematical Foundations and Applications (Wiley, 1990).
  7. J. Lévy Véhel, "Fractal approaches in Signal Processing," Fractals 3, 755-775 (1995). [CrossRef]
  8. P. Legrand and J. Lévy Véhel, "Local regularity-based interpolation," in WAVELET X, Part of SPIE’s Symposium on Optical Science and Technology, SPIE 5207 (2003).
  9. P. Legrand, "Debruitage et interpolation par analyse de la regularite Hölderienne. Application a la modelisation du frottement pneumatique-chaussee," Ph. D. thesis, Université de Nantes (2004).
  10. C. Tricot, Curves and Fractal Dimension (Springer-Verlag 1995). [CrossRef]
  11. K. Mikolajczyk and C. Schmid, "Scale and affine invariant interest point detectors," Int. J. Comput. Vision 1, 63-86 (2004). [CrossRef]
  12. Visual Geometry Group: http://www.robots.ox.ac.uk/ vgg/research/

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1. Fig. 2. Fig. 3.
 
Fig. 4.
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited