Understanding and Decoding a JPEG Picture utilizing Python

Hello everybody! 👋 At this time we’re going to perceive the JPEG compression algorithm. One factor lots of people don’t know is that JPEG is just not a format however reasonably an algorithm. The JPEG photographs you see are principally within the JFIF format (JPEG File Interchange Format) that internally makes use of the JPEG compression algorithm. By the tip of this text, you’ll have a a lot 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 reasonably solely the essential baseline format whereas writing our decoder.

Introduction

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

Totally 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 will likely be exploring every phase. You may need to seek advice from this picture fairly a couple of occasions whereas studying this tutorial.

On the very fundamental stage, virtually each binary file comprises a few markers (or headers). You’ll be able to consider these markers as type of like bookmarks. They’re very essential for making sense of a file and are utilized by packages like file (on Mac/Linux) to inform us particulars a few file. These markers outline the place some particular data in a file is saved. Many of the markers are adopted by size data for the actual marker phase. This tells us how lengthy that specific phase 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 we have now reached the tip of a picture file. Each marker, apart from FFD0 to FFD9 and FF01, is straight away adopted by a size specifier that gives you the size of that marker phase. As for the picture file begin and picture file finish markers, they are going to all the time be two bytes lengthy every.

All through this tutorial, we will likely be working with this picture:

Let’s write some code to establish 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 sort 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 measurement 2 so we offer unpack two bytes from our img_data. You would possibly ask your self how we knew it was a brief. Properly, we all know that the markers in JPEG are 4 hex digits: ffd8. One hex digit equals 4 bits (¹⁄₂ 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 we have now the essential framework in place, let’s transfer on and determine what the remainder of the picture information comprises. We’ll undergo some obligatory principle first after which get all the way down to coding.

Encoding a JPEG

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

Regardless that the picture beneath gained’t imply a lot to you proper now, it gives you 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 House

Based on the JPEG spec (ISO/IEC 10918-6:2013 (E), part 6.1):

• Photos encoded with just one part are assumed to be grayscale information during which 0 is black and 255 is white.
• Photos encoded with three parts are assumed to be RGB information encoded as YCbCr until the picture comprises an APP14 marker phase as laid out in 6.5.3, during which case the colour encoding is taken into account both RGB or YCbCr in response to the applying information of the APP14 marker phase. The connection between RGB and YCbCr is outlined as laid out in Rec. ITU-T T.871 | ISO/IEC 10918-5.
• Photos encoded with 4 parts are assumed to be CMYK, with (0,0,0,0) indicating white until the picture comprises an APP14 marker phase as laid out in 6.5.3, during which case the colour encoding is taken into account both CMYK or YCCK in response to the applying information of the APP14 marker phase. 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 a substitute of RGB. That is tremendous helpful in JPEG because the human eye is fairly dangerous at seeing high-frequency brightness adjustments over a small space so we are able to basically scale back the quantity of frequency and the human eye gained’t have the ability to inform the distinction. Outcome? A extremely compressed picture with virtually no seen discount in high quality.

Identical to every pixel in RGB coloration area is made up of three bytes of coloration information (Pink, Inexperienced, Blue), every pixel in YUV makes use of 3 bytes as properly however what every byte represents is barely completely different. The Y part determines the brightness of the colour (additionally known as luminance or luma), whereas the U and V parts decide the colour (also called chroma). The U part refers back to the quantity of blue coloration and the V part refers back to the quantity of pink coloration.

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

Discrete Cosine Rework & Quantization

JPEG converts a picture into chunks of 8×8 blocks of pixels (known as MCUs or Minimal Coding Items), adjustments the vary of values of the pixels in order that they middle 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 but it surely is sensible 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 how you can reproduce it utilizing an 8×8 matrix of cosine capabilities. Learn extra right here)

The 8×8 matrix of cosine capabilities seem like this:

We apply DCT to every part 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 perform (out of 64 complete capabilities) contributes to the 8×8 enter matrix. The coefficient matrix of a DCT usually comprises 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 perform and the underside proper represents the very best frequency cosine perform.

What this tells us is that the majority photographs comprise 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 dangerous 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 up to now we haven’t finished something lossy. We’ve solely remodeled 8×8 blocks of YUV parts into 8×8 blocks of cosine capabilities 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. While you save a picture utilizing JPEG, most picture modifying packages 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 possibly can’t recreate the precise unique picture from the ensuing JPEG picture.

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

