3 ms·

How do camera apps recognize where the QR code is in the image, and what part of the image it should decode? I guess it also often has to some processing on it,

How do camera apps recognize where the QR code is in the image, and what part of the image it should decode? I guess it also often has to some processing on it, as it will be scewed/bent/etc. Looking at this guide, it's easy to understand the steps. But I don't get how one actually would apply them in code to a picture of a QR code. How?

pjot 3y ago
QR codes have certain zones that scanners look for. To determine orientation scanners look for “alignment markers”.
- phoronixrly 3y ago
  Do you have an article that goes into the details of implementing a reader, and does not just tell you 'use pyzbar'?
  - stavros 3y ago
    That would probably be a machine vision problem, but I'm also curious to know how you turn the pixels of a photo into a series of bits.
alex_suzuki 3y ago
Typically by looking at „runs“ of black and white pixels (after image has been binarized/thesholded). For a QR code marker, you would look for a 1-1-3-1-1 pattern, which would indicate that this image row crosses a QR code finder pattern.
- kaoD 3y ago
  But do they do this at different angles? If so, which? How do they deal with (possibly partially) obscured alignment markers? How do they determine the angle and size of squares? How does one sample each square (center point, average of square, min, max...)? Should I convert my image to grayscale first? If so... which of the RGB-to-grayscale methods should I use for best results? Should I pre-process the picture to enhance sharpness and reduce focus artifacts? Should I bruteforce each frame of the video stream in look for the alignment markers? Etc. etc. I think I have the general idea on how all that works, but... isn't there an official spec/algorithm on how one is supposed to do this? The devil is in the details.
  - phoronixrly 3y ago
    I've also been looking for a course that goes over this step by step, and step 1 is not pip install opencv/pyzbar/pytorch...
  - matsemann 3y ago
    Yes exactly. Do I need to look for 1-1-3-1-1 markers in _all_ 359 directions? What about warping/distortion of the surface etc? All the details is what I'm interested in seeing.
  - moring 3y ago
    If you have a rough idea how it works, include these in your google queries to get results that go into details ;) Some more things to include: - perspective correction may be needed (the surface with the QR code is not parallel to the image plane, so pixels further away get smaller) - if the algorithm takes parameters, such as color filters / black-vs-white thresholds, try with different parameter sets in sequence. The user is pointing the camera at the code for a relatively long time, compared to the time it takes to process an image. - pixely images should produce a recognizable pattern in the fourier transform of the image. This gives you the size AND rotation at once. (edit: formatting)
  - alex_suzuki 3y ago
    The 1-1-3-1-1 (with tolerance) works at angles as well, as long as the code is not perspectively warped. You are right in assuming that there‘s a lot more to it than that. Localization and decoding (usually these are considered separately) 2D codes is an active research field, and there are a lot different approaches. Disclaimer: I an the author of STRICH (https://strich.io https://strich.io) and have dived relatively deep into the topic.
    - alex_suzuki 3y ago
      Also, you can always look at how libraries such as ZXing do it. Especially for QR codes, there is a lot of code available on the internet.
  - avianlyric 3y ago
grishka 3y ago
There are various computer vision algorithms for detecting lines in images, like Hough transform[1]. You can combine it with an edge detection algorithm[2] for increased reliability. You would then look for quadrilaterals that have some space around them (as required by the QR code spec), transform them into squares, binarize the pixels (there are different approaches to that too, but a simple threshold would work in simplest cases), and only then would you start looking for the corner markers and trying to actually decode the QR code. At least that's how I'd do it if I were to build a QR code reader from scratch. I built a similar thing for Telegram a while ago[3] for recognizing the text in the machine-readable zone of passports and ID cards. It does different things after the initial detection/transform/binarization steps, but those would be the same for a QR code reader. [1] https://en.wikipedia.org/wiki/Hough_transform https://en.wikipedia.org/wiki/Hough_transform [2] https://en.wikipedia.org/wiki/Edge_detection https://en.wikipedia.org/wiki/Edge_detection [3] https://github.com/DrKLO/Telegram/blob/master/TMessagesProj/jni/secureid_ocr.cpp https://github.com/DrKLO/Telegram/blob/master/TMessagesProj/...

pjot 3y ago

QR codes have certain zones that scanners look for. To determine orientation scanners look for “alignment markers”.

phoronixrly 3y ago
Do you have an article that goes into the details of implementing a reader, and does not just tell you 'use pyzbar'?
- stavros 3y ago
  That would probably be a machine vision problem, but I'm also curious to know how you turn the pixels of a photo into a series of bits.

alex_suzuki 3y ago

Typically by looking at „runs“ of black and white pixels (after image has been binarized/thesholded). For a QR code marker, you would look for a 1-1-3-1-1 pattern, which would indicate that this image row crosses a QR code finder pattern.

kaoD 3y ago
But do they do this at different angles? If so, which? How do they deal with (possibly partially) obscured alignment markers? How do they determine the angle and size of squares? How does one sample each square (center point, average of square, min, max...)? Should I convert my image to grayscale first? If so... which of the RGB-to-grayscale methods should I use for best results? Should I pre-process the picture to enhance sharpness and reduce focus artifacts? Should I bruteforce each frame of the video stream in look for the alignment markers? Etc. etc. I think I have the general idea on how all that works, but... isn't there an official spec/algorithm on how one is supposed to do this? The devil is in the details.
- phoronixrly 3y ago
  I've also been looking for a course that goes over this step by step, and step 1 is not pip install opencv/pyzbar/pytorch...
- matsemann 3y ago
  Yes exactly. Do I need to look for 1-1-3-1-1 markers in _all_ 359 directions? What about warping/distortion of the surface etc? All the details is what I'm interested in seeing.
- moring 3y ago
  If you have a rough idea how it works, include these in your google queries to get results that go into details ;) Some more things to include: - perspective correction may be needed (the surface with the QR code is not parallel to the image plane, so pixels further away get smaller) - if the algorithm takes parameters, such as color filters / black-vs-white thresholds, try with different parameter sets in sequence. The user is pointing the camera at the code for a relatively long time, compared to the time it takes to process an image. - pixely images should produce a recognizable pattern in the fourier transform of the image. This gives you the size AND rotation at once. (edit: formatting)
