This site is devoted to mathematics and its applications. Created and run by Peter Saveliev.

Robustness of geometry

From Mathematics Is A Science

Jump to: navigation, search

The analysis starts with this simple principle:

Pixels are small.

...and objects are large. So the question is, what changes to the image will produce "small" changes to the output of analysis, especially objects measurements.

1 How noise affects measurements: area vs. perimeter

The accuracy of measurements is reduced by noise and other environmental factors. In the digital domain, we have the complete knowledge of the values of the pixels. That may lead to the feeling that the accuracy, if not absolute, is always sufficiently good. The argument in support of this attitude is very simple: “The resolution is just so high!”

We know that the area behaves well in this respect. As the resolution increases, the digital area converges to the “real” are of the “real” object. However, the accuracy of measuring of the length of a digital curve is limited by the degree of its approximation by regular curves – independent of the resolution!

Now we have to deal with noise as well. Turns out, the length, and the length related characteristics, once again behaves poorly in comparison to the area.

Let’s consider a very simple example. Suppose we have an image containing a 1x1 black square on white background. Suppose also that the resolution is 1/N, so that the square contains N*N pixels. Add noise. Let’s suppose the noise is just a single black pixel. Now, how are the area and the perimeter of the square affected by this event?

Square with noisy pixel.jpg

If the new pixel ends up inside the square, neither area nor perimeter is affected. Same, if it is entirely outside the rectangle. Now, suppose the pixel is adjacent to the border of the square, as in the picture.

Then the area changes from 1 to 1+1/N2, while the perimeter changes from 4 to 4+2/N. Proportionally, the changes are 1/N2 and 1/(2N) respectively. As the resolution increases (and N goes to infinity), both go to 1. However, the “noisy” area approaches the “real” area much faster than the perimeter!

Another characteristic is the centroid. The centroid of the square is (½, ½). Under our one-pixel noise, the x-coordinate of the centroid is now

½*1+(1+1/(2N))*1/N2 = ½+1/N2 +1/(2N3). 

It converges at the rate of 1/N2.

On the other hand, the box dimensions change by a single pixel, 1/n! Not as good - they are length related.

Roundness is a tricky one. It is 4π*area/perimeter2, a mixture of areas and lengths. For the square, the roundness is 4π/16. For the new, “noisy”, square we have


After some algebra (long division OMG!) we reduce this to

4π/16+1/(4N) + higher power terms. 

Once again, this is, roughly, 1/N.

2 Robustness under transformations: translations and rotations

Area is robust under both. In fact all measurements are robust under translations.

Lengths of curves aren't robust under rotations. Hence neither are Perimeter or Roundness.

3 Robustness under noise and blur

Contrast isn't robust under noise, but average contrast is. And so is saliency.

Exercise. What about diameter and major and minor axes?

4 Robustness under changed resolution

Switching from 1 megapixel to 2 megapixel camera improves the accuracy of measurements very little. The logic here is that the error of the area of a 1000x1000 square is the order of magnitude of 1000, so that the relative error is .1%.

There can be no robustness of geometry without Robustness of topology.