CSE 4227 · Chapter 11 · Deck 10

Chain code, first difference and shape number

How to write a chain code, why it changes with start point and rotation, and the CC → CFD → NCFD fix. Every past question is solved in answer-script form, with a step-by-step simulator next to each one.

★ Must study on this page

Chain code: what it is and how to write one: write the chain code: in 5 finals and the Fall 25 quiz
The fix: CC → CFD → NCFD (shape number): CC → CFD → NCFD: the part that carries the marks
Past questions solved like the answer script: the exact past questions, solved

Start here: representation and description

slides 3–9Know in 2 lines

In plain wordsAfter segmentation you have a blob of pixels: "this is the object". To compare it with other objects (is it a 0 or a 6? a bone or a crack?) you need a short, fixed way to write the shape down (representation) and a few numbers that describe it (description). A chain code writes the outline as a list of arrow directions.

Slide 3. Where it fits: segmentation → raw data (pixels) → representation → computation of descriptors. A representation uses either external characteristics (the boundary: shape) or internal characteristics (the pixels inside: regional properties such as colour and texture).

Slide 4. Image representation = how an image is stored and modelled for analysis. Image description = how we characterise and communicate its content.

representation (slides 5–7)	what it is	example
1. pixel-based	ordered arrays of pixel values (grayscale or RGB); each pixel = intensity/colour at a spatial location	convolution, filtering (low-level operations)
2. region-based	after segmentation the image is a set of regions, described by their boundary (external) or the pixels inside (internal)	a tumour described by its boundary curve or its inside pixels
3. feature-based	extracted features (edges, corners, textures, shapes) instead of raw pixels; compact and robust for recognition	SIFT, HOG, deep-learning embeddings

descriptor (slide 8)	what it holds
boundary descriptors	chain codes: the boundary as a sequence of line segments with direction and length; useful for shape analysis
region descriptors	statistics: mean intensity, variance, texture; colour histograms of a region
structural descriptors	graph-based models: parts as nodes and their relationships as edges
semantic description	high-level meaning ("a cat sitting on a chair"), done by deep-learning models that map features to language

Chain code: what it is and how to write one

Must studyslides 10–13Came in past papers

In plain wordsStand on one pixel of the outline. Look at where the next outline pixel is: right, up-right, up… Write that direction as a number. Step there and repeat until you are back where you started. The list of numbers is the chain code. You no longer need the picture: start pixel + numbers redraw the whole outline.

Slide 10. A chain code is a boundary representation technique used to describe the shape of an object. Instead of storing all pixels of a boundary, it encodes the contour as a sequence of directional steps.

Slide 11. How it works: (1) boundary extraction: find the contour of the object; (2) starting point selection: pick one boundary pixel; (3) directional encoding: trace the boundary pixel by pixel and write each step as a direction number.

8-directional chain code (8-connectivity): 0 right, 1 up-right, 2 up, 3 up-left, 4 left, 5 down-left, 6 down, 7 down-right

4-directional code (slide 11 calls it crack code): 0 right, 1 up, 2 left, 3 down

TrapDirection numbers go round counterclockwise starting from 0 = right, like angles in maths: code k means angle k × 45° (8-dir) or k × 90° (4-dir). Up is 2 in 8-dir but 1 in 4-dir. Draw the compass in every answer.

Slide 10 example. A square boundary traced counterclockwise from the bottom-left pixel: two steps right, two up, two left, two down.

slide 10 square: CC = 00224466

Slide 12. Chain code example (the digit "0"): start at the blue pixel at the top and walk clockwise. Code: 0, 0, 7, 7, 5, 6, 5, 5, 4, 3, 2, 2, 2, 1, 2. This is also the SP24 final figure (solved below).

slide 12: CC = 007756554322212 (15 moves)

Try it, step by step: slide 12, the digit 0. Watch each move get its number, then the first difference and the normalisation.

Slide 12. Advantages: compact representation of boundaries; easy to store and manipulate; useful for shape analysis and recognition.

Slide 13. Simulation on a region of dots: start at the red dot (bottom-left of the bottom row) and walk counterclockwise. Chain code 001232446567.

slide 13: CC = 001232446567

Try it, step by step: slide 13 simulation, counterclockwise from the red dot.

Slide 13. Is the chain code translation invariant? YES. Moving the whole shape somewhere else in the image does not change any step, because the code stores only relative moves, never absolute positions.

Why the plain chain code is not enough

slides 14–19Came in past papers

In plain wordsThe same shape can give many different chain codes: start at another pixel and the list is shifted; turn the shape and every digit changes; make it bigger and the list gets longer. For recognition we want one code per shape. That is what the next section fixes.

Slide 14. Is invariance needed? The letter F appears moved, scaled and rotated: we want translation, scale and rotation invariance so all of them are recognised as F.