- alex_suzuki 3y ago
  The 1-1-3-1-1 (with tolerance) works at angles as well, as long as the code is not perspectively warped. You are right in assuming that there‘s a lot more to it than that. Localization and decoding (usually these are considered separately) 2D codes is an active research field, and there are a lot different approaches. Disclaimer: I an the author of STRICH (https://strich.io https://strich.io) and have dived relatively deep into the topic.
  - alex_suzuki 3y ago
    Also, you can always look at how libraries such as ZXing do it. Especially for QR codes, there is a lot of code available on the internet.
- avianlyric 3y ago

grishka 3y ago

There are various computer vision algorithms for detecting lines in images, like Hough transform[1]. You can combine it with an edge detection algorithm[2] for increased reliability. You would then look for quadrilaterals that have some space around them (as required by the QR code spec), transform them into squares, binarize the pixels (there are different approaches to that too, but a simple threshold would work in simplest cases), and only then would you start looking for the corner markers and trying to actually decode the QR code. At least that's how I'd do it if I were to build a QR code reader from scratch. I built a similar thing for Telegram a while ago[3] for recognizing the text in the machine-readable zone of passports and ID cards. It does different things after the initial detection/transform/binarization steps, but those would be the same for a QR code reader. [1] https://en.wikipedia.org/wiki/Hough_transform https://en.wikipedia.org/wiki/Hough_transform [2] https://en.wikipedia.org/wiki/Edge_detection https://en.wikipedia.org/wiki/Edge_detection [3] https://github.com/DrKLO/Telegram/blob/master/TMessagesProj/jni/secureid_ocr.cpp https://github.com/DrKLO/Telegram/blob/master/TMessagesProj/...