Cris’s Image Analysis Blog

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.

(more…)

The convolution is an important tool in image processing. All linear filters are convolutions (like, for example, the Gaussian filter). One of the reasons linear filters are so prevalent is that they imitate physical systems. For example, an analog electric circuit (containing resistors, capacitors and inductors) can be described by a convolution. The projection of a cell on a slide, through the microscope’s optical systems, onto the CCD sensor, can be described by a convolution. Even the sampling and averaging that occur in the CCD can be described by a convolution.

Two properties of the convolution are quite interesting when looking for an efficient implementation:

• The convolution is a multiplication in the Fourier domain: f(x)⊗h(x) ⇒ F(ω)⋅H(ω) . This means that you can compute the convolution by applying the Fourier transform to both the image and the convolution kernel, multiplying the two results, then inverse transforming the result.
• The convolution is associative: (f⊗h₁)⊗h₂ = f⊗(h₁⊗h₂) . This post is about the repercussions of this property.

(more…)

Last month I posted a tutorial on snakes. I explained that with snakes, the segmentation solution is obtained by minimizing an energy functional. The gradient descent minimization then yields an update function for the snake that can be seen as a set of internal and external forces acting on the snake. I was curious to see where we would get if we were to define the snake simply as a set of balls, connected with each other through springs, moving over the image with momentum, friction, and all the rest. For this, we will completely abandon the notions of gradient descent, function minimization, and so forth, and write a simple Newtonian physics simulation.

(more…)

In this post I want to show how easy it is to implement snakes using MATLAB and DIPimage. The next release of DIPimage will have some functionality implementing snakes, and this post is based on code written for that. The first implementation of snakes I made for DIPimage used a custom class, dip_snake, to simplify usage. We decided eventually to do without the class. The code discussed here uses that first implementation, which you can download here. The most important bits of the code are identical to that in the next release of DIPimage, but the wrapping is not. Adding the class is a nice excuse to show how to modify DIPimage to understand a new parameter type. I will discuss that in a future post.

(more…)

David Coeurjolly from the Université de Lyon just gave a presentation here at my department. He discussed, among other things, an algorithm that computes the Euclidean distance transform and is separable. The distance transform is an operation that takes a binary image as input, and writes in each object pixel the distance to the nearest background pixel. All sorts of approximations exist, using various distance measures that approximate the Euclidean distance. Using truly Euclidean distances is rather expensive. However, by making an algorithm that is separable, the computational cost is greatly reduced.

David’s algorithm computes the square distance first along each of the rows of the image, then modifies these distances by doing some operations along the columns. In higher-dimensional images you can just repeat this last step along the other dimensions. The operation to modify these distance values sounded very much like parabolic erosions to me, so I just gave this a try.

(more…)