7 ms·

Hi everyone! OP here. Why write another article on JPEG when there are already hundreds of articles on the internet? Well, normally when you read articles on J

by yasoob 6y ago

Hi everyone! OP here. Why write another article on JPEG when there are already hundreds of articles on the internet? Well, normally when you read articles on JPEG, the author just gives you details about what the format looks like. You don’t implement any code to do the actual decompression and decoding. Even if you do write code, it is in C/C++ and not accessible to a wide group of people. I tried to change that through this article. I give you a guided tour of JPEG encoding/decoding process and show you how it can be implemented in Python3. I mainly focus on decoding baseline encoded JPEG images.

voltagex_ 6y ago
I really really like this - especially with all the references you've listed. I think more programmers should have a go at working with various file formats. Well done on this article.
- yasoob 6y ago
  Thanks! And I completely agree with the idea that more programmers should have a go at working with various file formats. I learned so much about binary file layouts through this one project. Before writing this article I had no idea that JPEGs use Huffman tables. Now all those Huffman table lectures from college algos classes make sense. I was never told in that class that this is a major use case for Huffman tables. Maybe I would have shown more interest then if I knew this fact.
enriquto 6y ago
> Even if you do write code, it is in C/C++ and not accessible to a wide group of people. To be honest, writing a jpeg decoder in C seems easier and more natural than doing it in python.
- userbinator 6y ago
  As someone who has done it in C, I would both agree and disagree --- reading the file format will definitely be easier since C lets you pick bits/bytes/words/etc. off the stream directly, but on the other hand the high-level structures (looping, etc.) would probably be easier with Python. Overall, seeing as OP's Python implementation is less than 300 LoC while my C implementation was closer to 750, the Python might be easier. Then again, I followed the algorithms/flowcharts in the spec, which do a faster table-based Huffman decoding than the bit-by-bit of this Python version, and also implemented arbitrary(!) chroma subsampling as the spec allows, so it's not a direct comparison.
  - a_t48 6y ago
    Python also lets you read bytes off the stream directly.
  - smabie 6y ago
    Using Haskell and a parser combinator would probably be the easiest
    - enriquto 6y ago
      Easier for whom? Most programmers would not be able to follow that code. On the other hand, a really simple C or Python algorithm is more or less universally readable.
      - eru 6y ago
        It's not so much about the algorithm, but the parsing itself. Parser combinators give you one of the most straightforward ways to express parsers. You are right, that the language you express your parser combinators in vs the language you express an alternative solution in also will have an impact. You can in theory express parser combinators in Python. But it's gonna be a bit ugly, because Python has relatively clunky syntax for functions. Some people have tried writer parser combinator libraries for eg JavaScript. See https://github.com/GregRos/parjs https://github.com/GregRos/parjs I just found a parser combinator library for Python https://pypi.org/project/parsita/ https://pypi.org/project/parsita/ But it looks like they have to abuse some Python magic to make the code readable.
        enriquto 6y ago
        Alright, but jpeg decoding is nearly all algorithm, there's almost no parsing. Do you have a particular haskell jpeg decoder in mind that uses parser combinators?
        eru 6y ago
        No. But the author of the original comment mentioning Haskell https://news.ycombinator.com/item?id=23841865 https://news.ycombinator.com/item?id=23841865 might have had?
- pansa2 6y ago
  If you’re trying to describe a file format or algorithm in the most accessible way, wouldn’t pseudocode be the best thing to use? If that’s not an option (because you want the code to be executable), I think Python is the closest popular language to pseudocode.
  - kerkeslager 6y ago
    I think being executable is really key, because one way I check my understanding of code is to make modifications to the code and see if they do what I expect them to do.
    - pansa2 6y ago
      IMO the ideal setup would be for an article to contain pseudocode and to have supplementary executable code. This would allow the article to explain concepts without boilerplate and unnecessary details, but also ensure that those details are available for readers who wish to investigate further. I still think it's an advantage to write the executable code as close to pseudocode as possible. There is further discussion of pseudocode vs executable code at https://academia.stackexchange.com/q/140986 https://academia.stackexchange.com/q/140986.
      - kerkeslager 6y ago
        So, what elements of Python do you consider boilerplate? I say this not as someone defending Python, but as someone writing a programming language.
        smabie 6y ago
        Lack of function currying and anonymous function arguments. Also having to explicitly convert a zip, map, etc to a list. Also the lambda keyword.
        kerkeslager 6y ago
        Hmm, I think you're using the word "boilerplate" differently than it is usually used. The changes you're proposing are functional changes that can't be transparently applied by a compiler/interpreter without changing behavior. Currying is a subset of partial application, which Python supports via the standard library. Universal currying would be terser in some situations, but it conflicts with Python's args/kwargs implementation. Frankly, I don't think currying is a good thing even in languages such as Haskell where it doesn't conflict, as it makes it much less clear what the flow is when functions can be called with different signatures. Anonymous function arguments, I'm just not sure what you're talking about there. Explicitly converting higher order function results to lists is not boilerplate, it's a meaningful difference. The explicit conversion allows you to determine when code is actually executed, instead of having it executed eagerly. Universal lazy application like in Haskell has broader implications which are generally negative, particularly with regards to performance and being able to reason about execution: production Haskell often turns this off, and for good reason. The lambda keyword is arguably boilerplate, but I'm skeptical of whatever alternate syntax you're proposing there. C#-style anonymous functions wouldn't work with Python syntax. If you're proposing people use the λ symbol, I'm going to frankly say that's a bad idea, because most developers' keyboards don't have that symbol. Like it or not, English with a latin keyboard is the lingua franca of software--if you want to target another language that would be reasonable, but that's a big choice with broader implications.
