Posts Tagged ‘timing’

Union-Find

Wednesday, March 21st, 2018

The Union-Find data structure is well known in the image processing community because of its use in efficient connected component labeling algorithms. It is also an important part of Kruskal’s algorithm for the minimum spanning tree. It is used to keep track of equivalences: are these two objects equivalent/connected/joined? You can think of it as a forest of trees. The nodes in the trees are the objects. If two nodes are in the same tree, they are equivalent. It is called Union-Find because it is optimized for those two operations, Union (joining two trees) and Find (determining if two objects are in the same tree). Both operations are performed in (essentially) constant time (actually it is O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly and is always less than 5 for any number you can write down).

Here I’ll describe the data structure and show how its use can significantly speed up certain types of operations.

(more…)

Efficient algorithms vs efficient code

Saturday, October 21st, 2017

Since I have spent quite a bit of time porting 25-year old code, I have been confronted with the significant changes to CPU architecture over that time. Code in DIPlib used to be very efficient back then, but some optimizations did not age well at all. I want to show some examples here. It is nice to see that a little bit of effort into optimization can go a long way.

I also want to give a quick example of a highly optimized implementation of an inefficient algorithm, which highlights the difference between algorithms and code.

(more…)

DIPimage 2.6 released

Monday, April 14th, 2014

Today we released version 2.6 of DIPimage and DIPlib. The change list is rather short. There are two items that I think are important: 1) We fixed a bug that caused an unnecessary copy of the output image(s) in the DIPlib-MEX interface, slowing down functions especially for large images. 2) We introduced a new setting to automatically make use of a feature introduced in the previous release.

(more…)

DIPimage 2.5.1 released

Friday, October 4th, 2013

We recently released a bugfix for DIPimage release 2.5. Since I didn’t announce the release of 2.5 here, this might be a good opportunity to review some of the improvements in 2.5.

(more…)

DIPimage 2.0 released

Wednesday, November 19th, 2008

Last week the new release for DIPimage and DIPlib was made available at diplib.org. The change list is pretty substantial, though there should be no real compatibility concerns. One of the most important changes is that, for both Windows and Linux, some image processing functionality now can use multithreading to make best use of multi-processor and multi-core systems. For example, all separable filters will use all available cores by default. (more…)