APS Excellence in Physics Education Award
November 2019

Education Prize Logo
Science SPORE Prize
November 2011

NSF Logo
The Open Source Physics Project is supported by NSF DUE-0442581.

algorithm of tracker? post and replies

Return to the algorithm of tracker? thread
Login to post to this thread

What kind of algorithm uses the tracker programm to track?
Martin Peters
13 Posts

Hi Doug, hi all,
I got another question. This time about how tracker decides if the marked match is similar to the template or not.
For a better understanding and to analyse trackers inaccuracy of measurement I would like to know how exactly tracker finds the right section of the video.

I know so far:
I tell the programm to search for the template and it compares the pixels. But how can I know this is exactly the right point?
I know the Automark value (standard is 4) has something to do with the precision of the track.

Can you explain how it works or tell me where I can find these information?

Thanks a lot

Martin


Replies to What kind of algorithm uses the tracker programm to track?

Re: What kind of algorithm uses the tracker programm to track? -
Douglas Brown Avatar
Douglas Brown
449 Posts

Hi Martin,

Good question, thanks for asking. The algorithm's not at all obvious and not (yet) posted anywhere!

Here's an outline of the tempate-matching process:

  1. At each test position in the search area, find the RGB square deviation ("RGBSqD": sum
      of squares of rgb differences of all pixels) between the template and video image.
      Note that the RGBSqD is zero for a perfect match and larger for poorer matches.

  2. Determine the average RGBSqD for all test positions.

  3. Define the position for which the RGBSqD is minimum as the "working" best match.
      Convert the RGBSqD to a "peak height" (PH) using PH = (avgRGBSqD/matchRGBSqD)-1.
      Note that the PH is infinity for a perfect match, greatest for the best match and zero for
      an average match.

  4. If the PH exceeds the "Automark" setting, the match is deemed to be a good one
      (i.e., significantly better than average).

  5. For sub-pixel accuracy, fit a Gaussian curve to the PHs of the working best match
      and its immediate vertical and horizontal neighbors. Note that the 3-point Gaussian
      fits should be exact.

  6. The final best match (sub-pixel) is the position of the peak of the Gaussian fit.

  7. The width of the Gaussian fit is indicative of the uncertainty of the match position,
      but it is not used to explicitly estimate this uncertainty.

I hope this answers your question in enough detail.  If not, or if you have more questions, please don't hesitate to ask :-)

Doug

 



Re: Re: What kind of algorithm uses the tracker programm to track? -
Martin Peters
13 Posts

Hey Doug,
thanks for your answer! This was really helpful.
Up to now I've got just one other question concerning the tracking algorithm:
I can change the template size by hand. But what is the max and min template size (in pixels) and do you already have any examinations how the template size affects the accuracy of the tracking result?
Thanks again!
Kind regards
Martin



Re: What kind of algorithm uses the tracker program to track? -
Douglas Brown Avatar
Douglas Brown
449 Posts

There is no min or max template size, Martin. And I have never attempted to measure how the template size affects the tracking accuracy. I'm not even sure how one would go about doing this! There are so many possible variations in illumination, focus, etc... Doug



Re: Re: What kind of algorithm uses the tracker program to track? -
Martin Peters
13 Posts

For example I noticed that if you choose a small template the program is much faster, but sometimes matches the wrong position if there are similar objects near the target.



Re: Re: Re: What kind of algorithm uses the tracker program to track? -
Douglas Brown Avatar
Douglas Brown
449 Posts

Yes, there are definitely limitations to the ability of the autotracking algorithm to find the correct match in certain images. But in your example a larger template might not do any better...

The real key is to control the background and track objects with sharp boundaries, unique colors, etc. Of course, this is not always possible, and in those cases the need for human intervention (ie manual tracking) is inevitable.

Doug



OSP Projects:
Open Source Physics - EJS Modeling
Tracker
Physlet Physics
Physlet Quantum Physics
STP Book