userbinator 6y ago
It's great to see more people complete the "JPEG decoder challenge" --- and document it too. Have you read the official T.81 spec[1]? It is one of the easier standards to read, and it has flowcharts of all the algorithms which mean you can implement without really understanding the theory. As you mentioned there are lots of other articles about writing JPEG decoders, as well as for the other popular image formats GIF and PNG. What I haven't seen much of if at all, however, are articles about video decoding; if you're interested to try another challenge, I recommend a decoder for H.261: https://www.itu.int/rec/T-REC-H.261-199303-I/en https://www.itu.int/rec/T-REC-H.261-199303-I/en (I've written one --- in C --- and it is actually far simpler than JPEG in many ways, although it shares many similarities. A H.261 decoder in Python, with associated article, would definitely be very interesting to see, and AFAIK also a world-first!) [1] https://www.w3.org/Graphics/JPEG/itu-t81.pdf https://www.w3.org/Graphics/JPEG/itu-t81.pdf
- yasoob 6y ago
  Thanks for the H.261 decoder suggestion! I will actually seriously consider it because I am personally curious how video decoders work as well. I will make sure to document the process if I end up working on it.
  - jart 6y ago
    If you understand JPEG then you already understand the important bits of MPEG. It's also fun to study scaling and colorspaces. See https://justine.storage.googleapis.com/printimage.html https://justine.storage.googleapis.com/printimage.html and https://justine.storage.googleapis.com/printvideo.html https://justine.storage.googleapis.com/printvideo.html
- deepaksurti 6y ago
  And have more fun by doing the encoding/decoding on GPU [1] [1] https://github.com/CESNET/GPUJPEG https://github.com/CESNET/GPUJPEG
rohan1024 6y ago
This. I know C, C++ implementations are efficient but to see python implementation of this makes it lot easier to understand. > You don’t implement any code to do the actual decompression and decoding This is also true in case of face recognition. Nobody tells you internals and just tells you to use tools like OpenCV. Maybe it's too complicated but a post like OP's for face recognition would be a treat!
pjmlp 6y ago
Very good article, congratulations on doing it and choosing a more approachable language as well.
cgrealy 6y ago
> Even if you do write code, it is in C/C++ and not accessible to a wide group of people. Eh?? There are literally millions of C++ programmers and high quality C++ compilers are available on almost every platform for free. How is that “not accessible”?
- smcl 6y ago
  Equally there are millions who don't use C or C++. I think it’s pretty fair to describe this as a "wide group of people" who would consider C or C++ inaccessible.
  - cgrealy 6y ago
    That’s a nonsense argument. For any given programming language, the number of people not using it outweighs the number of people using it by several orders of magnitude. It’s hard to get accurate numbers, but a quick google estimates there is roughly double the number of Python programmers than C++ programmers. I find it very difficult to imagine there isn’t some overlap there and even more difficult to imagine a competent Python programmer looking at C++ code and being completely unable to read it.
    - smcl 6y ago
      There is definitely a substantial number of people who know Python and have had little to no exposure to C or C++. To the point where they'd really rather see something like this presented in a language they're familiar with and that they can try out in an environment they've already got setup. There's no harm in having many articles on a given subject (think how many monad posts there are) - if you dislike one you don't have to read it, there's plenty of other interesting stuff out there :-)
      - cgrealy 6y ago
        I don't have a problem with someone writing an article on whatever for whatever language. Go nuts. I just think saying "articles written in C++ are inaccessible" is kinda dumb.
