Technical Reports

The ICICS/CS Reading Room

1978 UBC CS Technical Report Abstracts

TR-78-01 Exploiting Spectral, Spatial and Semantic Constraints in the Segmentation of Landsat Images, February 1978 Dale Starr and Alan K. Mackworth

A critique of traditional classification techniques for LANDSAT images and consideration of some scene analysis techniques, exploiting spatial organization and meaning, lead to a new approach to computer programs for LANDSAT image understanding. To justify this approach, a program that combines modified maximum likelihood techniques with interpretation-controlled region merging methods to interpret forest cover in LANDSAT images is described. For comparison purposes, a pure supervised classifier using the same data made 43% more errors and produced a segmentation twice as complex.

TR-78-02 Forests and Pyramids: Using Image Hierarchies to Understand Landsat Images, March 1978 Ezio Catanzariti and Alan K. Mackworth

Computer-based Landsat image interpretation has neglected the spatial organization of the image in favour of the spectral and temporal organization. A brief survey of techniques that exploit spatial information, including multistage sampling, is given. Semantically-guided region-merging methods have been used successfully but they require sophisticated and expensive list processing facilities. Similar semantic and spatial sensitivity can be introduced by exploiting a pyramidal, hierarchical representation of the image advocated by Kelly, Tanimoto and Levine. The image pyramid is constructed bottom-up with the original image as the base. Each level is a reduced resolution version of the level below, constructed by averaging the signatures of adjacent pixels at the lower level. By classifying pixels at the higher levels one is efficiently classifying semantically uniform regions in the original image. If, however, a region's signature lies in the spectral overlap of two or more classes its subregions will have to be considered for classification. Several refinements of this technique, including the use of semantically-based region splitting and merging techniques at each level of the pyramid, are described. .br These techniques are used to classify forest cover types on Vancouver Island in a Landsat image. The results of several initial experiments indicate that, compared to a baseline of a traditional supervised maximum-likelihood classifier, the cost of maintaining the pyramid is balanced by the vast reduction in the number of pixel classifications. The spatial homogeneity or readability of the segmented image, as measured by the number of regions, is improved by a factor of three while the accuracy of the classification is unaffected or slightly improved. When the region splitting and merging techniques are applied at each level of the imaqe pyramid the accuracy and the readability of the final segmentation both increase markedly. It is thereby demonstrated that these pyramidal techniques offer many of the advantages of the semantically-driven region-merging approach in a more flexible and efficient fashion. Indeed the two approaches have been combined to achieve substantial benefits for Landsat image interpretation.

TR-78-03 A Procedural Model of Recognition for Machine Perception, March 1978 William S. Heavens

This thesis is concerned with aspects of a theory of machine perception. It is shown that a comprehensive theory is emerging from research in computer vision, natural language understanding, cognitive psychology, and Artificial Intelligence programming language technology. A number of aspects of machine perception are characterized. Perception is a recognition process which composes new descriptions of sensory experience in terms of stored steriotypical knowledge of the world. Perception requires both a schema-based formalism for the representation of knowledge and a model of the processes necessary for performing search and deduction on that representation. As an approach towards the development of a theory of machine perception, a computational model of recognition is presented. The similarity of the model to formal mechanisms in parsing theory is discussed. The recognition model integrates top-down, hypothesis-driven search with bottom-up, data-driven search in hierarchical schemata representations. Heuristic procedural methods are associated with particular schemata as models to guide their recognition. Multiple methods may be applied concurrently in both top-down and botton-up search modes. The implementation of the recognition model as an Artificial Intelligence programming language called MAYA is described. MAYA is a multiprocessing dialect of LISP that provides data structures for representing schemata networks and control structures for integrating top-down and bottom-up processing. A characteristic example from scene analysis, written in MAYA, is presented to illustrate the operation of the model and the utility of the programming language. A programming reference manual for MAYA is included. Finally, applications for both the recognition model and MAYA are discussed and some promising directions for future research proposed.

TR-78-04 An Approach to the Organization of Knowledge for the Modelling of Converstion, February 1978 Gordon I. McCalla

This report describes an approach to modelling conversation. It is suggested that to succeed at this endeavour, the problem must be tackled principally as a problem in pragmatics rather than as one in language analysis alone. Several progmatic aspects of conversation are delineated and it is shown that the attempt to account for them raises a number of general issues in the representation of knowledge. .br A scheme for resolving some of these issues is presented and given computational description as a set of (non-implemented) LISP-based control structures called $\mid$LISP. Central to this scheme are several different types of objects that encode knowledge and communicate this knowledge by passing messages. One particular kind of object, the pattern expression ($\mid$PEXPR), turns out to be the most versatile. $\mid$PEXPRs can encode an arbitrary amount of procedural or declarative information; are capable, as a by-product of their message passing behaviour, of providing both a context for future processing decisions and a record of past processing decisions; and make contributions to the resolution of several artificial intelligence problems. .br Some examples of typical conversations that might occur in the general context of attending a symphony concert are then explored, and a particular model of conversation to handle these examples is detailed in $\mid$LISP. The model is goal oriented in its behaviour, and, in fact, is described in terms of four main goal levels: higher level non-linguistic goals; scripts directing both sides of a conversation; speech acts guiding one conversant's actions; and, finally, language level goals providing a basic parsing component for the model. In addition, a place is delineated for belief models of the conversants, necessary if utterances are to be properly understood or produced. The embedding of this kind of language model in a $\mid$LISP base yields a rich pragmatic environment for analyzing conversation.

TR-78-05 On the Efficent Implementation of Implicit Runge-Kutta Methods, May 1978 James M. Varah

Extending some recent ideas of Butcher, we show how one can efficiently implement general implicit Runge-Kutta methods, including those based on Gaussian quadrature formulas which are particularly useful for stiff equations. With this implementation, it appears that these methods are more efficient than the recently proposed semi-explicit methods and their variants.

TR-78-06 The Design and Implementation of a Run-Time Analysis and Interactive Debugging Environment, January 1978 Mark Scott Johnson

TR-78-07 Optimization of Memory Hierarchies in Multi-programmed Computer Systems with Fixed Cost Constraint, January 1978 Samuel T. Chanson and Prem Swarup Sinha

This paper presents, using queuing theory and optimization techniques, a methodology for estimating the optimal capacities and speeds of the memory levels in a computer system memory hierarchy operating in the multiprogrammed environment. Optimality is with respect to mean system response time under a fixed cost constraint. It is assumed that the number of levels in the hierarchy as well as the capacity of the lowest level are known. The effect of the storage management strategy is characterized by the hit ratio function which, together with the device technology cost functions are assumed to be representable by power functions. It is shown that as the arrival rate of processes and/or the number of active processes in the system increase, the optimal solution deviates considerably from that under a uniprogrammed environment.

TR-78-08 Solving Boundary Value Problems with a Spline-Collocation Code, January 1978 Uri Ascher

TR-78-09 Stability Restrictions on Second Order, Three Level Finite Difference Schemes for Parabolic Equations, December 1978 James M. Varah

In this paper we are concerned with second order schemes which are easy to use, and apply readily to nonlinear equations. We examine the stability restrictions for such schemes using linear stability analysis, and illustrate their behaviour on Burgers' equation.

If you have any questions or comments regarding this page please send mail to