[PDF] Video Object Tracking using SIFT and Mean Shift

View - Download Video Object Tracking using SIFT and Mean Shift

Previous PDF

Next PDF

Video Object Tracking using SIFT and Mean Shift

Master Thesis in Communication Engineering

ZHU CHAOYANG

Department of Signals and Systems

Signal Processing Group

CHALMERS UNIVERSITY OF TECHNOLOGY

Report No. Ex005/2011

Thesis for degree of Master of Science

Video Object Tracking using SIFT and Mean Shift

Chaoyang Zhu

Supervisor and Examinor: Professor Irene Gu

Department of Signal and System, Signal Processing Group, Chalmers University of Technology (CTH), Sweden (Report: Ex005/2011)

Gothenburg, 2011

I

Abstract

Visual object tracking for surveillance applications is an important task in computer vision. Many algorithms and technologies have been developed to automatically monitor pedestrians, traffic or other moving objects. One main difficulty in object tracking, among many others, is to choose suitable features and models for recognizing and tracking the target. Some common choices of features to characterize visual objects are: color, intensity, shape and feature points. In this thesis three methods are studied: mean shift tracking based on the color pdf, optical flow tracking based on the intensity and motion, SIFT and RANSAC tracking based on scale invariant local feature points. Mean shift is then combined with local feature points. Preliminary results from experiments have shown that the adopted method is able to track target with translation, rotation, partial occlusion and deformation. II

Table of Contents

Abstract .............................................................................................................................. I

Table of Contents ............................................................................................................. II

Chapter 1. Introduction ..................................................................................................... 1

1.1 Concept of visual object tracking ....................................................................... 1

1.2 Applications of visual object tracking ................................................................ 2

1.3 Difficulties and algorithms ................................................................................. 2

1.4 The structure of this thesis .................................................................................. 3

Chapter 2. Feature Extraction Methods ............................................................................ 4

2.1 SIFT method ....................................................................................................... 4

2.1.1 Concept and features of SIFT .................................................................. 4

2.1.2 Scale-space extrema detection ................................................................. 5

2.1.3 Locating keypoints .................................................................................. 7

2.1.4 SIFT feature representation ..................................................................... 9

2.1.5 Orientation assignment ............................................................................ 9

2.1.6 Keypoint matching ................................................................................ 10

2.2 RANSAC method ............................................................................................. 11

2.2.1 Basics of RANSAC ............................................................................... 11

2.2.2 The RANSAC algorithm ....................................................................... 14

2.2.3 Results from RANSAC ......................................................................... 18

2.3 Mean Shift ........................................................................................................ 18

2.3.1 Basics of Mean Shift ............................................................................. 18

2.3.2 Mean shift algorithm ............................................................................. 20

2.3.3 Results of mean shift tracking ............................................................... 22

2.4 Optical flow method ......................................................................................... 23

2.4.1 Basics of optical flow ............................................................................ 23

2.4.2 Variants of optical flow ......................................................................... 26

Chapter 3. Combined Method ........................................................................................ 28

3.1 Description of the combined method ............................................................... 28

3.2 Algorithm of the combined method ................................................................. 29

Chapter 4. Experimental Results .................................................................................... 33

4.1 Results from SIFT and RANSAC .................................................................... 33

4.2 Results from Mean Shift ................................................................................... 34

4.3 Results from optical flow ................................................................................. 35

4.4 Results from the combined method .................................................................. 36

4.5.1. Discussion ............................................................................................. 38

4.5.2. Conclusion and future work ................................................................. 39

Acknowledgements ........................................................................................................ 42

References ...................................................................................................................... 43

1

Chapter 1. Introduction

1.1 Concept of visual object tracking

