Graphics, Imaging, and Games Lab

Introduction

When building filtering masks around each pixel in an image, the filter needs to know which pixels are adjacent to a given pixel. Up until now, I have been using a 4 neighbour configuration, in which each pixel is adjacent to the pixels immediately to the left and right, immediately above, and immediately below.

Recently, I tried using an 8 neighbour configuration, in which each pixel is adjacent to the four closest pixels along diagonal offsets, in addition to the pixels above and below and to the left and right.

I uploaded a gallery of images to demonstrate the behavior of the cumulative range geodesic filter at various parameter values.

The gallery is available here.

This version of the filter is a replication of the prototype version created by Dr. Mould (see http://gigl.scs.carleton.ca/node/481).

From the images, it is evident that the masks created by the filter can be very irregular in shape. As the "gamma" parameter increases, the mask boundaries are pulled closer to the source pixel, resulting in more circular mask shapes and a softer output image.

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.

Introduction

The MATLAB language is ideal for writing prototype programs very quickly, as MATLAB provides a large number of built-in functions and it is possible to run code fragments without embedding them in a full program with a "main" function, header files, etc. Unfortunately, MATLAB programs are interpreted as opposed to compiled and run more slowly than compiled C programs, for example.

On the other hand, it is possible to take advantage of both the speed of C and the ease of use of MATLAB by writing MEX-functions in C. I decided to use this approach in order to obtain a faster cumulative range geodesic filtering program than the MATLAB code version which I had written earlier.

Filter Mask Generation Using a Binary Heap

Seeking to improve the speed of the cumulative range geodesic filtering program described in my last blog entry, I started by examining code for Dijkstra's algorithm written by David Gleich (downloaded from http://www.mathworks.com/matlabcentral/fileexchange/24134-gaimc-graph-algorithms-in-matlab-code ). I had been using this code to produce data with which I could compare my results to determine if my program was working correctly. David Gleich's code, which uses a binary heap, ran significantly faster than my program.

Using David Gleich's program and some general information on binary heaps as guides, I substituted the Fibonacci heap with a binary heap. The version which used a Fibonacci heap processed an image at a rate of around one pixel per second, while the version with a binary heap, following some initial changes to improve its efficiency, reached a speed of about 50 pixels per second. After working much harder on optimizing the code, the filter ran at about 350 pixels per second.

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.