can anyone explain or describe the tracking algorithm used in touchlib? i’m interested to know. can’t really make out what is happening on blobtracker.cpp.

or any articles that explains this? the mathematics of it, etc. i tried google but can’t find anything related.

thanks

http://geekblog.nl/entry/24 and more of the algorithms are explained here : http://geekblog.nl/ (not touchlib version but just to give you some idea how it’s working)

Basically the implementation of the blob tracker native in touchlib is very confusing.

What it does is quite simple though.

There are a couple main steps:

1- Find the blobs in the screen. This is done by counting the number of connected white pixels in the screen. Pixels that touch more than 3 (from top of my head) pixels around them that are also white are part of the same blob. Then it does some checks on the shape too, to see if it is roughly circular. From this part, the blobtracker knows coordinates of blobs on the screen.

2- Now the blobtracker needs to identify which finger corresponds to which blob. This is done by comparing the position of each of the blobs with the blobs in the previous frame:

• If there is a blob close enough in the previous frame, the blob in the current frame gets the ID of the blob in the previous frame: it’s the same finger that moved.
• If there is no blob close enough: it is a new finger, so make a new unused ID for it.
• There are also blob IDs present in the previous frame that get no new blob assigned to them: these fingers are no longer touching the screen.

3- Now we know for each blob either if it is new, if it moved, and we also know the fingers that stopped touching the screen. For each of these options send an event for finger-down, finger-up or finger-moved.

4- OSC then listens for these events and bundles them into a frame and sends them out as TUIO messages to Flash or other applications.

Basically the number of fingers is so small (for the computer) that even for 100 fingers the naive algorithm of comparing each finger to all options from the previous frame is good enough. The native algorithm in touchlib uses a double-recursive function which is more complicated and also performance heavy.

The above naive approach does have the drawback that the data that is collected is a bit rough. For instance, when a finger ‘skips’ over the screen or the user moves really fast, the blob may sometimes get lost esp. with lower framerate cameras. If the blob is lost only for 1 camera frame the finger gets a new ID, and what appears as 1 movement to the user is several movements to the application.

That’s about it. Good luck!

Thanks much for the help Erik

Great explanation Erik. Thank You.

Erik2003 - 19 June 2008 01:13 PM

Basically the implementation of the blob tracker native in touchlib is very confusing.

What it does is quite simple though.

There are a couple main steps:

1- Find the blobs in the screen. This is done by counting the number of connected white pixels in the screen. Pixels that touch more than 3 (from top of my head) pixels around them that are also white are part of the same blob. Then it does some checks on the shape too, to see if it is roughly circular. From this part, the blobtracker knows coordinates of blobs on the screen.

2- Now the blobtracker needs to identify which finger corresponds to which blob. This is done by comparing the position of each of the blobs with the blobs in the previous frame:

• If there is a blob close enough in the previous frame, the blob in the current frame gets the ID of the blob in the previous frame: it’s the same finger that moved.
• If there is no blob close enough: it is a new finger, so make a new unused ID for it.
• There are also blob IDs present in the previous frame that get no new blob assigned to them: these fingers are no longer touching the screen.

3- Now we know for each blob either if it is new, if it moved, and we also know the fingers that stopped touching the screen. For each of these options send an event for finger-down, finger-up or finger-moved.

4- OSC then listens for these events and bundles them into a frame and sends them out as TUIO messages to Flash or other applications.

Basically the number of fingers is so small (for the computer) that even for 100 fingers the naive algorithm of comparing each finger to all options from the previous frame is good enough. The native algorithm in touchlib uses a double-recursive function which is more complicated and also performance heavy.

The above naive approach does have the drawback that the data that is collected is a bit rough. For instance, when a finger ‘skips’ over the screen or the user moves really fast, the blob may sometimes get lost esp. with lower framerate cameras. If the blob is lost only for 1 camera frame the finger gets a new ID, and what appears as 1 movement to the user is several movements to the application.

That’s about it. Good luck!

That’s good explanation Erik.
The blob tracking algorithm used in TouchLib, while naive and brute force, is a bit more complex than you described it in #2.
The way it finds the optimal blob match is by minimizing the sum of all the distances between the blobs of the current frame from the previous frame (global minima).
In order to do that we iterate through all of the permutations of the blobs, building the list and then in the next step find the item in this list with the minimum sum of distances. You can imediately see the problem with this approach when the blob count gets larger. Besides the fact that the algorithm is recursive in nature, it also has a problem in allocating a large amount of data to hold the blob permutations used in compare step. This data size is a factoriel of the blob count.
So, for example for 5 blobs, the algorithm needs to iterate through 120 permutations. For 10 blobs, the algorithm needs to iterate through 3628800 permutations. As you can see, this number grows very fast. Although they have placed some safeguards such as maximum blob distance (in order to cut some of the permutations), at some point this approach becomes not practical. This is even more true having the fact that we have to do all of this in real-time.

~Alex

Wow! I had no idea it got that deep into the iterations.

jet-plane - 19 June 2008 12:19 PM

http://geekblog.nl/entry/24 and more of the algorithms are explained here : http://geekblog.nl/ (not touchlib version but just to give you some idea how it’s working)

Thx Jet-Plane, I got new idea to modify touchlib form this website thx so much.

Hull

is there a difference between touchlib’s and opencv’s(sample folder: blobtrack.cpp) algo?