1 00:00:00,400 --> 00:00:05,160 Hi and welcome to the last two modules in module eight, where we will talk about the 2 00:00:05,160 --> 00:00:09,659 JPEG compression standard. As we said before, an image stored in raw 3 00:00:09,659 --> 00:00:14,766 format occupies a lot of space. Normally, a color picture will use 24 bits 4 00:00:14,766 --> 00:00:19,969 per pixels and there a lot of pixels in an image produced by a camera today. 5 00:00:19,970 --> 00:00:23,750 By contrast, an image encoded with the JPEG standard will be encoded at 6 00:00:23,750 --> 00:00:27,590 approximately 2 bits per pixel and it will be very hard to tell the difference 7 00:00:27,590 --> 00:00:30,786 between the two. So how does this magic happen? 8 00:00:30,786 --> 00:00:35,478 Jpegs achieve this remarkable result by combining three fundamental lines of 9 00:00:35,478 --> 00:00:38,602 attack. The first one is called transform coding 10 00:00:38,602 --> 00:00:42,760 and it means that we actually encode the image in the Fourier domain rather than 11 00:00:42,760 --> 00:00:46,793 the space domain. The second is variable quantization. 12 00:00:46,793 --> 00:00:51,832 We allocate a different number of bits to different parts of the image, and this is 13 00:00:51,832 --> 00:00:57,160 based on psycho-visual test that have been carried out to determine what is important 14 00:00:57,160 --> 00:01:01,441 to the eye and what is not. And the third ingredient is called entropy 15 00:01:01,441 --> 00:01:05,559 coding and it is a technique from information theory that allows us to 16 00:01:05,559 --> 00:01:09,388 shrink the size of the bit stream, encoding the image even more. 17 00:01:09,388 --> 00:01:15,267 Hi, and welcome to module 8.5 in which we will talk about image compression. 18 00:01:15,268 --> 00:01:19,816 We will review the reason why we can compress images, namely the redundancy 19 00:01:19,816 --> 00:01:24,280 that is present in natural images And then, we will look at the fundamental 20 00:01:24,280 --> 00:01:28,458 ingredients in an image coding system. But first, let's start with a very simple 21 00:01:28,458 --> 00:01:32,098 thought experiment that will convince you that image compression is a necessity. 22 00:01:32,098 --> 00:01:39,140 Consider an image of size 256 x 256, encoded at 8 bits per pixel. 23 00:01:39,140 --> 00:01:45,907 That amount of storage that an image like that requires is on the order of 500,000 24 00:01:45,907 --> 00:01:49,290 bits. Now, from a purely combinatorial point of 25 00:01:49,290 --> 00:01:53,724 view, each bit in this image can be set independently to 0 or to 1. 26 00:01:53,724 --> 00:02:00,514 So the total number of possible images of size 256 x 256 at 8 bits per pixel, is a 27 00:02:00,514 --> 00:02:07,220 staggering 2 to the power of 524,288. To put that in perspective, we can change 28 00:02:07,220 --> 00:02:12,995 the base and express this as 10 to the power of 157, 000 and something. 29 00:02:12,995 --> 00:02:18,694 Now compare this to the number of atoms in the universe, which is estimated to be 10 30 00:02:18,694 --> 00:02:23,198 to the power of 82. This means that clearly, the subset of 31 00:02:23,198 --> 00:02:30,029 meaningful images of size 256 x 256, must be very, very, very small, compared to the 32 00:02:30,029 --> 00:02:34,059 number of all possible images. Let's take a different approach. 33 00:02:34,060 --> 00:02:39,262 Assume that we can actually collect all the images that exist in the world, 34 00:02:39,262 --> 00:02:44,430 pictures, drawings and so on, so forth. And suppose that we can list them in a 35 00:02:44,430 --> 00:02:49,144 massive encyclopedia of images. Now that we have a list and a catelog of 36 00:02:49,144 --> 00:02:54,312 all possible images we can indicate each image in the encyclopedia just be giving 37 00:02:54,312 --> 00:02:58,680 the cardinal number in the list. Now to put some numbers in this thought 38 00:02:58,680 --> 00:03:03,014 experiment, let's do this very simple back of the envelope calculation. 39 00:03:03,014 --> 00:03:08,350 Current estimates say that on the internet we have about 50 billion images and 40 00:03:08,350 --> 00:03:15,180 pictures that are floating around. Let us assume to simplify matters that all 41 00:03:15,180 --> 00:03:21,368 of these images are encoded at 8 bits per pixel and they have size 256 times 256. 42 00:03:21,368 --> 00:03:29,217 Well, each of these images encoded in raw format requires in excess of 500,000 bits. 43 00:03:29,217 --> 00:03:34,642 If we use the enumeration scheme from the encyclopedia of the image where we can 44 00:03:34,642 --> 00:03:40,218 identify each image by its index, we just need to provide this number to specify an 45 00:03:40,218 --> 00:03:44,005 image. And therefore, the cost to encode an image 46 00:03:44,005 --> 00:03:48,600 is simply the log in base 2 of the number of images in the list. 47 00:03:48,600 --> 00:03:51,989 So that's about 33 bits per image to encode. 48 00:03:51,990 --> 00:03:56,703 All possible images in the internet today. The downside to this encoding scheme is 49 00:03:56,703 --> 00:04:00,705 that it requires a lot of side information, in other words I can send an 50 00:04:00,705 --> 00:04:04,776 image to you by sending you its index number but unless you have the full 51 00:04:04,776 --> 00:04:09,100 encyclopedia at your disposal you won't be able to see the image itself. 52 00:04:09,100 --> 00:04:13,260 So on the one hand we have an indication that there is an enormous redundancy in 53 00:04:13,260 --> 00:04:15,880 the amount of space that we allocate to an image. 54 00:04:15,880 --> 00:04:20,430 And on the other hand, we have a sort of lower bound that tells us that the number 55 00:04:20,430 --> 00:04:25,330 of images that make sense in theory, could be encoded with approximately 30 bits per 56 00:04:25,330 --> 00:04:27,872 image. Neither approach gives us a solution to 57 00:04:27,872 --> 00:04:30,676 the problem. So we need to analyze the physical 58 00:04:30,676 --> 00:04:34,727 properties of images in more detail. The idea is to exploit the physical 59 00:04:34,727 --> 00:04:39,107 redundancy in images to reduce the bit budget, but of course we have to be 60 00:04:39,107 --> 00:04:44,080 careful and define redundancy specifically in terms of the human visual system. 61 00:04:44,080 --> 00:04:49,150 In order to allocate bits to features that matter, we have to find out what this 62 00:04:49,150 --> 00:04:54,454 features are and thankfully researchers have worked a lot on this on this problem 63 00:04:54,454 --> 00:04:59,890 and ran lots of pyschovisual experiments to find out things that matter the most. 64 00:04:59,890 --> 00:05:03,922 With this knowledge at hand, we can go ahead and define what is called a lossy 65 00:05:03,922 --> 00:05:07,670 compression scheme. In other words, an imaging coding system 66 00:05:07,670 --> 00:05:12,845 that will discard the information that it deems irrelevent with respect to either 67 00:05:12,845 --> 00:05:15,979 the intelligibility or quality of an image. 68 00:05:15,980 --> 00:05:19,874 So let's look at the key ingredients that will lead us to the JPEG compression 69 00:05:19,874 --> 00:05:22,698 scheme. The first is compressing the image at 70 00:05:22,698 --> 00:05:26,196 block level. We'll see this with an example in just a 71 00:05:26,196 --> 00:05:28,821 second. The second ingredient is using the 72 00:05:28,821 --> 00:05:32,500 suitable transform to move the blocks into a different domain. 73 00:05:32,500 --> 00:05:37,635 So we do a change of bases that will make it easier for us to decide which parts to 74 00:05:37,635 --> 00:05:42,460 keep, and which parts to discard. Smart quantization is the way we will go 75 00:05:42,460 --> 00:05:47,220 about discarding irrelevant parts. By allocating very few or no bits at all 76 00:05:47,220 --> 00:05:51,945 to some of the transform coefficients, we will be able to reduce the bit rate 77 00:05:51,945 --> 00:05:55,096 selectively. And finally, entropy coding is a technique 78 00:05:55,096 --> 00:05:57,420 that we will borrow from information theory. 79 00:05:57,420 --> 00:06:02,248 And it will allow us to compress even more the bit stream that we have obtained form 80 00:06:02,248 --> 00:06:06,532 the previous smart quantization. To understand the importance of block 81 00:06:06,532 --> 00:06:10,492 coding, let's see what we can do if we decide to compress an image at pixel 82 00:06:10,492 --> 00:06:13,355 level. The only thing we can do in that case is 83 00:06:13,355 --> 00:06:16,110 to reduce the number of bits that we allocate to each pixel. 84 00:06:16,110 --> 00:06:21,570 This is equivalent to quantizing the image using fewer levels and in the limit we can 85 00:06:21,570 --> 00:06:26,358 not got below one bit per pixel. So if we try and apply this to our center 86 00:06:26,358 --> 00:06:32,070 image we get something that has completely distorted the content of the original 87 00:06:32,070 --> 00:06:35,220 image. So pixel level quantization only takes us 88 00:06:35,220 --> 00:06:38,760 so far before image quality is completely compromised. 89 00:06:38,761 --> 00:06:42,979 Now by comparison, let's look at a very simple compression strategy that operates 90 00:06:42,979 --> 00:06:46,826 at block level. What we do here, is we divide the image 91 00:06:46,826 --> 00:06:50,458 into blocks. And then we code the average value with 92 00:06:50,458 --> 00:06:54,382 eight bits. We use 3 x 3 pixel blocks using eight bits 93 00:06:54,382 --> 00:06:57,612 for each block. So, we use a little bit less than one bit 94 00:06:57,612 --> 00:07:00,610 per pixel, and the result is what you see here on the right. 95 00:07:00,610 --> 00:07:04,898 If you look attentively at the details, you might perceive some jagged edges 96 00:07:04,898 --> 00:07:09,134 around, for instance, here. These are the so-called, block artifacts 97 00:07:09,134 --> 00:07:12,965 and come from the fact that we have split the image into small blocks. 98 00:07:12,966 --> 00:07:18,005 But, nonetheless, the overall result is definitely much, much better than what we 99 00:07:18,005 --> 00:07:21,990 would obtain using pixel level compression at the same bit rate. 100 00:07:21,990 --> 00:07:26,854 The power of block level compression comes from the fact that in each block we 101 00:07:26,854 --> 00:07:31,946 exploit the local correlation between neighboring pixels and at the same time, 102 00:07:31,946 --> 00:07:37,038 since blocks are independent, we separate the coding for different parts of the 103 00:07:37,038 --> 00:07:40,379 image. The block scheme we've seen just before is 104 00:07:40,379 --> 00:07:43,410 a very simple naive one. We just take the average value of the 105 00:07:43,410 --> 00:07:45,624 pixel. And the result is that we have noticeable 106 00:07:45,624 --> 00:07:49,227 block artifacts even though our blocks are very, very small, three by three. 107 00:07:49,227 --> 00:07:52,581 Can we do better? Well in order to do better we have to 108 00:07:52,581 --> 00:07:55,140 introduce the second ingredient which is transform coding. 109 00:07:55,140 --> 00:08:00,004 To give you an idea of how transform coding works, assume you have a simple one 110 00:08:00,004 --> 00:08:04,944 dimensional discrete time signal and assume that you will encode each sample 111 00:08:04,944 --> 00:08:09,746 with r bits per sample. So if the signal is like this one here, 112 00:08:09,746 --> 00:08:13,620 storing the signal, as is, will require n times r bits. 113 00:08:13,620 --> 00:08:19,453 You have n samples, r bits per sample. But now suppose you take the DFT of the 114 00:08:19,453 --> 00:08:23,920 signal And it turns out the DFT looks like this. 115 00:08:23,920 --> 00:08:28,208 Well, what happened was that the signal was a sinusoid that corresponded to one of 116 00:08:28,208 --> 00:08:30,800 the bases factor for the length of the signal. 117 00:08:30,800 --> 00:08:37,430 But with this representation, in theory, instead of having n r bits to code the 118 00:08:37,430 --> 00:08:42,179 signal, we just need to code two DFT coefficients. 119 00:08:42,180 --> 00:08:46,840 Possibly together with their position. And so the amount of bits that we spend to 120 00:08:46,840 --> 00:08:49,590 encode the signal, is definitely less than n r. 121 00:08:49,590 --> 00:08:54,554 So the lesson that we get from the simple example, is that we would like a transform 122 00:08:54,554 --> 00:08:59,226 that when transform in an image block captures the important features of the 123 00:08:59,226 --> 00:09:02,994 block in just a few coefficients. So that we can just encode those 124 00:09:02,994 --> 00:09:06,967 coefficients and discard all the rest. Also, we would like the transform to be 125 00:09:06,967 --> 00:09:11,121 efficient to compute because we're interested in efficient compression 126 00:09:11,121 --> 00:09:14,648 algorithm. The answer to these two requirements is a 127 00:09:14,648 --> 00:09:18,983 transform called discrete cosine transform or DCT for short. 128 00:09:18,984 --> 00:09:22,664 Mathematically the DCT can be expressed as such. 129 00:09:22,665 --> 00:09:27,860 It is very similar to the DFT. Except that the basis functions are based 130 00:09:27,860 --> 00:09:31,082 on cosines rather than on complex exponentials. 131 00:09:31,082 --> 00:09:35,920 The advantage of this formulation is that the transform is a purely real transform, 132 00:09:35,920 --> 00:09:38,590 when applied to real signals, such as images. 133 00:09:38,590 --> 00:09:41,964 Instead of studying the structure of this double summation. 134 00:09:41,965 --> 00:09:48,542 We can just exploit our intuition about basis expansions and realize that each 135 00:09:48,542 --> 00:09:55,138 coefficient of the DCT is just the inner product, mainly, a measure of similarity 136 00:09:55,138 --> 00:09:59,758 between the image and. Each of the basis functions. 137 00:09:59,758 --> 00:10:06,222 Now remember we're operating at block level so if for instance we're going to 138 00:10:06,222 --> 00:10:12,888 split our image as a cos to[UNKNOWN] into 8 by 8 pixel blocks, it means that n here 139 00:10:12,888 --> 00:10:17,767 is equal to 8. And the same in the other direction and so 140 00:10:17,767 --> 00:10:23,238 we will have 64 basis functions for the space of 8 by 8 images. 141 00:10:23,239 --> 00:10:29,610 We can actually plot this basis functions like so and here we have increasing values 142 00:10:29,610 --> 00:10:34,458 of the index K1 and of the index K2. And we can see that by computing the DCT 143 00:10:34,458 --> 00:10:38,359 we're actually correlating namely, measuring the similarity. 144 00:10:38,360 --> 00:10:42,000 Between an image block, and each one of these patterns here. 145 00:10:42,000 --> 00:10:45,070 Some patterns will capture and edge like behavior. 146 00:10:45,070 --> 00:10:48,037 Some patterns will capture a textual like behavior. 147 00:10:48,038 --> 00:10:52,402 But in general, there will be a pattern that will be able to capture most of the 148 00:10:52,402 --> 00:10:57,150 information contained in the small block. And this is really the philosophy behind 149 00:10:57,150 --> 00:11:00,748 transform coding in jpeg. Now when it comes to smart quantization, 150 00:11:00,748 --> 00:11:04,902 what we need to do Is to change a little bit the definition of quantization that we 151 00:11:04,902 --> 00:11:09,012 have seen in Module Seven. The idea is that we want to be able to 152 00:11:09,012 --> 00:11:13,087 discard as many values of the transform as possible. 153 00:11:13,088 --> 00:11:17,522 And by discarding them, we mean that we set them to zero, and therefore, we don't 154 00:11:17,522 --> 00:11:21,928 need to specify their amplitude. This is achieved by using so called dead 155 00:11:21,928 --> 00:11:25,469 zone quantizers, that we will see in just a second. 156 00:11:25,470 --> 00:11:30,200 The second part of smart quantization is being able to change the quantization step 157 00:11:30,200 --> 00:11:34,109 according to the importance of the coefficients that we are quantizing. 158 00:11:34,109 --> 00:11:37,999 So key coefficients will require a fine grain resolution. 159 00:11:38,000 --> 00:11:42,664 Therefore more bits will be allocated to them, whereas less important coefficients 160 00:11:42,664 --> 00:11:46,435 can be quantized rather coarsely. So let's go back to the quantization model 161 00:11:46,435 --> 00:11:50,365 that we saw in module seven. Suppose that our input is bounded between 162 00:11:50,365 --> 00:11:55,216 minus 2 and 2, and that we're using Two bits to quantize the input, then we're 163 00:11:55,216 --> 00:11:59,913 dividing the input range into four intervals because we have two bits per 164 00:11:59,913 --> 00:12:04,841 input sample and we are associating a representative value to each interval 165 00:12:04,841 --> 00:12:09,205 which happens to be the mid point. Mathematically in this case, we can say 166 00:12:09,205 --> 00:12:13,732 that the quantized value. Is simply the floor of the input value 167 00:12:13,732 --> 00:12:16,473 plus 0.5. You can see however that in this model 168 00:12:16,473 --> 00:12:21,010 there is no zero value in the output. If the input signal is even slightly 169 00:12:21,010 --> 00:12:26,800 positive, it will get associated to 0.5. And if it's slightly negatve to minus 0.5 170 00:12:26,800 --> 00:12:31,002 but there is no zero. A dead zone quantizer on the other hand 171 00:12:31,002 --> 00:12:36,722 uses intervals that have the same width as a standard quantizer but centers an 172 00:12:36,722 --> 00:12:40,925 interval around 0. So all values in this case from 0.5 to 173 00:12:40,925 --> 00:12:46,202 minus 0.5 will be mapped to zero. So small values will be quantized as zero. 174 00:12:46,202 --> 00:12:51,826 And then the rest proceeds with the usual staircase so everything is shifted by 0.5. 175 00:12:51,826 --> 00:12:56,058 From 0.5 to 1.5 we will have a representative value of one. 176 00:12:56,058 --> 00:13:00,181 Mathematically this is equivelant to saying that the quantization scheme simply 177 00:13:00,181 --> 00:13:02,689 rounds the input value to the nearest integer. 178 00:13:02,690 --> 00:13:05,948 You can notice now that we have an asymmetric characteristic for the 179 00:13:05,948 --> 00:13:09,470 quantizer. So in a sense, we're wasting half a bit. 180 00:13:09,470 --> 00:13:14,156 We can add level to the right side or the left side if needs be but the advantage of 181 00:13:14,156 --> 00:13:17,751 having a deadzone largely offsets the loss of half a bit. 182 00:13:17,752 --> 00:13:22,300 And finally let's go see that the last ingredient in the success of JPEG which is 183 00:13:22,300 --> 00:13:25,420 entropy coding. The idea behind entropy coding is to 184 00:13:25,420 --> 00:13:29,330 minimize the effort to encode a certain amount of information. 185 00:13:29,330 --> 00:13:34,823 And the way we do that is by associating short symbols to values that are 186 00:13:34,823 --> 00:13:38,958 frequently used. Now this may sound familiar to you, and 187 00:13:38,958 --> 00:13:44,640 the reason is, because it is familiar. The Morse Code, that was invented in 1836, 188 00:13:44,640 --> 00:13:49,764 is a typical example of a coding scheme where we use very short symbols for 189 00:13:49,764 --> 00:13:53,906 frequently used values. So, for instance, the most common letter 190 00:13:53,906 --> 00:13:58,462 in the English alphabet is the letter E, and, therefore, the symbol that we use to 191 00:13:58,462 --> 00:14:02,630 encode E is the shortest possible symbol in the Morse alphabet, the dot. 192 00:14:02,630 --> 00:14:07,580 And then we can find, for instance, which is the second most common letter in the 193 00:14:07,580 --> 00:14:12,380 English alphabet turns out to be I, which gets two dots, and so on and so forth. 194 00:14:12,380 --> 00:14:17,140 So Morse code was invented to minimize the time that it would take to send a message 195 00:14:17,140 --> 00:14:21,410 over a telegraph line, but we can use exactly the same principle to try and 196 00:14:21,410 --> 00:14:25,474 minimize the amount of memory that we must use to encode a bit stream. 197 00:14:25,475 --> 00:14:28,384 We will see this in more detail in the next module.