Archive for the ‘tutorials’ Category

Color quantization, minimizing variance, and k-d trees

Saturday, May 26th, 2018

A recent question on Stack Overflow really stroke my curiosity. The question was about why MATLAB’s rgb2ind function is so much faster at finding a color table than k-means clustering. It turns out that the algorithm in rgb2ind, which they call “Minimum Variance Quantization”, is not documented anywhere. A different page in the MATLAB documentation does give away a little bit about this algorithm: it shows a partitioning of the RGB cube with what looks like a k-d tree.

So I ended up thinking quite a bit about how a k-d tree, minimizing variance, and color quantization could intersect. I ended up devising an algorithm that works quite well. It is implemented in DIPlib 3.0 as dip::MinimumVariancePartitioning (source code). I’d like to describe the algorithm here in a bit of detail.

(more…)

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

Having fun with C++11 — how to pass flags to a function

Wednesday, January 4th, 2017

I’ve never been very active posting here, and since I left academia it has been even slower. All of 2016 passed without a single post! Since I now work for a company, it’s become more difficult for me to post about the fun little things that I work with. Nevertheless, I wanted to share a C++ construct that I came up with to pass flags (a collection of yes/no options) to a function.

(more…)

The curse of the big table

Wednesday, June 3rd, 2015

As an Area Editor for Pattern Recognition Letters, I’m frequently confronted with papers containing big tables of results. It is often the deblurring and denoising papers that (obviously using PSNR as a quality metric!) display lots of large tables comparing the proposed method with the state of the art on a set of images. I’m seriously tired of this. Now I’ve set my foot down, and asked an author to remove the table and provide a plot instead. In this post I will show what is wrong with the tables and propose a good alternative.

(more…)

No, that’s not a Gaussian filter

Friday, February 6th, 2015

I recently got a question from a reader regarding Gaussian filtering, in which he says:

I have seen some codes use 3×3 Gaussian kernel like

    h1 = [1, 2, 1]/4

to do the separate filtering.

The paper by Burt and Adelson (The Laplacian Pyramid as a Compact Image Code, IEEE Transactions on Communication, 31:532-540, 1983) seems to use 5×5 Gaussian kernel like

    h1 = [1/4 - a/2, 1/4, a, 1/4, 1/4-a/2],

and a is between 0.3-0.6. A typical value of a may be 0.375, thus the Gaussian kernel is:

    h1 = [0.0625, 0.25, 0.375, 0.25, 0.0625]

or

    h1 = [1, 4, 6, 4, 1]/16.

I have written previously about Gaussian filtering, but neither of those posts make it clear what a Gaussian filter kernel looks like.

(more…)