Springer Series in Information Sciences – serie

In the first edition of this book, we covered in Chapter 6 and 7 the applications to multidimensional convolutions and DFT's of the transforms which we have introduced, back in 1977, and called polynomial transforms. Since the publication of the first edition of this book, several important new developments concerning the polynomial transforms have taken place, and we have included, in this edition, a discussion of the relationship between DFT and convolution polynomial transform algorithms. This material is covered in Appendix A, along with a presentation of new convolution polynomial transform algorithms and with the application of polynomial transforms to the computation of multidimensional cosine transforms. We have found that the short convolution and polynomial product algorithms of Chap. 3 have been used extensively. This prompted us to include, in this edition, several new one-dimensional and two-dimensional polynomial product algorithms which are listed in Appendix B. Since our book is being used as part of several graduate-level courses taught at various universities, we have added, to this edition, a set of problems which cover Chaps. 2 to 8. Some of these problems serve also to illustrate some research work on DFT and convolution algorithms. I am indebted to Mrs A. Schlageter who prepared the manuscript of this second edition. Lausanne HENRI J. NUSSBAUMER April 1982 Preface to the First Edition This book presents in a unified way the various fast algorithms that are used for the implementation of digital filters and the evaluation of discrete Fourier transforms.

Due to continual progress in the large-scale integration of semiconductor circuits, parallel computing principles can already be met in low-cost sys­ tems: numerous examples exist in image processing, for which special hard­ ware is implementable with quite modest resources even by nonprofessional designers. Principles of content addressing, if thoroughly understood, can thereby be applied effectively using standard components. On the other hand, mass storage based on associative principles still exists only in the long­ term plans of computer technologists. This situation is somewhat confused by the fact that certain expectations are held for the development of new storage media such as optical memories and "spin glasses" (metal alloys with low-density magnetic impurities). Their technologies, however, may not ripen until after "fifth generation" computers have been built. It seems that software methods for content addressing, especially those based on hash coding principles, are still holding their position firmly, and a few innovations have been developed recently. As they need no special hardware, one might expect that they will spread to a wide circle of users. This monograph is based on an extensive literature survey, most of which was published in the First Edition. I have added Chap. ?, which contains a review of more recent work. This updated book now has references to over 1200 original publications. In the editing of the new material, I received valuable help from Anneli HeimbUrger, M. Sc. , and Mrs. Leila Koivisto.

The second edition has not deviated significantly from the first. The printing of this edition, however, has allowed us to make a number of corrections which escaped our scrutiny at the time of the first printing, and to generally improve and tighten our presentation of the material. Many of these changes were suggested to us by colleagues and readers and their kindness in doing so is greatly appreciated. Delft, The Netherlands and P. A. Ruymgaart Buffalo, New York, December, 1987 T. T. Soong Preface to the First Edition Since their introduction in the mid 1950s, the filtering techniques developed by Kalman, and by Kalman and Bucy have been widely known and widely used in all areas of applied sciences. Starting with applications in aerospace engineering, their impact has been felt not only in all areas of engineering but as all also in the social sciences, biological sciences, medical sciences, as well other physical sciences. Despite all the good that has come out of this devel­ opment, however, there have been misuses because the theory has been used mainly as a tool or a procedure by many applied workers without fully understanding its underlying mathematical workings. This book addresses a mathematical approach to Kalman-Bucy filtering and is an outgrowth of lectures given at our institutions since 1971 in a sequence of courses devoted to Kalman-Bucy filters.

The first edition having been sold out, gives me a welcome opportunity to augment this volume by some recent applications of speech research. A new chapter, by Holger Quast, treats speech dialogue systems and natural lan­ guage processing. Dictation programs for word processors, voice dialing for mobile phones, and dialogue systems for air travel reservations, automated banking, and translation over the telephone are at the forefront of human-machine inter­ faces. Spoken language dialogue systems are also invaluable for the physically handicapped. For researchers new to the field, the new chapter (pp. 67-106) provides an overview of fundamental linguistic concepts from phonetics, morphology, syntax, semantics and pragmatics, gramm ars and knowedge representation. Symbolic methodology, such as Norman Chomsky's traditional hierarchy of formal languages is layed out as are statistical approaches to analyze text. Proven tools of language processing are covered in detail, including finite­ state automata, Zipf's law, trees annd parsers. The second part of the new chapter introduces the building blocks of state-of-the-art dialogue systems.

