CS Theses & Dissertations 1997

For 1997 graduation dates (in alphabetical order by last name):

A Fast Heuristic for Finding the Minimum Weight Triangulation
Beirouti, Ronald
URI : http://hdl.handle.net/2429/6380
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Snoeyink

Indexing Without Invariants in Model-based Object Recognition
Beis, Jeffrey S.
URI : http://hdl.handle.net/2429/6716
Degree : Doctor of Philosophy – PhD
Graduation Date : 1997-11
Supervisor : Dr. Lowe

This thesis presents a method to efficiently recognize 3D objects from single, 2D images by the use of a novel, probabilistic indexing technique. Indexing is a two-stage process that includes an offline training stage and a runtime lookup stage. During training, feature vectors representing object appearance are acquired from several points of view about each object and stored in the index. At runtime, for each image feature vector detected, a small set of the closest model vectors is recovered from the index and used to form match hypotheses. This set of nearest neighbours provides interpolation between the nearby training views of the objects, and is used to compute probability estimates that proposed matches are correct. The overall recognition process becomes extremely efficient when hypotheses are verified in order of their probabilities. Contributions of this thesis include the use of an indexing data structure (the /cd-tree) and search algorithm (Best-Bin First search) which, unlike the standard hash table methods, remain efficient to higher index space dimensionalities. This behavior is critical to provide discrimination between models in large databases. In addition, the repertoire of 3D objects that can be recognized has been significantly expanded from that in most previous indexing work, by explicitly avoiding the requirement for special-case invariant features. Finally, an incremental learning procedure has been introduced which extracts model grouping information from real images as the system performs recognition, and adds it into the index to improve indexing accuracy. A new clustering algorithm (Weighted Vector Quantization) is used to limit the memory requirements of this continual learning process. The indexing algorithm has been embedded within a fully functional automatic recognition system that typically requires only a few seconds to recognize objects in standard sized images. Experiments with real and synthetic images are presented, using indexing features derived from groupings of line segments. Indexing accuracy is shown to be high, as indicated by the rankings assigned to correct hypotheses. Experiments with the Best-Bin First search algorithm show that, if it is acceptable to miss a small fraction of the exact closest neighbours, the regime in which Кd-tree search remains efficient can be extended, roughly from 5-dimensional to 20-dimensional spaces, and that this efficiency holds for very large numbers of stored points. Finally, experiments with the Weighted Vector Quantization algorithm show that it is possible to incorporate real image data into the index via incremental learning so that indexing performance is improved without increasing the memory requirements of the system.

Roll - A Robotic On-Board Localization System Using Landmarks
Brewster, Jeff Charles
URI : http://hdl.handle.net/2429/5723
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Little

Simulating Craniofacial Growth
Coughlan, Kevin Michael
URI : http://hdl.handle.net/2429/5919
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Forsey

Integrating H-splines into Softimage/3D
Duprat, Jean-Luc
URI : http://hdl.handle.net/2429/6435
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Forsey

Modeling of Rocks and Ornamental Garden Stones
Ellefson, Christopher J.
URI : http://hdl.handle.net/2429/5932
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Fournier

Interval Graphs: An Examination of Random Graph Models and Algorithms for Determination of Graph Properties
Harrison, Bradley
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112185
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Pippenger

Adapting the Human-Comuter Interface to Support Collaborative Learning Environments for Children
Inkpen, Kori
URI : http://hdl.handle.net/2429/6692
Degree : Doctor of Philosophy – PhD
Graduation Date : 1997-11
Supervisor : Dr. Booth

