Discussion of Cheeseman's An inquiry into computer understanding

We discuss some points on which we agree, and others on which we disagree, with Cheeseman's target article. Particular agreements include the need for an eclectic approach; disagreements include the misleading distinction between probabilistic and logical reasoning regarding the notion of truth, and also some matters of nonmonotonicity.     

Recognition of spatial point patterns

Complex patterns may sometimes be efficiently represented by a small number of points extracted from the image on the basis of atypical properties of neighborhoods of the points. In this paper we describe theoretical and experimental results on the use of sequences of interpoint distances extracted from a noisy point image to match the image with one of a set of prototypes. Minimal spanning tree and nearest neighbor distances are used for these computations. The methods applied are invariant under translation and rotation of the image and could be made invariant to scale changes. Several distance measures between classes are defined. Sufficient conditions for the separability of classes are given in terms of these measures.     

Gradient Based Image Motion Estimation Without Computing Gradients

Computing an optical flow field using the classical image motion constraint equation is difficult owing to the aperture problem and the need to compute the image intensity derivatives via numerical differentiation—an extremely unstable operation. We integrate the above constraint equation over a significant spatio-temporal support and use Gauss's Divergence theorem to replace the volume integrals by surface integrals, thereby eliminating the intensity derivatives and numerical differentiation. We tackle the aperture problem by fitting an affine flow field model to a small space-time window. Using this affine model our new integral motion constraint approach leads to a robust and accurate algorithm to compute the optical flow field. Extensive experimentation confirms that the algorithm is indeed robust and accurate.     

An improved branch and bound algorithm for computing k-nearest neighbors

In 1975 Fukunaga and Narendra proposed an efficient branch and bound algorithm for computing k-nearest neighbors. Their algorithm, after a hierarchical decomposition of the design set into disjoint subsets, employs two rules in order to eliminate the necessity of calculating many distances. This correspondence discusses the applicability of two additional rules for a further reduction of the number of distance computations. Experimental results using samples from bivariate Gaussian and uniform distributions suggest that the number of distance computations required by the modified is typicaly one fourth of that of the Fukunaga-Narendra algorithm.     

General Branch and Bound,and its relation to A1 and AO1

Branch and Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. Various heuristic search procedures used in artificial intelligence (AI) are considered to be related to B&B procedures. However, in the absence of any generally accepted terminology for B&B procedures, there have been widely differing opinions regarding the relationships between these procedures and B&B. This paper presents a formulation of B&B general enough to include previous formulations as special cases, and shows how two well-known AI search procedures (A1 and AO1) are special cases of this general formulation.