Graphics, Imaging, and Games Lab

In my previous post (http://gigl.scs.carleton.ca/node/495), the plots of filtering time vs. aspect ratio perhaps hide what is actually going on. The two plots below should make more sense.

Analysis

Basically, the binary heap used as part of the filter requires a number of operations proportional to the base-2 logarithm of the number of pixels in the heap for inserting a pixel into the heap, extracting the minimum-key pixel, and decreasing the key of a pixel. When filtering an image with a large mask size, if one side of the image is very small, the number of pixels in the heap is proportional to the length of the smaller side. This results in the filtering time having the approximately linear relationship to the base-2 logarithm of the smaller image side length, as shown in the above plots. Notice how this relationship weakens as the mask size decreases.

In the second plot above, there is a small dip in filtering time at aspect ratios approaching one (where the smallest side of the image is at its longest). I hypothesize that this is due to my filtering program's splitting of the mask building process into two parts: Initially, the filter does not bother to check if the coordinates of pixels adjacent to those in the mask are valid (i.e. within the image). However, in the second part of mask generation, the mask is sufficiently large for it to possibly touch the edge of the image, and so all adjacent pixel coordinates are checked. This procedure should, in theory, speed up mask building on images with aspect ratios nearer to 1, because these images contain more pixels far from the image edges.