joris
/
digilyzer
1
0
Fork 0
Code
digilyzer/qrdecode.py

1550 lines
49 KiB
Python
Raw Permalink Normal View History

First release of Digilyzer
2019-12-08 15:07:19 +01:00
"""
Decoding QR codes from high-quality images.
The algorithms in this module are unsophisticated and will
only work for computer generated, non-rotated, undamaged
QR codes. This module can not be used to process QR codes
from photographs or scanned images.
Only Model 2 QR codes are supported.
"""
import sys
import numpy as np
import PIL
# The Reed-Solomon codes for QR error correction are computed over
# the finite field GF(2**8) = GF(2)[a] / (a**8 + a**4 + a**3 + a**2 + 1).
#
# Elements of this field are represented as 8-bit unsigned integers,
# where each bit represents a coefficient of the polynomial with
# the least significant bit corresponding to the lowest order term.
#
# The element "a" (represented as integer value 2) is a primitive element
# of this field.
#
REED_SOLOMON_GF_POLY = 0b100011101
# Construct lookup tables for exp/log:
# reed_solomon_gf_exp[k] = a**k
# reed_solomon_gf_log[a**k] = k
reed_solomon_gf_exp = 256 * [0]
reed_solomon_gf_log = 256 * [0]
v = 1
for k in range(1, 256):
v = (v << 1) ^ ((v >> 7) * REED_SOLOMON_GF_POLY)
reed_solomon_gf_exp[k] = v
reed_solomon_gf_log[v] = k
reed_solomon_gf_exp[0] = 1
reed_solomon_gf_log[1] = 0
del k, v
class QRDecodeError(Exception):
"""Raised when QR decoding fails."""
pass
def debug_msg(msg):
"""Print a debug message."""
print(msg, file=sys.stderr)
def bits_to_word(bits):
"""Convert a list or array of bits to an integer.
Parameters:
bits: List or array of bits, starting with least-significant bit.
Returns:
Unsigned integer value of the bits.
"""
v = 0
p = 1
for b in bits:
if b:
v += p
p *= 2
return v
def decode_version_word(raw_word):
"""Decode error correction bits in the version information.
Parameters:
raw_word (int): 18-bit integer containing raw version information.
Returns:
6-bit integer containing the decoded QR code version.
Raises:
QRDecodeError: If the version information can not be decoded.
"""
# The version information uses a (18,6) BCH code with generator
# polynomial x**12 + x**11 + x**10 + x**9 + x**8 + x**5 + x**2 + 1.
poly = 0b1111100100101
# This code only detects bit errors but does not correct them.
# TODO : implement proper error correction
v = raw_word
while v >= 2**12:
if v & 1:
v ^= poly
v >>= 1
if v:
raise QRDecodeError("Data corruption in version information")
return raw_word >> 12
def decode_format_word(raw_word):
"""Decode error correction bits in the format word.
Parameters:
raw_word (int): 15-bit integer containing raw format information.
Returns:
5-bit integer containing the decoded format information.
Raises:
QRDecodeError: If the format information can not be decoded.
"""
# The format word uses a (15,5) BCH code with generator
# polynomial x**10 + x**8 + x**5 + x**4 + x**2 + x + 1.
poly = 0b10100110111
# This code only detects bit errors but does not correct them.
# TODO : implement proper error correction
v = raw_word
while v >= 2**10:
if v & 1:
v ^= poly
v >>= 1
if v:
raise QRDecodeError("Data corruption in format bits")
return raw_word >> 10
def quantize_image(image):
"""Quantize the specified image into black and white pixels.
Parameters:
image (PIL.Image): Input image.
Returns:
2D Numpy array where 0 = black, 1 = white.
"""
# Convert to greyscale.
img_grey = image.convert(mode="L")
# Extract pixel values.
data_grey = np.array(img_grey)
# Quantize to black-and-white.
min_pixel = np.min(data_grey)
max_pixel = np.max(data_grey)
threshold = (min_pixel + max_pixel) // 2
data_bw = (data_grey > threshold).astype(np.uint8)
return data_bw
def scan_boundaries(img_data):
"""Scan horizontally to detect color boundaries.
Returns (boundpos, boundmap).
boundpos is a 2D array of shape (nrow, ncol+2).
boundpos[y,k] is the X coordinate of the first pixel after the k-th
color boundary on row y.
boundpos[y,0] == 0 by definition.
boundpos[y,k] == ncol if k is larger than the number of color boundaries.
boundmap is a 2D array of shape (nrow, ncol).
boundmap[y,x] is the number of color boundaries to the left of pixel (x,y).
"""
(nrow, ncol) = img_data.shape
boundpos = np.zeros((nrow, ncol + 2), dtype=np.uint32)
boundmap = np.zeros((nrow, ncol), dtype=np.uint32)
for y in range(nrow):
(edges,) = np.where(img_data[y, 1:] != img_data[y, :-1])
boundpos[y, 0] = 0
if len(edges) > 0:
boundpos[y, 1:1+len(edges)] = edges + 1
boundpos[y, 1+len(edges):] = ncol
steps = np.zeros(ncol)
steps[edges+1] = 1
boundmap[y] = np.cumsum(steps)
return (boundpos, boundmap)
def check_position_detection(bounds):
"""Check whether the specified range of 5 intervals has the right
proportions to correspond to a slice through a position detection pattern.
An ideal slice through a position detection pattern consists of
5 intervals colored B,W,B,W,B with lengths proportional to 1,1,3,1,1.
Returns:
(center_coord, pixels_per_module) if this could be a position
detection pattern, otherwise (0, 0).
"""
# Expected relative positions of black/white boundaries
# within the position detection pattern.
expect_bound_pos = [-3.5, -2.5, -1.5, 1.5, 2.5, 3.5]
if (len(bounds) != 6) or (bounds[4] >= bounds[5]):
return (0, 0)
pattern_width = float(bounds[5] - bounds[0])
middle_width = float(bounds[3] - bounds[2])
if (pattern_width < 7) or (middle_width < 3):
return (0, 0)
center = float(sum(bounds)) / 6.0
pitch = (pattern_width + middle_width) / 10.0
good = True
for k in range(6):
rel_bound_pos = (bounds[k] - center) / pitch
if abs(rel_bound_pos - expect_bound_pos[k]) >= 0.5:
good = False
break
if not good:
return (0, 0)
return (center, pitch)
def find_position_detection_patterns(img_data):
"""Locate QR code position detection patterns.
Parameters:
img_data (ndarray): 2D Numpy array containing black-and-white image.
Returns:
List of tuples (x, y, dx, dy).
Note that integer values of X/Y coordinates refer to pixel corners.
The upper-left corner of the image has coordinates (0, 0).
The center of the upper-left pixel has coordinates (0.5, 0.5).
The lower-right corner of the image has coordinates (nrow, ncol).
"""
(nrow, ncol) = img_data.shape
if (nrow < 7) or (ncol < 7):
return []
# Scan for horizontal and vertical color boundaries.
(hbounds, hmap) = scan_boundaries(img_data)
(vbounds, vmap) = scan_boundaries(img_data.transpose())
patterns_raw = []
# Scan each row to find position detection patterns.
for y in range(nrow):
# Start at the first black interval.
bx = 0
if img_data[y, 0] != 0:
bx += 1
# Consider each range of five intervals with colors B,W,B,W,B.
while hbounds[y, bx+4] < ncol:
# Check that this horizontal slice has the correct
# proportions for a position detection pattern.
(cx, dx) = check_position_detection(hbounds[y, bx:bx+6])
if dx > 0:
# Check that the vertical slice also has a pattern.
x = int(cx)
by = vmap[x, y] - 2
if img_data[y, x] == 0 and by >= 0 and by + 4 < nrow:
(cy, dy) = check_position_detection(vbounds[x, by:by+6])
if (dy > 0) and (dx <= 2 * dy) and (dy <= 2 * dx):
# Add this location as a candidate pattern.
patterns_raw.append((cx, cy, dx, dy))
bx += 2
# Discard duplicate entries.
patterns = []
for fnd in patterns_raw:
(cx, cy, dx, dy) = fnd
dupl = False
for (tcx, tcy, tdx, tdy) in patterns:
if ((abs(tcx - cx) < 3 * max(dx, tdx))
and (abs(tcy - cy) < 3 * max(dy, tdy))):
dupl = True
break
if not dupl:
patterns.append(fnd)
return patterns
def make_finder_triplets(patterns):
"""Select three position detection patterns that could
together form the finder pattern for a QR code.
If multiple finder triplets are feasible, return them all,
starting with the highest QR code version.
Parameters:
patterns: List of tuples describing position detection patterns.
Returns:
List of tuples (finder_ul, finder_ur, finder_dl).
"""
finder_triplets = []
# Try all candidates for the upper-left pattern.
for fnd in patterns:
(cx, cy, dx, dy) = fnd
# Search a matching pattern with horizontal separation.
for fndh in patterns:
(hcx, hcy, hdx, hdy) = fndh
# Check that pixel pitch is roughly compatible.
if 8 * abs(dx - hdx) > dx + hdx:
continue
if 8 * abs(dy - hdy) > dy + hdy:
continue
# Check that Y coordinates match.
if abs(cy - hcy) > dy + hdy:
continue
# Check that X separation is sufficient.
xsep = 2 * abs(cx - hcx) / (dx + hdx)
if xsep < 12:
continue
# Search a matching pattern with vertical separation.
for fndv in patterns:
(vcx, vcy, vdx, vdy) = fndv
# Check that pixel pitch is roughly compatible.
if 8 * abs(dx - vdx) > dx + vdx:
continue
if 8 * abs(dy - vdy) > dy + vdy:
continue
# Check that X coordinates match.
if abs(cx - vcx) > dx + vdx:
continue
# Check that X and Y separation are roughly compatible.
ysep = 2 * abs(cy - vcy) / (dy + vdy)
if ysep < 12 or ysep < 0.75 * xsep or ysep > 1.25 * xsep:
continue
# Identify upper-right and lower-left patterns,
# depending on rotation.
if (hcx - cx) * (vcy - cy) > 0:
# not rotated or 180 degrees rotated
fnd_ur = fndh
fnd_dl = fndv
else:
# 90 degrees or 270 degrees rotated
fnd_ur = fndv
fnd_dl = fndh
# Estimate QR code version.
qrver = (0.5 * (xsep + ysep) - 10) / 4.0
# Bonus point if QR code is non-rotated.
score = qrver
if hcx > cx and vcy > cy:
score += 1
finder_triplets.append((score, (fnd, fnd_ur, fnd_dl)))
# Sort by decreasing score.
finder_triplets.sort(reverse=True)
return [triplet for (score, triplet) in finder_triplets]
def extract_qr_version(img_data, finder_ul, finder_ur):
"""Extract the QR version from the upper-right version field.
Parameters:
img_data (ndarray): 2D array representing the quantized image.
finder_ul: Tuple representing the location of the upper-left
position detection pattern.
finder_ur: Tuple representing the location of the upper-right
position detection pattern.
Returns:
QR code version (range 1 .. 40).
Raises:
QRDecodeError: If the version information can not be decoded.
"""
(ul_cx, ul_cy, ul_dx, ul_dy) = finder_ul
(ur_cx, ur_cy, ur_dx, ur_dy) = finder_ur
# Create affine transform to specify the local QR matrix
# around the upper-right finder.
transform = np.zeros((3, 3))
if abs(ur_cx - ul_cx) > abs(ur_cy - ul_cy):
# not rotated or 180 degrees rotated
transform[0, 0] = ur_dx * np.sign(ur_cx - ul_cx)
transform[1, 1] = ur_dy * np.sign(ur_cx - ul_cx)
else:
# 90 degrees or 270 degrees rotated
transform[1, 0] = ur_dy * np.sign(ur_cy - ul_cy)
transform[0, 1] = -ur_dx * np.sign(ur_cy - ul_cy)
transform[0, 2] = ur_cx
transform[1, 2] = ur_cy
transform[2, 2] = 1.0
version_bits = []
for i in range(18):
x = i % 3 - 7
y = i // 3 - 3
xp = transform[0,0] * x + transform[0,1] * y + transform[0,2]
yp = transform[1,0] * x + transform[1,1] * y + transform[1,2]
xp = int(xp)
yp = int(yp)
version_bits.append(1 - img_data[yp, xp])
# Convert bits to word.
version_word_raw = bits_to_word(version_bits)
# Decode error correction bits.
qr_version = decode_version_word(version_word_raw)
if qr_version < 1 or qr_version > 40:
raise QRDecodeError("Unsupported QR code version {}"
.format(qr_version))
return qr_version
def locate_qr_code(img_data, triplet):
"""Consider the QR code defined by the specified finder triplet
and extract precise location, orientation and QR code version.
Parameters:
img_data (ndarray): 2D array representing the quantized image.
triplet: Tuple (finder_ul, finder_ur, finder_dl).
Returns:
Tuple (affine_transform, qr_version).
Raises:
QRDecodeError: If no QR code was detected.
"""
(finder_ul, finder_ur, finder_dl) = triplet
(ul_cx, ul_cy, ul_dx, ul_dy) = finder_ul
(ur_cx, ur_cy, ur_dx, ur_dy) = finder_ur
(dl_cx, dl_cy, dl_dx, dl_dy) = finder_dl
# Estimate the QR code version based on horizontal data.
hdist = ((2 * (ul_cx - ur_cx) / (ul_dx + ur_dx))**2
+ (2 * (ul_cy - ur_cy) / (ul_dy + ur_dy))**2)**0.5
qrver = round((hdist - 10) / 4)
# For QR versions higher than 6, decode the version information.
if qrver > 6:
qrver = extract_qr_version(img_data, finder_ul, finder_ur)
# Determine nominal separation between finders.
qrsep = 10 + 4 * qrver
# Determine module-to-pixel scaling and rotation.
transform = np.zeros((3, 3))
transform[0, 0] = (ur_cx - ul_cx) / qrsep
transform[1, 0] = (ur_cy - ul_cy) / qrsep
transform[0, 1] = (dl_cx - ul_cx) / qrsep
transform[1, 1] = (dl_cy - ul_cy) / qrsep
# Determine coordinates of upper-left coordinate.
transform[0, 2] = ul_cx - 3.5 * (transform[0, 0] + transform[0, 1])
transform[1, 2] = ul_cy - 3.5 * (transform[1, 0] + transform[1, 1])
transform[2, 2] = 1.0
return (transform, qrver)
def sample_qr_matrix(img_data, transform, qr_version):
"""Sample each module in the QR matrix.
Parameters:
img_data (ndarray): 2D array representing the quantized image.
transform (ndarray): Affine transform specifying the position,
size and orientation of the QR code.
qr_version (int): QR code version.
Returns:
2D square Numpy array containing the value of each module
(0 = white, 1 = black).
"""
qrsize = 17 + 4 * qr_version
xcoord = np.zeros((qrsize, qrsize))
xcoord[0] = np.arange(qrsize) + 0.5
xcoord[1:] = xcoord[0]
ycoord = xcoord.transpose()
xidx = transform[0,0] * xcoord + transform[0,1] * ycoord + transform[0,2]
yidx = transform[1,0] * xcoord + transform[1,1] * ycoord + transform[1,2]
xidx = xidx.astype(np.int32)
yidx = yidx.astype(np.int32)
# Clip coordinates to the image area.
(nrow, ncol) = img_data.shape
xidx = np.clip(xidx, 0, ncol - 1)
yidx = np.clip(yidx, 0, nrow - 1)
matrix = img_data[yidx, xidx]
matrix = 1 - matrix
return matrix
def extract_format_data(matrix):
"""Extract format information from the upper-left corner.
Parameters:
matrix (ndarray): 2D array containing the QR matrix.
Returns:
Tuple (error_correction_level, mask_pattern).
Raises:
QRDecodeError: If the format information can not be decoded.
"""
format_mask = 0b101010000010010
# Fetch format bits from matrix.
format_bits = []
for i in range(6):
format_bits.append(matrix[i, 8])
format_bits.append(matrix[7, 8])
format_bits.append(matrix[8, 8])
format_bits.append(matrix[8, 7])
for i in range(6):
format_bits.append(matrix[8, 5-i])
# Convert bits to word and apply the format mask.
format_word_raw = bits_to_word(format_bits)
format_word_raw ^= format_mask
# Decode error correction bits.
format_word = decode_format_word(format_word_raw)
# Decode error correction level and mask pattern.
error_correction_idx = ((format_word >> 3) & 3)
mask_pattern = (format_word & 7)
error_correction_table = "MLHQ"
error_correction_level = error_correction_table[error_correction_idx]
return (error_correction_level, mask_pattern)
def make_mask_pattern(qrsize, mask_pattern):
"""Generate the specified 2D XOR mask pattern.
Parameters:
qrsize (int): Size of the QR code (number of modules along one edge).
mask_pattern (int): Mask pattern reference from format information.
Returns:
2D array to be XOR-ed with the matrix before extracting codewords.
"""
xcoord = np.zeros((qrsize, qrsize), dtype=np.uint32)
xcoord[0] = np.arange(qrsize)
xcoord[1:] = xcoord[0]
ycoord = xcoord.transpose()
if mask_pattern == 0:
mask_val = (xcoord + ycoord) % 2
elif mask_pattern == 1:
mask_val = ycoord % 2
elif mask_pattern == 2:
mask_val = xcoord % 3
elif mask_pattern == 3:
mask_val = (xcoord + ycoord) % 3
elif mask_pattern == 4:
mask_val = (ycoord // 2 + xcoord // 3) % 2
elif mask_pattern == 5:
mask_val = (xcoord * ycoord) % 2 + (xcoord * ycoord) % 3
elif mask_pattern == 6:
mask_val = ((xcoord * ycoord) % 2 + (xcoord * ycoord) % 3) % 2
else:
mask_val = (xcoord + ycoord + (xcoord * ycoord) % 3) % 2
mask_bool = (mask_val == 0)
mask = mask_bool.astype(np.uint8)
return mask
def get_alignment_pattern_locations(qr_version):
"""Return a list of (x, y) locations of alignment patterns.
Parameters:
qr_version (int): QR code version.
Returns:
List of tuples (x, y) specifying the center location of
each alignment pattern.
"""
coord_tbl = {
1: [6],
2: [6, 18],
3: [6, 22],
4: [6, 26],
5: [6, 30],
6: [6, 34],
7: [6, 22, 38],
8: [6, 24, 42],
9: [6, 26, 46],
10: [6, 28, 50],
11: [6, 30, 54],
12: [6, 32, 58],
13: [6, 34, 62],
14: [6, 26, 46, 66],
15: [6, 26, 48, 70],
16: [6, 26, 50, 74],
17: [6, 30, 54, 78],
18: [6, 30, 56, 82],
19: [6, 30, 58, 86],
20: [6, 34, 62, 90],
21: [6, 28, 50, 72, 94],
22: [6, 26, 50, 74, 98],
23: [6, 30, 54, 78, 102],
24: [6, 28, 54, 80, 106],
25: [6, 32, 58, 84, 110],
26: [6, 30, 58, 86, 114],
27: [6, 34, 62, 90, 118],
28: [6, 26, 50, 74, 98, 122],
29: [6, 30, 54, 78, 102, 126],
30: [6, 26, 52, 78, 104, 130],
31: [6, 30, 56, 82, 108, 134],
32: [6, 34, 60, 86, 112, 138],
33: [6, 30, 58, 86, 114, 142],
34: [6, 34, 62, 90, 118, 146],
35: [6, 30, 54, 78, 102, 126, 150],
36: [6, 24, 50, 76, 102, 128, 154],
37: [6, 28, 54, 80, 106, 132, 158],
38: [6, 32, 58, 84, 110, 136, 162],
39: [6, 26, 54, 82, 110, 138, 166],
40: [6, 30, 58, 86, 114, 142, 170]
}
coords = coord_tbl[qr_version]
cmin = coords[0]
cmax = coords[-1]
align_locs = []
for y in coords:
for x in coords:
if ((x == cmin or y == cmin)
and (x in (cmin, cmax))
and (y in (cmin, cmax))):
# Skip alignment patterns that would collide
# with position detection patterns.
pass
else:
align_locs.append((x, y))
return align_locs
def get_data_locations(qr_version):
"""Return the locations of all modules representing codewords.
The locations are sorted in the order of bit placement, starting with
the most significant bit of the codeword in the lower-right corner.
Parameters:
qr_version (int): QR code version.
Returns:
Array of shape (num_bits, 2) where each row describes
a module location with the X coordinate in the first column
and the Y coordinate in the second column.
"""
qrsize = 17 + 4 * qr_version
# Build a map that marks modules used in function patterns.
func_mask = np.zeros((qrsize, qrsize), dtype=np.uint8)
func_mask[:9, :9] = 1 # upper-left position detection pattern
func_mask[:9, -8:] = 1 # upper-right position detection pattern
func_mask[-8:, :9] = 1 # lower-left position detection pattern
func_mask[6, :] = 1 # horizontal timing pattern
func_mask[:, 6] = 1 # vertical timing pattern
# Mark version information in the mask.
if qr_version > 6:
func_mask[:6, -11:-8] = 1 # upper-right version information
func_mask[-11:-8, :6] = 1 # lower-left version information
# Mark alignment patterns in the mask.
align_locs = get_alignment_pattern_locations(qr_version)
for (x, y) in align_locs:
func_mask[y-2:y+3, x-2:x+3] = 1
# List the modules in the QR matrix, including special areas and
# function patterns but skipping the vertical timing column.
# List these modules from right to left in strips of two columns wide,
# alternating between upward and downward traversal of the strips.
# Number of two-column strips.
nstrip = (qrsize - 1) // 2
# Prepare X coordinates.
xcoords = np.arange(qrsize - 1, 0, -1) # columns right-to-left
xcoords[-6:] -= 1 # skip vertical timing column
xcoords = xcoords.reshape((nstrip, 2)) # make groups of two columns
xcoords = np.repeat(xcoords, repeats=qrsize, axis=0) # repeat for each row
xcoords = xcoords.flatten() # ungroup
# Prepare Y coordinates
ycoords = np.arange(qrsize) # list rows downward
ycoords = np.repeat(ycoords, repeats=2) # repeat for two columns per strip
ycoords = np.concatenate((ycoords[::-1], ycoords)) # upward + downward
ycoords = np.tile(ycoords, nstrip // 2) # repeat for each pair of strips
# Out of this list of modules, select the modules that are not used
# in function patterns.
(idx,) = np.nonzero(1 - func_mask[ycoords, xcoords])
# Build the return array.
data_locations = np.column_stack((xcoords[idx], ycoords[idx]))
return data_locations
def extract_codewords(matrix, mask_pattern):
"""Extract the sequence of codewords from the QR matrix.
Parameters:
matrix (ndarray): 2D array containing the QR matrix.
mask_pattern (int): Mask pattern reference from format information.
Returns:
Array of codewords in order of placement in the matrix.
"""
qrsize = matrix.shape[0]
qr_version = (qrsize - 17) // 4
# Unmask the QR code.
mask = make_mask_pattern(qrsize, mask_pattern)
unmasked_matrix = matrix ^ mask
# Get the locations of codewords in placement order.
data_locations = get_data_locations(qr_version)
xcoords = data_locations[:, 0]
ycoords = data_locations[:, 1]
# Fetch codeword bits from the matrix.
data_bits = unmasked_matrix[ycoords, xcoords]
# Split bits in groups of 8 bits per codeword.
nwords = len(data_bits) // 8
codeword_bits = data_bits[:8*nwords].reshape((nwords, 8))
# Calculate value of each 8-bit codeword.
bit_values = (1 << np.arange(8))[::-1]
codewords = np.sum(codeword_bits * bit_values, axis=1)
return codewords.astype(np.uint8)
def get_block_structure(qr_version, error_correction_level):
"""Return the data block structure of the specified QR code type.
Parameters:
qr_version (int): QR code version
error_correction_level (str): Error correction level (L, M, Q or H).
Returns:
Tuple (n_codewords, n_check_words, n_blocks, max_errors).
"""
num_codewords_table = {
1: 26, 2: 44, 3: 70, 4: 100,
5: 134, 6: 172, 7: 196, 8: 242,
9: 292, 10: 346, 11: 404, 12: 466,
13: 532, 14: 581, 15: 655, 16: 733,
17: 815, 18: 901, 19: 991, 20: 1085,
21: 1156, 22: 1258, 23: 1364, 24: 1474,
25: 1588, 26: 1706, 27: 1828, 28: 1921,
29: 2051, 30: 2185, 31: 2323, 32: 2465,
33: 2611, 34: 2761, 35: 2876, 36: 3034,
37: 3196, 38: 3362, 39: 3532, 40: 3706
}
block_structure_table = {
1: [( 7, 1), ( 10, 1), ( 13, 1), ( 17, 1)],
2: [( 10, 1), ( 16, 1), ( 22, 1), ( 28, 1)],
3: [( 15, 1), ( 26, 1), ( 36, 2), ( 44, 2)],
4: [( 20, 1), ( 36, 2), ( 52, 2), ( 64, 4)],
5: [( 26, 1), ( 48, 2), ( 72, 4), ( 88, 4)],
6: [( 36, 2), ( 64, 4), ( 96, 4), ( 112, 4)],
7: [( 40, 2), ( 72, 4), ( 108, 6), ( 130, 5)],
8: [( 48, 2), ( 88, 4), ( 132, 6), ( 156, 6)],
9: [( 60, 2), ( 110, 5), ( 160, 8), ( 192, 8)],
10: [( 72, 4), ( 130, 5), ( 192, 8), ( 224, 8)],
11: [( 80, 4), ( 150, 5), ( 224, 8), ( 264, 11)],
12: [( 96, 4), ( 176, 8), ( 260, 10), ( 308, 11)],
13: [( 104, 4), ( 198, 9), ( 288, 12), ( 352, 16)],
14: [( 120, 4), ( 216, 9), ( 320, 16), ( 384, 16)],
15: [( 132, 6), ( 240, 10), ( 360, 12), ( 432, 18)],
16: [( 144, 6), ( 280, 10), ( 408, 17), ( 480, 16)],
17: [( 168, 6), ( 308, 11), ( 448, 16), ( 532, 19)],
18: [( 180, 6), ( 338, 13), ( 504, 18), ( 588, 21)],
19: [( 196, 7), ( 364, 14), ( 546, 21), ( 650, 25)],
20: [( 224, 8), ( 416, 16), ( 600, 20), ( 700, 25)],
21: [( 224, 8), ( 442, 17), ( 644, 23), ( 750, 25)],
22: [( 252, 9), ( 476, 17), ( 690, 23), ( 816, 34)],
23: [( 270, 9), ( 504, 18), ( 750, 25), ( 900, 30)],
24: [( 300, 10), ( 560, 20), ( 810, 27), ( 960, 32)],
25: [( 312, 12), ( 588, 21), ( 870, 29), (1050, 35)],
26: [( 336, 12), ( 644, 23), ( 952, 34), (1110, 37)],
27: [( 360, 12), ( 700, 25), (1020, 34), (1200, 40)],
28: [( 390, 13), ( 728, 26), (1050, 35), (1260, 42)],
29: [( 420, 14), ( 784, 28), (1140, 38), (1350, 45)],
30: [( 450, 15), ( 812, 29), (1200, 40), (1440, 48)],
31: [( 480, 16), ( 868, 31), (1290, 43), (1530, 51)],
32: [( 510, 17), ( 924, 33), (1350, 45), (1620, 54)],
33: [( 540, 18), ( 980, 35), (1440, 48), (1710, 57)],
34: [( 570, 19), (1036, 37), (1530, 51), (1800, 60)],
35: [( 570, 19), (1064, 38), (1590, 53), (1890, 63)],
36: [( 600, 20), (1120, 40), (1680, 56), (1980, 66)],
37: [( 630, 21), (1204, 43), (1770, 59), (2100, 70)],
38: [( 660, 22), (1260, 45), (1860, 62), (2220, 74)],
39: [( 720, 24), (1316, 47), (1950, 65), (2310, 77)],
40: [( 750, 25), (1372, 49), (2040, 68), (2430, 81)]
}
error_correction_table = {"L": 0, "M": 1, "Q": 2, "H": 3}
level_code = error_correction_table[error_correction_level]
n_codewords = num_codewords_table[qr_version]
(n_check_words, n_blocks) = block_structure_table[qr_version][level_code]
assert n_check_words % n_blocks == 0
max_errors = n_check_words // n_blocks // 2
if max_errors < 6:
max_errors -= 1
return (n_codewords, n_check_words, n_blocks, max_errors)
def rs_mul(a, b):
"""Multiply two elements of GF(2**8) as used in the Reed Solomon code.
Parameters:
a (int): Integer in range 0 .. 255.
b (int): Integer in range 0 .. 255.
Returns:
Product in GF(2**8) as an integer in range 0 .. 255.
"""
if a == 0 or b == 0:
return 0
# a * b == exp(log(a) + log(b))
loga = reed_solomon_gf_log[a]
logb = reed_solomon_gf_log[b]
result = reed_solomon_gf_exp[(loga + logb) % 255]
return result
def rs_div(a, b):
"""Divide two elements of GF(2**8) as used in the Reed Solomon code.
Parameters:
a (int): Dividend, range 0 .. 255.
b (int): Divisor, range 1 .. 255.
Returns:
Quatient a / b in GF(2**8) as an integer in range 0 .. 255.
"""
assert b != 0
if a == 0:
return 0
# a / b == exp(log(a) - log(b))
loga = reed_solomon_gf_log[a]
logb = reed_solomon_gf_log[b]
result = reed_solomon_gf_exp[(255 + loga - logb) % 255]
return result
def rs_eval_poly(poly, x):
"""Evaluate a polynomial within GF(2**8) as used in the Reed Solomon code.
Parameters:
poly (ndarray): Array of coefficients of the polynomial,
starting with the zero-order term.
x (int): Element to evaluate.
Returns:
Value of the polynomial at "x" as an integer.
"""
n = len(poly) - 1
ret = poly[n]
for i in range(n):
ret = rs_mul(ret, x) ^ poly[n-1-i]
return ret
def rs_berlekamp_massey(syndrome):
"""Use the Berlekamp-Massey algorithm to calculate
the error locator polynomial for the specified set of syndromes.
The error locator polynomial is a polynomial
C[L] * x**n + C[L-1] * x**(L-1) + ... + C[1] * x + C[0]
with the following properties:
- C[0] = 1;
- the degree "n" is as low as possible;
- the convolution of C(x) with the syndrome polynomial S(x) equals zero.
If we view the syndrome as an array S[0], S[1], ... S[N-1],
the last property of the error locator polynomial can be written
as follows:
C[0] * S[k] + C[1] * S[k-1] + ... + C[L] * S[k-L] = 0
(for all k where L <= k < N).
All calculations are in the GF(2**8) field of the Reed Solomon code.
Parameters:
syndrome (list): List of syndromes.
Returns:
List of coefficients of the error locator polynomial.
"""
# See https://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm
n = len(syndrome)
poly = (n + 1) * [0]
poly[0] = 1
prev_poly = list(poly)
l = 0
prev_l = 0
b = 1
m = 1
for k in range(n):
assert prev_l + m == k + 1 - l
d = syndrome[k]
for i in range(1, l+1):
d ^= rs_mul(syndrome[k-i], poly[i])
if d == 0:
m += 1
else:
ratio = rs_div(d, b)
if 2 * l <= k:
for i in range(prev_l, -1, -1):
prev_poly[i+m] = poly[i+m]
poly[i+m] ^= rs_mul(prev_poly[i], ratio)
prev_poly[:m] = poly[:m]
prev_l = l
l = k + 1 - l
b = d
m = 1
else:
assert prev_l + m <= l
for i in range(prev_l + 1):
poly[i+m] ^= rs_mul(prev_poly[i], ratio)
m += 1
return poly[:l+1]
def rs_forney(syndrome, error_locator, error_locations):
"""Use Forney's algorithm to calculate the error values.
Parameters:
syndrome (list): List of syndromes.
error_locator (list): Coefficients of the error locator polynomial.
error_locations (list): Error locations.
Returns:
List with error value for each listed error location.
"""
# See https://en.wikipedia.org/wiki/Forney_algorithm
n_error = len(error_locations)
assert len(error_locator) == n_error + 1
assert len(syndrome) >= len(error_locator) - 1
# Calculate the coefficients of the error evaluator polynomial.
#
# err_eval(x) = syndrome(x) * error_locator(x) (mod x**n_syndrome)
#
# Note that the definition of error_locator(x) guarantees that
# err_eval(x) will have zero-valued coefficients for all terms
# of degree >= n_error. Thus, the degree of err_eval(x) is at most
# (n_error - 1), and we only need to calculate the first n_error
# coefficients.
#
err_eval = (len(error_locator) - 1) * [0]
for k in range(len(error_locator) - 1):
for i in range(len(error_locator) - k - 1):
err_eval[k + i] ^= rs_mul(syndrome[k], error_locator[i])
# Calculate the coefficients of the formal derivative of
# the error locator polynomial.
errloc_deriv = (len(error_locator) - 1) * [0]
for i in range(1, len(error_locator)):
if i % 2 == 1:
errloc_deriv[i-1] = error_locator[i]
# Calculate the error values:
# e[k] = X[k] * err_eval(1/X[k]) / errloc_deriv(1/X[k])
#
# where X[k] = a**error_locations[k]
#
error_values = n_error * [0]
for k in range(n_error):
x = reed_solomon_gf_exp[error_locations[k]]
xinv = reed_solomon_gf_exp[255-error_locations[k]]
v_err_eval = rs_eval_poly(err_eval, xinv)
v_errloc_deriv = rs_eval_poly(errloc_deriv, xinv)
error_values[k] = rs_div(rs_mul(x, v_err_eval), v_errloc_deriv)
return error_values
def rs_error_correction(data_words, check_words, max_errors, debug_level=0):
"""Perform Reed-Solomon error correction on a message block.
Parameters:
data_words (list): List of received data words.
check_words (list): List of received error correction words.
max_errors (int): Maximum number of errors to correct.
debug_level (int): Optional debug level.
Returns:
List of corrected data words.
Raises:
QRDecodeError: If error correction fails.
"""
n_data_words = len(data_words)
n_check_words = len(check_words)
n_received_words = n_data_words + n_check_words
received_words = data_words + check_words
# Sanity check on the number of correctable errors.
assert 2 * max_errors <= n_check_words
if debug_level >= 2:
debug_msg("REED-SOLOMON: ({}, {}, r={})"
.format(n_received_words, n_data_words, max_errors))
#
# See also https://en.wikipedia.org/wiki/Reed-Solomon_error_correction
#
# The received words (data words followed by error check words)
# form a polynomial over GF(2**8):
# R(x) = r0 + r1 * x + r2 * x**2 + r3 * x**3 + ...
#
# Note that the first received word is the coefficient for the
# highest-powered term of the polynomial (r0 is the last received word).
#
# Calculate the error syndromes for k = 0 .. (n_check_words-1):
# syndrome[k] = R(a**k)
#
# Note that "a" (represented as integer value 2) is a primitive element
# of GF(2**8).
#
received_poly = received_words[::-1]
syndrome = n_check_words * [0]
for k in range(n_check_words):
x = reed_solomon_gf_exp[k]
syndrome[k] = rs_eval_poly(received_poly, x)
# Quick check if all syndromes are zero.
if all([(x == 0) for x in syndrome]):
# No errors, just return the data words.
return data_words
if debug_level >= 3:
debug_msg(" syndrome = " + str(syndrome))
# Determine the error locator polynomial.
error_locator = rs_berlekamp_massey(syndrome)
# Check that the degree of the error locator polynomial does not
# exceed the maximum number of correctable errors.
n_error = len(error_locator) - 1
if n_error > max_errors:
raise QRDecodeError("Uncorrectable errors in Reed-Solomon code")
if debug_level >= 1:
debug_msg("REED-SOLOMON: {} errors".format(n_error))
# Find the roots of the error locator polynomial.
# If all roots are different AND each root equals "a**(-p[i])" where
# "p[i]" is a valid index into the received message, then
# the values "p[i]" represent the error locations.
error_locations = []
for k in range(n_received_words):
x = reed_solomon_gf_exp[255-k]
v = rs_eval_poly(error_locator, x)
if v == 0:
error_locations.append(k)
if debug_level >= 3:
debug_msg(" error_locations = " + str(error_locations))
# Check that all roots of the error locator polynomial are different
# and correspond to a valid position.
if len(error_locations) != n_error:
raise QRDecodeError("Uncorrectable errors in Reed-Solomon code")
# Use Forney's algorithm to find the error values.
error_values = rs_forney(syndrome, error_locator, error_locations)
# Correct errors.
# Note: location 0 is the last received word.
for i in range(n_error):
k = n_received_words - 1 - error_locations[i]
received_words[k] ^= error_values[i]
## Double check that the syndrome is all-zero after error correction.
## This check is not necessary; the corrected syndrome is guaranteed
## to be zero if Reed-Solomon decoding is correctly implemented.
## This is a nice sanity check for debugging.
#received_poly = received_words[::-1]
#syndrome = n_check_words * [0]
#for k in range(n_check_words):
# x = reed_solomon_gf_exp[k]
# syndrome[k] = rs_eval_poly(received_poly, x)
#assert all([(x == 0) for x in syndrome])
# Return the corrected data words.
return received_words[:n_data_words]
def codeword_error_correction(codewords,
qr_version,
error_correction_level,
debug_level=0):
"""Perform error correction and return only the data codewords.
Parameters:
codewords (list): List of codewords in placement order.
qr_version (int): QR code version
error_correction_level (str): Error correction level (L, M, Q or H).
debug_level (int): Optional debug level.
Returns:
List of error-corrected data codewords.
Raises:
QRDecodeError: If error correction fails.
"""
(n_codewords, n_check_words, n_blocks, max_errors
) = get_block_structure(qr_version, error_correction_level)
assert len(codewords) == n_codewords
n_data_words = n_codewords - n_check_words
n_data_words_per_block = n_data_words // n_blocks
n_long_blocks = n_data_words % n_blocks
corrected_data = []
for i in range(n_blocks):
# Collect data words from codeword sequence.
k = i + n_blocks * n_data_words_per_block
data_words = codewords[i:k:n_blocks]
if i >= n_blocks - n_long_blocks:
extra_word = codewords[n_data_words-n_blocks+i]
data_words.append(extra_word)
# Collect error correction words from codeword sequence.
check_words = codewords[n_data_words+i::n_blocks]
# Perform Reed-Solomon error correction.
message = rs_error_correction(data_words,
check_words,
max_errors,
debug_level)
corrected_data += message
return corrected_data
def get_bits_from_stream(bitstream, position, num_bits):
"""Read bits from the bitstream.
Parameters:
bitstream (list): List of 8-bit data codewords.
position (int): Index of first bit to read.
num_bits (int): Number of bits to read.
Returns:
Integer representing the obtained bits (most-significant bit first).
Raises:
QRDecodeError: If the requested range exceeds the bitstream length.
"""
if position + num_bits > 8 * len(bitstream):
raise QRDecodeError("Unexpected end of bitstream")
word_pos = position // 8
bit_pos = position % 8
k = min(num_bits, 8 - bit_pos)
mask = (1 << k) - 1
value = (bitstream[word_pos] >> (8 - bit_pos - k)) & mask
bits_remaining = num_bits - k
while bits_remaining >= 8:
word_pos += 1
word = bitstream[word_pos]
value = (value << 8) | word
bits_remaining -= 8
if bits_remaining > 0:
word_pos += 1
mask = (1 << bits_remaining) - 1
lsb = 8 - bits_remaining
word = (bitstream[word_pos] >> (8 - bits_remaining)) & mask
value = (value << bits_remaining) | word
return value
def decode_numeric_segment(bitstream, position, nchar):
"""Decode a segment in numeric mode.
Parameters:
bitstream (ndarray): Array of 8-bit data codewords.
position (int): Bit position within the bitstream.
nchar (int): Number of characters to decode.
Returns:
Tuple (decoded_data, new_position).
Raises:
QRDecodeError: If decoding fails or end of bitstream is reached.
"""
frag = bytearray(nchar)
ndone = 0
while ndone < nchar:
k = min(nchar - ndone, 3)
nbits = 3 * k + 1
value = get_bits_from_stream(bitstream, position, nbits)
position += nbits
if k > 2:
frag[ndone+2] = 0x30 + value % 10
value = value // 10
if k > 1:
frag[ndone+1] = 0x30 + value % 10
value = value // 10
if value > 9:
raise QRDecodeError("Invalid numeric data")
frag[ndone] = 0x30 + value
ndone += k
return (frag, position)
def decode_alphanumeric_segment(bitstream, position, nchar):
"""Decode a segment in alphanumeric mode.
Parameters:
bitstream (ndarray): Array of 8-bit data codewords.
position (int): Bit position within the bitstream.
nchar (int): Number of characters to decode.
Returns:
Tuple (decoded_data, new_position).
Raises:
QRDecodeError: If decoding fails or end of bitstream is reached.
"""
alphanum_table = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"
assert len(alphanum_table) == 45
frag = bytearray(nchar)
ndone = 0
while ndone < nchar:
k = min(nchar - ndone, 2)
nbits = 5 * k + 1
value = get_bits_from_stream(bitstream, position, nbits)
position += nbits
if k > 1:
frag[ndone+1] = alphanum_table[value % 45]
value = value // 45
if value > 44:
raise QRDecodeError("Invalid alphanumeric data")
frag[ndone] = alphanum_table[value]
ndone += k
return (frag, position)
def decode_8bit_segment(bitstream, position, nchar):
"""Decode a segment in 8-bit mode.
Parameters:
bitstream (ndarray): Array of 8-bit data codewords.
position (int): Bit position within the bitstream.
nchar (int): Number of characters to decode.
Returns:
Tuple (decoded_data, new_position).
Raises:
QRDecodeError: If decoding fails or end of bitstream is reached.
"""
frag = bytearray(nchar)
for i in range(nchar):
frag[i] = get_bits_from_stream(bitstream, position, 8)
position += 8
return (frag, position)
def decode_bitstream(bitstream, qr_version):
"""Decode the specified QR bitstream.
Parameters:
bitstream (list): Array of 8-bit data codewords.
qr_version (int): QR code version.
Returns:
Decoded data as a bytestring.
Raises:
QRDecodeError: If decoding fails.
"""
# Determine number of bits in character count field.
if qr_version <= 9:
character_count_bits = [0, 10, 9, 0, 8]
elif qr_version <= 26:
character_count_bits = [0, 12, 11, 0, 16]
else:
character_count_bits = [0, 14, 13, 0, 16]
decoded_data = bytearray()
position = 0
# Decode segments until end of bitstream (or terminator).
while position + 4 <= 8 * len(bitstream):
# Read mode indicator.
mode = get_bits_from_stream(bitstream, position, 4)
position += 4
# Stop at terminator marker.
if mode == 0:
break
# Reject unsupported modes.
if mode not in (1, 2, 4):
if mode == 7:
raise QRDecodeError("ECI mode not supported")
if mode == 3:
raise QRDecodeError("Structured Append mode not supported")
if mode in (5, 9):
raise QRDecodeError("FNC1 mode not supported")
if mode == 8:
raise QRDecodeError("Kanji mode not supported")
raise QRDecodeError("Unsupported mode indicator 0x{:x}"
.format(mode))
# Read character count.
nbits = character_count_bits[mode]
nchar = get_bits_from_stream(bitstream, position, nbits)
if nchar < 0:
raise QRDecodeError("Unexpected end of bitstream")
position += nbits
# Decode characters.
if mode == 1:
(frag, position
) = decode_numeric_segment(bitstream, position, nchar)
elif mode == 2:
(frag, position
) = decode_alphanumeric_segment(bitstream, position, nchar)
elif mode == 4:
(frag, position
) = decode_8bit_segment(bitstream, position, nchar)
decoded_data += frag
return bytes(decoded_data)
def matrix_to_string(matrix):
"""Format the QR matrix as a string."""
lines = []
qrsize = matrix.shape[0]
for y in range(qrsize):
s = []
for x in range(qrsize):
if matrix[y, x] == 0:
s.append(".")
elif matrix[y, x] == 1:
s.append("X")
else:
s.append("?")
lines.append(" " + " ".join(s))
return "\n".join(lines)
def bitstream_to_string(bitstream):
"""Format the bitstream as a string."""
bits = []
for word in bitstream:
for k in range(8):
bits.append((word >> (7 - k)) & 1)
return "".join(map(str, bits))
def decode_qrcode(image, debug_level=0):
"""Decode the QR code in the specified image.
Parameters:
image (PIL.Image): Input image.
debug_level (int): Optional debug level (0..3).
Returns:
Decoded data as a byte string.
Raises:
QRDecodeError: If decoding fails.
"""
# Convert to black-and-white.
img_data = quantize_image(image)
# Locate position detection patterns.
patterns = find_position_detection_patterns(img_data)
if debug_level >= 2:
debug_msg("POSITION DETECTION PATTERNS:")
for pattern in patterns:
debug_msg(" " + str(pattern))
if len(patterns) < 3:
npattern = len(patterns)
if npattern == 0:
raise QRDecodeError("No position detection patterns found")
raise QRDecodeError("Only {} position detection patterns found"
.format(npattern))
# Make groups of three compatible finders.
finder_triplets = make_finder_triplets(patterns)
if len(finder_triplets) == 0:
raise QRDecodeError("No valid finder pattern found")
# Try to decode according to each triplet.
first_exception = None
for triplet in finder_triplets:
if debug_level >= 1:
debug_msg("FINDER TRIPLET:")
for fnd in triplet:
debug_msg(" " + str(fnd))
try:
# Extract QR code location, orientation and version.
transform, qr_version = locate_qr_code(img_data, triplet)
if debug_level >= 2:
debug_msg("AFFINE TRANSFORM:")
debug_msg(str(transform))
# Sample the QR matrix.
matrix = sample_qr_matrix(img_data, transform, qr_version)
if debug_level >= 3:
debug_msg(matrix_to_string(matrix))
# Extract format information.
(error_correction_level, mask_pattern
) = extract_format_data(matrix)
if debug_level >= 1:
debug_msg("QR VERSION: {} {} mask={}"
.format(qr_version,
error_correction_level,
mask_pattern))
# Extract codewords from the QR matrix.
codewords = extract_codewords(matrix, mask_pattern)
# Unpack codeword sequence and perform error correction.
bitstream = codeword_error_correction(list(codewords),
qr_version,
error_correction_level,
debug_level)
if debug_level >= 3:
debug_msg("BITSTREAM: " + bitstream_to_string(bitstream))
except QRDecodeError as exc:
# If decoding fails on the first finder triplet,
# save the exception and try decoding the remaining triplets.
# If all triplets fail, report the error from the first triplet.
if first_exception is None:
first_exception = exc
if debug_level >= 1:
debug_msg("FAILED: " + str(exc))
continue
# Successfully extracted a bitstream from the QR code.
# This implies we correctly located the QR code in the image,
# so from this point on it does not make sense to retry with
# different finder triplets if an error occurs.
# Decode the bitstream.
return decode_bitstream(bitstream, qr_version)
raise first_exception