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 here is a big future here. 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.

Download the new version or first read a bit about the background. 

Besides a few minor improvements, the main novelty is more ways to change the analysis settings. There are six sliders now.

As before we have two sliders for the two main measurements – size and contrast. Now, the confusingly named “Max growth rate” has been remade into “Border contrast”. What does it mean? Both this and the second slider consider the difference in intensity inside the object from that of the surrounding area. But, while the contrast slider considers the maximal difference throughout the object (that why it’s now called Max contrast), the border contrast slider looks at the area just inside the contour. The result is about the same as before: it detects sharp edges, i.e. the contours with the largest difference between what’s just inside and what’s just onside of it.

The next slider works similarly but takes into account the average difference in intensity inside the object from that of the surrounding area. It’s called Average contrast.

The last two sliders simply threshold the image. For example, if you set Intensity, dark to 100, the contours of dark objects will the intensity equal to exactly 100. If you set Intensity, light to 100, the contours of light objects will the intensity equal to exactly 155 (here 155=255-100). It was set this way in order to ensure that contours grow as you move any of the six sliders from left to right. This is a very unsophisticated tool but it’s quite effective when the image lighting is uniform.

The need for introducing these new tools came from a specific, real life image analysis task: Measuring staining in the liver.

Reminder to the current customers: you can download the new version and activate it with your current serial number.

Reminder to the rest: the new price $195 won’t become effective until June 15.

Tracking objects in a video is easy to illustrate with this demo (click the link, a screenshot with explanation is below). The demo comes from an old version of Pixcavator. That “universal” prototype contains the backbone of the current Pixcavator IA, a morphological analysis application (I’ll write about that at some point), and the motion/object tracking application. The program finds objects in each frame of the video but also tells you which ones reappear in the next frame. Both merging and splitting is captured. As a result an object that passes “behind” another is treated as if it is merged. This is not what you expect from object tracking but it actually makes sense: remember there is no “behind” in 2D! To get true tracking one would need to incorporate some image/object matching as well. The program also has other Pixcavator-like features: ignoring objects that are too small or ones that disappear too quicky. It is fairly fast.

The old price, $150, has been the same since August 2007. The new price is $195. It will come into effect in June. Bulk discounts will also be introduced.

This image analysis example came from a biomedical researcher: “I would like to know if the program can calculate relative areas and analyse differences in immunostaining intensity… In images 1 and 2, I need to know if Pixcavator can convert image 1 in 2 and then in image 2 giving a percentage of the are in red in relation to the all field. In image 3, I need 2 things (it is an immunostaining of the liver). I need to know if the program can give me a level of intensity of the immunostaining (that is the intensity of brow in the image) and secondly the fraction of the area that is immunostained (i.e., brown coloured).”

