OpenCV: QR Code detection and extraction


       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 ar is the area of a polygon r then, 
a1 : a2... : aN = R in 2D plane X then, 
a’1 : a’2 ... : aN = 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 a1, a2 and aare in the ratio 7:5:3. Plane B is obtained by perspective transformation of plane A. However the areas of the polygons a'1, 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



Source:
Git: https://github.com/bharathp666/opencv_qr.git

Download:
Download from DsynFLO box folder - https://app.box.com/s/191dc0l9hr37orltufok

License:
ZERO License.

References:
OpenCV 2D Image co-ordinate system - Link

Equation of a line - Link
Equation of a line with 2 known points -Link
Solutions to equation of a line - Link
Position of a point with respect to a straight line - Link
Perpendicular distance of point from a line formed by two other points - Link
Slope of a line  - Link

21 comments:

  1. image.cpp:6:10: fatal error: opencv2/opencv.hpp: No such file or directory
    how to solve this?

    ReplyDelete
  2. At tage din medicin som ordineret eller medicinoverholdelse er vigtig for at kontrollere kroniske tilstande,
    behandling af midlertidige tilstande og generel langvarig sundhed og velvære. En personlig forbindelse med din sundhedsudbyder eller apotek er en vigtig del af overholdelse af medicin.

    imovane
    køb imovane i danmark
    imovane 7 5 mg
    reductil sibutramin 15mg
    oxikodon pris
    tramadol 100mg

    ReplyDelete
  3. Taking your medicine as prescribed or medication adherence is important for controlling chronic conditions,
    treating temporary conditions, and overall long-term health and well-being. A personal connection with your health-care provider or pharmacist is an important part of medication adherence.

    imovane
    köpa imovane i danmark
    imovane 7 5 mg
    reductil sibutramine 15mg
    oxikodon pris
    tramadol 100mg

    ReplyDelete
  4. At tage din medicin som foreskrevet, eller at medicinsk overholdelse er vigtig for at kontrollere kroniske tilstande,
    behandling af midlertidige forhold og generelt langsigtet sundhed og velvære. En personlig forbindelse til din læge eller apotek er en vigtig del af overholdelse af medicin.

    imovane
    køb imovane i danmark
    imovane 7 5 mg
    reductil sibutramin 15mg
    xanax gadepris
    tramadol 100mg

    ReplyDelete
  5. Hvis du tager din medicin som foreskrevet, eller at medicinsk overholdelse er vigtig for at kontrollere kroniske tilstande,
    behandling af midlertidige tilstande og generelt langsigtet sundhed og velvære. En personlig forbindelse til din læge eller apotek er en vigtig del af overholdelsen af medicin.

    imovane
    køb imovane i danmark
    imovane 7 5 mg
    reductil sibutramin 15mg
    xanax gadepris

    tramadol 100mg

    ReplyDelete
  6. At tage din medicin som foreskrevet, eller at medicinsk overholdelse er vigtig for at kontrollere kroniske tilstande,
    behandling af midlertidige forhold og generelt langsigtet sundhed og velvære. En personlig forbindelse med din læge eller apotek er en vigtig del af medicinoverholdelse.

    imovane
    køb imovane i danmark
    imovane 7 5 mg
    reductil sibutramin 15mg
    xanax gadepris
    Köp Sobril 25 mg

    ReplyDelete
  7. Å ta medisinen slik den er foreskrevet, eller medisinadhesjon er viktig for å kontrollere kroniske tilstander,
    behandling av midlertidige forhold og generell langsiktig helse og velvære. En personlig forbindelse med helsepersonell eller apotek er en viktig del av medisinering.

    Kjøp imovane online Norge
    Zolpidem kjøp online
    kjøpe imovane i sverige
    Köpa Reductil 15mg i Sverige
    kop sobril utan recept
    tramadol 100mg

    ReplyDelete
  8. Taking your medicine as prescribed or medication adherence is important for controlling chronic conditions,
    treating temporary conditions, and overall long-term health and well-being. A personal connection with your health-care provider or pharmacist is an important part of medication adherence.

    Kjøp imovane online Norge
    Zolpidem køb online
    köpa imovane i sverige
    Köpa Reductil 15mg i Sverige
    kop sobril utan recept
    kop concerta 54 mg i sverige

    ReplyDelete
  9. treating temporary conditions, and overall long-term health and well-being. A personal connection with your health-care provider or pharmacist is an important part of medication adherence.

    Kjøp imovane online Norge
    köpa imovane i danmark
    køb imovane i sverige
    reductil
    sobril uten resept
    adderall sverige

    ReplyDelete
  10. Å ta medisinen som foreskrevet eller medisinering er viktig for å kontrollere kroniske tilstander,
    behandling av midlertidige forhold og generell langsiktig helse og velvære. En personlig forbindelse med helsepersonell eller apotek er en viktig del av medisinering.

    Kjøp imovane online Norge
    kjøpe imovane i danmark
    kjøp imovane i sverige
    reductil
    sobril uten resept
    adderall sverige

    ReplyDelete