mehh 6y ago
Very cool! It's not that far off going for an MPEG-2 video decoder next, highly recommend (a long time since I did, so take with a pinch of salt). That would be great to see in python to make that realm more accessible.
bhhaskin 6y ago
This is a cool article. I have always wondered the internals of JPEG and this has lots of details. Just as an FYI it should be a "Show HN:". Edit: NVM! I didn't realize you didn't post this.

by yasoob 6y ago

voltagex_ 6y ago

I really really like this - especially with all the references you've listed. I think more programmers should have a go at working with various file formats. Well done on this article.

yasoob 6y ago
Thanks! And I completely agree with the idea that more programmers should have a go at working with various file formats. I learned so much about binary file layouts through this one project. Before writing this article I had no idea that JPEGs use Huffman tables. Now all those Huffman table lectures from college algos classes make sense. I was never told in that class that this is a major use case for Huffman tables. Maybe I would have shown more interest then if I knew this fact.

enriquto 6y ago

> Even if you do write code, it is in C/C++ and not accessible to a wide group of people. To be honest, writing a jpeg decoder in C seems easier and more natural than doing it in python.

userbinator 6y ago
As someone who has done it in C, I would both agree and disagree --- reading the file format will definitely be easier since C lets you pick bits/bytes/words/etc. off the stream directly, but on the other hand the high-level structures (looping, etc.) would probably be easier with Python. Overall, seeing as OP's Python implementation is less than 300 LoC while my C implementation was closer to 750, the Python might be easier. Then again, I followed the algorithms/flowcharts in the spec, which do a faster table-based Huffman decoding than the bit-by-bit of this Python version, and also implemented arbitrary(!) chroma subsampling as the spec allows, so it's not a direct comparison.
- a_t48 6y ago
  Python also lets you read bytes off the stream directly.
- smabie 6y ago
  Using Haskell and a parser combinator would probably be the easiest
  - enriquto 6y ago
    Easier for whom? Most programmers would not be able to follow that code. On the other hand, a really simple C or Python algorithm is more or less universally readable.
    - eru 6y ago
      It's not so much about the algorithm, but the parsing itself. Parser combinators give you one of the most straightforward ways to express parsers. You are right, that the language you express your parser combinators in vs the language you express an alternative solution in also will have an impact. You can in theory express parser combinators in Python. But it's gonna be a bit ugly, because Python has relatively clunky syntax for functions. Some people have tried writer parser combinator libraries for eg JavaScript. See https://github.com/GregRos/parjs https://github.com/GregRos/parjs I just found a parser combinator library for Python https://pypi.org/project/parsita/ https://pypi.org/project/parsita/ But it looks like they have to abuse some Python magic to make the code readable.
      - enriquto 6y ago
        Alright, but jpeg decoding is nearly all algorithm, there's almost no parsing. Do you have a particular haskell jpeg decoder in mind that uses parser combinators?
        eru 6y ago
        No. But the author of the original comment mentioning Haskell https://news.ycombinator.com/item?id=23841865 https://news.ycombinator.com/item?id=23841865 might have had?
pansa2 6y ago
If you’re trying to describe a file format or algorithm in the most accessible way, wouldn’t pseudocode be the best thing to use? If that’s not an option (because you want the code to be executable), I think Python is the closest popular language to pseudocode.
- kerkeslager 6y ago
  I think being executable is really key, because one way I check my understanding of code is to make modifications to the code and see if they do what I expect them to do.
  - pansa2 6y ago
    IMO the ideal setup would be for an article to contain pseudocode and to have supplementary executable code. This would allow the article to explain concepts without boilerplate and unnecessary details, but also ensure that those details are available for readers who wish to investigate further. I still think it's an advantage to write the executable code as close to pseudocode as possible. There is further discussion of pseudocode vs executable code at https://academia.stackexchange.com/q/140986 https://academia.stackexchange.com/q/140986.
    - kerkeslager 6y ago
      So, what elements of Python do you consider boilerplate? I say this not as someone defending Python, but as someone writing a programming language.
      - smabie 6y ago
        Lack of function currying and anonymous function arguments. Also having to explicitly convert a zip, map, etc to a list. Also the lambda keyword.
        kerkeslager 6y ago
        Hmm, I think you're using the word "boilerplate" differently than it is usually used. The changes you're proposing are functional changes that can't be transparently applied by a compiler/interpreter without changing behavior. Currying is a subset of partial application, which Python supports via the standard library. Universal currying would be terser in some situations, but it conflicts with Python's args/kwargs implementation. Frankly, I don't think currying is a good thing even in languages such as Haskell where it doesn't conflict, as it makes it much less clear what the flow is when functions can be called with different signatures. Anonymous function arguments, I'm just not sure what you're talking about there. Explicitly converting higher order function results to lists is not boilerplate, it's a meaningful difference. The explicit conversion allows you to determine when code is actually executed, instead of having it executed eagerly. Universal lazy application like in Haskell has broader implications which are generally negative, particularly with regards to performance and being able to reason about execution: production Haskell often turns this off, and for good reason. The lambda keyword is arguably boilerplate, but I'm skeptical of whatever alternate syntax you're proposing there. C#-style anonymous functions wouldn't work with Python syntax. If you're proposing people use the λ symbol, I'm going to frankly say that's a bad idea, because most developers' keyboards don't have that symbol. Like it or not, English with a latin keyboard is the lingua franca of software--if you want to target another language that would be reasonable, but that's a big choice with broader implications.

