Understanding and Decoding a JPEG Picture utilizing Python

Hello everybody! ? Right this moment we’re going to perceive the JPEG compression algorithm. One factor lots of people don’t know is that JPEG just isn’t a format however quite an algorithm. The JPEG pictures you see are largely within the JFIF format (JPEG File Interchange Format) that internally makes use of the JPEG compression algorithm. By the top of this text, you should have a significantly better understanding of how the JPEG algorithm compresses information and how one can write some customized Python code to decompress it. We won’t be overlaying all of the nuances of the JPEG format (like progressive scan) however quite solely the essential baseline format whereas writing our decoder.

Introduction

Why write one other article on JPEG when there are already tons of of articles on the web? Nicely, usually if you learn articles on JPEG, the creator simply offers you particulars about what the format seems to be like. You don’t implement any code to do the precise decompression and decoding. Even if you happen to do write code, it’s in C/C++ and never accessible to a large group of individuals. I plan on altering that by exhibiting you ways a primary JPEG decoder works utilizing Python 3. I can be basing my decoder on this MIT licensed code however can be closely modifying it for elevated readability and ease of understanding. You’ll find the modified code for this text on my GitHub repo.

Completely different elements of a JPEG

Let’s begin with this good picture by Ange Albertini. It lists all completely different elements of a easy JPEG file. Check out it. We can be exploring every section. You might need to confer with this picture fairly just a few occasions whereas studying this tutorial.

On the very primary stage, virtually each binary file accommodates a few markers (or headers). You possibly can consider these markers as kind of like bookmarks. They’re very essential for making sense of a file and are utilized by applications like file (on Mac/Linux) to inform us particulars a couple of file. These markers outline the place some particular data in a file is saved. A lot of the markers are adopted by size data for the actual marker section. This tells us how lengthy that specific section is.

File Begin & File Finish

The very first marker we care about is FF D8. It tells us that that is the beginning of the picture. If we don’t see it we are able to assume that is another file. One other equally essential marker is FF D9. It tells us that now we have reached the top of a picture file. Each marker, aside from FFD0 to FFD9 and FF01, is straight away adopted by a size specifier that provides you with the size of that marker section. As for the picture file begin and picture file finish markers, they may at all times be two bytes lengthy every.

All through this tutorial, we can be working with this picture:

Let’s write some code to determine these markers.

from struct import unpack


marker_mapping = {
    0xffd8: "Begin of Picture",
    0xffe0: "Utility Default Header",
    0xffdb: "Quantization Desk",
    0xffc0: "Begin of Body",
    0xffc4: "Outline Huffman Desk",
    0xffda: "Begin of Scan",
    0xffd9: "Finish of Picture"
}


class JPEG:
    def __init__(self, image_file):
        with open(image_file, 'rb') as f:
            self.img_data = f.learn()
    
    def decode(self):
        information = self.img_data
        whereas(True):
            marker, = unpack(">H", information[0:2])
            print(marker_mapping.get(marker))
            if marker == 0xffd8:
                information = information[2:]
            elif marker == 0xffd9:
                return
            elif marker == 0xffda:
                information = information[-2:]
            else:
                lenchunk, = unpack(">H", information[2:4])
                information = information[2+lenchunk:]            
            if len(information)==0:
                break        

if __name__ == "__main__":
    img = JPEG('profile.jpg')
    img.decode()    

# OUTPUT:
# Begin of Picture
# Utility Default Header
# Quantization Desk
# Quantization Desk
# Begin of Body
# Huffman Desk
# Huffman Desk
# Huffman Desk
# Huffman Desk
# Begin of Scan
# Finish of Picture

We’re utilizing struct to unpack the bytes of picture information. >H tells struct to deal with the info as big-endian and of kind unsigned brief. The info in JPEG is saved in big-endian format. Solely the EXIF information can be in little-endian (despite the fact that it’s unusual). And a brief is of dimension 2 so we offer unpack two bytes from our img_data. You may ask your self how we knew it was a brief. Nicely, we all know that the markers in JPEG are 4 hex digits: ffd8. One hex digit equals 4 bits (1/2 byte) so 4 hex digits will equal 2 bytes and a brief is the same as 2 bytes.

The Begin of Scan part is straight away adopted by picture scan information and that picture scan information doesn’t have a size specified. It continues until the “finish of file” marker is discovered so for now we’re manually “searching for” to the EOF marker every time we see the SOC marker.

Now that now we have the essential framework in place, let’s transfer on and determine what the remainder of the picture information accommodates. We’ll undergo some obligatory idea first after which get all the way down to coding.

Encoding a JPEG

I’ll first clarify some primary ideas and encoding methods utilized by JPEG after which decoding will naturally comply with from that as a reverse of it. In my expertise, instantly making an attempt to make sense of decoding is a bit laborious.

Although the picture beneath received’t imply a lot to you proper now, it provides you with some anchors to carry on to whereas we undergo the entire encoding/decoding course of. It exhibits the steps concerned within the JPEG encoding course of: (src)

JPEG Shade Area

In response to the JPEG spec (ISO/IEC 10918-6:2013 (E), part 6.1):

• Photographs encoded with just one element are assumed to be grayscale information during which 0 is black and 255 is white.
• Photographs encoded with three parts are assumed to be RGB information encoded as YCbCr until the picture accommodates an APP14 marker section as laid out in 6.5.3, during which case the colour encoding is taken into account both RGB or YCbCr in keeping with the appliance information of the APP14 marker section. The connection between RGB and YCbCr is outlined as laid out in Rec. ITU-T T.871 | ISO/IEC 10918-5.
• Photographs encoded with 4 parts are assumed to be CMYK, with (0,0,0,0) indicating white until the picture accommodates an APP14 marker section as laid out in 6.5.3, during which case the colour encoding is taken into account both CMYK or YCCK in keeping with the appliance information of the APP14 marker section. The connection between CMYK and YCCK is outlined as laid out in clause 7.

Most JPEG algorithm implementations use luminance and chrominance (YUV encoding) as an alternative of RGB. That is tremendous helpful in JPEG because the human eye is fairly unhealthy at seeing high-frequency brightness adjustments over a small space so we are able to primarily cut back the quantity of frequency and the human eye received’t be capable to inform the distinction. End result? A extremely compressed picture with virtually no seen discount in high quality.

Identical to every pixel in RGB shade house is made up of three bytes of shade information (Crimson, Inexperienced, Blue), every pixel in YUV makes use of 3 bytes as nicely however what every byte represents is barely completely different. The Y element determines the brightness of the colour (additionally known as luminance or luma), whereas the U and V parts decide the colour (also referred to as chroma). The U element refers back to the quantity of blue shade and the V element refers back to the quantity of crimson shade.

This shade format was invented when shade televisions weren’t tremendous widespread and engineers wished to make use of one picture encoding format for each shade and black and white televisions. YUV could possibly be safely displayed on a black and white TV if shade wasn’t accessible. You possibly can learn extra about its historical past on Wikipedia.

Discrete Cosine Rework & Quantization

JPEG converts a picture into chunks of 8×8 blocks of pixels (referred to as MCUs or Minimal Coding Items), adjustments the vary of values of the pixels in order that they heart on 0 after which applies Discrete Cosine Transformation to every block after which makes use of quantization to compress the ensuing block. Let’s get a high-level understanding of what all of those phrases imply.

A Discrete Cosine Rework is a technique for changing discrete information factors into a mixture of cosine waves. It appears fairly ineffective to spend time changing a picture right into a bunch of cosines however it is smart as soon as we perceive DCT together with how the following step works. In JPEG, DCT will take an 8×8 picture block and inform us tips on how to reproduce it utilizing an 8×8 matrix of cosine features. Learn extra right here)

The 8×8 matrix of cosine features appear to be this:

We apply DCT to every element of a pixel individually. The output of making use of DCT is an 8×8 coefficient matrix that tells us how a lot every cosine operate (out of 64 whole features) contributes to the 8×8 enter matrix. The coefficient matrix of a DCT usually accommodates greater values within the prime left nook of the coefficient matrix and smaller values within the backside proper nook. The highest left nook represents the bottom frequency cosine operate and the underside proper represents the very best frequency cosine operate.

What this tells us is that the majority pictures include an enormous quantity of low-frequency data and a small quantity of high-frequency data. If we flip the underside proper parts of every DCT matrix to 0, the ensuing picture would nonetheless seem the identical as a result of, as I discussed, people are unhealthy at observing high-frequency adjustments. That is precisely what we do within the subsequent step.

I discovered an exquisite video on this subject. Watch it if DCT doesn’t make an excessive amount of sense.

We’ve all heard that JPEG is a lossy compression algorithm however to date we haven’t completed something lossy. We’ve solely reworked 8×8 blocks of YUV parts into 8×8 blocks of cosine features with no lack of data. The lossy half comes within the quantization step.

Quantization is a course of during which we take a few values in a particular vary and turns them right into a discrete worth. For our case, that is only a fancy identify for changing the upper frequency coefficients within the DCT output matrix to 0. If you save a picture utilizing JPEG, most picture enhancing applications ask you ways a lot compression you want. The share you provide there impacts how a lot quantization is utilized and the way a lot of upper frequency data is misplaced. That is the place the lossy compression is utilized. When you lose high-frequency data, you may’t recreate the precise authentic picture from the ensuing JPEG picture.

Relying on the compression stage required, some widespread quantization matrices are used (enjoyable truth: Most distributors have patents on quantization desk building). We divide the DCT coefficient matrix element-wise with the quantization matrix, around the outcome to an integer, and get the quantized matrix. Let’s undergo an instance.

When you have this DCT matrix:

This (widespread) Quantization matrix:

Then the ensuing quantized matrix can be this:

Although people can’t see high-frequency data, if you happen to take away an excessive amount of data from the 8×8 picture chunks, the general picture will look blocky. On this quantized matrix, the very first worth known as a DC worth and the remainder of the values are AC values. If we have been to take the DC values from all of the quantized matrices and generated a brand new picture, we are going to primarily find yourself with a thumbnail with 1/eighth decision of the unique picture.

Additionally it is essential to notice that as a result of we apply quantization whereas decoding, we must be certain the colours fall within the [0,255] vary. In the event that they fall outdoors this vary, we must manually clamp them to this vary.

Zig-zag

After quantization, JPEG makes use of zig-zag encoding to transform the matrix to 1D (img src):

Let’s think about now we have this quantized matrix:

The output of zig-zag encoding can be this:

[15 14 13 12 11 10 9 8 0  ...  0]

This encoding is most popular as a result of many of the low frequency (most important) data is saved at first of the matrix after quantization and the zig-zag encoding shops all of that at first of the 1D matrix. That is helpful for the compression that occurs within the subsequent step.

Run-length and Delta encoding

Run-length encoding is used to compress repeated information. On the finish of the zig-zag encoding, we noticed how many of the zig-zag encoded 1D arrays had so many 0s on the finish. Run-length encoding permits us to reclaim all that wasted house and use fewer bytes to symbolize all of these 0s. Think about you will have some information like this:

10 10 10 10 10 10 10

Run-length encoding will convert it into:

7 10

We have been capable of efficiently compress 7 bytes of knowledge into solely 2 bytes.

Delta encoding is a method used to symbolize a byte relative to the byte earlier than it. It’s simpler to grasp this with an instance. Let’s say you will have the next information:

10 11 12 13 10 9

You should use delta encoding to retailer it like this:

10 1  2  3  0 -1

In JPEG, each DC worth in a DCT coefficient matrix is delta encoded relative to the DC worth previous it. Which means that if you happen to change the very first DCT coefficient of your picture, the entire picture will get screwed up however if you happen to modify the primary worth of the final DCT matrix, solely a really tiny a part of your picture can be affected. That is helpful as a result of the primary DC worth in your picture is often essentially the most various and by making use of the Delta encoding we deliver the remainder of DC values near 0 and that ends in higher compression within the subsequent step of Huffman Encoding.

Huffman Encoding

Huffman encoding is a technique for lossless compression of knowledge. Huffman as soon as requested himself, “What’s the smallest variety of bits I can use to retailer an arbitrary piece of textual content?”. This coding format was his reply. Think about you need to retailer this textual content:

a b c d e

In a standard state of affairs every character would take up 1 byte of house:

a: 01100001
b: 01100010
c: 01100011
d: 01100100
e: 01100101

That is based mostly on ASCII to binary mapping. However what if we may provide you with a customized mapping?

# Mapping

000: 01100001
001: 01100010
010: 01100011
100: 01100100
011: 01100101

Now we are able to retailer the identical textual content utilizing manner fewer bits:

a: 000
b: 001
c: 010
d: 100
e: 011

That is all nicely and good however what if we wish to take even much less house? What if we have been capable of do one thing like this:

# Mapping
0:  01100001
1:  01100010
00: 01100011
01: 01100100
10: 01100101

a: 0
b: 1
c: 00
d: 01
e: 10

Huffman encoding permits us to make use of this kind of variable-length mapping. It takes some enter information, maps essentially the most frequent characters to the smaller bit patterns and least frequent characters to bigger bit patterns, and eventually organizes the mapping right into a binary tree. In a JPEG we retailer the DCT (Discrete Cosine Rework) data utilizing Huffman encoding. Keep in mind I advised you that utilizing delta encoding for DC values helps in Huffman Encoding? I hope you may see why now. After delta encoding, we find yourself with fewer “characters” to map and the whole dimension of our Huffman tree is decreased.

Tom Scott has an exquisite video with animations on how Huffman encoding works normally. Do watch it earlier than transferring on.

A JPEG accommodates as much as 4 Huffman tables and these are saved within the “Outline Huffman Desk” part (beginning with 0xffc4). The DCT coefficients are saved in 2 completely different Huffman tables. One accommodates solely the DC values from the zig-zag tables and the opposite accommodates the AC values from the zig-zag tables. Which means that in our decoding, we must merge the DC and AC values from two separate matrices. The DCT data for the luminance and chrominance channel is saved individually so now we have 2 units of DC and a pair of units of AC data giving us a complete of 4 Huffman tables.

In a greyscale picture, we’d have solely 2 Huffman tables (1 for DC and 1 for AC) as a result of we don’t care in regards to the shade. As you may already think about, 2 pictures can have very completely different Huffman tables so you will need to retailer these tables inside every JPEG.

So we all know the essential particulars of what a JPEG picture accommodates. Let’s begin with the decoding!

JPEG decoding

We are able to break down the decoding right into a bunch of steps:

1. Extract the Huffman tables and decode the bits
2. Extract DCT coefficients by undoing the run-length and delta encodings
3. Use DCT coefficients to mix cosine waves and regenerate pixel values for every 8×8 block
4. Convert YCbCr to RGB for every pixel
5. Show the ensuing RGB picture

JPEG normal helps 4 compression codecs:

• Baseline
• Prolonged Sequential
• Progressive
• Lossless

We’re going to be working with the Baseline compression and in keeping with the usual, baseline will include the sequence of 8×8 blocks proper subsequent to one another. The opposite compression codecs format the info a bit in another way. Only for reference, I’ve coloured completely different segments within the hex content material of the picture we’re utilizing. That is the way it seems to be:

We already know {that a} JPEG accommodates 4 Huffman tables. That is the final step within the encoding process so it needs to be step one within the decoding process. Every DHT part accommodates the next data:

Suppose you will have a DH desk much like this (src):

Will probably be saved within the JFIF file roughly like this (they are going to be saved in binary. I’m utilizing ASCII only for illustration functions):

0 1 5 1 1 1 1 1 1 0 0 0 0 0 0 0 a b c d e f g h i j okay l

The 0 signifies that there isn’t a Huffman code of size 1. 1 means that there’s 1 Huffman code of size 2. And so forth. There are at all times 16 bytes of size information within the DHT part proper after the category and ID data. Let’s write some code to extract the lengths and components in DHT.

class JPEG:
    # ...
    
    def decodeHuffman(self, information):
        offset = 0
        header, = unpack("B",information[offset:offset+1])
        offset += 1

        # Extract the 16 bytes containing size information
        lengths = unpack("BBBBBBBBBBBBBBBB", information[offset:offset+16]) 
        offset += 16

        # Extract the weather after the preliminary 16 bytes
        components = []
        for i in lengths:
            components += (unpack("B"*i, information[offset:offset+i]))
            offset += i 

        print("Header: ",header)
        print("lengths: ", lengths)
        print("Components: ", len(components))
        information = information[offset:]

    
    def decode(self):
        information = self.img_data
        whereas(True):
            # ---
            else:
                len_chunk, = unpack(">H", information[2:4])
                len_chunk += 2
                chunk = information[4:len_chunk]

                if marker == 0xffc4:
                    self.decodeHuffman(chunk)
                information = information[len_chunk:]            
            if len(information)==0:
                break        

When you run the code, it ought to produce the next output:

Begin of Picture
Utility Default Header
Quantization Desk
Quantization Desk
Begin of Body
Huffman Desk
Header:  0
lengths:  (0, 2, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Components:  10
Huffman Desk
Header:  16
lengths:  (0, 2, 1, 3, 2, 4, 5, 2, 4, 4, 3, 4, 8, 5, 5, 1)
Components:  53
Huffman Desk
Header:  1
lengths:  (0, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Components:  8
Huffman Desk
Header:  17
lengths:  (0, 2, 2, 2, 2, 2, 1, 3, 3, 1, 7, 4, 2, 3, 0, 0)
Components:  34
Begin of Scan
Finish of Picture

Candy! We received the lengths and the weather. Now we have to create a customized Huffman desk class in order that we are able to recreate a binary tree from these components and lengths. I’m shamelessly copying this code from right here:

class HuffmanTable:
    def __init__(self):
        self.root=[]
        self.components = []
    
    def BitsFromLengths(self, root, component, pos):
        if isinstance(root,checklist):
            if pos==0:
                if len(root)<2:
                    root.append(component)
                    return True                
                return False
            for i in [0,1]:
                if len(root) == i:
                    root.append([])
                if self.BitsFromLengths(root[i], component, pos-1) == True:
                    return True
        return False
    
    def GetHuffmanBits(self,  lengths, components):
        self.components = components
        ii = 0
        for i in vary(len(lengths)):
            for j in vary(lengths[i]):
                self.BitsFromLengths(self.root, components[ii], i)
                ii+=1

    def Discover(self,st):
        r = self.root
        whereas isinstance(r, checklist):
            r=r[st.GetBit()]
        return  r 

    def GetCode(self, st):
        whereas(True):
            res = self.Discover(st)
            if res == 0:
                return 0
            elif ( res != -1):
                return res
                
class JPEG:
    # -----

    def decodeHuffman(self, information):
        # ----
        hf = HuffmanTable()
        hf.GetHuffmanBits(lengths, components)
        information = information[offset:]

The GetHuffmanBits takes within the lengths and components, iterates over all the weather and places them in a root checklist. This checklist accommodates nested lists and represents a binary tree. You possibly can learn on-line how a Huffman Tree works and tips on how to create your personal Huffman tree information construction in Python. For our first DHT (utilizing the picture I linked at first of this tutorial) now we have the next information, lengths, and components:

Hex Knowledge: 00 02 02 03 01 01 01 00 00 00 00 00 00 00 00 00
Lengths:  (0, 2, 2, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0)
Components: [5, 6, 3, 4, 2, 7, 8, 1, 0, 9]

After calling GetHuffmanBits on this, the root checklist will include this information:

[[5, 6], [[3, 4], [[2, 7], [8, [1, [0, [9]]]]]]]

The HuffmanTable additionally accommodates the GetCode technique that traverses the tree for us and provides us again the decoded bits utilizing the Huffman desk. This technique expects a bitstream as an enter. A bitstream is simply the binary illustration of knowledge. For instance, a typical bitstream of abc can be 011000010110001001100011. We first convert every character into its ASCII code after which convert that ASCII code to binary. Let’s create a customized class that can enable us to transform a string into bits and skim the bits one after the other. That is how we are going to implement it:

class Stream:
    def __init__(self, information):
        self.information= information
        self.pos = 0

    def GetBit(self):
        b = self.information[self.pos >> 3]
        s = 7-(self.pos & 0x7)
        self.pos+=1
        return (b >> s) & 1

    def GetBitN(self, l):
        val = 0
        for i in vary(l):
            val = val*2 + self.GetBit()
        return val

We feed this class some binary information whereas initializing it after which use the GetBit and GetBitN strategies to learn it.

Decoding the Quantization Desk

The Outline Quantization Desk part accommodates the next information:

In response to the JPEG normal, there are 2 default quantization tables in a JPEG picture. One for luminance and one for chrominance. These tables begin on the 0xffdb marker. Within the preliminary code we wrote, we already noticed that the output contained two 0xffdb markers. Let’s prolong the code we have already got and add the power to decode quantization tables as nicely:

def GetArray(kind,l, size):
    s = ""
    for i in vary(size):
        s =s+kind
    return checklist(unpack(s,l[:length]))
  
class JPEG:
    # ------
    def __init__(self, image_file):
        self.huffman_tables = {}
        self.quant = {}
        with open(image_file, 'rb') as f:
            self.img_data = f.learn()

    def DefineQuantizationTables(self, information):
        hdr, = unpack("B",information[0:1])
        self.quant[hdr] =  GetArray("B", information[1:1+64],64)
        information = information[65:]


    def decodeHuffman(self, information):
        # ------ 
        for i in lengths:
            components += (GetArray("B", information[off:off+i], i))
            offset += i 
            # ------

    def decode(self):
        # ------
        whereas(True):
            # ----
            else:
                # -----
                if marker == 0xffc4:
                    self.decodeHuffman(chunk)
                elif marker == 0xffdb:
                    self.DefineQuantizationTables(chunk)
                information = information[len_chunk:]            
            if len(information)==0:
                break        

We did a few issues right here. First, I outlined a GetArray technique. It’s only a helpful technique for decoding a variable variety of bytes from binary information. I changed some code in decodeHuffman technique to utilize this new operate as nicely. After that, I outlined the DefineQuantizationTables technique. This technique merely reads the header of a Quantization Desk part after which appends the quantization information in a dictionary with the header worth as the important thing. The header worth can be 0 for luminance and 1 for chrominance. Every Quantization Desk part within the JFIF accommodates 64 bytes of QT information (for our 8×8 Quantization matrix).

If we print the quantization matrices for our picture. They may appear to be this:

3    2    2    3    2    2    3    3   
3    3    4    3    3    4    5    8   
5    5    4    4    5    10   7    7   
6    8    12   10   12   12   11   10  
11   11   13   14   18   16   13   14  
17   14   11   11   16   22   16   17  
19   20   21   21   21   12   15   23  
24   22   20   24   18   20   21   20  


3     2    2    3    2    2    3    3
3     2    2    3    2    2    3    3
3     3    4    3    3    4    5    8
5     5    4    4    5    10   7    7
6     8    12   10   12   12   11   10
11    11   13   14   18   16   13   14
17    14   11   11   16   22   16   17
19    20   21   21   21   12   15   23
24    22   20   24   18   20   21   20

Decoding Begin of Body

The Begin of Body part accommodates the next data (src):

Out of this information we solely care about just a few issues. We’ll extract the picture width and peak and the quantization desk variety of every element. The width and peak can be used once we begin decoding the precise picture scans from the Begin of Scan part. As a result of we’re going to be primarily working with a YCbCr picture, we are able to anticipate the variety of parts to be equal to three and the element varieties to be equal to 1, 2 and three respectively. Let’s write some code to decode this information:

class JPEG:
    def __init__(self, image_file):
        self.huffman_tables = {}
        self.quant = {}
        self.quantMapping = []
        with open(image_file, 'rb') as f:
            self.img_data = f.learn()
    # ----
    def BaselineDCT(self, information):
        hdr, self.peak, self.width, parts = unpack(">BHHB",information[0:6])
        print("dimension %ix%i" % (self.width,  self.peak))

        for i in vary(parts):
            id, samp, QtbId = unpack("BBB",information[6+i*3:9+i*3])
            self.quantMapping.append(QtbId)         
    
    def decode(self):
        # ----
        whereas(True):
                # -----
                elif marker == 0xffdb:
                    self.DefineQuantizationTables(chunk)
                elif marker == 0xffc0:
                    self.BaselineDCT(chunk)
                information = information[len_chunk:]            
            if len(information)==0:
                break        

We added a quantMapping checklist attribute to our JPEG class and launched a BaselineDCT technique. The BaselineDCT technique decodes the required information from the SOF part and places the quantization desk numbers of every element within the quantMapping checklist. We’ll make use of this mapping as soon as we begin studying the Begin of Scan part. That is what the quantMapping seems to be like for our picture:

Quant mapping:  [0, 1, 1]

Decoding Begin of Scan

Candy! We solely have yet one more part left to decode. That is the meat of a JPEG picture and accommodates the precise “picture” information. That is additionally essentially the most concerned step. All the pieces else now we have decoded to date will be regarded as making a map to assist us navigate and decode the precise picture. This part accommodates the precise picture itself (albeit in an encoded type). We’ll learn this part and use the info now we have already decoded to make sense of the picture.

All of the markers now we have seen to date begin with 0xff. 0xff will be a part of the picture scan information as nicely but when 0xff is current within the scan information, it can at all times be proceeded by 0x00. That is one thing a JPEG encoder does routinely and known as byte stuffing. It’s the decoder’s obligation to take away this continuing 0x00. Let’s begin the SOS decoder technique with this operate and eliminate 0x00 whether it is current. Within the pattern picture I’m utilizing, we don’t have 0xff within the picture scan information however it’s nonetheless a helpful addition.

def RemoveFF00(information):
    datapro = []
    i = 0
    whereas(True):
        b,bnext = unpack("BB",information[i:i+2])        
        if (b == 0xff):
            if (bnext != 0):
                break
            datapro.append(information[i])
            i+=2
        else:
            datapro.append(information[i])
            i+=1
    return datapro,i

class JPEG:
    # ----
    def StartOfScan(self, information, hdrlen):
        information,lenchunk = RemoveFF00(information[hdrlen:])
        return lenchunk+hdrlen
      
    def decode(self):
        information = self.img_data
        whereas(True):
            marker, = unpack(">H", information[0:2])
            print(marker_mapping.get(marker))
            if marker == 0xffd8:
                information = information[2:]
            elif marker == 0xffd9:
                return
            else:
                len_chunk, = unpack(">H", information[2:4])
                len_chunk += 2
                chunk = information[4:len_chunk]
                if marker == 0xffc4:
                    self.decodeHuffman(chunk)
                elif marker == 0xffdb:
                    self.DefineQuantizationTables(chunk)
                elif marker == 0xffc0:
                    self.BaselineDCT(chunk)
                elif marker == 0xffda:
                    len_chunk = self.StartOfScan(information, len_chunk)
                information = information[len_chunk:]            
            if len(information)==0:
                break        

Beforehand I used to be manually searching for to the top of the file every time I encountered the 0xffda marker however now that now we have the required tooling in place to undergo the entire file in a scientific order, I moved the marker situation contained in the else clause. The RemoveFF00 operate merely breaks every time it observer one thing apart from 0x00 after 0xff. Due to this fact, it can escape of the loop when it encounters 0xffd9, and that manner we are able to safely search to the top of the file with none surprises. When you run this code now, nothing new will output to the terminal.

Recall that JPEG broke up the picture into an 8×8 matrix. The subsequent step for us is to transform our picture scan information right into a bit-stream and course of the stream in 8×8 chunks of knowledge. Let’s add some extra code to our class:

class JPEG:
    # -----
    def StartOfScan(self, information, hdrlen):
        information,lenchunk = RemoveFF00(information[hdrlen:])
        st = Stream(information)
        oldlumdccoeff, oldCbdccoeff, oldCrdccoeff = 0, 0, 0
        for y in vary(self.peak//8):
            for x in vary(self.width//8):
                matL, oldlumdccoeff = self.BuildMatrix(st,0, self.quant[self.quantMapping[0]], oldlumdccoeff)
                matCr, oldCrdccoeff = self.BuildMatrix(st,1, self.quant[self.quantMapping[1]], oldCrdccoeff)
                matCb, oldCbdccoeff = self.BuildMatrix(st,1, self.quant[self.quantMapping[2]], oldCbdccoeff)
                DrawMatrix(x, y, matL.base, matCb.base, matCr.base )    
        
        return lenchunk +hdrlen

We begin by changing our scan information right into a bit-stream. Then we initialize oldlumdccoeff, oldCbdccoeff, oldCrdccoeff to 0. These are required as a result of bear in mind we talked about how the DC component in a quantization matrix (the primary component of the matrix) is delta encoded relative to the earlier DC component? This can assist us maintain monitor of the worth of the earlier DC components and 0 would be the default once we encounter the primary DC component.

The for loop might sound a bit funky. The self.peak//8 tells us what number of occasions we are able to divide the peak by 8. The identical goes for self.width//8. This briefly tells us what number of 8×8 matrices is the picture divided in.

The BuildMatrix will take within the quantization desk and a few further params, create an Inverse Discrete Cosine Transformation Matrix, and provides us the Y, Cr, and Cb matrices. The precise conversion of those matrices to RGB will occur within the DrawMatrix operate.

Let’s first create our IDCT class after which we are able to begin fleshing out the BuildMatrix technique.

import math


class IDCT:
    """
    An inverse Discrete Cosine Transformation Class
    """

    def __init__(self):
        self.base = [0] * 64
        self.zigzag = [
            [0, 1, 5, 6, 14, 15, 27, 28],
            [2, 4, 7, 13, 16, 26, 29, 42],
            [3, 8, 12, 17, 25, 30, 41, 43],
            [9, 11, 18, 24, 31, 40, 44, 53],
            [10, 19, 23, 32, 39, 45, 52, 54],
            [20, 22, 33, 38, 46, 51, 55, 60],
            [21, 34, 37, 47, 50, 56, 59, 61],
            [35, 36, 48, 49, 57, 58, 62, 63],
        ]
        self.idct_precision = 8
        self.idct_table = [
            [
                (self.NormCoeff(u) * math.cos(((2.0 * x + 1.0) * u * math.pi) / 16.0))
                for x in range(self.idct_precision)
            ]
            for u in vary(self.idct_precision)
        ]

    def NormCoeff(self, n):
        if n == 0:
            return 1.0 / math.sqrt(2.0)
        else:
            return 1.0

    def rearrange_using_zigzag(self):
        for x in vary(8):
            for y in vary(8):
                self.zigzag[x][y] = self.base[self.zigzag[x][y]]
        return self.zigzag

    def perform_IDCT(self):
        out = [list(range(8)) for i in range(8)]

        for x in vary(8):
            for y in vary(8):
                local_sum = 0
                for u in vary(self.idct_precision):
                    for v in vary(self.idct_precision):
                        local_sum += (
                            self.zigzag[v][u]
                            * self.idct_table[u][x]
                            * self.idct_table[v][y]
                        )
                out[y][x] = local_sum // 4
        self.base = out

Let’s attempt to perceive this IDCT class step-by-step. As soon as we extract the MCU from a JPEG, the base attribute of this class will retailer it. Then we are going to rearrange the MCU matrix by undoing the zigzag encoding by way of the rearrange_using_zigzag technique. Lastly, we are going to undo the Discrete Cosine Transformation by calling the perform_IDCT technique.

When you bear in mind, the Discrete Cosine desk is fastened. How the precise calculation for a DCT works is outdoors the scope of this tutorial as it’s extra maths than programming. We are able to retailer this desk as a worldwide variable after which question that for values based mostly on x,y pairs. I made a decision to place the desk and its calculation within the IDCT class for readability functions. Each single component of the rearranged MCU matrix is multiplied by the values of the idc_variable and we ultimately get again the Y, Cr, and Cb values.

This can make extra sense as soon as we write down the BuildMatrix technique.

When you modify the zigzag desk to one thing like this:

[[ 0,  1,  5,  6, 14, 15, 27, 28],
[ 2,  4,  7, 13, 16, 26, 29, 42],
[ 3,  8, 12, 17, 25, 30, 41, 43],
[20, 22, 33, 38, 46, 51, 55, 60],
[21, 34, 37, 47, 50, 56, 59, 61],
[35, 36, 48, 49, 57, 58, 62, 63],
[ 9, 11, 18, 24, 31, 40, 44, 53],
[10, 19, 23, 32, 39, 45, 52, 54]]

You’ll have the next output (discover the small artifacts):

And in case you are even courageous, you may modify the zigzag desk much more:

[[12, 19, 26, 33, 40, 48, 41, 34,],
[27, 20, 13,  6,  7, 14, 21, 28,],
[ 0,  1,  8, 16,  9,  2,  3, 10,],
[17, 24, 32, 25, 18, 11,  4,  5,],
[35, 42, 49, 56, 57, 50, 43, 36,],
[29, 22, 15, 23, 30, 37, 44, 51,],
[58, 59, 52, 45, 38, 31, 39, 46,],
[53, 60, 61, 54, 47, 55, 62, 63]]

It’ll outcome on this output:

Now let’s end up our BuildMatrix technique:

def DecodeNumber(code, bits):
    l = 2**(code-1)
    if bits>=l:
        return bits
    else:
        return bits-(2*l-1)
      
      
class JPEG:
    # -----
    def BuildMatrix(self, st, idx, quant, olddccoeff):
        i = IDCT()

        code = self.huffman_tables[0 + idx].GetCode(st)
        bits = st.GetBitN(code)
        dccoeff = DecodeNumber(code, bits) + olddccoeff

        i.base[0] = (dccoeff) * quant[0]
        l = 1
        whereas l < 64:
            code = self.huffman_tables[16 + idx].GetCode(st)
            if code == 0:
                break

            # The primary a part of the AC quantization desk
            # is the variety of main zeros
            if code > 15:
                l += code >> 4
                code = code & 0x0F

            bits = st.GetBitN(code)

            if l < 64:
                coeff = DecodeNumber(code, bits)
                i.base[l] = coeff * quant[l]
                l += 1

        i.rearrange_using_zigzag()
        i.perform_IDCT()

        return i, dccoeff

We begin by creating an Inverse Discrete Cosine Transformation class (IDCT()). Then we learn within the bit-stream and decode it utilizing our Huffman desk.

The self.huffman_tables[0] and self.huffman_tables[1] confer with the DC tables for luminance and chrominance respectively and self.huffman_tables[16] and self.huffman_tables[17] confer with the AC tables for luminance and chrominance respectively.

After we decode the bit-stream, we extract the brand new delta encoded DC coefficient utilizing the DecodeNumber operate and add the olddccoefficient to it to get the delta decoded DC coefficient.

After that, we repeat the identical decoding process however for the AC values within the quantization matrix. The code worth of 0 means that now we have encountered an Finish of Block (EOB) marker and we have to cease. Furthermore, the primary a part of the AC quant desk tells us what number of main 0’s now we have. Keep in mind the run-length encoding we talked about within the first half? That is the place that’s coming into play. We decode the run-length encoding and skip ahead that many bits. The skipped bits are all set to 0 implicitly within the IDCT class.

As soon as now we have decoded the DC and AC values for an MCU, we rearrange the MCU and undo the zigzag encoding by calling the rearrange_using_zigzag after which we carry out inverse DCT on the decoded MCU.

The BuildMatrix technique will return the inverse DCT matrix and the worth of the DC coefficient. Keep in mind, this inverse DCT matrix is just for one tiny 8×8 MCU (Minimal Coded Unit) matrix. We can be doing this for all the person MCUs in the entire picture file.

Displaying Picture on display screen

Let’s modify our code just a little bit and create a Tkinter Canvas and paint every MCU after decoding it within the StartOfScan technique.

def Clamp(col):
    col = 255 if col>255 else col
    col = 0 if col<0 else col
    return  int(col)

def ColorConversion(Y, Cr, Cb):
    R = Cr*(2-2*.299) + Y
    B = Cb*(2-2*.114) + Y
    G = (Y - .114*B - .299*R)/.587
    return (Clamp(R+128),Clamp(G+128),Clamp(B+128) )
  
def DrawMatrix(x, y, matL, matCb, matCr):
    for yy in vary(8):
        for xx in vary(8):
            c = "#%02xpercent02xpercent02x" % ColorConversion(
                matL[yy][xx], matCb[yy][xx], matCr[yy][xx]
            )
            x1, y1 = (x * 8 + xx) * 2, (y * 8 + yy) * 2
            x2, y2 = (x * 8 + (xx + 1)) * 2, (y * 8 + (yy + 1)) * 2
            w.create_rectangle(x1, y1, x2, y2, fill=c, define=c)


class JPEG:
    # -----
    def StartOfScan(self, information, hdrlen):
        information,lenchunk = RemoveFF00(information[hdrlen:])
        st = Stream(information)
        oldlumdccoeff, oldCbdccoeff, oldCrdccoeff = 0, 0, 0
        for y in vary(self.peak//8):
            for x in vary(self.width//8):
                matL, oldlumdccoeff = self.BuildMatrix(st,0, self.quant[self.quantMapping[0]], oldlumdccoeff)
                matCr, oldCrdccoeff = self.BuildMatrix(st,1, self.quant[self.quantMapping[1]], oldCrdccoeff)
                matCb, oldCbdccoeff = self.BuildMatrix(st,1, self.quant[self.quantMapping[2]], oldCbdccoeff)
                DrawMatrix(x, y, matL.base, matCb.base, matCr.base )    
        
        return lenchunk+hdrlen
      

if __name__ == "__main__":
    from tkinter import *
    grasp = Tk()
    w = Canvas(grasp, width=1600, peak=600)
    w.pack()
    img = JPEG('profile.jpg')
    img.decode()    
    mainloop()

Let’s begin with the ColorConversion and Clamp features. ColorConversion takes within the Y, Cr, and Cb values, makes use of a method to transform these values to their RGB counterparts, after which outputs the clamped RGB values. You may marvel why we’re including 128 to the RGB values. When you bear in mind, earlier than JPEG compressor applies DCT on the MCU, it subtracts 128 from the colour values. If the colours have been initially within the vary [0,255], JPEG places them into [-128,+128] vary. So now we have to undo that impact once we decode the JPEG and that’s the reason we’re including 128 to RGB. As for the Clamp, through the decompression, the output worth may exceed [0,255] so we clamp them between [0,255] .

Within the DrawMatrix technique, we loop over every 8×8 decoded Y, Cr, and Cb matrices and convert every component of the 8×8 matrices into RGB values. After conversion, we draw every pixel on the Tkinter canvas utilizing the create_rectangle technique. You’ll find the whole code on GitHub. Now if you happen to run this code, my face will present up in your display screen ?

Conclusion

Oh boy! Who would have thought it might take 6000 phrase+ rationalization for exhibiting my face on the display screen. I’m amazed by how good a few of these algorithm inventors are! I hope you loved this text as a lot as I loved writing it. I realized a ton whereas penning this decoder. I by no means realized how a lot fancy math goes into the encoding of a easy JPEG picture. I’d work on a PNG picture subsequent and take a look at writing a decoder for a PNG picture. You must also attempt to write a decoder for a PNG (or another format). I’m positive it can contain loads of studying and much more hex enjoyable ?

Both manner, I’m drained now. I’ve been gazing hex for much too lengthy and I believe I’ve earned a well-deserved break. You all take care and when you’ve got any questions please write them within the feedback beneath. I’m tremendous new to this JPEG coding journey however I’ll attempt to reply as a lot as I presumably can ?

Bye! ? ❤️

Additional studying

If you wish to delve into extra element, you may check out just a few useful resource I used whereas writing this text. I’ve additionally added some further hyperlinks for some attention-grabbing JPEG associated stuff: