Quebrando CAPTCHAs - Parte III: Segmentação de imagens

Por Julio 22/07/2017

Nesse post vamos discutir um pouco sobre modelar CAPTCHAs. Vou assumir que você já viu o post de introdução e o post sobre download, leitura e classificação manual de CAPTCHAs.

Digamos que você tenha uma base de dados de treino composta por \(N\) imagens com os textos classificados. Nossa resposta nesse caso é uma palavra de \(k\) caracteres (vamos considerar \(k\) fixado), sendo que cada caractere \(c\) pode ter \(p\) valores.

O problema de modelar o CAPTCHA diretamente é que a variável resposta tem um número exponencial de combinações de acordo com o número de caracteres:

\[ \Omega = p^k. \]

Por exemplo, um CAPTCHA com \(k=6\) e \(p=36\) (26 letras e 10 números), que é muito comum, possui um total de 2.176.782.336 (> 2 bilhões) combinações! E não preciso dizer que é completamente inviável baixar e modelar tudo isso de CAPTCHAs.

A alternativa imediata que aparece é tentar separar a imagem em um pedaço para cada caractere e fazer um modelo para prever caracteres. Assim nossa resposta é reduzida para \(p\) categorias, que é bem mais fácil de tratar.

Vamos usar como exemplo o CAPTCHA dos TRTs. Primeiro, o download:

library(decryptr)
library(tidyverse)
arq_captcha <- decryptr::download_trt(dest = 'img', n = 1)

Visualizando a imagem:

"img/captcha705f7bad4a3d.jpeg"  %>% 
  read_captcha() %>% 
  plot()

Infelizmente, segmentar a imagem nos lugares corretos é uma tarefa difícil. Pior até do que predizer as letras. Para simplificar, vamos fazer um corte fixado das letras:

arq_captcha %>% read_captcha() %>% plot()
abline(v = 30 + 15 * 0:5, col = 'red')

Podemos também limitar os eixos x (tirar os espaços vazios à esquerda e à direita) e y (superiores e inferiores).

"img/captcha705f7bad4a3d.jpeg" %>% 
  load_image() %>% 
  magrittr::extract(-c(1:9, 31:dim(.)[1]), -c(1:15, 106:dim(.)[2]), TRUE) %>% 
  grDevices::as.raster() %>% 
  graphics::plot()
abline(v = 15 * 1:5, col = 'red')
abline(v = 15 * c(0, 6), col = 'black')
abline(h = c(0, 21), col = 'blue')

Agora temos uma imagem de tamanho dimensões 21x15 por caractere. Nosso próximo desafio é transformar isso em algo tratável por modelos de regressão. Para isso, colocamos cada pixel em uma coluna da nossa base de dados.

No caso do TRT, cada CAPTCHA gerará uma tabela de 6 linhas e 315 (21 * 15) colunas. Podemos usar esse código para montar:

arq_captcha %>% 
  load_image() %>% 
  magrittr::extract(-c(1:9, 31:dim(.)[1]), -c(1:15, 106:dim(.)[2]), 1) %>% 
  as_tibble() %>% 
  rownames_to_column('y') %>% 
  gather(x, value, -y) %>% 
  mutate_at(vars(x, y), funs(parse_number)) %>% 
  mutate(letra = (x - 1) %/% 15 + 1,
         x = x - (letra - 1) * 15) %>% 
  mutate_at(vars(x, y), funs(sprintf('%02d', .))) %>% 
  unite(xy, x, y) %>% 
  spread(xy, value, sep = '') %>% 
  mutate(y = c('a', 'f', '3', 'd', 'w', 'x')) %>% 
  select(y, everything(), -letra)
