Edge-aligned filter

Preface

This is based on a report that I submitted for my university Computer Vision assignment. Each member of the course was given an individual assignment to undertake. Mine was to examine the effect of using a Gaussian filter aligned with the edges in an image.

Introduction

The Gaussian filter is effective in removing normally-distributed random noise from an image. Because it averages the value over a range of pixels, it also causes a loss of detail: the image is blurred, and edges are less sharp.

However, the Gaussian filter need not be circular in shape. An elliptical filter, where one axis is longer than the other, causes greater blurring along the long axis. This can be used to filter along an edge, removing noise whilst retaining edge detail.

A method for achieving filtering by aligning an elliptical filter along the edges of an image is presented and evaluated here.

Method

Edge detection

The Canny edge-detector finds the edges in an image in an effective manner. A typical input and output from this algorithm is shown in Figure 1.

Image of car wheel Image of car wheel after processing with Canny edge detector
Figure 1 (taken from Heath et al)

The Canny algorithm itself includes a Gaussian filtering stage for some immunity from noise in the source image.

The Canny algorithm can be summarized as follows:

  • Gaussian filtering is applied to the source image (to prevent noise from causing spurious edges to be falsely detected)
  • The intensity gradient of each pixel is found.
  • Gradients steeper than a threshold value are determined to be edges.
  • Each row and column is scanned in a threshold pass. High and low thresholds are used in a hysteresis pattern.

In the present application, however, a slightly different approach is taken. This seeks to identify not only where an edge is located, but also its direction. Therefore, at the threshold stage, the angle of the normal to the edge is calculated from the arctangent of the x and y gradients, and the overall gradient of the edge along the normal is calculated using Pythagoras’ theorem. In addition, since this process is not carried out separately for the x and y directions, a dual-threshold hysteresis system is not used. Calculation of the angle is simplified by the fact that the aligned filter exhibits rotational symmetry of order two. It is therefore only necessary to find the angle within the range -π/2≤θ≤π/2.

Filter alignment

The edge detection stage divides the image into edge- and non-edge regions. In the case of a non-edge region, the orientation of the filter is not significant; a circular Gaussian filter can therefore be used (see Figure 2). As the circular filter has already been used as a precursor to the edge-detection, the process is speeded up by using this pre-filtered image for non-edges.

Image of various Gaussian filter shapes in non-edge region
Figure 2

Image of elliptical Gaussian filter aligned along an edge
Figure 3

On edges, the direction of the edge can be determined from the surrounding pixels, and the Gaussian filter is aligned along the edge such that smoothing is only performed along the edge (see Figure 3). The short axis of the filter is normal to the edge, and the long axis is therefore parallel to the edge (or tangential in the case of a curve)

Edge filtering

Filtering is achieved by convolving the image with an aligned Gaussian filter. Figure 4 shows an example of a directional Gaussian filter. The pixels nearest to the current pixel have the highest weighting, whilst those further away have less. By using an elliptical filter, the pixels along the edge can be given the greatest weighting.

3D plot of bivariate Gaussian distribution
Figure 4

Parameters of bivariate Gaussian distribution illustrated on x-y plot
Figure 5

The value of the filter at a point (x,y) is given by:

gθ(x,y) = exp(-((x cosθ + y sinθ)2/2σx2 + (y cosθ – x sinθ)2/2σy2))

Where θ is the angle between the axis of the filter and the y-axis, and σx and σy are the axial dimensions of the filter normal and parallel to the edge respectively. See Figure 5 for a graphical representation. For the aligned filter, σx is normal to the edge.

For the case of a non-directional filter, σx = σy and the value of θ is irrelevant.

Implementation

Process

Figure 6 shows an overview of the filtering process as it is implemented here. This is carried out as follows:

  • The source image IS is filtered using a Gaussian filter to give the filtered image IG.
  • IG is used as the input to the edge detector. Where an edge is detected, the angle of the edge is used as a control input to the aligned filter.
  • The aligned filter processes the original image IS on the edge pixels only, to produce image IE.
  • The edge pixels in IE are used to replace the edges in the circular-filtered image IG. As previously discussed, non-edge pixels are taken from IG.

Flow diagram of filter operation
Figure 6

