Computer Vision and Shape Recognition

The following sections are included:

• FOREWORD

• CONTENTS

An automated system for measuring the alignment accuracy of an exposed photosensitive film resist circuit pattern on a metalized ceramic substrate is described, The system is robust and capable of handling low contrast images with high noise levels and varying degrees of degradation of the circuit pattern. The technique that we will present involves estimating, with the aid of a calibrated vision system, the actual coordinates of two predefined salient features of the circuit pattern, component pads, and calculating the horizontal, vertical, and rotational deviation of the expose mask. The vision algorithm that was implemented will be detailed and its development as an optimization problem, to satisfy the speed, accuracy, and hardware constraints of the system will be discussed. Measurements are accurate to the nearest 2.5 microns and the processing time of each ceramic substrate is not more than sixty seconds using an IBM AT microcomputer…

The problem of concern in this article is the recognition of 3D objects and the determination of their locations (including orientation and position) in three dimensional (3D) space. In solving the problem, the technique reported here is different from others in that only one intensity image is used, as opposed to the use of range map or multiple images. Further, no physical constraints are placed upon the object’s orientation and position; that is, the object can assume any position and orientation in 3D space…

Current robot vision systems consist of pseudo realtime feedback, where a scene is analysed while the robot is in a resting state, or otherwise occupied. For many applications a tight feedback loop with the robot servos being driven by sensor data is desirable. To this end, a lightweight, robot wrist mountable laser range finder has been developed at NRC. This sensor provides single scan lines of range data at a rate of approximately 13 calibrated profiles per second. Calibration of the range data is a nontrivial task. Linear interpolation is used on large samples collected from the range finder. Processing these calibrated scans to provide scene infonnation is a unique problem and considerably different from intensity image processing, and should also be recognized as distinct from processing entire 3-D range images. Although there is only a single raster scan of data, explicit cues to the content of the 3-D scene are available. This paper describes a method of calibrating range data, and a library of utilities written to extract information from the range profiles. Potential applications and future directions are discussed…

Piecewise functional approximation of picture is shown to be a useful tool for the segmentation of range (3D) image. A hierarchical step-wise optimization algorithm is employed to transform the global optimization problem into one of sequential optimization. The step-wise criterion then corresponds to the increase of the approximation error produced by the merge of two segments. The segmentation results of range image of polyhedra are shown with the utilization of a planar approximation model. Constraints on segment contour length and segment shape is then added to improve the results…

Temporally persistent spatial patterns in the electroencephalogram (EEG) are extracted using the Karhunen-Loeve transformation (KLT). Three basic patterns are shown to be sufficient to account for more than 94% of the variance in a 1.0 s segment of the EEG from both a normal individual and a patient with a malignant brain tumor. These patterns interpolated to form topographic maps, reveal what appear to be important spatial characteristics of the EEG. The results suggest that the method may be extremely valuable not only for the reduction of the data collected during electroencephalography but also for delineating spatially independent brain electrical sources underlying the EEG…

Mammography is an effective method for detecting breast cancer at the earliest possible stage. Mass screening of mammograms requires the development of automated systems to diagnose breast cancer reliably and efficiently. This paper reports an approach to the detection of one marker, circumscribed masses, using a combination of detection criteria used by experts. The cirteria include the shape, brightness contrast and uniform density of tumor areas…

One of the more elusive goals in the field of remote sensing is to develop a completely automated feature extraction and identification system. The output of such a system, which is often referred to as a fully automated computer cartography system, is usually an annotated thematic map. To date only computer assisted cartographic systems have been developed. Human photointerpreters are still required for feature identification and verification. A mix of digital image analysis techniques and expert systems technology has shown some successes in the automated feature detection and identification problem. However, one of the biggest stumbling blocks at the moment, is how to represent the knowledge contained in a scene in a compact reliable structure that is compatible with expert systems. This paper outlines this knowledge representation problem, presents an analysis of various image segmentation techniques, discusses the segment attnbutes required for inferencing and discusses some of the problems associated with this technique…

Efficient implementation of pattern recognition and image processing functions in VLSI requires algorithmic parallelization of the underlying computation under the constraint of I/O bandwidth limitation. In this paper, we illustrate the parallelization process and the synchronization of the inherent control and data flow of systolic architecture using two feature extraction algorithms. The first algorithm extracts shape features such as edges, start and end points. The extracted shape features can be used to recognize handwritten characters. The second algorithm detects straight line segments using Hough Transform…

Recently a new class of non-linear hybrid filters which combine FIR substructures with median operations were proposed and analyzed. They are shown to have excellent detail preserving properties and are computationally more efficient than conventional median and KAVE filters. In this paper, we propose a class of parallel algorithms for their computation using pipeline architectures. We described the algorithms for different hardware configuration, i.e. for the case where one comparator is available and for machines with two comparators. Analysis of the algorithms for both cases are also given. It is shown that using a commercial pipeline processor which can perform each processing pass at video refresh rate (30 frames per sec), except for the three-level bidirectional hybrid filter, all the filters can be computed using the proposed algorithms in less than one second. The minimum number of refresh memories needed without having to perform image transfer to and from disk are also derived. Its implications for the choice of algorithms are discussed. Discussions on implementation issues involving programming a pipeline processor are also included…

A feature analysis method was developed for the recognition of hand-generated gestures (or markings). Gesture recognition differs from handwriting recognition because gestures are often generated in different proportions, rotations, and sometimes in mirror images. The features are based on direction changes and they are applied successfully to gestural variations. This recognition system is a part of a keyboardless direct manipulation interface to a spreadsheet application…

Contours of digitized characters are traced and segmented by detection of sufficiently curved arcs. The resulting reference points are closely related to the structural features (such as endpoints, cavities…) of characters or patterns. Piecewise approximation is done with parametric cubics and quartics and results are compared. Very good quality approximations are obtained at relatively low cost…

A classification of discrete contours via signatures is studied. Two algorithms to compute the signature have been developed. In the first algorithm a multidimensional sorting is used. The second algorithm is based on a simple geometrical considerations. Two types of signature are considered — the length signature and the area signature. Statistical features based on Fourier descriptors are derived from the signatures. In classification the k-NN algorithm is used with k and the size of the feature vector chosen experimentally. The algorithms have been tested on the handwritten, totally unconstrained characters from Suen’s data base and recognition success rates of 91% and 93% were achieved for the length and area signature respectively…

This paper reports on subjective experiments to define skeletons of digitized characters. These models are then used in three perception experiments to compare the outputs of 11 thinning algorithms previously published in the literature. The overall process is proposed as a systematic evaluation protocol for different algorithms…

Specularly reflecting surfaces confuse traditional shape-from-shading algorithms because the variation in image intensity within a specularity does not directly relate to the cosine of the incident angle, as it would for a simple Lambertian reflector. To overcome this problem, color is introduced and a method of removing the specular component of the intensity variation is proposed based on a dichromatic model of surface reflection. Unlike Shafer’s method for specularity removal, which is restricted to unifonnly colored surface patches, our algorithm uses information from several differently colored regions. The specular component due to interface reflection does not change across the regions even though the diffuse component due to body reflection does. In color space, the regions project to planes and the color of the specular component is found as the common intersection of these planes. Once the color of the specular component is known, it is removed from the original image. The resulting image preserves the relative intensity of the diffuse component so it can then be successfully input to a traditional shape-from-shading algorithm…

The concept of Visual Routine is introduced. A. description is given of an implemented computer system which can correctly compute in images of simple 2-D geometric shapes eleven common properties and relations. A visual routine programming language is outlined. Issues relevant to the control of visual-routine-based search are discussed. The results of testing the system are reported…

Various schemes have been developed to identify the direction of motion in a scene, often to assist in compressing the information required to broadcast a sequence of images. These schemes typically make sequential comparisons of blocks of pixels in order to arrive at a most likely direction of motion. This paper investigates how an artificial neural network may be used to perform the same task. The approach is interesting because these networks perform computations in parallel, thus allowing a form of top-down as well as bottom-up processing. Also, because computations are conceptually performed in parallel, it would be possible to consider performing the task in real time with an appropriate hardware implementation. Preliminary results show that a properly trained network has interesting properties similar to those of real neurons and can, indeed, report direction of movement based on binary pixel values…

A graphics package for generating the range data of 3-D objects is described, The simulating data generated by this package can be used for 3-D object recognition or related research. It is a useful tool for someone who wants to work on range data of 3-D objects, but does not have a good range finder…

Space Station is a major international space project involving the United States, Canada, Europe and Japan. As well as being a major vision system in its own right as an observatory for Earth and the universe, Space Station will need to employ sophisticated computer vision systems for its operation. For example, in order to enhance crew safety and maximize efficiency, a strong emphasis is being placed on the use of automation and robotics in station operations, with computer vision being a key technology needed to implement this strategy. Computer vision will be used in human/machine interfaces, closed-loop control of manipulators, tracking and capturing of payloads, guidance of robotic systems, detection of imminent collisions, and recognition of objects.

In Canada, a number of vision systems are currently being evaluated, including: real-time photogrammetry, laser depth profiling, stereo camera processing, and both 2-D and 3-D image classification. In addition, Canada is committed to an ongoing technology development program, including enhanced computer vision systems, in order to meet the evolving needs of the station over its 30 year life. It is anticipated that this development program will generate substantial spin-off and industrial benefits back on Earth.

Experimental results for matching 3-D industrial-like range data objects with plane and curved surfaces, are here presented. The system is based on a statistical approach. The obtained invariant parameters used for matching purposes are functions of the geometrical dimensions of the object and a number of second order central moments of the object’s surface and of the contour of its base silhouette. We started by calculating 22 invariant parameters and ended by choosing the best 10 parameters. These are chosen according to a simple criterion. Four classification techniques for the matching purposes are tested, of which a hybrid one is the one we recommend. Comments and conclusion are given…

Seismic data can be used to ima the acoustic impedance variations in the earth. In order to convert such data an image that more. closely matches the vision of geology, image enhancement techniques including pattern recognition methods must be applied. A syntax-dependent approach employing a string-to-string matching algorithm matches peaks between traces on a seismic record. A filtering process then enforces matching coherence by correcting matches that deviate seriously from the general trend around anomalous pairs. Connected pairs form lateral coherent events which have a confidence measure. These events are targets of any seismic investigation. Clustering technique can be used to associate the events with geologic zones. The algorithm performs well in a test run and detects most of the strong reflections…

The basis of the topographic primal sketch consist of segmenting range images into surface patches according to categories defined by differential geometry operators such as the Gaussian and mean curvatures. From the sign of these invariant functions of directional derivatives, one can generate categories such as peak, pit, ridge, ravine, saddle, flat and hillside. From this initial classification, we can group these categories to obtain a rich, hierarchical, and structurally complete representation of the fundamental range image structure. In the paper, we present a novel technique where an initial estimate of the categories full of inconsistent labelling due to noise is transformed into a consistent one by label relaxation technique. We also discuss the problem of numerical stability of the Gaussian and mean curvatures and study the effects of different operators on these estimates…

We discuss ways by which different methodologies for image analysis may be combined for better results. We focus on the combination of region growing and edge detection to achieve better segmentation…

The paper describes the growth of image processing technology in the last 25 years. The current market place is described and future developments based on rapidly growing computer technology are predicted…

The following sections are included:

• LIST OF CONTRIBUTORS