Performance:QrCode

From BoofCV
Jump to navigationJump to search

Abstract

QR Codes (Quick Response Code) are fiducial markers used to embed digital information visually on 2D surfaces. QR Codes are commonly used in consumer and industrial applications was a way to embed information, such as website addresses or part numbers. A QR Code reader or scanner can visually detect a QR code and decode the message inside. There are numerous free open source and commercial proprietary software libraries available. This study compares all known open source libraries in their ability to correctly detect QR codes and efficiently process them. Results are presented where performance is broken down based on different categories. While there is no library which dominates every category, on average BoofCV's detector is the fastest and most reliable detector.

Updated: March 19, 2019

Evaluated Libraries:

To cite this study please use the following:

@misc{QRBenchmark,
  title = {Study of QR Code Scanning Performance in Different Environments. V3},
  howpublished = {\url{https://boofcv.org/index.php?title=Performance:QrCode}},
  author = {Peter Abeles},
  originalyear = {03.19.2019}
}

Introduction

Originally designed in 1994 by the Japanese company Denso Wave for the automotive industry QR Codes are widely used in consumer and industrial applications today. Each digital bit is encoded as a square in a 2D array. Different parts of the marker are used to locate the QR code, aid in decoding, and error correction. The amount of information which can be stored is depends on the version and configuration. The QR Code marker is fully specified in the ISO/IEC 18004 document. For more about the history see wikipedia.


Structure of a QR Code. From Wikipedia

This benchmark evaluates the performance of different open source QR Code scanners under different real world environmental conditions. Only open source libraries are considered since they are easily accessible. One thing clear from this study is that the behavior of scanners is difficult to succinctly summarize.

Each library's ability to detect and decode a QR code varies widely depending on the environmental conditions. It's not uncommon for a library to get near 100% in one category then fail completely in another. How fast each library runs high dependent not only on image size but also on the scenes structure and the number of QR codes visible.

All test images and evaluation source code is freely available

Categories

Images where broken up into several categories, each of which would stress a detector in a different way. Representative images for each category are shown below. Categories were selected based on known failure conditions and common use cases.

Image Dataset
Blurred
Images which are blurred due to focus or motion
Brightness
Same scene but with the exposure manually adjusted from under to over exposed
Bright Spots
Abrupt changes in intensity can throw off adaptive thresholding techniques
Close
Images taken so close to the image that black regions are no longer uniformly black
Curved
QR Codes on curved or uneven surfaces. Specification says it needs to be on a flat surface.
Damaged
Printing errors, scratches, pens, ... etc
Glare
Glare obscuring or degrading part of the QR Code
High Version
Unusually high version numbers, e.g. 25 and 40
Monitor
Pictures taken of QR Codes on a monitor. If close the pixels are visible.
Nominal
Intended to be representative of normal use cases. All of these should be readable
Non-Compliant
Specification was intentionally broken. Often for artistic reasons
Pathological
Intentionally corrupted markers designed to break detectors
Perspective
Marker viewed at increasingly skewed angles
Rotated
Same image but rotated 360 degrees
Shadows
Non uniform lighting caused by shadows

Evaluated Libraries

This section discusses each individual libraries and how the benchmark had to be adapted to each of them. Unless otherwise stated the default settings of each library was used.

BoofCV

Returns four precise corners (sub-pixel accuracy) for each position pattern and an approximate location of each alignment pattern. A bounding box is also returned. Since there is no feature at the fourth corner it is found by intersecting lines from finder patterns.

OpenCV

Can only detect a single QR Code in an image. Returns a single bounding box at sub-pixel accuracy. New since OpenCV 4.

Quirc

Returns bounding box as represented by four corners. It's a bit unusual in that it doesn't fully process the image but delays some processing until a request is made to decode a specific marker.

ZBar

Because ZBar is designed to detect multiple types of fiducials the source code can be a bit vague. By inspection it was determined that it returned four corners bounding a QR code.

ZXing

ZXing only provides the center of the three position patterns. The fourth corner was estimated using the formula below. If the marker is "square" in the image this works well but if skewed it is off by a bit. This is O.K. because the benchmark has a very loose definition for matching.

float x3 = pts[2].getX() + (pts[0].getX()-pts[1].getX());
float y3 = pts[2].getY() + (pts[0].getY()-pts[1].getY());

Default settings for ZXing has a low detection rate in simple scenarios. To improve the detection rate it was configured to trade speed for reliability with the flags below:

hints.put(DecodeHintType.TRY_HARDER,null);

ZXing was intentionally designed for speed over 100% detection rate (citation needed). The idea being that when processing a video stream eventually one image will be readable.

Evaluation Procedure

For all QR Codes in every image in the test set four corners were selected and saved. These four corners define the bounding box and are used to decide of a library correctly detected a QR Code or not. If a detected marker was found to overlap labeled markers in the image by a minimum of 10% then it was considered a match. 10% might seem like a low threshold but not all libraries return precise location information. The exact threshold for determining a match was found to not be important.

Four selected corners on QR Code. CW or CCW order doesn't matter.

Detection performance was evaluated using F-Measure. To compute F-Measure we need to precision and recall. To find precision and recall we need to count the number of true positives, false positives, true negatives, and false negatives. Detecting the same QR code more than once was also considered but none of the libraries were found to do that.

True Positives
When a labeled marker is matched to a detected marker
False Positive
When no labeled marker is matched to a detected marker
True Negative
Always 100% in this scenario.
False Negative
When a labeled marker is not matched to any detected marker

Summary detection results were computing weighing results in each category equally. If a category had 200 QR Codes it would have the same weight as one with 10. This was to avoid biasing the results to one particular environment, a flaw in an earlier version.

As mentioned runtime performance (how fast a library can process an image) is dependent on scene structure, number of qr codes, and image size. The results presented here focus on scene structure dependency. A more fine grained analysis related to image size and number of visible markers might be added in the future. Processing time for an image was measured using the system clock and measured actual time as compared to CPU time. Some argue that CPU time is more accurate but would be very difficult to measure here because we did not want to measure how long each application took to decode the input JPEG image just processing time.

Examples of how runtime was measured in Java and C++.

long time0 = System.nanoTime();
detector.process(gray);
long time1 = System.nanoTime();
auto time0 = chrono::steady_clock::now();
Image zimage(width, height, "Y800", image.data, width * height);
int n = scanner->scan(zimage);
...
auto time1 = chrono::steady_clock::now();

It was not obvious always what should be measured and what should not be measured. For example, after the image has been loaded should the conversion from color to gray be included? OpenCV would load an image as gray even if it was color so it would be unfair to penalize libraries which didn't use OpenCV. Most libraries did all the heavy processing inside their process()/scan() functions. However some libraries delayed processing until the QR code message/location was requested. In that case the timing would be extended around the qr code message accessors.

Relative runtime is shown for each category. This was done because there are no standard image sizes and some categories might tend to have larger or smaller images confusing the results. The summary performance was found by averaging the median runtime across all categories, where each category had equal weight. Median performance was used here in an attempt to limit outliers skewing results. A few library had large spikes in processing time under specific conditions.


Detection Results

No library dominates all categories. BoofCV is the best or a close second best in every categories, except in the non-compliant and pathological categories. It requires stricter adherence to the specification. ZBar tends to do better than ZXing in most categories but loses out in the summary plot due to the categories which ZXing does best in. While Quirc does well in most common situations it performs poorly in categories which all other libraries do well in. OpenCV's scanner needs a lot of work in general when it comes to detection. OpenCV being limited to detecting one marker in an image didn't help.

Higher is Better


Detection Performance by Categories
Detection Performance Summary

Runtime Results

If the "lots" scenario is ignored, then ZXing is the fastest library followed not far behind by BoofCV. However if that category is taken in account then BoofCV is the fastest library by a large margin followed by Quirc. OpenCV has performance in the middle behind ZXing. ZBar was consistently the slowest libraries in all categories and had sever issues in the 'lots' category, it was 20x slower than BoofCV! Mean of the median times was used in summary plot in an attempt to mitigate this bias.

Interesting to note that the two Java libraries were the fastest (ignoring "lots") by a large margin while the two C/C++ libaries were the slowest. This is likely due to algorithmic details and because operations which can be vectorized do not dominating the processing of QR Codes.

Relative Runtime by Categories
Runtime Performance Summary

Category Counts

To give you an idea of the size of this test set and the diversity of images in each category, where are the number of images in each category.

Number of Images in Each Category

Conclusions

Which library is the best depends on the situation and is very subjective. If the markers are standard compliant then your best bet is probably BoofCV due its ability to detect more markers and respectable speed in all situations. If your markers are damaged or artistic then ZXing would be a good choice, assuming you can ensure that 'lots' of markers are not visible at once. If you can't use a Java library and have to use C/C++ then ZBar is your best choice, just hope that only one or two markers are visible at any time.

Changes

March 19, 2019

  • Added two new categories
    • High Version and Perspective
  • A few additional images to blur and others
  • Updated BoofCV to 0.33 and ZXing to 3.3.3

January 16, 2019

  • Re-weighted detection summary to avoid heavily weighting "lots" category
  • Added OpenCV 4's new QR Code detector
  • Using latest 33-SNAPSHOT of BoofCV (subject to change)

October 2018

  • Initial Publication