Iris recognition has gained popularity due to factors such as its perceived high accuracy, significant usability advantages attributed to its non-contact acquisition method, and the availability of low cost sensors due to improvements in technology. However, non-contact biometrics authentication systems are vulnerable to different types of attacks than contact-type biometrics, such as fingerprints, for which there are a number of simple techniques to guard against attacks. In particular, the fashion industry has developed designer contact lenses with patterns that range from a simple change in eye color to the imposition of stars or other festive decorations. As these lenses are readily available and can be personalized at a very affordable price, their use in thwarting or spoofing iris-based authentication systems becomes plausible. Given the high security nature of many of these systems, there is a urgent need for a some countermeasure to this type of attack. In this paper, we describe a novel method to detect the presence of fake iris patterns, such as designer contact lenses, during the image acquisition stage to further enhance the basic security value of iris biometrics. Exploiting the anatomy and geometry of the human eye, we present a structured light projection method to detect the presence of artificial items obscuring the real iris. The detection principle has been verified using an inexpensive experimental setup consisting of a miniature projector and an offset camera. We also describe a novel algorithm to process the acquired images to find patterned contact lenses, and measure its performance using data collected with our apparatus. We argue that the addition of the proposed system and algorithm to existing iris biometrics based authentication systems will significantly improve their security.

Biometric matching decisions have traditionally been made based solely on a score that represents the similarity of the query biometric to the enrolled biometric(s) of the claimed identity. Fusion schemes have been proposed to benefit from the availability of multiple biometric samples (e.g., multiple samples of the same fingerprint) or multiple different biometrics (e.g., face and fingerprint). These commonly adopted fusion approaches rarely make use of the large number of non-matching biometric samples available in the database in the form of other enrolled identities or training data. In this paper, we study the impact of combining this information with the existing fusion methodologies in a cohort analysis framework. Experimental results are provided to show the usefulness of such a cohort-based fusion of face and fingerprint biometrics.

We present a face reconstruction approach for revocable face matching. The proposed approach generates photometrically valid cancelable face images by following the image formation process. Given a face image, the approach estimates facial albedo followed by a subject-specific key based photometric deformation to generate a cancelable face image. The proposed approach allows for using any available face matcher to perform verification or recognition in the transformed domain, a capability missing from most existing works on cancelable face matching. Experiments are performed to evaluate the performance, privacy and cancelable aspects of the face images reconstructed using the approach. Results obtained are very promising and make a strong case for such backward compatible cancelable face representations that can seamlessly make use of advancements in automatic face recognition research.

Cancelable biometric systems are gaining in popularity for use in person authentication for applications where the privacy and security of biometric templates are important considerations. A variety of approaches have been proposed in the literature. In this work, we have chosen two (a registration based and a registration free) techniques and performed a comparative study focusing on template representation size, useful dataset coverage, system accuracy and transform strength. Results show that both systems have their own advantages that are suited for use in specific applications.

Biometric identification has numerous advantages over conventional ID and password systems; however, the lack of anonymity and revocability of biometric templates is of concern. Several methods have been proposed to address these problems. Many of the approaches require a precise registration before matching in the anonymous domain. We introduce binary string representations of fingerprints that obviates the need for registration and can be directly matched. We describe several techniques for creating anonymous and revocable representations using these binary string representations. The match performance of these representations is evaluated using a large database of fingerprint images. We prove that given an anonymous representation, it is computationally infeasible to invert it to the original fingerprint, thereby preserving privacy. To the best of our knowledge, this is the first linear, anonymous and revocable fingerprint representation that is implicitly registered.

Biometrics-based authentication systems offer obvious usability advantages over traditional password and token-based authentication schemes. However, biometrics raises several privacy concerns. A biometric is permanently associated with a user and cannot be changed. Hence, if a biometric identifier is compromised, it is lost forever and possibly for every application where the biometric is used. Moreover, if the same biometric is used in multiple applications, a user can potentially be tracked from one application to the next by cross-matching biometric databases. In this paper, we demonstrate several methods to generate multiple cancelable identifiers from fingerprint images to overcome these problems. In essence, a user can be given as many biometric identifiers as needed by issuing a new transformation "key." The identifiers can be cancelled and replaced when compromised. We empirically compare the performance of several algorithms such as Cartesian, polar, and surface folding transformations of the minutiae positions. It is demonstrated through multiple experiments that we can achieve revocability and prevent cross-matching of biometric databases. It is also shown that the transforms are noninvertible by demonstrating that it is computationally as hard to recover the original biometric identifier from a transformed version as by randomly guessing. Based on these empirical results and a theoretical analysis we conclude that feature-level cancelable biometric construction is practicable in large biometric deployments.

