Get best of the week

Wann muss der Videosequenzerkennungsprozess gestoppt werden?

Hallo Habr! Heute möchten wir Ihnen von einer sehr interessanten Aufgabe erzählen, mit der wir uns seit Beginn unserer Forschung zur Dokumentenerkennung im Videostream befasst haben - dem Problem, die optimale Stoppzeit zu finden.



Feige. 1. Bilder von Textfeldern von ID-Dokumenten auf Frames einer Videosequenz.

Wie viele wissen, ist das Hauptprodukt von Smart Engines ein System zur Erkennung von Identitätsdokumenten, Smart IDReader, das sowohl auf Servern und Desktops als auch auf Mobilgeräten anwendbar ist. In einer großen Anzahl von Fällen muss die Erkennung von Dokumenten auf einem Mobiltelefon offline erfolgen. Oft können wir die Bedingungen und die Qualität der Aufnahme nicht kontrollieren, und die Kosten eines Erkennungsfehlers, insbesondere beim Erkennen von Ausweisdokumenten, sind sehr hoch. Gleichzeitig haben wir einen wichtigen Vorteil: Wir können nicht ein Bild, sondern eine Folge von aufgenommenen Bildern (siehe Abb. 1) verwenden, um die Erkennungsgenauigkeit zu erhöhen.

Bei Verwendung mehrerer Bilder von Textfeldern ergeben sich zwei wichtige Fragen. Die erste Frage ist, wie Beobachtungen kombiniert werden können. Lohnt es sich, die Quellframes zu kombinieren, um ein Bild, eine höhere „Qualität“ oder ein besseres Frame zu erhalten (wo ist dann die Garantie, dass es ein gutes Frame gibt)? Oder erkennen Sie zuerst das Feld in jedem Frame und wählen Sie dann das „sicherste“ Ergebnis aus (nach welchen Kriterien?) Oder kombinieren Sie Frame-für-Frame-Erkennungsergebnisse usw. Wir halten uns an den letzteren Ansatz (Frame-für-Frame-Erkennung mit Interframe-Kombination von Ergebnissen), aber der optimale Ansatz kann sich sowohl in Abhängigkeit von der verwendeten Erkennungs-Engine als auch von anderen Aufgabenparametern unterscheiden.

Die zweite Frage, die sich unabhängig von der ersten stellt, ist, wann der Beobachtungsprozess gestoppt werden soll. Mit anderen Worten, nach welchem ​​Kriterium entscheiden Sie, dass der Erfassungsprozess gestoppt werden kann und das im aktuellen Moment akkumulierte Ergebnis als endgültig erkannt wird? Wie kann man solche Kriterien miteinander vergleichen und gibt es ein optimales?

Es geht um das Problem, den Moment zu finden, in dem der Beobachtungsprozess gestoppt wird, der in diesem Artikel behandelt wird.

Was wir erreichen wollen


Das Erkennen einer Textzeichenfolge in einer Videosequenz, bei der sich das Ergebnis nach der Erfassung einer anderen Beobachtung auf die eine oder andere Weise verbessert, kann als jederzeitiger Algorithmus betrachtet werden - ein Algorithmus mit einem sich sequenziell verbessernden Ergebnis, dessen Berechnung jederzeit gestoppt werden kann. Ein praktisches Werkzeug zur Visualisierung der Qualität solcher Algorithmen sind „ Erwartete Leistungsprofile “ - Diagramme der Abhängigkeit der Qualität des Ergebnisses, gemessen in der einen oder anderen Form, von der Berechnungszeit.


Feige. 2. Profile der Effizienz der Textzeilenerkennung in einer Videosequenz (niedriger ist besser). Die schwarz gepunktete Linie ist Frame für Frame-Qualität, die schwarze durchgezogene Linie ist das Ergebnis der Interframe-Kombination. Die orange Linie ist das, was wir von der „guten“ Stoppregel erwarten.

