Processing time

I've tried a variety of images and, as the diagram indicates, the processing time appears to depend linearly on the number N of pixels in the image. Roughly, 40 seconds per megapixel (40 seconds for a 1000x1000 image). The testing was done on HP Pavilion laptop with Intel Core 2 Dual CPU T7500 2.2GHz.

The processing time as a function of the image size.

There is no known limit on the size of files (in bytes) Pixcavator can open. There are however limitations in terms of the dimensions of the images. Depending on your computer, images larger than 2000x2000 may require processing time that is too long to be practical. This still beats manual counting. Also consider that if your computer runs out of RAM, it can take really long time. Certainly, the estimate provided by Pixcavator won't be valid anymore.

If your images are significantly larger than 2000x2000, my advice is to find out how accurate your measurements need to be. Then consider simply shrinking the images.

The tests show a linear dependence but in reality the (worst case scenario) complexity is quadratic: O(N²) [1], where N is the number of pixels in the image. This is how we get this result.

The analysis algorithm works as follows:

The complexity of the algorithm for an image of this kind is O(N²).

• Each of the N pixels is added consecutively and is processed separately.
• For each of the N pixels, at least one new object is created and you may have to run around one of the existing objects to mark its edges.
• If this object is very thin and fills the image (like this spiral on the right), its perimeter is proportional to N.

This situation however may seems unusual, such as the image. Images of maps or microchips may fall into this category. Image of cells or other particles do not.

Adding a pixel creates up to 9 nodes in the augmented graph. Hence the graph size and

 the memory usage is O(N).

After the graph is built, it is analyzed to extract objects from the image. It requires following the list of all principal cycles. This list is O(N), above. For each such cycle, you may have to visit some of its ancestors or descendants. To reach them you have to visit some auxiliary nodes as well. But once again the total number of nodes is O(N). Therefore

 the complexity of the entire algorithm is O(N2).