Article : écoulements tourbillonnants, méthodes optiques. Ce que vous vouliez savoir sur le flux optique, mais que vous étiez gêné de demander. Méthodes de détermination du flux optique

Dans les systèmes de vision par ordinateur et de traitement d'images, la tâche de déterminer les mouvements d'objets dans un espace tridimensionnel à l'aide d'un capteur optique, c'est-à-dire une caméra vidéo, se pose souvent. Ayant une séquence d'images en entrée, il est nécessaire de recréer l'espace tridimensionnel capturé sur celles-ci et les changements qui s'y produisent au fil du temps. Cela semble compliqué, mais en pratique, il suffit souvent de trouver les déplacements de projections bidimensionnelles d'objets dans le plan du cadre.

Si nous voulons savoir à quel point tel ou tel objet s'est déplacé par rapport à sa position sur l'image précédente pendant le temps qui s'est écoulé entre les images de fixation, alors très probablement, tout d'abord, nous nous souviendrons du flux optique. Pour trouver le flux optique, vous pouvez utiliser en toute sécurité une implémentation prête à l'emploi, testée et optimisée de l'un des algorithmes, par exemple de la bibliothèque OpenCV. En même temps, cependant, il est très inoffensif de comprendre la théorie, c'est pourquoi j'invite toutes les personnes intéressées à examiner l'une des méthodes populaires et bien étudiées. Cet article ne contient ni code ni conseils pratiques, mais il existe des formules et un certain nombre de dérivations mathématiques.

Il existe plusieurs approches pour déterminer les décalages entre deux images adjacentes. Par exemple, pour chaque petit fragment (disons 8 x 8 pixels) d'une image, vous pouvez trouver le fragment le plus similaire dans l'image suivante. Dans ce cas, la différence entre les coordonnées des fragments originaux et trouvés nous donnera un déplacement. La principale difficulté ici est de savoir comment trouver rapidement le fragment souhaité sans parcourir l'intégralité du cadre pixel par pixel. Diverses implémentations de cette approche résolvent le problème de la complexité informatique d’une manière ou d’une autre. Certains connaissent un tel succès qu’ils sont utilisés, par exemple, dans les normes courantes de compression vidéo. Le prix de la rapidité est bien entendu la qualité. Nous considérerons une autre approche, qui nous permet d'obtenir des décalages non pas pour des fragments, mais pour chaque pixel individuel, et est utilisée lorsque la vitesse n'est pas si critique. C'est à cela que le terme « flux optique » est souvent associé dans la littérature.

Cette approche est souvent appelée différentielle, car elle repose sur le calcul de dérivées partielles selon les directions horizontale et verticale de l'image. Comme nous le verrons plus tard, les dérivées seules ne suffisent pas à déterminer les déplacements. C'est pourquoi, sur la base d'une idée simple, une grande variété de méthodes sont apparues, chacune utilisant une sorte de danse mathématique avec un tambourin pour atteindre l'objectif. Concentrons-nous sur la méthode Lucas-Kanade, proposée en 1981 par Bruce Lucas et Takeo Kanade.

Méthode Lucas-Kanade

Tout autre raisonnement repose sur une hypothèse très importante et peu juste : Supposons que les valeurs des pixels passent d'une image à l'autre sans changer. Ainsi, nous faisons l’hypothèse que les pixels appartenant au même objet peuvent se déplacer dans n’importe quelle direction, mais que leur valeur restera inchangée. Bien entendu, cette hypothèse a peu à voir avec la réalité, car les conditions d’éclairage globales et l’éclairage de l’objet en mouvement lui-même peuvent changer d’une image à l’autre. Cette hypothèse pose de nombreux problèmes, mais, curieusement, malgré tout, elle fonctionne plutôt bien dans la pratique.

En langage mathématique, cette hypothèse peut s'écrire ainsi : . Où I est une fonction de la luminosité des pixels en fonction de la position sur l'image et du temps. En d'autres termes, x et y sont les coordonnées des pixels dans le plan du cadre, le décalage et t le numéro de cadre dans la séquence. Admettons qu'une seule période de temps s'écoule entre deux images adjacentes.

Cas unidimensionnel

Considérons d’abord le cas unidimensionnel. Imaginons deux cadres unidimensionnels de 1 pixel de haut et 20 pixels de large (image de droite). Dans la deuxième image, l'image est légèrement décalée vers la droite. C'est ce déplacement que nous souhaitons retrouver. Pour ce faire, imaginons ces mêmes frames comme des fonctions (figure de gauche). L'entrée est la position du pixel, la sortie est son intensité. Dans cette représentation, le déplacement souhaité (d) apparaît encore plus clairement. Conformément à notre hypothèse, cela est simplement décalé, c'est-à-dire que nous pouvons dire que .

Veuillez noter que, si vous le souhaitez, vous pouvez également l'écrire sous forme générale : ; où y et t sont fixes et égaux à zéro.

Pour chaque coordonnée, nous connaissons les valeurs à ce stade, de plus, nous pouvons calculer leurs dérivées. Associons les valeurs connues au décalage d. Pour ce faire, nous écrivons le développement en série de Taylor pour :

Faisons une deuxième hypothèse importante : Supposons qu'elle soit suffisamment bien approchée par la dérivée première. Ayant fait cette hypothèse, nous écartons tout après la dérivée première :

Dans quelle mesure est-ce correct ? En général, pas grand chose, on perd ici en précision, à moins que notre fonction/image ne soit strictement linéaire, comme dans notre exemple artificiel. Mais cela simplifie considérablement la méthode, et pour obtenir la précision requise, vous pouvez faire une approximation successive, que nous examinerons plus tard.

Nous y sommes presque. Le déplacement d est notre valeur souhaitée, nous devons donc faire quelque chose avec . Comme nous l’avons convenu plus tôt, nous allons donc simplement réécrire :

Cas bidimensionnel

Passons maintenant du cas unidimensionnel au cas bidimensionnel. Écrivons le développement dans une série de Taylor et écartons immédiatement toutes les dérivées supérieures. Au lieu de la dérivée première, un dégradé apparaît :

Où est le vecteur déplacement.
Conformément à l'hypothèse formulée. Notez que cette expression est équivalente à . C'est ce dont nous avons besoin. Réécrivons :

Puisqu'un intervalle de temps unitaire s'écoule entre deux images, on peut dire qu'il n'y a rien de plus qu'une dérivée par rapport au temps.
Réécrivons :

Réécrivons-le à nouveau, en élargissant le dégradé :

Nous avons une équation qui nous dit que la somme des dérivées partielles doit être égale à zéro. Le seul problème est que nous avons une équation, mais elle contient deux inconnues : et . À ce stade, des envolées de fantaisie et une variété d’approches commencent.

Faisons une troisième hypothèse : Supposons que les pixels voisins soient décalés de la même distance. Prenons un fragment de l'image, disons 5 x 5 pixels, et convenons que pour chacun des 25 pixels et sont égaux. Ainsi, au lieu d’une équation, nous obtiendrons 25 équations à la fois ! Il est évident que dans le cas général le système n'a pas de solution, on va donc chercher telle et cela minimiser l'erreur :

