"Fast, Accurate Detection of 100,000 Object Classes on a Single Machine"
(CVPR 2013 Best Paper Award)
-- Mark Ruzon, Google
Abstract
Many object-detection systems are constrained by the time required to convolve a target image with a bank of filters that code for different aspects of an object's appearance, such as the presence of component parts.
We exploit locality-sensitive hashing to replace the dot-product kernel operator in the convolution with a fixed number of hash-table probes that effectively sample all the filter responses in time independent of the size of the filter bank. To show the effectiveness of the technique, we apply it to evaluate 100,000 deformable-part models requiring more than a million (part) filters on multiple scales of a target image in less than 20 seconds using a single multi-core processor with 20GB of RAM.
This represents a speed-up of approximately 20,000 times - four orders of magnitude - when compared with performing the convolutions explicitly on the same hardware. While mean average precision over the full set of 100,000 object classes is about 0.16, due in large part to the challenges in gathering training data and collecting ground truth for so many classes, we achieve a mAP of at least 0.20 on a third of the classes and 0.30 or better on about 20 percent of the classes.
Biography
Ruzon received a bachelor's from USC and a master's and Ph.D. from Stanford University, where he wrote the seminal paper on natural image matting. After school he worked at Adobe and two startups, the second of which, SnapTell, had an app featured in an iPhone commercial. After SnapTell was acquired by Amazon.com in 2009, he worked for a year at Amazon's search engine, A9.com, before joining Google. He worked in Google Research for two years on object detection for YouTube before joining the Street View team in April.
