Image Expansion using Segmentation-based method by Abdul Karim M U R A D A G H A B.Sc. AL-ISRA University, JORDAN, 1996 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF T H E REQUIREMENTS FOR T H E D E G R E E OF MASTER OF APPLIED SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA November 2000 © Abdul karim M U R A D A G H A , 2000 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada Date Ajpv § DE-6 (2/88) Abstract Image enlargement is a vital process for printing images on large format printers. Image expansion introduces many new pixels to the original image. Proper values for these new pixels should be found otherwise distortion and significant degradation in the quality of the image w i l l result. Several methods have been employed to minimize such distortion. The most popular of these methods are the pixel replication and the linear interpolation methods. This is because these methods are not computationally demanding. In this work, we develop a new image expansion method that preserves the quality of the edges in the expanded image, where other methods fail. First, the edges in the original image are extracted. For binary images we use Laplacian operator and for gray-level images we use Canny edge detector. We propose a new algorithm, which replicates the edge shape so that the edges in the expanded image do not appear zigzagged. Our algorithm expands the edges while it preserves the edge information such as the shape and the continuity of the edge. The edge-shape-replication algorithm simply, classifies the edges into two classes: short post-CCC and long post-CCC edges, each is expanded differently. Most of the original pixels keep their values after the expansion. However, the remaining pixels' values are calculated using one of three proposed techniques based on the location of the pixel whose value is to be calculated. The three locations of these pixels are pixels that lie on an edge, pixels that are adjacent to edges, and the remaining pixels areas. To compare performance of our proposed method with others, we reduced the test images to their quarter size then expanded them to their original sizes. The sum of absolute errors (SAD's ) between the original image and the expanded images are calculated. Our proposed method is shown to outperform the replication, linear and cubic interpolation methods. - iii -Contents CONTENTS IV LIST OF FIGURES VIII LIST OF TABLES XVI ACKNOWLEDGEMENTS XVII 1 INTRODUCTION 1 1.0 M O T I V A T I O N S 1 1.1 D I G I T A L I M A G E E X P A N S I O N : B A C K G R O U N D 1 /. /. / Interpolation Methods 2 1.1.2 Adaptive Methods 3 1.1.3 Statistical Methods 4 1.1.4 Other Methods 4 2 IMAGE EXPANSION METHODS 6 2.0 INTRODUCTION 6 2.1 R E P L I C A T I O N M E T H O D 6 2.1.1 One-Dimension Replication 7 2.1.2 Two-Dimension Replication 8 2.1.3 Algorithms 8 2.2 L I N E A R INTERPOLATION M E T H O D 9 2.2.1 Mathematical Representation 9 2.2.2 One-Dimension Interpolation 14 - iv -2.2.3 Two-Dimension Interpolation 16 2.2.4 The Algorithm 16 2.3 Q U A D R A T I C INTERPOLATION M E T H O D 17 2.3.1 Mathematical Representation 17 2.3.2 One-dimension Interpolation 20 2.3.3 Two-Dimension Interpolation 21 2.3.4 Algorithm 21 2.4 C U B I C INTERPOLATION • 2 2 2.4.1 Mathematical Representation 22 2.4.2 One-dimension Interpolation 25 2.4.3 Two-Dimension Interpolation 26 2.4.4 Algorithm 27 2.5 B E Z I E R INTERPOLATION M E T H O D 28 2.5.1 Mathematical Representation 28 2.5.2 One-dimension Interpolation 31 2.5.3 Two-Dimension Interpolation 32 2.5.4 Algorithm 32 2.6 S P L I N E INTERPOLATION M E T H O D 33 2.6.1 Mathematical Representation 34 2.6.2 One-dimension Interpolation. 36 2.6.3 Two-Dimension Interpolation 37 2.6.4 Algorithm 37 2.7 B - S P L I N E INTERPOLATION 3 8 2.7.1 Mathematical Representation 39 2.7.2 One-dimension Interpolation 42 2.7.3 Two-Dimension Interpolation 43 2.7.4 Algorithm 43 F R E Q U E N C Y INTERPOLATION 44 - v -2.8 I D E A L F I L T E R INTERPOLATION 44 2.8.1 One-dimension Interpolation 44 2.8.2 Two-Dimension Interpolation 46 2.8.3 Algorithm 46 2.9 B U T T E R W O R T H F I L T E R INTERPOLATION 4 7 2.9.1 One-dimension Interpolation 47 2.9.2 Two-Dimension Interpolation 48 2.9.3 Algorithm 49 3 EXPERIMENTAL SIMULATION 50 3.0 INTRODUCTION '. 5 0 3.1 T H E T R O P I C I M A G E E X A M P L E S 51 3.2 T H E S A A D I M A G E E X A M P L E S 58 3.3 A N A L Y S I S OF T H E E X P A N S I O N M E T H O D S 65 3.3.1 Replication Method 65 3.3.2 Linear Interpolation Method 65 3.3.3 Quadratic Interpolation Method 66 3.3.4 Cubic Interpolation Method 66 3.3.5 Bezier Interpolation Method 67 3.3.6 Spline Interpolation Method 67 3.3.7 B-Spline Interpolation Method 67 3.3.8 Ideal Filter Interpolation Method 68 3.3.9 Butterworth Filter Interpolation Method 68 4 INFORMATION-PRESERVING IMAGE EXPANSION METHOD 69 4.0 INTRODUCTION 69 4.1 E D G E D E T E C T I O N , E D G E E N C O D I N G 7 0 4.2 E D G E EXPANSION PROCESS 73 4.3 T H E P R O P O S E D M E T H O D 7 6 - vi -4.4 S L O P E L I N E E D G E S C A S E S 84 4.5 E X A M P L E S 91 4.6 B I N A R Y I M A G E S E X P A N S I O N 92 4.7 G R A Y - L E V E L I M A G E E X P A N S I O N 95 Expansion process 95 4.8 R E S U L T S 102 5 CONCLUSIONS AND FUTURE SUGGESTIONS 104 5.0 O V E R V I E W 104 5.1 C O N C L U S I O N S 105 . 5.2 SUGGESTIONS FOR F U T U R E W O R K 106 BIBLIOGRAPHY 107 - vii -List of Figures Figure 2.1 The original one dimension data 7 Figure 2.2 The result of pixel replication method (4 times) 8 Figure 2.3 The linearly contributed values from the two neighbor points 10 Figure 2.4 The original value, and its mapped result, in the 4 times expansion case 11 Figure 2.5 Bilinear Interpolation process 11 Figure 2.6 The model (spread unction) of Bilinear Interpolation 14 Figure 2.7 The original one dimension data 14 Figure 2.8 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values, (c) the expansion result to the right, (d) the expansion result to the left 15 Figure 2.9 The original value, and its mapped result, in 4-time expansion case 18 Figure 2.10 The model (spread function) of Biquadratic Interpolation 19 Figure 2.11 The original one dimension data 20 Figure 2.12 (a) The mapped data onto the expanded domain, (b) The expansion result to the right direction 20 - viii -Figure 2.13 The original value, and its mapped result, in 4-time expansion case 24 Figure 2.14 The model (spread function) of Bicubic Interpolation 25 Figure 2.15 The original one dimension data 25 Figure 2.16 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values 26 Figure 2.17 The original value, and its mapped result, in 4-time expansion case 29 Figure 2.18 The model (spread function) of Bezier Interpolation 30 Figure 2.19 The original one dimension data 31 Figure 2.20 (a) The mapped data onto the expanded domain, (b) the expansion result to the right direction using Bezier interpolation.... 31 Figure 2.21 The original one dimension data 36 Figure 2.22 The result of 4-time expansion using spline interpolation 37 Figure 2.23 The original value, and its mapped result, in 4-time expansion case 40 Figure 2.24 The model (spread function) of B-spline Interpolation 41 Figure 2.25 The original one dimension data 42 Figure 2.26 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values 42 Figure 2.27 The original one dimension data 45 Figure 2.28 The expanded one dimension data using replication method 45 - ix -Figure 2.29 The F F T of the expanded signal, with the Ideal L P F , and filtered F F T 45 Figure 2.30 The result of IFFT of the filtered signal by using ideal L P F 46 Figure 2.31 The original one dimension data 47 Figure 2.32 The expanded one dimension data using replication method 47 Figure 2.33 The F F T of the expanded signal, the Butterworth L P F 48 Figure 2.34 The result of IFFT of the signal filtered by the Butterworth L P F 48 Figure 3.1 The "Tropic" image and its expanded results using ten different methods including the proposed method 52 Figure 3.2 The original "Tropic" image 53 Figure 3.3 The Expanded image by the replication method, expansion factor is equal 3 54 Figure 3.4 The Expanded image by the Linear Interpolation method, expansion factor is equal 3 55 Figure 3.5 The Expanded image by the Cubic Interpolation method, expansion factor is equal 3 56 Figure 3.6 The Expanded image by the Proposed method, expansion factor is equal 3 57 Figure 3.7 The "Saad" image and its expanded results using ten different methods including the proposed method 59 Figure 3.8 The original "Saad" image 60 Figure 3.9 The Expanded image by the replication method, expansion factor is equal 3 61 - x -Figure 3.10 The Expanded image by the Linear Interpolation method, expansion factor is equal 3 62 Figure 3.11 The Expanded image by the Cubic Interpolation method, expansion factor is equal 3 63 Figure 3.12 The Expanded image by the Proposed method, expansion factor is equal 3 64 Figure 4.1 The Laplacian operator 70 Figure 4.2 Example on an edge detected using the Laplacian edge detector 71 Figure 4.3 The numbering scheme used with 8-connectivety chain coding 72 Figure 4.4 Examples of edges and their chain codes 73 Figure 4.5 Example of 8 pixels horizontal line edge and its expanded edge 73 Figure 4.6 Examples of slope line edges 74 Figure 4.7 (a) A slope line edge, (b) Its expanded result by repeating the chain code 3 times, (expansion factor = 3) 75 Figure 4.8 (a) A slope-line edge, (b) Its expanded results using edge-shape-replication and the proposed methods, (expansion factor = 3) 75 Figure 4.9 A n Example of a slope line edge, (a) Actual edge in the edge image, (b) Its chain code representation 76 Figure 4.10 Example of the C C C detector, (a) The chain code, (b) The detection processes, and (c) The C C C detector result where only two C C C s are detected 77 - xi -Figure 4.11. Example of a segment of a slope line edge, its pre-part, the C C C , and its post-part, (a) The segment chain code, and (b) The edge in the edge image 77 Figure 4.12 A long slope line edge and its chain code 78 Figure 4.13 Example of the edge that is analyzed in Table 4.1 79 Figure 4.14 The two estimations of the real edge, (a) Position 1 (above), and (b) Position 2 (under) 80 Figure 4.15 The expansion process of the first estimated position which is above the slope line edge 81 Figure 4.16 The expansion process of the second estimated position which is under the slope line edge 83 Figure 4.17 Short post-CCC slope line edge (case 1), (a) The slope line edge and its chain code, (b) the segment, its pre- and post-CCCs, and the C C C 85 Figure 4.18 Short post-CCC slope line edge (case 1), (a) The slope line edge, (b) The sample of an edge divided into pieces, the pieces expanded by (c) The replication method, (d) The proposed method, and (e) The expanded edge by using the proposed method 86 Figure 4.19 Short post-CCC slope line edge (case 1) with few segment, (a) The slope line edge, (b) The expanded edge by using the proposed method 87 - xii -Figure 4.20 Long post-CCC slope line edge (case 2), (a) The slope line edge and its chain code, (b) the segment, its pre- and post-CCCs, and the C C C 88 Figure 4.21 Long post-part slope line edge (case 2), (a) The slope line edge, (b) The sample of an edge divided into pieces, the pieces expanded by (c) The replication method, (d) Expanding the segment as a case 1 segment, (e) The proposed method, and (f) The expanded edge by using the proposed method 89 Figure 4.22 Slope line edge (case 2), (a) The slope line edge and its segment, (b) the edge estimated position, and (c) The 3 times expanded result 90 Figure 4.23 The "Maple L e a f image (a) The original edge image, (b) The expanded edge image using the proposed method, the expansion factor is 3 91 Figure 4.24 The "Texas M a p " image (a) The original edge image, and the expanded images using the proposed method, the expansion factors are (b) 3, and (c) 5 ; 92 Figure 4.25 The " A B C " Image, (a) The original binary image, and its reduced then expanded by 2 images using four different methods (b) Replication, (c) Linear Interpolation, (d) Cubic Interpolation, and (e) The proposed method 93 Figure 4.26 The "Rabab" Image, (a) The original binary image, and its reduced then expanded by 2 images using four different methods - xiii -(b) Replication, (c) Linear Interpolation, (d) Cubic Interpolation, and (e) The proposed method 94 Figure 4.27 Example on the original pixels mapping onto the expanded image (a) The original pixels, (b) The expanded image 95 Figure 4.28 The three different pixel position with respect to an edge. Gray pixels lie in a homogenous region, Dark pixels lie on an edge, White pixels lie near edge pixels 96 Figure 4.29 (a) The original pixels, (b) The three different positions of the inside region pixels 97 Figure 4.30 The window that calculates the value of the pixels to the right of an original pixel 97 Figure 4.31 The window that calculates the value of the pixels to the bottom of an original pixel 98 Figure 4.32 The window that calculates the value of the pixels to the right-bottom of an original pixel 98 Figure 4.33 Example of filling the edge pixels by repeating the original edge pixels' values, (a) The original edge pixels, (b) The chain code represented by arrows, (c) The expanded edge, (d) The values o f the expanded edge pixels repeated from the original 'pixels, and (e) The edge pixels values 99 Figure 4.34 Example of filling the edge pixels by the proposed method, (a) The original edge pixels, (b) The original edge values that were - xiv -kept or altered for the expanded edge, and (c) The calculated values of the expanded edge 100 Figure 4.35 Examples of filling near edge pixels. Gray pixels lie in a homogenous region, Dark pixels lie on edge, White pixels lie near edge pixels. The closed shapes are the pixels to be averaged so as to calculate the pixel marked as question mark 1021 - xv -List of Tables Table 1 Sample of the segments' properties table 78 Table 2 The Sum of the Absolute Error of four images enlarged using three methods and the proposed method 102 - xvi -Acknowledgements M y first and foremost thanks go to my supervisor, Dr. Rabab Ward, for her supervision, friendly patience, academic guidance and generous support. This work would not be possible without her close attention. M y special thanks also go to Dr . Saif Zahir for the technical support throughout this work. I am grateful to Dr. Musleh Harbah and Dr. AbdulNasir Hussien for the guidance and the advice throughout my earlier years that make me what I am today. I am also thankful to my colleagues at the Digital Image Processing Lab specially our research engineer Dr. Alen Docef, and my friend Dr. Ismaeil Ismaeil. Finally, I can not thank my parents enough, especially my mother, for the moral support and spiritual guidance, and my brothers and sisters for their patience and understanding. Abdul Kar im M U R A D A G H A The University of British Columbia October 2000 - xvii -To my beloved Mother Aicha - xviii -1 Introduction 1.0 Motivations Expansion of color images is a vital process for printing images on large format printers especially for images with low resolution mode. Image expansion introduces many new pixels to the original image that w i l l cause distortion and significant degradation in the quality of the image. Several methods have been employed to minimize such distortion: (1) Pixel replication; (2) Pixels averaging; (3) Edge detecting method and others. In this research we introduce a new segmentation-based technique that segment the image into regions. The boundaries of these regions i.e. the image edges are expanded so the resultant image has close resemblance with the original one. Such a method tends to retain the characteristics and features of the original image. 1.1 Digital Image Expansion: Background Image expansion is a very important part of the digital image processing field. It is used in many applications such as, multimedia, image communication, digital photography, and medical imaging. Digital images are expanded by fitting an image with a continuous model and resampling this model on a new expanded sampling grid. Most of image interpolation methods can be grouped under one of the four categories. These are 1) conventional interpolation methods, 2) adaptive methods, 3) statistical methods, and 4) new recent methods. 1.1.1 Interpolation Methods Interpolation methods form the conventional methods in which an interpolation function is applied indiscriminately on the whole image. The first serious effort in image interpolation field is the sampling and interpolation discussion presented by Schafer et al. in 1973 [1]. The fastest, simplest, and most commonly used methods are: 1) The replication method, which also is called nearest neighbor or zero-degree interpolation. This method is equivalent to a sine function in the frequency domain and is a poor low pass filter [2, 3]. 2) The bilinear (first-degree or linear) interpolation method; this method attenuates frequencies near the cutoff frequency, resulting in image blurring and smoothing [4, 5]. These two methods are the simplest and fastest methods, but they suffer from either block effects or blurring (over-smoothing effects). 3) Interpolation method with higher degrees such as quadratic (second-degree) or cubic (third-degree) interpolations these methods can produce better results than the zero or first degree interpolation methods. 4) Sine interpolation, which has considerable energy over extended distance, and requires pruning [6, 7], or truncating [8, 9]. 5) Radial basis functions, which avoid blockiness effects [10]. 6) Cubic spline interpolation which tends to cause overshooting at sharp edges, producing ringing effects [11, 12]. 7) High resolution cubic splines (cubic convolution) [2, 3, 13, 14, 15, 16, 17], 8) Spline-like methods; these methods simulate the spline function and produce similar results to those of the spline but use much simpler functions [15, 18, 19]. 9) Generalized spline filters based on partial differential equation (PDE) for image models [20, 21]. 10) ILR filtering [22] and Fourier transform where frequency interpolation is used [23, 24, 25, 26]. There are other interpolation functions such as Mitchmod function [27], and Mitchel l and Smith [28]. Some of these conventional interpolation methods produce better results than others. These methods are not optimal, in the sense that they are not designed to minimize degradations and artifacts, and lack the consideration of the local characteristics of the image. 1.1.2 Adaptive Methods Typically, an image with lower spatial resolution has relatively lower bandwidth in the Fourier domain. The frequency response of an interpolation function normally approximates an ideal low pass filter with the cutoff frequency equal to the Nyquist frequency of the sampled image. A n interpolated image frequency response still lies within the original image bandwidth. Even an ideal interpolation method only preserves the original frequency components within the input image bandwidth. To expand a low-resolution image to high-resolution image with sharp edges, such an expansion algorithm should be able to generate high frequency components in the spectrum that correlate to the original frequency components. For that reason, a number of adaptive expansion methods were developed. A n adaptive technique was introduced in the late 1980's by Wang et al. [29]. Other adaptive methods include an: adaptive interpolation method based on the local structure of the image and which takes advantage of the intensity variations that are indistinguishable by the human eye [30, 31]. Lee et al., introduced a fast adaptive B-spline interpolation method. This method produces block or mosaic effects [32]. Nonlinear interpolation methods based on a source model and incorporating a local edge fitting were also developed [33, 34, 35, 36, 37]. Directional interpolation methods based on the local analysis of the spatial image structure were discussed in [17, 38, 39]. Enhancing edge during scaling [40, 41, 42, 43] and edge-restricted spatial interpolation based on cubic spline-under-tension kernel were also introduced [44]. 1.1.3 Statistical Methods Statistical methods usually involve and exploit some texture parameters. The methods in this category require that such parameters be estimated for the prescribed underlying image model. Parameters estimation is, however, a computationally demanding procedure. This limits the usefulness of these methods for any real time applications [35]. This category includes methods that are based on image models such as, Markov random fields [45, 46], Gibbs random field [47, 48, 1, 4], and others [49]. 1.1.4 Other Methods The fourth category of image expansion methods forms recent methods. This category is based on methods such as: D C T , neural networks; and wavelets. Image interpolation methods that use D C T coefficients of 8x8 blocks of the original image are introduced in [50, 51, 52, 53]. The use of Radial Basis Functions Network ( R B F N ) for image interpolation is also introduced [54, 55]. Random Neural Network (RNN) is also used to interpolate images [56]. Other work uses Wavelet techniques to interpolate images [57, 58, 59]. - 5 -2 Image Expansion Methods 2.0 Introduction Many methods are developed for image expansion. Some are very popular and commonly used, some are theoretical, and others lie in between. The Replication and the Linear interpolation methods are very popular. The spline interpolation method is more theoretical than practical. In this chapter different methods for image expansion are discussed. 2.1 Replication Metho d The pixel replication method simply maps each pixel in the original image onto an N x N block of pixels, where N is the expansion factor, and each of the pixels of the N x N block has the value o f the original pixel. For example, for an expansion factor 3, each pixels in the original image is mapped onto a 3 x 3 block of pixels in the expanded image. Such a process is usually followed by some sort of a local correction heuristic that attempts to change the appropriate pixel gray levels depending on their neighborhood - 6 -in the original image [42]. This method is also known as zero-order interpolation. This method is very simple and cheap to implement, however, it introduces a tiling or "jaggies" effect which is known as a blockiness effect, specially at high expansion factors. For N = 4, the normalized mapping process is as follows 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2.1.1 One-Dimension Replication Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.1, and assume it is to be expanded 4 times. 1 Figure 2.1 The original one dimension data The expanded result is [ 4 4 4 4 1 1 1 1 3 3 3 3 2 2 2 2 ] , the original values are bolded, Figure 2.2 shows this process. www 1 Figure 2.2 The result of pixel replication method (4 times) 2.1.2 Two-Dimension Replication The original 2-dimentional set of values shown below is expanded 4 times. Each pixel is replicated 4 times in both the x and the y-axis directions, as follows 0 20 40 20 60 80 40 80 60 => 0 0 0 0 0 0 0 20 20 20 20 20 20 20 20 40 40 40 40 40 40 40 40 0 0 20 20 20 20 40 40 40 40 0 0 20 20 20 20 40 40 40 40 0 0 20 20 20 20 40 40 40 40 0 0 20 20 20 20 40 40 40 40 20 20 60 60 60 60 80 80 80 80 20 20 60 60 60 60 80 80 80 80 20 20. 60 60 60 60 80 80 80 80 20 20 60 60 60 60 80 80 80 80 40 40 80 80 80 80 60 60 60 60 40 40 80 80 80 80 60 60 60 60 40 40 80 80 80 80 60 60 60 60 40 40 80 80 80 80 60 60 60 60 2.1.3 Algorithms The pixel replication algorithm is separable. That means it can be applied as a row one-dimension pixel replication followed by a column one-dimension pixel replication. - 8 -2.2 Linear Interpolation Method This method finds an estimate for an unknown point by linearly interpolating the values of its neighboring points. For the one-dimensional case linear interpolation finds the estimate of the unknown point from its 2 nearest points whose values are known. This involves fitting a straight line through the two points. This method is also called first-order interpolation or pixel averaging. Linear interpolation is the easiest interpolation method. In the two-dimension case, the linear interpolation method is called bilinear interpolation and involves finding the unknown value of a point from four known points. The bilinear interpolation method is relatively simple, fast and computationally inexpensive. On the other hand, it introduces blurring and contouring effects around edges in the expanded image. 2.2.1 Mathematical Representation In one dimension case, given two data points (pairs of numbers) (x 0 , fo), (xi , f]), linear interpolation finds a polynomial pi(x) such that pi(xo) = fo, and pi(xi) = f i . N o w pi(x) can be written as [60] pi(x) = fo + ( x - x 0 ) f [ x o , Xi] (1) / - / where f[xo, xi] is the first divided difference and is given by — - . Assuming the distance between x i and xo = 1, i.e. x i - xo = 1 then f[xo, xi] = fi - fo. The subscript 1 of pi(x) indicates the degree of the polynomial, which is 1 for the linear interpolation polynomial. Equation (1) can now be written as pi(x) = f0 + (x - x 0 ) (fi - f 0). (2) From that we can see that pi(xo) = fo, pi(xi) = f i . Let r = (x - XQ) then pi(x) = p!(x 0 + r) = fo + r ( f , - f 0 ) = f0 + r fi - r f0 (1 - r) f0 + r f, (3) i.e. the interpolated value pi(x) is a weighted sum of fo and fi where fo and f] contribute (1 - r)fo and r f i , respectively, towards the value at a point x as shown in Figure 2.3. Figure 2.3 The linearly contributed values from the two neighbor points In other word, f0 is mapped onto { (1 - r) f0 } to its right, and fi is mapped onto { r fi } to its left. A n d the expanded image w i l l be the result of adding the overlapped mapped values. This expansion could be easily shown to be equivalent to convolving the input image with a system whose impulse response function for an expansion factor N = 4 is as shown in Figure 2.4. # • Original points w . Contributed points -10-p 0 0 # Original point ® Mapped points Figure 2.4 The original value, and its mapped result, in the 4 times expansion case. In the two-dimensional case, four data points are given (xo, yo, fo), (x i , y i , fi), (X2, y2, h), and (X3, y3, fy). The bilinear interpolation is three linear (one-dimensional) interpolations. • • Original points • Contributed points (x3,yj (a) \y) L L * M / © (xa yj / 1 , i (x, / (x,y) yJ 4/ (x„y) (x2,y) (x^yj (b) (c) Figure 2.5 Bilinear Interpolation process. -11 -Similar to the assumptions in the one-dimensional case, let r = (x - xo) and s = (y - yo) as shown in Figure 2.5. The first linear interpolation is a horizontal interpolation between fo and f\ and finds a polynomial pn(x), such that pn(xo) = fo, and pn(xi) = f\. Using (3) where r = (x - xo), pi i(x) can be written as The second linear interpolation is a horizontal interpolation between and £3 and finds a polynomial Pi2(x), such that pi2(x2) = £2, and pi2(x3) = £3. r = (x - X2) then pi2(x) can be written as N o w consider a point (xo + r, yo + s), the third linear interpolation is a vertical interpolation and finds a polynomial pi(x, y) that passes through pn(xo + r), and pnfa + r). N o w pi(x, y) can be written as Pn(xo + r) = ( l - r ) f i + r f i (4) p i 2 ( x 2 + r) = ( l - r ) f 2 + r f 3 (5) p i (x 0 + r, y 0 + s) = (1 - s) p M ( x 0 + r) + (s) p i 2 ( x 2 + r) = (1 - s)(l - r) f0 + (1 - s)(r) f, + (s)(l - r) f2 + (s)(r) f3 (6) i.e. the interpolated value pi(x, y) is a weighted sum of fo, f i , f*2, and £3. -12-In other word, the pixel (xo, yo) contributes { (1 - s)(l - r) fo } to its lower-right pixels, the pixel (xi , yi) contributes { (1 - s)(r) fi } to its lower-left pixels, the pixel (x 2 , y 2 ) contributes { (s)(l - r) f2 } to its upper-right pixels, and the pixel (x 3 , y 3 ) contributes { (s)(r) f3 } to its upper-left pixels. A n d the expanded image w i l l be the result of adding these four contributions. This can be shown to be equivalent to convolving the original image with a system whose impulse response function e.g. for the case of expansion factor N = 4 is as shown in Figure 2.6. 16 0 0 0 0 0 0 0 0 0 0 1 2 3 4 3 2 1 0 0 2 4 6 8 6 4 2 0 0 3 6 9 12 9 6 3 0 0 4 8 12- 16 12 8 4 0 0 3 6 9 12 9 6 3 0 0 2 4 6 8 6 4 2 0 0 1 2 3 4 3 2 1 0 0 0 0 0 0 0 0 0 0 -13-Figure 2.6 The model (spread unction) of Bilinear Interpolation 2.2.2 One-Dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.7, and assume it is to be expanded 4 times. I Figure 2.7 The original one dimension data Zero padding is first used to complete the process. This is followed by mapping these data onto the expanded domain, then adding the overlapped values. The result of expansion to the right direction is [ 4 3.25 2.5 1.75 1 1.5 2 2.5 3 2.75 2.5 2.25 2 1.5 1 0.5 -14-]. A n d the result o f expansion to the left direction is [ 1 2 3 4 3.25 2.5 1.75 1 1.5 2 2.5 3 2.75 2.5 2.25 2 ], the original data is bolded for convenience, Figure 2.8 shows this process. 1-V I (a) (b) O 0 1 V (c) o 1 V (d) Figure 2.8 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values, (c) the expansion result to the right, (d) the expansion result to the left. -15-2.2.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times, so that each pixel is mapped onto a 7x7 block then the overlapped values are added, then rounded to the nearest integer to produce the final expanded result. 0 20 40 20 60 80 =>• 40 80 60 0 5 10 15 20 25 30 35 5 11 18 24 30 35 40 45 10 18 25 33 40 45 50 55 15 24 33 41 50 55 60 65 20 30 40 50 [6QJ 65 70 75 25 35 45 55 65 68 70 73 30 40 50 60 70 70 70 70 35 45 55 65 75 73 70 68 40 50 60 70 80 75 70 65 30 38 45 53 60 56 53 49 20 25 30 35 40 38 35 33 10 13 15 18 20 19 18 16 20 10 25 13 30 15 35 18 40 20 38 19 35 18 33 16 30 15 .23 11 15 8 8 4 2.2.4 The Algorithm Bilinear interpolation algorithm is a separable one. That means it can be applied as a row one-dimension linear interpolation on every row followed by a column one-dimensional linear interpolation on every column. -16-2.3 Quadratic Interpolation Method Quadratic interpolation uses a second-degree polynomial whose curve passes through three points. Using three points fo, f i , and f2 to find interpolated values for points between fo and fj is called forward interpolation, and to interpolate values for points between fi and f2 is called backward interpolation [60]. In this section, only forward quadratic interpolation is considered. For the two-dimensional case it is called biquadratic interpolation, and it involves nine pixels. That means better quality than linear interpolation. But it still introduces blurry results. 2.3.1 Mathematical Representation In the one-dimension case, given three data points (three pairs of numbers) (x 0 , fo), (x ] 5 fi), (X2, f 2), quadratic interpolation finds a polynomial p 2(x) such that p2(xo) = fo, P2(xi) = f i , and p2(x2) = f2. The quadratic polynomial is [60, 61] p 2(x) = f0 + (x - x 0 ) f[x 0 , Xi] + (x - x 0)(x - Xi) f[x 0 , X i , x 2 ] (7) where the subscript 2 of p2(x) indicates the degree of the polynomial. f[xo, xi] is the first f - f divided difference and is given by — — — = fi - f0, where x i - x 0 = 1, and fTx0, x i , x 2 ] is X j — xQ the second divided difference and given by = 0.5 (f2 - 2 fi + fo). x2 — xQ From the above we can deduce that P2(x0) = fo, P2(xi) = f], p 2 (x 2 ) = f2- Let r = (x - x 0 ) , -17-then p 2(r) = fo + r (f, - f0)+ 0.5 r (r - 1) (f2 - 2 f, + f0) = 0.5 ( ( r - 1) ( r - 2) f0 + 2 r (2 - r ) f, + r ( r - 1) f2 ) (8) To find the interpolated value for an unknown point lying between fo and fj, we notice from (8) that f0 contributes { 0.5 (r - l ) ( r - 2) f0 }, fi contributes { (r)(2 - r) fi }, and f2 contributes { 0.5 (r)(r - 1) f2 }, to this point. Thus for an expansion factor = 4 it can be shown that each original point w i l l be mapped onto eleven values in the expanded result as shown in Figure 2.9. After mapping all the original points, the expanded data w i l l be the result of adding the overlapped mapped values. # Original point 0 Mapped points Figure 2.9 The original value, and its mapped result, in 4-time expansion case. The two-dimensional mapping function can be found by simply convolving a horizontal one-dimensional mapping function with a vertical one-dimensional mapping function. A s an example consider an expansion factor 4. A pixel in the original image is mapped onto an 11 x 11 block in the expanded image according to Figure 2.10. -18-0 0 0 0 0 0 0 0 0 0 0 0 0 0 .6 .8 .6 0 - 3 - 5 - 6 - 6 - 4 - 2 -1 0 0 .8 1 .8 0 - 4 - 6 - 8 - 8 - 5 - 3 -1 0 0 .6 .8 .7 0 - 3 - 5 - 6 - 6 - 4 - 2 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 3 - 4 - 3 0 12 21 26 28 18 11 4 0 0 - 5 - 6 - 5 0 21 36 45 48 32 18 8 0 0 - 6 - 8 - 6 0 26 45 56 60 39 23 9 0 0 6 - 8 - 6 0 28 48 60 64 42 24 10 0 0 - 4 - 5 - 4 0 18 31 39 42 28 16 7 0 0 - 2 - 3 - 2 0 11 18 23 24 16 9 4 0 0 -1 -1 -1 0 4 8 9 10 7 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 2.10 The model (spread function) of Biquadratic Interpolation -19-2.3.2 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.11, and assume it is to be expanded 4 times. 1 Figure 2.11 The original one dimension data Mapping each datum onto the expanded domain, then adding the overlapped values, the expanded result to the right direction is [ 4 2.78 1.88 1.28 1 1.97 2.63 2.97 3 1.97 1.13 0.47 2 1.31 0.75 0.31 ], Figure 2.12 shows this process. \ (a) O I V (b) Figure 2.12 (a) The mapped data onto the expanded domain, (b) The expansion result to the right direction. 20 2.3.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times. In this case each pixel is mapped onto an 11x11 block then the overlapped values are added, then rounded to the nearest integer. The following is the expansion result to the right direction. 0 20 40 20 60 80 => 40 80 60 0 1 5 5 12 10 19 15 25 20 32 31 45 38 54 41 57 40 56 26 37 15 21 6 9 10 15 19 25 27 35 35 44 43 52 57 67 67 76 70 79 68 76 44 50 25 28 11 12 20 31 32 45 43 57 52 67 60 74 74 83 83 87 84 85 80 79 53 52 30 30 13 12 38 41 54 57 67 70 76 79 82 84 87 85 87 83 83 78 75 69 49 45 28 26 12 11 40 26 56 37 68 44 76 50 8 0 l 5 3 79 52 75 49 69 45 60 139 39 26 23 15 9 6 15 6 21 9 25 11 28 12 30 13 30 12 28 12 26 11 23 9 15 6 08 4 4 1 2.3.4 Algorithm Biquadratic interpolation algorithm is a separable one. That means it can be applied as a one-dimension quadratic interpolation on every row and then as a one-dimensional quadratic interpolation on every column. -21 -2.4 Cubic Interpolatio n Cubic interpolation is the process of interpolation using third order degree polynomials interpolation using the four points (pixels) x_i, xo, x i and x 2 , to interpolate values lying between the first and second points x.i and xo is called forward cubic interpolation. Interpolation of points lying between the third and fourth points using the 4 known points is called backward cubic interpolation. The most common interpolation is the central one and involves interpolation between the second xo and the third points xj [60, 61]. h i this section, only the central cubic interpolation is considered. For the two-dimensional case it is called bicubic interpolation, and it uses sixteen pixels. Interpolating values lying amongst the four points at the center of the sixteen known pixels is called central bicubic interpolation and is the process used here. Although this method produces sharper transition areas at edges, it still introduces blurry results and oscillations at the edges and is computationally expensive. This method produces better quality than the previous discussed interpolation methods. 2.4.1 Mathematical Representation In the one-dimension case, given four data points (x_i, f_i), (xo, fo), (x i , fi), and (x 2 , f 2), cubic interpolation finds a polynomial P3(x) such that P3(x_i) = f_i, P3(xo) = fo, P3(xi) = f i , and P3(x2) = f2. The cubic polynomial formula is p 3(x) = f0 + (x - x 0 ) f[x 0 , x i ] + ( x - x 0 ) ( x - x i ) f [ x o , x , , x 2 ] -22-+ (x - x 0)(x - x,)(x - x 2 ) f[x.i , X 0 , X , , x 2 ] (9) where the subscript 3 of P3(x) indicates the degree of the polynomial [60, 61]. f[xo, xi] is the first divided difference and is given by A z A = fi . f0.? w h e n x, - x 0 = 1. f[xo, x i , x 2 ] is the second divided difference and is given by f[Xl,x2]-f[x0,Xl] = 0 5 ( f 2 _ 2 f i + f o l a n d x2 XQ f[xo, x i , x 2 , x 3 ] is the third divided difference and is given by / [ * 0 , * p * 2 ] - / [ * - , , * ( , , * . ] _ 0 . 5 ( / 2 - 2 / , + / 0 ) - 0 . 5 ( / 1 - 2 / 0 + / _ 1 ) Let r = (x - xo), so p 3(r) = f0 + r (f, - f0)+ 0.5 r (r - 1) (f2 - 2 f, + f0) + r (r -1) (r - 2) (f2 - 3 f, - 3 f0 + £,) = \ [ ( - 3 r ( r - l ) 2 U + 3 ( r 2 (3 r - 5) + 2 ) f 0 - r (3 r 2 - 4 r - 1) f, + 3 r 2 ( r - 1) f2 ) ] 6 (10) For a point lying between x 0 and x i , f] contributes { - 0.5 (r)(r - l ) 2 f_i } towards its interpolated value, f0 contributes { 0.5 ((r)2(3 r - 5) + 2) f0 }, fi contributes { - 0.5 (r)(3r2 — 4r — 1) fi }, and f2 contributes {0.5 (r)2(r - 1) f2 }. For an example, consider the case when the expansion factor is 4. It can be shown that the value o f an original pixel w i l l be mapped onto fifteen values in the expanded result as shown in Figure 2.13. After mapping all the original points, the expanded data w i l l be the result of adding the overlapped mapped values. -23-Original point Mapped points Figure 2.13 The original value, and its mapped result, in 4-time expansion case. For the two-dimensional mapping function, it can be shown that this could be accomplished by simply convolving a horizontal one-dimensional mapping function with a vertical one-dimensional mapping function. A s an example consider an expansion factor 4. A pixel in the original image is mapped onto a 15 x 15 block in the expanded image as shown in Figure 2.14. 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .1 .1 0 - . 4 - . 8 - 1 - 2 - 1 - . 8 - . 4 0 .1 .1 0 0 0 .1 .3 .3 0 - 1 - 2 - 4 - 4 - 4 - 2 - 1 0 .3 .3 .1 0 0 .1 .3 .3 0 - 1 - 3 ' - 4 - 5 - 4 - 3 - 1 0 .3 .3 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - . 3 - 1 - 1 0 3 8 13 15 13 8 3 0 - 1 - 1 - . 3 0 0 - . 8 - 2 - 3 0 8 2 0 31 3 6 31 2 0 8 0 - 3 - 2 - . 8 0 0 - 1 - 4 - 4 0 13 31 48 56 48 31 13 . 0 - 4 - 4 - 1 0 0 - 2 - 4 - 5 0 15 3 6 5 6 64 5 6 3 6 15 0 - 5 - 4 - 2 0 0 - 1 -4* - 4 0 13 31 48 56 48 31 13 0 - 4 - 4 - 1 0 0 - . 8 - 2 - 3 0 8 2 0 31 3 6 31 2 0 8 0 - 3 - 2 - . 8 0 0 - . 3 - 1 - 1 0 3 8 13 15 13 8 3 0 - 1 - 1 - . 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .1 .3 .3 0 - 1 - 3 - 4 - 5 - 4 - 3 - 1 0 .3 .3 .1 0 0 .1 .3 .3 0 - 1 - 2 - 4 - 4 - 4 - 2 - 1 0 .3 .3 .1 0 0 0 .1 .1 0 - . 4 - . 8 - 1 - 2 - 1 - . 8 - . 4 0 .1 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -24-Figure 2.14 The model (spread function) of Bicubic Interpolation 2.4.2 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.15, and assume it is to be expanded 4 times. 1 Figure 2.15 The original one dimension data Mapping these data onto the expanded domain, then adding the overlapped values, the result of expansion to the right direction is [ 4 3.63 2.63 1.56 1 1.22 1.88 2.59 3 2.98 2.75 2.39 2 1.52 0.94 0.38 ], Figure 2.16 shows this process. -25-?1 I . . 1 r • I; • j • ,T v • • • T T T • • (a) O O 0 I V (b) Figure 2.16 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values 2.4.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times. In this case each pixel is mapped onto a 15x15 block then the overlapped values are added, then rounded to the nearest integer. The following is the result of expansion in the right direction. -26-0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 => 0 4 9 15 20 26 34 39 40 33 21 9 20 18 9 3 4 8 15 22 29 37 45 51 51 43 27 11 23 20 10 4 9 15 23 32 40 49 58 64 64 52 •33 14 31 27 12 5 15 22 32 42 51 60 70 76 74 61 39 16 37 32 14 6 20 29 40 51 60 69 78 83 80 65 41 17 40 36 16 6 26 37 49 60 69 76 82 84 80 65 41 17 36 31 14 5 34 45 58 70 78 82 84 83 76 61 38 15 28 25 12 4 39 51 64 76 83 84 83 78 69 54 34 14 22 20 9 3 40 51 64 74 80 80 76 69 60 46 29 12 20 18 9 3 33 43 52 61 65 65 61 54 46 36 22 9 32 20 10 4 21 27 33 39 41 41 38 34 29 22 14 6 52 36 14 6 9 11 14 16 17 17 15 14 12 9 6 2 71 59 20 8 20 23 31 37 40 36 28 22 20 32 52 71 80 69 24 10 18 20 27 32 36 31 25 19 18 20 36 59 69 29 13 6 9 10 12 14 16 14 12 9 9 10 14 20 24 13 7 3 3 4 5 6 6 5 4 3 3 4 6 8 10 6 3 1 2.4.4 Algorithm Bicubic interpolation process is a separable one. That means it can be applied as a one-dimensional cubic interpolation on every row and then as a one-dimensional cubic interpolation on every column. -27-2.5 Bezier Interpolation Method The most popular Bezier curve is the Bezier cubic curve, which is a cubic polynomial curve segment, named after Pierre Bezier who developed these curves for use in designing automobiles at Renault. These curves are obtained by using the end points tangent vectors and the values of two intermediate points. Bezier cubic interpolation involves 4 pixels in the one-dimensional case. The Bezier cubic curve passes through the two end points and finds an interpolated value for the other two-middle points. The cubic Bezier interpolation method simply fits a curve that starts at the first point, ends at the last one, and does not necessarily pass through the middle ones [28, 62]. This method is found to eliminate the blockiness effect at the edges, but it introduces unacceptable smoothness and blurring. 2.5.1 Mathematical Representation Using four given data (x 0 , fo), (xi , fi), (x 2 , f 2), and (X3, f3) the cubic Bezier interpolation finds a cubic polynomial p(x) given by [28, 62, 63, 64] L p(x)=Y,PkBk(x) ( i i ) 4=0 where L is the order of the polynomial, pk is the polynomial coefficients and the functions Bk(x) are known as Bernstein polynomials, and are given by Bi{x)={%-xrks <12) 28 k\(L-k)\ So the Bezier curve between these four data points is given by p{x) = Ypk* *(\-x)L'kxk (13) The expanded image at any point x w i l l be the result of adding the overlapped mapped values of the weight contributions of the 4 nearest original points. For the case of N = 4 i.e the 4 times expansion, the contributions of the original value w i l l spread (get mapped) onto fifteen values in the expanded result, which is the mapping function shown in Figure 2.17. # Original point # Mapped points I - S — i f — f - — . ^ Figure 2.17 The original value, and its mapped result, in 4-time expansion case. The two-dimensional mapping function can be found by simply convolving a horizontal one-dimensional mapping function with a vertical one-dimensional mapping function. A s an example consider an expansion factor 4. A pixel in the original image is mapped onto a 15 x 15 block in the expanded image as shown in Figure 2.18. -29-0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 1 1 1 1 0 0 0 1 1 2 2 2 3 3 4 3 3 2 2 2 1 1 0 0 1 2 3 3 3 5 5 6 5 5 4 3 3 2 1 0 0 1 2 3 3 4 5 6 6 6 5 4 3 3 2 1 0 0 1 2 4 4 6 7 8 9 8 7 6 4 4 2 1 0 0 2 3 5 5 7 9 10 11 10 9 7 5 5 3 2 0 0 2 3 5 6 8 10 12 12 12 10 8 6 5 3 2 0 0 2 4 6 6 9 11 12 13 12 11 9 6 6 4 2 0 0 2 3 5 6 8 10 12 12 12 10 8 6 5 3 2 0 0 2 3 5 5 7 9 10 11 10 9 7 5 5 3 2 0 0 1 2 4 4 6 7 8 9 8 7 6 4 4 2 1 0 0 1 2 3 3 4 5 6 6 6 5 4 3 3 2 1 0 0 1 2 3 3 4 5 5 6 5 5 4 3 3 2 1 0 0 1 1 2 2 2 3 3 4 3 3 2 2 2 1 1 0 0 0 1 1 1 1 2 2 2 2 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 2.18 The model (spread function) of Bezier Interpolation -30-2.5.2 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.19, and assume it is to be expanded 4 times. 1 Figure 2.19 The original one dimension data Mapping these data onto the expanded domain, then adding the overlapped values, the result of the expansion to the right direction is [ 2.25 2.5 2.8 2.56 2.17 2.28 2.35 2.27 2.2 2.12 2 1.9 1.72 1.6 1.5 1.3 ], Figure 2.20 shows this process. (b) Figure 2.20 (a) The mapped data onto the expanded domain, (b) the expansion result to the right direction using Bezier interpolation -31 -2.5.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times. In this case each pixel is mapped onto a 15x15 block then the overlapped values are added, then rounded to the nearest integer. The following is the result of the expansion to the right direction. 0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 7 11 14 18 19 22 24 26 25 25 23 20 16 15 11 8 11 17 21 26 27 30 33 34 32 33 29 26 20 18 14 10 16 21 26 31 32 37 39 40 38 32 34 29 23 21 16 11 18 26 31 37 38 43 45 46 42 38 38 33 25 23 17 12 19 27 32 38 39 44 46 46 42 42 38 32 25 23 17 12 22 31 37 43 44 50 51 52 47 47 43 37 28 26 20 14 24 33 39 45 46 51 53 53 48 48 43 37 29 27 21 15 26 34 40 46 46 52 53 52 47 48 43 38 29 27 21 16 25 32 38 42 42 47 48 47 42 43 39 34 27 25 19 14 25 33 38 42 42 47 48 48 43 44 40 36 29 27 21 16 23 29 34 38 38 43 43 43 39 40 38 34 28 26 21 16 20 26 29 33 32 37 37 38 34 36 34 34 26 25 20 15 16 20 23 25 25 28 29 29 27 29 28 26 23 21 18 14 15 18 21 23 23 26 27 27 25 27 26 25 21 20 17 13 11 14 16 17 17 20 21 21 19 21 21 20 18 17 14 10 8 10 11 12 12 14 15 16 14 16 16 15 14 13 10 9 2.5.4 Algorithm Bezier interpolation algorithm is a separable process. That means it can be applied as a one-dimensional Bezier interpolation on every row and then as a one-dimensional Bezier interpolation on every column. -32-2.6 Spline Interpolation Method The term spline goes back to the long flexible strips of metal used by draftsmen to lay out the surface of airplanes, cars, and ships. "Ducks", which are attached to the splines, were used to pull the spline in various directions. Splines are piecewise polynomials with pieces that are smoothly connected together. The connection points of the polynomials are called "knots". For a spline of degree n, each segment is a polynomial of degree n, which needs n + 1 coefficients to describe each piece [16, 60]. However, there is an additional smoothness constraint that imposes the continuity of the spline and its derivatives up to order (n - 1) at the knots [60]. Cubic splines are the most popular splines because they have minimum oscillation at the knots. Higher order splines produce more oscillations. The cubic spline interpolation involves 4 points and it uses three different third-degree polynomials. This is different from the cubic interpolation. The cubic interpolation fits a single third-degree polynomial through the four points it uses to interpolate. Cubic spline fits three different polynomials, each is a third-degree polynomial, one between the first and the second points, one between the second and the third points, and one between the third and the fourth points. This method does not have a fixed model (kernel). The cubic spline polynomials are computed by solving a set of equations that involves the equations of the polynomials and their derivatives. This method is stable because it is data dependent, so that no fixed model (kernel) can be used for all points as in the other previous methods [16, 60]. The cubic spline polynomial produces relatively good edge -33-lines, however, it oscillates at the edge lines, but the major drawbacks of this method are the complexity and the computational time. 2.6.1 Mathematical Representation Using four data points (pairs of numbers) (x 0 , fo), (x i , fi), (x 2 , f 2), and (x 3 , f3) the cubic spline interpolation finds three cubic polynomials, po(x) that interpolates between xo and X i , pi(x) that interpolates between x i and x 2 , p 2(x) that interpolates between x 2 and x 3 . For each polynomial there are four conditions and these are Pj(Xj) = fj, Pj(x J +i) = f J + i , p J Xx J ) = k J, pj ,(Xj +i) = kj+i, (14) where pj\xj) is the derivative of pj (XJ), j = 0, 1,2, and k 0 and k 3 are given, for simplicity they are equal to zero. B y direct calculation the spline polynomial can be written as P j ( x ) = fj * (x - x J + 1 ) 2 [1 + 2 (x - Xj)] + f j + 1 * (x - X j ) 2 [1 - 2 (x - x j + 1 ) ] + kj * (X - Xj) (x - x j + 1 ) 2 + k J + 1 * (x - Xj) 2 (X - X j + i ) (15) Differentiating pj(x) and Pj+i(x) twice, and making Pj"(x) = Pj+r'(x) (16) results in - 3 4 -k j . 1 +4kj + k J + 1 = 3 ( f j + 1 - f j . 1 ) The spline polynomial could be shown to bealso (17) Pj(x) = a j 0 + aji (x - Xj) + a j 2 (x - Xj) 2 + a j 3 (x - Xj)3 (18) Using Taylor's formula, the spline coefficients (ajo, aji, aj2, and aj3) are obtained as ajo = Pj(xj) = fj aji =Pj'(xj) = kj a j 2 = 3 (f j +, -fj) - (k J + 1 + 2 kj) a j 3 = 2 ( f J - f j + 1 ) - ( k J + 1 + k j ) (19) The three cubic spline polynomials are written as [60] p 0(x) = aoo + aoi (x - x 0 ) + ao2 (x - x 0 ) 2 + ao3 (x - x 0 ) 3 Pi(x) = aio + an ( x - x ! ) + a i 2 ( x - x i ) 2 + a i 3 ( x - x i ) 3 (20) p 2(x) = a 2 0 + a 2 i (x - x 2 ) + a 2 2 (x - x 2 ) 2 + a 2 3 (x - x 2 ) 3 where the aj's (ajo, aji, aj2, and aj3) are the spline coefficients. - 3 5 -The process starts with computing the derivatives of spline polynomials at the nodes of the spline curve (k 0, k i , k 2 , k 3 ) . Usually ko, and k 3 are given or set to zero. The k i , and k 2 are found by solving the system of equations k 0 + 4 k , + k 2 = 3 ( f 2 - f o ) k , + 4 k 2 + k 3 = 3 ( f 3 - f i ) (21) Next step is calculating the spline coefficients. Because this type of interpolation is data-dependent, so there is no fixed model for any arbitrary values. 2.6.2 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.21, and assume it is to be expanded 4 times and ko = k 3 = 0. I Figure 2.21 The original one dimension data Solving the mathematical equations and interpolating, the result of the expansion to the right direction of the cubic spline interpolation method is [ 4 3.49 2.39 1.34 1 1.33 1.83 2.41 3 2.87 2.52 2.16 2 1.8 0.6 0.2 ], Figure 2.22 shows the expanded result. -36-• Original points @ Mapped points Figure 2.22 The result of 4-time expansion using spline interpolation 2.6.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times using bicubic spline interpolation. The following is the result of expansion to the right direction. 0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 => 0 3 8 15 20 26 33 38 40 36 25 23 20 18 8 3 3 5 12 19 25 31 38 44 46 41 34 27 23 20 10 4 8 12 20 29 37 43 51 57 58 53 43 34 31 27 13 5 15 19 29 41 50 57 65 71 72 65 53 42 37 32 14 5 20 25 37 50 60 67 75 80 80 71 58 46 40 36 16 6 26 31 43 57 67 74 79 82 80 71 56 42 36 31 14 5 33 38 51 65 75 79 81 79 75 64 48 34 28 25 12 4 38 44 57 71 80 82 79 74 67 56 41 27 21 19 9 3 40 46 58 72 80 80 75 67 60 50 37 25 20 16 7 2 36 41 53 65 71 71 64 56 50 45 39 34 32 20 10 4 25 34 43 53 58 56 48 41 37 39 44 49 52 36 14 6 23 27 34 42 46 42 34 27 25 34 49 65 71 59 20 8 20 23 31 37 40 36 28 21 20 32 52 71 80 68 24 10 18 20 27 32 36 31 25 19 16 20 36 59 68 29 13 6 8 10 13 14 16 14 12 9 7 10 14 20 24 13 7 3 3 4 5 5 6 5 4 3 2 4 6 8 10 6 3 1 2.6.4 Algorithm The spline interpolation process is a separable one. That means it can be applied as a one-dimensional spline interpolation on every row and then a one-dimensional spline interpolation on every column. -37-2.7 B-Spline Interpolation B-spline is a special family of spline curves, the B is derived from the word basis. These splines consist of curve segments whose polynomial coefficients depend on the few middle points only. Thus, changing the value of a point affects only a small part of the curve, this behavior is called local control. In addition the time needed to compute the coefficients is greatly reduced. B-splines have the same continuity behavior as natural splines, but they do not pass through the original points. So there is a trade off between accuracy and simplicity. The natural splines produce relatively accurate curves but they are sensitive to the local values (pixels) and are computationally demanding. The B -spline method produces smoothed curves, which do not pass through the original points, but it is relatively a simple method [28, 63, 64]. The most famous B-spline interpolation method is the cubic B-spline interpolation method, which uses four points in the one dimensional case. A B-spline curve results from repeatedly convolving the Box function with itself. The order of the B-spline is the number of the times the box function is convolved with itself [28, 64]. The Cubic B-spline results from convolving the box function with itself three times. The cubic B-spline interpolation method is simpler and easier than the spline interpolation method, more stable than the cubic interpolation method because it does not oscillate, and computationally cheap. On the other hand, the original data are not exactly mapped, which means it is not as accurate. The other disadvantage is that the transition line at an edge is not as sharp as i.e. the cubic B-spline introduces smoothness to the expanded image [16]. -38-2.7.1 Mathematical Representation The cubic B-spline polynomial is the result of the convolution of a box function with itself three times. Given four equidistant points, the data (pairs of numbers) (x_i, f_i), (xo, fo), (x i , fi), and (x 2 , f 2), assume x i - xo = 1, and r = x - xo. The cubic B-spline function contribution expands to two neighbor pixels each side (forward and backward). The cubic spline contribution function can be give by the following equation The result of the cubic B-spline interpolation is that f.i contributes { ((1 - r ) 3 / 6) f_i } to the other points to be interpolated, fo contributes {(0.5 r 3 - r 2 + 2 / 3) fo }, fi contributes { (0.5 (1 - r) 3 - (1 - r ) 2 + 2 / 3) fi }, and f2 contributes { (r 3 / 6) f2 } [2, 3]. Then the expanded image w i l l result by adding the overlapped mapped values [28, 64]. The contributions can be written as follows P(t) = w ( l - t ) (x_2 < t < X.,) v ( 2 - t ) (x , < t < x 0 ) v ( t - 2 ) ( x 0 < t < x , ) u ( t -3 ) (x, <t < x 2 ) where U(t) =4a-t)3 o v(t) = - ( 3 t 3 - 6 t 2 + 4 ) 6 ( l - r ) 3 f -l + ( 3 r 3 - 6 r 2 + 4 ) f0 + ( 3 ( l - r ) 3 - 6 ( l - r ) 2 + 4 ) f 1 + - 3 9 -In 4-time expansion case, the original value w i l l be mapped onto fifteen values in the expanded result and this is called the mapping function, as shown in Figure 2.23. Figure 2.23 The original value, and its mapped result, in 4-time expansion case. The two-dimensional mapping function can be found by simply convolving a horizontal one-dimensional mapping function with a vertical one-dimensional mapping function [63, 64]. A s an example consider an expansion factor 4. A pixel in the original image is mapped onto a 15 x 15 block in the expanded image as shown in Figure 2.24. • Original point © Mapped points T -40-0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .1 .1 .1 .1 .1 .1 .1 0 0 0 0 0 0 0 0 .1 .2 .4 .6 .8 1 .6 .6 .4 .2 .1 0 0 0 0 0 .1 .3 .8 1 2 3 3 3 2 1 .8 .3 .1 0 0 0 0 .2 .8 2 3 5 7 7 7 5 3 2 .8 .2 0 0 0 .1 .4 1 3 6 10 12 13 12 10 6 3 1 .4 .1 0 0 .1 .6 2 5 10 15 19 20 19 15 10 5 2 .6 .1 0 0 .1 .8 3 7 12 19 24 26 24 19 12 7 3 .8 .1 0 0 .1 1 3 7 13 20 26 28 26 20 13 7 3 1 .1 0 0 .1 .8 3 7 12 19 24 26 24 19 12 7 3 .8 .1 0 0 .1 .6 2 5 10 15 19 20 19 15 10 5 2 .6 .1 0 0 .1 .4 1 3 6 10 12 13 12 10 6 3 1 .4 .1 0 0 0 .2 .8 2 3 5 7 7 7 5 3 2 .8 .2 0 0 0 0 .1 .3 .8 1 2 3 3 3 2 1 .8 .3 .1 0 0 0 0 0 .1 .2 .4 .6 .8 1 .8 .6 .4 .2 .1 0 0 0 0 0 0 0 0 .1 .1 .1 .1 .1 .1 .1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Figure 2.24 The model (spread function) of B-spline Interpolation -41 -2.7.2 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.25, and assume it is to be expanded 4 times. 1 Figure 2.25 The original one dimension data Mapping these data onto the expanded domain, then adding the overlapped values, the expanded result to the right direction is [ 2.8 2.77 2.46 2.08 1.83 1.84 2.04 2.3 2.5 2.54 2.42 2.17 1.83 1.44 1.02 0.64 ], Figure 2.26 shows this process. I km (a) O B n n • I T P 4 (b) Figure 2.26 (a) The mapped data onto the expanded domain, (b) the result of adding the overlapped values -42 2.7.3 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times. In this case each pixel is mapped onto a 15x15 block then the overlapped values are added, then rounded to the nearest integer. The following is the result of the expansion in the right direction. 0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 => 6 10 14 18 23 27 31 33 34 32 29 25 20 15 10 6 10 14 19 25 30 35 40 42 43 41 36 31 25 19 13 8 14 19 25 32 38 44 48 51 51 48 43 36 29 22 15 9 18 25 32 39 46 52 56 58 57 54 48 40 32 24 17 10 23 30 38 46 53 58 62 63 62 57 51 43 34 25 17 11 27 35 44 52 58 63 65 66 63 58 51' 42 33 25 17 10 31 40 48 56 62 65 67 66 62 56 49 41 32 24 16 10 33 41 51 58 63 66 66 63 59 53 47 39 31 23 16 10 34 43 51 57 62 63 62 59 55 50 45 38 32 24 17 11 32 41 48 54 57 58 56 52 50 47 44 40 35 28 20 13 29 36 43 48 51 51 49 47 45 44 44 43 39 33 24 15 25 31 36 41 43 42 41 39 38 40 43 44 42 36 27 18 20 25 29 32 34 33 32 31 32 35 39 42 42 36 28 18 15 19 22 24 25 25 24 23 24 28 33 36 36 32 24 16 10 13 15 17 17 17 16 16 17 20 24 27 28 24 19 12 6 8 9 10 11 10 10 10 11 13 15 18 18 16 12 8 2.7.4 Algorithm The cubic B-spline interpolation process is a separable one. That means it can be applied as a one-dimensional cubic B-spline interpolation on every row and then as a one-dimensional cubic B-spline interpolation on every column. -43-Frequency Interpolation This method starts with expanding the signal using the replication method. Then a low pass filter is applied in the frequency domain to smooth the high frequencies (blockiness effect) that are introduced by the replication expansion. This method is also called defocusing [41]. It sounds easy but there is one thing to be careful with, and that is the shape of the filter. There are many low pass filters that could be applied in this type of interpolation, but only two cases are discussed in this section: (1) The ideal low pass filter; and (2) The Butterworth low pass filter. 2.8 Ideal Filter Interpolation After the pixel replication method is used to expand the image, an ideal low pass filter is applied to the F F T of that expanded image [23]. The cutoff frequency is f m a x , where f m a x is the maximum frequency of the original image. It is clear that this method is simple and very fast. However, this method causes blurring, rippling and oscillation effects at the edges in the expanded image [27, 41]. 2.8.1 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.27, and assume it is to be expanded 4 times. The expanded points using replication are [ 4 4 4 4 1 1 1 1 3 3 3 3 2 2 2 2 ], as shown in Figure 2.28. -44-• 1 Figure 2.27 The original one dimension data • © o o • V V V 1 m m Figure 2.28 The expanded one dimension data using replication method Applying an ideal low pass filter on the F F T of the expanded data is shown in Figure 2.29. Then computing the IFFT of the filtered points, the expanded result is [ 3.44 4.28 4.28 3.25 1.75 0.72 0.72 1.56 2.56 3.13 3.13 2.75 2.25 1.87 1.87 2.44 ], where the original data are bolded for convenience. Figure 2.30 shows this process. Figure 2.29 The F F T of the expanded signal, with the Ideal L P F , and filtered F F T . The Ideal Low Pass Filter -45-T • i • • • • Original points Mapped points v v Figure 2.30 The result of IFFT of the filtered signal by using ideal L P F 2.8.2 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times, the expanded result as follows: 0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 => 14 3 3 13 23 28 28 29 34 39 39 35 34 35 35 28 3 0 0 3 12 15 15 20 31 42 42 32 20 16 16 12 3 0 0 3 12 15 15 20 31 42 42 32 20 16 16 12 13 3 3 14 26 32 32 34 43 52 52 42 31 26 26 23 23 12 12 26 44 52 52 54 62 73 73 60 43 35 35 33 28 15 15 32 52 63 63 65 76 90 90 72 51 39 39 38 28 15 15 32 52 63 63 65 76 90 90 72 51 39 39 38 29 20 20 34 54 65 65 63 68 76 76 63 45 34 34 35 34 31 31 43 62 76 76 68 63 65 65 54 36 23 23 30 39 42 42 52 73 90 90 76 65 63 63 52 29 10 10 25 39 42 42 52 73 90 90 76 65 65 65 52 29 10 10 25 35 32 32 42 60 72 72 63 54 52 52 47 39 32 32 35 34 20 20 31 43 51 51 45 36 29 29 39 55 68 68 54 35 16 16 26 35 39 39 34 23 10 10 32 68 96 96 69 35 16 16 26 35 39 39 34 23 10 10 32 68 96 96 69 28 12 12 23 33 38 38 35 30 25 25 35 54 69 69 51 2.8.3 Algorithm This method is not a separable method. -46-2.9 Butterworth Filter Interpolation A Butterworth low pass filter is used instead of an ideal low pass filter. The filter is applied on the F F T of the data expanded using the replication method. This method produces better results than the ideal low pass filter, in terms of ripples and oscillations [23, 27]. But it is not as simple to implement. 2.9.1 One-dimension Interpolation Let the original data set be [ 4 1 3 2 ], as shown in Figure 2.31, and assume it is to be expanded 4 times. 1 Figure 2.31 The original one dimension data The expanded points using replication are [ 4 4 4 4 1 1 1 1 3 3 3 3 2 2 2 2 ] , the original data is bolded for convenience, as shown in Figure 2.32. o o © f O <? O I Figure 2.32 The expanded one dimension data using replication method - 4 7 -Applying the Butterworth low pass filter on the F F T of the expanded data as shown in Figure 2.33. Then computing the IFFT o f the filtered points, the expanded result is [ 3.48 4 4 3.25 1.75 1 1 1.52 2.52 3 3 2.75 2.25 2 2 2.48 ], the original data is bolded for convenience. Figure 2.34 shows this process. Figure 2.33 The F F T of the expanded signal, the Butterworth L P F f © @ m t • Original points O Mapped points I w Figure 2.34 The result of IFFT of the signal filtered by the Butterworth L P F 2.9.2 Two-Dimension Interpolation Assume the original 2-dimentional image is to be expanded 4 times. The expanded result after replication and applying the Butterworth filter is -48-0 20 40 20 20 60 80 40 40 80 60 20 20 40 20 80 => 2.9.3 Algorithm This method is not a separabl 13 5 5 11 21 26 26 28 5 0 0 5 15 20 20 24 5 0 0 5 15 20 20 24 11 5 5 12 25 31 31 35 21 15 15 25 42 51 51 54 26 20 20 31 50 60 60 64 26 20 20 31 50 60 60 64 28 24 24 35 54 64 64 66 33 34 34 44 64 74 74 71 36 40 40 50 70 81 81 74 35 40 40 50 70 81 81 74 34 34 34 43 61 70 70 64 34 25 25 31 44 49 49 45 35 20 20 25 35 40 40 35 35 20 20 25 35 40 40 35 28 15 15 21 31 36 36 34 method -49-33 36 36 35 34 35 35 28 34 40 40 34 25 20 20 45 34 40 40 34 25 20 20 45 44 50 50 43 31 25 25 21 64 70 70 61 44 35 35 31 74 81 81 70 49 40 40 36 74 81 81 70 49 40 40 36 71 74 74 64 45 35 35 34 66 64 64 55 35 25 25 29 64 60 60 51 31 20 20 26 64 60 60 51 31 20 20 26 55 51 51 47 39 34 34 35 35 31 31 39 56 65 65 54 25 20 20 34 65 80 80 65 25 20 20 34 65 80 80 65 29 26 26 35 54 65 65 52 3 Experimental Simulation 3.0 Introduction In this section the results of using ten different methods, nine of which were discussed in the previous section. The tenth method is our proposed method and this is introduced and discussed in Chapter 4. For all these pictures, the expansion factor is equal to 2. The aim of this study is not to restore undersampled (scaled down) images, but to expand any given image. Thus the criterion for the effectiveness of each method is to be measured by the visual appearance as judged by the human observer. -50-The Tropic Image Examples B-spline Interpolation Spline Interpolation The Proposed Method Figure 3.1 The "Tropic" image and its expanded results using ten different methods including the proposed method. - 5 2 -Figure 3.2 The original "Tropic" image -53-Figure 3.3 The Expanded image by the replication method, expansion factor is equal 3. - 5 4 -Figure 3.6 The Expanded image by the Proposed method, expansion factor is equal 3. -57-3.2 The Saad Image E xamples / B-spline Interpolation Spline Interpolation Ideal L P F Frequency Interpolation Butterworth L P F Frequency Interpolation The Proposed Method Figure 3.7 The "Saad" image and -59-Figure 3.8 The original "Saad" image - 6 0 --61 Figure 3.10 The Expanded image by the Linear Interpolation method, expansion factor is equal 3. -62 Figure 3.11 The Expanded image by the Cubic Interpolation method, expansion factor is equal 3 -63 Figure 3.12 The Expanded image by the Proposed method, expansion factor is equal 3. -64 3.3 Analysis of the Ex p ansion Methods 3.3.1 Replication Method The pixel replication method is very fast and computationally cheap. Having these advantages makes it the first choice in many digital signal processing applications. The major drawback of the pixel replication method is the apparent blockiness effects introduced all over the image and specially at the edges [27, 41]. The blockiness effect is obvious at the edge whether the edge is sharp or smooth. A sharp edge is an edge where the intensity difference across it is large, and usually lies between two different regions in the image. A smooth edge is an edge where the intensity difference across it is small, and lies within a region in the image. The higher the expansion factor the more obvious and annoying the blockiness effects in the expanded image [1, 2, 3, 15]. Sometimes the blockiness effects are not acceptable even within a smooth region. 3.3.2 Linear Interpolation Method The linear interpolation method assumes that the image has a continuos intensity function but not necessarily a continuos first derivative. The linear interpolation method is fast and computationally cheap, which makes it attractive for many applications and a good competitor to the pixel replication method in many image processing applications [4, 5, 41]. The linear interpolation method reduces but does not eliminate the blockiness effects at the edges introduced by the expansion process. However, it reduces the blockiness effects in the other areas of the expanded image. The blockiness and the blurring effects are obvious in the expanded image and the higher the expansion factor -65 the more obvious and annoying the blockiness effects. The linear interpolation method introduces a ringing or contouring effects as it smoothes the expanded image [27]. 3.3.3 Quadratic Interpolation Method The quadratic interpolation method assumes that the image has a continuos intensity function and a continuos first derivative but not necessarily a continuos second derivative [60]. This method reduces the ringing or contouring effects of the linear interpolation but it does not eliminate the blockiness effects. The quadratic interpolation method produces blurry expanded image but better than linear interpolation. It is more computationally demanding than the linear interpolation method. For higher expansion factors this method gives better performance than linear interpolation. 3.3.4 Cubic Interpolation Method The cubic interpolation method assumes that the image has a continuos intensity function and continuos first and second derivatives but not necessarily continuos higher derivatives. The cubic interpolation method reduces the blockiness effects specially within homogeneous regions [60]. However, the blockiness at the edges still exists. Cubic interpolation produces better results than the linear and quadratic interpolation methods, but it is not as fast computationally. Cubic interpolation may introduce oscillation effects at the edges because of the assumption about the continuity of the image and its derivatives [15, 16]. -66 3.3.5 Bezier Interpolation Method Bezier interpolation eliminates any blockiness effects in the expanded image by (unacceptably) oversmoothing the expanded image. This method does not map the original pixels' values into the expanded image, so that it is not suitable for image expansion application. Bezier interpolation method is a good method for modeling and rendering in the computer vision fields [63, 64]. 3.3.6 Spline Interpolation Method Spline interpolation is sensitive to the pixels' values, because it is data dependent. This method interpolates the homogenous regions well [16]. On the other hand, it causes oscillation effects at the edges in the expanded image, which is not tolerable in some applications. The main drawback of spline interpolation is that it is very computationally expensive because it has to solve a set of spline equations for 4 pixel. In some applications, where the system complexity and cost of computations are not the first priorities, spline interpolation method could be considered a good interpolation method [15,16]. 3.3.7 B-Spline Interpolate n Method The Cubic B-spline method eliminates the blockiness in the expanded image by smoothing the expanded image, while it does not map the original pixels ' values into the expanded image [63, 64]. Cubic B-spline smoothness is much less than that of the cubic Bezier method. The smoothness causes the sharp edges to seem defocused or blurred. This method deals very well with smooth areas inside the homogeneous regions. In -67 many applications this method is considered as a good method because it doesn't introduce blockiness effects as most other methods do [16]. 3.3.8 Ideal Filter Interpolation Method The ideal low pass filter cutoff frequency is equal to the original image bandwidth. That means the expanded image would only contain frequency components that exist in the original image [27]. Using this ideal low pass filter eliminates all the high frequency components from the expanded image. This introduces little distortion to the edges and ripples or oscillations (waves) effects in the homogenous regions. The sharp edges are relatively reserved, but the oscillation blurs the smooth areas inside the homogeneous regions [23]. The smoother the region the higher are the oscillation effects. A s a result, the smoothest regions suffer the most. This method is computationally cheap and fast but neither precise nor efficient. This is not used for image expansion purposes. 3.3.9 Butterworth Filter In terpolation Method Using other ideal low pass filters instead of the ideal low pass filter w i l l better preserve the high frequency components. This w i l l improve the ripple and oscillation effects, but introduces blockiness effects. The closer the low pass filter to the ideal low pass filter the more the oscillation and the less the blockiness, on the other hand the wider the transition period of the low pass filter the less the oscillations and the more the blockiness [23]. The extreme case is keeping all frequency components which result in the replication method. -68 4 Information-Preserving Image Expansion Method 4.0 Introduction A common problem shared by existing methods is that the edges in the expanded image have a zigzag effect. This is specially unacceptable when these edges are known to be straight edges. Our method described in this chapter does not have this problem. After finding the edges in the original image, these edges are expanded so as to preserve their original shapes. Then the values of the pixels and around the edges are estimated so as to yield a natural and usually acceptable effect. This method starts with edge detection. There are many edge detection techniques that can be used to produce the edge image. These include the Sobel, Roberts, Laplacian [65], Canny [66, 67], Gaussian, or L o G (Laplacian of Gaussian) [68, 69, 70] edge detectors. The Laplacian edge detector is used with binary images because it produces closed edges in the edge image [66]. A n d Canny edge detector is used with gray level images because it produces a thin edge, which is of -69 • single-pixel width [67]. There are many other methods that detect edge in binary images [71], gray-level images [72, 73, 74, 75], and color images [76, 77]. Other methods produce two or more pixel wide edges and this may cause problems in the expansion stage. 4.1 Edge Detection, E dge Encoding 1. Edge Detection For gray-level images we use the Canny edge detector. For binary images, the 4-connectivity Laplacian operator [66], as shown in Figure 4.1, is used as an edge detection algorithm. This edge detector involves applying the Laplacian operator on a binary image. A positive, zero, or negative value w i l l be the result of this edge detector. Only the positive outcomes are considered as an edge. 0 -1 0 -1 4 -1 0 -1 0 Figure 4.1 The Laplacian operator. - The positive value occurs when the detected pixel has the value 1, and one or more of its 4-connectivety neighbor pixels have the value 0. - The zero value occurs when the detected pixel and all o f its 4-connectivety neighbor pixels have the same intensity values, either the value 1 or 0. - The negative value occurs when the detected pixel has the value 0 and one or more of its 4-connectivety neighbor pixels have the value 1. - 70 A n example on the three possible values of the Laplacian edge detector that applied on a binary image is shown Figure 4.2. 2. Chain coding After detecting the one pixel wide edges, these edges are coded using chain coding. A l l edges in the edge image are coded using an 8-connectivety chain code with a simple numbering scheme [78]. Figure 4.3 shows the used numbering scheme. 0 -1 0 -1 4 -1 0 -1 0 Laplcian edge detector Pixel marked as an edge pixel by using Laplacian edge detector The three possible outcomes of the Laplacian operator I—* 1 1 0 1 1 0 i i o o 0 0 0 ^12 0 0 0 Example of an edge in a binary image, and sample pixels l x , l y , and l z 1 1 0 1 1 1 1 1 1—I 0 0 1 V 0 1 0 0 Positive result Zero result Negative result Figure 4.2 Example on an edge detected using the Laplacian edge detector. -71 3 2 1 5 6 7 Figure 4.3 The numbering scheme used with 8-connectivety chain coding. Chain coding starts from the upper-left corner to the lower-right corner. Chain coding of edges proceeds as follows: 1. The search for the beginning of an edge starts from right, left, up, down, north-east, north-west, south-west, and south-east, which is in chain code numbers: 0, 4, 2, 6, 1, 3, 5, then 7. 2. A t each pixel position lying on an edge, the encoder starts the search for the next pixel using the previous pixel direction. For example, i f the previous pixel on the edge is coded in the direction 6, which is the downward direction, the encoder then searches for the next chain pixel by considering the pixels whose direction are 6 + 1 - 7 and 6 - 1 = 5 . If the pixel is an edge pixel i.e., with a pixel value in the edge image equals to 1, then the encoder stops the search for the next pixel. 3. If the pixel in step 2 is not an edge pixel, the encoder searches the remaining unchecked chain code directions in the following order: 0, 4, 2, 6, 1, 3, 5, then 7. In the above example the encoder w i l l check the following sequence: 0, 4, 2, 1, then 3. -72 The start pixel 0 0 2 0 0 2 0 0 2 0 0 0 0 7 7 6 6 5 5 4 4 3 3 2 2 1 1 1 0 0 1 0 0 7 6 6 5 4 Figure 4.4 Examples of edges and their chain codes. 4.2 Edge expansion process Edges in the edge image are classified into one of two types: 1) Straight line edges i.e., horizontal lines, vertical lines, or lines with 45° or 135° slope values. The chain code of such a line has a series of the same chain code number e.g. 3, 3, . . . , 3. These types of edges are expanded by a straightforward technique, which is that of repeating the chain code of the edge as many times as the expansion factor. For example consider an edge with chain code [ 0 0 0 0 0 0 0 0 ] , which is a total of 8 pixels at the angle 0°. Assume this horizontal line edge is to be expanded 3 times, then the expanded result of that edge is a total o f 24 pixels at the angle 0° i.e. a horizontal line edge also [79]. Figure 4.5 shows this edge and its expanded edge. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An original horizontal edge The expanded horizontal edge Figure 4.5 Example of 8 pixels horizontal line edge and its expanded edge. -73 2) Slope line edges other than those in (1) above. These edges are simply formed of two or more short connected lines that are shifted from each other by one pixel in the horizontal, vertical, or diagonal direction depending on the values of their slope. Figure 4.6 shows examples of slope edges in the edge image. Figure 4.6 Examples of slope line edges. The chain code of a slope line edge consists of a series of the same chain code with a single change in the chain code ( C C C ) between pixels, which means the pixels have the same direction but with a single change in direction between pixels, which represents the single shift. For example consider the slope line edge with the chain code [ 2 2 1 2 2 2 ], in this example the slope line edge is a series o f 2's and the single change is 1, i.e. the change in the chain code ( C C C ) is 1. This edge is a line with six pixels long at the angle 76°. -74 Expanding a slope line edge by repeating the chain code of every pixel by the expansion factor number is called edge-shape-replication and introduces a staircase phenomenon that causes the unnatural look of the edges in the expanded edge image as shown in Figure 4.7. The higher the expansion factor the more unnatural and annoying the staircase phenomenon is. t t t ? -*»-t*>-*»-*»-)t-*»~ r 9 (a) (b) Figure 4.7 (a) A slope line edge, (b) Its expanded result by repeating the chain code 3 times, (expansion factor = 3). Obviously, using the edge-shape-replication method does not enlarge slope line edges correctly. The proposed method described below enlarges the slope line edges efficiently as shown in Figure 4.8. The proposed method Replication method (a) (b) Figure 4.8 (a) A slope-line edge, (b) Its expanded results using edge-shape-replication and the proposed methods, (expansion factor = 3). -75 4.3 The Proposed Method After representing all the edges in the edge image as chain code sequences, the slope line edges are then found in these sequences. A slope line edge was defined earlier as a series of the same chain code number (same direction) with single change between pixels, which is called a change in chain code (CCC) . Figure 4.9 shows an example of a slope line edge with the chain code [ 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 ] , which has changes in its chain code i.e. 3 C C C s , where the slope line edge is a series of 0's and the C C C s are equal to 2. Figure 4.9 An Example of a slope line edge, (a) Actual edge in the edge image, (b) Its chain code representation. We notice that to recognize an edge as a slope line edge simply involves checking the C C C s in the chain code. The C C C detector starts from the second number in the chain code - because the first number cannot be a C C C - and checks all the numbers of the chain code. A chain code number is considered a C C C only i f the number before it and the number after it are equal and both are different from its value as shown in Figure Series of the same chain code number (0) CCCs (2) (a) (b) 4.10. -76 6 6 2 6 5 7 0 7 7 7 (a) 6 6(2)6 5 7 ® 7 7 7 4 ^ C C C (c) 6g2]6 5 70 77 7 6 6|2Jj5|7 0 7 7 7 6 6 2 6[5Jjo|7 7 7 6 6'2 6 5 7[0W7l7 6 |6^6[570777 662 6 ^ 7 0 7 7 7 6 6 2 6 5 7 ^ 7 7 7 662 65 70|7^7 (b) Figure 4.10 Example of the C C C detector, (a) The chain code, (b) The detection processes, and (c) The C C C detector result where only two C C C s are detected. The series of the same chain code numbers before the C C C , and the series of the same chain code numbers after it forms one series, which is called a segment. The series before is called pre-CCC, and the series after is called post-CCC. For example, consider the segment with the chain code [ 0 0 0 2 0 0 0 ], which is part of a slope line edge. Clearly, the 2 is the C C C , and the series of three 0's before it is the pre-CCC and the series of the three 0's after it is the post-CCC as shown in Figure 4.11. C C C post-CCC pre-CCC (b) Figure 4.11. Example of a segment of a slope line edge, its pre-part, the C C C , and its post-part, (a) The segment chain code, and (b) The edge in the edge image. -77 A long slope-line edge consists of more than one C C C in its chain code sequence. In this case, segments are overlapped, as a pre-CCC of a segment is a post-CCC of another as shown in Figure 4.12. The chain code of a long slope line edge 2 0 0#0 0#0 0 © 0 0#0 0@0 0 Assumed slope line edge CCCs Figure 4.12 A long slope line edge and its chain code. A l l slope line edges can be separated into segments whose properties are listed in a table that lists the edge position, edge direction, C C C direction, and the length of the pre-CCC and post-CCC of a segment. Table 4.1 shows an example of the edge with slope lines shown in Figure 4.13, whose chain code is [ 0 7 6 7 7 6 7 7 6 5 5 6 5 6 5 6 6 6 6 6 6 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 4 6 6 ]. Table 1 Sample of the segments' properties table. Pre-part Change in Position Pre-part Post-part Direction Chain Code in chain Length length (CCC) code 7 6 3 1 2 7 6 6 2 2 5 6 12 2 1 5 6 14 1 1 6 7 22 5 15 6 4 38 15 2. -78 \ k / J ,i i 8 i s i s 8 4 8 4 8 t I S i 8 Figure 4.13 Example of the edge that is analyzed in Table 4.1 Before expanding (enlarging) a slope line edge, its edge position must be estimated. We consider two estimated positions only: (1) completely above the slope line edge, and (2) completely under the slope line edge. Figure 4.14 shows these two estimated positions. The first position is considered in the proposed algorithm. -79 The estimated real edge The slope line edge The estimated real edge (a) (b) Figure 4.14 The two estimations of the real edge, (a) Position 1 (above), and (b) Position 2 (under). In the first case, the edge is estimated to be above the slope line edge. Here the area under the estimated edge position is formed of triangles whose two sides are the C C C pixel and its pre-CCC as shown in Figure 4.15 (a). The chain code sequence of that example is [ 0 0 0 2 0 0 0 2 0 0 0 ] . In Figure 4.15 (b) this edge is separated into 1) A triangle [ 0 0 0 2 ] , which consists of the pre-CCC [ 0 0 0 ] and the C C C [ 2 ], 2) A triangle [ 0 0 0 2 ] , which consists of the pre-CCC [ 0 0 0 ] and the C C C [2], 3) A line [ 0 0 0 ] , which is the post-CCC. Enlarging a slope line edge using the traditional replication method introduces blockiness effects and the chain code sequence when the expansion factor is equal to 4 w i l l be [ 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 ] as shown in Figure 4.15 (c). Our proposed method regenerates the estimation of the slope line edge, using the same original triangle sequence [ 0 0 0 2 ], four times (the expansion factor = 4 in this example), the enlarged triangle sequence then becomes [ 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 ], as shown in Figure 4.15 (d). Repeating the same process for every triangle produces the enlarged slope line edge efficiently, and the final enlarged edge - 80 chain code sequence is [ 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 ] , as shown in Figure 4.15 (e). The estimated real edge C C C and its ) pre-CCC ...•Q^O-tO-iO ,..-C;^0-0~tO • ^ © H O H O • • • m^o~to~*Q • • • (d) Figure 4.15 The expansion process of the first estimated position which is above the slope line edge. -81 In the second case, the edge is estimated to be under the slope line edge, the area above the estimated edge position is simply formed o f triangles. Two sides of the triangle are formed by the C C C pixel and its post-CCC as shown the example in Figure 4.16 (a). The chain code sequence of this example is [ 0 0 0 2 0 0 0 2 0 0 0 ]. In Figure 4.16 (b) the edge is separated into 1) A line [ 0 0 0 ] , which is the pre-CCC, 2) A triangle [ 2 0 0 0 ] , which consists of the C C C [ 2 ] and the post-CCC [ 0 0 0 ] , 3) A triangle [ 2 0 0 0 ] , which consists of the C C C [ 2 ] and the post-CCC [ 0 0 0 ] . Expanding a slope line edge using the traditional replication method introduces blockiness effects and the chain code sequence when the expansion factor is 4 w i l l be [ 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 ] as shown in Figure 4.16 (c). Our proposed method regenerates the estimation of the slope line edge, using the same original triangle sequence [ 2 0 0 0 ], (four times, the expansion factor - 4 in this example), the enlarged triangle becomes [ 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 ], as shown in Figure 4.16 (d). Repeating the same process for every triangle above the real edge the expansion produces the enlarged slope line edge efficiently, and the final enlarged edge chain code sequence is [ 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 ] , as shown in Figure 4.16 (e). -82 The estimated real edge C C C and its post-CCC (a) (b) (C) • O «D O !• K> O iO «• ~tO K>~tO §-io-*o-«>"" g-i©-*©-!©-'" o~o-to.^o-"" (d) (e) Figure 4.16 The expansion process of the second estimated position which is under the slope line edge. 83 4.4 Slope Line Edges Cases There are 2 different cases of slope line edges. This classification depends on the length of the segment after the change in the chain code i.e. the post-CCC of the segment relative to the length of its pre-CCC. In general, the length of the pre -CCC of a segment is close to the length of its post-CCC in value. This is the first case, and is considered to be the short post-CCC case. The other case is the long post-CCC case, where the post-C C C is considered to be long i.e. it is at least twice as long as the pre-part of the same segment. For example, consider a segment whose pre-CCC length is 3 pixels, it w i l l be considered a short post-CCC segment i f the post-CCC length is 5 pixels or less. On the other hand, it w i l l be considered a long post-CCC segment i f the post-CCC length is 6 pixels or more. These two cases are expanded differently [80, 81]. Case 1 (short post-CCC segment): In this case, the post-CCC length is greater or equal to twice the pre -CCC length. For example, consider the slope line edge with chain code [ X 0 0 2 0 0 0 Y ] , where the 2 is the C C C , and the segment is [ 0 0 2 0 0 0 ]. The pre-CCC length is 2 pixels, and the length of the post-CCC is 3 pixel, which is obviously less than 4. In this work, we consider the estimated edge position to be position 2, which is the under the slope line edge. Position 1 could also be taken but then the positions and the processes for the other cases should be reversed. Figure 4.17 shows this example. A s described before, repeating the triangle that is made of the C C C and the post-CCC of the segment N times, where N is the expansion factor expands this type of segments. - 84 Sample of an edge Segment C C C 1 0 0 2 0 0 2 2 1 0 0 2 0 0 2 2 (a) (b) Figure 4.17 Short post-CCC slope line edge (case 1), (a) The slope line edge and its chain code, (b) the segment, its pre- and post-CCCs, and the C C C . Figure 4.18 shows the expansion process. In general, a slope line edge is made of few overlapped segments. To expand such an edge, the triangle o f the C C C and the post-C C C of every segment is repeated N times, where N is the expansion factor. Figure 4.19 shows an example of a slope line edge with few overlapped segments. -85 The estimated real edge C C C and its post-CCC C C C t ? 1 0 0 2 0 0 2 2 (a) (b) (C) (d) (e) Figure 4.18 Short post-CCC slope line edge (case 1), (a) The slope line edge, (b) The sample of an edge divided into pieces, the pieces expanded by (c) The replication method, (d) The proposed method, and (e) The expanded edge by using the proposed method. -86 Segments 7 0 0 1 0 0 2 0 0 0 2 0 0 1 1 (a) 7 7 0 0 0 0 1 0 0 1 0 0 2 0 0 0 2 0 0 0 2 0 0 2 0 0 1 1 1 1 (b) Figure 4.19 Short post-CCC slope line edge (case 1) with few segment, (a) The slope line edge, (b) The expanded edge by using the proposed method. Case 2: (long post-CCC segment): In this case, the post-CCC length is greater or equal to twice the pre -CCC length. For example, consider the slope line edge with chain code [ X 0 0 2 0 0 0 0 0 0 Y ] , where the 2 is the C C C , and the segment is [ 0 0 2 0 0 0 0 0 0 ]. The pre-CCC length is 2 pixels, and the length of the post-CCC is 6 pixel. In this work, we consider the estimated edge position to be position 2, which is the under the slope line edge. Figure 4.20 shows this example. -87 Sample of an edge 1 0 0 2 0 0 0 0 0 0 6 6 (a) (b) Figure 4.20 Long post-CCC slope line edge (case 2), (a) The slope line edge and its chain code, (b) the segment, its pre- and post-CCCs, and the C C C . Repeating the triangle, which is made of the C C C and the post-CCC of the segment, does not expand this type o f segment correctly. To expand this type of segments correctly, the triangle to be repeated is made of the C C C and only part of the post-CCC. The length of the considered part is equal to the length of the pre-CCC, in the above example, the triangle to be repeated N times, is the C C C and the only two pixels of the post-CCC [ 2 0 0 ], where the C C C is 2, and N is the expansion factor. Figure 4.21 shows the expansion process. Figure 4.22 shows an example of a slope line edge with few overlapped segments and the last segment is a long one. Segment ^ - C C C 1 0 0 2 0 0 0 0 0 0 6 6 -88 The estimated real edge C C C 4 1 0 0 2 0 0 0 0 0 0 6 6 (a) C C C and part of its post-CCC (b) (c) • • • • f - 0 - ) 0 - ( « - » 0 - « D f » - • • - I C H O - l » - 1 0 - I O - + - • • (d) • • o-tOr> t - i o o \ % xo *o ~*o <o ~ o - t o o O- iO^O"" 0 - 0 : * 0 " " (e) o-to-^o" 0 §0 ^•~*o-to «» " £ 8 (0 Figure 4.21 Long post-part slope line edge (case 2), (a) The slope line edge, (b) The sample of an edge divided into pieces, the pieces expanded by (c) The replication method, (d) Expanding the segment as a case 1 segment, (e) The proposed method, and (f) The expanded edge by using the proposed method. - 89 Segments 7 0 0 1 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 (a) Chain code replication 7 7 0 0 0 0 1 0 0 1 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 (b) Figure 4.22 Slope line edge (case 2), (a) The slope line edge and its segment, (b) the edge estimated position, and (c) The 3 times expanded result. -90 4.5 Examples The result of edge image expansion is obviously clear in an image that contains only lines such as "Maple L e a f and "Texas" images which are shown in Figure 4.23 and Figure 4.24. (a) (b) Figure 4.23 The "Maple L e a f image (a) The original edge image, (b) The expanded edge image using the proposed method, the expansion factor is 3. -91 (b) (c) Figure 4.24 The "Texas Map" image (a) The original edge image, and the expanded images using the proposed method, the expansion factors are (b) 3, and (c) 5. 4.6 Binary Images Expansion Laplacian edge detector produces closed edges, which means closed regions. Expanding a closed edge produces a closed expanded edge. Flood filling is used to f i l l the closed expanded regions. Figure 4.25 shows an example of expanding " A B C " binary image using three different conventional methods and the proposed method. In that example the original image reduced by 2, then expanded by 2 using the same method for reduction then expansion. Another example is the "Rabab" image, which is the Arabic writing of the name Rabab. Figure 4.26 shows the reduction by 2 then expansion by 2 using three conventional methods and the proposed method. -92 ABC (a) ABC (b) ABC (c) ABC ABC (d) (e) Figure 4.25 The " A B C " Image, (a) The original binary image, and its reduced then expanded by 2 images using four different methods (b) Replication, (c) Linear Interpolation, (d) Cubic Interpolation, and (e) The proposed method. -93 (a) (b) (c) (d) (e) Figure 4.26 The "Rabab" Image, (a) The original binary image, and its reduced then expanded by 2 images using four different methods (b) Replication, (c) Linear Interpolation, (d) Cubic Interpolation, and (e) The proposed method. -94 4.7 Gray-Level Image Expansion The Canny edge detector [67] is used to produce the edge image of a gray-level image. The Canny edge detector produces single width pixel edges as the edge image [82]. Edges in the edge image are coded and expanded following the same procedure that is used with the binary image expansion and which is discussed in the previous section [82]. However, expanding the inside or the homogenous regions of gray-level images is different from that of the binary images. Expansion process A l l original pixels are mapped onto the expanded image. The expansion procedure introduces many new pixels in the expanded image, which have to be filled. For example, expanding an image 2 times introduces three new pixels for every original pixel as shown in Figure 4.27. X • X • X X • • • • X Orignnal pixels X X X • X • * Inroduced pixels by expansion to be filled • • • • (a) (b) Figure 4.27 Example on the original pixels mapping onto the expanded image (a) The original pixels, (b) The expanded image. The introduced pixels are filled differently depending on their position relative to an edge. There are three different kind of pixels depending on their positions relative of an -95 edge: (a) inside pixel (far from an edge), (b) edge pixel (lies on the edge itself), and (c) near edge pixel (within two pixels distance from an edge), as shown in Figure 4.28. Figure 4.28 The three different pixel position with respect to an edge. Gray pixels lie in a homogenous region, Dark pixels lie on an edge, White pixels lie near edge pixels. (a) Inside pixels: a window of 3x3 is used to determine i f the pixel to be expanded is an inside pixel or not. This type includes all pixels that are 2 or more pixels away from an edge and are considered to form pixels in homogenous regions. These pixels are filled using adaptive averaging filters. Inside a homogenous region, the introduced pixel position is one o f three different positions with respect to the original pixel. The three different positions are to the right, to the bottom and to the right-bottom of the original pixel as shown in Figure 4.29. Each of these positions is expanded with a different window. The window coefficients (a and b) determine the method that w i l l be used to f i l l - 96 the new pixel. Giving a and b the values 1 and 0, respectively, fides the value of the new pixel using the replication method. Giving them both the same values (i.e. in this case 0.5), finds the value of the new pixel using the linear interpolation method. The proposed method uses the value 0.7 for a and the value 0.3 for b. X o X o X X • A • A X X X o X O • A • A X Orignnal pixels Inroduced pixels O To the right • To the bottom A To the right-bottom (a) (b) Figure 4.29 (a) The original pixels, (b) The three different positions of the inside region pixels. A pixel to the right of the original pixel lies horizontally between two original pixels and is represented as a circle in Figure 4.29. Such pixels are filled using the window that is shown in Figure 4.30. c X O X O • A • A X © o • A • A Figure 4.30 The window that calculates the value of the pixels to the right of an original pixel. -97 A pixel to the bottom of the original pixel lies vertically between two original pixels and is represented as a square in Figure 4.29. Such pixels are filled by also using the averaging filter as shown in Figure 4.31. The window coefficients are 0.7 for a and 0.3 for b, as explained before. X O X O • A © A X O X O • A • A Figure 4.31 The window that calculates the value of the pixels to the bottom of an original pixel. A pixel to the right-bottom of the original pixel lies in the middle among four original pixels and is represented as a triangle in Figure 4.29. Such pixels are filled using the averaging filter shown in Figure 4.32. The window coefficients can be chosen as explained before. The window coefficients are 0.7 for a and 0.1 for b, as explained before. X • X • O O A x ] O • A • A A Figure 4.32 The window that calculates the value of the pixels to the right-bottom of an original pixel. -98 (b) Edge pixels: are pixels that lie on an edge itself. A s discussed earlier the shape of the edge such as in Figure 4.33 (a), whose chain code is represented by arrows in Figure 4.33 (b), would be expanded to become as shown in Figure 4.33 (c). However, repeating these pixels' values as shown in Figure 4.33 (d), produces a zigzag effect, as shown in Figure 4.33 (e). 9 86 85 78 76 V) 74 72 70 (a) (c) 86 85 78 76 85 78 76 74 72 70 74 72 70 V) > 1 4 V) (b) !2> 52) (d) Edge pixel • • Edge chain code of the first segment • A> • Edge chain code of the second segment (e) Figure 4.33 Example of filling the edge pixels by repeating the original edge pixels' values, (a) The original edge pixels, (b) The chain code represented by arrows, (c) The expanded edge, (d) The values of the expanded edge pixels repeated from the original pixels, and (e) The edge pixels values. -99 The proposed method suggests that any original edge pixel that does not lie on an expanded edge, its value w i l l be altered, as shown in Figure 4.34 (b), and it w i l l be calculated the next step with the next type of pixels (c). The value o f a new edge pixel is calculated from its two nearest original edge pixels, which are original pixels and lie on the expanded edge too. The linear interpolation technique is used to calculate the value of a new pixel from its nearest two known edge pixels. For example in Figure 4.34 (b), the unknown value of the pixel that lies between the 78 and the 76 pixels is 77. 86 85 78 76 74 72 70 (a) 84 82 80 m 77 75 74 73 I\ 85 74 if 1 (b) g | Original pixel lies on the expanded edge 85 74 Original pixels altered 86 Edge pixel is filled using the proposed method (c) Figure 4.34 Example of filling the edge pixels by the proposed method, (a) The original edge pixels, (b) The original edge values that were kept or altered for the expanded edge, and (c) The calculated values of the expanded edge. - 100 (c) Near edge pixels: A near edge pixel is a pixel whose distance from any edge pixel is less than two pixels, where the distance between any 2 horizontal, vertical or diagonal pixels is considered to be equal to 1. These pixels lie in the narrow areas between the homogenous regions and edges and are shown as white squares in Figure 4.35. These pixels are computed by averaging their neighbor pixels within the same region, which means the same side o f the edge. At most three of the eight neighbor pixels of the considered pixel are averaged depending on the position of the neighbor pixels relative to the edge. The pixels that are averaged are the farthest pixels from the edge. Figure 4.35 shows examples of filling near edge pixels. Near edge pixel to be calculated Figure 4.35 Examples of filling near edge pixels. Gray pixels lie in a homogenous region, Dark pixels lie on edge, White pixels lie near edge pixels. The closed shapes are the pixels to be averaged so as to calculate the pixel marked as question mark. - 101 4.8 Results The proposed method is tested with binary and gray-level images. The result in Table 2. is obtained by reducing the original image by factor 2 then expanding them by factor 2 using different methods. The images are reduced by eliminating every other row then eliminating every other column. The sum of absolute error between the original image and the expanded image is used to compare the performance of the replication, linear and cubic interpolation, with the performance of the proposed method. Table 2. can show that the proposed method outperforms the other method with the binary and gray-level images. Table 2 The Sum of the Absolute Error of four images enlarged using three methods and the proposed method Sum of the Absolute Error Image Replication Linear Interpolation Cubic Interpolation Proposed Method Binary A B C 964 903 1006 572 Rabab 931 879 972 545 Multi Gray Levels Tropic 207742 123775 115402 71139 Saad 295097 153533 140711 93811 In terns of complexity, the number of operations required by our binary proposed method is 30% more than that of the replication method. The types of operations here are additions, subtraction, and assigning. Our gray-level proposed method depends on edge detection (Canny). Here the edge detection consumes around 90% of the total operations - 102 complexity. The other 10% of the computations are consumed by edge coding, edge classifying, edge expansion, and homogenous regions filling. These require around 25% of the number of operations required by the cubic interpolation method. - 103 5 Conclusions and Future Suggestions 5.0 Overview Image expansion is an essential tool for many applications, such as digital photography, satellite imagery, biomedical image processing, and Internet browsing. The expansion process introduces many new pixels to be filled. For example, expanding the image two times produces three new pixels for each original pixel. To f i l l these new pixels there are: 1) the conventional methods; 2) the adaptive methods, 3) the statistical methods, and 4) the methods that use new concepts such as wavelet and neural networks. Our proposed method lies in the second category, i.e. the adaptive methods category. The conventional methods expand the whole image using the same process for every pixel. Some give results that are better than others, but all suffer from one or more of the following effects: blockiness, blurring (over smoothing), contouring, ringing, or - 104 oscillation effects. This is because these types of methods are not optimal, as generally they are not designed to minimize a certain function of error or artifacts. They also lack to consider the local characteristics of the image. The adaptive methods produce better results than the conventional methods as they consider the local characteristics of the image. Generally, the statistical methods are very computationally demanding and expensive as they compute the local characteristics of the image. 5.1 Conclusions The proposed method preserves the quality of the expanded image and does not distort edges and corners where most of the information resides. The proposed method adaptively expands the image as it expands the edges in different scheme from the homogenous regions. The expanded edges using the proposed method are better in quality and visually look more natural and near exact. The proposed method is tested with many images: binary and gray-level images. The Sum of Absolute Error (SAE) technique is used to measure the performance of the proposed method in terms of quality. The proposed method outperforms other methods in term of quality as was shown in Table 2. - 105 5.2 Suggestions for Future Work The following are few suggestions for continuing this research. • Edge Detection is the first step of the proposed method and it is used to classify the image pixels as an edge pixel or not. This is a critical decision as the following steps depend on this decision. The Canny edge detector yields very good results but it is computationally demanding. For further study, other edge detection methods can be tested or developed. • Edge coding is an important process on which the quality depends. The proposed method uses relatively simple edge coding technique to create an edge chain code. Using more complicated and more accurate edge coding technique is one of the suggestions for future study. There are many techniques for edge coding that can be used to improve the quality of the expanded edges [83, 84, 85]. • In this thesis project, edges are considered to be one of two cases: 1) short post-CCC segment i.e. the segment after the change in the chain code is short, 2) long post-CCC segment i.e. the segment after the change in the chain code is long. We have another classification that consists of 16 cases instead of two and it produces better results but it is not complete. The more the cases the better the expanded edges the better the quality. That means future study could be done on better classification for the edge. • Another suggestion for future study is the expansion process of the homogenous regions. The expansion process of the pixels inside the homogenous regions can be done based on a statistical information or the texture information of that region. - 106 Bibliography [1] R. Schafer; L . Rabiner, " A Digital Signal Processing Approach to Interpolation", Proc. of I E E E Conference 1973, Volume 61, pp. 692-702. [2] S. Rifman, "Digital Rectification of E R T S Multispectral Imagery", Proc. o f , 1973, V o l . l , p p . 1131-1142. [3] R. Bernstein, "Digital Image Processing of Earth Observation Sensor Data", I B M J. Res. Dev., 1976, 20, pp.40-57. [4] J. Parker; R. Kenyon; D . Troxel, "Comparison of Interpolation methods for Image Resampling", I E E E Trans, on Medical Imaging, 1983, 2, (1), pp. 31-39. [5] H . C . Hsieh; W.T . Chang, "Image interpolation by Analogue Circuit", Electronics Letters, V o l . 28, No. 9, A p r i l 1992, pp. 867-868. [6] J. Markel , " F F T pruning", I E E E Trans, on Audio Electroacoust, 1971, 19, pp. 305-311. [7] T. Smit; M . Smith; S. Nichols, "Efficient Sine Function Interpolation Technique for Center Padded Data", I E E E Trans, on Acoustic Speech Signal Processing, 1990, 38, (9), pp. 1512-1517. - 107 [8] J. Ratzel, "The Discrete Representation of spatially Continuous Images", Ph.D. Dissertation, Massachusetts Institute of Technology, Cambridge, 1980. [9] P. Sankar, and L . Ferrari, "Simple Algorithms and Architecture for B-spline Interpolation", I E E E Trans, on Pattern Analysis and Machine Intelligence, 1988, 10, (2), pp. 271-276. [10] S. Gustafson; T. Rhoadarmer; J. Loomis; G . Little, "Smart Zooming", Proc. on SPIE-Int. Soc. Opt. Eng., 1994, 2238, pp. 170-175. [11] H . Hou; H . Andrews, "Cubic splines for Image Interpolation and Digital Filtering", I E E E Trans, on Acoustic and Speech Signal Processing, 1978, 26, (6), pp. 508-517. [12] C. Lee; M . Eden; M . Unser, "Near Optimal Geometric Image Scaling Using Oblique Projection Operators", Proc. of I E E E Acoustic, Speech, and Signal Processing Conference, Atlanta, G A , U S A , 7-10 May, 1996. [13] J. Taber, "Evaluation of Digitally Corrected E R T S Images", Proc. of Third Earth Resources Technology Satellite-1, 1973, V o l . 1, pp. 1838-1843. [14] R. Keys, "Cubic Convolution Interpolation for Digital ImageProcessing", I E E E Trans, on Acoustic, Speech and Signal Processing, 1981, 29, (6), pp.1153-1160. [15] M . Unser, A . Aldroubi, M . Eden, "Enlargement or Reduction of Digital Images With Min imum Loss of Information", I E E E Trans, on Image Processing, V o l . 4, No. 3, March v 1995, pp. 247-258. [16] M . Unser, "Splines a Perfect Fit for Signal and Image Processing", I E E E Trans, on Signal Processing, V o l . 16, No. 6, November 1999, pp. 22-38. - 108 [17] V . Algaz i ; G . Ford; R. Potharlanka, "Directional Interpolation of Images Based on Visual Properties and Rank Order Filtering", Proc. of International Conference on Acoustic, Speech and Signal Processing, I C A S S P ' 9 1 , Toronto, Canada, 1991, V o l . M12.25. [18] F . G . B . De Natale, G.S. Desoli, D . D . Giusto, and G . Vernazza, " A Spline-Like Scheme for Least-Square Bilinear Interpolation of Images", Proc. of I E E E Acoustic, Speech, and Signal Processing Conference, New York, N Y , U S A , A p r i l 27-30, 1993 [19] L A . Ferrari; J .H. Park, " A n Efficient Spline Basis for Multi-Dimensional Applications: Image interpolation", Proc. of I E E E International Symposium on Circuits and Systems, Honk Kong, June 9-12, 1997. [20] T. Chen; R. De Figueiredo, "Two-Dimensional Interpolation by Generalized Spline Filters Based on Partial Differential Equation Image Models", I E E E Trans, on Acoustic, Speech and Signal Processing, 1985, 33, (3), pp. 631-642. [21] G . Chen; R J . P . de Figueiredo, " A Unified Approach to Optimal Image Interpolation Problems Based on Linear Partial Differential Equation Models", I E E E Trans, on Image Processing, V o l . 2, No . 1, Jan. 1993, pp. 41-49. [22] T. Ramstad; Y . Wang, "Efficient Image Interpolation Scheme Using Hybrid ITR Nyquist Filters", Optical Eng., 1992, 31, (6), pp. 1277-1283. [23] R. Constable; I. Kay; M . Smith; R. Henkelman, "High Quality Zoomed M R Images, Using Discrete Fourier Transform Interpolation", J. Comput. Assist. Tomogr., 1989, 13, (1), pp. 179-181. - 109 [24] P J . S . G . Ferreira, "The Duality of Two Recent Image Interpolation Methods", Proc. of I E E E International Conference on Image Processing, Lausanne, Switzerland, A p r i l 16-19,1996. [25] H . Chen; G . E . Ford, " A n FIR Image Interpolation Filter Design Method Based on Properties of Human Vis ion" , Proc. of 1 s t International Conference on Image Processing, Austin, T X , U S A , Nov. 13-16, 1994. [26] T. Yamada, R. Ishii, " A n Algorithm to Magnify Images", Proc. of I E E E International Conference on industrial Technology, ICIT '96, Shanghai, China, Dec. 2-6, 1996. [27] J.P. Oakley, " A New Method for Image Interpolation and its Applications in Image Analysis", Proc. of Third International Conference on Image Processing and its Applications, Warwick, U K , 1989. [28] David Ki rk , "Graphics Gems III", Academic Press Professional Inc., 1992. [29] A . M . Darwish, M . S . Bedair, S.I. Shaheen, "Adaptive Resampling Algorithm for Image Zooming", Proc. of IEE Vision, Image and Signal Processing, Aug . 1997. [30] Y . Wang; S. Mitra , "Edge Preserved Image Zooming", Proc. o f European Signal Processing, E U R A S I P - 8 8 , Grenoble, France, 1988, pp. 1445-1448. [31] S. Thurnhofer; M . Lightstone; S. Mitra, "Adaptive Interpolation of Images With Application to Interlaced-to-Progressive Conversion", Proc. of SPIE-Int. Soc. Opt. Eng., 1991, 1460, pp.614-625. - 110 [32] S.W. Lee; J .K. Paik, "Image Interpolation Using Adaptive Fast B-Spline Filtering", Proc. of I E E E International Conference on Acoustics, Speech, and Signal Processing, Minneapolis, M N , U S A , Apr i l 27-30, 1993. [33] K . Jensen; D . Anastassiou, "Spatial Resolution Enhancement of Images Using Nonlinear Interpolation", Proc. of International Conference on Acoustic, Speech, and Signal Processing, I C A S S P ' 9 0 , Albuquerque, N M , 1990,pp. 2045-2048. [34]K. Jensen; D . Anastassiou, "Subpixel Edge Localization and Interpolation of Stil l Images", I E E E Trans, on Image Processing, 1995, 4, (3), pp. 285-295. [35] N . Herofotou, A . N . Venetsanopoulos, "Colour Image Interpolation for High Resolution Acquisition and Display Devices", I E E E Trans, on Consumer Electronics, V o l . 41, No . 4, Nov. 1995, pp. 1118-1126. [36] B . Zeng; A . N . Venetsanopoulos, "Comparative Study of Several Nonlinear Image Interpolation Schemes", Proc. of SPIE, V o l . 1818, 1992, pp. 21-29. [37] A . Lehtonen; M . Renfors, "Nonlinear Quineunx Interpolation Filtering", Proc. of SPIE, V o l . 1360, 1990, pp. 135-142. [38] S.D. Bayrakeri; R . M . Mersereau, " A New Method For Directional Image Interpolation", Proc. of I E E E International Conference on Acoustics, speech, and Signal Processing, Detroit, M I , U S A , M a y 9-12,1995. [39] S. Carrato; G . Ramponi; S. Marsi , " A Simple Edge-Sensitive Image Interpolation Filter", Proc. o f I E E E International Conference on Image Processing", Lausanne, Switzerland, Sept. 16-19, 1996. - Ill [40] W . Bender; C. Rosenberg, "Image Enhancement Using Non-Linear Sampling", Proc. of SPIE-Int. Soc. Opt. Eng., 1991, pp. 59-70. [41] S. Thurnhofer; S. Mitra, "Edge-Ehanced Image Zooming", Optical Eng., 1996, 35, (7), pp. 1862-1869. [42] G . H . Atwood, W . A . Davis, "Image Expansion Using Interpolation and Heuristic Edge Following", Proc. of I E E E International Conference on Image Processing and its Applications, Warwick, U K , 1989. [43] P .W. Wong; J.P. Allebach, "Convergence of an Iterative Edge Directed Image Interpolation Algorithm", Proc. of I E E E International Symposium on Circuits and Systems, Honk Kong, June 9-12, 1997. [44] K . Xue; A . Winans; E . Walowit, " A n Edge-Restricted Spatial Interpolation Algorithm", J. Electron. Imaging, 1992, 12, pp. 152-161. [45] D . Geiger, J.E. Kogler, "Scaling Images and Image Features V i a the Renormalization Group", Proc. of I E E E Computer Vis ion and Pattern Recognition, New York, N Y , U S A , June 15-17, 1993. [46] R .R . Schultz, R . L . Stevenson, " A Bayesian Approach to Image Expansion for Improved Definition", I E E E Trans, on Image Processing, V o l . 3, No . 3, May , 1994, pp. 233-242. [47] N . Herodotou; A . N . Venetsanopoulos; L . Onural, "Image Interpolation Using a Simple Gibbs Random Field Model" , Proc. of I E E E International Conference on Image Processing, Washington, D C , U S A , 23-26 Oct. 1995. - 112 [48] R .R . Schultz, R . L . Stevenson, "Improved Definition Image Expansion", Proc. of I E E E Acoustic, Speech, and Signal Processing Conference, San Francisco, C A , U S A , March, 23-26, 1992. [49] T. Sikora, P.Richardson, "Image Interpolation Based on Image Statistics: a Case Study", Proc. of I E E E Region 10 International Conference, T E N C O N '92, Melbourne, V i c , Australia, Nov. 11-13, 1992. [50] S.A. Martucci, "Image Resizing in the Discrete Cosine Transform Domain", Proc. of International Conference on Image Processing, Washington, D C , U S A , Oct. 23-26, 1995. [51] N . Merhav, V . Bhaskaran, " A Transform Domain Approach to Spatial Domain Image Scaling", Proc. of I E E E Acoustic, Speech, and Signal Processing Conference, Atlanta, G A , U S A , M a y 7-10, 1996. [52] K . P . Hong; J .K. Paik; H J . K i m ; C . H . Lee, " A n Edge-Preserving Image Interpolation System for a Digital Camcorder", I E E E Trans, on Consumer Electronics, V o l . 42, No. 3, Aug. 1996, pp. 279-284. [53] K . P . Hong; J .H. Paik; H.J . K i m ; C . H . Lee, " A n Edge-Preserving Image Interpolation System for a Digital Camcorder", Proc. of I E E E International Conference on Consumer Electronics, Rosemont, IL, U S A , June 5-7, 1996. [54] F. Ahmed; S.C. Gustafson; M . A . Kar im, "High-Fidelity Image Interpolation Using Radial Basis Function Neural Networks", Proc. of I E E E National conference on National Aerospace Electronics, Dayton, O H , U S A , M a y 22-26, 1995. - 113 [55] T. Sigitani, Y . Iiguni, H . Maeda, "Image Interpolation for Progressive Transmission by Using Radial Basis Function Network", I E E E Trans, on Neural Networks, V o l . 10, No. 2, Marsh 1999, pp. 381-390. [56] E . Gelenbe, H . Bakircioglu, T. Kocak, "Iamge Processing with the Random Neural Network (RNN)" , Proc. of 13 t h International Conference on Digital Signal Processing, July 2-4, 1997. [57] S.G. Chang, Z . Cvetkovic, M . Vetterli, "Resolution Enhancement of Images Using Wavelet Transform Extrema Extrapolation", Proc. of I E E E International Conference on Acoustics, Speech, and Signal Processing, ICASSP-95 , New York, N Y , U S A , M a y 9-12, 1995. [58] W . K . Carey; D . B . Chuang; S.S, Hemami, " Regularity-Preserving Image Interpolation", Proc. of International Conference on Image Processing, Oct. 26-29, 1997. [59] A . Youssef, "Analysis and Comparison of Various Image Downsampling and Upsampling Methods", Proc. of I E E E Conference on Data Compression, Snowbird, U T , U S A , March 30-Apri l 1, 1998. [60] Kreyszic, "Advanced Engineering Mathematics", sixth edition, John Wiley & Sons, 1988. [61] M . Abramowitz; L A . Stegun, "Handbook of Mathematical Functions", Dover Edition, General Puplishing Company, Ltd, Toronto, Ontario, Canada, 1965 [62] Alen W . Paeth, "Graphics Gems V " , Academic Press Professional Inc., 1995. [63] Foley; V a n Dam; Feiner; Hughes; Phillips, "Introduction to Computer Graphics", Addison-Wesley Publishing Company, Inc., 1994. - 114 [64] F.S H i l l Jr., "Computer Graphics", Macmil lan Publishing Company, 1990. [65] R . C . Gonzalez; P. Wintz, "Digital Image Processing", Addison-Wesley, 1987. [66] J. Canny, " A Computational Approach to Edge Detection", I E E E Trans, on Pattern Anal , and Mach. Intelligence, vol . 8, pp 679-698, 1986. [67] D . Marr; H . Hildreth (1980), "Theory of Edge Detection", Proc. Roy. Sco. London, B207, 187-217. [68] S. L ig in ; S. Dinaggang; Q. Feih, "Edge Detection on Real Time Using L o G Filter", I E E E Proc. of International Symposium on Speech, Image Processing, and Neural Network, Shanghai, China, 13-16 A p r i l , 1994. [69] A . A . Masoud; M . M . Bayoumi, "Using local structure for the reliable removal of noise from the output of the L o G edge detector", I E E E Trans. Systems, M a n and Cybernetics, V o l . 25, No. 2, Feb 1995, pp. 328-337. [70] L . Ganesan; P. Bhattaharyya, "Edge Detection in Untextured and Textured Images -a Common Computational Framework", I E E E Trans, on Systems, M a n and Cybernetics, Part B , vol . 27, pp 823-834, 1997. [71] N . Okamoto; W . Chen; N . Iida; T. Minami , "Automatic extraction of contour lines and feature points from profile images", Proc. of I E E E Canadian Conference on Electrical and Computer Engineering, M a y 25-28, 1997. [72] Y . Haifeng, H . Makela, " A new edge extraction method for vehicle navigation", Proc. of I C A R Fifth International Conference on Advanced Robotics, June 19-22, 1991. - 115 [73] F. Mokhtarain, R. Suomela "Curvature scale space for robust image corner detection", Proc. of 14 t h International Conference on Pattern Recognition, A u g 16-20, 1998. [74] L . B i n , A . D . J. Cross, E . R. Hancock, "Corner detection using vector potential", Proc. of 14 t h International Conference on Pattern Recognition, A u g 16-20, 1998. [75] F. Mokhtarian, and R. Suomela, "Robust Image Corner Detection Through Curvature Scale Space", I E E E Trans, on Pattern Analysis and Machine Intelligence, vol . 20, pp 1376-1381, 1998. [76] P .E. Trahanias, A . N . Venetsanopoulos, "Color Edge Dtection Using Vector Order Statistics", I E E E Trans. Image Processing, V o l . 2, No . 2, A p r i l 1993, pp. 259-264. [77] P. S. W u , L . M i n g , "Fast edge detection for color image", Proc. of 3 r d International Conference on Signal Processing, Oct 14-18, 1996. [78] G . C. Gurski, M . T. Orchard, "On the use of orientation information for improved contour difference coding", Proc. of I E E E Symposium on Circuits and Systems, M a y 3 -6, 1993. [79] J. Yuan, C . Y . Suen, " A n Optimal Algorithm for Detecting Straight Lines in Chain Code", I A P R international Conference on Pattern Recognition. Montreal, Que, C A N A D A , 30 Aug . - 3 Sept., 1992. [80] A . K . Murad Agha; R . K . Ward; S. Zahir, "Image Expansion Using Segmentation-Based Method", Proc. of I E E E Pacific R i m Conference on Communications, Computers and Signal Processing, P A C R L M 1999, Victoria, Canada, August 22-24, 1999. - 116 [81] A . K . Murad Agha; R . K . Ward; S. Zahir, " A Near Exact Image Expansion Scheme for Bi -Leve l Images", Proc. of International Conference on Image Processing, ICIP'2000, Vancouver, Canada, September 10-13, 2000. [82] J. Koplowitz, and V . Greco, "On the Edge Location Error for Local Maximum and Zero-Crossing Edge Detector", I E E E Trans, on Pattern Analysis and Machine Intelligence, vol . 16, pp 1207-1212, 1994. [83] H. L i , B .S . Manjunath, S.K. Mitra, "Contour - Based Multisensor Image Registration", I E E E Proc. of the Twenty Sixth Asilomar Conference on Signals, Systems, and Computers. Santa Barbara, C A , U S A , 26-28 Oct.. 1992. [84] M . Gokmen, C. C. L i , "Edge detection and surface reconstruction using refined regularization", I E E E Trans. Pattern Analysis and Machine Intelligence, V o l . 15, No. 5, M a y 1993, pp. 492^199. [85] D . E . Tamir, K . Phillips, A . Abdul-Karim, "Efficient chain-code encoding for segmentation-based image compression", Proc. of D C C Conference on Data Compression, Marsh 3 1 - A p r i l 3, 1996. [86] " A Study Guide for Digital Image Processing", Mark J.T. Smith, Alen Doecf, Scientific Publishers, 1997 [87] "Digital Image Processing Techniques", Michael P. ekstrom, Academic Press, 1984. [88] "Fundamentals of Digital Image Processing", A n i l K . Jain, Prentice Hal l , 1989. [89] "Numerical Recipes Example Book (C)", W.T. Vetterling; S.A. Teukolsky; W . H . Press; B .P . Flannery, Cambridge University Press, 1988. - 117
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Image expansion using segmentation-based method
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Image expansion using segmentation-based method Murad Agha, Abdul Karim 2000
pdf
Page Metadata
Item Metadata
Title | Image expansion using segmentation-based method |
Creator |
Murad Agha, Abdul Karim |
Date Issued | 2000 |
Description | Image enlargement is a vital process for printing images on large format printers. Image expansion introduces many new pixels to the original image. Proper values for these new pixels should be found otherwise distortion and significant degradation in the quality of the image will result. Several methods have been employed to minimize such distortion. The most popular of these methods are the pixel replication and the linear interpolation methods. This is because these methods are not computationally demanding. In this work, we develop a new image expansion method that preserves the quality of the edges in the expanded image, where other methods fail. First, the edges in the original image are extracted. For binary images we use Laplacian operator and for gray-level images we use Canny edge detector. We propose a new algorithm, which replicates the edge shape so that the edges in the expanded image do not appear zigzagged. Our algorithm expands the edges while it preserves the edge information such as the shape and the continuity of the edge. The edge-shape-replication algorithm simply, classifies the edges into two classes: short post-CCC and long post-CCC edges, each is expanded differently. Most of the original pixels keep their values after the expansion. However, the remaining pixels' values are calculated using one of three proposed techniques based on the location of the pixel whose value is to be calculated. The three locations of these pixels are pixels that lie on an edge, pixels that are adjacent to edges, and the remaining pixels areas. To compare performance of our proposed method with others, we reduced the test images to their quarter size then expanded them to their original sizes. The sum of absolute errors (SAD's) between the original image and the expanded images are calculated. Our proposed method is shown to outperform the replication, linear and cubic interpolation methods. |
Extent | 13024436 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-07-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065043 |
URI | http://hdl.handle.net/2429/11414 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2001-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2001-0082.pdf [ 12.42MB ]
- Metadata
- JSON: 831-1.0065043.json
- JSON-LD: 831-1.0065043-ld.json
- RDF/XML (Pretty): 831-1.0065043-rdf.xml
- RDF/JSON: 831-1.0065043-rdf.json
- Turtle: 831-1.0065043-turtle.txt
- N-Triples: 831-1.0065043-rdf-ntriples.txt
- Original Record: 831-1.0065043-source.json
- Full Text
- 831-1.0065043-fulltext.txt
- Citation
- 831-1.0065043.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065043/manifest