## # A tibble: 6 x 316
##       y   xy01_01   xy01_02   xy01_03   xy01_04   xy01_05   xy01_06
##   <chr>     <dbl>     <dbl>     <dbl>     <dbl>     <dbl>     <dbl>
## 1     a 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843
## 2     f 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843
## 3     3 0.9803922 1.0000000 0.8705882 0.5568627 0.5647059 0.8705882
## 4     d 0.9764706 0.9294118 0.9764706 0.9450980 0.9333333 0.9411765
## 5     w 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843 0.9607843
## 6     x 0.9294118 0.9529412 0.9882353 0.9333333 0.9921569 0.9450980
## # ... with 309 more variables: xy01_07 <dbl>, xy01_08 <dbl>,
## #   xy01_09 <dbl>, xy01_10 <dbl>, xy01_11 <dbl>, xy01_12 <dbl>,
## #   xy01_13 <dbl>, xy01_14 <dbl>, xy01_15 <dbl>, xy01_16 <dbl>,
## #   xy01_17 <dbl>, xy01_18 <dbl>, xy01_19 <dbl>, xy01_20 <dbl>,
## #   xy01_21 <dbl>, xy02_01 <dbl>, xy02_02 <dbl>, xy02_03 <dbl>,
## #   xy02_04 <dbl>, xy02_05 <dbl>, xy02_06 <dbl>, xy02_07 <dbl>,
## #   xy02_08 <dbl>, xy02_09 <dbl>, xy02_10 <dbl>, xy02_11 <dbl>,
## #   xy02_12 <dbl>, xy02_13 <dbl>, xy02_14 <dbl>, xy02_15 <dbl>,
## #   xy02_16 <dbl>, xy02_17 <dbl>, xy02_18 <dbl>, xy02_19 <dbl>,
## #   xy02_20 <dbl>, xy02_21 <dbl>, xy03_01 <dbl>, xy03_02 <dbl>,
## #   xy03_03 <dbl>, xy03_04 <dbl>, xy03_05 <dbl>, xy03_06 <dbl>,
## #   xy03_07 <dbl>, xy03_08 <dbl>, xy03_09 <dbl>, xy03_10 <dbl>,
## #   xy03_11 <dbl>, xy03_12 <dbl>, xy03_13 <dbl>, xy03_14 <dbl>,
## #   xy03_15 <dbl>, xy03_16 <dbl>, xy03_17 <dbl>, xy03_18 <dbl>,
## #   xy03_19 <dbl>, xy03_20 <dbl>, xy03_21 <dbl>, xy04_01 <dbl>,
## #   xy04_02 <dbl>, xy04_03 <dbl>, xy04_04 <dbl>, xy04_05 <dbl>,
## #   xy04_06 <dbl>, xy04_07 <dbl>, xy04_08 <dbl>, xy04_09 <dbl>,
## #   xy04_10 <dbl>, xy04_11 <dbl>, xy04_12 <dbl>, xy04_13 <dbl>,
## #   xy04_14 <dbl>, xy04_15 <dbl>, xy04_16 <dbl>, xy04_17 <dbl>,
## #   xy04_18 <dbl>, xy04_19 <dbl>, xy04_20 <dbl>, xy04_21 <dbl>,
## #   xy05_01 <dbl>, xy05_02 <dbl>, xy05_03 <dbl>, xy05_04 <dbl>,
## #   xy05_05 <dbl>, xy05_06 <dbl>, xy05_07 <dbl>, xy05_08 <dbl>,
## #   xy05_09 <dbl>, xy05_10 <dbl>, xy05_11 <dbl>, xy05_12 <dbl>,
## #   xy05_13 <dbl>, xy05_14 <dbl>, xy05_15 <dbl>, xy05_16 <dbl>,
## #   xy05_17 <dbl>, xy05_18 <dbl>, xy05_19 <dbl>, xy05_20 <dbl>,
## #   xy05_21 <dbl>, xy06_01 <dbl>, ...

Muito bem! Agora basta rodar o mesmo para toda a base de treino e rodar um modelo. Para esse post, vamos usar uma base de 2300 CAPTCHAs classificados. Essa base fica com 13800 linhas e 315 colunas. Vamos usar 11000 linhas para treino e as 2800 restantes para teste. O modelo utilizado será um randomForest padrão.

library(randomForest)
dados <- readRDS('d_segment_captcha.rds') %>% 
  mutate(y = factor(y))

# monta bases de treino e teste
set.seed(4747) # reprodutibilidade
ids_treino <- sample(seq_len(nrow(dados)), 11000, replace = FALSE)
d_train <- dados[ids_treino, ]
d_test <- dados[-ids_treino, ]
model <- randomForest(y ~ . - captcha_id, data = d_train) 

O resultado do modelo pode ser verificado na tabela de observados versus preditos na base de teste. O acerto foi de 99.4% em cada caractere! O maior erro ocorreu no confundimento da letra n com a letra h. Assumindo que o erro não depende da posição do caractere no CAPTCHA, teremos um acerto de aproximadamente 96.7% para a imagem.