Scientists in optics are increasingly confronted with problems that are of a random nature and that require a working knowledge of probability and statistics for their solution. This textbook develops these subjects within the context of optics using a problem-solving approach. All methods are explicitly derived and can be traced back to three simple axioms given at the outset. Students with some previous exposure to Fourier optics or linear theory will find the material particularly absorbing and easy to understand. This third edition contains many new applications to optical and physical phenomena. This includes a method of estimating probability laws exactly, by regarding them as laws of physics to be determined using a new variational principle.

This text treats the problem of pattern analysis, that is, the automatic interpretation of sensor signals, in particular images, image sequences, and continuous speech. The emphasis of the book is on an integrated view covering the initial preprocessing and segmentation, the classification of individual objects, the representation of relevant data, the automatic determination of control strategy, and knowledge-based understanding of the input with respect to an internal model of the task domain. The view is based on the idea that pattern analysis proceeds from the sensor data via different levels of abstraction to the desired final representation. In this second edition, every chapter has been revised and partly rewritten. Material has been added to the chapters on segmentation, classification, and knowledge, and the chapters on preprocessing and control have been updated. The book is meant as an introductory text for the researcher and student specializing in this field.

While the present edition is bibliographically the third one of Vol. 8 of the Springer Series in Information Sciences (IS 8), the book actually stems from Vol. 17 of the series Communication and Cybernetics (CC 17), entitled Associative Memory - A System-Theoretical Approach, which appeared in 1977. That book was the first monograph on distributed associative memories, or "content-addressable memories" as they are frequently called, especially in neural-networks research. This author, however, would like to reserve the term "content-addressable memory" for certain more traditional constructs, the memory locations of which are selected by parallel search. Such devices are discussed in Vol. 1 of the Springer Series in Information Sciences, Content-Addressable Memories. This third edition of IS 8 is rather similar to the second one. Two new discussions have been added: one to the end of Chap. 5, and the other (the L VQ 2 algorithm) to the end of Chap. 7. Moreover, the convergence proof in Sect. 5.7.2 has been revised.

This volume treats the analysis of 3D dynamic scenes using a stereovision system. Several approaches are described, for example two different methods of dealing with long and short sequences of images of an unknown environment, including an arbitrary number of rigid mobile objects. Results obtained from stereovision systems are found to be superior to those from monocular image systems, which are often very sensitive to noise and therefore of little use in practice. It is shown that motion estimation can be further improved by the explicit modelling of uncertainty in geometric objects. The techniques developed in this book have been successfully demonstrated with a large number of real images in the context of visual navigation of a mobile robot.

This textbook deals with the analysis and design of imaging systems and image processing systems. It contains in a single volume the background material necessary for understanding both the physics of such systems and the way in which the designs accommodate the visual perception of the observer. Of central importance is the mathematics of converting optical images to electrical signals and vice versa, whereby it is stressed that the quality of such conversions must be judged subjectively. The material is easily accessible to senior undergraduates and first year students. A knowledge of elementary physics, calculus, and linear system theory is assumed, but an extensive mathematical and statistical background is not required. This third edition has been updated and includes chapters on colour and the design of improved television systems, and an appendix describing the current status of high-definition television throughout the world.

Discrete H Optimization is concerned with the study of H optimization for digital signal processing and discrete-time control systems. The first three chapters present the basic theory and standard methods in digital filtering and systems from the frequency-domain approach, followed by a discussion of the general theory of approximation in Hardy spaces. AAK theory is introduced, first for finite-rank operators and then more generally, before being extended to the multi-input/multi-output setting. This mathematically rigorous book is self-contained and suitable for self-study. The advanced mathematical results derived here are applicable to digital control systems and digital filtering.

This text brings together concepts and approaches from the fields of photogrammetry and computer vision. In particular, it examines techniques relating to quantitative image analysis, such as orientation, camera modelling, system calibration, self-calibration and error handling. The chapters have been contributed by experts in the relevant fields, and there are examples from automated inspection systems and other real-world cases. The book provides study material for students, researchers, developers and practitioners.

