Posts Tagged ‘mathematical morphology’

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…)

Tags: DIPimage, DIPlib, labeling, mathematical morphology, timing, Union-Find, watershed.

Posted in algorithms, analyses, tutorials | 1 Comment »

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…)

Tags: dilation, DIPimage, DIPlib, Gaussian, mathematical morphology, timing.

Posted in analyses | 6 Comments »

Sunday, June 23rd, 2013

We recently organized the 11^{th} International Symposium on Mathematical Morphology here in Uppsala. I’m very happy with how the event turned out, and we got lots of positive comments from participants, so all our hard work paid off. We had a nice turnout, very interesting presentations, and lots of discussions. And I’m now the editor of a book containing all the papers presented.

There seem to be several trending topics in the ISMM community at the moment. One of those is the application of Mathematical Morphology to colour images. People have been working on this topic for a while now, and still there is no optimal solution. This year, three very different methods were presented to try and solve this problem. But what is this problem about?

(more…)

Tags: colour, filtering, mathematical morphology, vector ordering.

Posted in tutorials | 2 Comments »

Saturday, June 30th, 2012

We are going to be organizing the 11th conference in a series dedicated to Mathematical Morphology. This is the main conference in the field, and many of the ideas within Mathematical Morphology were first presented there. I can’t count the number of times the proceedings for this series is mentioned in the reference list of my papers! The first call for papers just went out, I’m copying it here for anyone interested. For more information, visit the ISMM 2013 website.

(more…)

Tags: conference, mathematical morphology.

Posted in announcements | No Comments »

Saturday, April 17th, 2010

I found an interesting submission on the File Exchange. It uses a very simple set of mathematical morphology filters to find the solution to simple mazes. I have several other solutions, so I decided to write an entry about the subject.

(more…)

Tags: distance transform, mathematical morphology, maze, skeleton.

Posted in tutorials | 16 Comments »