Method and System for Editing Multiresolution Images at Fractional-Levels of Resolution Using a Wavelet Representation

The invention relates to a method and apparatus for editing images, and more particularly, to a method and apparatus for editing images having different resolutions.

This invention was made with government support under Grant No. CCR-9357790, awarded by the National Science Foundation and with support from Air Force Award No. 80-9307. The government has certain rights in the invention.

Editing displayed images by "painting" them or performing a similar type of operation has been done for some time. For example, the painting of multiresolution images is discussed by Perlin and Velho in "A Wavelet Representation for Unbounded Resolution Painting," Technical Report, New York University, November, 1992. The report describes the use of a multiresolution tree structure to implement an unbounded resolution paint system. The report also describes the use of wavelets to make it feasible to quickly propagate changes at multiple resolutions. However, the system discussed by Perlin and Velho does not support fractional-level (continuous) zooming into an image at an arbitrary resolution to enable a user to edit at any convenient scale. The system of Perlin and Velho also does not address the simplification of a variety of compositing operations when extrapolating the changes made at a course resolution level to a higher resolution level of the image. Finally, the system discussed in Perlin and Velho is limited to a standard wavelet basis.

It is an object of the invention to provide fractional-level "continuous" zooming in order to allow a user to display and edit portions of a multiresolution image at an arbitrary size.

Yet another object is to use lazy evaluation in compositing operations to simplify and "speed up" the process of editing an image.

In one aspect the present invention relates to a method of displaying and editing an image, which has discrete levels of resolution, at fractional levels of resolution thereof. The fractional levels lie anywhere in between the discrete levels. The editions made at the fractional-level resolution are stored in a foreground buffer and are updated by rescaling the editions to the next highest discrete level of resolution. The modified foreground buffer is then combined with a background buffer, which contains the image prior to any editions, and results in a composited image. The composited image is then propagated to a selected one of the discrete resolutions from its present resolution, by decomposing the composited image to all the lower levels of resolution and extrapolating the composited image to a higher level of resolution using lazy evaluation.

The image, which has a number of discrete levels of resolution, can be represented by a quadtree structure. Here, each of the levels of resolution has a corresponding level on the quadtree structure, and each level on the quadtree structure has a plurality of nodes. When an edition is made to the image, which changes all the edited nodes to a different color/transparency or erases all the opacity of the edited nodes, a simplified form of extrapolation can be used to propagate these changes. This is accomplished by multiplying the edited node transparency with the nodes occupying the level of the quadtree corresponding to the new resolution level.

Still other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description wherein the preferred embodiment of the invention has been shown and described, simply by way of illustration of the best mode contemplated at the time of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and descriptions are to be regarded as illustrative in nature, and not as restrictive.

FIG. 1 shows a system for displaying and editing images at various resolutions.

FIG. 2A shows the quadtree as used by the present invention and FIGS. 2B-2D show portions of an image corresponding to the quadtree.

FIGS. 3A-3D show the process of fractional-level zooming in, editing, and panning out on an image.

FIGS. 4A-4E show the use of different kinds of painting operations on an image.

FIGS. 5A-5D show different fractional-levels of zooming and multiresolution painting at that fractional-level of zooming.

FIGS. 6A-6D show the manipulation of a single multiresolution image which is made from six successive images.

FIG. 1 shows an acceptable apparatus for carrying out the method of the present invention. The apparatus includes input devices such as graphics pad 20, video input 34, and scanner 36, as well as a computer 22. The computer 22 includes a visual display unit 24, an electronic portion 26 having a CPU and a memory, a zooming device 38 (keyboard or sensor on display 24) and a paintbrush 28. The apparatus of FIG. 1 can be used to carry out the processes of the present invention. For example, the apparatus of FIG. 1 is useful for carrying out the process of fractional-level zooming to any selected resolution of an image 30 displayed on visual display unit 24 by using zooming device 38, and then editing a selected area of the image 30 at that fractional-level resolution using paintbrush 28. The apparatus can then extrapolate the editions of the image 30 to a lower resolution level using a simplified procedure.

The paintbrush 28 in the apparatus of FIG. 1 can be used to edit the image 30 in a variety of ways. For example, the paintbrush 28 can be used to remove paint from the image 30, or place paint on the image 30. The paintbrush 28 may also be used to apply paint on the image 30 only where paint has already been applied to the background of the image. Further, the image may be edited by placing paint on the image 30 only where it is applied by the paintbrush 28 and where the background of the image 30 is transparent.

Initially, the image 30 is digitized and stored in the memory of the computer 22 by any suitable means, such as the digital graphics pad 20, by direct creation on computer 22 using the CPU and a graphics program, by being input electronically from a network or other device via the modem 32, by input from the video 34 or a scanner 36 or any other suitable method. Once digitized, the image 30 can be stored in the memory of the computer 22 as a multiresolution image, which is an image having different resolutions in different places. Because the stored image 30 is a multiresolution image, it can be varied adaptively according to need.

The image 30 can be defined mathematically as the sum of piecewise-constant functions at different resolutions 2.sup.j .times.2.sup.j. In this sense, the image 30 can have "infinite" resolution everywhere. A user zooming into the image 30 would see more detail as long as higher-resolution detail is present. For example, a user working with the image 30, as shown in FIG. 2B, can zoom into the image to display an even higher resolution image consisting mostly of the leg 19. With control device 38, higher and higher levels of resolution can be obtained by the user. However, once the highest resolution is exceeded, the pixels of the finest-resolution image will appear to grow as larger and larger constant-colored squares.

The representation of the multiresolution image 30 is stored in the memory of computer 22 as a sparse quadtree structure 31, as shown in FIG. 2A. The nodes of the quadtree structure 31 have a correspondence with the displayed pixels of the image 30. For example, the root 21 of quadtree structure 31 at level j=0, as shown in FIG. 2A, corresponds to a pixel 27 on the entire image 30 at the lowest resolution. Further, if area 23, as shown in FIG. 2B, represents a quarter of the image, then if the user zooms so area 23 fills the display 24, the children nodes 25 of the root 21 correspond to the four pixels 33 of the area 23, as shown in FIG. 2C. If the user zooms into area 35, which represents a quarter of the area 23, so that it fills in display 24, then the four pixels 37 correspond to the four children nodes 29 of node 25, as shown in FIG. 2D. Thus, each level j of quadtree 31, shown in FIG. 2A, corresponds to a scaled version of the multiresolution image 30 at resolution 2.sup.j .times.2.sup.j. Note that, by the usual convention, "higher" levels of the quadtree (i.e., near the root 21) correspond to lower-resolution versions of the image, and vice versa.

Each node of the quadtree contains the following information described by the following pseudocode:

The d.sub.i values in the QuadTreeNode structure describe how the colors of the child nodes deviate from the color of their parent node and are called the detail coefficients. These coefficients allow the computation of the RGBA colors of the four children, given the color of the parent. The .alpha. (opacity) component of a color c and detail coefficient d.sub.i are referred to as c..alpha. and d.sub.i..alpha., respectively. Thus, the detail coefficients allow the computation of the colors of pixels 33 in FIG. 2C using the color of the pixel 27 in FIG. 2B, which correspond to node 25 and root 21, respectively.

The .tau. value represents the transparency of the node and can be used to simplify the extrapolation of various editing operations as will be discussed later. Here, the value .tau. is initialized to 1. The child[i] fields are pointers to the four children nodes. Since some of the children nodes may be null, the child[i] fields can alternatively be represented by a single pointer to an array of four children to optimize storage.

Each node N, for example node 29 in FIG. 2A, of the quadtree 31 corresponds to a particular region A(N) of the display 24, for example a corresponding one of the pixels 33 of FIG. 2C can be denoted by A(N). The value of A(N) is determined implicitly by the structure of the quadtree 31 and the particular view, and does not need to be represented explicitly in the actual node N.

In the present invention, which allows fractional-level zooming and editing, there does not need to be a one-to-one correspondence between the pixels on the display and the nodes at some level j in the quadtree. Thus, each node on the quadtree does not have to represent a pixel on the displayed image.

