Graphics, Imaging, and Games Lab

Introduction

The cumulative range geodesic image filter was first developed by Dr. Mould in 2012, and is described in the following article:

Image and Video Abstraction using Cumulative Range Geodesic Filtering, Computers & Graphics, 2013.

(Available here on this website)

This term, I will work on modifying the filter to see what results it can produce, and also to explore a few applications beyond simply stylizing images.

First, however, I am building my own version of the filter in order to become familiar with the details of the implementation.

Cumulative Range Geodesic Filtering using a Fibonacci Heap

The cumulative range geodesic filter works by averaging together the values of all pixels in a mask surrounding the current pixel being processed. The average value becomes the pixel's colour in the output image. What makes this filter unique in particular, however, is that masks are irregularly-shaped regions surrounding their source pixels. The filter selects pixels to be part of a mask based on their "distance" from the source pixel, which is computed by taking into account both spatial distances and colour differences in the image.

Since the filter must find the pixels with the smallest "distances" to the source pixel, it needs some way to store a list of nearby pixels and keep track of which one should be added to the mask next. In other words, the filter uses a min-heap. The first heap that I implemented for use in the filtering program is called a "Fibonacci heap" and was first developed by Michael L. Fredman and Robert Endre Tarjan (Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, Journal of the Association for Computing Machinery, Vol. 34, No. 3, July 1987, Pages 596-615). I created the heap by adding more features (such as the "decrease key" heap operation, and a function for plotting the heap) to the incomplete implementation made by Daniel Underwood (downloaded from http://www.mathworks.com/matlabcentral/fileexchange/30072-fibonacci-heap).

Quick Summary of the Fibonacci Heap Implementation

Why?

Fibonacci heaps give asymptotically faster performance than other heaps when used in some graph-related algorithms (such as Dijkstra's algorithm). I was aware that they have a high constant overhead, however.

Results

The filtering program, implemented in the MATLAB language, processed an image on the order of one pixel per second. There are likely a few reasons for this:

• The constant overhead associated with using a Fibonacci heap may make the heap efficient only for heap sizes much higher than what is required during image filtering. When filtering, the size of the heap will generally be less than 1000.
• The heap was implemented in an object-oriented program, where each node in the heap was an object linked to other nodes. All objects were part of a subclass of MATLAB's "handle" class. In later work, I found that object-oriented code is very slow in MATLAB, at least for "handle" objects. (I have not yet worked with value objects in MATLAB.)

Solution

I switched to a binary min-heap, as will be discussed in the next blog entry.

A Demonstration of a Fibonacci Heap

I have posted a few images to show how the internal organization of a Fibonacci heap changes over the course of a few heap operations: http://gigl.scs.carleton.ca/node/487

As shown in the gallery, whenever a node loses two of its children due to decrease key or delete operations (since being linked into a tree), it is cut from its parent. This can result in "cascading cuts", as shown between images 3 and 4 in the gallery.