KNN (K plus proches voisins)

L'algorithme KNN est une méthode d'apprentissage supervisé simple qui peut être utilisée pour la classification de données. Dans le contexte de la reconnaissance de CAPTCHA, il permet d'identifier les caractères présents dans une image après un prétraitement approprié.

Paramètres de l'implémentation sklearnLa classe KNeighborsClassifier de sklearn possède plusieurs paramètres de configuration :

• n_neighbors : Le nombre de voisins à considérer pour la classification
• weights : Méthode de pondération des voisins ('uniform' ou 'distance')
• algorithm : Algorithme sous-jacent ('auto', 'ball_tree', 'kd_tree', 'brute')
• leaf_size : Taille des feuilles pour les arbres de recherche
• p : Paramètre pour la métrique de distance (1 pour Manhattan, 2 pour Euclidienne)
• metric : Métrique de distance à utiliser
• metric_params : Paramètres supplémentaires pour la métrique
• n_jobs : Nombre de processeurs parallèles à utiliser

Pour la reconnaissance de CAPTCHA numériques, seul le paramètre n_neighbors est généralement pertinent.

Méthodes principales

• fit(X, y) : Entraîne le modèle avec les données X et les étiquettes y
• predict(X) : Prédit les étiuqettes pour les nouvelles données X
• predict_proba(X) : Retourne les probabilités de chaque classe pour les données X
• score(X, y) : Calcule la précision du modèle sur les données X avec les étiquettes y
• kneighbors(X) : Retourne les k plus proches voisins et leurs distances pour les données X

Prétraitement des images

Pour reconnaître des caractères dans une image CAPTCHA, plusieurs étapes de prétraitement sont nécessaires.

Téléchargement des CAPTCHA

Les images CAPTCHA peuvent être obtenues via diverses API. Une approche courante consiste à:

1. Envoyer une première requête pour obtenir un cookie de session
2. Utiliser ce cookie dans une deuxième requête pour récupérer l'image CAPTCHA

Opérations de base

Le prétraitement commence par convertir l'image en niveaux de gris et la binariser:

from PIL import Image
import numpy as np

# Ouverture de l'image
image = Image.open('captcha.png')
image_gris = image.convert('L')  # Conversion en niveaux de gris
pixels = np.array(image_gris)

# Binarisation avec un seuil
seuil = 180
pixels_binaires = (pixels < seuil) * 255

# Suppression des bords
pixels_sans_bord = pixels_binaires[1:-1, 1:-1]

Réduction du bruit

Après binarisation, des points de bruit peuvent subsister. Une méthode simple consiste à éliminer les pixels isolés:

hauteur, largeur = pixels_sans_bord.shape

for i in range(1, hauteur-1):
    for j in range(1, largeur-1):
        if pixels_sans_bord[i, j] == 0:  # Si c'est un pixel noir
            # Compter les pixels noirs dans le voisinage 3x3
            voisinage = pixels_sans_bord[i-1:i+2, j-1:j+2]
            pixels_noirs = np.sum(voisinage == 0)
            
            # Si le pixel est isolé, le convertir en blanc
            if pixels_noirs < 2:
                pixels_sans_bord[i, j] = 255

Segmentation des caractères

La segmentation consiste à diviser l'image en plusieurs images contenant un seul caractère. Pour les CAPTCHA simples, une approche par tranchage horizontal peut être efficace:

# Définition des positions de coupe approximatives
positions_coupe = [3, 13, 23, 33]

# Extraction de chaque caractère
caracteres = []
for i in range(len(positions_coupe)-1):
    debut = positions_coupe[i]
    fin = positions_coupe[i+1]
    caractere = pixels_sans_bord[:, debut:fin]
    
    # Redimensionnement si nécessaire
    if caractere.shape[1] < 10:
        padding = np.zeros((caractere.shape[0], 10-caractere.shape[1]))
        caractere = np.hstack((caractere, padding))
    
    caracteres.append(caractere)

Annotation manuelle

Chaque caractère extrait doit être étiqueté avec la valeur correspondante. Cette étape est fastidieuse mais nécessaire pour l'entraînement du modèle.

Création du modèle

Deux approches peuvent être utilisées pour extraire les caractéristiques des images de caractères:

Approche 1: Utliisation de tous les pixels

from sklearn.neighbors import KNeighborsClassifier
import os
import numpy as np

# Chargement des données d'entraînement
donnees_X = []
etiquettes_y = []

for etiquette in os.listdir('donnees_entrainement'):
    for fichier in os.listdir(f'donnees_entrainement/{etiquette}'):
        # Lecture de l'image
        image = Image.open(f'donnees_entrainement/{etiquette}/{fichier}')
        pixels = np.array(image)
        
        # Binarisation et aplatissement
        pixels_binaires = (pixels > 180) * 1
        caracteristiques = pixels_binaires.ravel()
        
        donnees_X.append(caracteristiques)
        etiquettes_y.append(int(etiquette))

# Entraînement du modèle
X_entrainement = np.array(donnees_X)
y_entrainement = np.array(etiquettes_y)

modele_knn = KNeighborsClassifier(n_neighbors=10)
modele_knn.fit(X_entrainement, y_entrainement)

Approche 2: Caractéristiques par sommes de lignes et colonnes

Cette méthode réduit le nombre de caractéristiques tout en conservant l'essentiel de l'information:

# Chargement des données avec caractéristiques réduites
donnees_X = []
etiquettes_y = []

for etiquette in os.listdir('donnees_entrainement'):
    for fichier in os.listdir(f'donnees_entrainement/{etiquette}'):
        # Lecture de l'image
        image = Image.open(f'donnees_entrainement/{etiquette}/{fichier}')
        pixels = np.array(image)
        pixels_binaires = (pixels > 180) * 1
        
        # Extraction des caractéristiques
        caracteristiques = []
        
        # Sommes des pixels noirs par ligne
        for i in range(pixels_binaires.shape[0]):
            caracteristiques.append(np.sum(pixels_binaires[i] == 0))
        
        # Sommes des pixels noirs par colonne
        for j in range(pixels_binaires.shape[1]):
            caracteristiques.append(np.sum(pixels_binaires[:, j] == 0))
        
        donnees_X.append(caracteristiques)
        etiquettes_y.append(int(etiquette))

# Entraînement du modèle
X_entrainement = np.array(donnees_X)
y_entrainement = np.array(etiquettes_y)

modele_knn = KNeighborsClassifier(n_neighbors=10)
modele_knn.fit(X_entrainement, y_entrainement)

Analyse des performances

Une analyse de l'impact du nombre d'échantillons par classe et de la valeur de k a montré que:

• Pour ce type de CAPTCHA simple, seulement 6 échantillons par classe suffisent pour atteindre 100% de précision
• La valeur de k n'affecte pas significativement les résultats dans ce cas précis

Ces résultats s'expliquent par la simplicité des caractères et la faible variabilité des images. Pour des CAPTCHA plus complexes, des approches plus avancées comme les réseaux de neurones convolutionnels (CNN) seraient plus appropriées.