Visual object tracking is an important task within the field of computer vision. It aims at locating a moving object or several ones in time using a camera. An algorithm analyses the video frames and outputs the location of moving targets within the video frame. So it can be defined as the process of segmenting an object of interest from a video scene and keeping track of its motion, orientation, occlusion etc. in order to extract useful information by means of some algorithms. Its main task is to find and follow a moving object or several targets in image sequences. The proliferation of high-powered computers and the increasing need for automated video analysis have generated a great deal of interest in visual object tracking algorithms. The use of visual object tracking is pertinent in the tasks of automated surveillance, traffic monitoring, vehicle navigation, human-computer interaction etc. Automated video surveillance deals with real time observation of people or vehicles in busy or restricted environments leading to tracking and activity analysis of the subjects in the field of view. There are three key steps in video surveillance: detection of interesting moving objects, tracking of such objects from frame to frame, and analysis of object tracks to recognize their behavior. Visual object tracking follows the segmentation step and is more or less equivalent to the "recognition" step in the image processing. Detection of moving objects in video streams is the first relevant step of information extraction in many computer vision applications. There are basically three approaches in visual object tracking. Feature- based methods aim at extracting characteristics such as points, line segments from image sequences, tracking stage is then ensured by a matching procedure at every time instant. Differential methods are based on the optical flow computation, i.e. on the apparent motion in image sequences, under some regularization assumptions. The third class uses the correlation to measure interimage displacements. Selection of a particular approach largely depends on the domain of the problem. The development and increased availability of video technology have in recent years inspired a large amount of work on object tracking in video sequences [1]. Many researchers have tried various approaches for object tracking. Nature of the technique used largely depends on the application domain. Some of the research work done in the field of visual object tracking includes, for example: The block matching technique for object tracking in traffic scenes in [2]: A motionless airborne camera is used for video capturing. They have discussed the block matching technique for different resolutions and complexities. Object tracking algorithm using a moving camera in [3]: The algorithm is based on domain knowledge and motion modeling. Displacement of each point is assigned a discreet probability distribution matrix. Based on the model, image registration step is carried out. The registered image is then compared with the background to track the moving object. Video surveillance using multiple cameras and camera models in [4]: It uses object features gathered from two or more cameras situated at different locations. These features are then combined for location estimation in video surveillance systems. Another simple feature based object tracking method is explained in [5]: The method first segments the image into foreground and background to find objects of interest. Then four types of features are gathered for each object of interest. Then for each consecutive frames the changes in features are calculated for various possible 2 directions of movement. The one that satisfies certain threshold conditions is selected as the position of the object in the next frame. A feedback-based method for object tracking in presence of occlusions in [6]: In this method several performance evaluation measures for tracking are placed in a feedback loop to track non-rigid contours in a video sequence.

1.2 Applications of visual object tracking

Visual object tracking has many applications. Some important applications are: (1) Automated video surveillance: In these applications computer vision system is designed to monitor the movements in an area (shopping malls, car parks, etc.), identify the moving objects and report any doubtful situation. The system needs to discriminate between natural entities and humans, which require a good visual object tracking system. (2) Robot vision: In robot navigation, the steering system needs to identify different obstacles in the path to avoid collision. If the obstacles themselves are other moving objects then it calls for a real-time visual object tracking system. (3) Traffic monitoring: In some countries highway traffic is continuously monitored using cameras. Any vehicle that breaks the traffic rules or is involved in other illegal act can be tracked down easily if the surveillance system is supported by an object tracking system. (4) Animation: Visual object tracking algorithm can also be extended for animation. (5) Government or military establishments. To sum up, visual object tracking is applied to a wide range of fields nowadays, such as multimedia, video data compression, industry production, military affairs and so on. Accordingly, it is of great real significance and application value to investigate in visual object tracking. The detection and tracking of motion object in real time image sequences is the important task in image processing, computer vision, mode identification etc. It flexibly combines the technologies of image processing, autocontrol and information science, forms a new technology of real time detection of motion object, extraction location information of the object and tracking of it. Furthermore, rapid progress in technologies of signal processing, sensor and new material provides reliable software and hardware for the capturing and processing of image in real time.

1.3 Difficulties and algorithms

In general, trackers can be subdivided into two categories [7]. First, there are generic trackers which use only a minimum amount of a priori information, e.g., the mean-shift approach by Comaniciu et al. [8] and the color-based particle filter developed by Perez et al. [9]. Secondly, there are trackers that use a very specific model of the object, like e.g. the spline representation of the contour by Isard et al. [10, 11]. The objects found in video trackers are often being tracked in "difficult" environments characterised by the variable visibility (e.g. shadows, occlusions) and the presence of spurious (e.g. similarly-coloured) objects and backgrounds. As a result, visual object tracking still suffers from a lack of robustness due to temporary occlusions, objects crossing, changing lighting conditions, specularities and out-of- plane rotations.The main difficulty in video tracking is to associate target locations in 3 consecutive video frames, especially when the objects are moving fast relative to the frame rate. Here, video tracking systems usually employ a motion model which describes how the image of the target might change for different possible motions of the object to track. Many algorithms have been developed and implemented to solve the difficulties that arised from the video tracking process, such as SIFT ( Scale Invariant Feature Transform), KPSIFT (keypoint-preserving-SIFT), PDSIFT (partial-descriptor-SIFT), RANSAC(Random Sample Consensus), mean shift, optical flow, GDOH (gradient distance and orientation histogram) etc. The role of the tracking algorithm is to analyze the video frames in order to estimate the motion parameters. These parameters characterize the location of the target.

