Re: C++ Rotation Weaknesses

[Sean Owen]

Very cool. This is QR codes, right? Yes, there is certainly going to be weakness near 45 degrees (plus multiples of 90). The heuristic for finding finder patterns is weakest at these rotations, since you only find the 1:1:3:1:1 white-black ratios if you happen to cut through the center of the finder pattern. That's an acceptable tradeoff since you virtually never scan at this rotation in practice.

I'd be interested in looking at your improvements. I suppose the challenge is to come up with something that works better but is not slower, since then you'd be harming 99.99% of use cases a little to help 0.01% somewhat. 

I don't work on C++, only Java. Can you summarize the change -- is it just that you implement a method to rotate by 45 degrees and use it, since that would cause QR codes at about 45 degrees to become upright? Makes sense, but would only be enabled for TRY_HARDER mode.

[Constantin Scheuermann]

Hi Sean,

The rotation at the moment is only done, in case the decoder was not able to decode the QR-Code in normal mode. Sure, the try Harderflag could be used to additionaly enable this rotation.

Exactly the first idea was to implement a simple rotation method. At the moment im am using imagemagick lib to rotate. What would you suggest?

I tested ZBar as well, which is much better concerning the decoding rate. My aim would be to increase ZXings decoding rate, but only rotation comes to my mind. Do you have any ideas?

[Constantin Scheuermann]

Additionally, maybe it could be usefull to patch the c++ version of ZXing with this patch, but i have no idea where i suggest the patch. First this forum seams to be suitable but where can i get feedback concerning a patch?

[Sean Owen]

For QR codes? I'd be surprised if anything was notable better than zxing... just because it's not hard to decode QR codes and it's pretty optimized at this point. That is, any library ought to find them quite well. Are you using TRY_HARDER? and are you using Java? The Java version is going to be much more up to date and probably effective than C++. (If you don't want to mess with Java directly, send images to http://zxing.org/w/decode.jspx -- it's the latest code wit TRY_HARDER enabled.)

I think the 45-degree thing is a decent idea, I'll record it as a feature request.

I'd rather implement this in Java, then port the change to C++. All the other languages ought to follow Java.

[Steven Parkes]

I suspect that rotation implementation will end up being platform-specific. It's certainly possible to do this manually but at least for C++/Objective C, both ImageMagick and Core Graphics have primitives for this that I would presume to be optimized.

[Constantin Scheuermann]

Hey Sean,
the new Simulation took me quite some time, but referring to your comment, I have done my simulations with the ZXing Java Core. I did not use the TRY_HARDER, but this is simulated next.

Surprisingly the Java Core is slightly weaker than the C++ Core. I will attach the evaluation of ZBar, which decodes better than ZXing. Yet I have no explanation for it. Maybe we can find out, why. Do you have an idea?

Looking forward to your answer.

Find my results attached

[Sean Owen]

Hmm, don't think it's possible for the C++ to be better. It is strictly < as it is an older port. But, could be differences in how you load and binarize the image.

You probably need to use TRY_HARDER to get a legitimate result in your context. Your test prioritizes accuracy completely over speed, and you are using a mode that prioritizes speed mostly.

You also need to use the latest Java code, if not already.

I don't quite understand how to read your charts -- what are the axes of each plot? I know they're degrees, but what degrees?

I have a change that will detect better at 45 + 90n degrees but you need TRY_HARDER mode.

[Constantin Scheuermann]

Okay, I will run the next evaluation with the TRY_HARDER Flag. Will take some time until I will have the results. I used the latest Java Code from the repository, checked it out before starting the simulation 7 days ago.

About the charts:
The QRCode is rotated within a OpenGL environment in all three axis (X,Y,Z). X and Y range from 0° - 180° in 1° steps. Z axis as well, but only in 6°steps. This resulting in a total of 1944000.

The heatmaps show the decode results in x and y-axis from 0°-180°. Each heatmap symbolizes a one 6° step in z-axis.
The plot I generated shows (at y-axis) the percentage of successfully encoded QRCodes. At x-axis it shows the 6° steps in z axis. Keep in mind that within each step in z-axis, all rotations in x- and y-axis (0°-180°) in 1° steps are evaluated.

Find attached the publications we made. There you can find a detailed description of what we are doing: Paper

[Constantin Scheuermann]

I initiated the next evaluation.
For decoding I am using now:
com.google.zxing.client.j2se.CommandLineRunner [FILE] --brief --try_harder

I am excited about the results, but due to my limited calculation power it will take some days. I will post them as soon as they are finished.

[Sean Owen]

OK, but what does it mean to scan at 90 degree rotation about the x- or y- axis? You would be looking at the side of the image and there would be zero image data. Rotations from 90 to 180 degrees has the code flipped over, and QR codes aren't valid when mirror-imaged. Does 90 mean "flat", un-rotated?

I am pretty sure the library is not going to scan QR coes at extreme perspective distortion, like near +/- 90 degrees. I'd be surprised if it works past +/- 70. Which is what you find. The heuristics are certainly optimized for flat images and I know they break down for cases like this, which almost never happen in practice. I don't know if TRY_HARDER will help there.

But let me send you a patch that will help at 45 + 90n rotation around the z-axis. Might as well try that before you launch your tests.

[Constantin Scheuermann]

You are right, the angles 0° in x and 0° in y, as well as 180° in both, result in a black picture. The QR Code can not be seen

I will send you some angle examples

X 15° Y 150° Z 0° = The QR Code almost lies on his back (x very low)

X 90° Y 55° Z 0°

Now some z Rotation at 90°

X 85° Y 150° Z 90° (The QR Code is rotated 90° Counter Clock wise, interesting finding, that we have here a maximum of decoded QR Codes. So it works best at a rotation of 90° Counter Clockwise)

What do you mean with +/-70 degrees? One Heatmap is from ZBar another Framework, which is able to decode QRCodes. About which heatmap/results are you talking?

Thanks, great, i will just paste the patch an run the simulations again. I will tell you as soon as i patched and started...

[Constantin Scheuermann]

The first QRCode angle was wrong, it is  X 15 Y 90 Z 0. See the filenames to be sure as well they are XXXXX-YYYYY-ZZZZZ.

[Constantin Scheuermann]

I applied your patch and the simulations are running, thanks for that. This is actually the same approach as i posted in my patchfile for the c++ core. I am expecting similar results as the results for the c++ core. Lets see ...

As i used the latest repository source code for the java evaluations, I am wondering, why the Java core is slightly weaker than the c++ core. Do you have any idea?

[Sean Owen]

I mean that I'm sure the heuristics in this library aren't going to work at extreme perspective distortion. I suppose it would be cool to read such things but they're not found in real-world use cases, and if you can assume there's not so much distortion you can make it a lot faster in the common case.

I don't think Java is worse at decoding, I'm saying there is some difference in how images are loaded. For example... what are the alpha channel values in these images?

[Constantin Scheuermann]

Okay, i agree. But there are usecases where people had problems scanning an QRCode advertisment about 5 or 6 meters above peoples head. The angle was quite extreme. The advertisment didn´t work.

About the alpha values, what exactly would you like to know? The pictures that I used as Input or when the pictures are already read?
I already had a brief look at the first results, the decoding rate increases, but to give you qualified results I have to wait ....

Would be great, if the patch works. For c++ and the java implementation it seems to be quite suitable, what do you think? But still, what i am really curious about is, why ZBar makes way more successfull decodings ...

[Sean Owen]

It is just a wild guess but do the images have an alpha channel? the ones used as input.

There could indeed be a different in C++ that happens to make it work better for these images. I don't know what it is and would be surprised. The best bet is just that the image comes in somewhat differently.

The main difference is that zxing is explicitly rejecting finder patterns that are 'found' but seem to have extreme perspective distortion as almost surely false positives. That's a good assumption. 

If you want to make the library try to scan for such extreme angles I think it is pretty easy to do so. Find this bit of code in FinderPatternFinder...

    // If we found a finder-pattern-like section, but its size is more than 40% different than

    // the original, assume it's a false positive

    int stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] +

        stateCount[4];

    if (5 * Math.abs(stateCountTotal - originalStateCountTotal) >= 2 * originalStateCountTotal) {

      return Float.NaN;

    }

Just remove it. I am not certain it will do the trick, but should. For your images, I don't think false positives will be so much of a problem (?) but I don't know that for sure either.

[Constantin Scheuermann]

The input images have an alpha channel:
Border color: rgba(223,223,223,1),  Colorspace: RGB, Depth: 8/1-bit, Channel depth: gray: 1-bit alpha: 1-bit

I will try this trick in the next evaluation. I will run it as soon as the other ended.

The first 4 plots are finished.
I ploted them together with the normal Java core:

[Sean Owen]

I ask because I know I fixed something in Java a long while ago where a funny alpha channel would mess up the interpretation of the image... but you're using the latest and I don't think it would cause problems here actually. It would make it all fail or something.

Yes I am not surprised that adding code to get another look at the QR code even helps in non-rotated cases.

[Constantin Scheuermann]

Simulations are still running. I loaded the new source from repository. I saw you added the rotation patch but not in the QRCodeReader. I still needed to add the Code for the rotation in case decoding was unsuccessful.

Two evaluations are running, the rotation patch and the rotation+extreme angles as you suggested. I am excited if the rotation patch is as good as the rotation patch for the c++ core.

Will write as soon as results are available.

[Sean Owen]

Yes the QRCodeReader change by itself isn't complete. The result points it reports are wrong since they are in the rotated image.

[Constantin Scheuermann]

Hi there,

the simulations are finished. Find the results attached. So with the idea of rotation ccw and the additional patch i was able to improve the overall decoding rate up to 10%. I just added the overall figure, showing my c++ patch, the patch from Sean with the same idea but implemented for the java core, and than additionally the java core with scanning all angles, with out limits.

[Sean Owen]

These are interesting results, thanks for all your work here. Looking forward to your final paper if you can share it.