A. Programming Concepts and Skills · Algorithm Design and Analysis

2-D Array Algorithms: Matrix Multiplication and Image Pixels

A3.5 C2.1 C2.2About 75 minutes

Learning goals

I can multiply two matrices with a triple loop, and state the precondition on their sizes.
I can explain why matrix multiplication of two n × n matrices is O(n³).
I can process a greyscale image stored as a 2-D array: invert, brighten (with clamping), flip and blur it.
I can explain why some image algorithms must write into a new array instead of changing the image in place.

Words to know

matrix
A rectangular 2-D array of numbers, with a size written rows × columns (e.g. 2 × 3).

matrix product
For A (n × m) and B (m × p), the n × p matrix C where C[i][j] is the sum of A[i][k] × B[k][j] over k.

pixel
One dot of a digital image; in a greyscale image, a number for its brightness.

greyscale
An image where each pixel is a single brightness value, commonly 0 (black) to 255 (white).

clamping
Forcing a value back into an allowed range, e.g. min(255, v + 50) so brightness never goes above 255.

neighbourhood
The pixels around a given pixel, such as the 3 × 3 block centred on it.

Every photo is a 2-D array

When you crop, brighten or blur a photo on your phone, the app runs 2-D array algorithms. A greyscale photo is a grid of brightness numbers; a colour photo stores three numbers (red, green, blue) per pixel. Matrices, the other big 2-D topic in A3.5, power computer graphics, game physics, machine learning and the page-ranking ideas behind web search.

In this lesson you will write the two algorithms the curriculum names: multiplying matrices and processing pixels in an image.

Matrix multiplication

Two families order groceries. Family 0 wants 4 L of milk, 2 loaves of bread and 1 bottle of maple syrup; family 1 wants 6, 3 and 2. Two stores have different prices. What does each family pay at each store?

Put the orders in a matrix A (one row per family, one column per item) and the prices in B (one row per item, one column per store). The answer is the matrix product C = A × B: each entry is a row of A "dotted" with a column of B:

C[i][j] = A[i][0] × B[0][j] + A[i][1] × B[1][j] + … + A[i][m − 1] × B[m − 1][j]

Precondition: the number of columns of A must equal the number of rows of B (here 3 items). The result has the rows of A and the columns of B: 2 families × 2 stores.

One entry of the product. The highlighted row of A (family 0's order) meets the highlighted column of B (store Y's prices) and gives the highlighted entry of C.

def mat_mult(A, B):

"""Return the matrix product A x B.

Precondition: A is n x m, B is m x p (columns of A == rows of B).

Postcondition: returns a new n x p matrix C with

C[i][j] = A[i][0]*B[0][j] + ... + A[i][m-1]*B[m-1][j].

"""

n, m, p = len(A), len(A[0]), len(B[0])

assert len(B) == m, "columns of A must equal rows of B"

C = [[0] * p for i in range(n)]

for i in range(n): # each row of A

for j in range(p): # each column of B

total = 0

for k in range(m): # walk along the row and down the column

total += A[i][k] * B[k][j]

C[i][j] = total

return C

# rows: two families; columns: litres of milk, loaves of bread, bottles of maple syrup

orders = [[4, 2, 1],

[6, 3, 2]]

# rows: milk, bread, syrup; columns: price at store X, price at store Y (dollars)

prices = [[2.50, 2.25],

[3.00, 3.50],

[9.00, 8.00]]

print(mat_mult(orders, prices))

Output: [[25.0, 24.0], [42.0, 40.0]]. Family 0 pays $25 at store X or $24 at store Y; family 1 pays $42 or $40. The assert checks the size precondition.

Cost of matrix multiplication

For A (n × m) and B (m × p), there are n × p entries, and each needs m multiplications: n × m × p multiplications in total. For two n × n matrices that is n³: O(n³). Doubling the size of the matrices multiplies the work by 8.

Three things to notice:

Order matters: A × B is usually not equal to B × A, and B × A may not even be defined (here B is 3 × 2 and A is 2 × 3, so B × A is 3 × 3, a completely different matrix).
Graphics cards (GPUs) are built to do enormous numbers of these multiplications at once, which is why they are used for 3-D games and for machine learning.
Cleverer algorithms exist (Strassen's algorithm is about O(n^2.81)), a topic for university algorithms courses.

Images as 2-D arrays

A greyscale image is a 2-D array img[r][c] with values from 0 (black) to 255 (white). Row 0 is the top of the image and column 0 is the left edge. Pixel algorithms come in two kinds:

Point operations change each pixel using only its own value: invert (255 - v), brighten (v + 50), threshold (255 if v > 128 else 0). Each is one pass: O(rows × cols).
Neighbourhood operations use the pixels around each pixel: blur, sharpen, edge detection. These must read from the original image and write into a new one.

A 6 × 9 greyscale image of a tree (6 rows, 9 columns), drawn in its real pixel colours, and the result of inverting it.

tree = [

[255, 255, 255, 255, 0, 255, 255, 255, 255],

[255, 255, 255, 0, 0, 0, 255, 255, 255],

[255, 255, 0, 0, 0, 0, 0, 255, 255],

[255, 255, 255, 0, 0, 0, 255, 255, 255],

[255, 0, 0, 0, 0, 0, 0, 0, 255],

[255, 255, 255, 255, 120, 255, 255, 255, 255],

]

SHADES = "@%#*+=-:. " # darkest (0) ... lightest (255)

def show(img):

for row in img:

line = ""

for v in row:

line += SHADES[v * (len(SHADES) - 1) // 255]

print(line)

def inverted(img):

return [[255 - v for v in row] for row in img]

def brightened(img, amount):

return [[min(255, v + amount) for v in row] for row in img]

show(tree)

print("---------")

show(inverted(tree))

print("---------")

show(brightened(tree, 100))

Its checked output is shown in the next box. The show function prints a character for each pixel, from @ (darkest) to a space (lightest), so you can "see" an image without any graphics library. brightened clamps with min(255, ...): without it, white pixels would become 355, which is not a valid brightness.

@@@

@@@@@

@@@

@@@@@@@

---------

@@@@ @@@@

@@@ @@@

@@ @@

@@@ @@@

@ @

@@@@+@@@@

---------

***

*****

***

*******

Output of the program above (checked by running it).

Flipping and mirroring

Flipping an image left to right is the mirror algorithm from Two-Dimensional Arrays: Rows, Columns and Traversals: reverse every row. Flipping it upside down reverses the order of the rows: swap row r with row rows − 1 − r for the top half, which only swaps references, so it is O(rows). Rotating 90° is a transpose followed by a mirror.

Worked example

A 3 × 3 box blur

Blurring replaces each pixel with the average of the 3 × 3 block centred on it. At the edges, only the neighbours that are inside the image count. Blur this 4 × 4 image (a bright square on a black background), rounding down with //:

[[0, 0, 0, 0], [0, 90, 90, 0], [0, 90, 90, 0], [0, 0, 0, 0]]

Corner (0, 0): its block inside the image is rows 0 to 1, columns 0 to 1: 0, 0, 0, 90. Sum 90, count 4: 90 // 4 = 22.
Edge (0, 1): rows 0 to 1, columns 0 to 2: 0, 0, 0, 0, 90, 90. Sum 180, count 6: 30.
Inside (1, 1): the full 3 × 3 block: 0, 0, 0, 0, 90, 90, 0, 90, 90. Sum 360, count 9: 40.
By symmetry the whole result is [[22, 30, 30, 22], [30, 40, 40, 30], [30, 40, 40, 30], [22, 30, 30, 22]]: the sharp edge of the square has been smoothed out.
Why a new array? If you wrote 40 into (1, 1) in place, the next pixel (1, 2) would average the new 40 instead of the original 90, and the result would depend on the order of the loops. Reading from the original and writing to a copy keeps every pixel's calculation based on the original image.

[[22, 30, 30, 22], [30, 40, 40, 30], [30, 40, 40, 30], [22, 30, 30, 22]]. Each pixel reads up to 9 neighbours, so the blur is O(9 × rows × cols) = O(rows × cols).

def blurred(img):

"""Return a new image where each pixel is the average (rounded down)

of itself and its neighbours that lie inside the image."""

rows, cols = len(img), len(img[0])

out = [[0] * cols for r in range(rows)]

for r in range(rows):

for c in range(cols):

total = count = 0

for dr in (-1, 0, 1):

for dc in (-1, 0, 1):

rr, cc = r + dr, c + dc

if 0 <= rr < rows and 0 <= cc < cols:

total += img[rr][cc]

count += 1

out[r][c] = total // count

return out

img = [[0, 0, 0, 0],

[0, 90, 90, 0],

[0, 0, 0, 0]]

for row in blurred(img):

print(row)

Output, one line each: [22, 30, 30, 22], [30, 40, 40, 30], [30, 40, 40, 30], [22, 30, 30, 22]. Four nested loops, but the inner two always run 3 × 3 = 9 times, a constant. The if keeps the neighbour inside the image (the precondition for indexing).

Colour images

In a colour image each pixel is usually three numbers: (red, green, blue), each 0 to 255. Store it as a 2-D array of tuples, img[r][c] = (r_val, g_val, b_val). A simple greyscale conversion averages them, (r_val + g_val + b_val) // 3; photo editors often weight green more heavily because human eyes are most sensitive to it (a common formula is 0.299 R + 0.587 G + 0.114 B). Real programs read and write image files with a library such as Pillow, but the algorithms are exactly the loops in this lesson.

Just for fun

A pixel walks into a photo editor and asks to be brightened by 200.

The editor says, "Sorry, I have to clamp you at 255." The pixel says, "Fine, but I'm still the brightest one in the room." (So is every other pixel that asked.)

Hands-on activity

Pixel art and the grocery matrix

You need: graph paper (or a grid drawn on paper), a pencil, and a computer with Python.

On graph paper, draw a simple 10 × 10 picture (a maple leaf, a snowflake, a canoe, your initials) by shading squares. Use three shades: black (0), grey (128) and white (255).
Type it into Python as a 2-D array and display it with show from the lesson.
Write and test: inverted, flipped_upside_down, mirrored (a new array, not in place), and thresholded(img, t) (pixels above t become 255, others 0). Show each result.
Apply blurred to your picture twice. What happens to the edges?
Matrix part: make a 3 × 4 "orders" matrix for three people in your home (how many of 4 snack items each wants) and a 4 × 2 matrix of prices at two stores (from a flyer or website, or made up). Use mat_mult to find each person's cost at each store. Check one entry by hand.

What to look for: every function returns an image of the same size; blurring twice smooths more; the hand-checked matrix entry matches the program's.

Your turn

A is 3 × 4 and B is 4 × 2. Is A × B defined? What size is it? Is B × A defined?

Compute mat_mult([[1, 2], [3, 4]], [[5, 6], [7, 8]]) by hand.

How many multiplications does multiplying two 100 × 100 matrices take with the triple loop? Two 200 × 200?

Write a list comprehension that thresholds img: pixels above 128 become 255, others 0.

Why does brightened use min(255, v + amount)?

Why must a blur write into a new array?

More practice: warm-up

In a greyscale image, what do 0 and 255 mean?

What does inverting do to a pixel of value 200?

What is the Big-O of inverting an r × c image?

What size is the product of a 2 × 5 and a 5 × 3 matrix?

Which pixel is img[0][0]?

More practice: on your own

Predict the output:

img = [[10, 200], [250, 40]]

out = [[min(255, v + 60) for v in row] for row in img]

print(out)

Write flipped_upside_down(img) that returns a new image with the rows in reverse order.

Blur pixel (1, 1) of [[9, 9, 9], [9, 0, 9], [9, 9, 9]] with a 3 × 3 box blur (rounding down).

Compute the matrix product [[2, 0, 1]] × [[3], [4], [5]] and say its size.

Write to_grey(img) that converts a 2-D array of (r, g, b) tuples to greyscale by averaging.

Challenge

The identity matrix I has 1s on the diagonal and 0s elsewhere. Show that A × I = A for a 2 × 2 matrix A = [[a, b], [c, d]], and write identity(n).

Edge detection: a simple horizontal edge detector computes, for each pixel not in the last column, abs(img[r][c] - img[r][c + 1]). What does a large value mean? Apply it to row [0, 0, 200, 200, 200].

A 4K image is 3840 × 2160 pixels. A 3 × 3 blur does about 9 additions per pixel. About how many additions is that, and how many for a 9 × 9 blur? What Big-O describes the cost for a k × k blur?

Check your understanding

Quiz

A is 4 × 3 and B is 3 × 5. What size is A × B?

What is the first row of [[1, 2], [0, 1]] × [[3, 1], [2, 4]]?

What is the Big-O of multiplying two n × n matrices with the triple loop?

Brightening a pixel of 230 by 50 with clamping gives:

Why does a box blur need a separate output image?

Which operation on an image is O(rows) rather than O(rows × cols) when done in place on a list of lists?

For parents and teachers

Big idea: This lesson completes A3.5 with the two remaining named examples: multiplying matrices and processing the pixels of an image. The size precondition for matrix multiplication and the "write to a new array" rule for blurs practise C2.1, and O(n³) versus O(rows × cols) continues C2.2.

How to help: The graph-paper pixel art is a great shared activity. Ask your teen to predict what each function will do to the picture before running it. For matrices, check one entry of the grocery matrix together with a calculator.

Common difficulties:

Mixing up the order of the loops or indexes in matrix multiplication (A[i][k] * B[k][j] is the pattern: k runs along A's row and down B's column).
Forgetting the size precondition, or assuming A × B = B × A.
Not clamping, which gives brightness values above 255 or below 0.
Blurring in place.
Edge pixels: forgetting to check that a neighbour's indexes are inside the image (negative indexes in Python silently wrap to the other side!).