Laszlo Babai, University of Chicago

Abstract We describe a new efficient algorithm to find the min-convolution and more generally, the rank-convolution of a function (grayscale image) with an arbitrary binary function (the mask). We also mention related algorithms by Felzenszwalb that work more efficiently when the mask has special properties such as convexity. We indicate the significance of such algorithms to a number of areas in image processing, including object recognition, image registration, and belief propagation, the latter having applications to image restoration and to depth estimation/3D reconstruction.

Joint work with Pedro Felzenszwalb.

Bio Laszlo Babai is a professor of computer science and mathematics at the University of Chicago. His research areas include algorithms and complexity theory as well as areas of pure mathematics (combinatorics and group theory). He shared the 1993 Goedel Prize for introducing the concept of interactive proofs. He feels fortunate to have Pedro Felzenszwalb, a junior colleague with phenomenal vision, next door.