Algorithms for Graphics and Image Processing

The technological developments of the last ten years have made com­ puter graphics and image processing by computer popular. Pictorial pat­ tern recognition has also shown significant progress. Clearly, there exist overlapping interests among the three areas of research. Graphic displays are of concern to anyone involved in image processing or pic­ torial pattern recognition and many problems in graphics require methodologies from image processing for their solutions. The data structures used in all three areas are similar. It seems that there is a common body of knowledge underlying all three areas, pictorial informa­ tion processing by computer. The novelty of these fields makes it difficult to design a course or to a write a book covering their basic concepts. Some of the treatises on graphics focus on the hardware and methods of current interest while treatises on image processing often emphasize applications and classical signal processing. The fast evolution of technology causes such material to lose its relevance. For example, the development of optical fibers has reduced the importance of bandwidth compression.

1: Introduction.- 1.1 Graphics, Image Processing, and Pattern Recognition.- 1.2 Forms of Pictorial Data.- 1.2.1 Class 1: Full Gray Scale and Color Pictures.- 1.2.2 Class 2: Bilevel or “Few Color” pictures.- 1.2.3 Class 3: Continuous Curves and Lines.- 1.2.4 Class 4: Points or Polygons.- 1.3 Pictorial Input.- 1.4 Display Devices.- 1.5 Vector Graphics.- 1.6 Raster Graphics.- 1.7 Common Primitive Graphic Instructions.- 1.8 Comparison of Vector and Raster Graphics.- 1.9 Pictorial Editor.- 1.10 Pictorial Transformations.- 1.11 Algorithm Notation.- 1.12 A Few Words on Complexity.- 1.13 Bibliographical Notes.- 1.14 Relevant Literature.- 1.15 Problems.- 2: Digitization of Gray Scale Images.- 2.1 Introduction.- 2.2 A Review of Fourier and other Transforms.- 2.3 Sampling.- 2.3.1 One-dimensional Sampling.- 2.3.2 Two-dimensional Sampling.- 2.4 Aliasing.- 2.5 Quantization.- 2.6 Bibliographical Notes.- 2.7 Relevant Literature.- 2.8 Problems.- Appendix 2.A: Fast Fourier Transform.- 3: Processing of Gray Scale Images.- 3.1 Introduction.- 3.2 Histogram and Histogram Equalization.- 3.3 Co-occurrence Matrices.- 3.4 Linear Image Filtering.- 3.5 Nonlinear Image Filtering.- 3.5.1 Directional Filters.- 3.5.2 Two-part Filters.- 3.5.3 Functional Approximation Filters.- 3.6 Bibliographical Notes.- 3.7 Relevant Literature.- 3.8 Problems.- 4: Segmentation.- 4.1 Introduction.- 4.2 Thresholding.- 4.3 Edge Detection.- 4.4 Segmentation by Region Growing.- 4.4.1 Segmentation by Average Brightness Level.- 4.4.2 Other Uniformity Criteria.- 4.5 Bibliographical Notes.- 4.6 Relevant Literature.- 4.7 Problems.- 5: Projections.- 5.1 Introduction.- 5.2 Introduction to Reconstruction Techniques.- 5.3 A Class of Reconstruction Algorithms.- 5.4 Projections for Shape Analysis.- 5.5 Bibliographical Notes.- 5.6 Relevant Literature.- 5.7 Problems.- Appendix 5.A: An Elementary Reconstruction Program.- 6: Data Structures.- 6.1 Introduction.- 6.2 Graph Traversal Algorithms.- 6.3 Paging.- 6.4 Pyramids or Quad Trees.- 6.4.1 Creating a Quad Tree.- 6.4.2 Reconstructing an Image from a Quad Tree.- 6.4.3 Image Compaction with a Quad Tree.- 6.5 Binary Image Trees.- 6.6 Split-and-Merge Algorithms.- 6.7 Line Encodings and the Line Adjacency Graph.- 6.8 Region Encodings and the Region Adjacency Graph.- 6.9 Iconic Representations.- 6.10 Data Structures for Displays.- 6.11 Bibliographical Notes.- 6.12 Relevant Literature.- 6.13 Problems.- Appendix 6.A: Introduction to Graphs.- 7: Bilevel Pictures.- 7.1 Introduction.- 7.2 Sampling and Topology.- 7.3 Elements of Discrete Geometry.- 7.4 A Sampling Theorem for Class 2 Pictures.- 7.5 Contour Tracing.- 7.5.1 Tracing of a Single Contour.- 7.5.2 Traversal of All the Contours of a Region.- 7.6 Curves and Lines on a Discrete Grid.- 7.6.1 When a Set of Pixels is not a Curve.- 7.6.2 When a Set of Pixels is a Curve.- 7.7 Multiple Pixels.- 7.8 An Introduction to Shape Analysis.- 7.9 Bibliographical Notes.- 7.10 Relevant Literature.- 7.11 Problems.- 8: Contour Filling.- 8.1 Introduction.- 8.2 Edge Filling.- 8.3 Contour Filling by Parity Check.- 8.3.1 Proof of Correctness of Algorithm 8.3.- 8.3.2 Implementation of a Parity Check Algorithm.- 8.4 Contour Filling by Connectivity.- 8.4.1 Recursive Connectivity Filling.- 8.4.2 Nonrecursive Connectivity Filling.- 8.4.3 Procedures used for Connectivity Filling.- 8.4.4 Description of the Main Algorithm.- 8.5 Comparisons and Combinations.- 8.6 Bibliographical Notes.- 8.7 Relevant Literature.- 8.8 Problems.- 9: Thinning Algorithms.- 9.1 Introduction.- 9.2 Classical Thinning Algorithms.- 9.3 Asynchronous Thinning Algorithms.- 9.4 Implementation of an Asynchronous Thinning Algorithm.- 9.5 A Quick Thinning Algorithm.- 9.6 Structural Shape Analysis.- 9.7 Transformation of Bilevel Images into Line Drawings.- 9.8 Bibliographical Notes.- 9.9 Relevant Literature.- 9.10 Problems.- 10: Curve Fitting and Curve Displaying.- 10.1 Introduction.- 10.2 Polynomial Interpolation.- 10.3 Bezier Polynomials.- 10.4 Computation of Bezier Polynomials.- 10.5 Some Properties of Bezier Polynomials.- 10.6 Circular Arcs.- 10.7 Display of Lines and Curves.- 10.7.1 Display of Curves through Differential Equations.- 10.7.2 Effect of Round-off Errors in Displays.- 10.8 A Point Editor.- 10.8.1 A Data Structure for a Point Editor.- 10.8.2 Input and Output for a Point Editor.- 10.9 Bibliographical Notes.- 10.10 Relevant Literature.- 10.11 Problems.- 11: Curve Fitting with Splines.- 11.1 Introduction.- 11.2 Fundamental Definitions.- 11.3 B-Splines.- 11.4 Computation with B-Splines.- 11.5 Interpolating B-Splines.- 11.6 B-Splines in Graphics.- 11.7 Shape Description and B-splines.- 11.8 Bibliographical Notes.- 11.9 Relevant Literature.- 11.10 Problems.- 12: Approximation of Curves.- 12.1 Introduction.- 12.2 Integral Square Error Approximation.- 12.3 Approximation Using B-Splines.- 12.4 Approximation by Splines with Variable Breakpoints.- 12.5 Polygonal Approximations.- 12.5.1 A Suboptimal Line Fitting Algorithm.- 12.5.2 A Simple Polygon Fitting Algorithm.- 12.5.3 Properties of Algorithm 12.2.- 12.6 Applications of Curve Approximation in Graphics.- 12.6.1 Handling of Groups of Points by a Point Editor.- 12.6.2 Finding Some Simple Approximating Curves.- 12.7 Bibliographical Notes.- 12.8 Relevant Literature.- 12.9 Problems.- 13: Surface Fitting and Surface Displaying.- 13.1 Introduction.- 13.2 Some Simple Properties of Surfaces.- 13.3 Singular Points of a Surface.- 13.4 Linear and Bilinear Interpolating Surface Patches.- 13.5 Lofted Surfaces.- 13.6 Coons Surfaces.- 13.7 Guided Surfaces.- 13.7.1 Bezier Surfaces.- 13.7.2 B-Spline Surfaces.- 13.8 The Choice of a Surface Partition.- 13.9 Display of Surfaces and Shading.- 13.10 Bibliographical Notes.- 13.11 Relevant Literature.- 13.12 Problems.- 14: The Mathematics of Two-Dimensional Graphics.- 14.1 Introduction.- 14.2 Two-Dimensional Transformations.- 14.3 Homogeneous Coordinates.- 14.3.1 Equation of a Line Defined by Two Points.- 14.3.2 Coordinates of a Point Defined as the Intersection of Two Lines.- 14.3.3 Duality.- 14.4 Line Segment Problems.- 14.4.1 Position of a Point with respect to a Line.- 14.4.2 Intersection of Line Segments.- 14.4.3 Position of a Point with respect to a Polygon.- 14.4.4 Segment Shadow.- 14.5 Bibliographical Notes.- 14.6 Relevant Literature.- 14.7 Problems.- 15: Polygon Clipping.- 15.1 Introduction.- 15.2 Clipping a Line Segment by a Convex Polygon.- 15.3 Clipping a Line Segment by a Regular Rectangle.- 15.4 Clipping an Arbitrary Polygon by a Line.- 15.5 Intersection of Two Polygons.- 15.6 Efficient Polygon Intersection.- 15.7 Bibliographical Notes.- 15.8 Relevant Literature.- 15.9 Problems.- 16: The Mathematics of Three-Dimensional Graphics.- 16.1 Introduction.- 16.2 Homogeneous Coordinates.- 16.2.1 Position of a Point with respect to a Plane.- 16.2.2 Intersection of Triangles.- 16.3 Three-Dimensional Transformations.- 16.3.1 Mathematical Preliminaries.- 16.3.2 Rotation around an Axis through the Origin.- 16.4 Orthogonal Projections.- 16.5 Perspective Projections.- 16.6 Bibliographical Notes.- 16.7 Relevant Literature.- 16.8 Problems.- 17: Creating Three-Dimensional Graphic Displays.- 17.1 Introduction.- 17.2 The Hidden Line and Hidden Surface Problems.- 17.2.1 Surface Shadow.- 17.2.2 Approaches to the Visibility Problem.- 17.2.3 Single Convex Object Visibility.- 17.3 A Quad Tree Visibility Algorithm.- 17.4 A Raster Line Scan Visibility Algorithm.- 17.5 Coherence.- 17.6 Nonlinear Object Descriptions.- 17.7 Making a Natural Looking Display.- 17.8 Bibliographical Notes.- 17.9 Relevant Literature.- 17.10 Problems.- Author Index.- Algorithm Index.