Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cmc.msu.ru/pub/2011.ICIAR.Sorokin_Mizotin_Krylov.GaussLaguerreKeypoints.en.pdf Дата изменения: Wed May 18 16:10:00 2011 Дата индексирования: Mon Oct 1 19:42:32 2012 Кодировка:

Gauss-Laguerre Keyp oints Extraction Using Fast Hermite Pro jection Metho d
Dmitry V. Sorokin, Maxim M. Mizotin, and Andrey S. Krylov
Laboratory of Mathematical Methods of Image Processing, Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia {dsorokin, mizotin, kryl}@cs.msu.ru http://imaging.cs.msu.ru

Abstract. Keypoints detection and descriptors construction method based on multiscale Laguerre-Gauss circular harmonic functions expansions is considered. Its efficient acceleration procedure is introduced. Two acceleration ideas are used. The first idea is based on the interconnection between Laguerre-Gauss circular harmonic functions system and 2D Hermite functions system. The further acceleration is based on the original fast Hermite pro jection method. The comparison tests with SIFT algorithm were performed. The proposed method can be additionally enhanced and optimized. Nevertheless even preliminary investigation showed promising results. Keywords: keypoints extraction, Gauss-Laguerre circular harmonic functions, Hermite functions, fast Hermite pro jection method, image matching

1

Intro duction

The images keypoints extraction is one of the basic problems of low level image processing. Keypoints detection and parametrization is the initial step in tasks like stereo matching [1], ob ject recognition [2], video indexing [3], panorama building and others. There are many approaches to the keypoints detection problem such as Harris corner detector [4], DoG approach presented by Lowe [5], the approach based on circular harmonic functions theory [6], [7], etc. The problem of keypoints descriptor construction is also widely presented in literature [4], [5], [8]. The invariance to a class of pro jective and photometric transformations is the target property of the descriptor construction algorithm. This property is crucial to obtain high matching rate across multiple views. As the ma jority of keypoints descriptors construction algorithms are computationally expensive, development of efficient computation algorithms becomes actual. In this paper the keypoints detection and descriptors construction multiscale approach based on Gauss-Laguerre circular harmonic functions [6] is considered. The 2D Hermite pro jection-based fast algorithm for efficient exact keypoints


2

Dmitry Sorokin, Maxim Mizotin, Andrey Krylov

descriptors computation is proposed. The structure of the paper is the following: the first section is devoted to the Gauss-Laguerre keypoints extraction and its Hermite pro jection method acceleration, in the second section the fast Hermite pro jection method is considered and test results are described in the last section.

2
2.1

Gauss-Laguerre Keyp oints
Gauss-Laguerre keyp oints detection

Let us consider a family of complex orthonormal and polar separable functions:
| (r, ; ) = n | (r2 / )e i

.

Their radial profiles are Laguerre functions:
| | n

(x) =

1 n! (n + + 1)

x

/2 -x/2

e

L (x) , n

where n = 0, 1, ...; = 0, ±1, ±2... and L (x) are Laguerre polynomials: n L (x) = (-1)n x- e n
x

d (xn+ e dxn

-x

).

The Laguerre functions n (x) can be calculated using the following recurrence relations:



n+1

(x) =

