An Heuristic Search based Approach for Moving Objects Tracking

1 Problem Formulation

Let { } 2 1 , , ℜ ⊆ = r t t T K be a set of points that represent a template, let { } 2 1 , , ℜ ⊆ = s i i I K be another set of points that denote an input image, let a bounded set of translational transformations G(.) be a set of transformations 2 2 : ℜ → ℜ G consisting of translations, which are parameterized by a vector ( ) ∈ ∆ ∆ T y x, [ ]× ∆ ∆ max min , [ ] 2 max min , ℜ ⊆ ∆ ∆ and let a bounded error notion of quality of match ( ) ε , , I T G Q ; be a measurement for computing the degree of match between a template T and a current input image I. The quality of match assigned to a transformation G is represented by the allowed error boundε , when template points are brought to point's image using a transformation G:

Given a template T, an input image I and an error boundε , template position matching problem can be viewed as a search process in the space of transformations in order

2 A* Search Algorithm

Problem solving through the use of heuristic search strategies is expressed through a state space based representation approach [Pearl, 1984]. According to the heuristic search framework, template position matching problem is formulated as: the search process oriented to find the transformation parameters Gmax ∈ G(.) that maximizes the quality of function match Q(G) between the transformed template G(T) and the current image I. Next, each one of the elements of the problem is described:

• State: each state n is associated with a subset ( ) . G ⊆ k G , which is represented by the transformation corresponding to the centre that is referred to as Gc.
• Initial state: is represented by a bounded set of translational transformations G(.), which allowing matching the current template into the current scene.
• Final state: is the transformation that best matches the current template points into the current scene, according to the quality of function Q(G). The quality of function match assigned to a transformation G is expressed in terms of the partial directed Hausdorff distance between the transformed template T and the current image I:

That is, the final state corresponds to the state with the translation Gmax which verifies that the distance between 80% of translated template points and current image points are less than 2.0.

• Operators: for each current state n, the operators A and B are computed:
• Each partial set of transformations from the current state is partitioned into four regions by vertical and horizontal bisections (that is, four new states).
• The quality of function match (equation 3) is computed for each one of the four new states.

Splitting operation generates an expanded quaternary tree where with each node a 2 i x 2 j region is associated. The splitting operation is finished when the quadrisection process computes a translational motion according to the quality of function match Q(G). The best node to expand is computed through the use of an A* approach [Pearl, 1984]. The corresponding cost value assigned to each state n is defined as:

h*(n) is formulated in terms of expanding the best state of the search space based on measuring the similarity among the distribution functions that characterize the current state n and the objective state, denoted respectively by P and Q. The distribution function P is represented by a histogram distances { } r i Gc H K 1 = , which contains the number of template points T at distance dj with respect to the points of the input image I, when the transformation Gc of the current state n is applied on the current template T. The distribution function Q is modelled by approximating { } r i Gc H K 1 = by an exponential distribution function ( ) an ke n f - = .

The similarity between the distributions P and Q is evaluated through the relative entropy or Kullback-Leibler distance measurement from information theory [Cover and Thomas, 1991]:

An estimated cost function c(n) is employed to lead the search process towards promising solutions. With this aim, a depth term is added to the f(n) function (expression 4). This term is based on the number of operators of type A applied from the initial search node to the current node n.

An alpha-beta predictive filtering [Shalom and Rong, 1993] is incorporated into the search algorithm with the purpose of predicting target position and reducing the initial size of the search space of transformations, focused on the assumption that there is a relationship between the size of the search area and the resulting uncertainty of the alphabeta predictive filtering. Figure 1 illustrates the integration of the stages that compose the alpha-beta filtering with the computation of the dimension M x N of G(.) and their respective equations.

The algorithm for template position matching in our approach based on an A* search is as follows.

Input

G(.): initial set of transformations.

ε : distance error bound allowed when template points are brought to point's image using a transformation G.

v(k) : uncertainty measurement computed by alpha-beta filtering approach. ω : estimate which determines from what value should be selected 2 max or 2 min bound value for computing MxN dimension of G(.).

2 max and 2 min : upper and lower nearest values to the innovation factor v(k). η : number of operators of type A applied from the initial search state to

• the current state n.

Output

MxN dimension of initial state set G(.)

Step 1) Compute adjustable MxN dimension of initial state set G(.):

• 2.1) Split current state n into four new states { } 4 1K = i n

While ( ( ) ε > G Q ) Do

• 2.2) Compute ( ) ( ) ( ) I T G h G Q c k c , ← for each new ni
• 2.3) Expand the best state ni according the evaluation

• function ( ) ( ) ( ) n h n c n f * + = : 2.3.1) ( ) ( ) Q P D n h ← * 2.3.2) ( ) ( ) η + - ← 1 n c n c

3 Comparative Analysis and Runtime

Diverse experiments have been carried out with 24 different sequences, achieving the same behaviour for all of them on a P-IV 2.4 GHz. Comparing the results achieved from the proposed A* heuristic search that uses an adjustable-size search area approach with the blind search strategy that does not use information to guide the search process and does not estimate the dimension appropriated for initial search state such as the conventional search strategy described by [Rucklidge, 1996], demonstrates that the proposed A* heuristic search framework is computationally lighter and as consequence, faster than the blind search strategy, in an average rate of three times better. Average time measured in seconds for processing each frame for the 24 different sequences is 0.01, confirming the adaptation of the search strategy proposed to real-time restrictions under unrestricted environments for arbitrary shapes.