QR-code localization — the important recognition step that has been neglected

Information piece on article’s main concepts

In this section we’ll mention the main QR-code characteristics that are used to create the localization method, as well as a brief description of the original Viola-Jones object detection method.

QR-code

QR-code (acronym for Quick Response Code) is a two-dimensional barcode that was developed in Japan in the mid-90s to serve the automobile industry. Due to its fast readability and greater storage capacity compared to standard one-dimensional barcodes, the QR-code system grew popular in various fields all over the world.

The Viola-Jones method

Everybody and his dog already wrote about the Viola-Jones method here on Habr. Even we have done it a few times ourselves (for example, here, here, and here). Still, we consider it necessary to address the main points of this method in just a few words.

QR-code detection algorithm

When constructing a QR-code localization approach, we were guided by the following specificities of the problem. First off, the algorithm being developed by us has to be characterized by high-performance so we can apply it in real-time recognition systems. Second, this algorithm has to be resistant to possible barcode distortions in an image. Third, it has to take into consideration any existing QR-code variability.

  • the original Viola-Jones method uses Haar features that “highlight” texture specificities of an object; in our case, a QR-code is made up of black and white elements, their distribution varies greatly from one barcode to another.
  • the original method is designed to detect identical objects in a predetermined orientation, which is not applicable in our situation.

Gradient Haar-like features for QR-code scanning

We used a special family of gradient Haar features to construct an effective QR-code detector. These features are rectangular Haar-like features calculated over the map of directed edges which makes their generalizing power much stronger.

A decision tree of strong classifiers

A decision tree of strong classifiers is represented as a binary decision tree: each node is a strong classifier, its right branches are subwindows that presumably contain an object, and its left branches are the ones that didn’t get recognized as an object. The definitive answer is presented only in leaves. The classic cascade classifier that was described in the original Viola and Jones research is a decision tree-like classifier with only one “positive” output (leaf) and a lot of “negative” outputs.

Experimental results of QR-code detection

For experimental purposes, we prepared a set of barcodes consisting of 264 images that we would use to assess the effectiveness of our algorithm. The physical size of the images was around 1 MP. There was only one QR-code of arbitrary orientation in each image, the size of a barcode was not less than 10% of the image’s area. There are some examples of the images from this set below.

Conclusion

These days QR-codes are used in various aspects of life: in the advertising industry to encode URL-addresses, in public sectors to provide e-services, etc. Although the QR-code scanning tasks are extremely widespread today, the existing open-source libraries focus primarily on QR-code decoding and neglect the localization problem. To be honest, the real goal of this article was not so much in describing an effective QR-code localization method, as an attempt to show you, dear reader, how we can get the free libraries almost to the industrial level with the help of scientific thinking and systems analysis and with the knowledge on how to use classic digital image processing tools.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Smart Engines

Smart Engines

A software development company with a broad expertise in computer vision, document processing and OCR, mobile recognition systems and AI. www.smartengines.com