Ici g est une fonction qui détermine les coefficients de pondération des pixels. L'option la plus courante est une gaussienne bidimensionnelle, qui donne le plus grand poids au pixel central et de moins en moins à mesure qu'il s'éloigne du centre.

Pour trouver le minimum, on utilise la méthode des moindres carrés et on trouve ses dérivées partielles par rapport à et :

Réécrivons-le sous une forme plus compacte et assimilons-le à zéro :

Réécrivons ces deux équations sous forme matricielle :

Si la matrice M est inversible (de rang 2), on peut calculer et , qui minimisent l'erreur E :

C'est tout. Nous connaissons le déplacement approximatif des pixels entre deux images adjacentes.

Étant donné que les pixels adjacents participent également à la recherche du décalage de chaque pixel, lors de la mise en œuvre de cette méthode, il convient de calculer au préalable les dérivées horizontales et verticales du cadre.

Inconvénients de la méthode

La méthode décrite ci-dessus repose sur trois hypothèses importantes qui, d’une part, nous donnent la possibilité fondamentale de déterminer le flux optique, mais d’autre part, introduisent une erreur. La bonne nouvelle pour les perfectionnistes est que nous n’avons besoin que d’une seule hypothèse pour simplifier la méthode et que nous pouvons gérer ses conséquences. Nous avons supposé que pour approximer le déplacement, la dérivée première nous suffirait. Dans le cas général, ce n’est certainement pas le cas (figure de gauche). Pour obtenir la précision requise, le décalage de chaque paire d'images (appelons-les et ) peut être calculé de manière itérative. Dans la littérature, cela s'appelle le gauchissement. En pratique, cela signifie qu'après avoir calculé les déplacements à la première itération, on déplace chaque pixel de la trame dans le sens opposé de manière à compenser ce déplacement. Lors de la prochaine itération, au lieu de l'image originale, nous utiliserons sa version déformée. Et ainsi de suite, jusqu'à l'itération suivante, tous les déplacements résultants sont inférieurs à la valeur seuil spécifiée. Nous obtenons le déplacement final pour chaque pixel spécifique comme la somme de ses déplacements à toutes les itérations.

De par sa nature, cette méthode est locale, c'est-à-dire que lors de la détermination du décalage d'un pixel spécifique, seule la zone autour de ce pixel est prise en compte - le voisinage local. En conséquence, il est impossible de déterminer les déplacements dans des zones suffisamment grandes (plus grandes que la taille du voisinage local) uniformément colorées du cadre. Heureusement, de telles zones ne sont pas souvent trouvées dans les images réelles, mais cette fonctionnalité introduit néanmoins un écart supplémentaire par rapport au véritable décalage.

Un autre problème est que certaines textures de l'image produisent une matrice singulière M pour laquelle la matrice inverse ne peut pas être trouvée. Par conséquent, pour de telles textures, nous ne pourrons pas déterminer le décalage. Autrement dit, il semble y avoir un mouvement, mais on ne sait pas clairement dans quelle direction. En général, ce problème n’est pas le seul à souffrir de la méthode considérée. Même l’œil humain ne perçoit pas un tel mouvement sans ambiguïté (pôle Barber).

Conclusion

Nous avons examiné les fondements théoriques de l'une des méthodes différentielles de recherche du flux optique. Il existe de nombreuses autres méthodes intéressantes, dont certaines donnent aujourd’hui des résultats plus fiables. Cependant, la méthode Lucas-Kanade, bien que très efficace, reste assez simple à comprendre et convient donc bien pour introduire les fondamentaux mathématiques.

Bien que le problème de la recherche du flux optique soit étudié depuis plusieurs décennies, les méthodes continuent d'être améliorées. Les travaux se poursuivent étant donné qu'après un examen plus approfondi, le problème s'avère très difficile et que la stabilité et l'efficacité de nombreux autres algorithmes dépendent de la qualité de la détermination des biais dans le traitement de la vidéo et de l'image.

Sur cette note prétentieuse, permettez-moi de conclure et de passer aux sources et liens utiles.
Méthode Lucas-Kanade

Lucas Canada

Ajouter des balises

Agafonov V. Yu. 1

1 Agafonov Vladislav Yurievich - étudiant diplômé du département "Conception assistée par ordinateur et systèmes de conception de recherche", Université technique d'État de Volgograd,

Volgograd

Annotation: V Cet article traite de deux approches pour rechercher des décalages entre les images dans un flux vidéo. La première approche est basée sur la minimisation de l'erreur par la méthode des moindres carrés lors de la recherche du déplacement des points clés de l'image. La deuxième approche est basée sur l’approximation d’une région de chaque pixel par un polynôme quadratique, qui peut être bien utilisé dans l’estimation de mouvement. Les principales étapes de mise en œuvre des méthodes sont décrites. Des ensembles de tests d'images ont été préparés en tenant compte des spécificités de la tâche. Les résultats de ces tests sont présentés.

Mots clés: traitement d'image, recherche de déplacement d'image

APPLICATION DE METHODES DE FLUX OPTIQUES A L'ESTIMATION DU DEPLACEMENT D'IMAGE

Agafonov V.U. 1

1 Agafonov Vladislav Urevich - étudiant de troisième cycle du département « Systèmes de conception assistée par ordinateur et conception de recherche »,

Université technique d'État de Volgograd, Volgograd

Abstrait: dans cet article, des méthodes d'estimation du décalage d'image sont décrites. La première approche est basée sur la minimisation de l’erreur quadratique moyenne lors de la recherche du déplacement des points clés de l’image. La deuxième approche est basée sur l'approximation de chaque voisinage des deux trames par des polynômes quadratiques, ce qui peut être réalisé efficacement en utilisant la transformation d'expansion polynomiale. Les principales étapes de mise en œuvre de ces méthodes sont décrites. Des ensembles d'images de test sont préparés en tenant compte de la nature spécifique du problème. Les résultats des travaux sont présentés.

Mots clés: traitement d'image, estimation du décalage d'image

CDU 004.932.2

Introduction

Lors de la résolution de problèmes de vision par ordinateur, le problème de l'estimation du mouvement d'un objet en images ou du déplacement de deux images consécutives dans un flux vidéo se pose souvent. L'estimation précise des paramètres de mouvement de la scène dans les images est un facteur important pour de nombreux algorithmes, c'est pourquoi les méthodes de détection de mouvement doivent fournir une précision inférieure au pixel.

Il existe plusieurs approches pour estimer le déplacement d'une image. Les principaux sont : l'identification des caractéristiques clés de l'image, suivie d'une comparaison des points clés, la détermination de la corrélation de phase de la représentation fréquentielle du signal d'image et du flux optique. Ce dernier dans sa forme principale n'est pas utilisé pour rechercher des déplacements d'image ; il sert à déterminer la présence de mouvement dans l'image. Ainsi, le flux optique est utilisé dans les systèmes de détection et de suivi d'objets.

Le flux optique est le modèle de mouvement apparent des objets, des surfaces ou des bords d'une scène provoqué par le mouvement relatif d'un observateur (œil ou caméra) par rapport à la scène. Les algorithmes basés sur le flux optique, tels que la détection de mouvement, la segmentation d'objets et le codage de mouvement, utilisent ce mouvement d'objets, de surfaces et de bords.

