Introduction à DETR - Partie 2 : Le rôle crucial de l'algorithme hongrois

Aperçu

Comme nous l'avons vu dans l'article précédent sur DETR, ou Detection Transformer, est un nouveau modèle d'apprentissage profond pour détecter des objets dans des images. C’est un modèle tout-en-un que nous pouvons entraîner de bout en bout. DETR effectue la détection d'objets en le traitant comme un problème de prédiction défini et utilise un transformateur pour traiter les caractéristiques de l'image.

Voici une vue d'ensemble de son fonctionnement : DETR commence avec une base de réseau neuronal convolutionnel (CNN) normale pour extraire les caractéristiques de l'image d'entrée, comme la plupart des modèles de vision. Il aplatit ces caractéristiques, ajoute des informations de position pour indiquer où se trouvent les objets dans l'image et les transmet à un encodeur de transformateur. Après avoir parcouru le transformateur qui permet au modèle de comprendre les relations entre les caractéristiques de l'image, il existe un décodeur de transformateur.

Un décodeur de transformateur prend ensuite en entrée un petit nombre fixe d'intégrations positionnelles apprises, appelées requêtes d'objets - celles-ci l'aident à déterminer quels objets sont présents. Il s'occupe des caractéristiques de l'image codée par l'encodeur pour prédire les emplacements et les classes des objets. En résumé, DETR remplace le pipeline de détection d'objets traditionnel par un transformateur qui prédit directement les objets.

Correspondance bipartite optimale dans DETR : minimiser la perte de prédiction d'ensemble pour la détection d'objets

La perte de prédiction définie est déterminée à l'aide de la méthode de correspondance bipartite, qui aligne les objets prédits avec les objets de vérité terrain. La technique consiste à trouver la meilleure correspondance entre les objets prédits et les objets de vérité terrain en fonction de leur scores de similarité. Pour obtenir les scores de similarité, il examine l'intersection sur union (IoU) des boîtes englobantes prédites et des boîtes de vérité terrain. L’utilisation d’une correspondance bipartite signifie que chaque objet prédit est associé, au maximum, à un objet de vérité terrain, et vice versa.

L’équation de l’appariement bipartite optimal est définie comme :

Le problème d'optimisation représenté par cette équation est utilisé pour trouver la permutation optimale des objets prédits, qui est ensuite utilisée pour produire l'ensemble final de prédictions d'objets.

Il s'agit de minimiser la perte de correspondance totale entre les objets de vérité terrain et les objets prédits, en examinant toutes les permutations possibles des prédictions. Il choisit celle qui entraîne la perte de correspondance totale la plus faible.

Au lieu d'utiliser l'approche normale où nous faisons des propositions de régions puis classifions chaque région, DETR effectue simplement un ensemble de prédictions d'objets en même temps pour l'image entière.

Le rôle de l'algorithme hongrois dans la minimisation des coûts

L'algorithme hongrois est considéré comme une solution très efficace pour résoudre le problème d'affectation, qui consiste à trouver l'affectation optimale d'un ensemble de tâches à un ensemble d'agents avec des coûts donnés.

Cet article sert de guide d’introduction sur le sujet. Il vise à expliquer le fonctionnement de l’algorithme hongrois, tout en explorant les moyens de le mettre en œuvre plus efficacement. Néanmoins, les étapes de calcul de l'algorithme hongrois peuvent être résumées dans le diagramme ci-dessous.

L'organigramme de l'algorithme hongrois commence par la construction d'une matrice de coûts. Chaque élément représente le coût d'affectation d'un travailleur pour accomplir une tâche.

L'algorithme suit la réduction de ligne, où nous soustrayons le plus petit élément de chaque ligne de tous les éléments de cette même ligne.

Nous passons ensuite à la réduction des colonnes et appliquons ce processus de la même manière sur toutes les colonnes. Suite à cette étape, notre prochain objectif est de couvrir tous les zéros de notre matrice avec le nombre minimum de lignes horizontales et verticales.

