Multiscale Image Analysis with Wedgelets

Image Representation

Image representation is a fundamental issue in image processing research. Good representation naturally leads to better results in a range of image processing applications (e.g. de-noising, compression). Usually, multiscale representations are more desirable because it allows more flexibility, such as variable-rate coding or compression.

A simple way to represent images is to use encode as a matrix of pixel values. For example, at each point in a 614x614 image, we use 8 bits to represent the color at that point. This method, though simple, is an un-natural representation of images. Real objects in a photo aren't composed of a collection of points of different colors and intensity. Instead, we have lines, shapes, contours, etc; things are at a more macroscopic level than pixels. Such representations will usually lead to poor performance in applications such as denoising and compression.

Wavelets and their Limitations

Currently, the state-of-the-art representation method uses wavelets. Wavelet bases have proved so effective in representing images that it quickly found its way into the newest standards like JPEG2000.

However, wavelets have their limitations. They are good at representing one-dimensional singularities, but do not extend well to higher dimensions. To see this, look closely at an image encoded with JPEG2000. You should notice some block-like artifacts around curved or diagonal lines. The reason is that in 2D images, wavelet transforms are applied one-dimension at a time, separately in vertical and horizontal directions. Thus, it picks out any edges or lines that run vertically or horizontally easily, but misses the diagonal or curved ones. To represent a diagonal line, we need very many little wavelets forming a zig-zag like pattern. This is what creates the block artifacts. The more compression you use, the easier you'll notice this artificial effect.

Considering tha natural images contain lines and curves in all directions, new representation methods must be sought. This is where wedgelets enter the picture.

A New idea: Wedgelets

Wedgelets are first introduced by Dr. Dave Donoho at Stanford University. In a nutshell, they are localized functions at different scales, locations, and orientation that give piecewise linear approximations for images. Just like wavelets, wedgelets are used to decompose an image at multiple scales (resolution). The difference is that wedgelet functions are defined in 2D, which allows them to model diagonal lines easily. Basically, a wedgelet defines one line (in any orientation and shift) on a 2D block. It also specifies the average pixel values at two sides of the line in the block.

To represent an image using wedgelets, we use a recursive dyadic partitioning scheme. (This is a fancy way of saying: we partition the image into chunks of fours recursively at different resolution). The algorithm uses a bottom-up approach. First, we begin at the finest resolution and define wedgelets for all the blocks of image pixels there. If we happen to look at part in the image with a diagonal line, we will put down a wedgelet of that orientation there. (The estimation of the best wedgelet at each block can be determined by using some sort of mean-square error criteria.) After we're done putting down wedgelets at one scale, we move up to the coarser scale and do the same. At each of the coarser scales, we have the option of either inheriting the finer scale wedgelets defined previously or using a new wedgelet defined for the coarser scale. Doing the former will make your image sharper, while doing the latter will save you bits. The power of multiscale image analysis comes from the ability to choose the resolution at different parts of the image dynamically. In an image, a broad area (such as the blue sky) will have few wedgelets while a detailed pattern (such as the design on a person's shirt) will have many wedgelets. The result is an image that is most sharp but also most parsimonious.

References

For more information, check out the websites of Dr. Rob Nowak and his PhD student Becca Willett. (They taught me all this)

BACK TO MY HOMEPAGE
Last updated: Feb 21, 2004