DsynFLO: October 2014

In our previous post we covered a lot of ground regarding Smartwatches and Eco-system. Few of the interesting things that came out of that discussion was the co-existence of Chrome and Android. A constant remainder is not enough to suggest that Google did not have a stable and independent platform until Android took off. Now with the significant stronghold they have on smart phones, Google is making amendments within the Organization to tweak up its other portal to the Internet by garnishing it with Android. Chrome OS that hasn't really grown out of its infancy yet and is constantly hurtled by Windows releases. The best possible attempt for Chrome is to hijack Android market share by providing itself the ability to run Android applications natively and by pushing the "web-based" capabilities to Android. The above picture exactly illustrates what Canonical did with Ubuntu for Android.

Hiding between the lines

Yet another interesting topic that came out in the post, was the evidently missing Microsoft's Smartwatch. News reports suggest that Microsoft watch will be out with this years end [2014]. The Windows platform is much better equipped to adopt smaller devices thanks to improvements in Windows RT. But the big question is will the plunge into making hardware burn fingers again ?

A mock-up of the Microsoft (Windows/Surface?) Watch -

Related: The Best Smart Watch ever
Sources: CNET, WallStreet.org, VCPost

There are many ways to decode QR Code these days. Here is an attempt to detect QR Code in an image to manipulate within OpenCV.

1. Detection of QR Code Identification markers

We start of the topic by discussing something that is not a part of this sample program. If you need to get on with it, you can skip directly to "Step 1".

The first task is to identify reliable patterns in the QR Code as show above. This can be determined using the technique described below.

A hypothetical Ratio Theorem:

Definition: Ratio of the Areas of N number of two dimensional polygons remain invariant to the uniform geometric transformation.

If a_r is the area of a polygon r then,

a₁ : a_2...: a_N = R in 2D plane X then,

a’₁ : a’_{2 ...} : a’_N = R for any other 2D plane Y which is geometric transformation of X

Consider the following example marker in 2D plane A, the areas of the polygons a₁, a₂and a₃are in the ratio 7:5:3. Plane B is obtained by perspective transformation of plane A. However the areas of the polygons a'₁, a'₂and a'₃plane B can be resolved as multiple of 7, 5 and 3 respectively i.e., 7β:5β:3β or simply 7:5:3. The same is illustrated in the figure below-

Ratio of the areas of the polygons

Proof: I have none. May be some other time.

All great men are gifted with intuition. They know without reasoning or analysis, what they need to know.

This approach is not used in the sample program, instead the structured OpenCV Contour detection technique is used.

Actual Step 1

OpenCV Countour detection does much more then identifying contours in an image. It also stores the relationship and hierarchy amongst the contours. This is nicely explained in the OpenCV documentations and tutorials OpenCV Contour Hierarchy.

Applying contour detection to a QR Code, the contour tracing the perimeter of the pattern polygons has the following characteristics -

It is a contour with subsequent enclosed (nested) contours. Although looking at an Identification marker, you would expect to detect 3 'nested' contours, however the inner boundary is also accounted as a contour resulting in 5 nested contours as shown here.

Nested contours in Identification marker

2. Determining the three distinct Identification markers

Post identification the three markers of the QR Code, the key step now is to determine the orientation of the markers and the positions wrt each other. (i.e., to determine which among the three markers are top, right, bottom and in what order.)

This is achieved easily using a triangle. The triangle is formed by using the mass centers of each of the three contours as vertices. The Vertex not involved in the largest side is obviously out lying and turns out to be the "top" marker*. Differentiating markers "right" and "bottom" out of the remaining two vertices, requires calculating the slope of the line they form and the position of the marker "top" wrt to this line.

* Limitation: This assumption is not true for acute perspective angles. a different approach is required to resolve and is a limitation of current implementation.

Determination of QR Code Identification Markers

3. Identify the four corners of each Identification markers

In this step we provide the contour points of the polygon to the function which retrieves the four corners of the polygon. The method measures the distance of each point on the perimeter with the center to determine four farthest points. These are likely to be the vertices of the polygon.

This function is implemented and well documented as part of OpenAR. More info openAR.

4. Determining the fourth point of the QR Code

Once four corners of all the three identification markers are obtained it is easy to estimate the fourth corner of the QR Code. The estimation is done by extending the lines forming the boundaries of the other two identification markers namely RIGHT and BOTTOM as shown in the figure below.

The line formed by O[3] and O[2] in BOTTOM identification marker is extended. Similarly line formed by M[1] and M[2] of RIGHT identification marker is extended to meet at N,this estimated position serves as the forth corner of the QR Code.

Reference identification objects in the QR Code

5. Orientation and Perspective correction

Having now obtained the 4 corners of the QR Code, namely L[0], M[1], N and O[3], we can apply OpenCV warpPerspective() function to restore the QR Code to readable position.

QR Code Orientation

6. QR Code decoding

QR Code thus recovered from the frame can now be used to extract the data. There are several libraries that are capable and compatible with OpenCV such as ZBar.

Note: This step is not part of the sample.

Another useful library libdecoderqr that was demonstrated in earlier posts, can also be explored. Link