Compression Algorithm Opens the Door to Widespread 3-D Application; Technique Compresses Geometric Data 12 Times More Efficiently Than MPEG4 Standard.

Business Editors

SIGGRAPH 2000

NEW ORLEANS--(BUSINESS WIRE)--July 26, 2000

Computer scientists from Bell Labs, the research and development arm of Lucent Technologies (NYSE: LU), and the California Institute of Technology have developed the first technique that makes it practical to transmit detailed three-dimensional data on the Internet and to work with this kind of data on personal computers.

At the SIGGRAPH 2000 Conference here this week, the researchers are announcing a breakthrough algorithm for what people in this field call "digital geometry compression." The breakthrough could have an impact in fields as diverse as manufacturing, entertainment, medicine, education and retail sales. Geometry in this sense refers to geometric representations of objects - anything from aircraft parts to cartoon characters - detailed information about size and shape with which 3-D virtual objects can be displayed, measured and manipulated. Digital geometric data is typically acquired by 3-D laser scanning and represents objects using dense meshes of millions or even billions of triangles.

The compression challenge is to use the fewest possible bits to store and transmit these huge, complex data sets, which do not yield to the kinds of processing techniques that have made digital audio, image and video applications commonplace. Efficient geometry compression - delivering the same quality with fewer bits or higher quality with the same bit budget - could supercharge 3-D applications found today at the high end of manufacturing and film making. It also could unlock the potential of high-end 3-D on consumer systems.

The researchers - led by Wim Sweldens of Bell Labs' Mathematical Sciences Research Center and Professor Peter Schroeder of Caltech's Computer Science Department, who is currently on leave at Bell Labs - report that their technique for geometry compression is 12 times more efficient than the method standardized in MPEG4 and six times more efficient than the best previously published method.

The scientific results presented this week could solve problems in every area of geometry processing technology, from data acquisition by 3-D scanning to noise removal, storage, transmission, authentication, editing and reproduction.

Several aspects of the Bell Labs / Caltech approach set it apart from other research in digital geometry processing. One is the team's original use of wavelet transformation, "wavelets" for short, a mathematical technique that has solved a surprising variety of practical problems since its emergence in the early 1980s. Wavelet transformation is complementary to Fourier transforms, long-established techniques for processing signals and analyzing physical data.

"Geometry is poised to become the fourth wave of digital multimedia communication," Sweldens said. "The first three waves - sound in the 1970s, images in the '80s, and video in the '90s - were enabled by signal processing based on Fourier transforms. This kind of signal processing simply cannot handle geometry. Wavelets can."

In fact, the first generation of wavelets, which were built on Fourier transforms, did not handle the geometry of curved surfaces well. One of Sweldens's earlier fundamental contributions was the development of a technique called "lifting," an efficient way to generate wavelets without Fourier transforms. (Although developed with geometry in mind, lifting proved to be effective in other areas as well; it was recently incorporated into the JPEG 2000 standard for image compression.)

Producers of animated films and video games are expected to be among the early adopters of wavelet-based geometry compression. "Imagine a multiplayer, Internet-based video game that looks as good as Toy Story," Schroeder said. But the potential applications go far beyond entertainment.

"Manufacturing companies that can justify a huge investment in systems for 3-D scanning and digital geometry processing have already begun using this technology to create virtual parts catalogues," Schroeder said. "They can use geometric representations when they put out requests for parts, use geometry to guide fabrication equipment, and compare scans of newly made parts to the original designs. Now, if you drastically reduce the cost of this technology while improving the quality of applications, geometry processing is likely to be used in many more parts of the manufacturer's enterprise, from design to sales and order fulfillment. Also, the technology becomes something that small manufacturers, potentially every manufacturer, can and will use."

Mass customization is another likely application. For example, a clothing company might take 3-D scans of customers, transmit the geometric representations to a factory, and ship tailored goods to the customers' homes.

Though tools for working with geometry are being developed first by and for manufacturers, film makers and other high-end users, consumer applications may not lag far behind. "Think of real estate," Sweldens said. "Today someone selling a house puts pictures of all the rooms on the Web. Soon the seller may be putting a video walkthrough of the house on the Web. When geometry processing reaches the desktop - in software like today's digital photo and video editors - you'll not only be able to see any view of any room in the house, but you'll also be able to see how it will look after you knock out a wall, repaint the rooms, and drop in new furniture from a 3-D catalogue."

