This system is designed to recognize digits from 0 to 9. The input images are pre-processed to a uniform size of 32x32 pixels in black and white. For clarity, images are stored in a text format, despite not being memory efficient.

Data Collection: Text File Format

The dataset is adapted from the "Optical Recognition of Handwritten Digits" dataset available in the UCI Machine Learning Repository.

Data Preparation: Converting Images to Feature Vectors

The trainingDigits directory contains approximately 2000 examples, with about 200 samples per digit. The testDigits directory holds around 900 test samples, with no overlap between the two sets.

A 32x32 binary image matrix is converted into a 1x1024 vector. The function image_to_vector reads a file, processes 32 lines, and stores each character as an integer in a NumPy array.

import numpy as np
from os import listdir
import operator

def k_nearest_predict(input_vector, feature_matrix, label_vector, k):
    # Calculate Euclidean distances
    num_samples = feature_matrix.shape[0]
    diff_matrix = np.tile(input_vector, (num_samples, 1)) - feature_matrix
    squared_diff = diff_matrix ** 2
    squared_dist = squared_diff.sum(axis=1)
    distances = squared_dist ** 0.5
    
    # Get indices of k smallest distances
    sorted_indices = distances.argsort()
    
    # Tally votes from k nearest neighbors
    vote_count = {}
    for i in range(k):
        current_label = label_vector[sorted_indices[i]]
        vote_count[current_label] = vote_count.get(current_label, 0) + 1
    
    # Return the label with the highest vote count
    sorted_votes = sorted(vote_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_votes[0][0]

def image_to_vector(filepath):
    feature_vector = np.zeros((1, 1024))
    with open(filepath, 'r') as file:
        for row in range(32):
            line = file.readline()
            for col in range(32):
                feature_vector[0, 32 * row + col] = int(line[col])
    return feature_vector

Test the conversion function in a Python interpreter:

>>> import digit_knn
>>> test_vec = digit_knn.image_to_vector('digits/testDigits/0_13.txt')
>>> test_vec[0, 0:31]
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  1.,  1.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.,  0.])
>>> test_vec[0, 32:63]
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,
        1.,  1.,  1.,  1.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.,  0.])

Algorithm Testing: Digit Recognition with KNN

The test_recognition_system function evaluates the classifier. Ensure from os import listdir is included.

def test_recognition_system():
    true_labels = []
    train_files = listdir('./digits/trainingDigits/')
    num_train = len(train_files)
    train_matrix = np.zeros((num_train, 1024))
    
    # Load and vectorize training data
    for idx in range(num_train):
        filename = train_files[idx]
        digit_label = int(filename.split('_')[0])
        true_labels.append(digit_label)
        train_matrix[idx, :] = image_to_vector(f'./digits/trainingDigits/{filename}')
    
    # Test the classifier
    test_files = listdir('./digits/testDigits/')
    error_total = 0.0
    num_test = len(test_files)
    
    for idx in range(num_test):
        filename = test_files[idx]
        actual_digit = int(filename.split('_')[0])
        test_vector = image_to_vector(f'./digits/testDigits/{filename}')
        predicted_digit = k_nearest_predict(test_vector, train_matrix, true_labels, 3)
        
        print(f'Classifier prediction: {predicted_digit}, Actual digit: {actual_digit}')
        if predicted_digit != actual_digit:
            error_total += 1.0
    
    print(f'\nTotal errors: {int(error_total)}')
    print(f'Error rate: {error_total / float(num_test)}')

The function loads training files from ./digits/trainingDigits/, parses the digit label from the filename (e.g., 9_45.txt represents digit 9, instance 45), and stores the vectorized data. It then processes each file in ./digits/testDigits/, using the k_nearest_predict funcsion for classification. Since pixel values are already 0 or 1, normalization is not required.

Execute the test:

>>> digit_knn.test_recognition_system()
Classifier prediction: 0, Actual digit: 0
Classifier prediction: 0, Actual digit: 0
... (output continues for all test files)
Classifier prediction: 9, Actual digit: 9

Total errors: 11
Error rate: 0.011628

The KNN classifier achieves an error rate of approximate 1.2% on this dataset. The performance can be influenced by adjusting the parameter k, modifying the training sample selection, or changing the number of training examples.