Imperium Accelero 9K

Image Processing Techniques and Algorithms

Intro

During the development of the IA9K several methods of 2D image manipulation were researched.  The purpose of this app note is to provide a starting point for other groups attempting to do image processing with an FPGA.  For example, groups may wish to implement edge detection image filtering necessary for artificial vision etc.   As the project nears completion this page will be updated with the methods that actually worked with further details on their implementation.

Technical Specs

IA9K was built using an Altera Apex20KE FPGA mounted on a Nios development board with 128MB of Azen SRAM.  Size requirements for each filtering technique will be included at the end of each section as the architectures are completed.  

Image Processing using Convolution

The heart of the IA9K consisted of a 3x3 convolver to filter image data.  The decision to use convolution as the basis of the filters was made since a wide range of image effects could be produced simply by changing the weights in the convolution matrix.  Images were filtered by passing the pixel data into the 3x3 convolver (block diagram shown below) and then determining the pixel color by convolving the pixel data of the surrounding pixels.

More detailed Information on this convolver can be found at: http://www.tecnun.com/asignaturas/tratamiento%20digital/dsp40k.pdf

Since the convolver is fully-programmable only the coefficients of the convolver matrix need to be changed to provide a variety of image effects.  Below is a list of convolver matrix coefficients that were incorporated into the IA9K.

Pixel by Pixel Image Processing

Color manipulation was performed by manipulating each individual pixel.  Effects such as grayscale, negative images, and gamma correction were all accomplished by altering the image one pixel at a time.  Below is a list of pixel by pixel operations incorporated into the IA9K.

Details of Implementation

The first step in implementing a NxN convolver is to find a way to shift the grid data into the convolver so that the calculation may proceed.  The method used in our 3x3 convolver involved creating a large shift register to store two complete lines of image data plus three additional pixels.  New pixel data is  inserted sequentially into the shift register effectively displacing the convolution (3x3) window to a new adjacent position until the whole image has been visited.  The one thing that should be noted about this method is that the shift register will grow rapidly with the size of the image being processed.  For, larger images the shifting technique remains the same but the image must be split up into several vertical strips so that the width of the shift registers may be reduced and the shift registers can be reused after operation on each column of data has completed.  The advantage of using this technique is that it provides the convolution calculation with a new window of pixel data on each clock cycle after the registed has filled.

Further details on the shift register can be found at: http://www.grm.polymtl.ca/circus/data/MUG1997_paper.pdf

The next step in designing the convolver is to understand the calculation itself.  The following images were taken from Altera application note 215 (http://www.altera.com/literature/an/an215.pdf) on implementing convolution and other DSP techniques.  The calculation combines a 3x3 grid of image data and the convolution matrix weights to compute a new value for the center pixel of the 3x3 grid.

The convolution operation on a pixel neighborhood can produce a wide range of numerical values. It is therefore important to adjust each value to match the range of the display or memory storage device. One method, termed clipping, is utilized to truncate the values to the bounds of the display range. Another method that generally produces better results operates by reducing the scale of values to fit the display range. The latter method is called normalization and is implemented by our design. The bias value for each filter reflects the absolute value of the sum of the negative coefficients convolution matrix. The bias represents the total deviation of the output values from the lower bound of the display range. The normalization value reflects the sum of the absolute values of the elements in the convolution kernel. The bias is added to each output value to ensure that it lies within the lower boundary of the display range, and the normalization value is used to scale down the output values to fit the upper boundary of the display range.

Finally, the following two links are java animations of exactly what the IA9K convolver is trying to achieve :

Size Estimation and Code: The final implementation of the IA9k convolver was designed to operate on small images (96x64 pixels) and use 3561 logical elements.  Please see the final web report posted by the IA9k team for all source code  and filter implementation details in their entirety.

More References used in this document

http://dot.tt.hut.fi/dip/ (digital image processing)

http://www.tecnun.com/asignaturas/tratamiento%20digital/dsp40k.pdf (fully programmable 3x3 convolver)

Additional Image Filtering Resources

http://www.efg2.com/Lab/Library/ImageProcessing/Algorithms.htm (image processing algorithms)

http://www.altera.com/support/examples/verilog/ver_twod_fir.html (two-dimensional FIR filter implemented in verilog)

http://www.faqs.org/faqs/graphics/algorithms-faq/ (image processing algorithm faq)

http://www.cogs.susx.ac.uk/users/davidy/teachvision/vision2.html (convolution in low-level vision)

This app note was created by

Ian "Jungle Flow" Ferguson, Imperium Accelero 9000 [ March 2k3 ]