Technical Reports

## 1985 UBC CS Technical Report Abstracts

TR-85-01 Recognizing VLSI Circuits from Mask Artwork, January 1985 Amir Alon and William S. Havens

The design of Very Large Scale Integrated (VLSI) circuits remains an art despite recent advances in Computer Assisted Design (CAD) techniques. Unfortunately, the sophistication of the design procss has not kept pace with the VLSI hardware technology. Very expensive errors proliferate into fabrication despite powerful design rule checkers and circuit simulators. We have developed an alternative approach derived from research in knowledge representation and schema-based computer vision. The system implemented recognizes an abstract logic function description of the VLSI circuit from its mask layout artwork. Our technique reverses the desiFn process thereby recovering the logical function actually fabricated in the chip. No simulation is necessary and conceptually all logical design errors can be detected. The work is a direct application of schema labelling techniques which were developed for the Mapsee2 sketch map understanding system. This prototype system has been tested on a number of logical chip designs with correct results. Some results are presented.

TR-85-02 Recovering Shape \& Determining Attitude from Extended Gaussian Images, April 1985 James Joseph Little

This dissertation is concerned with surface representations which record surface properties as a function of surface orientation. The Extended Gaussian Image (EGI) of an object records the variation of surface area with surface orientation. When the object is polyhedral, the EGI takes the form of a set of vectors, one for each face, parallel to the outer surface normal of the face. The length of a vector is the area of the corresponding face.

The EGI uniquely represents convex objects and is easily derived from conventional models of an object. An iterative algorithm is described which converts an EGI into an object model in terms of coordinates of vertices, edges, and faces. The algorithm converges to a solution by constrained optimization. There are two aspects to describing shape for polyhedral objects: first, the way in which faces intersect each other, termed the adjacency structure, and, second, the location of the faces in space The latter may change without altering the former, but not vice versa. The algorithm for shape recovery determines both elements of shape. The continuous support function is described in terms of the area function for curves, permitting a qualitative companson of the smoothness of the two functions. The next Section describes a method of curve segmentation based on extrema of the support function. Because the support function varies with translation, its behaviour under translation is studied, leading to proposals for several candidate centres of support. The study of these ideas suggests some interesting problems in computational geometry.

The EGI has been applied to determine object attitude, the rotation in 3-space bringing a sample object into correspondence with a prototype. The methods developed for the inversion problem can be applied to attitude determination. Experiments show attitude determination using the new method to be more robust than area matching methods. The method given here can be applied at lower resolution of orientation, so that it is possible to sample the space of attitudes more densely, leading to increased accuracy in attitude determination.

The discussion finally is broadened to include non-convex objects, where surface orientation is not unique. The generalizations of the EGI do not support shape reconstruction for arbitrary non-convex objects. However, surfaces of revolution do allow a natural generalization of the EGI The topological structure of regions of constant sign of curvature is invariant under Euclidcan motion and may be useful for recognition tasks.

TR-85-03 A Fast Divide \& Conquer Protocol for Contention Resolution on Broadcast Channels, April 1985 Karl Abrahamson

We describe a contention resolution protocol for an ethernet-like broadcast channel The protocol is based on tree algorithms, particularly that of Greenberg. We show how to obtain a simpler and more accurate estimate of the number of contending stations than Greenberg's method, and use the new estimation method to obtain an improved protocol.

TR-85-04 LNTP --- An Efficient Transport Protocol for Local Area Networks, February 1985 Samuel T. Chanson, K. Ravindran and Stella Atkins

As interests in local area networks (LANs) grow so is the demand for protocols that run on them. It is convenient and a common practice to adopt existing transport protocols that had been designed for long haul networks (LHNs) for use in LANs. DARPA's Transmission Control Protocol/lnternet Protocol (TCP/IP) for example, is available in 4.2 BSD UNIX for interface to Ethernet and other LANs. This is not desirable from a performance standpoint as the control structure is usually much more complex than is necessary, and LANs and LHNs have very different characteristics. Though there exists simpler transport protocols such as the User Datagram Protocol (UDP) most do not provide adequate flow control which, because of the much higher channel speed, is critical in the LAN environment.

