QR Code Pattern Recognition and Message Extraction

The goal of this project is to successfully detect and reconstruct the perfect QR-code pattern and then decode and extract the message and information within. Usually, the QR-code images are corrupted, Blurred or at least rotated which makes the pattern recognition harder than simple scenarios.

You can check the relevant links as below:

Introduction

The following image demonstrates a damaged QR-Code:

.

In this situation, robust algorithms can effectively recognize specific patterns in the image and reconstruct the main matrix of a quick response code. The project has two main part:

In the first part of this project the implemented software, which is developed using MATLAB, successfully recognizes the main QR pattern and then extracts the QR-Matrix. Here’s an example of performing this phase

Then by using decoding techniques, the message is extracted from the QR-code. The QR-matrix might be corrupted, i.e. we probably lost some amount of information. According to this scenario, QR-codes are made by Error-Correction Coding which helps us through the decoding process. As an example a sample final output depicted in the following image: 

.

Running the Code and Technical Considerations

Run Mfiles/MAIN.m file. Two things need to be considered:

  • The version of the QR-Code should be known and specified by the user although brute-force search can be done by the user too. In other words, if the user does not know the version of QR-Code, he/she has to test all the six versions supported by the code by inputting the version number.
  • The other important thing is that the path of the input image has to be determined by the user.

The following code of the MAIN.m file demonstrates the two aforementioned matters.

prompt = {'Please input the version:'};
dlg_title = 'Version';
num_lines = 1;
def = {'2'};
answer = inputdlg(prompt,dlg_title,num_lines,def);
[version, ~] = str2num(answer{1});
module=4*version+17;    % Number of modules(General formula=4*(Version Number)+17)  
Im = imread('path_to_image');     % Input image.

Reliability

The reliability is based on two important consideration:

  • The first one is whether the image processing part can extract the correct QR pattern or not?
  • The second one is that is we have the correct pattern of the QR code, whether we can decode it or not?

Error Correction Reliability

The second item related to the number of errors that the Reed-Solomon decoder should correct. If the error is more than the maximum ability of the error correction then the message cannot be correctly and fully decoded. Since this part is not the main goal of this project/course so we don’t go deep any further in this area.

QR Code Pattern Recognition Ability

There is different scenarios and different approaches to overcome the deficiencies. We investigate them from the easy to the worst-case scenario.

Three Finder Pattern and one Alignment Pattern

Suppose that we have a clear image and a straight point of view. This is the easiest scenario. We believe that the software can easily detect the finder patterns and alignment pattern and the QR code reconstruction would be easy. In other scenarios even if the image is blurred or damaged, if we can find these 4-points, then we can perfectly reconstruct the QR code.

Limitation

The caveat is that what if the simulation finds a wrong alignment pattern or finder patter? The answer is according to the characteristics of the finder patter it is very unlikely to find a wrong finder pattern. The software has been tested for a wide variety of images. The problem is that it is likely for software to find a point as the Alignment Pattern while it is not!! The reason that we have to add another diagonal ration search for AP candidates is to prevent this phenomenon and by testing different test images we conclude that the developed software is reliable to that even.

Three Finder Pattern and no Alignment Pattern

Sometimes the software cannot find the AP because there might be no AP in a damaged image or there is but the software cannot find the Alignment Pattern. The former has no solution for finding AP but for the later we can allow more error in searching for the alignment pattern. This ability is defined in the software.

Limitation

The caveat is that allowing more error might lead to finding an Alignment Pattern which is not the correct one. The final solution for that which prevents this issue is that if the software cannot detect AP then ignore it and use the last corner of the QR-Code as the fourth point for perspective transformation. But the previous algorithm that we developed for this task was not very precise because if the image is not from a straight point of view the if the looking angle is far from 90 even by 20 degrees, then the software fails to find the fourth corner of the QR-Code\footnote{Fourth corner refers to the corner which is not connected to any of three finder patterns} pattern. In better words, it finds something which is not the correct one. The last algorithm that we implemented for this issue is to find two candidates for the fourth corner and using the average. According to the test images that we used for this algorithm, it is more efficient than the previous one.

Less Than Three Finder Pattern

If the simulation cannot find more than three finder pattern then it is very difficult to tackle this problem. It may happen in very rare scenarios in which the image is very blurred and almost the pattern cannot be seen. The solution is to use different thresholding in order to find and locate the finder patterns and separators. In this scenario, we try the previous approach for finding the fourth corner of the QR code and try to reconstruct the pattern.

Advantage of Algorithm for Finding the Fourth Corner

The advantage of finding the fourth corner is that is lots of scenarios we can have a straight image from the pattern whether blurred and noisy or not. Using this method we don’t need to have the Alignment Pattern location. It might be less reliable but if there is not any other choice it can be applied.

How to make a contribution

The simulation sometimes fails to decode the version 5-Q and 5-H QR code because of the more complex interleaving pattern of the data and error correction code-words. The author is working on modifying the software to successfully decode 5-Q and 5-H QR codes and any contribution is more than welcome for that part or any other parts.

Test

In order to demonstrate precision and authentication of software, different test images have been tested. Note that this project is restricted to QR codes version-1 through version-6.

Scroll to Top