Implementation

Contrary to kdtrees, the cover tree nodes always represent one point. So you have as many nodes as you have data points. Each of them can have several children, sorted by “level”, or distance hierarchy. Each level halves the distance between the node and its children. When constructing the tree instance, the distance you use is given as parameters (and its type is a template parameter, as well as the point type and the data type used for comparisons).

Construction of the tree is done by searching in the tree for the closest node and the lowest hierarchy possible. In all time, the min and max levels are tracked in the tree. On insertion, the max level is tried, and if it fails, the max level is increased by one. The failure occurs if the new point is furthest of the root point that the maximum distance on the max level. At each level, the set of the nodes that are closer to the new point than the current maximum distance are kept (function populate_set_from_node). If the least distance is greater than the next level maximum level (function find_min_dist, the recursion stops and the new node is inserted in the first node in the set.

When doing a search, a list of distances and points (of type NearestNodesStructure) is created and its size is kept at the number of neighbors k. On entrance of a new level (level_traversal), all nodes that have children that could be close enough (current distance less than maximum level distance + distance to the current k-th neighbors found with find_k_dist) are added to the list. In order to speed search, a map is not used, but a partial sort is done at each iteration (which makes find_k_dist work without sorting the container again). Without this, the performance is worse than a linear knn search.

I didn’t implement other functions like removal or traversal. I don’t need them, but feel free to add them if you need. Sidenote: I will try to find time to refactor the code, because it is not very clean at the moment (especially the knn method).

Results

So some figures. I’ve populated a tree with 100k elements, and then made a 10-neighbors search with the cover tree, and with a standard linear search. Without the construction time, the search is about ten times faster than a linear one. Of course, it all depends on the cover tree balance. You could design a cover tree that has too many levels (but also the data would be unusual) and that would result in an almost linear time.

I’ve done a profile with callgrind, but the majority of the time is in the tree construction. No point in checking the search and displaying it here as the following timings show:

Build time 00:09:38.530397
Out time (linear) 00:00:00.238989
Out time (cover_tree) 00:00:00.012518

What must be optimized is clearly the build time.

The test code is in the main.cpp file on github.

Cover Tree code on Github is here and the publication with detailed algorithms here.

I’ve implemented this pattern in most of my production code, when different algorithms are needed for some computation. Some weeks ago, a colleague asked to use one of my production codes, because the parallel I/O were hidden inside a job scheduler. The only thing he had to do was deriving a base class, implement the algorithm, and he could use the massively distributed framework. Of course, the derived class builder was registered in a map, registry pattern inside.

The idea of the plugin emerged when he didn’t want to compile the whole distributed system. As his class was automatically registered on startup, the plugin system was quite easy to implement: just dlopen() the library, and the build would be registered. Usually, you have to extract some function from the library before being able to use it. With a registry pattern, this is no longer the case. So I did just that, and now all the complicated algorithms can now be exported as plugins, which eases the building process (through SCons) and of course the algorithm development (big time).

Now, I just need to optimize the distributed framework for I/O…

So let’s talk about the book’s comprehensive guide.

Content and opinions

Sonar has an internal programming language, CAL. One of the reasons I’ve chosen this book is that there is a chapter on CAL.

The first thing one wants to do when starting Sonar is usually playing something. The author does not and spends four chapters explaining the basics of Sonar: first what gravitates around Sonar (sound card, synthesizer…), then how to configure Sonar to one’s needs, handling projects and finally how to navigate in a project.

The next three chapters are about music and sound handling: how they are recorded (audio or MIDI), how it can be modified (piano roll view, step sequencer view, event list or also tempo list), and some advanced features like quantize and audio snap. In my opinion, these are not really advanced features, because I tend to use them with all my projects. Also, the Groove Quantize is something that may not always be intuitive, but it is well explained in one page.

I have more or less skipped the eighth chapter, as they cover VST instruments, and I’m used to other instruments from Native Instruments. Having them is great when you don’t have some, but not relying on them allows to change Sonar to another sequencer if needed. Before moving to the console part, the author covers some other views that are useful to create content, like the matrix view or groove clips.

After a chapter on the console view, the author tackles effects. This means explaining how they can work and the different kind of effects and their implementation in Sonar. As for the instruments, the effects offered in Sonar are thoroughly explained, although their interface is simple enough. The next chapter covers automation and control surfaces, as their use is precisely on mixing and mastering. My only regret is that the generic control surface support has some issues that were not explained (especially when you have a motorized control surface, the automation does not make the knobs move as for a Mackie Control).

The last chapters (except for CAL) cover some side-functions that I don’t use: the export to a CD is not something I usually do with my sequencer (in fact I don’t do it on my computer, I prefer using a professional CD burner), surround is not something I’m interesting in (although it seems to be correctly covered by the author), I don’t work with the staff view and I don’t care about Studioware. This being said, I cared about the last chapter.

I expected a lot from the CAL chapter, but I knew that it could not be a full CAL course. The basics are covered, as well as some examples. Sadly it stops there, as the author refers to online tutorials that I never found. Still, it is enough for an accomplished programmer to start and to dig inside CAL with the help of the several scripts.

A great aspect of the book is keyboard shortcuts. Some of the functions are even only accessible by shortcuts, and of course when mastered, shortcuts can greatly enhance productivity.

Conclusion

The book tries to cover all aspects of Sonar. Although CAL is not as addressed as I would like it to be, it is covered enough to be usable. The last word would be that this guide is a good companion to the application.

Content and opinions

You don’t have to read the book to know how to take a picture, but each chapter adds a new angle o the way one can use the 7D. The first chapter is a ten configuration tips list, and I think each one of them is relevant. They have already helped me enhance my pictures. The second chapter is a list of things to check and understand before shooting. I have to say I didn’t apply them all (updating the firmware for instance), and there is also an overview of the basic technical elements in a camera (shutter, iso…).

Then the serious work begins. The third chapter browses through the different capture modes. Each mode is explained with the associated available changes (exposure, ISO…). Then two chapters tackle what I would say are the most common styles: portrait and landscape. I learnt about a lot of things offered by the 7D in those chapters, like exposure metering or the electronic level. There are a lot of tips that are available in those two chapters. The sixth chapter is about moving targets, a subject that is hard, but it seems that the camera has some useful functions for that.

Then, two chapters tackle subjects that are common to all modes: light and composition. There are more advanced books on these topics, but the author manages to cover the most useful ground, from hints to warnings. The last chapter but one is on video, it is interesting, but I didn’t get my 7D for video. Still, there is a warning that I did find very interesting on this subject. I won’t tell it here, go and grab the book instead.

The ending chapter is about some “advanced” techniques, but it’s more about explaining some things you can do with the 7D, but there is 90% chance that you won’t ever use any of them.

Finally, it is worth mentioning that each chapter starts with one or two pictures and some associated comments. This is a great help when you don’t have much experience. After each chapter, a small list sums up all new information.

Conclusion

This book is a perfect complement to the user guide. The latter explains one button or setting after the other, whereas the former links everything together. When you don’t know about the different modes of the camera (aperture or shutter for instance), it is a must have to take great pictures.

The Antipole Tree

An antipole tree is a binary search tree that is constructed on antipole pairs. An antipole pair is composed of the furthest points in a set. When constructing the tree, one starts with the full set of images/thumbnails, then recursively, an antipole pair is chosen from the (sub)set (figure 1) and two new clusters are created, images are aggregated to the nearest image of the pair (figure 2). When the subset is small enough, the recursion stops.

Figure 1: Original set with the first antipole pair

Figure 2: Two subsets based on the antipole pair in the original set

The search uses a distance-sorted list. When a leaf node is visited, one looks for the nearest image and stores the result. When an internal node is visited, its children will be added to the sorted list, and the distance will be the distance to the center of the cluster minus the radius (figure 3). This way, if the current best is nearer to the reference than the nearest cluster, no nearest image will be found. It’s a usual distance search in a binary tree.

Figure 3: distance from a new image to the different subsets

Result

Of course, building the tree is costly. Although it can be parallelized, it is still slow. The upper side is that using a tree for the search is O(log(n)) instead of the usual O(n). It is actually more efficient for mosaic databases with several thousands of images or more. The result is of course exactly the same as with the linear search.

There are some differences between the original publication (see the reference) and the current code. In the reference, the antipole pair has a special status, as the center of the clusters and they are not tested with the rest of the subset in a leaf node. So in the original code, each tested cluster tests at least one image with the reference, whereas only leaf nodes give the closest images search in my case. The difference is that the center of each cluster will be the real center of the cluster, meaning that the minimum distance will be more close to the reality, and I hope that this will translate into speed-up. The other addition is that the visiting code is also simpler, which is better for maintenance.

Conclusion

This tool has now a logarithmic image search. It should be faster than linear search for huge mosaic databases. Also, the final photomosaic was enhanced by changing the result mosaic mean to the original image mosaic.

Reference : Antipole Tree Indexing to Support Range Search and K-Nearest Neighbor Search in Metric Spaces

Random numbers are important in a raytracer because one needs oversampling to have anti-aliasing, and to have a more realistic rendering, we need to add some jitter inside the oversampling. I won’t talk about this here, it is not my point (yet). So I’ve decided to resurrect IRT from the dead, at least long enough to test parallel random number generators. It is now on Github, and I’ve also changed the matrix library to Eigen. Some optimizations later, it is slightly faster than before, although it is still very far from Bikker’s work.

The Python wrappers are still working BTW.

Let’s hope I find some time to finish this before getting back at VSTs

Content and opinions

The focus on the book is how to use a Version Control system, so several chapters are dedicated to how to use the most well-known one – and the one the author develops.

The book is split in three parts: “old” VCSs, new VCSs and finally how they work. The first chapter is a glossary of the special VCS words and their meaning. Once this is done, the first example chapter starts with Subversion. A small situation is depicted with two coders that are locally closed.

The third chapter starts the second part and it introduces new concepts for distributed VCSs. A complete chapter is dedicated to the advantages of DVCSs, and it doesn’t fall in the common pitfalls (those are in fact a reason to some humor from the author). The next chapter does exactly the opposite, i.e. explains the drawbacks of a DVCS. Although I disagree on GUI part (there are wonderful GUIs for both Mercurial and GIT on Windows, and on Linux they have a great integration in Eclipse for instance), I do agree with the author on the main topics here. The next four chapters are the practical application seen in the second chapter applied to Mercurial, Git and Veracity (two chapter for this one, one to explain the differences with Mercurial and Git, and one for the scenario), the tool the author develops.

The last part can be called “how to use them”. Even for the second generation tools like SVN, I was flabbergasted to see that a lot of coders didn’t even know how to use it, and even worse, that experienced managers didn’t know how to implement an appropriate workflow. So I think that the first chapter in this part should be something that everyone HAS to read if one wants to be called a coder. Seriously. Then, as I’ve said, the author explains how the distributed tools work and some of their internals. It’s not for the average coder, but it’s really interesting – for the culture. The last chapter is a set of golden rules, and like the first chapter, it’s something mandatory to read and use.

Conclusion

One of the most easy-to-read introductory books and a book on a sensible subject, this book should be read by everyone searching for a robust tool to support one’s development. It is also a very good argumentation on why you should use one.

The code is available under the GPL2 on github and on Sourceforge.

The plugin can be download on the Sourceforge project page.

The plugin was tested with Tracktion 3 (Windows XP).

Snapshot:

QtSimpleEQ UI

For instance, here is an original image:

Original photo

Rendered photomosaic

The code is available on GitHub, as usual, and it has been tested on Windows and Linux.

• The first is my fault, as the code of the EQ disappeared from my Git repository, so I have to code it again. Mainly it is just plugin the correct actions between the filters and the GUI.
• The second is an error at the end of the test. I’ve updated my Qt version from 4.7.1 to 4.7.4, and since this update (or perhaps since I updated to Python 2.7 for pyVST), I found that even a recompiled QtSimpleOverdrive has the same behavior. It did not when I released it. It seems that Qt is complaining about events that are bounced between different threads, but the actual error message is more cryptic, and impossible to debug the application at this point.

I hope to fix these mistakes this month, I really hope I can get QtVST to work again.