January 29, 2011

Lengths of curves: theoretical aspects

Filed under: education,image processing/image analysis software,mathematics — Peter Saveliev @ 4:09 pm

The subject of lengths of curves in the digital envisonment has been discussed here several times. It’s summarized here: http://inperc.com/wiki/index.php?title=Lengths_of_curves. The main idea to take home is that no matter how high the resolution of your image is, the relative error of the measurement of the length of a “real” curve as approximated by a “digital” curve remains constant. That’s bad news for computing the perimeter or the roundness of an object in the image.

The perimeter of a square and that of the inscribed circle are the same.

The perimeter of a square and that of the inscribed circle are the same.

A broader explanation for this failure is that the geometry of the universe is independent of direction, i.e. isotropic. By adding the grid and limiting our curves to it we make our approximation of this universe anisotropic. As the examples show, the horizontal and vertical directions are different from the rest. And no matter how much we improve this approximate universe by making the grid finer and finer, it will remain anisotropic. Choosing a triangular or hexagonal grid or other tricks won’t help.

The result is counter-intuitive. Indeed, refining the approximation has to lead to the exact result. Actually, there is a moment in calc1, when the issue arises and it requires some careful thinking.

The issue comes up when the definition of the Riemann integral is introduced. The integral is defined as the “limit” of Riemann sums, but what sums? They may be initially defined as a sums over intervals of equal length. In this case there is only one parameter and it may seem that you are just dealing with the same limits as the ones used for continuity, derivatives etc. However, this definition is inadequate if you want to prove some simple properties of the integral. Turns out, you need to be able to deal with arbitrary partitions of the interval. Then the Riemann integral is still a limit but a limit of Riemann sums over all possible subdivisions of the interval. For continuous functions it does not matter (you have to prove that), but for some other functions is does. These functions are non-integrable. The issue is often glossed over in a standard Calculus class (so that not to traumatize the students).

A similar situation here. We need to consider all possible rectangular grids. Then take the limit. The limit will be a two-parameter kind: the width of the pixel and its height go to 0, independently. Then, when both are smaller than some delta, the length of the approximated curve will be within some given epsilon from the length of the “real” curve. Problem solved!

Solved? It’s unclear how to use this insight to improve the accuracy…

January 28, 2011

Electronic Imaging conference

Filed under: image processing/image analysis software,mathematics,news — Peter Saveliev @ 1:06 pm

I attended the Electronic Imaging conference this week in San Francisco, organized by IS&T/SPIE.

When I was getting ready I tried to figure out what talks to attend. This is what I discovered:

Very sad!

Turns out, there were a few mostly mathematical talks…

Gave my talk: Graph non-tree representation of the topology of gray scale images. It was based on the paper under the same name but I also added some more recent stuff about analysis of color images (still to some).

Gave a demonstration of Pixcavator, Pixcavator image-to-image search, and Pixcavator mobile (still to come). The demo session was an especially fun part with a lot to see and a lot of people to talk with.

January 12, 2011

Tineye image search still can’t handle rotated versions

Filed under: computer vision/machine vision/AI,image search,reviews — Peter Saveliev @ 3:48 pm

In spite of prior assurances, Tineye still can’t find rotated versions of images.


image:tineye honda.jpg

image:tineye honda rotated.jpg

Other image-to-image search engines here

January 11, 2011

Computational topology short course

Filed under: computer vision/machine vision/AI,education,mathematics — Peter Saveliev @ 11:12 am

It was a part of the annual Joint Mathematics Meeting in New Orleans.



  1. Topological Data Analysis by Afra Zomorodian
  2. Persistent Topology by Gunnar Carlsson
  3. Topological Dynamics: Rigorous Numerics via Cubical Homology by Marian Mrozek
  4. Euler Calculus for Sensor Data by Robert Ghrist
  5. Topology in Robotics: Planning with Uncertainty by Michael Erdmann
  6. Optimization of Cycles and Bases by Jeff Erickson

Analysis of digital images wasn’t discussed. Fortunately, I just finished a draft of a paper on this exact subject. It’s called Homology groups of filtrations. Broadly, this is my view on persistent homology.