Experience Implementing An Elliptical Head Tracker in MatlabJing Han ShiauDepartment of Computer Science and EngineeringUniversity of California, San DiegoLa Jolla, CA, [email protected] project implements an elliptical head tracker based onideas proposed by Birchfield in Matlab. The techniquesintroduced in Birchfield’s papers make little assumptionsabout the human head, and should be able to run in real-time. Implementation has shown that real-time applicationshould not be done in Matlab since any code involving forloops would drastically slow the program down. Implemen-tation issues and details are discussed as well as ideas forincorporating gaze estimation.1. IntroductionBecause of many potentially important applications suchas video conferencing, distance, learning, automatic videoanalysis and surveillance, head tracking is one of themost active field in computer vision. A good head trackershould make as little assumption about the human head aspossible. Having a small number of assumptions allowsthe head tracker to generalize to different situations; havinga simple model representation of the tracked object alsohelps simplifying the computation. Birchfield’s ellipticalhead tracker [1] is chosen to be implemented becauseit only assume that the human head can be modelledusing an ellipse and nothing else. The simple and generalassumption makes the elliptical head tracker a fairly robustone.Programs written in C/C++ need to be compiled differ-ently for different platforms. In recent years, there is amovement for platform independent languages to increasethe portability of programs. Programmers are encouragedto use languages like Java that supports platform indepen-dence as well as object-oriented programming style andhigh-level programming environments are preferred. How-ever, C/C++ are still popular programming languages be-cause empirical studies have been done to show that plat-form dependent languages run faster than platform indepen-dent languages. For this reason, a lot of real-time trackingsystems are coded in C/C++. The experience of an attemptto create a portable real-time head tracking system in Mat-lab, a high-level programming environment, is discussed.2. BackgroundThe elliptical head tracker models the human head bya vertical ellipse with a fixed aspect ratio of 1.2 (majoraxis:minor axis). The ellipse is centered at (x, y), withσ being the length of the minor axis. The notations = (x, y, σ) represents the head’s state. A pre-definedmodel is used to find the location of the head in the image.A location that best matches the values of the model isexpected to be the head location. Two modules are used incomparison with the model: gradient and color. The basisbehind the elliptical head tracker is that ”every closed setin the plane can be decomposed into two disjoint sets: theboundary and the interior.” [1] The expected head locationmaximizes the scores computed based on the intensitygradient and color histograms.The search space S is the set of locations within somerange of predicted location such thatS = {s : |x − xp| ≤ xr, |y − yp| ≤ yr, |σ − σp| ≤ σr}.In Birchfield’s implementation, the implementation, xr=yr= 8 pixels; in Matlab’s implementation, the range is keptthe same, but searches are done every 2 pixels. σrremains 1pixel. For a given frame t, the position (xp, yp) is predictedfrom the constant velocity assumption [2], utilizing headpositions found in the previous two frames. The width ofthe head is assumed to be roughly constant from frame toframe. Therefore, the predicted state of the head in frame tis given by:xpt= 2x∗t−1− x∗t−2ypt= 2y∗t−1− y∗t−2σpt= σ∗t−1.12.1. Gradient ModuleGiven a state s, the gradient score φg(s) is computed fromthe dot product of the intensity gradient gsaround theperimeter of the ellipse and the unit vector normal to theellipse nσalong the perimeter. Mathematically, the gradi-ent score at pixel i is:φg(s) =1NσNσXi=1|nσ(i) · gs(i)|.This measure evokes the greatest response for contourswhose gradient direction matches the elliptical normalalong the ellipse perimeter; therefore, the predicted can-didate position has the largest gradient score in the searchspace S. In order to incorporate the gradient score to thecolor score, the former is converted as follows:φg(s) =φg(s) − minsi∈sφg(si)maxsi∈sφg(si) − minsi∈sφg(si).2.2. Color ModuleBefore tracking, a model image of a three-quarters viewof the head being tracked is input into the system. Acolor histogram in a color space with axes B − G, G − Band B + G + R is constructed from the pixels inside theellipse in the model image. The first two axes of the colorspace contains chrominance information and are sampledinto eight bins while the last axis contains luminanceinformation and is sampled into four bins. The range of thehistogram is saved for later computation.The color score is computed from the histogram inter-section between the model histogram M and an arbitraryimage histogram I as follows:φc(s) =PNi=1min(Is(i), M(i))PNi=1Is(i).The color histogram represents how closely the image re-sembles the color distribution of the model as a percentageof the total number of pixels inside the ellipse.To give equal weight to the gradient score and the colorscore, the latter is also converted into a percentage of theform:φc(s) =φc(s) − minsi∈sφc(si)maxsi∈sφc(si) − minsi∈sφc(si).3. Implementation IssuesThe initial goal was to create a real-time tracking system;however, the speed at which Matlab programs execute is tooslow for such purposes. Even with optimized implemen-tations, each frame would require at least fifteen secondsto process on a PIII 600. [4] In this system, each framerequires about one minute to process despite efforts to de-crease running time.3.1. Modified Gradient ScoreInitially, the gradient score is calculated as reported above,but the performance is poor. Referencing project done byPatrick Lu of Stanford [4], a slightly different gradient scoreis used. The new gradient scores computes the dot productbetween the ellipse normal and the gradient of the pixelsalong the ellipse on the intensity map of the image and sumup the values. The sum is then ”normalized” by divisionwith the sum of gradient value along the y-axis. The trackeris able to lock onto the contour of the head much better us-ing this new gradient score than the one described in theBirchfield