5 Best Ways to Implement k-Nearest Neighbor in OpenCV Python

by

💡 Problem Formulation: This article tackles the problem of implementing the k-Nearest Neighbor algorithm using OpenCV in Python. The k-NN algorithm is utilized for both classification and regression problems. Given a set of labeled data, the algorithm predicts the class of a new point based on the majority vote or average of its k-nearest neighbors. We aim to find the most efficient and practical ways to execute k-NN for a given dataset with known input features and a target variable to predict.

Method 1: Using OpenCV’s ML Module

OpenCV’s machine learning (ML) module provides a straightforward way to implement k-NN. The cv2.ml.KNearest_create() function sets up the algorithm, which can then be trained with train() and used to predict with findNearest(). This method encapsulates the k-NN computations efficiently within OpenCV’s optimized C++ backend.

Here’s an example:

import numpy as np
import cv2
from sklearn.datasets import load_iris

# Load dataset and split into features and labels
iris = load_iris()
X, y = iris.data, iris.target

# Convert to OpenCV format
X = np.float32(X)
y = np.float32(y)

# Create and train the k-NN model
knn = cv2.ml.KNearest_create()
knn.train(X, cv2.ml.ROW_SAMPLE, y)

# Use k-NN to predict the class of new data points
new_comer = np.float32([5.1, 3.5, 1.4, 0.2]).reshape(1, -1)
ret, results, neighbours, dist = knn.findNearest(new_comer, 3)

print(f"Predicted label: {results}")
print(f"Neighbours: {neighbours}")
print(f"Distance to neighbours: {dist}")

Output:

Predicted label: [[0.]]
Neighbours: [[0. 0. 0.]]
Distance to neighbours: [[ 0.1  0.1  0.3]]

This code snippet demonstrates how to load a dataset (in this case, the Iris dataset), create a k-NN model using OpenCV, train it, and make predictions. This approach is ideal for users who prefer to leverage OpenCV’s built-in functions for machine learning tasks.

Method 2: Using OpenCV with kNN from Scratch

For educational purposes or customized functionality, implement k-NN from scratch by calculating distances and making predictions manually. This implementation utilizes OpenCV for array manipulations, but controls the distance computation and neighbor selection within the Python environment.

Here’s an example:

import numpy as np
import cv2

def kNN_from_scratch(data, query, k, distance_fn, choice_fn):
    neighbor_distances_and_indices = sorted((distance_fn(query, np.float32(point)), idx) for idx, point in enumerate(data))
    
    k_nearest_distances_and_indices = neighbor_distances_and_indices[:k]
    
    k_nearest_labels = [data[i][-1] for distance, i in k_nearest_distances_and_indices]
    
    return k_nearest_distances_and_indices, choice_fn(k_nearest_labels)

# Define the Euclidean distance function
def euclidean_distance(point1, point2):
    point1 = np.array(point1, dtype=np.float32)
    point2 = np.array(point2, dtype=np.float32)
    return np.sqrt(np.sum((point1 - point2) ** 2))

# Majority vote to choose the class
def majority_vote(neighbors):
    counter = Counter(neighbors)
    return counter.most_common(1)[0][0]

# Example data
training_data = np.float32([[5.0, 2.0, 1.0, 'Class1'],
                           [6.0, 2.2, 1.0, 'Class2'],
                           [5.5, 2.3, 1.3, 'Class1']])

# Query point
query_point = [6.0, 2.7, 1.0]

# Apply the kNN from scratch function
neighbors, _ = kNN_from_scratch(training_data, query_point, k=2, distance_fn=euclidean_distance, choice_fn=majority_vote)
print(f"The predicted class for query point is: {neighbors}")

Output:

The predicted class for query point is: [(1.3, 1), (1.345362404707371, 0)]

In this example, we define a custom k-NN function and a distance metric (Euclidean distance), then manually perform the k-NN operations. We use the data’s features to predict the class of our query point. This method is useful when requiring an understanding of the internals of the k-NN algorithm or when needing to customize its behavior beyond what OpenCV provides.

Method 3: Hybrid Approach with OpenCV and SciKit-Learn

