1 00:00:00,220 --> 00:00:04,625 Welcome to Module 8.2. One of the first things we do when we 2 00:00:04,625 --> 00:00:08,980 first start playing with a program like Photoshop and similar is learning how to 3 00:00:08,980 --> 00:00:13,852 translate, re-size or crop an image. The simple image manipulations can be 4 00:00:13,852 --> 00:00:18,177 described in terms of operators called affine transforms. 5 00:00:18,178 --> 00:00:22,678 The only problem is that affine transforms are defined for the continuous space, 6 00:00:22,678 --> 00:00:27,676 whereas here we are in discrete space. So in order to get the sub-pixel values 7 00:00:27,676 --> 00:00:33,826 that affine transforms require, we usually employ local interpolation schemes. 8 00:00:33,826 --> 00:00:38,455 And one very popular interpolation scheme is called a bilinear interpolation and we 9 00:00:38,455 --> 00:00:43,390 will study how that works. Hi, and welcome to module 8.2, Digital 10 00:00:43,390 --> 00:00:47,724 Signal Processing. We will take about image manipulations, 11 00:00:47,724 --> 00:00:52,268 and in particular we will consider a class of transformations called affine 12 00:00:52,268 --> 00:00:56,741 transforms and we will see how to implement affine transformations for the 13 00:00:56,741 --> 00:01:00,894 class of digital images using the bi-linear interpolation method. 14 00:01:00,894 --> 00:01:05,644 An affine transform is a mapping that reshapes a coordinate system. 15 00:01:05,644 --> 00:01:11,226 In our case, we're talking about images so we're interested in a mapping from r two 16 00:01:11,226 --> 00:01:14,875 to r two. An affine transform is defined in terms of 17 00:01:14,875 --> 00:01:18,110 a two by two matrix and a translation vector. 18 00:01:18,110 --> 00:01:23,588 And a new coordinate pair is given by the multiplication of the matrix times the 19 00:01:23,588 --> 00:01:27,597 original coordinate pair minus the translation vector. 20 00:01:27,598 --> 00:01:30,319 In compact form we will express it like so. 21 00:01:30,320 --> 00:01:33,344 Let's look at some examples of affine transform. 22 00:01:33,344 --> 00:01:38,220 A very simple one is translation. The matrix here is the identity matrix. 23 00:01:38,220 --> 00:01:42,820 And the translation vector specifies the new origin of the plane. 24 00:01:42,820 --> 00:01:46,516 So if we have this simple image here, and we apply a translation, we would get the 25 00:01:46,516 --> 00:01:50,195 simple result. Scaling is an affine transform, where the 26 00:01:50,195 --> 00:01:55,009 matrix is a diagonal matrix and the diagonal entries are the amount of 27 00:01:55,009 --> 00:01:58,934 stretching or contraction of each axis independently. 28 00:01:58,934 --> 00:02:04,352 In this example for instance we have a scaling where clearly a 1 is equal to a 2 29 00:02:04,352 --> 00:02:08,847 and both are less than 1 because the resulting image is larger. 30 00:02:08,848 --> 00:02:13,756 Rotation is another refined tranform, we have seen this before, the sturcture of 31 00:02:13,756 --> 00:02:17,190 the matrix is like so. We have cos sign of the theta on the 32 00:02:17,190 --> 00:02:21,994 diagonal, and sign of the theta and minus sign of theta on the anti diagonal. 33 00:02:21,994 --> 00:02:24,489 A pure rotation leaves the origin in place. 34 00:02:25,510 --> 00:02:32,106 And as an example here's a notation by an angle theta that is clearly larger than pi 35 00:02:32,106 --> 00:02:35,878 over two. And here for instance you have a rotation 36 00:02:35,878 --> 00:02:39,332 by pi. Flips can be both horizontal or vertical 37 00:02:39,332 --> 00:02:42,959 and they simply swap the direction of an axis. 38 00:02:42,960 --> 00:02:48,926 In both cases the matrix is diagonal and, in the case of a horizontal flip, the 39 00:02:48,926 --> 00:02:54,374 first element of the diagonal would be minus one and the second one is one. 40 00:02:54,374 --> 00:02:59,255 Vice-versa for a vertical flip, the second axis gets flipped and so the second 41 00:02:59,255 --> 00:03:01,997 element of the diagonal would be minus one. 42 00:03:01,998 --> 00:03:03,839 Here in the image we see a horizontal flip. 43 00:03:05,290 --> 00:03:09,951 Shear is a stretching of the plane in either the horizontal or vertical 44 00:03:09,951 --> 00:03:13,565 direction. For this case of Fourier transform, the 45 00:03:13,565 --> 00:03:17,630 matrix is either upper triangular or lower triangular. 46 00:03:17,630 --> 00:03:23,421 You have ones on the main diagonal. And according to whether the shear is 47 00:03:23,421 --> 00:03:28,443 horizontal or vertical, you have a parameter s on the upper corner or on the 48 00:03:28,443 --> 00:03:32,244 lower corner. Effective shearing is like so, in this 49 00:03:32,244 --> 00:03:37,881 case you have horizontal shearing where the horizontal axis is stretched. 50 00:03:37,881 --> 00:03:42,996 If we now try to apply affine transform to a digital image, we run into a fundamental 51 00:03:42,996 --> 00:03:46,077 problem. Remember, a digital image lives in 52 00:03:46,077 --> 00:03:51,602 discrete space, in other words, pixel coordinates Are pairs of integers that 53 00:03:51,602 --> 00:03:54,928 live in z2. The affine transform on the other hand, 54 00:03:54,928 --> 00:04:00,020 maps these original coordinates onto a point in r2, which means that the new pair 55 00:04:00,020 --> 00:04:04,884 of coordinates can lie anywhere on the plane, and in particular, it will most 56 00:04:04,884 --> 00:04:08,170 likely lie in between integer pixel coordinates. 57 00:04:08,170 --> 00:04:14,378 To understand the situation better, if this is the regualr grid of pixels in Z 58 00:04:14,378 --> 00:04:20,780 two, and this is the result of the affine transformation we would like that each 59 00:04:20,780 --> 00:04:25,690 point here on this grid be mapped to a point on this grid here. 60 00:04:25,690 --> 00:04:29,265 But unfortunately the affine transform would probably map this point here in 61 00:04:29,265 --> 00:04:34,337 between. So how do we solve this problem? 62 00:04:34,338 --> 00:04:38,638 The first step is to consider the inverse transform, so instead of going from the 63 00:04:38,638 --> 00:04:43,666 original image to the destination image. Here, let me draw it again.We start from 64 00:04:43,666 --> 00:04:48,996 the destination image, for which we know we want points to lie on the grid and we 65 00:04:48,996 --> 00:04:52,880 compute the originating point from the original image. 66 00:04:52,880 --> 00:04:57,240 So, if this is the original image This is a transformed image. 67 00:04:57,240 --> 00:05:03,828 We take each point on the grid and we find the point it would come from with a 68 00:05:03,828 --> 00:05:08,257 inverse transform. Now, just like before, this point will not 69 00:05:08,257 --> 00:05:11,994 lie on the original grid, but here is the second step. 70 00:05:11,995 --> 00:05:19,535 This pair of coordinates we found with inverse transform, we will express as 2 71 00:05:19,535 --> 00:05:26,838 integer coordinte, eta 1 and eta 2, plus 2 correction factors tau 1 and tau 2 where 72 00:05:26,838 --> 00:05:33,378 tau 1 and tau 2 are strictly less than one, so it is a sub-pixel correction 73 00:05:33,378 --> 00:05:40,681 factor so again if this is a magnifying view of the original grid are transformed 74 00:05:40,681 --> 00:05:47,439 gives us a point here will define that this point t1 and t2 is equal to a point 75 00:05:47,439 --> 00:05:54,197 on a grid data 1 data 2 plus a correction factor of tau 1 here and a correction 76 00:05:54,197 --> 00:05:58,090 factor, tau 2. So the question now is how to find the 77 00:05:58,090 --> 00:06:01,130 sub-pixel value here in the middle of the grid. 78 00:06:01,130 --> 00:06:06,849 And the idea is to interpolate from the four neighboring pixels. 79 00:06:06,850 --> 00:06:10,934 When the interpolation scheme between neighbouring pixel is the linear 80 00:06:10,934 --> 00:06:14,970 interpolator, this strategy goes under the name bilinear interpolation. 81 00:06:14,971 --> 00:06:20,203 So, let's see how this works. We have our reference point, x of eta 1 82 00:06:20,203 --> 00:06:26,280 and eta 2, and we also have the 3 Neighboring points like so remember are 83 00:06:26,280 --> 00:06:33,181 sub pixel value as computed before falls here in the middle and it is expressed as 84 00:06:33,181 --> 00:06:39,670 a pixel at a horizontal distance of tow one and a vertical distance of tow two 85 00:06:39,670 --> 00:06:44,137 from the reference coordinate eta one and eta two. 86 00:06:44,138 --> 00:06:48,294 So, to compute it's value we first interpolate in the horizontal direction. 87 00:06:48,295 --> 00:06:55,822 And we find two sub-pixel values at vertical coordinate eta2 and eta2 plus 1, 88 00:06:55,822 --> 00:07:02,771 both at a distance of tau1 from eta1. And then, once we have these two values, 89 00:07:02,771 --> 00:07:08,720 we compute a vertical interpolation at a distance of tau2 like so. 90 00:07:08,720 --> 00:07:13,598 And this gives us our desired value. With the first order interpolater, the 91 00:07:13,598 --> 00:07:18,614 value is simply a linear combination of the values of the four pixels that we've 92 00:07:18,614 --> 00:07:23,250 solved before weighted by some factors that take their distance from the 93 00:07:23,250 --> 00:07:29,470 reference point into account. One thing that can happen is that when we 94 00:07:29,470 --> 00:07:35,230 compute t1 and t2 as the inverse of affine transform, we get a value that falls 95 00:07:35,230 --> 00:07:38,770 outside of the support of the original image. 96 00:07:38,770 --> 00:07:43,223 And in that case we will have to replace this value with a standard value of 97 00:07:43,223 --> 00:07:48,770 choice, which is usually zero. You can now try and use the bi-linear 98 00:07:48,770 --> 00:07:56,570 interpolation to compute the shearing of a standard image, and if we do that we 99 00:07:56,570 --> 00:07:59,468 obtain something like this.