As I have mentioned before, I am at the initial stages of writing a book on elementary computer vision (see part 1, part 2,  and the wiki). After Digital Image Processing Using MATLAB by Gonzalez, Woods, and Eddins, another one to consider is Computer Vision by Shapiro and Stockman.

In my last paper, I made a comment about topology of binary images: “These issues have been studied over the last 100 years or so and they are well understood”. It was pointed out to me that digital image analysis didn’t start until the 1960s, so how come?

Let me set the record straight.

The history is this. Algebraic topology was founded by Poincare around 1900 (the title of his book “Analysis Situs” converted from Latin to Greek turns into “topology”). There was no talk about binary images, obviously. What they studied was cell complexes, collections of cells attached to each other in an appropriate way. The cells were initially only triangular but later of any shape. It was also informally assumed that all topological theorems are independent of the cell decomposition or representation. This fact was formally proven by the 1950s, roughly. By then all the issues had been settled and algebraic topology had become one of the central disciplines in mathematics. The fist monographs were written in the 1930s (Alexandroff&Hopf) and first (graduate) textbooks were written in the 1960s (Hilton&Wiley, Mac Lane, Spanier, and many more).

Undergraduate books are rare (one that I like the most and use is Theory of Surfaces by Kinsey). Courses are even rarer. As a result, computer scientists (and even mathematicians) are often unfamiliar with the well established ways of dealing with even the most elementary topological issues (and I mean really elementary: how many objects, which ones have holes or tunnels and how many, etc.)

Even though relevant papers pop up once in a while, the connection of image analysis to algebraic topology is not a common knowledge among practitioners of computer vision and image analysis. I know this from personal experience…

The main reference on the subject is Computational Homology by Kaczynski, Mischaikow, and Mrozek. This is still very much a graduate text. Hopefully, our wiki is more accessible.

Soon after version 3.2, the next one is here. There are a couple of changes.

First, a feature was added to help with image exploration. As you move the mouse around the analyzed image, the object you hover over is highlighted. The contour is shown blue and, if “Color objects” is chosen, the whole object is colored. The data about it is displayed under the image as before.

Second, the limitations on the kind of objects to be captured have been removed. To avoid dealing with excessive number of objects in the image and the spreadsheet, only objects with “saliency” above a certain threshold were taken into account and displayed. There have been no complaints about that until recently. A manufacturing company needs to analyze an 1000×2000 image which is almost all black with a few light dots here and there (1-3 pixels in size). In the new version even objects this small will be captured. However, the number of objects will be limited to 1000.

This is a question that has been asked many times over the last few months. The answer is always positive but some things need to be clarified.

If you need help with your images, there are three main options.

Option 1. I analyze the image myself.

There are some choices to be made about the analysis settings however. Then I’d have to base my decisions on common sense without any understanding of the problem. For example, I may try to capture the most prominent – large, high contrast, round, etc - features in the image and ignore the rest. It is very easy to end up solving a wrong problem. At best, the result will be a sample of what Pixcavator can do.

For more meaningful results, therefore, the image should be analyzed by a person who knows that he needs to find in the image.

Option 2. The user analyzes the image.

To find the right settings, a fair amount of trial and error may be needed. Fortunately, Pixcavator is very easy to learn. As the user can start experimenting with Pixcavator, he will quickly come to understand the affect of moving the sliders on the development of the contours.

There is a danger however that the settings that have been found won’t work for the next image.

Option 3. The user describes what he wants to find in the image.

Then I can base my analysis on this description. However, I am likely to be unfamiliar with the terminology of your field and can’t tell what you are looking for based solely on your verbal explanations. For this approach to work, the description will have to be very specific and include the sizes, shapes, colors, locations of objects to be found in the image.

Alternatively, you would provide me with a few images that have been analyzed manually. For this approach to work, the user will have to outline in the image the features he is interested in (example below). Then I would try to reproduce your results with Pixcavator. Then, if this works, I would try to apply the analysis to other images.

Keep in mind that it is always possible that the image is too complex or of too poor quality for a meaningful analysis.

The latest version of our image analysis software is out!

Pixcavator was initially designed primarily for counting: cells, objects, and other features. Everything is designed around this task: the clickable contours, the spreadsheet, the averages of the measurements, etc. Now, more and more often we see Pixcavator used for measuring. The reason is simple. Manually measuring the area, or perimeter, of a complex object is close to impossible even if the image is clear and the object is has well defined borders.  A medical example is here and another one here.

Pixcavator captures contours of all objects – light and dark - and displays all their measurements. If, however, there is just one object but with a few holes, it is important to see that this data gives you the area of what’s inside the contour. What you frequently need instead is the area of the object,  which is

the area of what’s inside the contour - the areas of the holes.

The main new feature in version 3.2 is a step in that direction. Pixcavator now displays the two numbers above - the total area of dark and the total area of light – as percentages of the total size of the image (under Review summary, second row). So, to find the area of a dark object with light holes in it, one has to subtract these two numbers. (Caution: You have to make sure however that the holes are in the object not the background).

Download Pixcavator 3.2 here.

The screenshot tells the whole story. The image of a table in the upper left corner is the query image. The rest are supposed to be “similar”. What is the image filled with numbers doing here you ask? Hmm… Oh yes, it’s a table of numbers!