L'optimalité de la couverture est vérifiée comme suit : si le nombre de lignes est égal à la taille de la matrice, alors une affectation optimale existe ; sinon, des ajustements doivent être apportés à la matrice.

Les ajustements consistent à soustraire de tous les éléments découverts et à les ajouter à tout élément couvert par deux lignes. Ce processus se répète jusqu'à ce qu'il y ait autant de lignes de recouvrement que pour la taille de la matrice. Il est alors possible de déterminer une affectation optimale en utilisant des positions nulles dans la matrice.

L'algorithme hongrois joue un rôle important dans le modèle DETR (DEtection TRansformer). Le modèle DETR considère chaque image comme un ensemble d'objets, et l'algorithme hongrois est utilisé pour associer des prédictions aux objets GT (Ground Truth) correspondants. Visualisons le processus dans le diagramme ci-dessous.

Après avoir traité une image, DETR génère un nombre fixe de prédictions par image. Chaque prédiction comprend une étiquette de classe et un cadre de délimitation. Simultanément, le modèle dispose d'un ensemble d'objets GT pour chaque image, chacun constitué d'une classe et d'un cadre de délimitation.

Pour que l'algorithme hongrois fonctionne efficacement, une matrice de coûts est impérative. Dans DETR, nous élaborons ce schéma crucial en évaluant et en quantifiant chaque prédiction par rapport à son objet de vérité terrain correspondant afin d'établir une estimation précise. 'coût'. Cette valeur sert d'indicateur perspicace de toute incongruence ou écart entre la prédiction et l'objet GT.

Il existe deux facteurs critiques qui contribuent au coût total : "l'erreur de classe" et "l'erreur de boîte englobante". L'erreur de classe est essentiellement la log-vraisemblance négative de l'étiquette GT compte tenu de la classe prédite du modèle. distribution. L’erreur de boîte englobante est la perte L1 entre les coordonnées prédites et GT de la boîte englobante.

En entreprenant une analyse méticuleuse de la matrice des coûts, le modèle DETR utilise l'ingénieux algorithme hongrois avec un savoir-faire précis. Cela lui permet de trouver l’affectation optimale des prédictions qui sont rapidement et précisément mappées sur leurs objets GT respectifs. Cette approche pionnière minimise le coût total tout en optimisant les performances globales pour une efficacité maximale.

Algorithme hongrois et calcul des coûts dans DETR

L'algorithme hongrois est utilisé pour résoudre le problème d'affectation en temps polynomial. Lors de l'évaluation des performances des modèles de détection d'objets, deux paramètres essentiels entrent en jeu__ :__

• L'Erreur de classe, E_c, est calculée à l'aide de la perte d'entropie croisée : E_c=-log(P(Y=y)), où P(Y=y) est la probabilité prédite de la classe GT.
• L'erreur de boîte englobante, E_b, est simplement la perte L1 (somme des différences absolues) entre les coordonnées prédites de la boîte englobante (x_pred, y_pred, w_pred, h_pred) et les coordonnées GT (x_gt, y_gt, w_gt, h_gt) : E_b=|x_pred - x_gt| + |y_pred - y_gt| + |w_pred - w_gt| + |h_pred - h_gt|.

Le coût total, C, est alors une somme pondérée des erreurs de classe et du cadre de délimitation : C=λ*E_c + (1-λ)*E_b, où λ est un paramètre de pondération qui équilibre les contributions des erreurs de classe et de boîte englobante.

Intégrée au DETR, se trouve cette formule qui résume l’essence de l’algorithme hongrois. Le point crucial de cette formule mathématique révolutionnaire consiste à attribuer chaque prédiction à l’objet de vérité terrain correspondant tout en minimisant le coût total.

Cette approche garantit la meilleure correspondance possible entre les prédictions du modèle et les objets réels de l’image. C’est grâce à cette technique que DETR dégage son aptitude exceptionnelle à la détection précise d’objets. Cette capacité avancée est obtenue avec une fluidité transparente grâce à son cadre innovant de bout en bout. DERT supprime les composants personnalisés encombrants que l'on trouve aujourd'hui parmi la plupart des modèles concurrents.

