Many imaging tasks involve ill-posed problems, which require realistic priors. Standard convex optimization techniques use priors that prefer globally smooth images, and thus tend to give poor results. Graph cut methods, which permit edge-preserving priors for a restricted class of ill-posed problems, have proven quite successful over the last decade.
This research project will address an important but challenging class of ill-posed problems, namely those arising from rank-deficient linear inverse systems. Such underconstrained problems occur in medical imaging tasks such as MRI&CT image reconstruction and fMRI undistortion, as well as in traditional vision problems such as super- resolution. Currently these applications rely on convex optimization methods, which do not support realistic image priors. Yet existing graph cut methods cannot be applied due to some difficult theoretical issues.
To overcome these challenges we propose a collaboration between computer vision researchers and experts in graph algorithms. We will develop new graph constructions to address linear inverse systems, drawing heavily on state-of-the-art techniques from boolean optimization. To simplify our task we will exploit specific properties of the rank-deficient linear inverse systems that arise in the applications of interest. We will focus primarily on sparse structured linear inverse systems, an important subclass which contains all of the applications that drive our work. While our proposed work stresses algorithm development, we will also do a significant experimental evaluation of new algorithms on a range of applications, both to assess their performance and to identify promising new avenues.
This project brings together experts in computer vision, medical imaging and graph algorithms to address a problem of broad interest in a novel manner. The linear inverse systems that we are concerned with arise in a wide range of medical applications, as well as in other areas, yet current techniques have significant shortcomings. Our approach draws heavily on methods developed by the investigators over the last decade, which have proven quite successful for related problems. In addition, this project will strengthen the ties between researchers in computer vision and algorithms, which have proven to be quite beneficial to both areas.
Publications and additional material resulting from this project will be made available at www.cs.cornell.edu/~rdz/graphcuts.html
New computational and mathematical techniques were developed for an important class of problems that arise in many applications. These problems involve understanding ambiguous data from a sensor system, such as an MRI machine or a CT scanner. The underlying problems are extremely difficult to solve without making unrealistic assumptions about the general appearance of images (for example, assuming that there are no sharp boundaries). Our approach to this problem involved a close collaboration between computer scientists who come from very different parts of the discipline. In particular, we not only involved researchers and students with expertise in computer vision (which is where these problems have traditionally been addressed). We also brought in a number of collaborators, including two co-investators, who work on advanced mathematical techniques that have not been previous applied to these problems. The main results were published in the top peer-reviewed conferences and journals. Open source implementations of the main techniques were distributed, and are being used by other researchers. Students at different levels, including undergraduates, masters students and PhD students, participated fully in these research activities. Several women were funded, including a co-PI, two PhD students, and four undergraduates. One of our main goals was to build a bridge between different parts of the computer science community, by bringing in researchers with very different backgrounds to focus on a common problem of great practical importance. Our project resulted in many formal collaborations between such researchers (nearly all of our publications have authors from multiple areas of CS). In addition it produced many informal collaborations, for example resulting in join workshops, invited talks, and other grant applications.
