Get best of the week

Quand arrêter le processus de reconnaissance de séquence vidéo?

Salut Habr! Aujourd'hui, nous aimerions vous parler d'une tâche très intéressante à laquelle nous sommes confrontés depuis le tout début de nos recherches sur la reconnaissance de documents dans le flux vidéo - le problème de trouver le temps d'arrêt optimal.



Figure. 1. Images de champs de texte de documents d'identité sur des images d'une séquence vidéo.

Comme beaucoup de gens le savent, le principal produit des moteurs intelligents est un système de reconnaissance des documents d'identité, Smart IDReader, applicable à la fois sur les serveurs et les ordinateurs de bureau, et sur les appareils mobiles. Dans un grand nombre de cas, la reconnaissance des documents sur un téléphone portable doit avoir lieu hors ligne, souvent nous ne pouvons pas contrôler les conditions et la qualité de la prise de vue, et le coût des erreurs de reconnaissance, notamment lors de la reconnaissance des documents d'identification, est très élevé. Dans le même temps, nous avons un avantage important - nous pouvons utiliser non pas une image, mais une séquence d'images capturées (voir Fig.1), pour augmenter la précision de reconnaissance.

Lorsque vous utilisez plusieurs images de champs de texte, deux questions importantes se posent. La première question est de savoir comment combiner les observations? Vaut-il la peine de combiner les images source pour obtenir une image, une «qualité» supérieure, ou choisir une meilleure image (alors où est la garantie qu'il y aura une image qui soit bonne)? Ou, peut-être, reconnaissez d'abord le champ sur chaque image, puis sélectionnez le résultat le plus «sûr» (selon quels critères?), Ou combinez les résultats de la reconnaissance image par image, etc. Nous adhérons à cette dernière approche (reconnaissance trame par trame avec combinaison intertrame de résultats), mais l'approche optimale peut différer à la fois en fonction du moteur de reconnaissance utilisé et d'autres paramètres de tâche.

La deuxième question qui se pose indépendamment de la première est de savoir quand arrêter le processus d'observation? En d'autres termes, selon quel critère décidez-vous que le processus de capture peut être arrêté et que le résultat accumulé par le moment actuel est reconnu comme final? Comment comparer ces critères entre eux et existe-t-il un critère optimal?

Il s'agit du problème de trouver le moment d'arrêter le processus d'observation qui sera discuté dans cet article.

Ce que nous voulons réaliser


Reconnaître une chaîne de texte dans une séquence vidéo, dans laquelle après avoir capturé une autre observation, le résultat s'améliore d'une manière ou d'une autre, peut être considéré comme un algorithme Anytime - un algorithme avec un résultat s'améliorant séquentiellement, dont le calcul peut être arrêté à tout moment. Un outil pratique pour visualiser la qualité de ces algorithmes est « les profils de performance attendus » - des graphiques de la dépendance de la qualité du résultat, mesurée sous une forme ou une autre, sur le temps de calcul.


Figure. 2. Profils d'efficacité de la reconnaissance des lignes de texte dans une séquence vidéo (plus c'est bas, mieux c'est). La ligne pointillée noire est de qualité image par image, la ligne noire continue est le résultat de la combinaison intertrame. La ligne orange est ce que nous attendons de la «bonne» règle d'arrêt.

En figue. La figure 2 montre les profils d'efficacité pour reconnaître une chaîne de texte - la dépendance de l'erreur moyenne (en termes de distance de Levenshtein à la bonne réponse) sur le nombre de trames traitées. Des graphiques noirs ont été obtenus en utilisant Tesseract v4.0.0 sur les champs de texte de l' ensemble de données MIDV-500 . On peut voir que l'utilisation de la combinaison intertrame des résultats de reconnaissance permet d'obtenir une valeur d'erreur beaucoup plus faible (ce qui, en général, n'est pas surprenant).

Que voulons-nous d'une «bonne» règle d'arrêt? Étant donné que nous nous attendons, tout à fait raisonnablement, à ce que plus nous continuons le processus, meilleur sera le résultat moyen, ce serait bien si la règle d'arrêt sur certaines séquences vidéo était considérée comme «plus longue», s'il y avait une chance de minimiser l'erreur, et sur certaines, elle s'arrêterait serait plus tôt si le résultat est déjà bon, ou s'il n'y a aucune chance de l'améliorer. De ce fait, avec la même qualité moyenne du résultat combiné, en moyenne, moins de trames traitées peuvent être atteintes, et vice versa, avec le même nombre moyen de trames, le résultat moyen est meilleur. En d'autres termes, il est important de comprendre que la règle d'arrêt ne consiste pas seulement à minimiser le temps, mais aussi à maximiser la qualité, pour le même temps (moyen).

Cherchons la règle d'arrêt sous la forme suivante: après avoir traité la trame suivante et reçu le résultat de reconnaissance combiné, nous considérons une caractéristique et coupons son seuil - si, par exemple, elle est inférieure au seuil, alors nous nous arrêtons, sinon nous continuons. Ensuite, avec une règle d'arrêt fixe, mais en faisant varier le seuil, nous obtiendrons également un profil d'efficacité, à l'exception que l'axe horizontal ne contiendra pas le nombre exact de trames traitées, mais la moyenne (voir le graphique orange sur la figure 2). Plus ce graphique est bas, plus nous pouvons considérer la règle d'arrêt comme efficace. Nous pouvons considérer que le profil initial du «résultat combiné» est le profil de l'efficacité de la règle d'arrêt triviale - dans laquelle nous réduisons simplement le nombre d'images traitées par le seuil.

Ce que dit la théorie


En statistique mathématique, les problèmes de recherche du temps d'arrêt optimal sont bien connus et sont étudiés depuis longtemps. Les tâches les plus célèbres de cette classe sont peut-être la tâche d'une mariée difficile (elle était très impliquée, par exemple, Boris Abramovich Berezovsky), la tâche de vendre une maison et d'autres. Sans approfondir la théorie, posons brièvement le problème de la reconnaissance dans les séquences vidéo comme le problème d'arrêt optimal.

Nous notons l'erreur du résultat combiné à la nième étape du processus comme \ epsilon (R_n). Nous supposons que si nous nous arrêtons à la nième étape, nous subirons une perte de la forme suivante :, L_n = \ epsilon (R_n) + c \ cdot noùc- un coût relatif prédéterminé de chaque observation. La tâche de trouver le temps d'arrêt optimal peut être formulée comme une recherche d'une variable aléatoire N- le temps d'arrêt, dont la distribution dépend des observations d'entrée (dans certaines publications, la valeur Nest appelée le moment de Markov ), et à laquelle la perte attendue est minimisée \ mathrm {E} (L_N).

Problèmes monotones


Dans certaines conditions, dans de tels problèmes, la règle d'arrêt optimale peut être explicitement exprimée. Un exemple est le problème dit monotone. Le critère de la monotonie du problème est le suivant: si à une étape la nperte L_nne dépasse pas la perte attendue à l'étape suivante, alors elle sera effectuée à toutes les étapes suivantes. En d'autres termes, de ce qui s'est passé, l'événement L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {reçu} ~ n ~ \ text {frames})s'ensuit que l'événement se produira L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {reçu} ~ n + 1 ~ \ text {frames}). Pour les problèmes monotones, la règle d'arrêt dite "à courte vue" est optimale: arrêtez-vous dès la première étape où la condition est remplie L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {reçu} ~ n ~ \ text {frames}).

Supposons que notre tâche soit monotone. Après avoir écrit la règle myope en termes de notre fonction, L_nnous obtenons que nous devons nous arrêter lorsque la condition suivante est remplie:

\ epsilon (R_n) - \ mathrm {E} (\ epsilon (R_ {n + 1}) | \ text {reçu} ~ n ~ \ text {frames}) \ le c.

Bien sûr, c'est génial, mais pour mettre en œuvre cette règle, nous devons être en mesure d'évaluer en runtime non seulement la «justesse» du résultat actuel, mais aussi la justesse attendue du prochain, ce qui n'est pas si simple (sans parler de ce que nous avons impérieusement exigé de la tâche). monotonie). Pouvons-nous en quelque sorte appliquer cette règle sans évaluer directement la «justesse» du résultat? .. Vous pouvez essayer d'évaluer le côté gauche de l'inégalité par le haut.

Comment utiliser la règle myope?


Supposons qu'une fonction \ epsilon (R_n)soit la distance \ rho (R_n, R ^ *)entre le résultat R_nde la reconnaissance combinée et la «bonne réponse» R ^ *, et comme toute distance qui se respecte, l'inégalité du triangle tient. La distance de Levenshtein mentionnée ci-dessus satisfait l'inégalité du triangle, ainsi qu'une fonction simple sous la forme de «bien / mal» (si nous supposons que \ rho (R_n, R ^ *)pour la bonne réponse, elle est nulle et pour la mauvaise réponse, elle est constante). Selon l'inégalité du triangle, le côté gauche de notre critère d'arrêt ne dépasse pas \ mathrm {E} (\ rho (R_n, R_ {n + 1}) | \ text {reçu} ~ n ~ \ text {frames})- la distance attendue du résultat combiné actuel au suivant.

Exigeons également de notre algorithme de combiner les images entre les résultats de reconnaissance, de sorte qu'en moyenne la distance entre les résultats combinés adjacents n'augmente pas au fil du temps (c'est-à-dire que nous considérerons la séquence des résultats combinés comme un processus `` convergent '', mais pas nécessairement vers la bonne réponse). Ensuite, si la distance attendue du résultat actuel au suivant devient inférieure au seuil c, deux choses sont faites à la fois. Premièrement, le critère d'arrêt à courte vue est rempli (puisque sa partie gauche est délimitée d'en haut par cette même distance). Et deuxièmement, la tâche devient monotone: à l'étape suivante, la distance attendue par rapport à la réponse suivante n'augmentera pas, ce qui signifie qu'elle continuera d'être inférieure au seuil c, et le critère à courte vue sera à nouveau rempli.

Cela signifie que si nous nous attendons à ce que les distances entre les résultats combinés adjacents n'augmentent pas en moyenne, alors nous devons nous arrêter par seuil de coupure de la distance attendue du résultat actuel au prochain, approximant ainsi la règle optimale. Vous devez comprendre qu'une telle règle n'est plus optimale (puisque la «vraie» règle optimale pourrait s'arrêter plus tôt), mais au moins nous ne nous arrêterons pas plus tôt que nécessaire.

Il existe plusieurs façons d'évaluer la distance attendue du résultat combiné actuel au suivant. Par exemple, si la distance de Levenshtein est utilisée comme métrique sur les résultats, alors même juste la distance entre les deux derniers résultats de la mise en page est une bonne approximation. Une autre approche possible consiste à simuler une éventuelle prochaine observation (par exemple, sur la base de celles déjà obtenues), à effectuer des combinaisons «inactives» et à calculer la distance moyenne aux prédictions obtenues.


Figure. 3. Comparaison des profils de performances pour plusieurs règles d'arrêt.

En figue. 3 montre des profils de performances pour plusieurs règles d'arrêt. N_K- la même règle «triviale» «mentionnée ci-dessus» - avec un seuil de coupure du nombre d'observations traitées. N_ {CX}etN_ {CR}- seuils de coupure de la taille maximale de cluster des mêmes résultats image par image ( N_ {CX}) et combinés ( N_ {CR}). N- la règle décrite dans cet article, avec une estimation de la distance attendue au résultat suivant en utilisant des combinaisons de modélisation et de "ralenti".

Au lieu d'une conclusion


Le but de l'article était de montrer que dans les systèmes de reconnaissance de documents sur des trames de séquences vidéo, il existe de nombreux problèmes intéressants, non seulement directement de la vision par ordinateur, mais aussi d'autres domaines intéressants. Bien que nous ayons montré le problème de trouver le temps d'arrêt optimal uniquement sous sa forme la plus simple, la partie la plus intéressante commence lorsque, par exemple, nous voulons prendre en compte dans le modèle non seulement le nombre d'images, mais aussi le temps d'exécution réel. Nous espérons que vous étiez intéressé et merci de votre attention!

- La

publication a été préparée sur la base de l'article sur les stratégies d'arrêt optimales pour la reconnaissance de texte dans un flux vidéo, K. Bulatov, N. Razumnyi, VV Arlazarov, IJDAR 22, 303-314 (2019) 10.1007 / s10032-019-00333-0 .

Si le lecteur s'intéresse à la théorie du temps d'arrêt optimal, en particulier à la preuve de l'optimalité de la règle myope pour les problèmes monotones, nous recommandons fortement le cours publié sur l' arrêt optimal et les applications (Thomas Ferguson, UCLA).

Quelques autres sources intéressantes à ce sujet:
Chow YS, Siegmund D. De grandes attentes: La théorie de l'arrêt optimal , Houghton Mifflin, 1971, 139 p.
Berezovsky B.A., Gnedin A.V. The Best Choice Problem , Science, 1984, 200 p.
Ferguson TS, Hardwick TS Stopping rules for relecture , Journal of Applied Probability., V. 26, N. 2, 1989, p. 303-313.
Ferguson TSStatistiques mathématiques: une approche théorique de la décision . Presse académique, 1967, 396 p.

More articles:


All Articles