Improvements in digital geometry compression, which are measured in terms of the number of bits per vertex needed to describe a mesh of triangles within a given margin of error, can be exploited in the same ways as gains in other kinds of compression. Application designers, and ultimately end users, will be able to trade off bits or bandwidth for the quality of 3-D representations. Tested against other approaches, the Bell Labs / Caltech method proved to be superior across the board and especially effective in enabling high-quality reproduction with relatively few bits.

This is the sixth year running that the extremely competitive technical program of the annual SIGGRAPH conference - considered the premiere international event showcasing scientific research and new developments in computer graphics and interactive technology - has featured papers by Sweldens, Schroeder, and their collaborators. The results published this week augment an increasingly complete toolbox for digital geometry processing that the team has been developing since 1994.

The researchers' latest breakthrough in compression was built on their earlier achievements, including the generalization of wavelets to represent spherical data and arbitrary geometries. It also exploited their research on meshes, particularly their insight that two of three types of coordinates used to describe a mesh consume a large fraction of the bit budget but contribute very little to quality. Another key element was the collaborators' original contribution to "subdivision," a novel way of building smooth surfaces.

Like other areas of wavelet research - which is known for bringing together mathematicians and computer scientists, theorists and engineers - digital geometry processing has inspired collaboration across boundaries that sometimes separate disciplines and institutions. Collaboration between Sweldens and Professor Ingrid Daubechies of Princeton University has focused primarily on the theoretical side of wavelets, yet has had an impact on the applied side as well. In addition to Sweldens and Schroeder, collaborators who have contributed to the current work are: Andrei Khodakovsky and Igor Guskov at Caltech; Kiril Vidimce at Mississippi State University; David Dobkin and Aaron Lee at Princeton; and Lawrence Cowsar at Bell Labs, Lucent Technologies.

More information on the annual SIGGRAPH conference can be found at www.siggraph.org. The papers "Progressive Geometry Compression" and "Normal Meshes" are available at http://cm.bell-labs.com/who/wim/papers/compression and http://cm.bell-labs.com/who/wim/papers/normalmesh.

Bell Labs is celebrating its 75th anniversary this year. One of the most innovative R&D entities in the world, Bell Labs has generated more than 40,000 inventions since 1925. It has played a pivotal role in inventing or perfecting key communications technologies for most of the 20th century, including transistors, digital networking and signal processing, lasers and fiber-optic communications systems, communications satellites, cellular telephony, electronic switching of calls, touch-tone dialing, and modems.

Today, Bell Labs continues to draw some of the best scientific minds. With more than 30,000 employees located in 25 countries, it is the largest R&D organization in the world dedicated to communications and the world's leading source of new communications technologies. In a recent report, Technology Review magazine said Bell Labs patents had the greatest impact on telecommunications for 1999.

Lucent Technologies, headquartered in Murray Hill, N.J., USA, designs and delivers the systems, software, silicon and services for next-generation communications networks for service providers and enterprises. Backed by the research and development of Bell Labs, Lucent focuses on high-growth areas such as broadband and mobile Internet infrastructure; communications software; communications semiconductors and optoelectronics; Web-based enterprise solutions that link private and public networks; and professional network design and consulting services. For more information on Lucent Technologies and Bell Labs, visit the Web sites http://www.lucent.com and http://www.bell-labs.com.

Founded in 1891, Caltech has an enrollment of some 1900 students, and an academic staff of about 280 professorial faculty and 130 research faculty. The Institute has more than 19,000 alumni. Caltech employs a staff of more than 2000 on campus and 4700 at JPL.

Over the years, 28 Nobel Prizes and four Crafoord Prizes have been awarded to faculty members and alumni. Forty-five Caltech faculty members and alumni have received the National Medal of Science; and eight alumni (two of whom are also trustees), two additional trustees, and one faculty member have won the National Medal of Technology. Since 1958, 13 faculty members have received the annual California Scientist of the Year award. On the Caltech faculty there are 77 fellows of the American Academy of Arts and Sciences; and on the faculty and Board of Trustees, 69 members of the National Academy of Sciences and 48 members of the National Academy of Engineering. For more information on Caltech, visit its Web site at http://www.caltech.edu.