search

nayuki / QR-Code-generator

High-quality QR Code generator library in Java, TypeScript/JavaScript, Python, Rust, C++, C.
https://www.nayuki.io/page/qr-code-generator-library
5.19k stars 1.11k forks source link

Feature Request: Please consider expanding project scope to include decoding #1

Closed bidafiwoc closed 8 years ago

bidafiwoc commented 8 years ago

First off, I really like what you've done with your QR-code-generator project.

I came across your work while searching (web + GH + BB) for pure python-based programs to handle QR code decoding / encoding. Much as you describe in your writeup [1], I found a lot of projects with sub-optimal dev choices---too many external dependencies, insufficient documentation (internal comments and external manuals / examples), incomplete or unfaithful compliance with Denso-Wave and ISO/IEC 18004 standards (models 1&2)---some don't even implement Reed-Solomon. Anyway, kudos to you for a really clean and concise project:

In short, thanks for what you've shared with the O/S community here.

All that being said, I hope to motivate you to please consider expanding your project to include decoding of QR-Codes. If anything, there's an even more limited ecosystem of open-source QR-code decoders, compared to that of QR-Code encoders. In the python world, at least, there's pretty much only ZBar (or a multitude of projects which depend upon it); and ZBar's last stable release was in 2009, with no code checkins since 2012 (and it doesn't support modern Python). Of course, there's also a Python port of ZXing (from native Java), but ZXing is a large (~70k LOC!), all-encompassing framework. While there are obviously additional decoders in your other target languages (JS, Java, C++), I believe there are similarly fewer choices there, compared to the situation with encoders.

Given what I can sense of your philosophy with this project, I assume you'd consider any type of QR-code image manipulation (necessary for "full-stack" decoding from the analog world) to be well outside of scope, and I'm not suggesting otherwise as part of this feature request: scope would still exclude image capture, deskewing / perspective-correction / contrast-tuning, and (finally) conversion of pixels into a vector QR-code (ie, SVG). For example, just as you provide the 'to_svg_str()' function in your QRCode class as the final output stage (after which user-code takes over to otherwise manipulate QR codes), perhaps the appropriate scope to accept input for decoding would be a similar 'from_svg_str()' function, or just a logical 2D numeric array (representing input to be decoded). This would leave all bitmap->vector image manipulation external to your library, and instead in user-supplied code (through custom libraries, PIL/imagemagick, opencv3, etc).

I look forward to your consideration of this feature request, though it significantly expands the scope of your library. If it's beyond the itch you're proverbially scratching here, I'll continue to enjoy using your library for encoding only.

Thanks, and best wishes for continued success with this (and other) projects!

[1] https://www.nayuki.io/page/qr-code-generator-library

nayuki commented 8 years ago

Hello bidafiwoc and thank you for your gracious, well-explained feedback. I appreciate the time you took to include all the important details and make a really polished write-up. =)

Response to miscellaneous topics:

(web + GH + BB)

De-acronymized as (web + GitHub + Bitbucket). When I was scouting for competitors, I searched Google and PyPI.

Denso-Wave and ISO/IEC 18004 standards (models 1&2)

I implemented Model 2 and I think everybody else did the same. I have read the Model 1 section described in the ISO specification out of curiosity, but are there any libraries out there that actually implement it?

some don't even implement Reed-Solomon

I wonder what this means? If a QR code blanks out all the Reed-Solomon ECC codewords, then it won't be decodable by a conventional RS decoder (you'd have to force it to accept the data as-is and ignore all the ECC bytes). Did you mean that they offload the RS encoding to some other library?

If it's beyond the itch you're proverbially scratching here, I'll continue to enjoy using your library for encoding only.

Are you building an application that needs to encode and decode QR codes, if I may ask?

nayuki commented 8 years ago

Now onto the main question - will I build a QR Code decoder?

Maybe, perhaps. Currently I am missing the understanding of one critical piece of the puzzle, which is Reed-Solomon ECC decoding and the Berlekamp-Massey algorithm. I started reading about this ~5 years ago but haven't gotten anywhere. It would be great if I understood it, because then I can implement the algorithm compactly, handle things like value ranges and overflow correctly, and build strong guarantees about what the algorithm can and can't do.