In practice, for efficiency, the filtering and combinations are combined, and the resulting image IO is overwritten into the buffer used to store the Gaussian filter. There are therefore only two full-image buffers in use, one for the source image, and one for the processed image as it passes through each stage.

Optimizations

In order to speed up processing, two particular optimizations were implemeted.

First, the circular Gaussian filter is separable. This means that each row can be filtered one-dimensionally in the horizontal dimension to give an intermediate image. If each column of the intermediate image is then filtered in the vertical direction, the result is the same as for a full filter of each pixel. For an image of X×Y pixels and a filter mask of N×N pixels, a full filter requires N×N×X×Y multiplication operations, whilst the optimized version requires only 2×N×X×Y multiplications.

Second, it is not possible to separate the filter whose axes are not parallel to the axes of the image, so a different approach is taken for the aligned filter. A look-up table is be used for generation of the mask for the aligned filter. The angle is quantized, and the aligned filter for each quantized angle is calculated in advance prior to filtering. This significantly reduces the amount of calculation required to filter each pixel.

The optimizations above were only implemented at the end of development, after a working non-optimized version of the code had been implemented. Although the exact time taken for processing depends upon the source image and threshold values chosen, these two optimizations together reduced the time taken for processing a large image by a factor of about twenty.

Finally, the size of the Gaussian filter does not have to be very large, as the weighting of pixels is low away from the centre of the filter. It is therefore possible to specify the size of the filter mask for an optimal speed/quality ratio. In practice, 5×5 provides an adequate size whilst not requiring an excessive number of calculations.

Program structure

The implementation has been carried out in C, as a simple console application, processing an input file and writing an output file.

All images and filters are stored in floating-point format, and all calculation is carried out in floating-point. Although this is slower than integer or fixed-point calculation on most processors, it allows a greater degree of abstraction (e.g. a filter mask is the same as an image).

The program code is split into a number of source files:

  • eaf.h—Header file
  • eaffile.c—Image file reading and writing
  • eafimg.c—Image- and pixel-level functions
  • eaffilt.c—Filtering and supporting functions
  • eaf.c—Front-end demonstration application

Compilation and linking is straightforward, requiring no supporting files beyond the standard libraries, and the application has been successfully compiled and run using several compilers.

The program operation is decomposed into a large number of functions whose operation is described in comments accompanying the code. The source code is listed in Appendix B.

Data structures

As previously stated, the image data is stored and manipulating in floating-point format, specifically as type double. A data structure is defined to hold the pixel buffer and other appropriate information for each image.

This has the additional benefit of also being able to store filter masks. The size of the buffer is specified, along with the location of the origin, and a pointer to a separately-allocated buffer holding the pixel values.

Edge behaviour

Where convolution is carried out in the program, pixels located beyond the edge of the image are given the same value as those at the edge. This behaviour is a result of the get_pixel function which returns the nearest edge value for out-of-range pixels.

Usage

The program has a number of command-line options to allow control of the various parameters in the program. The area of the aligned filter is generally the same as that of the circular filter, so for ease of use, this is specified as an equivalent radius and a length:width ratio. Therefore, an aligned filter with an equivalent radius of σ and aspect ratio α will give the same area as a circular filter of radius σ and therefore the same degree of noise reduction, but the actual radii of the ellipse will be such that σy = ασx.

For testing purposes, two additional parameters are supported:

  • Test mode—pixels not on an edge are replaced with white (for the purpose of determining the optimal threshold value)
  • Gaussian mode—only the first-stage Gaussian filtering is performed on the image (for comparison of Gaussian vs. aligned filter)

Evaluation

The program has been tested on two different classes of test image:

  • Photographic images
  • Geometric test images

Space permits only a brief discussion here, so these two types of image data have been chosen to give a good overview of the results achieved by the filter.

Photographic: Lena

The ‘classic’ Lena test image was used to test the operation of the filter on a photographic image. To cope with the low resolution of printed images, a small section of the image is used. Noise was added. The filter was then applied with various parameters.

This test process gives a good indication of the effectiveness of the filter from a subjective point of view.

Table 1 shows the image with varying amounts of added noise, processed with a range of parameters. The table shows the source image, the Gaussian filtered version, and the output from the edge-aligned filter in both test mode and normal mode. This enables a visual comparison of the sharpness of edges when compared with the original. The printing process might not render these images as clearly as they appear on the screen.

The RMS error in each processed image as compared to the original noise-free source is given in the table. Significantly, the RMS error is not greatly different in the edge-aligned filtered image than in the equivalent Gaussian filtered image, whilst the subjective quality is considerably improved.

Owing to the effect of the threshold value and the initial Gaussian filtering, pronounced edges are accurately reproduced in the filtered image, such as on the brim of the hat. Edges with lesser gradients are not picked up, and are therefore subject to the blurring of the circular Gaussian filter.

Geometric: Circle and square

A simple two-colour image of a light grey solid circle and square on a dark grey background was created using a painting package. Grey was used to enable normally distributed random noise to be added to the image with minimal clipping. Table 2 shows the source image with and without noise, processed with the Gaussian filter and with the aligned filter.

The edges are sharply reproduced. However, corners are eroded. This is due to the fact that a corner has two perpendicular edges. It is not possible to align the filter such that it meets both of these constraints.

A slight halo effect can be observed to the left and top of edges of both positive and negative gradient. This is due to the fact that gradient is determined only from the adjacent pixels to the left and top of a given pixel. Therefore, when processing a pixel immediately to the left of an edge, the system does not recognise that an aligned filter should be used. As a result, the circular filter includes the pixels on the other side of the edge, producing the halo. This is a weakness of the method used to calculate the gradient.

Two graphs show a section through the left edge of the square. Figure 7 compares the original image with the Gaussian filtered image and the image as processed by the aligned filter. Figure 8 shows the results when noise is added to the source image. The horizontal axis represents displacement, whilst the vertical axis gives the grey value of the pixel at that offset. It can be seen that the edge is accurately reproduced in both cases.

Speed

A rough measure of the speed of processing is indicated by the fact that filtering takes approximately six seconds on the full 512×512 pixel Lena image using a system with a 400MHz AMD K6-2 processor.

Table 1 & 2

These tables have been omitted from this online document. You are encouraged to download and compile the source code in order to evaluate the performance of the algorithm for yourself.

Graph showing edge performance of algorithm on an image without added noise
Figure 7

Graph showing edge performance of algorithm on an image with noise added
Figure 8

Conclusions

A method for removing noise from an image has been presented. Unlike the circular Gaussian filter, this process preserves the sharpness of edge details whilst still carrying out a comparable amount of smoothing.

On photographic sources, the results are good. The results are subjectively better than the Gaussian filter, giving less impression of blurring. Noise removal is similar to that obtained with the Gaussian filter. This was expected, given that this process uses Gaussian filtering.

On artificial sources, the edges are reproduced with reasonable accuracy. However, there is a flaw in the method used to calculate the gradient. This is discussed in more detail below. Corners are also a problem for the filter, and cannot be reproduced well.

The process is dependent on the source image (the more edges, the more processing is carried out) so that it is not possible to calculate the exact time taken to process an image in advance. This may be significant in real-time or video processing.

Overall, this method is a useful alternative to the standard Gaussian method where edge detail needs to be preserved.

Improvements

There are still optimizations and improvements remaining to be made in the code, many of which are commented to this effect in the source.

The method used for calculation of gradient is too simplistic, as it fails to take into account all the surrounding pixels when determining what constitutes an edge. This is manifested in the ‘halo’ effect to the left and top of sharp edges. An improvement could be achieved by using all pixels (either 4- or 8-connected) around the pixel under test, and weighting these accordingly.

The present implementation makes heavy use of floating-point operations. Rewriting the code to use fixed-point (i.e. scaled integers) processing would normally be faster on general-purpose processors. Note: I later tried this, and it turned out not to be the case. The floating-point implementation was slightly faster.

Appendix A: Program operation

General operation

The program takes an input file, processes it, and writes the resulting image to an output file. Both filenames must be specified on the command line to the program.

File format

The program only works on greyscale images, and assumes 8 bits per pixel. Files are read and written in PGM (portable greymap) format. The source file can be in either text or binary format (header ‘P2’ or ‘P5’ respectively). The output file is always written in binary format.

Syntax

The help screen of the program explains the command-line options available and the syntax.

Appendix B: Source code

This is straightforward ANSI C. It has been successfully compiled using GNU (gcc), Microsoft (cl) and Borland (bcc32) compilers on i386 architecture.

You can download the source code as a zip package: