Krusader - easily obtain image info using GraphicsMagick

Want to get the information of an image easily by right-clicking on it and then on an 'identify' button?

1. Install GraphicsMagick
2. Open Krusader, go to User Actions and add a new action of type 'Archive'.
3. Copy paste this into 'commands': gm identify -verbose %aCurrent%
4. In execution mode, select 'execute in terminal'.

Now press on apply and you should be able to get the information of an image through this user action. A terminal window should open with the results of executing the command specified above.

Skip Lists compared with Treaps and Red-Black Trees

I implemented the skip list, which is a linked-list based data structure that has an average performance comparable to BSTs (O(log n) for insertion/search/removal). What I find amazing about this data structure is that it is REALLY REALLY easy to implement (insertion took... 20 lines?) for such good performance. Furthermore, it is a data structure that can be made concurrency-friendly without major complications as the underlying structure is just a linked-list.

References:

- http://en.wikipedia.org/wiki/Skip_list
- Lecture from MIT
- Article on MSDN
- C# implementation by Leslie Sanford

I also wanted to compare the performance of the Skip List against the Treap and the Red-Black Tree. For that, I used my own implementation of the first two and I used a TreeMap (in Java Collections) for the third.

The Skip List was initialized with log(n) levels, where n is the amount of keys we'll be inserting into the structures. The random number of levels for each inserted key is calculated by generating a new level with a probability of 0.50 each time (equivalent to tossing a fair coin each time).

The test was done by executing the attached application several times and more or less memorizing the execution times (yeah, not very scientific... but I just wanted to have a quick look) for inputs of <100000 and >300000 pre-generated random numbers. The results, in descending order (fastest to slowest) were:

Insertion:
1. Treap
2. Skip List /RB tree (depending on input size: RB-tree faster with smaller input, skip list faster with larger input)

Search:
1. Treap
2. RB-tree
3. Skip List

Removal:
1. Treap
2. Skip List
3. RB-tree

The Treap was consistently faster (actually MUCH faster, I have to say) than the other two for all three operations, which is also the result obtained by Heger (pages 67-75). The skip list's performance was 'pretty good' but didn't seem too stable (could also be that my implementation was flawed in some way), while the RB-tree looked very stable. However, the skip list was incredibly easy to implement, which is also a great factor to take into account.

As for the memory footprint, I couldn't really compare them fairly but the general impression after running a profiler was that both the Treap and the RB-Tree used less space, which is quite logical as the Skip List uses quite a bit space for the pointers.

Note: if you want to run the test yourself you should remove the calls to System.out.println, as they affect the runtimes. The Treap package is also within the attached NetBeans project so that the comparisons can be done.

Source code:

Download

Treaps

A Treap is a data structure that combines a binary search tree with the heap invariant, which means that any root node of any subtree has a higher priority than its children (with a max-heap invariant, that is).

The idea is that BSTs perform really well when the insertions are done randomly, as it tends to be balanced, so the Treap tries to simulate this randomness by assigning random priorities to the inserted nodes.

I quickly implemented insertion/removal only for the purpose of learning and haven't refactored it, so the code could probably be further optimized/simplified.

Quick notes:

- Insertion: insert key X with a random priority. Insert works as in BSTs. Once the node is inserted, 'heapify' the node with the corresponding rotations.

- Removal: the opposite of the insertion. Find key X to remove, rotate the node down (preserving the heap invariant) until it becomes a leaf or has a null child and then remove it appropriately.

Further reference:
- http://en.wikipedia.org/wiki/Treap
- C implementation by Farooq Mela: https://github.com/fmela/libdict/blob/master/src/tr_tree.c

The Treap might perform better than BSTs, Skip Lists or other balanced trees such as Red-Black Trees, AVLs, AA trees or Splay Trees. Reference:

A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)

Source code (netbeans project):

Download

Issues with video recording

Some bug in OpenCV-1.0 provoked segmentation faults in an attempt to record video.

The solution was to upgrade to OpenCV-2.0.

Edit: doesn't work in 2.0 either. No error given, but the video file is not being written.

Further improving gesture recognition

So far the minimal bounding box has been used to check that the whole hand is inside the viewport but this proved unreliable when the hand orientation was horizontal/vertical, as the box would be horizontal/vertical as well. Instead, the bounding circle was used. Only if it was completely inside would the gesture considered to be recognised.

Aside from this, to make pointer movement easier pointer movement could be enabled/disabled with gestures, which would make the pointer easier to control as the camera quite probably will not cover all the screen, so the user might find himself moving the hand in and out of the screen towards the desired direction in order to get the pointer to the desired location.

Improving gesture recognition: discarding invalid gestures

Several problems arised with our method of gesture recognition based on convexity defects with respect to the convex hull. We were able to discard some invalid convexity points based on the distance from the deepest point in the defect to the convex hull.

However, this approach still had a problem, which is shown in the next picture.

Poor segmentation can yield false positives, as is shown in the picture.

We did not find an easy way to tackle it, so in the end it was decided that this gesture would not be recognised. Instead, we decided that the only gesture with one valid convexity defect which would be accepted would be the thumb-up gesture, rotation-invariant.


As can be observed, this gesture has a particular width to height ratio, so gestures which don't meet a certain ratio threshold can be discarded. In particular, 1.6 was selected, being the result of dividing width/height or the inverse, whichever is >1.

Another criteria we used to validate gestures was to establish a minimum and maximum number of sides that the gesture's polygonal approximation can have. With the polygonal approximation we have chosen, the start and finish points of the convexity defect, the fingertips, can be either spikes or flat.

We chose the minimum number of sides to be 6, which we found happened with a closed fist. Then, for every convexity defect we can count 4 sides. Invalid defects change what would have been one side to two or more. Removing already counted sides, we get the following formula:

Min_sides = 6
Max_sides = min_sides + (4 x valid_defects) - (valid_defects-1) - invalid_defects

Even though not perfect, with these two simple methods we are able to discard many invalid gestures due to poor segmentation and thus have a more robust recognition.

Possible improvements out of our scope

1. Other skin models so as to include other races
2. Motion recognition
3. Expand gesture set making use of the fingertips and the angles between them.
4. Recognize gestures in movement - useful for gaming, for example.
5. Improve recognition in heavy clutter
6. Improve performance
7. Multiple hands tracking for enhanced functionality.
8. Improve hand presence detection
9. Find a way to segment hand and discard forearm without sleeves
10. Improve dynamical model
11. Find a more cost-effective segmentation method and enhance robustness to changes in light.
12. Enhance mouse motion with acceleration, for example.