StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything Models

Each language version is independently generated for its own context, not a direct translation.

🎨 Le Dilemme du Peintre Trop Pressé

Imaginez que SAM (Segment Anything Model) est un peintre génial, capable de dessiner n'importe quel objet sur une photo avec une précision chirurgicale. Il peut isoler un chat, une voiture ou un doigt en un clin d'œil.

Mais il y a un problème : ce peintre est extrêmement lent.
Pour peindre une image, il regarde chaque petit carré de la photo (appelé "token") individuellement. C'est comme si, pour peindre un ciel bleu, il devait vérifier la couleur de chaque grain de sable sur la plage, même là où il n'y a rien d'intéressant. Cela demande une puissance de calcul énorme, ce qui rend l'outil difficile à utiliser sur des téléphones ou des ordinateurs portables.

✂️ L'Idée de Base : "Fusionner les Carrés"

Des chercheurs ont essayé de résoudre ce problème en inventant des techniques pour fusionner les carrés inutiles.
Imaginez que vous avez une mosaïque de 10 000 tuiles. Au lieu de les regarder une par une, vous dites : "Regarde, ces 100 tuiles bleues du ciel sont toutes pareilles. On va les coller ensemble en une seule grande tuile bleue."
Cela réduit le travail de moitié, voire de 90 %. C'est ce qu'on appelle le Token Merging (fusion de jetons).

Le problème : Les méthodes existantes sont un peu "bêtes". Elles fusionnent les tuiles au hasard ou par grappes rigides.

