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? - Jul 24, 2013 at 3:47AM
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? - Jul 25 2013 9:20PM
Douglas Brown Avatar
Douglas Brown
109 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? - Aug 09 2013 2:44AM
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? - Aug 09 2013 1:21PM
Douglas Brown Avatar
Douglas Brown
109 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? - Aug 16 2013 6:13AM
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? - Aug 16 2013 2:47PM
Douglas Brown Avatar
Douglas Brown
109 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



The OSP Network:
Open Source Physics - Tracker - EJS Modeling
Physlet Physics
Physlet Quantum Physics