.. _poly_projection_ref:

Poly Projection
===============

Overview
--------

Poly projection is a projection based approach to finding the same object across
successive frames. By fitting the past particle locations with a polynomial,
the polynomial can be evaluated to predict where the particle location should
be. The closest particle to the projected location is then used. The algorithm
is:

+-------+----------------------------------------------------------------------+
| Frame | Description of step                                                  |
+=======+======================================================================+
| n     | An object is found                                                   |
+-------+----------------------------------------------------------------------+
| n+1   | Using the default search radius :math:`r_{default}`, find the        |
|       | closest point to the previous location, :math:`p(n)`.                |
+-------+----------------------------------------------------------------------+
| n+2   | Using the previous two points (:math:`p(n)` and :math:`p(n+1)`),     |
|       | calculate the velocity, :math:`v(n)`. Using this velocity, project   |
|       | the next location, :math:`p_{predict}(n+2) = p(n)*v(n)`.  Finally,   |
|       | find the closest object to the predicted location, within the search |
|       | radius, :math:`r_{search}`.                                          |
+-------+----------------------------------------------------------------------+
| n+3   | Using the previous three points (:math:`p(n)`, :math:`p(n+1)`, and   |
|       | :math:`p(n+2)`), fit a polynomial, :math:`f()`. Evaluate the         |
|       | polynomial at the current frame to predict the object location,      |
|       | :math:`p_{predict}(n+3) = f(n+3)`. Finally, find the closest object  |
|       | to :math:`p_{predict}(n+3)`, within the search radius,               |
|       | :math:`r_{search}`.                                                  |
+-------+----------------------------------------------------------------------+
| n+i   | Repeat the n+3 step, using some or all the previous points to fit a  |
|       | new polynomial, until an object can not be found within the          |
|       | search radius at the projected location,                             |
|       | :math:`p_{predict}(n+i) = f(n+i)`                                    |
+-------+----------------------------------------------------------------------+

Where the following variables are defined as:

+------------------------+-----------------------------------------------------+
| Variable               | Description                                         |
+========================+=====================================================+
| :math:`p(n)`           | x, y, z position of the object                      |
+------------------------+-----------------------------------------------------+
| :math:`f(n)`           | polynomial fit to some or all of the previous       |
|                        | positions                                           |
+------------------------+-----------------------------------------------------+
| :math:`v(n)`           | velocity of the object                              |
+------------------------+-----------------------------------------------------+
| :math:`uncertainty`    | multiplier to calculate search radius               |
+------------------------+-----------------------------------------------------+
| :math:`r_{minimum}`    | minimum search radius                               |
+------------------------+-----------------------------------------------------+
| :math:`r_{search}(n)`  | search radius,                                      |
|                        | :math:`max(uncertainty*v(n-1), r_{minimum})`        |
+------------------------+-----------------------------------------------------+

Graphically, the algorithm looks like:

.. image:: ../../../tracker/images/poly_projection.png
    :align: center


Limitations
-----------

For a given search area, there can potentially be many objects. The current
implementation defaults to the closest object to the :math:`p_{predict}(n)`.
Depending on the speed of the objects, the closest object might not be the same
object, especially on the first step while using the default search area. One
way to overcome this issue is to use a sufficiently high sample rate (frame
rate) such that the displacement of the object is less than the center of its
closest neighbor.

The other method (not implemented yet) is to try matching objects using either
the intensity or a group of pixels (tile). This can be used to match objects as
opposed to picking the closest object.

Polynomial Order
----------------

For most applications, a polynomial degree of 2 should be sufficient to capture
and predict the motion of objects with acceleration. A polynomial with a degree
of 2 represents the following kinematic equation:

.. math::

   d = vt+{{1}\over{2}}at^2

where :math:`d` is the displacement, :math:`v` is the velocity, :math:`t` is
time and :math:`a` is acceleration. High order polynomials can also have wild
oscillations, causing predictions to be inaccurate as depicted below:

.. image:: ../images/poly_degree_compare.png
    :align: center

In practice, it has been observed that higher order polynomials can capture
collisions better then second order polynomials. Sample rates also need to be
sufficiently high to capture multiple points during the collision as well.

Neighbor Search
---------------

A KDTree, implemented in scipy, is constructed from the objects of each frame.
This tree is then used to find neighboring objects to a given point
(:math:`p_{predict}(n)`).