Résultat : Elles collent souvent des tuiles importantes (le bord d'une voiture, un fil électrique fin) avec des tuiles inutiles (le ciel).
Conséquence : Le peintre finit par dessiner des bords flous, des objets déformés ou des détails fins qui disparaissent complètement. C'est comme si on essayait de réduire la taille d'un dessin au trait en écrasant les lignes importantes.

🛡️ La Solution : StructSAM (Le Gardien de la Structure)

Les auteurs de cet article ont créé StructSAM. C'est une méthode intelligente qui ne fusionne pas n'importe quoi, n'importe comment. Voici comment ça marche, avec une analogie simple :

1. Le Détecteur de "Bords" (L'Énergie)

Imaginez que StructSAM a un système de détection de contours comme un radar.

Il regarde l'image et se demande : "Est-ce que cette zone change beaucoup ?"
Si c'est une zone plate (un ciel bleu uni, un mur blanc), le radar dit : "Zone calme ! On peut fusionner tout ça."
Si c'est une zone agitée (le bord d'une feuille, les yeux d'un chat, un fil électrique), le radar crie : "STOP ! Zone critique ! Ne touchez à rien !"

C'est ce qu'ils appellent une "score d'énergie". Plus il y a de changements (de gradients), plus l'énergie est forte, et plus on protège la zone.

2. La Règle du "Chef de Quartier"

Dans les zones calmes (le ciel), StructSAM divise l'image en petits quartiers. Dans chaque quartier, il choisit un seul représentant (le "Chef") pour parler au reste du groupe.

Il choisit le chef le plus "calme" (celui qui ressemble le plus à ses voisins).
Il fusionne tout le quartier autour de ce chef.
Le tour de magie : Une fois le calcul fait, il dé-fusionne tout instantanément pour rendre l'image à sa taille originale, mais avec les informations compressées. C'est comme si vous faisiez un résumé rapide d'un livre, puis que vous réécriviez le livre entier en utilisant ce résumé pour ne rien oublier.

3. Le Respect des "Invités Spéciaux" (Les Prompts)

Parfois, l'utilisateur dit à SAM : "Peintre, concentre-toi sur cette boîte rouge !"
StructSAM est très poli : il sait que si l'utilisateur pointe une zone, c'est que c'est important. Il fusionne donc moins à l'intérieur de la boîte (pour garder les détails) et beaucoup plus à l'extérieur (pour aller vite).

📊 Les Résultats : Plus Rapide, Sans Perte de Qualité

Grâce à cette méthode intelligente :

Vitesse : StructSAM réduit le travail de calcul de 25 % à 40 %. C'est comme passer d'une voiture de sport à une Formule 1 : ça va beaucoup plus vite.
Qualité : Contrairement aux autres méthodes qui floutent les bords, StructSAM garde les contours nets. Les tests montrent qu'il fonctionne aussi bien sur des photos de nature que sur des radiographies médicales (où chaque détail compte pour sauver des vies).

🧠 En Résumé : L'Analogie Finale

Imaginez que vous devez ranger une bibliothèque immense.

Les anciennes méthodes (ToMe, etc.) disent : "Prenez 50 % des livres au hasard et collez-les ensemble." Résultat : vous perdez des romans complets et vous gardez des encyclopédies vides.
StructSAM dit : "Regardez les étagères. Si une étagère contient 100 livres de la même couleur (le ciel), on les remplace par un seul livre récapitulatif. Mais si une étagère contient des livres de couleurs différentes (les bords d'un objet), on les laisse tous intacts."

Le résultat ? Vous avez rangé la bibliothèque deux fois plus vite, mais vous n'avez perdu aucun livre important.

C'est exactement ce que fait StructSAM : il rend l'intelligence artificielle plus rapide et plus économe en énergie, sans sacrifier la précision, en respectant la "structure" naturelle de l'image.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique et Contexte

Le modèle Segment Anything Model (SAM) et ses variantes (comme MedSAM) ont révolutionné la segmentation d'images grâce à leur capacité de généralisation et à leur architecture fondée sur les Transformers (ViT). Cependant, leur déploiement pratique est entravé par un coût computationnel élevé. L'encodeur d'images, qui représente plus de 98 % des paramètres et des opérations (FLOPs), est particulièrement coûteux, surtout pour les grandes variantes (ViT-L, ViT-H).

Bien que des méthodes de compression (distillation, quantification, ré-architecture) existent, elles nécessitent souvent un réentraînement coûteux ou une calibration spécifique, ce qui les rend inapplicables dans des scénarios "off-the-shelf" (prêts à l'emploi) où les données d'entraînement ne sont pas disponibles.

Les techniques de fusion de tokens (token merging) développées pour les ViT standards (comme ToMe) permettent d'accélérer l'inférence en réduisant dynamiquement le nombre de tokens traités par les couches d'attention. Cependant, leur application directe à SAM échoue pour deux raisons principales :

Architecture hybride : L'encodeur de SAM alterne entre attention locale (fenêtrée) et globale, et préserve des détails spatiaux fins cruciaux pour la prédiction des masques.
Nature de la tâche : La segmentation nécessite une sortie dense et structurée. Les heuristiques existantes de sélection de destinations de fusion (aléatoire ou basée sur la similarité globale) tendent à éroder les frontières des objets et à "fuir" les informations des invites (prompts), dégradant rapidement la précision (mIoU/Dice) à mesure que le taux de fusion augmente.

2. Méthodologie : StructSAM

Les auteurs proposent StructSAM, un cadre de fusion-défusion de tokens préservant la structure et le spectre, conçu spécifiquement pour l'architecture de SAM. La méthode opère sans modifier les poids du modèle ni nécessiter de réentraînement.

A. Estimation d'énergie par gradient

Au lieu d'utiliser des graphes complets coûteux, StructSAM calcule un score d'énergie de token léger basé sur les gradients du premier ordre des cartes de caractéristiques de l'encodeur.

Les gradients sont approximatifs via des différences finies ou des opérateurs de Sobel.
Les tokens situés près des frontières d'objets (forts gradients) reçoivent un score d'énergie élevé et sont protégés de la fusion.
Les tokens dans les régions visuellement plates (faibles gradients) sont identifiés comme redondants et fusionnables.

B. Partitionnement en cellules et sélection de zones

Pour assurer une cohérence spatiale et respecter les fenêtres d'attention de SAM :

La grille de tokens est divisée en cellules non chevauchantes ( $s \times s$ ).
Chaque cellule reçoit un score de "platitude" (basé sur le gradient maximal à l'intérieur de la cellule).
Seules les cellules les plus "plates" (faible variation structurelle) sont sélectionnées pour la fusion. Les cellules contenant des frontières restent intactes.

C. Fusion et Défusion explicite (Merge-Unmerge)

Contrairement aux méthodes de classification qui réduisent progressivement le nombre de tokens jusqu'à la fin, StructSAM utilise une interface fusion-calcul-défusion à l'intérieur de chaque bloc d'attention :

Fusion : Dans les cellules sélectionnées, les tokens sources sont moyennés vers un token de destination choisi comme étant le plus stable (celui avec le gradient le plus faible dans la cellule).
Calcul : L'attention (locale ou globale) est calculée sur l'ensemble de tokens réduit.
Défusion (Unmerging) : Immédiatement après l'attention, la résolution originale est restaurée en dupliquant les caractéristiques mises à jour du token de destination vers tous les tokens de la cellule. Cela garantit que le décodeur de masques de SAM reçoit toujours une grille de caractéristiques dense à la résolution originale.

D. Variante sensible aux invites (Prompt-aware)

Lorsque des invites (boîtes, points) sont fournies, la méthode applique un taux de fusion plus agressif dans les zones d'arrière-plan (hors invite) et un taux plus faible (ou nul) à l'intérieur de la région invitée, préservant ainsi les détails critiques pour la tâche.

3. Fondements Théoriques : Analyse Spectrale

Les auteurs offrent une interprétation théorique de leur méthode via la théorie des graphes spectraux.

La fusion de tokens est vue comme un coarsening de graphe (regroupement de nœuds), suivi d'un lifting (remontée) pour restaurer la résolution.
Ils démontrent que leur stratégie guidée par les scores (basée sur les gradients) garantit une distorsion spectrale bornée du Laplacien du graphe sous-jacent.
En revanche, les méthodes baselines (fusion aléatoire ou par fenêtre stricte) peuvent provoquer une dérive spectrale irréductible, expliquant théoriquement pourquoi elles échouent à préserver la structure fine nécessaire à la segmentation dense.

4. Résultats Expérimentaux

Les expériences ont été menées sur une large gamme de benchmarks (naturels et médicaux) avec des modèles SAM (ViT-B, ViT-L) et MedSAM, dans un cadre strict "off-the-shelf" (sans fine-tuning).

Efficacité : StructSAM réduit les FLOPs de l'encodeur de 25 % à 30 % (jusqu'à 40 %+ avec la variante sensible aux invites).
Précision : La méthode maintient une qualité de segmentation quasi-identique à l'original, avec des chutes minimes de mIoU ou de Dice (ex: -0.62 points de Dice sur le dataset INbreast pour MedSAM).
Comparaison : Elle surpasse systématiquement les méthodes de référence (ToMe, PiToMe, ToMeSD, VidToMe, ALGM), en particulier sur les tâches sensibles aux frontières (DIS5K, ThinObject5K) et les images médicales.
- Sur le dataset Cityscapes (taux de fusion 70 %), StructSAM conserve plus de 93 % des performances de la ligne de base pour les grands objets, contre 67-84 % pour les autres méthodes.
- Sur INbreast (mammographie), elle réduit les calculs de 28,5 % avec une perte de précision négligeable, là où les concurrents subissent des baisses de performance significatives.
Coût de calcul : L'estimation du score d'énergie par gradient est très peu coûteuse (réduction de 75 % des FLOPs d'estimation par rapport aux méthodes basées sur des graphes complets comme PiToMe).

5. Contributions Clés et Signification

Première évaluation systématique : Analyse approfondie de l'application du token merging aux modèles de segmentation fondationnels (SAM), révélant les limites des approches existantes pour les tâches denses.
Nouvelle architecture StructSAM : Introduction d'une stratégie de fusion préservant la structure, guidée par les gradients et les cellules, avec un mécanisme de récupération explicite des tokens.
Garantie théorique : Fourniture d'une analyse spectrale prouvant la stabilité de la méthode et expliquant mathématiquement sa supériorité sur les heuristiques aléatoires.
Impact pratique : Permet le déploiement de modèles de segmentation lourds sur des appareils à ressources limitées (médical, robotique, embarqué) sans réentraînement, en réduisant drastiquement le coût d'inférence tout en préservant la précision des frontières.

En résumé, StructSAM comble le fossé entre l'efficacité computationnelle et la précision structurelle requise pour la segmentation d'images, offrant une solution légère et robuste pour accélérer les modèles fondationnels de vision par ordinateur.