$30
Project 4 - QR Code Reader
What to Submit
Submit this iPython Notebook--containing all your code for the programming exercises below--on learning suite.
Your notebook file should produce the relevant plots and also provide a short write-up with answers to the questions below.
Please also fill in here the time that each part took you:
Part A: FILL IN TIME -> 5 hrs
Part B: FILL IN TIME -> 12 hrs
Part C: FILL IN TIME -> 5 hrs
Tests: FILL IN TIME -> 4 hrs
Challenge 1: FILL IN TIME -> 2 hrs
Challenge 3: FILL IN TIME -> 1 hr
Write-up: FILL IN TIME ->
Understanding QR Codes
QR codes (short for Quick Response Codes) were invented in 1994, by the DENSO Corporation. These codes store data in two dimensions in the form of an array of contrasting regions. The information density of a QR code is much higher than a vanilla barcode; depending on the format used and the resolution of reader, over a thousand bytes can be encoded in a region the size of a postage stamp.
QR codes use a Reed–Solomon error correction based technology to help recover from errors in reading (for instance, caused by a smudge, badly printed code or other deformity).
Any QR code can be broken into the following sections:
On three corners of a QR code are square blocks that the reader uses to coarsely identify and then align the code. These will be of primary interest during the lab. Once these corners are identified and the image is aligned, the size of the QR code is determined by the timing information which alternates from black and white in both the vertical and horizontal direction.
Once the image is aligned and the size determined, the QR code is discretized, undergoes an Xor with a particular mask given the format information, and read bit for bit in the following order:
For more details about the decoding process, see the DataGenetics Wounded QR Codes Blog.
For this lab, we will focus primarily the computer vision side of QR codes, which involves detecting, aligning, and discretizing QR codes so that they can be read properly.
import cv2 as cv
import matplotlib.pyplot as plt
import numpy as np
import scipy.ndimage as ndi
Part A: Finding Corners
QR codes are designed with a very specific pattern so that can efficiently be detected, oriented, and decoded. The first step to detecting a QR code is finding the position markers that are always present in three of the four corners. These position markers always have a black/white/black/white/black ratio of 1:1:3:1:1, no matter the angle they are approached from.
Preprocess your image by thresholding to black and white. Scan across rows of the image, marking locations that have the 1:1:3:1:1 ratio (note: this is most easily done by keeping multiple counters for black and white pixels).
Once you have candidate locations, verify the locations by also scanning vertically, diagonally and in other directions. Also complete a non maximal suppression to get your final three candidate points.
class Region:
def __init__(self, is_white: bool, start: int, end: int):
self.is_white = is_white
self.start = start
self.end = end
self.dist = end-start
self.center = int((start+end)/2)
def equals_with_err(num1, num2, err=3):
return num2 <= num1+err and num2 >= num1-err
# returns whether the pt is now "confirmed" or not
def append_centers(pt_arg, unconfirmed_arg, confirmed_arg) -> bool:
if pt_arg in unconfirmed_arg:
confirmed_arg.append(pt_arg)
return True
unconfirmed_arg.append(pt_arg)
return False
def center_is_11311(regions, c) -> bool: # c is the center, returns the width of smaller regions, i.e. the "1"
d1, d2, d3, d4, d5 = regions[c-2].dist, regions[c-1].dist, regions[c].dist, regions[c+1].dist, regions[c+2].dist
return equals_with_err(d1,d2,1) and equals_with_err(d1,d4,1) and equals_with_err(d1,d5,1) and equals_with_err(d1*3, d3, 3)
def pre_process(img_arg):
return np.where(img_arg > 130, 255, 0)
# This algorithm assumes a square image, i.e. width == height
def parse(img_arg):
shape = img_arg.shape
rows, cols = shape[0], shape[1]
centers_unconfirmed, centers_confirmed = [], []
ratio_width = 0
for i in range(rows):
row_regions, col_regions = [], []
row_is_white, col_is_white = True, True
row_start, col_start = 0, 0
for j in range(cols):
if j == 0:
row_is_white = img_arg[i, j] == 255
col_is_white = img_arg[j, i] == 255
elif j == cols-1:
row_regions.append(Region(row_is_white, row_start, j))
col_regions.append(Region(col_is_white, col_start, j))
else:
if img_arg[i, j-1] != img_arg[i, j]:
row_regions.append(Region(row_is_white, row_start, j))
row_start = j
if img_arg[j-1, i] != img_arg[j, i]:
col_regions.append(Region(col_is_white, col_start, j))
col_start = j
if len(row_regions) >= 5:
for j in range(2, len(row_regions)-2):
if center_is_11311(row_regions, j):
if append_centers([i, row_regions[j].center], centers_unconfirmed, centers_confirmed):
ratio_width = row_regions[j-2].dist
if len(col_regions) >= 5:
for j in range(2, len(col_regions)-2):
if center_is_11311(col_regions, j):
if append_centers([col_regions[j].center, i], centers_unconfirmed, centers_confirmed):
ratio_width = col_regions[j-2].dist
return centers_confirmed, ratio_width
Part B: Finding The Fourth Point and Aligning with a Homography
QR codes only contain three known corner points, but homographies require four points to be defined. If the warping present in the image is small enough, an affine transform is generally sufficient to find the fourth point (i.e. the x,y coordinate difference between point 1 and point 2 will be the same as the x,y coordinate difference between point 3 and point 4). Use this assumption to find the fourth point.
Once you have the four points, generate the homography that would align the QR code with the x,y axes. Crop the aligned image until only the QR code is visible.
# Assumption: we know the point missing is the bottom-right corner
def get_fourth_pt(pts_arg, shape_arg):
if len(pts_arg) != 3:
raise Exception("Must have 3 and only 3 points to get a fourth using this method")
mid_pt = min(pts_arg, key=lambda pt: dist_to_points(pt, pts_arg))
ref_pt = list(filter(lambda pt: pt != mid_pt, pts_arg))[0]
delta_x = mid_pt[0] - ref_pt[0]
delta_y = mid_pt[1] - ref_pt[1]
rem_pt = list(filter(lambda pt: pt not in [mid_pt,ref_pt], pts_arg))[0]
x = rem_pt[0] - delta_x
y = rem_pt[1] - delta_y
return [x, y]
def dist_to_points(pt_arg, pts_arg):
dist = 0
for pt in pts_arg:
dist += pow(pt_arg[0]-pt[0], 2) + pow(pt_arg[1]-pt[1], 2)
return dist
def get_pts_prime(shape_arg, ratio_width, pts_arg):
rows,cols = shape_arg[0], shape_arg[1]
offset = int(ratio_width*shape_arg[0]*3.5/(pts_arg[3][1]-pts_arg[0][1]+(ratio_width*7)))
top_left = [offset, offset]
top_right = [offset, cols-offset]
bot_left = [rows-offset, offset]
bot_right = [rows-offset, cols-offset]
return [top_left, bot_left, bot_right, top_right]
# Returns pts_arg as [top_left, bot_left, bot_right, top_right]
def ordered_pts(pts_arg):
s = sorted(pts_arg, key=lambda ele: ele[0])
t = s[:2]
t_left = min(t, key=lambda ele: ele[1])
t_right = max(t, key=lambda ele: ele[1])
b = s[2:]
b_left = min(b, key=lambda ele: ele[1])
b_right = max(b, key=lambda ele: ele[1])
return [t_left, b_left, b_right, t_right]
def rotate_pts(pts_arg, fourth_pt_arg):
while pts_arg[2] != fourth_pt_arg:
pts_arg = [pts_arg[3]] + pts_arg[:3]
return pts_arg
def align(img_arg):
img_arg = pre_process(img_arg)
confirmed_pts, width = parse(img_arg)
fourth_pt = get_fourth_pt(confirmed_pts, img_arg.shape)
pts = ordered_pts(confirmed_pts + [fourth_pt])
pts_prime = get_pts_prime(img_arg.shape, width, pts)
pts = rotate_pts(pts, fourth_pt)
# The way we calculated the points is backwards from how cv would do it, so we must reverse the x and y values.
pts = list(map(lambda x: [x[1], x[0]], pts))
pts_prime = list(map(lambda x: [x[1], x[0]], pts_prime))
homography = cv.findHomography(np.array(pts), np.array(pts_prime), cv.RANSAC, 5.0)[0]
res = np.array(cv.warpPerspective(np.array(img_arg.copy(), dtype=float), homography, img_arg.shape), dtype=int)
return res, width
Part C: Discretization
Now that the image is aligned, the QR code needs to discretized so that each block is a single bit, rather than a group of pixels. The simplest way to do this is to count the number of black and white pixels in a region and assign the block to the highest count. However, to do this, the size of the QR code needs to be determined. All QR codes have an odd number of bits per row and column, starting at size 21 and incrementing by 4 (i.e. 21x21, 25x25, 29x29, ...). For this lab, you will only need to check for sizes from 21 to 33.
To check if a QR code matches a given size, discretize the QR code asumming the given size. Then, determine if the timing information alternates in the appropriate manner (see the Understanding QR Codes for more information). If the timing information is valid, then you can assume that the QR code is the given size.
Once you have the correct size, discretize the QR code accordingly and return a Numpy array of True/False values.
# Assume we alredy know which ones are top-left and top-right
def get_start_row(img_arg, expected_width):
for row in range(img_arg.shape[0]):
if img_arg[row,0] == 255:
# return img_arg[row-int(expected_width*3/4), ::]
return img_arg[row-int(expected_width*2/3), ::]
raise Exception("Didn't find the row of timing marks")
# Returns how many pixels are white/black in a row without encountering another pixel of different color
def num_contin_pixels(row_arg, expected_white: bool):
num_pixels = 0
for i in range(len(row_arg)):
temp_is_white = row_arg[i] == 255
if temp_is_white != expected_white or i == len(row_arg)-1:
return num_pixels
# Check the expected pattern, we could expect 7 black bits, 1 white spacing bit, timing mark bit, etc.
def has_bit(cross_line, expected_num_bits: int, expected_white: bool, ave_width: int, err=1):
is_white = cross_line[0] == 255
if expected_white != is_white:
return None
num_pix = 1
for i in range(1, len(cross_line)):
temp_is_white = cross_line[i] == 255
if is_white != temp_is_white or i == len(cross_line)-1:
actual_num_bits = int(num_pix/ave_width)
if actual_num_bits <= expected_num_bits+err and actual_num_bits >= expected_num_bits-err:
return cross_line[num_pix::]
else:
return None
num_pix += 1
# Given a row across 2 of the 3 corners, return the average num of pixels of bit width
def get_ave_width_float(row_arg):
is_white = row_arg[0] == 255
num_pixels = 1
for i in range(1, len(row_arg)):
temp_is_white = row_arg[i] == 255
if temp_is_white != is_white or i == len(row_arg)-1:
return num_pixels/7
num_pixels += 1
def get_ave_width(row_arg) -> int:
return int(get_ave_width_float(row_arg))
# Given the expected num of bits, return a list of tuples representing
# groups of bits, where tuple[0] == num_bits, tuple[1] == is_white
def get_pattern(size: int):
pattern = [(7, False), (1, True)]
temp_is_white = False
for i in range(size-16):
pattern.append((1, temp_is_white))
temp_is_white = not temp_is_white
pattern.append((1, True))
pattern.append((7, False))
return pattern
# pattern expects a list of tuples, where tuple[0] == num_bits, tuple[1] == is_white
# Will always be 7 bits on the left, then 1 white bit, then x timing marks, then 1 white bit,
# then 7 black bits so if size=21, then 21-7-1-7-1 = 21-16 = 5 timing marks.
def has_pattern(row_arg, expected_width: int, pattern) -> bool:
for tup in pattern:
if len(row_arg) == 0: # sanity check
return False
row_arg = has_bit(row_arg, tup[0], tup[1], expected_width)
if row_arg is None:
return False
return True
def is_valid_qr(start_row_arg, size, expected_width):
return has_pattern(start_row_arg.copy(), expected_width, get_pattern(size))
def get_qr_size(img_arg, sizes_to_check, orig_width):
# start from the top down until QR code ends
# then start going right until it is white, we are now at the timing marks.
start_row = get_start_row(img_arg, orig_width).copy() # doesn't really need to be a copy, but just in case
# We update the width because it might be higher now. Hopefully updating from the first 7 bits is enough.
updated_width = get_ave_width(start_row)
for size in sizes_to_check:
if is_valid_qr(start_row, size, updated_width):
return size
return None
def discretize(img_arg, qr_size_arg: int, expected_width: float):
res = np.zeros((qr_size_arg, qr_size_arg), bool)
for row in range(qr_size_arg):
for col in range(qr_size_arg):
expected_row = int(row*expected_width+int(expected_width/2))
expected_col = int(col*expected_width+int(expected_width/2))
res[row,col] = True if img_arg[expected_row, expected_col] == 255 else False
return res
Part D: Decoding
QR codes are decoded using a very particular block pattern (see Understanding QR Codes). However, for simplicity, we have implemented this decoder for you. To use it, simply call decode() from the decoder.py file and feed it your 2D Numpy array. It will return a string with the QR code data.
Note: You may need to run conda install beautifulsoup4 and conda install requests to get the decoder to run.
from decoder import decode
def get_decoded(discretized_arg):
return decode(discretized_arg)
# Unless a cell above needs debugging, this is the only cell that we should deal with, acting as an interface
def do_everything(img_arg):
plt.subplot(2, 2, 1), plt.imshow(img_arg, cmap="gray")
aligned, orig_width = align(img_arg)
plt.subplot(2, 2, 2), plt.imshow(aligned, cmap="gray")
plt.show()
qr_size = get_qr_size(aligned, (21, 25, 29, 33), orig_width)
updated_width = aligned.shape[0]/qr_size
discretized = discretize(aligned.copy(), qr_size, updated_width)
decoded = get_decoded(discretized)
print(decoded)
Tests
Once you have your full algorithm working, run your code on the five test images in the QR_codes folder. Show your results below.
image = cv.imread("QR_codes/test1.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/test2.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/test3.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/test4.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/test5.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
http://byu.edu
http://byu.edu
http://byu.edu
http://byu.edu
http://DataGenetics.com
Grading and Challenges
Points for this assigment will be assigned as follows (100 points total):
[20 pts] Code that correctly finds the three corners of the QR code.
[20 pts] Code that aligns the QR code and crops appropriately.
[20 pts] Code that correctly discretizes for an arbitrary size.
[10 pts] For a full algorithm that correctly scans the five test images.
The last 30 points are earned through completing a subset of the following challenges:
[15 pts] Correctly scan a QR code that is misaligned by more than 90 degrees (e.g. challenge1.png)
[15 pts] Correctly scan a QR code that is perspective shifted by using the additional alignment square present in larger QR codes. (e.g. challenge2.png)
[15 pts] Correctly scan a QR code that is surrounded by additional pixels (e.g. challenge3.png)
[15 pts] Correctly scan a QR code with large amounts of noise and distortion (e.g. challenge4.png)
[30 pts] Implement a Code 128 1D bar code scanner (e.g. challenge5.png)
You may earn up to 15 points extra credit for additional challenges you complete.
image = cv.imread("QR_codes/challenge1.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/challenge3.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
image = cv.imread("QR_codes/challenge4.png", cv.IMREAD_GRAYSCALE)
do_everything(image)
http://byu.edu
http://byu.edu
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/2757596747.py in <module>
6
7 image = cv.imread("QR_codes/challenge4.png", cv.IMREAD_GRAYSCALE)
----> 8 do_everything(image)
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/1391444194.py in do_everything(img_arg)
5 plt.subplot(2, 2, 2), plt.imshow(aligned, cmap="gray")
6 plt.show()
----> 7 qr_size = get_qr_size(aligned, (21, 25, 29, 33), orig_width)
8 updated_width = aligned.shape[0]/qr_size
9 discretized = discretize(aligned.copy(), qr_size, updated_width)
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/2505462664.py in get_qr_size(img_arg, sizes_to_check, orig_width)
6 updated_width = get_ave_width(start_row)
7 for size in sizes_to_check:
----> 8 if is_valid_qr(start_row, size, updated_width):
9 return size
10 return None
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/3106927643.py in is_valid_qr(start_row_arg, size, expected_width)
1 def is_valid_qr(start_row_arg, size, expected_width):
----> 2 return has_pattern(start_row_arg.copy(), expected_width, get_pattern(size))
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/3155920910.py in has_pattern(row_arg, expected_width, pattern)
6 if len(row_arg) == 0: # sanity check
7 return False
----> 8 row_arg = has_bit(row_arg, tup[0], tup[1], expected_width)
9 if row_arg is None:
10 return False
/var/folders/7g/hr65gkl12213wbsg6s4lkmqm0000gq/T/ipykernel_50281/1232363264.py in has_bit(cross_line, expected_num_bits, expected_white, ave_width, err)
8 temp_is_white = cross_line[i] == 255
9 if is_white != temp_is_white or i == len(cross_line)-1:
---> 10 actual_num_bits = int(num_pix/ave_width)
11 if actual_num_bits <= expected_num_bits+err and actual_num_bits >= expected_num_bits-err:
12 return cross_line[num_pix::]
ZeroDivisionError: division by zero
## Write-up: Provide an explanation for the following items: * Which part of this lab did you find most difficult? * For each challenge completed, explain how you were able to solve the problem presented. * What improvements would you recommend for this lab?
Your Write-up Here
Part B took me a really long time to debug. I was originally generating my own homography, but didnt matter if I used a third party library or my own homography, the QR code wouldn’t align properly. Then I realised it was due to the fact that cv would read the pixels in reverse order, so I just flipped the x and y and it worked great.
Challenge 1: I pre-defined an order in which my methods would expect input/output as top-left, bot-left, bot-right, top-right. With this in mind, the 3 squares could be in any adjacent, so I needed a consistent way to map my fourth point needed for the homography. What I did was create a little method that would return the middle corner. Then I would pick any other corner and define the transformation from my middle corner to the adjacent corner. I then applied the same transformation from the remaining corner. Once I defined my fourth point, all I had to do was rotate the image. I did this by just shifting the elements by 1 until the empty corner was in place. I did notice that the decode method still worked if I didn’t rotate the QR code, but I had already written the rotating method so I kept it there.
Challenge 3: My methods found the 3 corners as normal. I then scaled the mapping of the points we’d expect our corners to be in based on the size of the image and the size of the QR code. I just had to modify the offset to be offset*bit_width*img_width/qr_width. Doing so would map the corners properly and the homography would do the rest.
Challenge 4: I didn’t complete this challenge. I found that I was able to properly align my QR code, but my discretisation kept being wrong. I figured that the pre-processing I was doing wasn’t enough, but I could find which bits where incorrect. I figured I’d still get some extra credit points for being able to align the image.
The biggest change I’d make to the lab (and really to almost every lab so far) is to have more cases to compare against. For example, in this lab it would have been a game changer for me to have the expected discretisation of each QR code. Because I didn’t, debugging was far more difficult than it would have been otherwise. I would have liked to know which bits were wrong and try to fix it, but since I had already gotten 2 challenges I thought it wasn’t worth the time and effort for a few more extra points.