It took me the whole summer but the lecture notes for Vector calculus are now online. They have been fully transcribed, edited, illustration added. There is certainly a lot of work left to make them more presentable, readable, etc. That will continue along with linking, internally and to the rest of the site. As a part of this work I’ll try to add something that I feel is missing – the discrete angle (image analysis, data analysis, etc).

The total number of articles has reached 446, with 1208 illustrations. There is some duplicate content but not a lot. The point is that one can take this material, rearrange it in a number of ways, and create various courses depending on the goals, or the audience, etc.

Still to come are the two courses I am teaching this fall: Calculus 1 and Differential Geometry. They will be transcribed some time next winter. More courses will continue to appear as a part of what I call my “fantasy math” project.

The summer is over and it’s time to report on some of the events. In the beginning of summer I made page for 3 potential NSF REU projects. These are the two that I ended up supervising:

• The Topology of Data by Joseph Snyder, and
• 3D Image Analysis by James Molchanoff

The topic of the REU was computational science so the general goal was to do something new computationally while learning some math. So, we used and modified some existing software. The main idea of the first project is to use jPlex to compute dimensions of datasets while the main idea of the second was to use CHomP to compute the homology classes of 3D images along with their persistence. Ironically, jPlex computes persistent homology but lacks relative homology which had to be implemented. On the other hand, CHomP has relative homology but the persistence had to be implemented. These issues were mostly resolved. Unfortunately, in either case there wasn’t enough time to test the programs with real-life data.

To be continued…

One of the most basic methods of analyzing gray scale image is to find the pixels area of high contrast. These areas are likely to be where an object ends and the the background begins.

More precisely, these are the areas where the change of the gray – for light to dark or dark to light – is the fastest. Then one needs a threshold so that all pixels where this change is higher that this number are considered “edges”:

Mathematically, we deal with

 the rate of change of the gray level

             = the gradient of the gray scale function.

(In fact, one only needs the norm of the gradient.) Computation of the derivative however in the digital (discrete) context is a challenge as it is severely affected by noise. Consider the image of coins and its version with noise added.

If now edge detection is run, the results are unsatisfactory – too many irrelevant contours. 

Of course it may be possible to filter out the smaller contours. In this particular case it’s impossible because they are parts of large ones. In fact they form large fractal-like structures. This is the reason why edge detection may have to be preceded by smoothing of the image.

Read more…

Under Review summary (in Output tab) Pixcavator shows the data about the objects found in the image. Pixcavator displays the total area of dark and the total area of light objects – as percentages of the total size of the image (second row).

Under certain circumstances though, the contours of the same kind may be “nested” and, as a results, these percentages may be wrong or even above 100%.

Example below (measuring grass coverage): the dark shows the 151% coverage.

The number is certainly meaningless (there will be a warning about that in the next release).

Why is it above 100%? Because the area is covered several times by these objects. If you click “Color objects”, you’ll see one large object with red contour and many others inside of it.

What happens is easier to see in this simpler image:

The results of image analysis may considered “good” here, but only in the sense that we have captured some 3D information. In general, we restrict our attention to image with mostly 2d information (see Images appropriate for analysis).

What exactly happens here? The way Pixcavator’s sliders operate is this: the contour is allowed to grow until its size (or contrast) is over the bound set by the corresponding slider. Practically, this means that each potential contour C is compared to a contour C’ corresponding to the previous gray level. Then, if C passes but C’ does not then C is plotted.

For more, see Nested boundaries.

In the last post I discussed some issues you encounter when you want to evaluate vegetation coverage based on image analysis.

Now, the area covered should be just a step towards what we are really interested in – the height of the vegetation (or volume, even better).

Let’s consider how one can compute the height of vegetation from a digital image. The idea is very simple:

 the average height = the area / the width.

Consider now what we see in the image.

Views from a side (vegetation in green) and from above:

Assumptions:

1. The board is a square and its dimensions are known.
2. The board is vertical (otherwise it’s impossible to know where the bottom is).
3. The bottom of the board is horizontal on the horizontal (along the board) ground.
4. The field of view of the camera includes the edge of the vegetation and the top of the board.

Then, the average height computed as below is independent from:

• the deviation of the angle of the camera from the horizontal,
• the distance from the camera to the board,
• the height of the position of the camera above the ground.

The measurements (the image in black, the bottom of the board in red):

These come from image analysis:

 A = the area of the board visible above the vegetation (sq pixel),
 W = the width of the board (pixel).

This is known:

 S = the length of the side of the board (in).

Then average height of the vegetation above the ground (in) is:

  H = S * (1 - A / W2).

Computations here.

The full name is REU Site: Computational Science Training at Marshall University for Undergraduates in the Mathematical and Physical Sciences (PI Howard Richards). REU stands for “Research Experiences for Undergraduates”. The grant was just approved b the NSF but the application dealine in April 9. If you know anyone who might be interested, encourage them to apply. This is the website: http://www.marshall.edu/REU/.

I will be supervising 2 students in 1-2 of these areas:

• image analysis, and/or
• image-to-image search, and/or
• topological data analysis.

Temporary page for the projects: Computational science training: 2010 projects.

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.