Since the second edition of this book came out in early 1997, the number of scientific papers published on the Self-Organizing Map (SOM) has increased from about 1500 to some 4000. Also, two special workshops dedicated to the SOM have been organized, not to mention numerous SOM sessions in neural­ network conferences. In view of this growing interest it was felt desirable to make extensive revisions to this book. They are of the following nature. Statistical pattern analysis has now been approached more carefully than earlier. A more detailed discussion of the eigenvectors and eigenvalues of symmetric matrices, which are the type usually encountered in statistics, has been included in Sect. 1.1.3: also, new probabilistic concepts, such as factor analysis, have been discussed in Sect. 1.3.1. A survey of projection methods (Sect. 1.3.2) has been added, in order to relate the SOM to classical paradigms. Vector Quantization is now discussed in one main section, and derivation of the pointdensity of the codebook vectors using the calculus of variations has been added, in order to familiarize the reader with this otherwise com­ plicated statistical analysis. It was also felt that the discussion of the neural-modeling philosophy should include a broader perspective of the main issues. A historical review in Sect. 2.2, and the general philosophy in Sects. 2.3, 2.5 and 2.14 are now expected to especially help newcomers to orient themselves better amongst the profusion of contemporary neural models.

The first edition having been sold out, gives me a welcome opportunity to augment this volume by some recent applications of speech research. A new chapter, by Holger Quast, treats speech dialogue systems and natural lan­ guage processing. Dictation programs for word processors, voice dialing for mobile phones, and dialogue systems for air travel reservations, automated banking, and translation over the telephone are at the forefront of human-machine inter­ faces. Spoken language dialogue systems are also invaluable for the physically handicapped. For researchers new to the field, the new chapter (pp. 67-106) provides an overview of fundamental linguistic concepts from phonetics, morphology, syntax, semantics and pragmatics, gramm ars and knowedge representation. Symbolic methodology, such as Norman Chomsky's traditional hierarchy of formal languages is layed out as are statistical approaches to analyze text. Proven tools of language processing are covered in detail, including finite­ state automata, Zipf's law, trees annd parsers. The second part of the new chapter introduces the building blocks of state-of-the-art dialogue systems.

This book brings together concepts and approaches from the fields of photogrammetry and computer vision. In particular, it examines techniques relating to quantitative image analysis, such as orientation, camera modelling, system calibration, self-calibration and error handling. The chapters have been contributed by experts in the relevant fields, and there are examples from automated inspection systems and other real-world cases. The book provides study material for students, researchers, developers and practitioners.

During the past two decades there has been a considerable growth in interest in problems of pattern recognition and image processing (PRIP). This inter­ est has created an increasing need for methods and techniques for the design of PRIP systems. PRIP involves analysis, classification and interpretation of data. Practical applications of PRIP include character recognition, re­ mote sensing, analysis of medical signals and images, fingerprint and face identification, target recognition and speech understanding. One difficulty in making PRIP systems practically feasible, and hence, more popularly used, is the requirement of computer time and storage. This situation is particularly serious when the patterns to be analyzed are quite complex. Thus it is of the utmost importance to investigate special comput­ er architectures and their implementations for PRIP. Since the advent of VLSI technology, it is possible to put thousands of components on one chip. This reduces the cost of processors and increases the processing speed. VLSI algorithms and their implementations have been recently developed for PRIP. This book is intended to document the recent major progress in VLSI system design for PRIP applications.

This book results from a Workshop on Multiresolution Image Processing and Analysis, held in Leesburg, VA on July 19-21, 1982. It contains updated ver­ sions of most of the papers that were presented at the Workshop, as well as new material added by the authors. Four of the presented papers were not available for inclusion in the book: D. Sabbah, A computing with connections approach to visual recognition; R. M. Haralick, Fitting the gray tone intensity surface as a function of neighborhood size; E. M. Riseman, Hierarchical boundary formation; and W. L. Mahaffey, L. S. Davis, and J. K. Aggarwal, Region correspondence in multi-resolution images taken from dynamic scenes. The number and variety of papers indicates the timeliness of the H0rkshop. Multiresolution methods are rapidly gaining recognition as an important theme in image processing and analysis. I would like to express my thanks to the National Science Foundation for their support of the Workshop under Grant MCS-82-05942; to Barbara Hope for organizing and administering the Workshop; to Janet Salzman and Fran Cohen, for retyping the papers; and above all, to the speakers and other partici­ pants, for making the Workshop possible.

he problem of analyzing sequences of images to extract three-dimensional T motion and structure has been at the heart of the research in computer vi­ sion for many years. It is very important since its success or failure will determine whether or not vision can be used as a sensory process in reactive systems. The considerable research interest in this field has been motivated at least by the following two points: 1. The redundancy of information contained in time-varying images can over­ come several difficulties encountered in interpreting a single image. 2. There are a lot of important applications including automatic vehicle driv­ ing, traffic control, aerial surveillance, medical inspection and global model construction. However, there are many new problems which should be solved: how to effi­ ciently process the abundant information contained in time-varying images, how to model the change between images, how to model the uncertainty inherently associated with the imaging system and how to solve inverse problems which are generally ill-posed. There are of course many possibilities for attacking these problems and many more remain to be explored. We discuss a few of them in this book based on work carried out during the last five years in the Computer Vision and Robotics Group at INRIA (Institut National de Recherche en Informatique et en Automatique).

The field of image restoration is concerned with the estimation of uncorrupted im­ ages from noisy, blurred ones. These blurs might be caused by optical distortions, object motion during imaging, or atmospheric turbulence. In many scientific and en­ gineering applications, such as aerial imaging, remote sensing, electron microscopy, and medical imaging, there is active or potential work in image restoration. The purpose of this book is to provide in-depth treatment of some recent ad­ vances in the field of image restoration. A survey of the field is provided in the introduction. Recent research results are presented, regarding the formulation of the restoration problem as a convex programming problem, the implementation of restoration algorithms using artificial neural networks, the derivation of non­ stationary image models (compound random fields) and their application to image estimation and restoration, the development of algorithms for the simultaneous image and blur parameter identification and restoration, and the development of algorithms for restoring scanned photographic images. Special attention is directed to issues of numerical implementation. A large number of pictures demonstrate the performance of the restoration approaches. This book provides a clear understanding of the past achievements, a detailed description of the very important recent developments and the limitations of existing approaches, in the rapidly growing field of image restoration. It will be useful both as a reference book for working scientists and engineers and as a supplementary textbook in courses on image processing.

Forty years ago, in 1957, the Principle of Maximum Entropy was first intro­ duced by Jaynes into the field of statistical mechanics. Since that seminal publication, this principle has been adopted in many areas of science and technology beyond its initial application. It is now found in spectral analysis, image restoration and a number of branches ofmathematics and physics, and has become better known as the Maximum Entropy Method (MEM). Today MEM is a powerful means to deal with ill-posed problems, and much research work is devoted to it. My own research in the area ofMEM started in 1980, when I was a grad­ uate student in the Department of Electrical Engineering at the University of Sydney, Australia. This research work was the basis of my Ph.D. the­ sis, The Maximum Entropy Method and Its Application in Radio Astronomy, completed in 1985. As well as continuing my research in MEM after graduation, I taught a course of the same name at the Graduate School, Chinese Academy of Sciences, Beijingfrom 1987to 1990. Delivering the course was theimpetus for developing a structured approach to the understanding of MEM and writing hundreds of pages of lecture notes.

T. Viéville: A Few Steps Towards 3D Active Vision appears as Vol. 33 in the Springer Series in Information Sciences. A specific problem in the field of active vision is analyzed, namely how suitable is it to explicitly use 3D visual cues in a reactive visual task? The author has collected a set of studies on this subject and has used these experimental and theoretical developments to propose a synthetic view on the problem, completed by some specific experiments. With this book scientists and graduate students will have a complete set of methods, algorithms, and experiments to introduce 3D visual cues in active visual perception mechanisms, e.g. autocalibration of visual sensors on robotic heads and mobile robots. Analogies with biological visual systems provide an easy introduction to this subject.

