Prof. Marian Mrozek  was kind enough to inform me about the coming update of CHomP in his email that I quote below:

The power of the software comes from much newer algorithms. Some of them are described in the papers:

• M. Mrozek, P. Pilarczyk, N. Zelazna, Homology algorithm based on acyclic subspace, Computers and Mathematics with Applications, 55 (2008), 2395 –2412.
• M. Mrozek, B. Batko, Coreduction homology algorithm, Discrete and Computational Geometry, 41 (2009), 96-118.
• M. Mrozek, Cech Type Approach to Computing Homology of Maps
  Discrete and Computational Geometry, accepted
• and a few more which are just in preparation.

We just finish[ed] writing a new, much stronger version of the software which will accept not only cubical complexes but also simplicial complexes and general CW complexes and will produce broader output, in particular homology generators, homology maps and persistence intervals for filtered complexes.

The new version of our software at first will be available from the webpage
of our CAPD group at Jagiellonian University, Krakow, Poland:
http://capd.ii.uj.edu.pl/.

Take a look also at our Homology Software page.

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 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!).

From simplicity comes complexity. And beauty!

I added a list of recent customers of ours here.

I also created a page for the course I am teaching: Introductory algebraic topology. The outline is there already and some of the articles have been written. The second one is Homology as a equivalence relation. Consider the question, What is a tunnel? It’s not as simple as it seems. It takes some work to find a good answer, the main part of which is: A tunnel is an equivalence class of closed surves.

Over the following months (it’s a two semester course) I’ll keep adding material as the course progresses.

I am also teaching Advanced calculus and some of this stuff will also find its way into the wiki.

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.

I spent two weeks attending lectures (three every weekday!). It was the IMA New Directions Short Course Applied Algebraic Topology at the Institute for Mathematics and Its Applications at the University of Minnesota. The main focus was on how the methods of algebraic topology can contribute to data analysis. I am quite certain that there is a big future here (in fact, I’ll add article Topological data analysis to the wiki soon). Sensor networks, robotics, and dynamics were also discussed.

The main link with all the lectures is this: http://www.ima.umn.edu/2008-2009/ND6.15-26.09/. Another good site is due to Gunnar Carlson, one of the organizers. It is called TMSCSCS: Topological Methods in Scientific Computing, Statistics and Computer Science. A lot of interesting preprints here as well as jPlex, the software that actually does the computations that we discussed. There is also a Wikipedia article. A Google group was formed by the participants.

I am working on a paper that will summarize my views on this stuff, as it fits both data analysis and computer vision…

Next for me is the WORDCOMP conference in Las Vegas, July12-17. I’ll be giving a talk at IPCV’09, International Conference on Image Processing, Computer Vision, and Pattern Recognition. It will be based mainly on the last paper of mine.

The full name is IMA New Directions Short Course Applied Algebraic Topology. It is run in the Institute for Mathematics and Its Applications located on campus of the University of Minnesota.

I attended another IMA short course in 2004. The course was called Computational Topology and it changed the direction of my research. Until then my interests were in algebraic topology and fixed point theory. After the course I became convinced that algebraic topology would have serious industrial applications. It took me another year to find my personal interest - digital image analysis.

The main focus of the current course will be on how algebraic topology can contribute to methods of data analysis. This topic is of special interest to me as I am also working on image-to-image search applications.

I started writing the article for “Pixel” and the word certainly has multiple meanings…

1. A location within the image: two coordinates.
2. A location and its value: 0 or 1 for binary, 0-255 for gray scale, 3 numbers for color.
3. A little square/tile (see Cell decomposition of images).
4. A unit of length.
5. A unit of area.

More important is to keep in mind while analyzing images this simple principle:

This is important in two ways.

First, as the resolution increases the analysis results should “converge” to the analysis results of the real scene depicted in the image. Because the world is analog (another good principle).

Whatever the “real” (or physical) object is depicted in the image, its area computed as the sum of pixels will be as close as we like to its “true” area as the resolution increases (for more rigorous interpretation [1]). See the pictures below.

This is not that simple with the length. Indeed, increasing the resolution will not reduce the relative error of the measurement. See Lengths of curves.

Second, we need to analyze image in such a way that a single pixel variation of the image would be negligible. In fact, a singple round of erosion or dilation, i.e. adding or removing a layer of pixels from the border of an object, will not dramatically change the area or perimeter of an object. Why? Because pixels are small.

The original image, the effect of dilation, the effect of erosion.

         

This works fine for geometric measurements (see also Robustness of geometry) if the topology does not change. It’s not so easy for topology. The example on the right shows that adding the red pixel merges three objects and also creates a hole (white object).

Then we can say that these topological features aren’t robust. In fact the robustness can be measured in term of how many dilations and erosions it takes to change the topology. For example,

• how many erosions does it take to split an object into two or more?
• how many dilations does it take to create a hole in an object?

  

I promised to update the article about Betti numbers in the wiki. So here it is.

Betti numbers count the number of topological features in the image.

For example, in the first image on the right the number of objects is 6, so the 0th Betti number B₀ is 6. The number of holes is 2, so the 1st Betti number B₁ is 2 as well.

More generally, the 0th, 1st and 2nd dimensional topological features are:

• objects or connected components – dimension 0,
• holes or tunnels – dimension 1, and
• voids or cavities – dimension 2.

These numbers in each dimension are captured by the Betti numbers, B₀, B₁, and B₂. Examples are in the table below.

	B0 (parts)	B1 (holes)	B2 (voids)
Letter O	1	1	0
Two letters O	2	2	0
Letter B	1	2	0
Donut	1	1	0
Tire	1	2	1
Ball	1	0	1

 

 The tire (torus) has two tunnels represented by these two “cycles”.

 

 

 This cycle is trivial and not to be counted.

In practice, i.e., computer vision and image analysis, you can’t count topological features. Instead you count “cycles” that capture them. Counting 0-cycles and 1-cycles in 2D is fairly simple.

Let’s now consider 1-cycles, i.e., circular curves, in 3D. In the torus, there are two kinds of cycles: the latitudes (one is red) and the longitudes (one is blue). The latitudes capture the tunnel inside the tire while the longitudes capture the tunnel through the tire.

Clearly there are many cycles that capture the same topological feature. So, how do you avoid overcounting them? The answer is: if two cycles are homologous to each other, they are counted as one.

One way to explain homology is this. Two cycles are homologous if they together form the boundary of a surface.

For example, any latitude is homologous to the red cycle because they are the two ends of a tube cut from the tire. Any longitude is homologous to the blue cycle because they are the two edges of a strip cut from the tire. This is why B₁ = 2.

In the sphere the blue cycle is homologous to a point, a trivial cycle, that’s why B₁ = 0. Another way to see that it is trial is to imagine how it can contract to a point like a rubber band. The same thing happens with the donut.

Betti numbers are combined together (as the alternating sum) to produce the well-known Euler number (aka Euler characteristics).

BTW, B_n = rank H_n.