Pyramid-based Computer Graphics

3y ago
67 Views
3 Downloads
2.15 MB
12 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Baylee Stein
Transcription

J.M. Ogden E.H. Adelson J R. Bergen P.J. BurtPyramid-based computer graphicsPyramid-based graphics techniques can provide realisticcomputer graphics on small systems without the complexitiesof physics simulations.Humanbeings have an intuitive feel for graphics. Graphicsproblems such as blending two images smoothly, interpolatingto fill in missing image data, or creating realistic looking imagesare routinely solved by artists using traditional media. It i smuch more difficult to perform these tasks mathematically. Amajor step in solving a computer graphics problem is choosingan appropriate numerical representation for the image, onewhich allows us to use our visual and artistic intuition in anatural way.Artists often tend to separate the spatial scales of an imagewhen creating or altering a picture. When an artist paints alandscape, the coarse scale (low spatial frequency) informationis filled in first, as a wash of color in a large region. Intermediate-size details can be added next with a medium-sizebrush. As a last step, the artist draws the fine details with asmall brush. The image can be considered a sum of overlays ofincreasingly fine detail. When an artist touches up a damagedpicture, both the large and small scale variations are consideredin filling in the missing pieces. In synthesizing and combiningimages, we would like to imitate the artist’s ability to see animage on both large and small scales by representing the imagemathematically on many different spatial scales simultaneously.The simplest way to represent an image is to set the numericalvalue of each pixel proportional to the image intensity. Thisrepresentation is useful when we want to paint or draw directlyone pixel at a time, or when simple manipulations of contrastor color are desired. But it becomes cumbersome when wewant to look at an image at several spatial resolutions.Abstract: This paper describes pyramid solutions to graphicsproblems that have proven difficult in other imagerepresentations. The "physics simulation" approach grows moreout of the physics and mathematical modelling traditions.Greater realism can be achieved by using the physics simulationapproach but the complexity and computation time are vastlyincreased over the multiresolution pyramid approachesdescribed here. 1985 RCA CorporationFinal manuscript received October 21, 1985Reprint RE-30-5-14A Fourier transform representation can be used to separatethe various spatial scales of an image. Unfortunately, when weleave the familiar spatial domain for the spatial frequencydomain our intuitive feel for the problem is lost. Operating o nthe Fourier transform of an image, we can no longer "see" localspatial features in a recognizable form. What is really needed i sa representation that describes an image at multiple spatialresolutions, and also preserves the local spatial structure thatallows us to "see" the picture at each scale. Pyramid representations are ideal for this class of problems.1,2,3The pyramid representation and computer graphicsThe pyramid representation expresses an image as a sum ofspatially bandpassed images while retaining local spatial information in each band. A pyramid is created by lowpass-filtering animage G0 with a compact two-dimensional filter. The filteredimage is then subsampled by removing every other pixel andevery other row to obtain a reduced image G1. This process i srepeated to form a Gaussian pyramid G0, G1, G2, G3 . Gn(Fig. 1).Gk (i,j) ΣΣm nG k - 1(2i m, 2 n),k 1,NExpanding G1 to the same size as G0 and subtracting yields thebandpassed image L0. A Laplacian pyramid L o, L 1, L 2, . Ln - 1 , canbe built containing bandpassed images of decreasing size andspatial frequency.Lk Gk - Gk l,k 0,N-1where the expanded image Gk,1 is given byGk,l (i,j) 4Σ Σ Gk,l - 1[(2i m/2, 2j n)/2)]f(m,n)m nThe original image can be reconstructed from the expandedbandpass images:G0 L0 L1,1, L2,2 .LN - 1,N-1 GN,NRCA Engineer 30-5 Sept./Oct. 1985

REDUCE (filter subsample)Figure 2 shows an image represented as a sum of several spatialfrequency bands.The Gaussian pyramid contains lowpassed versions of theoriginal G0, at progressively lower spatial frequencies. Thiseffect is clearly seen when the Gaussian pyramid "levels" areexpanded to the same size as G0 (Fig. 3a). The Laplacianpyramid consists of bandpassed copies of G0. Each Laplacianlevel contains the "edges" of a certain size, and spans approximately an octave in spatial frequency (Fig. 3b).This pyramid representation is useful for two important classesof computer graphics problems. First, tasks that involve analysisof existing images, such as merging images or interpolating to fillin missing data smoothly, become much more intuitive when wecan manipulate easily visible local image features at severalspatial resolutions. And second, when we are synthesizing images,the pyramid becomes a multiresolution sketch pad. We can fill i nthe local spatial information at increasingly fine detail (as anartist does when painting) by specifying successive levels of apyramid.In this paper, we will describe pyramid solutions to somegraphics problems that have proven difficult in other imagerepresentations:1. Image analysis problems(a) Interpolation to fill missing pieces of an image(b) Smooth merging of several images to form mosaics2. Creation of realistic looking images(a) Shadours and shading(b) Fast generation of natural looking textures and scenes usingfractals(c) Real-time animation of fractals.Multiresolution interpolation and extrapolationFig. 1. Building the pyramid.The problemThe need to interpolate missing image data in a smooth, naturalway arises in a number of contexts. It can be used to removespots and scratches from photographs, to fill in transmittedimages that are incomplete, and to create interesting computergraphic effects.A solutionInsight into the problem of interpolation is gained by consideringthe image as a sum of patterns of many scales. A typicalphotograph includes small scale fluctuations due to surfacetexture, superimposed on more gradual changes due to surfacecurvature or illumination variations. Similarly, a painting is acomposite made up of features of many scales, rendered withbrushes of different sizes. In predicting the values of the missingpieces of an image, we need to consider intensity variations o nboth small and large scales.Figure 4 shows a one-dimensional representation of an imageG0 that has some missing values. One method of interpolating t ofind the unknown region is to use a Taylor series expansion. Ifthe size of the missing piece is comparable to the finest scalefeatures of the image, a good estimate of the unknown valuex dx can be obtained through a simple linear prediction basedon the first derivative G 0' at the point x:G0 (x dx) G0 (x) dx G0'(x).If the missing piece is large compared to the fine scale features ofFig. 2. The pyramid as a sum of spatial frequency bands.Ogden/Adelson/Bergen/Burt: Pyramid-based computer graphics5

Fig. 3. Expanded Gaussian and Laplacian pyramids.the image, we need to examine variations on larger scales as well.We can compute such an estimate by fitting the function G 0(x)to a Taylor polynominal of higher degree. This involvestaking higher order derivatives that represent the image variationover a larger number of pixels. One disadvantage of thisapproach for computer graphics is that it is computationallyexpensive. It is also difficult to adjust the degree of the interpolating polynomial to account for missing regions of differentsizes.An alternative way to look at the missing information o nmany scales is to build a Gaussian pyramid. This represents theimage G0 at different spatial resolutions ranging from fine (G0) t ocoarse (Gn). The unknown piece of G0 is also missing from G 1,G 2, . G n. Note that the size of the missing region is reduced in thereduced pyramid levels. Now, instead of fitting a Taylor polynomial of high degree at the finest spatial scale, we use linearinterpolation at multiple spatial resolutions to fill in the missinginformation.In the example shown, the size of the missing piece is largecompared to the fine scale variations contained in G0 and G1, butis comparable to the feature size in Gn-1 and small comparedto the coarse features of Gn. Starting with G0, we use linearextrapolation to predict the values of unknown points with twoknown neighbors.G0 (i) 2 G0 (i 1) - G0 (i 2)6For this example, most of the unknown values of G0 are "leftblank." A small border one pixel wide is extrapolated into theunknown region. Now we build G1 and extrapolate again. Atthis reduced resolution, the extrapolated border corresponds to alarger proportion of the unknown region. When the extrapolatedG1 is expanded to full size, the border also expands in size fromone pixel to several pixels. Continuing to lower spatial resolutions, we eventually reach a reduced pyramid level Gn, where theunknown region has shrunk to only one pixel. Extrapolation atG n gives a pyramid level with all the values filled in.An extrapolated image is built by reconstructing the extrapolated pyramid. Starting with Gn, we expand to form G n,1. Wherea pixel in the next highest frequency band Gn-1 is missing, thevalue from Gn,1 is used. Continuing this process, we form anextrapolated image G 0, with all unknown points filled in.ExamplesFigure 5a shows a portrait that has had ink spilled on it. Thelocations of the ink spots are indicated in a mask image, Fig.5b. When a two-dimensional multiresolution interpolation procedure is applied, the missing image points are filled in smoothly,as shown in Fig. 5c. In many cases, the result is so naturallooking that the flaw would not be detected except on closeRCA Engineer 30-5 Sept./Oct. 1985

