QR code detection at angles

[Ralf Kistner]

I want to try to improve the detection/recognition of QR codes at angles (phone
not parallel to the surface). Version 1 codes are my priority, but it
could also help with the larger ones. There are basically two
shortcomings I've found in the current algorithm:

1. As stated in the "DeveloperNotes" wiki page, version 1 QR codes
don't have an alignment pattern, so edge detection could be used to
find the fourth corner.

2. Another problem for all QR codes is that the finder patterns are
often not found at greater angles. I'm guessing it is because (after
binarizing) the patterns are often not in a 1:1:3:1:1 ratio, but
closer to say 1:2:3:2:1 or 2:1:3:1:2.

The second issue is the more serious problem (the fourth corner can't
be found without the first three).
To solve this:
- the pattern finding can be improved, or
- the patterns can be ignored completely, and only edge detection
used to determine the position of the code, similar to that used for
datamatrix.

From what I've heard in the mailing list, the detector for datamatrix
doesn't work very well, so it will probably not work that well for QR
codes either?

Before I try to develop any new algorithms on my own, are there any
existing algorithms (perhaps used by other projects) for either
pattern finding or edge detection I could use? Are there any other
ways this could be improved?

Ralf

[Sean Owen]

Yes you're right about all this. The approach used now is quick and
simplistic, and works quite well for small amounts of skew. It doesn't
work well for significant skew.

You can try the MonochromeRectangleDetector (sp? I forget) which tries
to locate the corners of a mostly-black image in a mostly-white
surrounding region. I find it works alright -- worth a try indeed.

This implementation makes more assumptions, like that the center of
the image is inside the barcode. It's going to be more sensitive to
noise. In the case of QR Codes it's not simple to find the bottom-
right corner since you don't know if it's black or not, and being off
by a couple pixels might fail.

My guess is in the common case, this approach will be less effective.
It may do better in cases of extreme skew, I don't know. Is this
important for an application you're thinking of?


Edge detection is in theory the right thing to apply here, since the
actual code boundaries should be the most obvious edges. I have never
gotten this to work well -- every algo I tried on real images didn't
reliably find the borders -- it's worse on QR Code since there is not
a solid border. I bet this can be improved with more heuristics and
complex calculations. There's some practical limit on how much
computation you can do though: the QR detector takes up to 200ms and
is trying to be very quick. If you make this work better, but it takes
1.5sec to scan... may not be a net win for usability.


I wouldn't discourage you from experimenting, to see what you can make
of this. There are probably approaches I missed when I looked at this
ages ago.

[Bas Vijfwinkel]

>From what I've heard in the mailing list, the detector for datamatrix
>doesn't work very well, so it will probably not work that well for QR
>codes either?

When testing the port to Actionscript I made a few months, I noticed
that the QR code detector is far better than the datamatrix decoder.
Especially when images were tilted or rotated a bit, the datamatrix
decoder has more difficulty locating the datamatrix.

>- it's worse on QR Code since there is not a solid border.

Although QR codes do not have solid edges themselves, most QR codes
are printed on the same background color (usually white).
This background color (with a small variance) could act as a sort of
border.
That could maybe be of assistance for locating the qr code.
With path finding algorithms you could determine the surroundings of
the qrcode which could act as a substitute border

[Ralf Kistner]

On Thu, Dec 3, 2009 at 11:48 AM, Bas Vijfwinkel <bas5w...@gmail.com> wrote:
>>- it's worse on QR Code since there is not a solid border.
> Although QR codes do not have solid edges themselves, most QR codes
> are printed on the same background color (usually white).
> This background color (with a small variance) could act as a sort of
> border.
> That could maybe be of assistance for locating the qr code.
> With path finding algorithms you could determine the surroundings of
> the qrcode which could act as a substitute border

Even though there is a solid white border arround the barcode, there
is no clear line/border that separates it from the barcode. Is there a
good way to find this substitute border? For the QR decoding to work
properly, we need to approximate the border as a straight line, and it
needs to be very accurate (within one module from the "real" border).

What type of path finding algorithms are you suggesting?

Ralf

[Ralf Kistner]

I ran the MonochromeRectangleDetector on my test data now, but in most
cases it doesn't work at all when the picture is taken from an angle.
It assumes that the leftmost, rightmost, topmost and bottommost
corners are the 4 distinct corners of the rectangle. This is often not
true in my test data, resulting in triangles or corners in the middle
of an edge. The same happens for datamatrix codes.

I'll use the same concept of using the mostly-black area, but I'm
going to try to find the edges instead of the corners. It's not gonna
be easy, but might work. Will let you know if I make progress.

Ralf

[Ralf Kistner]

I created a new detector class that works much better for version 1 QR
codes at angles (even at about 10 degrees it makes a big difference).
I tried to keep the code as separate as possible, but still had to
make some changes to the existing files to avoid code duplication.

As I don't want to commit to the core code directly, I made some
patches. Could someone (Sean or Daniel?) please review them?

The first patch (detector_refactoring) allows me to extend the
detector by only overriding the createTransform method. It also
includes a minor bugfix, unless I'm mistaken (missing "/ 7.0f" in
calculateModuleSizeOneWay).

The second patch (increase_tolerance) simply increases the tolerance
of the crossCheckVertical methods both in FinderPatternFinder and
AlignmentPatternFinder from 20% to 40%. With 20% tolerance often not
possible to detect the finder patterns when scanned from an angle, as
the patterns appear more rectangular than square. With QR codes from
version 2 upwards, this alone greatly improves the detection.

In addition to these patches, I have a class for general edge
detection, and a class extending (the modified) Detector, using the
edge detection. I also have a few more classes I used for testing
these. This is similar in purpose to ImageConverter, but generates
nice HTML to view the results.

As these additional classes don't modify any existing classes, I guess
I could commit them myself? Should I put them in a new package in core
or j2se, in a new folder, in a new branch?

I also ported the detection classes to C++ (as the C++ port is all I
actually use). Is it fine if I commit this directly?

I'll discuss the actual algorithms and its performance when I commit the code.

Ralf

[Sean Owen]

Let's take it piece by piece:

It seems like you can try 45/135/225 rotation entirely outside of the
code by just rotating the image you feed in beforehand. I'm not
entirely against this part of the change, but am reluctant to add
complexity for a case that seems rare. 1D barcodes almost always occur
at right angles to the image.

Your bug fix is exactly right, oops.

Does your tolerance change increase the pass rate of the unit tests?
If so, I'm all for it.

Could I have a look at your Detector extensions first in a patch? I
imagine I'm happy to let you run with that.

C++: likewise, happy to let you run with that since neither of us
really touches it. However i know several people are actively
interested in working on this port. If you're adding code, I imagine
it does not interfere with anyone else's changes.

>  detector_refactoring.patch
> 12KViewDownload
>
>  increase_tolerance.patch
> 2KViewDownload

[Ralf Kistner]

Sean,

I guess I wasn't clear, I'm referring to cases where the camera is not
parallel to the surface, so perspective distortion occurs. This cannot
be fixed just by rotating the image.

The current test data doesn't contain many cases like these, so it
doesn't really affect the unit tests. With the 40% tolerance it solves
112 instead of 113 with global thresholding, and 117 instead of 115
with local thresholding (a modified version).

However, I have a lot of test data where it makes a big difference. I
attached two examples.

The increased tolerance is enough for any QR code with an alignment
pattern. However, it alone doesn't help for QR version 1 codes. For my
application we mostly use version 1 codes, and it is important to be
able to scan it from an angle. I do realize that for other
applications this might be a small and unimportant case. The first
patch I sent is not strictly required, but it avoids code duplication
when using my detector, as it allows me to extend the class. I don't
currently have the code with me, but this is basically what the code
does:

- Uses the current detector to locate the finder and alignment patterns.
- If an alignment pattern is found, it acts just like the current
detector, and does nothing else.
- If the 3 finder patterns are found, but no alignment pattern:
- The sides of the finder patterns are used to find approximate
bottom and right edges.
- Using these approximations, a more accurate search is performed
for the real edges.
- The intersection of these edges are used as the bottom-right corner.
More details are in the code comments.

The performance of the code is reasonable. In the C++ port, it roughly
doubles the total time of the detection algorithm, which is still
small compared to the time the binarizer takes. The Java code probably
needs more optimization.

Currently the QR code contains some hardcoded values, which are
specifically optimized for 240x180 images (I don't have any other test
data). It will need some work before it will be usable for larger
images as well.

This adds a lot of code, for general barcode scanning applications it
might not be worth it. The edge detection functions might be useful
for datamatrix codes.

I'll send you the code soon. Use or don't use it, it's up to you. It
should be useful to keep it for possible future development anyway.

As for the C++ port, the changes to the current code are minor. I'll
be using the edge detection in my Symbian application, but I'll leave
it disabled by default.

Ralf

[Sean Owen]

I'm going to commit a version of your tolerance change since it does
seem to cause about 12 more images to pass and only loses 1, and you
have evidence it improves detection on other types of images. Let me
then look again at your other patch. I think I'm OK committing a
version of it. For example I would rather not have protected fields
but instead use getters.

[Sean Owen]

Yeah I'm fine with the other patch too. I will commit with only one
substantive change -- rather than making those fields protected, let's
go with access via protected getters.

As for the rest of the new Detector... hmm I like the idea of reading
version 1 codes better. I suppose the question is how much better,
compared to how much more code and complexity? and to what degree does
it slow down the 'normal' case? You could post a patch for discussion.

>  0051.jpg
> 4KViewDownload
>
>  0035.jpg
> 5KViewDownload

[Ralf Kistner]

I attached my code. I'm not sure where (folder & package) to put it
yet, and I don't have good class names.

There are still some issues for the code:
- I used ResultPoint to represent any point. This is probably not the
best class to use.
- I used (Array)Lists, which should be replaced by arrays or Vector?
Perhaps a single float[] should be used instead of the current
List<ResultPoint>? For development the latter was simpler, but not
very efficient.
- I used floating point operations in most places. In many places it
is useful to have a resolution of half a pixel, but fixed-point
operations might be faster.
- As mentioned before, the code is currently optimized only for 240x180 images.

I haven't measured the performance properly for Java yet. If an
alignment pattern is found, it does nothing extra, so it would not
have any performance impact. If not, the C++ port doubles the
detection time. The Java code would probably triple the detection time
(Are there any good Java profilers out there?). The tests were all
performed on a desktop, I'm not sure how the performance would look on
a phone.

With the current test data, this code makes almost no difference, as
there are very few version 1 codes. The one noticeable difference is
with qrcode-2/5.jpg, which gives an ArithmeticException in
GF256.inverse (I still have to investigate this).

With my test data, this change improves the number of recognized
barcodes by about 30%. These are fairly 'normal' version 1 codes, with
relatively small angles. Should I also commit some of my test data? I
have a few hundred images, but many of them are similar, so I guess I
should at least organize them and remove the redundant ones.

I also attached my test utilities. These could be useful for other
barcode types as well.

Ralf