Introduction
So far every program has answered questions about pixels: how bright, where the edges are, which pixels form an object. Image classification asks a question about the whole picture: is this a cat or a dog, a 3 or an 8, a pedestrian or a lamp post? This lesson builds a classifier from parts you already know, the k-nearest-neighbours rule and gradients, and shows the key idea of classic computer vision: features.
How it works
Images as vectors. Flatten an image row by row and it becomes a long list of numbers, a point in a space with one dimension per pixel. Similar images should be close points. The L1 distance adds absolute differences, Σ |aᵢ − bᵢ|; the L2 distance is √(Σ (aᵢ − bᵢ)²); comparing squared L2 distances avoids the square root and gives the same order.
k-nearest neighbours. Keep a training set of labelled images. To classify a new image, find the k training images closest to it and take a vote among their labels. With k = 1, you copy the label of the single nearest image. Larger k is more robust to mislabelled or unusual examples; ties need a rule, such as preferring the closer neighbour. k-NN does no learning at all, but every prediction compares the new image with the whole training set, which gets slow for large datasets.
Measuring. Always evaluate on a separate test set, never on the training images (k = 1 would score 100% on its own training data). Report accuracy, and a confusion matrix (how often class A is predicted as class B) to see which classes are confused.
Why raw pixels fail. Move a vertical bar one pixel to the right and almost every pixel changes, so its raw distance to the original bar can be larger than its distance to a completely different shape. Pixel distances measure where ink is, not what shape it makes.
Features. A feature is a measurement chosen to describe what matters and ignore what does not. For shapes, edge directions matter more than exact positions. The histogram of oriented gradients (HOG, Dalal and Triggs, 2005) computes the gradient at each pixel, takes its direction (from 0° to 180°, ignoring sign), and adds its magnitude to a histogram of direction bins. It does this separately for small cells (such as 8 × 8 pixels) and normalises the histograms so lighting changes cancel out. A vertical bar produces mainly horizontal gradients (0°) wherever it is, so its HOG features hardly change when it moves within a cell. HOG features with a linear classifier were the standard pedestrian detector for years.
Example
train = [
("vertical", "0100/0100/0100/0100"),
("horizontal", "0000/1111/0000/0000"),
("diagonal", "1000/0100/0010/0001"),
]
tests = [
("vertical", "0001/0001/0001/0001"),
("horizontal", "0000/0000/0000/1111"),
("diagonal", "0001/0010/0100/1000"),
]
def pixel_distance(a, b):
return sum([x != y for x, y in zip(a, b)])
def switches(rows):
return sum([row.count("01") + row.count("10") for row in rows])
def features(img):
# How often the ink switches on or off moving across, and moving down, as shares of all switches.
rows = img.split("/")
columns = ["".join(col) for col in zip(*rows)]
across, down = switches(rows), switches(columns)
return (across / (across + down), down / (across + down))
known = [(name, features(img)) for name, img in train]
right_pixels = right_features = 0
for truth, img in tests:
by_pixels = min([(pixel_distance(img, t), name) for name, t in train])[1]
f = features(img)
by_features = min([(abs(f[0] - g[0]) + abs(f[1] - g[1]), name) for name, g in known])[1]
print(f"{truth:10} features {f} pixels say {by_pixels:10} features say {by_features}")
right_pixels += by_pixels == truth
right_features += by_features == truth
print("correct:", right_pixels, "of 3 by pixels,", right_features, "of 3 by features")Line by line
- Each 4 × 4 picture is written as one string, rows separated by
/. There is one training picture per class: a vertical bar, a horizontal bar and a diagonal. - The test pictures show the same three shapes in different places.
pixel_distancecounts differing characters, the L1 distance for 0/1 pixels.featuresis a tiny, two-bin relative of HOG: it counts how often the ink switches on or off moving across the rows and moving down the columns, as shares of the total. A vertical bar only switches across, giving (1.0, 0.0).- By pixels, every test picture is closer to a different class: the vertical bar at column 3 differs from the training vertical bar in 8 pixels but from the horizontal bar and the diagonal in only 6. All three predictions are wrong.
- By features, each shape matches its own class exactly, wherever it is drawn, so all three are right.
Expected result
vertical features (1.0, 0.0) pixels say diagonal features say vertical
horizontal features (0.0, 1.0) pixels say diagonal features say horizontal
diagonal features (0.5, 0.5) pixels say horizontal features say diagonal
correct: 0 of 3 by pixels, 3 of 3 by features
In the real world
k-NN on raw pixels classifies the MNIST handwritten digits (28 × 28 pixels, 70,000 images) with about 97% accuracy, because digits are centred and similar in size. Real photos vary far more, which is why HOG, SIFT-style descriptors and, since 2012, learned features from convolutional networks took over. Nearest-neighbour search is still everywhere: photo search, face recognition and duplicate detection compare learned feature vectors with fast approximate neighbour search. In Python (shown as text; these libraries do not run on this site):
from skimage.feature import hog
from sklearn.neighbors import KNeighborsClassifier
features = [hog(img, orientations=9, pixels_per_cell=(8, 8), cells_per_block=(2, 2)) for img in images]
model = KNeighborsClassifier(n_neighbors=3).fit(features, labels)
print(model.score(test_features, test_labels)) # accuracy on the test set
Common mistakes
- Testing on the training images, which hides how badly the classifier generalises.
- Comparing raw pixels of images that are not aligned, so position differences swamp shape differences.
- Forgetting to scale features, so one large-valued feature decides every distance.
- Using an even k with two classes, which invites ties.
- Reporting only accuracy when one class is rare; check the confusion matrix too.
Best practices
- Split the data into training and test sets first, and keep the test set untouched until the end.
- Start with a simple baseline (k-NN on pixels) so you know how much better features or networks are.
- Normalise feature vectors, as HOG does, to cancel lighting and contrast changes.
- Look at misclassified test images; they show what the features miss.
Summary
An image can be flattened into a vector and classified by its nearest neighbours in a labelled training set, with accuracy measured on separate test images. Raw pixel distances break when objects move, so classic vision describes images with features. HOG collects gradient directions, weighted by magnitude, into normalised histograms per cell, capturing shape while tolerating small shifts and lighting changes.
Quick check
Key takeaways
- A classifier is only as good as the features it compares; raw pixels change completely when an object moves one pixel.
- k-NN needs no training, but it must compare every test image with every training image.
- Gradient-orientation histograms describe shape (which way edges run) and tolerate small shifts and lighting changes.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.