Image Based Velocity Estimation by Feature Extraction and Sub-Pixel Image Matching

Image Based Velocity Estimation by Feature Extraction and Sub-Pixel Image Matching

Nalina S 1, Arindam Mal2, Vani K S3, Subhalakshmi.K4

1,3Acharya Institute of Technology , Department of CS&E, Bangalore.

2,4Scientist at LEOS (ISRO), Peenya 1st stage, 1st cross, Bangalore.

Abstract – Image based techniques are wide area of research in present era. Motion is an integral part of daily visual experience. Velocity estimation of moving object by taking images at different time interval and at different altitude is the goal of this paper. After image acquisition feature extraction and feature matching are applied on captured images. Feature based methods will reduce the complexity of processing, by selecting only some unique feature. In this paper corners are selected as a feature to be extracted. Matching is key step in many applications like image mosaic, image registration, motion estimation etc. All feature based methods have matching point till one-pixel. In this paper a sub-pixel matching is applied using surface fitting equation along with Normalized-cross- correlation (NCC). Feature extraction is done using Kanade- Lucas-Tomasi (KLT) feature extraction method. Surface fitting equation is used to find more accurate feature point. Matching is done using NCC. This method is robust and efficient for velocity estimation.

Keywords: feature based method, Sub-pixel accuracy, Surface fitting equation, NCC.

1. INTRODUCTION

   Feature based methods are used for various applications like template matching, motion detection, image fusion and registration, image mosaic etc. First unique features in the image are to be identified; features can be an Edges, Corners, lines, points etc. Here corner is selected as a feature. A corner can be defined as the intersection of two edges. A corner can also be defined as points for which there are two dominant and different edge directions in a local neighborhood of a point. Image matching methods are classified into area based matching, feature based matching, and intensity based matching. [3] Feature based techniques handle complex image distortions.

   Velocity is estimated by extracting set of features in current image and matching same features in subsequentimage. KLT algorithm [1] is used to extract the features. An integrated feature based method called sub-pixel image matching is use to reach accuracy to sub-pixel, by taking detected feature Points of KLT as window center. Then image matching technique is used to compare the feature Point in the subsequent image which gives accurate displacement. Tracking of feature is one of the important tasks for feature matching. Traditionally, motion as been represented as translation [1].

   Main focus of this paper is to estimate accurate displacement between twoconsecutive images using KLT, NCC and Surface fitting equation [2]. With this method matching accuracy can reach sub-pixel.

   Second section of this paper will give step by step procedure for sub-pixel image matching. Section 2.1 explains basics of image extraction. Section 2.2 gives detailed information of KLT feature extraction method. Section 2.3 contains NCC working and in section2.5 sub-pixel methodology. Section2.4 explains about generating image. Section 3 having results of the methodology used in this paper.

2. RELATED WORK

   Many approaches are used previously to obtain accurate velocity of the helicopter. Landing helicopter safely and precisely on selected location during descent is the present area of research. Towards this end, an inertial navigation technique is used. In 2002 Kalman filter processes linear and rotational velocity in turn reduces convergence time.2013 image based Segmentation is used on sequence of images. By segmenting images in horizontal and vertical directions. In this technique no restriction will be imposed on the camera motion. In 2007 DIMES was developed, which uses homography and feature extraction and matching techniques for velocity estimation.

   In 2013 an optical flow based technique is proposed to estimate angular velocity based on sequences of star-field images. Poisson equation and least-square methods are then used to estimate velocity. The main disadvantage of this technique is noise removal has to be done for both images. This will increase the time complexity of the algorithm. The intensity mean and standard deviation are computed over each image. All pixels with intensity less than noise threshold are discarded. A unit vector based method is also used for velocity estimation. Image based techniques by selecting features are very robust methods and efficient.