Traditional fingerprint acquisition is limited to single-image capture and processing. With the advent of faster capture hardware, faster processors, and advances in video compression standards, newer systems can capture and exploit video signals for tasks that are difficult using a single image. We propose the use of fingerprint video sequences to investigate detecting two aspects of the dynamic behavior of fingerprints. Specifically, we are interested in the detection of distortion of fingerprint impressions due to excessive force and the detection of the positioning of fingers during image capture. These issues often lead to difficulties in establishing a precise match between acquired images. The proposed techniques investigate dynamic characteristics of fingerprints across video sequence frames. A significant advantage of our approach for distortion analysis is that it works directly on MPEG-1,-2 encoded fingerprint video bitstreams. The proposed methods have been tested on the NIST-24 live-scan fingerprint video database and the results are promising. We also describe a new concept called the "resultant biometrics", a new type of biometrics which has both a physiological, physical (e.g., force, torque, linear motion, rotation) component and/or a temporal characteristic, added by a subject to an existing biometric. This resultant biometric is both desirable and efficient in terms of easy modification of compromised biometrics and is harder to produce with spoof body parts.

The level of security at a facility is directly related to how well the facility can keep track of "who is where". The "who" part of this question is typically addressed through the use of face images for recognition either by a person or a computer face recognition system. The "where" part of this question can be addressed through 3D position tracking. The "who is where" problem is inherently multi-scale, wide angle views are needed for location estimation and high resolution face images for identification. A number of other people tracking challenges like activity understanding are multiscale in nature. An effective system to answer "who is where?" must acquire face images without constraining the users and must closely associate the face images with the 3D path of the person. Our solution to this problem uses computer controlled pan-tilt-zoom cameras driven by a 3D wide-baseline stereo tracking system. The pan-tilt-zoom cameras automatically acquire zoomed-in views of a person's head, while the person is in motion within the monitored space.

Biometrics-based authentication and identification systems have to handle images acquired in noisy and hostile environments. The signal quality is assessed to decide if there is sufficient signal strength to process further. Poor quality signals require "enhancement" before further processing of the input signal. Often enhancement implies creating a more visibly pleasing image. However, biometrics signals need to improve the image quality for machine processability. This means that the enhancement algorithm should have some weak model about the sample (image) formation process. Enhancement is then some type of "normalization" or "beautification". We present a weak model-based image enhancement algorithm for fingerprint images. The results of the proposed algorithm are presented in terms of the improvements in the overall system performance measured in terms of a receiver operating characteristics curve.

This paper is concerned with the topic of personalized news assembly at the set-top box, based on augmented video. This is video complemented with additional information that is somehow relevant to the semantic video content. We touch upon the technique that is used for video augmentation, which is video subject detection followed by information searches on the subject. The focus of this paper is on subject detection implemented using traditional text analysis tools; video segmentation is based on these results and visual processing. We describe the architecture of such a system and the benefits to the consumer. Further we discuss a preliminary system that shows the viability of the concept.

for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). Copies may be requested from IBM T. J. Watson Research Center, P. O. Box 218,

Distortions in fingerprint images arising from the elasticity of finger skin and the pressure and movement of fingers during image capture lead to great difficulties in establishing a match between multiple images acquired from a single finger. In a single fingerprint image depicting a finger at some given instant of time, it is difficult to get any distortion information. Further, static two-dimensional or three-dimensional (electronic) copies of fingerprints can be fabricated and used to spoof remote biometric security systems since the input required by the systems is not a function of time. This paper addresses these issues, by proposing the novel use of fingerprint video sequences to investigate and exploit dynamic behaviors manifested by fingers over time during image acquisition. In particular, we present a novel approach to detect and estimate distortion occurring in fingerprint video streams. Our approach directly works on MPEG-{1, 2} encoded fingerprint video bitstreams to estimate interfield flow without decompression, and uses flow characteristics to investigate temporal behaviour of the fingerprints. The joint temporal and motion analysis leads to a novel technique to detect and characterize distortion reliably. The proposed method has been tested on the NIST 24 database and the results are very promising.

Biometrics-based authentication is becoming popular because of increasing ease-of-use and reliability. Performance evaluation of such systems is an important issue. We attempt to address two aspects of performance evaluation that have been conventionally neglected. First, the "difficulty" of the data that is used in a study influences the evaluation results. We propose some measures to characterize the data set so that the performance of a given system on different data sets can be compared. Second, conventional studies often have reported the false reject and false accept rates (FRR, FAR) in the form of match score distributions. However, no confidence intervals are computed for these distributions, hence no indication of the significance of the estimates is given. In this paper, we systematically study and compare parametric and nonparametric (bootstrap) methods for measuring confidence intervals. We give special attention to false reject rate estimates.

We propose a feedback path for the feature extraction stage, followed by a feature refinement stage for improving the matching performance. This performance improvement is illustrated in the context of a minutia-based fingerprint verification system. We show that a minutia verification stage based on re-examining the gray-scale profile in a detected minutia's spatial neighborhood in the sensed image can improve the matching performance by /spl sim/4% on our database. Further, we show that a feature refinement stage which assigns a class label to each detected minutia (ridge ending and ridge bifurcation) before matching can also improve the matching performance by /spl sim/3%. A combination of feedback (minutia verification) in the feature extraction phase and feature refinement (minutia classification) improves the overall performance of the fingerprint verification system by /spl sim/8%.

Fingerprint matching is challenging as the matcher has to minimize two competing error rates: the False Accept Rate and the False Reject Rate. We propose a novel, efficient, accurate and distortion-tolerant fingerprint authentication technique based on graph representation. Using the fingerprint minutiae features, a labeled, and weighted graph of minutiae is constructed for both the query fingerprint and the reference fingerprint. In the first phase, we obtain a minimum set of matched node pairs by matching their neighborhood structures. In the second phase, we include more pairs in the match by comparing distances with respect to matched pairs obtained in first phase. An optional third phase, extending the neighborhood around each feature, is entered if we cannot arrive at a decision based on the analysis in first two phases. The proposed algorithm has been tested with excellent results on a large private livescan database obtained with optical scanners.

In an automatic fingerprint identification or authentication system, the matcher subsystem handles the most complex task of compensating for scaling, translation, rotation and structural distortions of the fingerprint minutiae features due to skin elasticity. We analyze the effect of controlled image acquisition on matcher performance. We show that simple steps in image acquisition can enhance the system performance vastly.

With the use of inkless scanners as input devices for acquiring fingerprints of a person, the digital image of the finger is restricted to the area in contact with the sensor The conventional method of fingerprint image acquisition involves obtaining a nail-to-nail image of the finger known as the rolled fingerprint impression. We present a method of constructing a rolled fingerprint from an image sequence of partial fingerprints using a live-scan fingerprint imager.

Efficient content-based retrieval of image and video databases is an important application due to rapid proliferation of digital video data on the Internet and corporate intranets. Text either embedded or superimposed within video frames is very useful for describing the contents of the frames, as it enables both keyword and free-text based search, automatic video logging, and video cataloging. We have developed a scheme for automatically extracting text from digital images and videos for content annotation and retrieval. We present our approach to robust text extraction from video frames, which can handle complex image backgrounds, deal with different font sizes, font styles, and font appearances such as normal and inverse video. Our algorithm results in segmented characters that can be directly processed by an OCR system to produce ASCII text. Results from our experiments with over 5000 frames obtained from twelve MPEG video streams demonstrate the good performance of our system in terms of text identification accuracy and computational efficiency.

Fingerprint verification is one of the most reliable personal identification methods. However, manual fingerprint verification is incapable of meeting today's increasing performance requirements. An automatic fingerprint identification system (AFIS) is needed. This paper describes the design and implementation of an online fingerprint verification system which operates in two stages: minutia extraction and minutia matching. An improved version of the minutia extraction algorithm proposed by Ratha et al. (1995), which is much faster and more reliable, is implemented for extracting features from an input fingerprint image captured with an online inkless scanner. For minutia matching, an alignment-based elastic matching algorithm has been developed. This algorithm is capable of finding the correspondences between minutiae in the input image and the stored template without resorting to exhaustive search and has the ability of adaptively compensating for the nonlinear deformations and inexact pose transformations between fingerprints. The system has been tested on two sets of fingerprint images captured with inkless scanners. The verification accuracy is found to be acceptable. Typically, a complete fingerprint verification procedure takes, on an average, about eight seconds on a SPARC 20 workstation. These experimental results show that our system meets the response time requirements of online verification with high accuracy.

Fingerprint verification is an important biometric technique for personal identification. We describe the design and implementation of a prototype automatic identity-authentication system that uses fingerprints to authenticate the identity of an individual. We have developed an improved minutiae-extraction algorithm that is faster and more accurate than our earlier algorithm (1995). An alignment-based minutiae-matching algorithm has been proposed. This algorithm is capable of finding the correspondences between input minutiae and the stored template without resorting to exhaustive search and has the ability to compensate adaptively for the nonlinear deformations and inexact transformations between an input and a template. To establish an objective assessment of our system, both the Michigan State University and the National Institute of Standards and Technology NIST 9 fingerprint data bases have been used to estimate the performance numbers. The experimental results reveal that our system can achieve a good performance on these data bases. We also have demonstrated that our system satisfies the response-time requirement. A complete authentication procedure, on average, takes about 1.4 seconds on a Sun ULTRA I workstation (it is expected to run as fast or faster on a 200 HMz Pentium).

Texture analysis methods have been used in various image processing tasks, such as image segmentation, recognition, shape analysis, texture synthesis, and image compression. When applying any of these methods, we assume that the input image has some textural characteristics. This paper addresses the problem of deciding whether an image has texture; in other words, whether texture-based methods are suitable for processing the image. We define a texture to have a spatially uniform distribution of local gray-value variations. A fast algorithm for detecting regions that have texture according to this definition is presented. The performance of the method is demonstrated on several synthetic and natural images.

The authors present an automatic product 1D system ("VeggieVision"), intended to ease the produce checkout process. The system consists of an integrated scale and imaging system with a user-friendly interface. When a produce item is placed on the scale, an image is taken. A variety of features, color, texture (shape, density), are then extracted. These features are compared to stored "signatures" which were obtained by prior system training (either on-line or off-line). Depending on the certainty of the classification, the final decision is made either by the system or by a human from a number of choices selected by the system. Over 95% of the time, the correct produce classification is in the top four choices.

Fingerprint images vary in quality. In order to ensure that the performance of an automatic fingerprint identification system (AFIS) will be robust with respect to the quality of input fingerprint images, it is essential to incorporate a fingerprint enhancement module in the AFIS system. We introduce a new fingerprint enhancement algorithm which decomposes the input fingerprint image into a set of filtered images. From the filtered images, the orientation field is estimated and a quality mask which distinguishes the recoverable and unrecoverable corrupted regions in the input image is generated. The input fingerprint image is adaptively enhanced in the recoverable regions. The performance of our algorithm has been evaluated on an online fingerprint verification system using the MSU fingerprint database containing over 600 fingerprint images. Experimental results show that our enhancement algorithm improves the performance of the online fingerprint verification system and makes it more robust with respect to the quality of input fingerprint images.

The generalized Hough transform and geometric hashing are two contemporary paradigms for model-based object recognition. Both schemes simultaneously find instances of objects in a scene and determine the location and orientation of these instances. The methods encode the models for the objects in a similar fashion and object recognition is achieved by image features "voting" for object models. For both schemes, the object recognition time is largely independent of the number of objects that are encoded in the object-model database. This paper puts the two schemes in perspective and examines differences and similarities. The authors also study object representation techniques and discuss how object representations are used for object recognition and position estimation.>

Neighboring points on a smoothly curved surface have similar surface orientations and illumination conditions. Hence, their brightness values can be used to compute the ratio of their reflectance coefficients. Based on this observation, an efficient algorithm is developed that estimates a reflectance ratio for each region in an image with respect to its background. The region reflectance ratio represents a physical property of a region that is invariant to the illumination conditions. The ratio invariant is used to recognize objects from a single brightness image of a scene. Experimental results demonstrate the power of using reflectance and geometric properties of objects simultaneously.>

Describes techniques for stabilizing the implicit function fitting process. The key drawback of implicit function fitting methods described in literature thus far has been the stability with respect to outliners in the data. In this paper methods for stabilizing the implicit function fitting using additional constraints in the form of surface (curve) normals are described. These constraints eliminate the problem of sensitivity of the implicit function fitting method to outliners in the data. The authors demonstrate that in certain cases the fitting process can be reduced to a generalized eigenvalue problem that can be efficiently solved by standard numerical procedures. Preliminary experimental results with 2D curves consisting of point location and curve normal constraints as data are encouraging.>

A framework for 3D object recognition is presented. Its flexibility and extensibility are accomplished through a uniform, parallel, and modular recognition architecture. Concurrent and stacked parameter transforms reconstruct a variety of features from the input scene. At each stage, constraint satisfaction networks collect and fuse the evidence obtained through the parameter transforms, ensuring a globally consistent interpretation of the input scene and allowing for the integration of diverse types of information. The final interpretation of the scene is a small consistent subset of the many initial hypotheses about partial features, primitive features, feature assemblies, and 3D objects computed by the various parameter transforms. A complete, integrated, and implemented system that extracts planar surfaces, patches of quadrics of revolution, and planar intersection curves of these surfaces from a depth map viewing 3D objects is described. Experimental results on the recognition behavior of the system are presented.>

The multiwindow transform, an extension of parameter transform techniques that increase performance and scope by exploiting the long-range correlated information contained in multiple portions of an image, is presented. Multiple-window transforms allow the extraction of high-dimensional features with improvement in accuracy over conventional techniques while keeping linear to low-order-polynomial computational and space requirements with respect to image size and dimensionality of the features. Using correlated information provides a direct link between extracted features and supporting regions in the image. This, coupled with evidence integration techniques, is used to suppress noisy or nonexistent feature hypotheses. Parameter spaces are implemented as constraint satisfaction networks, where feature hypotheses with overlapping support in the image compete. After an iterative relaxation phase, surviving hypotheses have disjoint support, forming a segmentation of the image. Examples show the performance and provide insight about the behavior.>

A survey is presented of some of the surface reconstruction methods that can be found in the literature; the focus is on a small, recent, and important subset of the published reconstruction techniques. The techniques are classified based on the surface representation used, implicit versus explicit functions. A study is made of the important aspects of the surface reconstruction techniques. One aspect is the viewpoint invariance of the methods. This is an important property if object recognition is the ultimate objective. The robustness of the various methods is examined. It is determined whether the parameter estimates are biased, and the sensitivity to obscuration is addressed. The latter two aspects are particularly important for fitting functions in the implicit form. A detailed description is given of a parametric reconstruction method for three-dimensional object surfaces that involves numeric grid generation techniques and variational principle formulations. This technique is invariant to rigid motion in dimensional space.>

A novel approach is presented for pruning the amount of search needed to match image features to object models. The technique relies on active networks which capture various visibility and geometric constraints between features of a model to prune these features from search space during matching. The networks, which can be efficiently implemented in Boolean logic, integrate harmoniously with the previous work in feature recognition and object matching. A method is proposed for clustering model features (vsets) and four types of constraints which assist in building the networks. The authors show, both analytically and empirically, the dramatic reduction in search provided by activation nets.>

A general framework for multiresolution visual recognition is introduced. The input is processed simultaneously at a coarse resolution throughout the image and at finer resolution within a small window. An approach for controlling the movement of the high-resolution window is described which allows for the unification of a variety of data and model-driven behavioral paradigms. Three modes have been implemented, one based on large unexplained areas in the data, one on conflicts in the object-model database, and one on a 2D space-filling algorithm. It is argued that this kind of multiresolution processing not only is useful in limiting the computational time, but also can be a deciding factor in making the entire vision problem a tractable and stable one. To demonstrate the approach, a class of 3D surface textures is introduced as a feature for recognition in the system considered. Surface texture recognition typically requires higher-resolution processing than required for the extraction of the underlying surface. As an example, surface texture is used to discriminate between a ping-pong ball and a golf ball.>

A vision system to recognize 3-D objects is presented. A novel notion of generalized feature makes it possible to develop a homogeneous architecture to support recognition from simple partial features to complex feature assemblies and 3-D objects. Layered concurrent parameter transforms vote for feature hypotheses on the basis of image data and previously reconstructed features. Recognition networks, motivated by connectionist systems, collect votes, fuse evidence from various sources and ensure global consistency. In addition, they provide an integrated solution to the segmentation problem. The highly modular design allows fundamentally different types of features to interact in a coherent way, utilizing redundancies for more robust recognition. Within this paradigm, a system extracts planar patches, patches of quadrics of revolution, and the intersection curves of these surfaces (lines and conic sections in three-space) from a depth map. Reconstructed features index into a model database to form consistent object hypotheses. Experimental results detailing the recognition behavior or real depth maps are included.>

A generalized neighborhood concept is presented which extends the usual techniques for feature extraction using parameter transforms. Generalized neighborhoods allow operators to use the joint information contained in distant portions of the same feature; i.e. to utilize the long-distance correlation present in the image. The generalized neighborhood techniques, by correlating local information over different portions of the image, produce up to two orders of magnitude improvement in accuracy over conventional techniques. The response also becomes more complicated; false features may be detected due to a peculiar form of correlated noise. A general framework, motivated by connectionist networks, is presented which eliminates this behaviour by introducing competitive processes in the parameter spaces. A novel approach to the generation of lateral inhibition links in the networks is proposed which is consistent with generalized neighborhoods. Experiments are provided that show results on range data. Complex surfaces and 3-D surface-intersection curves are reconstructed from the data.>

The problem of multiresolution 2-D and 3-D shape representation is addressed. Shape is defined as a probability measure with compact support. Both object representations, typically sets of curves and/or surface patches, and observations, sets of scattered data, can be represented in this way. Global properties of shapes are defined as expectations (statistical averages) of certain functions. In particular, the moments of the shapes are global properties. To any shape S and every integer d>0 is associated a shape polynomial of degree 2d, whose coefficients are functions of the moments of S. These polynomials are related to the shape S in an affine-invariant way. They yield small values near S and large values far away, and their level sets approximate S. The shape polynomials define two distances between shapes. As asymmetric measures how well one shape fits as a subset of another one; a symmetric version indicates how equal two shapes are. The evaluation of these distance measures is determined by a sequence of computationally very fast matrix operations. The distance measures are used for recognition and positioning of objects in occluded environments.>

New asymptotic methods are introduced that permit computationally simple Bayesian recognition and parameter estimation for many large data sets described by a combination of algebraic, geometric, and probabilistic models. The techniques introduced permit controlled decomposition of a large problem into small problems for separate parallel processing where maximum likelihood estimation or Bayesian estimation or recognition can be realized locally. These results can be combined to arrive at globally optimum estimation or recognition. The approach is applied to the maximum likelihood estimation of 3-D complex-object position. To this end, the surface of an object is modeled as a collection of patches of primitive quadrics, i.e., planar, cylindrical, and spherical patches, possibly augmented by boundary segments. The primitive surface-patch models are specified by geometric parameters, reflecting location, orientation, and dimension information. The object-position estimation is based on sets of range data points, each set associated with an object primitive. Probability density functions are introduced that model the generation of range measurement points. This entails the formulation of a noise mechanism in three-space accounting for inaccuracies in the 3-D measurements and possibly for inaccuracies in the 3-D modeling. We develop the necessary techniques for optimal local parameter estimation and primitive boundary or surface type recognition for each small patch of data, and then optimal combining of these inaccurate locally derived parameter estimates in order to arrive at roughly globally optimum object-position estimation.

The recognition in image data of viewed patches of spheres, cylinders, and planes in the 3-D world is discussed as a first step to complex object recognition or complex object location and orientation estimation. Accordingly, an image is partitioned into small square windows, each of which is a view of a piece of a sphere, or of a cylinder, or of a plane. Windows are processed in parallel for recognition of content. New concepts and techniques include approximations of the image within a window by 2-D quadric polynomials where each approximation is constrained by one of the hypotheses that the 3-D surface shape seen is either planar, cylindrical, or spherical; a recognizer based upon these approximations to determine whether the object patch viewed is a piece of a sphere, or a piece of a cylinder, or a piece of a plane; lowpass filtering of the image by the approximation. The shape recognition is computationally simple, and for large windows is approximately Bayesian minimum-probability-of-error recognition. These classifications are useful for many purposes. One such purpose is to enable a following processor to use an appropriate estimator to estimate shape, and orientation and location parameters for the 3-D surface seen within a window.

In order to realize robust real-time 3-D object recognition and object location and orientation estimation, a 2-D image is partitioned into small square windows which are processed in parallel. It is assumed that a 3-D object can be approximated by chunks of planes, spheres, and cylinders and that one such surface type is seen within a small window. Our solutions are largely for matte surfaces (i.e. diffusely reflecting); we do touch on specular (i.e, mirror) surfaces. Two kinds of results have been obtained in this work. For the purpose of 3-D object type recognition, a simple 2-D polynomial approximation is made to the image data in a window. Based on the relationships between polynomial coefficients and 3-D surface shape-types, a reliable decision can be made as to whether the object surface seen is that of a plane, a cylinder or sphere. In addition to providing the appropriate observables for surface-type recognition, these polynomial fits act as remarkably effective nonlinear lowpass filters.