Data Structures, Computer Graphics, and Pattern Recognition (eBook)

Front Cover 1
Data Structures, Computer Graphics, and Pattern Recognition 4
Copyright Page 5
Table of Contents 6
List of Contrib utors 12
Preface 14
PART I: FUNDAMENTAL METHODOLOGY 16
Chapter 1. Data Structure Design 18
1. Levels of Data Refinement 18
2. An Example of Stepwise Data Structure Design 19
3. Research Activities 25
4. Other Descriptions of Data Levels 31
5. A Second Example of Data Description by Levels 35
6. Conclusions 38
Problems 41
References 43
Chapter 2.The Concise Structuring of Geometric Data for Computer Aided Design 46
I. Introduction 46
II. Shape Descriptions 48
III. Shape Instantiation 52
IV. A Quantitative Formulation 54
V. The Structuring of BDS 59
VI. Summary 69
Study Questions 69
References 71
Chapter 3. Data 
74 
Abstract 74
Algorithms 75
Data-Structures 86
Language Comparison 87
Pascal Data-Structures 89
Pascal Program for Noisy Template Matching 95
Exercises 113
References 115
Chapter 4. Organizing Data in Computer Graphics Applications 118
Introduction to Chapter 118
A. 
120 
Abstract 120
1. Introduction to the Data Structure Problem in Computer Graphics 120
2. Types of Data Structures 123
3. Languages for Creating and Manipulating Data Structures 135
4. Computer Graphics Systems and Their Data Structures 143
5. Summary and Conclusions 155
6. Bibliography 157
B. On the Application of Relational Data Structures in Computer Graphics 168
Abstract 168
1. Introduction 168
2. Inherent Problems in Computer Graphics 169
3. Relational Data Bases 171
4. Relational Structures in Computer Graphics 172
5. Graphical Operations Using Relational Structures 176
6. A Geographical Data System Example 177
7. Conclusions 178
References 180
C. Data Structures in Computer Graphics 182
1. Introduction 182
2. The Concept of Picture-Building 183
3. Data Definitions 184
4. Data Specification and Manipulation 185
5. Environment of Picture Building System 189
6. Conclusions 190
Exercises Relating to Structuring of Graphical Data 191
References 192
Chapter 5. Some Observations on Linguistics for Scene Analysis 194
Abstract 194
Introduction 194
Algorithms vs. Biological Solution to the Pattern Recognition Problem 196
The "Two Worlds" of Pattern Recognition 196
The Problem 199
More on the Problem 200
Some Thoughts on Segmentation, Recognition and a Picture Language for Single Gray Level Pictures of 
203 
Comment 206
Conclusions 207
Research Problems 207
Appendix A: Feature Combinations 209
Appendix B: Eye Motion during Observation of Pictures 213
Appendix C: Effects of Brain Damage and Incomplete Development 217
Appendix D: A Simplified Picture Language 218
References 220
Additional Reading 223
PART II: DESIGN DECISIONS 226
Chapter 6. Data Management and Pattern Recognition 228
Abstract 228
1. Introduction 228
2. A Basis for Theoretical Study 229
3. Properties of a Pattern Definition Language 230
4. An Example of Pattern Definition Language 231
5. Preprocessing and Self-Organizing Data Management 233
6. Costs 234
7. Total Cost Definition Graphs 235
8. Expected Cost of a Family of Preprocessed Pattern Definitions 238
9. An Example of Expected Cost after Preprocessing 241
10. A Simple Model of When to Preprocess 242
11. Projection of User Needs: Incomplete Definition Trees 244
12. Expected Total Number of Runs As a Figure of Merit for Preprocessing 247
13. Preprocessors As Adaptive Systems 249
14. Conclusions 251
References 252
Chapter 7. The Design of Satellite Graphics Systems 254
1. Why Satellite Graphics? 254
2. Design Problems and Goals 256
3. Program Structures 259
4. Fixed Function Satellites 261
5. Programmable Satellites 271
6. The Hardware Configuration 282
7. Conclusions 283
References 285
Chapter 8. Interactive Image Segmentation: Line, Region and Semantic Structure 288
Abstract 288
Introduction 288
Overall Segmentation Strategy 292
System Configuration 293
Region Growth 296
Line Growth 302
Image Data Base 306
Region and Line Refinement 308
Preliminary Implementation Results 311
Conclusions 320
References 321
Chapter 9. Interactive Audio-Graphics for Speech and Image Characterization 324
Introduction 324
Data Characterization 327
System Configuration 332
Subsystem Architecture 339
Applications 345
Problems 387
References 391
PART III: RESEARCH ASPECTS 398
Chapter 10. Modifying Graphics Images 400
Abstract 400
1. Introduction 401
2. Language Specification 404
3. Sketch Implementation 418
4. Conclusions 423
References 426
Chapter 11. Surface Representation for Computer Aided Design 428
Abstract 428
1. Introduction 428
2. Tensor Products 428
3. Coons Patches 435
References 440
Chapter 12. Automatic Detection of Suspicious Abnormalities in Breast Radiographs 442
Preliminary Preparation 443
Breast Tissue Outlining 444
Breast Partitions 445
Texture Statistics 446
Feature Selection 449
Classification 453
Results 455
Data Structure 457
Conclusions 457
Exercises 459
Answers 460
References 462
Chapter 13. Error-Correcting Parsing for Syntactic Pattern Recognition 464
I. Introduction 464
II. Min-Distance Error-Correcting Parser As a Syntactic Pattern 
466 
III. Stochastic (Maximum-Likelihood) Error-Correcting 
474 
IV. Transition Network Grammar - 
482 
V. Relationships between TNG and Chomsky's Hierarchy 486
VI. Stochastic Transition Networks 492
VII. Error-Correcting Syntax Analysis for TNG 493
Appendix 500
References 506
Index 508