Questions from msigwald

[srowen]

Moving a question from the wiki here:
---------
Sean, thanks for the fast reply. I have a few extra questions though:
1) How do you detect a rotated or skewed image? Or you just don't and
always apply the perspective transform just in case? 2) In the case of
QR codes, what four points do you pass on to the perspective function?
I think I read something about passing the 3 finder pattern plus the
bottom-right alignment pattern, but if I am not mistaken, if you used
the centers of those points youl get a pretty deformed image, since
the alignment corner is not perfectly aligned with none of the finder
patterns' centers. 3) Does your client detect codes automatically
without needing the user to take a snapshot, like other decoders do? I
haven't had the chance of using a client based on you library, since I
don't have any 3gphone, so I couldn't see in action. Well, once again,
thanks a lot for your Quick Response to my question ;D, and
congratulations on a very neat piece of code. I also took a look at
the the other open source project out there and the coding "style"
gave me the creeps.
----------

We look for the three finder patterns, and (unless it's version 1) the
bottom right alignment pattern. You really need four points to
determine the perspective transform properly, so I think it's odd that
there isn't a fourth point in version 1 QR Codes.

The alignment pattern at the bottom right is not in the corner, no.
But you just account for that. You know that the top right corner
should map to (3.5,3.5) in the "pure" matrix of modules, and the
alignment pattern maps to (dimension - 6.5, dimension - 6.5) Then you
construct a matrix (actually, the reverse of this, mapping from the
pure result matrix of bits to the image) based on these four source /
destination point pairs and it works.

Could you make a continuous scan client? yes, sure. It's more up to
the client app than the core library. The Android client (not the M5
one in perforce though) works this way, sure.

Thanks for the kind words on the code. We did try to make it easy to
understand and therefore modify.

[Martin Sigwald]

Thanks again for your quick answer. You left one question unanswered,

though:
1) How do you detect a rotated or skewed image? Or you just don't and
always apply the perspective transform just in case?

[pierrey...@gmail.com]

You can't do a continuous scan client with J2ME. It's possible in
other languages though.

[srowen]

Oh, that comes with finding the finder patterns in the image. The
transformation matrix you establish accounts for rotation and skew.

I suppose I should mention that there is one subtle point: once you
find three finder patterns, which is which? The first one you find is
not necessarily the top left one, if the code is rotated. We figure
that the two that are most distant from one another are the top right
and bottom left codes, which determines the top left one. How to
disambiguate those two? we use the vector cross product to figure that
out. The top-left/bottom-left vector crossed with the top-left/top-
right vector should have a positive z component.

[srowen]

You *could* write a client that continuously scans in J2ME. We made
one but abandoned it. Given that J2ME devices tend to be slower, if
the decode time is 2-3 seconds even, this gets really unusable because
of the lag. You wait 4 seconds, it doesn't decode you move in a bit,
but oh that's when the 3rd capture is taking, and it's blurred... if
you're capturing once or twice a second this is not a big deal.

[Martin Sigwald]

What I meant is if you had any way of knowing if the image is rotated
or not, since if it isn't you would be wasting processor time by
applying the perspective transform.
Regarding the problem of labeling the finder patterns I already
accounted for that. Curiously enough, I used the same techniques you
mentioned. While the vector cross product can`t never fail, there is a
problem with the criteria used to find the first corner, since certain
spatial rotations can deform the image to the point where the topleft
pattern is no longer the most equidistant to the other two. However, I
haven´t been able to find a better way of doing this, but I am sure
there must be some better criteria.
By the way, in case you are wondering why I am so interested in all
this, I am currently taking a course in digital processing and, for
the final project, me and my teammates are exploring better ways of
decoding QR codes in difficult lighting conditions, as well as ways of
correcting really skewed images. We think this are the two most
important problems to solve in order to make QR a really mainstream
tool.Motion blur and imperfect images seem to be the other two major
topics to tackle.

Greetings from Argentina,
Martin Sigwald

[srowen]

Hmm, you are right. I suppose if you found the image was oriented
perfectly upright, and not at all perspective-distorted, you could
replace the expensive matrix transformation with a simple scale and
translate. I think it would be very rare in practice to encounter this
in a camera photo.

However if you are decoding a "perfect" image of a QR Code, like those
you might find on the web, of course you know it is perfectly upright
and not skewed. In that case we do have a decoder hint type called
"PURE_BARCODE" which signals to the decoder that it should assume the
image is a pure monochrome image, not rotated, not skewed, and of
course it can detect the QR Code much faster. I think that would be
our answer to your point.

You are definitely right -- it is possible that the top right and
bottom left finder patterns are not the most distant two points.
Imagine a photograph taken at an extremely flat angle along the
diagonal between the top right and bottom left finder pattern. But in
the normal case this heuristic works.

I do not know of a more reliable way to determine this except to
perhaps examine the image in complex ways. For example you should be
able to confirm your guess by seeing where black/white pixels seem to
occur in relation to these points. If you're right you should see
black/white pixels mostly out to the point where you'd guess the
fourth corner is. This is a good idea -- maybe too expensive relative
to the value it adds.

I would be very interested to hear the outcomes of your research. This
library is most weak in accounting for blur due to the camera focal
length or motion blur, and currently does not account for shadows (I
have experimented with this recently and have not found a cheap
improvement that improves performance substantially).

[BrettSt...@gmail.com]

With regards to the skew and rotation of barcodes, I have a quick
question:
Where could I look to easily grab the coordinates of any two corners
of a scanned barcode?
I am looking to resolve the barcode's angular displacement so knowing
which two corners I am referencing would be nice as well. Any quick
solutions? Is there a particular barcode format (1d, 2d) that would
make this any easier using zxing?

Many thanks,
Brett

On Jul 4, 2:28 pm, srowen <sro...@gmail.com> wrote:
> Hmm, you are right. I suppose if you found the image was oriented
> perfectly upright, and not at all perspective-distorted, you could
> replace the expensive matrix transformation with a simple scale and
> translate. I think it would be very rare in practice to encounter this
> in a camera photo.
>
> However if you are decoding a "perfect" image of a QR Code, like those
> you might find on the web, of course you know it is perfectly upright

> and notskewed. In that case we do have a decoder hint type called

> "PURE_BARCODE" which signals to the decoder that it should assume the

> image is a pure monochrome image, not rotated, notskewed, and of

> > correcting reallyskewedimages. We think this are the two most

> > important problems to solve in order to make QR a really mainstream
> > tool.Motion blur and imperfect images seem to be the other two major
> > topics to tackle.
>
> > Greetings from Argentina,
> > Martin Sigwald
>
> > On Jul 4, 1:37 pm, srowen <sro...@gmail.com> wrote:
>
> > > Oh, that comes with finding the finder patterns in the image. The
> > > transformation matrix you establish accounts for rotation and skew.
>
> > > I suppose I should mention that there is one subtle point: once you
> > > find three finder patterns, which is which? The first one you find is
> > > not necessarily the top left one, if the code is rotated. We figure
> > > that the two that are most distant from one another are the top right
> > > and bottom left codes, which determines the top left one. How to
> > > disambiguate those two? we use the vector cross product to figure that
> > > out. The top-left/bottom-left vector crossed with the top-left/top-
> > > right vector should have a positive z component.
>
> > > On Jul 4, 11:10 am, Martin Sigwald <msigw...@gmail.com> wrote:
>
> > > > Thanks again for your quick answer. You left one question unanswered,
> > > > though:

> > > > 1) How do you detect a rotated orskewedimage? Or you just don't and

[srowen]

The Result object from decode() contains not only the contents of the
barcode but an array of ResultPoints, which are basically (x,y)
coordinates of key points in the barcode. What that means depends on
the format. For QR Codes it is the center of the three finder patterns
and the center of the bottom right alignment pattern if present. I
believe the order is bottom-left top-left, top-right, then bottom-
right alignment pattern.

From that you can derive whatever you like about rotation, and when
you have four points, about skew.

For 1D we do not attempt to find the boundaries of the 1D barcode, but
just find a line that cuts across the whole 1D barcode. This may or
may not be parallel to the long axis of the barcode, and may or may
not go through its center. In this case you get two points, which is
the start and end of a line segment that cuts from one side of the 1D
barcode to the other, where we were able to decode it. You can tell
something about the rotation from that, but not determine it exactly;
two points would not tell you about skew.

One last thing, the Result also includes some metadata about the
decoded barcode. So far there is only one possible bit of metadata,
and that is approximate orientation. We don't populate this for 2D
barcodes but do use it to tell you when we found a 1D barcode after
rotating the image 90, 180, or 270 degrees. If you just want to know
something like this it's already done for you.