A factorization approach to grouping

The foreground group in a scene may be 'discovered' and computed as a factorized approximation to the pairwise affinity of the elements in the scene. A pointwise approximation of the pairwise affinity information may in fact be interpreted as a 'saliency' index, and the foreground of the scene may be obtained by thresholding it. An algorithm called 'affinity factorization' is thus obtained which may be used for grouping. The affinity factorization algorithm is demonstrated on displays composed of points, of lines and of brightness values. Its relationship to the Shi-Malik normalized cuts algorithms is explored both analytically and experimentally. The affinity factorization algorithm is shown to be computationally efficient (O(n) floating-point operations for a scene composed of n elements) and to perform well on displays where the background is unstructured. Generalizations to solve more complex problems are also discussed.