ORB (Oriented FAST and Rotated BRIEF)
ORB, acronyme de Oriented FAST and Rotated BRIEF, est un algorithme de vision par ordinateur utilisé pour la détection et la description de points d’intérêt locaux dans une image. Il combine de manière efficace et rapide les fonctionnalités du détecteur de points d’intérêt FAST (Features from Accelerated Segment Test) et du descripteur binaire BRIEF (Binary Robust Independent Elementary Features), tout en y ajoutant des améliorations clés pour l’invariance à la rotation et une meilleure robustesse aux variations d’échelle et de bruit.
Les concepts fondamentaux d’ORB reposent sur une approche en deux étapes : la détection de points d’intérêt puis leur description. Pour la détection, ORB utilise une version modifiée de FAST, appelée oFAST (Oriented FAST). Le FAST original identifie les coins potentiels en examinant un cercle de pixels autour d’un point candidat et en vérifiant s’il existe un arc de pixels contigus suffisamment plus clairs ou plus sombres que le centre. ORB améliore FAST en lui conférant une invariance à la rotation. Pour ce faire, il calcule l’orientation de chaque point d’intérêt détecté en utilisant le moment d’intensité dans le patch entourant le point. Cette orientation est déterminée par l’angle du vecteur allant du centre du patch à son centroïde d’intensité. De plus, pour gérer les variations d’échelle, ORB applique le détecteur oFAST sur une pyramide d’images (différentes résolutions de l’image originale), permettant ainsi de détecter des points d’intérêt à différentes échelles. Un score (basé sur le score de Harris ou FAST) est utilisé pour sélectionner les points d’intérêt les plus saillants.
Pour la description des points d’intérêt détectés, ORB utilise une version modifiée de BRIEF, appelée rBRIEF (Rotated BRIEF). Le descripteur BRIEF original génère une chaîne binaire (un vecteur de bits) pour chaque point d’intérêt en effectuant une série de comparaisons de luminosité entre des paires de pixels sélectionnées aléatoirement (selon un motif prédéfini) dans le patch entourant le point. Si le premier pixel de la paire est plus lumineux que le second, un ‘1’ est enregistré, sinon un ‘0’. BRIEF est très rapide à calculer et à comparer (en utilisant la distance de Hamming), mais il est très sensible à la rotation de l’image. ORB résout ce problème en utilisant l’orientation calculée par oFAST. Avant de calculer le descripteur BRIEF, le motif des paires de pixels à comparer est tourné en fonction de l’orientation du point d’intérêt. Ainsi, le descripteur rBRIEF devient invariant à la rotation dans le plan de l’image. ORB utilise également un processus d’apprentissage pour sélectionner des paires de pixels qui sont moins corrélées et ont une variance plus élevée, améliorant ainsi la capacité distinctive du descripteur.
L’importance d’ORB réside principalement dans son excellent compromis entre performance (vitesse de calcul et de correspondance), efficacité mémoire (grâce à ses descripteurs binaires compacts) et robustesse (notamment à la rotation et partiellement à l’échelle et aux changements d’illumination). Il s’est imposé comme une alternative très populaire aux algorithmes plus anciens et computationnellement plus coûteux comme SIFT (Scale-Invariant Feature Transform) et SURF (Speeded Up Robust Features), surtout après que ces derniers aient été initialement soumis à des brevets. La disponibilité d’ORB sans restrictions de brevet et son intégration précoce dans des bibliothèques open-source largement utilisées comme OpenCV ont grandement contribué à son adoption massive. Son impact est particulièrement notable dans les applications de vision par ordinateur en temps réel et sur les plateformes aux ressources limitées, telles que les appareils mobiles, les drones et les robots.
Les applications pratiques d’ORB sont nombreuses et variées. Il est couramment utilisé pour la reconnaissance d’objets, où les caractéristiques ORB d’une image sont comparées à celles d’une base de données d’objets connus. Il est également fondamental dans le suivi d’objets (tracking), permettant de suivre le déplacement d’un objet ou de la caméra à travers une séquence vidéo en appariant les points d’intérêt entre les images successives. Une application majeure est la localisation et cartographie simultanées (SLAM), où un robot ou un appareil construit une carte de son environnement tout en estimant sa propre position dans cette carte. Des systèmes SLAM très performants, comme ORB-SLAM et ses variantes (ORB-SLAM2, ORB-SLAM3), reposent entièrement sur l’algorithme ORB pour l’extraction et la correspondance de caractéristiques. D’autres applications incluent l’assemblage de panoramas (stitching), la reconstruction 3D à partir de multiples vues (Structure from Motion – SfM) et la réalité augmentée (AR), où il permet d’ancrer des éléments virtuels de manière stable par rapport à des objets ou des scènes du monde réel. Par exemple, une application AR pourrait utiliser ORB pour reconnaître une affiche et superposer une vidéo ou un modèle 3D dessus.
Bien qu’ORB soit un algorithme bien défini, certaines nuances existent principalement dans son implémentation et son paramétrage. Les développeurs peuvent ajuster plusieurs paramètres, tels que le nombre maximum de points d’intérêt à détecter, le facteur d’échelle entre les niveaux de la pyramide d’images, le seuil de détection FAST, ou la taille du patch utilisé pour le descripteur BRIEF. Ces paramètres influencent directement le compromis entre la vitesse, la densité des points d’intérêt et la qualité de la correspondance. Un nombre plus élevé de points peut améliorer la robustesse mais augmente le temps de calcul. Un facteur d’échelle plus petit dans la pyramide améliore la robustesse à l’échelle mais demande plus de calculs. Il n’existe pas de variations fondamentales majeures de l’algorithme ORB lui-même, mais différentes stratégies peuvent être employées pour la sélection des paires de pixels dans rBRIEF ou pour le filtrage des points d’intérêt. L’implémentation fournie par la bibliothèque OpenCV est souvent considérée comme la référence standard.
Pour une compréhension holistique d’ORB, il est utile de connaître les concepts étroitement liés. Ceux-ci incluent la détection de points d’intérêt (feature detection), la description de caractéristiques (feature description), la correspondance de caractéristiques (feature matching), l’invariance géométrique (rotation, échelle, affine), les descripteurs locaux (local descriptors) et la vision par ordinateur (computer vision). ORB est souvent comparé à d’autres algorithmes de détection et description de points d’intérêt comme SIFT, SURF, AKAZE, BRISK, et FREAK, qui offrent différents compromis entre vitesse, précision et robustesse. FAST et BRIEF sont les composants de base d’ORB. Conceptuellement, ORB s’oppose aux descripteurs globaux (qui décrivent l’image entière, comme GIST ou HOG dans certains contextes) ou aux approches « sans caractéristiques » (featureless ou direct methods) utilisées dans certaines variantes de SLAM qui opèrent directement sur les intensités des pixels plutôt que sur des points d’intérêt détectés.
ORB a été développé par Ethan Rublee, Vincent Rabaud, Kurt Konolige et Gary Bradski au sein du laboratoire de recherche Willow Garage. Il a été présenté en 2011 dans un article intitulé « ORB: An efficient alternative to SIFT or SURF ». L’objectif principal était de créer un algorithme de caractéristiques locales qui soit non seulement très rapide et efficace, mais aussi libre de brevets, contrairement à SIFT et SURF qui étaient alors brevetés et limitaient leur utilisation commerciale. ORB a été conçu pour répondre aux besoins des applications robotiques et de vision par ordinateur en temps réel, qui nécessitent une extraction et une correspondance rapides de caractéristiques sur des plateformes potentiellement limitées en ressources de calcul. Son succès a été rapide, en grande partie grâce à ses performances solides et à son statut open-source, menant à son intégration rapide dans OpenCV et à son utilisation généralisée dans la recherche et l’industrie.
Les avantages d’ORB sont nombreux. Sa rapidité de calcul, tant pour la détection (grâce à FAST) que pour la description (grâce à BRIEF), est un atout majeur. Ses descripteurs binaires sont très compacts, ce qui réduit l’empreinte mémoire et accélère considérablement l’étape de correspondance en utilisant la distance de Hamming (calculable très efficacement via des opérations XOR et de comptage de bits). Le fait qu’il soit libre de droits a été un facteur clé de son adoption. Il offre une bonne invariance à la rotation et une robustesse décente aux variations d’échelle (via la pyramide) et d’illumination modérées. Cependant, ORB présente aussi des limitations. Sa robustesse aux changements d’échelle très importants est généralement inférieure à celle de SIFT. Il peut être plus sensible aux fortes variations d’illumination, aux flous importants et aux changements de point de vue extrêmes que des descripteurs plus complexes. La performance d’ORB peut dépendre de manière significative du choix des paramètres et il peut avoir des difficultés dans les scènes peu texturées où le détecteur FAST peine à trouver suffisamment de coins stables. Malgré ces limitations, ORB reste un outil extrêmement précieux et largement utilisé en vision par ordinateur, représentant un excellent équilibre entre efficacité et performance pour de nombreuses applications.