1.4 The structure of this thesis

The thesis consists of four chapters, the details are as follows: In Chapter 1, we explain the concept of visual object tracking and introduce some of the research work done in the field, five aspects of its important applications, the difficulties in visual object tracking, and some algorithms dealing with these issues. The structure of this thesis is also described. In Chapter 2, we review the current feature generation methods in the field of visual object tracking, including SIFT, RANSAC, mean shift and optical flow. An extensive survey of the concept, characteristics, detection stages, algorithms, experimental results of SIFT as well as advantages of SIFT features are presented. The concept, algorithm of RANSAC, experimental result of using RANSAC and basic affine transforms are dissertated. The basic theory and algorithm of mean shift, density gradient estimation and some experimental results of mean shift tracking are described. The basic theory of optical flow, two kinds of optical flow and experimental results of optical flow are given in the last part. In Chapter 3, we present an enhanced SIFT and mean shift for object tracking.. The flowchart of algorithmic is included and some experimental results of the integration of mean shift and SIFT feature tracking are presented. Experiment results verified that the proposed method could produce better solutions in object tracking of different scenarios and is an effective visual object tracking algorithm. In Chapter 4, we discuss the work done in this thesis. Several directions for further research are presented, including: Develop algorithms for tracking objects in unconstrained videos; Efficient algorithms for online estimation of discriminative feature sets; Further study on the online boosting methods for feature selection. Using semi-supervised learning techniques for modeling objects; Modeling the problem using Kalman filter more accurately; Improving the speed of the fitting algorithm in the active appearance model by using multi-resolution; Investigating the convergence property of the proposed framework. 4

Chapter 2. Feature Extraction Methods

Visual object tracking is an important topic in multimedia technologies, particularly in applications such as teleconferencing, surveillance and human- computer interface. The difficulty in visual object tracking process is to find and filter some features that are less sensitive to image translation, scaling, rotation, illumination changes, distortion and partially occlusion. The goal of object tracking is to determine the position of the object in images continuously and reliably against dynamic scenes. To achieve this target, a number of elegant methods have been established. This thesis has studied several image feature generation methods, including SIFT, RANSAC, mean shift, optical flow. The feature points of SIFT is based on keypoints. RANSAC method is based on parameters of a mathematical model from a set of observed data, mean shift method is based on the kernel and density gradient function, optical flow is based on color or intensity changes.

2.1 SIFT method

2.1.1 Concept and features of SIFT

Scale Invariant Feature Transform (SIFT) is an approach for detecting and extracting local feature descriptors that are reasonably invariant to changes in illumination, scaling, rotation, image noise and small changes in viewpoint. This algorithm is first proposed by David Lowe in 1999, and then further developed and improved [12]. SIFT features have many advantages such as follows: (1) SIFT features are all natual features of images. They are favorably invariant to image translation, scaling, rotation, illumination, viewpoint, noise etc. (2) Good speciality, rich in information, suitable for fast and exact matching in a mass of feature database. (3) Fertility. Lots of SIFT features will be explored even if there are only a few objects. (4) Relatively fast speed. the speed of SIFT even can satisfy real time process after the SIFT algorithm is optimized. (5) Better expansibility. SIFT is vey convenient to combine with other eigenvector, and generate much useful information. Detection stages for SIFT features are as follows: (1) Scale-space extrema detection: The first stage of computation searches over all scales and image locations. It is implemented efficiently by means of a difference- of-Gaussian function to identify potential interest points that are invariant to orientation and scale. 5 (2) Keypoint localization: At each candidate location, a detailed model is fit to determine scale and location. Keypoints are selected on basis of measures of their stability. (3) Orientation assignment: One or more orientations are assigned to each keypoint location on basis of local image gradient directions. All future operations are performed on image data that has been transformed relative to the assigned scale, orientation, and location for each feature, thereby providing invariance to these transformations. (4) Generation of keypoint descriptors: The local image gradients are measured at the selected scale in the region around each keypoint. These gradients are transformed into a representation which admits significant levels of local change in illumination and shape distortion.

