Most of the recent content has come from two main sources. First, I have been adding, as before, examples of image analysis from the users of Pixcavator. The second is the course I’ve been teaching since last fall: Introductory algebraic topology. I plan to add more content from the courses that I teach: Vector calculus (this summer), Introductory differential geometry (next fall), and maybe also something of lower level like Calc1 (next winter).

What is the goal? I would like the site to cover a big chunk of the math curriculum, interlinked within and with the computer vision / image analysis topics (see The Mathematics of Computer Vision). Even though the format is identical to Wikipedia the presentation is very different. This is a textbook: more details, more examples, exercises, etc. It can still be used for reference.

The content comes directly from my lectures. I use Tablet PC with Windows Journal. I started doing this last fall and I really love the results: bright, colorful slides, but with the spontaneity and flexibility of a chalkboard. Later I transcribe the lectures into text, put it on the site, and simply copy the illustrations. (Plus, I don’t have to deal with chalk on my shoes, pants, and lungs!) I think this approach has huge advantages over the common practice of simply posting video lectures online: searchability, cross-linking, speed of download, the person can read and work at his own pace, etc.

Q: We need to “measure all the seedlings area (by dividing by the number of them I can get indication to their area and structure, and other parameters I can get)… The area covered is 80*80cm.”

The screenshot shows the results of my experiment. Here the red contours surround the darker areas (vegetation) and green surround the lighter areas inside. So, the total coverage is 60 – 9 = 51%. Unfortunately, I was unable to separate the seedlings from the rest of the vegetation.

There is also work with ecological researchers to measure vegetation coverage but mostly with horizontal shots.

Other examples of image analysis

Q: We “need to verify the internal diameter, external diameter and the wall thickness between the ID, OD and the reinforcement yarn. One issue we have is that the wall is not always concentric. We have a minimum wall thickness specification so we would like to measure the wall thickness at the thinnest point to determine if it meets our spec or not.”  

I analyzed one of the images. I found fairly good contours that capture the inner (red) and outer (green) borders of the hose with the settings that you can see in the screenshot. The measurements for this contours can be seen in the Pixcavator’s output table.

The area inside the red contour is 130,966. Assuming this is a circle, the area is equal to π*R², so the radius is

 R = √(130,966/3.14) = 204 pixels.

Then the external diameter is 408 pixels (one would have to do calibration at this point to convert to inches).

The area inside the green contour is 96,595. Assuming this is a circle, the radius is

 R = √(96,595/3.14) = 175 pixels.

Then the internal diameter is 350 pixels.

This suggests that the thickness of the wall should be 204-175=29 pixels. This is the average thickness of a ring with these measurements. To verify this number one can drop the assumption that these are circles and use the perimeters of the contours taken from the output table. Then

 average thickness
   = (area of the wall)/(average perimeter)
   = (130,966-96,595)/((1,547+1,283)/2)
   = 24 pixels.

A similar computation is presented here: Wall of a blood vessel.

Other examples of image analysis

Below is the abstract of a paper I am working on.

Suppose we have conducted 1000 experiments with a set of 100 various measurements in each. Then each experiment is a string of 100 numbers or simply a vector of dimension 100. The result is a collection of disconnected 1000 points (aka point cloud) in the 100-dimensional Euclidean space.

It is impossible to visualize this data as any representation that one can see is lim

ited to dimension 3 (by using colors one gets 6, time – 7). Yet we still need to answer the same questions about the object behind the point cloud: is it one piece or more? Is there a tunnel or a void? And what about possible 100-dimensional topological features?

This is a common approach to the problem.

For a point cloud in a euclidean space, suppose we are given a threshold r so that any two points within r from each other are to be considered “close”. Then each pair of such points is connected by an edge. If three points are “close”, we add a face, etc. The result is a cell complex (more precisely, simplicial complex) that approximates the manifold M behind the point cloud.

We want to count the number of topological features in M by means of the Betti numbers: the number of connected components in M, the number tunnels, the number of voids, etc. This information is contained in the homology of the complex.

Further, to deal with noise and other uncertainty one needs to evaluate the significance of these topological features. For each value of the threshold r we build a separate cell complex, then combine the homology groups of these complexes in a single structure, and count the features with a high measure of robustness. This measure, called persistence, is the length of the interval of values of r for which each of the topological features is present.

Even more important than these “global” properties may be the local topology of the data. For example, in both of the images above the datasets are 3-dimensional but what’s behind is 2-dimensional (surfaces). This is called dimensionality reduction.

Most of the links here are dead but the article will be fixed by the time I am done with the topology course.

A more detailed outline is here: Homological methods in manifold learning (warning: heavy math).

This fall I have been teaching Topology I (Topology II next spring). I decided to emphasize algebraic topology and in fact started with it rather than point set topology which alone can take two semesters.

Outline
This is an introductory, two semester course on algebraic topology and its applications. It is intended for advanced undergraduate and beginning graduate students.

Part 1. Introduction to algebraic topology
Starts with topological issues in digital image analysis, informal introduction of homology

Part 2. Homology theory
Cubical complexes, their homology, and maps

Part 3. Overview of point-set topology
Minimized to the extreme (still could have cut even more)

Part 4. Homology groups
A more formal, group theory based, exposition

Part 5. Homology and uncertainty
Applications in computer vision, image analysis and data analysis

Part 6. Beyond homology
The fundamental group and cohomology

Also, I ran across this white paper from Hewlett-Packard: Algebraic topology for computer vision. Good review and an honest attempt to convince the practitioners to that this is something that they might need to know (good luck with that!).

I took this image analysis example from the site of Able Image Analyzer. It was easy to reproduce the results with Pixcavator.

Setting the contrast slider at 100 gives you good contours for both Sicily and the calibration bar. The length of the latter is see to be 217 pixels, so

 217 pixels  = 250 km.

The are of Sicily is see to be 18884 pixels, so

 the area = 18884*(250/217)^2 = 25064 sq km.

(Here 250/217 is the calibration factor). The actual area is 25706, so the error is about 2.5%.

 See other image analysis examples.

Wikipedia’s article lists image analysis software in the form of a table. The columns are:

• Product  
• Developer 
• Cost (USD) 
• Open source 
• Software license  
• OS 
• Continuous 
• Industries, Uses and Applications

I thought that the type of license, open/closed source, OS, etc aren’t very interesting, while some more important, in my view, data should be added. Based on the inspection of the vendors’ sites, I tried to answer the following questions.

What is the price? In the absence of that information, I put $$$$ indicating that the price might be in the thousands.

Is there a free version available for download? Companies with $$$$ usually don’t have that.

Does the site provide examples of how the software has been used for image analysis? Very often, surprisingly little is provided.

Does the site reveal the methods/algorithms behind the software? Commercial vendors say nothing. Open source certainly qualifies for Yes in this category but most of the time the source is all you get. The actual math, algorithms, errors, etc are ignored.

To see the new table follow this link: Image analysis software.

From simplicity comes complexity. And beauty!

This is an example of “electron micrographs of biological membranes containing proteins. We need to get as much as possible information about the particle size, shape, clustering, crowdiness, etc.”

I ran Pixcavator with both images. The quality of the first one is much better and so are the results. The particles are captured quite well and with a couple minutes of trial and error they could be even better. Once the contours are found, the information about sizes, shapes, locations is provided (table on the right). The results for the second image are less encouraging. The shadows are just too large relative to the sizes of the particles so that their borders aren’t well defined. The result might still be OK for counting, as well as locations and distances.

You can find all info about the table in this article Pixcavator’s output table. Some examples relevant to this task are here Particle and cell analysis.

“Can the histograms of the size/diameter distributions be calculated?”

Yes, but only via Excel (another example: Measurement statistics of fibers). The table contains the centers of mass of all particles and one can easily compute the distances between them (if you want to treat the particles as circles, you subtract their radii). Also, the Voronoi diagram is intended exactly for such a problem.

A much simpler, but cruder, way would be to assume that the particles are evenly distributed. You can compute the average distance by looking at the density of particles (number of particles / the area of the image). Also you can think of them as circles, then, for example, if you have 100 particles in a 100×100 image, the average distance to the nearest neighbor is 10.