3. STEPS FOR VELOCITY ESTIMATION

   1. Feature Extraction

      In the last few years, the increase in digital cameras has led to the development of automatic techniques for feature extraction and matching. In pattern recognition and image processing feature extraction is a special form of

      dimensionality reduction. When the input data to an algorithm is too large to be processed and it is suspected to be notoriously redundant then the input data will be transformed into a reduced representation i.e. set of features (also named features vector). Transforming the input data into the set of features iscalled featureextraction. If the features extracted are carefully chosen it is expected that the features set will extract the relevant information from the input data in order to perform the desired task using this reduced representation instead of the full size input.

      Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. One of corner detection method is KLT.

   2. Kanade-Lucas Tomasi [KLT]Algorithm

      KLT is an automatic detection and tracking algorithm. It makes use of spatial intensity information to direct search that yield best match. This method is developed on idea of local search using gradient weighted by approximation to second derivative of image [6]. It is having 3 steps; (i) calculate structure matrix G and cornerness for each pixel in the image. (ii) Calculate max cornerness max. (iii) Keep all pixels that have cornerness larger than certain percentage (5%-10 %) of max.

      Corners have strong gradients in more than one direction. The computation is based on first partial derivative of image function I (u, v) in horizontal and vertical directions.

      Ix (u, v) = I/x (u, v) and Iy (u, v) =I/y (u, v)

      For each location in image (u, v), we compute 3 values.

      1. First is the square of the partial derivative of image horizontally

         x

         A (u, v) = I 2 (u, v)

      2. Second is square of partial derivative of same image

         I vertically.

         y

         B (u, v) = I 2 (u, v)

      3. Third is product of partial derivative of image in both horizontal and vertical directions

      C (u, v) = Ix (u, v) * Iy (u,

      = max (|1|, |2|)

      Maximum eigenvalue will give the corner point in the image. KLT is scale invariant and rotation invariant.

   3. Image Matching

      Image matching is the fore-step of image registration, automatic change detection, motion detection and image mosaic etc. matching accuracy will impact these applications. Different matching methods are sum-of-square-differences (SSD), sum-of-absolute- differences (SAD) and Normalized-cross-correlation (NCC) etc are used to compare feature points in the template search window.

      The simplest of the similarity measures is SAD, which is calculated by subtracting pixels within a square neighborhoodbetween the reference image I1 and the subsequent image I2 followed by the aggregation of absolute differences within the square window.

      In SSD differences are squared and aggregated within a square window and later optimized by WTA strategy. This measure has a higher computational complexity compared to SAD algorithm as it involves numerous multiplication operations

      The normalized cross-correlation (NCC) [5] is used for image matching to measure the similarity between matching entities in one image and their corresponding entities in the next image. The algorithm was developed based on the concept of distance measure and second, normalized to account for the differences in brightness and contrast. An image I over an area is taken at timet and another image at timet+t. Computation is done by taking a window with feature point as a center of window. Selecting window size is depending on user, larger the window size computation time will be less.

      First Image Second image

      v)

      It can be interpreted as matrix G. The gradient matrix G is given by:

      G=

      G is a scalar matrix, means there exist scalars 1 and 2 and vectors v1 and v2. Such that

      A .vi= i .vi

      Gradient matrix is of the form sparse matrix. Find the largest eigenvalue of the gradient matrix. Power method is used to find largest eigenvalue, expected Eigen-value i

      >=0.

      Figure 1: matching window in target image with respect to reference image

      The NCC is computed by using formula

      The full working of the proposed method is shown in the figure 2. A new approach for sub-pixel accuracy as been proposed in this paper. Selecting search window is also one of the big tasks. After feature extraction to label the feature points a connected component labeling technique is used. All feature based techniques estimate motion by correlation technique.

      By finding maximum of Normalized-cross-correlation (NCC) will get displacement between first and second frame. RANSAC method can be used to remove outliers. SAD and SSD can also give better result. Area based methods also not suitable.

      of this simulated image pair become fraction of size x/N,

      y/N. Simulated image pair is reduced to sub-pixel level if down sampling rate is larger than maximum shift. For his purpose resolution and accuracy were chosen to be 1024 X 1024 and 8 bits per pixel, respectively. Each simulated image size is 256X256 as down sampling is done with factor N=4.

      Simulated images are used to check the correctness of the method which is proposed in this paper

      E. Sub-Pixel Methodology

      For orienting matched points to sub-pixel, the second order polynomial surface fitting equation [2] is used. This gives high accuracy matching.

      Equation is given by

      Z (x, y) = ax2+by2+cxy+dx+ey+f

      Where, Z is corner response value at the position (x, y). a, b, c, d, e and f are constants

      Above given equation can be formed by 9 points in a 3 X 3 window. The window is selected by taking detected interest point as window center.

      Table1: 3X3 corner response window.

      Z1	Z2	Z3
      Z4	Z5	Z6
      Z7	Z8	Z9

      Equation is solved by using planametric separation of g. In this case g=1, the constants can be find by using equations below.

      Fig 2: Flow chart of image matching

   4. Generate Simulated Image by Down Sampling

   Verification of proposed algorithm is done using simulated images created by down sampling. Simulated image pair is created from single high- resolution image by filtering and down sampling [8]. An image is shifted by integer value of x, y and angle theta. Images are down sampled by a factor of N in every dimension. Relative shift

   a = (z1+z3+z4+z6+z7+z9)/6g2- (z2+z5+z8)/3g2 b = (z1+z2+z3+z7+z8+z9)/6g2 (z4+z5+z6)/3g2 c = (z3+z7-z1-z9)/4g2

   d = (z3+z6+z9-z1-z4-z7)/6g e = (z1+z2+z3-z7-z8-z9)/6g

   f = (2(z2+z4+z6+z8) (z1+z3+z7+z9) +5z5)/9

   Calculating the gradients in x and y directions of the quadric surface and form the equation

   z/x = 2ax + c y + d= 0

   z/y = 2by +c x + e = 0

   Then, extreme point at (x, y) is calculated, the precise position of feature point is at (x +x, y +y).

