IMS-Microsoft Research Workshop: Foundations of Data Science – Edge Detection on a Computational Budget: A Sublinear Approach

Edge Detection is an important task in image analysis. Various applications require real-time detection of long edges in large noisy images. Motivated by such settings, in this talk we’ll address the following question: How well can one detect long edges under severe computational constraints, that allow only a fraction of all image pixels to be processed ? We present fundamental lower bounds on edge detection in this setup, a sublinear algorithm for long edge detection and a theoretical analysis of the inevitable tradeoff between its statistical detection performance and the allowed computational budget. The competitive performance of our algorithm will be illustrated on both simulated and real images.

(Joint work with Inbal Horev, Meirav Galun, Ronen Basri (Weizmann) and Ery Arias-Castro (UCSD).)