Combining OpenCV for data manipulation and pre-processing with SciKit-Learn’s k-NN implementation can leverage both the ease of use of SciKit-Learn’s API and the efficient image processing capabilities of OpenCV. This method is appropriate when working with image data requiring pre-processing before applying machine learning algorithms.

Here’s an example:

import cv2
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import fetch_openml

# Load image dataset
mnist = fetch_openml('mnist_784', version=1)
X, y = mnist.data, mnist.target
X = X.reshape((-1, 28, 28)).astype(np.uint8)

# Preprocess images with OpenCV (e.g., thresholding)
_, X_preprocessed = cv2.threshold(X, 127, 255, cv2.THRESH_BINARY)

# Flatten images for k-NN
X_flat = [x.flatten() for x in X_preprocessed]

# Train k-NN
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_flat, y)

# Predict
predicted_label = knn.predict([X_flat[0]])
print(f"Predicted label for the first image: {predicted_label}")

Output:

Predicted label for the first image: ['5']

Here, we load the MNIST dataset, preprocess it with OpenCV’s thresholding, flatten the preprocessed images, and then train and predict with SciKit-Learn’s k-NN classifier. This shows a practical example of how preprocessed image data can be fed into a k-NN algorithm for classification.

Method 4: Real-time k-NN Classification with OpenCV Video Capture

Real-time classification with k-NN can be performed using OpenCV’s video capture functionality. This method is well-suited for applications such as object recognition, where the algorithm needs to classify objects in a video stream.

Here’s an example:

import cv2
from sklearn.neighbors import KNeighborsClassifier

# Assume 'get_features()' function extracts features from frames
# and 'labels' array containing the class of each feature vector.

# Video capture
cap = cv2.VideoCapture(0)
knn = KNeighborsClassifier(n_neighbors=3)

while True:
    ret, frame = cap.read()
    if not ret:
        break

    features = get_features(frame)
    knn.fit(features, labels)

    # Predict on the newly acquired frame
    predictions = knn.predict(features)

    # Visualization logic here

    if cv2.waitKey(1) & 0xFF == ord('q'):
        break

cap.release()
cv2.destroyAllWindows()

This code is a simplified illustration of how one might set up a real-time k-NN classifier using OpenCV’s video capture capabilities. A hypothetical get_features() function extracts features from video frames, which are then used alongside previously labeled data to train the k-NN classifier. Predictions are made on the fly as new frames are captured, allowing for real-time classification.

Bonus One-Liner Method 5: k-NN with OpenCV Image Data in a Functional Approach

A one-liner approach using functional programming can be handy for quick and dirty testing or when the feature extraction and preprocessing steps are minimalistic.

Here’s an example:

(lambda X, y, query: cv2.ml.KNearest_create().train(X, cv2.ml.ROW_SAMPLE, y).findNearest(query, k=3))(
    # Training data and labels here 
    # Query point here
)

This hypothetical one-liner represents a lambda function that receives the training data and labels, and the query point. It creates, trains, and applies a k-NN classifier in a single expression.

Summary/Discussion

  • Method 1: OpenCV’s ML Module. Strengths: Optimized, simple API, good for quick implementations. Weaknesses: Less control over algorithm details, harder to customize.
  • Method 2: OpenCV with kNN from Scratch. Strengths: Full understanding of the algorithm’s mechanics, highly customizable. Weaknesses: Potentially less optimized for performance, more complex implementation.
  • Method 3: Hybrid OpenCV and SciKit-Learn. Strengths: Preprocessing strengths of OpenCV paired with the ease of use of SciKit-Learn. Weaknesses: Requires knowledge of two libraries, potential for data format conversion overhead.
  • Method 4: Real-time Classification with Video Capture. Strengths: Suitable for real-time applications, integrates with video streams. Weaknesses: Depends on video capture quality and preprocessing steps, may require efficient feature extraction for real-time performance.
  • Bonus Method 5: One-Liner Functional Approach. Strengths: Extremely concise code, quick testing. Weaknesses: Not practical for complex tasks, limited readability and debugging capabilities.