Slide 15. Is it invariant to rotation, scaling or reflection? An L-shaped boundary with the 4-direction code:

case (slide 15)	chain code
original	03032211
start point changed	03221103
reflected	01033221
rotated	10033212

Every case gives a different code even though it is the same L. Slide 16. Why invariance matters: shape recognition, classification and matching need a representation that stays the same despite rotation, scaling or reflection.

Slide 17. Problems in chain code representation (learn this list, it is a 3-mark theory question):

Starting point sensitivity: different starting points → different codes.
Rotation dependence: rotating the shape changes the sequence.
Scaling issues: enlarging/reducing alters the code length.
Noise sensitivity: small irregularities in the boundary cause large changes.
Ambiguity: different traversal paths or connectivity choices (4 vs 8) yield different codes.

Slide 18. Starting point solution using shape number (same direction). A square traced clockwise from three different corners:

start	chain code
top-left	000666444222
top-right	666444222000
bottom-left	222000666444

The shape number is the smallest sequence among all circular shifts of the CC, here 000666444222. It is starting-point invariant.

Try it, step by step: slide 18 square. Change the start point, then normalise the CC: the smallest shift is the same every time.

Slide 19. Rotation and scaling comparison: rotating the square by 45° turns every 0/2/4/6 into 1/3/5/7 (different code); scaling it up makes the code longer. The shape number alone does not fix either.

TrapSlides 18, 19, 21 and 24 have AI-made pictures ("Made with AI") and a few printed digits are sloppy (e.g. slide 24 shows an 11-digit CFD for a 12-move square). Trust the method, not those digits. For the 12-move square 000222444666 the CFD is 002002002002.

The fix: CC → CFD → NCFD (shape number)

Must studyslides 20–24Came in past papers

In plain wordsRotation changes every direction by the same amount. So instead of storing the directions, store the turns: how much you turn at each corner. A turn does not care which way the shape faces. That is the first difference. Then, to forget the start point, read the ring of turns from the place that gives the smallest number.

Slide 20. Chain code changes with: (1) changing the start point, (2) reflection, (3) rotation. Solution is normalisation, in 3 steps:

1. Chain code (CC) → 2. Circular First Difference (CFD) → 3. Normalised CFD (NCFD, aka shape number)

Step 2: circular first difference

CFD_i = (c_i+1 − c_i) mod n for i = 1 … N, with c_N+1 = c₁ (wrap round)

n = 8 for an 8-direction code, 4 for a 4-direction code. "Circular" means the last digit compares the last code with the first one, because the boundary is a closed loop. So the CFD has exactly as many digits as the CC.

Why it works: rotating the shape by 90° adds 2 (8-dir) to every code digit. In (c_i+1 + 2) − (c_i + 2) the 2 cancels. So the CFD is rotation invariant (for multiples of 45° in 8-dir, 90° in 4-dir).

Meaning of a CFD digit (8-dir): 0 = straight on, 1 = 45° left turn, 2 = 90° left, 4 = U-turn, 6 = 90° right, 7 = 45° right.

Step 3: normalise (minimum magnitude)

Write the CFD from every start (all circular shifts) and pick the smallest number. This is the NCFD, also called the shape number: invariant to start point and rotation.

Slide 21 example (4-direction, slide 15 L shapes): all four codes end at the same NCFD:

case	CC	CFD (next − this) mod 4	NCFD
original	03032211	31330303	03033133
start point changed	03221103	33030331	03033133
reflected	01033221	13303033	03033133
rotated	10033212	30303313	03033133

NCFD known as SHAPE NUMBER, an invariant code: 03033133 (slide 22).

Try it, step by step: slide 21–22 L shape, 4-direction code 03032211. Use the compass with 4 arrows.

Slide 22 · worked in full (4-direction)worked

CC = 0 3 0 3 2 2 1 1 (start at the circled corner).

i	1	2	3	4	5	6	7	8
this c_i	0	3	0	3	2	2	1	1
next c_i+1	3	0	3	2	2	1	1	0
next − this	3	-3	3	-1	0	-1	0	-1
mod 4 = CFD	3	1	3	3	0	3	0	3

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 31330303. Circular shifts: 31330303, 13303033, 33030331, 30303313, 03033133, 30331330, 03313303, 33133030. Smallest = 03033133.

Slide 23: Gonzalez's version (different subtraction!)

Three shapes (the third is rotated 90°) with chain codes 444201066, 066444201, 067644222. "Curvature = differences in chain code values", then "normalise curvature = mod 8", then "code is the cyclic permutation which produces the smallest number": 002271202 for all three.

chain code	this − next (slide 23)	mod 8	smallest shift
444201066	0 0 2 2 -1 1 -6 0 2	002271202	002271202
066444201	-6 0 2 0 0 2 2 -1 1	202002271	002271202
067644222	-6 -1 1 2 0 2 0 0 2	271202002	002271202

TrapSlide 23 subtracts this − next; slide 22 subtracts next − this. Each digit of one is 8 minus the other (mod 8), so the final numbers differ (slide-22 rule on these shapes gives 006617606). Both are invariant. In the exam use slide 22's rule (next − this, the textbook rule), write the formula, and the marker can follow you.

Try it, step by step: slide 23 shape 1 (444201066). The difference rule is set to slide 23's this − next; switch it to see the slide-22 answer.

Slide 24. Comparison table:

representation	start-point invariant	rotation invariant	notes
chain code (CC)	✗	✗	basic, sensitive to start and rotation
shape number (smallest circular shift of CC)	✓	✗	fixes start-point ambiguity only
CFD (differential chain code)	✗	✓	encodes direction changes
NCFD (normalised CFD)	✓	✓	fixes both start point and rotation

Trap"Shape number" means two things in this deck: slide 18/24 use it for the smallest shift of the CC; slides 21–22 use it for the NCFD. In an answer, write both lines with their names ("start-point invariant CC = …", "NCFD = …") and you cannot lose the mark.

Long codes, noise and resampling; applications; class work

slides 25–29On study list

Slides 25–26. Problems with a raw pixel boundary: (1) long chains of codes; (2) no invariance to rotation and scale; (3) sensitive to noise: easily disturbed by small bumps; plus the start point problem.

Solution: re-sample the boundary to a lower resolution (a coarser grid) before calculating the code. Each boundary point is moved to the nearest node of the coarse grid; the code is then written between those nodes.

Slide 27. Examples: object boundary → resampled boundary vertices → 4-directional or 8-directional chain code. Before resampling the code is long (000000766…1111); after resampling it is short (076666…12). Fewer digits, and tiny bumps disappear.

In plain wordsResampling is like tracing the outline with a thick marker on graph paper: you only keep the big turns, not every wiggle of the pen.

Slide 28. Applications:

field	use case	how chain codes help
object detection	find shapes (circles, squares, L-shapes) in documents or industrial parts	trace the boundary; shape numbers match templates regardless of orientation
character recognition (OCR)	handwritten or printed characters	each character's contour is a chain code; shape numbers recognise it even if rotated or slightly distorted
medical imaging	tumours, organs, bones in scans	the code describes the boundary; shape numbers compare across patients or time
remote sensing	lakes, buildings in satellite images	contours as codes; shape numbers classify despite rotation or scale

Slide 29 · Class workworked

An image is given (dots on a grid). Write down the 8-chain code and find the shape number of it. Starting point: the top dot marked by the arrow.

Step 1 · chain code. Start at the top dot (0,3), the arrow and walk clockwise round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start

8-direction code: 0 = right, counting counterclockwise, 45° apart

move	from → to	direction	code
1	(0,3) → (0,4)	right →	0
2	(0,4) → (1,5)	down-right ↘	7
3	(1,5) → (2,5)	down ↓	6
4	(2,5) → (3,5)	down ↓	6
5	(3,5) → (4,5)	down ↓	6
6	(4,5) → (5,5)	down ↓	6
7	(5,5) → (6,4)	down-left ↙	5
8	(6,4) → (7,3)	down-left ↙	5
9	(7,3) → (6,2)	up-left ↖	3
10	(6,2) → (5,1)	up-left ↖	3
11	(5,1) → (4,1)	up ↑	2
12	(4,1) → (3,2)	up-right ↗	1
13	(3,2) → (2,2)	up ↑	2
14	(2,2) → (1,3)	up-right ↗	1
15	(1,3) → (0,3)	up ↑	2

CC = 076666553321212 (15 moves)

Step 2 · start-point invariance (shape number of slide 18). The boundary is a loop, so any digit can be the first. Write the code from every start (circular shifts) and pick the one that reads as the smallest number.

from 1	0	7	6	6	6	6	5	5	3	3	2	1	2	1	2
from 2	7	6	6	6	6	5	5	3	3	2	1	2	1	2	0
from 3	6	6	6	6	5	5	3	3	2	1	2	1	2	0	7
from 4	6	6	6	5	5	3	3	2	1	2	1	2	0	7	6
from 5	6	6	5	5	3	3	2	1	2	1	2	0	7	6	6
from 6	6	5	5	3	3	2	1	2	1	2	0	7	6	6	6
from 7	5	5	3	3	2	1	2	1	2	0	7	6	6	6	6
from 8	5	3	3	2	1	2	1	2	0	7	6	6	6	6	5
from 9	3	3	2	1	2	1	2	0	7	6	6	6	6	5	5
from 10	3	2	1	2	1	2	0	7	6	6	6	6	5	5	3
from 11	2	1	2	1	2	0	7	6	6	6	6	5	5	3	3
from 12	1	2	1	2	0	7	6	6	6	6	5	5	3	3	2
from 13	2	1	2	0	7	6	6	6	6	5	5	3	3	2	1
from 14	1	2	0	7	6	6	6	6	5	5	3	3	2	1	2
from 15	2	0	7	6	6	6	6	5	5	3	3	2	1	2	1

all circular shifts of the CC · highlighted = smallest

AnswerStart-point invariant chain code = 076666553321212 (smallest shift, starting at digit 1).

Step 3 · circular first difference (CFD). Slide 22 rule: CFD_i = (c_i+1 − c_i) mod 8; the last digit wraps round to the first. This removes rotation.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
this c_i	0	7	6	6	6	6	5	5	3	3	2	1	2	1	2
next c_i+1	7	6	6	6	6	5	5	3	3	2	1	2	1	2	0
next − this	7	-1	0	0	0	-1	0	-2	0	-1	-1	1	-1	1	-2
mod 8 = CFD	7	7	0	0	0	7	0	6	0	7	7	1	7	1	6

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 770007060771716

Step 4 · normalise (NCFD). Smallest circular shift of the CFD. This removes the start point too.

from 1	7	7	0	0	0	7	0	6	0	7	7	1	7	1	6
from 2	7	0	0	0	7	0	6	0	7	7	1	7	1	6	7
from 3	0	0	0	7	0	6	0	7	7	1	7	1	6	7	7
from 4	0	0	7	0	6	0	7	7	1	7	1	6	7	7	0
from 5	0	7	0	6	0	7	7	1	7	1	6	7	7	0	0
from 6	7	0	6	0	7	7	1	7	1	6	7	7	0	0	0
from 7	0	6	0	7	7	1	7	1	6	7	7	0	0	0	7
from 8	6	0	7	7	1	7	1	6	7	7	0	0	0	7	0
from 9	0	7	7	1	7	1	6	7	7	0	0	0	7	0	6
from 10	7	7	1	7	1	6	7	7	0	0	0	7	0	6	0
from 11	7	1	7	1	6	7	7	0	0	0	7	0	6	0	7
from 12	1	7	1	6	7	7	0	0	0	7	0	6	0	7	7
from 13	7	1	6	7	7	0	0	0	7	0	6	0	7	7	1
from 14	1	6	7	7	0	0	0	7	0	6	0	7	7	1	7
from 15	6	7	7	0	0	0	7	0	6	0	7	7	1	7	1

all circular shifts of the CFD · highlighted = smallest

AnswerChain code invariant to start point and rotation (NCFD, shape number of slides 21–22) = 000706077171677.

Try it, step by step: slide 29 class work, from the arrowed top dot.

Past questions solved like the answer script

Must studyslides allCame in past papers

Every chain-code question so far is the same recipe: (1) write the CC with a labelled figure and compass, (2) smallest shift of the CC if they ask "invariant to starting point", (3) CFD, (4) smallest shift of the CFD if they ask "starting point and rotation". The figures below are redrawn from the question papers (row, column counted from 0 at the top-left unless the paper prints x–y axes).

F25 Quiz (Q3D) Q27 + 7 marks

For the boundary in the grid figure (anticlockwise), compute the 8-directional chain code that is (i) invariant to the starting point; (ii) invariant to both the starting point and rotation.

Step 1 · chain code. Start at the top pixel (1,2) and walk anticlockwise round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start

8-direction code: 0 = right, counting counterclockwise, 45° apart

move	from → to	direction	code
1	(1,2) → (2,1)	down-left ↙	5
2	(2,1) → (3,0)	down-left ↙	5
3	(3,0) → (4,1)	down-right ↘	7
4	(4,1) → (5,1)	down ↓	6
5	(5,1) → (6,2)	down-right ↘	7
6	(6,2) → (5,3)	up-right ↗	1
7	(5,3) → (4,4)	up-right ↗	1
8	(4,4) → (3,4)	up ↑	2
9	(3,4) → (2,3)	up-left ↖	3
10	(2,3) → (1,2)	up-left ↖	3

CC = 5576711233 (10 moves)

from 1	5	5	7	6	7	1	1	2	3	3
from 2	5	7	6	7	1	1	2	3	3	5
from 3	7	6	7	1	1	2	3	3	5	5
from 4	6	7	1	1	2	3	3	5	5	7
from 5	7	1	1	2	3	3	5	5	7	6
from 6	1	1	2	3	3	5	5	7	6	7
from 7	1	2	3	3	5	5	7	6	7	1
from 8	2	3	3	5	5	7	6	7	1	1
from 9	3	3	5	5	7	6	7	1	1	2
from 10	3	5	5	7	6	7	1	1	2	3

all circular shifts of the CC · highlighted = smallest

AnswerStart-point invariant chain code = 1123355767 (smallest shift, starting at digit 6).

Step 3 · circular first difference (CFD). Slide 22 rule: CFD_i = (c_i+1 − c_i) mod 8; the last digit wraps round to the first. This removes rotation.

i	1	2	3	4	5	6	7	8	9	10
this c_i	5	5	7	6	7	1	1	2	3	3
next c_i+1	5	7	6	7	1	1	2	3	3	5
next − this	0	2	-1	1	-6	0	1	1	0	2
mod 8 = CFD	0	2	7	1	2	0	1	1	0	2

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 0271201102

Step 4 · normalise (NCFD). Smallest circular shift of the CFD. This removes the start point too.

from 1	0	2	7	1	2	0	1	1	0	2
from 2	2	7	1	2	0	1	1	0	2	0
from 3	7	1	2	0	1	1	0	2	0	2
from 4	1	2	0	1	1	0	2	0	2	7
from 5	2	0	1	1	0	2	0	2	7	1
from 6	0	1	1	0	2	0	2	7	1	2
from 7	1	1	0	2	0	2	7	1	2	0
from 8	1	0	2	0	2	7	1	2	0	1
from 9	0	2	0	2	7	1	2	0	1	1
from 10	2	0	2	7	1	2	0	1	1	0

all circular shifts of the CFD · highlighted = smallest

AnswerChain code invariant to start point and rotation (NCFD, shape number of slides 21–22) = 0110202712.

Try it, step by step: F25 quiz boundary. Set “Normalise” to CC for part (i), CFD for part (ii).

SP24 Final Q3(d)4 + 4 marks

Write the chain code for the boundary of the object (grid figure, clockwise, start at the arrow). Compute the chain code which is invariant to both the starting point and rotation. Show the final chain code and illustrate the proof.

This is the slide 12 digit-0 boundary.

Step 1 · chain code. Start at the arrowed pixel (0,2) and walk clockwise round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start

8-direction code: 0 = right, counting counterclockwise, 45° apart

move	from → to	direction	code
1	(0,2) → (0,3)	right →	0
2	(0,3) → (0,4)	right →	0
3	(0,4) → (1,5)	down-right ↘	7
4	(1,5) → (2,6)	down-right ↘	7
5	(2,6) → (3,5)	down-left ↙	5
6	(3,5) → (4,5)	down ↓	6
7	(4,5) → (5,4)	down-left ↙	5
8	(5,4) → (6,3)	down-left ↙	5
9	(6,3) → (6,2)	left ←	4
10	(6,2) → (5,1)	up-left ↖	3
11	(5,1) → (4,1)	up ↑	2
12	(4,1) → (3,1)	up ↑	2
13	(3,1) → (2,1)	up ↑	2
14	(2,1) → (1,2)	up-right ↗	1
15	(1,2) → (0,2)	up ↑	2

CC = 007756554322212 (15 moves)

Step 2 · circular first difference (CFD). Slide 22 rule: CFD_i = (c_i+1 − c_i) mod 8; the last digit wraps round to the first. This removes rotation.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
this c_i	0	0	7	7	5	6	5	5	4	3	2	2	2	1	2
next c_i+1	0	7	7	5	6	5	5	4	3	2	2	2	1	2	0
next − this	0	7	0	-2	1	-1	0	-1	-1	-1	0	0	-1	1	-2
mod 8 = CFD	0	7	0	6	1	7	0	7	7	7	0	0	7	1	6

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 070617077700716

Step 3 · normalise (NCFD). Smallest circular shift of the CFD. This removes the start point too.

from 1	0	7	0	6	1	7	0	7	7	7	0	0	7	1	6
from 2	7	0	6	1	7	0	7	7	7	0	0	7	1	6	0
from 3	0	6	1	7	0	7	7	7	0	0	7	1	6	0	7
from 4	6	1	7	0	7	7	7	0	0	7	1	6	0	7	0
from 5	1	7	0	7	7	7	0	0	7	1	6	0	7	0	6
from 6	7	0	7	7	7	0	0	7	1	6	0	7	0	6	1
from 7	0	7	7	7	0	0	7	1	6	0	7	0	6	1	7
from 8	7	7	7	0	0	7	1	6	0	7	0	6	1	7	0
from 9	7	7	0	0	7	1	6	0	7	0	6	1	7	0	7
from 10	7	0	0	7	1	6	0	7	0	6	1	7	0	7	7
from 11	0	0	7	1	6	0	7	0	6	1	7	0	7	7	7
from 12	0	7	1	6	0	7	0	6	1	7	0	7	7	7	0
from 13	7	1	6	0	7	0	6	1	7	0	7	7	7	0	0
from 14	1	6	0	7	0	6	1	7	0	7	7	7	0	0	7
from 15	6	0	7	0	6	1	7	0	7	7	7	0	0	7	1

all circular shifts of the CFD · highlighted = smallest

AnswerChain code invariant to start point and rotation (NCFD, shape number of slides 21–22) = 007160706170777.

Proof (illustration). (a) Start point. Start instead at pixel (3,5) (move 6): CC′ = 655432221200775. Its CFD is 707770071607061, a circular shift of the CFD above, and its smallest shift is again 007160706170777.

(b) Rotation. Rotate the object 90° counterclockwise: every move turns by 90°, so every code digit increases by 2 (mod 8): CC″ = 221170776544434. CFD″ = 070617077700716, identical to the CFD above, because (c_i+1 + 2) − (c_i + 2) = c_i+1 − c_i. So NCFD″ = 007160706170777.

Same final code in both cases, so the NCFD is invariant to the start point and to rotation.

Try it, step by step: SP24 boundary (same as slide 12). After the run, change the difference rule to see why you must name it.

SP22 Final Q6(b)(ii)4 marks

Grid image of black points (axes x to the right, y upward) with an arrow at the reference pixel. Find the chain code that is invariant to the starting point and rotation, 8-neighbour.

Reading the figure. Points are written (x, y). (1,4) is filled but lies inside the outer boundary, so the outer chain passes through (0,4). In (x, y) form "up" means y + 1.

Step 1 · chain code. Start at the arrow pixel (3,5) and walk clockwise (the arrow enters (3,5) from (2,6)) round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start · axes x →, y ↑

8-direction code: 0 = right, counting counterclockwise, 45° apart

move	from → to	direction	code
1	(3,5) → (4,6)	up-right ↗	1
2	(4,6) → (5,5)	down-right ↘	7
3	(5,5) → (6,4)	down-right ↘	7
4	(6,4) → (5,3)	down-left ↙	5
5	(5,3) → (4,2)	down-left ↙	5
6	(4,2) → (3,1)	down-left ↙	5
7	(3,1) → (2,2)	up-left ↖	3
8	(2,2) → (1,3)	up-left ↖	3
9	(1,3) → (0,4)	up-left ↖	3
10	(0,4) → (1,5)	up-right ↗	1
11	(1,5) → (2,6)	up-right ↗	1
12	(2,6) → (3,5)	down-right ↘	7

CC = 177555333117 (12 moves)

from 1	1	7	7	5	5	5	3	3	3	1	1	7
from 2	7	7	5	5	5	3	3	3	1	1	7	1
from 3	7	5	5	5	3	3	3	1	1	7	1	7
from 4	5	5	5	3	3	3	1	1	7	1	7	7
from 5	5	5	3	3	3	1	1	7	1	7	7	5
from 6	5	3	3	3	1	1	7	1	7	7	5	5
from 7	3	3	3	1	1	7	1	7	7	5	5	5
from 8	3	3	1	1	7	1	7	7	5	5	5	3
from 9	3	1	1	7	1	7	7	5	5	5	3	3
from 10	1	1	7	1	7	7	5	5	5	3	3	3
from 11	1	7	1	7	7	5	5	5	3	3	3	1
from 12	7	1	7	7	5	5	5	3	3	3	1	1

all circular shifts of the CC · highlighted = smallest

AnswerStart-point invariant chain code = 117177555333 (smallest shift, starting at digit 10).

Step 3 · circular first difference (CFD). Slide 22 rule: CFD_i = (c_i+1 − c_i) mod 8; the last digit wraps round to the first. This removes rotation.

i	1	2	3	4	5	6	7	8	9	10	11	12
this c_i	1	7	7	5	5	5	3	3	3	1	1	7
next c_i+1	7	7	5	5	5	3	3	3	1	1	7	1
next − this	6	0	-2	0	0	-2	0	0	-2	0	6	-6
mod 8 = CFD	6	0	6	0	0	6	0	0	6	0	6	2

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 606006006062

Step 4 · normalise (NCFD). Smallest circular shift of the CFD. This removes the start point too.

from 1	6	0	6	0	0	6	0	0	6	0	6	2
from 2	0	6	0	0	6	0	0	6	0	6	2	6
from 3	6	0	0	6	0	0	6	0	6	2	6	0
from 4	0	0	6	0	0	6	0	6	2	6	0	6
from 5	0	6	0	0	6	0	6	2	6	0	6	0
from 6	6	0	0	6	0	6	2	6	0	6	0	0
from 7	0	0	6	0	6	2	6	0	6	0	0	6
from 8	0	6	0	6	2	6	0	6	0	0	6	0
from 9	6	0	6	2	6	0	6	0	0	6	0	0
from 10	0	6	2	6	0	6	0	0	6	0	0	6
from 11	6	2	6	0	6	0	0	6	0	0	6	0
from 12	2	6	0	6	0	0	6	0	0	6	0	6

all circular shifts of the CFD · highlighted = smallest

AnswerChain code invariant to start point and rotation (NCFD, shape number of slides 21–22) = 006006062606.

Try it, step by step: SP22 points, labelled in (x, y) like the paper.

SP23 Final Q2(c)1 + 4 marks

What is chain code? For the boundary figure (counterclockwise), compute the chain code that is invariant to the starting point (8-direction).

Chain code is a boundary representation: starting from a boundary pixel, the contour is written as a sequence of direction numbers (0–7 for 8-connectivity, 0 = right, counterclockwise), one per step to the next boundary pixel. It is compact and translation invariant.

Reading the figure. Polygon edges counterclockwise from the bottom vertex: up-right ×2, right ×2, up ×2, up-left ×2, left ×2, down-left ×2, down-right ×2, down ×2.

Step 1 · chain code. Start at the bottom vertex and walk counterclockwise round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start

8-direction code: 0 = right, counting counterclockwise, 45° apart

CC = 1100223344557766 (16 moves)

from 1	1	1	0	0	2	2	3	3	4	4	5	5	7	7	6	6
from 2	1	0	0	2	2	3	3	4	4	5	5	7	7	6	6	1
from 3	0	0	2	2	3	3	4	4	5	5	7	7	6	6	1	1
from 4	0	2	2	3	3	4	4	5	5	7	7	6	6	1	1	0
from 5	2	2	3	3	4	4	5	5	7	7	6	6	1	1	0	0
from 6	2	3	3	4	4	5	5	7	7	6	6	1	1	0	0	2
from 7	3	3	4	4	5	5	7	7	6	6	1	1	0	0	2	2
from 8	3	4	4	5	5	7	7	6	6	1	1	0	0	2	2	3
from 9	4	4	5	5	7	7	6	6	1	1	0	0	2	2	3	3
from 10	4	5	5	7	7	6	6	1	1	0	0	2	2	3	3	4
from 11	5	5	7	7	6	6	1	1	0	0	2	2	3	3	4	4
from 12	5	7	7	6	6	1	1	0	0	2	2	3	3	4	4	5
from 13	7	7	6	6	1	1	0	0	2	2	3	3	4	4	5	5
from 14	7	6	6	1	1	0	0	2	2	3	3	4	4	5	5	7
from 15	6	6	1	1	0	0	2	2	3	3	4	4	5	5	7	7
from 16	6	1	1	0	0	2	2	3	3	4	4	5	5	7	7	6

all circular shifts of the CC · highlighted = smallest

AnswerStart-point invariant chain code = 0022334455776611 (smallest shift, starting at digit 3).

(Not asked, but if they add rotation: CFD = 0702010101020703, NCFD = 0101010207030702.)

Try it, step by step: SP23 polygon (code 1100223344557766). Normalise is set to CC because the question asks only for start-point invariance.

F21 Final B1(b)3 + 3 marks

(i) What is chain code? Problems in chain code representation. (ii) For the boundary (grid figure, anticlockwise), find the chain code invariant to both starting point and rotation, 8-neighbour.

(i) A chain code represents a boundary by a start pixel and a sequence of direction numbers (8-dir: 0 = right, 1 = up-right, … 7 = down-right), one per step along the contour. Problems: it depends on the starting point; it changes with rotation; its length changes with scale; it is sensitive to noise (small bumps change many digits); codes get long for big boundaries; different traversal/connectivity choices give different codes (ambiguity). Fixes: shape number / NCFD and resampling.

(ii)

Step 1 · chain code. Start at the arrowed bottom pixel (8,3) and walk anticlockwise round the boundary. Each move to the next boundary pixel gets the number of its direction (8-direction compass: 0 = right, then counterclockwise).

boundary with each move's code · ringed = start

8-direction code: 0 = right, counting counterclockwise, 45° apart

move	from → to	direction	code
1	(8,3) → (7,4)	up-right ↗	1
2	(7,4) → (6,5)	up-right ↗	1
3	(6,5) → (6,6)	right →	0
4	(6,6) → (6,7)	right →	0
5	(6,7) → (5,7)	up ↑	2
6	(5,7) → (4,8)	up-right ↗	1
7	(4,8) → (4,9)	right →	0
8	(4,9) → (4,10)	right →	0
9	(4,10) → (3,10)	up ↑	2
10	(3,10) → (2,9)	up-left ↖	3
11	(2,9) → (1,8)	up-left ↖	3
12	(1,8) → (0,7)	up-left ↖	3
13	(0,7) → (0,6)	left ←	4
14	(0,6) → (0,5)	left ←	4
15	(0,5) → (0,4)	left ←	4
16	(0,4) → (1,3)	down-left ↙	5
17	(1,3) → (2,3)	down ↓	6
18	(2,3) → (3,2)	down-left ↙	5
19	(3,2) → (4,1)	down-left ↙	5
20	(4,1) → (5,1)	down ↓	6
21	(5,1) → (6,1)	down ↓	6
22	(6,1) → (7,2)	down-right ↘	7
23	(7,2) → (8,3)	down-right ↘	7

CC = 11002100233344456556677 (23 moves)

Step 2 · circular first difference (CFD). Slide 22 rule: CFD_i = (c_i+1 − c_i) mod 8; the last digit wraps round to the first. This removes rotation.

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
this c_i	1	1	0	0	2	1	0	0	2	3	3	3	4	4	4	5	6	5	5	6	6	7	7
next c_i+1	1	0	0	2	1	0	0	2	3	3	3	4	4	4	5	6	5	5	6	6	7	7	1
next − this	0	-1	0	2	-1	-1	0	2	1	0	0	1	0	0	1	1	-1	0	1	0	1	0	-6
mod 8 = CFD	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2

first difference, last column wraps round (next of the last digit = the first digit)

CFD = 07027702100100117010102

Step 3 · normalise (NCFD). Smallest circular shift of the CFD. This removes the start point too.

from 1	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2
from 2	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0
from 3	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7
from 4	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0
from 5	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2
from 6	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7
from 7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7
from 8	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0
from 9	1	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2
from 10	0	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1
from 11	0	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0
from 12	1	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0
from 13	0	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1
from 14	0	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0
from 15	1	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0
from 16	1	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1
from 17	7	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1
from 18	0	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7
from 19	1	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0
from 20	0	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1
from 21	1	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0
from 22	0	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1
from 23	2	0	7	0	2	7	7	0	2	1	0	0	1	0	0	1	1	7	0	1	0	1	0

all circular shifts of the CFD · highlighted = smallest

AnswerChain code invariant to start point and rotation (NCFD, shape number of slides 21–22) = 00100117010102070277021.

Try it, step by step: F21 boundary, anticlockwise from the arrow at the bottom (23 moves).

SP25 Final (CLO3 case study)case study

A medical imaging team analyses X-ray images of bones to detect fractures. They apply chain code representation, histogram analysis, the Hough transform and power-law transformation. Discuss how each technique contributes to detecting fractures and enhancing the image, with applications, advantages or limitations.

Power-law (gamma) transformation s = c·r^γ first adjusts contrast: γ < 1 brightens dark regions so thin, faint fracture lines in dense bone become visible; γ > 1 darkens washed-out regions. Cheap, pointwise; limitation: one γ for the whole image, needs tuning.

Histogram analysis (and equalisation) shows how gray levels are spread; it helps choose a threshold to separate bone from soft tissue and spreads crowded levels to raise contrast. Limitation: global, can amplify noise.

Chain code representation: after segmenting the bone, its outer boundary is written as a chain code. A healthy bone outline is smooth (CFD mostly 0, small turns); a fracture shows as a sudden break or sharp turns (large CFD digits such as 2–6) or a gap in the boundary. The normalised CFD (shape number) lets the team compare the bone's shape with a template or an earlier scan regardless of start point or rotation (patient position). Advantages: compact, translation and (after normalisation) rotation invariant. Limitations: sensitive to noise and scale; resample the boundary first.

Hough transform finds straight lines (and other parametric shapes) even when broken: fracture lines are often line-like, so peaks in the (ρ, θ) accumulator locate them and their angle, and bone shafts can be fitted as lines to spot misalignment. Robust to gaps and noise; limitation: heavier computation, needs good edge maps.

Together: power-law + histogram → clearer image; segmentation and chain code → bone outline and shape change; Hough → fracture line position and orientation.

Traps and one-minute sheet

slides all

Draw the compass in every answer: 0 = right, counting counterclockwise. 8-dir: 2 = up, 6 = down. 4-dir: 1 = up, 3 = down.
Grid rows count downward: going to a smaller row number is "up". If the paper prints x–y axes (SP22), up is y + 1.
Walk in the direction the question says (clockwise / anticlockwise). Wrong direction = wrong code.
The chain is closed: the last move returns to the start pixel, and the CFD's last digit wraps to the first code. CC and CFD have the same number of digits.
Negative difference: add n (8 or 4). (2 − 7) mod 8 = 3.
"Invariant to start point" = smallest shift of the CC. "Invariant to start point and rotation" = smallest shift of the CFD (NCFD).
Slide 22 uses next − this, slide 23 uses this − next. Name your rule.
Smallest shift: compare digit by digit from the left; the first digit that differs decides. Show the list of shifts, it is where the marks are.

what	how	invariant to
chain code CC	one direction number per boundary step	translation
smallest shift of CC	min over circular shifts	+ start point
CFD	(c_i+1 − c_i) mod n, wrap round	+ rotation (multiples of 45°/90°)
NCFD (shape number)	min over circular shifts of CFD	start point + rotation
resampling	coarser grid before coding	less noise, shorter code (helps scale)