Needles in a haystack: Fast spatial search for targets in similar-looking backgrounds

This paper develops an efficient and robust algorithm that simultaneously detects and locates image anomalies and intrusions. Anomalies refer to image regions that do not belong to expected classes. In situations where most of the image is of one or more types of known background classes while a few isolated regions may belong to unknown classes, the algorithm detects and locates potential intrusions by blanking regions it classifies as members of the known classes. We used a combination of Fourier filtering, a fast linear way to scan the content of the whole scene in parallel, with Margin-Setting, a powerful nonlinear discriminant trained to distinguish members of known classes from everything else. That combination retains the power of Margin-Setting and the simplicity, speed, and locating ability of Fourier filtering. Examples show the ability of this method to remove essentially all background material while leaving the similar looking intrusions intact. The classifier is trained using a few small square patches extracted from images or image regions representing the background classes of interest. Processed images related to four different problems as well as cumulative numerical results of many tests performed on one of those problems are presented. Excellent performance is observed for the examples considered here.