Successive Refinement  

Robert P. Munafo, 2010 Feb 25.



Successive Refinement is an algorithm for graceful gradation in rendering, image processing, and other generally grid-oriented compute-intensive operations. It is particularly useful in interactive systems because of its presentation of coarse intermediate results to the user. In certain algorithms it can form the basis of optimizations which take advantage of local similarity, local common subexpressions, local linearity, or some similar phenomenon.

Successive Refinement algorithms vary, but the common principle is to scan the grid at a "coarse" spacing, then again (in one or several passes) at increasingly finer spacings.

Successive refinement is used in Mandelbrot programs as both a user interface device and as an optimization. The improvement that it provides cannot be overemphasized. It will instantly transform a barely useable program into a powerful viewer. The program will complete its work typically 2-3 times faster, and often a hundred times faster. What's more, the successive refinement of the image during the imaging process allows the user an early glimpse of the final result, often foregoing the need to wait for completion.

After first pass (1.0 sec.)
After first pass (1.0 sec.)
After second pass (3.0 sec.)
After second pass (3.0 sec.)
After third pass (9 sec)
After third pass (9 sec)
After fourth pass (27 sec)
After fourth pass (27 sec)
Four stages of successive refinement, with representative elapsed times, as implemented by Super MANDELZOOM (1985), my first Mandelbrot viewer program. The image is the same as that on the August 1985 Scientific American cover.

Successive Refinement as a User Interface Improvement

As a user interface device, successive refinement allows the user to view a coarse representation of the current image, followed soon after by a less coarse version, then by better and better versions gradually over time. The implementation is fairly simple, consisting of little more than several successive raster scans. This can be done as follows:

Program MANDELBROT-SR-1 ~~~~~~~~~~~~~~~~~~~~~~~ COMMENT "The crudest Successive Refinement algorithm, applied to the Mandelbrot Set. Allows the user to quit early if the coarse rendition shows that the image will be uninteresting."   FOR chunk_size IN {16, 8, 4, 2, 1} DO FOR x = 1 TO grid_width INCREMENT_BY chunk_size DO FOR y = 1 TO grid_height INCREMENT_BY chunk_size DO LET r = XtoRealCoord(x) LET i = YtoImagCoord(y) LET count = EscapeIterations(r,i) LET color = MyColorMapping(count) FillRectangle(PARAM("left") = x, PARAM("top") = y, PARAM("width") = chunk_size, PARAM("height") = chunk_size, PARAM("color") = color) IF UserIntervention() THEN EXIT FOR(chunk_size) END IF END FOR(y) END FOR(x) END FOR(chunk_size)

On each iteration of the outermost FOR loop, the grid is scanned, evaluated, and plotted in squares of the current chunk size. The subroutine "fill_rectangle" takes five parameters, as shown: the top-left coordinates, the width and height, and a color.

This implementation is of course slower in the end than a single grid scan, because 25% of the squares are iterated and drawn twice, and 6.25% are drawn three times, etc.

With fairly little effort we can avoid this extra computation.

Program MANDELBROT-SR-2 ~~~~~~~~~~~~~~~~~~~~~~~ COMMENT "Successive Refinement, avoiding repetition of work done on the previous pass."   FOR chunk_size IN {16, 8, 4, 2, 1} DO FOR x = 1 TO grid_width INCREMENT_BY chunk_size DO FOR y = 1 TO grid_height INCREMENT_BY chunk_size DO IF ( chunk_size EQUALS 16 ) THEN LET do_evaluate = TRUE ELSE IF ( ((x / chunk_size) DIVISIBLE_BY 2) AND ((y / chunk_size) DIVISIBLE_BY 2) ) THEN LET do_evaluate = FALSE ELSE LET do_evaluate = TRUE END IF   IF ( do_evaluate ) THEN LET r = XtoRealCoord(x) LET i = YtoImagCoord(y) LET count = EscapeIterations(r,i) LET color = MyColorMapping(count) FillRectangle(PARAM("left") = x, PARAM("top") = y, PARAM("width") = chunk_size, PARAM("height") = chunk_size, PARAM("color") = color) IF UserIntervention() THEN EXIT FOR(chunk_size) END IF END IF END FOR(y) END FOR(x) END FOR(chunk_size)

Inside the three loops we have added two tests. The first ensures that the first scan (chunk_size 16) will be complete. The second allows subsequent passes to skip the squares computed on the previous pass.

Successive Refinement as a Performance Optimization

Optimization via Successive Refinement is a little more difficult, but well worth the effort. The technique is to watch the neighboring points during the grid scan and skip the Mandelbrot iteration if all of the neighbors have the same "count". This works quite well for the Mandelbrot Set (at least at the low magnifications that most beginning explorers use — see Optimizations - Domains of Efficacy)

Program MANDELBROT-SR-3 ~~~~~~~~~~~~~~~~~~~~~~~ COMMENT "Successive Refinement for the Mandelbrot Set, with optimization to take advantage of local similarity (solid regions)."

Implementation starts by declaring an array to hold the computed count values :

DECLARE counts_array: ARRAY[1 TO grid_width, 1 TO grid_height] OF INTEGER

Our three loops are the same :

FOR chunk_size IN {16, 8, 4, 2, 1} DO FOR x = 0 TO (grid_width-chunk_size) INCREMENT_BY chunk_size DO FOR y = 0 TO (grid_height-chunk_size) INCREMENT_BY chunk_size DO

We compute the coordinates of the current square's "parent". These are the coordinates of the square from the previous pass that the current square is a part of. For example, on the second pass, the square at (8,24) is an 8x8 square which is a part of the 16x16 square at (0,16). Thus (0,16) are the coordinates of the "parent" of (8,24).

IF (x DIVISIBLE_BY (2*chunk_size)) THEN LET parent_x = x ELSE LET parent_x = x - chunk_size END IF

The computation of parent_y is similar :

IF (y DIVISIBLE_BY (2*chunk_size)) THEN LET parent_y = y ELSE LET parent_y = y - chunk_size END IF

We then perform a test to see if the current square should be evaluated. The first part of the IF ensures that all squares will be drawn on the first pass, just as before :

IF ( chunk_size EQUALS 16) THEN LET do_evaluate = TRUE

The second part, just as before, ensures that we skip squares that were drawn on the previous pass — note however that the test is now simplified because we can use the variables parent_x and parent_y :

ELSE IF ( (x EQUALS parent_x) AND (y EQUALS parent_y) ) THEN LET do_evaluate = FALSE

The third part is the new test : it calls a subroutine, "all-neighbors-same", which will return TRUE if all of the neighboring squares have the same count as the square given by the parameters parent_x and parent_y. "chunk_size * 2" is the spacing between the parent square and the neighboring parent squares. Eight neighbors will be tested :

ELSE IF (all-neighbors-same(parent_x, parent_y, chunk_size * 2) ) THEN LET do_evaluate = FALSE

The last part of the IF is the default : if none of the other tests worked, we must evaluate the point :

ELSE LET do_evaluate = TRUE END IF

After determining if we evaluate, we then proceed as follows :

IF (do_evaluate) THEN LET r = XtoRealCoord(x) LET i = YtoImagCoord(y) LET count = EscapeIterations(r,i) ELSE LET count = counts_array[parent_x, parent_y] END IF b

This instructs the computer to use the "parent"'s count value if we are on a square that is being skipped. Then we proceed to draw :

LET counts_array[x,y] = count LET color = MyColorMapping(count) FillRectangle(PARAM("left") = x, PARAM("top") = y, PARAM("width") = chunk_size, PARAM("height") = chunk_size, PARAM("color") = color) IF UserIntervention() THEN EXIT FOR(chunk_size) END IF

This is the same as before, the only difference being that we store our count value in the array for use on the next pass. (Sharp readers will note that when a square has the same coordinates as its parent, we redraw it. This is of little consequence.) Now we end our loops :

END FOR(y) END FOR(x) END FOR(chunk_size)

As a user-interface improvement, Successive Refinement can work even better if the pixels are split in two (vertically or horizontally on alternating passes) instead of in four. In other words, if the first pass produces 8x8 pixels, the second would produce 4x8 pixels, the third 4x4 pixels, the fourth 2x4 pixels and so on.

While these pseudo-code examples have used the Dwell or Escape-Iterations function for rendering the Mandelbrot Set, Successive Refinement lends itself equally well and with similar results to the function.

With great effort, Successive Refinement can be applied to the .




From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2017.     Mu-ency index


Robert Munafo's home pages on HostMDS   © 1996-2017 Robert P. Munafo.
aboutcontact    mrob    mrob27    @mrob_27    mrob27
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Details here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2017 Feb 02. s.11