(x - - 2n - 1 (n + 1)(n + + 1)
n-1

n (x) -

n(n + ) (n + 1)(n + + 1)
0 (x) =

(x) , n = 0, 1, ..., /; ,
-1

1 ( + 1)

x/2 e

-x/2

(x) 0 .

These functions n (x), called Gauss-Laguerre circular harmonic functions (CHFs), are referenced by integers n (referred by radial order) and (referred by angular order). The real parts of n (x) (n = 0, 1, ..., 4; = 1, 2, ..., 5) are illustrated in Fig. 1. The Gauss-Laguerre CHFs are self-steerable, i.e. they can be rotated by the angle using multiplication by the factor ei . They also keep their shape invariant under Fourier transformation. And they are suitable for multiscale and multicomponent image analysis [6], [9]. Let us consider an observed image I (x, y ) defined on the real plane R2 . Due to the orthogonality of n family the image I (x, y ) can be expanded in the analysis point x0 , y0 for fixed in Cartesian system as follows: g,n (x0 , y0 ; )n (, ; ) , =- n=0

I (x0 , y0 ) =


Gauss-Laguerre Keypoints Extraction using Fast Hermite Pro jection Method

3

Fig. 1. The real part of

n

(n = 0, 1, ..., 4; = 1, 2, ..., 5).

where g,n (x0 , y0 ; ) =



I (x0 , y0 )n (, ; )dxdy ,

- -

and = (x - x0 )2 + (y - y0 )2 , = arctan(

y - y0 ). x - x0

Let us consider the keypoints detection algorithm introduced in [6]. Let be the scale parameter and [2-smax , 2smax ] discretized in (2smax + 1) octaves where each octave contains Ns uniformly sampled scales. So the set of scales is defined as {j }, where j = 0, 1, ..., 2Ns (2smax + 1) - 1. Taking into account the Gauss-Laguerre CHFs property of being detectors for some image features (like edges, forks, crosses etc.), n = 0, = 3, 4 that corresponds to forks and crosses are considered. The set of 2Ns (2smax + 1) energy maps is defined as: S (x, y ; ) = |g3,0 (x, y ; )|2 + |g4,0 (x, y ; )|2 , {j } , referred as image scalogram. The scalogram is inspected by 3D sliding window (5 x 5 x 3). The keypoints candidates K = (x, y ; ) are defined as the scalogram local maxima within the window. Here (x, y ) is the keypoint coordinate and is the keypoint reference scale. So the image keypoints set is {K }. This set is reduced by rejecting those keypoints K which have the same position (x, y ) for more than two reference scales. And, finally, the keypoints K with energy value S (x, y ; ) less than a selected threshold are omitted: S (x, y ; ) < T · max(S (x, y ; )) .
x,y

(1)


4

Dmitry Sorokin, Maxim Mizotin, Andrey Krylov

2.2

Gauss-Laguerre Keyp oints Descriptors

The Gauss-Laguerre keypoints descriptors construction algorithm was first proposed in [6]. Each keypoint K = (x, y ; ) is associated to a local descriptor = {(n, , j )}. This is a complex-valued vector consisted of local image pro jections to a set of Gauss-Laguerre CHFs n at 2jmax scales neighbor to the keypoint K reference scale . The elements are defined as: (n, , j ) = n = 0, ..., n
max

g,n (x, y ; j ) · e g,n (x, y ; j ) · e

-i -i

j j

,

, = 1, ..., max , j = -jmax , ..., jmax ,

where j is the j-th scale following if j > 0, or preceding if j < 0 in the discretized scale space. The normalization makes descriptor invariant to the contrast changes. The phase shift e-ij is used to make the descriptors invariant to the keypoint pattern orientation, where j = arg(g1,0 (x, y ; j ) . The matching performance of this technique was demonstrated in [6] in comparison with SIFT algorithm. It was found in [6] that Gauss-Laguerre keypoints extraction method matching results overcome SIFT algorithm results in the case of rotation, scale and translation transformation of images. Nevertheless the computational cost of the algorithm is high. 2.3 Descriptors Computation using 2D Hermite Functions Expansion

The 2D Hermite functions m,n (x, y ; ) form the complete orthonormal system in L2 space and can be defined as: m,n 1 x (x, y ; ) = m
n

y

, n (x) =

(-1)n e

-

· Hn (x) , 2n n !

x2 2

(2)

where n = 0, 1, 2... and Hn (x) are Hermite polynomials: Hn (x) = (-1)n e
x
2

d (e dxn

-x2

).

The Hermite functions n (x) can be calculated using the following recurrence relations: n (x) = x 2 n n
-1

(x) -
-
x2 2

n-1 n

n-2

(x) , n = 2, 3, ...,
-
x2 2

1 0 (x) = e 4

2x , 1 (x) = e 4

.


Gauss-Laguerre Keypoints Extraction using Fast Hermite Pro jection Method

5

The 2D Hermite image I (x, y ) expansion in the analysis point x0 , y0 for fixed can be defined as:


I (x0 , y0 ) =
m=0 n=0

h

m,n

(x0 , y0 ; )m,n (x, y ; ) ,

where


h

m,n

(x0 , y0 ; ) =
- -

I (x0 + x, y0 + y )m,n (x, y ; )dxdy .

(3)

As one can see from (2), m,n (x, y ; ) functions are Cartesian separable, so the computation of (3) can be performed as follows:


hm,n (x0 , y0 ; ) =
-

x I (x0 + x, y )m ( )dx ,

(4)

for every fixed y and after that h 1 (x0 , y0 ; ) =


m,n

h
-

m,n

y (x0 , y0 + y ; )n ( )dy .

(5)

The coefficients of the 2D Hermite and Gauss Laguerre CHFs expansions are block-wise linearly related [10], [11] (the example of connection between GaussLaguerre circular harmonic functions and 2D Hermite functions is illustrated in Fig. 2). So the corresponding coefficients g,n and hm,n of image expansion to the sets of these functions are connected with the same relation. Using the separability of m,n functions and interconnection between m,n and n functions the number of operations for g,n computation can be reduced up to several times. To suppress the descriptor changes due to the brightness changes we introduce the following step. Before expanding the image in keypoint neighborhood into the set of Gauss-Laguerre CHFs the average value of keypoints boundary pixels intensity is subtracted from keypoint neighborhood image intensity values. Further acceleration can be achieved using fast Hermite pro jection method to compute coefficients hm,n and hm,n in 1D expansions (4), (5).

3

Fast Hermite Pro jection Metho d

In common case 1D Hermite pro jection method is defined as:


f (x) =
m=0

cm m (x)


6

Dmitry Sorokin, Maxim Mizotin, Andrey Krylov

Fig. 2. An example of relation between Gauss-Laguerre circular harmonic functions and 2D Hermite functions

where m (x) are 1D Hermite functions, cm are Hermite coefficients:


cm =
-

f (x)m (x)dx .

(6)

Each coefficient in (6) can be rewritten through Hermite polynomials as follows: 2 x2 1 cm = e-x f (x)e 2 Hm (x)dx , m
-

where Hm (x) is Hermite polynomial, m is Hermite normalization constant: m = 2m m! .

This integral can be approximated by Gauss-Hermite quadrature [13]: cm 1 = m


e-
- N

x

2

f (x)e

x2 2

Hm (x)dx
x2 k 2

1 m

A
k=1

k

f (xk )e

Hm (xk ) ,

where xk ­ Hermite polynomials HN (x) zeros, Ak ­ associated weights: 2N -1 N ! Ak = 2 2 . N HN -1 (xk )


Gauss-Laguerre Keypoints Extraction using Fast Hermite Pro jection Method

7

Computation cost and precision loss of these associated weights increase with the increase of N [12]. This problem can be solved by replacement of Hermite polynomials by Hermite functions in (7) [12]. After simplification the following formula can be obtained: cm 1 N
N

µm-1 (xk )f (xk ) , N
k=1

where µm-1 (xk ) is an array of associated constants: N µ
m N -1

(xk ) =

m (xk ) . n -1 (xk ) N

More details on fast Hermite pro jection method can be found in [12]. Keypoints descriptors elements computation can be even more accelerated using fast Hermite pro jection method to calculate hm,n and hm,n in (4) and (5). However fast Hermite Pro jection method is lossy. So this acceleration brings in some error to the Gauss-Laguerre image expansion coefficients g,n and as a consequence keypoints descriptors elements.

4

Results

Proposed keypoints extraction algorithm has been tested on the images selected from the dataset freely available on the web, which provides the image and the relating homographies sequences (http://www.robots.ox.ac.uk/ ~vgg/research/affine/). Typical values of achieved acceleration of initial descriptor construction algorithm are demonstrated in Table 1. The threshold T in keypoints detection (1) was set for each image independently to get about 1000 keypoints per image. The values of descriptors construction parameters were n = 5, = 5, jmax = 2. Fast Hermite pro jection method was applied for keypoints with reference scale > 5. This value was chosen experimentally to get optimal balance between acceleration and approximation errors.
Table 1. Method acceleration results Image 2D Hermite Fast Hermite pro jection Overall name separability acceleration method acceleration acceleration boat1 3.77 1.42 5.36 boat2 3.80 1.45 5.50 boat3 3.82 1.39 5.31 graf1 1.44 3.22 4.67 graf2 1.49 3.25 4.85 graf3 1.49 3.37 5.02


8

Dmitry Sorokin, Maxim Mizotin, Andrey Krylov

The complete comparison of computational cost of proposed acceleration of Gauss-Laguerre descriptors construction algorithm and SIFT descriptors construction algorithm [5] is not given in this paper due to the fact that current implementation of Gauss-Laguerre keypoints descriptors construction algorithm is not optimized. Current implementation of the Gauss-Laguerre algorithm with the fast Hermite pro jection method acceleration is 10.5 times slower than implementation of SIFT which is freely available on the web (http: //www.robots.ox.ac.uk/~vgg/research/affine/). The proposed method was compared in precision-recall [8] with SIFT keypoints descriptors construction algorithm. Descriptors were constructed for the same set of keypoints [5] selected with Gauss-Laguerre keypoints detection algorithm. Threshold T was identical for both pair images and its value was set to get at least 1000 keypoints in both images. The values of Gauss-Laguerre descriptors construction parameters were n = 5, = 5, jmax = 2. Fast Hermite pro jection method was applied for keypoints with reference scale > 5. Different recall values were obtained changing the nearest neighbor distance ratio parameter in descriptors matching procedure proposed by Lowe [5]. Typical results are illustrated in Fig. 3, 4. The proposed method needs additional enhancement and optimization. Nevertheless even preliminary investigation showed promising results. In Fig. 3 the results for graf1-graf2 image pair are given. This pair corresponds to points of view changing transformation. The obtained results show that Gauss-Laguerre descriptors and fast modification of Gauss-Laguerre descriptors perform better matching than SIFT descriptors for the same level of recall. However SIFT descriptors allow to reach the higher level of recall.

1 0.9 0.8 0.7 0.6 0.5 Gauss-Laguerre Fast Gauss-Laguerre SIFT

Recall

0

0.2

0.4 Precision

0.6

0.8

1

Fig. 3. Precision-Recall graph with different descriptors for graf1-graf2 image pair.


Gauss-Laguerre Keypoints Extraction using Fast Hermite Pro jection Method

9

In Fig. 4 the results for boat1-boat2 image pair are given. This pair corresponds to rotation and zoom transformations. The obtained results show that Gauss-Laguerre descriptors performs better matching than SIFT descriptors for some levels of recall, but SIFT descriptors outperforms proposed descriptors in the area of high values of recall. Hermite pro jection based Gauss-Laguerre descriptors demonstrate less level of both recall and precision than SIFT and Gauss-Laguerre descriptors.

1 0.9 0.8 0.7 0.6 0.5 Gauss-Laguerre Fast Gauss-Laguerre SIFT

Recall

0

0.2

0.4 Precision

0.6

0.8

1

Fig. 4. Precision-Recall graph with different descriptors for boat1-boat2 image pair.

5

Conclusion

The efficient computation technique of Gauss-Laguerre keypoints descriptors using both the interconnection between Laguerre-Gauss circular harmonic functions and 2D Hermite functions and fast Hermite pro jection method have been proposed. The preliminary test results look promising. Nevertheless the tests showed that proposed descriptors are not fully invariant to brightness and contrast changes. Future work will include investigation in the field of brightness and contrast invariance of the descriptors and further improvement of GaussLaguerre keypoints detection algorithm.

Acknowledgments. The work was supported by RFBR grant 10-01-00535-a and federal target program "Scientific and scientific-pedagogical personnel of innovative Russia in 2009-2013".


10

Dmitry Sorokin, Maxim Mizotin, Andrey Krylov

References
1. Schaffalitzky, F., Zisserman, A.: Multi-view Matching for Unordered Image Sets. In: ECCV2002. LNCS, vol. 2350, pp. 414­431. Springer, Heidelberg (2002) 2. Tuytelaars, T., Ferrari, V., Van Gool, L.: Simultaneous ob ject recognition and segmentation from single or multiple model views. Int. J. of Computer Vision. 67(2), 159­188 (2006) 3. Morand, Cl., Benois-Pineau, J., Domenger, J.-Ph., Zepeda, J., Kijak, E., Guillemot, Ch.: Scalable ob ject-based video retrieval in HD video databases. J. Signal Processing: Image Communication 25(6), 450­465 (2010) 4. Harris, C. G., Stephens, M.: A combined corner and edge detector. In: 4th Alvey Vision Conf. Manchester, pp. 147­151. (1988) 5. Lowe, D.: Distinctive image features from scale-invariant keypoints. Int. J. of Computer Vision 60(2), 91­110 (2004) 6. Sorgi, L., Cimminiello, N., Neri, A.: Keypoints Selection in the Gauss Laguerre Transformed Domain. In: BMVC06. pp. 133­142. (2006) 7. Hse, H., Newton, A.R.: Sketched symbol recognition using zernike moments. In: ICPR04, pp. 367­370. (2004) 8. Mikola jczyk, K., Schmid, C.: A performance evaluation of local descriptors. IEEE Trans. On PAMI 27(10), 1615­1630 (2005) 9. Jacovitti, G., Neri, A.: Multiresolution circular harmonic decomposition. IEEE Trans. Signal Processing 48(11), 3243-3247 (2000) 10. Zauderer, E.: Complex argument Hermite-Gaussian and Laguerre-Gaussian beams. J. Opt. Soc. Amer. A. 3(4), 465­469. (1986) 11. Di Claudio, E. D., Jacovitti, G., Laurenti, A.: Maximum Likelihood Orientation Estimation of 1-D Patterns in Laguerre-Gauss Subspaces. IEEE Tran. Image Processing 19(5), 1113­1125 (2010) 12. Krylov, A., Korchagin, D.: Fast Hermite Pro jection Method. In: ICIAR 2006, LNCS, vol. 4141, pp. 329­338. Springer, Heidelberg (2006) 13. Krylov, V.I.: Approximate Calculation of Integrals. Macmillan Press, New York (1962)