The presence of computers in schools has grown tremendously over the last ten years. In the wake of this enormous growth, sound research on how to effectively design learning environments and successfully integrate computers into the classroom is needed. The research described in this dissertation evaluates computer-based collaborative learning environments for children using three important criteria: (a) the social environment in which the technology is placed, (b) the technology that provides for explicit collaboration, and (c) the low-level interface design. An additional focus of the research, which crosses all three themes, is gender. The research comprised three experimental studies that were conducted in the three research themes. All these studies employed a creative problem-solving game as the research vehicle. The social theme of the research focuses on the interactions between children mediated by computers. We examined whether the ways children were assigned to work on computers affected their achievement and their motivation. Our results show that how children are asked to use computers does in fact affect their achievement. Grouping children around a single computer can have a positive effect on both achievement and motivation compared to having children play on their own computers. The technology theme of the research focuses on extending computer technology from single-user computers to technology more suited to supporting collaboration in a multi-user environment. We modified the computer environment (both the hardware and the software) to allow the addition of a second mouse to see how this change would affect the children's achievement, learning, and behaviour while playing a puzzle-solving game collaboratively. The results show that the addition of a second mouse to the computer can positively affect children's achievement and learning in the game as well as the temporal patterns of who controls the mouse. The interface design theme of the research focuses on the usability of the graphical user interfaces found in children's software. Even if we understood how to structure the computer environment in the classroom, and we knew how to modify the computer to support children's collaboration, our learning environments might still be ineffective if we are not careful with the design of the low-level details of the user interface. We examined children's use of two common mouse-interaction techniques, drag-and-drop and point-and-click, to see whether the choice of mouse interaction style affects children's ability to move objects around on the screen. The results show that children are able to perform a point-and-click movement faster and with fewer errors than with a drag-and-drop movement and that more children prefer the point-and-click interaction style over the drag-and-drop interaction style. When these two mouse-interaction styles are used in a commercial puzzle-solving environment our studies reveal that the choice of interaction style can affect both achievement and motivation. While many children adapt to the user interfaces with which they are presented, our results show how even a widely accepted interaction style such as drag-and-drop can be difficult for some children and can affect motivation and achievement in a learning environment. Gender differences were observed in all stages of the research, which strengthens the conventional wisdom that girls and boys often interact differently with technology. We emphasize the need to be sensitive to these differences and we provide specific recommendations in this regard.

Using Recorded Motion for Facial Animation
Kobayashi, Tony
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112149
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Forsey

Exploring Partially Observable Markov Decision Processes by Exploiting Structure and Heuristic Information
Leung, Siu-Ki
URI : http://hdl.handle.net/2429/5772
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Boutilier

Efficient and Effective Subimage Similarity Matching for Large Image Databases
Leung, Kai Sang Carson
URI : http://hdl.handle.net/2429/6537
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Ng

Finding Topographically-Similar Regions in a Triangulated Terrain Model
Litchfield, Gwen
URI : http://hdl.handle.net/2429/5945
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Snoeyink

Surface Reflectance and Shape from Images Using a Collinear Light Source
Lu, Jiping
URI : http://hdl.handle.net/2429/6670
Degree : Doctor of Philosophy – PhD
Graduation Date : 1997-05
Supervisor : Dr. Little

The purpose of computer vision is to extract useful information from images. Image features such as occluding contours, edges, flow, brightness, and shading provide geometric and photometric constraints on the surface shape and reflectance of physical objects in the scene. In this thesis, two novel techniques are proposed for surface reflectance extraction and surface recovery. They integrate geometric and photometric constraints in images of a rotating object illuminated under a collinear light source (where the illuminant direction of the light source lies on or near the viewing direction of the camera). The rotation of the object can be precisely controlled. The object surface is assumed to be C2 and its surface reflectance function is uniform. The first technique, called the photogeometric technique, uses geometric and photometric constraints on surface points with surface normal perpendicular to the image plane to calculate 3D locations of surface points, then extracts the surface reflectance function by tracking these surface points in the images. Using the extracted surface reflectance function and two images of the surface, the technique recovers the depth and surface orientation of the surface simultaneously. The second technique, named the wire-frame technique, further exploits geometric and photometric constraints on the surface points with surface orientation coplanar with the viewing direction and the rotation axis to extract a set of 3D curves. The set of 3D curves comprises a wire frame on the surface. The depth and surface orientation between curves on the wire frame can be interpolation by using geometric or photometric methods. The surface reflectance function can be extracted from the points on the wire frame and used for photometric interpolation. The wire-frame technique is superior because it does not need the surface reflectance function to extract the wire frame. It also works on piecewise uniform surfaces and requires only that the light source be coplanar with the viewing direction and the rotation axis. In addition, by interpolating the depth and surface orientation from a dense wire frame, the surface recovered is more accurate. The two techniques have been tested on real images of surfaces with different reflectance properties and geometric structures. The experimental results and comprehensive analysis show that the proposed techniques are efficient and robust. As an attempt to extend our research to computer graphics, work on extracting the shading function from real images for graphics rendering shows some promising results.

Trace-Automata:  A formal Framework for using abstaction to verify hybrid systems
Martin, Andrew
URI : http://hdl.handle.net/2429/6614
Degree : Doctor of Philosophy – PhD
Graduation Date : 1997-05
Supervisor : Dr. Seger