Your words are quite encouraging! It looks like you've done your research and discovered a noticeable lack of choices in QR Code decoders in terms of languages, code size, etc. If I come to the conclusion that I can make a meaningful and high quality contribution to the set of open-source QR decoders, I would probably do it. I'd even borrow a Berlekamp-Massey algorithm just to make the product work and earmark it for future overhaul once I understand the math behind it.

Rest assured, I would actually take a full-stack approach to QR decoding. Though I wouldn't build the camera app, I would handle all the backend data processing starting from an image raster: recognition of finder patterns, inverse perspective transform, contrast adjustment, pixel snapping, and then all the actual QR decoding procedure with bit scanning and ECC decoding. Although I don't have experience implementing software that covers the first 4 messy analog-ish steps, I think I can implement reasonable heuristics to operate on general (but not pathological) images. Still, the Reed-Solomon Berlekamp-Massey stuff worries me, and I'll have to figure out how to address that problem before I could start working on this project idea.

bidafiwoc commented 8 years ago

Hi @nayuki,

Thanks for your inclusive, expeditious reply above. Sorry for delay in my response now --- busy with work during the week, and needed a bunch of time to aggregate the situation more fully for you (see below) across all four languages of preference.

Responding first to miscellaneous topics:

I implemented Model 2 and I think everybody else did the same. I have read the Model 1 section described in the ISO specification out of curiosity, but are there any libraries out there that actually implement it?

I'm not sure: I found one codebase (by @metaxm, see below) that claimed it was "Version 1" only, which makes little sense to me if one interprets that strictly according to QR-Code's meaning of "version"; perhaps the developer actually meant "Model 1". However, all code comments were in Chinese, so I couldn't easily tell.

some don't even implement Reed-Solomon

I wonder what this means? If a QR code blanks out all the Reed-Solomon ECC codewords, then it won't be decodable by a conventional RS decoder (you'd have to force it to accept the data as-is and ignore all the ECC bytes). Did you mean that they offload the RS encoding to some other library?

Your point is completely valid, which is why I was so surprised to find libraries that made the claim as to not implementing RS ECC. (I'm not referring to those that used external RS libraries, as that's a completely valid engineering decision.) See packages listed below by @vsergeev and @allenywang (though, please note that I did not explicitly examine the codebase, but just relied upon developer comments in 'README' files). Perhaps they are academic coding exercises.

Are you building an application that needs to encode and decode QR codes, if I may ask?

Yes, exactly (smartphone space). In the absence of QR-Codes, users can just enter information manually in order to exchange info between devices (use-case scenario cannot assume wifi/cell back-haul network connectivity to cloud in order to serve as intermediary). That's a bit tedious and quite error prone (even for relatively small amounts of information), but always doable if absolutely need-be.

Your existing QR-Code generator definitely gets me (at least) half-way to a real solution!

Your words are quite encouraging! It looks like you've done your research and discovered a noticeable lack of choices in QR Code decoders in terms of languages, code size, etc.

Thank you. Given that I'm requesting such a significant increase in scope, doing my part in terms of background investigation seems the least of it. I spent some more time this weekend to provide a much more comprehensive examination of all decoders I could (reasonably) identify online. I'll follow-up this response with another one that lists all of them, organized somewhat hierarchically, alongside some of my notes on pros/cons for the more important packages.

Rest assured, I would actually take a full-stack approach to QR decoding. Though I wouldn't build the camera app, I would handle all the backend data processing starting from an image raster: recognition of finder patterns, inverse perspective transform, contrast adjustment, pixel snapping, and then all the actual QR decoding procedure with bit scanning and ECC decoding.

That would be wonderful! Full-stack (especially with few to no external dependencies for image manipulation) is a real boon.

On the topic of analog -> digital pre-decoding conversions, I came across the following academic reference which might be helpful:

Also, here's a collection of QR-Codes (with problems in analog domain) to stress-test analog -> digital reliability:

Still, the Reed-Solomon Berlekamp-Massey stuff worries me, and I'll have to figure out how to address that problem before I could start working on this project idea.

Understood. If it helps, here are some nice references that I came across:

