The title may sound sensationalist but it came from this study outlined at ScienceDaily.com. Here is the full quote:

When people are asked to search for an item that will appear only once in 100 images, they might miss as many as a third of the objects they’re supposed to be finding. Studies of radiologists looking at images to find cancer have shown similar error rates.

I think this fact provides new evidence in support of the use of computer aided diagnosis (CAD). It is happening but the progress is very slow. Screening seems the most appropriate starting point. It could be cancer or blood work (see the article on cell counting in our wiki).

Recall that in the previous posts we discussed what happens if one computes the length of a curve in a digital image as the total sum of distances between consecutive points. The conclusion was that using the length computed this way to evaluate the shapes of objects leads to disastrous results.

What do we do?

Let’s review. Computing lengths of horizontal and vertical segments produces correct results. Computing lengths of diagonal segments leads to a 40% error. To fix that, every time we have a triple of consecutive points arranged in a triangle we should replace 1+1=2 in the computation with √2. The result is that now all 45 degree segments have correct lengths! Great!

Great? Not quite. What about 22.5 degree segments? To make matters simpler consider instead segments with 2 horizontal steps followed by 1 vertical. We compute its length as 1+√2, which is about 2.41. Meanwhile the “true” length is √(2^2+1^2) = √5, which is about 2.24. The error is almost 8%!

Once again, what do we do? Very simple, we take into account this new type of segments. Now we have three types: horizontal/vertical, diagonal, and now 2-straight-then-turn. To compute the length of a curve we break it into segments of the three types and add their lengths.

You can predict what happens next. We try 22.5/2 degree – there will still be an error. And so on. There is no exact method to compute the length of a digital curve, locally.

This is the idea – as I understand it – of the paper On Local Definitions of Length of Digital Curves by Mohamed Tajine and Alain Daurat. One breaks a curve into a sequence of “small” (n steps) curves, each small curve is assigned a length (it does not have to be the distance from the beginning to the end), then the length of the original curve is the sum of those. Simple enough. The caveat was discussed previously. As the resolution approaches 0, the length computed this way should converge to the “true” length. Generally, it does not!

The paper proves that this “local” approach can’t produce the exact result no matter how large n is. Of course, you can interpolate the curve and measure the result. But that’s a can of worms that deserves a separate discussion.

The result is interesting. It’s helpful too in the sense that you don’t have to waste your time trying to find a solution to a problem that can’t be solved.

I do have a minor criticism. The curve is a sequence of “small” curves consecutively attached to each other, fine. Once you start to compute the length, however, the way they are attached is thrown out. If you don’t want to lose information, you should allow the curves to overlap, by a single pixel. My guess is that the result would still stand.

Another issue not discussed in the paper is that the error goes down as n increases. This is a good news because it allows one to produce meaningful results in shape evaluation. About that in the next post.

Caught a CSI show and started to reminisce. Tons of cool equipment including computers of all kinds and software from the 22nd century. Fingerprint identification? In seconds! DNA analysis? A snap! Even face recognition (ha!). At the same time you see them staring at those old fashioned light microscopes. The CSI people do their investigations in Second Life now but never use digital microsopes. Fiction?

Recall that in the last post we observed that, since a curve in a digital image is represented as sequences of points, it is natural to think of its length as the total sum of distances between consecutive points. However, with this approach the length of a diagonally oriented segment will be overestimated by 40%.

In the case of digital images, to compute the perimeter of an object we simply count the number of vertical and horizontal edges. Here is one interesting consequence. The perimeters of a square and the inscribed circle are the same!

Here is a more practical example. Suppose we want to classify objects in an image, like the one on the right. Suppose we have detected and captured these objects and now all we want to do is to tell nuts from bolts. Let’s adopt a “dumb” approach and try to use the simplest method available. Then some of these objects can be classified based on size only. However, there are some bolts and nuts of about the same size and we have to look at their shapes. That does not work out as you’d expect.

The “roundness”, area/(perimeter squared), will be lower for elongated objects, like bolts. This works perfectly well in the continuous domain but in the digital domain it is possible to think of very different shapes with both area and perimeters exactly same. Take a diagonally oriented square with side a. Then its area is a*a and its (digital) perimeter is 4*√2*a. Now, a horizontally oriented rectangle (√2+1)*a by (√2-1)*a will have the same measurements. The proportions of this rectangle are about 1-to-5. It’s a bolt that looks like a nut…

In the next post I will briefly discuss a paper on this subject.

Look at this press release Lockheed Martin to Develop Automated Object Recognition Using Brain-Inspired Technology. To be inspired by brain they would need to understand how it works. Do they, really? Where did they stash their Nobel prize? Apparently, they know how a person looking at an apple forms the word ‘apple’ in his brain. If a scientist made such a claim, it would be immediately challenged - by other scientists. But as long as this is a “technology”, people will believe anything. And some (DARPA) even pay money for it!

This is also a part of another pattern – trying to emulate nature to create new technology. The idea is very popular but when has it ever been successful? Do cars have legs? Do planes flap their wings? Do ships have fins? What about electric bulb, radio, phone? It’s silly to think that computers will be an exception. End of rant.

This is a problem most people outside the field are unaware of. In fact, I have also overlooked it for a while. The problem is, how do we measure lengths of curves in digital images? First, why do we need that? Because we want to be able to evaluate shapes of objects and the most elementary way to do it is to compare their areas to their perimeters. For example, area/(perimeter)^2 will tell circles from squares.

In the digital domain, curves are represented as sequences of points. It seems “obvious” that the length is the total sum of distances between consecutive points. The trouble starts as soon as you realize that the same “physical” curve will have many digital representations – depending on the resolution of the image and the orientation of the curve with respect to the grid of the image.

Consider this example. If r is the size of the pixel, a line segment of length a will be represented by roughly a/r pixels… but only if it is placed horizontally or vertically! If it is placed diagonally, there will be √2*a/r pixels arranged in the staircase pattern. The result is that the digital length of a curve may vary by 40%. If you overlook this difference, the consequences may be disastrous.

To be continued…

• We hit 20,000 downloads! About 5,000 are downloads of Pixcavator 2.3. So far no complaints about any serious bugs. In reality there are some problems with the measurements of light objects. They are being fixed.
• Article on measuring objects was added. It makes more precise what is being computed, especially for gray scale images. More examples will be added.

Oh TechCrunch and its confused readers (and writers!)… In a recent post tells about a company that uses “extremely wide angle lenses to capture full spherical images of the urban environment” to create a “3D panorama”. They expect somebody to find “the latitude, longitude, elevation, and other attributes of garbage cans…”. A discussion of whether this is a “true” 3d follows.

As I wrote in my comment, there is an easy way to define 3D: “I can see the object AND I know how far it is”. The object is a 2D picture and the distance (depth) is the 3rd dimension. Without that, it’s not 3D. It does not matter whether the picture is curved. I would even venture to suggest this “rule”:

To capture a 3D image you need a 3D camera.

What is a 3D camera? Well, any camera takes 2D pictures so all you need to add is the 3rd dimension. Time could be that, so a video camera is a 3D camera. Or you could combine several cameras in a row - that row is the 3rd dimension (in fact just two cameras will do). In either case, you can find the distance via stereo vision. Or you could simply add a distance measuring device such as radar, lidar, etc.

The company in question makes thousands of pictures from a moving car, so there is a third dimension. But since it seems that they don’t do any stitching, then maybe not…