January 1972 - Vol. 15 No. 1
Features
Pictorial pattern recognition and the phase problem of x-ray crystallography
The availability of interactive, three-dimensional, computer graphics systems coupled to powerful digital computers encourages the development of algorithms adapted to this environment. Pictorial pattern recognition techniques make possible a number of approaches to X-ray structure determination based on molecular model building, i.e. the use of chemical information to frame “structural hypotheses” which can computationally be tested and refined by reference to the experimental data.
Application of standard pattern recognition algorithms is hindered by the fact that the cross-correlation between a model and the correct structure cannot be computed because of a fundamental incompleteness in the measured data. However, it is possible to compute an upper bound to such a cross-correlation. A simple example demonstrates that this information can be the basis of a technique for structure determination that can make effective use of an interactive graphics system.
Model building by cross-correlations has intrinsic advantages over usual crystallographic techniques based on the autocorrelation or Patterson function, especially for large structures. This is significant, for crystallography of biological macromolecules has been and will continue to be a field of intense interest.
On shrinking binary picture patterns
A parallel processing algorithm for shrinking binary patterns to obtain single isolated elements, one for each pattern, is presented. This procedure may be used for counting patterns on a matrix, and a hardware implementation of the algorithm using large scale integrated tecnology is envisioned. The principal features of this method are the very small window employed (two-by-two elements), the parallel nature of the process, and the possibility of shrinking any pattern, regardless of the complexity of its configuration. Problems regarding merging and disconnection of patterns during the process as well as the determination of the maximum number of steps necessary to obtain a single isolated element from a pattern, are reviewed and discussed. An analogy with a neural network description, in terms of McCulloch-pitts “neurons” is presented.
Use of the Hough transformation to detect lines and curves in pictures
Hough has proposed an interesting and computationally efficient procedure for detecting lines in pictures. This paper points out that the use of angle-radius rather than slope-intercept parameters simplifies the computation further. It also shows how the method can be used for more general curve fitting, and gives alternative interpretations that explain the source of its efficiency.
A text-editing and manipulation program is described. The program operates from low-cost cathode-ray tube entry and display stations with keyboard and 13 function buttons. Applications, potential economy of operation, and some aspects of implementation are discussed.
Teacher/student authored CAI using the NEWBASIC system
The pedagogical advantages of a general purpose interactive system called NEWBASIC/CATALYST are discussed. NEWBASIC/CATALYST incorporates an advanced implementation of BASIC, system-level interactive features, and a general capability for extension through user oriented function attachment. Application of this last feature to provide a flexible CAI scan capability is illustrated. An example of interaction at the system level shows how students can mix the advantages of independent or “solo” mode computing with those of guided or “dual” mode interaction. Preliminary experience with the system in an urban secondary school setting is discussed.
MUSE: a model to understand simple English
MUSE is a computer model for natural language processing, based on a semantic memory network like that of Quillian's TLC. MUSE, from a Model to Understand Simple English, processes English sentences of unrestricted content but somewhat restricted format. The model first applies syntactic analysis to eliminate some interpretations and then employs a simplified semantic intersection procedure to find a valid interpretation of the input. While the semantic processing is similar to TLC's, the syntactic component includes the early use of parse trees and special purpose rules. The “relational triple” notation used during interpretation of input is compatible with MUSE's memory structures, allowing direct verification of familiar concepts and the addition of new ones. MUSE also has a repertoire of actions, which range from editing and reporting the contents of its own memory to an indirect form of question answering. Examples are presented to demonstrate how the model interprets text, resolves ambiguities, adds information to memory, generalizes from examples, and performs various actions.
Quadratic programming for nonlinear regression
A quadratic programming algorithm is described for use with the magnified diagonal method of nonlinear regression with linear constraints. The regression method is published in JACM, July 1970.
Algorithm 418: calculation of Fourier integrals [D1]
The most commonly used formula for calculating Fourier integrals is Filon's formula, which is based on the approximation of the function by a quadratic in each double interval. In order to obtain a better approximation the cubic spline fit is used in [1]. The obtained formulas do not need the explicit calculation of the spline fit, but in addition to the function values at all intermediate points, the values of the first and second derivatives at the boundary points are required. However, these values are often obtained from symmetry conditions. If the derivatives at the end-points are unknown, they may be calculated from a cubic spline fit, for example by using some exterior points or by using two extra interior conditions for the spline fit. It can also be noted that in certain periodic cases the terms containing the derivatives will cancel, and their values will be superfluous. The use of Algorithm 353 [2] is recommended if the frequency &ohgr;/&pgr; is a positive integer and the interval is [0,1]. Test computations reported in [1] indicate that the spline formula is more accurate than Filon's formula. Both are of the fourth order. The expansion of the error term in powers of the step length contains only even powers, and therefore the use of Richardson extrapolation is very efficient.