This paper discusses the unique characteristics and requirements of LANs and describes a new transport level protocol (LNTP) specifically designed for use on LANs. The fundamental philosophy in the design of LNTP is simplicity. Any features irrelevant to the LAN environment is not included. As well, LNTP uses a simple but effective deferred flow control mechanism which is activated only when the traffic intensity exceeds some value. This protocol has been implemented and runs under 4.2 BSD UNIX in place of TCP/IP. Detailed comparisons between LNTP, TCP and a few other protocols are given in the paper. Measurement data showed an improvement in network throughput rate of at least 30%, over that of TCP. The problem of internet communication is also addressed.

TR-85-05 On Process Aliases in Distributed Kernel Design, April 1985 K. Ravindran and Samuel T. Chanson

As distributed computing systems become popular because of their functional, economics and reliability characteristics, a new class of problems has emerged. These problems are characterized by the fact that the resources being used by a process as well as the system state is distributed. The management of the processes and resources in such an environment present a challenge that cannot be satisfactorily met by the traditional procedural-based methods which often assume the existence of shared memories. This paper presents a multiagent structure consisting of corporate processes and their associated aliases as an efficient and systematic solution to this class of problems. The model and the kernel primitives necessary to implement the model together with some design considerations are outlined. An example described in terms of the model is also given.

TR-85-06 Performance Evaluation of the ARPANET Transmission Control Protocol in a Local Area Network Environment, July 1985 Samuel T. Chanson, K. Ravindran and Stella Atkins

The Transmission Control Protocol (TCP) of ARPANET is one of the most popular transport level communication protocols in use today. Originally designed to handle unreliable and hostile subnets in a long-haul network TCP has been adopted by many local area networks (LAN) as well. It is, for example, available in 4.2 BSD UNIX for interface to Ethernet and several other LAN technologies. This is convenient but not desirable from a performance standpoint since the control structure is far more complex than is necessary for LANs.

This paper describes what we learned in measuring and tuning the performance of TCP in transferring large files between two hosts of different speeds over the Ethernet. Models are presented which allow the optimal buffer size and the flow control parameter to be determined. Based on observed traffic patterns and those reported elsewhere, we formulated guidelines for the design of transport protocols for a single LAN environment. We then present a new, much simpler LAN transport level protocol which replaces TCP with significant improvement in network throughput. Internet packets will use the full TCP. This is done at the gateway. Since the majority of the packets in a LAN are for local usage, this scheme improves the overall network throughput rate as well as the mean packet delay time.

TR-85-07A Hierarchical Arc Consistency: Exploiting Structured Domains in Constraint Satisfaction Problems, June 1985 Alan K. Mackworth, Jan A. Mulder and William S. Havens

Constraint satisfaction problems can be solved by network consistency algorithms that eliminate local inconsistencies before constructing globa1 solutions. We describe a new algorithm that is useful when the variable domains can be structured hierarchically into recursive subsets with common properties and common relationships to subsets of the domain values for related variables. The algorithm, HAC, uses a technique known as hierarchical arc consistency. Its performance is analyzed theoretically and the conditions under which it is an improvement are outlined. The use of HAC in a program for understanding sketch maps, Mapsee3, is briefly discussed and experimental results consistent with the theory are reported.

TR-85-07 State Inconsistency Issues in Local Area Network-Based Distributed Kernels, August 1985 Samuel T. Chanson and K. Ravindran

State inconsistency is an inherent problem in distributed computing systems (DCS) because of the high degree of autonomy of the executing entities and the inherent delays and errors in communicating events among them. Thus any reliable DCS should provide means to recover from such errors. This paper discusses the state inconsistency issues and their solution techniques in local area network based distributed kernels. In particular, we deal with state inconsistencies due to i) failures of processes, machines and/or the network, ii) packet losses, iii) new machines joining or exiting from the network, and iv) processes or hosts migrating from one machine to another in the network. The solutions presented are mostly provided within the kernel itself and are transparent to the applications.

TR-85-08 Computation of Full Logic Programs Using One-Variable Environments, January 1985 Paul J. Voda

(Abstract not available on-line)