Dans ce travail, deux approches sont envisagées, l'une permettant d'obtenir des décalages pour des points clés individuels et la seconde pour chaque pixel individuel.

Flux optique par méthode Lucas-Kanade

Le concept de base de la méthode est de supposer que les valeurs des pixels se déplacent d'une image à l'autre sans changer :

Où. En ignorant le terme restant, on obtient la formule de l'approximation ???? :

où détermine le décalage. Conformément à l'hypothèse formulée, nous obtenons cela. Ensuite, nous écrivons l'équation (4) sous la forme

Il s’avère que la somme des dérivées partielles est nulle. Cependant, comme nous n’avons qu’une seule équation et deux inconnues, nous devons imposer des conditions supplémentaires. Une méthode courante consiste à imposer des restrictions sur les pixels proches. Supposons que les pixels voisins se déplacent de manière égale. Évidemment, il ne peut pas y avoir de décalage satisfaisant tous les pixels, nous minimisons donc l'erreur en utilisant la méthode des moindres carrés.

où est une matrice symétrique, est un vecteur et est un scalaire. Les coefficients sont calculés à l'aide des moindres carrés pondérés pour les valeurs de signal dans un quartier donné. La fonction de pondération se compose de deux éléments appelés certitude et applicabilité. La certitude relie la valeur d'un signal en fonction des valeurs du voisinage. L'applicabilité détermine la contribution relative des points en fonction de leur position dans le quartier. Habituellement, le point central a le poids le plus important, le poids des points restants diminue dans la direction radiale. Puisque l’image est développée comme un polynôme quadratique dans un certain voisinage, il est nécessaire de comprendre comment le polynôme se comporte avec un déplacement idéal. Soit un polynôme quadratique de la forme :

En égalisant les coefficients correspondants des polynômes quadratiques, nous avons :

Cela est vrai pour n’importe quel signal.

Évidemment, l’hypothèse selon laquelle le signal peut être représenté par un seul polynôme est tout à fait irréaliste. Cependant, la relation (10) peut être utilisée pour des signaux réels, même si des erreurs surviennent. La principale question est de savoir si les erreurs sont suffisamment petites pour que l’algorithme soit utile.

Remplaçons la représentation polynomiale globale par une représentation locale. Calculons les coefficients polynomiaux pour la première image et pour la deuxième image. Conformément à (9), cela devrait être le cas, mais en pratique, l'approximation est utilisée :

où reflète le remplacement du déplacement global par un déplacement spatialement variable.

En pratique, l’équation (11) peut être résolue élément par élément, mais les résultats s’avèrent trop bruités. Au lieu de cela, on suppose que la région de déplacement change lentement afin que nous puissions intégrer les informations en utilisant les pixels voisins. On cherche donc à trouver, satisfaisant (11) dans le voisinage, ou plus formellement :

Le principal problème de cette méthode est l’hypothèse selon laquelle les polynômes sont les mêmes, à l’exception du décalage. Puisque le développement polynomial local du polynôme changera en fonction de l'environnement, cela introduira une erreur dans (11). Pour les petits déplacements, cela n'a pas d'importance, mais à mesure que le déplacement augmente, l'erreur augmente. Si l'on a une connaissance a priori du biais, on peut comparer deux polynômes : le premier in, le second in, où il s'agit du biais a priori, arrondi à une valeur entière. De cette façon, nous pouvons exécuter la méthode de manière itérative. Un meilleur biais a priori signifie un biais relativement plus faible, ce qui augmente les chances d’obtenir une bonne estimation du biais réel.

Application des méthodes de flux optiques au problème de la recherche de déplacements d'images

Pour tester ces méthodes, des tests ont été effectués sur un ensemble de données artificielles, c'est-à-dire obtenue à l’aide d’un générateur d’images biaisées. Pour obtenir un décalage de sous-pixels, des zones présentant un léger décalage les unes par rapport aux autres ont été découpées dans l'image originale. Après cela, les images de test résultantes ont été compressées plusieurs fois ; en conséquence, certaines informations les concernant ont disparu et le déplacement a été réduit au sous-pixel.

Pour la méthode Lucas-Kanade, il est nécessaire de sélectionner de nombreux points clés dont il faut trouver le déplacement. À cette fin, la méthode classique de recherche de limites et de coins est utilisée. Après avoir obtenu le déplacement de chacun de ces points, il faut faire la moyenne du résultat obtenu.

Pour la méthode Farneback, il suffit de faire la moyenne des valeurs de déplacement dans chaque pixel.

L'expérience a été réalisée sur un échantillon de 20 paires de tests et l'écart type pour chaque méthode a été calculé.

OP Lucas-Canada
PO Farnebaca

Tableau 1 - Écart type des déplacements

D’après les résultats expérimentaux, on peut voir que les deux méthodes estiment le déplacement des images avec une grande précision. Le résultat de la méthode de Farneback montre un résultat moins bon car la méthode estime le déplacement pour tous les pixels et peut commettre des erreurs sur les parties monochromatiques de l'image.

Chaque méthode a ses propres avantages et inconvénients, ainsi que sa portée et ses limites. La méthode Lucas-Kanade implémente un flux optique clairsemé et

peut atteindre une précision inférieure au pixel. Mais avec un mouvement parallèle non plan, un autre problème se pose : comment estimer le déplacement de points qui ne sont pas essentiels. La première solution consiste à construire un diagramme de Voronoï pour le plan image avec des points clés donnés. Cette approche repose sur l’hypothèse que les zones situées à proximité des points clés se déplacent de la même manière que les points clés. En général, ce n'est pas toujours vrai. En pratique, les points clés sont pour la plupart des zones présentant des changements de gradient brusques, ce qui signifie que les points clés seront principalement concentrés sur des objets détaillés. Par conséquent, le déplacement des zones de couleur unie comportera une erreur importante. La deuxième solution est de trouver l'homographie de deux images. Cette solution souffre également d'une estimation imprécise du déplacement sur les bords de l'image.

L'avantage de la méthode du flux optique de Farneback est que le déplacement est trouvé pour chaque pixel. Cependant, cette méthode commet également des erreurs sur les objets périodiques et faiblement texturés, mais nous permet d'évaluer un mouvement parallèle non plan.

Conclusion

Cet article traite d'une approche d'estimation du déplacement d'image basée sur des méthodes de flux optique. L'applicabilité des méthodes est prouvée et les résultats d'une analyse comparative sont présentés. Des études expérimentales des méthodes ont montré que cette approche est très précise et peut être utilisée pour estimer les paramètres de mouvement d'une scène.

Bibliographie/ Les références

1. Fleet D., Weiss Y. Estimation du flux optique // Manuel de modèles mathématiques en vision par ordinateur. - Springer États-Unis, 2006. - pp. 237-257.
2. Farnebäck G. Estimation de mouvement à deux images basée sur l'expansion polynomiale // Analyse d'image. - 2003. - P. 363-370.

