Archive for the ‘algorithms’ Category

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

Computing Feret diameters from the convex hull

Monday, February 13th, 2012

Some time ago I wrote about how to compute the Feret diameters of a 2D object based on the chain code of its boundary. The diameters we computed were the longest and shortest projections of the object. The shortest projection, or smallest Feret diameter, is equivalent to the size measured when physically passing objects through sieves (i.e. sieve analysis, as is often done, e.g., with rocks). The longest projection, or largest Feret diameter, is useful as an estimate of the length of elongated objects.

The algorithm I described then simply rotated the object in two-degree intervals, and computed the projection length at each orientation. The problem with this algorithm is that the width estimated for very elongated objects is not very accurate: the orientation that produces the shortest projection could be up to 1 degree away from the optimal orientation, meaning that the estimated width is length⋅sin(π/180) too large. This doesn’t sound like much, but if the aspect ratio is 100, meaning the length is 100 times the width, we can overestimate the width by up to 175%!

(more…)

The convex hull of a 2D object

Sunday, September 18th, 2011

Last year I wrote about computing the the boundary length and various other measures, given an object’s chain code. The chain code is a simple way of encoding the polygon that represents a 2D object. It is very simple to compute the object’s convex hull given this polygon. Why would I want to do that? Well, the convex hull gives several interesting object properties, such as the convexity (object area divided by convex hull area). Certain other properties, such as the Feret diameters, are identical for an object and its convex hull, and the convex hull thus gives an efficient algorithm to compute these properties.

(more…)

Bresenham’s line drawing algorithm in any number of dimensions

Friday, July 22nd, 2011

edit: I should have called this “an algorithm that produces the same output as Bresenham’s algorithm, generalised to arbitrary dimensions” (see discussion below)

J.E. Bresenham published an algorithm in 1965, which is used to draw 2D digital lines. Many people have extended the algorithm to work in 3D, and I’ve even found a website with code for 4D, 5D and 6D versions of the algorithm. However, all the code I come across is way more complex that it needs to be, giving the impression that this is a complicated algorithm. Nothing is further from the truth! Drawing digital lines is the most simple and straight-forward task. I’m going to deviate from the classical thinking that an efficient algorithm should use only integer values. This will make our task trivial.

(more…)

Dithering

Friday, January 7th, 2011

First of all: Happy New Year!

Over the holidays I’ve been learning about dithering, the process of creating the illusion of many grey levels using only black and white dots. This is used when displaying an image on a device with fewer than the 64 or so grey levels that we can distinguish, such as an ink-jet printer (which prints small, solid dots), and also when quantizing an image to use a colour map (remember the EGA and VGA computer displays?). It turns out that this is still an active research field. I ran into the paper Structure-aware error diffusion, ACM Transactions on Graphics 28(5), 2009, which improves upon a method presented a year earlier, which in turn improved on the state of the art by placing dots to optimize the appearance of thin lines. This got me interested in the basic algorithms, which I had never studied before. Hopefully this post will give an understanding of dithering and its history.

(more…)