HANDBOOK OF

IMAGE PROCESSING OPERATORS

Reinhard Klette

Berlin Technical University

Piero Zamperoni

late of Braunschweig Technical University

John Wiley & Sons

CHICHESTER · NEW YORK · BRISBANE · TORONTO · SINGAPORE

Flyer to this Handbook
Amazon bookshop page for this book
Floppy to this Handbook

CONTENTS

	Preface								 ix
	Instructions to the Reader					  x
	Often Used Variables						xii

1	Images, Windows and Operators					  1

1.1	Images								  1
	1.1.1	Discrete Image Coordinates and Digital Geometry		  2
	1.1.2	Discrete Image Values and Functions of Image Values	  8
	1.1.3	Color Images, Image Sequences and Multi-channel Images	 14
1.2	Sub-Images							 20
	1.2.1	Windows							 20
	1.2.2	Windows on Images					 24
1.3	Functions on Windows						 26
	1.3.1	Classes of Window Functions				 27
	1.3.2	Auxiliary Functions on Windows or Images		 28
	1.3.3	Some Window Functions					 34
1.4	Operators							 38
	1.4.1	Geometrical Operators					 39
	1.4.2	Point Operators						 40
	1.4.3	Local Operators						 41
	1.4.4	Global Operators					 42
1.5	Bibliographic References					 43


2	Methodical Fundamentals						 47

2.1	Image Synthesis							 48
2.2	Halftone Image Representation					 51
2.3	Geometrical Fitting						 54
2.4	Image Restoration and Image Enhancement				 57
2.5	Image Segmentation						 60
2.6	Iconic Representation of Local Features				 62
2.7	Extraction of Patterns						 64
2.8	Iconic Representation of Geometrical Relations			 65
2.9	Special and Art Effects						 67
2.10	Bibliographic References					 69


3	Algorithmic Fundamentals					 71

3.1	Algorithmic Efficiency						 71
	3.1.1	Estimation of Computing Time				 71
	3.1.2	Absolute and Asymptotic Evaluations			 75
	3.1.3	Decomposition of Homogenous Local Operators		 77
	3.1.4	Updating Method for Local Operators			 82
3.2	Image Data							 83
	3.2.1	Image Data Locations in Image Files			 83
	3.2.2	Overwriting or Saving the Original Image		 84
	3.2.3	Reading, Buffering and Writing back into Memory		 85
3.3	Control Structures						 89
	3.3.1	Local Operators (centered) 				 89
	3.3.2	Local Operators (non-centered)				 92
	3.3.3	Point Operators						 94
3.4	Procedures							 95
	3.4.1	  Procedure RND_EQU					 95
	3.4.2	  Procedure RND_NORM					 97
	3.4.3	  Procedure MAXMIN					 98
	3.4.4	  Procedure SELECT					 99
	3.4.5	  Procedure QUICKSORT					100
	3.4.6	  Procedure BUBBLESORT					102
	3.4.7	  Procedure BUCKETSORT					102
	3.4.8	  Procedure FFT						104
	3.4.9	  Procedure FWT						106
	3.4.10	  Procedure BRESENHAM					108
3.5	Bibliographic References					111


4	Coordinate Transformations and Geometrical 			113
	Operators

4.1	One-to-One Coordinate Transformations				114
	4.1.1	Image Mirroring						116
	4.1.2	Image Shifting						117
	4.1.3	90¡ Image Rotation					120
4.2	Size Reduction and Magnification				120
	4.2.1	Image Size Reduction onto a Quadrant			121
	4.2.2	Image Magnification by Scale Factor 2			124
	4.2.3	Image Pyramids 						125
4.3	Affine Transformations						129
	4.3.1	Products of Transformation Matrices			130
	4.3.2	Computation of Transformation Matrices			134
	4.3.3	Affine Image Transformations				136


5	Gray Scale Transformations and Point Operators			141

5.1	Gray Scale Transformations					142
	5.1.1	Gray Value Scaling in a Selected Region			142
	5.1.2	Linear Stretching to the Full Gray Value Range		143
	5.1.3	Variations of Gradation Functions			145
	5.1.4	Gray Value Histogram Equalization			147
5.2	Generation of Noisy Images					149
	5.2.1	Generation of Spike Noise				150
	5.2.2	Generation of Images with Additive Random Noise		151
5.3	Binarization of Gray Value Images				153
	5.3.1	Binarization with Hysteresis				153
	5.3.2	Recursive Binarization					155
	5.3.3	Binarization Based on Discriminant Analysis		159
	5.3.4	Halftoning by Means of a Threshold Matrix		161
5.4	Point-to-point Operations Between Images			163
	5.4.1	Synthetic Background Compensation			164
	5.4.2	Piece-wise Linear Background Subtraction		166
	5.4.3	Some Operations with Two Images				169
5.5	Image Segmentation by Multilevel Thresholding			173
	5.5.1	Extraction of Constant Gray Value Lines			173
	5.5.2	Thresholding by Extraction of the Histogram Extrema	175
	5.5.3	Multilevel Thresholding for Unimodal Histograms		179
5.6	Multi-channel Images						186
	5.6.1	Basic Arithmetic Operations				186
	5.6.2	Color Model Conversion					190
	5.6.3	Pseudo-Coloring						192


6	Window Functions and Local Operators				195

6.1	Smoothing and Noise Reduction					195
	6.1.1	Linear Convolution with User-defined Kernel		195
	6.1.2	Smoothing with a Separable Unweighted Averaging Filter	199
	6.1.3	Smoothing with a Separable Binomial Filter		203
	6.1.4	Smoothing in a Selected Neighborhood			206
	6.1.5	Adaptive Smoothing Based on Local Statistics		208
	6.1.6	Smoothing by Adaptive Quantile Filtering		211
	6.1.7	Elimination of Small Objects in Binary Images		215
	6.1.8	Halftoning by Means of Error Distribution		217
6.2	Edge Extraction							219
	6.2.1	One-Pixel-Edge Operator					219
	6.2.2	Standard Edge Operators					221
	6.2.3	Morphological Edge Operator				224
	6.2.4	Edge Detection by Gaussian Filtering (LoG and DoG)	227
	6.2.5	Deriche Edge Operator					236
	6.2.6	Contra-harmonic Filter					241
6.3	Image Sharpening and Texture Enhancement			244
	6.3.1	Extreme Value Sharpening				245
	6.3.2	Unsharp Masking and Space-variant Binarization		248
	6.3.3	Locally Adaptive Scaling for Detail Enhancement		252
	6.3.4	Adaptive Contrast Enhancement at Edges			255
6.4	Region Growing and Image Approximation				258
	6.4.1	Agglomerative Region Growing Operator			258
	6.4.2	Concavity-filling Operator for Gray Value Images	261
	6.4.3	Mode Enhancement					266
6.5	Rank-order Filtering						270
	6.5.1	Median Filtering and Non-linear Sharpening		271
	6.5.2	Minimum and Maximum (Erosion and Dilation)		275
	6.5.3	Rank Selection Filter					279
	6.5.4	Max/min-median Filter for Image Enhancement		281
	6.5.5	Some Adaptive Variants of the Median Operator		283
	6.5.6	General L-Filter in a 3´3 Window			287
	6.5.7	Rank Selection Filter with Adaptive Window		289
	6.5.8	Rank-order Transformation (Contrast Stretching)		296
	6.5.9	Anisotropy-controlled Adaptive Rank-order Filters	298
6.6	Line Extraction Filters						306
	6.6.1	Line Extraction						307
	6.6.2	Suppression of Line Patterns				309


7	Global Operators						313

7.1	Topological Operators						313
	7.1.1	Connected Component Labeling				314
	7.1.2	Thinning of Binary Images				319
	7.1.3	Thinning of Gray Value Images				327
7.2	Geometrical Constructions					332
	7.2.1	Contour Following for Binary Images			332
	7.2.2	Delaunay Triangulation and Voronoi Diagram		341
	7.2.3	Hough Transformation for Straight Lines			350
7.3	Signal Analysis Operators					355
	7.3.1	Fourier Transformation					356
	7.3.2	Inverse Fourier Transformation for Filtering		359
	7.3.3	Spectrum						363
	7.3.4	Walsh Transformation					365


	Glossary							369
	Index								391


CITR: last update: 22 April 1998