Le flux optique est une technologie utilisée dans divers domaines de la vision par ordinateur pour déterminer les décalages, la segmentation, la sélection d'objets et la compression vidéo. Cependant, si nous voulons le mettre en œuvre rapidement dans notre projet, après l'avoir lu sur Wikipédia ou ailleurs, nous tomberons très probablement très vite sur le fait qu'il fonctionne très mal et échoue lors de la détermination de décalages de l'ordre de 1-2 pixels (du moins c'était le cas pour moi). Passons ensuite aux implémentations prêtes à l'emploi, par exemple dans OpenCV. Là, il est implémenté en utilisant diverses méthodes et on ne sait absolument pas pourquoi l'abréviation PyrLK est meilleure ou pire que la désignation Farneback ou quelque chose comme ça, et vous devrez comprendre la signification des paramètres, qui sont nombreux dans certains mises en œuvre. De plus, ce qui est intéressant, c’est que ces algorithmes fonctionnent d’une manière ou d’une autre, contrairement à ce que nous avons écrit nous-mêmes. Quel est le secret ?

Qu'est-ce que le flux optique

Le flux optique (OP) est une image de mouvement apparent qui représente le décalage de chaque point entre deux images. Essentiellement, il représente un champ de vitesse (puisque le décalage, jusqu'à l'échelle, est équivalent à la vitesse instantanée). L'essence de l'OP est que pour chaque point de l'image, un décalage (dx, dy) est trouvé afin que le point de la deuxième image corresponde au point d'origine. Comment déterminer la correspondance des points est une question distincte. Pour ce faire, vous devez prendre une sorte de fonction ponctuelle qui ne change pas en raison du déplacement. On considère généralement qu'un point conserve son intensité (c'est-à-dire la luminosité ou la couleur pour les images couleur), mais les points qui préservent l'ampleur du dégradé, le Hessien, sa grandeur ou son déterminant, le Laplacien, et d'autres caractéristiques peuvent être considérés comme identiques. . Évidemment, le maintien de l'intensité échoue si l'éclairage ou l'angle d'incidence de la lumière change. Cependant, si nous parlons d'un flux vidéo, il est fort probable que l'éclairage ne changera pas beaucoup entre deux images, ne serait-ce que parce qu'une courte période de temps s'écoule entre elles. Par conséquent, l’intensité est souvent utilisée comme une fonction conservée en un point.

Sur la base de cette description, on peut confondre OP avec la recherche et la comparaison de points caractéristiques. Mais ce sont des choses différentes, l'essence du flux optique est qu'il ne recherche aucun point particulier, mais, sur la base des paramètres de l'image, essaie de déterminer où un point arbitraire s'est déplacé.

Il existe deux options pour calculer le flux optique : dense (dense) et sélectif ( clairsemé). Le flux Sparse calcule le décalage de points donnés individuels (par exemple, les points sélectionnés par un détecteur de caractéristiques), le flux dense calcule le décalage de tous les points de l'image. Naturellement, le flux sélectif est calculé plus rapidement, mais pour certains algorithmes, la différence n'existe pas. si grand, et pour certaines tâches, il est nécessaire de trouver le flux en tous points de l'image.

Pour les cas dégénérés, des méthodes plus simples pour déterminer le décalage peuvent être utilisées. En particulier, si tous les points de l'image ont le même décalage (l'image entière est décalée), alors la méthode de corrélation de phase peut être appliquée : calculer la transformée de Fourier pour les deux images, trouver la convolution de leurs phases et l'utiliser pour déterminer le décalage ( voir en.wikipedia.org /wiki/Phase_correlation). Vous pouvez également utiliser la correspondance de blocs : recherchez le décalage qui minimise la norme de différence entre les images dans la fenêtre. Dans sa forme pure, un tel algorithme fonctionnera longtemps et est instable aux rotations et autres distorsions. Wikipédia en anglais répertorie les algorithmes répertoriés comme diverses options de calcul du flux optique, mais cela ne me semble pas très correct, car ces algorithmes peuvent être utilisés à d'autres fins et ne résolvent pas complètement ce problème. Nous appellerons méthodes basées sur les caractéristiques locales des flux optiques des images (ce que l'on appelle méthodes différentielles dans la Wikipédia anglaise).

Approche standard (méthode Lucas-Kanade)

Une description mathématique de l’algorithme est donnée de manière suffisamment détaillée dans cet article, mais elle n’aborde que les aspects théoriques.

Considérons un modèle mathématique de flux optique, en supposant que l'intensité du point n'a pas changé à la suite du déplacement.

Laisser – l'intensité en un point (x, y) de la première image (c'est-à-dire au temps t). Dans la deuxième image, ce point s'est déplacé de (dx, dy), tandis que le temps dt s'est écoulé, puis nous avons Taylor étendu la fonction d'intensité au premier terme (on mentionnera plus tard pourquoi seulement au premier), voici les dérivées partielles par rapport aux coordonnées et au temps, c'est-à-dire essentiellement un changement de luminosité au point (x, y) entre deux images.

Nous pensons que le sujet a conservé son intensité, ce qui signifie
Nous obtenons une équation avec deux inconnues (dx et dy), ce qui signifie qu'il ne suffit pas de la résoudre, c'est-à-dire que vous n'irez pas loin avec cette seule équation.

La solution la plus simple au problème est l’algorithme de Lucas-Kanade. Dans notre image, nous avons des objets d'une taille supérieure à 1 pixel, ce qui signifie que, très probablement, à proximité du point actuel, d'autres points auront à peu près les mêmes déplacements. Par conséquent, nous prenons une fenêtre autour de ce point et minimisons (par la méthode des moindres carrés) l'erreur totale avec des coefficients de pondération distribués selon la Gaussienne, c'est-à-dire de sorte que les pixels les plus proches de celui étudié aient le plus grand poids. Après les transformations les plus simples, on obtient un système de 2 équations à 2 inconnues :

Comme on le sait, ce système n'a pas toujours de solution unique (bien que très souvent) : si le déterminant du système est égal à zéro, alors soit il n'y a pas de solutions, soit il y en a un nombre infini. Ce problème est connu sous le nom de problème d'ouverture : ambiguïté de déplacement avec un champ de vision limité pour les images périodiques. Cela correspond au cas où un fragment d'image apparaît, dans lequel il existe une certaine cyclicité ; ici, même une personne ne sera pas en mesure de déterminer sans ambiguïté où l'image s'est déplacée. Le problème est qu'en raison du bruit dans des situations aussi ambiguës, nous n'obtiendrons pas un déterminant nul, mais un très petit, ce qui conduira très probablement à des valeurs de décalage très élevées qui ne sont pas particulièrement corrélées à la réalité. Ainsi, à un certain stade, il vous suffit de vérifier si le déterminant du système est suffisamment petit et, si c'est le cas, de ne pas considérer ces points ni de les marquer comme erronés.

Pourquoi ça ne marche pas ?

Si nous nous arrêtons à ce stade et mettons en œuvre cet algorithme, il fonctionnera avec succès. Mais seulement si le décalage entre images adjacentes est très faible, de l'ordre de 1 pixel, et même alors pas toujours. (Pour analyser la qualité, des séquences synthétiques avec différents décalages relatifs ont été générées, et ce décalage peut être exprimé par un nombre non entier de pixels, puis l'image résultante est interpolée en conséquence) Déjà avec un décalage de 2 pixels, l'erreur sera grande , et si 3 ou plus, alors le résultat sera généralement insuffisant. Quel est le problème?

Ici, les mathématiques nous installent. Elle nous a inculqué le sentiment que toutes les fonctions qui nous entourent sont continues et plusieurs fois différenciables. Et en général, à l'institut, on nous a appris à écrire l'approximation d'une fonction au voisinage d'un point en utilisant la formule de Taylor, et nous l'utilisons partout avec inconscience et joie. Pensons maintenant à la signification physique des dérivés à cet endroit ? On veut les utiliser pour déterminer la variation de la valeur d'une fonction dans un voisinage fini d'un point, et la dérivée donne une idée d'un voisinage infinitésimal. Pour élargir ce voisinage, il serait possible d'ajouter un ordre supérieur de dérivées au développement de Taylor, mais cela conduirait à des non-linéarités dans le système, ce qui rendrait sa résolution beaucoup plus difficile, et les avantages seraient discutables, d'autant plus que en pratique, nous n'avons pas affaire à des fonctions différenciables multiples continues, mais à des fonctions discrètes généralement peu claires. Il serait donc plus logique de rechercher une fonction g(x), pour laquelle dans notre cas discret f(x) + g(x) = f(x+1), f(x) + 2g(x) = f(x) est satisfait aussi précisément que possible +2), f(x) - g(x) = f(x-1), etc. Ainsi, dans ce cas, nous n'avons pas besoin d'une dérivée, mais d'une fonction linéaire qui est le plus proche des points de la fonction d’origine. Des calculs mathématiques simples mènent à une solution , Où . Si nous avons construit la dérivée en utilisant un point adjacent de chaque côté, alors nous avons eu de la chance : dans ce cas, la formule coïncide avec la formule de calcul approximatif des dérivées : g(x) = (f(x+1) – f(x- 1)) / 2. Typiquement, dans OpenCV, lors du calcul du flux optique Lucas-Kanade, c'est exactement cette formule qui est utilisée, nous y reviendrons plus tard. Mais si vous prenez plus de points, alors la formule devient complètement différente des schémas de différence classiques pour la dérivée première.

Évidemment, si l'on construit cette fonction, par exemple, en utilisant trois points voisins à gauche et à droite de celui d'origine, alors elle ne dépend en aucun cas des points situés plus loin, et, par conséquent, si l'on décale plus de trois points, nous obtiendrons encore souvent des résultats inadéquats. Et aussi, plus le nombre de points à partir desquels nous construisons cette fonction est grand, plus l'écart moyen de la ligne résultante par rapport aux points utilisés est grand - encore une fois en raison du fait que nous n'avons pas d'images variant linéairement, mais qui sait de quelle sorte. En pratique, des décalages de plus de 2 pixels produisent déjà une erreur insuffisamment importante, quel que soit le nombre de points pris en compte.

Un autre point faible de l'algorithme est que, encore une fois, nous n'avons pas affaire à des fonctions continues lisses, mais à des fonctions arbitraires, voire discrètes. Par conséquent, dans certains fragments d’image, l’intensité peut « sauter » sans aucun motif évident, par exemple aux limites des objets ou à cause du bruit. Dans ce cas, aucune fonction g(x) ne peut décrire avec suffisamment de précision les changements de l’image au voisinage du point. Pour lutter contre cela (au moins partiellement), il est proposé de maculer l'image originale, et il sera utile de la maculer assez fortement, c'est-à-dire qu'il est préférable de ne pas utiliser même le flou gaussien préféré de tout le monde (moyenne avec coefficients de pondération), mais juste un filtre box (moyenne uniforme sur la fenêtre), et plusieurs fois de suite. La finesse de l’image est désormais plus importante pour nous que le détail.

Cependant, ces mesures ne nous éviteront pas non plus de limiter le décalage détecté à 2-3 pixels. Et en passant, dans OpenCV 1.0, il y avait une telle implémentation du flux optique, et cela ne fonctionnait que dans des conditions idéales et avec de très petits changements.

Ce qu'il faut faire?

En résumé, le Lucas-Kanade habituel est efficace pour identifier les petits décalages, de sorte que l'image est similaire à son approximation linéaire. Pour lutter contre cela, nous utiliserons la technique CV standard - multi-scaling : nous allons construire une « pyramide » d'images de différentes échelles (presque toujours mises à l'échelle 2 fois le long de chaque axe, c'est plus facile à calculer) et les parcourir avec un flux optique d'une image plus petite à une plus grande, alors le petit décalage détecté dans une petite image correspondra à un grand décalage dans une grande image. Dans la plus petite image, nous détectons un décalage de pas plus de 1 à 2 pixels. , et en passant d'une échelle plus petite à une plus grande, nous utilisons le résultat de l'étape précédente et affinons les valeurs de décalage, dans OpenCV, il est implémenté par la fonction calcOptFlowPyrLK. L'utilisation de cet algorithme pyramidal nous permet de ne pas nous soucier du calcul d'un linéaire. approximation sur plusieurs points : il est plus facile de prendre plus de niveaux de la pyramide, et à chaque niveau prendre une approximation assez grossière de cette fonction. Par conséquent, OpenCV ne calcule que deux points voisins. , nos conclusions sur l'avantage de la fonction d'approximation sur la dérivée se sont révélées inutiles : pour un tel nombre de points de référence, la dérivée est la meilleure fonction d'approximation.

Quels sont les autres ?

Cet algorithme n'est pas la seule option pour calculer le flux optique. Dans OpenCV, en plus du flux Lucas-Kanade, il existe également un flux Farneback et SimpleFlow, et l'algorithme Horn-Schunck est également souvent mentionné.

Méthode Corne–Schunck est de nature un peu plus globale que la méthode Lucas-Kanade. Cela repose sur l’hypothèse que le flux optique sera assez fluide sur toute l’image. A partir de la même équation, il est proposé de passer à la fonctionnelle, c'est-à-dire d'ajouter l'exigence d'absence de changement brutal des équipes avec un coefficient de pondération α. Minimiser cette fonctionnelle nous conduit à un système de deux équations :

Dans ces équations, il est proposé de calculer le Laplacien approximativement : – différence avec la valeur moyenne. Nous obtenons un système d'équations que nous écrivons pour chaque pixel et résolvons le système global de manière itérative :

Dans cet algorithme, ils suggèrent également d'utiliser la multi-mise à l'échelle et recommandent de redimensionner les images non pas par 2, mais par un facteur de 0,65.

Cet algorithme a été implémenté dans les premières versions d'OpenCV, mais a ensuite été abandonné.

Farneback proposé d'approximer le changement d'intensité dans le voisinage en utilisant une forme quadratique : I = xAx + bx + c avec une matrice symétrique A (en fait, considérant le développement de Taylor au premier terme, nous avons pris l'approximation linéaire I = bx + c , c'est-à-dire que maintenant nous sommes simplement décidés à augmenter la précision de l'approximation) Si l'image s'est déplacée dans ce quartier, alors, nous substituons dans le développement quadratique, ouvrons les parenthèses, nous obtenons


.

Nous pouvons maintenant calculer les valeurs de A, b, c dans les deux images, et alors ce système deviendra redondant par rapport à d (la première équation est particulièrement déroutante), et en général, d peut être obtenu à partir de la deuxième équation : . Nous devons recourir à l'approximation suivante : . Notons également pour simplifier , Alors nous obtenons simplement .

Pour compenser le bruit dans le calcul, on se tourne à nouveau vers l'hypothèse qu'à proximité du point étudié, tous les points ont plus ou moins le même décalage. Par conséquent, nous intégrons à nouveau l'erreur sur la fenêtre avec des coefficients de pondération gaussiens w, et trouvez le vecteur d qui minimise cette erreur totale. Nous obtiendrons ensuite la valeur optimale et l’erreur minimale correspondante. Autrement dit, nous devons calculer pour chaque point, faire la moyenne sur la fenêtre, inverser la matrice et obtenir le résultat. En conséquence, ces produits peuvent être calculés pour l'ensemble de l'image et des valeurs pré-calculées pour différents points peuvent être utilisées, c'est-à-dire que c'est exactement le cas lorsqu'il est logique de calculer un flux dense.

Comme d'habitude, cet algorithme comporte un certain nombre de modifications et d'améliorations, permettant principalement l'utilisation d'informations connues a priori - une approximation initiale donnée du flux - et, encore une fois, une mise à l'échelle multiple.

La base de la méthode Flux simple réside l’idée suivante : si nous ne savons toujours pas comment déterminer un décalage supérieur à la taille de la fenêtre sur laquelle nous avons recherché les dérivées, alors pourquoi s’embêter à calculer les dérivées ? Trouvons simplement le point le plus similaire dans la fenêtre ! Et pour lever les ambiguïtés et compenser le bruit, on tient compte du fait que l'écoulement est continu et qu'au voisinage d'un point donné tous les points ont quasiment le même décalage. Et nous résoudrons à nouveau le problème de la taille de la fenêtre grâce à la multi-mise à l'échelle.

Plus strictement, l'algorithme ressemble à ceci : pour tous les points de la fenêtre, il existe une fonction « énergie » qui est responsable (avec une dépendance logarithmique inverse) de la probabilité que le point initial passe à ce point : . Ensuite, la convolution de cette énergie avec une fenêtre gaussienne est considérée et les valeurs (dx,dy) qui minimisent cette fonction sont trouvées. Pour obtenir une précision inférieure au pixel, un petit voisinage du point optimal trouvé (dx,dy) est considéré et le pic de la fonction énergétique y est recherché comme le pic d'un paraboloïde. Et comme mentionné ci-dessus, cette procédure est effectuée sur une pyramide d’images à l’échelle. Leur algorithme propose également des méthodes astucieuses pour accélérer les calculs, mais ceux qui sont intéressés le découvriront par eux-mêmes. Ce qui est important pour nous, c’est que de ce fait, cet algorithme soit (théoriquement) assez rapide avec une bonne précision. Et il n’a pas le même problème que les précédents, à savoir que plus le décalage est important, plus il est détecté.

Et si on ne prenait pas d’intensité ?

Il a été dit plus haut que la correspondance entre les points peut être déterminée par différentes quantités, alors pourquoi considérons-nous uniquement l'intensité ? Mais parce que toute autre valeur peut s'y réduire : nous filtrons simplement les images avec le filtre approprié et transmettons les images filtrées à l'entrée des algorithmes décrits ci-dessus. Par conséquent, si vous souhaitez utiliser le flux optique, réfléchissez d'abord à quelle caractéristique de l'image sera la plus stable dans vos conditions et effectuez un filtrage approprié afin que l'entrée de l'algorithme ne soit pas l'intensité, mais cette caractéristique.

Pratique

Essayons en pratique les algorithmes que nous propose OpenCV.

Ici, vous pouvez effectuer de nombreuses études différentes de chaque algorithme, en faisant varier les paramètres, en modifiant les séquences d'entrée - avec différents décalages, rotations, transformations projectives, segments, avec un bruit différent, etc. Tout cela prendrait beaucoup de temps et prendrait la taille du rapport. dépasserait cet article, je propose donc ici de nous limiter au cas simple du décalage d'image parallèle d'une distance fixe et de l'imposition d'un petit bruit. Cela vous permettra de comprendre en termes généraux comment exécuter des algorithmes et lequel d'entre eux est le plus cool.

La syntaxe des procédures est décrite en détail sur la page contenant le manuel ; je fournirai ici une traduction résumée avec mes commentaires.

Le Lucas-Kanade classique est implémenté avec une pyramide dans la procédure calcOpticalFlowPyrLK. L'algorithme calcule le flux clairsemé, c'est-à-dire que pour un ensemble donné de points dans la première image, il estime leur position dans la seconde. Les paramètres d'entrée sont assez évidents : deux images d'entrée, un ensemble de points d'entrée et de sortie, status - un vecteur de sortie indiquant si le point correspondant a été trouvé avec succès, err - un vecteur de sortie des erreurs estimées des points correspondants, WinSize - la taille de la fenêtre sur laquelle se produit la moyenne gaussienne, j'ai pris 21x21 et ça a bien fonctionné, maxLevel – le nombre de couches dans la pyramide moins un, c'est à dire le numéro de la dernière couche, j'ai pris 5, les critères – la condition de sortie le processus itératif de détermination du décalage (la minimisation de l'erreur se fait de manière itérative) – j'ai laissé ce paramètre par défaut, flags – des drapeaux supplémentaires, par exemple, vous pouvez utiliser l'approximation du flux initial ou sélectionner la méthode d'estimation de l'erreur, minEigThreshold – le seuil de gradient valeur en dessous de laquelle la matrice est considérée comme singulière, je l'ai laissée par défaut. Depuis OpenCV 2.4.1, une pyramide précalculée d'images mises à l'échelle peut être utilisée lors du calcul du flux.

Le résultat du travail est que les petits et grands décalages sont détectés avec succès et de manière stable, il résiste à des bruits assez importants, le temps de fonctionnement est d'environ 10 ms pour 400 points avec une pyramide à 5 couches (sur un cœur i7 950).

À propos, cet algorithme est également implémenté sur GPU (CUDA), en version dense et clairsemée.

Le flux Farneback est implémenté par la procédure calcOpticalFlowFarneback, le flux dense est calculé, c'est-à-dire le décalage de chaque point. Paramètres : images d'entrée, flux de sortie au format d'une matrice flottante à deux canaux, pyr_scale détermine le rapport d'échelle entre les couches de la pyramide, niveaux – le nombre de niveaux dans la pyramide, winsize – la taille de la fenêtre sur laquelle la moyenne est effectuée. est effectué, itérations – le nombre d'itérations à chaque niveau, poly_n – la taille du polynôme par lequel les valeurs de A et b sont estimées, poly_sigma – le sigma du flou gaussien lors du lissage des dérivées, valeurs des paramètres recommandées sont indiqués dans le manuel, des drapeaux – des drapeaux supplémentaires, par exemple, vous pouvez utiliser l'approximation initiale du débit ou autrement la moyenne sur la fenêtre.

Cet algorithme est beaucoup moins stable (d'après mes observations), il rate plus facilement des images assez uniformes (apparemment, le problème est le manque de filtrage des points ratés), et il ne détecte pas bien les grands décalages. Cela a fonctionné pour moi en 600 ms sur une image 512x512.

Le flux SimpleFlow implémente la procédure calcOpticalFlowSF (encore une fois, le flux dense est calculé), et il comporte de nombreux paramètres mystérieux sans valeurs par défaut, et en général, pour le moment, les informations sur la page sont fournies de manière très succincte. Essayons de le comprendre. Les 3 premiers sont des images d'entrée et de sortie à deux canaux ; couches – le nombre de couches dans la pyramide, c'est-à-dire combien de fois nous redimensionnons l'image originale ; averaging_block_size – la taille de la fenêtre dans laquelle nous avons calculé la fonction d'énergie des pixels ; max_flow – le décalage maximum que nous voulons pouvoir déterminer à chaque étape, il est essentiellement déterminé par la taille de la fenêtre (bien qu'il ne soit pas tout à fait clair pourquoi il s'agit d'un int). Vous pouvez vous arrêter ici, ou définir quelques paramètres supplémentaires, la signification de certains d'entre eux m'échappe.

Le site propose un exemple de son utilisation, dans lequel il est lancé avec les paramètres suivants : calcOpticalFlowSF(frame1, frame2, flow, 3, 2, 4, 4.1, 25.5, 18, 55.0, 25.5, 0.35, 18, 55.0, 25.5 , dix) ;

Mon algorithme fonctionne beaucoup plus lentement que les autres, environ 9 à 12 secondes par image 512x512. Le résultat du travail semble plus plausible que celui de Farneback, au moins le décalage des images uniformes est mieux déterminé et cela fonctionne sensiblement mieux avec des décalages importants.

conclusions

Si vous souhaitez utiliser le flux optique quelque part, demandez-vous d’abord si vous en avez besoin : vous pouvez souvent vous en sortir avec des méthodes plus simples. Entreprendre d'implémenter soi-même un flux vaut la peine d'y réfléchir quelques fois : chaque algorithme possède de nombreuses astuces, subtilités et optimisations ; Quoi que vous fassiez, cela fonctionnera probablement mieux dans OpenCV (en supposant qu'il soit là, bien sûr). De plus, ils exploitent pleinement les optimisations logiques et matérielles telles que l'utilisation d'instructions SSE, le multithreading, les capacités de calcul avec CUDA ou OpenCL, etc. Si vous avez simplement besoin de calculer le décalage d'un certain ensemble de points (c'est-à-dire un flux clairsemé), alors vous peut utiliser en toute sécurité la fonction calcOpticalFlowPyrLK, elle fonctionne bien, de manière fiable et assez rapide. Pour calculer un écoulement dense, il est bon d'utiliser la fonction calcOpticalFlowSF, mais elle est très lente. Si les performances sont critiques, alors calcOpticalFlowFarneback, mais vous devez toujours vous assurer que les résultats de son travail vous conviendront. Ajouter des balises

Veuillez le formater conformément aux règles de formatage de l'article.

Flux optique est une image du mouvement apparent des objets, des surfaces ou des bords d'une scène résultant du mouvement de l'observateur (œil ou caméra) par rapport à la scène. Les algorithmes basés sur le flux optique, tels que la détection de mouvement, la segmentation d'objets, l'encodage de mouvement et le calcul de disparité stéréo, exploitent ce mouvement des objets, des surfaces et des bords.

Estimation du flux optique

Des séquences d'images ordonnées permettent d'estimer le mouvement sous forme de vitesse d'image instantanée ou de déplacement discret. Fleet et Weiss ont compilé un didacticiel sur la méthode du gradient d'estimation du flux optique.

Une analyse des méthodes de calcul du flux optique a été réalisée dans les travaux de John L. Barron, David J. Fleet et Steven Beauchemin. Ils passent en revue les méthodes tant du point de vue de la précision que du point de vue de la densité du champ vectoriel résultant.

Les méthodes basées sur le flux optique calculent le mouvement entre deux images prises au temps et à chaque pixel. Ces méthodes sont dites différentielles, car elles reposent sur une approximation du signal par un segment d'une série de Taylor ; ainsi, ils utilisent des dérivées partielles par rapport aux coordonnées temporelles et spatiales.

En cas de dimension 2D+ t(les cas de dimensions supérieures sont similaires) un pixel à une position avec une intensité dans une image sera déplacé de , et , et l'équation suivante peut être écrite :

En supposant que le déplacement est petit et en utilisant la série de Taylor, on obtient :

.

De ces égalités il résulte :

à partir de là, il s'avère que

- composantes de la vitesse du flux optique en ,
, , - images dérivées dans les directions correspondantes.

Ainsi:

L’équation résultante contient deux inconnues et ne peut être résolue de manière unique. Cette circonstance est connue sous le nom problème d'ouverture. Le problème est résolu en imposant des restrictions supplémentaires - la régularisation.

Méthodes de détermination du flux optique

Utiliser le flux optique

La recherche sur les flux optiques est largement menée dans les domaines de la compression vidéo et de l'analyse de mouvement. Les algorithmes de flux optique déterminent non seulement le champ de flux, mais utilisent également le flux optique pour analyser l'essence et la structure 3D de la scène, ainsi que le mouvement 3D des objets et de l'observateur par rapport à la scène.

Le flux optique est utilisé en robotique pour la reconnaissance d'objets, le suivi d'objets, la détection de mouvement et la navigation de robots.

De plus, le flux optique est utilisé pour étudier la structure des objets. Puisque la détection de mouvement et la création de cartes de la structure de l’environnement font partie intégrante de la vision animale (humaine), la mise en œuvre de cette capacité innée au moyen d’un ordinateur fait partie intégrante de la vision par ordinateur.

Imaginez une vidéo de cinq images d'une balle se déplaçant du bas à gauche vers le haut à droite. Les méthodes de détection de mouvement peuvent déterminer que sur un plan bidimensionnel, une balle se déplace vers le haut et vers la droite, et des vecteurs décrivant ce mouvement peuvent être obtenus à partir d'une séquence d'images. En compression vidéo, il s'agit de la description correcte de la séquence d'images. Cependant, dans le domaine de la vision par ordinateur, sans informations supplémentaires, il est impossible de dire si la balle se déplace vers la droite et l'observateur est immobile, ou si la balle est au repos et l'observateur se déplace vers la gauche.

voir également

Remarques

Liens

• DROP : (interface Windows) Logiciel gratuit d'estimation du flux optique dense utilisant l'optimisation discrète.
• Le French Aerospace Lab : implémentation GPU d'un flux optique basé sur Lucas-Kanade

Fondation Wikimédia. 2010.

• Débitmètres optiques
• Fibre optique à double revêtement

Voyez ce qu'est « Flux optique » dans d'autres dictionnaires :

Élément optique- un système optique qui permet d'obtenir une réflexion rétroréfléchissante. Remarque On distingue les types d'éléments optiques suivants : à bords plats, sphériques et à film. Source … Dictionnaire-ouvrage de référence des termes de la documentation normative et technique

efficacité optique d'un dispositif d'éclairage- L'efficacité d'un dispositif d'éclairage, calculée par rapport au flux lumineux nominal de la (des) lampe(s), sans tenir compte de l'influence de l'environnement, des conditions thermiques et de la position du dispositif d'éclairage sur le flux lumineux de la lampe ( les lampes). [GOST... ... Guide du traducteur technique

Pincettes optiques- Schéma d'utilisation d'une pince à épiler optique dans l'étude de l'ARN polymérase Pince à épiler optique (anglais ... Wikipedia

CONVERTISSEUR ÉLECTRON-OPTIQUE- (EOC), un dispositif photoélectronique sous vide permettant de convertir l'image d'un objet invisible à l'œil (en IR, UV et rayons X) en image visible ou d'améliorer la luminosité de l'image visible. Le fonctionnement de l'intensificateur d'image est basé sur la conversion optique. ou radiographie... ... Encyclopédie physique

Lucas–Canada- L'algorithme de Lucas Kanade est une méthode locale différentielle largement utilisée pour calculer le flux optique en vision par ordinateur. Comme on le sait, l'équation de base du flux optique contient deux inconnues et ne peut être résolue de manière unique.... ... Wikipedia

L'algorithme de Lucas- Canada, une méthode locale différentielle de calcul du flux optique, largement utilisée en vision par ordinateur. L'équation fondamentale du flux optique contient deux inconnues et ne peut pas être résolue de manière unique. L'algorithme de Lucas Kanade contourne... ... Wikipédia

OuvrirCV- Tapez vision par ordinateur Auteur... Wikipédia

Suivi (infographie)- Ce terme a d'autres significations, voir Tracking (significations). Le suivi est la détermination de la localisation d'un objet en mouvement (plusieurs objets) dans le temps à l'aide d'une caméra. L'algorithme analyse les images vidéo et donne la position... ... Wikipédia

La construction du flux optique est traditionnellement considérée comme une procédure permettant d'évaluer les changements géométriques de luminosité entre les images actuelles (actuelles) et précédentes. Le mouvement des objets devant une caméra fixe, ainsi que le mouvement de la caméra dans l'environnement environnant, entraînent des changements correspondants dans l'image. Le mouvement apparent du champ visible (distribution bidimensionnelle de la luminosité) observé lorsque la caméra se déplace par rapport aux objets imagés ou aux objets par rapport à la caméra est appelé flux optique. Définissons le champ de mouvement en attribuant un vecteur vitesse à chaque point de l'image. À un moment donné, un point sur l’image correspond à un certain point sur la surface de l’objet. Ces deux points sont liés par des équations de conception. Le point objet se déplace rapidement par rapport à la caméra. Cela génère un mouvement du point correspondant dans l'image. Au fil du temps, le point se déplace d'une distance et son image se déplace d'une distance (voir Fig. 1).

Riz. 1.

Les distributions de luminosité se déplacent avec les objets observés. Le flux optique, comme mentionné précédemment, est le mouvement apparent du motif de luminosité. Idéalement, le flux optique correspond au champ de mouvement déterminé précédemment, mais en pratique ce n'est pas toujours le cas.

Soit maintenant la luminosité d'un pixel en un point de l'image à un instant donné. Alors, si et - et sont des composantes du vecteur de flux optique à ce stade, alors nous pouvons nous attendre à ce que

Annulons par sur les côtés gauche et droit, divisons par et allons jusqu'à la limite. On a

Les dérivées peuvent être facilement obtenues à partir de l'image en utilisant des approximations numériques des dérivées par différences finies

Réécrivons (4) sous la forme

Ici, la région est la région dans laquelle le flux optique est recherché. La valeur du coefficient détermine le niveau de significativité de la partie lissage de la fonctionnelle (11). A noter que dans la littérature, les propositions de choix de valeurs diffèrent radicalement. Par exemple, dans le livre, il est proposé de choisir cette constante égale, dans le livre - égale.

Le problème de minimisation de la fonctionnelle (6) est résolu en utilisant la procédure itérative (7)-(8). La séquence de vitesses qui minimise la fonctionnelle (6) a la forme :

Ici l'index montre le numéro de l'itération en cours, - les indices du nœud de grille actuel.

Le processus itératif se termine lorsque l'écart (9) entre deux itérations successives est inférieur à un nombre prédéterminé :

Cependant, cette condition est assez peu pratique à utiliser explicitement en raison des coûts de calcul importants liés à son calcul s’il est nécessaire de la vérifier à chaque itération. Par conséquent, un nombre fixe d’itérations est généralement utilisé. Par exemple, dans les travaux, il est proposé d'utiliser. En pratique, pour des images avec un bon contraste d’objet, des itérations suffisent. L’utilisation d’un nombre d’itérations beaucoup plus important peut conduire à l’apparition de vitesses erronées non nulles dans les régions où le champ de vitesse est en réalité nul. Cela se produit notamment lorsque deux objets différents se déplacent à une courte distance l’un de l’autre. Le champ de vitesse entre eux est en réalité nul, mais le flux optique calculé sur un grand nombre d'itérations peut être non nul en raison de l'hypothèse de continuité du mouvement.

Le flux optique peut également être nul là où le champ de vitesse n'est pas nul. Ce cas se produit par exemple lors du déplacement d'un objet caractérisé par une luminosité constante sur toute la surface de la zone d'image occupée. Dans ce cas, le flux optique calculé à la limite de l'objet sera non nul, et celui calculé au centre de l'objet sera proche de zéro, tandis que le champ de vitesse réel devra être le même sur toute la surface de l'objet. L'object. Ce problème est appelé « problème d’ouverture ».

Il est proposé de calculer les dérivées de la luminosité de l'image comme suit :

Ici, une approximation de grille des dérivées est utilisée. L'index indique le numéro de la frame actuelle, - les indices du nœud de grille actuel. Les variations et lors du calcul des dérivées partielles (10) peuvent être choisies de n'importe quelle manière. Généralement, un maillage est utilisé

Désormais, en remplaçant les dérivées partielles (10) et les vitesses moyennes (8) dans le processus itératif (7) avec des conditions initiales, pour tout le monde dans la région, il est facile de trouver les vitesses de tous les points de la grille sur les images observées de la vidéo. séquence.

Le schéma informatique décrit suit les méthodes traditionnelles d’estimation du flux optique. Cependant, des expériences menées sur un grand volume d'enregistrements vidéo réels ont montré que lorsque les algorithmes d'analyse de flux optique opèrent directement à partir des images numériques originales en demi-teintes, la qualité des données de sortie de ces algorithmes n'est pas suffisamment élevée en raison de l'influence significative du bruit et d'autres interférences sur la qualité de la détection des objets. À cet égard, dans ce travail, il est proposé d'utiliser une procédure spéciale de différence cumulative décrite dans la section suivante comme procédure de prétraitement des données vidéo. L'intérêt de cette procédure est la sélection préliminaire robuste des contours des objets en mouvement, à partir de laquelle est ensuite calculée une estimation des flux optiques, qui est utilisée au stade de la formation des hypothèses et du suivi des objets en mouvement.