😅 🖕🏻 🤦🏼 Quando parar o processo de reconhecimento de sequência de vídeo? 🕞 👊🏼 🤘🏿

Oi Habr! Hoje, gostaríamos de falar sobre um problema muito interessante com o qual estamos lidando desde o início de nossa pesquisa sobre reconhecimento de documentos no fluxo de vídeo - o problema de encontrar o tempo de parada ideal.

FIG. 1. Imagens de campos de texto de documentos de identificação em quadros de uma sequência de vídeo.

Como muitas pessoas sabem, o principal produto dos Smart Engines é um sistema de reconhecimento de documentos de identidade, o Smart IDReader, aplicável em servidores e desktops, e em dispositivos móveis. Em um grande número de casos, o reconhecimento de documentos em um telefone celular deve ocorrer offline, geralmente não podemos controlar as condições e a qualidade da filmagem, e o custo de erros de reconhecimento, especialmente no reconhecimento de documentos de identificação, é muito alto. Ao mesmo tempo, temos uma vantagem importante - podemos usar não uma imagem, mas uma sequência de quadros capturados (veja a Fig. 1), para aumentar a precisão do reconhecimento.

Ao usar várias imagens de campos de texto, duas questões importantes surgem. A primeira pergunta é como combinar observações? Vale a pena combinar os quadros de origem para obter uma imagem, uma "qualidade" mais alta ou escolher um quadro melhor (então onde está a garantia de que haverá um quadro no qual tudo esteja bem)? Ou, talvez, primeiro reconheça o campo em cada quadro e, em seguida, selecione o resultado mais "confiante" (por quais critérios?) Ou combine resultados de reconhecimento quadro a quadro, etc. Aderimos à última abordagem (reconhecimento quadro a quadro com combinação de resultados entre quadros), mas a abordagem ideal pode diferir, dependendo do mecanismo de reconhecimento usado e de outros parâmetros da tarefa.

A segunda questão que surge independentemente da primeira é quando parar o processo de observação? Em outras palavras, por qual critério você decide que o processo de captura pode ser interrompido e o resultado acumulado no momento atual é reconhecido como final? Como comparar esses critérios entre si e existe um ótimo?

Trata-se do problema de encontrar o momento de interromper o processo de observação que será discutido neste artigo.

O que queremos alcançar

O reconhecimento de uma sequência de texto em uma sequência de vídeo, na qual após a captura de outra observação, o resultado melhora de uma maneira ou de outra, pode ser considerado como um algoritmo a qualquer momento - um algoritmo com um resultado que melhora sequencialmente, cujo cálculo pode ser interrompido a qualquer momento. Uma ferramenta conveniente para visualizar a qualidade de tais algoritmos é o “ Perfil de desempenho esperado ” - gráficos da dependência da qualidade do resultado, medido de uma forma ou de outra, no tempo de cálculo.

FIG. 2. Perfis de eficiência de reconhecimento de linha de texto em uma sequência de vídeo (quanto menor, melhor). A linha pontilhada preta é de qualidade quadro a quadro, a linha sólida preta é o resultado da combinação entre quadros. A linha laranja é o que queremos da regra de parada “boa”.

Na Fig. A Figura 2 mostra os perfis de eficiência para o reconhecimento de uma sequência de texto - a dependência do erro médio (em termos da distância de Levenshtein à resposta correta) no número de quadros processados. Gráficos em preto foram obtidos usando o Tesseract v4.0.0 nos campos de texto do conjunto de dados MIDV-500 . Pode-se observar que o uso da combinação entre quadros de resultados de reconhecimento permite obter um valor de erro muito menor (o que, em geral, não é surpreendente).

O que queremos de uma regra de parada "boa"? Como esperamos, razoavelmente, que quanto mais continuarmos o processo, melhor será o resultado médio, seria ótimo se a regra para parar em algumas sequências de vídeo consideradas "mais longas", se houvesse uma chance de minimizar o erro e, em algumas, ele parasse seria mais cedo se o resultado já estiver bom ou se não houver chance de melhorá-lo. Devido a isso, com a mesma qualidade média do resultado combinado, em média, menos quadros processados podem ser alcançados e vice-versa, com o mesmo número médio de quadros, o resultado médio é melhor. Em outras palavras, é importante entender que a regra de parada não é apenas minimizar o tempo, mas também maximizar a qualidade, pelo mesmo tempo (médio).

Vamos procurar a regra de parada da seguinte forma: depois de processar o próximo quadro e receber o resultado do reconhecimento combinado, consideramos alguma característica e cortamos seu limite - se, digamos, estiver abaixo do limite, paramos, caso contrário continuamos. Então, com uma regra de parada fixa, mas variando o limite, também obteremos um perfil de eficiência, com a exceção de que o eixo horizontal não conterá o número exato de quadros processados, mas a média (veja o gráfico laranja na Fig. 2). Quanto menor esse gráfico, mais eficaz podemos considerar a regra de parada. Podemos considerar o perfil inicial do “resultado combinado” como o perfil da efetividade da regra trivial de parada - na qual simplesmente cortamos o número de quadros processados pelo limite.

O que a teoria diz

Nas estatísticas matemáticas, os problemas de encontrar o tempo ideal de parada são bem conhecidos e há muito tempo são investigados. Talvez as tarefas mais famosas desta classe sejam as de uma noiva exigente (ela estava muito envolvida, por exemplo, Boris Abramovich Berezovsky), a tarefa de vender uma casa e outras. Sem aprofundar a teoria, vamos colocar brevemente o problema de reconhecimento nas sequências de vídeo como o problema ideal de parada.

Denotamos o erro do resultado combinado na

i - ésima etapa do processo como $\ epsilon (R_n)$ . Assumimos que, se pararmos na

i - ésima etapa, sofreremos uma perda da seguinte forma :, $L_n = \ epsilon (R_n) + c \ cdot n$ em que

- algum custo relativo predeterminado de cada observação. A tarefa de encontrar o tempo de parada ideal pode ser formulada como uma busca por uma variável aleatória

- o tempo de parada, cuja distribuição depende das observações de entrada (em alguma literatura, o valor

é chamado de momento de Markov ) e em que a perda esperada é minimizada $\ mathrm {E} (L_N)$ .

Problemas monótonos

Sob certas condições, nesses problemas, a regra de parada ideal pode ser expressa explicitamente. Um exemplo é o chamado problema monótono. O critério para a monotonicidade do problema é o seguinte: se em alguma etapa a

perda

não exceder a perda esperada na próxima etapa, isso será realizado em todas as etapas subsequentes. Em outras palavras, pelo que aconteceu, o evento $L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {received} ~ n ~ \ text {frames})$ segue que o evento acontecerá $L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {received} ~ n + 1 ~ \ text {frames})$ . Para problemas monótonos, a chamada regra de parada míope é ideal: pare na primeira etapa em que a condição for atendida $L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {received} ~ n ~ \ text {frames})$ .

Suponha que nossa tarefa seja monótona. Depois de escrever a regra míope em termos de nossa função, L_n

concluímos que precisamos parar quando a seguinte condição for atendida:

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

É claro que isso é ótimo, mas para implementar essa regra, precisamos avaliar em tempo de execução não apenas a “correção” do resultado atual, mas também a correção esperada do próximo, o que não é tão simples (sem mencionar o que exigimos imperiosamente da tarefa monotonia). De alguma forma, podemos aplicar essa regra sem avaliar diretamente a “correção” do resultado? ... Você pode tentar avaliar o lado esquerdo da desigualdade de cima para baixo.

Como a regra míope pode ser usada?

Vamos supor que uma função $\ epsilon (R_n)$ seja a distância $\ rho (R_n, R ^ *)$ do resultado do reconhecimento combinado R_n

até a "resposta correta" R ^ *

e, como qualquer distância que se respeite, a desigualdade do triângulo se mantém. A distância de Levenshtein mencionada acima satisfaz a desigualdade do triângulo, bem como uma função simples na forma de “certo / errado” (se assumirmos que $\ rho (R_n, R ^ *)$ para a resposta correta é zero e para a resposta errada é constante). De acordo com a desigualdade do triângulo, o lado esquerdo do nosso critério de parada não excede $\ mathrm {E} (\ rho (R_n, R_ {n + 1}) | \ text {received} ~ n ~ \ text {frames})$ - a distância esperada do resultado combinado atual para o próximo.

Também vamos exigir do nosso algoritmo que combine resultados de reconhecimento entre quadros, para que, em média, a distância entre resultados combinados adjacentes não aumente ao longo do tempo (ou seja, consideraremos a sequência de resultados combinados como um processo "convergente", embora não necessariamente para a resposta correta). Então, se a distância esperada do resultado atual para o próximo for menor que o limite c, duas coisas serão feitas ao mesmo tempo. Em primeiro lugar, o critério de parada míope é cumprido (já que sua parte esquerda é delimitada acima por essa mesma distância). E, em segundo lugar, a tarefa se torna monótona: na próxima etapa, a distância esperada para a próxima resposta não aumentará, o que significa que continuará sendo menor que o limite c, e o critério míope será preenchido novamente.

Isso significa que, se esperamos que as distâncias entre os resultados combinados adjacentes não aumentem, em média, precisamos parar pelo limite de limiar da distância esperada do resultado atual para o próximo, aproximando-se assim da regra ideal. Você precisa entender que essa regra não é mais ideal (já que a regra ideal "real" pode parar mais cedo), mas pelo menos não vamos parar antes do necessário.

Existem várias maneiras de avaliar a distância esperada do resultado combinado atual para o próximo. Por exemplo, se a distância de Levenshtein for usada como métrica sobre os resultados, mesmo a distância entre os dois últimos resultados do layout será uma boa aproximação. Outra abordagem possível é simular uma possível observação seguinte (por exemplo, com base nas já obtidas), realizar combinações "inativas" e calcular a distância média às previsões obtidas.

FIG. 3. Comparação de perfis de desempenho para várias regras de parada.

Na Fig. 3 mostra perfis de desempenho para várias regras de parada. N_K

- a mesma regra "mencionada acima" e "trivial" - com um limite de limiar do número de observações processadas. $N_ {CX}$ e $N_ {CR}$ - limites limiares do tamanho máximo do cluster dos mesmos resultados quadro a quadro ( $N_ {CX}$ ) e combinados ( $N_ {CR}$ ).

- a regra descrita neste documento, com uma estimativa da distância esperada para o próximo resultado usando combinações de modelagem e "inatividade".

Em vez de uma conclusão

O objetivo do artigo era mostrar que nos sistemas de reconhecimento de documentos em quadros de sequências de vídeo existem muitos problemas interessantes, não apenas diretamente da visão computacional, mas também de outras áreas interessantes. Embora tenhamos mostrado o problema de encontrar o tempo de parada ideal apenas na sua forma mais simples, a parte mais interessante começa quando, por exemplo, queremos levar em consideração não apenas o número de quadros no modelo, mas também o tempo de execução real. Esperamos que você esteja interessado e obrigado por sua atenção!

- A

publicação foi preparada com base no artigo Sobre estratégias de parada ideais para reconhecimento de texto em um fluxo de vídeo, K. Bulatov, N. Razumnyi, VV Arlazarov, IJDAR 22, 303-314 (2019) 10.1007 / s10032-019-00333-0 .

Se o leitor estiver interessado na teoria do tempo ideal de parada, em particular a prova da otimização da regra míope para problemas monótonos, recomendamos o curso publicado de Ótima parada e aplicações (Thomas Ferguson, UCLA).

Algumas fontes mais interessantes sobre esse assunto:
Chow YS, Siegmund D. Grandes expectativas: A teoria da parada ideal , Houghton Mifflin, 1971, 139 p.
Berezovsky B.A., Gnedin A.V. O Melhor Problema de Escolha , Science, 1984, 200 pp.
Ferguson TS, Hardwick TS Regras de parada para revisão , Journal of Applied Probability., V. 26, N. 2, 1989, p. 303-313.
Ferguson TSEstatística matemática: uma abordagem teórica da decisão . Academic press, 1967, p. 396.

Quando parar o processo de reconhecimento de sequência de vídeo?

O que queremos alcançar

O que a teoria diz

Problemas monótonos

Como a regra míope pode ser usada?

Em vez de uma conclusão

More articles: