## Edge detection: The Scale Space Theory

Consider an image as a bounded function with no smoothness or structure assumptions a priori. Most relevant information of a given image is contained in the contours of the mapped objects: Think for example of a bright object against a dark background—the area where these two meet presents a curve where the intensity varies strongly. This is what we refer to as an “edge.”

Initially, we may consider the process of detection of an edge by the simple computation of the gradient This gradient should have a large intensity and a direction which indicates the perpendicular to the curve. It therefore looks sound to simply compute the gradient of and choose the points where these values are *large*. This conclusion is a bit unrealistic for two reasons:

- The points where the gradient is larger than a given threshold are open sets, and thus don’t have the structure of curves.
- Large gradient may arise in certain locations of the image due to tiny oscillations or noise, but completely unrelated to the objects being mapped. As a matter of fact, there is no reason to assume the existence or computability of any gradient at all in a given digital image.

## Voronoi mosaics

While looking for ideas to implement voronoi in `sage`, I stumbled upon a beautiful paper written by a group of japanese computer graphic professionals from the universities of Hokkaido and Tokyo: A Method for Creating Mosaic Images Using Voronoi Diagrams. The first step of their algorithm is simple yet brilliant: Start with any given image, and superimpose an hexagonal tiling of the plane. By a clever approximation scheme, modify the tiling to become a voronoi diagram that adaptively minimizes some approximation error. As a consequence, the resulting voronoi diagram is somehow adapted to the desired contours of the original image.

(Fig. 1) | (Fig. 2) | (Fig. 3) | (Fig. 4) |

In a second step, they manually adjust the Voronoi image interactively by moving, adding, or deleting sites. They also take the liberty of adding visual effects by hand: emphasizing the outlines and color variations in each Voronoi region, so they look like actual pieces of stained glass (Fig. 4).

## Image Processing with numpy, scipy and matplotlibs in sage

In this post, I would like to show how to use a few different features of `numpy`, `scipy` and `matplotlibs` to accomplish a few basic image processing tasks: some trivial image manipulation, segmentation, obtaining of structural information, etc. An excellent way to show a good set of these techniques is by working through a complex project. In this case, I have chosen the following:

Given a HAADF-STEM micrograph of a bronze-type Niobium Tungsten oxide (left), find a script that constructs a good approximation to its structural model (right).

Courtesy of ETH Zurich

For pedagogical purposes, I took the following approach to solving this problem:

**Segmentation of the atoms**by thresholding and morphological operations.**Connected component labeling**to extract each single atom for posterior examination.**Computation of the centers of mass**of each label identified as an atom. This presents us with a lattice of points in the plane that shows a first insight in the structural model of the oxide.- Computation of
**Delaunay triangulation**and**Voronoi diagram**of the previous lattice of points. The combination of information from these two graphs will lead us to a decent (approximation to the actual) structural model of our sample.

Let us proceed in this direction: