Get best of the week

¿Cuándo detener el proceso de reconocimiento de secuencia de video?

Hola habr Hoy nos gustaría contarles sobre una tarea muy interesante que hemos estado abordando desde el comienzo de nuestra investigación sobre el reconocimiento de documentos en la transmisión de video: el problema de encontrar el tiempo de detención óptimo.



Higo. 1. Imágenes de campos de texto de documentos ID en cuadros de una secuencia de video.

Como mucha gente sabe, el producto principal de Smart Engines es un sistema de reconocimiento de documentos de identidad, Smart IDReader, aplicable tanto en servidores y equipos de escritorio como en dispositivos móviles. En un gran número de casos, el reconocimiento de documentos en un teléfono móvil debe realizarse fuera de línea, a menudo no podemos controlar las condiciones y la calidad del disparo, y el costo de un error de reconocimiento, especialmente al reconocer documentos de identificación, es muy alto. Al mismo tiempo, tenemos una ventaja importante: no podemos usar una sola imagen, sino una secuencia de fotogramas capturados (ver Fig. 1), para aumentar la precisión del reconocimiento.

Cuando se usan múltiples imágenes de campos de texto, surgen dos preguntas importantes. La primera pregunta es cómo combinar observaciones? ¿Vale la pena combinar los cuadros de origen para obtener una imagen, una "calidad" más alta, o elegir un cuadro mejor (entonces, ¿dónde está la garantía de que habrá un cuadro en el que todo está bien?) O, tal vez, primero reconozca el campo en cada cuadro, y luego seleccione el resultado más “seguro” (¿con qué criterio?), O combine los resultados de reconocimiento cuadro por cuadro, etc. Nos adherimos al último enfoque (reconocimiento cuadro por cuadro con la combinación de resultados entre cuadros), pero el enfoque óptimo puede diferir tanto según el motor de reconocimiento utilizado como otros parámetros de la tarea.

La segunda pregunta que surge independientemente de la primera es ¿cuándo detener el proceso de observación? En otras palabras, ¿con qué criterio decide que el proceso de captura se puede detener y el resultado acumulado por el momento actual se reconoce como final? ¿Cómo comparar tales criterios entre sí y hay uno óptimo?

Se trata del problema de encontrar el momento de detener el proceso de observación que se discutirá en este artículo.

Lo que queremos lograr


Reconocer una cadena de texto en una secuencia de video, en la que después de capturar otra observación, el resultado mejora de una forma u otra, puede considerarse como un algoritmo Anytime , un algoritmo con un resultado que mejora secuencialmente, cuyo cálculo se puede detener en cualquier momento. Una herramienta conveniente para visualizar la calidad de tales algoritmos son los " Perfiles de rendimiento esperados ": gráficos de la dependencia de la calidad del resultado, medido de una forma u otra, en el tiempo de cálculo.


Higo. 2. Perfiles de eficiencia de reconocimiento de línea de texto en una secuencia de video (menor es mejor). La línea punteada negra es de calidad cuadro por cuadro, la línea continua negra es el resultado de la combinación entre cuadros. La línea naranja es lo que queremos de la regla de parada "buena".

En la Fig. La Figura 2 muestra los perfiles de eficiencia para reconocer una cadena de texto: la dependencia del error promedio (en términos de la distancia de Levenshtein a la respuesta correcta) del número de cuadros procesados. Se obtuvieron gráficos negros usando Tesseract v4.0.0 en los campos de texto del conjunto de datos MIDV-500 . Se puede ver que el uso de la combinación entre cuadros de resultados de reconocimiento permite alcanzar un valor de error mucho más bajo (que, en general, no es sorprendente).

¿Qué queremos de una regla de parada "buena"? Como esperamos, razonablemente, que cuanto más tiempo continuemos el proceso, mejor tendremos un resultado promedio, sería excelente si la regla de detención en algunas secuencias de video se considerara "más larga", si hubiera una posibilidad de minimizar el error, y en algunas se detendría sería anterior si el resultado ya es bueno, o no hay posibilidad de mejorarlo. Debido a esto, con la misma calidad promedio del resultado combinado, en promedio, se pueden lograr menos cuadros procesados, y viceversa, con el mismo número promedio de cuadros, el resultado promedio es mejor. En otras palabras, es importante comprender que la regla de detención no se trata solo de minimizar el tiempo, sino también de maximizar la calidad, por el mismo tiempo (promedio).

Busquemos la regla de detención de la siguiente forma: después de procesar el siguiente cuadro y recibir el resultado de reconocimiento combinado, consideramos algunas características y cortamos su umbral; si, por ejemplo, está por debajo del umbral, nos detenemos, de lo contrario continuamos. Luego, con una regla de detención fija, pero variando el umbral, también obtendremos un perfil de eficiencia, con la única excepción de que el eje promedio no se ubicará en el eje horizontal, sino el promedio (vea el gráfico naranja en la Fig. 2). Cuanto más bajo es este gráfico, más eficaz podemos considerar la regla de detención. Podemos considerar que el perfil inicial del "resultado combinado" es el perfil de la efectividad de la regla de detención trivial, en la que simplemente reducimos el número de tramas procesadas por el umbral.

Lo que dice la teoría


En estadística matemática, los problemas de encontrar el tiempo de parada óptimo son bien conocidos y han sido investigados durante mucho tiempo. Quizás las tareas más famosas en esta clase son la tarea de una novia exigente (ella estuvo muy involucrada, por ejemplo, Boris Abramovich Berezovsky), la tarea de vender una casa y otras. Sin profundizar en la teoría, planteemos brevemente el problema del reconocimiento en secuencias de video como el problema óptimo de detención.

Denote el error del resultado combinado en el nortei-ésimo paso del proceso como \ epsilon (R_n). Suponemos que si nos detenemos en el nortei-ésimo paso, incurriremos en una pérdida de la siguiente forma :, L_n = \ epsilon (R_n) + c \ cdot ndondeC- algún costo relativo predeterminado de cada observación. La tarea de encontrar el tiempo de detención óptimo puede formularse como una búsqueda de una variable aleatoria norte: el tiempo de detención, cuya distribución depende de las observaciones de entrada (en alguna literatura, el valor nortese denomina momento de Markov ), y en el que se minimiza la pérdida esperada \ mathrm {E} (L_N).

Problemas monótonos


Bajo ciertas condiciones, en tales problemas, la regla de detención óptima puede expresarse explícitamente. Un ejemplo es el llamado problema monótono. El criterio para la monotonicidad del problema es este: si en algún paso la nortepérdida L_nno excede la pérdida esperada en el siguiente paso, esto se realizará en todos los pasos posteriores. En otras palabras, por lo que sucedió, el evento L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {recibido} ~ n ~ \ text {frames})sigue que el evento sucederá L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {recibido} ~ n + 1 ~ \ text {frames}). Para problemas monótonos, la llamada regla de detención "miope" es óptima: deténgase en el primer paso donde se cumple la condición L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {recibido} ~ n ~ \ text {frames}).

Supongamos que nuestra tarea es monótona. Una vez escrita la regla miope en términos de nuestra función, L_nobtenemos que debemos detenernos cuando se cumple la siguiente condición:

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

Esto, por supuesto, es excelente, pero para implementar dicha regla, necesitamos poder evaluar en tiempo de ejecución no solo la "corrección" del resultado actual, sino también la corrección esperada del próximo, que no es tan simple (sin mencionar lo que exigimos imperiosamente de la tarea monotonía). ¿Podemos aplicar esta regla de alguna manera sin evaluar directamente la "corrección" del resultado? ... Puede intentar evaluar el lado izquierdo de la desigualdad desde arriba.

¿Cómo se puede usar la regla miope?


Supongamos que una función \ epsilon (R_n)es la distancia \ rho (R_n, R ^ *)desde el resultado de reconocimiento combinado R_nhasta la "respuesta correcta" R ^ *, y como cualquier distancia que se respete a sí misma, la desigualdad del triángulo se mantiene. La distancia de Levenshtein mencionada anteriormente satisface la desigualdad del triángulo, así como una función simple en forma de "correcto / incorrecto" (si suponemos que \ rho (R_n, R ^ *)para la respuesta correcta es cero y para la respuesta incorrecta es constante). Según la desigualdad del triángulo, el lado izquierdo de nuestro criterio de detención no excede \ mathrm {E} (\ rho (R_n, R_ {n + 1}) | \ text {recibido} ~ n ~ \ text {cuadros}): la distancia esperada desde el resultado combinado actual hasta el siguiente.

Exigamos también de nuestro algoritmo resultados de reconocimiento de combinación entre cuadros, de modo que, en promedio, la distancia entre resultados combinados adyacentes no aumente con el tiempo (es decir, consideraremos la secuencia de resultados combinados como un proceso "convergente", aunque no necesariamente a la respuesta correcta). Entonces, si la distancia esperada desde el resultado actual hasta el siguiente es menor que el umbral c, se hacen dos cosas a la vez. En primer lugar, se cumple el criterio de detención miope (ya que su parte izquierda está limitada desde arriba por esta misma distancia). Y en segundo lugar, la tarea se vuelve monótona: en el siguiente paso, la distancia esperada a la siguiente respuesta no aumentará, lo que significa que seguirá siendo inferior al umbral c, y el criterio miope se cumplirá nuevamente.

Esto significa que si esperamos que las distancias entre los resultados combinados adyacentes no aumenten en promedio, entonces debemos detenernos cortando la distancia esperada del resultado actual al siguiente, aproximando así la regla óptima. Debe comprender que dicha regla ya no es óptima (ya que la regla óptima "real" podría detenerse antes), pero al menos no lo haremos antes de lo necesario.

Hay varias formas de evaluar la distancia esperada desde el resultado combinado actual hasta el siguiente. Por ejemplo, si la distancia de Levenshtein se usa como la métrica sobre los resultados, incluso solo la distancia entre los dos últimos resultados del diseño es una buena aproximación. Otro enfoque posible es simular una posible próxima observación (por ejemplo, basada en las ya obtenidas), realizar combinaciones "inactivas" y calcular la distancia promedio a las predicciones obtenidas.


Higo. 3. Comparación de perfiles de rendimiento para varias reglas de detención.

En la Fig. 3 muestra perfiles de rendimiento para varias reglas de detención. N_K- la misma regla "trivial" "mencionada anteriormente" - con un umbral límite del número de observaciones procesadas. N_ {CX}yN_ {CR}- límites de umbral del tamaño máximo del clúster de los mismos resultados cuadro por cuadro ( N_ {CX}) y combinado ( N_ {CR}). norte- la regla descrita en este documento, con una estimación de la distancia esperada al siguiente resultado usando modelos y combinaciones "inactivas".

En lugar de una conclusión


El objetivo del artículo era mostrar que en los sistemas de reconocimiento de documentos en cuadros de secuencias de video hay muchos problemas interesantes, no solo directamente desde la visión por computadora, sino también desde otras áreas interesantes. Aunque mostramos el problema de encontrar el tiempo de detención óptimo solo en su forma más simple, la parte más interesante comienza cuando, por ejemplo, queremos tener en cuenta no solo el número de cuadros en el modelo, sino también el tiempo de ejecución real. Esperamos que haya estado interesado, y gracias por su atención.

- La

publicación se preparó sobre la base del artículo sobre estrategias de detención óptimas para el reconocimiento de texto en una transmisión de video, K. Bulatov, N. Razumnyi, VV Arlazarov, IJDAR 22, 303-314 (2019) 10.1007 / s10032-019-00333-0 .

Si el lector está interesado en la teoría del tiempo de detención óptimo, en particular, la prueba de la optimización de la regla miope para problemas monótonos, recomendamos encarecidamente el curso publicado Optimal Stopping and Applications (Thomas Ferguson, UCLA).

Algunas fuentes más interesantes sobre este tema:
Chow YS, Siegmund D. Grandes expectativas: La teoría de la parada óptima , Houghton Mifflin, 1971, 139 p.
Berezovsky B.A., Gnedin A.V. The Best Choice Problem , Science, 1984, 200 págs.
Ferguson TS, Hardwick TS Reglas de detención para la corrección de pruebas , Journal of Applied Probability., V. 26, N. 2, 1989, p. 303-313.
Ferguson TSEstadística matemática: un enfoque teórico de decisión . Prensa académica, 1967, 396 p.

More articles:


All Articles