To accomplish fractional-level (i.e., continuous) zooming and editing, the square region A(N), corresponding to a given node N at level j in the quadtree, must be observed as to how it would grow as a user zooms in continuously from level j to j+1 to j+2. From such an observation it can be derived that the size of A(N) would increase exponentially from width 1 to 2 to 4 on the display 24. Thus, when displaying at a fractional level j+t, for some t between 0 and 1, A(N) should have size 2.sup.t .times.2.sup.t.

On workstations that provide antialiased polygon drawing, fractional zooming is implemented by drawing each node as a single square of the proper fractional size. On less expensive workstations that support only integer-sized polygons efficiently, a slightly less efficient but still adequate display can be achieved by rounding each rendered square to the nearest pixel.

The quadtree itself is given by the pseudocode:

The c value in the quadtree structure Q supplies the color of the root node 21; it corresponds to an average of all the colors in the image 30.

The quadtree is sparse in that it contains no leaves (i.e., last set of nodes at highest level j) with detail coefficients d.sub.i that are all 0. Thus, the constant portions of the image at any particular resolution are represented implicitly. This convention allows the support of infinite resolutions in a finite structure. It also allows the explicit representation of high-resolution details only where they actually appear in the image.

FIGS. 3A-3D show the process of fractional-level zooming in and then fractional-level editing a portion of image 30. Once the user has zoomed into a higher fractional-level resolution, shown in FIG. 3B, as discussed above, he can again use the zoom control device 38 to zoom into an even higher fractional-level resolution of a selected portion of the image 30. The selected portion, such as the head of the subject 40 in the image 30 can then be edited at that fractional level. For example, a teardrop 42 can be added below the left eye 44 with paintbrush 28 as shown in FIG. 3C. After the user edits the selected portion of the image 30, he can then pan out to a lower fractional-level resolution as shown in FIG. 3D.

After the multiresolution image 30 has been edited, it is updated to propagate the results of the editing operation to the rest of the multiresolution image, as represented by the quadtree 31. The update involves two steps: decomposition, in which the changes are propagated to all higher levels of the quadtree 31, that is, for example, changes to nodes 25 at level J=1 alter root 21 at level J=0, as shown in FIG. 2A; and extrapolation, in which changes are propagated to all the lower levels of the quadtree 31, that is, for example, changes at nodes 25 at level J=1 alter node 29 at level J=2, as shown in FIG. 2A. This updated version is then stored in the memory of computer 22. The updated version of the image 46, shown in FIG. 3D, can then be output by the visual display unit 24 or printed by the printer 35, as shown in FIG. 1.

These steps of displaying the image, painting the image, and then updating the image, as discussed above, can be implemented in the following manner.

In the first step of displaying the image 30 on the visual display unit 24 at any fractional level, an image of resolution 2.sup.j+t .times.2.sup.j+t is displayed by calling the following recursive Display routine once, which passes the color parent root to the overall quadtree:

The pseudocode above recurses from the root 21 of FIG. 2A to level j+t-1 for the entire image; in reality, it should only recurse within the bounds of the portion of the image 30 that fits in the display window of display unit 24. Note that if m pixels are displayed, the entire display operation takes approximately O(m) time. For this fractional-level display routine the recursion must be bottomed out whenever node N is at level [j+t-1]. Further, the region A (child[i]) must correspond to the appropriate fractional size. Finally, in this step a background buffer B, which represents the currently displayed image 30, is created.

The second step of fractional-level painting or editing is implemented by compositing a newly-painted foreground buffer F with the background buffer B to create a new resulting image R. Fractional-level painting or editing is supportable by updating the quadtree representation by first rescaling the buffer of newly painted changes F to the size of the next higher integer level, as if the user had painted the changes at level j+1; the scaling factor required is 2.sup.1-t. Then the same update as before can be performed, starting from level j+1. A discussion on the compositing algebra used to combine the newly painted foreground buffer with the background buffer can be found in Porter and Duff, "Compositing Digital Images," Proceedings of SIGGRAPH '84 (Minneapolis, Minn., Jul. 23-27, 1984), in Computer Graphics 18(3):253-259, 1984; and in the context of digital painting in Salesin and Barzel, "Two-Bit Graphics," IEEE Computer Graphics and Applications 6:36-42, 1986.