For clustering, I did some work with the data. Instead of dealing with a fairly complex geometry of Voronoi diagram, I implemented a very simple statistical computation, with Excel: the distribution of the distance to the nearest neighbor. The spreadsheet is here. The Excel work was awkward – for example I had to transpose a column. I wish I knew Excel better to come up with something more straightforward. The result seems to make sense:

Other examples of image analysis

A request came from a researcher who wants to “analyse images from optical microscopy of surfactants. Those images have a hair of known thickness in order to obtain an idea of the real dimensions involved… The hair’s thickness is 0.045 mm.”

I did some preliminary work. First you need to convert pixels into millimeters. I re-analyzed the image. I had to add a black border to the image. This is a way to capture a light object that touches the edge of the image (another is to invert the colors).

and the thickness of the hair is 23 pixels. So, 23 pixels = .045 mm, or 1 pixel = .045/23 = .002. This is the conversion factor (aka calibration factor). I inserted it at the top the output table. On the right you see two new columns – they are the sizes and the perimeters converted into mm.

One would have to repeat the analysis of the hair thickness for all images though, unless all pictures are taken at the same distance and the hair is the same. If these images are taken from the same distance, you need to do the calibration only once and then use the same conversion factor for all of them. Another good new is that the conversion procedure will work equally well regardless of 10X, 5X etc magnification that comes from the microscope.

See also other examples of image analysis

Topology is usually defined as the science of the spacial properties that preserved under continuous transformations. So that you can bend, stretch and shrink etc but not tear or glue. This might be the only way to capture the essence in a single sentence but this sentence is meaningless to a person who knows nothing about topology. And the question “Why do we need to study topology?” still remains.

So, we start with examples instead. They come from three seemingly unrelated areas: computer vision, cosmology, and data analysis.

Computer vision

In industrial settings one might need to consider the integrity of objects being manufactured.

The first question may be: this is a bolt holding two things together, does it still or is there a crack in it?

Could be a bone too…

The second question may be: this material is supposed to hold liquid, is it water tight or is there leakage?

In other words: does it hold water?

The third question may be: to be strong this alloy is supposed to be solid, is it or are there air bubbles?

The opposite question is: does it hold air?

Observe that we consider here three different kinds of integrity as there may be a crack but no hole or vice versa etc.

We can describe these situations informally as:

• there are cuts in the object,
• there are tunnels,
• there are voids.

These three types of “damage” correspond to cycles of dimensions 0, 1, and 2 respectively. This is why:

• The simplest object with a “cut” is two points and points are 0-dimensional.
• The simplest object with a “tunnel” is a circle and curves are 1-dimensional.
• The simplest object with a “void” is a sphere and surfaces are 2-dimensional.

Cosmology

What is the shape of the universe? What is the topology? Does it have “cuts”, “tunnels”, or “voids”?

Read the whole article.

Taking two images of the same scene from two slightly different locations and then matching the items in them pairwise gives you the distances to these items.

The image matching part is crucial and less trivial. For example on the right the corner of the cube may be a good pixel to choose. The rest of image is mainly featureless. The geometry is trivial, below.
Suppose we established a match between a pixel P in image I and pixel Q in image J. Let’s find the distance to what the pixels depict.

Two images with a red pixel in each image representing the same thing:

We need only to consider only the horizontal line through P,Q to find the distance to the object with the red dot. View from above; the eyes are the foci of the cameras. Black lines are the images:

“Triangulation”: the object lies on the line from the focus of the camera and its mark on the image. Here the big red dot is the actual location of the object:

The geometry:

D is what we are looking for.

The pink, and the blue, triangles are similar. So, after a bit of algebra we have:

where d=x+y is simply the distance the pixel moves as we switch from one image to the other, called the disparity.

More details in the article.

TechCrunch deadpools Riya. Certainly, no surprise to me. Their technology was never been impressive (posts are here). Like.com remains but does not seem to be going anywhere…

At least TechCrunch announced this death after promoting Riya for 3 years. Others have died or will die more quietly.

I gave a talk at the WORDCOMP conference in Las Vegas, specifically IPCV’09, International Conference on Image Processing, Computer Vision, and Pattern Recognition. Here is the slides with comments. It also makes sense to look at the paper the talk came from.