1 00:00:01,850 --> 00:00:03,080 Hi and welcome to module 8.3, 2 00:00:03,080 --> 00:00:08,000 in which we will apply frequency analysis to digital imaging. 3 00:00:08,000 --> 00:00:12,680 We will first define DFT for two dimensional signals, and 4 00:00:12,680 --> 00:00:16,040 then we will look at the amount of information that we can extract 5 00:00:16,040 --> 00:00:19,250 from the magnitude and the phase of the DFT of an image. 6 00:00:19,250 --> 00:00:23,470 4D analysis of two dimensional signals can be developed exactly as we did for 7 00:00:23,470 --> 00:00:24,990 the one dimensional case. 8 00:00:24,990 --> 00:00:27,980 Says here we're concerned mostly with digital images. 9 00:00:27,980 --> 00:00:31,420 Namely finite support, two dimensional images, 10 00:00:31,420 --> 00:00:35,500 we will only review the definition of the two dimensional DFT. 11 00:00:35,500 --> 00:00:40,740 So let's consider a two dimensional finite support signal of support, 12 00:00:40,740 --> 00:00:43,760 big N one times big N two. 13 00:00:43,760 --> 00:00:48,760 The DFT is defined as the double sum for the first index that goes from zero to 14 00:00:48,760 --> 00:00:53,610 big N one minus one, and the second index that goes from zero to big N two 15 00:00:53,610 --> 00:00:59,060 minus one of the values of the dimensional signal over the support. 16 00:00:59,060 --> 00:01:04,234 Times the product of two complex exponentials 17 00:01:04,234 --> 00:01:09,672 whose frequencies are 2 pi over big N1 n1 k1, 18 00:01:09,672 --> 00:01:13,262 and 2 pi over big N2 n2 2 k2. 19 00:01:13,262 --> 00:01:17,930 The product of this two complex exponential represents a basis 20 00:01:17,930 --> 00:01:22,060 function for the space of images of size n1 times n2. 21 00:01:22,060 --> 00:01:27,130 The DFT can be easily inverted just like we did in the one dimensional case. 22 00:01:27,130 --> 00:01:31,280 We take basically complex exponentials with the sign reverse and 23 00:01:31,280 --> 00:01:35,650 we repeat the sum taken now the DFT coefficients into the sum. 24 00:01:35,650 --> 00:01:39,930 Normalisation is by convention applied to the inverse formula and 25 00:01:39,930 --> 00:01:45,180 in this case we have to divide the sum by the product of big N1 times big N2. 26 00:01:45,180 --> 00:01:49,990 It is certainly instructive to look in more detail at the basis functions for 27 00:01:49,990 --> 00:01:53,990 the space N1 times N2 images. 28 00:01:53,990 --> 00:01:58,310 These have the form that we have shown before in the DF sum, and we can 29 00:01:58,310 --> 00:02:02,540 easily prove, like in the one dimensional case, that they are orthogonal. 30 00:02:02,540 --> 00:02:09,920 There are n1 times n2 basis function for an image of that size, and so, 31 00:02:09,920 --> 00:02:15,330 it would be very hard to look at each one of them, even for images of moderate size. 32 00:02:15,330 --> 00:02:19,280 But we can try and plot some key representative basis functions to give you 33 00:02:19,280 --> 00:02:24,055 an idea of what the building blocks are for an image in space. 34 00:02:24,055 --> 00:02:28,780 We will show this basis functions by plotting the real part only as a grey 35 00:02:28,780 --> 00:02:33,555 scale image where the value of zero is indicated by a black and 36 00:02:33,555 --> 00:02:35,685 the value of one is indicated by white. 37 00:02:36,775 --> 00:02:42,265 So here we have the space of 256 by 256 pixel images. 38 00:02:42,265 --> 00:02:46,175 And this is one of the simplest basis functions that we can plot. 39 00:02:46,175 --> 00:02:48,865 We keep the vertical frequency as 0 and 40 00:02:48,865 --> 00:02:53,685 the horizontal frequency spans 1 period between 0 and 255. 41 00:02:53,685 --> 00:02:59,120 So if we were to look at this in a three dimensional space we could plot, 42 00:02:59,120 --> 00:03:03,820 this is the image plane and these are the values of the basis function. 43 00:03:03,820 --> 00:03:08,740 And this a wave, a solid wave that goes like this, right? 44 00:03:08,740 --> 00:03:11,820 So it goes down and and then it goes up again and 45 00:03:11,820 --> 00:03:14,690 here we have the white part and here we have the black part. 46 00:03:16,780 --> 00:03:21,060 We can invert the roles of the vertical and horizontal frequency and 47 00:03:21,060 --> 00:03:25,530 we get an image which is simply a noted degree of rotation of the previous one. 48 00:03:25,530 --> 00:03:31,400 We can increase the horizontal frequency at this point for K 1 equal to two we 49 00:03:31,400 --> 00:03:38,250 will have the basis function spans two periods over the support of the image. 50 00:03:40,350 --> 00:03:45,680 This will be 3 periods, and if we 51 00:03:45,680 --> 00:03:50,550 swap the roles of the frequency, we obtain again an image rotated by 90 degrees. 52 00:03:51,760 --> 00:03:54,530 We can increase the frequency the more and 53 00:03:54,530 --> 00:03:57,950 the density of these bands will increase correspondingly. 54 00:03:57,950 --> 00:03:59,450 Whenever the vertical frequency and 55 00:03:59,450 --> 00:04:04,570 horizontal frequency are the same, the bands will be angled at 45 degrees. 56 00:04:04,570 --> 00:04:06,418 And by varying the frequencies, 57 00:04:06,418 --> 00:04:09,784 we can obtain a wide range of different angles for the bands. 58 00:04:15,577 --> 00:04:20,473 The good news is that a 2D-DFT basis functions are separable, 59 00:04:20,473 --> 00:04:24,830 and so the DFT can be computed in a separable way. 60 00:04:24,830 --> 00:04:29,780 In particular, we first compute a one D-DFT along the columns. 61 00:04:30,810 --> 00:04:38,560 So if this is our image of size big n one time big n two, we first compute 62 00:04:39,890 --> 00:04:45,570 big n one D-DFT is of size and two along the columns. 63 00:04:45,570 --> 00:04:50,690 And once we're done with that, we compute 1 DDFTs along the rows. 64 00:04:50,690 --> 00:04:57,770 So, computationally, speaking, we first need to compute big n1, DFTs of size n2. 65 00:04:57,770 --> 00:04:59,840 We know that we can use the DFFD algorithm. 66 00:04:59,840 --> 00:05:05,810 So the cost will be N two log in base two of N two and 67 00:05:05,810 --> 00:05:12,540 then we need to compute N two FFTs of size N one. 68 00:05:12,540 --> 00:05:17,960 So there would be N one log in base two of N one which is much less than N one and 69 00:05:17,960 --> 00:05:19,530 N two squared. 70 00:05:19,530 --> 00:05:23,780 The cost of implementing a two dimensional DFT directly from the equation. 71 00:05:25,030 --> 00:05:28,250 We can also express the two D-DMT matrix form. 72 00:05:28,250 --> 00:05:31,400 For that we need to express first of all the signal, 73 00:05:31,400 --> 00:05:33,780 the two dimensional signal as a matrix. 74 00:05:33,780 --> 00:05:37,940 This is very straight forward because an n one times n two image 75 00:05:37,940 --> 00:05:41,010 is simply an n one times n two matrix. 76 00:05:41,010 --> 00:05:44,650 There is only the technicality that the Orientation 77 00:05:44,650 --> 00:05:48,280 of the rows is inverted with respect to the Cartesian notation. 78 00:05:48,280 --> 00:05:55,950 So for instance in the Cartesian plane, N2 would go from, say, 0 upwards. 79 00:05:55,950 --> 00:06:01,460 But if we express, and this is our image, but if we express this in matrix notation, 80 00:06:01,460 --> 00:06:04,740 this element of the matrix normally is 00. 81 00:06:04,740 --> 00:06:07,900 So, there's a flipping of the vertical axis. 82 00:06:07,900 --> 00:06:10,010 But this is just a technicality. 83 00:06:10,010 --> 00:06:15,480 You will also recall the N times N DFT matrix that we saw in module 4.2. 84 00:06:15,480 --> 00:06:20,010 This is a standard DFT matrix of size N, 85 00:06:20,010 --> 00:06:26,840 where W recall this simply e to the -j to phi over capitan N. 86 00:06:26,840 --> 00:06:31,875 With this notation implies, let's look at the DFT formula once again. 87 00:06:31,875 --> 00:06:39,130 The inter summation is simply the product of 88 00:06:39,130 --> 00:06:46,320 the DFT matrix of size big N2 times the signal matrix. 89 00:06:46,320 --> 00:06:50,130 We call this intermedia matrix capital V and 90 00:06:50,130 --> 00:06:55,330 Capital V belongs to the space of N2 times N1 matrices. 91 00:06:55,330 --> 00:07:00,460 Then the outer sum can be expressed, the right product of 92 00:07:00,460 --> 00:07:06,410 the matrix V which is defined, times a DFD matrix, of size capital N1. 93 00:07:06,410 --> 00:07:07,230 And so 94 00:07:07,230 --> 00:07:13,180 the resultant signal is a matrix that collects the DFT values for the image. 95 00:07:13,180 --> 00:07:16,940 In compact form we can express the two dimensional DFT 96 00:07:16,940 --> 00:07:19,950 as a product of a DFT matrix exercise and 97 00:07:19,950 --> 00:07:24,440 two times the image times the DFT matrix times the size and one. 98 00:07:25,630 --> 00:07:28,770 So now we know how to compute a two dimensional DFT. 99 00:07:28,770 --> 00:07:30,780 Well, can we look at one? 100 00:07:30,780 --> 00:07:33,990 We can try and plot the magnitude of the DFT. 101 00:07:33,990 --> 00:07:36,630 Since the DFT is a two dimensional signal and 102 00:07:36,630 --> 00:07:39,130 therefore can be interpreted as an image. 103 00:07:39,130 --> 00:07:44,980 But this wouldn't work because the dynamic range of the DFT is way too big for 104 00:07:44,980 --> 00:07:48,840 either a monitor screen or a piece of paper to represent. 105 00:07:48,840 --> 00:07:52,420 We wouldn't have grayscale level to show the details. 106 00:07:52,420 --> 00:07:56,500 So we could try to normalize the values by dividing the DFT magnitude 107 00:07:56,500 --> 00:07:58,570 by its maximum value. 108 00:07:58,570 --> 00:08:02,180 And yet, that wouldn't work either, because for images on average, 109 00:08:02,180 --> 00:08:05,270 the distribution of the the magnitude of the three coefficients 110 00:08:05,270 --> 00:08:06,790 follows a curve like this one. 111 00:08:08,000 --> 00:08:12,730 So what we have here is a few outliers here that really go above the average 112 00:08:12,730 --> 00:08:17,860 values of the coefficients, and some tail outliers here that drive the value down. 113 00:08:17,860 --> 00:08:21,190 What we're interested in is this band between the extreme. 114 00:08:22,240 --> 00:08:24,210 So we take a two step approach. 115 00:08:24,210 --> 00:08:29,181 First we remove the flagrant outliers, for instance the value of DFT in [0, 116 00:08:29,181 --> 00:08:31,990 0] is simply the sum of all pixel values. 117 00:08:31,990 --> 00:08:36,670 Now, for a grey scale images where all pixels are positive values between zero 118 00:08:36,670 --> 00:08:38,270 and one, say, 119 00:08:38,270 --> 00:08:43,980 this will be definitely a large value with respect to any other coefficient. 120 00:08:43,980 --> 00:08:48,240 And then, to remove the tail we use nonlinear mapping. 121 00:08:48,240 --> 00:08:52,630 For instance, we use a curve like x to the power of one-third after normalizing all 122 00:08:52,630 --> 00:08:54,024 values between 0 and 1. 123 00:08:54,024 --> 00:08:57,740 So for instance, if this is the range between 0 and 1, 124 00:08:57,740 --> 00:09:02,485 the nonlinearity will map this range like so, which means that the tail 125 00:09:02,485 --> 00:09:06,880 outliers that we've seen before will be squished in a band. 126 00:09:06,880 --> 00:09:10,490 That is very close to zero, and so they will appear as black pixels. 127 00:09:10,490 --> 00:09:13,560 And the rest of the values, those that we're interested in, 128 00:09:13,560 --> 00:09:16,310 will occupy the bulk of the dynamic range of the medium. 129 00:09:17,400 --> 00:09:20,670 If we do that, we obtain something like this. 130 00:09:20,670 --> 00:09:25,580 So our little dog has been transform in this, cryptic image here. 131 00:09:25,580 --> 00:09:30,290 Where if you look very closely we can identify for instance some lines here and 132 00:09:30,290 --> 00:09:35,090 here that correspond to clear lines in the image 133 00:09:35,090 --> 00:09:40,020 captured by some of the basic functions that have this orientations, but 134 00:09:40,020 --> 00:09:43,360 by and large it's very, very difficult to understand what's going on. 135 00:09:45,160 --> 00:09:48,998 We get a confirmation of our suspicion if we try to 136 00:09:48,998 --> 00:09:54,630 invert the free so we take an image, 137 00:09:54,630 --> 00:09:58,550 we take the Fourier transform, we discard the phase information, and 138 00:09:58,550 --> 00:10:02,270 then we do an inverse Fourier transform from the magnitude. 139 00:10:02,270 --> 00:10:05,890 What we get if we start with a dog picture is this picture here, 140 00:10:05,890 --> 00:10:09,830 where we are absolutely unable to guess the original picture. 141 00:10:09,830 --> 00:10:15,410 What is more interesting is that if we do the same thing but keep in just the phase. 142 00:10:15,410 --> 00:10:18,110 In other words, we throw away the magnitude, 143 00:10:18,110 --> 00:10:20,370 we set the magnitude uniformly at one. 144 00:10:20,370 --> 00:10:24,540 But we keep the phase information and then we do an inverse transform. 145 00:10:24,540 --> 00:10:26,330 We obtain the following image. 146 00:10:26,330 --> 00:10:32,180 So with images, the phase information carries most of the relevant information. 147 00:10:32,180 --> 00:10:33,870 So why is that? 148 00:10:33,870 --> 00:10:36,950 The idea is that most of the semantic information in an image 149 00:10:36,950 --> 00:10:39,310 is contained into its edges. 150 00:10:39,310 --> 00:10:43,135 Edges are points of discontinuity in the gray level's signal. 151 00:10:43,135 --> 00:10:46,320 In 1-D, you would represent an edge as a transition from, 152 00:10:46,320 --> 00:10:49,900 say, a wide level to a dark level. 153 00:10:49,900 --> 00:10:53,280 This resolution is what the eye perceives as image. 154 00:10:54,400 --> 00:10:58,340 Now edges, therefore, are very localized in space. 155 00:10:58,340 --> 00:11:03,065 And they're not captured by the DFT's magnitude, which represents a distribution 156 00:11:03,065 --> 00:11:06,120 in frequency of the energy of the whole image. 157 00:11:06,120 --> 00:11:10,250 In order to obtain an edge from the combination of functions on 158 00:11:10,250 --> 00:11:14,458 the other hand, their phase has to be aligned in a very precise manner. 159 00:11:14,458 --> 00:11:18,140 And that's why the phase information captures the intelligibility 160 00:11:18,140 --> 00:11:19,520 part of an image. 161 00:11:19,520 --> 00:11:23,792 A consequence of this is that the global DFT of an image is only of limited use in 162 00:11:23,792 --> 00:11:24,931 image processing.