ADVANCES IN ELECTRONICS AND ELECTRON PHYSICS
VOLUME 86
EDITOR-IN-CHIEF
PETER W. HAWKES Centre National de la Recher...
67 downloads
1301 Views
12MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
ADVANCES IN ELECTRONICS AND ELECTRON PHYSICS
VOLUME 86
EDITOR-IN-CHIEF
PETER W. HAWKES Centre National de la Recherche Scient$que Toulouse. France
ASSOCIATE EDITOR
BENJAMIN KAZAN Xerox Corporation Palo Alto Research Center Palo Alto, California
Advances in
Electronics and Electron Physics EDITEDBY PETER W. HAWKES CEMESILaboratoire d’Optique Electronique du Centre National de la Recherche Scientijique Toulouse, France
VOLUME 86
ACADEMIC PRESS, INC. Harcourt Brace Jovanovich, Publishers
Boston San Diego New York London Sydney Tokyo Toronto
This book is printed on acid-free paper. @ COPYRIGHT 0 1993 BY ACADEMIC PRESS,INC. ALL RIGHTS RESERVED. NO PART OF THIS PUBLICATION MAY BE REPRODUCED OR TRANSMITTED IN ANY FORM OR BY ANY MEANS, ELECTRONIC OR MECHANICAL, INCLUDING PHOTOCOPY, RECORDING, OR ANY INFORMATION STORAGE AND RETRIEVAL SYSTEM, WITHOUT PERMISSION IN WRITING FROM THE PUBLISHER.
ACADEMIC PRESS,
INC. 1250 Sixth Avenue, San Diego. CA 92101-4311
United Kingdom Edition published by
ACADEMIC PRESS LIMITED 24-28 Oval Road, London NWI 7DX
LIBRARY OF CONGRESS ISSN 0065-2539 ISBN 0-12-014728-9
CATALOG C A R D
NUMBER: 49-7504
PRINTED IN THt UNITED STATES OF AMERICA
93
94
95
96 97
BC 9 8 7 6 5 4 3 2
1
CONTENTS CONTRIBUTORS . . . . . . . . . . . . . . . . . . . . . . . PREFACE. . . . . . . . . . . . . . . . . . . . . . . . . .
Recent Advances in GaAs Dynamic Memories JAMESA . COOPER. JR. I . Introduction. Motivation. and Potential Applications . . . IT. pn-Junction Storage Capacitors . . . . . . . . . . . . I11. JFET and MESFET DRAM Cells . . . . . . . . . . . IV . Heterostructure DRAM Cells . . . . . . . . . . . . . V . Bipolar DRAMS. . . . . . . . . . . . . . . . . . . . VI . Future Directions . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . .
vii ix
. . . . .
Expert Systems for Image Processing. Analysis. and Recognition TAKASHI MATSUYAMA I . Introduction . . . . . . . . . . . . . . . . . . . . . I1. Expert Systems for Image Processing and Analysis (ESIPAs) 111. Representing Knowledge about Image Analysis Strategies . . IV . Representing Spatial Relations and Spatial Reasoning for Image Understanding . . . . . . . . . . . . . . . . . . Concluding Remarks . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . .
1 6 32 44 59 64 77
81 87 124 143 163 168
n-beam Dynamical Calculations KAZUTO WATANABE I. I1. I11. IV . V.
Introduction . . . . . . . . . . . . . n-beam Dynamical Calculation Methods Bethe Method . . . . . . . . . . . . . Multislice Method . . . . . . . . . . Coupled Differential Equations . . . . V
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
173 176 178 187 199
vi
CONTENTS
VI. Summary. . . . . Acknowledgments . Appendix A: Crystal References . . . .
. .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Potential. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
218 2 19 219 22 1
Methods for Calculation of Parasitic Aberrations and Machining- Tolerances in Electron Optical Systems M. I. YAVOR 225 I. Introduction . . . . . . . . . . . . . . . . . . . . . 11. Parasitic Aberrations caused by Electron Optical Element 227 Misalignment . . . . . . . . . . . . . . . . . . . . . 111. Effects of Electromagnetic Field Disturbances on Charged Particle Trajectories . . . . . . . . . . . . . . . . . . 235 IV. General Methods for Calculation of Electromagnetic Field Disturbances due to Electrode or Pole Face Distortions. . . 245 V. Field Disturbance in Electrostatic and Magnetic Sector Analyzers . . . . . . . . . . . . . . . . . . . . . . . 26 1 VI. Application of Approximate Conformal Mappings . . , . . 269 VII. Conclusion . . . . . . . . . . . . . . . . . . . . . . 277 References . . . . . . . . . . . . . . . . . . . . . . 279
INDEX. . . . . . . . . . . . . . . . . . . . . . . . . .
28 3
CONTRIBUTORS Numbers in parentheses indicate the pages on which the authors’ contributions begin.
JAMES A. COOPER, JR. (l), School of Electrical Engineering, Purdue University, West Lafayette, IN 47907- 1285 (8 l), Department of Information Technology, Faculty TAKASHI MATSUYAMA of Engineering, Okayama University, 3- 1 - 1 Tsushima-Naka, Okayama, Okayama 700, Japan
KAZUTO WATANABE (173), Tokyo Metropolitan Technical College, 1-10-40 Higashiohi, Shinagawa-Ku, Tokyo 140, Japan M. I. YAVOR(225), Institute of Analytical Instrumentation, Pr Ogorodnikova 26, 198103 St. Petersburg, Russia
vii
This Page Intentionally Left Blank
PREFACE
Computer memory, expert systems in image processing, and image simulation and tolerances, are the themes of this volume. All of them are of considerable importance today. We begin with an account by James A. Cooper on the use of gallium arsenide for dynamic RAM technology. Attractive though GaAs is, there are problems to be overcome and James Cooper examines these critically, notably the limitations to long-term charge storage on p n junctions. He then examines the various one-transistor dynamic RAM cells, notably junction field-effect transistors, metal-semiconductor FETs, modulationdoped FETs, heterojunction, quantum well and bipolar cells. His chapter ends with a critical examination of future possibilities. The chapter has numerous illustrations to help make this material accessible to a wide readership. The second chapter deals with expert systems for image processing, analysis and recognition. This is a rapidly developing field of great commercial as well as intellectual importance. Takashi Matsuyama subtitles his account “Declarative Knowledge Representation for Computer Vision,” which reminds us that in these expert systems we have to distinguish between procedural and declarative knowledge. After an introductory analysis of the problem and a brief recapitulation of the associated vocabulary, the author explores in detail expert systems in the field of image processing and analysis. A section is then devoted to the representation of strategic knowledge and a further section deals with the important topic of spatial relations in image understanding. Here too, the many examples should help the reader through this difficult but important material. The third chapter is concerned with the simulation of images by the n-beam method, which is a topic of major importance for the electron microscopist. Although this is a subject that is found in textbooks on high-resolution microscopy, new ideas and fresh developments continue to appear in the specialized journals. This survey by an expert, Kazuto Watanabe, is therefore very welcome. Simulation is an essential step in the interpretation of electron images when the detail is close to the limit of resolution of the instrument since direct interpretation is impossible or at best risky. The volume ends with a chapter by Michael Yavor on a remarkably unpleasant topic in particle optics, the calculation of parasitic aberrations. These aberrations arise as a result of imperfect machining of polepieces and electrodes, and are almost inevitable owing to the extremely high tolerances ix
X
PREFACE
that have to be maintained not only in machining but also in alignment. They are not easy to calculate because they require either the application of a sophisticated perturbation calculation to a system of relatively high symmetry (typically two planes of symmetry or rotational symmetry) or the development of a fully three-dimensional approach. Although the theory of such aberrations has been known for several decades, the practical implications have not yet been fully explored. This is hence a valuable, and bold, addition to the subject. In conclusion, I thank all the authors for taking so much time to work on their chapters, and I append a list of those anticipated in forthcoming volumes of the series.
FORTHCOMING ARTICLES Neural networks and image processing Image processing with signal-dependent noise Parallel detection Microscopic imaging with mass-selected secondary ions Magnetic reconnection Sampling theory ODE methods Interference effects in mesoscopic structures Integer sinusoidal transforms The artificial visual system concept Minimax algebra and its applications Corrected lenses for charged particles Data structures for image processing in C The development of electron microscopy in Italy Electron crystallography of organic compounds The study of dynamic phenomena in solids using field emission Gabor filters and texture analysis Amorphous semiconductors Median filters
J. B. Abbiss and M. A. Fiddy H. H. Arsenault P. E. Batson M. T. Bernius
A. Bratenahl and P. J. Baum J. L. Brown J. C. Butcher M. Cahay W. K. Cham J. M. Coggins R. A. CuninghameGreen R. L. Dalglish M. R. Dobie and P. H. Lewis G. Donelli D. L. Dorset M. Drechsler J. M. H. Du Buf W. Fuhs N. C. Gallagher and E. Coyle
xi
PREFACE
Bayesian image analysis Non-contact scanning force microscopy with applications to magnetic imaging Theory of morphological operators Noise as an indicator of reliability in electronic devices Applications of speech recognition technology Spin-polarized SEM Fractal signal analysis using mathematical morphology Electronic tools in parapsychology Image formation in STEM Phase-space treatment of photon beams Fuzzy tools for image analysis Z-contrast in materials science Electron scattering and nuclear structure Edge detection The wave-particle dualism Electrostatic lenses Scientific work of Reinhold Rudenberg Metaplectic methods and image processing X-ray microscopy Accelerator mass spectroscopy Applications of mathematical morphology Focus-deflection systems and their applications The suprenum project Knowledge-based vision Electron gun optics Spin-polarized SEM Cathode-ray tube projection TV systems
Parallel imaging processing methodologies Signal description The Aharonov-Casher effect
S. and D. Geman U. Hartmann
H. J. A. M. Heijmans B. K. Jones H. R. Kirby K. Koike P. Maragos R. L. Morris C. Mory and C. Colliex G. Nemes S. K. Pal S . J. Pennycook G . A. Peterson M. Petrou H. Rauch F. H. Read and I. W. Drummond H. G . Rudenberg W. Schempp G. Schmahl J. P. F. Sellschop J. Serra T. Soma 0. Trottenberg J. K. Tsotsos Y. Uchikawa T. R. van Zandt and R. Browning L. Vriens, T. G . Spanjer and R. Raue S. Yalamanchili A. Zayezdny and I. Druckmann A. Zeilinger, E. Rase1 and H. Weinfurter
This Page Intentionally Left Blank
.
ADVANCES IN ELECTRONICS AND ELECTRON PHYSICS VOL . 86
Recent Advances in GaAs Dynamic Memories JAMES A . COOPER. JR . School of Electrical Engineering. Purdue University. West Lafayette. IN
I . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . A . Introduction and Background . . . . . . . . . . . . . . . . . B. Motivations for the Development of DRAM Technology in GaAs . I1. pn-Junction Storage Capacitors . . . . . . . . . . . . . . . . . . . A . General Description . . . . . . . . . . . . . . . . . . . . B. Charge Storage on pn Junctions . . . . . . . . . . . . . . . . C . Theory of pnp Storage Capacitors . . . . . . . . . . . . . . . D . Experimental Results . . . . . . . . . . . . . . . . . . . . . I11. JFET and MESFET DRAM Cells. . . . . . . . . . . . . . . . . A . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . B. Implementations of JFET and MESFET DRAM Cells . . . . . . C . Effect of Transistor Gate Leakage . . . . . . . . . . . . . . . D . A 4-Bit JFET Dynamic Content-Addressable Memory . . . . . . IV . Heterostructure DRAM Cells . . . . . . . . . . . . . . . . . . . . A . Introduction . . . . . . . . . . . . . . . . . . . . . . . . B . Undoped Heterostructure DRAMs . . . . . . . . . . . . . . . C . Quantum-Well Floating-Gate DRAMs . . . . . . . . . . . . . D . Modulation-Doped Heterostructure DRAMs . . . . . . . . . . . V . Bipolar DRAMs . . . . . . . . . . . . . . . . . . . . . . . . A . Introduction . . . . . . . . . . . . . . . . . . . . . . . . B. Concept of the Bipolar DRAM Cell . . . . . . . . . . . . . . . C . Experimental Results . . . . . . . . . . . . . . . . . . . . . VI . Future Directions . . . . . . . . . . . . . . . . . . . . . . . . A . Introduction . . . . . . . . . . . . . . . . . . . . . . . . B. Trench Capacitors and Stacked Capacitors in GaAs . . . . . . . C . Nondestructive Readout Cells . . . . . . . . . . . . . . . . . D . Ultra-Long Storage Times: Quasi-Static and Nonvolatile DRAMs . E . Nonconventional Applications . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . . . . . .
1 1
4 6 6 8 16 23 32 32 32 37 40
44 44 44 49 54 59 59 59 62
64 64 65 69 71
74 17
1. INTRODUCTION. MOTIVATION. AND POTENTIAL APPLICATIONS A . Introduction and Background
The evolution of electronic systems inevitably creates demand for integrated circuits with higher integration densities. higher speeds. and lower power consumption. Often the performance of a system is limited by a relatively 1
Copyright 0 1993 by Academic Press. Inc . All rights of reproduction in any form reserved . ISBN 0-12-014728-9
2
JAMES A. COOPER, JR.
small number of components in certain critical paths, so that improvements in the speed of these components reflect directly in enhanced performance of the system as a whole. The desire for high-speed integrated circuits for such applications has led to the investigation of GaAs as a host semiconductor for high-performance systems. The trend toward programmable digital systems has intensified the need for large quantities of high-speed digital memory. To date, most of the memory development in GaAs has been based on simple adaptations of existing GaAs circuit technology in the form of six-transistor static storage cells (Fiedler, Chun, and Kang, 1988; Makino et al., 1988, 1990; Vogelsang et al., 1988; Terrell, Ho, and Hinds, 1988; Maysue et al., 1989; Nakano et al., 1990), as shown in Fig. l(a). These cells are organized in a two-dimensional array to form a random-access memory (RAM). Circuits of up to 16 kilobit complexity have been demonstrated, with access times in the 3-7 nsec range. While straightforward to design and build, these static RAM (SRAM) cells are inefficient in two respects: they occupy considerable chip area, and they dissipate static power in the storage state. In silicon integrated circuit technology, the majority of large-scale RAM circuits are one-transistor dynamic RAMS (DRAMs) of the type shown in Fig. l(b). The one-transistor DRAM cell is much smaller than the six-transistor SRAM cell and dissipates negligible standby power, thus permitting large arrays to be incorporated on a single chip. The one-transistor cell consists of a storage capacitor and a single access transistor. In operation, the access transistor is turned on by the word line, electrically connecting the storage capacitor to the bit line. The storage capacitor is then charged to the potential of the bit line, representing either a logic 0 or a logic 1. When the access transistor is turned off by the word line, the storage capacitor is isolated from the bit line and remains charged to the former bit-line potential until leakage currents eventually destroy the stored information. This gradual degradation of the stored potential requires that the storage cell be periodically read and refreshed. The refreshing period must be substantially shorter than the storage time of the weakest cell in the array at the highest operating temperature. In silicon DRAM systems, refresh rates in the neighborhood of 1 kHz are commonly used, and therefore the weakest DRAM cell must have a storage time greater than about 20msec at the highest temperature. The storage capacitor in most silicon DRAMs is a metal-oxide-semiconductor (MOS) capacitor, made possible by the high-quality SiO, insulator formed by thermal oxidation of silicon. One of the obstacles to the development of DRAM cells in GaAs has been the lack of a high-quality native oxide. However, it has been found that charge storage in GaAs can be successfully accomplished using the capacitance of properly designed reversebiased p n junctions. As evidence of progress in this area, Fig. 2 shows the
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES Bit Line
VDD
VDD
3
Bit Line
+ Bit Line
Word Line
(b) FIGURE 1. Six-transistor static RAM cell (a), and one-transistor dynamic RAM cell (b). Static RAM cells in GaAs usually use MESFETs or JFETs.
evolution in room temperature storage time of GaAs homojunction capacitors over the past four years. Note that storage times have increased about one order-of-magnitude every two years and are now over 10 hours at room temperature. These results are far superior to those observed in silicon MOS capacitors. Several types of access transistors are possible in GaAs. These include metal-semiconductor field-effect transistors (MESFETs), junction field-effect transistors (JFETs), modulation-doped field-effect transistors (MODFETs), and heterojunction bipolar transistors (HBTs). All have been investigated
4
JAMES A. COOPER, JR.
loo I
,
1986
,
'
'
' ' ' ,
1987
'
1988
' ' ,
'
1989
' ' '
'
'
1990
' ' '
'
, ' ' ,
1991
I
1992
Year FIGURE 2. Room temperature storage time of GaAspn homojunction storage capacitors as a function of year since development began in 1987. The trend line indicates one order-ofmagnitude increase every two years.
and will be discussed and compared in Sections 111-V. At this point, however, it is appropriate to consider possible applications for GaAs DRAMS. B. Motivations for the Development of DRAM Technology in GaAs As mentioned previously, digital systems in GaAs will require digital memory, and in order to preserve the speed advantage of GaAs systems, this memory must be fast. As a specific example, consider a GaAs microprocessor operating at a clock rate of 200MHz (5nsec cycle time). Such a processor would be similar to the 32-bit GaAs RISC microprocessor designed by Texas Instruments as part of the VSHIC program (Whitmire, Garcia, and Evans, 1988). A typical instruction requires several accesses to external memory. The simple instruction shown in Fig. 3(a) consists of four cycles: fetch instruction, decode instruction, fetch data, operate on data. Each cycle requires 5 nsec, for a total of 20 nsec for the entire instruction. However, if the program and data are stored off-chip in a silicon memory, operation is slowed considerably. For example, assume a 20nsec silicon SRAM is used. Then each external memory access requires the insertion of three "wait states," bringing the total instruction time to 50 nsec, as shown in the bottom half of Fig. 3(a). Now suppose instead we place a high-speed GaAs cache memory on the same chip as the microprocessor. Assuming a good ratio of cache "hits," the wait states can be eliminated and the instruction execution time decreases by a factor of 2.5. Figure 3(b) shows system throughput as a function of CPU cycle time for two cases: (i) when each memory access must be directed to a 20 ns off-chip RAM, and (ii) when each access can be handled by a 0.5 ns
RECENT ADVANCES I N GaAs DYNAMIC MEMORIES
5
Simple 4-Cycle Instruction Format
Decode
Fetch Instruction
-
I Instruction 1 I +t
Fetch Data
Operate on Data
I I
I
cycle
Introduction of Wait States to Accomodate Slow Memory (5 ns cycle time, 20 ns memory access time)
Fetch
Decode Fetch Data
Wait Wait Wait
I
I
I
I
I
I
Operate
Wait Wait Wait
I
D~~
I
CPU Clock Rate (MHz) 1oooo
1000
100
1
10
1000
100
10
0.1
Cycle Time (ns)
FIGURE 3. Part (a) shows a basic four-cycle CPU instruction. Assuming a 5 nsec CPU cycle time, each access to a 20 nsec external memory would require the introduction of four wait states, increasing the execution time to 10 CPU cycles. In part (b) we illustrate the impact that a 0.5 nsec on-chip cache memory would have on system performance as a function of cycle time, assuming a unity cache hit ratio.
on-chip cache memory. It is apparent that the benefits of cache memory increase significantly as the CPU cycle time decreases. In order to be useful, a cache memory must be sufficiently large to ensure a good ratio of cache “hits.” A typical size would be 16 kilobytes (131,072
6
JAMES A. COOPER, JR.
bits). If such a memory were constructed with six-transistor static RAM cells, it would probably be too large to be included on a GaAs microprocessor chip. However, such a cache memory could be implemented using one-transistor dynamic RAM cells without excessive area penalty. There are other motivations for the development of dynamic memory technology in GaAs. A dynamic memory is inherently an analog device, and several specialized applications exist for analog storage. Examples include switched capacitor filters and electronic neural networks (see Section VI). In addition, the basic information obtained in the course of DRAM development is applicable to any device or circuit that requires low leakage, such as GaAs dynamic logic or low-dark-current imagers. As an example, GaAs DRAM research has led to a technique for reducing the subthreshold current in GaAs MESFETs by three orders of magnitude (see Section 111). In the sections that follow we will consider the factors limiting long-term charge storage on pn junctions in GaAs. We will then describe several types of one-transistor DRAM cells, including JFET, MESFET, MODFET, heterojunction, quantum well, and bipolar cells. We will conclude with a discussion of future directions, applications, and opportunities. 11. PN-Junction Storage Capacitors
A . General Description
Dynamic charge storage in GaAs can be accomplished quite efficiently using the capacitance of a properly designed reverse-biased p n junction. In this section we will first discuss the operating principles and design considerations for pn junction storage capacitors. We will then present experimental data on the performance of GaAs p n junction capacitors as a function of doping, geometry, and temperature. To begin, let us consider the pnp test structure shown in Fig. 4. Here the central n-layer is floating, and forms two back-to-back pn junctions with the surrounding p-type layers. The storage time of these back-to-back p n junctions is tested as follows: A bias Vpof either polarity is applied across the structure. This forward biases one p n junction and reverse biases the other. In the process, electrons are removed from the floating n-region across the forward-biased junction, leaving the n-layer at a positive potential. In steady state, the potential of the n-layer is essentially equal to V,, since the steady-state current will be negligible unless the reverse-biased junction is driven into breakdown. When the applied bias is returned to 0, the charge on the n-region redistributes between the two junctions in such a way that both are reverse biased. The n-region is now floating at a positive potential
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
P GaAs Substrate
FIGURE 4. Schematic of a pnp charge storage capacitor, with junction voltages defined for further analysis. Note that the voltage polarities are chosen so that positive values indicate reverse bias.
somewhat less than V,, as determined by the capacitance divider formed by the two junctions. The storage capacitor will gradually discharge as thermal generation supplies electrons to the positive n-region. This discharge can be monitored by observing the capacitance of the two back-to-back junctions, as illustrated in Fig. 5. Immediately following the bias pulse, this capacitance is small due to the large depletion regions of the reverse-biased junctions. As thermal generation returns the structure to equilibrium, the capacitance gradually rises to the value determined by the zero-bias depletion widths of the two junctions. For discussion purposes, we define the storage time as the time required for the capacitance to return to within l/e (36.8%) of its equilibrium value. In designingpn junction storage capacitors, two objectives must be kept in mind. First, we wish to maximize the charge storage density at a given voltage; i.e., the capacitance per unit area of the junction. Second, we wish to minimize the generation current that discharges the capacitor. Up to a certain point, both these objectives may be met by increasing the doping on both sides of the junction. There is, however, a limit beyond which increasing the doping will actually increase the generation current per unit area and reduce the storage time. These effects will be discussed later in this section. Before moving to a more detailed discussion of charge storage in the pn junction capacitor, however, we will anticipate the final results of this chapter by
8
JAMES A. COOPER, JR.
FIGURE 5 . Capacitance transient observed on a symmetrically-doped pnp storage capacitor. For t < 0 the bias is 0 and the structure is in equilibrium. A bias pulse V, is applied at I = 0 and removed at I = to. During the bias pulse, one junction is forward biased while the other is reverse biased. Electrons are removed from the n-region by the forward-biased junction, leaving that region positive charged. The capacitance decreases due to the increased depletion width of the reverse-biased junction. At t = to the bias is returned to 0. The n-region remains positively charged and both junctions are now reverse biased. Thermal generation gradually returns the structure to equilibrium. The capacitance recovery is approximately exponential in time, with time constant T ~ .
revealing that, by proper design, it has proven possible to achieve both high-charge storage densities (1.85 fC/pm2for a single junction or 3.7 fC/pm2 for a pnp structure at 1 V reverse bias [Dungan, 1989; Dungan et al., 19901) and long storage times ( 2 10 hours at room temperature [Stellwag, Melloch, and Cooper, 1991b]) using pn-junction storage capacitors. B. Charge Storage on pn Junctions 1. Steady-State Relationships
In order to examine the most important features of charge storage on p n junctions, we will make a number of simplifying assumptions. We assume an abrupt (step) junction having uniform nondegenerate doping on each side, as shown in Fig. 6 . We also assume that all dopant atoms are ionized at the temperatures of interest. Employing the depletion approximation, it is easy to show that the maximum electric field, which occurs at the metallurgical
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
9
Mx -X
0
FIGURE 6 . Cross section of an abrupt pn junction. The voltage polarity is defined so that a positive value represents a reverse bias.
junction, is given by
where E, is the semiconductor permittivity, NA and No are the doping on the p and n sides, respectively, and xp and x, are the depletion widths on thep and n sides. These depletion widths can be expressed in terms of the total potential drop across the junction as
Here VAis the applied voltage, taken to be positive under reverse bias, and V,, is the built-in potential of the junction, given by (4)
where q is the electronic charge, k is Boltzmann’s constant, T is absolute temperature, and niis the intrinsic carrier concentration at temperature T. The capacitance of the junction serves as a useful indicator of the electrostatic state at any given time and is given by
where A is the junction area. Finally, we will calculate the charge storage density of a pn junction. The charge per unit area removed from the junction under reverse bias VAis given
10
JAMES A. COOPER, JR.
where xpoand xn0are the equilibrium values of xpand x,. Making use of either (2) or (3), the charge stored per unit area at reverse voltage V, is
Here we see that the charge storage density increases as the square root of doping and also as the square root of (VB,+ 5 ) .The maximum charge storage density is limited by junction breakdown. In GaAs, to achieve breakdown fields requires charge densities in excess of 5 fC/pm2.However, a more reasonable value for maximum charge storage density is in the range of 1-2 fC/pmz. This is comparable to the planar charge storage densities presently achieved in silicon dynamic RAMS. 2 . Generation Mechanisms In describing the operation of a pnp storage capacitor, we indicated that if the voltage is quickly swept back toward 0, the charge removed from the n-region will not change appreciably. The rate at which charge “leaks back” onto the n-region is a central issue in DRAM cell operation. Working toward an understanding of the charge recovery transient in a pnp structure, we first need to consider the generation mechanisms responsible for leakage in reverse-biased pn junctions. Electron-hole pairs can be created by thermal generation, photogeneration, or impact ionization. Assuming the capacitor is kept in the dark and that internal fields are low enough that impact ionization can be neglected, the primary leakage mechanism is thermal generation (Dungan, 1989). Thermal generation can occur within the depletion region itself or in the neutral bulk within a diffusion length of the depletion region. We will show that generation in the neutral bulk can be neglected compared to generation in the depletion region. Finally, thermal generation may occur along the periphery of the device, where thepn junction is exposed by a mesa etch. This “edge” generation will prove to be important and must be included in calculation of the charge recovery transient. Thermal generation may involve either direct band-to-band transitions or transitions through defect centers in the forbidden band-gap (ShockleyRead-Hall generation). Because of the greater energy required for each transition, band-to-band generation is much less likely than generation by means of defect centers (SRH generation). Therefore, we will neglect bandto-band generation in the discussions which follow.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
11
a. Generation in the Depletion Region. The bulk generation rate per unit volume due to a single-level defect center at energy ETis given by (Shockley and Read, 1952)
n: - np (8) zp(n + n1) + TAP +PI) Here n and p are the electron and hole densities, z, and 7p are electron and hole lifetimes, and n, and p , are constants that depend on the energy E T of the defect center. Since we have assumed nondegenerate material, the carrier densities can be written
G=
n = niexp( F,, T - Ei
)
(9)
where F, and Fp are the quasi-Fermi levels for electrons and holes, and E, is the intrinsic Fermi level, usually taken to lie approximately at midgap. The constants n, and p, are the carrier densities that would be present if the respective Fermi levels lay at the energy ET. Therefore, we can write
PI =.PI(
T)
- ET
The np product in the numerator of (8) can be obtained by multiplying (9) and (10): np = n:exp( F" -7;T-) -Fp It is commonly assumed that the quasi-Fermi levels can be extended across the depletion region of a pn junction with essentially zero slope. Under this assumption, the splitting of the quasi-Fermi levels within the depletion region is equal to the applied voltage, and (13) may be written np
= n:exp(
%)
Combining (8)-(12) and (14), we can write
Equation (15) gives the generation rate per unit volume at any point within
12
JAMES A. COOPER, JR. 1.5
,
,
,
,
,
,
,
,
,
N A = N D = l x l O ” cmm3
-
V*=5V
. c
1.0
-
0.5
-
i
1
0
u b‘
,
0.0
I
,
t i , ;
FIGURE 7. Generation rate per unit volume as a function of position in the depletion region, calculated using (15). Here we have assumed a symmetrical junction with midgap generation centers.
the depletion region. To calculate the total leakage current per unit area arising from generation within the depletion region, we need to integrate (15) with respect to position from one edge of the depletion region to the other: + XP
Jdepl
=4
G ( 4&
(16)
The integration in (16) is complicated by the fact that the terms (F, - E,) and ( E , - F,) in (15) are strong functions of position. The simplest way to evaluate the integral in (16) is to recognize that the integrand is very nearly a rectangular function of position. Figure 7 shows the generation rate given by (15) as a function of position for a typicalpnjunction. Note that G(x) goes exponentially to 0 wherever either (F,, - E T ) or ( E , - 4 ) is positive. When both (F,, - E T ) and (ET - F,) are negative, the exponential terms may be
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
13
neglected and (15 ) reduces to G=“[l %
-exp(s)]
where z, is a generation lifetime given by %=
e(E~-EOIkT p
e(E,--Er)IkT
+
n
(18)
In the typical case, V, 9 kT/q, so that (17) becomes simply G = ni/zc. The leakage current can then be expressed as
where W, is the generation width, defined as the region within which (Fn- E,) and (E, - F,) are negative; i.e., the region where F, < E, < Fp.
b. Generation in the Neutral Regions. Hole-electron pairs that are thermally generated withln one diffusion length of the edge of the depletion region can also contribute a leakage current that will discharge the capacitor. This diffusion current is described by the Shockley diode equation:
where D,and Dpare diffusion coefficients, L, and Lpare diffusion lengths, and npo and pnoare equilibrium minority carrier concentrations for electrons and holes, respectively. This diffusion current arises as a result of the concentration gradient of minority carriers in the neutral regions adjacent to the edge of the depletion region. Under sufficiently large reverse bias (V, > 0), the minority carrier concentrations at the edge of the depletion regions are essentially 0, while deep within the neutral regions they are at their equilibrium values: npo= n f / N Aand pno= $IND. This concentration gradient gives rise to a steady diffusion current in the reverse direction. In GaAs pn junction storage capacitors, however, this diffusion current is negligible compared to generation within the depletion region (Dungan, 1989). This can be seen by the following calculation: At room temperature, n: in GaAs is approximately 4 x 10l2cm-6 while the doping densities N, and ND for typical storage capacitors are in the range lO”-lO’*~m-~.Thus the equilibrium minority concentrations npoand p,,,, are typically on the order of lo-’ ~ r n at - ~room temperature. Assuming reasonable values for diffusion coefficients and diffusion lengths, we estimate a total diffusion current of about 2000 carriers/(cm2s). If the capacitor has an area of 10 x 10 pm’, the Carrie&, or total diffusion current discharging the capacitor is only 2 x one carrier returned to the storage capacitor every eight minutes. Since the
14
JAMES A. COOPER, JR.
minimum charge stored on the capacitor is at least lo6 carriers, this leakage rate is totally negligible. c. Generation at the Junction Perimeter. Leakage current arising from generation at the perimeter of the storage capacitor must also be considered. Experimental measurements on real storage capacitors indicate that a substantial portion of the leakage current is due to such generation. At etched surfaces the termination of the crystal lattice gives rise to a continuum of generation-recombination centers distributed across the bandgap in energy. The total generation rate per unit area at the perimeter can be calculated by summing the contributions from generation centers at various energy levels across the band-gap. Thus, in analogy to (8), we may write (Schroder, 1987)
where n, and p , are the carrier densities at the surface, ,c, and c,, are capture coefficients of surface centers for holes and electrons, and D,T(E) is the density of surface centers at energy E measured per unit area per eV. The terms nls and pisare functions of energy E and are analogous to the n, and p i terms defined for bulk centers in (11) and (12) earlier. As in the case of bulk generation, we regard (21) as representing the surface generation rate at one point within the depletion region and integrate (21) with respect to position within the depletion region. Thus, by analogy to (16), the surface generation contribution to current in the depletion region is given by
j
+X P
J W P
=4
GP(x)dx
(22)
- Xn
In order to calculate this integral, we recognize that n, and p s are functions of x,and that the G, in the integrand will be negligible except in the region WGpwhere both n, and p s are small compared to ni. Since n, and p , are negligible within W,,, the integrand GPis independent of position and can be taken outside the integral in (22). Thus, combining (21) and (22) using these considerations leads to
where s, is identified as the surface generation velocity. Equation (24) for surface generation in the depletion region is the direct counterpart to (19) for bulk generation in the depletion region.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
15
3. Charge Recovery Transient
Combining (19) and (24) and taking into account the area and perimeter of the junction leads to an expression for the total generation current discharging the p n junction storage capacitor
z = ( ~ c e p )l A +
( ~ d e p 1 . P )= ~
qni
[(3) + w,,s)P] 7,
A
(
(25)
Using (6), the total charge stored on the capacitor can be written
Q = qNA(xp - x p ~ ) A (26) where xp is the depletion width on the p side of the junction and x is the 40 value of xp in equilibrium. To maintain charge neutrality, we require that NA ( x p - x p O ) = ND ( x n - xnO) (27) where x, and xd are the actual and equilibrium values of depletion width on the n-side of the junction. Denoting (x, + x , ) by Wand (xpO xd) by Wo,we can write
+
In order to write the differential equation governing charge decay in a p n junction charge storage capacitor, we must obtain expressions for the effective generation widths W, and W, in (25). The generation width W, was introduced in (19) and defined as the width of the region where F, < E, < F,. For the most general situation where NA # No and E , # E,, the expressions for W, as a function of bias are cumbersome (Dungan, 1989). However, if the generation centers lie very close to midgap ( E , x E,) and the junction is symmetrically doped (NA= ND = NB),then the expression for the generation width W, is simplified considerably. Under these assumptions, one can show that W,
-+
(W - W,). . .if NA = ND and E,
= E,
(29) where W is the depletion width at reverse bias and W, is the equilibrium depletion width ( VA= 0). If we further assume that the generation width at the perimeter is the same as the generation width in the bulk, we can write (Dungan, 1989) that
w,=
W,,=(W-
Inserting (30) into (25) yields
W,)=- 2Q qAN,
16
JAMES A . COOPER. JR
Equation (31) has the solution
Q(r)
=
Q(0)eKf’7s
where tS is the storage time constant defined by
Equation (33) is extremely important to understanding the capabilities of pn junction storage capacitors in GaAs. As will be confirmed by experimental measurements in Section II.C, (33) tells us that the storage time should be a strong function of temperature, since the intrinsic carrier concentration ni increases exponentially with temperature according to
where N, and Nvare the effective density of states in the conduction band and valence band, respectively, and EGis the band-gap energy. Although N,, N,, and E G are weak functions of temperature, the dominant temperature dependence arises because of the kT factor in the exponent. Thus, if (34) is inserted into (33), one expects that a plot of In (tS)versus l/Twould be linear with a slope approximately equal to EG/(2k).In other words, the storage time of a pn junction storage capacitor decreases exponentially with temperature. A second point that is apparent from an examination of (33) is that a plot of 1 / t S versus ( P / A ) should be linear, with slope 2nis,/NB and intercept 2n,/NBt,. From such a plot, it should be possible to estimate both the surface generation velocity and the generation lifetime at a given temperature. A final point should be made with regard to (30)-(33). In developing these equations we have assumed a symmetrically doped junction with generation centers at midgap. If either of these assumptions fail, our equations have to be modified. In the general case where ND# NAor E , # E,, WGis larger than ( W - W,) and the ratio of WG/(W - W,) is bias dependent (Dungan, 1989). As a result, the charge recovery transient in (32) is no longer exactly exponential, and the storage time in (33) loses its special significance. A recovery time can still be defined, however, but it becomes bias dependent. We will touch on this matter again in Section II.C.2. C. Theory of pnp Storage Capacitors Having considered the generation mechanisms and charge recovery transient in pn junctions, we now return to the pnp storage capacitor structure shown
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
17
in Fig. 4. The behaviour of this structure was described qualitatively in Section 1I.A. 1. Steady-State Capacitance- Voltage Relationship At this point we wish to calculate the capacitance-voltage relation of the pnp structure shown in Fig. 4.We assume that, in general, the two pn junctions are not doped symmetrically, and we designate the doping of the top layer NAl and the bottom layer NA2.When a bias is applied across the pnp structure, negligible current will flow in steady state, since one of the pn junctions is reverse biased. Consequently, the voltage drop across the forward-biased junction is also negligible, and virtually all the applied voltage develops across the reverse-biased junction. Thus, the total capacitance of the structure is that of two capacitors in series, one at essentially zero bias and the other reverse biased by an amount V,. Assume that V, > 0, so that the top junction is forward biased and the bottom junction is reverse biased. Under these conditions (and assuming the dopings NAIand NA2are within about two orders of magnitude of each other) the capacitance of the top junction CJ,(0) will be larger than the capacitance of the bottom junction cJ2( V,). Equation ( 5 ) can be used to calculate both these capacitances. The total capacitance of the pnp structure measured in steady state is then
The total charge stored is given by (7) evaluated for the reverse-biased junction (junction 2):
The steady-state capacitance-voltage relationship (V, swept away from 0 ) is illustrated for two values of NA2in Fig. 8. Note that if the doping is not symmetrical (i.e., NA2# NAI), the capacitance-voltage relationship will not be symmetrical about VA= 0. Figure 8 shows a decreasing capacitance when the voltage is swept away from 0 in either direction (assuming quasi-steady-state conditions), and a different, almost flat, capacitance if the voltage is swept rapidly back toward 0. The capacitance remains nearly constant when the voltage is swept toward 0 because the charge Qlotal removed from the n-region during the outward sweep cannot be quickly restored when the voltage is reduced. Again, assume that V, > 0, so that the top junction is forward biased and the bottom junction is reverse biased. When the applied bias is swept toward 0, the charge Q,,,,, , which originally resided entirely on the bottom junction, must
18
JAMES A. COOPER, JR. 4.0 10 N -
3.5 10
. E
3.0 10
8 .-0
2.510
c)
p
2.0 10
0 -5
-4
-3 -2
-1
0
1
2
3
4
5
Applied Voltage (V)
FIGURE8. Capacitance-voltage curves of a pnp storage capacitor for two different values of doping in the second pf region.
now redistribute between the two junctions in such a manner that the total voltage drop across both junctions adds up to V, . Thus, the voltages V, and V, must satisfy
where Qto,,, is given by (36) when V, reaches its maximum value on the outward sweep. At the same time, we can write
-v,+v,=V,
(38)
Substituting ( 3 8 ) into (37) yields
Equation (39) can be solved for V, as a function of VA.The capacitance of the pnp structure as VAis swept back toward 0 is then given by
where V, is obtained from the solution of (39). Depending on the relative dopings N,, and N A 2 ,the capacitance may increase or decrease as VAis swept toward 0. An example of C-V relationships for both symmetrical and asymmetrical doping is shown in Fig. 8. The value of V, that satisfies (39) when V, = 0 is of particular importance, since this is the voltage across each of thepn junctions at the end of the "write pulse." It is this voltage that determines the generation widths W, and W,, at the start of the charge recovery transient.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
19
2. Capacitance Recovery Transient (Dungan, 1989) Assume that the pnp structure has been ,pulsed to a specific voltage V, = Vp, resulting in a stored charge QtOmi, where Qtotai is given by (36).If the structure is symmetrically doped ( N A i= NA2),the charge Qtota, divides equally between junctions 1 and 2. If we further assume that each junction individually is symmetrically doped (N,, = NA2= N,, call this value of doping NB)and that the dominant generation centers lie at midgap (E, = Ei),the charge recovery transient of each junction is given by (32), with Q(0) set equal to Qtota,/2.The instantaneous charge on each junction given by (32) can be related to an instantaneous value of depletion width using (28). Thus, combining (32) and (28), we can write for each junction that Q(t)
Qtotai
= -exp 2
(- t/z,)
=qANB 2 ( W ( t )-
6)
(41)
Solving for W(t), W ( t ) = W,+-exp(-t/z,) Qtotai qANB Since the capacitance of the pnp structure is that of two junctions in series, we can write
As can be seen from (43), the capacitance transient that occurs due to generation within the pn junction is not exponential, but rather the reciprocal of a constant plus an exponential. Plots of (43) for NB = 5 x 10’7cmp3and pulse voltages of 1,2, and 5 V are shown in Fig. 9 as symbols. One is tempted to view the curves in Fig. 9, as truely exponential; i.e., as represented by an equation of the form C(t) = C,, - [C,,- C(O)]exp ( - t / z c )
(44)
In fact, the lines in the figure (barely visible beneath the symbols) are least-squares fits of (44)to the “data” represented by the symbols. The agreement would appear to be excellent, but the time constants zc obtained by the fit are approximately 9, 16, and 32% longer than z, for the 1, 2, and 5 V curves, respectively. Under the assumed conditions of symmetrical doping and midgap generation centers, we can derive an expression relating the measured capacitance recovery time constant zc to the actual charge recovery time constant z, by
20
JAMES A. COOPER, JR.
h
2 610.’
8 a C .-8
c)
510-8
P 0 4 10 -
1
0
1
2
3
4
5
t l zs
FIGURE 9. Capacitance recovery transients (symbols) calculated from (43) for a symmetricalpnp storage capacitor with NA = ND = 5 x lO”cm-’ and pulse voltages of 1,2, and 5 V. The solid lines (almost obscured by the symbols) are least-squares fits to (44).Although the fits appear to be quite good, the time constants T~ obtained by the fitting are longer than T~ by 9, 16, and 32%, as shown on the figure.
equating (43)and (44).As shown by Dungan (1989), this ratio can be written
Here e is the base of natural logarithms (e = 2.7182). The time constant ratio in (45)is typically between 1 and 2. In particular, since Qtota, increases as the square root of pulse voltage V, through (36), the capacitance recovery times observed in experiments will be voltage dependent, increasing as pulse voltage is increased. This is consistent with the trends in Fig. 9. As stated, such variations are typically less than a factor of 2 over the normal range of pulse voltages used (1 V < I V,l < 5 V). Note that the charge recovery time constant ss is not voltage dependent (see eq. 33) - rather it is our approximation of zs by zc that is voltage dependent. The preceding discussion required the rather restrictive assumptions that both junctions are symmetrically doped ( N A ,= ND = N A 2 ) and that the dominant generation centers lie at midgap (ET = Ei). These restrictions may be removed through a more careful calculation of the generation volume, the region where FN < ET < F,. The mathematics involved are straightforward but tedious (Dungan, 1989) and will not be reproduced here. However, an example of such a calculation is shown in Fig. 10. Here we plot the normalized capacitance recovery transient for two pulse voltages and three generation center positions. All six curves are calculated assuming that the (A/ effective generation current per unit volume in the depletion region, Jeff cm’), is equal to unity. The “time” axis actually represents the time integral of the charge density generated per unit volume in the depletion region during
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
21
1.o
0.8 0.6 0.4
0.2 0.0 0.00
0.01
0.02
0.04
0.03
JEFFt (C/cm
0.05
3,
FIGURE10. Normalized capacitance recovery transients for a nonsymmetrical pnp capacitor ( N A ,= NA2= 1 x 10’8cm-3,ND = 1 x l O ” ~ m - ~for ) two pulse voltages and three generation center energies. The horizontal axis is “time” multiplied by the effective generation current per unit volume Jeff= qn,(l/s, + s,P/A).
the recovery. Actual times can be computed by dividing the normalized = qn,(l/tG s G P / A ) . “time” axis by Jeff One observes that the capacitance recovery time constants in Fig. 10 (the point where the normalized capacitance is 0.632) are dependent both on initial bias and on the energy of the generation center. Again, higher pulse voltages lead to longer capacitance recovery times. However, as stated earlier, the variations are typically less than a factor of 2. We shall see that these corrections are small compared to the range of storage times that arise due to variations in the design of the storage capacitors and the procedures used to fabricate them. In the sections that follow, we will make no particular distinction between the capacitance recovery time constant tC and the charge recovery time constant tS and will simply refer to the measured capacitance recovery time constant as the “storage time” ts.
+
3 . Charge Removal Transient
In the development in Section II.C.1, we made the tacit assumption that charge is removed instantaneously from the n-region whenever a bias V, is applied across the pnp structure. This is not the case, and in fact the charge removal transient that occurs on the application of bias can be extremely slow in a higher band-gap semiconductor material such as AlGaAs or Sic. To obtain closed-form expressions for the charge removal transient, we will consider the simple circuit consisting of a forward-biased diode charging a capacitor, as shown in Fig. 11. For this development, we assume the capacitor has a fixed value independent of voltage. The capacitor is initially at zero voltage, and a bias 6 is applied across the diode-capacitor combination at t = 0. We wish to obtain an expression for the voltage V , across the
22
JAMES A. COOPER. JR
I +
t=O
VA
T
7i7T FIGURE11. Simple circuit model for visualizing the charge removal transient in a pnp capacitor structure.
capacitor as a function of time. The current flowing through the forwardbiased diode may be written 1 = lo ( e q ' ~ ' ~ ' - 1) = C dQ
dt
(46)
where Qc is the charge on the capacitor and I, is the saturation current density of the diode given by I,
=
ya.i(0" + L~NA
--)
0,
(47)
LpND
It is significant to note that I, varies as the square of n,. Since n, decreases exponentially with band-gap energy, as shown by (34), I, may be extremely small in high-band-gap semiconductors at room temperature. The charge on the capacitor can be written Qc = cvc = C ( ~-A VD)
(48)
and its derivative is
Combining (46) and (49) gives a differential equation that may be solved for Vo(t).After algebra, we find that
where
T,,
given by
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
10.1510-1310-11
l o - O 10-7 .,0-5
23
lo-3
t IT,
FIGURE 12. Diode voltage drop as a function of time for several values of applied voltage
6 during the charge removal transient. The write time can be made arbitrarily short if the write process is terminated before the diode voltage reaches 0. For example, if we are willing to provide a write voltage V, that is 0.25 V greater than the final value of capacitor voltage (allowing VD to be 0.25V % 10kT/q at the end of the write process), then the write time can be reduced to 10-~~,.
is the time for a steady current I, to charge the capacitor C to a potential kT/q. Equation (50) is plotted for several values of V, in Fig. 12. If V, b kT/q and t -g q,, (50) can be simplified to
This relationship explains the linear dependence of the V, = co curve in Fig. 12. It is perhaps more enlightening to plot the capacitor voltage as a function of time, as shown in Fig. 13. The point to note from both figures is that the capacitor charges to within VD(t)of the pulse voltage V, in a specific time t , regardless of the value of VA. Therefore, if we wish to charge the capacitor to a voltage V,, in time t , , this can be accomplished by applying a pulse , V D ( t lis ) obtained from (50) or voltage V, given by V, = V,, + V D ( t l )where Fig. 12. These arguments can be refined by including the specific voltage dependence of the capacitance using (5). This is left as an exercise for the reader.
D . Experimental Results 1. Eflect of Temperature
Consider a large-area storage capacitor in which bulk generation dominates
24
JAMES A. COOPER, JR.
lo-’
10.5
10’
t IT,
FIGURE13 Capacitor voltage as a function of time for several values of applied voltage VA the capacitor dunng the charge removal transient. Note that at a specific time, say t/ro = voltage falls short of the applied voltage VAby the same amount, regardless of the value of VA. This “shortfall” is, of course, the diode voltage drop.
(A/PS
sGtG) so
that the storage time constant given by (33) can be written
Inserting (18) and (34) into (53) and assuming that (i) the dominant generation center is above midgap (this assumption is arbitrary, and equally valid equations would result if the opposite assumption were made), and (ii) z, is of the same order of magnitude as r P ,leads to
where AET = IE, - E l / .Equation (54) suggests that the storage time will be thermally activated with an activation energy EAgreater than or equal to half the band-gap. (Note that we would have reached the same conclusion if we had assumed the generation center to be below midgap, except that t pwould be replaced by 7,). To further appreciate the temperature dependence of (54), note that N , and N y are proportional to T3I2and that T~ is inversely proportional to the thermal velocity vth, which increases as TIi2.Thus, the prefactor is proportional to (1 / T)’. This dependence, however, is overshadowed by the temperature dependence of the exponential factor. In the exponent, the band-gap energy EG is a weak function of temperature and can be approximated by a firstorder Taylor expansion as EG(T) % E G O
-
UT
(55)
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
25
Temperature ("C) 181
144
111
2.4
2.6
84
60
40
21
3.0
3.2
3.4
F8
d
I"
2.2
2.8
1000/T
(1IK)
FIGURE14. Measured capacitance recovery time constants as a function of temperature for pnp capacitors in GaAs and Al,Ga,_,As (x x 0.2). The recovery process is thermally activated, with activation energies very close to half the band-gap.
where EGO is the extrapolated zero-temperature band-gap and ci is a parameter. For GaAs in the neighborhood of room temperature (Thurmond, 1975), EGO z 1.56eV and ci = 4.17 x 10-4eV/K. Inserting (55) into (54) yields
The first exponential term is now explicitly temperature independent. From the second exponential term, we see that the activation energy should be greater than or equal to half the extrapolated zero-temperature band-gap, which for GaAs is about 0.78 eV. Figure 14 shows measured storage times (Dungan, 1989) forpnp capacitors fabricated in GaAs and Al,Ga,-,As (x z 0.2). These capacitors were grown by molecular beam epitaxy (MBE) and were mesa isolated by chemical etching. The doping and thickness of the layers are the same. The storage times in Fig. 14 are indeed thermally activated, as required by (56), and the activation energies are consistent with generation sites at or very close to midgap (AETz 0). In considering the magnitudes of the storage times, we note that dynamic memories in silicon are typically refreshed at a 1 kHz rate, so that the storage times of individual cells must be longer than the refresh period of 1 msec. To take a conservative view, we shall require a storage time of at least 100msec
26
JAMES A. COOPER, JR Temperature (“C) 182 l0000
144
111
2.4
2.6
84
60
40
21
5
2.8
3.0
3.2
3.4
3.6
1000 100 10 1 0.1 0.01 2.2
lOOO/T(1/K)
FIGUREIS. Capacitance recovery time constants for three GaAs pnp capacitors having different doping concentrations. The doping on the lightly doped side is given in the legend. The ~ ~ Note the reduction longest storage times are obtained for dopings in the low l O ’ ’ ~ n -range. in activation energy for the most highly doped sample (0 1990 IEEE).
for GaAs-based memories. By this criterion, Fig. 14 indicates that both these (unoptimized) pnp storage capacitors would be capable of satisfactory operation to over 100°C. 2. Effect of Doping
Equation (33) indicates that the charge storage time constant T~ is expected to scale directly with doping. This is because higher dopings result in smaller depletion regions, and generation within the depletion region determines the storage time. Also, (7) tells us that the charge storage density, i.e., the charge stored per unit area at a given voltage, increases as the square root of doping. Since long storage times and high-charge storage densities are both desirable, it would appear that high doping levels on both sides of the junction are called for. Figure 15 shows measured time constants for three pnp storage capacitors grown by MBE and mesa isolated by chemical etching (Dungan, 1989; Dungan ef al., 1990). All growth and processing conditions were the same except for the doping of the layers. In all three structures the n-layer is doped 1 x l O ” ~ m - ~The . p-layer dopings are 7 x 1015cm-3,1 x 1017cm-3,and 1 x 1019cm-3.All three capacitors are effectively one-sided step junctions, with the generation occurring primarily on the lightly doped side. The doping of the lightly doped side is shown in the figure. (Note that for the sample with NA = 10’9cm-3,the lightly doped side is the n-region, ND = l O ” ~ m - ~ ) . Equation ( 3 3 ) suggests that the charge recovery time constant should scale linearly with the doping of the lightly doped side. Figure 15 shows that
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
27
recovery time indeed increases with doping up to about 1 x 1017cm-3. However, the sample with dopings of 1 x 1018cm-3exhibits a reduced time constant at all temperatures and a reduced activation energy. Thus it appears that there is a practical limit above which further increases in doping actually reduce the storage time. The reduced storage time of the most highly doped sample can be explained by the phenomenon of field-induced barrier lowering. This effect occurs when electric fields within the depletion region become high enough to modify the escape energy of carriers confined on a generation center. This can occur when the potential drop over a distance comparable to the radius of the electron orbit is significant compared to the ground-state energy of the center. Frenkel(l938) showed that the change in escape energy AEA is given by -
AEA = 2q/$
(57)
where F is the electric field in V/cm. Thus, AEA calculated by (57) can be viewed as the reduction in activation energy resulting from field-induced barrier lowering. Applying this correction to the data of Fig. 15, we obtain AE, values of 90, 180, and 330meV, respectively, for the three curves of increasing doping density. These values correspond approximately to the differences between activation energies seen in the figure. It has been found experimentally (Dungan, 1989; Dungan et al., 1990) that higher doping levels can be used successfully if a small undoped (or lightly doped) i layer is inserted between the p and n-type regions in each junction, resulting in a p-i-n-i-p structure such as shown in Fig. 16. The i layer has the effect of reducing the maximum electric field in the depletion region, thereby avoiding the barrier lowering phenomenon, while maintaining a very highcharge storage density (high capacitance per unit area). The storage times of two p-i-n-i-p storage capacitors are compared to a pnp storage capacitor of similar doping in Fig. 17. 3. Eflect of Device Area and Device Scaling In order to construct a high-density memory array using p n junction storage capacitors, it is important that the size of the capacitor be reduced as much as possible. Two issues arise immediately: (i) charge storage capacity and (ii) storage time. Clearly, as the area of the capacitor is reduced, the amount of stored charge is reduced proportionally. What is perhaps not immediately apparent is that the storage time is also reduced. We shall consider both of these limitations in this section. First, we consider the charge storage capacity. To permit reliable detection
28
JAMES A. COOPER. JR.
i (undoped) 30nm
N+ 10’’ cmJ i (undoped) 30nm
FIGURE16. Storage capacitor having p-i-n-i-p structure. The presence of the undoped i layers reduces the maximum electric field in the junction, minimizing field-induced barrier lowering, while still providing a high capacitance per unit area.
of the signal charge during readout and to minimize soft errors due to alpha particle strikes, a dynamic memory must store a certain minimum charge in each cell. In silicon dynamic memories, this minimum is typically on the order of lo6 electrons. To understand how this restriction affects the GaAs storage cell, let us consider the p-i-n-i-p capacitor of Fig. 16. For this capacitor, the Temperature (“C) 182 10000
144
111
84
60
40
21
5
2.4
2.6
2.8
3.0
3.2
3.4
3.6
1000
100
sE H
10 1
0.1 0.01 2.2
10001T(IIK)
FIGURE17. Capacitance recovery times for pnp and p-i-n-i-p storage capacitors. By introducing an i layer, we are able to avoid the reduction in room temperature storage time caused by field-enhanced generation.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
29
Square Edge Length (pm) 198
98
78
62
5.0 6.25
.-cE
0.16
a,
0.12
8.33
8
0.08
12.5
f
0.04
25.0
P
-
3 v
$
C
0 0 100 200 300 400 500 600 700 800
Perimeter / Area (Ilcm)
FIGURE18. Inverse storage time of square pnp capacitors as a function of P / A ratio at several temperatures. At each temperature, the generation lifetime T~ is calculated from the intercept and the surface generation velocity sc from the slope.
charge storage density of each junction is about 1.85fC/pm2 at a reverse voltage of 1 V. Accounting for both junctions, the area required to store lo6 electrons would be 43 pm2 or 6.6pm on a side. This area would be reduced if a higher signal voltage were used. A reasonable lower limit would appear to be around 25 pm2 or 5 pm per side.’ Next we consider the effect of scaling on storage time. One obvious geometrical consequence of reducing the capacitor area is the fact that the perimeter-to-area ratio P / A increases. Taking the inverse of (33),
(-+
1 =2ni 1 TS
NB
sG;)
TG
This implies that a plot of inverse time constant versus P / A should produce a straight line whose slope is determined by the surface generation velocity and whose intercept is determined by the bulk generation lifetime. This is illustrated by the data (Sheppard, 1991) in Fig. 18 for four different temperatures. The inverse storage time increases linearly with P / A , in good agreement with (58). From the slopes and intercepts, we can calculate values of T~ and sG at each temperature using (58). These data are shown in Fig. 19. Here we see that both T~ and sG are relatively weak functions of temperature I As an aside, we note that one wishes to retain lo6 electrons at the end of one refreshing period. We have defined storage time as the time for the electron density to be reduced to l/e of its initial value. Thus, we should store 2.7 x lo6 charges at the beginning of the transient, requiring 2.7 times the quoted area. However, in practice one never allows the charge to decay to lie of its initial value before refreshing. In fact, if we require the storage time to be at least IOOmsec, but refresh at a 1 kHz rate, the initial charge will only decay to 0.99 of its initial value at the end of one refreshing period.
30
JAMES A. COOPER, JR Temperature (“C)
-
111
104
97
91
84
-‘E In
78
In
Y
r”
C
.-0
c)
e
al c
8 0 Q
lo4 3 2.60
h
2.65
2.70
2.75
2.80
2.85
lOOO/l(lIK)
FIGURE19. Bulk lifetime tG and surface generation velocity sG deduced from the plot of Fig. 18.
(at least compared to the temperature dependence of n,). This slight temperature dependence indicates that the dominant generation centers are not precisely at midgap. The generation lifetime is in the vicinity of 200 ns, which is an excellent value for GaAs. We note that the precise values of T~ are somewhat uncertain, since the intercepts in Fig. 18 are estimated by extrapolation and are sensitive to small errors in fitting the data. Of more practical interest is the time constant to be expected if the area of the storage capacitor is reduced below the 62pm per side of the smallest capacitor shown. If we extrapolate the data in Fig. 18 to a side length of 5 pm, we find a storage time of 1.5 sec at 101OC. This is still comfortably above our criterion of 100msec. Therefore it appears that adequate charge storage densities and acceptable storage times can be achieved with storage capacitors down to 5pm on a side.
4. Metal Evaporation Technique Since storage time is determined by extremely small generation currents, it is to be expected that it should be sensitive to certain details of the processing. One of the most important aspects of the processing in this regard is the method of metal deposition. In fact, the storage time of well-made identically prepared samples is reduced by about three orders of magnitude if the ohmic metal is deposited in an electron-beam evaporator as compared to a thermally heated evaporator (Stellwag et al., 1992a). Figure 20 shows storage time versus temperature for four 100 x 100pm2 p-i-n-i-p storage capacitors (Stellwag et al., 1992a). These capacitors are taken from two wafers whose epitaxial layers were grown by MBE using As, and As, flux, respectively. Both p+ layers are doped 1 x 1019cm-3,the n-layer is
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
/
lo5
5
Thermally lo3
Evaporated
i! i=
$
// / AS2
z
d
/
10'
lo-'
10"
E-Beam Evaporated
,
1
I
,
1
,
1
,
1
,
1
1
,
I
,
31
32
JAMES A. COOPER, JR
on the flux conditions during MBE growth. This suggests that, rather than creating new centers, the electron-beam environment is simply activating preexisting centers present in the As-grown film, the density of which depends on the growth conditions.
111. JFET
AND
MESFET DRAM CELLS
A . Introduction
In Section I1 we considered the design and performance of pn junction storage capacitors in some detail. However, the storage capacitor is only half the story. In order to construct a complete DRAM cell, it is necessary to provide an access transistor that will connect the storage capacitor to the bit line for reading and writing and isolate the storage capacitor from the bit line during storage. In this section we will consider two means of implementing this access transistor in GaAs: (i) using junction field-effect transistors (JFETs), and (ii) using metal-semiconductor field-effect transistors (MESFETs). Figure 21 shows how one might implement a one-transistor DRAM cell utilizing a JFET access transistor and a MESFET access transistor. In the following sections we will present experimental results on early versions of both JFET and MESFET DRAM cells, with special attention to the effects of transistor leakage on storage time.
B. Implementations of JFET and MESFET DRAM Cells The first demonstration of a complete JFET-accessed GaAs DRAM cell was reported by Neudeck et al. (1989). The structure, shown in Fig. 22, consists of two large-area p + n storage capacitors surrounded by a ring-gate JFET. Two storage capacitors are used in this implementation so that the charge can be monitored by observing the capacitance between the two p+ plates. This is necessary since the structure is fabricated on a 1 pm undoped buffer layer. The layers are grown by MBE, and the p + gates are patterned by wet etch. The 50nm p-type GaAs layer under the channel is included to improve subthreshold performance of the access transistor, and it is fully depleted during normal operation (Yamasaki, Kato, and Hirayama, 1985). Figure 23 shows waveforms obtained during electrical writing of the cell. The top waveform is the capacitance between the twop+ capacitor plates, the middle waveform is the bit line voltage applied to the source of the JFET, and the lower waveform is a series of 1 msec write pulses applied to the gate of the access transistor (the word line). The word line is held at a negative
33
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES Bit Line
Word Line
PorS.1. GaAs
JFET DRAM Cell
Bit Line
Word Line
ohmic contac
PorS.1. GaAs I
I
MESFET DRAM Cell
FIGURE21. Two examples of FET-accessed DRAM cells in GaAs. Each cell consists of a pn junction storage capacitor and an access transistor. The top drawing depicts a JFET DRAM cell, while the bottom drawing illustrates a MESFET DRAM cell.
potential to keep the JFET biased off. When the word line is pulsed to 0, the JFET is turned on and the potential of the bit line is connected to the storage capacitor. During the first pulse the bit line is positive, and electrons are removed from the n-side of the p n junction storage capacitors. This reverse biases the p n junctions, widening the depletion regions and reducing the capacitance signal. When the second word line pulse occurs, the bit line has returned to 0. This allows electrons from the bit line to flow to the storage capacitors, returning them to their equilibrium conditions. The capacitance is thus increased. One notes that the capacitance signal changes only when the word line is pulsed to 0. This proves that the storage capacitor is effectively isolated by the access transistor: changes in bit line potential have no effect on capacitance while the access transistor is off. The high-capacitance condition occurs when the storage capacitors are in equilibrium, so this state will not decay
34
JAMES A. COOPER, JR. JFET Source (Bit Line)
JFET Drain
JFET Ring Gate (Word Line)
PN Junction Charge Storage Capacitors
50 nm P+ GaAs
FIGURE 22. A prototype JFET DRAM cell implemented in GaAs by Neudeck et al. The cell consists of two storage capacitors surrounded by a ring-gate JFET. Two storage capacitors are used to allow the charge recovery to be monitored by observing the capacitance between the storage gates. A second JFET is included for evaluation purposes (01990 IEEE).
with time. The low-capacitance state represents a reverse bias on the storage capacitor. This is a temporary condition, and the capacitance will gradually return to its equilibrium value as thermal generation discharges the storage capacitor. This can be seen in the waveforms of Fig. 23, where the storage
r
CPII
Capacitance Signal
-
1 -
0
1 msec Write pulse
--)-
-1
-
A L
-2 -
4
wPiue I
4 WPite 0
Bit Line Voltage
4 wuiue I
Word Line Voltage
Time (s)
FIGURE23. Writing waveforms for the JFET DRAM cell of Fig. 22. The upper trace is the cell capacitance, the middle trace is the bit line voltage, and the lower trace is the write pulse train applied to the word line. Note that the cell capacitance changes only at the moments when write pulses are applied to the word line. The stored 1 state gradually decays due to gate leakage in 1990 IEEE). the JFET access transistor and generation in the substrate depletion region (0
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
-
Storage Node Write Pulse
-
0
>
35
-1 -
r
;
:
?
,
:
:
;
:
-
;
;
Word Line Voltage
time is estimated to be on the order of 1 s. This low storage time is due to two factors. First, the gate-to-drain leakage current in the access transistor flows directly to the storage capacitor. In this prototype geometry, the access transistor is a ring-gate configuration that actually maximizes the leakage current supplied to the storage capacitor. Second, the large undoped buffer layer below the storage capacitor provides a large generation volume for leakage currents discharging the storage capacitor. During normal operation of a GaAs DRAM cell, the cell capacitance would not be monitored. Instead, the charge state of the cell would be detected by a change in potential of the bit line when the access transistor is turned on. This mode of operation is demonstrated in Fig. 24. Here the bit line is connected directly to a high-impedance active oscilloscope probe. The top waveform in the figure is the potential of the probe, the middle waveform is a write pulse applied to the p + terminal of the storage capacitor, and the bottom waveform is the pulse train applied to the word line. The write pulse (middle waveform) momentarily forward biases the pn junction storage capacitor, removing electrons from the n-region. During the first word line pulse, the JFET is turned on and electrons flow from the bit line to the storage capacitor to restore the missing electrons. This causes the bit line to jump to a positive potential. The rapid decay of the bit line signal is caused by the RC time constant of the active probe. By the end of the first word line pulse, the bit line potential has essentially returned to ground, and as a result the storage capacitor is also essentially at ground, The second word line pulse produces almost no response on the bit line, since the storage capacitor is
36
JAMES A. COOPER, JR.
Alloyed Ohm (Bit Line) Contact
E, 0
10pm x 200 p n Au MESFET Ga (Word Line)
0
i Storage Node Connection
50 nm
P-
NA = 1 x 10" cm-3
Undoped GaAs
FIGURE25. Top view and cross section of a MESFET DRAM cell implemented by Neudeck et al. This cell employs a linear gate rather than a ring gate, in order to minimize gate leakage current discharging the storage capacitor.
now at ground potential. Thus the charge state of the cell can be determined by detecting the bit line potential when the access transistor is turned on. Similar results have also been achieved using MESFET access transistors (Dungan et al., 1990). Figure 25 shows the top view and cross section of an experimental MESFET DRAM cell (Neudeck, 1991). Notice that in this structure the ring gate has been replaced by a linear gate. Writing waveforms for the MESFET cell are shown in Fig. 26. These waveforms are very similar to those of the JFET DRAM cell in Fig. 23. In order to eliminate the need for a negative supply voltage, the cell is operated with bit line potentials that vary from 1.3V for a logic 0 to 2.45 V for a logic 1. (A thorough discussion of operating voltage considerations for FET-accessed GaAs DRAM cells can be found in Dungan, 1989, and in Dungan et al., 1990). As expected, the cell capacitance changes only when the access transistor is turned on. In spite of the reduced gate width exposed to the storage capacitors, the storage time for this cell is only about 25 msec at room temperature. The drastic reduction in storage time is the result of increased gate leakage in the MESFET as compared to JFET. This effect will be discussed next.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES L
-
P5
Cell Capacitance Signal
4 :
1
-
Q
c
,
3-5
5
-0
’
37
r
Bit Line Voltage
2 -
-_
s”
1 psec Pulse
-
1 -
*-Write
MESFET Gate (Word Line) Voltage
0 I
I
I
I
I
I
I
I
FIGURE 26. Writing waveforms for the MESFET DRAM cell of Fig. 25. The top trace is the cell capacitance, the middle trace is the bit line voltage, and the lower trace is the write pulse train applied to the word line. The access transistor threshold voltage is + 0.8 V, and positively 1990 IEEE). shifted logic levels are employed (0
C . Eflect of Transistor Gate Leakage When an access transistor is connected to the storage capacitor, additional leakage mechanisms are introduced that reduce the storage time of the cell, even when the access transistor is deliberately biased into the off state. These leakage mechanisms are illustrated in Fig. 27. The primary leakage mechanisms are subthreshold leakage of electrons from the source to the drain and leakage of electrons from the gate (or gate depletion region) to the drain. Since the drain is connected directly to the storage capacitor, these leakage paths tend to prematurely discharge the capacitor. Subthreshold leakage from the source can be described by (Conger, (Word Line)
t
4 -
Source
Drain
IDG
(Storage Node)
(Bit Line)
ov
++I++
4
IDS
--r-
FIGURE 27. Drain current components in a GaAs field-effect access transistor. The primary mechanisms affecting DRAM storage time are drain-to-source current I,,, and drain-to-gate current I,.
38
JAMES A. COOPER, JR. 10
10 -5
- VDs = + 0.5V
Transistor
ON
0..
c p! L
a
-1 .o
\
/,
10 -10
-0.5
0.0
. 0.5
Gate Voltage (V)
FIGURE28. Drain current as a function of gate voltage in a GaAs field-effect transistor. I,, is the drain-to-source current and IDG is the drain-to-gate current. I,, decreases exponentially with gate voltage below threshold, but eventually I,, dominates. This gate current is not present in silicon MOS transistors, but it is the dominant leakage mechanism in most FET-accessed GaAs DRAM cells.
Peezalski, and Shur, 1988)
Here ZDs, is the current measured at threshold (VGs= VT), V,, is gate-tosource voltage, VTis the threshold voltage, VDs is drain-to-source voltage, and n is a subthreshold ideality factor. If V,, is greater than a few kT, the term in square brackets approaches unity. In any event, the last factor shows that the current decreases exponentially as V,, is reduced below threshold. Unfortunately, one encounters a fundamental difficulty in taking advantage of this exponential reduction in subthreshold current. This is because GaAs, unlike silicon, does not possess a true insulator that can be placed between the gate and channel. As a result, a significant gate-to-drain current can flow whenever the gate becomes too strongly reverse biased with respect to the channel. This is illustrated in Fig. 28, where we show the measured drain current for a GaAs MESFET as a function of gate voltage (Neudeck, 1991). As gate voltage is reduced below threshold, the drain current in Fig. 28 drops exponentially with gate voltage, in agreement with (59). However, a minimum is reached at a gate voltage of about -0.2V; below - 0.2 V the drain current increases. This increase is due to electrons flowing from gate to drain, and the I-V characteristic in this region is that of the reverse-biased gate-to-channel junction. If the transistor of Fig. 28 were used in a p n junction DRAM cell, the storage time would be reduced to a few hundred milliseconds at room temperature. Obviously, there is considerable motivation for minimizing this effect.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
39
o3
1
10-4
*
=: 3
j
105
104 107
lo4 lov 10-10 10 -11
-2.0
-1.o
-1.5
-0.5
0.0
Gate Voltage (V)
FIGURE29. Drain current vs. gate voltage for a 5 x 350pm ring-gate JFET.
For comparable devices, gate leakage is considerably lower in a JFET than a MESFET (Dungan et al., 1990; Neudeck, 1991). Figure 29 shows drain current versus gate voltage for a 5 x 350pm ring-gate JFET, while Fig. 30 shows drain current in a 10 x 350pm ring-gate MESFET. At room temperature, the gate-to-drain leakage in the JFET is more than two orders of magnitude smaller than in the MESFET. Thus, one expects superior storage time performance from a JFET-based memory. It has been found that the gate-to-drain leakage of MESFETs can be reduced significantly by treating the GaAs surface with ammonium sulfide (NH,),S just prior to thermal evaporation of Schottky metal (Neudeck et al., 1991a). (It is important in this procedure that the metal not be deposited in an electron-beam evaporator). Figure 31 shows drain and gate currents at room temperature for treated and untreated 10 x 350pm ring-gate
10.~ 10’~ 10.~
10.’
10.’ 10.10
-1.4
-1.2
-1.0
-0.8
-0.6
-0.4
-0.2
0.0
Gate Voltage (V)
FIGURE30. Drain current vs. gate voltage for a 10 x 350 pm ring-gate MESFET. Note that at room temperature the gate-to-drain leakage in the MESFET is more than two orders of magnitude higher than in the JFET of Fig. 29.
40
JAMES A. COOPER, JR
10.~ 10.6 10” 10-8
10.”
lo-’* -1.o
-0.5
0.0
0.5
Gate Voltage (V)
FIGURE31. Drain and gate currents for a 10 x 350pn ring-gate MESFET with and without (NH,),S surface treatment prior to gate metal deposition. In the treated device the gate current exceeds the drain current for Vc < - 0.3 V because the gate depletion region is punching through to the substrate, causing substrate holes to flow to the gate. This phenomenon has no effect on DRAM storage (01991 IEEE).
MESFETs. The drain current in the treated device is reduced by about three orders of magnitude compared to the untreated device. (In the treated device, the gate current exceeds the drain current below about - 0.3 eV. This excess gate current is due to gate-to-substrate punchthrough, and has no effect on the storage time of the DRAM cell, since it does not flow to the storage capacitor .) The reduction in gate-to-drain current in the treated devices is attributed to an increase in Schottky barrier height that results from an unpinning of the Fermi level (Carpenter, Melloch, and Dungan, 1988). The (NH,)2S layer is thought to passivate most of the surface states that otherwise would exist at the metal-semiconductor interface. Although (NH,),S-treated surfaces degrade within a few hours if exposed to air, the presence of the metal gate protects the (NH,),S layer in these MESFETs. No changes in I-V characteristics could be detected after over a year of undessicated storage at room temperature.
D. A 4-Bit JFET Dynamic Content-Addressable Memory As a final example of demonstration circuits involving GaAs DRAM technology, we consider the four-bit dynamic content addressable memory (DCAM) constructed by Neudeck and coworkers (Neudeck, 1991). In a content-addressable memory, each storage cell contains logic to compare the bit of information stored in the cell with a binary signal presented on the bit line. The organization of a typical content addressable memory is depicted in Fig. 32. Each word in the memory array contains many bits of data stored
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES Bit Line
41
Bit Line
Word Line
Match Line
Word Line
Match Line
FIGURE 32. Schematic diagram of a content-addressable memory. Each memory cell contains logic elements that compare the contents of the cell to the information on the bit lines. If a bit fails to match, the cell pulls its match line to ground. Only if all cells in a word match the input pattern will the match line for that word remain high.
in individual cells connected to a common word line. In addition, the storage cells in each word of a content addressable memory are also connected to a second horizontal line called the match line. To select a stored word based on content, a binary pattern is impressed on the bit lines. Each cell in the memory compares its stored bit to the bit on its bit line. If any cell finds a mismatch, it pulls its associated match line to ground. Only if every bit in a word matches the input pattern will the associated match line remain high. Content addressable memories are useful in situations where large data bases are to be searched rapidly for specific patterns. The GaAs DCAM cell (Neudeck, 1991) is shown in Fig. 33. This cell consists of two JFET DRAM cells and four additional n-channel JFETs used to implement an exclusive-nor (XNOR) function. A unique feature of this design is the fact that an ohmic contact is established to the n-type region of the storage capacitor in each DRAM cell. This contact is connected to the gate of an n-channel JFET in the XNOR logic so that the contents of the cell can be compared with the new data on the bit lines. Altogether, six transistors and two storage capacitors are required per cell. The cell of Fig. 33 is implemented in a 2 x 2 DCAM array, complete with peripheral circuitry to load the memory with initial data, read the stored data using the bit lines, select the word lines, and read the match lines. In all, 40 JFETs and 8 storage capacitors are involved. Figure 34 shows operating waveforms of the 2 x 2 DCAM array. During the first six cycles a distinctive binary pattern (all 0s) is loaded into the
42
JAMES A. COOPER, JR. Word Line I
-
. Bit
Bit Line
Line
Match Line
5 0,
L
m
B L
Storage Node Contact
Storage Capicitor (Gate Metal)
v)
>m
‘DRAM Access JFET
FIGURE33. Schematic of one cell of the JFET DCAM cell (top) and layout of the cell (bottom). Each cell consists of two one-transistor DRAM cells and four n-channel JFET XNOR transistors. A two-level metal process is employed, with the top interconnect metal placed on polyimide for isolation.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
43
Keyword Input (81 & 82) and Match Line Output (M1 & M2)
MI M2
81
881
82
882
Stored Memory Contents
FIGURE 34. Operating waveforms of the 2 x 2 JFET DCAM array. The two match line and four bit line waveforms are shown for six cycles. During each cycle, the memory is loaded with a four-bit data pattern and then presented with nine interrogation patterns. The boxes at the bottom indicate the data pattern written into each word of the memory. The boxes at the top indicate the nine interrogation patterns and the match line responses. A d represents a “don’t care” condition, implemented by taking both bit and bit-bar lines low; d bits always match the stored bit.
memory. In the next nine cycles, all possible binary input patterns (including “don’t care” inputs) are presented and the match line outputs tabulated at the top of the figure. Beginning with the sixteenth cycle, a new data pattern (all 1s) is loaded into the memory and the interrogation pattern repeated. This cycle continues until all stored data patterns are verified with all possible input combinations. In all cases, the DCAM produced the correct outputs. The array was also tested as an eight-bit DRAM. In this mode, the match lines are ignored and the individual DRAM cells in each DCAM cell are written and read out using the bit lines. The array was fully functional in this mode as well.
44
JAMES A. COOPER, JR.
This DCAM array is far too small to be useful, it does not contain all the necessary peripheral logic such as sense amplifiers and address decoders, and it has not been optimized for minimum cell size or maximum speed of operation. Nevertheless, it does demonstrate that GaAs JFET DRAM cells can be combined into a working memory array, that they can be read and written electrically without interference between adjacent cells or excessive cross talk, and that they can be combined with logic within each cell to operate as a content-addressable memory.
IV. HETEROSTRUCTURE DRAM CELLS A . Introduction
Heterostructure DRAM cells have been investigated by several groups. These cells can be classified into two types: (i) generation-limited cells, similar to the pn junction JFET and MESFET DRAM cells already discussed, in which the nonequilibrium state is a deficit of carriers and the cell returns to equilibrium by thermal generation, and (ii) leakage-limited cells, in which the nonequilibrium state is an excess of carriers and the cell returns to equilibrium by leakage of excess carriers over a potential barrier. As we shall see, the generation-limited DRAM designs have been more successful, since generation is characterized by activation energies of at least half the semiconductor band-gap. To create a comparable leakage-limited memory would require a heterojunction band discontinuity of comparable magnitude. Such band discontinuities are difficult to achieve in 111-V material systems. In the following sections we shall first review the results obtained with leakage-limited devices (undoped heterojunction cells and quantum-well floating-gate cells). We will conclude with a discussion of generation-limited devices (modulation-doped heterojunction cells). B. Undoped Heterostructure DRAMS
A storage capacitor employing an undoped heterojunction (Cooper, Qian, and Melloch, 1986) is shown in Fig. 35(a). The barrier layer is undoped Al,Ga,-.As (x = 0.38), and excess electrons are confined in a two-dimensional electron gas (2DEG) in the GaAs adjacent to the heterojunction, as shown in part (b). Figure 36 shows C-V and I-V characteristics of the structure at 77 K in the dark and under white light (Kleine et al., 1989b). In the dark no measurable current flows, and the capacitance is that of an MOS structure in deep
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
45
FIGURE 35. A leakage-limited heterojunction storage capacitor formed by undoped AlGaAs on GaAs. A cross section of the structure is shown in (a) and the band diagram for the interface region is shown in (b). The top Al,Ga,-,As layer has a mole fraction x of 0.38, while the Al,Ga,_,As layers in the five-period superlattice have a mole fraction of 0.30. The superlattice buffer layer is included to improve material quality of the subsequently grown layers. Electrons in the 2DEG tend to escape. over the heterojunction to the GaAs gate. This leakage process limits the storage time of this capacitor.
46
JAMES A. COOPER, JR.
-
I . r L , , , , I , , , ,
I
,
,
, ,
,,
, , ,
,
, , ,
,
,
, , , ,,
1n-‘
10-7
Gate Voltage [V]
FIGURE36. Capacitance- and current-voltage characteristics of the heterojunction storage capacitor of Fig. 35 at 77 K. The current and the upper capacitance curves were taken under white light illumination, and the lower capacitance curve was taken in the dark. The dark current was too small to be measured. The ledge in the light-on capacitance curve indicates that electrons 1989 IEEE). are being stored in the 2DEG (0
depletion - the capacitance decreases as voltage is swept positive due to the expanding depletion region in the p-type GaAs. Under illumination, photogeneration occurs in the depletion region. Holes are swept into the substrate, while electrons drift to the GaAs/AIGaAs interface, where they are trapped in the potential well. As voltage is swept positive under illumination, a capacitance ledge is observed. This ledge is caused by the screening effect of electrons in the 2DEG at the GaAs/AlGaAs interface. The leakage current also increases. This can be explained as follows: At any bias, a steady state exists between electrons supplied to the 2DEG by photogeneration and electrons escaping the 2DEG to the gate or to the substrate. In the ledge region, not all of the photogenerated electrons flow from the 2DEG to the gate. Some are injected to the substrate, where they recombine with holes, producing no current. As the gate voltage increases, field emission and thermionic field emission of electrons from the 2DEG to the gate increase, and an increasing fraction of photogenerated electrons flow to the gate. The capacitance remains almost constant for a range of gate voltages (the “ledge”) because additional charges added to the gate by the increasing gate voltage are imaged by additional electrons in the 2DEG; the depletion region is shielded from the additional charges and does not expand. Eventually, the 2DEG contains the maximum electron density that can be contained behind the finite potential barrier (AEc = 0.3eV). Beyond this point no more electrons can be added to the 2DEG, and the depletion region is no longer shielded from increases in the gate charge. As a result, the capacitance again
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
-1 .o
0.0
47
1.0
Voltage (Volts)
FIGURE37. Transient capacitance decay at several gate voltages at 55K.When light is extinguished, electrons in the 2DEG leak over the heterojunction barrier to the gate, and the capacitance decreases to the dark value. The lack of hysteresis in the C-V curves in depletion (V, < - 0.4V) proves that all the stored electrons have been expelled from the ZDEG, and none 1989 IEEE). are held in traps (0
decreases with gate voltage. The gate current saturates, since now essentially all of the photogenerated electrons are flowing from the 2DEG to the gate. The various processes by which electrons escape the 2DEG are illustrated in part (b) of Fig. 35. These include thermionic emission over the potential barrier to the gate, thermionic-field emission through the top of the barrier, tunneling from quantized energy levels at E, and E , , diffusion into the substrate, and black-body photoemission over the barrier to the gate (Kleine et al., 198913). The rate at which electrons escape determines the storage time. This escape rate can be determined from a capacitance-time (C-t) transient at any voltage in the capacitance ledge region. An example of a series of such C-t transients is shown in Fig. 37. By a careful analysis of the rate of change of capacitance during each transient, the leakage current can be determined as a function of electric field in the AlGaAs and the quasi-Fermi level splitting in the 2DEG. From these analyses it is possible to distinguish which of the several leakage mechanisms in Fig. 35(b) is dominant in each bias region and to determine relevant constants in the mathematical expressions for each leakage mechanism. We shall not go into such detail here; the interested reader is referred to the literature (Kleine et al., 1989b). The major conclusion to be drawn from the work on leakage-limited undoped heterostructure DRAM cells is that storage times are too short to be useful except at cryogenic temperatures. This is illustrated by Fig. 38, where electron density in the 2DEG is plotted as a function of time following extinction of the light (Kleine et al., 1989b). Symbols represent experimental data obtained from capacitance transients, and lines are theoretical predictions based on the known emission mechanisms. One observes that storage
48
I
10'
10'
102
Time [s]
FIGURE38. Stored electron density as a function of time at 50 and 80K. The points represent experimental data at several values of gate voltage, while the lines are predictions of the emission theory of Kleine et al. (1989b). Storage times are on the order of a few seconds at 80 K (0 1989 IEEE).
times of around 1000 seconds are obtained at 50K. However, at 80K the storage times have dropped to the order of a few seconds. Measurements at higher temperatures are not practical due to the short time constant of the C-t transient. Figure 39 shows the heterojunction barriers in the GaAs/AlGaAs system as a function of AlAs mole fraction (Batey and Wright, 1986). The largest conduction band discontinuity, about 0.35 eV, occurs around x = 0.4, where the AlGaAs bandgap becomes indirect. This is very close to the mole fraction of the samples presented in Figs. 35-38. However the valence band discon0.6 0.5
0.4
I5 '0
w" U
0.3 0.2 0.1
0 0.0
0.2
0.4
0.6
0.8
1.0
AlAs Mole Fraction
FIGURE39. Conduction and valence band discontinuities in the AlGaAs ternary system as a function of AlAs mole fraction. The largest discontinuity in the conduction band occurs around x = 0.4,where the AlGaAs becomes indirect. In the valence band, however, the discontinuity increases monotonically as x approaches unity.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
49
0
I
Barrier
Potential Well
AuZn
-
f
N GaAs 1 ~ 1 0 cm3 '~
\
3 N+ GaAs Substrate
FIGURE 40. A heterojunctioncapacitor for storing holes at the interface between undoped AlAs and n-type GaAs. The valence band discontinuity at this interface is about 0.55 eV.
tinuity increases monotonically, reaching a maximum value of about 0.55 eV at x = 1. Perhaps an advantage can be gained by storing holes in a twodimensional gas at the GaAs/AlAs interface! Figure 40 shows a heterostructure storage capacitor formed by undoped AlAs and n-type GaAs. This capacitor was also studied by the method of C-t transients (Qian, Melloch, and Cooper, 1986, 1989), and the results for a gate voltage of - 3 V are shown in Fig. 41. Here we see that storage times of tens of seconds are obtained at 100 K, and measurable charge storage persists to almost 200 K. Again, however, room temperature operation is not feasible. In addition to questions of storage time, we must also consider the charge storage density of heterojunction DRAM cells. The hole memory capacitor of Fig. 41 can retain about 8 x 10" holes per cm2at 150 K, while the electron capacitor of Fig. 38 retains only about 1 x 10" electrons per cm2at 80 K. In order to store lo6 carriers, the hole capacitor would need to be at least 1 1 x 11pm2, while the electron capacitor would need to be at least 32 x 32 pm2. In Section I1 we found that pnp homojunction capacitors could be made as small as 5 x 5pmZ. C. Quantum- Well Floating-Gate DRAMS
Two groups have investigated charge storage in quantum wells formed by heterojunctions. The first such structure was reported by Capasso and co-workers (Capasso et al., 1988; Beltram et al., 1988), and is shown in Fig. 42. In this structure a GaAs quantum well, formed between two AlAs barriers, serves as a floating gate for an underlying field-effect transistor. Electrons are injected into the quantum well from the gate by a negative pulse. This injection is aided by grading the band-gap of the barrier layer between the gate and the quantum well. Once stored, the electrons cause a positive shift in the threshold voltage of the underlying transistor. This
50
JAMES A. COOPER, JR.
90 K
vg = -3.0 v
10
.---.
3
N
I
b!
E
L
rl
0
4
x
5
h
Y
v
a
..
A
0
lo-'
I
10"
I
10'
I
102
lo3
t [sec]
FIGURE 41. Hole density in the capacitor of Fig. 40 as a function of time at several temperatures. Hole densities in the low 10" cm-' range can be retained for several seconds at temperatures up to 190K, but room temperature operation is not feasible.
threshold shift can be detected by observing the current in the transistor, providing a form of nondestructive readout. In the GaAs/AlAs version, the room temperature storage time was about 2 sec, increasing to about 4 hr at 77 K. Figure 43 shows drain current transients at 140 K and at room temperature following filling pulses from the gate. From measurements of effective threshold voltage shift, a sheet charge density of about 10l2cm-2 was inferred for the quantum well. A similar structure was investigated by Lott, Klein, and Weaver (1989b). This structure differed from the structure of Fig. 42 in that a variable-period superlattice was used to produce the graded-band-gap effect in the injector region. Storage times of around 1 sec were reported at room temperature, with sheet charge densities above 10''cm-2. The latter workers have also reported similar devices using InAs (wells)/ AlAsSb (barriers) on InAs substrates (Lott et al., 1989a), and using InGaAs (wells)/InAlAs (barriers) on InP substrates (Lott et al., 1990). The InAs/ AlAsSb structures exhibited a l / e storage time of only 50 sec at 77 K. Storage time data was not reported at higher temperatures. The InGaAs/InAlAs devices had storage times of around lOsec at 200K, decreasing to less than 1 s at 250 K. In the latter devices, the dominant mechanism of charge loss was
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
N+Gah 500nm
graded undoped
"raped
AlGaAs 180 nm
1
200 nm
U AlAs 100
nm
51
N SI GaAs OeAS 75 Substrate nm
Equlllbrlum
Du~Ing WRITE phase
FIGURE 42. A floating-gate DRAM cell in which electrons are stored in a GaAs quantum well between two AlAs barrier regions. Electrons are injected from the top gate over a compositionally graded AlGaAs barrier. The presence of electrons on the floating gate modulates the 1988 IEEE). current in the GaAs channel below, providing nondestructive readout (0
identified as horizontal leakage over a lateral potential barrier, rather than vertical emission over the heterojunction discontinuity. The quantum-well DRAM structures described previously are qualitatively similar to the single-heterojunction storage capacitors discussed in Section 1V.B. In both cases electrons are retained behind the potential barrier created by the conduction band discontinuity at a heterojunction. The storage time is determined by the rate at which electrons are emitted over the heterojunction. In comparing the storage times reported for these two types of structures, a striking difference in storage time is apparent: The capacitors of Section IV.B, which were based on the heterojunction between GaAs and Al,Ga,_,As
52
JAMES A. COOPER, JR.
-a -E
2 c5-)/-vw
atp= loops
Atp=1 ms
(z
(b)
3
za
4T=300K
a
n
3
I
I
9
5-
T= 140K
-
I WRITE
4-
0
WRITE
ERASE (SHORT LIGHT PULSE)
2
4 TIME
6
(c)
8
10
(5)
FIGURE 43. Channel current in the floating-gate DRAM of Fig. 42 as a function of time at (a) 140K and (b) room temperature. The current transients have time constants of 4 hours at 140 K and 2 seconds at room temperature. Part (c) illustrates the write-erase operation at 140 K (erase is accomplished by shining light on the sample) (01988 IEEE).
(x = 0.38), had measurable storage times only below 100 K. In contrast, the quantum-well capacitors of Section C, based on the heterojunction between GaAs and AlAs, had storage times of 1-2 sec at room temperature and 4 hr at 140K. What can account for such a dramatic difference? One possible explanation is that the GaAs/AlAs and InAs/AlAsSb systems are heterojunctions between direct band-gap and indirect band-gap semiconductors. Thus, electrons residing in the r valley in the quantum well must be emitted into the X valley in the barrier. The thermionic emission rate of
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
53
electrons over a potential barrier decreases exponentially with the barrier height. However, Solomon, Wright, and Lanza (1986) have argued that when the heterojunction is indirect, the prefactor before the exponential term is diminished, owing to reflections caused by wave function mismatch. A similar argument applies to thermionic-field emission (tunneling). Solomon et af. (1986) have calculated these prefactors from measurements of dc current through n+ in- n+ structures, where the i layers were undoped Al,Ga, -,As (0.3 < x < 0.8) and the doped layers were GaAs. They conclude that the prefactor for thermionic emission decreases by about a factor of 200 at x = 0.8 as compared to the value when x < 0.4. For thermionic-field emission, the prefactor decreases by about a factor of 2500 at x = 0.8. However, Kleine, Melloch, and Cooper (1989a) have pointed out that these decreases are insufficient to explain the reported room temperature storage times of the quantum-well storage capacitors. Kleine et al. measured the transient decay of electron density at the heterojunction between GaAs and Al,Ga,-,As at 55K for mole fractions of 0.4, 0.6, 0.8, and 1. The optimum mole fraction for electron storage at this temperature was found to be between 0.4 and 0.6, and the storage time decreased markedly as the mole fraction approached unity (Kleine et al., 1989a). Moreover, they showed that the storage time of a GaAs/AlAs barrier at room temperature, based on the parameters of Solomon et al., would be less than 1psec. Another possible explanation for the long storage times reported for quantum-well capacitors is charge trapping (Kleine et af., 1989a). It is not possible to determine from capacitance or threshold voltage transients whether the stored charges are mobile or confined in deep traps in the material. Certainly, if charges were confined in traps, the storage times would be much greater than predicted by thermionic emission or thermionic field emission theories. If charge trapping were taking place, the cell would also be highly resistant to electrical erasure, and could not function effectively as a random-access (read-write) memory. Indeed, the floating-gate cells of Capasso et al. (1988) and Beltram et af. (1988) could not be electrically erased, and instead were erased with light. Moreover, evidence of charge trapping in the AlAs was specifically mentioned by the groups investigating GaAs/AlAs quantum-well capacitors (Capasso et al., 1988; Beltram et al., 1988; Lott et al., 1989b). In the single-heterojunction results reported in Section B and in the emission study of Kleine et al. (1989a), charge trapping could be ruled out by the fact that no hysteresis was observed when C-V curves were swept rapidly in both directions (electrical removal of stored electrons). To summarize this rather confusing section, quantum-well storage capacitors have exhibited storage times up to 1-2 sec at room temperature, although some controversy exists regarding the explanation for the storage
54
JAMES A. COOPER, JR.
I
2DEG
P+ GaAs
....................
I
N AlGaAs
P GaAs P+ GaAs Substrate
FIGURE44. Cross-section and band diagram of a modulation-doped heterostructure storage capacitor. Because of the band banding in the AlGaAs layer, the Fermi level at the interface lies above the conduction band in the GaAs. As a result, a 2DEG will be present at the GaAs/AlGaAs interface in equilibrium.
phenomenon. The issue is made moot, to some extent, by the results obtained with simple pn junction storage capacitors in Section I1 and the results to be reported in the next section. D . Modulation-Doped Heterostructure DRAMS
A heterostructure capacitor employing modulation doping is illustrated in Fig. 44. This type of structure has a distinct advantage over both the undoped heterostructure capacitors considered in Section B and the quantum-well capacitors discussed in the last section. This is because the modulation-doped structure of Fig. 44 is generation limited, in the sense that it retains a two-dimensional electron gas as the equilibrium state. The non equilibrium
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
55
Access
P+ substrate
L--
Storage Capacitor
, Word Ly,
FIGURE45. Cross section of a MODFET DRAM cell. This cell consists of a rnodulationdoped heterostructure capacitor and a MODFET access transistor.
state is achieved by removing electrons, and the structure returns to equilibrium by thermal generation, just as the pn homojunction capacitors of Section 11. Thus one expects storage times in modulation-doped heterostructure capacitors to be comparable to those in p n homojunction capacitors. Figure 45 illustrates a complete one-transistor DRAM cell using a modulation-doped heterostructure (Kleine, Cooper, and Melloch, 1991). A p + GaAs layer is used as the gate of the access transistor and the top electrode of the storage capacitor. This p + layer has a higher barrier to the AlGaAs than a metallic gate, thus reducing gate leakage current in the access transistor (Priddy et al., 1987). The AlGaAs layers have an AlAs mole fraction x = 0.3. The storage capacitor is 187 x 190pmZ,while the access transistor has a gate length of 5Spm and width of 54pm. Storage times of an isolated modulation-doped storage capacitor and a complete DRAM cell are shown as a function of temperature in Fig. 46. As was the case with JFET and MESFET DRAM cells, addition of the access transistor reduces storage times by several orders of magnitude. This is due to gate leakage current flowing when the transistor is biased off. At room
56
JAMES A. COOPER, JR. Temperature ("C) 105f,'
144 .
,
111 '
'
60
84 '
'
'
39 ,.
21 ,
1OOO/T (1/K)
FIGURE46. Storage times of an isolated modulation-doped storage capacitor and a complete MODFET DRAM cell as a function of temperature. The isolated capacitor has a storage time of 4.3 hr at room temperature. The storage time of the complete cell is reduced to about 2 min at room temperature because of leakage currents in the MODFET access transistor.
temperature, the storage time of an isolated modulation-doped storage capacitor is about 4.3 hr. In the complete DRAM cell, gate leakage in the access transistor reduces the storage time to about 2min at room temperature. The storage capacitor exhibits two activation energies, indicating two independent generation processes are occurring. The fact that both of these activation energies are greater than half-band-gap suggests generation through centers some distance from the middle of the band-gap. The results shown in Fig. 46 were obtained on cells that had thermally evaporated metal. The use of electron-beam metallization reduces the storage time of isolated capacitors to around 15min at room temperature. This is consistent with the results reported for pn junction storage capacitors in Section II.D.4. Figure 47 illustrates electrical writing of the MODFET DRAM cell. The charge state of the storage capacitor is monitored by measuring the capacitance between the storage gate and the substrate. A gate bias of - 2.9 V was applied to the access transistor during storage, and the gate was pulsed to 0 to write information into the cell. The arrows indicate the points where the MODFET access transistor was momentarily pulsed on. Write pulses as short as 20nsec were effective in writing the cell. Shorter pulses were not investigated due to equipment limitations. It can be seen that for this particular device the room temperature l/e capacitance recovery time is about 3 min. The bit line waveforms during reading are shown in Fig. 48. Here the potential of the bit line is monitored by a high-impedance FET probe. The 2DEG in the storage capacitor is first partially removed by pulsing the
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES 11
0.5
10
0.4
9
0.3
a 0 8 c m c
0.2
E: a v
-k 0
-
’ 0
.-O
7
0.1
Q
6
0.0
al
=-
m
B -
8
57
C
2
-0.1
5 4
-0.2 0
200
100
300
500
400
600
Time (s)
FIGURE 47. Writing waveforms for the MODFET DRAM cell of Fig. 45. Note that the cell capacitance changes only at the instants when write pulses are applied to the word line (indicated by arrows). The storage time of this cell can be estimated from the capacitance transient to be about 3 min at room temperature.
storage gate to a negative bias for sufficient time for the electrons to recombine with substrate holes. The pulse voltage magnitude is indicated on the figure. Note that for the largest pulse voltage shown here (- 1.5V), the 2DEG is still not totally removed, since the threshold voltage for this device is - 2.08 V. The access transistor is turned on at t = 0, which is 50 msec after the end of the emptying pulse. For r > 0, charge sharing occurs between the storage capacitor and the combined capacitance of the bit line and FET probe, resulting in a voltage output proportional to the charge required to refill the storage capacitor. The decay of the output signal for r > 0 is due primarily to the conductance of the FET probe. 0.5
E
-.-m
,
,
I
,
,
,
,
,
,
,
,
,
,
,
,
. , ,
,
,
,
,
300 K
0.4
E: 0.3 al w
tc
0.2
.=
0.1
0
.4 m
0 -10
0
20 Time (ps)
10
30
40
FIGURE48. Bit line waveforms during reading of the MODFET DRAM of Fig. 45 as a function of the write pulse voltage used to empty the storage capacitor. The access transistor is turned on at time t = 0, which occurs 50msec after a I is written to the cell. The storage capacitor contains a partial 2DEG even for the - 1.5 V case, since the threshold voltage for total removal of the 2DEG is - 2.08 V.
58
JAMES A. COOPER, JR.
output
Memory Cel I S
F1
MODFET F3
F2
s
F4
D
500 nm undoped AlGaAa
-
950 nm p AlGaAs
-
360 nm p GaAs
seml-InsulatingG a b substrate
FIGURE49. A modulation-doped heterostructure DRAM cell reported by Chen et al. Electrons are stored in the 2DEG under gate F2, while gates F1 and F3 are used for isolation. The transistor formed by gate F4 is used to buffer the output. During testing, gate F3 was left on permanently. In an actual DRAM, transistors FI and F3 would be replaced by a single MODFET (reprinted with permission of Lincoln Laboratory, Massachusetts Institute of Technology, Lexington, Massachusetts).
A similar modulation-doped heterostructure DRAM cell has been reported by Chen, Goodhue, and Mahoney (1991). This cell, shown in Fig. 49, utilizes a 20 nm undoped GaAs quantum-well channel grown on a fourperiod AlGaAs/GaAs superlattice buffer layer. An undoped AlGaAs layer and a p + AlGaAs barrier are placed under the superlattice to prevent electron emission to the semiinsulating substrate, and a modulation-doped barrier is grown on top of the GaAs channel. All AlGaAs layers have mole fraction x = 0.23. The primary storage gate is labeled F2, and two separate transistors, labeled Fl and F3, are used for writing and reading the cell. An output MODFET, F4, is also included to amplify the signal resulting from charge transfer when F3 is turned on. In functionality demonstrations, however, Chen et al. kept F3 biased on to avoid capacitive coupling between the read pulse and the cell and placed a 1 MQ resistor in series with the gate of F2 to minimize coupling of the write pulse applied to F1. The circuit of Fig. 49 has a storage time of only 250msec at room temperature, probably due to leakage through transistor F3, which is always left on. However, large-area isolated storage capacitors exhibit storage times as long as 5.4sec at room temperature and up to 40 sec at 77 K. The charge storage density is 4.5 x 10" electrons per cm'.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
59
V. BIPOLARDRAMs A . Introduction
In Section I1 we found that the storage time ofpn junction storage capacitors is limited by thermal generation of hole-electron pairs. This process is slow in higher band-gap materials such as GaAs, and well-made storage capacitors can have storage times of several hours at room temperature. In Sections I11 and IV we learned that the addition of a field-effect access transistor (either JFET, MESFET, or MODFET) reduced the overall storage time of the complete cell to the order of 0.1-100sec. This drastic reduction in storage time is due to unavoidable gate leakage when the access transistor is in the off state. We note that silicon DRAM cells avoid this problem because MOS transistors have essentially no gate leakage. The most straightforward way to eliminate gate leakage in the access transistor is to eliminate the gate! This can be done if, instead of a field-effect access transistor, we employ a bipolar access transistor. We should point out that bipolar DRAM cells are really not new, since DRAMs based on integrated injection logic were introduced in silicon in the early 1970s (Sander and Early, 1976; Quinn et al., 1978). These cells worked well, but they offered no particular operational advantage over MOS DRAM cells, since MOS cells in silicon are not limited by gate leakage. However, in GaAs the advantage over FET-accessed cells is enormous. In this section we will discuss the operation of a bipolar DRAM cell in GaAs. B. Concept of the Bipolar DRAM Cell A bipolar DRAM cell in GaAs (Stellwag, Cooper, and Melloch, 1991, 1992) is illustrated schematically in Fig. 50. This cell can be recognized as the basic pnp storage capacitor of Fig. 4 with an additional n-type layer on top. This n-type layer, together with the p - and n-type layers immediately beneath it, form an npn bipolar transistor. This bipolar transistor is merged with the pnp storage capacitor, as indicated in the figure. The base of the bipolar transistor is connected to the word line and the emitter to the bit line. The collector is floating and forms a p n junction with the substrate. The capacitance of this latter pn junction, together with the capacitance of the base-collector junction, stores the charge. Operation of the bipolar DRAM cell is illustrated in Fig. 51. In equilibrium, the n-type collector is at ground potential, corresponding to a stored logic 0 (part a). A logic 1 is written by removing electrons from the collector. This is done by taking both bit line and word line positive, thereby forward
60
JAMES A. COOPER. JR
Bit Line NPN Bipolar Access Transistor
Word Line
t ...........
%
.......
P GaAs N GaAs
Floating Collector
PNP
Storage Capacitor
P+ GaAs substrate
*
FIGURE50. Cross section of a bipolar DRAM cell in GaAs. An npn bipolar transistor is merged with a pnp storage capacitor to form the cell. Alternatively, the cell may be viewed as an npn bipolar transistor with a floating collector, with the collector specially constructed to have a large capacitance to ground.
biasing the collector-base junction (part b). Electrons will flow from the collector to the emitter until the collector-base voltage has been reduced to 0. The collector is now at the potential of the word line. If both bit line and word line are returned to ground, part (c), the collector remains positively charged due to the loss of electrons. The structure is now storing a logic 1. Note that all potentials applied to the cell are now at ground. As a result, the only currents that will discharge the collector are those due to generation in the depletion regions of the two reverse biased junctions. This is the same situation as the pnp storage capacitors of Section 11, where storage times of several hours were obtained at room temperature. Also, note that, since storage takes place with all terminals at ground potential, no power is dissipated in the storage state. Indeed, the memory can be considered nonvolatile, in the sense that all external power can be removed without loss of stored data, at least for times short compared to the normal storage time of the cell. The cell can be written to a logic 0 state by keeping the bit line at ground and taking the word line slightly positive, as shown in part (d). Electrons then flow from the emitter to the collector until the collector-toemitter voltage is 0. In examining the sequence of band diagrams in Fig. 5 1, we note a conflict. To empty the cell, the word line and bit line are taken several volts positive. To fill the cell, however, the bit line is kept at ground and the word line is taken only slightly positive. Since we have no way of knowing whether the bit line will be positive or at ground during a particular writing operation, how can we know to what potential to take the word line? The answer is that the writing operation must be a two-step procedure: First all cells in a word
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES Substrate
61
Floating coiiector
%?* \....
0
.
(a)
Store Zero (Equilibrlurn)
0
....
(b) Read -or-
Write One
0
0
0
(c) Store One
FIGURE 51. Band diagrams illustrating the operation of the bipolar DRAM of Fig. 50. Data consists of the presence or absence of electrons in the floating collector. Electrons are removed by taking both the word line and bit line positive, as shown in part (b). Data is stored when both the word line and bit line are at ground potential, as in parts (a) and (c). Electrons are inserted by taking the word line slightly positive while the bit line is held at ground, part (d).
must be emptied (word line and all bit lines taken several volts positive), then the cells must be selectively refilled, based on the bias state of their particular bit lines (word line taken only slightly positive). From the schematic drawing in Fig. 50, two other advantages of the bipolar cell can be seen. First, the cell conserves area, since the access transistor is vertically integrated on top of the storage capacitor. Second, the cell is inherently fast, since charge transport during reading and writing is vertical rather than horizontal. This latter point deserves further explanation. In FET-accessed cells such as shown in Fig. 21, charge transport occurs laterally along the FET channel. During reading and writing, the storage capacitor in these structures functions essentially as a long-channel FET, and the channel can pinch off, limiting current flow. This pinch-off effect is avoided in the bipolar structure.
62
JAMES A. COOPER, JR.
The bipolar DRAM of Fig. 50 can also be realized as a heterojunction bipolar transistor, or HBT. In the HBT the emitter is formed from AlGaAs, and the base and collector from GaAs. HBTs are widely used in GaAs bipolar circuits because the valence band offset at the emitter-base junction drastically reduces hole injection from the base into the emitter, improving the emitter injection efficiency. This improvement is so great that it is no longer necessary to keep the base doping lower than the emitter doping. The increase in base doping has the added advantage of reducing the base spreading resistance. To apply these ideas to the bipolar DRAM cell, we must consider the requirements on the bipolar access transistor. As illustrated in Fig. 51, the operation of the bipolar DRAM dictates that the access transistor operate in both the forward and inverse modes. When electrons are removed from the floating collector (Fig. 51(b)), the transistor is in the inverse mode, with the collector functioning as an emitter and the emitter functioning as a collector. If we construct the cell using HBT technology, it will be desirable to fabricate both the collector and emitter in AlGaAs to enhance both forward and inverse operations. Therefore, we envision a double-heterojunction bipolar transistor in which the n-type emitter and n-type collector are both AIGaAs. The presence of a heterojunction in the reverse-biased collector-base junction would have minimal effect on forward operation. A further extension would be to make all layers (except the base) AlGaAs, since this would reduce generation in the depletion region of the collectorsubstrate junction. C . Experimental Results A prototype homojunction bipolar DRAM cell is shown in cross section in Fig. 52. This cell was grown by MBE, and metalized using a thermal evaporator (Stellwag et al., 1991a, 1992b). The storage time of the cell is measured by observing the transient recovery of the base capacitance following writing a logic 1. The capacitance transient of a 36 x 48 ,urn2cell at room temperature is shown in Fig. 53. The l/e recovery time is 16,200 sec, or 4 . 5 hr. This storage time is of the same magnitude as storage times of isolated pnp capacitors reported in Section 11, indicating that the presence of the bipolar access transistor has no negative effects on storage time. Figure 54 shows storage time as a function of temperature for several bipolar DRAM cells. An activation energy of 0.88 eV is common to all cells, and larger cells have slightly longer storage times, consistent with the scaling arguments presented in Section II.D.3. The cell is electrically written in Fig. 55. The 3 V, 1 msec word line pulses are not shown, but occur at the points indicated by arrows. Note that the capacitance increases when the bit line is at ground (store 0 state), since this
63
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
p+ GaAs I I
1x10 19cm-3
Access Transistor
100 nm
I GaAs
30 nm 5x10 "cni3
p+ GaAs
I I
200 nm
1x10 '9cmi3 1000 nm
p+ GaAs Substrate
FIGURE 52. Cross section of the experimental device used to verify the operation of the 1992 IEEE). bipolar DRAM (0
returns the cell to equilibrium. When the bit line is positive (store I state), the capacitance decreases. This is because electrons have been removed from the floating collector, widening the depletion regions. The capacitance transient in the store 0 state is due to the turn-off time of the forward-biased emitterbase junction, as excess carriers are removed by recombination. This transient has no effect on operation of the memory. We should emphasize that in the high-capacitance store 0 state, the cell is actually in equilibrium, Time (hours) 0
2
4
6
1.10
G'
e 8c
1
105
-
.
,
0
10
mj. I '
.
-
m
0
10,000
20,000
30,000
40,000
Time (sec) FIGURE 53 Capacitance recovery transient measured at the base contact of the bipolar DRAM cell of Fig 52 at room temperature A recovery time constant of 4 5 hr is observed (01992 IEEE)
64
JAMES A. COOPER, JR. Temperature ( "C ) 144
111
84
60
40
21
1
105
2.4
2.6
2.8
3.0
1000 / T (1/
3.2
3.4
K)
FIGURE54. Storage time as a function of temperature for several bipolar DRAM cells. All cells have an activation energy of about 0.88 eV. Storage time decreases slightly as the cell is 1992 scaled to smaller dimensions, as expected from the scaling discussion in Section I1 (0 IEEE).
and no further decay of capacitance will occur. The nonequilibrium condition actually corresponds to the low-capacitance store 1 state. Thus, the capacitance in the store 1 state will gradually rise (with a time constant of 4.5 hr at room temperature). No such rise is perceptible on the short time scale of this figure.
VI. FUTURE DIRECTIONS A . Introduction
In the five previous sections we have described experimental work that has led to the present state of the art in GaAs one-transistor DRAM cells. Over the past years, storage times in GaAs capacitors have increased dramatically - from about 3 min at room temperature in 1987 to over lOhr in 1991, and the trend seems likely to continue. Moreover, the use of bipolar access transistors, as described in Section V, makes it possible to construct complete DRAM cells having storage times on the same order of magnitude as the capacitors alone. The charge storage density of p n junction capacitors in GaAs is comparable to that achieved in planar storage capacitors in silicon. What next? What directions should GaAs DRAM development take from this point? What applications can be identified that would lead to commercialization of these devices? We will address some of these questions in this final section.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
65
-
L
c m
Equilibrium Capacitance
I
---
m
c)
Store 0
0
8 0
Store 1
m
iL------1
0
200
400
600
800
1000
Time (sec)
FIGURE 55. Electrical writing of the bipolar DRAM cell. For this test, the charge state of the cell is monitored by observing the base capacitance. To write the cell, 3 V, 1msec write pulses are applied to the word line at the times indicated by arrows. The capacitance decay in the store 0 state is due to the turn-off transient of the forward-biased emitter-base junction, and it has no effect on operation. The store-0 state is in fact the equilibrium condition and will never decay. The low-capacitance store 1 state is the nonequilibrium condition. This capacitance will gradually increase with a time constant of 4.5 hr at room temperature. This increase is imperceptible on the time scale of this plot (0 1992 IEEE).
B. Trench Capacitors and Stacked Capacitors in GaAs One of the dramatic developments in the evolution of silicon DRAMs was the introduction of vertical structures to increase the effective charge storage density (Sunami, 1985; Lu, 1989; Sunouchi et al., 1990). These vertical structures take the form of trench capacitors and stacked capacitors, as illustrated in Fig. 56. A large number of variations on these basic ideas have been proposed, but we will not attempt to review them here. The main point is that vertical structures have become absolutely necessary in silicon DRAMs at the integration levels prevalent today. On first glance it would appear that GaAs would be unable to emulate these vertical structures, and so would be totally unable to compete for high-density DRAM applications. However, that may not be the case at all. In this section, we will describe early efforts to develop a trench capacitor
66
JAMES A. COOPER, JR. Bit Line
Word
Line
Plate Voltage
SIO,
P Silicon
Trench Capacitor Cell
Plate Voltage Bit Line
Word Line
P Silicon
P Stacked Capacitor Cell
FIGURE56. Two types of vertical-geometry DRAM cells in silicon. The trench capacitor cell conserves area by placing the storage capacitor on the sidewalls of a vertical trench. The trench aspect ratio can be as high as 30: 1. The stacked capacitor cell utilizes a multilayer sandwich of insulating and conducting layers formed on top of the semiconductor surface.
technology in GaAs. We will also speculate on the use of stacked capacitors in conjunction with GaAs DRAM cells. Trench capacitors and complete trench DRAM cells can be grown in GaAs using a technique known as atomic layer epitaxy (ALE) (Bedair et al., 1985). ALE is a gas-phase epitaxial growth technique similar to metal-organic chemical vapor deposition (MOCVD) except that special precautions are taken to expose the growth surface to only one species of adatom at a time. Epitaxy is carried out in a temperature range where growth is self-limiting, so that a single monolayer of either Ga or As is formed during one cycle. The growth surface is alternately exposed to ambients containing Ga and As source gases, resulting in layer-by-layer growth. This leads to unprecedented control of the growing film on an atomic level. One very useful property of this growth technique is the ability to grow high-quality layers conformally on vertical sidewalls of etched trenches. This property is exploited to build trench DRAMS in GaAs. Figure 57 is a scanning electron micrograph of four 100 x 100pm’ mesaisolated GaAs p n diodes grown by ALE over a substrate in which several square 2pm deep trenches were etched prior to growth (Neudeck et al.,
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
67
FIGURE 57. SEM photograph of four 100 x 1oOpm2mesa-isolated pn diodes grown by ALE conformally over a substrate in which 2 pm deep trenches were etched prior to growth. Two of the mesas have a single 30 x 30pm2trench each, one mesa has nine 10 x 10pm2trenches. and one is planar (no trenches). The planar mesa is at the upper right. The light-colored square regon near the center of this device is the metal ohmic contact. An SEM cross section of one of the trenches is shown at the bottom.
68
JAMES A. COOPER, JR. Area = 100 x 100 pm
-1
0
-0.5
0.5
Voltage (V)
FIGURE58. Current-voltage characteristics at 1 4 4 O C for three ALE-grown pn diodes (symbols) with and without trenches. The nine-trench diode has 360pm of trench sidewall, while the one-trench diode has 120pm of trench sidewall. The line represents one of the best MBEgrown planar diodes.
1991b). Three types of diodes are shown: the diode on the upper right has no trenches (planar diode), the diodes on the upper left and the lower right each have one 30 x 30pm’ trench, and the diode on the lower left has nine 10 x 10pm2 trenches. The surface morphology is smooth, and conformal growth of epitaxial layers over the trench sidewalls is observed. Figure 58 shows the current-voltage characteristics of these three types of structures at 144OC. Also shown for comparison is one of the best planar diodes grown by MBE. Both forward and reverse currents are larger for the diodes containing trenches, but the reverse characteristics are not significantly degraded. Figure 59 shows the dependence of reverse current on trench perimeter for the three structures at a reverse voltage of 1V. Note that the one-trench and the nine-trench diodes each have the same trench area and same total diode area,
0
100
200
300
400
Trench Perimeter (pm)
FIGURE59. Leakage current at 144°C and 1 V reverse bias for the three ALE diodes of Fig. 5 8 . The reverse leakage increases linearly with trench perimeter.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
69
but the trench perimeter differs by a factor of three. From this plot it is apparent that the reverse leakage scales with trench perimeter. It is not possible to determine from this measurement whether the leakage is due to the sidewalls themselves or to generation at the edges where the vertical sidewalls meet the horizontal top and bottom surfaces. This question can be resolved by a study of the dependence of leakage current on trench depth. Measurements of leakage current as a function of temperature indicate that the leakage is thermally activated. The planar diodes have an activation energy of 0.713 eV while both the trenched samples have an activation energy of 0.844 eV. These samples were metalized by electron-beam evaporation. Further work is needed to determine the dependence of leakage current on trench depth and sidewall orientation. In addition, both pnp storage capacitors and bipolar DRAM cells need to be built using this technique, and storage times need to be measured as a function of trench depth and orientation. Preliminary evidence based on the diode leakage measurements suggests that the degradation of storage time caused by the trenches would be within acceptable limits. The advantages of increased charge storage in the same amount of horizontal chip area would probably far outweigh the negative effects on storage time, particularly when storage times of planar devices are now measured in terms of hours at room temperature. Another approach to achieve higher charge storage densities with nonplanar capacitor structures is the use of stacked capacitors, similar to those illustrated in Fig. 56. In silicon DRAMS these stacked capacitors are formed by alternating layers of polysilicon conductors and SiO, insulators fabricated by a complex and ingenious sequence of deposition and selective etching. There is no fundamental reason why these steps cannot be performed on GaAs substrates. In effect, we are proposing that the storage capacitor need not be integral to the GaAs substrate, but could simply be deposited on the top surface after all the GaAs active devices are fabricated. This would open the possibility for a number of different structures, including metaloxide-metal capacitors, stacked capacitors such as shown in Fig. 56, and capacitors having a ferroelectric material as dielectric. C . Nondestructive Readout Cells
Another direction that shows great promise are GaAs DRAM cells that provide nondestructive readout with internal gain. Two types of structures are known to be under investigation (Cooper, 1989; Hetherington, Klein, and Weaver, 1991). One such structure, the bipolar/field-effect (BiFET) cell (Cooper, 1989), is shown in Fig. 60. Here the basic bipolar cell of Section V has been modified by the addition of a second base contact. This second contact allows the base layer to function as the channel of a lateral JFET,
70
JAMES A. COOPER, JR Gate / Emitter Source / Base
P I 30 nm undoped
r-
-
Y
Drain / Base
P
N GaAs P+ GaAs
I
N+ GaAs
l
FIGURE 60. A proposed bipolar-field-effect (BiFET) DRAM cell. The cell operates as a bipolar storage cell as described in Section V. Once a potential is stored on the floating collector, the depletion region of the collector-base junction modulates the lateral conductivity of the base layer. By establishing two ohmic contacts to the base, it is possible to detect the charge state of the floating collector by measuring the current between the two base contacts. In effect, the base forms a lateral JFET, gated from above by the emitter and from below by the floating collector.
gated from the top by the emitter and from the bottom by the floating collector. As a result, the current in the JFET is controlled by the potential of the floating collector, providing nondestructive readout. Because the cell now has gain, a robust signal can be placed on the bit lines during readout. Data is written to the cell in the conventional way using the bipolar access transistor (see Section V). The additional requirements on the base layer place new constraints on the design of the cell. In particular, the base layer thickness and doping must be adjusted to allow significant modulation by the floating collector. This must be accomplished without sacrificing the operation of the bipolar access transistor, both in the forward and inverse modes. Work is proceeding on these design issues, but no insurmountable problems are foreseen. The design problem is made more tractable by the several degrees of freedom inherent in the structure. Adjustable parameters include the base doping and thickness, the logic voltages on the floating collector, and the bias voltage on the emitter during readout. In addition, the use of heterojunctions at the emitter-base and collector-base junctions would improve bipolar operation, further relaxing the design constraints. In addition to providing nondestructive readout for digital (binary) memories, the BiFET cell can also be used as an analog memory. This mode of operation opens the possibility for several new applications, one of which is in the field of artificial neural networks. This will be discussed in Section
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
71
D. Ultra-Long Storage Times: Quasi-Static and Nonvolatile DRAMs As pointed out in the introduction to this section, storage times in GaAs memories have increased dramatically in recent years. In simple GaAs bipolar DRAM cells, storage times in excess of 4 hr at room temperature are now routinely obtained. For many applications such as cache memory, in which paging occurs at predictable intervals, storage times of this magnitude allow the cell to be operated essentially as a static memory, without the need for refreshing of any kind. Moreover, the bipolar DRAM has the unique feature that storage is accomplished with no external bias applied to the cell. This is because the bipolar access transistor is a current-controlled device and is off when the base current is 0. Thus, bipolar DRAMs can be used in applications where data is to be retained during temporary power losses, provided such interruptions are short compared to the normal storage time of the memory. In this mode, the memory is considered “nonvolatile,” at least for limited periods of time. What if the storage time could be extended to the order of days, months, or even years? In a moment, we will show experimental evidence that such storage times may indeed be possible. But first, we should point out the potential advantages that this type of nonvolatile memory would have in comparison to nonvolatile memories available today. In present-day nonvolatile memories in silicon, a charge is injected onto a floating gate by tunneling through a thin tunnel oxide or by avalanche injection over the potential barrier of a thicker oxide (Kahng and Sze, 1967; Frohman-Bentchkowsky, 1974; Nishi and Iizuka, 1981). Storage times are measured in years, but writing operation is quite slow, typically on the order of 100psec per bit, and writing requires pulse voltages much larger than the normal 5 V supply voltage. Therefore, operation is effectively restricted to read-only memory (ROM) applications, and the devices are variously referred to as programmable ROMs (PROMS), electrically alterable ROMs (EA-XOMs or E-PROMS), or “flash” E-PROMS. The bipolar DRAM, on the other hand, achieves nonvolatile storage from its inherently long charge recovery time and does not depend on tunneling or avalanche injection across an oxide barrier. As a result, electrical writing is expected to be very fast, typically on the order of nanoseconds or less per bit, and operation as a high-speed read-write memory is not compromised. Silicon E-PROMS also suffer from a wearout mechanism that limits the number of times the memory can be reprogrammed to around 106-107times. Although this is not a limitation when the memory is used as a ROM, it does preclude use of these devices in RAM applications, where lo6 writing operations can occur in a few seconds of real time. The bipolar DRAM suffers from no comparable wearout mechanism.
72
JAMES A. COOPER, JR
As stated earlier, storage times on the order of months to years may be possible using the basic bipolar DRAM structure of Section V, provided a suitable semiconductor material is utilized. One particularly attractive material for such applications is silicon carbide (Sic) (Davis et al., 1988). This is because S i c has a band-gap almost three times as large as silicon and twice as large as GaAs. S i c occurs in both cubic and hexagonal forms. Cubic (“beta”) S i c has a lattice constant of 4.359A and a band-gap of 2.3eV. Hexagonal (“alpha”) S i c occurs in a variety of polytypes, each having a hexagonal basal plane but with different stacking sequences in the vertical direction. The most useful polytype is “6H,” with a band-gap of 2.9 eV. Both beta and 6H material have been used to fabricate electronic devices (Kong et al., 1987; Palmour et al., 1991), including MESFETs, JFETs, MOSFETs, and bipolar transistors. 6H-Sic wafers are available commercially from Cree Research, Inc., Durham, NC, and are now grown at a number of research laboratories in the United States, Europe, Japan, and the states constituting the former Soviet Union. S i c is physically robust, being one of the hardest and most chemically inert materials known to humankind. It is thermally stable, and electronic devices retain good electrical characteristics to very high temperatures. MOSFET operation has been demonstrated (Palmour, Kong, and Davis, 1987) to 65OoC, and packaged devices operate reliably for extended periods at temperatures up to 35OoC, limited by the thermal stability of the package. Therefore, a major application for S i c is high-temperature and high-power electronic devices. For further information on S i c crystal growth, fabrication techniques, and electrical properties, the reader is referred to the literature. In order to evaluate S i c for use in long-term dynamic memory applications, we have investigated the storage time of npn storage capacitors in 6H-Sic (Gardner et al., 1991). A cross section of the experimental device is shown in Fig. 61. All layers are doped in situ during epitaxy. Circular npn diodes are isolated by reactive ion etching and passivated with S O z formed by wet thermal oxidation. Ohmic contacts are annealed Ni. Capacitance recovery times are measured on various devices using the techniques described in Section 11. Referring to equations (33) and (34) of Section 11, we are reminded that the recovery time of a pn junction storage capacitor is expected to increase exponentially with band-gap energy as exp (EG/2kT), assuming that generation lifetimes in the materials are comparable. Since the band-gap energy of 6H-Sic is 1.48eV greater than the band-gap of GaAs, one expects the storage time at room temperature to be larger by a factor of exp(28.6) or approximately 12 orders of magnitude. Alternatively, we expect to observe the same storage time as GaAs at an absolute temperature that is higher by the ratio of the band-gaps, or approximately a factor of 2. This means that S i c devices should exhibit
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
73
Ni Ohmic Contact
30 nm undoped
-
N 6H Sic Substrate (Siface)
FIGURE 61. Prototype n-i-p-i-nstorage capacitor fabricated in 6H-Sic for storage time measurements. The etched surfaces are passivated by thermal SiO, grown by wet oxidation.
storage times at 600 K (3OOOC) that are comparable to those of GaAs at room temperature. Figure 62 shows storage time versus temperature for several Sic diodes (Cooper et al., 1991). As predicted, storage times on the order of 10 min are observed at 300°C. All diodes have an activation energy around 1.48 eV, close to half the band-gap. If we extrapolate these data to room temperature, we would predict a storage time of about loi3sec, or about 300,000 years! Of course, such an extrapolation is not realistic - other mechanisms having lower activation
los
b
'
.
,
,
,
,
,
,
1
,
.
,
,
I
"
' 3
I I I
lo4
I
/-
6H-!SIC
I
10'
loo
; '
'
'
FIGURE62. Recovery time versus temperature for storage capacitors fabricated in GaAs and in 6H-Sic. The activation energy of the Sic capacitors is about 1.48 eV, close to half the band-gap. Data on the S i c samples had to be taken above 300°C because at lower temperatures the storage times are too long to be conveniently measured.
74
JAMES A. COOPER, JR.
energies (or not thermally activated at all) will become dominant before room temperature is reached. The point, however, is that thermal generation is not likely to limit storage times in these devices. How long will room temperature storage times be? That question is difficult to answer with any confidence, since it will require actual room temperature measurements over extended periods of time. Such measurements have not yet been attempted. To summarize, we have shown the possibility of one-transistor memories having exceedingly long storage times at room temperature. For practical purposes, such memories can be regarded as static. In addition, since the bipolar cell requires no external bias to retain data, these memories are also nonvolatile. Because they can be written in nanoseconds, these devices can be used in high-speed RAM applications. E. Nonconventional Applications
TOconclude this chapter, we wish to suggest some nonconventional applications for these compact storage devices. Dynamic memory is usually associated with digital electronics. However, the applications we will describe in this section use the fact that the dynamic memory is inherently an analog device. The basic elements of the dynamic memory cell, storage capacitors and access transistors, are utilized in a number of analog applications such as switched capacitor filters. In addition, the basic capacitor structure, which has been optimized for exceedingly low dark current, is ideal for use in low-light-level imagers. Perhaps the most novel application, one that has arisen only in the last few years, is in the emerging field of electronic neural networks. We will describe this particular application next. Artificial neural networks are electronic circuits that embody many of the features of biological neural systems (Hopfield, 1988; Lippmann, 1987). In particular, they are highly interconnected networks composed of a large number of very simple identical elements. The basic elements of neural networks are neurons and synapses. In electronic neural networks, neurons are simple amplifiers having saturating (or sigmoidlike) input-output characteristics. The input to each neuron is a summing node connected to a large number of surrounding neurons by resistive connections called synapses. An example of a simple electronic neural network is shown in Fig. 63. Here the network consists of a row of amplifiers (neurons) whose outputs are brought around to a matrix of resistive connections (synapses). The synapse matrix forms the interconnections between neurons. One simple way to visualize the operation of a neural network is to define an energy function for the network. This energy function depends on the output voltages of the neurons in the array. If there are n neurons, the energy function is defined on an n-dimensional space. The exact dependence of the
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
I
75
I
FIGURE63. Illustration of a simple Hopfield neural network. The network consists of a row of amplifiers (neurons) whose outputs are brought around to a matrix of resistive connections (synapses). The synapse matrix forms the interconnections between neurons. Programming is accomplished by specifying the strengths of the resistive connections in the synapse matrix.
network energy on the individual neuron voltages is determined by the resistive weights of the synapse elements in the interconnection matrix. Thus, the information content of the network, in effect its programming, is contained in the resistive weights of the synapse connections. One use of such a neural network is in pattern recognition. Suppose that an input pattern (which could be an optical image, a fragment of speech, a radar signature, etc.) is to be classified based on a number of predetermined “example” patterns, To be specific, let us assume that the network is to identify a two-dimensional image as belonging to one of 26 possible classes: the letters of the alphabet. The weights in the synapse matrix of the neural network are selected so that the energy function of the network exhibits local minima. Each local minimum corresponds to one of the “example” patterns that are acceptable answers to the identification problem. The inputs to the neurons are then preset to potentials that correspond to the input image to be identified. This, in effect, places the network in an initial condition at some point in the n-dimensional parameter space corresponding to the input pattern. The network is then allowed to settle into the local energy minimum that is “nearest” the starting point. This minimum corresponds to one of the 26 possible “answers” - the 26 letters of the alphabet. In this way, the network performs a natural minimization function, determining which “example” pattern is the minimum distance from the input pattern.
76
JAMES A. COOPER, JR
The question of how to specify the weights in the synapse matrix so that the local minima in the energy function are efficiently placed is a subject of current research. However, for our purposes it suffices to understand that the network is “programmed” by specifying these synapse weights. To perform a meaningful pattern recognition task, the electronic neural network must be of sufficient size. In particular, the number of local minima in the energy function grows approximately as the square root of the number of neurons. Unfortunately, the number of synapse connections grows as the square of the number of neurons. It is easy to see that simply identifying the letters of the alphabet would require perhaps a few thousand neurons and a few million synapses. How does all this relate to dynamic memories? In Section C , we described a combination bipolar-field-effect (BiFET) cell capable of nondestructive readout of stored information. We now suggest that this BiFET cell can be used to implement a very compact synapse connection for electronic neural networks. As discussed earlier, the potential on the floating collector in this device serves to back-gate the channel of the lateral JFET formed by the base layer. Thus, the conductance of this lateral JFET can be programmed to an analog value by storing the proper voltage on the floating collector. The JFET is then used to provide the desired resistive connection required of the synapse element. An illustration of the use of the BiFET cell in a synapse array is shown in Fig. 64. We assume that the weighting information is stored off-line in a conventional semiconductor memory. This weighting information is then loaded into the BiFET array using the data lines shown. Once initialized, the BiFET array is ready to provide weighted synapse connections for the neural network. Since it is important that the analog voltage in each cell does not change appreciably, the array will need to be refreshed in a time that is much shorter than the l/e storage times previously quoted for our DRAM cells. However, considering the long room-temperature storage times of GaAs bipolar cells (not to mention the storage times of S ic cells), such periodic refreshing should not be a significant problem, particularly since the normal settling time of the neural network is on the order of a few microseconds. The use of dynamic storage for the synapse weights allows the network to be reprogrammed on-the-fly to solve different classification problems, in effect becoming a general-purpose neural computer. In conclusion, we have pointed out a number of nonconventional applications for dynamic storage devices. The ultra-long storage times now being realized make possible a number of novel applications, as diverse as nonvolatile digital memory and high-density neural networks. The evolution of nonsilicon dynamic memory devices has been rapid, and a number of exciting directions are opening for future development.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
-
I,
11
l2
77
12
FIGURE 64. Realization of a Hopfield network using the BiFET storage cell of Fig. 60 as a programmable analog synapse element. Synapse weights are entered using the horizontal “data” lines.
REFERENCES Auret, F. D., Myburg, G., Bredell, L. J., Barnard, W. O., and Kunert, H. W. (1991). 16th Int’l Conf. on Defects in Semiconductors, Bethlehem, PA. Batey, J., and Wright, S. L. (1986). J. Appl. Phys. 59, 200. Bedair, S. M., Tischler, M. A., Katsuyama, T., and El-Masry, N. A. (1985). Appl. Phys. Lett. 47, 51.
Beltram, F., Capasso, F., Walker, J. F., and Malik, R. J. (1988). Appl. Phys. Lett. 53, 376. Capasso, F., Beltram, F., Malik, R. J., and Walker, J. F. (1988). IEEE Electron Device Lett. EDL-9, 377. Carpenter, M. S., Melloch, M. R., and Dungan, T. E. (1988). Appl. Phys. Lett. 53, 66. Chen, C. L., Goodhue, W. D., and Mahoney, L. J. (1991). Electronics Lett. 27, 1330. Conger, J., Peczalski, A., and Shur, M. S. (1988). IEEE Electron Device Lett. EDG9, 128. Cooper, J. A,, Jr. (1989). Unpublished. Cooper, J. A., Jr., Qian, Q.-D., and Melloch, M. R. (1986). IEEE Elecrron Device Lett. EDG7, 374. Cooper, J. A., Jr., Palmour, J. W., Gardner, C. T., Melloch, M. R., and Carter, C. H., Jr. (1991). 1991 Int’l. Semiconductor Device Res. Symp., Charlottesville, VA.
78
JAMES A. COOPER, JR
Davis, R. F., Sitar, Z., Williams, B. E., Kong, H. S., Kim, H. J., Palmour, J. W., Edmond, J. A,, Ryu, J., Glass, J. T., and Carter, C. H., Jr. (1988). Mat’l. Sci. and Engr. B1, 77. Dungan, T. E. (1989). Ph.D. dissertation, Purdue University, West Lafayette, IN (available as Tech. Rept. TR-EE 89-47). Dungan, T. E., Neudeck, P. G., Melloch, M. R., and Cooper, J. A,. Jr. (1990). IEEE Trans. Electron Devices ED-37, 1599. Fiedler, A., Chun, J., and Kang, D. (1988). IEEE GaAs IC Symposium Tech. Dig. 67. Frenkel, J. (1938). Phys. Rev. 54, 647. Frohman-Bentchkowsky, D. (1974). Solid-state Electron. 17, 517. Gardner, C. T., Cooper, J. A,, Jr., Melloch, M. R., Palmour, J. W., and Carter, C. H., Jr. (1991). 4th Int’l Conf. on Amorphous and Crystalline Silicon Carbide and Other IV-IV Materials, Santa Clara, CA. Hetherington, D. L., Klem, J. F., and Weaver, H. T. (1991). IEEE ELectron Device Lett. EDL-13, 146.
Hopfield, J. J. (1988). IEEE Circuits and Devices Magazine 4, 3 . Kahng, D., and Sze, S . M. (1967). Bell Syst. Tech. J . 46, 1283. Kleine, J. S., Melloch, M. R., and Cooper, J. A,, Jr. (1989a). Appl. Phys. Lett. 55, 1656. Kleine, J. S . , Qian, Q.-D., Cooper, J. A,, Jr., and Melloch, M. R. (1989b). IEEE Trans. Electron. Devices ED-36, 289. Kleine, J. S., Cooper, J. A,, Jr., and Melloch, M. R. (1991). Appl. Phys. L e u . 61, 834. Kleinhenz, R., Mooney, P. M., Schneider, C. P., and Paz, 0. (1984). In “13th Int’l. Conf. on Defects in Semiconductors” (L. C. Kimmerling and J. Parsey, eds.), p. 627, Coronado, CA. Kong, H. S., Palmour, J. W., Glass, J. T., and Davis, R. F. (1987). Appl. Phys. Lett. 51, 442. Lippmann, R. J. (1987). IEEE ASSP Magazine, 4. Lott, J. A,, Dawson, L. R., Weaver, H. T., Zippenan, T. E., and Caldwell, R. B. (1989a). Appl. Phys. Lett. 55, 1110. Lott, J. A,, Klem, J. F., and Weaver, H. T. (1989b). Appl. Phys. Lett. 55, 1226. Lott, J. A,, Klem, J. F., Weaver, H. T., Tigges, C. P., and Radoslovich-Cibicki, V. (1990). Electronics Lett. 26, 972. Lu, N. C. C. (1989). IEEE Circuits and Devices Magazine 5, 21. Makino, H., Matsue, S., Noda, M., Tanino, N., Takano, S . , Nishitani, K., and Kayano, S . (1988). IEEE GaAs IC Symposium Tech. Digest, 71. Makino, H., Matsue, S . , Noda, M., Tanino, N., Takano, S., Nishitani, K., and Kayano, S. (1990). IEEE Journal of Solid-state Circuits 25, 1232. Matsue, S., Makino, H., Noda, M., Tanino, N., Takano, S . , Nishitani, K., Kayano, S. (1989). IEEE GaAs IC Symp. Tech. Dig. Nakano, H., Noda, M., Sakai, M., Matsue, S., Oku, T., Sumitani, K., Makino, H., Takano, H., and Nishitani, K. (1990). IEEE GaAs IC Symp. Tech. Dig. Nel, M., and Auret, F. D. (1988). J. Appl. Phys. 64, 2422. Neudeck, P. G . (1991). Ph.D. dissertation, Purdue University, West Lafayette, IN (available as Tech. Rept. TR-EE 91-21). Neudeck, P. G., Dungan, T. E., Melloch, M. R., and Cooper, J. A,, Jr. (1989). IEEE Electron Device Lett. EDL-10, 477. Neudeck, P. G., Carpenter, M. S., Cooper, J. A,, Jr., and Melloch, M. R. (1991a). IEEE Electron Device Lett. EDL-10, 553. Neudeck, P. G., Kleine, J. S . , Sheppard, S. T., McDermott, B. T., Bedair, S . M., Cooper. J. A,, Jr., and Melloch, M. R. (1991b). Appl. Phys. Lett. 58, 83. Nishi, Y., and Iizuka, H. (1981). In “Applied Solid State Science, Suppl. 2A.,” (D. Kahng, ed.), Academic Press, New York. Palmour, J. W., Kong, H. S., and Davis, R. F. (1987). Appl. Phys. Lett. 51, 2028.
RECENT ADVANCES IN GaAs DYNAMIC MEMORIES
79
Palrnour, J. W., Kong, H. S., Waltz, D. G., Edrnond, J. A., and Carter, C. H., Jr. (1991). In “Trans. of First Int’l. High Temperature Electronics Conf.” (D. B. King and F. V. Thome, eds.), U.S. Government Printing Office, Washington, DC. Priddy, K. L., Kitchen, D. R., Grzyb, J. A,, Litton, C. W., Henderson, T. S., Peng, C.-K., Kopp, W. F., and Morkoc, H. (1987). IEEE Trans. Electron Devices ED-34, 175. Qian, Q.-D., Melloch, M. R., and Cooper, J. A,, Jr. (1986). IEEE Electron Device Lett. EDL-7, 607. Qian, Q.-D.. Melloch, M. R., and Cooper, J. A,, Jr. (1989). J . Appl. Phys. 65,3118. Quinn, P. M., Early, J. M., Sander, W. B., and Longo, T. A. (1978). IEEE Int’l. Solid-St. Circuits Conf. Rooks, M. J., Eugster, C. C., del Alarno, J. A,, Snider, G. L., and Hu, E. L. (1991). Int’l. Symp. on Electron, Ion, and Photon Beams, Seattle, WA. Sander, W. B., and Early, J. M. (1976). IEEE Int’l. Solid-St. Circuits Conf. Schroder, D. K. (1987). “Advanced MOS Devices.” Addison-Wesley, Reading, MA. Sheppard, S. T. (1991). MS dissertation, Purdue University, West Lafayette, IN. Shockley, W., and Read, W. T., Jr. (1952). Phys. Rev. 87, 835. Stellwag, T. B., Cooper, J. A., Jr., and Melloch, M. R. (1991a). IEEE Device Research Con$, Boulder, CO. Stellwag, T. B., Melloch, M. R., and Cooper, J. A., Jr. (1991b). Unpublished. Stellwag, T. B., Melloch, M. R., Cooper, J. A,, Jr., Sheppard, S. T., and Nolte, D. D. (1992a). J . Appl. Phys. 71, 4509. Stellwag, T. B., Cooper, J. A,, Jr., and Melloch, M. R. (1992b). IEEE Electron Device Lett. EDL-13, 129. Solomon, P. M., Wright, S. L., and Lanza, C. (1986). Superlattices and Microstructures 2, 521. Sunarni, H. (1985). IEEE Int’l. Electron Dev. Mtg. Tech. Dig., 694. Sunouchi, K., Horiguchi, F., Nitayarna, A,, Hieda, K., Takato, H., Okabe, N., Yarnada, T., Ozaki, T., Hashimoto, K., Takedai, S., Yagishita, A,, Kurnagae, A,, Takahashi, Y., and Masuoka, F. (1990). IEEE Int’l. Electron Dev. Mtg. Tech. Dig., 647. Terrell, W. C., Ho, C. L., and Hinds, R. (1988). IEEE GaAs IC Symp. Tech. Dig., 79. Thurmond, C. D. (1975). J . Electrochem. SOC.122, 1133. Vogelsang, C. H., Castro, J. A., Notthoff, J. K., Troeger, G. L., Stephens, J. S., and Krein, R. B. (1988). IEEE GaAs IC Symp. Tech. Dig., 75. Whitmire, D. A., Garcia, V., and Evans, S. (1988). IEEE Int’l. Solid-St. Circuits Conf. Yamasaki, K., Kato, N., and Hirayama, M. (1985). IEEE Trans. Electron Devices ED-32,2420.
This Page Intentionally Left Blank
ADVANCES IN ELECTRONICS A N D ELECTRON PHYSICS. VOL. 86
Expert Systems for Image Processing. Analysis. and Recognition: Declarative Knowledge Representation for Computer Vision TAKASHI MATSUYAMA Department o$ Information Technology. Faculty of Engineering. Okayama University. Okayama. Japan
I . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A . Declarative Knowledge Representation . . . . . . . . . . . . . . . . . B. Knowledge Representation in Computer Vision . . . . . . . . . . . . . C. Organization of the Chapter . . . . . . . . . . . . . . . . . . . . . . I1. Expert Systems for Image Processing and Analysis (ESIPAs) . . . . . . . . . A . Problems in Image Processing and Analysis . . . . . . . . . . . . . . . B. Characteristics of ESIPAs . . . . . . . . . . . . . . . . . . . . . . . C . General Architecture of ESIPAs . . . . . . . . . . . . . . . . . . . . D . Consultation System for Image Processing . . . . . . . . . . . . . . . . E . Knowledge-Based Program Composition System . . . . . . . . . . . . . F. Rule-Based Design System for Bottom-up Image Segmentation Algorithms . G . Goal-Directed Top-down Image Segmentation System. . . . . . . . . . . I11. Representing Knowledge about Image Analysis Strategies . . . . . . . . . . A . Heterogeneous Combination of Image Processing Operators . . . . . . . . B. Cooperative Integration of Multiple Stereo Vision Algorithms . . . . . . . IV. Representing Spatial Relations and Spatial Reasoning for Image Understanding A . Knowledge Representation in Logic Based on Topological Relations . . . . B. Structural Representation of Geometric Relations . . . . . . . . . . . . C . Algebraic Representation of Geometric Information and Geometric Theorem Proving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D . Reasoning Based on PART-OF Relations . . . . . . . . . . . . . . . . V. Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81 81 84 86 87 87 89 93 95 98 111 114 124 125 139 143 143 146 149 154 163 168
I . INTRODUCTION A . Declarative Knowledge Representation
Expert systems are computer software systems capable of intelligent problem solving. which usually requires sophisticated knowledge of human experts. In the 1980s expert systems in various task domains were developed and their practical utilities have been widely recognized: medical diagnosis. chemical 81
Copyright 0 1993 by Academic Press. Inc. All rights of reproduction in any form reserved. ISBN 0-12-0 14728-9
82
TAKASHI MATSUYAMA
substance analysis, geological investigation, computer system configuration, and so on. Generally speaking, any meaningful computer software or program can be considered as an embodiment of human knowledge; it is designed and implemented using knowledge in a specific task domain. In other words, without knowledge no useful software or program can be realized. For example, the following function in C programming language is a realization of the mathematical knowledge about absolute values of integer numbers:
absolute (n) int n;
c if (n)=o) return (n); else return (-n);
1 The most distinguishing characteristic of expert systems is the use of declarative knowledge. That is, knowledge in expert systems is explicitly represented as symbolic data, independent of the control of problem solving, while that in ordinary programs is implicitly encoded in and spread over various types of program statements. The knowledge represented by procedures like the preceeding absolute function is called procedural knowledge. A FORTRAN or C program for the fast Fourier transform (FFT) is a typical example of procedural knowledge. Although the program embodies the knowledge about FFT (i.e., when executed, it transforms an input data correctly based on the knowledge), the knowledge is implicitly encoded in the sequence of primitive operations like assignment and IF-THEN-ELSE control statements. Thus it is almost impossible to identify (and separate) the knowledge itself in (from) the program code. On the other hand, formulae in the first-order predicate calculus like Vx[MAN(x) + MORTAL(x)] [For all x,M A N ( x ) implies MORTAL(x). MAN and MORTAL are predicates and x a variable.] and so-called production rules like I F (condition for activation) THEN (action) (If the condition is satisfied, execute the action.) are typical examples of declarative knowledge, where knowledge is explicitly described in terms of symbols in a predefined vocabularly. Note that declara-
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
83
tive knowledge does not include any control information about how and in which order it is used. Thus we can freely design the control structure of reasoning and problem solving independent of the knowledge. Moreover, flexible modification and augmentation of knowledge can be easily realized by symbol manipulations, since the embodiment of knowledge is just a collection of well-formed symbolic data. The clear separation of knowledge from control leads to the natural decomposition of an expert system into knowledge base and reasoning engine.' The knowledge base is a collection of symbolic data representing knowledge and the reasoning engine is a control program that conducts reasoning based on the knowledge base. Merits and demerits of the declarative knowledge representation can be summarized as follows: Merit 1 : High Modularity and Easy Modijication. The declarative knowledge representation enables highly modular description of knowledge; knowledge is represented by a set of mutually independent descriptions (e.g., rules and axioms). Thus knowledge can be added, deleted, and modified easily by editing related portions of symbolic data in the knowledge base, while even a small change in procedural knowledge can lead to extensive modification of an entire program. Merit 2: High Transportability and Knowledge Sharing. Once knowledge in a specific task domain is described declaratively, it can be used in or transported to other expert systems even if it is not originally intended to be used in such systems. In other words, declarative knowledge can be shared by different expert systems. Merit 3: High-Level Reasoning. New knowledge can be automatically generated by reasoning and learning mechanisms since the addition of knowledge can be easily realized by inserting new symbolic descriptions into the knowledge base. Moreover, meta knowledge about how to use knowledge in a task domain can also be described declaratively to realize flexible control of reasoning processes. Merit 4: Introspective Explanation. Since the reasoning engine can memorize which knowledge is used in a specific reasoning process, it can present to a user an introspective explanation of the executed reasoning process. Demerit 1 : Limited Descriptive Vocabulary. Knowledge used in expert systems is often called shallow knowledge; declarative knowledge used in them is described in terms of naive qualitative vocabularies. Such naive descriptions limit the level of reasoning and analysis. Demerit 2: Low Eficiency. Declarative knowledge should be interpreted to be
'
Although the term inference engine is more popular than reasoning engine, we reserve inference for that in the formal mathematical logic and use reasoning in a general context.
84
TAKASHI MATSUYAMA
used in a reasoning process, so that many complicated symbolic processings (e.g., symbolic pattern matching) are inevitable. This lowers execution speed considerably. In short, it is the essence of the declarative knowledge representation that knowledge itself is described as independent objective data to be processed. With the declarative knowledge representation, we can gain much flexibility and versatility despite loose efficiency. The problem described in Demerit 1 is a crucial point in developing an expert system in a specific task domain. That is, how well we can symbolically describe the knowledge in that task domain determines the performance and utility of the developed expert system. On the other hand, Demerit 2 can be resolved by compiling the knowledge base. That is, although during the development we should use the declarative knowledge representation for its modifiability, we can encode the knowledge into procedures for efficiency once the entire set of knowledge required for problem solving is fixed. B. Knowledge Representation in Computer Vision
In general computer vision’ refers to visual information processing by computer. It includes image processing, analysis, and recognition. Image processing denotes transformation of an input image to another. Filtering operations like smoothing and edge enhancement are its typical examples. On the other hand, image analysis refers to image segmentation to extract meaningful image features such as lines and regions.’ In image processing, analysis, and recognition and modern computer vision for three-dimensional object recognition, most of the knowledge has been described procedurally. Reasons for this are as follows: 1. Digital filtering is a fundamental scientific discipline of image processing, and photometry and geometry in the three-dimensional world provide major knowledge sources for three-dimensional computer vision. All these scientific disciplines have been established based on quantitative analysis of physical phenomena, where mathematical formulae such as differential equations are used as general representational schemes. Thus it is natural to use numerical computation procedures as the embodiment of such physical knowledge.
’
Computer vision sometimes refers specifically to three-dimensional information analysis and object recognition from two-dimensional images. When necessary, we will refer to it explicitly as three-dimensional computer vision or computer vision for three-dimensional object recognition. In this chapter we will sometimes use image processing in a general sense, including both filtering and feature extraction.
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
85
2. For human beings, the identification of various visual properties - i.e., brightness, color, size, and shape - is so natural and immediate that no conscious thought or logical reasoning is required for their characterization. Consequently, only limited descriptive vocabularies for such visual properties have been developed and few efforts for their declarative description have been made until quite recently. 3. In ordinary statistical pattern recognition, patterns and objects to be analyzed are represented by n-dimensional vectors. This also leads to the development of numerical computation procedures in realizing the knowledge about various recognition methods. 4. Since the size of image data is large and its processing should often be done quickly in practical applications, the speed of execution has been an important factor to design computer systems for image processing, analysis, and recognition. Thus the efficiency of the procedural knowledge representation has been preferred to the flexibility of the declarative knowledge representation. Several years ago, Rosenfeld (1986) proposed the term expert vision systems to denote computer vision systems using declarative knowledge and had open discussions with several computer vision researchers on possibilities and utilities of the declarative knowledge representation for computer vision. Unfortunately, the discussions were not developed extensively, nor did they produce any creative concrete ideas at that time. Since then, however, many research efforts have been put to prove the feasibilities of expert vision systems. Especially in Japan, we organized a special interest group on expert vision and have developed various types of expert systems for image processing and analysis. On the other hand, several formal approaches to the declarative knowledge representation for computer vision were proposed to clarify the knowledge and reasoning mechanism required for image recognition and understanding. Moreover, a major focus of recent multimedia communication and database research is on the integration of textual, verbal, and visual information; and many methods for declarative characterization of visual information have been proposed for multimedia information processing. From an engineering point of view, since the speed and memory space of computers increased dramatically in the past few years and this increase is expected to continue, system designers for practical applications gradually shifted their attention from efficiency to the flexibility and versatility of implemented systems. Therefore we believe that by exploring the declarative knowledge representation for computer vision new scientific findings and technological
86
TAKASHI MATSUYAMA
successes will be obtained and many new-featured vision systems can be developed.
C. Organization of the Chapter In this chapter we will describe various approaches to the declarative representation of visual information and knowledge for image processing, analysis, and recognition. We will not survey or discuss that for multimedia information processing. First Section I1 gives an extensive survey of expert systems for image processing and analysis. They use the knowledge about image processing techniques to compose complex image analysis processes from primitive image processing operators. We classify the expert systems into the following four categories and discuss their objectives, knowledge representation, and reasoning methods: 1. Consultation system for image processing, 2 . Knowledge-based program composition system, 3. Rule-based design system for bottom-up image segmentation algorithms, 4. Goal-directed top-down image segmentation system. In order to realize flexible and reliable image analysis, ordinary sequential reasoning mechanisms such as backward-forward chaining in expert systems and linear resolution in PROLOG are not enough. In Section I11 we discuss the following sophisticated strategies (i.e., control mechanisms) for image analysis with practical examples: 1. Heterogeneous combinations of image processing operators. 2 . Cooperative integration of multiple stereo vision algorithms. The success of the declarative knowledge representation for computer vision rests wholy on how well we can symbolically describe various types of visual properties. In Section IV we first discuss the declarative representation of spatial relations for image recognition and understanding. During the discussion, we introduce two formal declarative knowledge representation methods for computer vision: 1. Knowledge representation in terms of the first-order predicate calculus, 2 . Algebraic knowledge representation and geometric theorem proving.
Then we describe expert vision systems for recognizing complex objects with internal structures; that is, reasoning based on PART-OF relations.
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
87
In Section V, we conclude the article by discussing future problems of the declarative knowledge representation for computer vision.4
FOR IMAGE PROCESSING AND ANALYSIS (ESIPAs) 11. EXPERTSYSTEMS
A . Problems in Image Processing and Analysis
A variety of image processing algorithms have been devised in the history of digital image processing. Although they do not work perfectly for complex natural images, their utilities have been proven in various application areas such as remote sensing, medical engineering, office and factory automation, and so on. In order to facilitate a wider use of digital image processing techniques, various software packages have been developed: FORTRAN subroutine libraries (Tamura e f al., 1983) and command libraries in image processing systems. As is well known, however, it is not so easy to make full use of such libraries; various forms of knowledge and know-how about image processing techniques are required to realize effective image analysis. In other words, the requirement for such knowledge limits utilities of the libraries and increases the cost of developing image processing systems for various applications. From a knowledge representation viewpoint, each subroutine or command in a library is a procedural embodiment of the knowledge about a primitive image processing operator, and the library is a simple collection of such procedural knowledge. Although the procedural knowledge representation for primitive image-processing operators is natural and effective, no systematic description about syntactic and semantic relations among subroutines and commands is supported in ordinary libraries. This makes it difficult for their users, especially those with little knowledge of and experience in image processing, to compose effective image analysis processes5 by selecting and combining primitive operators in the libraries. Note that even to read manuals of the libraries requires knowledge about image processing, for example, meanings of specialized terminology in image processing. Thus what we mean by knowledge and know-how about image processing techniques includes syntactic and semantic relations among subroutines and commands in image processing operator libraries. To investigate the knowledge about image processing techniques further, first we should examine popular problems encountered in designing image An earlier version of Sections I1 and 1II.A was published in Matsuyama (1989). By an image unalysisprocess we mean an executableprogram composed of various combinations of primitive operators. Types of combinations will be discussed in Section I11 in detail.
88
TAKASHI MATSUYAMA
analysis processes by using an image processing operator library. The following are typical problems in development image analysis processes: 1. Assessment of Image Quality. To assess the quality of an image is the first step in image analysis. Although one should design an image analysis process based on the assessment, how to measure and describe the image quality is a difficult problem. In the analysis of complex natural images, moreover, we encounter a more difficult problem; since the image quality often changes depending on its location in an image, we need to analyze the image and determine its structure to make the image quality assessment. This leads to a chicken-and-egg problem between image quality assessment and image structure analysis. When physical models of objects and imaging devices are available, we can assess the image quality based on such models. 2 . Selection of Appropriate Operators. There are many different operators (algorithms) for a specific image processing task. For edge detection, for example, several tens or more of operators have been developed. They are designed based on different image models and computation schemes, so that one has to select an appropriate operator considering the image quality, the purpose of image analysis, and characteristics of the operators. 3. Determination of Optimal Parameters. Many operators have adjustable parameters and their performance is heavily dependent on the values of the parameters (e.g., threshold in binarization). How to determine optimal parameter values is another difficult problem. 4. Combination of Primitive Operators. It is often necessary to combine many primitive operators to perform a meaningful task. For example, a popular way of extracting regions from an image is to apply smoothing edge detection +-edge linking sclosed boundary detection. To attain an effective combination of operators, the knowledge about syntactic and semantic relations between operators is required. 5. Trial-and-Error Experiments. Usually it is very hard to estimate a priori the performance of an operator for a given image, so that one has to repeat trial-and-error experiments by modifying parameters (and sometimes operators). To control such trial-and-error analysis, sophisticated knowledge about and rich experience in image processing are required. 6. Evaluation of Analysis Result. The process of evaluation is very important in realizing flexible image analysis. For example, the feedback analysis (Nagao, 1984) evaluates the difference between a processing result and the ideal output (i.e., the model of an object) and adjusts parameters for the analysis. How to evaluate the analysis result
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
89
and how to adjust parameters based on the evaluation is an important problem in designing image analysis processes with feedback loops. Vogt (1986) pointed out 10 major problems in developing image analysis programs, which are almost the same as the preceding, and analyzed their causes extensively. Among others he claimed that many intuitive, ad hoc, nonsystematic, and sometimes ambiguous factors are involved in the image analysis program development and that well-defined formal systems like mathematical morphology are required to facilitate the development. From the knowledge representation viewpoint discussed in Section I, his claim can be put as follows. When we develop a complex image analysis process, we usually write a main program that calls many primitive operators (subroutines) in a library. Such main program is really a procedural embodiment of the knowledge to solve the problems listed earlier. However, since this procedural knowledge is not systematically designed, no one, not even the programmer who wrote the main program, can understand clearly what knowledge is incorporated and how some portions of the program are related to others. Even worse, meaningless and incorrect knowledge can sneak into the program because there is no way of verifying the correctness of the procedural knowledge except by reading the program intensively. Due to these problems, it is very hard to improve an image analysis (main) program and modify it for other applications. This increases the time and cost of the image analysis program development. In other words, the procedural knowledge representation is efficient once correctly implemented, but its development and verification processes are far from efficient and usually require much time, cost, and moreover human expertise because no mechanical development and proof system is available. In short, while the procedural knowledge representation is useful for primitive image processing operators, its use in developing complex image analysis processes causes many problems. Therefore, we should study the declarative knowledge representation to examine its practical utilities in the development of complex image analysis processes.
B. Characteristics of ESIPAs Recently, several expert systems for image processing and analysis (ESIPAs, in short) were developed to facilitate the development of image analysis processes. They incorporated declarative knowledge representation and symbolic reasoning methods in artificial intelligence to solve the problems discussed in the previous section. The knowledge used by these systems is about how to effectively use and combine primitive image processing operators for image analysis. That is, the expertise stored in the systems is
90
TAKASHI MATSUYAMA
what we, computer vision researchers, have acquired and accumulated through the development of image analysis techniques. Before proceeding to technical discussions of ESIPAs we will discuss general characteristics of ESIPAs by comparing them to ordinary expert systems and image understanding systems. Expert systems have been developed for various tasks: signal interpretation, medical diagnosis, circuit design and trouble shooting, plant control, and so on (Hayes-Roth, Waterman, and Lenat, 1983). In general, the task of ESIPAs is to compose effective image analysis processes based on primitive image processing operators. In this sense, ESIPAs can be considered as expert design systems. The most successful system of this type would be R1 /XCON (McDermott, 1980b), which configures computer systems suitable for customer’s requirements by combining available functional components. The critical differences between ESIPAs and such expert design systems are 1. Although we can symbolically describe characteristics and behaviors of electronic circuits and computer hardware in terms of logical and mathematical expressions, it is very hard to describe the visual information included in an image and specify characteristics of image processing operators. 2. Since ESIPAs are given the input information in the form of raw image data (signal data), they have to analyze it to extract meaningful information and verify the effectiveness of composed image analysis processes.
Difference 1 implies that a major objective of developing ESIPAs is to investigate methods of formulating and describing the visual information in a declarative way: what types of image features we can extract from images, what properties they have, and how they are related to each other. Difference 2 means that ESIPA is not only an expert design system for symbolic reasoning but also an image analysis system for signal processing. Therefore, ESIPAs should have capabilities of both qualitative symbolic reasoning and quantitative signal processing. The integration of both qualitative (symbolic) and quantitative (numeric) information processing is also an important problem in image understanding and multimedia information processing. A primary objective of image understanding systems (IUSs in short) is to construct the symbolic description of the scene depicted in an image, while image processing transforms an image to another and pattern recognition classifies and labels objects represented by feature vectors. IUSs analyze an image(s) to interpret the scene in terms of object models given to IUSs as the knowledge about the world. Here interpretation refers to the correspondence
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
91
(i.e., mapping) between the description of the scene and the structure of the image. It associates objects in the scene (e.g., houses, roads) with image features in the image (e.g., points, lines, regions). Once the description of the scene is constructed, computer systems can answer various queries about the scene (e.g., how many houses exist in the scene?), perform physical operations by controlling robot manipulators (e.g., pick up and move physical objects), and if needed, generate explanations of the scene in natural languages. It is in this sense that we can say IUSs understand the scene. IUSs require diverse sources of knowledge to interpret visual scenes. In general, the knowledge they use can be classified into the following three types: 1. Scene Domain Knowledge. This type of knowledge includes intrinsic properties of and mutual relations between objects in the world. It is described in terms of the terminology defined in the scene: names of scene objects and their constituent parts, geometric coordinate systems to specify locations and spatial relations, physical scale systems to measure various size properties (e.g., length in meters) and so on. 2. Image Domain Knowledge. This type of knowledge is used to extract image features from an image and to group them to construct the structural description of the image. It is described in terms of the terminology defined in the image domain. This terminology must not be confused with that for describing the scene. For example, a word adjacent in the scene domain knowledge must be clearly discriminated from that in the image domain knowledge; adjacent image features need not correspond to adjacent objects in the scene. 3. Knowledge About the Mapping Between the Scene and the Image. This type of knowledge is used to transform image features to scene features and vice versa. It defines translation rules between the two terminologies used to describe the scene and the image domain knowledge. The knowledge about photogeometry is a typical knowledge source for the translation rules: viewing angle and focal length of a camera, color spectral properties, resolution, and so on. Although IUSs often use the declarative knowledge representation as ESIPAs, there are several differences between these two systems: Objective: A major purpose of ESIPAs is to realize effective image analysis processes by combining primitive image processing operators in a program library, while that of IUSs is to interpret a scene. In other words, ESIPAs are developed to make full use of available image processing techniques, while IUSs to realize new versatile visual recognition capability. Knowledge Sources: The knowledge used by ESIPAs is about how to use image processing techniques as well as the image domain knowledge. That
92
TAKASHI MATSUYAMA
is, no knowledge about the scene is used in ESIPAs, while IUSs require all three types of knowledge listed previously. Goal Specification: “Find roads” is a typical goal given to IUSs. Since goals for IUSs are described in terms of the scene domain terminology, IUSs require models of objects in the scene and the knowledge about the mapping in order to establish correspondence between the object models and image features extracted from the image. On the other hand, “find rectangles” is a typical goal given to ESIPAs. Since there are many possible methods to extract rectangles from an image, ESIPAs require the knowledge about primitive image processing operators in order to select promising ones and know-how about image processing techniques so as to combine them effectively. As will be described in detail in the following subsections, we can develop ESIPAs for various different tasks. Among them, one view of ESIPAs is to consider them as image segmentation modules in IUSs. Most of IUSs so far developed emphasized the importance of the knowledge of types 1 (scene domain knowledge) and 3 (knowledge for mapping), and many reasoning and computational methods have been developed based on such knowledge (Ballard and Brown, 1982; Binford, 1982; Brooks, 1981). However, we also need a lot of knowledge to analyze image data. The knowledge of type 2 (i.e., image domain knowledge) has been usually encoded in programs, so that it is very hard to see what knowledge is used for the image analysis in IUSs. Moreover, fixed processes of image analysis (i.e., image analysis procedures) reduce the flexibility of image segmentation capability of IUSs. For example, the poor capability of the ribbon detection (i.e., image segmentation) in the ACRONYM image understanding system (Brooks, 1981) limits its overall performance in object recognition. Selfridge (1 982) incorporated the knowledge about image processing techniques to realize the adaptive operation and parameter selection in his aerial image understanding system. The appropriate image processing operator and its optimal parameters were automatically selected through several iterations of trial-and-error image segmentation. This allowed flexible image segmentation and increased the reliability. Although his idea is very similar to ESIPAs, the knowledge for the operator and parameter selection in his system was still represented procedurally, and consequently, its reasoning capability was limited. In ESIPAs we describe the image domain knowledge and the know-how about image processing techniques explicitly (i.e., declaratively) and make it clear what knowledge is important and how we can use it effectively. Replacing a group of image analysis programs in IUSs by ESIPAs, we can
93
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
-
.
Library of Image
Request I Goal
Processing Operators
e r
Database of Characteristics of
n
imagedata specification
I
Image data
Analysis Result Reasoning Engine
composedprocess
a
knowledge about
C
Image Processing Techniques Knowledge about Knowledge about Image Processing Standard operators Image Analysis Processes
Selector
e -
increase the flexibility of image analysis in IUSs. Especially, the reliability of top-down image segmentation6can be greatly improved by incorporating an ESIPA as an image analysis module; since the model of a target image feature to be extracted and its approximate location are given in the top-down image segmentation, the ESIPA can accurately reason about the most reliable image segmentation tehnique (i.e., operators and parameters) using such information. C . General Architecture of ESIPAs
Figure 1 illustrates the general architecture of ESIPAs. It consists of the following modules: User Interface: A user of ESIPA interacts with the system through this
module. Its basic functions are to get a user’s request or analysis goal and image data to be analyzed and to return the analysis or reasoning result. Besides these primary functions, it supports various man-machine interface facilities such as displaying intermediate analysis results and reasoning histories graphically and sometimes asking the user for the evaluation of analysis results. Library of Image Processing Operators: This library is a major knowledge source of ESIPAs and contains a collection of procedures for primitive image processing operators, which can be called by the analysis executor. Note that the knowledge in this library is represented procedurally. Knowledge About Image Processing Techniques: This module is another major Later in this section we will discuss bottom-up and top-down image segmentation and describe ESIPAs for these two types of image segmentation.
94
TAKASHI MATSUYAMA
knowledge source of ESIPAs and includes various types of declarative knowledge about image processing: knowledge about standard image analysis processes, declarative characterization of individual image processing operators, rules for parameter selection, and so on. Database of Characteristics of Image Data: While the preceding two knowledge sources are usually built-in static information, this database stores all input and intermediate image data and their characteristics. They are dynamically created during the analysis and reasoning process. Analysis Executor: This module takes the full responsibility of executing image processing operators in the library and image analysis processes composed by the reasoning engine. All analysis results by this module are stored in the database for later use by the reasoning engine. Reasoning Engine: This is the central reasoning module in ESIPAs. It uses the knowledge about image processing techniques and characteristics of image data to reason about analysis plan generation, operator and parameter selection, and so on. Usually, reasoning in ESIPAs is done at two levels: 1. Analysis Plan Generation. First, ESIPAs reason about an appropriate
global plan to guide the analysis of a given image. The reasoning engine uses characteristics of the image and the knowledge about standard image analysis processes to generate the plan. The generated analysis plan can be considered as an abstract analysis process. 2 . Operator Selection and Parameter Adjustment. The reasoning at this level instantiates the generated analysis plan into an executable image analysis process: specific operators are selected from the library and values for their parameters are determined. These selections are done through the trial-and-error analysis of the input image: first ESIPAs perform image analysis by applying a promising operator and then evaluate the result to replace the operator or adjust parameter values. Here we classify ESIPAs into the following four categories: 1. Consultation system for image processing to improve user interface of image processing systems, 2. Knowledge-based program composition system to automatically generate complex image analysis programs, 3. Rule-based design system for image segmentation algorithms to realize flexible bottom-up image segmentation, 4. Goal-directed top-down image segmentation system for detecting specified image features. In the following subsections, we present an overview of these four types of
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
95
ESIPAs and discuss their objectives, knowledge representation, and reasoning methods.
D . Consultation System for Image Processing
A user of an interactive image processing system is usually required to select a command from a command library and specify appropriate parameters for the command. Although several HELP facilities are available, one has to refer to a manual to see the detailed usage of commands and the meanings of their parameters. In other words, syntax and semantics of commands are described only verbally in the manual, which forces users to read and understand documents written in specialized terminologies in image processing. Moreover, the information about how to select an appropriate command from a group of commands with similar functions and how to combine different commands to realize a meaningful image analysis process is rarely described in the manual. These problems implicitly prevent inexperienced users from using the system and limit its utility. Expert consultation systems for image processing (Sueda and Hoshi, 1986; Toriu, Iwase, and Yoshida, 1987) use such manual information as their knowledge source and help a user to select an appropriate command and parameters and to combine primitive commands to realize meaningful image analysis processes. Since the command and parameter selection is done under the system guidance, the man-machine interface of the systems can be greatly improved. This facility is useful especially for those with little experience in image processing. In Sueda and Hoshi (1986) a prototype of such a consultation system, EXPLAIN, was proposed. Figure 2 shows the general flow of the consultation. First a user specifies the purpose of image processing in terms of predefined abstract functional specifications (e.g., image quality enhancement, image segmentation). Then he or she inputs an image to be processed and describes its rough characteristics (e.g., color or B&W, noise level, contrast) via a terminal. The system first reasons about a global processing plan based on both the given goal specification and the stored knowledge about standard image analysis processes. The plan is described as an ordered sequence of abstract image processing algorithms (functions) such as noise elimination, edge detection, thresholding, region segmentation, and so on. The knowledge about standard image analysis processes includes a set of such abstract plans and rules to select an appropriate plan satisfying the user’s request and suitable to the given image data. This knowledge is the embodiment of know-how about how to combine primitive image processing operators to
96
TAKASHI MATSUYAMA
Global Procassi
Evaluation of the Result
G All Procassing Finished?
No
FIGURE2 . General flow of consultation (from Sueda and Hoshi, 1986).
realize meaningful image analysis processes. Such knowledge rarely has been written explicitly in ordinary manuals. After selecting an appropriate global processing plan, the system instantiates each abstract algorithm in the selected plan one by one from the beginning (Figure 3): a promising practical command and its appropriate parameters are determined for each abstract algorithm. The instantiation is done through conversations on the detailed user’s objective and image quality guided by the knowledge about commands. The knowledge in this system is described by a set of production rules, which control the search process to find an appropriate command sequence. In Figure 3, for example, the global plan consists of two abstract algorithms:
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
I
F I OK
Evaluation
I
97
OK
pi55-l
FIGURE3. Search process for the instantiation of abstract algorithms (from Sueda and Hoshi, 1986).
and NOISE-ELIMINATION. At the first stage, rule 20 for the instantiation of BACKGROUND-ELIMINATION was applied but failed; a user did not satisfy the analysis result by the selected command. Then, the system activates an alternative rule, rule 21, for the same abstract algorithm, BACKGROUND-ELIMINATION. The following is an illustrative example of a rule for instantiating BACKGROUND-ELIMINATION: BACKGROUND-ELIMINATION
*rule 21*
FOR INPUT OUTPUT EFFECT IF
BACKGROUND-ELIMINATION BINARY- IMAGE LABELED-IMAGE the background region i s eliminated the size o f the background i s larger than
objects
THEN
execute LABELING and LARGE-REGION-ELIMINATION
When this rule is activated, it instantiates into an abstract algorithm sequence,
BACKGROUND-ELIMINATION LABELING
followed
by
98
TAKASHI MATSUYAMA
As the next step of reasoning, rule 81 for instanis activated but fails. And finally, rule 82 instantiates LABELING to generate an executable command. The selected command is applied to the input image, and the result is immediately displayed on the monitor screen. Then, the system asks the user for its evaluation. Depending on the user’s evaluation, the system replaces the operator or modifies parameters by activating other rules and retries the analysis. If the selected command successfully analyzes the image, the system proceeds to the instantiation of the next abstract algorithm in the plan. Note that even if the intermediate analysis result by the selected command is satisfactory, the selection is cancelled and another rule for instantiation is activated if the user does not satisfy the analysis result at some later stage. This backtracking capability realizes the trial-and-error analysis to select commands and adjust parameters. The system performs a large backtrack to try another global processing plan when no new command can be applied to satisfy the user. In addition to the knowledge about standard image analysis processes and commands, EXPLAIN contains rules describing the information about hardware and software architectures of the image processing system such as the number of image memories and special registers. This information is useful to hide specific architectural features of the system from the user and enables him or her to think about image processing at the logical level. LARGE-REGION-ELIMINATION.
tiating
LABELING
E. Knowledge-Based Program Composition System Currently, many software libraries for image processing are available. For example, SPIDER (Tamura et al., 1983) is a FORTRAN subroutine library for image processing containing over 300 subroutines, and many image processing systems are equipped with command libraries. Syntactic and semantic characteristics of program modules (subroutines and commands) in a library, such as data types of arguments of a subroutine, are usually written in a manual. Using such software characteristics of program modules as the knowledge source, we can develop an automatic programming system, which composes complex programs by combining program modules in the library. A user of the system has only to write an abstract program specification without knowing about details of program codes. Although we usually have to improve the composed program in its analysis capability and efficiency, expert systems of this type are useful to quickly develop image analysis programs for various applications. Automatic programming has long been a dream in software engineering and artificial intelligence (Barr and Feigenbaum, 1982), but no general-purpose practical system has been developed. However, if we confine ourselves to a
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
99
specific application domain, there may be a good possibility to realize usable systems; we can employ much domain specific knowledge and heuristics. One of the most critical problems in automatic programming is how to describe the program specification. ESIPAs proposed so far use the following specification methods: 1. Specification through conversation, 2. Specification by abstract command and language, 3. Specification by example. Although these specification methods themselves are not very new, there is a big difference between ordinary automatic programming systems and ESIPAs for program composition. That is, besides the symbolic reasoning engine, ESIPAs contain the analysis executor (see Figure l), which executes partially composed programs so as to verify their utilities during the program composition. This capability is necessary because (a) specifications given to ESIPAs are often informal and ambiguous, so that they have to repeat trial-and-error experiments; and (b) usually specifications given to ESIPAs describe only image features to be extracted. Therefore, in order to verify if composed programs are satisfactory, ESIPAs have to apply them to real images and to examine whether or not extracted image features satisfy the specifications. 1. Program Specification Through Conversation Those systems that obtain program specifications through conversation (Tamura et al., 1988; Sato, Kitamura, and Tamura, 1988; Bailey, 1988, Clement and Thonnat, 1989; Bunke and Grimm, 1990) are very similar to the consultation systems described in Section 1I.D. That is, the reasoning and conversation with a user are performed just in the same way as the consultation systems; and when the user is satisfied with the final analysis result, the system composes a program based on the analysis history stored in the system. Figure 4 illustrates a search tree representing the reasoning history. Each node in this tree represents a practical operator (subroutine) selected by the system during the reasoning process, and arcs between nodes specify orders of execution. In the figure some sequences of operators could not generate the satisfactory result, and the sequence illustrated by bold lines denotes a successful image analysis process. The system generates an executable program corresponding to the successful path in the tree. For this program generation, the knowledge about practical programming languages is required in addition to that about image processing techniques: declaration of variables and their types, syntactic forms for procedure or subroutine calls and argument specification and so on. Since the trial-and-error analysis is required to find appropriate operators
100
TAKASHI MATSUYAMA
n
Y
successful analysis process n
FAIL
FAIL
b
\
FAIL
0
:operator SUCCESS
FIGURE 4. Search tree representing the reasoning history.
and parameters, the flexibility of a system is heavily dependent on the modification process of an instantiated plan. EXPLAIN, described earlier, uses an ordinary tree search algorithm with backtracking to find alternatives. It should be noted that the tree in Figure 3 illustrates a history of the search and that the system instantiates abstract algorithms one by one in a sequential fashion. Such a sequential search prevents the system from reasoning about image analysis processes from a global viewpoint. DIA-Expert (Tamura et al., 1988; Sato et al., 1988) uses the operation tree to explicitly describe an image analysis process at various levels of abstraction (Figure 5(a)). The level of the operation tree means the level of abstraction. That is, vertical arcs in the tree represent abstraction and instantiation relations between image analysis algorithms. At each level a sequence of image analysis algorithms is described. In the figure, such sequence is shown as a group of rectangular nodes connected by dashed arrows. The sequence at the bottom of the tree represents the sequence of executable software modules in the program library, names of subroutines in SPIDER. In DIA-Expert all reasoning processes for the plan generation, instantiation, and modification are considered as symbolic manipulations of operation trees (Figure 5(b)). Besides rules for these reasoning processes, the system contains additional rules to avoid artifacts caused by image processing operators and to enhance effects of the operators. When these rules are activated, auxiliary nodes representing various pre- and postprocessing operations are added to the operation tree (see the right side of Figure S(b)). These rules are useful to improve the capability and robustness of composed image analysis programs.
101
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION abstract algorithm abstract
binarization
noise elimination
-
single threshold
-
small reglon elimination
shape smoothing
-
shrink
expand
concrete executable command
order of execution
(a)An operation tree for segmentation.
iNSTANTlATE
L
I
small region elimination
I
I
AUGMENT
noise elimination
hole filling
FHL1
INSTANTiATE
small region elimination
- - - - _ _ - _ - ESAR
(b)Instantiationand augmentation of operation trees.
FIGURE5. Operation tree (from Tamura et al., 1988): (a) an operation tree for segmentation; (b) instantiation and augmentation of operation trees.
In short, the operation tree provides a uniform common data structure and enables the system to take a global view for program composition and modification. A similar tree representation of image analysis processes was used in Clement and Thonnat (1989). 2. Program SpecEfication by Abstract Command and Language
When we write a program for image processing, we have to write many codes
102
TAKASHI MATSUYAMA
besides those for essential processing: declaration and initialization of image data arrays, allocation of working memories, and so on. Especially, when we develop a complex image analysis program using a program module library, we want to devote ourselves to the function of each module without caring about such programming details. Expert systems that generate executable programs from abstract commands facilitate the development of complex image analysis programs. With such systems, we have to only specify combinations of modules in the library without knowing about their detailed syntactic and semantic structures. Sakaue and Tamura (1985) proposed an automatic program generation system using SPIDER. The system generates a complete RATFOR (structured FORTRAN) main program from a given abstract command sequence. Figure 6(a) shows an input command sequence, whose meaning is as follows: 1. For an image in the standard format (SFDI), G, compute its histogram (HISTl), 2. Find a threshold value from the histogram (THDS2), 3. Apply binarization to G using the threshold (SLTHl), 4. Apply connected component labeling (CLAB), 5. Remove tiny regions (ERSR3), 6. Compute a compactness measure of each region (CRCLI).
Each command denotes the name of a subroutine in SPIDER. The system stores the syntactic and semantic information about each argument of every subroutine in SPIDER, such as input-output discrimination, data type, and semantic usage (e.g., image data, histogram, property table, etc.). For example, Figure 6(b) shows the syntactic and semantic constraints of HISTl. The second line reads “the first argument ($1) is an input argument and its data type is Gray Picture” and the third line “the second argument ($2) is an output argument and its data type is Histogram.” The last three lines specify the semantic constraint on the first and second arguments: the third attribute of the first argument (i.e., $1-3, the number of gray levels of the input picture) must be equal to the first attribute of the second argument (i.e., $2-1, the size of an array for the output histogram). Based on this information, the system determines real arguments for each subroutine, if necessary, asks a user to specify missing parameters, and generates a complete main program consisting of a set of necessary data declarations and a sequence of subroutine calls (Figure 6(c)). By comparing the length of the input command sequence with that of the generated program, the effectiveness of the system can be clearly understood. Specifications used by this system describe abstract image analysis processes in terms of names of subroutines. In this sense, the level of abstrac-
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION SFDl
103
HIST1 $1 In GRYN $2 out HlST
G HlSTl in G THDS2 SLTHl in G CIAB ERSR3 CRCLl
I
$19 $2-1
(%)Syntactic and semantic consIraints.
(a)Command sequence. I program
PARTICLE
I
GRYU: GRAY PICluRE (O<= h <M;R ) HIST: H I S T O X M I EIW: BINARY IPdGi LAB: LAeELEO PICTURE WORK: kQ% AREA (1dlnENSIONAL) I m: LAIELEO PICTLRE
I integer integer lnteqger integer inteper integer
thrb51 WIT01
.I
errc AWN1
I
I I
M 1s
lrr ngr "r nr1
I
(c)Generated complete main program. FIGURE 6. Specification by abstract commands (from Sakaue and Tamura, 01985 IEEE): (a) command sequence; (b) syntactic and semantic constraints; (c) generated complete main program.
104
TAKASHI MATSUYAMA
tion of the program specification is not high; users have to know specific names of subroutines in SPIDER. We can consider it as a syntactic and semantic editor (i.e., so-called structured editor; Donzeau-Gouge, 1984) for the library, by which the program development is facilitated much more than ordinary text editors. De Haas (1987) proposed an automatic programming system that generates object detection programs from specified object models. Object models to be detected are described in terms of rewriting rules of an attribute grammar. For example, rules dl(R, S), d2(R, S) = disk(R, S) twodisks(R, D, S) -+ [dl(R, S ) , d2(R
+ D, S ) ]
describe that nonterminal symbol twodisks consists of two terminal symbols d l and d2, both of which are disk types. A disk (i.e., d l or d2) has two attributes, R and S. The former represents the location (two-dimensional position vector) and the latter the size of a disk. The symbol twodisks has an additional attribute I),which represents the displacement vector between two constituent disks. A user gives a goal like with “twodisks”: print (D,
2);,
which specifies “generate a program that detects an instance of twodisks and prints D with a precision plus or minus 2.” Using predefined object models, the system transforms the goal into an executable program: dl
= diskprograml();
d2
= diskprogram 1( );
D
= d2.R
-
d1.R;
print(D, k 2); Here diskprograml() denotes a primitive function in the program library. It analyzes an image to detect a disk and measure its properties. As is seen in this example, terminal symbols in the attribute grammar directly correspond to program modules that extract corresponding types of image features, and attributes of terminal symbols describe properties of extracted image features. In contrast to the previous ESIPA, the level of the specification in this system is too high; whereas a user can specify complex image features with internal structures by defining new nonterminal symbols, it is impossible to compose and modify program modules for primitive image feature extraction. That is, combinations of fundamental image processing operators like
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
105
smoothing, edge detection, and thresholding are built in and fixed in the program modules. In other words, the knowledge for primitive image feature extraction is procedurally represented in the modules. A more flexible ESIPA for extracting complex image features will be described in Section 1V.D.
3 . Program Specijication by Example In most ESIPAs a user specifies the objective, characteristics of an image, and evaluation results by using a predefined vocabularly (i.e., a set of symbolic predicates). As is well known, however, it is very hard to describe the expected analysis result and the image quality in such symbolic descriptions. (We will discuss this problem, specifically declarative representations of spatial relations and structures, later in Section IV.) One idea to avoid this problem is to use images and or figures for the goal specification. In IMPRESS (Hasegawa, Kubota, and Toriwaki, 1986, 1987), a user specifies a goal of analysis by a sample3gure. That is, a request given to the system is “compose a program by which the input image is transformed into the sample figure.” Figure 7 illustrates a reasoning process in IMPRESS. The overall reasoning process in IMPRESS is similar to those of other ESIPAs: the global processing plan determination followed by the operator and parameter selection. First, the system determines a global processing plan based on the type of the sample figure: point, line, or region. A plan in IMPRESS is also described as a sequence of abstract algorithms. Then, the reversed version (i.e., inverse function) of each abstract algorithm in the plan is applied to the sample figure one by one from the end (see the left column in Figure 7). The images generated by these inverse operations are used as the references to evaluate the performance of and select practical operators and parameters for each abstract algorithm in the plan. In selecting an appropriate operator and parameters for (i.e., instantiation of) each abstract algorithm, the system applies several promising operators with different parameter values in parallel. All the processing results are compared with the reference image that was generated from the sample figure. Then, the system selects the best operator with optimal parameters that generated the most similar result to the reference image. In Figure 7, for example, six different edge detection operators like SOBEL, PREWITT, and so on were applied to the input image. The numbers listed under the resultant images show goodness measures evaluated based on the reference image at the top of the left column of Figure 7. In this example, the first-order diagonal difference operator was selected and its resultant image was used as the input for the next binarization stage. After interating similar instantiation process for each subsequent abstract algorithm, the system generates a complete
106
TAKASHI MATSUYAMA
I
I
1 1
1
f
--
TION
E I M sf B I N A R I Z A
t
E
FIGURE 7. Goal specification by a sample figure (from Hasegawa et al., 1987)
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
107
image analysis program by combining the selected practical operators with optimal parameter values. The goal specification by example is very natural and easy for any user. The use of sample figures is especially effective to determine optimal parameters, which usually requires trial-and-error analysis. In IMPRESS, however, all knowledge about inverse operators for generating reference images and evaluation methods for selecting practical operators and parameters is described procedurally in a group of specialized programs. Thus, many heuristics and ad hoc rules are implicitly incorporated. This makes it hard to improve and augment reasoning capabilities of the system. Another serious problem in IMPRESS is that it composes an image analysis process (program) based on a single pair of an image and a sample figure, so that selected operators and parameters depend heavily on that specific image data and sample figure. Most users, however, want to have a general image analysis process that works well for a class of images with similar properties. A preliminary discussion on this problem is given in Hasegawa et al. (1988). First several pairs of images taken from the same class and corresponding sample figures were given to IMPRESS to generate a set of (different) image analysis processes. They proposed a heuristic reasoning method of consolidating such image analysis processes into an integrated one, which is expected to work well for all member images of that class. In general, however, the consolidation requires sophisticated reasoning for generalization and abstraction of image analysis processes. Such highlevel reasoning is very difficult without well-defined theoretical foundations for describing syntax and semantics of image analysis operators and their combinations. In this sense, the method proposed in (Hasegawa et al., 1988) is far from complete, nor does it give a promising direction to be pursued for the generalization of image analysis processes. Vogt (1989) proposed an automatic programming system named REM, whose goal specification is also given by sample figures. He emphasized that to realize intelligent systems like automatic programming systems, a concrete mathematical theory is of the first importance. REM uses the mathematical morphology (Serra, 1982, 1986) as its theoretical basis. That is, image analysis processes composed by REM are described by combinations of various morphological operators for (mainly binary) two-dimensional images. In REM, the goal specification was augmented from that in IMPRESS as follows. The following three sets of images are given as a goal specification (Figure 8(a)): 1. XO = {XOi( i = 1
-
N)}: A set of base images. These images are samples taken from a class of images to be analyzed.
108
TAKASHI MATSUYAMA base image
reject mask
I
(a) Problem specification by a base image, accept and reject masks.
Sequential Decomposition
Split Decomposition
Transform
-
x1
Sequential Decomposition
Fill-in Transform
Transform
1
Fill-in Transform
( XO-
OP1
X4-
OP2
X5-
OP4
A0 I RO
)
(b) Example of the algorithm state tree (see text).
FIGURE8. Program composition using morphological operator: (a) problem specification by a base image, accept, and reject masks; (b) example of the algorithm state tree (see text).
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
-
109
2. A0 = {AOi (i = 1 N ) } :A set of accept masks. Each mask image in this set specifies a group of pixels that must be extracted from its corresponding base image. 3. RO = {ROi (i = 1 N ) } : A set of reject masks. Each mask image in this set specifies a group of pixels that must not be extracted from its corresponding base image.
-
First, the problem of IMPRESS discussed earlier, i.e., a composed image analysis process in IMPRESS depends heavily on a pair of an input image and a sample figure, is solved to some extent by using sets of images as a problem specification. Second, a goal of image analysis is described more precisely by using both positive and negative examples; i.e., accept and reject masks. The reasoning for program composition in REM is performed by the stepwise refinement of abstract analysis processes. The reasoning engine uses a tree structure named Algorithm State Tree to maintain the current state and history of the reasoning process so far executed. Figure 8(b) illustrates an example of the algorithm state tree. Each nonterminal node (ellipse) in the tree represents an abstract image analysis process, which in turn is represented by a directed graph. In the graph, a node represents a base image set, a set of intermediate analysis results or a pair of accept and reject mask sets. An arc in the graph represents a practical morphological operator (OPS 1, OPS2, OPS3, OPS4, and UNION in Figure 8(b)) or a subproblem to be solved (i.e., an abstract image analysis process to be composed, PROBO, PROB1, PROB2, PROB3, and PROB4 in Figure 8(b)). For example, the root node of an algorithm state tree contains a directed graph with a single arc. This arc represents the original problem specified by a user, PROBO, and connects a set of base images and a pair of accept and reject mask sets given as a goal specification (see Figure 8(b)). Each subproblem is symbolically described in terms of three sets of images: input images to be analyzed and accept and reject masks for the input images. To solve a subproblem (i.e., to instantiate an abstract image analysis process), the reasoning engine first analyzes degrees of overlap among the three sets of images and masks. Then it instantiates the subproblem by selecting an appropriate morphological operator depending on characteristics of the overlaps. About 10 predicates are prepared to describe characteristics of overlaps. Predicate A-SUP (A-ZNF), for example, implies that each base image (i = 1 N ) is an upper (lower) bound on its corresponding accept mask A i . Predicates R-SUP and R-INF are defined similarly using base images and reject masks. The operator selection process is implemented by a decision tree, so that the flexibility of reasoning is limited. In most cases, however, the selected operator, when applied to base
x.
-
110
TAKASHI MATSUYAMA
images, does not produce perfect results that match the given accept and reject masks completely. Then the reasoning engine transforms (specializes) the subproblem into a combination of the selected operator and a new (sub-) subproblem. By this transformation, the graph including that subproblem (i.e., node in the algorithm state tree) is expanded to a new graph, which then is added to the algorithm state tree as a new child node of the original one (see Figure 8(b)). An arc in the algorithm state tree represents such transformation. The following three types of transformations were proposed in REM: 1. Fill-in Transform. This transform just replaces a subproblem with a selected morphological operator. The transform of this type is executed when the selected operator generates analysis results that completely match the accept and reject masks. 2. Sequential Decomposition Transform. This is the most commonly used transform. The original subproblem is decomposed into a sequence of the selected operator followed by a new subproblem. The set of base images for the new subproblem is generated by applying the selected operator to the set of original base images. On the other hand, complicated processings are required to produce the accept and reject masks for the new subproblem. This is because a major purpose of the new subproblem is to compensate the imperfection of the selected operator. Thus the accept and reject masks of the new subproblem are not the same as those of the original subproblem. Note that this point is not illustrated in Figure 8(b). 3. Split Decomposition Transform. As shown in Figure 8(b), this transform splits the original subproblem (arc in a graph) into multiple new subproblem (arcs), whose results are combined by UNION or INTERSECTION operators. This transform does not seem to be implemented in Vogt (1989) because it is very hard to generate accept and reject masks for :he new subproblems; degrees of overlap among images and masks alone do not include enough information to conduct reasoning about new subproblems in this transform.
The search process executed by the reasoning engine expands the algorithm state tree by applying these transforms until a graph with no subproblem (leaf node in the tree) is obtained. The implemented search algorithm was a simple breadth first search and some cost function was incorporated to guide the search. In short, although REM’s approach is interesting and promising, the image analysis processes that can be composed by it are limited. This is because 1. Although a simple thresholding operator and some mechanism to cope
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
111
with noise were incorporated, many filtering operators for gray images were not used. The implemented system is mainly for binary image processing. 2. Morphological operators were augmented with bandpass operators that include ranges of parameter values to control sizes of structural elements. But the ability to describe shapes, especially linelike figures, is limited. 3. Sophisticated knowledge about operator characteristics is required to realize more flexible operator combinations like the split decomposition transform; image analysis processes composable by the implemented system are confined to sequential ones. (We will discuss this problem later in Section 111.)
F. Rule-Based Design System f o r Bottom-up Image Segmentation Algorithms Image segmentation is a crucial analysis process in image recognition and understanding. It extracts image features such as lines, corners, and regions from an image, in terms of which the structure of the image is described symbolically. In this sense, the segmentation process can be considered as a bridge between iconic signal data and symbolic structural description. Hundreds of image segmentation algorithms have been developed (Ballard and Brown, 1982; Rosenfeld and Kak, 1982), but none of them works perfectly for complex natural images and yet another new segmentation algorithm is being proposed. In general, there are two types of image segmentation for image recognition and understanding: 1. Bottom-up Image Segmentation. Given an image(s), an ordinary image
analysis process to extract image features is image (image quality enhancement) * enhanced image * (feature extraction) image feature * (grouping) =s structural description. The segmentation of this type is called bottom-up image segmentation. Its major knowledge sources are characteristics of imaging devices (e.g., resolution, focal length, color spectral properties), image models (e.g., step and roof edge models, smoothness of gray-level variations in a region), and so-called gestalt laws for grouping (e.g., proximity, good continuation). Usually no knowledge about specific objects to be detected is incorporated in the bottom-up segmentation process. This means that the entire image is analyzed uniformly; no specification about interesting areas is given a priori. 2 . Top-down Image Segmentation. The segmentation of this type
112
TAKASHI MATSUYAMA
sometimes called goal-directed image feature extraction. As its name stands, top-down image segmentation is guided by a goal, a model of an image feature to be extracted from an image. A goal may be specified directly by a human user or generated by the reasoning engine in an image understanding system. In IUSs top-down image segmentation is used to compensate the imperfection of bottom-up image segmentation; since the latter uses very general knowledge for image segmentation and little is known about the structure of an image under analysis, it often fails to extract some meaningful image features. (This reminds us the chicken-and-egg problem discussed in Section 1I.A.) Then, top-down image segmentation is initiated to find such missing image features. At the initiation of top-down image segmentation, IUSs reason about types and properties of missing image features and their approximate locations. Then such information is given as a goal specification to the top-down segmentation process. Thus, in contrast to the uniform analysis over the entire image in bottom-up image segmentation, topdown image segmentation analyzes only focused local areas based on the specific knowledge given in the goal specification. This is the reason why top-down image segmentation can compensate the imperfection of bottom-up image segmentation. The combination of the uniform bottom-up analysis and the goal-directed top-down analysis is a powerful and practical way of solving the chicken-and-egg problem in image analysis and understanding. Several ESIPAs described so far can be considered as those for top-down image segmentation: Haar’s system, IMPRESS, and REM. In this and next subsections, we will describe ESIPAs for image segmentation: first in what follows, we describe an ESIPA for bottom-up image segmentation and then, in the next subsection, we will describe an ESIPA for automatic top-down image segmentation. Usually, algorithms for bottom-up image segmentation use many heuristics to split or merge regions and lines into meaningful ones. For example, “merge neighboring small regions with similar properties into one region” and “connect pieces of collinear line segments into one” are typical heuristics used in bottom-up image segmentation. While filtering operators for smoothing and edge detection can be designed based on well-defined mathematical theories, the incorporation of heuristics into segmentation algorithms is inevitable; we have no concrete formal theory for grouping operations except psychologically tested gestalt laws. Thus, to design an image segmentation algorithm with high performance, we have to repeat trial-and-error experiments to test the effectiveness of incorporated
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
113
RULE(1): IF: (1)The. REGION SIZE is LOW AND ii)mREGION ASPECT RATIOis VERY HIGH AND (3)The DIFFERENCE in INTENSITY is N O T HIGH AND (4)The DIFFERENCE in HUE is NOT HIGH AND (5)The DIFFERENCE in SATURATION is NOT HIGH THEN: (1)MERGE the two REGIONS.
METARWE( 1): IF: (1)Previous PROCESS was FOCUS AND (2))previousPROCESS was ACTIVE THEN: (1)Match the REGION ANALYSIS rules.
METARULE(2): IF: (1)Previous PROCESS was REGION AND (2)Previous PROCESS was NOT ACTIVE THEN: (1)Match the LINE ANALYSIS rules.
FIGURE9. Production rules for bottom-up image segmentation.
heuristics. Moreover, different heuristics should be used depending on the image quality. Most image segmentation algorithms have been implemented as ordinary procedural programs, so that heuristics used by them are implicitly represented, and consequently, their flexibility and modifiability are vitiated. Nadif and Levine (1984) proposed a rule-based expert system for image segmentation to increase the flexibility and modifiability of bottom-up image segmentation. The objective of the system is to partition a given image into a set of mutually disjoint meaningful regions. In the system, various heuristics for image segmentation are represented by a set of production rules (Figure 9). As discussed in Section I, the explicit declarative representation of heuristics greatly facilitates their modification, augmentation, and the test of their effectiveness. Such facilities are very valuable in designing image segmentation algorithms because we have to devise and test various different heuristics depending on properties of images under analysis. As will be described later, moreover, flexible control mechanisms can be realized by rule-based systems. Roughly speaking two types of rules were used in the system: one for heuristics for image segmentation and the other for controlling the analysis flow of the segmentation process. 1 . Rules for Image Segmentation Heuristics. Rules of this type can also be
114
TAKASHI MATSUYAMA
divided into two sets: one for region-based segmentation and the other for line-based segmentation. This is because, to realize the meaningful partitioning of a complex image, region-based segmentation alone is not enough and complimentary line-based segmentation for detecting region boundaries is required. In both types of rules, the condition part of a rule describes constraints on attributes of regions and lines and their mutual spatial relations. The action part specifies a split and/or merge operation on the regions and lines specified in the condition part. Rule (1) in Figure 9 illustrates a production rule for region-based image segmentation. Several tens of primitive predicates and actions were prepared to describe heuristics in the form of production rules: in rule (1) in Figure 9, for example, REGION SIZE, LOW, ASPECT RATIO, VERY HIGH, MERGE, and so on. 2. Rules for Process Control. Besides rules for image segmentation heuristics, the system stores a set of meta rules to control the overall segmentation process (metarules (1) and (2) in Figure 9). First, the mode of the system is switched by a meta rule from region analysis to line analysis and vice versa. That is, which region-based or line-based analysis is performed is dynamically determined by meta rules. The second role of meta rules is to select and focus on a local area to be analyzed, and rules for image segmentation are applied to those regions or lines in the focused area. Metarule (1) in Figure 9 represents the control knowledge such that when a focused local area is selected, first perform region-based segmentation. Metarule (2) implies that perform line-based segmentation if region-based segmentation is terminated. Using these metarules, flexible control structures can be realized, which are very difficult in ordinary procedural segmentation programs. The flexibility of the system allows the fast development of effective image segmentation algorithms, although the execution time is slow. It should be noted that this ESIPA is different from the other ESIPAs discussed in this chapter; it is an expert system to develop a new image segmentation algorithm, while the others compose image analysis processes based on existing image processing operators. G . Goal-Directed Top-down Image Segmentation System
In image understanding of complex scenes, goal-directed top-down image segmentation is often required to correct errors incurred by initial bottom-up image segmentation as well as to verify the existence of a hypothesized object (Selfridge, 1982; Matsuyama and Hwang, 1990). For example, Figure 10 illustrates a snapshot of the spatial reasoning performed by our aerial image
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
115
FIGURE10. Example of top-down segmentation: (a) hypothesis generation for a missing object; (b) target window for top-down segmentation; (c) detected elongated rectangle.
116
TAKASHI MATSUYAMA
understanding system SIGMA (Matsuyama and Hwang, 1990). The scene under analysis is a suburban housing development; and the task of the system is to recognize houses, roads, and driveways and describe the structure of the scene in terms of recognized objects. The elongated and compact solid rectangles in Figure I O(a) show recognized road-piece and house instances that were detected by bottom-up image segmentation, respectively. Two overlapping dashed rectangles between the solid ones represent hypotheses for a driveway that were generated by these two recognized objects. As shown in the figure, since the contrast between the driveway and its surrounding area is very low, the elongated rectangle corresponding to the driveway could not be extracted by the bottom-up image segmentation. Then, the system initiates top-down image segmentation for extracting an elongated rectangle in the local window specified by the hypotheses (Figure 10(b)). Figure 1O(c) illustrates the elongated rectangle detected by the low level vision expert (LLVE) for top-down image segmentation in SIGMA. In what follows, we will describe the knowledge representation and reasoning methods of LLVE. (A summary of the reasoning mechanism of SIGMA will be given in Section 1V.D.) The task of LLVE is to automatically extract image features (e.g., lines and regions) that satisfy the constraints specified in a given goal. “Find a rectangle whose area size is between 100 and 200 pixels” is a typical example of the goal specification. LLVE uses two types of knowledge to conduct automatic image segmentation: 1. Knowledge about fundamental concepts in image segmentation: types of image features extractable from an image and types of image processing operators. 2. Know-how about image segmentation techniques: how to combine operators effectively and conduct trial-and-error analysis by selecting operators and adjusting their parameters.
The knowledge of type 1 can be defined in a formal way, while that of type 2 involves many heuristics. In LLVE the former type of knowledge is represented by a network describing the type structure in the task domain of image segmentation and the latter by a set of production rules. Suppose we want to extract line segments from a gray picture. Gray picture * (edge detection) * edge picture => (thresholding)*edge point => (linking) * line segment would be a typical analysis process to satisfy the objective. We call gray picture, edge picture, edge point, and line segment in the preceding example image features, and edge detection, thresholding, and linking transfer processes. An image feature refers to a type of information extractable from a raw picture data, and a transfer process an abstract
IMAGE PROCESSING, PROCESSING,ANALYSIS, ANALYSIS, AANNDD RECOGNITION RECOGNITION IMAGE
117 117
output Image Feature
Input Image Feature
Algorithm 1 Algorithm 2 Transfer Process
.......... Algorithm n-1 Algorithm n
Transfer Process 1
Transfer Process 2
-
1
. .. . . . .
Transfer Process N
FIGURE11. Image features, transfer processes, and process sequences.
algorithm’ that analyzes its input image feature to generate its output image feature. Usually, to extract a specific image feature from a raw picture, we have to combine several different transfer processes as shown in the preceding example. We call such ordered sequence of transfer processes process sequence. Figure 11 illustrates the conceptual relations among image features, transfer processes, and process sequences. Note again that a transfer process denotes a class (type) of practical algorithms with similar functions. LLVE uses image features and transfer processes as fundamental descriptive terms to represent the knowledge about image segmentation. Figure 12 illustrates the network knowledge organization used by the system, where each ellipse denotes an image feature and a directed arc a transfer process. Several kinds of icons are used to represent heads of arcs, which illustrate types of transfer processes. (Here we will not go into detailed discussions on the meanings of such types.) Each image feature is represented by a frame (Minsky, 1975). We call it the image feature frame. A frame is a data structure to represent structured knowledge about an object. It consists of a set of slots, where various types of information, such as attributes of the object, relations to other objects, and procedures to compute properties, are stored. Each image feature frame consists of a set of slots representing various attributes of the image feature. For example, the image feature frame for Line contains slots representing starting point, chain code, length, etc. (Figure 13(a)). In addition to slots for such attributes, every image feature frame
’
software type type theory theory (Harland, (Harland, 1984), 1984), aa transfer transfer process process can can also also be be From the viewpoint of software considered as a type: type: aafunctional functional type. type. That That is, is, all all functions functions that that transform transformdata dataof of type type AA into into type B are of the same same functional functional type type denoted denoted by by A A+ +B. B. those of type
118
TAKASHI MATSUYAMA Low Level Vision E x p e r t NETWORK D i s p l a y W i n d o w
FIGURE12. Network knowledge organization.
includes two additional slots used by the system: MADE-BY slot to represent the transfer process that generated the image feature, and FROM slot to represent its source image feature from which that image feature was generated. The system uses these two slots to maintain the analysis history. An image feature frame defines a class of practical image features. Real data extracted from an image are represented by its instances. Figure 13(b) shows an instance of the image feature frame for Line. All of the slots are filled with values representing the attributes of the detected line, while the image feature frame defines the slot structure. In image segmentation, image feature frame instances are analyzed by transfer processes, and new instances are generated. We also use a frame to represent a transfer process. Figure 13(c) shows the structure of the frame to represent transfer processes. All transfer processes have the same slot structure, while those of image feature frames vary depending on their attributes. As in the case of image feature frames, every really executed analysis process is represented by an instance of such frame, where all slots are filled with values representing the name of an executed practical algorithm, parameter values, input and output image feature frame instances, and computation time. Note that the value in the MADE-BY slot in Figure 13(b), (LINKING 890), denotes the name of an instance of transfer process frame LINKING, which was applied to an instance of image feature
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION Image Feature Frame Name: Slot Name:
119
Line Starting Point Chain Code Length MADE-BY FROM
(a)Image feature frame for Line Slot Name Image Feature Frame Name: Starting Point: Chain Code: Length: MADE-BY: FROM:
Slot Value Line (10, 60) (2, 3, 3, 5 ,....) 15.5
<Edge Point 567>
(b)Instance of image feature frame Line
I Transfer Process Frame Name:
-----
Slot Name:
Type of Transfer Process Algorithm Parameters Input Image Feature Frame Instance Output Image Feature Frame Instance Computation Time (c)Transfer process frame.
FIGURE 13. Symbolic representation of image features and transfer processes: (a) image feature frame for Line; (b) instance of the image feature frame for Line; (c) transfer process frame.
frame edge point, (Edge Point 567), to generate an instance of image feature frame line, (Line 123). In addition to the network describing the fundamental terminology for image segmentation, knowledge and know-how are required to realize effective image segmentation. The following lists tasks requiring knowledge. 1. Selection of an Appropriate Process Sequence (Efective Combination of Transfer Processes). Usually, there are many different ways of extracting a specific image feature. Such different analysis processes are
120
TAKASHI MATSUYAMA
represented as multiple directed paths (i.e., sequences of arcs) in the network. In other words, various different process sequences are embedded in the network. For example, there are two major paths to extract a region from a gray picture: one via line and the other via homogeneous region. Knowledge-based reasoning is required to find an appropriate process sequence. 2. Selection of a Practical Algorithm and Its Optimal Parameters. As noted before, a group of executable image processing operators are associated with each transfer process (see Figure 11). For example, the transfer process (i.e., arc in Figure 12) from gray picture to edge picture represents edge detection, with which various practical edge detection operators like the Sobel and Laplacian are associated. The system has to reason about which practical operator is useful for each transfer process in the selected process sequence. Moreover, since operators have many adjustable parameters, the system has to determine optimal values for them. 3. Realization of Robust Image Segmentation. We need many heuristics to make image segmentation robust and adaptive for images of different qualities. For example, if an image is noisy, one should smooth it before segmentation, and it is preferable to apply nonmaximum suppression to an edge picture before edge tracking. Moreover, image segmentation involves many steps of trial-and-error analysis; it is usually hard to determine the best operator and optimal parameter values before analyzing a given image. Thus, in order to make image segmentation adaptive, we need know-how to conduct trial-and-error analysis: how to select an alternative operator and adjust parameter values based on preceding analysis results. In LLVE, these knowledge and know-how are represented by production rules. Table I summarizes seven types of production rules used by the system. Each rule has an AT part in addition to ordinary IF and THEN parts. Conceptually, the AT part specifies where in the network each rule is to be stored: which node or arc in the network. As will be described later, the reasoning engine searches the network for the most promising process sequence to extract the image feature specified in a given goal. When the search process visits a node or follows an arc, rules stored in it are activated to guide the subsequent search. In other words, image features and transfer processes define the structure to be searched and production rules control the search. Figure 14 shows an example of the reasoning and segmentation by LLVE. The goal specification given to the system is as follows (Figure 14(b)). Find a rectangle(s) in the image shown in Figure 14(a) whose area size is between 100 and 400 and that is located in the specified window (upper-left and
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
121
TABLE I TYPESOF PRODUCTION RULESUSEDIN LLVE. Type of Production Rule
Function
Example
Transfer Process Selection Rule
Select promising transfer processes during the search
AT Region IF ISOLATION is NO, THEN select CLOSED-SEGMENT-TOREGION
Transfer Process Dependency Rule
Describe the dependency between transfer processes
AT HOMOGENEOUSREGION-TO-REGION IF NOISE-LEVEL is not LOW, THEN include BINARYPICTURE-TO-BINARYPICTURE
Cost Computation Rule
Estimate the processing cost of transfer processes
AT EDGE-POINT-TO-LINE IF algorithm equals linking and COMPLEXITY is HIGH, THEN (equation to compute the cost)
Constraint Transformation Rule
Transform constraints on the output image feature into those on the input image feature of the transfer process
AT REGION-TO-POLYGON FOR area IF T, THEN set POLYGON.AREA to REGION. AREA
Algorithm Selection Rule
Select a promising executable algorithm for the transfer process
AT EDGE-POINT-TOLINEAR-SEGMENT IF ACCURACY IS HIGH, THEN select fine Hough transform
Parameter Selection Rule
Select an appropriate parameter value for the algorithm
FOR thresholding, IF failed before, THEN increase the threshold by 20%
Failure Rule
Specify alternatives to recover from failure
AT POLYGON-TORECTANGLE IF T, THEN FIND-ANOTHERPATH from Polygon
122
TAKASHI MATSUYAMA
GOal Frame : RECTANGLE Goal Proowties : AREA-WE IINTEOW): 1103 mot
coMpLD(TTY 1syMBouc:
(b)
*0
No *Rectangle
c
Modify Threshold
FIGURE14. Example of image segmentation by LLVE.
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
123
in the goal specifies lower-right corners: (1 6539) and (204,115)). COMPLEXITY the complexity of the image data under analysis. To describe other image NOISE-LEVEL, and TEXTURE properites, predicates like ISOLATION, CONTRAST, are prepared. In addition to these specifications, we can describe ACCURACY and ALLOWABLE-COST in a goal. The former specifies how accurately the analysis should be done and the latter how much computation time can be spent. Given the goal, the system first reasons about which process sequence is best to extract the specified rectangle from the window. This reasoning is done by searching for the most promising path in the network connecting gray picture and rectangle. The search is initiated from the goal image feature, rectangle, and traces arcs in the network backward to the source image feature, gray picture. In principle, the search process tries to find the minimum cost path between the source and goal image features. Note that the cost of each transfer process is dynamically estimated by cost computation rules (Table I), because the computation cost varies depending on specified goals and properties of image data under analysis. Transfer process selection rules and transfer process dependency rules (Table I) represent know-how about how to combine transfer processes and guide the search. During the search, they are activated to prune search paths and introduce auxiliary transfer processes to make a selected process sequence effective, respectively. The pruning and introduction of auxiliary transfer processes by such rules surpass the minimum cost search: an expensive path can be selected if its utility and effectiveness are acknowledged by rules. In the current example, the process sequence shown in Figure 14(c) was selected. The self-looping transfer process at binary picture means noise elimination. This auxiliary transfer process was introduced to realize effective analysis by a transfer process dependency rule. After the search, the system executes the transfer processes included in the selected path one by one from the beginning (Figure 14(d)). Algorithm and parameter selection rules (Table I) are activated to select an appropriate executable operator and its parameters for each transfer process. Constraint transformation rules (Table I) transform constraints on the goal image feature (i.e., rectangle) into those on intermediate image features (i.e., nodes) in the selected path. When a transfer process (i.e., selected operator) is executed, an instance(s) of its output image feature is generated, and its attributes are compared with the constraints transformed onto the output image feature. If there exists at least one instance that satisfies the constraints, the transfer process is regarded as successful, and the next transfer process is executed by using that instance as input data. In the example, however, the transfer process POLYGON-TO-RECTANGLE failed: no instance of rectangle satisfying the given constraints was generated.
124
TAKASHI MATSUYAMA
In case of such failure, the system activates failure rules (Table I) associated with the failed transfer process. The rule associated with POLYGON-TORECTANGLE suggested “retry the same process sequence by changing a threshold value for binarization” (Figure 14(e)). This rule embodies the knowledge that the result of binarization is very sensitive to a threshold value, so that the modification of the threshold can improve the analysis result. By this modification, a rectangle satisfying the goal specification was successfully extracted (Figure 14(f)). In general, failure rules modify operators, parameters, and process sequences to recover from failure. The system returns failure when no possible modification by failure rules is left. As described, all reasoning processes are guided by production rules. Therefore, not all possible process sequences nor operators may be tried. In other words, the amount and quality of the knowledge represented by rules determine the capability of the system. The current system contains about 400 rules, but they are far from sufficient. Moreover, as shown in Figure 12, image features extractable by the system are confined to very primitive ones. LLVE cannot directly extract complex image features such as dark regions with narrow bottlenecks and bright holes. (We will describe an ESIPA for detecting complex image features with internal structures in Section 1V.D.) In addition to these problems, analysis processes executed by LLVE are confined to sequential combinations of transfer processes, which, as in the other ESIPAs, limits the capability of image analysis. We will discuss this point in the next section.
111. REPRESENTING KNOWLEDGE ABOUT IMAGE ANALYSIS STRATEGIES While objectives, knowledge representation, and reasoning methods of the ESIPAs discussed in Section I1 are different, they share a common general characteristic; that is, they are sequential reasoning systems. Their sequentiality is twofold: 1. Object-Level Sequentiality. Objects here stand for the entities that expert
systems process and reason about. In the case of ESIPAs, objects are image analysis processes to be composed or executed. Thus the object level sequentiality implies that all image analysis processes composed and executed by the ESIPAs so far described are confined to sequential combinations of primitive operators. Note that in REM, although a nonsequential combination, split decomposition transform, was proposed, no practical algorithm to realize it was described or implemented. 2 . Reasoning-Level Sequentiality. The reasoning processes of the ESIPAs
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
125
are realized by sequential search methods to find a solution in a problem state space. Figures 3 and 8 illustrate typical examples of such sequential search processes. While backtracking and some meta (control) rules were incorporated to augment the flexibility of the search, no concurrent, parallel, or cooperative reasoning was used.
In some sense, these sequentialities are natural partly because many standard image analysis processes can be modeled by sequential combinations of primitive operators, and partly because reasoning engines of ESIPAs can be easily realized by ordinary sequential reasoning mechanisms such as backward-forward chaining in expert systems and linear resolution in PROLOG. Such sequentialities, however, put significant limitations on the systems’ capabilities, which cannot be overcome no matter how much knowledge is incorporated. In the history of image processing research, many sophisticated image analysis strategies such as coarse-to-fine image analysis and integration of edge-based and region-based analyses have been developed to improve the effectiveness and reliability of image analysis. However, image analysis processes based on such strategies cannot be composed as sequential combinations of primitive operators. At the reasoning level, on the other hand, concurrent and parallel reasoning methods are being studied intensively in artificial intelligence to improve flexibility, reliability, and robustness as well as efficiency of intelligent systems (Bond and Gasser, 1988). By introducing concurrent or parallel processing we can get much more than the speed-up of computation; the cooperation and integration among concurrent and parallel reasoning modules allow various substantial improvements of systems’ reasoning capabilities, which are very difficult to realize by sequential reasoning systems. In this section, we will describe the following two advanced ESIPAs to see how reliable and robust image analysis can be realized by introducing nonsequentialities at the object and reasoning levels respectively: 1. Heterogeneous combinations of image processing operators, 2. Cooperative integration of multiple stereo vision algorithms. A . Heterogeneous Combination of Image Processing Operators
In the history of digital image processing, there have been proposed many image analysis strategies to increase the performance of image analysis: feedback (Nagao, 1984) and plan-guided (Kelly, 1971) analyses, coarse-tofine image analysis based on multiresolution images, integration of edgebased and region-based analyses, various optimization methods, and so on.
126
TAKASHI MATSUYAMA
Although these strategies are useful to improve the accuracy, reliability, and efficiency of the analysis, the ESIPAs described so far cannot utilize them at all. Therefore how to incorporate the analysis strategies into ESIPAs is an important problem to improve their image analysis capabilities. In what follows, we discuss two schemes of representing image analysis strategies: one from a software engineering viewpoint and the other from a knowledge representation viewpoint. 1. Functional Programming Language for Heterogeneous Operator Combination All ESIPAs except the one described in Section 1I.F compose image analysis processes by combining primitive operators stored in a library. However, the composition is confined to sequential combinations of the operators. That is, the output of an operator is successively passed to the next operator as its input data. Although many standard image analysis processes can be represented as sequential combinations of operators, their performance is limited. When we describe an image processing operator by a function, the result of applying operator 0 to image D is denoted by O(D). Thus the sequential combination of operators can be described as O,(On-, (. ’ . O,(O, (D))),
(1)
where D denotes an input image data and the 0,, 0 2.,. . ,On-,, 0, functions representing image processing operators. We omit arguments of functions representing parameters for each operator. These functions are successively applied in this order: the innermost function is applied first to produce the data for the second innermost function and so on. This evaluation order is called the applicative order in functional programming. We proposed the following three types of heterogeneous (i.e., nonsequential) combination functions to represent typical image analysis strategies (Matsuyama, Murayama, and Ito, 1988): 1. Combination of multiple analysis results, 2. Mask controlled operation, 3. Parameter optimization.
While we implemented a simple functional programming language with these functions, we will only describe illustrative programs to see how complex image analysis processes can be described without going into implementation details. The combination of type 1 above is described as COMBINE(O, ( D l), . . .
,on(0,) BY c),
(2)
127
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
(a)Combinationof multiple analysis results
(b)Mask controlled operation
(c)Parameteroptimization
FIGURE15. Heterogeneous combinations of operators: (a) combination of multiple analysis results; (b) mask controlled operation; (c) parameter optimization.
where D , ,. . . ,Onare input images for operators 0,,. . . ,On, respectively (Figure 15(a)). C denotes a function that combines O,(D,) (i = 1 n). Note that C is just a function that takes multiple images as its input data and combines them to produce one output image. Therefore we could describe function (2) as
-
C ( 0 ,(Dl
)?
. . On(DnN, . 9
(3)
or more simply
-
C(D', . . . ,D"),
(4)
where D' = O,(D,) (i = 1 n). In other words, the function COMBINE is introduced just to explicitly describe the combination of multiple image data, and the keyword BY to specify the function name for the combination. These syntactic structures improve the readability of programs consisting of nested function calls. (See examples given later.)
128
TAKASHI MATSUYAMA
Typical examples of the processing done by the combination function C are (a) pixelwise logical and arithmetic operations between images, (b) spatial combination (i.e., mosaicking) of local analysis results, (c) consistency examination among multiple analysis results. Combination functions of type (a) are trivial. Practical examples of types (b) and (c) are given later. The mask controlled operation is a popular method to analyze specified (focused) local areas in an image, by which the focus of attention (Nagao, 1984) in image analysis can be realized. That is, suppose an entire image of a cluttered scene is too complex to be segmented into meaningful image features; due to various types of objects, complex lighting conditions, mutual reflections, and shadows, the image quality changes so widely depending on locations in the image that no operator based on a single image model works correctly for the entire image. However, if we can confine the domain of analysis into a small local area in the image, even a simple-minded operator can work correctly to extract a meaningful image feature. This is because the image quality in such a small area is almost homogeneous and the image structure is simple. Of course, it is not easy to find a local area where a meaningful image feature is located. Sophisticated reasoning mechanisms for such focus of attention were described in Selfridge (1982) and Matsuyama and Hwang (1990). The mask controlled operation is described as MASK(O(D) BY M ) . (5) M means a logical mask image to specify local areas in image D where operator 0 is to be applied (Figure 15(b)). Each pixel in the mask image has either TRUE or FALSE as its value. The output of function MASK is defined as O(D(x,y ) ) if M ( x,y ) = TRUE
undefined
if M ( x , y ) = FALSE,
(6)
where D(x,y ) and M(x,y ) denote pixels in D and M , respectively. Mask M itself can be an output of another operator, which extracts interesting regions. Note that we cannot write function (5) as M), (7) where D’= O(D). This is because the function MASK really applies function 0 to D only in those areas specified by M . In this sense, function 0 itself is an argument of the function MASK. A function that takes another function as its argument is called a functional in computer science. To make it explicit MASK(D’ BY
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
that
MASK
129
is a functional, we may write function (5) as MASK(O, D, M ) .
(8)
We use the keyword BY in (5) just for easy reading as in the case of (2). The parameter optimization is very useful to determine the optimal parameter value for an operator. It is described as
.. OPTIMIZE(O(D,
a ,
*, . .), n,,n,, n 3 , BY 0, AT E ) , *
(9)
where D denotes an input image to be processed, 0 an image processing operator, D, the reference image, and E the evaluation function. The symbol * denotes the parameter for operator 0 to be optimized. The parameter is changed from n, to n2 at the increment of n3, and operator 0 with each different parameter is applied to D repeatedly. Then the processed results are evaluated by evaluation function E using D, as the reference: the function E compares each processed result with D, and measures their mutual consistency. The function OPTIMIZE selects and outputs the best result among them: it selects the one whose consistency measure is the highest (Figure 15(c)). Note that the function OPTIMIZE is also a functional and that the keywords BY and AT are used for easy reading. Using these three types of combination functions, we can describe complex heterogeneous analysis processes in a compact way. In what follows, we will demonstrate the effectiveness of the heterogeneous combinations with illustrative examples. The first example is an integration of edge-based and region-based analyses. As is well known, it is very hard for an ordinary region segmentation operator to perfectly partition a complex image into meaningful regions. While most segmented regions correspond to objects in the scene, some cover multiple objects and others only parts of objects. Figure 16(b) is the result of ordinary region segmentation of Figure 16(a), where a shadowed face of the cube and a shadowed area of the floor were merged into one region (the rotated L-shaped region in Figure 16(b)). An image analysis strategy to detect and recover such segmentation errors is to integrate both region segmentation and edge detection. That is, since these analysis methods are complementary to each other, errors caused by one method can be corrected by the other. Moreover, we can evaluate the reliability of analysis based on the degree to which results by these complementary methods coincide with each other. The following function is an example of the integration between edgebased and region-based analyses. MAsK(region(D)BY binarym(coMBINE(region(D), edge(D) BY
edge-count), threshold))
(10)
130
C
TAKASHI MATSUYAMA
d
FIGURE 16. Combining edge-based and region-based analyses: (a) input image; (b) result of region segmentation; (c) detected edge points; (d) result of combining edge-based and regionbased analyses.
Figure 16(d) shows the analysis result by this function. First a pair of the innermost functions region and edge are applied to D, an input image: input image D (Figure 16(a)) is segmented into regions by the function region (Figure 16(b)) and edges are extracted by the function edge (Figure 16(c)). The function edge means edge enhancement followed by binarization and produces a binary picture representing edge points. That is, the function edge itself stands for a sequential combination of two primitive image processing operators (functions) in the library: edge(D) = binary(sobel(D), threshold-value),
(1 1)
where sobel denotes a filtering operation to enhance edges and threshold-value may be given by the user or computed by other functions. Then, the results of edge-based and region-based segmentations are combined by the function edge-count. It enumerates the number of edge points in each segmented region and outputs the image where each pixel is given the number of edge points in the region to which it belongs. The function binarym performs binarization using the specified threshold (i.e., threshold in function (10)) and outputs a logical mask image. Finally, the
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
131
I
FIGURE17. Optimization of threshold: (a) image of very low contrast; (b) result of ordinary binarization, the threshold value was determined by Ohtsu’s (1979) method; (c) detected edge points; (d) result of the sophisticated binarization, the threshold value was determined by the parameter optimization operator.
areas specified by this mask, which denote regions including many edge points in their interiors, are analyzed by the function region again to segment such nonhomogeneous regions. In the example, the rotated L-shaped region in Figure 16(b) was regarded as nonhomogeneous and segmented into two small regions in Figure 16(d). As is seen in Figure 16(a), the contrast of the boundary between these two newly segmented regions is too low to be detected by the initial uniform region segmentation; i.e., by the first application of the function region to input image D. It should be noted that Figure 16(d) includes those homogeneous regions that were not processed by the last mask operation as well as the regions generated by function (10). Thus, to obtain Figure 16(d), we applied another function COMBINE that spatially combined (mosaicked) into one image both the newly segmented regions produced by function (10) and the homogeneous regions detected at the initial region segmentation. Figure 17 shows an example of the parameter optimization. It is usually difficult to determine the optimal threshold for binarization in an image of low contrast (Figure 17(a)). Figure 17(b) shows the result of binarization by
132
TAKASHI MATSUYAMA
using the threshold value determined by Ohtsu’s (1979) method, where most of the elliptic particles could not be detected correctly. An effective strategy to determine a better threshold value is to use spatial information; the threshold value in Ohtsu’s method was determined based only on the gray-level histogram. oPTrMIzE(binary(D,*), 40,60,2 BY edge(D) AT efuncl)
(12)
realizes the binarization strategy proposed by Milgram (1979). First, the function edge defined in (1 1) is applied to input image D to detect edge points (Figure 17(c)). The threshold-value in function (1 1) was determined by Ohtsu’s method. Then the evaluation function efuncl examines the consistency between the resulting edge image and the region boundaries obtained by the binarization operator, binary: how well the region boundaries coincide with the detected edge points. Function OPTIMIZE changes the threshold value from 40 to 60 by 2 and outputs the binary picture processed with the optimal threshold value determined by efuncl (Figure 17(d)). The third example is so-called coarse-to-fine image analysis. To use images of multiple, different resolutions is an effective image analysis strategy to realize the focus of attention mechanism (Rosenfeld, 1984). The analysis strategy based on multiresolution images is called coarse-to-Jne analysis and has been used for various purposes: edge detection, motion analysis, stereo matching, and so on. Figure 18 illustrates an example of the edge detection using multiresolution images. Figures 18(a) and (b) show an original noisy image and edge points detected from it respectively. MAsK(binary(sobel(D),threshold)
BY
enlarge(binarym(sobe1
(shrink(D)), threshold)))
(13)
realizes the plan-guided edge detection proposed by Kelly (1971). First the innermost function shrink is applied to input image D to reduce the size of the image, and edge points are extracted from the shrunken image by the function sobel followed by binarym. Note that the function sobel enhances edges and that the function binarym produces a logical mask to be used for the subsequent mask operation. Then the logical mask image representing the detected edge points is enlarged by the function enlarge. The enlarged image (Figure 18(c)) is used as the mask for detecting edge points in the original image. (The functions shrink and enlarge modify the size (resolution) of an image by 0.5 and 2.0, respectively.) In the last mask operation, the functions sobel and binary (i.e., binary(sobel(D), threshold)) are applied only for those pixels specified by the mask in Figure 18(c). The threshold in (13) refers to a given threshold value for the binarization. Figure 18(d) shows the output image by function (13). By recursively applying this plan-guided edge
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
133
FIGURE18. Plan guided edge detection: (a) noisy image; (b) result of ordinary edge detection; (c) mask image for detailed edge detection; (d) result of the plan guided edge detection.
detection, the analysis based on the pyramid data structure (Rosenfeld, 1984) (hierarchical multiresolution images) can be realized. As demonstrated in these examples, we can describe various sophisticated image analysis strategies by using the proposed combination functions, Their incorporation into ordinary image processing softwares and ESIPAs will greatly improve the performance of image analysis.
2. Representing Image Analysis Strategies in LL VE LLVE, described in Section ILG, uses the network structure to represent the knowledge about image processing (Figure 12). However, the input of each transfer process (i.e., an arc in the network) is limited to a single image feature and the process sequence executed is nothing but a sequential combination of transfer processes. In order to represent the heterogeneous combinations described previously, we have to incorporate transfer processes with multiple, different input image features. To represent such extended transfer processes, we introduced the knowledge representation using a hypergraph. A hypergraph is a generalized graph (network) consisting of a set of nodes and a set of hyperarcs. The generalization is in that, while an arc in a graph connects a pair of nodes, a hyperarc connects a node with a set of nodes.
134
TAKASHI MATSUYAMA
result combinablon
FIGURE19. Knowledge representation by a hypergraph.
We can use a hyperarc to represent a transfer process with multiple input image features. That is, each function for the heterogeneous combinations, COMBINE, MASK, and OPTIMIZE, is represented by a hyperarc in the hypergraph. In Figure 19, a hyperarc is illustrated by a set of directed arcs grouped by a circular line. For example, the result combination in function (10) can be represented by the hyperarc connecting Edge-Point and HomogeneousRegion to Mask-Picture, the mask operation in function (10) by the hyperarc connecting Gray-Picture and Mask-Picture to Homogeneous-Region, and the binarization (optimization) process by function (12) by the hyperarc connecting Gray-Picture and Edge-Point to Binary-Picture in Figure 19. As discussed earlier, the image analysis using multiple resolutions has proven a very effective image analysis strategy. However, all image features in LLVE are considered as at a single resolution. So we need to further extend its knowledge representation so that the image analysis based on multiple resolutions can be realized. One straightforward idea is to use a hierarchical hypergraph (Figure 20). Each level of the hierarchy stores a subhypergraph, representing the knowledge about image features and transfer processes at a certain resolution. Operations that change the resolution, such as shrinking or
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
135
resolution2
resolution1
FIGURE20. Hierarchical hypergraph.
enlargement of an image, are represented by transfer processes across the levels. However, since most image processing operators are defined independent of spatial resolution, subhypergraphs at different levels take the same structure. In order to eliminate this redundancy, we introduced into each image feature a parameter representing its resolution. For example, GrayPicture(s) denotes the image feature of Gray-Picture type at resolution s. Using such image features with the resolution parameter, we can compress the hierarchical hypergraph in Figure 20 into a single-layered parameterized hypergraph. Those transfer processes that change resolutions, i.e., those arcs across the levels in Figure 20, are represented by looping arcs in the parameterized hypergraph. Note that, while the (abstract) knowledge itself is represented by this single-layered parameterized hypergraph, it is instantiated and expanded into a multilayered (concrete) hypergraph by the search (reasoning) process. Figure 2 1(a) illustrates a parameterized hypergraph representing the analysis strategy for edge detection using multiple resolutions. Figure 21(b) shows an instantiated hypergraph with fixed resolution parameters, which was generated from the parameterized hypergraph in Figure 21(a). While Figure 21(a) represents the abstract knowledge, Figure 21(b) shows the heterogeneous analysis process to be executed. (As for the instantiation process see later.) While the network knowledge representation is LLVE is augmented to the
136
TAKASHI MATSUYAMA shrink
enlarge
(a)Parameterized hypergraph representing the image analysis strategy using multiple resolutions
(b)An instantiated hypergraph with fixed resolution parameters
FIGURE21. Instantiation of a parameterized hypergraph: (a) parameterized hypergraph representing the image analysis strategy using multiple resolutions; (b) an instantiated hypergraph with fixed resolution parameters.
hypergraph with resolution parameters, the other knowledge represented by a set of production rules need not be changed. We can use the same search method to reason about the most effective image analysis process. Note, however, that, while the original reasoning process only searches a connected path (process sequence) in the network, the new reasoning process should generate an instantiated hypergraph as well as search the parameterized hyper gr aph . Let us explain the process of instantiating the parameterized hypergraph
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
137
in Figure 21(a), the reasoning process using the hypergraph knowledge representation. When we are given an input image, the Gray-Picture(s) node in Figure 21(a) is instantiated and its resolution parameter is set to 1; that is, Gray-Picture(1) node is generated. Suppose the current goal is to find Edge-Point(1). Given such goal, Edge-Point(s) in Figure 21(a) is also instantiated to generate Edge-Point( 1) node. At this initial stage, the instantiated hypergraph consists of two isolated nodes: Gray-Picture( 1) and EdgePoint(]). LLVE searches the abstract hypergraph in Figure 21(a) to generate an instantiated hypergraph connecting these two nodes. The search and instantiation of Figure 21(a) are done as follows. Step 1. As described previously, Gray-Picture(1) and Edge-Point( 1) are generated first as seed nodes in the instantiated hypergraph. Step 2. The search in the parameterized hypergraph is started at the goal image feature node, Edge-Point(s) in Figure 21(a), and follows hyperarcs backward toward Gray-Picture(s). (This backward search is the same as that used in original LLVE.) In Figure 21(a), two incoming arcs (transfer processes) are attached to Edge-Point(s): enlarge and binarization. Step 3. Suppose a production rule associated with Edge-Point(s) prohibits the search process from following the former arc (i.e., enlarge). The rationale behind this rule is that to apply transfer process enlarge, process A in Figure 21(a) for the mask operation must be included in the already traversed path. In other words, transfer process enlarge must be used in connection with the mask operation represented by process A to realize the plan guided edge detection. This rule is realized by the transfer process selection rule listed in Table I. Step 4. The, the search process follows the binarization arc to Edge-Picture(s). At the same time, the search process instantiates Edge-Picture(s) to generate Edge-Picture( 1) node and connects it to Edge-Point( 1) via the binarization arc in the instantiated hypergraph. Step 5. There are two incoming arcs at Edge-Picture(s): a hyperarc representing process A and an ordinary arc representing edge detection (Figure 21(a)). Suppose we take the hyperarc representingprocess A . If we followed the other arc, the search would be terminated to generate the process sequence consisting of edge detection followed by binarization. Step 6. Since the selected hyperarc leads to both Gray-Picture(s) and MaskPicture(s), the search process has to follow these two paths (partial hyperarcs). First, the path leading to Gray-Picture(s) (denoted as P1 in Figure 21(a)) is terminated at this node, since the input data to be processed is stored at Gray-Picture( 1). (Gray-Picture( 1) has been already included in the instantiated hypergraph.) Then Edge-Picture( 1) node and Gray-Picture(1) node are connected by a partial hyperarc denoted by P1
138
TAKASHI MATSUYAMA
in the instantiated hypergraph. On the other hand, the search process traces the other path leading to Mask-Picture(s) (i.e., P 2 in Figure 21(a)) and instantiates Mask-Picture(s) to generate Mask-Picture( 1) node, which then is added to the instantiated hypergraph and is connected with Edge-Picture( 1) node. Step 7. Next, the search process traces the incoming arc at Mask-Picture(s) to visit again Edge-Point(s) node. Since process A has been included in the already traversed path (i.e., the instantiated hypergraph so far constructed), the enlarge process is selected by the transfer process selection rule associated with Edge-Point(s) (see Step 3). When transfer process enlarge is selected, a production rule associated with it is activated. This rule represents the dependency between transfer processes (i.e., the transfer process dependency rule in Table I). The knowledge represented by this rule is that to apply transfer process enlarge, transfer process shrink must be applied first: both of these transfer processes must be included sequentially in the instantiated hypergraph. Based on this knowledge, GrayPicture(# node and Edge-Point(+) node are generated and connected to Gray-Picture( 1) and Edge-Point( 1) by shrink and enlarge arcs in the instantiated hypergraph, respectively. Step 8. After applying the preceding transfer process dependency rule, the goal of the search is reduced to finding a path connecting Gray-Picture()) and Edge-Point()). Since this goal is exactly the same as the original one except the resolution, the same search process as above is conducted again in the parameterized hypergraph. Step 9. This time, suppose we take edge detection rather than process A at Step 5. Then, the search path from Edge-Point($) is terminated at GrayPicture(# via Edge-Picture(+), and the completely instantiated hypergraph in Figure 21(b) is constructed. If we took process A again, the resolution would be reduced to and the same search process would be repeated once again. By iterating such search, we could generate the image analysis process (instantiated hypergraph) based on the pyramid data structure.
+
Although the search process seems to be complicated, the search in hypergraphs is the same as that in AND-OR graphs (Nilsson, 1980). There have been developed many search algorithms for AND-OR graphs, so that we can use them for this search process. In summary, with the augmentations just described (i.e., hypergraph knowledge representation and introduction of the resolution parameter), LLVE could perform various types of heterogeneous combinations of primitive operators, which would substantially improve its image analysis capability. (These augmentations have not been implemented in LLVE.)
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
139
B. Cooperative Integration of Multiple Stereo Vision Algorithms As noted at the beginning of this section, ordinary ESIPAs involve two types of sequentialities: one at the object level and the other at the reasoning level. The former has been augmented by the heterogeneous combination operators described in Section 1II.A. In this section, we will discuss the latter problem and introduce a cooperative reasoning scheme for integrating multiple different stereo matching algorithms. Generally speaking, there are two different objectives in parallel-concurrent processing. One is, of course, fast computation, and the rate of speed-up is of primary concern. The other is the so-called distributed problem solving to develop more flexible and robust intelligent systems (Bond and Gasser, 1988). The flexibility and robustness are attained by cooperative interactions among parallel-concurrent reasoning agents. Each agent is an independent reasoning module with its own specific analysis and reasoning capabilities and specialized knowledge. During problem solving, agents exchange partial analysis and reasoning results to each other by communication. While the knowledge and input information of each individual agent is limited, it can conduct analysis and reasoning based on the information communicated from other agents. Thus a major interest of distributed problem solving is not in speed-up but in the development of sophisticated communication protocols to realize flexible cooperations among agents; i.e., cooperative integration of multiple reasoning agents. No cooperative integration among image processing operators was realized in the ESIPAs so far described although various types of primitive operators are combined to form complex image analysis processes. Ordinary combinations of operators can be compared to playing with toy blocks. While we can build a variety of complex-shaped objects (i.e., analysis processes) by combining blocks (i.e., operators), each block itself stays as is; its properties such as shape and color are not changed at all by the combination. On the other hand, what we mean by the cooperative integration can be compared to genetic surgery to fuse different types of biological cells. After the fusion, a new cell (i.e., analysis process) is born whose properties are different from those of its constituent cells (i.e., operators). The properties of the constituent cells are mixed and inherited to the new cell. As is clear from these metaphors, the cooperative integration is quite different from the combination and enables us to realize new analysis and reasoning capabilities. In this section we describe a cooperative image analysis for stereo vision and later in Section 1V.D a cooperative spatial reasoning for image understanding. Watanabe and Ohta (1990) proposed a cooperative integration of multiple stereo vision algorithms. A major problem in stereo vision is how to make
140
TAKASHI MATSUYAMA TABLE I1 CHARACTERISTICS OF THE THREE STEREO MATCHING ALGORITHMS ~
Image feature
~~
Application range
~
~~~~~
Accuracy of correspondence
Characteristics
~~~~
Point-based Interval-based Segment-based
Interesting points Intervals on the scanline Connected edge elements ~
Source: Watanabe and Ohta,
0
A
Textural part
A
0
X
A
Intra-scanline consistency Inter-scanline consistency
~~~~~~
01990 IEEE
correspondence between points in the left and right images. Once the correspondence is established, the three-dimensional depth (distance from the camera) of the corresponding point can be calculated easily. Although various matching algorithms for stereo vision have been developed, none of them works perfectly for complicated scenes. This is because the structure of one image can be very different from that of the other due to mutual and self-occlusions among three-dimensional objects. The idea in Watanabe and Ohta (1990) for realizing reliable stereo matching is to execute different stereo matching algorithms in parallel and integrate their results. The difference between this method and the COMBINE operator described in Section I1I.A. 1 is that in the former multiple algorithms make interactions during execution, while in the latter multiple operators are applied independently without any interaction. That is, the integration in the former is done among algorithms, while that in the latter among analysis results by independent algorithms. The following three stereo matching algorithms were used: Point-Based Matching. Using small windows centered at prominent edges in the left and right images as templates, apply template matching to find a pixel location with the highest correlation value. Interval-Based Matching. Using a dynamic programming technique, conduct matching between intervals delimited by edges on the corresponding left and right horizontal scan lines. Segment-Based Matching. Make correspondence between connected edge segments extracted from the left and right images using their geometric properties and gray-level contrast along the edges. Table I1 summarizes the characteristics of these three methods. It shows that they complement each other. Thus, integrating these complementary
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
Algorithm A results of algorithm A
rules for *-
communi-
query uer
% answer r x 4
rules for communication
.
141
Algorithm B results of algorithm B
FIGURE 22. Internal structure of cooperative reasoning modules (from Watanabe and Ohta, 01990 IEEE).
algorithms, a more reliable matching process can be realized; the drawbacks of one algorithm can be compensated by the others. The integration among these algorithms is realized by the following cooperative interaction among reasoning modules. 1. For each algorithm, a reasoning module is implemented as a concurrent process. It analyzes given stereo images by applying its own algorithm, and the analysis result is stored in it as its private information. Thus, the same input stereo images are analyzed by a group of modules in parallel. Figure 22 illustrates the internal structure of cooperative reasoning modules. 2. When a module finds ambiguity in matching at a certain location, it asks the other modules for their analysis results at that location. Using the information given by the others, the module resolves the ambiguity. Since the protocol for such communication between the modules depends on applications, each module stores a set of production rules to represent the knowledge about the mutual communication (Figure 22). With such rules, various types of interactions among the modules can be realized: determination of the applicability of a specific algorithm, adjustment of parameters of an algorithm, complementation of imperfect analysis result, as well as the resolution of ambiguity described previously. In short, the declarative knowledge used in this ESIPA is about the mutual communication-interaction among image analysis processes. (Analysis algorithms are fixed and described procedurally .) 3. Each module must conduct the analysis to reply requests given from the others as well as the matching for its own purpose. Moreover, multiple requests may be issued simultaneously. Thus, a module itself consists of multiple concurrent subprocesses; when a request is given, the module generates a new subprocess to conduct analysis and reply to the request. 4. Besides three modules for stereo matching, the system includes the disparity map generation module (Figure 23). This module accumulates all partial results produced by the matching modules. When a new correspondence is established, each matching module informs it to the
142
TAKASHI MATSUYAMA
Results on
matching module
matching module Information
of occulusion
matching module Results on segments
FIGURE23. Module organization in the cooperative integration of stereo vision algorithms (from Watanabe and Ohta, 0 1 9 9 0 IEEE).
disparity map generation module. Each correspondence is associated with a numerical value representing its reliability as well as the spatial location and the depth information. The disparity map generation module computes the overall reliability and the global disparity map based on the partial information given from the matching modules. Note that the processing done by this module is the same as the combination of multiple analysis results. According to Watanabe and Ohta (1990), a considerable amount of improvement was attained by the cooperative integration. However, since only a few studies on distributed problem solving has been done in computer vision and image understanding, more intensive researches should be done on the following problems:
More Sophisticated Scheme for Interaction. In the preceding system, the interaction among analysis modules is specified by production rules. Although such declarative specification is useful, the implemented interaction scheme is very primitive; only point-to-point communication (i.e., one module makes a request to a specific module) was realized. We should investigate more sophisticated interaction schemes such as broadcasting and multiparty interaction (Bond and Gasser, 1988) to develop distributed computer vision systems. Well-Defined Reliability Computation Method. In integrating multiple partial analysis results, numerical values representing their reliabilities are often used. However, many heuristics and ad hoc rules are implicitly used for the evaluation and integration of reliability values. We should study welldefined mathematical foundations like Dempster-Shafer’s evidence theory (Shafer, 1975) for the reliability computation and integration.
IMAGE PROCESSING, ANALYSIS, A N D RECOGNITION
143
IV. REPRESENTING SPATIAL RELATIONS AND SPATIAL REASONING FOR IMAGEUNDERSTANDING In general the information used for visual recognition can be classified into the following two types:
Attributes: intrinsic properties such as brightness, color, textures, location, shape and so on. ReZations: spatial relation, temporal relation, and semantic relations like causal and generalization-specialization relations. Recognition based on object’s attributes have been studied extensively in statistical pattern recognition, in which the knowledge about objects is represented by probabilistic distribution functions. On the other hand, a major research goal of image understanding is the analysis and reasoning based on the relational information. With the introduction of relational information, limitations of statistical pattern recognition can be removed. For example, relaxation labeling and constraint filtering are useful relationbased analysis methods to resolve ambiguities and remove errors in the attribute-based recognition (Ballard and Brown, 1982; Binford, 1982; Brooks, 1981). Since the geometry is an important axis defining the visual world, spatial reasoning, reasoning based on spatial relations, is a crucial function in image understanding. In this section, we first present an overview of various schemes of representing spatial relations8 and spatial reasoning methods for image understanding. In the latter half of the section, we discuss the knowledge representation and reasoning based on PART-OF relations, spatial composition relations, and introduce ESIPAs for the recognition of complex objects with internal structures.
A . Knowledge Representation in Logic Based on Topological Relations Topological relations, such as adjacency, intersection, and inclusion, have been often used in IUSs to represent spatial relations among image features and scene objects (Ohta, 1985; Rubin, 1980). They also play an important role in describing structures of complex-shaped objects (e.g., the winged edge model for three-dimensional objects; Ballard and Brown, 1982). Such popular utilization of topological relations can be ascribed to their clear semantics; even in digital images, we can rather easily define and analyze topological relations between image features. We use spatial relations in a general sense and geometric relations to denote specific spatial relations involving metric information.
144
TAKASHI MATSUYAMA
With well-defined topological relations, we can represent the knowledge for image understanding in a formal way. The most formal declarative knowledge representation scheme would be mathematical logics. (See Genesereth and Nilsson, 1987, for utilizations of mathematical logics for artificial intelligence.) Reiter and Mackworth (1989) uses first-order predicate calculus to represent the knowledge for image understanding. Specifically, the knowledge is represented by three types of logical axioms: scene axioms for the scene domain knowledge, image axioms for the image domain knowledge, and depiction axioms for the knowledge about the mapping between the scene and image. (As for the knowledge used in IUSs, see Section 1I.B.) The task of their system is to interpret a given line drawing as a map; that is, to recognize line segments and regions as rivers, roads, shores, land, and water areas. First, image axioms, the knowledge about semantic definitions of primitive image features are described in terms of logical formulae as follows: (Vx)image-feature(x) = line-segment(x) v region(x)
(14)
(Vx) i [line-segment(x) A region(x)J,
(15)
where = and i stand for logical equivalence and negation, respectively. These axioms imply that there are two types of image features, line-segment and region, and they are mutually exclusive. To describe the structure of a given line drawing, first, connected line segments and regions are extracted from the line drawing. Then their types and topological relations among them are described using the following logical formulae: (Vx)line-segment(x) = x
=
I,
(Vy)region(y) = y = r , v y
v x = I, v . . . v x = 1, = rz
... v y = I, . . . v (x = I, A y
= ( x = l, A y = r,,) v (Vx,y)chi(x,y) = (x = I, A y = I,.) v . . . v
(Vx,y)bound(x,y)
(16)
v
(x = 1,
A
y
= r,)
=
1,)
-
-
(17) (18) (19)
The first and second formulae imply that logical constants I, (i = 1 n ) and r, ( j = 1 m) denote line segments and regions, respectively. The third and fourth formulae describe topological relations between line segments and regions; predicate bound(x,y) means that line segment x is on the boundary of region y and c h i ( x , y ) that two line segments x and y intersect each other. The knowledge about the scene, in this case, the map, is described in the same way. First, categories of scene objects are defined as follows.
(VX)SCENE-OBJECT(X)
= ROAD@)
v RIVER(X) v SHOFE(X) v LAND(X) v
WATER(X)
(20) ( V X ) l [ROAD(X) A RIVER(X)]
(2 1)
IMAGE PROCESSING, ANALYSIS, AND RECOGNITION
145
( v X ) l [RIVER(X) A SHORE(X)]
(22)
(VX) 1(LAND(X) A WATER(X)].
(23) Then, the knowledge about topological relations between scene objects is described using predicates like CROSS and LOOP. (Vx,~)RIVER(X) A
RIVER(
CROSS(X, y )
(24)
+ LOOP(X)
(25)
+ 1LOOP(X)
(26)
(VX)SHORE(X)
(VX)RIVER(X)
y ) -+ i
Note that predicates representing image domain categories and relations are in lowercase letters while those representing the scene domain knowledge in capital letters. As discussed in Section II.B, for correspondence between image features and scene objects, the knowledge about the mapping between the scene and image domains is required. Such knowledge can also be described by logical formulae as follows: (Vx)image-feature(x) -+ SCENE-OBJECT(O(X)) A ((VY)A(X,
Y> Y = 4x)) +
A
A(x, a(x))
(27)
Here, (r stands for the mapping function which transforms image domain entities into scene domain entities, and predicate A(x, y ) implies that image feature x corresponds to scene object y. That is, interpretation, correspondence between the image and the scene, is represented by this function and relation. It should be noted that the preceeding formula just represents general knowledge about the mapping. We must prove for each logical constant representing an image feature (e.g., I,) which of ROAD(CT(~,)) A A(Z!,a(&)), RIVER(CT(~~)) A A((, a(l,)), or SHORE(O(Z,)) A A(l,,a(l!)) is the logical consequence of all sets of given axioms. (A line segment is to be recognized as