 Open Access
 Total Downloads : 441
 Authors : Nalina S, Arindam Mal, Vani K S, Subhalakshmi.K
 Paper ID : IJERTV3IS080540
 Volume & Issue : Volume 03, Issue 08 (August 2014)
 Published (First Online): 06092014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Image Based Velocity Estimation by Feature Extraction and SubPixel Image Matching
[IBVEFS]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 onepixel. In this paper a subpixel matching is applied using surface fitting equation along with Normalizedcross correlation (NCC). Feature extraction is done using Kanade LucasTomasi (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, Subpixel accuracy, Surface fitting equation, NCC.

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 subpixel image matching is use to reach accuracy to subpixel, 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 subpixel.
Second section of this paper will give step by step procedure for subpixel 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 subpixel methodology. Section2.4 explains about generating image. Section 3 having results of the methodology used in this paper.

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 starfield images. Poisson equation and leastsquare 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.

STEPS FOR VELOCITY ESTIMATION

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.

KanadeLucas 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.

First is the square of the partial derivative of image horizontally
x
A (u, v) = I 2 (u, v)

Second is square of partial derivative of same image
I vertically.
y
B (u, v) = I 2 (u, v)

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.


Image Matching
Image matching is the forestep of image registration, automatic change detection, motion detection and image mosaic etc. matching accuracy will impact these applications. Different matching methods are sumofsquaredifferences (SSD), sumofabsolute differences (SAD) and Normalizedcrosscorrelation (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 crosscorrelation (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 Eigenvalue 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 subpixel 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 Normalizedcrosscorrelation (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 subpixel 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. SubPixel Methodology
For orienting matched points to subpixel, 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

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+z7z1z9)/4g2
d = (z3+z6+z9z1z4z7)/6g e = (z1+z2+z3z7z8z9)/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).


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 pinpoint landing of helicopter on plane surface automatically without human intervention. [4].

CONCLUSION
In this paper, a subpixel image matching is done using surface fitting equation. During feature point extraction KLT algorithm is used along with surface fitting equation for subpixel 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. Pinpoint 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 ElectroOptics 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

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

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

Zitova, B., Flusser, J., 2003. Image registration methods:a survey,
Image and vision computing,21, pp.9771000

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

Misganu DebellaGilo, Andreas KÃ¤Ã¤b. Subpixel precision image matching for measuring surface displacements on mass movements using normalized crosscorrelation .Institute of eco sciences,
University of Oslo, Norway

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

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

C. Saravanan, M. Surender. Algorithm for Face Matching Using Normalized CrossCorrelation. International Journal of Engineering and Advanced Technology (IJEAT) ISSN: 2249 8958, Volume2,
Issue4, April 201

YiHsien Lin, ChinHsing Chen, ChihCheng 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

Xie, B., Flusser, J., 2003. Image registration methods: a survey. Image and Vision Computing, 21, PP.9771000