In Abb. Abbildung 2 zeigt die Effizienzprofile zum Erkennen einer Textzeichenfolge - die Abhängigkeit des durchschnittlichen Fehlers (in Bezug auf den Abstand von Levenshtein zur richtigen Antwort) von der Anzahl der verarbeiteten Frames. Schwarze Grafiken wurden mit Tesseract v4.0.0 in den Textfeldern des MIDV-500-Datensatzes erhalten . Es ist ersichtlich, dass die Verwendung der Interframe-Kombination von Erkennungsergebnissen es ermöglicht, einen viel niedrigeren Fehlerwert zu erzielen (was im Allgemeinen nicht überraschend ist).

Was wollen wir von einer „guten“ Stoppregel? Da wir vernünftigerweise davon ausgehen, dass das durchschnittliche Ergebnis umso besser ist, je länger wir den Prozess fortsetzen, wäre es großartig, wenn die Regel für das Anhalten einiger Videosequenzen als „länger“ angesehen würde, wenn die Möglichkeit besteht, den Fehler zu minimieren, und bei einigen würde sie anhalten wäre früher, wenn das Ergebnis bereits gut ist oder es keine Chance gibt, es zu verbessern. Aus diesem Grund können mit der gleichen durchschnittlichen Qualität des kombinierten Ergebnisses im Durchschnitt weniger verarbeitete Frames erzielt werden, und umgekehrt ist mit der gleichen durchschnittlichen Anzahl von Frames das durchschnittliche Ergebnis besser. Mit anderen Worten, es ist wichtig zu verstehen, dass es bei der Stoppregel nicht nur darum geht, die Zeit zu minimieren, sondern auch darum, die Qualität für dieselbe (durchschnittliche) Zeit zu maximieren.

Suchen wir nach der Stoppregel in der folgenden Form: Nachdem wir den nächsten Frame verarbeitet und das kombinierte Erkennungsergebnis erhalten haben, betrachten wir ein Merkmal und schneiden seinen Schwellenwert ab. Wenn er beispielsweise unter dem Schwellenwert liegt, stoppen wir, andernfalls fahren wir fort. Mit einer festen Stoppregel, die jedoch den Schwellenwert variiert, erhalten wir auch ein Effizienzprofil, mit der Ausnahme, dass die horizontale Achse nicht die genaue Anzahl der verarbeiteten Frames, sondern den Durchschnitt enthält (siehe das orangefarbene Diagramm in Abb. 2). Je niedriger dieses Diagramm ist, desto effektiver können wir die Stoppregel betrachten. Wir können das Anfangsprofil des „kombinierten Ergebnisses“ als das Profil der Wirksamkeit der Trivial-Stop-Regel betrachten, bei der wir einfach die Anzahl der vom Schwellenwert verarbeiteten Frames reduzieren.

Was die Theorie sagt


In der mathematischen Statistik sind die Probleme beim Finden der optimalen Stoppzeit bekannt und seit langem untersucht. Die vielleicht berühmtesten Aufgaben dieser Klasse sind die Aufgabe einer wählerischen Braut (sie war sehr involviert, zum Beispiel Boris Abramovich Berezovsky), die Aufgabe, ein Haus zu verkaufen und andere. Lassen Sie uns, ohne tief in die Theorie einzusteigen, kurz das Problem der Erkennung in Videosequenzen als das optimale Stoppproblem darstellen.

Wir bezeichnen den Fehler des kombinierten Ergebnisses im ni-ten Schritt des Prozesses als \ epsilon (R_n). Wir gehen davon aus, dass wir, wenn wir beim ni-ten Schritt anhalten , einen Verlust der folgenden Form erleiden:, L_n = \ epsilon (R_n) + c \ cdot nwobeic- einige vorgegebene relative Kosten jeder Beobachtung. Die Aufgabe, die optimale Stoppzeit zu finden, kann als Suche nach einer Zufallsvariablen formuliert werden N.- deren Stoppzeit von den eingegebenen Beobachtungen abhängt (in einigen Literaturstellen wird der Wert N.als Markov-Moment bezeichnet ) und bei der der erwartete Verlust minimiert wird \ mathrm {E} (L_N).

Eintönige Probleme


Unter bestimmten Bedingungen kann bei solchen Problemen die optimale Stoppregel explizit ausgedrückt werden. Ein Beispiel ist das sogenannte monotone Problem. Das Kriterium für die Monotonie des Problems ist folgendes: Wenn der nVerlust in einem Schritt den L_nerwarteten Verlust im nächsten Schritt nicht überschreitet, wird dies in allen nachfolgenden Schritten durchgeführt. Mit anderen Worten, aus dem, was passiert ist, L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {empfangen} ~ n ~ \ text {frame})folgt, dass das Ereignis eintreten wird L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {empfangen} ~ n + 1 ~ \ text {frame}). Für monotone Probleme ist die sogenannte „kurzsichtige“ Stoppregel optimal: Stopp beim allerersten Schritt, bei dem die Bedingung erfüllt ist L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {empfangen} ~ n ~ \ text {frame}).

Angenommen, unsere Aufgabe ist eintönig. Nachdem L_nwir die Kurzsichtigkeitsregel in Bezug auf unsere Funktion geschrieben haben, müssen wir aufhören, wenn die folgende Bedingung erfüllt ist:

\ epsilon (R_n) - \ mathrm {E} (\ epsilon (R_ {n + 1}) | \ text {empfangen} ~ n ~ \ text {frame}) \ le c.

Das ist natürlich großartig, aber um diese Regel zu implementieren, müssen wir in der Lage sein, zur Laufzeit nicht nur die „Korrektheit“ des aktuellen Ergebnisses zu bewerten, sondern auch die erwartete Korrektheit des nächsten, was nicht so einfach ist (ganz zu schweigen davon, was wir von der Aufgabe gebieterisch gefordert haben) Monotonie). Können wir diese Regel irgendwie anwenden, ohne die „Richtigkeit“ des Ergebnisses direkt zu bewerten? .. Sie können versuchen, die linke Seite der Ungleichung von oben zu bewerten.

Wie kann die Kurzsichtigkeitsregel angewendet werden?


Nehmen wir an, dass eine Funktion \ epsilon (R_n)die Entfernung \ rho (R_n, R ^ *)vom kombinierten Erkennungsergebnis R_nzur „richtigen Antwort“ R ^ *ist und wie jede Entfernung, die sich selbst respektiert, die Dreiecksungleichung gilt. Der oben erwähnte Levenshtein-Abstand erfüllt die Dreiecksungleichung sowie eine einfache Funktion in Form von „richtig / falsch“ (wenn wir annehmen, dass \ rho (R_n, R ^ *)die richtige Antwort Null und die falsche Antwort konstant ist). Entsprechend der Dreiecksungleichung überschreitet die linke Seite unseres Stoppkriteriums nicht \ mathrm {E} (\ rho (R_n, R_ {n + 1}) | \ text {empfangen} ~ n ~ \ text {frame})den erwarteten Abstand vom aktuellen kombinierten Ergebnis zum nächsten.

Lassen Sie uns auch von unserem Algorithmus verlangen, dass Interframe-Kombinationserkennungsergebnisse kombiniert werden, damit der Abstand zwischen benachbarten kombinierten Ergebnissen im Laufe der Zeit nicht zunimmt (das heißt, wir betrachten die Folge kombinierter Ergebnisse als einen „konvergierenden“ Prozess, obwohl dies nicht unbedingt der richtigen Antwort entspricht). Wenn dann der erwartete Abstand vom aktuellen Ergebnis zum nächsten kleiner als der Schwellenwert c wird, werden zwei Dinge gleichzeitig erledigt. Erstens ist das kurzsichtige Stoppkriterium erfüllt (da sein linker Teil von oben durch denselben Abstand begrenzt ist). Und zweitens wird die Aufgabe eintönig: Im nächsten Schritt wird der erwartete Abstand zur nächsten Antwort nicht größer, was bedeutet, dass er weiterhin unter dem Schwellenwert c liegt und das kurzsichtige Kriterium wieder erfüllt wird.

Das heißt, wenn wir erwarten, dass die Abstände zwischen benachbarten kombinierten Ergebnissen im Durchschnitt nicht zunehmen, müssen wir aufhören, indem wir den erwarteten Abstand vom aktuellen Ergebnis zum nächsten abschneiden und so die optimale Regel annähern. Sie müssen verstehen, dass eine solche Regel nicht mehr optimal ist (da die „echte“ optimale Regel früher aufhören könnte), aber zumindest werden wir nicht früher als nötig aufhören.

Es gibt verschiedene Möglichkeiten, den erwarteten Abstand vom aktuellen kombinierten Ergebnis zum nächsten zu bewerten. Wenn beispielsweise der Levenshtein-Abstand als Metrik für die Ergebnisse verwendet wird, ist auch nur der Abstand zwischen den letzten beiden Ergebnissen des Layouts eine gute Annäherung. Ein anderer möglicher Ansatz besteht darin, eine mögliche nächste Beobachtung zu simulieren (z. B. basierend auf den bereits erhaltenen), "Leerlauf" -Kombinationen durchzuführen und den durchschnittlichen Abstand zu den erhaltenen Vorhersagen zu berechnen.


Feige. 3. Vergleich von Leistungsprofilen für mehrere Stoppregeln.

In Abb. 3 zeigt Leistungsprofile für mehrere Stoppregeln. N_K- die gleiche "oben erwähnte" "triviale" Regel - mit einem Schwellenwert für die Anzahl der verarbeiteten Beobachtungen. N_ {CX}undN_ {CR}- Schwellenwerte für die maximale Clustergröße derselben Frame-by-Frame- ( N_ {CX}) und kombinierten ( N_ {CR}) Ergebnisse. N.- die in diesem Dokument beschriebene Regel mit einer Schätzung des erwarteten Abstands zum nächsten Ergebnis unter Verwendung von Modellierungs- und Leerlaufkombinationen.

Anstelle einer Schlussfolgerung


Ziel des Artikels war es zu zeigen, dass es in Dokumentenerkennungssystemen auf Frames von Videosequenzen viele interessante Probleme gibt, nicht nur direkt aus der Bildverarbeitung, sondern auch aus anderen interessanten Bereichen. Obwohl wir das Problem gezeigt haben, die optimale Stoppzeit nur in ihrer einfachsten Form zu finden, beginnt der interessanteste Teil, wenn wir beispielsweise nicht nur die Anzahl der Frames im Modell, sondern auch die tatsächliche Ausführungszeit berücksichtigen möchten. Wir hoffen, Sie waren interessiert und bedanken uns für Ihre Aufmerksamkeit!

- Die

Veröffentlichung wurde auf der Grundlage des Artikels über optimale Stoppstrategien für die Texterkennung in einem Videostream von K. Bulatov, N. Razumnyi, VV Arlazarov, IJDAR 22, 303-314 (2019) 10.1007 / s10032-019-00333-0 erstellt .

Wenn der Leser an der Theorie der optimalen Stoppzeit interessiert ist, insbesondere am Nachweis der Optimalität der Kurzsichtigkeitsregel für monotone Probleme, empfehlen wir dringend den veröffentlichten Kurs Optimales Stoppen und Anwendungen (Thomas Ferguson, UCLA).

Einige andere interessante Quellen zu diesem Thema:
Chow YS, Siegmund D. Große Erwartungen: Die Theorie des optimalen Stopps , Houghton Mifflin, 1971, 139 S.
Berezovsky B.A., Gnedin A.V. The Best Choice Problem , Science, 1984, 200 Seiten.
Ferguson TS, Hardwick TS Stoppregeln für das Korrekturlesen , Journal of Applied Probability., V. 26, N. 2, 1989, p. 303-313.
Ferguson TSMathematische Statistik: ein entscheidungstheoretischer Ansatz . Academic Press, 1967, 396 S.

More articles:


All Articles