Image Processing Lecture Notes PDF

Image processing Lecture Dr. Hazin G. Daway Dr. Doaa Ali Taban CHAPTER SIX: Image Analysis IMAGE ANALYSIS 6.1 Image Analysis Image analysis involves manipulating the image data to determine exactly the informat...

Image processing Lecture Dr. Hazin G. Daway Dr. Doaa Ali Taban CHAPTER SIX: Image Analysis IMAGE ANALYSIS 6.1 Image Analysis Image analysis involves manipulating the image data to determine exactly the information necessary to help solve a computer imaging problem. The image analysis process can be broken down into three primary stages: 1. Preprocessing: a stage where the requirements are typically obvious and simple, such as removal of artifacts from images or eliminating of image information that is not required for the application. For example, in one application we needed to eliminate borders from the images that have been digitized from film. 2. Data Reduction Involves either reducing the data in the spatial domain or transforming it into another domain called the frequency domain, and then extraction features for the analysis process. 3. Features Analysis The features extracted by the data reduction process are examine and evaluated for their use in the application. 6.2 Basic Relationships Between Pixels 1. Neighbors of a Pixels A pixel 𝑝 at coordinates (𝑥, 𝑦) has the following neighbors: 4-neighbors § four horizontal and vertical neighbors whose coordinates are (𝑥 + 1, 𝑦), (𝑥 − 1, 𝑦), (𝑥, 𝑦 + 1), (𝑥, 𝑦 − 1) § denoted by 𝑁! (𝑝). 1  diagonal neighbors (𝑥 + 𝑙, 𝑦 + 𝑙), (𝑥 + 𝑙 , 𝑦 − 𝑙), (𝑥 − 𝑙, 𝑦 + 𝑙), (𝑥 − 𝑙, 𝑦 − 1) § denoted by 𝑁" (𝑝). 8-neighbors § both 4-neighbors and diagonal neighbors § denoted by 𝑁# (𝑝). Note: some of the neighbors of 𝑝 lie outside the digital image if (𝑥, 𝑦) is on the border of the image. 4-neighbors diagonal neighbors 8-neighbors Figure (1) Neighbors of a Pixels. 2. Distance Measure For pixels 𝑝, 𝑞, and 𝑧, with coordinates (𝑥, 𝑦), (𝑠, 𝑡), and (𝑣, 𝑤), respectively, 𝐷 is a distance function or metric if a) 𝐷 (𝑝, 𝑞) ≥ 0 (𝐷 (𝑝, 𝑞) = 0 𝑖𝑓 𝑝 = 𝑞)), b) 𝐷 (𝑝, 𝑞) = 𝐷 (𝑞, 𝑝), and c) 𝐷 (𝑝, 𝑧) ≤ 𝐷 (𝑝, 𝑞) + 𝐷 (𝑞, 𝑧). Euclidean distance between 𝑝 and 𝑞 is defined as: 𝐷 (𝑝, 𝑞) = ;(𝑥 − 𝑠)$ + (𝑦 − 𝑡)$ …….(1) 2  City-block distance between 𝑝 and 𝑞 is defined as: 𝐷(𝑝, 𝑞 ) = |𝑥 − 𝑠| + |𝑦 − 𝑡|……………..….(2) Chessboard distance between 𝑝 and 𝑞 is defined as: 𝐷 (𝑝, 𝑞 ) = 𝑚𝑎𝑥(|𝑥 − 𝑠|, |𝑦 − 𝑡|)…(3) 6.3 Zooming and Shrinking Digital Image A) Zooming Zooming may be viewed as over-sampling. It is the scaling of an image area A of w×h pixels by a factor s while maintain the spatial resolution (i.e. output has sw×sh pixels). Zooming requires two steps: Creation of new pixel locations. Assignment of gray levels to those new locations. There are many methods of gray-level assignments, for example nearest neighbor interpolation and bilinear interpolation. 1. Nearest neighbor interpolation (zero-order hold) It is performed by repeating previous pixel values, thus creating a checkerboard effect, as in the Figure (2). Figure (2) Zero-Order Hold Method. Pixel replication (a special case of nearest neighbor interpolation) is used to increase the size of an image an integer number of times. The example below shows 8-bit image zooming by 2x (2 times) using nearest neighbor interpolation. 3  2. Bilinear interpolation (First -order hold) It is performed by finding linear interpolation between adjacent pixels, thus creating a blurring effect. This can be done by finding the average gray value between two pixels and use that as the pixel value between those two. We can do this for the rows first, and then we take that result and expand the columns in the same way. The example below shows 8-bit image zooming by 2 x (2 times) using bilinear interpolation: The first two pixels in the first row are averaged (8 + 4) / 2 = 6, and this number is inserted between those two pixels. This is done for every pixel pair in each row. 4  This method allows us to enlarge an M×N sized image to a size of (2M-1) × (2N-1) (or zoomed image has size (2M-1 × 2N-1) and be repeated as desired. We can use techniques such as padding which means adding new columns and/or rows to the original image in order to perform bilinear interpolation to get zoomed image of size (2M × 2N). Figure (3) shows image zooming using nearest neighbor interpolation and bilinear interpolation. We can clearly see the checkerboard and blurring effects. However, the improvements using bilinear interpolation in overall appearance are clear, especially in the 128×128 and 64×64 cases. The bilinear interpolated images are smoother than those resulted from nearest neighbor interpolation. Fig. (3) Top row: Images zoomed from 128×128, 64×64, and 32×32 pixels to 1024×1024 pixels using nearest neighbor interpolation in top row and bilinear interpolation in bottom row. B) Shrinking Image shrinking is accomplished by taking groups of pixels that are spatially adjacent and mapping them to one pixel. Shrinking may be viewed as under 5 sampling. Image shrinking is performed by row-column deletion. For example, to shrink an image by one-half, every other row and column are deleted. 6.4 Convolution Convolution is a widely used mathematical operator that processes an image by computing—for each pixel—a weighted sum of the values of that pixel and its neighbors (Figure 4). Depending on the choice of weights, a wide variety of image processing operations can be implemented. Convolution and correlation are the two fundamental mathematical operations involved in linear neighborhood-oriented image processing algorithms. Figure (4) Neighborhood processing for the case of linear filtering. 6.4.1 Convolution in the One-Dimensional Domain The convolution between two discrete one-dimensional (1D) arrays A(x) and B(x), denoted by A ∗ B, is mathematically described by the equation 6  EXAMPLE 1 In this example, we show how the result of a 1D convolution operation can be obtained step-by-step. Let A = {0, 1, 2, 3, 2, 1, 0} and B = {1, 3,−1}. The partial results of multiplying elements in A with corresponding elements in B, as B shifts from −∞ to ∞, are displayed below. 1. Initially, we mirror array B and align its center (reference) value with the first (leftmost) value of array A. 2 The partial result of the convolution calculation (0 × (−1)) + (0 × 3) + (1 × 1)= 1 (where empty spots are assumed as zero) is stored in the resulting array (A ∗ B). 2. Array B is shifted one position to the right. The partial result of the convolution calculation (0 × (−1)) + (1 × 3) + (2 × 1)= 5 is stored in the resulting array (A ∗ B) 3. Array B is shifted another position to the right. The partial result of the convolution calculation (1 × (−1)) + (2 × 3) + (3 × 1)= 8 is stored in the resulting array (A ∗ B). 4. Array B is shifted another position to the right. The partial result of the convolution calculation (2 × (−1)) + (3 × 3) + (2 × 1)= 9 is stored in the resulting array (A ∗ B). 7 5. Array B is shifted another position to the right. The partial result of the convolution calculation (3 × (−1)) + (2 × 3) + (1 × 1)= 4 is stored in the resulting array (A ∗ B). 6. Array B is shifted another position to the right. The partial result of the convolution calculation (2 × (−1)) + (1 × 3) + (0 × 1)= 1 is stored in the resulting array (A ∗ B). 7. Array B is shifted another position to the right. The partial result of the convolution calculation (1 × (−1)) + (0 × 3) + (0 × 1)= −1 is stored in the resulting array (A ∗ B). The final result of the convolution operation is the array {1, 5, 8, 8, 4, 1, −1}. 6.2.1 Convolution in the Two-Dimensional Domain The mathematical definition for 2D convolution is: where m2 is equal to half of the mask’s width and n2 is equal to half of the mask’s height, that is, m2 = ⌊m/2⌋ and n2 = ⌊n/2⌋ 8 where ⌊x⌋ is the floor operator, which rounds a number to the nearest integer less than or equal to x. The basic mechanism used to understand 1D convolution can be expanded to the 2D domain. In such cases, the 2D array A is usually the input image and B is a small (usually 3×3) mask. The idea of mirroring B and shifting it across A can be adapted to the 2D case as well: mirroring will now take place in both x and y dimensions, and shifting will be done starting from the top left point in the image, moving along each line, until the bottom right pixel in A has been processed. When the end of the row is reached, the mask is moved down one row, and the process is repeated row by row. This procedure has been performed on the entire image, the process of sliding, multiplying and summing is called convolution. EXAMPLE 2 9 6.5 Image Histogram The histogram of an image is a plot of the gray levels values versus the number of pixels at that value in the range [0, L-1] is a discrete function of the form: 𝐻 (𝑟% ) = 𝑛% …………………………...(9) Where 𝑟% is the kth gray level, and nk is the number of pixels in the image having the level 𝑟%. A normalized histogram is given by the equation: 𝑃 (𝑟% ) = 𝑛% ⁄𝑛 for k = 0,1,2, ….. , L − 1 …(10) P(𝑟% ) gives the estimate of the probability of occurrence of gray level 𝑟%. The sum of all components of a normalized histogram is equal to 1. The histogram plots are simple plots of (H(𝑟% ) = 𝑛% versus 𝑟% ). The next Figure. Show an image and its histogram. 10  Figure (4) Image Histogram. This appears as a graph with "brightness" on the horizontal axis from (0) to (255) for an 8-bit (intensity scale) and number of pixels on the vertical axis. the shape of histogram provide us with information about nature of the image or sub image if we considering an object within the image. For example: In the dark image the components of the histogram are concentrated on the low (dark) side of the gray scale. In case of bright image the histogram components are biased towards the high side of the gray scale. The histogram of a low contrast image will be narrow and will be centered towards the middle of the gray scale. The components of the histogram in the high contrast image cover a broad range of the gray scale. 11 Figure (5) different type of image histogram. 12  Tutorial Problem 1. without using program find the convolution of two vectors u=[1 0 1] , v=[2 7]. Using the cases: valid, same, and full, Solution: In the valid case F= u*v=[1 0 1]*[ 2 7 ] 1 0 1 2 7 F1= 2 1 0 1 2 7 F2 = 7 u*v=[ 2 7], for same case with zero padding F= u*v=[0 1 0 1 ]*[ 2 7 ] 0 1 0 1 2 7 F1=7 0 1 0 1 2 7 F2=2 0 1 0 1 2 7 F3=7 u*v=[ 7 2 7 ], for full case with zero padding u=[1 0 1] 13  up=x2 +(0)x+1= x2+1 v=[2 7] vp=2x+7 up*vp=2X3+7X2+2X+1 u*v=[2 7 2 7] Problem 2. by using MATLAB program find the convolution of two vectors u=[1 0 1] , v=[2 7] Solution: Using the cases valid , same , and full, clear all clc close all u = [1 0 1]; v = [2 7]; y1=conv(u,v,'valid') y2=conv(u,v,'same') y3=conv(u,v,'full') y4=conv(u,v) Problem 3. without using program find the convolution of two matrices A= 20 10 200 0 10 120 30 200 30 10 200 10 100 0 30 0 B= 1 1 1 1 1 1 1 1 1 Solution C(1,1)=20*1 +10*1+200*1 +10*1+120*1+30*1+30*1+10*1+200*1 14  =630 C(1,2)= 10*1+200*1+0*1+120*1+30*1+200 *1+ 10*1+200*1 +10*1 =780 C(2,1)= 10*1+120*1+30*1+30*1+10*1+200*1+100*1+0*1+30*1 =530 C(2,2)= 120*1+30*1+200*1+10*1+200*1+10*1+0*1+30*1+0*1 =600 c= 630 780 530 600 Problem 4. By using MATLAB program find the convolution of two matrix A= 20 10 200 0 10 120 30 200 30 10 200 10 100 0 30 0 B= 1 1 1 1 1 1 1 1 1 Solution clear all clc close all A=[20 10 200 0 ; 10 120 30 200;30 10 200 10 ; 100 0 30 0] B=[1 1 1 ;1 1 1; 1 1 1] C1=conv2(A,B,'valid') C2=conv2(A,B,same) Hint in the same A will be A=[0 0 0 0 0 0;0 20 10 200 0 0 ; 0 10 120 30 200 0 ;0 30 10 200 10 0 ; 0 100 0 30 0 0; 0 0 0 0 0 0 ] 15 Problem 5. Find the histogram for the clip data gray image manually 0 20 20 0 20 20 0 0 20 0 200 20 120 20 0 0 200 20 120 120 20 200 200 200 120 120 255 20 200 200 120 120 255 255 255 200 Solution Total size 36 P(0)=7/36=0.1944 P(20)=10/36=0.2778 P(120)=7/36=0.1944 P(200)=8/36=0.2222 P(255)=4/36=0.1111 Problem 6. Find the histogram for the gray image by using imhist commend Solution I = imread("mandi.tif"); [r c]=size(I); [y,x]=imhist(I); y=y./(r*c) plot(x,y) 16 17