Ogden/Adelson/Bergen/Burt: Pyramid-based computer graphics7

Fig. 5. Interpolation to fill missing points in an image.Fig. 6. Extrapolation example.examination. Figure 6 illustrates extrapolation when knownimage points represent only a small island within the imagedomain.Image mergingThe problemIt is frequently desirable to combine several source images intoa larger composite. Collages made up of multiple images areoften found in art and advertising, as well as in science (forexample, NASA's mosaic images of the planets). images caneven be combined to extend such properties as depth-of-fieldand dynamic range.The essential problem in image merging may be stated asone of "pattern conservation." Important details of the component images must be preserved in the composite, while n ospurious pattern elements are introduced by the merging process.Simple approaches to merging often create visible edge artifactsbetween regions taken from different source images.To illustrate the problems encountered in image merging,suppose we wish to construct a mosaic consisting of the left halfof an apple image, Fig. 7a, and the right half of an orange, Fig.7b. The most direct procedure is to simply join these imagesalong their center lines. However this results in a clearly visiblestep edge (Fig. 7c).An alternative approach is to join image components smoothlyby averaging pixel values within a transition zone centered on8Fig. 7. Multi-resolution spline of apple an orange. (a) Apple,(b) orange, (c) cut and paste composite (d) multi-resolutionpyramid mosaic.the join line. 3,4 The width of the transition zone is then a criticalparameter of the merging process. If it is too narrow, thetransition will still be visible as a somewhat blurred step. If it i stoo wide, features from both images will be visible within thetransition zone as in a photographic double exposure. Theblurred-edge effect is due to a mismatch of low frequencies alongthe mosaic boundary, while the double-exposure effect i sdue to a mismatch in high frequencies. In general there is n ochoice of transition zone width that can avoid both artifacts.RCA Engineer 30-5 Sept./Oct. 1985

Multiresolution splineWe can resolve the transition zone dilemma if the images aredecomposed into a set of bandpass components before they aremerged. A wide transition zone can then be used for the lowfrequency components, while a narrow zone is used for the highfrequency components. In order to have smooth blending, thewidth of the transition zone in a given band should be aboutone wavelength of the band's central frequency. The mergedbandpass components are then recombined to obtain the finalimage mosaic.Let S 0 , S 1 , S 2 , . Sk be a set of K source images. A set ofbinary mask images M o, M 1, M 2, . Mk determine how the sourceimages should be combined. Mk is "1" where source image Skis valid, and "0" elsewhere. Simply multiplying Sk 5 Mk andsumming over k would give a "cut and paste" composite withstep edges. Instead, we build a Laplacian pyramid Lk1 for eachsource image, and a Gaussian pyramid M k1 for each maskimage. A composite Laplacian pyramid Lk1 is formed by "cuttingand pasting" at each spatial scale by weighting each sourcepyramid level by its corresponding mask:Lcl (i,j) M k (i,j) Lkl (i,j)The final image is reconstructed from LC by expanding eachlevel and summing. Smooth blending is achieved because thetransition zone in each pyramid level is comparable to a wavelength of the central frequency of that level. When this procedureis applied to the apple and orange images of Fig. 7, an "orple"is obtained with no visible seam (Fig. 7d).MultifocusWhen assembling information from multiple source images weneed not always proceed region by region guided by maskimages. Some types of information can be merged in thepyramid node by node and be guided by the node's own value.Here we show how this type of merging can be used to extendthe depth-of-field of an image or increase its dynamic range.3Figures 8a and 8b show two exposures of a circuit boardtaken with the camera focused at different depth planes. Wewish to construct a composite image in which all the componentsand the board surface are in focus. Let LA and LB be Laplacianpyramids for the two source images. The low frequency levelsof these pyramids should have nearly identical values, sincechanges in focus have little effect on the low frequency components of the image. On the other hand, changes in focus willaffect node values in the pyramid levels where high spatialfrequency information is encoded. However, corresponding nodesin the two images will generally represent the same feature ofthe scene, and will differ primarily in attenuation due to blur.The node with the largest amplitude will be in the image that i smost nearly in focus. Thus, "in focus" image components canbe selected node-by-node in the pyramids rather than regionby-region in the original images. A pyramid LC is constructedfor the composite image by setting each node equal to thecorresponding node in LA or LB that has the larger absolutevalue:IfLAl (i,j) LBl (i,j)thenLCl (i,j) LAl (i,j)Ogden/Adelson/Bergen/Burt: Pyramid-based computer graphicsFig. 8. Multi-focus composite. (a, b) Two images of the samescene taken with different focuses, and (c) composite withextended depth-of-field.elseLCl (i,j) LBl (i,j)The composite image is then obtained simply by expanding andadding the levels of LC. Figure 8c shows an extended depth-of-fieldimage obtained in this ndThe problemWe will consider three different approaches to the problem ofcreating a realistic looking image. The first approach is to usethe computer as a paint box. No mathematical description ofthe scene is given. All the renderings, shading, shadows, andhighlights are done "by hand," as though the artist were using acanvas. The advantage of "paint box" approach is completeartistic control. The disadvantage is that it is time consuming t ocreate an image and difficult to make major changes withoutredrawing completely.A second approach is to create a three-dimensional mathematical "universe." The artist specifies the location of objects i nthis new world, their shapes and physical properties, and thelocation of light sources. A two-dimensional, photograph-likeimage of the three-dimensional world is made by tracing a largenumber of light rays as they are reflected, refracted and absorbed.The advantage of this "physics simulation" approach is thatvery realistic looking images can be created. This approach i salso flexible in that the viewing angle and properties of thecomponent parts can be changed as input parameters. Thedisadvantage is that it requires a complex physical model and alot of computation time.There is a third, "multiresolution," approach that lies somewhere between the first two and combines some of the advantages9

Fig.9. Multiresolution shadowing and shading of flat shapes.of each. As in the paint box approach, we are concernedprimarily with painting the two-dimensional image. The difference lies in the type of information on the artist's palette. Weusually think of a palette as an array of colors that can beblended and applied to an image. Using the pyramid we canextend the definition of palette to include multiresolution shapeand edge information as well as color and intensity. Multiresolution lowpass and bandpass copies of image features areextremely useful in creating special effects and in adding realismto an artifically generated shape. The advantage of this approachis that natural looking images can be generated quickly withoutresorting to an elaborate physics simulation. Artistic decisions aremade by viewing the two-dimensional image and the pyramidlevels and combining desired elements of each.An exampleAs an example of how an artist might use the pyramid as aspatial frequency palette, consider the problem of making flatshapes (Fig. 9a) appear three-dimensional by adding realisticlooking shadows and shading. Both the shadows and shadingresemble blurred copies of the original shape. Building a Gaussianpyramid of Fig. 9a, we select a lowpass copy that resembles softshadows (Fig. 9b). Comparing Fig. 9a and a slightly displaced9b pixel by pixel, and taking the maximum value at each point,10gives an image of shadowed paper cutouts floating or sitting o na glass-topped table (Fig. 9c). Now we need to add dimensionto the white cutouts. It has long been known that filtering animage with a "gradient" filter (1, -1) gives an effect of sideillumination. When gradient filtering is done at multiple resolutions, there is a great improvement in this bas-relief effect.Performing a combination of gradient and lowpass filtering o nFig. 9a gives us the low-frequency relief 9d. If the minimum ofFigs. 9d and 9a is taken, the result is an image of threedimensional-looking droplets (Fig. 9e). Finally, we add Fig. 9e t o9c to form shadowed droplets in Fig. 9f.Clearly, many other interesting graphic effects can be generated by imaginative use of the pyramid. It provides the artistwith a convenient and efficient way of accessing certain important features of an image—shapes and edges—at multiple resolutions. For certain problems, especially when computation facilities are limited, the multiresolution approach offers considerablerealism for little computation time.Pyramid generation of fractalsThe problemThe computer graphics community has adopted fractals as aremarkably effective way of synthesizing natural looking tex-RCA Engineer 30-5 Sept./Oct. 1985

Fig. 10. Cloud as a sum of random circles.Fig. 12. Pyramid generation of fractals.tures.5,6,7,8 The problem is to generate these textures quicklyusing multiresolution techniques.Fractals and the pyramidFig. 11. Coastline on three different spatial scales.Ogden/Adelson/Bergen/Burt: Pyramid-based computer graphicsTraditional mathematics has relied on idealized models of thecomplicated and irregular forms of nature. Structures such asclouds, mountains, and coastlines are difficult to describe i nterms of continuous, differentiable functions. Recently,Mandelbrot de

computer graphics on small systems without the complexities of physics simulations. Human beings have an intuitive feel for graphics. Graphics problems such as blending two images smoothly, interpolating to fill in missing image data, or creating realistic looking images

Related Documents:

10,339,828.3 cubic Pyramid Cubits. [(5,813.2355653 Pyramid Inches)/3 * 9 131 Pyramid Inches * 9 131 Pyramid Inches] The four faces of the pyramid are slightly concave, the only pyramid in Egypt to have been built this way. The centers of the four sides are indented with an extraordinary degree of precision. forming the only 8 sided pyramid in .

Volume of a Pyramid Words The volume V of a pyramid is one-third the product of the area of the base and the height of the pyramid. Algebra V 1 — 3 B h Height of pyramid Area of base EXAMPLE 1 Finding the Volume of a Pyramid Find the volume of the pyramid. V 1 — 3 Bh Write formula for volume. 1 — 3 (48)(9) Substitute. 144 Multiply.

Find the volume of each pyramid. 62/87,21 The volume of a pyramid is , where B is the area of the base and h is the height of the pyramid. The base of this pyramid is a right triangle with legs of 9 inches and 5 inches and the height of the pyramid is 10 inches. 16:(5 75

Your path to success with Pyramid Analytics for AWS Marketplace is: 1. Access the Pyramid 2020 Marketplace listing via the Pyramid Marketplace Seller page: AWS Marketplace: Pyramid Analytics BV (amazon.com) 2. Subscribe to Pyramid Analytics for AWS Marketplace a. This starts a 14 day free trial b. Pyramids default Marketplace EULA is the Amazon .

Computer Graphics & Image Processing 2003 Neil A. Dodgson 2 7 Course books Computer Graphics: Principles & Practice Foley, van Dam, Feiner & Hughes,Addison-Wesley, 1990 zOlder version: Fundamentals of Interactive Computer Graphics Foley & van Dam, Addison-Wesley, 1982 Computer Graphics &

Students will know that the base of a 4 sided pyramid is a square. Students will know that a 4 sided pyramid has 5 faces. Students will know that a 4 sided pyramid has 8 edges. Students will be able to build a triangle and square based pyramid. Title/Description of Lesson . Making a pyramid .Geometry in art and architecture

Introduction to Computer Graphics COMPSCI 464 Image credits: Pixar, Dreamworks, Ravi Ramamoorthi, . –Game design and development It is about –Learning the fundamentals of computer graphics –Implementing algorithms that are at the core of computer graphics . Fundamentals of Computer Graphics

Great Pyramid The largest pyramid is called the Great Pyramid. It was built for King Khufu near Cairo, Egypt. It took 30 years to build. This pyramid covers a large area and is 481 feet high. It was built with 2 million limestone blocks. The blocks were cut and moved without the large tools we use today. The Great Pyramidid 4 Barge