d_test %>% 
  mutate(pred = predict(model, newdata = .)) %>% 
  count(y, pred) %>% 
  spread(pred, n, fill = '.') %>% 
  remove_rownames() %>% 
  knitr::kable(caption = 'Tabela de acertos e erros.')
Table 1: Tabela de acertos e erros.
y 2 3 4 5 6 7 8 9 a b d e f h j k m n r s t u v w x y
2 109 1 . . . . . . . . . . . . . . . . . . . . . . . .
3 . 105 . . . . 1 . . . . . . . . . . . . . . . . . . .
4 . . 116 . . . . . . . . . . . . . . . . . . . . . . .
5 . . . 97 . . . . . . . . . . . . . . . . . . . . . .
6 . . . . 108 . . . . . . . . . . . . . . . . . . . . .
7 . . . . . 111 . . . . . . . . . . . . . . . . . . . .
8 . . . . . . 120 . . . . . . . . . . . . . . . . . . .
9 . . . . . . . 51 . . . . . . . . . . . . . . . . . .
a . . . . . . . . 63 . . . . . . . . . . . . . . . . .
b . . . . . . . . . 110 . . . . . . . . . . . . . . . .
d . . . . . . . . . . 108 . . . . . . . . 1 . . . . . .
e . . . . . . . . . . . 110 . . . . . . . . . . . . . .
f . . . . . . . . . . . . 116 . . . . . . . . . . . . .
h . . . . . . . . . 1 . . . 116 . . . 1 . . . . . . . .
j . . . . . . . . . . . . . . 115 . . . . . . . . . . .
k . . . . . . . . . . . . . . . 126 . . . . . . . . . .
m . . . . . . . . . . . . . . . . 122 2 . . . . . . . .
n . . . . . . . . . 1 . . . 3 . . 1 132 . . . . . . . .
r . . . . . . . . . . . . 1 . . . . . 91 . . . . . . .
s . . . . . . . . . . . . . . . . . . . 113 . . . . . .
t . . . . . . . . . . . . . . . . . . . . 106 . . . . .
u . . . . . . . . . . 1 . . . . . . . . . . 99 . . . .
v . . . . . . . . . . . . . . . . . . . . . . 99 . . 2
w . . . . . . . . . . . . . . . . . . . . . . . 107 . .
x . . . . . . . . . . . . . . . . . . . . . . . . 132 .
y . . . . . . . . . . . . . . . . . . . . . . . . . 102

Nem tudo são rosas

O resultado para o CAPTCHA do TRT é bastante satisfatório, mas infelizmente não generaliza para outros CAPTCHAs. Tome por exemplo o CAPTCHA da Receita Federal abaixo. Nesse caso, a posição dos caracteres muda significativamente de imagem para imagem, e assim fica difícil cortar em pedaços.

O mesmo modelo aplicado ao CAPTCHA da Receita possui acerto de 78.8% do caractere, o que equivale a apenas 23.8% de acerto para toda a imagem. Veja os resultados na Tabela 2