In case you have this DCT matrix:

This (widespread) Quantization matrix:

Then the ensuing quantized matrix will likely be this:

Regardless that people can’t see high-frequency data, in case you 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 had been to take the DC values from all of the quantized matrices and generated a brand new picture, we’ll basically find yourself with a thumbnail with 1/eighth decision of the unique picture.

It’s also essential to notice that as a result of we apply quantization whereas decoding, we should ensure the colours fall within the [0,255] vary. In the event that they fall exterior this vary, we should 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 we have now this quantized matrix:

The output of zig-zag encoding will likely be this:

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

This encoding is most well-liked as a result of a lot of the low frequency (most important) data is saved in the beginning of the matrix after quantization and the zig-zag encoding shops all of that in the beginning 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 a lot of the zig-zag encoded 1D arrays had so many 0s on the finish. Run-length encoding permits us to reclaim all that wasted area and use fewer bytes to characterize all of these 0s. Think about you’ve some information like this:

10 10 10 10 10 10 10

Run-length encoding will convert it into:

7 10

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

Delta encoding is a way used to characterize a byte relative to the byte earlier than it. It’s simpler to know this with an instance. Let’s say you’ve 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. Because of this in case you change the very first DCT coefficient of your picture, the entire picture will get screwed up however in case you modify the primary worth of the final DCT matrix, solely a really tiny a part of your picture will likely 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 convey the remainder of DC values near 0 and that leads to 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 must retailer this textual content:

a b c d e

In a standard situation every character would take up 1 byte of area:

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

That is based mostly on ASCII to binary mapping. However what if we may give you 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 method fewer bits:

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

That is all properly and good however what if we need to take even much less area? What if we had 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 type 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 informed you that utilizing delta encoding for DC values helps in Huffman Encoding? I hope you possibly can see why now. After delta encoding, we find yourself with fewer “characters” to map and the entire measurement of our Huffman tree is decreased.

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

A JPEG comprises 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 comprises solely the DC values from the zig-zag tables and the opposite comprises the AC values from the zig-zag tables. Because of this in our decoding, we should merge the DC and AC values from two separate matrices. The DCT data for the luminance and chrominance channel is saved individually so we have now 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 might have solely 2 Huffman tables (1 for DC and 1 for AC) as a result of we don’t care in regards to the coloration. As you possibly can already think about, 2 photographs 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 comprises. 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 response to the usual, baseline will comprise the sequence of 8×8 blocks proper subsequent to one another. The opposite compression codecs structure the info a bit in a different 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:

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

Suppose you’ve a DH desk much like this (src):

It is going to 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 any Huffman code of size 1. 1 means that there’s 1 Huffman code of size 2. And so forth. There are all the time 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        

In the event 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, factor, pos):
        if isinstance(root,record):
            if pos==0:
                if len(root)<2:
                    root.append(factor)
                    return True                
                return False
            for i in [0,1]:
                if len(root) == i:
                    root.append([])
                if self.BitsFromLengths(root[i], factor, 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, record):
            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 record. This record comprises nested lists and represents a binary tree. You’ll be able to learn on-line how a Huffman Tree works and how you can create your personal Huffman tree information construction in Python. For our first DHT (utilizing the picture I linked at the beginning of this tutorial) we have now the next information, lengths, and components:

Hex Information: 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 record will comprise this information:

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

The HuffmanTable additionally comprises the GetCode methodology that traverses the tree for us and offers us again the decoded bits utilizing the Huffman desk. This methodology expects a bitstream as an enter. A bitstream is simply the binary illustration of knowledge. For instance, a typical bitstream of abc will likely 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 permit us to transform a string into bits and browse the bits one after the other. That is how we’ll 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 comprises the next information:

Based on 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 lengthen the code we have already got and add the power to decode quantization tables as properly:

def GetArray(sort,l, size):
    s = ""
    for i in vary(size):
        s =s+sort
    return record(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 methodology. It’s only a helpful methodology for decoding a variable variety of bytes from binary information. I changed some code in decodeHuffman methodology to utilize this new perform as properly. After that, I outlined the DefineQuantizationTables methodology. This methodology 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 will likely be 0 for luminance and 1 for chrominance. Every Quantization Desk part within the JFIF comprises 64 bytes of QT information (for our 8×8 Quantization matrix).

If we print the quantization matrices for our picture. They’ll seem like 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 comprises the next data (src):

Out of this information we solely care about a couple of issues. We’ll extract the picture width and peak and the quantization desk variety of every part. The width and peak will likely be used after 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 part 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("measurement %ixpercenti" % (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 record attribute to our JPEG class and launched a BaselineDCT methodology. The BaselineDCT methodology decodes the required information from the SOF part and places the quantization desk numbers of every part within the quantMapping record. We’ll make use of this mapping as soon as we begin studying the Begin of Scan part. That is what the quantMapping seems like for our picture:

Quant mapping:  [0, 1, 1]

Decoding Begin of Scan

Candy! We solely have yet another part left to decode. That is the meat of a JPEG picture and comprises the precise “picture” information. That is additionally essentially the most concerned step. Every little thing else we have now decoded up to now will be considered making a map to assist us navigate and decode the precise picture. This part comprises the precise picture itself (albeit in an encoded type). We’ll learn this part and use the info we have now already decoded to make sense of the picture.

All of the markers we have now seen up to now begin with 0xff. 0xff will be a part of the picture scan information as properly but when 0xff is current within the scan information, it would all the time be proceeded by 0x00. That is one thing a JPEG encoder does routinely and known as byte stuffing. It’s the decoder’s responsibility to take away this continuing 0x00. Let’s begin the SOS decoder methodology with this perform 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 tip of the file every time I encountered the 0xffda marker however now that we have now 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 perform merely breaks every time it observer one thing aside from 0x00 after 0xff. Due to this fact, it would escape of the loop when it encounters 0xffd9, and that method we are able to safely search to the tip of the file with none surprises. In the event 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 following 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 keep in mind we talked about how the DC factor in a quantization matrix (the primary factor of the matrix) is delta encoded relative to the earlier DC factor? It will assist us hold monitor of the worth of the earlier DC components and 0 would be the default after we encounter the primary DC factor.

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 in brief 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 perform.

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

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’ll rearrange the MCU matrix by undoing the zigzag encoding by way of the rearrange_using_zigzag methodology. Lastly, we’ll undo the Discrete Cosine Transformation by calling the perform_IDCT methodology.

In the event you keep in mind, the Discrete Cosine desk is fastened. How the precise calculation for a DCT works is exterior the scope of this tutorial as it’s extra maths than programming. We are able to retailer this desk as a world 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 factor of the rearranged MCU matrix is multiplied by the values of the idc_variable and we finally get again the Y, Cr, and Cb values.

It will make extra sense as soon as we write down the BuildMatrix methodology.

In the event 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 possibly can 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 would consequence on this output:

Now let’s end up our BuildMatrix methodology:

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] seek advice from the DC tables for luminance and chrominance respectively and self.huffman_tables[16] and self.huffman_tables[17] seek advice from 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 perform 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 we have now 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 we have now. 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 we have now 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 methodology 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 will likely be doing this for all the person MCUs in the entire picture file.

Displaying Picture on display

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

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 capabilities. 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 would possibly marvel why we’re including 128 to the RGB values. In the event you keep in mind, earlier than JPEG compressor applies DCT on the MCU, it subtracts 128 from the colour values. If the colours had been initially within the vary [0,255], JPEG places them into [-128,+128] vary. So we have now to undo that impact after we decode the JPEG and that’s the reason we’re including 128 to RGB. As for the Clamp, in the course of the decompression, the output worth would possibly exceed [0,255] so we clamp them between [0,255] .

Within the DrawMatrix methodology, we loop over every 8×8 decoded Y, Cr, and Cb matrices and convert every factor of the 8×8 matrices into RGB values. After conversion, we draw every pixel on the Tkinter canvas utilizing the create_rectangle methodology. Yow will discover the entire code on GitHub. Now in case you run this code, my face will present up in your display 😄

Conclusion

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

Both method, I’m drained now. I’ve been looking at hex for a lot too lengthy and I feel I’ve earned a well-deserved break. You all take care and you probably have 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 possibly can check out a couple of useful resource I used whereas writing this text. I’ve additionally added some further hyperlinks for some attention-grabbing JPEG associated stuff: