C'est bon ! J'ai enfin réussi à faire fonctionner quelque chose de façon cohérente ! Ce problème m'a retenu pendant plusieurs jours... C'est amusant ! Désolé pour la longueur de cette réponse, mais j'ai besoin d'élaborer un peu sur certaines choses... (Bien que je puisse établir un record pour la plus longue réponse stackoverflow sans spam jamais !)
En passant, j'utilise l'ensemble complet de données qu'Ivo a fourni un lien vers dans son question initiale . Il s'agit d'une série de fichiers rar (un par chien) contenant chacun plusieurs expériences différentes stockées dans des tableaux ascii. Plutôt que d'essayer de copier-coller des exemples de code autonomes dans cette question, voici un exemple de l'utilisation de ces fichiers. Dépôt mercuriel bitbucket avec un code complet et autonome. Vous pouvez le cloner avec
hg clone [https://joferkington@bitbucket.org/joferkington/paw-analysis](https://joferkington@bitbucket.org/joferkington/paw-analysis)
Vue d'ensemble
Il y a essentiellement deux façons d'aborder le problème, comme vous l'avez noté dans votre question. Je vais en fait utiliser les deux de manière différente.
- Utilisez l'ordre (temporel et spatial) des impacts des pattes pour déterminer quelle patte est la bonne.
- Essayez d'identifier l'"empreinte de patte" en vous basant uniquement sur sa forme.
En gros, la première méthode fonctionne lorsque les pattes du chien suivent le schéma trapézoïdal présenté dans la question d'Ivo ci-dessus, mais échoue lorsque les pattes ne suivent pas ce schéma. Il est assez facile de détecter par programmation les cas où elle ne fonctionne pas.
Par conséquent, nous pouvons utiliser les mesures où il a fonctionné pour construire un ensemble de données d'entraînement (de ~2000 impacts de pattes de ~30 chiens différents) pour reconnaître quelle patte est la bonne, et le problème se réduit à une classification supervisée (avec quelques rides supplémentaires...). La reconnaissance d'images est un peu plus difficile qu'un problème "normal" de classification supervisée).
Analyse des modèles
Pour développer la première méthode, lorsqu'un chien marche (et non court !) normalement (ce qui n'est pas toujours le cas pour certains de ces chiens), nous nous attendons à ce que les pattes se heurtent dans l'ordre suivant : Avant gauche, Arrière droite, Avant droite, Arrière gauche, Avant gauche, etc. Le schéma peut commencer par la patte avant gauche ou avant droite.
Si c'était toujours le cas, nous pourrions simplement trier les impacts par temps de contact initial et utiliser un modulo 4 pour les regrouper par patte.
![Normal Impact Sequence]()
Cependant, même lorsque tout est "normal", cela ne fonctionne pas. Cela est dû à la forme trapézoïdale du motif. Une patte arrière tombe spatialement derrière la patte avant précédente.
Par conséquent, l'impact de la patte arrière après l'impact initial de la patte avant tombe souvent de la plaque du capteur et n'est pas enregistré. De même, l'impact de la dernière patte n'est souvent pas la patte suivante dans la séquence, car l'impact de la patte précédente est sorti de la plaque du capteur et n'a pas été enregistré.
![Missed Hind Paw]()
Néanmoins, nous pouvons utiliser la forme du modèle d'impact de la patte pour déterminer quand cela s'est produit, et si nous avons commencé avec une patte avant gauche ou droite. (En fait, j'ignore les problèmes liés au dernier impact ici. Il n'est pas trop difficile de l'ajouter, cependant).
def group_paws(data_slices, time):
# Sort slices by initial contact time
data_slices.sort(key=lambda s: s[-1].start)
# Get the centroid for each paw impact...
paw_coords = []
for x,y,z in data_slices:
paw_coords.append([(item.stop + item.start) / 2.0 for item in (x,y)])
paw_coords = np.array(paw_coords)
# Make a vector between each sucessive impact...
dx, dy = np.diff(paw_coords, axis=0).T
#-- Group paws -------------------------------------------
paw_code = {0:'LF', 1:'RH', 2:'RF', 3:'LH'}
paw_number = np.arange(len(paw_coords))
# Did we miss the hind paw impact after the first
# front paw impact? If so, first dx will be positive...
if dx[0] > 0:
paw_number[1:] += 1
# Are we starting with the left or right front paw...
# We assume we're starting with the left, and check dy[0].
# If dy[0] > 0 (i.e. the next paw impacts to the left), then
# it's actually the right front paw, instead of the left.
if dy[0] > 0: # Right front paw impact...
paw_number += 2
# Now we can determine the paw with a simple modulo 4..
paw_codes = paw_number % 4
paw_labels = [paw_code[code] for code in paw_codes]
return paw_labels
Malgré tout cela, il arrive fréquemment qu'il ne fonctionne pas correctement. De nombreux chiens de l'ensemble des données semblent courir, et les impacts de pattes ne suivent pas le même ordre temporel que lorsque le chien marche. (Ou peut-être que le chien a simplement de graves problèmes de hanches...)
![Abnormal Impact Sequence]()
Heureusement, nous pouvons toujours détecter de manière programmatique si les impacts des pattes suivent ou non le modèle spatial attendu :
def paw_pattern_problems(paw_labels, dx, dy):
"""Check whether or not the label sequence "paw_labels" conforms to our
expected spatial pattern of paw impacts. "paw_labels" should be a sequence
of the strings: "LH", "RH", "LF", "RF" corresponding to the different paws"""
# Check for problems... (This could be written a _lot_ more cleanly...)
problems = False
last = paw_labels[0]
for paw, dy, dx in zip(paw_labels[1:], dy, dx):
# Going from a left paw to a right, dy should be negative
if last.startswith('L') and paw.startswith('R') and (dy > 0):
problems = True
break
# Going from a right paw to a left, dy should be positive
if last.startswith('R') and paw.startswith('L') and (dy < 0):
problems = True
break
# Going from a front paw to a hind paw, dx should be negative
if last.endswith('F') and paw.endswith('H') and (dx > 0):
problems = True
break
# Going from a hind paw to a front paw, dx should be positive
if last.endswith('H') and paw.endswith('F') and (dx < 0):
problems = True
break
last = paw
return problems
Par conséquent, même si la simple classification spatiale ne fonctionne pas tout le temps, nous pouvons déterminer quand elle fonctionne avec une confiance raisonnable.
Ensemble de données de formation
À partir des classifications basées sur des motifs où il a fonctionné correctement, nous pouvons constituer un très grand ensemble de données d'entraînement de pattes correctement classées (~2400 impacts de pattes de 32 chiens différents !).
Nous pouvons maintenant commencer à examiner à quoi ressemble une patte avant gauche, etc. "moyenne".
Pour ce faire, nous avons besoin d'une sorte de "métrique de la patte" qui a la même dimensionnalité pour tous les chiens. (Dans l'ensemble de données complet, il y a à la fois des chiens très grands et très petits !) L'empreinte de la patte d'un elkhound irlandais sera à la fois beaucoup plus large et beaucoup plus "lourde" que l'empreinte de la patte d'un caniche jouet. Nous devons redimensionner chaque empreinte de patte de façon à ce que a) elles aient le même nombre de pixels, et b) les valeurs de pression soient normalisées. Pour ce faire, j'ai rééchantillonné chaque empreinte de patte sur une grille de 20x20 et j'ai redimensionné les valeurs de pression sur la base de la valeur de pression maximale, minimale et moyenne pour l'impact de la patte.
def paw_image(paw):
from scipy.ndimage import map_coordinates
ny, nx = paw.shape
# Trim off any "blank" edges around the paw...
mask = paw > 0.01 * paw.max()
y, x = np.mgrid[:ny, :nx]
ymin, ymax = y[mask].min(), y[mask].max()
xmin, xmax = x[mask].min(), x[mask].max()
# Make a 20x20 grid to resample the paw pressure values onto
numx, numy = 20, 20
xi = np.linspace(xmin, xmax, numx)
yi = np.linspace(ymin, ymax, numy)
xi, yi = np.meshgrid(xi, yi)
# Resample the values onto the 20x20 grid
coords = np.vstack([yi.flatten(), xi.flatten()])
zi = map_coordinates(paw, coords)
zi = zi.reshape((numy, numx))
# Rescale the pressure values
zi -= zi.min()
zi /= zi.max()
zi -= zi.mean() #<- Helps distinguish front from hind paws...
return zi
Après tout cela, nous pouvons enfin voir à quoi ressemble une patte moyenne avant gauche, arrière droite, etc. Notez qu'il s'agit d'une moyenne sur plus de 30 chiens de tailles très différentes, et nous semblons obtenir des résultats cohérents !
![Average Paws]()
Toutefois, avant d'effectuer une quelconque analyse sur ces derniers, nous devons soustraire la moyenne (la patte moyenne de toutes les pattes de tous les chiens).
![Mean Paw]()
Nous pouvons maintenant analyser les différences par rapport à la moyenne, qui sont un peu plus faciles à reconnaître :
![Differential Paws]()
Reconnaissance de pattes basée sur l'image
Ok... Nous avons enfin un ensemble de modèles avec lesquels nous pouvons commencer à essayer de faire correspondre les pattes. Chaque patte peut être traitée comme un vecteur à 400 dimensions (retourné par la fonction paw_image ) qui peuvent être comparés à ces quatre vecteurs à 400 dimensions.
Malheureusement, si nous utilisons simplement un algorithme de classification supervisée "normal" (c'est-à-dire trouver lequel des 4 motifs est le plus proche d'une empreinte de patte particulière en utilisant une simple distance), cela ne fonctionne pas de manière cohérente. En fait, il ne fait pas beaucoup mieux que le hasard sur l'ensemble de données d'entraînement.
C'est un problème courant dans la reconnaissance d'images. En raison de la forte dimensionnalité des données d'entrée et de la nature quelque peu "floue" des images (c'est-à-dire que les pixels adjacents ont une covariance élevée), le simple fait de regarder la différence entre une image et une image modèle ne donne pas une très bonne mesure de la similarité de leurs formes.
Eigenpaws
Pour contourner ce problème, nous devons construire un ensemble de "pattes propres" (tout comme les "visages propres" dans la reconnaissance faciale) et décrire chaque empreinte de patte comme une combinaison de ces pattes propres. Cette méthode est identique à l'analyse en composantes principales et fournit essentiellement un moyen de réduire la dimensionnalité de nos données, de sorte que la distance soit une bonne mesure de la forme.
Comme nous avons plus d'images d'entraînement que de dimensions (2400 contre 400), il n'est pas nécessaire de faire de l'algèbre linéaire "fantaisiste" pour la vitesse. Nous pouvons travailler directement avec la matrice de covariance de l'ensemble des données d'apprentissage :
def make_eigenpaws(paw_data):
"""Creates a set of eigenpaws based on paw_data.
paw_data is a numdata by numdimensions matrix of all of the observations."""
average_paw = paw_data.mean(axis=0)
paw_data -= average_paw
# Determine the eigenvectors of the covariance matrix of the data
cov = np.cov(paw_data.T)
eigvals, eigvecs = np.linalg.eig(cov)
# Sort the eigenvectors by ascending eigenvalue (largest is last)
eig_idx = np.argsort(eigvals)
sorted_eigvecs = eigvecs[:,eig_idx]
sorted_eigvals = eigvals[:,eig_idx]
# Now choose a cutoff number of eigenvectors to use
# (50 seems to work well, but it's arbirtrary...
num_basis_vecs = 50
basis_vecs = sorted_eigvecs[:,-num_basis_vecs:]
return basis_vecs
Ces basis_vecs sont les "pattes propres".
![Eigenpaws]()
Pour les utiliser, il suffit de faire un point (c'est-à-dire une multiplication matricielle) entre chaque image de patte (en tant que vecteur à 400 dimensions, plutôt qu'une image 20x20) et les vecteurs de base. Cela nous donne un vecteur à 50 dimensions (un élément par vecteur de base) que nous pouvons utiliser pour classer l'image. Au lieu de comparer une image 20x20 à l'image 20x20 de chaque patte "modèle", nous comparons l'image transformée à 50 dimensions à chaque patte modèle transformée à 50 dimensions. Cette méthode est beaucoup moins sensible aux petites variations dans la façon exacte dont chaque orteil est positionné, etc., et réduit essentiellement la dimensionnalité du problème aux seules dimensions pertinentes.
Classification des pattes basée sur les pattes propres
Maintenant, nous pouvons simplement utiliser la distance entre les vecteurs à 50 dimensions et les vecteurs "modèles" pour chaque patte pour classer quelle patte est la bonne :
codebook = np.load('codebook.npy') # Template vectors for each paw
average_paw = np.load('average_paw.npy')
basis_stds = np.load('basis_stds.npy') # Needed to "whiten" the dataset...
basis_vecs = np.load('basis_vecs.npy')
paw_code = {0:'LF', 1:'RH', 2:'RF', 3:'LH'}
def classify(paw):
paw = paw.flatten()
paw -= average_paw
scores = paw.dot(basis_vecs) / basis_stds
diff = codebook - scores
diff *= diff
diff = np.sqrt(diff.sum(axis=1))
return paw_code[diff.argmin()]
Voici quelques-uns des résultats : ![alt text]()
![alt text]()
![alt text]()
Problèmes restants
Il y a encore quelques problèmes, notamment avec les chiens trop petits pour que l'empreinte de la patte soit nette... (Il fonctionne mieux avec les grands chiens, car les orteils sont plus clairement séparés à la résolution du capteur). En outre, les empreintes partielles ne sont pas reconnues avec ce système, alors qu'elles peuvent l'être avec le système basé sur le motif trapézoïdal.
Cependant, comme l'analyse des pattes propres utilise intrinsèquement une métrique de distance, nous pouvons classer les pattes dans les deux sens, et revenir au système basé sur le motif trapézoïdal lorsque la plus petite distance de l'analyse des pattes propres par rapport au "livre de codes" dépasse un certain seuil. Je n'ai pas encore implémenté cette méthode, cependant.
Ouf... C'était long ! Je tire mon chapeau à Ivo pour avoir posé une question aussi amusante !