A knowledge of linear systems provides a firm foundation for the study of optimal control theory and many areas of system theory and signal processing. State-space techniques developed since the early sixties have been proved to be very effective. The main objective of this book is to present a brief and somewhat complete investigation on the theory of linear systems, with emphasis on these techniques, in both continuous-time and discrete-time settings, and to demonstrate an application to the study of elementary (linear and nonlinear) optimal control theory. An essential feature of the state-space approach is that both time-varying and time-invariant systems are treated systematically. When time-varying systems are considered, another important subject that depends very much on the state-space formulation is perhaps real-time filtering, prediction, and smoothing via the Kalman filter. This subject is treated in our monograph entitled "Kalman Filtering with Real-Time Applications" published in this Springer Series in Information Sciences (Volume 17). For time-invariant systems, the recent frequency domain approaches using the techniques of Adamjan, Arov, and Krein (also known as AAK), balanced realization, and oo H theory via Nevanlinna-Pick interpolation seem very promising, and this will be studied in our forthcoming monograph entitled "Mathematical Ap­ proach to Signal Processing and System Theory". The present elementary treatise on linear system theory should provide enough engineering and mathe­ of these two subjects.

This book consists of papers presented at an international symposium spon­ sored and organised by The Rank Prize Funds and held at The Royal Society, London, on 27-29 September, 1982. Since the inception of the Funds, the Trustees and their Scientific Advi­ sory Committee on Opto-e1ectronics have considered that the scope of opto­ electronics should extend to cover the question of how the eye transduces and processes optical information. The Funds have aimed to organise symposia on topics which, because of their interdisciplinary nature, were not well cov­ ered by other regular international scientific meetings. It was therefore very appropriate that the 1982 symposium should be on Physical and Biologi­ cal Processing of Images. The purpose of the symposium was to bring together scientists working on the physiology and psychology of visual perception with those developing ma­ chine systems for image processing and understanding. The papers were planned in such a way as to emphasise questions of how image-analysing systems can be organised, as well as the principles underlying them, rather than the detailed biophysics and structure of sensory systems or the specific design of hardware devices. As far as possible, related topics in biological and artificial sys­ tems were considered side by side.

This book deals with novel machine vision architecture ideas that make real-time projection-based algorithms a reality. The design is founded on raster-mode processing, which is exploited in a powerful and flexible pipeline. We concern ourselves with several image analysis algorithms for computing: projections of gray-level images along linear patterns (i. e. , the Radon transform) and other curved contours; convex hull approximations; the Hough transform for line and curve detection; diameters; moments and principal components, etc. Addition­ ally, we deal with an extensive list of key image processing tasks, which involve generating: discrete approximations of the inverse Radon transform operator; computer tomography reconstructions; two-dimensional convolutions; rotations and translations; multi-color digital masks; the discrete Fourier transform in polar coordinates; autocorrelations, etc. Both the image analysis and image processing algorithms are supported by a similar architecture. We will also of some of the above algorithms to the solution of demonstrate the applicability various industrial visual inspection problems. The algorithms and architectural ideas surveyed here unleash the power of the Radon and other non-linear transformations for machine vision applications. We provide fast methods to transform images into projection space representa­ tions and to backtrace projection-space information into the image domain. The novelty of this approach is that the above algorithms are suitable for implementa­ tion in a pipeline architecture. Specifically, random access memory and other dedicated hardware components which are necessary for implementation of clas­ sical techniques are not needed for our algorithms.

My first encounter with the theory of harmony was during my last year at school (1975). This fascinating system of rules crystallized the intuitive knowledge of harmony I had acquired from years of piano playing, and facilitated memorization, transcription, arrangement and composition. For the next five years, I studied music (piano) and science (Physics) at the Univer­ sity of Melbourne. This "strange combination" started me wondering about the origins of those music theory "rules". To what extent were they determined or influenced by physics? mathematics? physiology? conditioning? In 1981, the supervisor of my honours project in musical acoustics, Neville Fletcher, showed me an article entitled "Pitch, consonance, and harmony", by a certain Ernst Terhardt of the Technical University of Munich. By that stage, I had devoured a considerable amount of (largely unsatisfactory) material on the nature and origins of harmony, which enabled me to recognize the significance of Terhardt's article. But it was not until I arrived in Munich the following year (on Terhardt's invitation) that I began to appreciate the conse­ quences of his "psychoacoustical" approach for the theory of harmony. That is what this book is about. The book presents Terhardt's work against the broad context of music perception research, past and present. Music perception is a multidisciplinary mixture of physics, psychology and music. Where different theoretical ap­ proaches appear contradictory, I try to show instead that they complement and enrich one another.

