Archive for the ‘algorithms’ Category

## 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.

## 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.

## 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 chain code measures

Wednesday, October 13th, 2010

Last month I wrote a post showing how to calculate the perimeter of an object using its chain code. In this post I want to review several more measures that can be easily obtained from the chain codes: the minimum bounding box; the object’s orientation, maximum length and minimum width; and the object’s area. The bounding box and area are actually easier computed from the binary image, but if one needs to extract the chain code any way (for example to compute the perimeter) then it’s quite efficient to use the chain code to compute these measures, rather than using the full image. To obtain the chain codes, one can use the algorithm described in the previous post, or the DIPimage function `dip_imagechaincode`.

## How to obtain the chain code

Monday, September 27th, 2010

In the previous post I discussed simple techniques to estimate the boundary length of a binarized object. These techniques are based on the chain code. This post will detail how to obtain such a chain code. The algorithm is quite simple, but might not be trivial to understand. Future posts will discuss other measures that can be derived from such a chain code.

In short, the chain code is a way to represent a binary object by encoding only its boundary. The chain code is composed of a sequence of numbers between 0 and 7. Each number represents the transition between two consecutive boundary pixels, 0 being a step to the right, 1 a step diagonally right/up, 2 a step up, etc. In the post Measuring boundary length, I gave a little more detail about the chain code. Worth repeating here from that post is the figure containing the directions associated to each code:

The chain code thus has as many elements as there are boundary pixels. Note that the position of the object is lost, the chain code encodes the shape of the object, not its location. But we only need to remember the coordinates of the first pixel in the chain to solve that. Also note, the chain code encodes a single, solid object. If the object has two disjoint parts, or has a hole, the chain code will not be able to describe the full object.