How to implement Permutation

During the target tracking, finding the correspondence is always relevant. For multi-camera tracking there are large numbers of splendiferous methods to find the correspondence between the target-markers and image-points. But for one camera tracking system, brute-force is always the recommended one.

So that means we have to try every possible combination to test them and choose the best correspondence as the final result. How to evaluate the best result you can decide depending on the applications' case and implementation's method. But there is one thing for brute-force at any rate should be carried out -- permute one candidate group to achieve the ergodic. So the implementation of permutation is always required for brute-force. Actually it's not a so difficult topic for programming, but some details for the calling shouldn't be ignored.

One of the most popular method is a recursive way. The thinking is as follows: e.g we have 5 figures as {1, 2, 3, 4, 5}, the permutation of the last two figures is {4, 5} and {5, 4}. They are the permutation of 4 and 5 with the beginning of 5 and 4 respectively.
Let's look at the last 3 figures {3, 4, 5}, the permutation is {3, 4, 5}{3, 5, 4}; {4, 3, 5}{4, 5, 3}; {5, 3, 4}{5, 4, 3}, like above they are also the permutation of another 2 figures with the other one as beginning, this rule could be obtained until the end(or the beginning), that is the whole permutation. So with this feature we could take advantage of the recursive thinking to achieve all of the possible situations. The advantage is short and clean implementation, the codes are always easy to read and write. But the values during the recursive implementation is not simply achieved because of the recursive structure. But for a simple C application I think it's a good choice. I have written a C code here, and hoping it helps: permutation.c

Luckily by C++ implementation there are already 2 implemented methods pre_permutation and next_permutation to realize the permutation of an array. The difference is with the increasing order or decreasing one. Advantage compared with the first one is obvious that we could obtain the feed back for a further processing, but the order of the perputation is always determined, besides during my implementation it works perfect for array varible, but with vector definition, the mistakes always occur. It implies that before the implementation the size of the array should be decided, because permutation is not proper for a size-omitted array. We have to define the size of array during the initializaiton. So this way is not so perfect for the dynamic programming under which the numbers of markers from the target is not sure. Here is a example code of the Cpp implementation: permutation.cpp

In matlab implementation it is much easiser with the method perms(), e.g:
A = [1 2 3];
perms(A):
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Posted in: Codes,tracking technology