Lnear prediction theory and the related algorithms have matured to the point where they now form an integral part of many real-world adaptive systems. When it is necessary to extract information from a random process, we are frequently faced with the problem of analyzing and solving special systems of linear equations. In the general case these systems are overdetermined and may be characterized by additional properties, such as update and shift-invariance properties. Usually, one employs exact or approximate least-squares methods to solve the resulting class of linear equations. Mainly during the last decade, researchers in various fields have contributed techniques and nomenclature for this type of least-squares problem. This body of methods now constitutes what we call the theory of linear prediction. The immense interest that it has aroused clearly emerges from recent advances in processor technology, which provide the means to implement linear prediction algorithms, and to operate them in real time. The practical effect is the occurrence of a new class of high-performance adaptive systems for control, communications and system identification applications. This monograph presumes a background in discrete-time digital signal processing, including Z-transforms, and a basic knowledge of discrete-time random processes. One of the difficulties I have en­ countered while writing this book is that many engineers and computer scientists lack knowledge of fundamental mathematics and geometry.

Our aim in this book is to present and enlarge upon those aspects of parallel computing that are needed by practitioners of computational science. Today al­ most all classical sciences, such as mathematics, physics, chemistry and biology, employ numerical methods to help gain insight into nature. In addition to the traditional numerical methods, such as matrix inversions and the like, a whole new field of computational techniques has come to assume central importance, namely the numerical simulation methods. These methods are much less fully developed than those which are usually taught in a standard numerical math­ ematics course. However, they form a whole new set of tools for research in the physical sciences and are applicable to a very wide range of problems. At the same time there have been not only enormous strides forward in the speed and capability of computers but also dramatic new developments in computer architecture, and particularly in parallel computers. These improvements offer exciting prospects for computer studies of physical systems, and it is the new techniques and methods connected with such computer simulations that we seek to present in this book, particularly in the light of the possibilities opened up by parallel computers. It is clearly not possible at this early stage to write a definitive book on simulation methods and parallel computing.

Radar Array Processing presents modern techniques andmethods for processingradar signals received by an array ofantenna elements. With the recent rapid growth of thetechnology of hardware for digital signal processing, itisnow possible to apply this to radar signals and thus toenlist the full power of sophisticated computationalalgorithms. Topics covered in detail here include:super-resolution methods of array signal processing asapplied to radar, adaptive beam forming for radar, and radarimaging.This book will be of interest to researchers and studentsinthe radar community and also in related fields such assonar, seismology, acoustics and radio astronomy.

The image taken by a moving camera changes with time. These image motions contain information about the motion of the camera and about the shapes of the objects in the field of view. There are two main types of image motion, finite displacements and image velocities. Finite displacements are described by the point correspondences between two images of the same scene taken from different positions. Image velocities are the velocities of the points in the image as they move over the projection surface. Reconstruction is the task of obtaining from the image-motions information about the camera motion or about the shapes of objects in the field of view. In this book the theory underlying reconstruction is described. Reconstruction from image motion is the subject matter of two different sci­ entific disciplines, photogrammetry and computer vision. In photogrammetry the accuracy of reconstruction is emphasised; in computer vision the emphasis is on methods for obtaining information from images in real time in order to guide a mechanical device such as a robot arm or an automatic vehicle. This book arises from recent work carried out in computer vision. Computer vision is a young field but it is developing rapidly. The earliest papers on reconstruction in the computer vision literature date back only to the mid 1970s. As computer vision develops, the mathematical techniques applied to the analysis of recon­ struction become more appropriate and more powerful.

Motion and Structure from Image Sequences is invaluablereading for researchers, graduate students, and practicingengineers dealing with computer vision. It presents abalanced treatment of the theoretical and practical issues,including very recent results - some of which are publishedhere for the first time.The topics covered in detail are:- image matching and optical flow computation- structure from stereo- structure from motion- motion estimation- integration of multiple views- motion modeling and predictionAspects such as uniqueness of the solution, degeneracyconditions, error analysis, stability, optimality, androbustness are also investigated. These details togetherwith the fact that the algorithms are accessible withoutnecessarily studying the rest of the material, make thisbook particularly attractive to practitioners.