Teletext
Algorithm Load patterns: For each known character, store its h w pixel grid. Segment the image: Divide the input image into cells of size h w. Match each cell: Compare pixel-by-pixel against all patterns. For exact ma...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
A teletext display renders characters using a fixed-size pixel grid (a dot-matrix font). Given a library of known character patterns and an input image, recognize each character cell and decode the displayed message.
Each character occupies a cell of $w \times h$ pixels. The input image is a pixel grid whose dimensions are exact multiples of $w$ and $h$. Match each cell against the known patterns to decode the text.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Algorithm
Load patterns: For each known character, store its $h \times w$ pixel grid.
Segment the image: Divide the input image into cells of size $h \times w$.
Match each cell: Compare pixel-by-pixel against all patterns. For exact matching, find the pattern with zero differences. For noisy input, find the pattern with the smallest Hamming distance (number of differing pixels).
Hamming Distance
The Hamming distance between two $h \times w$ binary grids $A$ and $B$ is: \[ d(A, B) = \sum_{r=0}^{h-1} \sum_{c=0}^{w-1} \mathbf{1}[A[r][c] \ne B[r][c]]. \]
For noise-free input, the correct character has $d = 0$.
Complexity Analysis
Time: $O(T \cdot K \cdot wh)$ where $T$ is the number of character cells, $K$ is the alphabet size, and $wh$ is the cell size.
Space: $O(Kwh + WH)$ for storing patterns and the input image.
For typical parameters ($K \le 128$, $w, h \le 16$), this is efficient.
Example
Suppose characters are $3 \times 5$ pixels (width $\times$ height), with patterns for A and B:
A: B:
.#. ##.
#.# #.#
### ##.
#.# #.#
#.# ##.An input image of height 5, width 6 containing ``AB'':
.#.##.
#.##.#
####.
#.##.#
#.###.The decoder extracts each $3 \times 5$ block, matches against the patterns, and outputs ``AB''.
Notes
The inner loop includes an early termination optimization: if the running distance already exceeds the best so far, we skip the remaining pixels for that pattern.
When an exact match is found ($d = 0$), we immediately stop comparing further patterns.
For larger alphabets, bitmask representations of pixel rows enable faster comparisons using XOR and popcount operations.
Code
C++ solution used for this page.
// IOI 1992 - Problem 2: Teletext
// Pattern matching OCR: decode characters from pixel grid using Hamming distance.
#include <bits/stdc++.h>
using namespace std;
int main() {
int charW, charH, numChars;
scanf("%d%d%d", &charW, &charH, &numChars);
vector<char> charLabel(numChars);
vector<vector<string>> patterns(numChars, vector<string>(charH));
for (int k = 0; k < numChars; k++) {
char label[4];
scanf(" %c", &label[0]);
charLabel[k] = label[0];
for (int r = 0; r < charH; r++) {
char buf[256];
scanf("%s", buf);
patterns[k][r] = buf;
}
}
int imgH, imgW;
scanf("%d%d", &imgH, &imgW);
vector<string> image(imgH);
for (int r = 0; r < imgH; r++) {
char buf[1024];
scanf("%s", buf);
image[r] = buf;
}
int textRows = imgH / charH;
int textCols = imgW / charW;
for (int tr = 0; tr < textRows; tr++) {
for (int tc = 0; tc < textCols; tc++) {
int bestDist = INT_MAX;
char bestChar = '?';
for (int k = 0; k < numChars; k++) {
int dist = 0;
for (int r = 0; r < charH && dist < bestDist; r++) {
for (int c = 0; c < charW; c++) {
int ir = tr * charH + r;
int ic = tc * charW + c;
if (image[ir][ic] != patterns[k][r][c])
dist++;
}
}
if (dist < bestDist) {
bestDist = dist;
bestChar = charLabel[k];
if (dist == 0) break; // exact match
}
}
putchar(bestChar);
}
putchar('\n');
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.