TR-85-09 A Generic and Portable Image Processing Environment for Computer Vision, January 1985 William S. Havens

Computer Vision research is flourishing although its growth has been hindered by the lack of good image processing systems. Existing systems are neither general nor portable despite various attempts at establishing standard image representations and software. Issues of hardware architecture and processing efficiency have frequently dominated system design. Often standard representations are primarily data formats for exchanging data among researchers working at affiliated laboratories using similar equipment. We argue that generality, portability and extensibility are the important criteria for developing image processing systems. The system described here, called {\em PIPS}, is based on these principles. An abstract image datatype is defined which is capable of representing a wide variety of imagery. The representation makes few assumptions about the spatial resolution, intensity resolution, or type of information contained in the image. A simple set of primitive operations are defined for direct and sequential access of images. These primitives are based on a bit stream access method that considers files and devices to be a long contiguous stream of bits that can be randomly read and written. Bit streams allow the word boundaries and file system architecture of the host computer system to be completely ignored and require only standard byte-wide direct-access I/O support. The standard image representation has encouraged the development of a library of portable generic image operators. These operators support interactive experimentation and make it easy to combine existing functions into new more complex operations. Finally, graphics device interfaces are defined in order to isolate graphics hardware from image processing algorithms. The system has been implemented under the Unix operating system.

TR-85-10 Specification \& Initialization of a Logic Computer System, July 1985 Anthony J. Kusalik

A logic computer system consists of an inference machine and a compatable logic operating system. This paper describes prospective models for a logic computer system, and its hardware and software components. The language Concurrent Prolog serves as the single implementation specification, and machine language. The computer system is represented as a logic programming goal {\em logic\_computer\_system}. Specification of the system corresponds to resolution of this goal. Clauses used to solve the goal --- and ensuing subgoals --- progressively refine the machine, operating system, and computer system designs. In addition, the accumulation of all clauses describing the logic operating system constitute its implementation. Logic computer systems with vastly different fundamental characteristics can be concisely specified in this manner. Two contrasting examples are given and discussed. An important characteristic of both peripheral devices and the overall computer system, whether they are restartable or perpetual, is examined. As well, a method for operational initialization of the logic computer system is presented. The same clauses which incrementally specify characteristics of the computer system also describe the manner in which this initialization takes place.

TR-85-11 A New Basis Implementation for a Mixed Order Boundary Value ODE Solver, January 1985 Uri Ascher and G. Bader

The numerical approximation of mixed order systems of multipoint value ordinary differential equations by collocation requires appropriate representation of the piecewise polynomial solutions. B-splines were originally implemented in the general purpose code COLSYS, but better alternatives exist. One promising alternative as proposed by Osborne and discussed by Ascher, Pruess and Russell.

In this paper we analyze the performance of the latter solution representation for cases not previously covered, where the mesh is not necessarily dense. This analysis and other considerations have led us to implement a basis replacement in COLSYS and we discuss some implementation details. Numerical results are given which demonstrate the improvement in performance of the code.

TR-85-12 A Functional Programming Language with Context Free Grammars as Data Types, August 1985 Violet R. Syrotiuk

(Abstract not available on-line)

TR-85-13 Coaxial Stereo \& Scale Based Matching'', September 1985 Itzhak Katz

The past decade has seen a growing interest in {\em computer stereo vision}: the recovery of the depth map of a scene from two-dimensional images. The main problem of computer stereo is in establishing correspondence between features or regions in two or more images. This is referred to as the {\em correspondence problem}.

One way to reduce the difficulty of the above problem is to constrain the {\em camera modeling}. Conventional stereo systems use two or more cameras, which are positioned in space at a uniform distance from the scene. These systems use {\em epipolar geometry} for their camera modeling, in order to curb the search space to be one-dimensional --- along {\em epipolar lines}.

Following Jain's approach, this thesis exploits a non-conventional camera modeling: the cameras are positioned in space one behind the other, such that their optical axes are collinear (hence the name {\em coaxial stereo}), and their distance apart is known. This approach complies with a simple case of epipolar geometry which further reduces the magnitude of the correspondence problem.

