Understanding and writing a JPEG decoder in Python
yasoob.me
yasoob.me
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.
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
(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!)
To be honest, writing a jpeg decoder in C seems easier and more natural than doing it in 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.
If you just want to present a working implementation, both C and Python can express readable versions.
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
I just found a parser combinator library for Python https://pypi.org/project/parsita/ But it looks like they have to abuse some Python magic to make the code readable.
If that’s not an option (because you want the code to be executable), I think Python is the closest popular language to pseudocode.
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.
I say this not as someone defending Python, but as someone writing a programming language.
Similarly, executable code requires unnecessary detail, like the article’s `Stream` class. In pseudocode this could be replaced by simply saying “get the next N bits”.
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.
Scala's method for dealing with laziness through views and iterators works really well.
Why? What problem are you trying to solve here?
That syntax is inconsistent with other syntax in Python and is harder to type (lambda gets tab-completed after typing two home-row characters).
> Scala's method for dealing with laziness through views and iterators works really well.
If you're okay with generic iterables in Scala, I'm unsure what your objection to iter types in Python is.
map, filter, zip, etc should produce concrete values, not iterators. It's annoying to constantly turn iterators into lists. Like if scala's map or fold took in a list and produced an iterator, that would be super annoying. There's no point. If you want an iterator, turn the collection into an iterator. There's no reason for a function to take a list and return an iterator, unless that function is 'toIter.'
Ugly python:
list(map(lambda x: 2*x, [1, 2, 3, 4]))
map(x -> 2*x, [1, 2, 3, 4])
2*.[1, 2, 3, 4]
Beware of people who say "there's a reason" and then don't say what that reason is.
I suspect the reason in this case is that languages which use C-ish syntax it would make no senes to have lambda as a keyword. Python doesn't use C-ish syntax, so that reason doesn't apply.
> It's annoying to constantly turn iterators into lists.
So don't. Why are you constantly turning iterators into lists?
> There's no reason for a function to take a list and return an iterator,
Here are 5 reasons:
1. There are many cases where the iterator will never be evaluated, meaning you save O(n) time.
2. Even in cases where you evaluate the iterator, you'll often have performed many transformations upon that iterator. Forcing 5 transformations all at once means you have 1 loop instead of 5, meaning again you save O(n) time.
3. It encourages writing functional code, which doesn't depend on order of execution. (This is why Simon Peyton Jones says Haskell has lazy evaluation: it keeps them honest about side effects).
4. Explicit is better than implicit. Guessing that a user will want a list is a reasonable guess, but you're doing a lot of work based on that guess, and some percentage of the time you'll be wrong. It's better to do the minimum work necessary and let the user explicitly determine what type of result they want.
5. Consistent extensibility: map, zip, etc. take lots of iterable types. You could attempt to return the same iterable type as you receive, but then there isn't an easy way for users to use zip on user-defined types. It's better to call the type's __iter__ function and then just use that, as this allows users to define higher-order functions on their own types.
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.
Edit: NVM! I didn't realize you didn't post this.
> 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!
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.
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”?
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.
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 :-)
I just think saying "articles written in C++ are inaccessible" is kinda dumb.
I first learned the general ideas from this Computerphile video
https://www.youtube.com/watch?v=n_uNPbdenRs
While we're on it does anyone know of articles/videos that go into similar detail for HEVC?
One small note - the first image you mention that we'll need to reference is a bit small to read. Zooming in on the page does not zoom it in due to format of the page. I had to right click -> View image, in a separate tab in order to be able to zoom in enough to read the righthand side of it. edit: this is on the latest version of Firefox