userbinator 6y ago

It's great to see more people complete the "JPEG decoder challenge" --- and document it too. Have you read the official T.81 spec[1]? It is one of the easier standards to read, and it has flowcharts of all the algorithms which mean you can implement without really understanding the theory. As you mentioned there are lots of other articles about writing JPEG decoders, as well as for the other popular image formats GIF and PNG. What I haven't seen much of if at all, however, are articles about video decoding; if you're interested to try another challenge, I recommend a decoder for H.261: https://www.itu.int/rec/T-REC-H.261-199303-I/en https://www.itu.int/rec/T-REC-H.261-199303-I/en (I've written one --- in C --- and it is actually far simpler than JPEG in many ways, although it shares many similarities. A H.261 decoder in Python, with associated article, would definitely be very interesting to see, and AFAIK also a world-first!) [1] https://www.w3.org/Graphics/JPEG/itu-t81.pdf https://www.w3.org/Graphics/JPEG/itu-t81.pdf

yasoob 6y ago
Thanks for the H.261 decoder suggestion! I will actually seriously consider it because I am personally curious how video decoders work as well. I will make sure to document the process if I end up working on it.
- jart 6y ago
  If you understand JPEG then you already understand the important bits of MPEG. It's also fun to study scaling and colorspaces. See https://justine.storage.googleapis.com/printimage.html https://justine.storage.googleapis.com/printimage.html and https://justine.storage.googleapis.com/printvideo.html https://justine.storage.googleapis.com/printvideo.html
deepaksurti 6y ago
And have more fun by doing the encoding/decoding on GPU [1] [1] https://github.com/CESNET/GPUJPEG https://github.com/CESNET/GPUJPEG

rohan1024 6y ago

This. I know C, C++ implementations are efficient but to see python implementation of this makes it lot easier to understand. > You don’t implement any code to do the actual decompression and decoding This is also true in case of face recognition. Nobody tells you internals and just tells you to use tools like OpenCV. Maybe it's too complicated but a post like OP's for face recognition would be a treat!

pjmlp 6y ago

Very good article, congratulations on doing it and choosing a more approachable language as well.

cgrealy 6y ago

> Even if you do write code, it is in C/C++ and not accessible to a wide group of people. Eh?? There are literally millions of C++ programmers and high quality C++ compilers are available on almost every platform for free. How is that “not accessible”?

smcl 6y ago
Equally there are millions who don't use C or C++. I think it’s pretty fair to describe this as a "wide group of people" who would consider C or C++ inaccessible.
- cgrealy 6y ago
  That’s a nonsense argument. For any given programming language, the number of people not using it outweighs the number of people using it by several orders of magnitude. It’s hard to get accurate numbers, but a quick google estimates there is roughly double the number of Python programmers than C++ programmers. I find it very difficult to imagine there isn’t some overlap there and even more difficult to imagine a competent Python programmer looking at C++ code and being completely unable to read it.
  - smcl 6y ago
    There is definitely a substantial number of people who know Python and have had little to no exposure to C or C++. To the point where they'd really rather see something like this presented in a language they're familiar with and that they can try out in an environment they've already got setup. There's no harm in having many articles on a given subject (think how many monad posts there are) - if you dislike one you don't have to read it, there's plenty of other interesting stuff out there :-)
    - cgrealy 6y ago
      I don't have a problem with someone writing an article on whatever for whatever language. Go nuts. I just think saying "articles written in C++ are inaccessible" is kinda dumb.

mehh 6y ago

Very cool! It's not that far off going for an MPEG-2 video decoder next, highly recommend (a long time since I did, so take with a pinch of salt). That would be great to see in python to make that realm more accessible.

bhhaskin 6y ago

This is a cool article. I have always wondered the internals of JPEG and this has lots of details. Just as an FYI it should be a "Show HN:". Edit: NVM! I didn't realize you didn't post this.