The displacement of the projection of a stationary point occurs along a {\em radial line}, and depends only on its spatial depth and the distance between the cameras. Thus, to simplify (significantly) the recovery of depth from {\em disparity}, complex logarithmic mapping is applied to the original images. The logarithmic part of the transformation introduces great distortion to the image's resolution. Therefore, to minimize this distortion, it is applied to the features used in the matching process.

The search for matching features is conducted along radial lines. Following Mokhtarian and Mackworth's approach, a {\em scale-space} image is constructed for each radial line by smoothing its intensity profile with a {\em Gaussian filter} and finding {\em zero-crossings} in the second derivative at varying scale levels. Scale-space images of corresponding radial lines are then matched, based on a modified uniform cost algorithm. The matching algorithm is written with generality in mind. As a consequence, it can be easily adopted to other stereoscopic systems.

Some new results on the structure of scale-space images of one dimensional functions are presented.

TR-85-14 Using Discrimination Graphs to Represent Visual Knowledge, September 1985 Jan A. Mulder

This dissertation is concerned with the representation of visual knowledge. Image features often havee many different local interpretalions. As a result, visual interpretations are often ambiguous and hypothetical. In many model-based vision systems the problem of representing ambiguous and hypothelical interpretations is not very specifically addressed. Generally specialization hierarchies are used to suppress a potential explosion in local interpretations. Such a solution has problems, as many local interpretalions cannot be represented by a single hierarchy. As well, ambiguous and hypothetical interpretations tend to be represented along more than one knowledge representation dimension limiting modularity in representation and control. In this dissertation a better solution is proposed.

Classes of objects which have local features with similar appearance in the image are represented by discrimination graphs. Such graphs are directed and acyclic. Their leaves represent classes of elementary objects. All other nodes represent abstract (and sometimes unnatural) classes of objects which intensionally represent the set of elementary object classes that descend from them Rather than interpreting each image feature as an elementary object we use the abstract class that represents the complete set of possible (elementary) objects. Following the principle of least commitment the interpretation of each image feature is repeatedly forced into more restrictive classes as the context for the image feature is expanded until the image no longer provides subclassification information.

This approach is called discrimination vision and it has several attractive features. First, hypothetical and ambiguous interpretations can be represented along one knowledge representation dimension. Second the number of hypotheses represented for a single image feature can be kept small. Third in an interpretation graph competing hypotheses can he represented in the domain of a single variable. This often eliminates the need for restructuring the graph when a hypothesis is invalidated. Fourth, the problem of resolving ambiguity can be treated as a constraint satisfaction problem which is a well researched problem in Computational Vision.

Our system has been implemented as Mapsee-3, a program for interpreting sketch maps. A hierarchical arc consistency algorithm has been used to deal with the inherently hierarchical discrimination graphs. Experimental data show that, for the domain implemented, this algorithm is more efficient than standard arc consislency algorithm.

TR-85-15 Constraint Satisfaction, September 1985 Alan K. Mackworth

(Abstract not available on-line)

TR-85-16 Remote Interprocess Communication \& Its Performance in Team Shoshin, November 1985 Don Acton

Team Shoshin is an extension of Shoshin, a testbed for distributed software developed at the University of Waterloo. Part of the functionality of Shoshin can be attributed to its transparent treatment of remote interprocess communication. This is accomplished by having a special system process, the communications manager, handle the exchange of messages between machines. Shoshin's new hardware environment is significantly different from what it was originally designed on. This thesis describes the problems the new hardware presented and how those problems were overcome. Performance measurements of the time required for both local and remote message exchanges are made and compared. Using this empirical data, a simple model of the remote message exchange protocol is developed to try and determine how to improve performance. The software and hardware enhancements made to Shoshin have resulted in an improvement in system interprocess communication performance by a factor of four. Finally as a demonstration of Shoshin's interprocess communications facilities a simple UNIX based file server is implemented.

TR-85-17 Typed Recursion Theorems --- out of print, November 1985 K and Akira a

In recursion theory, recursion theorems are usually considered for effective functions over an effective universal set, like the set $N$ of all natural numbers or the set $RE$ of all recursively enumerable sets.

We observe that certain effective subsets of these effective universes have rich structure, and we study recursion theorems for these effective subsets.