This dissertation presents a new framework, trace-automata, for verifying hybrid systems. In addition, a simple, general theory of abstraction is presented, based on the idea of approximations that are liberal or conservative with respect to an abstraction function. This theory gives rise to a sound technique whereby hybrid systems are verified by constructing discrete approximations of both the implementation and the specification, and verifying that the approximate implementation satisfies the approximate specification. Trace-automata are language accepting, infinite tape automata, extended to allow multiple tapes, and to allow tapes that consist of continuous traces over the reals, as well as tapes that consist of sequences of discrete symbols. Hybrid systems are represented by automata that read some continuous tapes and some discrete tapes. Trace-automata are used to represent both the implementation and the specification of the system to be verified. Verification corresponds to demonstrating that the language accepted by the implementation is contained in that accepted by the specification. Hybrid systems are verified by constructing and verifying discrete approximations. Abstraction functions map continuous traces to discrete sequences. A liberal approximation of the system implementation is verified against a conservative approximation of the system specification. From this verification, it can be concluded that the original hybrid model satisfies the original specification. The dissertation describes a general technique for constructing discrete, liberal approximations of trace-automata representing differential equations and inclusions. In addition, trace-automata themselves can encode abstraction functions, with the result that trace-automata language containment can also be used to establish that an approximation is liberal or conservative as the case may be. These techniques are illustrated with an example verification based upon the Philips Audio Control Protocol with two agents, each capable of both transmitting and receiving. The verification is novel in that it is based upon a detailed model of the analog electrical behaviour of the bus.

Rigidity checking for matching 3D point correspondences under perspective projection
McReynolds, Daniel Peter Roland
URI : http://hdl.handle.net/2429/7366
Degree : Doctor of Philosophy – PhD
Graduation Date : 1997-11
Supervisor : Dr. Lowe

A solution is proposed for the problem of determining the correspondence between sets of point features extracted from a pair of images taken of a static scene from disparate viewpoints. The relative position and orientation between the viewpoints as well as the structure of the scene is assumed to be unknown. Point features from a pair of views are deemed to be in correspondence if they are projectively determined by the same scene points. The determination of correspondences is a critical sub-task for recovering the structure of the world from a set of images taken by a moving camera, a task usually referred to as structure-from-motion, or for determining the relative motion between the scene and the observer. A key property of a static world, assumed by the proposed method, is rigidity. Rigidity of the world and knowledge of the intrinsic camera parameters determines a powerful constraint on point correspondences. The main contribution of this thesis is the rigidity checking method. Rigidity checking is a tractable and robust algorithm for verifying the potential rigidity of a set of hypothesized three-dimensional correspondences from a pair of images under perspective projection. The rigidity checking method, which is based on a set of structure-from-motion constraints, is uniquely designed to answer the question, "Could these corresponding points from two views be the projection of a rigid configuration?" The rigidity constraint proposed in this thesis embodies the recovery of the extrinsic (relative orientation) camera parameters which determine the epipolar geometry - the only available geometric constraint for matching images. The implemented solution combines radiometric and geometric constraints to determine the correct set of correspondences. The radiometric constraint consists of a set of grey-level differential invariants due to Schmid and Mohr. Several enhancements are made to the grey-level differential invariant matching scheme which improves the robustness and speed of the method. The specification of differential invariants for grey-scale images is extended to color images, and experimental results for matching point features with color differential invariants are reported

A Portable Real Time Threads Environment
Mechler, Roland
URI : http://hdl.handle.net/2429/5966
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Neufeld

Verifying a Self-Timed Division Chip
Ono-Tesfaye, Tarik
URI : http://hdl.handle.net/2429/6572
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Greenstreet

Computer-Mediated Communication in a Software Engineering Project Course
Page, Steven
URI : http://hdl.handle.net/2429/6556
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Booth

Fast Progressive Transmission of Images Using Wavelets with Sorted Coefficients
Rempel, Allan G.
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112186
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Fournier

Statistical Modeling of Contact Interaction for Telerobotics and Haptics
Shi, Yunling
URI : http://hdl.handle.net/2429/6423
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Pai

Design and Implementation of a content-based video retrieval systems
Shi, Yaping
URI : http://hdl.handle.net/2429/6591
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Ng

Optimal Display Sequence for Multi-clip Queries
Shum, Paul Sik Leung
URI : http://hdl.handle.net/2429/5708
Degree : Master of Science – MSc
Graduation Date : 1997-05
Supervisor : Dr. Ng

Universal Access to Communication Systems: a comparison of the policies in Canada and the United States
Spears, Matthew Edward
Master’s essay available in print : https://bibrrs.library.ubc.ca/vwebv/holdingsInfo?bibId=112177
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Rosenberg

Efficient Transfer and Storage of Image Data for Distributed Development of Biomedical Imaging Tools
Tam, Roger
URI : http://hdl.handle.net/2429/6449
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisors : Dr. Cahoon, Dr. Neufeld

Forwarding State Reduction for Sparse Mode Multicast Communication
Tian, Jining
URI : http://hdl.handle.net/2429/6595
Degree : Master of Science – MSc
Graduation Date : 1997-11
Supervisor : Dr. Neufeld