Temos certeza de que hoje não existe um leitor Habr que não esteja familiarizado com os códigos QR. Esses códigos de barras bidimensionais estão por toda parte. É lógico que no mundo existem muitas ferramentas que permitem adicionar códigos QR ao seu projeto com algum grau de eficiência. O ponto principal é que essa eficiência mencionada depende diretamente da qualidade da ferramenta usada para reconhecer os códigos QR. E aqui vem o plug clássico: você pode resolver o problema (muito) bem e (muito) caro, ou pode de graça e de alguma forma. É possível modificar o free para que ele resolva bem o problema? Se estiver interessado, olhe embaixo do gato.O reconhecimento de um código QR em uma fotografia é uma tarefa bem posta de visão de máquina. Primeiramente, na tarefa, um objeto é investigado, que foi originalmente projetado especialmente para reconhecimento "conveniente". Em segundo lugar, a tarefa em si é dividida em várias subtarefas compreensíveis independentes: localização do código QR, orientação do código QR e decodificação direta do código QR. Acontece que o domínio público tem boas bibliotecas que podem resolver os dois últimos problemas: orientação e decodificação de um código QR. Um problema: para decodificação de alta qualidade, essas bibliotecas esperam que uma boa imagem binária diretamente do código de barras seja inserida. Por outro lado, pouca atenção é dada à tarefa de localização do código de barras na imagem.Em nossa experiência, quanto mais preciso você localizar um objeto de reconhecimento, mais fácil será escolher as ferramentas corretas de pré-processamento e, de fato, reconhecê-lo. Portanto, se você deseja melhorar a qualidade do reconhecimento de códigos QR em seu projeto, comece com a modernização de métodos para localizar códigos QR. De fato, mesmo que mais tarde você precise binarizar uma imagem, é muito mais eficiente (do ponto de vista qualitativo e computacional) binarizar uma região com um código de barras do que toda a imagem original.Neste artigo, mostraremos como melhorar facilmente a qualidade da localização de códigos QR usando métodos clássicos de processamento de imagem, além de fornecer características numéricas da eficácia do algoritmo proposto.Falaremos sobre a maneira original de localizar códigos QR nas imagens, usando o método Viola e Jones modificado como base.Nota informativa sobre o tópico do artigo
Nesta seção, descrevemos os principais recursos do código QR que são usados para construir o método de localização, bem como uma breve descrição da versão original do método Viola e Jones.Código QR
O código QR (abreviação de Código de Resposta Rápida) é um código de barras bidimensional desenvolvido no Japão em meados dos anos 90 para a indústria automotiva. Devido à capacidade de ler rapidamente e maior capacidade em comparação com códigos de barras lineares, o sistema de código QR tornou-se popular em todo o mundo em várias áreas da vida.Ao contrário dos códigos de barras lineares padrão, que geralmente são digitalizados por hardware, um código QR é frequentemente digitalizado por uma câmera. A estrutura do código QR está totalmente descrita na ISO / IEC 18004 (A norma ISO / IEC 18004). Para criar um algoritmo de reconhecimento robusto para essas imagens, o código QR possui alguns pontos de referência que formam um padrão de função: três quadrados nos cantos da imagem do código de barras (chamados padrões de localização) e quadrados menores de sincronização em toda a imagem do código de barras (chamados padrões de alinhamento) . Esses pontos permitem normalizar o tamanho da imagem e sua orientação.
FIG. Estrutura de código QR
Embora visualmente todos os códigos QR sejam semelhantes entre si, cópias diferentes de códigos QR, dependendo da quantidade de dados codificados, podem ter um layout diferente de elementos internos. Além disso, os chamados códigos QR de designer são muito populares, nos quais, em vez da parte de informações adicionais que garantem o reconhecimento de alta qualidade do código de barras, são utilizados elementos gráficos de terceiros (logotipos, emblemas, inscrições etc.). Todos esses recursos dos códigos QR devem ser levados em consideração ao criar métodos para localização e reconhecimento de códigos QR.
FIG. Diferentes opções válidas de código QR
Método Viola e Jones
Apenas os preguiçosos de Habré ainda não escreveram sobre o método de Viola e Jones. Até nós do nosso bloco fizemos isso várias vezes (por exemplo, aqui , aqui ou aqui ). E ainda assim, consideramos necessário, muito brevemente, literalmente em dois parágrafos, dizer o que é.O método de detecção de objetos Viola e Jones foi desenvolvido para procurar rostos em uma imagem em tempo real. Este método reduz o problema de detecção ao problema de classificação binária em cada ponto da imagem, ou seja, para cada região retangular da imagem tirada com todos os tipos de mudanças e escalas, a hipótese da presença do objeto desejado na região é verificada usando um classificador pré-treinado.Como espaço de recurso, o método Viola e Jones usa recursos retangulares de Haar, cujo valor é calculado como a diferença entre as somas de brilho dos pixels das áreas da imagem dentro de retângulos adjacentes. Para calcular efetivamente o valor dos recursos de Haar, é usada uma imagem integrada, também conhecida na literatura sob o termo tabela de área somada. Um binário “fraco” classificador h ( x ): × → {-1, + 1}, geralmente apresentado como uma árvore de reconhecimento com um ramo:
onde θ e p- o valor limite do atributo e a paridade do classificador, respectivamente. Em seguida, usando o método de aprendizado de máquina AdaBoost, um classificador "forte" é construído como uma superposição linear dos classificadores "fracos" acima. A alta velocidade do método Viola e Jones é garantida pelo uso de uma cascata de classificadores "fortes", que permite localizar regiões de imagem "vazias" (sem objetos) para um pequeno número de cálculos.Algoritmo de detecção de código QR
Ao construir um método para localizar um código QR, contamos com os seguintes recursos da tarefa. Primeiro, o método desenvolvido deve ter alto desempenho para uso em sistemas de reconhecimento que operam em tempo real. Em segundo lugar, o método deve ser resistente à distorção permitida do código de barras na imagem. Em terceiro lugar, o método deve levar em consideração toda a variabilidade existente dos códigos QR.Como mencionado acima, escolhemos o método de Viola e Jones como o método fundamental. Esse método se comprovou em várias tarefas de pesquisa de objetos rígidos, enquanto o método fornece o desempenho necessário. Mas na versão original, o método Viola e Jones não pode ser usado pelos seguintes motivos:- no método clássico de Viola e Jones, uma família de atributos de Haar é usada para "enfatizar" os recursos texturais do objeto e, no nosso caso, embora o código QR seja composto por barras pretas e brancas, sua distribuição é muito diferente do código de barras para o código de barras;
- o método clássico de Viola e Jones é projetado para o mesmo tipo de detecção de objetos em uma determinada orientação, o que também não é observado em nossa tarefa.
Para que o método Viola e Jones possa ser aplicado para resolver o problema, usamos a família original de recursos de limite e um classificador de alto nível na forma de uma árvore de decisão. A primeira modificação permitirá focar nas características de contorno do objeto estudado, e não na textura. A segunda modificação permitirá criar um único classificador que pode detectar objetos variáveis. A seguir, falaremos um pouco mais sobre cada modificação.Sinais de gradiente de Haar.
Para construir um detector eficaz de códigos QR, usamos uma família especial de recursos de gradiente [1]. Esses sinais são sinais retangulares de Haar, calculados no topo do mapa de limites direcionados, o que pode melhorar significativamente seu poder generalizador.O mapa de limites direcionais é uma imagem do módulo de gradiente, que também leva em conta a direção preferida do gradiente no ponto ( x , y ), definida como a discretização do ângulo da borda nas direções horizontal, vertical, + 45 ° e –45 °. Para construir um detector de código QR, usamos dois tipos de mapa de fronteira direcional: um mapa de fronteira reta e um mapa de face diagonal.Deixe a imagem original f ( x ,y ) Em seguida, pode-se calcular o valor aproximado do derivado ao longo das direcções verticais e horizontais com o operador de Sobel:
Além disso, utilizando g x e g y , é possível calcular a direcção da inclinação em cada ponto da imagem: O
mapa de bordas retas contém fronteiras essencialmente horizontais e verticais e é calculado como se segue:
Mapa bordas diagonais contêm principalmente bordas ao longo das diagonais e é calculado da seguinte forma:
No topo do mapa construído de bordas direcionadas (diagonal ou reta), são calculados sinais retangulares de Haar. Diferentemente dos recursos clássicos de Haar, esses recursos de limite generalizam objetos de poço que contêm um grande número de limites.
FIG. Ilustração de um mapa de bordas direcionadas: (a) a imagem original de um código QR, (b) um mapa de bordas retas, (c) uma imagem de um código QR girado (d) um mapa das bordas diagonais de um código QR girado
A árvore decisiva dos classificadores fortes
A árvore dos classificadores fortes [2] é um tipo de árvore de decisão binária: o nó da árvore é um classificador forte, na extremidade direita da qual existem sub-janelas supostamente contendo o objeto e à esquerda - aquelas que não foram reconhecidas como objeto, respectivamente. A resposta final é dada apenas em folhas. O classificador em cascata clássico descrito no trabalho original de Viola e Jones é, de fato, um classificador em árvore contendo apenas um resultado "positivo" (folha) e muitos resultados "negativos".Em [2], é mostrado que qualquer caminho da raiz até o nó mais baixo do classificador em árvore pode ser representado como uma cascata na qual os classificadores fortes individuais entram com uma resposta invertida. Graças a isso, é possível construir um algoritmo de aprendizado para o classificador em árvore, que usa o procedimento de treinamento do classificador em cascata clássico para ensinar caminhos individuais.O classificador em árvore permite treinar classificadores que são mais eficazes em termos de integridade para objetos variáveis em comparação com classificadores em cascata clássicos.Resultados experimentais
Como parte de um experimento para avaliar a eficácia do método de localização de código de barras proposto neste artigo, foi preparado um conjunto de imagens de código de barras consistindo em 264 imagens. O tamanho físico das imagens era de cerca de 1 MPix. Cada imagem contém apenas um código QR em uma orientação arbitrária, a área do código de barras era pelo menos 10% da área total da imagem. A figura abaixo mostra exemplos de imagens do conjunto montado.
FIG. Exemplos de imagens do conjunto de imagens de código de barras montado
O conjunto de imagens preparado foi dividido em um conjunto de treinamento e um conjunto de teste. O tamanho da amostra de treinamento foi de 88 imagens, o tamanho da amostra de teste foi de 176 imagens.O conjunto de treinamento foi usado tanto na preparação de exemplos positivos quanto na preparação de exemplos negativos. Como o número inicial de exemplos positivos era pequeno, usamos a tecnologia de aumento de dados [3]. Em particular, aplicamos a rotação ao redor do centro do código de barras em incrementos de 15⁰. Após o aumento, o número de exemplos positivos foi 2088 exemplos.Usando os mesmos exemplos positivos e negativos, treinamos três detectores de código QR: um classificador em cascata clássico com recursos padrão do Haar, um classificador em cascata clássico com recursos de limite e um classificador em árvore com recursos de limite. O primeiro classificador em cascata consistia em 12 níveis e continha um total de 58 atributos. O segundo classificador em cascata consistia em 8 níveis e continha um total de 39 atributos. O classificador de árvore treinado consistia em 39 vértices, continha um total de 110 caracteres, e o caminho máximo do topo para a folha era 9. Abaixo está um diagrama do classificador de árvore treinado.
FIG. Esquema do classificador de árvore treinado
Para avaliar a qualidade dos detectores construídos de códigos QR, usamos o módulo de decodificação de código de barras da biblioteca de visão computacional de código aberto OpenCV. No conjunto de imagens de teste preparado (que, como mencionado acima, consistia em 176 imagens), lançamos o módulo de decodificação sem nenhum pré-processamento especial, bem como após uma pesquisa preliminar de códigos QR usando detectores treinados. Abaixo estão os resultados da decodificação do código de barras:A tabela mostra que a localização preliminar do código QR usando o método descrito pode melhorar significativamente a qualidade da decodificação de código de barras (o número de erros de decodificação diminuiu 44%). Além disso, os resultados também demonstram que a aplicação do método original de Viola e Jones (com recursos clássicos de Haar e um classificador em cascata) não é eficaz na tarefa de localizar códigos QR.Agora vamos ver com que precisão cada classificador localiza o código de barras. A figura da esquerda para a direita mostra os resultados da detecção do mesmo código de barras com um classificador em cascata clássico com recursos padrão do Haar, um classificador em cascata clássico com recursos de limite e um classificador em árvore com recursos de limite. Pode-se observar que o classificador em árvore fornece a melhor precisão da localização do código de barras, levando em consideração a variabilidade dos códigos QR.
FIG. Ilustração do trabalho de detectores treinados na mesma imagem
Conclusão
Hoje, os códigos QR são usados em várias áreas da vida: no setor de publicidade para codificação de URLs, no segmento estadual como parte de serviços eletrônicos, etc. Apesar da distribuição extremamente alta desses códigos de barras, as bibliotecas de código aberto existentes se concentram no processo de decodificação, não no problema de localização. Mas, para ser sincero, o verdadeiro objetivo deste artigo não era tanto descrever um método eficaz de localização de códigos QR, mas sim tentar dizer a você, caro leitor, como, usando o pensamento científico e a análise de sistemas, entendendo como usar as ferramentas clássicas de processamento de imagem digital, você pode liberar bibliotecas trazem para o nível industrial real. Obrigado pela atenção.Lista de fontes utilizadas[1] A.A. Kotov, S.A. Usilin, S.A. Gladilin, and D.P. Nikolaev, “Construction of robust features for detection and classification of objects without characteristic brightness contrasts,” Journal of information technologies and computing systems, 1, 53-60, (2014).
[2] A. Minkina, D. Nikolaev, S. Usilin, and V. Kozyrev, “Generalization of the Viola-Jones method as a decision tree of strong classifiers for real-time object recognition in video stream,” in Seventh International Conference on Machine Vision (ICMV 2014), 9445, International Society for Optics and Photonics, (2015), doi:10.1117/12.2180941.
[3] D. P. Matalov, S. A. Usilin, and V. V. Arlazarov, “Modification of the viola-jones approach for the detection of the government seal stamp of the russian federation,” in Eleventh International Conference on Machine Vision (ICMV 2018), 11041, International Society for Optics and Photonics, (2019), doi:10.1117/12.2522793.