# Delaunay triangulation and Voronoi diagram in image processing

I am reading about image processing and it was mentioned in a couple of articles "Delaunay triangulation" and "Voronoi diagram".

I read on what the two things mean and how they are acquired, but why are they important in image processing? After searching on the DSP stackexchange and overall the Internet, I did not seem to find an explanation about this, so if I have missed a thread, with an explanation, I am apologizing in advanced.

...why are they important in image processing?

Because they offer ways by which to summarise a large set of points.

The Voronoi Diagram (VD) and Delaunay Triangulation (DT) of a set of points are duals of each other. If you have one of them you can construct the other.

The VD splits space into a set of tiles, one for each point in the set. Each tile represents those locations in space that are closest to a particular point in the set.

Imagine for example, that you take a handful of marbles and scatter them across the floor in a room. Then, you divide the room in a fine grid of locations. Let's say every 10cm x 10cm. You select one of the locations on this grid and measure its distance to all the marbles across the floor. This location will be closest to one of the scattered marbles. So, you assign this location in space to that marble. Then you repeat this process for all the locations in the fine grid, progressively assigning them to closest marbles.

In the end, you will have the VD of the set of points (positions of marbles on the floor). To visualise it, you simply plot each point in space choosing a different colour for each cluster.

To now construct the DT from the VD, you simply connect every two points in the set (the marbles on the floor) that share a boundary, to produce the VD's dual.

The whole point about this process is that it provides a way to relate the points in our set through rules and introduce some structure where before there was none.

The rule that governs the VD (measure distance, assign membership to the shortest distance) is "translated" to another rule in the DT. The triangles that are formed by connecting VD points that share a boundary have the maximum smallest angle of all other possible ways of connecting the points in triangles. Even for a moderate size of a set of points there is a huge number of possible ways by which the points can be connected into triangles. If you did form all of them and measured the smallest angle in the triangles of each one of these ways, the DT would be the one where the smallest angle of its triangles would be the largest.

The most obvious example where Delaunay Triangulation is applied is the construction of mesh geometry from point clouds. Say for example that you have a lidar which gives you a point cloud of measurements to points in its environment. If you do a Delaunay Triangulation on that set of points, you get a mesh that you can then render.

If you don't have a lidar, perhaps you have a number of cameras that are taking pictures of the same object and you wish to reconstruct the 3D representation of the object from the 2D views of each camera.

In these cases, the connection between DT and the result is obvious: We have a set of points and we would like to find the surface they are likely to define.

But, there are other applications where the "summarisation" is more pronounced.

Say for example that you want to do object recognition that is independent from scale or resolution. You take a camera, shoot a picture and then obtain some set of descriptors off of the object.

The descriptors are simply a cloud of points with specific geometrical relationships between them. Whether you shoot the object up close or from (reasonably) far away, these relationships will be preserved.

To summarise these points, you might want to use DT. In fact, it is used in face recognition or similar pattern recognition and shape-based retrieval applications as a descriptor of a set of points. In those, the DT is not just a way of connecting the points together but because of its properties (such as the minimal angle mentioned before) it can also be used to extract features from the resulting DT.

The VD has had applications in image compression. The main idea there is that you are trying to represent a large area of homogeneous (or approximately homogeneous) pixels with the value of a single "dominant" pixel. So, instead of storing $M \times N$ pixels, you store a set of key point positions and their colour and reconstruction involves obtaining the VD of the set of points which is now "painted" with the pixel colours.

Here (or here) is an example of that.

The artistic aspect of VDs (or DTs) applied to images is a consistent fad, it comes back again and again, you basically reduce the amount of triangles drastically and it creates a sort of "stained glass effect" on the whole image.

Hope this helps.