Modern Algorithms for Image Processing Computer Imagery by Example Using C# — Vladimir Kovalevsky
Modern Algorithms for Image Processing Computer Imagery by Example Using C# Vladimir Kovalevsky
Modern Algorithms for Image Processing: Computer Imagery by Example Using C# ISBN-13 (pbk): 978-1-4842-4236-0 ISBN-13 (electronic): 978-1-4842-4237-7 https://doi.org/10.1007/978-1-4842-4237-7 Library of Congress Control Number: 2018965475 Copyright © 2019 by Vladimir Kovalevsky This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Managing Director, Apress Media LLC: Welmoed Spahr Acquisitions Editor: Joan Murray Development Editor: Laura Berendson Coordinating Editor: Jill Balzano Cover image designed by Freepik (www.freepik.com) Distributed to the book trade worldwide by Springer Science+Business Media New York, 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer- sbm.com, or visit www.springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation. For information on translations, please e-mail rights@apress.com, or visit http://www.apress.com/ rights-permissions. Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Print and eBook Bulk Sales web page at http://www.apress.com/bulk-sales. Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub via the book's product page, located at www.apress.com/9781484242360. For more detailed information, please visit http://www.apress.com/source-code. Printed on acid-free paper Vladimir Kovalevsky Berlin, Germany
Dedicated to my wife, Dr. Baerbel Kovalevsky
v About the Author ����������������������������������������������������������������������������������������������������� ix Acknowledgments ��������������������������������������������������������������������������������������������������� xi Introduction ����������������������������������������������������������������������������������������������������������� xiii Table of Contents Part I: Image Processing �������������������������������������������������������������������������������� 1 Chapter 1: Introduction��������������������������������������������������������������������������������������������� 3 Chapter 2: Noise Reduction �������������������������������������������������������������������������������������� 5 The Simplest Filter ������������������������������������������������������������������������������������������������������������������������ 6 The Simplest Averaging Filter ������������������������������������������������������������������������������������������������������� 6 The Fast Averaging Filter �������������������������������������������������������������������������������������������������������������� 8 The Fast Gaussian Filter�������������������������������������������������������������������������������������������������������������� 14 The Median Filter ������������������������������������������������������������������������������������������������������������������������ 17 Sigma Filter: The Most Efficient One ������������������������������������������������������������������������������������������� 18 Suppression of Impulse Noise ���������������������������������������������������������������������������������������������������� 23 Chapter 3: Contrast Enhancement �������������������������������������������������������������������������� 43 Automatic Linear Contrast Enhancement ����������������������������������������������������������������������������������� 43 Histogram Equalization ��������������������������������������������������������������������������������������������������������������� 45 Measuring the Lightness of Color Images ����������������������������������������������������������������������������������� 49 Contrast of Color Images ������������������������������������������������������������������������������������������������������������� 52 Manually Controlled Contrast Enhancement ������������������������������������������������������������������������������� 53 Chapter 4: Shading Correction with Thresholding �������������������������������������������������� 65 Thresholding the Images ������������������������������������������������������������������������������������������������������������ 75 Chapter 5: Project WFshadBinImpulse ������������������������������������������������������������������� 81
vi Part II: Image Analysis ��������������������������������������������������������������������������������� 85 Chapter 6: Edge Detection �������������������������������������������������������������������������������������� 87 Laplacian Operator ���������������������������������������������������������������������������������������������������������������������� 87 The Method of Zero Crossing ������������������������������������������������������������������������������������������������������ 89 Are Zero Crossings of Laplacian Closed Curves? ������������������������������������������������������������������������ 89 How to Eliminate Irrelevant Crossings ���������������������������������������������������������������������������������������� 91 Noise Reduction Before Using the Laplacian ������������������������������������������������������������������������������ 92 Blur During the Digitization and Extreme Value Filter ����������������������������������������������������������������� 93 Fundamental Errors of the Method of Zero Crossing in the Laplacian ���������������������������������������� 98 Chapter 7: A New Method of Edge Detection �������������������������������������������������������� 101 Means for Encoding the Edges ������������������������������������������������������������������������������������������������� 102 The Idea of an Abstract Cell Complex ��������������������������������������������������������������������������������������� 103 A Simple Method of Encoding Edges ���������������������������������������������������������������������������������������� 105 Improvements of the Method of Binarized Gradient ����������������������������������������������������������������� 107 Further Improvements of the Method of Binarized Gradient ����������������������������������������������������� 120 The Edge Detector of Canny ������������������������������������������������������������������������������������������������������ 122 Edges in Color Images �������������������������������������������������������������������������������������������������������������� 123 Conclusions ������������������������������������������������������������������������������������������������������������������������������� 125 Chapter 8: A New Method of Image Compression ������������������������������������������������ 127 Using a Cell Complex for the Encoding of Boundaries �������������������������������������������������������������� 128 Description of the Project WFcompressPal ������������������������������������������������������������������������������� 131 The Project WFrestoreLin ���������������������������������������������������������������������������������������������������������� 150 Chapter 9: Image Segmentation and Connected Components ������������������������������ 167 Segmentation by Quantizing the Colors ������������������������������������������������������������������������������������ 168 Connected Components ������������������������������������������������������������������������������������������������������������ 168 The Graph Traversal Algorithm and Its Code ����������������������������������������������������������������������������� 171 The Pseudo-Code of the Breadth-First Algorithm ���������������������������������������������������������������� 172 Table of ConTenTs
vii The Approach of Equivalence Classes �������������������������������������������������������������������������������������� 173 The Pseudo-Code of the Root Algorithm ����������������������������������������������������������������������������������� 177 The Project WFsegmentAndComp ��������������������������������������������������������������������������������������������� 179 Conclusion �������������������������������������������������������������������������������������������������������������������������������� 186 Chapter 10: Straightening Photos of Paintings����������������������������������������������������� 187 The Principle of Straightening��������������������������������������������������������������������������������������������������� 189 Codes of Most Important Methods �������������������������������������������������������������������������������������������� 196 Conclusion �������������������������������������������������������������������������������������������������������������������������������� 203 Chapter 11: Polygonal Approximation of Region Boundaries and Edges ������������� 205 The Problem of Polygonal Approximation ��������������������������������������������������������������������������������� 205 Schlesinger’s Measure of Similarity of Curves ������������������������������������������������������������������������� 206 Statement of the Approximation Problem ��������������������������������������������������������������������������� 207 Algorithms for Polygonal Approximation ����������������������������������������������������������������������������������� 207 The Split-and-Merge Method ���������������������������������������������������������������������������������������������� 208 The Sector Method �������������������������������������������������������������������������������������������������������������� 209 The Improvement of the Sector Method ������������������������������������������������������������������������������ 210 Replacing Polygons by Sequences of Arcs and Straight Lines ������������������������������������������������� 211 Definitions and the Problem Statement ������������������������������������������������������������������������������� 211 The Approximate Solution ��������������������������������������������������������������������������������������������������� 212 The Project WFpolyArc �������������������������������������������������������������������������������������������������������������� 217 Methods Used in the Project WFpolyArc ������������������������������������������������������������������������������ 218 Precision of the Calculation of the Radii ����������������������������������������������������������������������������������� 225 Conclusion �������������������������������������������������������������������������������������������������������������������������������� 226 Chapter 12: Recognition and Measurement of Circular Objects ��������������������������� 227 Mathematical Foundation of the Method ���������������������������������������������������������������������������������� 228 The Project WFcircleReco ��������������������������������������������������������������������������������������������������������� 232 The Form of the Project WFcircleReco �������������������������������������������������������������������������������� 233 Table of ConTenTs
viii Chapter 13: Recognition of Bicycles in Traffic ������������������������������������������������������ 243 Mathematical Foundation of Ellipse Recognition ���������������������������������������������������������������������� 243 The Project WFellipseBike ��������������������������������������������������������������������������������������������������������� 247 Another Method of Recognizing the Direction �������������������������������������������������������������������������� 258 Chapter 14: A Computer Model of Cell Differentiation ������������������������������������������ 261 Conclusion �������������������������������������������������������������������������������������������������������������������������������� 266 References ������������������������������������������������������������������������������������������������������������ 267 Index ��������������������������������������������������������������������������������������������������������������������� 269 Table of ConTenTs
ix About the Author Vladimir Kovalevsky received his diploma in physics from the Kharkov University (Ukraine), his first doctoral degree in technical sciences from the Central Institute of Metrology (Leningrad), and his second doctoral degree in computer science from the Institute of Cybernetics of the Academy of Sciences of the Ukraine (Kiev) where he headed the Department of Pattern Recognition for more than a decade. Vladimir has been living in Germany since 1983. He was a researcher at the Central Institute of Cybernetics of the Academy of Sciences of the GDR, Berlin, a professor of computer science at the University of Applied Sciences Berlin, and a scientific collaborator at the University of Rostock. He has been a visiting researcher at the University of Pennsylvania, a professor at the Manukau Institute of Technology in New Zealand, and a professor at the Chonbuk National University in South Korea. He has reviewed for the journals Applied General Topology, Computer Vision and Image Understanding, IEEE Transactions on Pattern Analysis and Machine Intelligence, and others. Vladimir has been a plenary speaker at conferences in Europe, the United States, and New Zealand. His research interests include digital geometry, digital topology, computer vision, image processing, and pattern recognition. He has published four monographs and more than 180 journal and conference papers on image analysis, digital geometry, and digital topology.
xi Acknowledgments I wish to acknowledge valuable and fruitful discussions with Boris Flach, Reinhard Klette, Ulrich Koethe, Alexander Kovalevsky, Volkmar Miszalok, and Peer Stelldinger. These discussions have significantly contributed to this work. I would like to express my special appreciation to Alexander V. Kovalevsky, who helped significantly as an experienced programmer in the development of my projects.
xiii Introduction This book presents a collection of algorithms and projects for processing two- dimensional images. I developed and investigated the algorithms. Special emphasis is placed on computer solutions of problems related to the improvement of the quality of images, with image analysis and recognition of some geometrically definable objects. New data structures useful for image analysis are presented. The description of all algorithms contains examples of source code in the C# programming language. Descriptions of projects contain source code that can be used by readers. With this book I intend to help you develop efficient software for processing two- dimensional images. There are a lot of books on image processing, but important algorithms are missing from these books. I have developed many efficient algorithms as a new and important contribution to this area. I have paid great attention to solutions of problems in image analysis. On the other hand, problems of improving the quality of images are important for the arts. My wife is a recognized specialist in the history of the arts, and her publications often use copies of famous pictures and drawings. The photographs of these artworks are often of low quality. Often photographs of historical drawings illustrating the work of a painter are of such low quality that it is almost impossible to clearly see the contents of the image. Improving these images is therefore very important. In such cases, the programs I have developed for improving the quality of pictures are very useful. I have developed efficient algorithms for recognizing circles and ellipses in noisy images. These algorithms can be used for recognizing objects with a shape approximating a circle; for example, apples, mushrooms, and so on. They can also be used for recognizing bicycles in images of traffic because the wheels of bicycles are ideal circles, but if the bicycle is positioned in such a way that the plane of its frame is not orthogonal to the viewing ray, then its wheels look like ellipses rather than circles. I was therefore forced to develop efficient algorithms for recognizing ellipses in noisy images as well. My efforts were successful and the book contains a chapter devoted to the recognition of bicycles in noisy images. The book contains descriptions of numerous algorithms for image analysis, including these:
xiv • Manually controlled thresholding of shading corrected images. • A fast algorithm for simultaneously labeling all connected components in a segmented image. • A new efficient method of edge detection. • A fast algorithm for approximating digital curves by polygons and for estimating the curvature of circular arcs approximating the curve. • Algorithms for recognition and measurement of circular or elliptical objects in color images. Among the algorithms for image improvement, the most important are the following: • The algorithm for rectifying photographs of paintings taken at an oblique angle. • An algorithm correcting images of nonuniformly illuminated scenes. • The algorithm for improving the contrast of images of nonuniformly illuminated scenes. • The best algorithm for reducing Gaussian noise (the so-called Sigma- Filter). • The algorithm for reducing impulse noise. All descriptions are followed by a pseudo-code similar to the C# programming language. Most of the descriptions contain source code that can be copied from the text and used directly in a Windows Forms program written in the C# .NET language. All source code and figures are included in a download file (which you can access via the Download Source Code button located at www.apress.com/9781484242360) so you can see the colors. InTroduCTIon
3 © Vladimir Kovalevsky 2019 V. Kovalevsky, Modern Algorithms for Image Processing, https://doi.org/10.1007/978-1-4842-4237-7_1 CHAPTER 1 Introduction This book contains descriptions of algorithms for image processing such as noise reduction, including reduction of impulse noise, contrast enhancement, shading correction, edge detection, and many others. The source codes of the projects in the C# programming language implementing the algorithms are included on the book’s companion web site. The source codes are Windows Forms projects rather than Microsoft Foundation Classes Library (MFC) projects. The controls and the graphics in these projects are implemented by means of simple and easily understandable methods. I have chosen this way of implementing controls and graphics services rather than those based on MFC because the integrated development environment (IDE) using MFC is expensive. Besides that, the software using MFC is rather complicated. It includes many different files in a project and the user is largely unable to understand the sense and usefulness of these files. On the contrary, Windows Forms and its utility tools are free and are easier to understand. They supply controls and graphics similar to that of MFC. To provide fast processing of images we transform objects of the class Bitmap, which is standard in Windows Forms, to objects of our class CImage, the methods of which are fast because they use direct access to the set of pixels, whereas the standard way of using Bitmap consists of implementing the relatively slow methods of GetPixel and SetPixel or methods using LockBits, which are fast, but not usable for indexed images. The class CImage is rather simple: It contains the properties width, height, and nBits of the image and methods used in the actual project. My methods are described in the chapters devoted to projects. Here is the definition of our class CImage. class CImage { public Byte[] Grid; public int width, height, nBits; public CImage() { } // default constructor
4 public CImage(int nx, int ny, int nbits) // constructor { width = nx; height = ny; nBits = nbits; Grid = new byte[width * height * (nBits / 8)]; } public CImage(int nx, int ny, int nbits, byte[] img) // constructor { width = nx; height = ny; nBits = nbits; Grid = new byte[width * height * (nBits / 8)]; for (int i = 0; i < width * height * nBits / 8; i++) Grid[i] = img[i]; } } //*********************** end of class CImage ***************** Methods of the class CImage are described in the descriptions of projects. Chapter 1 IntroduCtIon
5 © Vladimir Kovalevsky 2019 V. Kovalevsky, Modern Algorithms for Image Processing, https://doi.org/10.1007/978-1-4842-4237-7_2 CHAPTER 2 Noise Reduction Digital images are often distorted by random errors usually referred to as noise. There are two primary kinds of noise: Gaussian noise and impulse noise (see Figure 2-1). Gaussian noise is statistical noise having a probability distribution similar to a Gaussian distribution. It arises mainly during acquisition (e.g., in a sensor). It could be caused by poor illumination or by high temperature of the sensor. It comes from many natural sources, such as the thermal vibrations of atoms in conductors, referred to as thermal noise. It influences all pixels of the image. Impulse noise, also called salt-and-pepper noise, presents itself as sparsely occurring light and dark pixels. It comes from pulse distortions like those coming from electrical welding near the electronic device taking up the image or due to improper storage of old photographs. It influences a small part of the set of pixels. Figure 2-1. Examples of noise: (a) Gaussian noise; (b) impulse noise
6 The Simplest Filter We consider first the ways of reducing the intensity of Gaussian noise. The algorithm for reducing the intensity of impulse noise is considered later in this chapter. The most efficient method of reducing the intensity of Gaussian noise is replacing the lightness of a pixel P by the average value of the lightness of a small subset of pixels in the neighborhood of P. This method is based on the fact from the theory of random values: The standard deviation of the average of N equally distributed random values is by the factor √N less than the standard deviation of a single value. This method performs a two-dimensional convolution of the image with a mask, which is an array of weights arranged in a square of W × W pixels, and the actual pixel P lies in the middle of the square. Source code for this filter is presented later in this chapter. This method has two drawbacks: It is rather slow because it uses W × W additions for each pixel of the image, and it blurs the image. It transforms fine edges at boundaries of approximately homogeneous regions to ramps where the lightness changes linearly in a stripe whose width is equal to W pixels. The first drawback is overcome with the fast averaging filter. However, the second drawback is so important that it prevents use of the averaging filter for the purpose of noise removal. Averaging filters are, however, important for improving images with shading (i.e., those representing nonuniformly illuminated objects), as we see later. I propose another filter for the purpose of noise removal as well. First, let us describe the simplest averaging filter. I present the source code of this simple method, which the reader can use in his or her program. In this code, as well as in many other code examples, we use certain classes, which are defined in the next section. The Simplest Averaging Filter The nonweighted averaging filter calculates the mean gray value in a gliding square window of W × W pixels where W is the width and height of a square gliding window. The greater the window size W, the stronger the suppression of Gaussian noise: The filter decreases the noise by the factor W. The value W is usually an odd integer W = 2 × h + 1 for the sake of symmetry. The coordinates (x + xx, y + yy) of pixels inside the window vary symmetrically around the current center pixel (x, y) in the intervals: −h ≤ xx ≤ +h and −h ≤ yy ≤ +h with h = 1, 2, 3, 4, and so on. Chapter 2 Noise reduCtioN
7 Near the border of the image the window lies partially outside of the image. In this case, the computation loses its natural symmetry because only pixels inside the image can be averaged. A reasonable way to solve the border problem is to take control of the coordinates (x + xx, y + yy) if they point out of the image. If these coordinates are out of the image the summation of the gray values must be suspended and the divisor nS should not be incremented. An example of the algorithm for averaging the colors is presented here. We often use in our code comments denoted by lines of certain symbols: lines marked with = label the start and the end of a loop, lines with minus signs label if instructions, and so on. This makes the structure of the code more visible. The simplest slow version of the algorithm has four nested for loops. public void CImage::Averaging(CImage input, int HalfWidth) { int nS, sum; for (int y=0; y<height; y++) //================================ { for (int x=0; x<width; x++) //============================== { nS=sum=0; for (int yy=-HalfWidth; yy<=HalfWidth; yy++) //======= { if (y+yy>=0 && y+yy<input.height ) for (int xx=-HalfWidth; xx<=HalfWidth; xx++) //=== { if (x+xx>=0 && x+xx<input.width) { sum+=input.Grid[x+xx+width*(y+yy)]; nS++; } } //====== end for (xx... =================== } //======== end for (yy... ======================= Grid[x+width*y]=(sum+nS/2)/nS; //+nS/2 is for rounding } //============ end for (x... ======================== } //============== end for (y... ======================== } //****************** end Averaging **************************** This is source code: The reader can copy it and put into its C# source, and it will work. The parameter HalfWidth is half the width of the gliding window. The width and height of the window are both equal to 2*HalfWidth+1. The variables x and y in the preceding code are the indexes of pixels in Grid, and xx and yy are the indexes of the pixels inside the gliding averaging window. Chapter 2 Noise reduCtioN
8 The computation of sum in the innermost for loop needs W × W additions and W × W accesses to the image for each pixel of the input image, which is quite time consuming. Let us remark once again that averaging filters, although they are very efficient at reducing the intensity of Gaussian noise, strongly blur the image. Therefore they should not be used for noise reduction. I suggest using the sigma filter described later in this chapter for this purpose. Averaging is used for the purpose of shading correction (see Chapter 4). Therefore it will be mostly used with a rather large gliding window, as large as half the width of the image. Then the simplest averaging routine becomes so time consuming that it is practically impossible to use it. For example, in the case of a grayscale image of 1000 × 1000 pixels and a gliding window of 400 × 400 pixels, which is typical for shading correction, the runtime of the function Averaging on a standard PC can take about 20 minutes. The Fast Averaging Filter The simplest averaging filter makes W2 additions and one division for each pixel of the image. For example, it makes 5 · 5 + 1 = 26 operations for each pixel in the case of a gliding window of 5 × 5 = 25 pixels. There are applications (e.g., the shading correction) that are using much greater gliding windows; for example, one of 400 × 400 = 160,000 pixels. If an application uses the simplest averaging filter with such a great gliding window, it can run for several minutes. It is possible to accelerate the averaging filter using the following basic idea: It is possible to calculate first the sums of gray values in small one-dimensional windows of 1 × W pixels. We call the arrays of these sums the columns. In the following description of the basic idea we use a Cartesian coordinate system, the index of a column of the image being the abscissa x and the index of a row being the ordinate y. We consider the ordinate axis as directed downward, from top to bottom, which is usual in image processing and different from the direction of the ordinate axis in mathematics. The fast averaging filter solves the same problem as the simplest filter, but it is much faster. The fast filter blurs the image in the same way as the simplest filter does. Therefore its main application is shading correction rather than noise suppression. When using the basic idea just mentioned, it is possible to reduce the number of operations per pixel from W × W to ≈4: The fast filter calculates and saves the sum of the gray values in each column of W pixels, and the middle pixel of each column lies in the Chapter 2 Noise reduCtioN
9 actual row of the image (Figure 2-2). The filter then directly calculates the sum over the window having its central pixel at the beginning of a row; that is, by adding up the sums saved in the columns. Then the window moves one pixel along the row, and the filter calculates the sum for the next location by adding the value of the column sum at the right border of the window and by subtracting the value of the column sum at the left border. It is necessary to check whether the column to be added or subtracted is inside the image. If it is not, the corresponding addition or subtraction must be skipped. Due to applying a similar procedure for the calculation of the column sums, the average number of additions or subtractions per pixel is reduced to ≈2 + 2 = 4. The sum inside the window must be calculated directly (i.e., by the addition of HalfWidth + 1 sums of columns) only for a pixel at the beginning of each row. The sums of columns must be calculated directly only for the pixels of the first row of the image. The filter updates the values of the columns when proceeding to the next row of the image by adding the gray value below the lower end and subtracting the gray value at the upper end of each column (Figure 2-2). In this case it is also necessary to check whether the gray value to be added or subtracted is in the image. The filter divides (with rounding) the sum by the number of pixels in the intersection of the window with the image as soon as the sum of the gray values in a window is calculated and saves the result in the corresponding pixel of the output image. Actual row Old column 1×W New column 1×W Old window W×W New window W×W + - + - + - + - +- +Y Figure 2-2. Explanation of the functioning of the fast average filter Chapter 2 Noise reduCtioN
Comments 0
Loading comments...
Reply to Comment
Edit Comment