digital-image-processing-part-one.pdf

Huiyu Zhou, Jiahua Wu & Jianguo Zhang Digital Image Processing Part I 2 Download free eBooks at bookboon.com Digital Image Processing: Part I 1st edition © 2014 Huiyu Zhou, Jiahua Wu & Jianguo Zhang & bookboon.com ISBN 978-87-7681-541-7 3 Download free eBooks at bookboon.com Digital Image Processing Part I Contents Contents Prefaces 7 1 Introduction 8 1.1 Digital image processing 8 1.2 Purpose of digital image processing 9 1.3 Application areas that use digital image processing 10 1.4 Components of an image processing system 14 1.5 Visual perception 14 1.6 Image acquisition 15 1.7 Image sampling and quantization 16 1.8 Basic relationship between pixels 17 1.9 Summary 19 1.10 References 19 1.11 Problems 19 Free eBook on Learning & Development By the Chief Learning Officer of McKinsey Download Now 4 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Contents 2 Intensity transformations and spatial filtering 20 2.1 Preliminaries 20 2.2 Basic Intensity Transformation Functions 20 2.3 Histogram Processing 22 2.4 Fundamentals of Spatial Filtering 26 2.5 Smoothing Spatial Filters 26 2.6 Sharpening filters 30 2.7 Combining image enhancement methods 33 2.8 Summary 34 2.9 References 35 2.10 Problems 36 3 Filtering in the Frequency Domain 37 3.1 Background 37 3.2 Preliminaries 37 3.3 Sampling and the Fourier Transform of Sampled Functions 38 3.4 Discrete Fourier Transform 43 3.5 Extension to Functions of Two Variables 44 3.6 Some Properties of the 2-D Discrete Fourier Transform 45 3.7 The Basics of Filtering in the Frequency Domain 46 www.sylvania.com We do not reinvent the wheel we reinvent light. Fascinating lighting offers an infinite spectrum of possibilities: Innovative technologies and new markets provide both opportunities and challenges. An environment in which your expertise is in high demand. Enjoy the supportive working atmosphere within our global group and benefit from international career paths. Implement sustainable ideas in close cooperation with other specialists and contribute to influencing our future. Come and join us in reinventing light every day. Light is OSRAM 5 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Contents 3.8 Image Smoothing Using Frequency Domain Filters 47 3.9 Image Sharpening Using Frequency Domain Filters 50 3.10 Summary 56 3.11 References and Further Reading 56 3.12 Problems 56 4 Image Restoration 57 4.1 Image degradation and restoration 57 4.2 Noise analysis 57 4.3 Restoration with spatial analysis 60 4.4 Restoration with frequency analysis 63 4.5 Motion blur and image restoration 66 4.6 Geometric transformation 69 4.7 References 360° 70. 4.8 Problems 71 thinking 360° thinking. 360° thinking. Discover the truth at www.deloitte.ca/careers Dis © Deloitte & Touche LLP and affiliated entities. Discover the truth at www.deloitte.ca/careers © Deloitte & Touche LLP and affiliated entities. Deloitte & Touche LLP and affiliated entities. Discover the truth 6 at www.deloitte.ca/careers Click on the ad to read more Download free eBooks at bookboon.com © Deloitte & Touche LLP and affiliated entities. Digital Image Processing Part I Preface Preface Digital image processing is an important research area. The techniques developed in this area so far require to be summarized in an appropriate way. In this book, the fundamental theories of these techniques will be introduced. Particularly, their applications in image denoising, restoration, and segmentation will be introduced. The entire book consists of four chapters, which will be subsequently introduced. In Chapter 1, basic concepts in digital image processing are described. Chapter 2 will see the details of image transform and spatial filtering schemes. Chapter 3 introduces the filtering strategies in the frequency domain, followed by a review of image restoration approaches described in Chapter 4. 7 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction 1 Introduction 1.1 Digital image processing Digital image processing is the technology of applying a number of computer algorithms to process digital images. The outcomes of this process can be either images or a set of representative characteristics or properties of the original images. The applications of digital image processing have been commonly found in robotics/intelligent systems, medical imaging, remote sensing, photography and forensics. For example, Figure 1 illustrates a real cardiovascular ultrasonic image and its enhanced result using a Wiener filter that reduces the speckle noise for a higher signal-to-noise ratio. (a) (b) Figure 1 Illustration of image enhancement by applying a Wiener filter to a cardiovascular ultrasonic image: (a) original, (b) enhanced image. Digital image processing directly deals with an image, which is composed of many image points. These image points, also namely pixels, are of spatial coordinates that indicate the position of the points in the image, and intensity (or gray level) values. A colorful image accompanies higher dimensional information than a gray image, as red, green and blue values are typically used in different combinations to reproduce colors of the image in the real world. The RGB color model used in the color representation is based on the human perception that has attracted intensive studies with a long history. One example area of the RGB decomposition can be found in Figure 2. The present RGB color model is based on the Young-Helmholtz theory of trichromatic color vision, which was developed by Thomas Young and Herman Helmhotz in the early to mid nineteenth century. The Young-Helmholtz theory later led to the creation of James Clerk Maxwell’s color triangle theory presented in 1860. More details on this topic can be found in. 8 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction (a) (b) (c) (d) Figure 2 An RGB image along with its R, G and B components: (a) RGB image, (b) R component, (c) G component and (d) B component. 1.2 Purpose of digital image processing The main purpose of digital image processing is to allow human beings to obtain an image of high quality or descriptive characteristics of the original image. In addition, unlike the human visual system, which is capable of adapting itself to various circumstances, imaging machines or sensors are reluctant to automatically capture “meaningful” targets. For example, these sensory systems cannot discriminate between a human subject and the background without the implementation of an intelligent algorithm. Figure 3 denotes a successful example where a human object is separated from his background using a k-means clustering algorithm, which is part of the technologies developed in digital image processing. We use this example to justify the importance and necessity of digital image processing. To separate the human object from the background, subsequent processes will be employed. These processes can be low-, mid- and high-level. Low-level processes are related to those primitive operators such as image enhancement, and mid-level processes will get involved in image segmentation, and object classification. Finally, high-level processes are intended to find certain objects, which correspond to the pre-requisite targets. The following description provides more details about the object segmentation, shown in Figure 3. 9 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction (a) (b) Figure 3 Illustration of human object segmentation from the background using a k-means clustering approach. Low-level processes are not desirable in this particular example. This is due to the fact that the original image has been acquired in a good condition and hence no evidence of image blurring occurs. During the mid-level processes, a manual assignment of cluster centers is achieved by a professional. This leads to optimal clustering of image intensities by the automatic k-means clustering. If necessary, the extracted object will be used to generate human identity, which is one of the high-level processes. Up to now, it is clear that without digital image processing one will not be able to generate “meaningful” object in this example and beyond. 1.3 Application areas that use digital image processing The applications of digital image processing have been tremendously wide so that it is hard to provide a comprehensive cover in this book. While being categorized according to the electromagnetism energy spectrum , the areas of the application of digital image processing here are summarized in relation to the service purpose. This is motivated by the fact that one particular application (e.g. surveillance) may get different sensors involved and hence presents confusing information in the categorization. In general, the fields that use digital image processing techniques can be divided into photography, remote sensing, medical imaging, forensics, transportation and military application but not limited to. Photography: This is a process of generating pictures by using chemical or electronic sensor to record what is observed. Photography has gained popular interests from public and professionals in particular communities. For example, artists record natural or man-made objects using cameras for expressing their emotion or feelings. Scientists have used photography to study human movements (Figure 4). 10 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction Figure 4 Study of human motion (Eakins Thomas, 1844–1916). Remote sensing: This is a technology of employing remote sensors to gather information about the Earth. Usually the techniques used to obtain the information depend on electromagnetic radiation, force fields, or acoustic energy that can be detected by cameras, radiometers, lasers, radar systems, sonar, seismographs, thermal meters, etc. Figure 5 illustrates a remote sensing image collected by a NASA satellite from space. Figure 5 An example of remote sensing images (image courtesy of NASA, USA). Medical imaging: This is a technology that can be used to generate images of a human body (or part of it). These images are then processed or analyzed by experts, who provide clinical prescription based on their observations. Ultrasonic, X-ray, Computerized Tomography (CT) and Magnetic Resonance Imaging (MRI) are quite often seen in daily life, though different sensory systems are individually applied. Figure 6 shows some image examples of these systems. 11 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction (a) (b) (c) Figure 6 Medical image examples: (a) ultrasound, (b) X-ray and (c) MRI. Forensics: This is the application of different sciences and technologies in the interests of legal systems. The purpose of digital image processing in this field is used to be against criminals or malicious activities. For example, suspicious fingerprints are commonly compared to the templates stored in the databases (see Figure 7). On the other hand, DNA residuals left behind by the criminals can be corresponding to their counterparts saved in the DNA banks. We will turn your CV into an opportunity of a lifetime Do you like cars? Would you like to be a part of a successful brand? Send us your CV on We will appreciate and reward both your enthusiasm and talent. www.employerforlife.com Send us your CV. You will be surprised where it can take you. 12 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Introduction Figure 7 A fingerprint image. Transportation: This is a new area that has just been developed in recent years. One of the key technological progresses is the design of automatically driven vehicles, where imaging systems play a vital role in path planning, obstacle avoidance and servo control. Digital image processing has also found its applications in traffic control and transportation planning, etc. Military: This area has been overwhelmingly studied recently. Existing applications consist of object detection, tracking and three dimensional reconstructions of territory, etc. For example, a human body or any subject producing heat can be detected in night time using infrared imaging sensors (Figure 8). This technique has been commonly used in the battle fields. Another example is that three dimensional recovery of a target is used to find its correspondence to the template stored in the database before this target is destroyed by a missile. Figure 8 An infrared image of tanks (image courtesy of Michigan Technological University, USA). 13 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction 1.4 Components of an image processing system An image processing system can consist of a light source that illuminates the scene, a sensor system (e.g. CCD camera), a frame grabber that can be used to collect images and a computer that stores necessary software packages to process the collected images. Some I/O interfaces, the computer screen and output devices (e.g. printers) can be included as well. Figure 9 denotes an image processing system. Figure 9 Components of an image processing system. 1.5 Visual perception Digital image processing is performed in order that an image does fit the human visual judgments. Before our study goes further, the human visual system has to be studied so that the target of image processing can be properly defined. In this subsection, we briefly describe the vision principle of the human eye. Figure 10 Illustration of eye anatomy (image courtesy of ). 14 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction The reflected light from the object enters the external layer that coats the front of the eye, which is called the cornea (see Figure 10). Afterwards, the light passes through some watery fluid namely the aqueous humor. Then the light reaches the iris that may contract or dilate so as to limit or increase the amount of light that strikes the eye. Passing through the iris, the light now arrives at the pupil, a black dot in the centre of the eye, and then reaches the lens. The lens can change its shape in order to obtain focus on reflected light from the nearer or further objects. 1.6 Image acquisition Images are generated from the combination of an illuminant source and the reflection of energy from the source. In general, images can be two dimensional (2-D) or three-dimensional (3-D), depending on the used sensors and methodologies. For example, a set of 2-D cardiovascular images can be piled up to form a 3-D image using an automatic correspondence algorithm. These 3-D reconstruction techniques will be detailed in later chapters. Image acquisition can be categorized to single sensor, sensor strips, and sensor arrays based. For example, a photodiode is made of a single sensor (see Figure 11). Computerized tomography uses sensor strips to measure the absorption of x-ray that penetrates the human body. Figure 12 shows one of these systems. An ordinary camera (e.g. Olympus E-620) is based on rugged arrays that normally consist of millions elements. e Graduate Programme I joined MITAS because for Engineers and Geoscientists I wanted real responsibili www.discovermitas.com Maersk.com/Mitas e G I joined MITAS because for Engine I wanted real responsibili Ma Month 16 I was a construction Mo supervisor ina const I was the North Sea super advising and the No Real work he helping foremen advis International al opportunities Internationa ree wo work or placements ssolve problems Real work he helping fo International Internationaal opportunities ree wo work or placements ssolve pr 15 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Introduction Figure 11 Illustration of a photodiode. Figure 12 Illustration of a computerized tomography system (image courtesy of ). 1.7 Image sampling and quantization 1.7.1 Basic concepts in sampling and quantization An image consists of an indefinite number of points with continuous coordinates and amplitudes. To convert this image to digital form, both the image coordinates and amplitudes must be discretized, where the image points will be changed to pixels while the amplitudes use discrete values. Sampling refers to digitization of the coordinates, and quantization is the digitization of the amplitude values. Figure 13 shows an example of image sampling and quantization, where (b) reveals that the image resolution is reduced, whilst (c) indicates that gray levels decrease, compared to (a). 16 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction (a) (b) (c) Figure 13 Illustration of image sampling and quantization: (a) original, (b) sampling and (c) quantization. 1.7.2 Representing digital images An image is normally represented in matrix form, originating from the upper left corner. Also, an image consists of a certain number of gray levels. For example, if it has 2m gray levels, this image is referred to “m-bit image”. One of the regular manipulations on the image is zooming or shrinking. Either way may bring down the resolutions of the original image due to interpolation or extrapolation of image points. One of the commonly noticed image problem is aliasing. This phenomenon appears when the interval of image sampling is higher than a half of the distance between two neighboring images points. As a result, the Moiré pattern effect will appear and seriously deteriorate the image quality. 1.8 Basic relationship between pixels 1.8.1 Neighbors of a pixel Assuming that a pixel has the coordinates (x, y), we then have its horizontal and vertical neighbors which have coordinates as follows (x+1, y), (x-1, y), (x, y+1) and (x, y-1) (1.8.1) We can have four diagonal neighbors of the point (x, y) below (x+1, y+1), (x+1, y-1), (x-1, y+1) and (x-1, y-1) (1.8.2) 1.8.2 Adjacency, connectivity, regions, and boundaries If an image point falls in the neighborhood of one particular pixel, we then call this image point as the adjacency of that pixel. Normally, there are two types of adjacency, namely 4- and 8-adjacency: 1) 4-adjacency: Two pixels are 4-adjacent if one of them is in the set with four pixels. 2) 8-adjacency: Two pixels are 8-adjacent if one of them is in the set with eight pixels. One example is shown below, where red “1s” form the 8-adjacency set. 17 Download free eBooks at bookboon.com Digital Image Processing Part I Introduction Connectivity is relevant but has certain difference from adjacency. Two pixels from a subset G are connected if and only if a path linking them also connects all the pixels within G. In addition, G is a region of the image as it is a connected subset. A boundary is a group of pixels that have one or more neighbors that do not belong to the group. 1.8.3 Distance measures Assuming there are two image points with coordinates (x, y) and (u, v). A distance measure is normally conducted for evaluating how close these two pixels are and how they are related. A number of distance measurements have been commonly used for this purpose, e.g. Euclidean distance. Examples of them will be introduced as follows. 18 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Introduction The Euclidean distance between two 2-D points I(x1,y1) and J(x2,y2) is defined as: ( x1 − x2 ) 2 + ( y1 − y 2 ) 2 (1.8.3) The City-block distance between two 2-D points (x1,y1) and (x2, y2 ) can be calculated as follows: | x1 − x2 | + | y1 − y 2 | (1.8.4) For the above two 2-D image points, the Chessboard distance is max( | x1 − x 2 |, | y1 − y 2 | ) (1.8.5) 1.9 Summary In this chapter, basic concepts and principles of digital image processing have been introduced. In general, this chapter started from the introduction of digital image processing, followed by a summary of different applications of digital image processing. Afterwards, the fundamental components of an image processing systems were presented. In addition, some commonly used techniques have been summarized. In spite of their incomplete stories and terse descriptions, these presented contents are representative and descriptive. The knowledge underlying with this introduction will be used in later chapters for better understanding of advanced technologies developed in this field. 1.10 References http://en.wikipedia.org/wiki/RGB, accessed on 29 September, 2009. R.C. Gonzalez and R.E. Woods, Digital Image Processing, 2nd version, Prentice-Hall, Inc. New Jersey, 2002. http://www.webmd.com/eye-health/amazing-human-eye, accessed on 29 September, 2009. http://www.imaginis.com/ct-scan/how_ct.asp, accessed on 29 September, 2009. http://en.wikipedia.org/wiki/K-means_algorithm, accessed on 29 September, 2009. 1.11 Problems (1) What is digital image processing? (2) Why do we need digital image processing? (3) Please summarize the applications of digital image processing in the society. (4) How is the human visual perception formed? (5) What is the difference between image sampling and quantization? (6) What is the difference between adjacency and connectivity? (7) How to compute the Euclidean distance between two pixels? 19 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2 Intensity transformations and spatial filtering 2.1 Preliminaries In this chapter, we will discuss about some basic image processing techniques that include the intensity transforms and spatial filtering. All the techniques introduced here will be performed in the spatial domain. 2.2 Basic Intensity Transformation Functions Photographic Negative: This is perhaps the simplest intensity transform. Supposing that we have a grey level image in the range [0,1], it is expected to transform the black points (0s) into the white ones (1s), and the white pixels (1s) ~ f ( x, y ) =that into the black ones (0s). This simple transform can be denoted by (assume 1 − f ( x, y ) is normalized into the range [0,1]) ~ f ( x, y ) = 1 − f ( x, y ) (2.2.1) For a 256 gray level image, the transform can be accomplished by ~ f ( x, y ) = 1 − f ( x, y ) / 256 (2.2.2) An example of the Photographic Negative transform is shown in Figure 14. (a) (b) Figure 14 A panda Image (a), and its photographic negative transformed image (b). 20 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering Gamma Transform Gamma transform is also called power-law transform. It is mathematically denoted as follows: ~ f ( x, y ) = c ∗ f ( x, y ) γ (2.2.3) ~ f ( xwhere , y ) = c ∗and ) γ two constants. The gamma transform can make pixels look brighter or darker f ( xγ, yare depending on the value of γ. When ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻ is within the range [0,1] and γ is larger than one, it makes the image darker. When γ is smaller than one, it makes the image look brighter. Figure 15 shows the output of the Gamma transform against different inputs with the parameters set as 0.5, 1 and 2 (ܿ ൌ ͳ). From this plot, we can see that the curve with γ = 2 is below the curve with γ = 1. This indicates that the output is smaller than the input, which explains why an image in the Gamma transform, when γ = 2, will become darker. 21 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering Figure 15 The plot of the Gamma transform against different parameters. Horizontal axis is the input, and vertical is the output. Figure 16 shows that the Gamma transformed panda image under different parameter values (c = 1). (a) (b) Figure 16 Gamma transformed images different parameters. (a) Gamma = 2 ; (b) Gamma = 0.5. 2.3 Histogram Processing Histogram is one simple but very important statistical feature of an image. It has been commonly used in image processing. Intensity histogram is a distribution of the grey level values of all the pixels within the image. Each bin in the histogram represents the number of pixels whose intensity values fall in that particular bin. A 256 grey level histogram is often used, where each grey level corresponds to one bin. Using bi to represent the ith number of bins, the histogram can be represented as follows: ݄ሺ݅ሻ ൌ ͓ሼሺ‫ݔ‬ǡ ‫ݕ‬ሻǡ ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ‫ܾ݅ א‬ሽ (2.3.1) 22 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering where # represent the Cardinality of the set. Though it is possible to show the histogram of a color image, in this chapter we mainly focus on the gray level histogram. The color histogram will be shown in Chapter 1 (Digital Image Processing – Part Two). Figure 17 shows an image and its grey level histogram of 64 bins. (a) (b) Figure 17 A mountain image (a) and its 64 bins grey level histogram (b). 2.3.1 Histogram Equalization It is a fact that the histogram of an intensity image lies within a limited data range. Those images usually have black or white foreground and background. Figure 18 shows an image example whose intensity distribution is either black or white. From Figure 18 (b), we can see that a very large portion of pixels whose intensity rests within the range [0, 50] or [180, 255]. A very small portion of pixel resides in the range of [50, 180]. This makes some details of the image hardly visible, e.g. the trees on the mountains in the image shown in Figure 18 (a). This problem can be solved by a histogram stretching technique called histogram equalization. The basic idea of histogram equalization is to find the intensity transform such that the histogram of the transformed image is uniform. Of the existing probabilistic theories, there exists such an intensity transform. Suppose that we have an image ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻ, and its histogram h(i), we have the accumulative function of h(i) as follows: ௜ ܿሺ݅ሻ ൌ ‫׬‬଴ ݄ሺ‫ݐ‬ሻ ݀‫ݐ‬ (2.3.1.1) It can be proved that such a transform makes the variable y = c(i) follow a uniform distribution. Thus, for a 256 grey level image, the histogram equalization can be performed by the following equation: ଶହ଺ ‫ݐ‬ൌ ‫ܿ כ‬ሺ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻሻ (2.3.1.2) ௡ where is the total number of pixels in the image. 23 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering (a) (b) Figure 18 (a) The mountain image after histogram equalization, and (b) histogram. Excellent Economics and Business programmes at: “The perfect start of a successful, international career.” CLICK HERE to discover why both socially and academically the University of Groningen is one of the best places for a student to be www.rug.nl/feb/education 24 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2.3.2 Histogram Matching Histogram Equalization is a special case of histogram matching. The general purpose of histogram matching is to find a transform that can adjust an image by converting its histogram to a specified histogram a priori. As we have learnt from the above discussion, the desired histogram in histogram equalization is a uniform distribution. In this case, there exists a transformation as shown in Eq. (2.3.1.2). A straightforward implementation can be achieved. However, in more general case we may want the desired histogram to be a specific shape and to adjust the image based on this histogram. This operation is called histogram matching. It can be achieved by matching the accumulative distributions of the original histogram and desired histogram. Step by step, it can be implemented as follows: 1) Compute the histogram of the original image f (x, y) and its accumulated distribution c(i). 2) Compute the accumulated distribution of the desired histogram d(i). 3) Compute the desired intensity g (x, y) at location (x, y) by matching the d(i) and c(i) using minimum distance criteria (nearest n) as follows: ݃ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൌ ݅ ‫ כ‬ൌ ௜ ሺȁ݀ሺ݅ሻ െ ܿሺ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻሻȁ (2.3.2.1) Figure 19 shows some internal results of the above steps on the image shown in Figure 17 (a). (a) (b) (c) (d) Figure 19 (a) The accumulated histogram of the image in Figure 2.3.1 (a); (b) the desired histogram; (c) the desired accumulated histogram; (d) the adjusted image based on image matching according to Eq. (2.3.2.1). 25 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2.4 Fundamentals of Spatial Filtering Filtering is a fundamental operation in image processing. It can be used for image enhancement, noise reduction, edge detection, and sharpening. The concept of filtering has been applied in the frequency domain, where it rejects some frequency components while accepting others. In the spatial domain, filtering is a pixel neighborhood operation. Commonly used spatial filtering techniques include median filtering, average filtering, Gaussian filtering, etc. The filtering function sometimes is called filter mask, or filter kernel. They can be broadly classified into two different categories: linear filtering and order- statistic filters. In the case of linear filtering, the operation can be accomplished by convolution, i.e., the value of any given pixel in the output image is represented by the weighted sum of the pixel values of its neighborhood (a linear combination) in the input image. For order-statistic filter, the value of a given pixel in the output image is represented by some statistics within its support neighborhood in the original image, such as the median filter. Those filters are normally non-linear and cannot be easily implemented in the frequency domain. However, the common elements of a filter are (1) A neighbourhood (2) an operation on the neighbourhood including the pixel itself. Typically the neighbourhood is a rectangular of different size, for example 3×3, 5×5 … and smaller than the image itself. 2.5 Smoothing Spatial Filters 2.5.1 Smoothing Linear Filters As stated above, linear filters have observed their output values as the linear combination of the inputs. The commonly used smoothing filters are averaging and Gaussian filters. The smoothing filters usually have the effect of noise reduction (also called low pass filtering, which will be discussed in the next chapter). It can be performed using the convolution operation. ெȀଶ ேȀଶ ‫ݏ‬ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൌ σ௠ୀିெȀଶ σ௡ୀିேȀଶ ݄ሺ݉ǡ ݊ሻ݂ሺ‫ ݔ‬െ ݉ǡ ‫ ݕ‬െ ݊ሻ (2.5.1.1) ݄ሺ݉ǡ ݊ሻ is a filtering mask of size MxN. Each element in this filter mask usually represents the weights used in the linear combination. The types of different linear filters correspond to different filter masks. The sum of all the elements in ݄ሺ݉ǡ ݊ሻ will affect the overall intensities of the output image. Therefore, it is sensible to normalize ݄ሺ݉ǡ ݊ሻ such that the sum is equal to one. In the case of negative values in ݄ሺ݉ǡ ݊ሻ, the sum is typically set to zero. For smoothing (low pass filters), the values in the mask must be positive; otherwise, this mask will contain some edges (sharpening filters). The linear filter can also be performed using correlation as follows: ெȀଶ ேȀଶ ‫ݏ‬ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൌ σ௠ୀିெȀଶ σ௡ୀିேȀଶ ݄ሺ݉ǡ ݊ሻ݂ሺ‫ ݔ‬൅ ݉ǡ ‫ ݕ‬൅ ݊ሻ (2.5.1.2) If ݄ሺ݉ǡ ݊ሻ is symmetric, i.e. ݄ሺ݉ǡ ݊ሻ ൌ ݄ሺെ݉ǡ െ݊ሻ, the correlation is equivalent to convolution. 26 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering Average Filtering The average filtering is also called mean filtering, where the output pixel value is the mean of its neighborhood. Thus, the filtering mask is as follows (3×3 as an example) ͳ ͳ ͳ ݄ ൌ ͳȀͻ อͳ ͳ ͳอ (2.5.1.2) ͳ ͳ ͳ In practice, the size of the mask controls the degree of smoothing and loss of the details. Gaussian Filtering Gaussian filtering is another important filter. The weights in the filter mask are of a Gaussian function (here we assume it is isotropic): ଵ ݄ሺ݉ǡ ݊ሻ ൌ ሺെͲǤͷ ‫ כ‬ሺ݉ଶ ൅ ݊ଶ ሻ Ȁߪሻ (2.5.1.3) ௓ where σ is the variance and controls the degree of smoothing. The larger value σ is, the larger degree smoothing can be achieved. For example, the 3×3 Gaussian filter with σ set as 1 is represented by the following equation. ͲǤ͸Ͳ ͲǤͳͲ ͲǤ͸Ͳ ݄ሺ݉ǡ ݊ሻ ൌ อͲǤͳͲ ͲǤͳ͸ ͲǤͳͲอ (2.5.1.4) ͲǤ͸Ͳ ͲǤͳͲ ͲǤ͸Ͳ Figure 20 shows the Gaussian mask of size 5×5, Figure 20 The 3D plot of the Gaussian filter with the variance set as 1. 27 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering Figure 21 shows the Lenna image as well as the filtered images using mean filtering with different mask sizes and Gaussian filtering with different. We can see that with the increment of the mask size of the mean filter, the level of smoothing becomes stronger. This also holds for the Gaussian filtering with different. (a) (b) (c) (d) (e) (f) (g) Figure 21 (a) The Lenna image; (b) (c) (d) filtered images using mean filtering with mask size 3, 7, 11; (e) (f ) (g) filtered images using Gaussian filtering with different variances at 1, 5, 9. 28 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2.5.2 Order-Statistic Filters The order-statistical filters are usually non linear filters, which are hardly represented by convolution. Commonly used filters include median filter. There are some other filters as well such as max/min filter. The median filter simply replaces the value of the pixel with the median value within its neighborhood. Similarly, the max/min filter replaces the value of the pixel with the maximum/minimum value within its neighborhood. Figure 22 shows the filtered image using a median filter of different mask sizes. (a) (b) (c) Figure 22 Filtered Lenna image using median filtering of different masks 3, 7, and 11. American online LIGS University is currently enrolling in the Interactive Online BBA, MBA, MSc, DBA and PhD programs: ▶▶ enroll by September 30th, 2014 and ▶▶ save up to 16% on the tuition! ▶▶ pay in 10 installments / 2 years ▶▶ Interactive Online education ▶▶ visit www.ligsuniversity.com to find out more! Note: LIGS University is not accredited by any nationally recognized accrediting agency listed by the US Secretary of Education. More info here. 29 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2.6 Sharpening filters The objective of sharpening is to draw the attention to the fine details of an image. This is also related to the situation where an image that has been blurred and now needs to be de-blurred. In contrast to the process of image smoothing that normally uses pixel averaging techniques, sharpening can be conducted using spatial differentiation. The image differentiation actually enhances edges and other discontinuities and depresses the areas of slowly changing gray-level values. The derivative of a function is determined via differencing. A basic first-order derivative of a one- dimensional function f(x) is ∂f = f ( x + 1) − f ( x) (2.6.1) ∂x Similarly, a second-order derivative can be defined as follows: ∂2 f = f ( x + 1) + f ( x − 1) − 2 f ( x) (2.6.2) ∂x 2 In this section, we mainly talk about the use of two-dimensional and second-order derivatives for image sharpening. It is inevitable to mention the concept of isotropic filters, whose response is independent of the discontinuity direction in the image. One of the simple isotropic filters is the Laplacian, which is defined as follows with a function f(x, y): ∂2 f ∂2 f ∇2 f = + (2.6.3) ∂x 2 ∂y 2 Where ∂2 f = f ( x + 1, y ) + f ( x − 1, y ) − 2 f ( x, y ) (2.6.4) ∂x 2 ∂2 f (2.6.5) = f ( x, y + 1) + f ( x, y − 1) − 2 f ( x, y ) ∂y 2 Then the two-dimensional Laplacian is obtained summing the two components: 2 [ ( 1, ) ( 1, ) ( , 1) ( , 1)] 4 ( , ) (2.6.6) 30 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering To implement Eq. (2.6.6) we illustrate four filter masks used for the Laplacian in Figure 23. 0 1 0 1 -4 1 0 1 0 1 1 1 1 -8 1 1 1 1 0 -1 0 -1 4 -1 0 -1 0 -1 -1 -1 -1 8 -1 -1 -1 -1 Figure 23 Filter masks used in the Laplacian enhancement. Such a Laplacian enhancement can be described as  f ( x, y ) − ∇ 2 f ( x, y ) F ( x, y ) =  (2.6.7)  f ( x, y ) + ∇ 2 f ( x, y ) 31 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering To simplify the Laplacian we have ( , ) ( , ) [ ( 1, ) ( 1, ) ( , 1) ( , 1)] (2.6.8) One of the examples using the Laplacian is shown in Figure 24. (a) (b) (c) (d) Figure 24 Image sharpening and histograms: (a) original image and its histogram (c), (b) shapened image and its histogram (d). For a function f(x, y), the gradient of f is defined as  ∂f   ∂x  ∇f =   (2.6.9)  ∂f   ∂y  32 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering In the implementation, this equation can be changed to ∇f ≈| ( z 7 + 2 z 8 + z 9 ) − ( z1 + 2 z 2 + z 3 ) | + | ( z 3 + 2 z 6 + z 9 ) − ( z1 + 2 z 4 + z 7 ) | (2.6.10) Where (z1,…,z9) are the elements of the 3×3 mask. This mask can be one of the following patterns: z1 z2 z3 z4 z5 z6 z7 z8 z9 -1 -2 -1 0 0 0 1 2 1 -1 0 1 -2 0 2 -1 0 1 Figure 25 Image mask that is used to generate gradients. 2.7 Combining image enhancement methods In real applications, it is hard to know what kind of noise has been added to an image. Therefore, it is difficult to find a unique filter that can appropriately enhance this noisy image. However, it is possible if several de-blurring methods can be combined in a framework in order to pursue a maximum denoising outcome. In the section, we explain one of the combinatorial techniques using an X-ray example. Figure 26 (a) illustrates a male chest’s X-ray image. The purpose of the process is to highlight the middle cross section of the image using the combination of sharpening and edge detection. Figure 26 (b) shows the result of applying the median filter, (c) is the outcome of using Sobel edge detection, and finally (d) demonstrates the combination of the Laplacian and Sobel process. Figure 26 (d) shows the edge details in the graph, which highlights the structure of the central cross section of the image. 33 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering (a) (b) (c) (d) Figure 26 Illustration of using the combination of different segmentation algorithm: (a) original, (b) median filtering, (c) Sobel edge detection and (d) combination of Laplacian and Sobel process. 2.8 Summary In this chapter, some basic image intensity transformation functions have been provided. This consists of negative and Gamma transforms. Afterwards, histogram based processing techniques were introduced. Especially, histogram equalisation and matching techniques were summarised due to their importance in image processing applications. 34 Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering To further enhance the image quality we then introduced a number of spatial filters. Particularly, we discussed about averaging filtering, Gaussian filtering, and statistic filters. Due to the needs of enhancing image contrasts, we then focused on the technical details of sharpening filters, which have been commonly used in the image processing applications. As an extension, we discussed about the applications of the combination of image enhancement methods. One of the examples is to integrate a Laplacian filter with the Sobel edge detection for better image details. 2.9 References http://www.radiologyinfo.org/en/photocat/gallery3.cfm?pid=1&Image=chest-xray. jpg&pg=chestrad, accessed on 15 October, 2009.. 35 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Intensity transformations and spatial filtering 2.10 Problems (8) Please perform the image negative and Gamma transform for the cameraman image as follows: (9) Please use the Matlab tools to generate codes to add Gaussian noise (mean = 0, variance = 2) to the above cameraman image, followed by averaging and Gaussian filtering respectively. (10) Can you find a proper sharpening filter for the following motion blurred image? (11) Why do we need to combine different filtering approaches for image enhancement? 36 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3 Filtering in the Frequency Domain 3.1 Background The Fourier transform is a fundamental mathematical tool in image processing, especially in image filtering. The name of ‘Fourier transform’ or ‘Fourier Series’ can be traced back to the date of year 1822 when a French mathematician published his famous work – the Analytic Theory of Heat. In this work, he had shown that any periodic function can be expressed as the sum of sines and cosines of different frequencies weighted by different values. This ‘sum’ interpretation is usually termed as ‘Fourier series’ (in modern mathematical theory this is in fact a special case of orthogonal decomposition of a function within one of the functional space e.g. Hilbert space, where each axis is represented by a function, e.g., the sine or cosines functions.). For non-periodic function, this type of operations is called ‘Fourier Transform’. For simplicity, in the following sections we will use the general term ‘Fourier transform’ to represent such a transform in both of the periodic and non-periodic functions. The merit of the Fourier transform is that a band limited function or signal could be reconstructed without loss of any information. As we will see, this in fact allows us to work completely in the frequency domain and then return to the original domain. Working in the frequency domain is more intuitive and can enable the design of image filters easier. Although the initial idea of the Fourier transform was applied to the heat diffusion, this idea has been quickly spread into other industrial fields and academic disciplines. With the advent of computer and discovery of the fast Fourier transform, the real-time practical processing of the Fourier transform becomes possible. In the following sections, we will show step by step the basic concept of Fourier transform from 1-D continuous function to the 2-D case. 3.2 Preliminaries 3.2.1 Impulse function and its properties Impulse function is one of the key concepts of sampling, either in spatial domain or in the frequency domain. A typical impulse function is defined as follows: λ ݂݅‫ ݔ‬ൌ Ͳ ߜሺ‫ݔ‬ሻ ൌ ቄ (3.2.1) Ͳ ‫݁ݏ݅ݓݎ݄݁ݐ݋‬ 37 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain And its integral is subject to the following constrains: ஶ ‫ି׬‬ஶ ߜሺ‫ݔ‬ሻ݀‫ ݔ‬ൌ ͳ (3.2.2) A very important feature of the impulse function is that for any continuous function f (x), the integral of the product of the function f (x) with the impulse function is simply the value of the f (x) at the location where the impulse happens. For example, if the location of the impulse is at T, the following mathematical expression can help us to get a sample from the function f (x) at T. ஶ ‫ି׬‬ஶ ݂ሺ‫ݔ‬ሻߜሺ‫ ݔ‬െ ܶሻ݀‫ ݔ‬ൌ ݂ሺܶሻ (3.2.3) The above equation implies that the operation of getting a value from the function f (x) at T can be performed by the integral of the product of this function with the impulse function at location T. This is the fundamental of the sampling theory. 3.3 Sampling and the Fourier Transform of Sampled Functions 3.3.1 Sampling In the real world, a scene or an object could be mathematically represented by a continuous function. However, in today’s digital world, to show or store an image of the scene in a computer the scene has to be converted into a discrete function. This digitalization process in fact can be called ‘sampling’. In fact, sampling is the process/operation of converting a continuous function into a discrete function. One role of this operation is that it makes the image representation tractable in a computer memory or storage and displayable on screen as well as visible to humans. In this process, a key question is what kind of sampling frequencies should be adopted in the sampling process (or which point will be selected to describe the discrete version of the function)? A sample refers to a value or set of values at a point in time and/or space. Mathematically, the sampling principle can be described as follows (beginning from simple periodic functions): Consider a continuous 1-D periodic function, ‫ݕ‬ሺ‫ݐ‬ሻ ൌ ‫ݕ‬ሺ‫ ݐ‬൅ ݊ܶሻ with ݊ ൌ Ͳǡͳǡʹǡ͵ǡ ǥ, where t represents the time in seconds. Now we are going to sample this function by measuring the value of continuous function every T seconds. T here is called sampling interval. Thus the sampled function (discrete version) can be represented by ‫ݕ‬ሾ݊ሿ ൌ ‫ݕ‬ሺ݊ܶሻǡ ݊ ൌ Ͳǡͳǡʹǡ͵ǡ ǥǤ (3.3.1) The sampling interval is an indicator of the frequency that we use to sample the function. Here we introduce a sampling frequency or rate that measures the number of samples in unit (usually in one second), f = 1/T. The sampling rate is conventionally measured in hertz or in samples per second. Intuitively, an ideal sampling rate allows us to reconstruct the original function successfully. 38 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain The output of sampling is a numerical sequence of the continuous function, usually represented by a matrix or vector of numbers. Image can be viewed as a 2D sampling version of the real world. A conventional representation of the image is a matrix of M number of rows and N number of columns. The spatial coordinates denotes the relative location of the pixels within the matrix (element index) while the entry of the matrix represents the value of the grey level intensity or color intensity at that pixel, usually represented by I(i, j). The smallest coordinates are conventionally set as (1,1) in the popular MATLAB program. Note the notation‫ܫ‬ሺ݅ǡ ݆ሻ in a matrix does not correspond to the actual physical coordinates. For example, a function f (x); x = 0,0.5,1 is represented by a matrix [f (0), f (0.5), f (1)]. The entry value at (1,2) is f (0.5) with actual physical coordinates x at 0.5. 3.3.2 The Fourier Transform of Sampled Functions The convolution theory tells us that the Fourier transform of the convolution of two functions is the product of the transforms of the two functions. Thus by applying the Fourier transform on the both side of Equation 3.2-3, we can get: ‫ܨ‬෨ ൫݂ሺ݊ܶሻ൯ ൌ ‫ܨ‬෨ ൫݂ሺ‫ݐ‬ሻ۪ߜሺ‫ݐ‬ሻ൯ ଵ ௡ ൌ σା‫ן‬ ௡ୀି‫ܨ ן‬ሺ‫ ݑ‬െ ሻ (3.3.2) ୼୘ ୼் Join the best at Top master’s programmes 3 3rd place Financial Times worldwide ranking: MSc the Maastricht University International Business 1st place: MSc International Business School of Business and 1st place: MSc Financial Economics 2nd place: MSc Management of Learning Economics! 2nd place: MSc Economics 2nd place: MSc Econometrics and Operations Research 2nd place: MSc Global Supply Chain Management and Change Sources: Keuzegids Master ranking 2013; Elsevier ‘Beste Studies’ ranking 2012; Financial Times Global Masters in Management ranking 2012 Maastricht University is the best specialist university in the Visit us and find out why we are the best! Netherlands (Elsevier) Master’s Open Day: 22 February 2014 www.mastersopenday.nl 39 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain This shows that Fourier transform of the sample function is a sampled version of the Fourier transform F(u) of continuous function f (t). Note that the sample pace in the frequency domain is the inverse of the sample pace in the spatial domain. 3.3.3 The Sampling Theorem As stated before, the reason why we discuss the sampling and Fourier transforms is to find a suitable sampling rate. Insufficient sampling may lose partial information of a continuous function. So, what is the relationship between the proper sampling interval and the function frequency? In other words, under what circumstances is it possible to reconstruct the original signal successfully (perfect reconstruction)? A partial answer is provided by the Nyquist–Shannon sampling theorem , which provides a sufficient (but not always necessary) condition under which perfect reconstruction is possible. The sampling theorem guarantees that band limited signals (i.e., signals which have a maximum frequency) can be reconstructed perfectly from their sampled version, if the sampling rate is more than twice the maximum frequency. Reconstruction in this case can be achieved using the Whittaker-Shannon interpolation formula. The frequency equivalent to one-half of the sampling rate is therefore a bound on the highest frequency that can be unambiguously represented by the sampled signal. This frequency (half the sampling rate) is called the Nyquist frequency of the sampling system. Frequencies above the Nyquist frequency can be observed in the sampled signal, but their frequency is ambiguous. This ambiguity is called aliasing later shown in Figure 27. To handle this problem effectively, most analog signals are filtered with an anti- aliasing filter (usually a low-pass filter with cutoff near the Nyquist frequency) before their conversion to the sampled discrete representation. We will show this principle using the following examples: Let us consider a simple function ݂ሺ‫ݔ‬ሻ ൌ ሺʹߨ݂ଵ ‫ݔ‬ሻ ൅ ሺʹߨ݂ଶ ‫ݔ‬ሻ with ݂ଵ set as 5 and ݂ଶ set as 10. We expect that the power spectrum of the FFT of the signal will have peaks at 5 and 10. Figure 27 (a) shows the original signal and (b) show the power spectrum. As expected, we can observe two peaks at u = 5 and 10 respectively in (b). According the Nyquist–Shannon sampling theorem, the minimum sampling rate is at least equal to the two times of the highest frequency of the signal. In our example, the trade-off rate is 20 (2×10). We now sample this signal with a rate larger than 20, say 40 to see what happens. Figure 27 (c) shows the sampled signal using this rate, and (d) shows the corresponding power spectrum. We can see that the signal looks quite similar to the original one with the peaks at frequency 5 and 10. This is sometimes called oversampling and leads to a perfect reconstruction of the signal. Another case is to sample the signal at a lower rate than 20, for instance 10. Figure 27 (d) and (f) show the sampled signal using rate 10 and its power spectrum. From this figure, we can see that trend of the signal is not preserved and the power spectrum looks different from the original one in (b). This is called under-sampling or frequency aliasing. In practice, most signals are band infinite. That means they usually have a very infinite frequency. The effect of aliasing almost exists in every case. However, in the case of high quality imaging system such an aliasing is not visually observable by human eyes. 40 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain (a) (b) (c) (d) 41 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain (e) (f ) Figure 27 Illustration of the sampling theorem: (a) original; (b) the power spectrum; (c) the sampled signal at sampling rate 40 (oversampling); (d) the power spectrum of (c); (e) the sampled signal at sampling rate 10 (under sampling); (f ) the power spectrum of (e). AXA Global Graduate Program Find out more and apply 42 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3.4 Discrete Fourier Transform 3.4.1 One Dimensional DFT Let us start with the 1-D discrete Fourier transform (DFT) for a discrete function ݂ሺ‫ݔ‬ሻ for‫ ݔ‬ൌ Ͳǡͳǡʹ ǥ ‫ ܯ‬െ ͳ. Its 1D Fourier transform can be calculated as follows: ࡲሺ࢛ሻ ൌ σࡹି૚ ࢞ୀ૙ ࢌሺ࢞ሻ ࢋ ି࢐࣓ , (3.4.1) ࢛࢞ ɘ ൌ ૛࣊ ቀ ቁ (3.4.2) ࡹ where ‫ ݑ‬ൌ Ͳǡͳǡʹǡ ǥ ‫ ܯ‬െ ͳ. is usually called frequency variables, similar to the coordinates ‫ ݔ‬in the spatial domain. The exponential on the right side of the equation can be expanded into sinuses and cosines with variables determining their frequencies as follows: ݁ ି௝ఠ ൌ ሺɘሻ ൅ ݆‫݊݅ݏ‬ሺ߱ሻ, (3.4.3) The inverse discrete Fourier transform is: ଵெିଵ ݂ሺ‫ݔ‬ሻ ൌ σ௨ୀ଴ ‫ܨ‬ሺ‫ݑ‬ሻ݁ ௝ఠ , (3.4.4) ெ 3.4.2 Relationship between the Sampling and Frequency Intervals Consider a discrete function with the fixed sample interval ΔT (i.e., the time duration between samples) and it contains N samples. Thus the total duration of the function is ‫ ܦ‬ൌ ܰ ‫ כ‬ȟܶ. Using Δu to represent the spacing in the Fourier frequency domain, the maximum frequency (i.e., the entire frequency range, also the maximum samples that will get during a time unit, usually per second) is just the inverse of the sampling interval. ൌ ͳȀȟܶ (3.4.5) Note that we have data samples and the frequency domain also has the same number of samples. ௎ ଵ The spacing per sample can be calculated as ȟ‫ ݑ‬ൌ ே ൌ ୼்‫כ‬ே. Thus, the relationship between ΔT and Δu can be stated using the following equation: ȟܶ ൌ ܰ ‫ כ‬ȟ‫ݑ‬ (3.4.6) 43 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3.5 Extension to Functions of Two Variables Similar to the 1D Fourier transform, the 2-D discrete Fourier transform can be expressed as follows: ೠೣ ೡ೤ ି௝ଶగቀ ା ቁ ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ σேିଵ ெିଵ ௬ୀ଴ σ௫ୀ଴ ‫ܫ‬ሺ‫ݔ‬ǡ ‫ݕ‬ሻ݁ ಾ ಿ , (3.5.1) Where I(x, y) is the original image of size M × N. u and v are in the same range. The inverse Fourier Transform is defined as follows: ೠೣ ೡ೤ ଵ ௝ଶగቀ ା ቁ ‫ܫ‬ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൌ σேିଵ ெିଵ ௩ୀ଴ σ௨ୀ଴ ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ݁ ಾ ಿ (3.5.2) ெே where F(u, v) is the Fourier transform of the original image. Usually the Fourier transform is complex in general. It can be written in the polar form: ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ܽ ൅ ܾ݆ ൌ ȁ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻȁ݁ ௝థሺ௨ǡ௩ሻ (3.5.3) And we have the magnitude and the phase angle as follows: ȁ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻȁ ൌ ሺܽଶ ൅ ܾ ଶ ሻ଴Ǥହ (3.5.4) ௔ ߶ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ିଵ ሺ ሻ, (3.5.5) ௕ The power spectrum is the square of the magnitude |F(u, v)|. Figure 28 shows an image, its power spectrum and phase angle respectively. (a) (b) (c) Figure 28 An image of sunflower (a), its power spectrum (b), and its phase component (c). 44 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3.6 Some Properties of the 2-D Discrete Fourier Transform The 2D Fourier transform has the following properties that are often used. 1) Translation invariant (magnitude). If a function I(x, y) is translated by an offset (ȟ‫ݔ‬ǡ ȟ‫ݕ‬ሻ, ೠ౴ೣ ೡ౴೤ its Fourier transform becomes ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ݁ ି௝ଶగቀ ಾ ା ಿ ቁ. We can see that the translation in ೠ౴ೣ ೡ౴೤ ି௝ଶగቀ ା ቁ the spatial domain only affects the phase component by ݁ ಾ ಿ. The magnitude ȁ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻȁ is not affected. 2) Periodicity. The 2D Fourier transform and its inverse are infinitely periodic ‫ ݑ‬in the and v directions. 3) symmetry: a) The Fourier transform of a real function is conjugate symmetric: ‫ כ ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ‫ܨ‬ሺെ‫ݑ‬ǡ െ‫ݒ‬ሻ, and the magnetite is always symmetric, i.e, ȁ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻȁ ൌ ȁ‫ܨ‬ሺെ‫ݑ‬ǡ െ‫ݒ‬ሻȁ. b) The Fourier transform of a real and even function is symmetric: ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ‫ܨ‬ሺെ‫ݑ‬ǡ െ‫ݒ‬ሻ. 4) Linearity: The Fourier transform of the sum of two signals equals to the sum of the Fourier transform of those two signals indepedently. ݃ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൅ ݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻ ൏ൌ൐ ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൅ ‫ܩ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ 5) Scaling: If the signal is spatially scaled wider or smaller, the corresponding Fourier transform will be scaled smaller or wider. The magnitude is also smaller or wider. ଵ ௨ ௩ ݂ሺߙ‫ݔ‬ǡ ߚ‫ݕ‬ሻ ൏ൌ൐ ‫ܨ‬ሺ ǡ ሻ. ௔ఉ ௔ ఉ Need help with your dissertation? Get in-depth feedback & advice from experts in your topic area. Find out what you can do to improve the quality of your dissertation! Get Help Now Go to www.helpmyassignment.co.uk for more info 45 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain The Fourier transform also has other properties. For a complete list of properties, interested readers may refer to some handbooks of signal/image processing and sites like Wikipedia and Mathworld. 3.7 The Basics of Filtering in the Frequency Domain As we have stated in Chapter 2, in the spatial domain the filtering operation is sometimes performed by the convolution operation with a filtering mask (Note this is the case for linear filter. For nonlinear filter, such as the median filter, the operation can NOT be performed in terms of convolution due the linearity of convolution). Fortunately, there exist some relationship between the convolution and Fourier transform as follows: Աሺ݃ሺ‫ݔ‬ǡ ‫ݕ‬ሻ۪݂ሺ‫ݔ‬ǡ ‫ݕ‬ሻሻ ൌ ‫ܩ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ, (3.7.1) where ⊗ denotes the convolution operator, ℑ represents the Fourier transform operation. Here the Fourier transform of the result of convolution between two functions is the product of the Fourier transform of those two functions respectively. The Fourier transform provides a direct theoretical explanation of the filtering technique used in the spatial domain. Using this technique, we have an intuitive perception of which frequency will be used to filter the signal. A straightforward step in the filtering design is to select a filter which removes some signals at certain frequency bands that we do not want to keep. The design of the filter will be down to how to specify F(u, v) – the Fourier transform of the spatial filter mask f (x, y). F(u, v) can be referred to as the filter transfer function. A good example is the commonly used filtering mask – Gaussian filtering. Figure 29 shows an Gaussian filter function in the space domain and its power spectrum in frequency domain. Note the difference between the variance. (a) (b) Figure 29 A Gaussian filter in the frequency domain (a) and its power spectrum in the frequency domain (b). 46 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3.8 Image Smoothing Using Frequency Domain Filters In this section we will introduce three main low pass filters including ideal lowpass Filters, Butterworth lowpass filters as well as Gaussian lowpass filters. In the following section, we will use the panda image to show the principles of the different filters: (a) (b) Figure 30 An image of a panda (a), and its power spectrum of the gray level image (b). 3.8.1 Ideal Lowpass Filters An ideal low pass filter is to switch off some high frequency signals and to allow the low frequency signal to get through based on a threshold. Mathematically, it is defined as follows: Ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൒ ܶͲ ‫ܯ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ൜ (3.8.1) ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൏ ܶͲ Here, T0 is a threshold, usually a nonnegative number. It represents the square of the radius distance from the point ሺ‫ݑ‬ǡ ‫ݒ‬ሻ to the center of the filter, usually called cut-off frequency. Intuitively, the set of ‫ݑ‬ଶ ൅ ‫ݒ‬ଶ ൌ ܶ଴ points at forms a circle. It blocks signals outside the circle by multiplying 0 and passes the signals outside the circle by multiplying 1. By doing this, we get the following filtered results in the frequency domain: Ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൒ ܶ଴ ‫ܫ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻǤ‫ܯ כ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ൜ (3.8.2) ‫ܫ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൏ ܶ଴ The operator represents the element wise dot product operation. Figure 31 shows an image example and its filtered image using the ideal low pass filters. 47 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain (a) (b) Figure 31 An ideal low pass filtering with cut-off frequency set as 10 (a), and the corresponding filtered image (b) from Figure 30 (a). 3.8.2 Butterworth Lowpass Filter The ideal low pass filter has a sharp discontinuity as T0. This will introduce some ring effects on the filtered image as shown in Figure 31 (b). In contrast, the Butterworth lowpass filter is much smoother at T0 and defined as follows: ଵ ‫ܯ‬ሺ‫ݑ‬Ǥ ‫ݒ‬ሻ ൌ ೅ሺೠǡೡሻ మ೙ ଵାቂ ቃ (3.8.3) ೅బ where T(u, v) is the radius from the point (u, v) to the origin in the frequency domain. Brain power By 2020, wind could provide one-tenth of our planet’s electricity needs. Already today, SKF’s innovative know- how is crucial to running a large proportion of the world’s wind turbines. Up to 25 % of the generating costs relate to mainte- nance. These can be reduced dramatically thanks to our systems for on-line condition monitoring and automatic lubrication. We help make it more economical to create cleaner, cheaper energy out of thin air. By sharing our experience, expertise, and creativity, industries can boost performance beyond expectations. Therefore we need the best employees who can meet this challenge! The Power of Knowledge Engineering Plug into The Power of Knowledge Engineering. Visit us at www.skf.com/knowledge 48 Click on the ad to read more Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain Figure 32 shows an example of Butterworth low pass filter with T0 = 10, and the filtered image from Figure 29 (a). Comparing the filtered image with the one in Figure 30, we notice that the Butterworth low pass filter produces less ringing effects than an ideal low pass filter using the same cut-off frequency. (a) (b) Figure 32 Butterworth low pass with cut-off frequency set as 10 (a), and the corresponding filtered image (b) from Figure 31 (a). 3.8.3 Gaussian Lowpass Filters In 2D image processing, an exemplar filter is Gaussian filtering. It is perhaps the most commonly used low pass filter in the literature. Mathematically in the frequency domain, it is defined as follows: ‫ܩ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ‫݁ܣ‬ሺെ݀ሺ‫ݑ‬ǡ ‫ݒ‬ሻȀʹߪ ଶ ሻ (3.8.4) ଵ ሺ‫ݑ‬ଶ ൅distance is an మaffine where ݀ ൌ ‫ ݒ‬ଶ ሻ function from the center point to the current point (u, v), usually denoted ଶఙ ଵ by ݀ ൌ మ ሺ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ሻ with σ denoting the standard deviation. Figure 33 shows the plot of the 2D ଶఙ Gaussian low pass filter and the filtered panda image respectively. (a) (b) Figure 33 Gaussian low pass filter (a) and the smoothed panda image (b), with set as 10 and A is set to 1. 49 Download free eBooks at bookboon.com Digital Image Processing Part I Filtering in the Frequency Domain 3.9 Image Sharpening Using Frequency Domain Filters 3.9.1 Ideal Highpass Filters An ideal highpass filter is to switch off some low frequency signals and to allow the high frequency signal to pass based on a threshold. It implies the difference between 1 and the ideal low pass filtering. Mathematically, it is defined as follows: ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൒ ܶͲ ‫ܯ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ൜ Ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൏ ܶͲ (3.9.1) In contrast to the ideal low pass filter, it blocks signals falling inside the circle by multiplying 0 and pass the signals settling outside the circle by multiplying 1. By doing this, we get the following filtered results in the frequency domain: ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൒ ܶ଴ ‫ܨ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻǤ‫ܯ כ‬ሺ‫ݑ‬ǡ ‫ݒ‬ሻ ൌ ൜ Ͳǡ ‫ݑ‬ଶ ൅ ‫ ݒ‬ଶ ൏ ܶ଴ (3.9.2) Figure 34 shows an example of using the ideal highpass filters applied to a

digital-image-processing-part-one.pdf

Document Details

Related

Full Transcript

Upgrade to continue