4. RESULTS

   Fig 4(a): Input image

   Fig 4(b): corresponding shifted image

   Fig 4(c ): Result after feature extraction

   Here a subsequent image is generated by giving shift x=5pixel, y=6pixel. Then feature extraction and matching is done using different matching techniques and results are shown in table below.

   SSD and SAD are not good for feature tracking, table above shows that NCC will give more accurate results compare to SSD and SAD. The proposed method is used for velocity estimation of unmanned aerial vehicles. This method will help in pin-point landing of helicopter on plane surface automatically without human intervention. [4].

5. CONCLUSION

In this paper, a sub-pixel image matching is done using surface fitting equation. During feature point extraction KLT algorithm is used along with surface fitting equation for sub-pixel orientation. KLT is invariant to rotation and scaling Normalized cross correlation method is used for matching first image with the second image. It is shown from experimental results that proposed method is robust, effective and suitable for estimating velocity of spacecraft in planetary application. Pin-point landing of the rover on planet can be done by the proposed method.

ACKNOWLEDGEMENT

The authors express their thanks to J.A.Kamalakar Director, Laboratory for Electro-Optics Systems, ISRO for the excellent technical support and suggestions provided during this development activity. The authors also thank Dr. G NagendraRao Deputy Director, SDA, LEOS, for his valuable encouragement and guidance

REFERENCES

1. Shi and C.Tomasi, Good features t track, in proceedings of Computer Vision and Pattern Recognition (CVPR 1994), pp.593-600 (Seattle, USA), June 1994

2. Weill JIAO, Yaling FANG, Guojin HE. An integrated feature based method for sub-pixel image matching. Center for Earth Observation and Digital Earth, Chinese Academy of Sciences, CHINA

3. Zitova, B., Flusser, J., 2003. Image registration methods:a survey,

   Image and vision computing,21, pp.977-1000

4. Larry matthies, Mark Maimone, Andrew Johnson, Yang Cheng, Reg Wilson, Carlos Villalpando, Steve Goldberg, and Andrews Huertas. Computer Vision on Mars. Jet Propulsion Laboratory, California Institute of Technology, USA 2007

5. Misganu Debella-Gilo, Andreas Kääb. Sub-pixel precision image matching for measuring surface displacements on mass movements using normalized cross-correlation .Institute of eco sciences,

   University of Oslo, Norway

6. Harris, C., Stephens, M.., 1988. A combined corner and edge detector. In: fourth Alvey Vision Conference, Manchester, UK, pp.147-151.

7. Xie, D., Zhan, Z., Jiang, W., 2003. Improving harris corner detector. Journal of Geomatics, 28(2), pp.22-23.

8. C. Saravanan, M. Surender. Algorithm for Face Matching Using Normalized Cross-Correlation. International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249 8958, Volume-2,

   Issue-4, April 201

9. Yi-Hsien Lin, Chin-Hsing Chen, Chih-Cheng Wei. New method for subpixel image matching with rotation invariance by combining the parametric template method and the ring projection transform process. National Cheng Kung University Department of Electrical Engineering Tainan, 701, Taiwan, ROC

10. Xie, B., Flusser, J., 2003. Image registration methods: a survey. Image and Vision Computing, 21, PP.977-1000