The wikiversity write-up (and tomerfiliba's associated code with comments) seem particularly beneficial for RS decoding. Further, if it might prove helpful, here are three external RS decoding libraries I identified, while searching for QR code decoders:

Take care, Bida

(until I post my next reply with full listing of identified packages...)

bidafiwoc commented 8 years ago

@nayuki,

I tried to conduct a fairly comprehensive search for all QR decoders in the four languages you currently include in your codebase (Java, C, Javascript, and Python). I even included a few close-source / proprietary packages (of absolutely no interest to me, nor, I would assume, you) that I happened to stumble across. In all, I examined close to 100 packages.

While reasonable people might disagree as to which codebases among these are the most meaningful, I would highlight four:

I choose these primarily as they are the original "upstream" decoders (ie, not ports of or wrappers around other decoding frameworks), and they have some level of acceptance or recognition by the community. (Should I have relaxed the "upstream" constraint, for example, @LazarSoft's port of ZXing to JavaScript would likely have been added to this list, given how popular it seems [even though it has apparently been abandoned since 2014]. Should I have relaxed the constraint that there be some level of community receptiveness, I might also have included the other QrCode in C, by @qsantos [abandoned as well, back in 2013]).

I find it quite surprising that, among all four (or even six) of these, only one single package (ZXing) is undoubtedly still in active development, while two others are long abandoned (2007 and 2009) and the fourth is in an unclear state of continuation. Not particularly auspicious for the community of QR decoders...

Now, for your further reference, here's the full list of packages I examined to make the above judgments:

JavaScript Decoders / Scanners:

C or C++ Decoders / Scanners:

Java Decoders / Scanners:

Python Decoders / Scanners:

Please excuse any errors in notes, or oversights in missing (or miscategorized) packages.

bidafiwoc commented 8 years ago

@nayuki

After posting the above full list of QR-Code decoders, along with my extracted preference for the four most important packages (only a single one of which is unambiguously still actively developed), I'm surprised to discover that the QR decoding ecosystem is even more sparsely populated with strong, independent code bases, than I had imagined in my first post here (at which point, I had only examined Python code bases).

Anyway, I'll look forward to your consideration of helping to ameliorate this scenario, and wish you the best regardless.

Incidentally, should it be helpful to you, please feel free to repurpose anything I've written in this issue for your own needs --- I hereby release it into public-domain, via Creative-Commons CC0.

Hope this helps, in some way, and take care, Bida

nayuki commented 8 years ago

Thanks for providing the wonderful information, @bidafiwoc!

I am acknowledging your commentary on version 1 / model 1, encoders without RS ECC, your proposed application for QR Code generation + scanning, DataGenetics' distorted QR codes, links to RS decoding algorithm.

Also I would like to thank you for the time you took to research the currently available QR code decoders and write the lengthy comparison. I like the humor in the "unusual 0-clause BSD license" ;-). It seems there are a lot of abandoned QR code projects out there, and that is sad because it makes it harder to find the worthwhile projects. You are kind for putting the research text in the public domain.

My status update right now is that I did a lot of reading about the RS decoding theory based on at least 5 different tutorials, with all the polynomial and linear algebra goodness. I understand parts of it such as the syndrome calculation and Chien search, but have yet to understand the Berlekamp-Massey algorithm, Forney algorithm, and exactly how to work with the error locator polynomial.

Subsequently, I wrote a private demo program that performs RS encoding (which I already know how to do) and limited RS decoding that can locate and correct a one-symbol error (which is new and experimental, but seems to work properly). It is still a big question at this point whether I can understand the rest of the math to implement a full RS decoder or not. Thanks again for your patience. =)

nayuki commented 7 years ago

For the record, I have a preliminary working Reed-Solomon ECC decoder today.

I chose the Peterson-Gorenstein-Zierler algorithm because it is described in the ISO QR Code specification as a decoding example, and because that description plus the Wikipedia description was comprehensible enough for me to implement concretely. The algorithm runs in O(k^3) time where k is the number of ECC bytes. This isn't as good as Berlekamp-Massey at O(k^2), but it's a decent start.

It remains to be seen whether I have the time to build out the rest of the logic for scanning QR Codes - such as image detection and segmentation, bit stream parsing, etc.

nayuki commented 7 years ago

Published an article now. Math is rigorously justified, and code is reference quality. https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder