Digital Image Processing
Assignment 3 - Multiresolution Painting and Compositing

By Abhinav Golas – 2003CS50466
S. Arun Nair – 2003CS50222

We did an implementation of the paper “Multiresolution Painting and Compositing” by Berman, Bartell and Salesin, published in SIGGRAPH 1994.

The paper allows us to edit an image at different resolutions, while preserving detail present at higher resolutions. This it does by maintaining a Tree based multiresolution structure by which we can view and edit the image at varying levels of detail.

The Quadtree structure:

The 3 d_i values provide 4 colour values, which can be used to paint 4 regions. The region mapping we have used is:

_______
| 1 | 2 |
-----------
| 4 | 3 |
-----------

So each leaf node provides information about a minimum of a 2x2 pixel region. The QuadTree is a sparse structure, i.e. A level is allocated only if there is detail which cannot be represented at the current level.

Display:

For displaying this image at a 2^jx2^j resolution we use j-1 levels of this QuadTree structure to draw the image by calculating 4 colour values from the 3 d_i values and the parent colour value of the pixel region. i.e. The colour values generated by level i-1 act as parent colour values for level i.

Editing:

For editing at level j, we first take a composite of the present colour value and the drawn value based on the alpha values (basically a weighted sum) and then proceed to propagate these values by the 2 functions specified, decompose and extrapolate. Decompose serves to propagate the changes up the tree order, i.e. to levels j-1 to 0, while extrapolate propagates the changes down the tree, i.e. From j+1 to the leaf nodes. Decompose is the same for all editing operations. Extrapolate is different for each of the 4 operations, ‘over’, ‘in’, ‘under’ and ‘erase’. For each operation we weigh the existing d_i values with a function of the modified parent colour values to get new d_i values.

Fractional resolutions:

Since the granularity of powers of 2 is not sufficient for editing and display purposes, the paper also provides for fractional zooming. Basically to scale the image to 2^j+t where j is an integer, and t is real and in [0,1], we simply zoom the 2^j size image to get the image. For editing purposes, the painted changes are assumed to have occurred at level j+1 by corresponding zooming by 2^1-t.

Implementation:

We made an implementation in C++ using OpenCV 0.9.9, and FLTK 1.7 for a GUI

Results:

Original image:

At resolution 2⁸x2⁸

Modified image:

First blue dots were applied at 2⁷x2⁷ with ‘over’ editing, then red dots were applied at 2⁶x2⁶ with ‘under’ editing. As we can see, the red dots go under the blue dots.

Hence we can see that the details i.e. The blue dots at higher resolution are preserved even when editing at lower resolution.

For further proofs and details please refer to the paper.