Previous posts on the topic are here.

This is a new version of a paper I wrote a few months ago. It describes the algorithm behind Pixcavator.

There are a couple of issues here. The first is reflected in the new title. It was unclear to a lot of people that the topology graph isn’t a tree. To deal with that I first added 5-6 mentions of the fact that “this graph isn’t a tree”. Then I added a section called The topology graph is not a tree. Finally I renamed the paper as well. At that point I just kept rewriting. The new version is almost unrecognizable. The image below illustrates the structure of the topology graph.

The second issue is the complexity of the algorithm as a function of the number of pixels N in the image. I show that my algorithm is O(N²) in the worst case scenario - the comb image on the right. In Fast computation of a contrast invariant image representation by P. Monasse and F. Guichard, they build a graph too (that one is a tree) and claim that the complexity is O(NlogN). Their proof looked unsatisfactory so I decided to apply their algorithm to my image. Odd…

Suppose the image is not quantized so there may be N levels of gray in the image. For each level, the level curve has to be traversed (step 4a). These level curves expand from a very short to the whole comb. The perimeter of the comb is N, roughly. Then the total number of pixels to be visited is 1+2+3+…+N = N*(N+1)/2. Therefore the complexity is O(N²), not O(NlogN).

Seems clear to me but maybe there is someone who can see a flaw in this argument? What am I missing? I’d appreciate any feedback.

In a recent post I made a couple of comments about MATLAB’s choice as the software for Digital Image Processing Using MATLAB by Gonzalez, Woods, and Eddins. I listed “MATLAB is ubiquitous” as a pro and “MATLAB is expensive” and “MATLAB is good for education and possibly research, problematic for industry” as two cons. Coincidentally, there was a discussion on Hacker News centered on MATLAB. Here are some of the comments:

… designed for engineers (I mean engineers, not computer programmers) to explore matrix models interactively, then save their work as scripts - you were never meant to use m-files for general purpose programming… What you’re paying for with MATLAB is access to the Mathworks Toolboxes. If you need them then it’s absolutely worth every penny.

Matlab is, to the programmer with experience in almost any other language, a tremendous horror… That being said, if you have the mathematical chops to rearrange your problem into something solvable via matrix transformations, you can probably write it quickly and elegantly in Matlab without worrying too greatly about execution speed. Better, the built in toolboxes have already solved huge (engineering) problem spaces… Prototype the math in Matlab, implement in a language that doesn’t suck.

.. the matrix/vector/tensor core is very elegant and powerful.

You’re probably unlikely to write a real application in Matlab… when you pay for Matlab, you pay for the assurance that the implementation of the tools provided is correct and therefore your research is based on a proven foundation.

My biggest complaint about Matlab (besides the licensing) is that it’s just a horrendously bad programming language (if you can call it a language at all)… you have to buy a toolbox for everything…

Matlab is really really, annoyingly powerful. You’ve got almost anything to try your ideas, implement an academic paper. But, it is slow (execution time). Prototype with Matlab, implement with C++.

Even though image processing/analysis wasn’t discussed, it is good to see that my assessment is confirmed.

I can add a few things though.

Matlab does some “rearranging“ of image manipulation (games) into matrix operations, they can’t be analyzed as matrices as they aren’t subject to matrix operations. They are in fact tables.

Matrices, yes. Linear algebra? Linear maps, kernels, images? Not as much. Quotient spaces? No. How am I supposed to compute homology of images?

Also, there are no pointers. So how am I supposed to implement graph representations of images?

So, MATLAB is mathematically powerful but only if you understand mathematics very narrowly.

Eventually I’ll add this to the wiki under MATLAB.

As I mentioned in the last post, I am at the initial stages of writing a book on elementary computer vision. It makes sense at this point to provide a rationale for such a book.

Current textbooks either have extensive prerequisites or take too long to get the student to use what’s been learned in real-life computer vision projects.

Let’s consider an example. Suppose we know freshman or sophomore students in a technical discipline. They have to take their first course in image processing. What are they capable of doing at the end of a typical course? They know about image representation and how to handle image files. They know how to increase contrast and remove noise. They are familiar with image restoration, image enhancement, and image compression. All good, but this choice of topics draws students toward photo editing and away from the scientific and industrial applications.

I am talking about the image processing vs. image analysis dilemma. The former produces images and the latter produces data. More on this here.

As image processing is a time consuming topic, the students may only get a little taste of image analysis (image segmentation and related topics about image content).

The result is that in order to make their skills applicable to scientific image analysis, they will need to take a more advanced course on the subject. Such a course would require (some combination of) calculus 1-3, linear algebra, probability. Even then, 3D images, especially their topology, are rarely addressed.

So, there may be a need for something even more elementary than Digital Image Processing Using MATLAB by Gonzalez, Woods, and Eddins discussed last time.

As I have mentioned before, I am thinking about writing a book on elementary computer vision and image analysis. Of course, I’ll follow what’s already in the wiki. It will take a while and in the process I research some of the better books related to the subject. I think Digital Image Processing Using MATLAB by Gonzalez, Woods, and Eddins is one of the best and closest to what I have in mind. Here is a short analysis.

The bottom line is that even though this may be the most elementary book on the subject, it’s still intermediate with serious prerequisites.