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.

In an 8 neighbour configuration, the spatial distances between the central pixel and its neighbours are not all equal, unlike in the 4 neighbour configuration. I took this into account by multiplying the incremental "cost" value between two pixels by the Euclidean length of their spatial separation. There are other constants used to weight displacements in an 8 neighbour configuration (3x3 neighbourhood) in literature. For instance, Gunilla Borgefors used values of 0.95509 and 1.36930, although their goal was not to measure the length of the path to a given pixel, but to approximate Euclidean distances between pixels (which should be independent of the path taken).

Reference: Distance Transformations in Digital Images, by Gunilla Borgefors. COMPUTER VISION, GRAPHICS, AND IMAGE PROCESSING 34, 344-371 (1986)

Comparison of Filtering with 4 or 8 Neighbour Configurations

Filtering with a 4 neighbour configuration, a mask size of 128, and a "gamma" value of zero

Filtering with an 8 neighbour configuration, a mask size of 128, and a "gamma" value of zero

There is almost no perceptible difference between the two images. However, a very close inspection will reveal that the texture of the butterfly's wing is sharper with an 8 neighbour configuration.

Looking "behind the scenes" into the workings of the filter, it becomes clear that the filtering process proceeded quite differently, as shown below. The following comparisons were generated for a pixel on the butterfly's visible hind wing, near the wing's left edge. The mask outlined in the images is for a mask size of 4096 pixels and a gamma value of zero.

Comparison of distances to a pixel (4 neighbour first, 8 neighbour second)

The maximum distances in the images (displayed as white) are 4.404 x 10⁷ and 3.865 x 10⁷ for the 4 neighbour and 8 neighbour images, respectively.

Comparison of the lengths of shortest paths to the source pixel of a mask (4 neighbour first, 8 neighbour second)

The longest path length in the 4 neighbour image is 2174 (white in this image), whereas the longest path length in the 8 neighbour image is 1593 (white in this image).

Comparison of pixel downstream counts (4 neighbour first, 8 neighbour second)

What is actually being displayed above are the base 2 logarithms of the downstream counts. The maximum downstream count in both images is the same as the number of pixels, 1021248, and corresponds to the source pixel of the mask.

Filtering Speed

Filtering the above image with a mask size of 512 pixels was 10.9% faster with an 8 neighbour configuration than with a 4 neighbour configuration.

(Image source: Bernard Llanos)