Fast computation of the SVM decision function over an image using minimal RAM.
Machine learning techniques have shown considerable promise for automating common visual inspection tasks. For example, Support Vector Machine (SVM) classifiers that have been learned from labeled training data deliver strong detection performance both for finding human faces in photographs and locating geologic landforms such as craters and volcanoes in planetary images gathered by spacecraft. However, SVMs are computationally expensive to apply to an image using the traditional spatial scanning method in which a rectangular window is slid across the image one pixel at a time and the SVM is evaluated on each patch of pixels under the window. The new software uses small fast Fourier transforms (FFTs) and the overlap- and-add technique from signal processing to quickly and efficiently compute the exact SVM decision function over an entire image using minimal random access memory (RAM).
SVMs classify a feature vector by computing a weighted combination of kernel evaluations between the feature vector and a set of “support vectors.” The support vectors are positive and negative examples from the training set that were identified during the learning phase. Each kernel evaluation is essentially a nonlinear measurement of the similarity between the feature vector and a given support vector. For many of the commonly used kernels, the kernel evaluation can be expressed as a linear dot product between the feature vector and the support vector followed by additional nonlinear operations. The linear part of the computation actually dominates the workload, which enables the software to achieve a significant speedup by performing the linear calculations over the entire image with FFTs. A further refinement uses the overlap-andadd technique to limit the amount of RAM required. Overlap-and-add computes small, localized FFTs and then pieces partial results together to establish the final answer.
The software provides an effective way to apply SVMs to image data and is particularly well suited for resource-constrained environments such as onboard a spacecraft. The technique allows exact computation of the SVM decision function over an image using minimal RAM (typically less than 5% of the size of the image). Also, the approach is complementary to “reduced set” methods, which speed up SVM calculations by reducing the number of support vectors required. Used together, the two methods can yield a multiplicative gain in performance. The software implementation is not specific to any particular domain. Thus far, it has been demonstrated for the crater detection problem; however, in principle, it can be used for a variety of image inspection tasks. One could envision a variety of smartphone apps based around the ability to take a picture and detect/classify/count objects in the picture.