2.1.2 Scale-space extrema detection

Interest points for SIFT features correspond to local extrema of difference-of-

Gaussian filters at different scales.

Given a Gaussian-blurred image described as the formula (,, ) (,, ) (,)Lxy Gxy Ixy (2-1) Where 22
2 2

1(,, )2

xy Gxye (2-2) (2-2) is a variable scale Gaussian, whose result of convolving an image with a difference-of-Gaussian filter is given by (,, ) (,, ) (,, )Dxy Lxyk Lxy (2-3) Which is just be different from the Gaussian-blurred images at scales andk. 6 Scale (first octave)Scale (next octave)

Gaussian

difference-of-

Gaussian

(DOG) Fig. 2.1 Diagram showing the blurred images at different scales, and the computation of the difference-of-Gaussian images The first step toward the detection of interest points is the convolution of the image with Gaussian filters at different scales, and the generation of difference-of- Gaussian images from the difference of adjacent blurred images. The rotated images are grouped by octave (an octave corresponds to doubling the value of ı), and the value of k is selected so that we can obtain a fixed number of blurred images per octave. This also ensures that we obtain the same figure of difference-of-Gaussian images per octave. Scale Fig. 2.2 Local extrema detection, the pixel marked × is compared against its 26 neighbors in a 3 × 3 ×3 neighborhood that spans adjacent DoG images Interest points (called keypoints in the SIFT framework) are identified as local maxima or minima of the DoG images across scales. Each pixel in the DoG images is 7 compared to its 8 neighbors at the same scale, plus the 9 corresponding neighbors at neighboring scales. If the pixel is a local maximum or minimum, it is selected as a candidate keypoint.

For each candidate keypoint:

(1) Interpolation of nearby data is used to accurately determine its position; (2) Keypoints with low contrast are removed; (3) Responses along edges are eliminated; (4) The keypoint is assigned an orientation. To determine the keypoint orientation, a gradient orientation histogram is computed in the neighborhood of the keypoint (using the Gaussian image at the closest scale to the keypoint's scale). The contribution of each neighboring pixel is weighted by the gradient magnitude and a Gaussian window with a ı that is 1.5 times the scale of the keypoint. Peaks in the histogram correspond to dominant orientations. A separate keypoint is reated for the direction corresponding to the histogram maximum, and any other direction within 80% of the maximum value. All the properties of the keypoint are measured relative to the keypoint orientation, this provides invariance to rotation.

2.1.3 Locating keypoints

The key step, also is the first step in object recognition using SIFT method is to generate the stable feature points. The figure below gives a whole process on how to find and describe the SIFT feature points.

Input an image

Create scale space

Compute difference of

gussian function

Detect scale space

extrema

Remove low

contrast pointsquotesdbs_dbs18.pdfusesText_24

[PDF] Ma Cuisine - Magimix

[PDF] livre-maitre

[PDF] Télécharger le petit livre 2017 - Fédération Nationale des Chasseurs

[PDF] Livre Phare 4eme | PDF, DOCX, EPUB and other eBooks formats

[PDF] LISTE DES MANUELS SCOLAIRES 1ère S - Lycée international

[PDF] Livre du professeur - Le livre du prof

[PDF] Manuels scolaires Classe de Terminale ANNEE SCOLAIRE 2016

[PDF] Les 10 étapes du succès par la PNL - PNL Audio Institut

[PDF] Histoire de la science politique dans ses rapports - Gallica - BnF

[PDF] Manuel de jardinage pour débutants - aupetitcolibri - Free

[PDF] Le jardin potager dans les zones tropicales - Agriculture et

[PDF] PRATIQUE DU FRANÇAIS

[PDF] Programme du CAPLP externe d économie et gestion de la session

[PDF] concours officier de police l essentiel - Bookelis

[PDF] Le Livre et la lecture en Algérie - unesdoc - Unesco