Approximating generalized 2D filters with boxed filters

Fall 2010

Student
Karanhaar Singh
Advisor
José Moura
Project description

One major area of research in image processing is finding algorithms capable of efficiently applying 2D image filters to images. Normally, for small sized problems, simply convolving the filter and the image together suffices. However, convolution is expensive--O(n*log(n))-- for large n, where n is the number of pixels in the image. Consequently, with large-scale problems, such as those involving large image databases, this methodology is not practical.

One possible solution to tackle such large-scale problems is to initially generate an "integral image" of the input image, where the value in each pixel in the integral image is defined as the running sum of all of the pixels above, and to the left, of it. Integral images are extremely valuable because they can be used to find the image's response to a linear combination of box filters extremely efficiently. A box filter is a filter whose non-zero values are all equal, and are arranged in a rectangle in the filter's matrix representation.

For this project, I will be working under the guidance of graduate student Bernardo Pires and faculty member Jose M F Moura to develop an automated algorithm to accurately approximate a general 2D filter by a linear combination of box filters. We will implement the filter in the programming language C and will test the algorithm against a large image database to assess the accuracy of our program.

Return to project list