
Lecture 15
Computer Science Department, Colorado School of Mines
By the end of this lecture, you should be able to:
| 1. Image Filtering | \(\displaystyle y[m,n]=\sum_{k,l} h[k,l]\,I[m+k,n+l]\) |
| 2. Optical Flow | \(\displaystyle I(x,y,t)=I(x+\Delta x,\ y+\Delta y,\ t+\Delta t)\) |
| 3. Camera Geometry | \(\displaystyle \lambda\,\mathbf{x}=\mathbf{K}\begin{bmatrix}{}^{c}\mathbf{R}_{w}&{}^{c}\mathbf{t}_{w}\end{bmatrix}\,{}^{w}\mathbf{X} \qquad \mathbf{x}^{T}\mathbf{F}\mathbf{x}'=0\) |
| 4. Machine Learning | \(\displaystyle \underset{\mathcal{S}}{\operatorname{arg\,min}}\sum_{i=1}^{k}\sum_{\mathbf{x}\in S_i}\left\lVert\mathbf{x}-\boldsymbol{\mu}_i\right\rVert^{2} \qquad y=\varphi\!\left(\mathbf{w}^{T}\mathbf{x}+b\right)\) |




| Type | Training data | Vision examples |
|---|---|---|
| Supervised | images and labels | classify clothing; detect pedestrians |
| Unsupervised | images only | group pixels by color (clustering); compress images (PCA) |
| Self-supervised | images only; the labels come from the data itself | predict hidden patches; match images to their captions |

| Dataset | Year | Images | Classes | Image size | Task |
|---|---|---|---|---|---|
| MNIST | 1998 | 60,000 train + 10,000 test | 10 digits | 28 × 28, gray | classification |
| FashionMNIST | 2017 | 60,000 train + 10,000 test | 10 clothing types | 28 × 28, gray | classification |
| CIFAR-10 | 2009 | 50,000 train + 10,000 test | 10 objects and animals | 32 × 32, color | classification |
| ImageNet | 2012 | 1.28 M train + 50,000 val | 1,000 | varies, color | classification |
| COCO | 2014 | 118,000 train + 5,000 val | 80 | varies, color | detection, segmentation, captions |
| Penn-Fudan | 2007 | 170 | pedestrians | varies, color | detection, segmentation |
| Images | Per class | |
|---|---|---|
| Training | 60,000 | 6,000 |
| Test | 10,000 | 1,000 |
28 × 28 gray images: 784 pixels, values 0 to 255.
Same format as MNIST, but harder: T-shirt, pullover, coat, and shirt look alike.
Small enough to train on a laptop CPU.
We compare our classifiers on this benchmark.

\[ \bbox[border: 2px solid #c53030; padding: 2px 6px]{\hat{y} = w_0 + w_1 x + w_2 x^2 + \dots + w_M x^M}\;\;{\color{#c53030}{\begin{array}{l}\textbf{polynomial}\\ \textbf{model}\end{array}}} \]
\[ \text{MSE} = \frac{1}{N} \sum_{i=1}^{N} \left(y_i - \hat{y}_i\right)^2 \]



Choosing a Hyperparameter


Polynomial.fit(x, y, deg): finds the \(w\)’s with the smallest training MSE (least squares).model(x): evaluates the fitted polynomial at x.mse(...): the mean squared error from before.min(val_mse, key=val_mse.get): the degree with the lowest validation error.On our data: best \(M\) = 3, test MSE = 0.072.

import numpy as np
from numpy.polynomial import Polynomial
def mse(model, x, y):
return np.mean((model(x) - y) ** 2)
# (x_tr, y_tr), (x_val, y_val), (x_te, y_te): splits
val_mse = {}
for M in range(16):
model = Polynomial.fit(x_tr, y_tr, deg=M)
val_mse[M] = mse(model, x_val, y_val)
best_M = min(val_mse, key=val_mse.get)
model = Polynomial.fit(x_tr, y_tr, deg=best_M)
print(best_M, mse(model, x_te, y_te)) # test: onceimport numpy as np
import matplotlib.pyplot as plt
from numpy.polynomial import Polynomial
# 1. Data: noisy samples of y = sin(2 pi x). Split 20 / 10 / 10.
rng = np.random.default_rng(0)
x = rng.uniform(0, 1, 40)
y = np.sin(2 * np.pi * x) + rng.normal(0, 0.25, 40)
x_tr, y_tr = x[:20], y[:20]
x_val, y_val = x[20:30], y[20:30]
x_te, y_te = x[30:], y[30:]
def mse(model, x, y):
return np.mean((model(x) - y) ** 2)
# 2. Fit every degree on the training set; measure training and validation error.
degrees = range(16)
train_mse, val_mse = [], []
for M in degrees:
model = Polynomial.fit(x_tr, y_tr, deg=M)
train_mse.append(mse(model, x_tr, y_tr))
val_mse.append(mse(model, x_val, y_val))
# 3. Choose the degree on the validation set; report the test error once.
best_M = int(np.argmin(val_mse))
model = Polynomial.fit(x_tr, y_tr, deg=best_M)
print("best degree:", best_M)
print("test MSE:", mse(model, x_te, y_te))
# 4. Plot the errors and the chosen fit.
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4.5))
ax1.semilogy(degrees, train_mse, "o-", label="training")
ax1.semilogy(degrees, val_mse, "s-", label="validation")
ax1.set_xlabel("degree")
ax1.set_ylabel("MSE")
ax1.legend()
xs = np.linspace(0, 1, 400)
ax2.scatter(x_tr, y_tr, label="training points")
ax2.plot(xs, model(xs), "g", label=f"degree {best_M} fit")
ax2.plot(xs, np.sin(2 * np.pi * xs), "k--", label="true curve")
ax2.legend()
plt.tight_layout()
plt.savefig("poly_fit.png")
plt.show()
| Task | Output | Common metrics |
|---|---|---|
| Regression | number(s) | mean squared error (MSE) |
| Classification | a category | accuracy; confusion matrix (which classes get mixed up) |
| Detection | a box and class per object | intersection over union (IoU); precision and recall; average precision (AP) |
| Segmentation | a label per pixel | IoU per class |

\[ \bbox[border: 2px solid #c53030; padding: 2px 6px]{d(\mathbf{x}, \mathbf{x}') = \sqrt{\sum_{j=1}^{784} \left(x_j - x'_j\right)^2}}\;\;{\color{#c53030}{\begin{array}{l}\textbf{L2}\\ \textbf{distance}\end{array}}} \]


k-Nearest Neighbors (KNN)
Training: store all training images and their labels.
Prediction for a new image \(\mathbf{x}\):



KNearest_create(): an empty KNN model.train(X, cv2.ml.ROW_SAMPLE, y): stores the data. X: one image per row (float32); y: the labels.findNearest(X, k): KNN prediction for each row of X. Returns the predicted labels, the labels of the k neighbors, and their distances.import cv2
import numpy as np
# X_tr: (50000, 784) float32, y_tr: labels 0-9
# X_te: (10000, 784) float32, y_te: labels 0-9
knn = cv2.ml.KNearest_create()
knn.train(X_tr, cv2.ml.ROW_SAMPLE,
y_tr.astype(np.float32))
# best_k: chosen on the validation set
_, pred, neighbors, dist = knn.findNearest(
X_te, k=best_k)
pred = pred.ravel().astype(int)
print("test accuracy:", np.mean(pred == y_te))
import gzip
from pathlib import Path
import cv2
import numpy as np
import matplotlib.pyplot as plt
# 1. Data: FashionMNIST as 784-vectors. Split 50,000 training / 10,000 validation; 10,000 test.
data_dir = Path("assets/datasets/fashion_mnist") # folder with the four .gz files
def read_idx(name, offset):
with gzip.open(data_dir / name) as f:
return np.frombuffer(f.read(), np.uint8, offset=offset)
X = read_idx("train-images-idx3-ubyte.gz", 16).reshape(-1, 784).astype(np.float32)
y = read_idx("train-labels-idx1-ubyte.gz", 8).astype(int)
X_te = read_idx("t10k-images-idx3-ubyte.gz", 16).reshape(-1, 784).astype(np.float32)
y_te = read_idx("t10k-labels-idx1-ubyte.gz", 8).astype(int)
X_tr, y_tr, X_val, y_val = X[:50000], y[:50000], X[50000:], y[50000:]
# 2. "Training": store the training images.
knn = cv2.ml.KNearest_create()
knn.train(X_tr, cv2.ml.ROW_SAMPLE, y_tr.astype(np.float32))
# 3. Choose k on the validation set. One search for the 20 nearest neighbors
# (closest first), then a majority vote among the first k of them.
ks = range(1, 21)
_, _, neighbors, _ = knn.findNearest(X_val, k=max(ks))
neighbors = neighbors.astype(int)
val_acc = []
for k in ks:
pred = np.array([np.bincount(row[:k], minlength=10).argmax() for row in neighbors])
val_acc.append(np.mean(pred == y_val))
best_k = ks[int(np.argmax(val_acc))]
print(f"best k = {best_k}, validation accuracy = {max(val_acc):.3f}")
# 4. Test accuracy with the chosen k, once.
_, pred, _, _ = knn.findNearest(X_te, k=best_k)
pred = pred.ravel().astype(int)
print(f"test accuracy = {np.mean(pred == y_te):.3f}")
# 5. Confusion matrix: row = true class, column = predicted class.
confusion = np.zeros((10, 10), int)
np.add.at(confusion, (y_te, pred), 1)
print(confusion)
# 6. Plot the validation curve.
plt.plot(ks, val_acc, "s-")
plt.xlabel("k")
plt.ylabel("validation accuracy")
plt.show()Confusion matrix: entry (row \(i\), column \(j\)) = number of test images of class \(i\) predicted as class \(j\).
Diagonal: correct predictions. Off-diagonal: mistakes, and which classes get mixed up.
\(\text{accuracy} = \dfrac{\text{sum of the diagonal}}{\text{sum of all entries}}\)
KNN (\(k\) = 6): 8,502 / 10,000 correct = 85.0%.
Easiest: Sneaker (97% correct). Hardest: Shirt (54%), most often called T-shirt/top (207 times).


k-Means Clustering

cv2.kmeans(data, K, bestLabels, criteria, attempts, flags):
data: one point per row (float32).K: the number of clusters \(k\).bestLabels: starting labels (None: not given).criteria: stop after 20 rounds or when the centers move < 1.0.attempts: 5 runs from different starts; keep the lowest compactness.flags: starting centers. KMEANS_PP_CENTERS: k-means++; KMEANS_RANDOM_CENTERS: random points.compactness, labels (cluster of each point), centers (\(k\) × 3).centers[labels]: each pixel → its center color.import cv2
import numpy as np
image = cv2.imread("fruits.jpg") # H x W x 3 (BGR)
pixels = image.reshape(-1, 3).astype(np.float32)
stop = cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER
criteria = (stop, 20, 1.0) # 20 rounds or moves < 1.0
compactness, labels, centers = cv2.kmeans(
pixels, 4, None, criteria, 5, cv2.KMEANS_PP_CENTERS)
segmented = centers[labels.ravel()].reshape(image.shape)
cv2.imwrite("fruits_k4.png", segmented.astype(np.uint8))PCA

\(\mathbf{u}_1\) holds 93% of the variance. Keep only the coordinate along \(\mathbf{u}_1\): 1 number instead of 2, and the points barely move.


\[ \bbox[border: 2px solid #c53030; padding: 2px 6px]{\hat{\mathbf{x}} = \boldsymbol{\mu} + a_1 \mathbf{u}_1 + \dots + a_k \mathbf{u}_k}\;\;{\color{#c53030}{\begin{array}{l}\textbf{PCA}\\ \textbf{reconstruction}\end{array}}} \]


PCACompute(data, mean, maxComponents): data has one image per row. mean=None: compute the mean. Returns the mean \(\boldsymbol{\mu}\) (1 × 784) and the components \(\mathbf{u}_j\) (one per row: 50 × 784).PCAProject(X, mean, vecs): the coordinates \(a_1, \dots, a_k\) of each row of X.PCABackProject(A, mean, vecs): the reconstructions \(\boldsymbol{\mu} + a_1 \mathbf{u}_1 + \dots + a_k \mathbf{u}_k\).| Input | Numbers | Accuracy | Time / image |
|---|---|---|---|
| pixels | 784 | 85.0% | 1.4 ms |
| PCA | 50 | 85.6% | 0.1 ms |
import cv2
import numpy as np
# X_tr: (50000, 784), X_te: (10000, 784) float32
mu, U = cv2.PCACompute(X_tr, mean=None, maxComponents=50)
F_tr = cv2.PCAProject(X_tr, mu, U) # (50000, 50)
F_te = cv2.PCAProject(X_te, mu, U) # (10000, 50)
X_hat = cv2.PCABackProject(F_te, mu, U) # (10000, 784)
print("MSE:", np.mean((X_hat - X_te) ** 2))
# Any classifier can use the features, e.g., KNN:
knn = cv2.ml.KNearest_create()
knn.train(F_tr, cv2.ml.ROW_SAMPLE, y_tr.astype(np.float32))
_, pred, _, _ = knn.findNearest(F_te, k=best_k)\[ \bbox[border: 2px solid #c53030; padding: 2px 6px]{f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b}\;\;{\color{#c53030}{\begin{array}{l}\textbf{linear}\\ \textbf{classifier}\end{array}}} \]
\(\mathbf{x}\): input point coordinates.
\(\mathbf{w}\): weights; \(b\): bias. Both learned.
Predict orange if \(f(\mathbf{x}) > 0\), blue otherwise.
The decision boundary \(f(\mathbf{x}) = 0\) is a line (a “hyperplane” in more dimensions).
Many lines separate the training points (dashed). Which one is best?

One vs. Rest

One vs. One
| One vs. rest | One vs. one | |
|---|---|---|
| SVMs for 3 classes | 3 | 3 |
| SVMs for 10 classes | 10 | 45 |
| Data per SVM | all images | images of 2 classes |
| Prediction | highest score | most votes |

setType(SVM_C_SVC): classification with a soft margin.setKernel(SVM_RBF), setC(...), setGamma(...): kernel and hyperparameters.train(F, ROW_SAMPLE, y): F one feature vector per row (float32); y labels (int32).predict(F): predicted labels.| \(\gamma\) = 0.01 | \(\gamma\) = 0.03 | \(\gamma\) = 0.1 | |
|---|---|---|---|
| \(C\) = 1 | 84.3% | 85.8% | 86.1% |
| \(C\) = 10 | 86.4% | 86.9% | 86.3% |
| \(C\) = 100 | 86.7% | 85.9% | 86.2% |
import cv2
import numpy as np
# F_tr, F_te: PCA features (50 per image), scaled
svm = cv2.ml.SVM_create()
svm.setType(cv2.ml.SVM_C_SVC)
svm.setKernel(cv2.ml.SVM_RBF)
svm.setC(best_C) # chosen on validation data
svm.setGamma(best_gamma)
svm.train(F_tr, cv2.ml.ROW_SAMPLE, y_tr.astype(np.int32))
# 10 classes: OpenCV trains 45 one-vs-one SVMs inside
_, pred = svm.predict(F_te)
print("test accuracy:", np.mean(pred.ravel() == y_te))import gzip
import time
from pathlib import Path
import cv2
import numpy as np
# 1. Data: FashionMNIST as 784-vectors. Split 50,000 training / 10,000 validation; 10,000 test.
data_dir = Path("assets/datasets/fashion_mnist") # folder with the four .gz files
def read_idx(name, offset):
with gzip.open(data_dir / name) as f:
return np.frombuffer(f.read(), np.uint8, offset=offset)
X = read_idx("train-images-idx3-ubyte.gz", 16).reshape(-1, 784).astype(np.float32)
y = read_idx("train-labels-idx1-ubyte.gz", 8).astype(np.int32)
X_te = read_idx("t10k-images-idx3-ubyte.gz", 16).reshape(-1, 784).astype(np.float32)
y_te = read_idx("t10k-labels-idx1-ubyte.gz", 8).astype(np.int32)
X_tr, y_tr, X_val, y_val = X[:50000], y[:50000], X[50000:], y[50000:]
# 2. PCA features (learned on the training set only), scaled to unit spread.
mu, U = cv2.PCACompute(X_tr, mean=None, maxComponents=50)
F_tr = cv2.PCAProject(X_tr, mu, U)
scale = F_tr.std()
F_tr = F_tr / scale
F_val = cv2.PCAProject(X_val, mu, U) / scale
F_te = cv2.PCAProject(X_te, mu, U) / scale
def train_svm(F, y, C, gamma):
svm = cv2.ml.SVM_create()
svm.setType(cv2.ml.SVM_C_SVC)
svm.setKernel(cv2.ml.SVM_RBF)
svm.setC(C)
svm.setGamma(gamma)
svm.setTermCriteria((cv2.TERM_CRITERIA_MAX_ITER + cv2.TERM_CRITERIA_EPS, 10000, 1e-3))
svm.train(F, cv2.ml.ROW_SAMPLE, y) # 10 classes: 45 one-vs-one SVMs inside
return svm
def accuracy(svm, F, y):
return np.mean(svm.predict(F)[1].ravel() == y)
# 3. Choose C and gamma on the validation set (train on 10,000 images to save time).
best_acc, best_C, best_gamma = 0, None, None
for C in [1, 10, 100]:
for gamma in [0.01, 0.03, 0.1]:
acc = accuracy(train_svm(F_tr[:10000], y_tr[:10000], C, gamma), F_val, y_val)
print(f"C = {C}, gamma = {gamma}: validation accuracy = {acc:.3f}")
if acc > best_acc:
best_acc, best_C, best_gamma = acc, C, gamma
# 4. Final model on all training images; test accuracy, once.
t0 = time.perf_counter()
svm = train_svm(F_tr, y_tr, best_C, best_gamma)
print(f"trained in {time.perf_counter() - t0:.0f} s")
print(f"C = {best_C}, gamma = {best_gamma}: test accuracy = {accuracy(svm, F_te, y_te):.3f}")| Method | Input | Test accuracy | Training time | Time per image | Model size |
|---|---|---|---|---|---|
| KNN (\(k\) = 6) | 784 pixels | 85.0% | none | 1.4 ms | 157 MB |
| KNN (\(k\) = 6) | 50 PCA features | 85.6% | PCA only | 0.1 ms | 10 MB |
| SVM (RBF) | 50 PCA features | 88.9% | 16.5 s | 0.1 ms | 3.1 MB |

Computer Vision; Colorado School of Mines | Kaveh Fathian