Pyramidal Architectures for Computer Vision ADV ANCES IN COMPUTER VISION AND MACHINE INTELLIGENCE Series Editor: Martin D. Levine McGill University Montreal. Quebec. Canada COMPUTER VISION FOR ELECTRONICS MANUFACTURING L. F. Pau HUMAN ENGINEERING IN STEREOSCOPIC VIEWING DEVICES Daniel B. Diner and Derek H. Fender PYRAMIDAL ARCHITECTURES FOR COMPUTER VISION Virginio Cantoni and Marco Ferretti SIGMA: A Knowledge-Based Aerial Image Understanding System Takashi Matsuyama and Vincent Shang-Shouq Hwang A Continuation Order Plan is available for this series. A continuation order will bring delivery of each new volume immediately upon publication. Volumes are billed only upon actual shipment. For further information please contact the publisher. Pyramidal Architectures for Computer Vision VIRGINIO CANTONI and MARCO FERRETTI University of Pavia Pavia, ltaly SPRINGER SCIENCE+BUSINESS MEDIA, LLC Llbrary of Congrass Cltllog1ng-ln-Publ1catlon Data Canton!, V. Pyra.!dal archlteetures for co~puter vlslon I Vlrglnlo Cantonl and Mareo Ferrett 1. p. c~. -- (Advanees In COMputer vlslon and aaehlne Inte Illgenee) Ineludas blbllographleal references and Index. ISBN 978-1-4613-6023-0 ISBN 978-1-4615-2413-7 (eBook) DOI 10.1007/978-1-4615-2413-7 ,. Co.puter archltecture. 2. COMputer viS Ion. 1. Ferrett " Mareo. II. Tltle. III. Serles. OA76.9.A73C35 1994 006.4'2--dc20 93-29212 CIP © 1994 Springer Science+Business Media New York Originally published by Plenum Press, New York in 1994 Ali rights reserved No part of this book may be reproduced, stored in a relrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfi1ming, recording, or otherwise, without written permission from the Publisher To Laura, Vera, and Livio -v.c. To Elvira and Eleonora -M.F. Preface Computer vision deals with the problem of manipulating information contained in large quantities of sensory data, where raw data emerge from the transducing sensors at rates between 106 to 107 pixels per second. Conventional general purpose computers are unable to achieve the computation rates required to op erate in real time or even in near real time, so massively parallel systems have been used since their conception in this important practical application area. The development of massively parallel computers was initially character ized by efforts to reach a speedup factor equal to the number of processing elements (linear scaling assumption). This behavior pattern can nearly be achieved only when there is a perfect match between the computational struc ture or data structure and the system architecture. The theory of hierarchical modular systems (HMSs) has shown that even a small number of hierarchical levels can sizably increase the effectiveness of very large systems. In fact, in the last decade several hierarchical architectures that support capabilities which can overcome performances gained with the assumption of linear scaling have been proposed. Of these architectures, the most commonly considered in com puter vision is the one based on a very large number of processing elements (PEs) embedded in a pyramidal structure. Pyramidal architectures supply the same image at different resolution lev els, thus ensuring the use of the most appropriate resolution for the operation, task, and image at hand. Furthermore, a hierarchy is introduced by interplane communication which allows the implementation of a general "planning" strat- vii viii Preface egy. Here the approach is to solve problems at a low spatial resolution, and therefore with a small amount of dats!, and then to proceed to successive re finements until the final verification of the results at the highest resolutions available. In this way, speedup factors greater than the number of PEs can be obtained in the quoted low-level vision tasks, because data reduction is an exponential function of the number of levels which have been used. This approach has shown how a few hierarchical levels can substantially increase the processing efficiency of systems comprising many PEs; this behav ior pattern has found a precise verification in various practical problems. Even in nature several large systems, composed of a great number of elements, have been shown to be self-organizing in a hierarchical structure, and the rules that these large sets configure follow the theory of HMSs. This book is split logically into three sections, which consist of Chapters 1 and 2, Chapters 3 to 8, and Chapters 9 and 10, respectively. The first section provides the groundwork for the architectural analysis carried out in the remainder of the book. It discusses the role of the hierarchy in setting up complex systems and then specializes in the use of the hierarchy in computer vision systems. Chapter 1 reviews the theory of hierarchical modular systems, which model the behavior of large self-organizing natural systems, such as monetary systems, settlement distribution over a territory, and natural languages. This theory shows that the introduction of a few hierarchical levels substantially increases the effectiveness of such large systems. The modularity criterion is inherited to some extent in the structure of most hierarchical architectures. Chapter 2 discusses in depth the benefits of hierarchical strategies in the vision domain. Essentially, the motivation for using such an approach is that of obtaining high computational performances by processing only the relevant image data at the right time. The behavior of the known parts of the human vision system is used as a guideline. Its preattentive and attentive phases per form the basic tasks of any hierarchical processing paradigm-that is, delineat ing the region of interest and focusing on it for a detailed scrutiny. In computer vision, such a paradigm is supported by ad hoc data structures that consist of multiresolution grids, which reproduce the image in different amounts of de tails. The term pyramid is used to clarify the hierarchical connections between adjacent grid layers. This chapter analyzes the alternatives for building such representations and the possible processing strategies. The second section more closely covers the architectural issues. It first introduces a framework for comparing the possible solutions according to to pology and to its functional composition. Then it describes and discusses the Preface ix actual machines and/or prototypes that can be described as pyramid architec tures or that have a pyramid processing mode explicitly supported in hardware. The simulation of pyramids on other parallel systems is also covered in detail. Chapter 3 describes all system organizations that construct a hierarchy with a homogeneous set of processing elements. In such cases, the topology of the interconnections is the main feature of the resulting system. The families of hierarchical systems considered include snowflakes, stars, trees, hypernets, and pyramids. A quantitative assessment of these hierarchies is carried out through a set of parameters that measure the capability of the network to sustain data exchanges among the processing elements. Chapter 4 focuses on hierarchical machines that have already been built (or at least fully designed) and organizes them into a taxonomy. This taxonomy is itself a small hierarchy with two levels. The first level splits the systems into homogeneous or heterogeneous ones according to their processing module capability. The second is based on the means of coupling these modules and on interconnection networks (tight-loose, compact-distributed, fixed-re configurable). The processing paradigm varies within the taxonomy: these in clude pipeline, SIMD, multi-SIMD, and MIMD systems. Chapter 5 concentrates on the most popular hierarchical topology, the ba sic pyramid, and on the homogeneous, massively parallel systems that have been proposed or at least built in prototype. When designing a pyramid struc ture, one may follow two approaches: the first with fine granularity, where one processor per image pixel is conceived, and the second with coarse granularity, where one microprocessor is associated with an image block. The former ap proach is the one followed in most cases, perhaps because of the expected benefits in designing a parallel system with VLSI. This chapter offers a com prehensive and in-depth analysis of the actual pyramid computers that attracted so much interest in the mid- and late-1980s. Chapter 6 analyzes alternatives to the true pyramid computer. Specialized hardware solutions have been proposed to achieve multiresolution processing without resorting to these expensive parallel architectures. Pipelined systems specializing in decimation (pyramid building) and expansion are the most effec tive alternative. The processing facilities of such systems offer a powerful multiresolution environment that can be easily integrated into low-cost, applica tion-specific devices. Chapter 7 addresses a more pragmatic issue. Massively parallel systems, once a small niche in the computer processing community, have now come of age, and commercial systems have become more and more widespread. Since none of them adopts a pyramid topology, it is worth studying the cost of em- x Preface bedding pyramids into their native structure. The mesh and the hypercube are the two most common topologies of such commercial systems. This chapter reviews embeddings proposed for the basic pyramids in these topologies. Chapter 8 closes the central section of the book by analyzing heteroge neous hierarchical systems. The rationale for designing a hierarchical system according to this paradigm is that it is difficult to match the computational requirements of the various processing steps (low to high) in a vision problem with just a single homogeneous architecture. Low-level tasks demand special ized hardware capable of matching the high speed of incoming data. Subse quent processes are best matched onto coarse-grained standard microproces sors. Some systems have been designed to merge the pyramid concept with this heterogeneous structure. The third section covers the user's point of view. Programming tools, including languages and development tools, are notoriously the most difficult part of a system project. With the recent advances in VLSI design, the time required to specify, design, build, and assemble a functioning prototype is shorter by order of magnitudes than the corresponding time to obtain a standard compiler. However, effective use of the hierarchical system must be made pos sible to the "naive" end user, whose energy should only be concentrated on the tasks, with almost no regard to the intricacies of the complex system he or she is programming. Chapter 9 covers the language side of this problem. Specific attempts have been made to conjugate standard languages with the pyramid architecture. Both the data structures and the semantics of the control operators need a revised interpretation. Chapter 10 faces the ultimate question of multiresolution processing. The expected advantages of this processing strategy must be measured (both from a theoretical computational point of view and in practical situations) and proved to be relevant. The chapter contains a selection from the huge number of algorithms that exploit pyramid processing in very diverse computer vision con texts. This overview, which does not pretend to be an exhaustive and up-to date tutorial on the subject, focuses on those algorithms which apply the multi processing strategy at its best. Virginio Cantoni Marco Ferretti Pavia, Italy Acknowledgments Many are the people who contributed to the effort of setting up this book. Some kindly provided up-to-date material on their work; others simply helped informally with suggestions. Among them, we would like to thank particularly Dr. Angelo Buizza for his guidance through the biological aspects of human vision, Dr. Mauro Mosconi, and our co-workers in the Computer Vision and CAD Laboratories of Pavia University. xi