Improving My Image at SIAM Imaging Science 2006
September 24, 2006
Donald Geman, chair of the SIAM Activity Group on Imaging Science, with Margaret Cheney (middle), the group�s program director (and, with Brett Borden, presenter of a minitutorial on radar imaging at IS06), and Luminita Vese, who gave an invited talk titled �Minimization Models and Algorithms for Image Segmentation, Image Decomposition and Texture Modeling.�
Fadil Santosa
The 2006 SIAM Conference on Imaging Science took place May 15�17, in Minneapolis, Minnesota, the third in a series sponsored by the SIAM Activity Group on Imaging Science. The first was held in Boston (2002) and the second in Salt Lake City (2004). I was a member of the program committee for the 2004 meeting and this time, with Ron Kimmel (Technion�Israel Institute of Technology), Frank Natterer (University of M�nster), and Stanley Osher (UCLA), I was a co-chair of the committee. The conference was held in my "backyard"---the Radisson Metrodome, which is on the University of Minnesota campus. I was there from 7:30 AM on the first day, when registration opened, till 7:00 PM, at the conclusion of the last contributed talk on the last day.
I heard all the invited talks, went to two minitutorials, attended a business meeting, listened to several talks in both minsymposia and contributed sessions, and saw a number of posters. The quality of the presentations overall was extremely high. There was an air of excitement, with some speakers describing breakthroughs on several fronts in this growing field. I can't recall a conference I enjoyed more. It was nice to catch up with people I know and to make new acquaintances. Despite my fully disclosed enthusiasm, what follows is my best attempt at a "fair and balanced" view of the conference.
The importance of imaging science in a number of application areas makes it a growing field. The 280 participants represented diverse disciplines, a nice mix of researchers from universities, government laboratories, and industry, from the U.S. and from abroad (about 23%). Approximately a quarter of the participants were students (as compared with the 10�20% characteristic of SIAM conferences).
The availability of good sensors, together with improved data-collection and storage capabilities, has led to an unprecedented flood of information in the form of images. Don Geman (of Johns Hopkins University and, as of January 2006, chair of the SIAG on Imaging Science) divides the field of imaging science into three parts: sensors-to-images, images-to-images, and images-to-words. Sensor data need to be processed to produce images. With further processing of the images, salient information contained in them can be extracted. Finally, for use in decision making, the salient information needs to be analyzed. This division is only for convenience, Geman points out. The fact is that a lot of developments occur on the fuzzy boundaries of these three areas, and a lot mathematics goes into the developments.
The conference had several themes. One area that came in for a lot of attention is image formation and inverse problems, with applications to radar, tomography, medical imaging, and other areas. Image processing, both deterministic and probabilistic, including segmentation, inpainting, and registration, was a very visible thread in the conference. Speakers discussed several hot developments in imaging, as described in the following sections.
Minimalist Art
In the opening invited lecture, Emmanuel Cand�s (Caltech) described a new approach that he dubbed "compressive sampling." The basic idea is that most images have a sparse representation in some bases, meaning that the coefficients in those bases are mostly zeros. The question then becomes: How much information is needed to reconstruct such an image? The goal is to reconstruct the image from a few random projections. The work, which has connections with minimum total variation reconstruction, has opened up new opportunities for sensing and imaging.
Reconstruction of images with sparse representations was definitely among the hot topics of the conference. No fewer than five minisymposia were devoted to it, prompting Miki Elad (Technion), himself a major contributor to the area, to comment that "the sparse representation folks are densely represented in this conference." I attended a few of these sessions and was amazed that some of them were "standing room only." A lot of the credit for the excitement goes to Cand�s, who with Justin Romberg (Caltech) and Terence Tao (UCLA), proved an impressive result about the possibility of perfect reconstruction, given small amounts of data. The theoretical development, together with progress in optimization algorithms, has sparked a lot of interest in technology based on compressive sampling. Rich Baraniuk (Rice) and his team, to mention one ex-ample, have built a one-pixel camera based on this principle.
I Saw it in TV
It all started with successful efforts to denoise images by minimizing their total variation. The technique, pioneered by Rudin, Osher, and Fatemi, is now familiarly referred to as TV or min TV. Over the years it has become a tool to which practitioners in different imaging applications turn again and again. Because of its effectiveness, it has attracted the attention of powerful analysts who want to understand how it works and what its limitations are. The computational issues that arise are active areas of research. Amazingly, interest in this topic continues to grow. The IS06 program included many presentations on TV-based methods in imaging science.
Invited speaker Luminita Vese (UCLA) showed how TV can be used for texture and cartoon segmentation. Backing up her assertions with compelling reasons, she explained why classical analysis is the right tool for analyzing images, and how the insights gained can also lead to the development of effective algorithms. TV was also the thread that unified the many topics in Osher's very well-attended minitutorial.
Working in such a rich area, re-searchers in TV have taken many different directions. One interesting development is the use of geometric measure theory to study a TV-penalized denoising method, as discussed at the conference by Bill Allard (Duke University), Kevin Vixie (Los Alamos), and Selim Esedoglu (University of Michigan).
Computational approaches for solving TV-penalized problems remain a challenge and were also the subject of many presentations. Recently, graph-cut methods and second-order cone programming have been applied to TV problems.
Geometry amplification. Surface subdivision can be performed as a sequence of image processing operations, starting from a coarse description (a 33 x 33-pixel image) and finally producing a dense tessellation (a 257 x 257-pixel image). Surface normals are then computed on the smoothly subdivided surface; fine detail is reintroduced by displacing the surface along the normal direction by a scalar displacement image. All computations are performed as image processing operations on a GPU (graphics processing unit, commonly found in current PCs). From the invited talk "Geometry Images: Representing 3D Shape Using Regular Grids + Perfect Spatial Hashing" of Hugues Hoppe, Microsoft Research.
Mini Me
With IS06, minitutorials--two-hour sessions meant to be accessible to a general scientific audience--were introduced to the SIAM imaging conferences. The sessions ran concurrently with the minisymposia and contributed paper sessions. The program committee had arranged for three minitutorials: recent developments in graph-cut methods for minimization of energy in image processing (more on this below), presented by Ramin Zabih (Cornell University) and Ashish Raj (University of California San Francisco); radar imaging, including the underlying mathematics and remaining challenges, by Margaret Cheney (RPI) and Brett Borden (Naval Postgraduate School); and PDE-based image restoration, by Stan Osher in a fantastic solo performance. For me, this lecture brimmed with ideas and exciting results, and I left energized and wanting to take part in this lively research area. Given the success of the minitutorials---all very well attended---I vote for their inclusion in the program for the next conference.
The Kindest Cut
Many tasks in image processing can be posed as variational problems. An example arises in medical image segmentation, with the need to extract the parts of an image corresponding to, say, the heart. Such a task can be viewed as a combinatorial optimization problem, specifically an assignment or labeling problem. We have to decide whether a given pixel is part of the heart or not. To do so, we choose two color values and assign each pixel in the image to one or the other. We require that the segmented image remain close to the original image, and penalize (using TV, for example) for breaking the region into too many small pieces.
Boykov (University of Western Ontario) and Zabih (Cornell) were among the first to recognize the connection between such optimization problems and the minimum-cut problem arising in graphs. Exploiting the equivalence between min-cut and max-flow, first noticed by Ford and Fulkerson, they have devised very fast algorithms for solving the combinatorial minimization problem arising in many image processing tasks.
In their minitutorial, Zabih and Raj presented both the theoretical developments behind fast graph-cut algorithms and their practical applications. One application they discussed is a tool for photo montage (see images above). Imagine that you took a series of pictures at a dinner party. You find that there is not a single picture in which everyone at the table looks great. The stack of pictures, however, does contain a good picture of each person. The question is, How do you create a single picture in which everyone looks good? This turns out to be a job for min-cut: The problem, after a bit of user selection, can be posed as a combinatorial optimization problem.
A set of original photos on the left are combined so that only the "good" regions of each photo, as determined by the user, appear in the composite image on the right. The regions are sewn together using graph-cut energy minimization. Images courtesy of Aseem Agarwala; from Aseem Agarwala, Mira Dontcheva, Maneesh Agrawala, Steven Drucker, Alex Colburn, Brian Curless, David Salesin, Michael Cohen, Interactive Digital Photomontage, ACM Transactions on Graphics (Proceedings of SIGGRAPH 2004).
If I were to make a prediction, the use of discrete mathematics in imaging and in inverse problems may be the next growth area. For example, Boykov recently established a connection between graph-cut and level-set methods. Perhaps we will also see the use of continuous methods in the solution, or approximate solution, of discrete optimization problems.
Final Notes
The number of excellent talks far exceeded the space available here. But I do want to mention something about the other invited presentations. In a talk that exemplified how deep, and beautiful, mathematics can lead to the design of practical algorithms, Alexander Katsevich (University of Central Florida) discussed the mathematics underlying computed tomography. Hugues Hoppe (Microsoft Research) described his work in computer graphics, specifically the interplay between computational geometry, computer science, and analysis. His talk was richly illustrated with beautiful pictures (see example at lower left). Bob Hummel gave the audience a glimpse of several imaging-related projects that he managed during his tenure at DARPA. Among them is a new laser-based sensing method that is capable of seeing objects hidden by clutter, such as foliage.
Fr�d�ric Guichard presented work done at DxO Labs, which produces a suite of very successful software for processing digital photographs. He showed how images captured by a digital camera can be improved by correcting for lens aberration, poor lighting, and bad color interpolation. I was particularly impressed to learn that the company implements cutting-edge, mathematically sophisticated methods to accomplish these tasks. I saw hope for even my worst snapshots.
In all it was a wonderful conference for me. I look forward to the next, even if it takes place a few miles further from my of home base.
Fadil Santosa is a professor and director of the Minnesota Center for Industrial Mathematics at the University of Minnesota.
