ARCHIVED CONTENT - THIS SITE IS NO LONGER UPDATED
This is the updated mirror of http://www.gorodnichy.ca/archives/phd/WorldModeling/.
Ph.D. Thesis
In speciality Computer Vision and Artificial Intelligence.
Department of Computing Science, University of Alberta, Edmonton, Canada. April 2000.
Download the dissertation: from Collections Canada, ResearchGate, videorecognition.com
This thesis considers the task of building world models from uncertain range data. We study the occupancy approach, which is one of the most popular approaches used for this task. We identify three problems of this approach which prevent it from being used for building 3D world models. The thesis aims to resolve these problems.
The first problem concerns the design of sensor models which assign the values of uncertainty to registered range data. Vision-based sensors are the most affordable sensors capable of registering 3D range data. However, their sensor models are not known or are very difficult to calculate using probability theory. In the thesis we propose a new approach for building visual sensor models which uses evidence theory. This approach allows one to efficiently build sensor models of unreliable, inexpensive video systems by employing stereo error analysis. We present the design of an inexpensive visual range sensor which consists of a single off-the-shelf video camera. This visual sensor is shown to be very suitable for world exploration problems.
The second problem deals with the combination rule, which combines uncertainty values obtained from different range data. Approximations of the Bayesian and Dempster-Shafer rules, which are the common rules used in the occupancy approach, in many cases assume the independence of range data, contrary to the usual situation. In the thesis, we develop a new technique for combining range data which is based on linear regression. This technique does not make assumptions about the data and can therefore be applied to combining dependent range data like those provided by a single camera range sensor.
Finally, the third problem concerns the redundancy of stored and processed data, which results from using the grid representation of the occupancy function. In the thesis we establish a new framework for representing the occupancy function in a parametric way using piecewise linear surfaces. This framework, which is the major thrust of the thesis, uses the developed techniques for registering and combining visual range data, and is tested on both simulated and real range data. The advantages and the limitations of the proposed framework are studied. Besides being more optimal space-wise, this framework is also shown to be more efficient for map extraction and world exploration.
While much remains to be done in the area we believe that the proposed strategies for building sensor models, combining uncertain range data, and using parametrically represented occupancy functions provide the basis for new applications of the occupancy approach and will promote the development of this approach in both world modeling and robot navigation.
Dans la présente thèse, nous considerons la tâche de construire des modèles de l'espace à partir de données télémetriques incertaines. Nous étudions l'approche d'occupation, qui est l'approche la plus populaire pour cette tâche. Nous identifions trois problèmes propres à cette approche qui l'empêchent de pouvoir être utilisée pour construire des modéles de l'espace tridimensionels. Le but de cette thèse est de résoudre ces problèmes.
Le premier problème est relié à la conception de modèles de capteur qui determinent les valeurs d'incertitude au données télémetriques registrées. Les capteurs qui sont basés sur les signaux optiques sont les capteurs les plus accessibles capables du registre des données télémetriques tridimensionelles. Cependant, leurs modèles de capteur ne sont pas connus ou sont très difficiles à calculer en utilisant la théorie des probabilités. Dans cette thèse, nous proposons une nouvelle approche pour construire des modèles de capteur optique basée sur la théorie de l'évidence. Cette approche permet de construire efficacement des modèles de capteur de systèmes optiques peux coûteux et peux fidèles en utilisant l'analyse de l'erreur du système stereo. Nous présentons la conception d'un capteur télémetrique fait à partir d'une videocamera générique. On fait la démonstration de l'adéquation de ce capteur optique pour des problèmes d'exploration de l'espace.
Le deuxième problème a rapport avec la règle qui combine des incertitudes obtenues à partir de différentes données télémetriques. Des approximations aux règles bayésienne et de Dempster-Shafer, qui sont les règles générales utilisées dans l'approche d'occupation, assument souvent l'indépendence des données télémetriques, contrairement à la situation habituelle. Dans cette thèse, nous développons une nouvelle technique pour combiner des données télémetriques basée sur la règression. Cette technique n'assume pas l'indépendance des données et peut donc être appliquée pour combiner des données télémetriques telles que celles obtenues par le capteur fait à partir d'une vidéocamera.
Finalement, le troisième problème est relié à la redondance des données enregistrées et traitées, qui résulte de l'utilisation de la représentation de grille de la fonction d'occupation. Dans cette thèse nous établissons un nouveau cadre pour représenter la fonction d'occupation d'une voie paramètrique en utilisant les surfaces linéaires. Ce cadre, qui est la principale contribution du présent travail, utilise les techniques développées pour régistrer et combiner des données télémetriques optiques, et est testé sur des données télémetriques simulées et réelles. En plus d'utiliser beaucoup moins de mémoire, on démontre aussi que ce cadre est plus efficace pour l'extraction de la carte de navigation.
Si bien il reste beaucoup à faire dans ce domain, nous pensons que les stratégies présentées pour construire des modéles de capteur, tout en combinant des donnes télémetriques incertaines, et en utilisant des fonctions d'occupation à représentation paramétrique, fournissent la base pour de nouvelles applications de l'approche d'occupation et stimuleront le développement de cette approche dans la modelisation de l'espace et la navigation robotique.
Contents:
Here is the Presentation made for thesis defence: PhD.ppt (1.4Mb), and here is the presenter - PhD.jpg
This Ph.D. thesis required conducting research in four areas:
Computer Vision (Problem 1) - to design an affordable range sensor capable of registering 3D data, which includes defining a sensor model and developing a paradigm for combining registered range data.
Uncertainty in AI (Problem 2) - to suggest and investigate a new approach to fuse uncertain range data, based on linear regression, as a solution to the problem of combining dependent and sparce range data.
World Modeling (Problem 3) - to suggest and investigate a parametric alternative to a grid-based approach in world modeling and map building, as a solution to the problems of redundancy of processed data and inefficientcy of grids for navigation
Machine Learning (Problem 4) - to explore reinforcement learning in navigation planning, where reinforcement learning is accomplished with an Adaptive Logic Network technique, which is known to be fas
Abstract: Artificial Intelligence (AI) is known to be rich with problems, where finding the solution by conventional search methods is computationally intensive. The time required is often exponential to the number of variables. Principally different way of searching for the decision is to build a dynamic self-organizing system, where the stable states correspond to the desirable solutions. In the paper the possibility of using such nondeterministic methods for resolving Artificial Intelligence problems is studied. It is shown why Hopfield Neural Networks (HN) are so suitable for the role of such a dynamical system. The following approaches of applying Hopfield Neural Networks for solving AI problems are discussed: the Energy approach, the Probability approach, the Graph approach. The last approach is based on using a Hopfield clique Network, introduced by Jagota in 1990. This network is known by the property that its stable states are exactly the maximal clique of the underlying graph. The purpose of the paper is to give a clear idea of how HN can be applied for different AI problms All described approaches are illustrated with concrete examples.. The main theorems .needed for understanding the mechanisms .are stated and the ideas of their proofs are presented..The areas .where these approaches are applicable and where not .are shown..
Bibliography: NNforFRbib.tex
"Adaptive Logic Networks for Facial Feature Detection"(D.O.Gorodnichy, W.W.Armstrong, X. Li), Lecture Notes in Computer Science, Vol 1311 (Proc. of 9th Intern. Conf. on Image Analysis and Processing (ICIAP'97), Florence, Italy, Sept. 1997, Vol. II), pp. 332-339, Springer.
Abstract: The task of automatic facial feature detection in frontal-view, ID-type pictures is considered. Attention is focused on the problem of eye detection. A neural network approach is tested using adaptive logic networks, which are suitable for this problem on account of their high evaluation speed on serial hardware compared to that of more common multilayer perceptrons. We present theoretical reasoning and experimental results. The experiments are carried out with images of different clarity, scale, lighting, orientation and backgrounds.
Keywords: neural network, adaptive logic network, face recognition, eye detection.
Compressed postscript file (130Kb): aln_eyes.ps.gz
Who's Who: reference links, techniques and names (updated continuously)
(Using the knowledge of the stereo for calculating confidence values)
(Source of uncertainty in vision - lense distortion & limited resolution)
(Data are dependent due to sensor models and using the same sensor)
Grids (Maps) and other Occupancy-based World Models (Representations)
Grids (Maps) and other Occupancy-based World Models (Representations)