model <- randomForest(y ~ . - captcha_id, data = d_train) 
Table 2: Tabela de acertos e erros para o CAPTCHA da Receita.
y 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z
1 28 . . . . . . . . . . . . . 2 . . 2 4 . 3 . . . . . . . 10 . . . . . .
2 . 28 . . . . . . . . . 2 . 1 1 . . . 2 . . . . . . . . . . . . . 1 . 8
3 1 . 29 . 3 . . 1 1 . . . . . . . . . 6 1 . . . . . . . . . . . . . . .
4 . . . 35 . . . . 1 . . . . . . . . . 1 . . 1 . . . . 1 . . . . 1 . . .
5 . . . . 30 . . . . . 1 . . 1 . . . . 1 . . . . . . 2 . 1 . . . . . . .
6 . . . 1 . 38 . . . . 3 . . 2 . . 1 . . . . . . . . . . . 1 . 1 1 . 1 .
7 1 . . . . . 38 . . . . . 1 . . . . . 2 . . . . . . . . 1 . . 2 . . . .
8 . . . . . 2 . 31 . . 3 . . . . . 5 1 . 2 . . . . . . . 1 . . . . 1 . .
9 . . . 1 . . 1 . 41 . . . . . 1 . . . . . . . . . . . . . 1 . 1 . 1 . 2
a . 1 . . . . . . . 79 . . . . . . . . . . . . . . 1 . . 1 . . . . 1 . 1
b . . . . . . . 1 . 1 60 . . 1 . . 4 . . 1 . . . 3 2 2 2 2 1 . . . 1 . .
c . 1 . . . . . . . . 2 62 1 5 1 2 . . 1 . . . . 6 1 1 . 1 1 . 1 . . . .
d . . 1 . . . . . . 3 3 . 35 3 . 4 1 . 1 1 2 1 1 8 2 2 . . . 12 . 1 1 . .
e . . . 1 . 1 . . . 4 1 1 . 83 2 . . . . . . . . . 2 . 1 1 . . . 3 . . .
f . . . . . . . . . 1 . . . 3 79 . . . . 1 . 1 . . 2 . . . 4 . . . . 1 .
g . . . . . . . . 2 1 . 1 . . . 64 . . 2 . . . . 3 . 17 . 2 1 . . . . . .
h . . . . . . . 1 . . 3 . . 1 . . 87 . . 2 1 2 2 . . . 3 . 2 . . . . . .
i 2 . . . . . . . . 2 . . . . 1 . . 36 2 . 1 . . . . . 1 . 4 . . 1 2 2 .
j . . . . . . . . 2 . 1 . 1 . . . . 4 70 . . . . 1 . 1 . 1 1 1 2 . . . .
k . . . . . . . 1 . . 1 . . . . . . . . 79 . . 1 . . . 1 . 1 . 1 1 1 . .
l 3 . . . . . . . . . 1 . . 2 1 . 1 . . . 38 . . . . . . . 12 . . 1 . . .
m . . . . . . . . . . . . . . . . 2 . . . . 101 3 . 1 . 2 . . . 1 . 1 . .
n . . . . . . . . . . 1 . 1 1 1 . 8 . . . . 2 67 . . . 4 . . 2 . 2 1 . .
o . . 1 . 1 . . . . 2 1 15 4 3 . 1 . . 2 . . . . 62 2 9 . 2 . 1 1 . . . .
p 2 . . 1 . . . . . . 2 . . 2 2 3 1 . . . . . 1 1 75 . 4 . 3 . . 2 . . .
q . . . . . . . . . 1 . 1 . 3 . 7 . . . . . 1 . 2 1 79 . . . . 1 . . . 1
r . . . . . . . . . . 2 . . . 4 . . . . 8 . . 1 . 3 . 65 . 4 . 1 . 1 . 1
s . . . . . . . 1 . 3 2 1 . 2 . . . . 2 . . . . . . . 1 87 . . 1 2 . . .
t . . . 1 . . . . . . 2 1 . 1 2 2 . . 1 1 . . . . . 1 1 1 78 . 1 1 1 . 1
u . . . . . . . . 1 2 1 . 2 . 1 . 1 1 3 . . . 1 . . 1 . . . 80 2 2 . . .
v . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 93 3 . 5 .
w . . . . . . . . . . . . . . . . . . 1 . . . 1 . . . . . . . 1 100 . . .
x . . . . . 2 . . . 1 . . . . . . . . . 1 . . . . . . . . . . . 3 91 1 .
y . . 1 1 1 . . . . 2 . . . . 1 1 . . 2 . . 1 . 2 1 . . . 2 1 15 1 1 75 .
z . . . . . . . . 1 1 . . . 2 . . 1 . . . . . . . . . . . . . . . . . 85

Claro que seria possível melhorar o poder preditivo com uma modelagem mais cuidadosa: nós usamos todos os parâmetros padrão da randomForest e não consideramos outros possíveis modelos. Mas acreditamos que o problema essencial está na segmentação, e não na modelagem após a segmentação.

Nos próximos posts, vamos mostrar como resolver o CAPTCHA da Receita com maior acurácia utilizando técnicas de Deep Learning que consideram a etapa de segmentação dentro da modelagem.

Wrap-up

  • Não dá para considerar todas as combinações de valores de um CAPTCHA diretamente num modelo de regressão.
  • Uma forma de resolver um CAPTCHA é segmentando a imagem em pedaços de mesma largura.
  • Para montar a base de treino, criamos uma coluna para cada pixel. Um CAPTCHA corresponde a uma base com \(k\) linhas e número de colunas igual ao número de pixels.
  • No CAPTCHA do TRT os resultados são satisfatórios.
  • Já para CAPTCHA da Receita essa estratégia pode ser ineficaz.
  • Vamos evoluir essa análise para técnicas que consideram a etapa de segmentação dentro da modelagem.

É isso. Happy coding ;)

comments powered by Disqus