Transformer les matrices de coûts en matrices de profit pour une détection d'objets optimale

La perte hongroise (ou perte de Kuhn-Munkres, comme on l'appelle dans un contexte plus large) permet un algorithme plus précis pour la détection d'objets tel que traité dans le cadre DETR (Detection Transformer). Il est largement reconnu que la vision par ordinateur pose des problèmes lorsque plusieurs objets possèdent des poids ou des tailles similaires.

Pour répondre à cette préoccupation, la perte hongroise implique l'optimisation d'un problème d'affectation au niveau de la solution qui délimite les objets de vérité terrain et les prédictions correspondants. Il est ici de la plus haute importance de transformer deux matrices en une matrice de profit pour permettre une optimisation efficace des prévisions.

La matrice des coûts appartient à une matrice de dimensions p x p, où la quantité désignée par 'p' représente le nombre de ressources attribuées pour réaliser une tâche. Dans notre cas particulier, il s'agit de prédictions et de comparaisons ultérieures avec des objets de vérité terrain. Un coût plus élevé dans ce contexte suggère une moins bonne qualité de correspondance. Aux fins du DETR, les coûts de correspondance par paire entre les boîtes de prédiction désignées par l'image et la vérité terrain sont utilisés pour calculer la matrice des coûts.

L'algorithme de perte hongrois a été initialement développé pour résoudre des problèmes d'affectation dans le but de maximiser le profit. Il est donc nécessaire de convertir la matrice des coûts en matrice des bénéfices. Ce processus de conversion consiste à soustraire chaque élément de la matrice de coûts de sa valeur maximale. En termes mathématiques, cette transformation peut s'exprimer comme suit :

_P\_ij = max(C) - C\_ij_

où P_ij représente l'élément de la matrice de profit, C_ij est l'élément de la matrice de coût et max© est la valeur maximale du coût matrice. Nous pouvons résumer le processus ci-dessous.

Le moteur de cette transformation est le désir de se synchroniser avec la quête de l’algorithme hongrois de maximiser les profits (ou, dans notre cas, de réduire les coûts). En mettant en œuvre une matrice de profit, nous pouvons mesurer et évaluer avec précision la « rentabilité » de chaque mission entre une prédiction et une vérité terrain, enrichissant ainsi les performances prédictives. Ajoutons un exemple pratique à l'organigramme ci-dessus.

Cette transformation améliore la capacité de l'algorithme à optimiser les prédictions par rapport aux objets de vérité terrain, car la conversion en matrice de profit aide le modèle à mieux comprendre les implications de chaque mission. De cette façon, l’algorithme hongrois peut prendre de meilleures décisions en corrélant les prédictions avec la vérité terrain, améliorant ainsi la précision de la détection.

Cas d'utilisation : Optimisation de la recherche d'images de commerce électronique avec DETR

Dans une plateforme de commerce électronique, une détection précise des objets dans les images de produits est primordiale pour optimiser l'expérience utilisateur. Pour garantir une allocation efficace des ressources et une gestion des coûts sur de telles plateformes, il est important de convertir les matrices de coûts en matrices de bénéfices. Le diagramme ci-dessous vise à illustrer les avantages pratiques de la mise en œuvre de l'augmentation des capacités de recherche d'images dans le commerce électronique à l'aide de ces techniques.

Première phase : Construction de la matrice des coûts

Dans la première étape, une matrice de coûts est générée dans laquelle chaque entrée (Cij) représente le coût encouru pour associer l'objet prédit du i-ème indice à celui de la j-ème vérité terrain. Le calcul de ce coût fait intervenir différents facteurs tels que :

• Coût de distance : calcul basé sur la distance euclidienne séparant la boîte englobante prédite de sa boîte englobante de vérité terrain correspondante, en utilisant une approche formelle et professionnelle.
• Coût de forme : écart dans les proportions ou les zones entre les cadres de délimitation prévus et réels détectés.
• Coût de classe : précision de la classification ou score de confiance associé à la classe d'objet identifiée.

Phase deux : Conversion de la matrice des coûts en bénéfices

Pour transformer la matrice de coûts en matrice de profit, il faut effectuer une inversion des valeurs de coûts. Ceci peut être réalisé grâce à la fonction de transformation notée _Pij=M−Cij_, où M représente une constante suffisamment grande garantissant que toutes les valeurs de profit sont positives. Lors de l'application de cette formule, nous obtenons la matrice de profit souhaitée P qui s'aligne sur la maximisation des profits dans des conditions qui donnent la priorité à la minimisation des coûts associés.

Troisième phase : application de l'algorithme de Kuhn-Munkres (hongrois)

À l'aide de la matrice de profit P, nous utilisons l'algorithme de Kuhn-Munkres pour discerner la correspondance optimale entre les entités prédites et celles de la vérité terrain. Cette étape critique garantit que la mission globale maximise le profit total

Phase quatre : intégration avec DETR et formation

• Annotation des données : produisez un ensemble de données de vérité terrain complet en annotant une collection variée d'images de produits avec des cadres de délimitation précis et des étiquettes de classe clairement définies.
• Initialisation du modèle : le processus d'initialisation implique l'intégration du mécanisme de réduction du profit/coût dans la fonction de perte du modèle DETR. Cela nécessite un calcul efficace de la perte de correspondance en mettant en œuvre un processus de correspondance au sein du pipeline de formation.
• Formation : organisez une formation pour le modèle DETR en utilisant la perte correspondante transformée en profit. Cela garantira qu’il adopte une approche optimale pour déterminer les cadres de délimitation et les classes avec des compétences améliorées tout en maximisant la matrice de rentabilité de l’opération. Cela conduira à de meilleures capacités de détection d’objets.

Phase cinq : déploiement et amélioration de l'expérience utilisateur

Une fois sa formation terminée, le modèle est ensuite déployé sur la plateforme e-commerce. Chaque fois qu'un utilisateur fait une demande de recherche d'image, le pipeline procède comme suit :

• Détection d'objets : la fonctionnalité de détection d'objets du modèle DETR applique des techniques de reconnaissance d'objets pour identifier et délimiter les objets présents dans une image de requête donnée. Il identifie avec précision chaque objet détecté en fournissant des étiquettes de classe correspondantes et des cadres de délimitation spécifiant leur emplacement géométrique dans l'image.
• Correspondance de produits : la plateforme utilise un mécanisme de détection d'objets optimal pour la correspondance de produits, où les objets détectés sont croisés avec les données d'inventaire pour récupérer les produits pertinents.
• Afficher les résultats : l'algorithme de recherche présente les produits correspondants à l'utilisateur avec précision, améliorant ainsi la pertinence des résultats et la satisfaction globale de ceux-ci.

Conclusion

L'algorithme hongrois est l'élément d'optimisation qui détermine le meilleur ensemble global de correspondances en fonction des scores de similarité. Il prend le graphe biparti et trouve la configuration idéale des matchs entre les deux camps. Ceci est crucial pour que DETR fonctionne réellement dans la pratique et fasse correspondre les bonnes régions visuelles aux bonnes requêtes textuelles.

La correspondance bipartite donne au DETR un cadre mathématique solide pour connecter le langage et la vision, tandis que l'algorithme hongrois trouve les meilleures correspondances dans ce cadre. Les deux techniques permettent à DETR d’aligner les concepts textuels et visuels de manière optimisée. C’est ce qui rend possible la mise en correspondance multimodale.

Références

Algorithme hongrois : un guide étape par étape de la méthode d'affectation

Le problème d'affectation (en utilisant l'algorithme hongrois)

A. R. Gosthipaty et R. Raha. « DETR Breakdown Part 2 : Introduction to DEtection TRansformers », PyImageSearch, P. Chugh, S. Huot, K. Kidriavsteva et A. Thanki, éd., 2023, https://pyimg.co/slx2k