Real-Time Parallel Computing : Image Analysis

This book is concerned with the aspects of real-time, parallel computing which are specific to the analysis of digitized images including both the symbolic and semantic data derived from such images. The subjects covered encompass processing, storing, and transmitting images and image data. A variety of techniques and algorithms for the analysis and manipulation of images are explored both theoretically and in terms of implementation in hardware and software. The book is organized into four topic areas: (1) theo­ retical development, (2) languages for image processing, (3) new computer techniques, and (4) implementation in special purpose real-time digital systems. Computer utilization, methodology, and design for image analy­ sis presents special and unusual problems. One author (Nagao)* points out that, "Human perception of a scene is very complex. It has not been made clear how perception functions, what one sees in a picture, and how one understands the whole picture. It is almost certain that one carries out a very quick trial-and-error process, starting from the detection of gross prominent features and then analyzing details, using one's knowledge of the world. " Another author (Duff) makes the observation that, "It is therefore more difficult to write computer programs which deal with images than those which deal with numbers, human thinking about arithmetic being a largely conscious activity.

General Theory.- The Elements of Digital Picture Processing.- 1. Introduction.- 2. Unary and Binary Operations.- 3. Higher Order Operations.- 4. Serial or Parallel Processing.- 5. Propagation.- 6. Conclusions.- 7. References.- Some Neighborhood Operators.- 1. Introduction.- 2. Region Growing Operator.- 3. Nearest Neighbor Sets.- 4. Region Shrinking Operators.- 5. Mark Interior Border Pixels.- 6. Connectivity Number Operator.- 6.1 Yokoi Connectivity Number.- 6.2 Rutovitz Connectivity Number.- 7. Connected Shrink Operator.- 8. Pair Relationship Operator.- 9. Thinning Operator.- 10. Distance Transformation Operator.- 11. Contact Distances.- 12. Non-Minima-Maxima Operator.- 13. Relative Extrema Operator.- 14. Connected Components Operator.- 15. Reachability Operator.- 16. Conclusion.- 17. References.- Region Relaxation in a Parallel Hierarchical Architecture.- 1. Introduction.- 1.1 The Need for Parallelism.- 2. A Parallel Hierarchical Architecture.- 2.1 Modes of Processing and Algorithm Specification.- 2.2 Reductions: Upward Processing within the Cone.- 2.3 Horizontal (Lateral) Processing: At a Fixed Level in the Cone.- 2.4 Projection: Processing Information Downward in the Cone.- 3. The Processing Cone as an Operating System for Image Analysis.- 4. Segmentation Algorithms and Applications.- 4.1 Glaucoma.- 4.2 Image Analysis Using Histogram Cluster Labels.- 4.3 Refinement of Initial Labeling Using Spatial Relaxation.- 4.4 Segmentation Algorithm Applied to a Natural Image.- 5. Localization.- 5.1 Region Merging.- 5.2 Results of Localization.- 6. Conclusion.- 7. Acknowledgements.- 8. References.- Generalized Cellular Automata.- 1. Introduction.- 2. One-Dimensional Cellular Automata.- 3. Multi-Dimensional Cellular Automata.- 4. Cellular Pyramids.- 5. Memory-Augmented Cellular Automata.- 6. Cellular Graphs.- 7. Concluding Remarks.- 8. Acknowledgements.- 9. References.- Theoretical Considerations on a Family of Distance Transformations and Their Applications.- 1. Introduction.- 2. Basic Definitions.- 3. Distance Transformation by Variable Operators (VODT).- 3.1 Distance Transformation by Variable Operators (VODT).- 3.2 DTLP (Distance Transformation of Line Pattern).- 3.3 The LMDT and Its Skeleton.- 4. Generalized Grey Weighted Distance Transformation (GGWDT).- 4.1 GGWDT and IGGWDT.- 4.2 Decomposition of Pictures by the GGWDT and Iterative Application of the GWDT.- 5. Conclusion.- 6. Acknowledgement.- 7. References.- Languages.- Image Data Modeling and Language for Parallel Processing.- 1. Introduction.- 2. Structure Lines.- 3. Requirements for Feature Retrieval.- 4. Language Requirements for Parallel Image Processing.- 5. A Language for Parallel Processing with Non-Deterministic and Recursive Features.- 6. Conclusion.- 7. Acknowledgements.- 8. References.- A Study on Parallel Parsing of Tree Languages and Its Application to Syntactic Pattern Recognition.- 1. Introduction.- 2. Parallel Parsing of Tree Languages.- 2.1 Tree Grammars.- 2.2 Lexical Analyzer for Tree Grammars.- 2.3 Parallel Parsing of Tree Languages.- 2.4 Simulation Results.- 3. Road Recognition by Using an Error-Correcting Tree Automaton.- 3.1 Primitive Selection.- 3.2 Grammar Construction.- 3.3 Road Recognition.- 4. Conclusions.- 5. Acknowledgements.- 6. References.- PIXAL: A High Level Language for Image Processing.- 1. Introduction.- 2. Basic Features of the PIXAL Language.- 2.1 Declaration.- 2.2 Parallel Statements.- 2.3 Global Assignment.- 2.4 Composition of Sequential and Parallel Operations.- 2.5 Built-In Functions.- 3. Implementation Considerations.- 4. Final Comments.- 5. References.- Languages for Parallel Processing of Images.- 1. Introduction.- 2. Languages for Image Analysis.- 3. Languages Associated with Parallel Processors.- 3.1 MORPHAL.- 3.2 CAP4.- 3.3 C3PL.- 3.4 DAP FORTRAN.- 3.5 GLOL.- 3.6 PPL.- 3.7 Other Languages.- 4. Examples of Use.- 5. Conclusions.- 6. References.- Techniques.- Real Time Region Analysis for Image Data.- 1. Introduction.- 2. Region Segmentation.- 2.1 Properties of Images and Regions.- 2.2 Spatial Clustering Algorithm.- 3. Picture Processing Firmware.- 3.1 Characteristics of Firmware.- 3.2 Support Software.- 3.3 Evaluation of Picture Processing Firmware.- 4. Application of Image Data.- 5. Conclusions.- 6. Acknowledgements.- 7. References.- Hybrid Image Processing Using a Simple Optical Technique.- 1. Introduction.- 2. Interactive Image Processing System.- 3. Adaptive Binarization Using Hybrid Processing.- 3.1 Mathematical Analysis.- 3.2 Optical Implementation.- 4. Contrast Improvement and Feature Extraction by Hybrid Processing.- 4.1 High Voltage Electron Microscope Images.- 4.2 Extraction of Dislocation Lines.- 5. Constant Variance Enhancement by Hybrid Processing.- 6. Conclusion.- 7. References.- Focus of Attention in the Analysis of Complex Pictures Such as Aerial Photographs.- 1. Introduction.- 2. Selective Area Analysis.- 2.1 Use of Context in Target Detection.- 2.2 Planning Methods for Focusing Attention.- 2.3 Application of Edge Preservation Smoothing...- 3. Conclusions.- 4. References.- The Virtual Plane Concept in Image Processing.- 1. Introduction.- 2. Virtual Tape.- 3. Virtual Plane.- 4. Implementation of the V-Plane Concept.- 5. Conclusions.- 6. Acknowledgements.- 7. References.- Hardware and Systems.- A Multi-Microprocessor Architecture for Associative Processing of Image Data.- 1. Introduction.- 2. Principle of Association.- 3. Associative Processing in a Semantic Data Base.- 4. Multi-Microprocessor ARES.- 4.1 Functional Configuration.- 4.2 Cell Structure.- 4.3 Multiple Response Resolver.- 4.4 Distribution of Data in a Semantic Data Base.- 5. Evaluation of the Optimum Number of Cells.- 6. Conclusion.- 7. Acknowledgements.- 8. References.- An Interactive Image Processing and Analysis System.- 1. Introduction.- 2. Interactive Image Processing and Analysis Systems.- 2.1 Man-Machine Interaction.- 2.2 Speeding Up Processing.- 2.3 Flexibility.- 2.4 Cost Reduction.- 2.5 Summary.- 3. An I2PAS at NEC/CRL.- 3.1 Color Image Display.- 3.2 Computer and Peripherals.- 3.3 Software and Applications.- 4. Future Developments.- 5. Conclusion.- 6. Acknowledgement.- 7. References.- Interpolation to Reduce Difficulty in D/A Conversion.- 1. Introduction.- 2. Interpolation of Samples.- 3. Estimation of the Value to be Interpolated.- 4. Implementation of the Interpolator.- 5. Experimental Result.- 6. Conclusion.- 7. References.- A Computing System Organization for Image Data Retrieval.- 1. Introduction.- 2. System Organization.- 2.1 The ARES for Associative Search of Semantic Data Bases.- 2.2 The ELPIS for Image Feature Extraction.- 3. Image Feature Extraction Facility.- 3.1 Feature Extraction by Content Addressing.- 3.2 Control of Detailed Fineness.- 4. Concluding Remarks.- 5. Acknowledgements.- 6. References.- A Compound Computer System for Image Data Processing.- 1. Introduction.- 2. Shared Intelligent I/O Controller (ETOILE).- 2.1 Programmable I/O Controller.- 2.2 Host-Controller Communication Facility.- 2.3 I/O Peripherals.- 2.4 User-Friendly Interface (UFI).- 2.5 The ETOILE Supervisor.- 2.6 Subsystems.- 3. Image Data Base.- 3.1 System Overview.- 4. Special-Purpose Processor.- 4.1 Structure of Special-Purpose Processor.- 4.2 Parallel Processing Schemes.- 5. Conclusion.- 6. Acknowledgements.- Interactive Techniques for Producing and Encoding Color Graphics.- 1. Introduction.- 2. Interactive Production of Color Graphics.- 2.1 Input of Line Drawings.- 2.2 Trimming Lines.- 2.3 Detection of Uncolored Closed Areas.- 2.4 Coloring.- 2.5 Outline of the Experimental System.- 3. Encoding of Color Graphics.- 3.1 Color Run-Length Coding.- 3.2 Boundary Coding.- 4. Concluding Remarks.- 5. References.- Image Processing Unit Hardware Implementation.- 1. Introduction.- 2. Design Concepts.- 2.1 Image Data Hierarchies.- 2.2 Important Image Processing Functions.- 2.3 Local Parallel Operations.- 2.4 Flexible Control.- 2.5 Word Length.- 3. Hardware Implementation.- 3.1 Microprogram Control and ALU.- 3.2 Address Control.- 3.3 Data Memory and Table Memory.- 3.4 Spatial Filtering.- 3.5 Fast Transform with Multiplier and Adder.- 3.6 Logical Filtering.- 3.7 Region Labeling.- 4. Software Implementations and Applications.- 4.1 Functional Commands for the IPU.- 4.2 Microprograms in the IPU.- 4.3 Applications.- 5. Conclusion.- 6. Acknowledgements.- 7. References.- Man-Machine Interactive Processing for Extracting Meteorological Information from GMS Images.- 1. Introduction.- 2. GMS Cloud Top Height Estimation System.- 2.1 Basic Equation.- 2.2 Basic Parameters.- 2.3 Conversion to Cloud Top Height.- 2.4 System Configuration and Function.- 3. GMS Cloud Wind Estimation System.- 3.1 GMS Cloud Wind Estimation System.- 3.2 Registration of Images.- 3.3 Wind Derivation.- 3.4 Quality Control in the CWES System.- 3.5 Delivery and Archiving.- 4. References.- An Array Processor for Image Processing.- 1. Introduction.- 2. Design Principles.- 2.1 The Memory Unit.- 2.2 The Processing Unit.- 2.3 The Array.- 2.4 The Processing Element.- 2.5 Programming.- 3. System Construction.- 3.1 System Outline.- 3.2 Control Memory.- 3.3 Central Processing Unit.- 3.4 Micro Instruction Controller.- 3.5 Picture Memory.- 3.6 Processing Element Array.- 3.7 Local Register.- 3.8 Input Output Controller.- 4. Parallel Processing.- 4.1 Processing Element.- 4.2 Data Supply to the Processing Element Array.- 4.3 Processing Element Array Execution Mode.- 5. Examples.- 5.1 Thresholding.- 5.2 Filtering.- 6. Conclusion.- 7. Acknowledgements.- 8. References.- Real-Time Shading Corrector for a Television Camera Using a Microprocessor.- 1. Introduction.- 2. Hardware Configuration.- 2.1 Operational Details.- 2.2 Correction Mode.- 3. Operation Flow.- 4. Conclusion.- 5. Acknowledgement.- 6. References.- Parallel Architectures for Image Processing.- 1. Introduction.- 2. The Binary Image.- 3. Binary Image Transforms.- 3.1 Geometric Transforms.- 3.2 Logical Transforms.- 3.3 Dilation and Erosion.- 3.4 General Comparison.- 4. Hardware Implementation.- 4.1 Optomechanical Model.- 4.2 Binary Cell Arrays.- 4.3 Computational Efficiency.- 4.4 Window Configurations.- 5. Array Architectures.- 5.1 Pipelined Processor.- 6. Conclusion.- Color Display for Image Processing with Multiple Functions.- 1. Introduction.- 2. Design Principles.- 2.1 Multiple Image Storage in the IC Memory.- 2.2 Arithmetic Operations on Each Picture Element.- 2.3 Access to the Displayed Data.- 2.4 Access from Multiple Computers.- 3. System Configuration.- 4. Utilization of Image Memory.- 5. Capabilities.- 5.1 Data Input and Output.- 5.2 Switching of Monitors.- 5.3 Pseudocolor Display.- 5.4 Mosaic Display.- 5.5 Display of Moving Images.- 5.6 Roll-up.- 5.7 Joystick.- 5.8 Vector Display.- 5.9 Character Display.- 5.10 Pointer Display.- 5.11 Variable Display Range.- 5.12 Arithmetic Operations.- 5.13 Image Input.- 6. Conclusion.- Image Processing Oriented Multiprocessor System with a Multipurpose Video Processor.- 1. Introduction.- 2. Interconnection Structure and Organization of the System.- 3. Intelligent Coupler and Implementation of Parallel Processing.- 4. Function and Organization of the Video System.- 5. Conclusion.- 6. Acknowledgements.- 7. References.- Author Index.