This page is a part of CVprimer.com, a wiki devoted to computer vision. It focuses on low level computer vision, digital image analysis, and applications. It is designed as an online textbook but the exposition is informal. It geared towards software developers, especially beginners, and CS students. The wiki contains mathematics, algorithms, code examples, source code, compiled software, and some discussion. If you have any questions or suggestions, please contact me directly.
Robustness of geometry
From Computer Vision Primer
The analysis starts with this simple principle:
...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.
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?
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
4π(1+1/N2)/(4+2/N)2.
After some algebra (long division OMG!) we reduce this to
4π/16+1/(4N) + higher power terms.
Once again, this is, roughly, 1/N.
Example: Contrast isn't robust under noise, Average contrast is. And so is Saliency.
Exercise. What about Diameter and Major and minor axes?
Robustness under transformations: translations and rotations
Example: Lengths of curves aren't robust under rotations. Hence neither are Perimeter or Roundness.
There can be no robustness of geometry without Robustness of topology.
Download the free Pixcavator Student Edition here.