After a few minutes of experimenting with Pixcavator, this is best I can do for now (screenshot #1 below). As you can see some of the red area is not captured while some holes are counted (#2). To find area of those holes I had to analyze the image with different settings (#3). So, the total area of the red is approximately:

10864+3501+1426+2103+1746-1477-1453 = 16710.

Then the percentage is

16710/(853×640) = 3%.

Unsatisfied with the result, I modified the software: I used thresholding as the 2nd slider instead of contrast and redid the analysis. The result was 5.51-1.65=3.86%, much better. 

The third image was trickier because the lighting is uneven. Initially I was unable to capture all brown areas - not simultaneously. Certainly, cropping the image and analyzing parts one by one is an option. (The average color, it is displayed for each contour under “Gray” in the Pixcavator’s output table). That’s something to keep in mind: what is displayed is the average intensity with respect to the color channel that you’ve chosen, in this case “Green”. (The ability to compute the average color with respect to all three channels is still under development.)

Unsatisfied with the result, I came up with another modification: I used average contrast for the 2nd slider and redid the analysis. The result was much better. The average gray (intensity in the green channel) was 132.

The two modifications will appear in version 4.2 due in June.

This version has only one new feature: the analysis is precomputed. The result is that moving sliders produces immediate effect on the contours and finding the best contours becomes very quick. You can see the effect in this video. The analysis stage is however quite longer than in the previous versions. So, before making this feature permanent I want to get some feedback from the users. That’s why this is just a test release.

The link is to a poster presentation made at the last meeting of Association for Research in Vision and Ophthalmology (ARVO) by Dr. Nalin Mehta. The title (shortened) is Evaluation of Choroidal Circulation Using Collapsed C-Scan Imaging. The goal is “to better differentiate between the various components and sub-types of age-related macular degeneration”. Further:

En face (C-scan) OCT images, collapsed and summated in the antero-posterior axis, were acquired for all patients over approximately monthly intervals throughout their treatment regimen. These images were standardized and analyzed using Pixcavator 3.1 (Intelligent Perception Co., Huntington, WV), an image analysis program which first captures the contours of the choroidal vascular pattern, differentiating the same from background scatter phenomenon, and then quantifies this pattern in proportion to the entire scanned area, producing an Excel (Microsoft Corp., Sacramento, CA) spreadsheet with locations and measurements of these vascular structures.

Before this became possible some challenges of image analysis had to be confronted: article in the wiki.

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 was about to review the newly released Google Similar Image Search when I ran across this one. The verdict: not so good.

The guy does not seem to realize though that Microsoft released its own similarity search a few months before. I am not judging because I missed it myself when it came out. It would be interesting to test and see which one is better (or not as bad). One point in favor of Microsoft is that Google didn’t index all images.

UPDATE: Another good revew at Rich Marr’s Tech Blog.

The idea is to examine the sizes of pores in the microscopy images (on the right), derive the permeability of the material from that data, and then compare to experimental results.

The image analysis was done manually (they call it “direct analysis”) and then with Pixcavator: “The values estimated by the “Pixcavator” program were based on the area estimation via integrating the number of pixels in this area.”

The comparison table is below.

The correlation looks good.

Other examples of image analysis.

Download here. Recent examples here.

The main changes are the following.

First, an annoying bug in the user interface was fixed. I don’t want to remind everybody what it was but I do certainly apologize. A few minor bugs were fixed too.

Second, a new slider “Border contrast” replaces the old. The idea is that by moving it you can jump to the nest sharp border. For example in the image below, the change in the gray level is very gradual. So, if you move the slider “Size” or “Contrast”, the growth is very slow and the former won’t even notice the sharp edge. With the new slider you get there is just a few abrupt steps: border contrast = 0, 10, and 15, respectively.

To our current customers. You can download the new version of Pixcavator and then activate it with your current serial number. This amounts to free upgrades for a foreseeable future.

BTW, the first digit in the version number refers to the calendar year of the development. This is the fourth since version 1.0 appeared in August ’06 (a prototype/testing program was created in the summer of ’05).

Finally our plans for the coming months:

• 4.1: Introduce a way to fully pre-compute all data (not only the construction of the topology graph but also and its analysis) so that moving sliders will change both the contours and the sliders virtually instantly.
• 4.2: Speed up the core algorithm (construction of the topology graph) significantly. I think its complexity will be linear instead of the current quadratic.
• 4.3: Introduce more data filtering tools (beyond unmark dark and light objects).

I’d be glad to hear your suggestions.

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?

  

Photoshop CS4 from Adobe Systems is a powerful image and photo editor but not a tool for scientific image analysis.

The software has a huge multitude of tools for image processing (and, of course, photo manipulation). There is no point in listing them here. The “extended” version also has a few fun features like auto-blending or content-aware scaling.

However, its image analysis capabilities are very limited. After searching for a while, just these two below all I found:

Use selection tools to define and calculate distance, perimeter, area, and many other measurements. Record data points in a Measurement Log and then export the data, including histogram data, to a spreadsheet for further quantitative analysis.

Easily and accurately tally objects or features in scientific images with the Count tool, which eliminates the need to perform manual calculations or rely on visual assessments of changes from image to image. Save even more time by performing multiple counts in a single image. Use separate colors for each count and save your counts in the file.

Adobe Photoshop CS4 Extended is priced at $999.

Over the last few months I have been contacted by many individuals and companies asking for help with their image analysis task or to evaluate the suitability of Pixcavator for them. I decided to pull some of these exchanges for my correspondence and present them to the public in the wiki under Case studies. The anonymity of the users is of course protected. There will be more examples.

From other news, I started to use Twitter (ID PeterSaveliev) to announce new posts for this blog as well as some short notes on the same subject. We’ll see how it goes…

I also decided to change, in part, how this blog is maintained vis-à-vis the wiki. In the past, a blog post would appear first. Then after a while, it would be turned into an article or articles in the wiki. Now I’ll start writing an article first and when it is sufficiently mature, I’ll post it in the blog. The news will appear as before

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.