Performance:QrCode

From BoofCV
Jump to: navigation, 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.

Evaluated Libraries:

To cite this study please use the following:

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

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 because they are free and can be quickly integrated into your hardware. 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.

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
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
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.

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 found lumping all results into a single bin. Categories will more images/markers will have greater weight. For this reason you should inspect the category results and use knowledge of your application to decide which is the best match.

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 was quested. 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 so 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.

Category Counts

The number of images in each category is shown as a histogram below. This is important because it gives you an idea of the level of diversity in each category as well as how bias the summary plots are. If a category has many images and many QR codes in it, it will heavily influence the summary plots.

Number of Images in Each Category

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.

Detection Performance by Categories
Detection Performance Summary

Runtime Results

Arguments can be made that either ZXing or BoofCV is the fastest library. ZXing is the fastest library in every category but 'lots'. There it did very poor while BoofCV was the top performer. This is also a perfect example of how the summary plot can be miss leading. Based on its results it would appear that BoofCV is 2.8x faster, while in reality it is 1.2x to 2x slower! Mean of the median times was used in summary plot in an attempt to mitigate this bias.

Quirc and ZBar were the slowest libraries. ZBar had issues in the 'lots' category taking 20x longer to process the images than the fastest library! Interesting to note that the two Java libraries were the fastest 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.

Relative Runtime by Categories
Runtime Performance Summary

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.