The step of fractional-level painting or editing an image supports several painting operations as shown in FIGS. 4A-4D. For example, if the image 30, as shown in FIG. 4A, has a clear or transparent area 50, and a painted area 52, then four distinct operations can be performed on this image. One of these operations is the "over" operation which places paint 54 on the image 30 everywhere along the path 58 of the paintbrush 28. Thus, both the painted area 52 and the clear area 50 are covered with paint 54, as shown in FIG. 4B. Another operation is the "under" operation, as shown in FIG. 4C. When performing an "under" operation, as a paintbrush 28 is moved along a path 58, the paint 54 is only applied on the clear or transparent area 50. None of the paint 54 is applied to the already painted background area 52 of the image. Yet another operation is the "in" operation, shown in FIG. 4D. For an "in" operation, when the paintbrush 28 is moved along the path 58, the paint 54 is only applied onto the painted area 52 along the path 58, and no paint is applied to the clear or transparent area 50 of the image 30. Finally, this step of fractional-level painting or editing also supports a unary "erase" operation, which removes paint from all of the background of the image 30. For example, when paintbrush 28 is moved along path 58, all the painted area 52 of image 30 is removed, as shown in FIG. 4E.

No special routines are required to implement fractional-level painting itself. One difference between conventional methods of painting and the present embodiment is that in addition to the composited resulting image R, a separate copy is kept of the foreground buffer F, which contains all of the newly applied paint. This foreground buffer F is necessary for updating the quadtree, as will be described. The process of painting proceeds until the user either changes the painting operation (for example, from "over" to "under"), or changes the display on display unit 24 by panning or zooming. Either of these operations triggers the third step of updating.

Finally, in the updating step for updating the necessary levels after the fractional-level editing has been performed, let j be the next higher level of the quadtree from the fractional-level at which the user has been painting, and c.sub.r (x,y) be the color of each modified pixel in the result image R. A decomposition of the entire image is performed by calling the following Decompose function once, passing the root of the quadtree Q.root as an argument, and storing the result in Q.c:

The pseudocode above assumes that the sparse quadtree structure already contains all of the nodes corresponding to the pixels in the result image R; however, if R has been painted at a higher resolution than the existing image, then new nodes may have to be allocated and added to the quadtree structure as part of the traversal. Furthermore, for efficiency, the Decompose function should be modified to only recurse in regions of the multiresolution image where changes have actually been made. Thus, if the portion of the image being edited has m pixels, then the entire decomposition operation takes O(m) time.

As can be inferred, the present invention is not limited to a standard wavelet basis, but instead uses a non-standard basis in a non-standard decomposition thereby reducing the complexity of the decomposition. For further discussion, see Stollitz et al., "Wavelets for Computer Graphics; A Primer," University of Washington, Department of Computer Science and Engineering, January, 1994, incorporated herein by reference.

Extrapolation is a bit more complicated, and depends on the particular compositing operation used. For binary painting operations, let c.sub.f (x,y) be the color of the foreground image F at each pixel (x,y), and let c.sub.f. .alpha.(x,y) be the pixel's alpha (opacity) value. For the "erase" operation, let .delta.(x,y) be the opacity of the eraser at each pixel. Extrapolation can then be performed by calling the following routine for the node N corresponding to each modified pixel (x,y) of the edited image:

The extrapolation procedure takes an amount of time proportional to the quantity of detail that appears further down the quadtree structure at higher resolutions of the modified parts of the image.

One novel aspect of the present invention is the capability to optimize and simplify this extrapolation operation, at least for the most common cases of painting "over" and erasing, by using a form of lazy evaluation. The two formulas for "over" and "erase" in the pseudocode above merely multiply the existing detail coefficients by some transparency constant, .tau.(x,y). (For painting "over," .tau.(x,y)=1-c.sub.f. .alpha.(x,y); for erasing, .tau. (x,y)=1-.delta.(x,y).) For these two operations, rather than calling the Extrapolate procedure for each node N, the value N..tau. stored at the node can be multiplied by .tau.(x,y). Later, if and when the d.sub.i values for a node N are actually required, they can be lazily updated by multiplying each N.d.sub.i with the .tau. values of all of the node's ancestors (i.e., parents, grandparents up the tree). For a discussion on lazy evaluation see Perlin and Velho in "A Wavelet Representation for Unbounded Resolution Painting" Technical Report, New York University, November, 1992. The product of the transparency and the nodes ancestors is easily performed as part of the recursive evaluation. Thus, if nodes 25 are altered their values can be extrapolated to all the nodes 29, as shown in FIG. 2A, by multiplying their respective values by the .tau.(x,y) of corresponding nodes 25.

This unique and very simple form of lazy evaluation is a by-product of the underlying wavelet representation for the image, since the detail coefficients at higher resolutions, such as nodes 29, depend only on the product of the opacities of all the paint applied and removed at lower resolutions, such root 21 or node 25. Any sort of lazy evaluation method would be much more complicated with image pyramids, since the high-resolution colors have a much more complex dependence on the colors of the paint applied and removed at lower resolutions. Note also that color correction, an important image operation, is a special case of compositing "over," and so can be performed on an arbitrarily high-resolution image in time proportional only to the resolution actually displayed.

The above-mentioned equations used within the display, painting, and updating steps may be derived. For example, if C.sup.n is a matrix of size 2.sup.n .times.2.sup.n representing the pixel values of image 30, then it can be associated with a function I.sup.n (x,y) as follows:

where .PHI..sup.n (x) is a row matrix of basis functions [.phi..sub.1.sup.n (x), . . . , .phi..sub.2.sup.n n(x)], called scaling functions. In this application, a Haar basis is used, where each scaling function .phi..sub.i.sup.n (x) is given by: ##EQU1##

The wavelet transform allows the decomposition of C.sup.n into a lower-resolution version C.sup.n-1 and detail parts D.sub.1.sup.n-1, D.sub.2.sup.n-1, and D.sub.3.sup.n-1, by using matrix multiplication as follows: ##EQU2##

In the Haar basis, the matrices A.sup.n and B.sup.n are given by: ##EQU3##

The detail coefficients d.sub.i at level j in the algorithm are the entries of the D.sub.i.sup.j matrix. Thus, equations (1)-(4) immediately above, provide the expressions used in the Decompose routine.

The four decomposed pieces can also be put back together again, using two new matrices P.sup.n and Q.sup.n, as follows:

This equation provides the expressions used in the fractional-level Display routine. In the Haar basis, these matrices are given by P.sup.n =2(A.sup.n).sup.T and Q.sup.n =2(B.sup.n).sup.T.

The original function I.sup.n (x,y) can be expressed in terms of the lower-resolution pixel values C.sup.n-1 and detail coefficients D.sub.i.sup.n-1 using a new set of basis functions .PSI..sup.j =[.PSI..sub.1.sup.j (x), . . . , .PSI..sub.m.sup.j (x)], called wavelets, as follows: ##EQU4##

In the Haar basis, there are m=2.sup.j wavelets in .PSI..sup.j, and each .PSI..sub.i.sup.j (x) is given by: ##EQU5##

Decomposing the first term .PHI..sup.n-1 (y)C.sup.n-1 .PHI..sup.n-1 (x).sup.T of equation (5) recursively allows the representation of function I.sup.n (x,y) in its wavelet basis, given by the row matrix

In order to derive the expressions used for compositing detail coefficients in the Extrapolate routine, compositing operations must be defined based on functions F, B, and R, built from the pixel values C.sub.f C.sub.b, and C.sub.r of the foreground, background, and resulting images, respectively, such that:

The foreground image has its highest-resolution components in level j, the next level above the fractional-level at which the user is editing/painting, whereas the background and resulting images have components in a potentially higher-resolution level n. For example, the "over" operation can be defined on functions F, B, and R as follows:

The expressions for compositing detail coefficients can be derived by writing each function in its wavelet basis, multiplying out, and regrouping terms. The final expressions are quite simple, as the pseudocode for the Extrapolate routine attests.

Treating boundary conditions correctly introduces a slight complication to the update and display algorithms previously described. The difficulty is that the Decompose function needs to have available to it the colors of the children of every node N that it traverses. For example, node 25 in FIG. 2A would require the colors of its children including node 29. However, some of these child nodes correspond to regions that are outside the boundary of the window in which the user has just painted, and therefore are not directly available to the routine. The obvious solution is to store color information, in addition to the detail coefficients, at every node of the quadtree; however, this approach would more than double the storage requirements of the quadtree, as well as introduce the extra overhead of maintaining redundant representations. Instead, a temporary auxiliary quadtree structure of just the colors necessary for the decomposition may be kept, this structure can be filled in during the Display operation at little extra cost in storage. The size of this auxiliary structure is just O(m).

Another zooming and editing procedure that zooms and paints at a fractional-level resolution is shown in FIGS. 5A-5D. By allowing continuous zooming into the image 30, a tree 60, shown in FIG. 5A, can be drawn at a low resolution. Then, a user by controlling the zoom device 38, shown in FIG. 1, can zoom into the tree 60 at any area of the image 30 by any fractional-level resolution of the image. Once zoomed in, a user may add leaves 62 to the tree 60 with paintbrush 28, as shown in FIG. 5B. A user may then continuously zoom out to a lower resolution level, as shown in FIG. 5C, and sweep paintbrush 28 along a path 58 using an "in" operation, to apply paint 57 to only the areas previously painted, in this case the leaves. A user may then quickly zoom out to an even lower resolution and rough in the sky 64 with passes of the paintbrush 28 along path 66, and then move the pen 28 along path 68 at the bottom of image 30 to paint in grass 70, both using an "under" operation so the previously painted leaves and tree are not affected, as shown in FIG. 5D. Thus, an image may be edited or created at any scale quickly and efficiently.

By allowing a user to zoom continuously into a multiresolution image, the utilization and composition of successive images can be merged together. For example, a multiresolution image can be made out of successive images from a book, such as Powers of Ten, by compositing its images together at different scales. In the book, each of the images is a 10x higher-resolution version of the central portion of its predecessor. Therefore, if six images are made into a single image 30, this image will have a 10.sup.5 range of scale. Further, with fractional-level editing available, each of the images from the book within image 30 can be manipulated. For example, FIG. 6A shows a simplification of one of the lower power successive images of the book. Here, the innermost detail is represented by a person lying on a blanket 72. A user could zoom out by a factor of 100,000 to an image of the continent and the planet 74, as shown in FIG. 6B. Then, as shown in FIG. 6C, the user could retouch the low resolution version of the image 30 using the "over" operation and a paintbrush 28 to create a smog-like effect 78 over the paintbrush path 76, which overlaps the higher resolution image of the person on the blanket 72. If the user then zooms into a higher level resolution, as shown in FIG. 6D, the person on the blanket 72 will be visible but slightly obfuscated by the smog created over path 76. Thus, the smog added over path 26 will affect all of the closer views without eliminating any of the detail present.

Accordingly, the present invention allows the fractional-level display and editing of images using multiresolution painting and compositing with the ability to make sweeping changes at a coarse resolution, as well as doing fine detail work at high resolutions, wherein a user can zoom into an image at an arbitrary resolution and to work at any convenient scale.

By zooming into an image and working at an arbitrary resolution, a user may work on a single image at any degree of resolution and not constrained to only operate at discrete levels of zooming in which the resolution doubles at each level. This enables operations like texture mapping, which allows portions of a texture that will be seen up close to be defined in more detail to be performed. Satellite and other image database formation, which allow overlapping images created at different resolutions to be coalesced into a single multiresolution image, are also possible with the present invention. Further, "importance-driven" physical simulations, which may be computed to different resolutions in different places, the use of virtual reality, hypermedia, and games, which allow for image detail to be explored interactively, by using essentially unlimited degrees of panning and zooming, and the use of an "infinite desktop" interface, which present a single virtual "desktop" with infinite resolution to the user, may all utilize the present invention.

While the foregoing has been a discussion of a specific embodiment of the present invention, those skilled in the art will appreciate that numerous modifications to the disclosed embodiment can be made without departing from the spirit and scope of the invention. Accordingly, the invention is defined by the following claims.