Pattern Recognition and Image Processing in C++

Parts of this text were used for several years by students in a one~term under­ graduate course in computer science. The students had to prepare projects in small groups (2~4 students).1 This book emphasizes practical experience with image processing. It offers a comprehensive study of • image processing and image analysis, • basics of speech processing, • object~oriented programming, • software design, • and programming in C++. The book is divided into four parts. In the first part we introduce image processing, image analysis, programming tools, and the basics of C++. In the second part we describe object~oriented programming in general and the possible applications of object~oriented concepts in C++. Several appli­ cations of object~oriented programming for image processing are discussed as well. The new features of C++ are introduced entirely through the use of examples. We cover the proper representation of the data that is a result of pattern analysis as well. The third part describes a complete system for image segmentation. Some of the material covered refers to the exercises found in the first and second parts: this verifies our belief that an image segmentation system of programs can be developed while simultaneously acquainting others to C++. We combine the data representation described in the second part with the algorithms that use and manipulate them here in the third part.

I Introductions.- 1 Pattern Recognition.- 1.1 Images and Sound.- 1.2 Applications of Pattern Recognition.- 1.3 Environment, Problem Domain, and Patterns.- 1.4 Characterization of Pattern Recognition.- 1.5 Recording of Speech Signals.- 1.6 Video Cameras and Projections.- 1.7 From Continuous to Digital Signals.- 1.8 Sampling Theorem in Practice.- 1.9 Visualization and Sound Generation.- 2 From C to C++.- 2.1 Syntax Notation.- 2.2 Principle of C++ Compilation.- 2.3 Function Calls and Arguments.- 2.4 Declaration and Definition of Variables.- 2.5 Unix-File Access via Standard Functions.- 2.6 Formatted Input and Output.- 2.7 Main Program.- 2.8 Preprocessor Directives.- 2.9 Conditional Compilation.- 3 Software Development.- 3.1 Software for Pattern Recognition.- 3.2 Principles of Software Development.- 3.3 Modular and Structured Programming.- 3.4 Comments and Program Layout.- 3.5 Documentation.- 3.6 Teamwork.- 3.7 Efficiency.- 3.8 Tools for Software Development with Unix.- 3.9 PUMA.- 4 Expressions, Statements, Functions.- 4.1 Instructions and Expressions.- 4.2 Logical Values and Conditionals.- 4.3 Function Definition.- 4.4 Loops.- 4.5 Declarations and Scope.- 4.6 Switches.- 4.7 Linkage.- 4.8 Programming with Modules.- 4.9 Control Structures.- 5 Classification and Pattern Analysis.- 5.1 Classification.- 5.2 Preprocessing.- 5.3 Feature Extraction.- 5.4 Analysis.- 5.5 Image Segmentation.- 5.6 Speech Segmentation.- 5.7 Pattern Understanding.- 5.8 Active Vision and Real Time Processing.- 5.9 Top-Level Loop for Speech Analysis.- 6 Arrays and Pointers.- 6.1 Vectors and Matrices.- 6.2 Pointers.- 6.3 Vectors vs. Pointers.- 6.4 Vector Initialization.- 6.5 Strings.- 6.6 Pointers Operations and Allocation.- 6.7 Pointer and Array Arguments.- 6.8 Pointer to Pointer.- 6.9 Main Function Arguments.- 7 Statistics for Pattern Recognition.- 7.1 Axioms.- 7.2 Discrete Random Variables.- 7.3 Continuous Random Variables.- 7.4 Mean and Variance.- 7.5 Moments of a Distribution.- 7.6 Random Vectors.- 7.7 Statistical Features and Entropy.- 7.8 Signal-to-Noise Ratio.- 7.9 Histograms.- 8 C++ as a better C.- 8.1 Type Declaration.- 8.2 Type Conversion for Pointers.- 8.3 Bit- and Shift-Operations.- 8.4 Type Specifiers and Variable Declaration.- 8.5 Type-Safe Linkage.- 8.6 Overloaded Function Names.- 8.7 Return Value and Arguments.- 8.8 Macros and Inline Functions.- 8.9 Function Pointers.- II Object-Oriented Pattern Analysis.- 9 Object-Oriented Programming.- 9.1 Object-Oriented Software Techniques.- 9.2 Basic Concepts.- 9.3 Data Abstraction and Modules.- 9.4 Inheritance.- 9.5 Abstract Classes.- 9.6 Object-Oriented Classification.- 9.7 Polymorphism.- 9.8 Other Object-Oriented Concepts.- 9.9 Class Libraries.- 10 Classes in C++.- 10.1 Structures.- 10.2 Methods and ADT’s.- 10.3 Class Declarations.- 10.4 Object Construction.- 10.5 Destruction of Objects.- 10.6 Overloaded Operators.- 10.7 Advanced Methods and Constructors.- 10.8 Vector Class.- 10.9 Class Design.- 11 Intensity Images.- 11.1 Array Class.- 11.2 Templates in C++.- 11.3 Images.- 11.4 External Data Formats.- 11.5 Binary Images.- 11.6 Color Images.- 11.7 Sub Images.- 11.8 Image Transformation and Registration.- 11.9 Neighborhood.- 12 Inheritance in C++-Classes.- 12.1 Motivation and Syntax.- 12.2 Base Class Access.- 12.3 Construction and Destruction.- 12.4 Pointer to Objects.- 12.5 Virtual Functions.- 12.6 Abstract Classes.- 12.7 Image Class Hierarchy.- 12.8 Multiple Inheritance.- 12.9 Implementation Issues.- 13 Edge Detection and Edge Images.- 13.1 Motivation.- 13.2 Strategies.- 13.3 Discrete Derivative of the Intensity.- 13.4 Sobel and Prewitt Operator.- 13.5 Bit Fields in C++.- 13.6 Unions in C++.- 13.7 Edge Class.- 13.8 Edge Images.- 13.9 Color Edge Operators.- 14 Class Libraries.- 14.1 Stream Input and Output.- 14.2 NIH Class Library.- 14.3 Dynamic Class Descriptions.- 14.4 Static Class Members.- 14.5 Input and Output for Objects.- 14.6 Strings.- 14.7 Container Classes.- 14.8 Time and Date.- 14.9 More Classes.- 15 Hierarchy of Picture Processing Objects.- 15.1 General Structure.- 15.2 Hippos Object.- 15.3 Images and Matrices.- 15.4 Chain Code Class.- 15.5 Enumerations and Scope Resolution.- 15.6 Polygonal Representation.- 15.7 Atomic Objects.- 15.8 Segmentation Objects.- 15.9 External Representation.- 16 Spectral Features and Speech Processing.- 16.1 Fourier Series and Fourier Transform.- 16.2 Discrete Fourier Transform.- 16.3 Fast Fourier Transform.- 16.4 2D Fourier Transform.- 16.5 Short time Fourier analysis.- 16.6 Linear Predictive Coding.- 16.7 Dynamic Time Warping.- 16.8 Hidden Markov Models.- 16.9 Different Types of Hidden Markov Modells.- III Pattern Recognition Algorithms.- 17 An Image Analysis System.- 17.1 Data Flow.- 17.2 Design of ANIMALS.- 17.3 XDR.- 17.4 Display and Capture.- 17.5 Graphical User Interfaces.- 17.6 Geometric Distortions.- 17.7 Polymorphic image processing.- 17.8 Efficiency.- 17.9 Image Segmentation Program.- 18 Synthetic Signals and Images.- 18.1 Synthetic Sound.- 18.2 Geometric Patterns.- 18.3 Pixel Noise.- 18.4 Gaussian Noise.- 18.5 Salt-and-Pepper Noise.- 18.6 Different Views of a 3D Polyhedral Object.- 18.7 Digits and Letters.- 18.8 Single Stereo Images.- 18.9 Spectrogram.- 19 Filtering and Smoothing Signals.- 19.1 Mean-Filter and Gaussian-Filter.- 19.2 Median-Filter.- 19.3 Smoothed Median-Filter.- 19.4 Edge Preserving Smoothing.- 19.5 K-Nearest Neighbor Averaging.- 19.6 Conditional Average Filter.- 19.7 Linear Reconstruction.- 19.8 Elimination of Noisy Image Rows.- 19.9 Resolution Hierarchies.- 20 Histogram Algorithms.- 20.1 Discriminant and Least Squares Threshold.- 20.2 Histogram Entropy Thresholding.- 20.3 Multithresholding.- 20.4 Local Histogram Equalization.- 20.5 Lookup Table Transformation.- 20.6 A Class for Histograms.- 21 Edge Images.- 21.1 Robert’s Cross.- 21.2 Second Derivative.- 21.3 Edge Model Masks.- 21.4 Alternative Methods.- 21.5 Thinning of Edge Images.- 21.6 Edge Thresholding.- 21.7 Non Maxima Suppression.- 21.8 Non Maxima Absorption.- 21.9 Class Edge Revisited.- 22 Line Detection Algorithms.- 22.1 Line Detection.- 22.2 Local Connectivity.- 22.3 Hysteresis Thresholds.- 22.4 Closing of Gaps.- 22.5 Zero crossings in Laplace-Images.- 22.6 Hough Transform.- 22.7 Canny Line Detection.- 22.8 Shen and Castan.- 22.9 Representation as Segmentation Objects.- 23 Chain Codes.- 23.1 Length of a Chain.- 23.2 Smoothing.- 23.3 Digital Linear Lines.- 23.4 Similarity.- 23.5 Intersections.- 23.6 Rotation.- 23.7 Conversion.- IV Appendix.- A Basics of C++.- A.1 History.- A.2 Identifier and Constants.- A.3 Basis Data Types in C and C++.- B Software Development Tools.- B.1 Groups and ID’s with Unix.- B.2 Program Building with make.- B.3 The Use of Libraries.- B.4 Version and Access Control with rcs.- C Source Codes and Tools.- C.1 List of Tools.- C.2 How to get the sources.- C.3 X11.- C.4 Slides.- C.5 Addresses.- C.6 Headers and Source Files.- C.7 Dummy Definitions.- C.7.1 Listing of animals/dummy/Dictionary.h.- C.7.2 Listing of animals/dummy/OIOxdr.h.- C.7.3 Listing of animals/ dummy/Represent.h.- C.7.4 Listing of animals/dummy/SeqCltn.h.- C.7.5 Listing of animals/dummy/Set.h.- C.7.6 Listing of animals/dummy/dummies. C.- References.- Figures.- Tables.- Index for Exercises.