Tecnologia de correção de distorção de páginas
(mzucker.github.io)- Para transformar fotos de documentos curvados em imagens planas, o método modela a pose 3D e a curvatura e resolve isso como um problema de otimização alinhando pontos de referência do texto
- Assim como Leptonica e CTM, segue um fluxo que divide o texto em linhas e encontra uma transformação de coordenadas para que elas pareçam paralelas e quase horizontais
- O modelo inclui o vetor de rotação
r, o vetor de translaçãot, os coeficientes de inclinação da curvaturaα,βe os offsetsx,ydos spans de texto, minimizando o erro de reprojeção - O pipeline segue por recorte da borda da página, detecção de contornos de texto, montagem dos spans, amostragem de pontos de referência, geração de valores iniciais, otimização de Powell e remapeamento com
cv2.remap - No exemplo de execução, os parâmetros variaram de 104 a 600, com tempo total de 5,3 a 24,8 segundos; como a maior parte foi gasta na otimização, ainda há espaço para melhorar a velocidade com outro solver ou linguagem compilada
Resolver páginas curvadas como um problema de otimização
- Um script anterior para transformar fotos de anotações manuscritas em PDF ficava no nível de usar
adaptiveThresholde agrupar várias imagens em um PDF, mas em fotos de documentos arquivados o enrolamento da página fazia o texto ficar bastante curvado - O objetivo era criar um programa que convertesse automaticamente fotos de páginas curvadas em imagens planas de documento
- O código está disponível no GitHub em page_dewarp
Fluxo básico trazido de Leptonica e CTM
- A correção de distorção em imagens de documentos é um problema já conhecido, e também está implementado na biblioteca open source de processamento de imagens Leptonica, de Dan Bloomberg
- Entre os materiais de referência estão o resumo dos resultados do dewarping contest e o artigo sobre o método vencedor, Coordinate Transform Model, ou CTM
- Leptonica e CTM dividem o problema em duas etapas em comum
- separar o texto em linhas
- encontrar uma distorção ou transformação de coordenadas que faça as linhas ficarem paralelas e horizontais
- Esta implementação representa a forma da página com vários parâmetros
r,t: vetor de rotação e vetor de translação que representam a orientação 3D e a posição da páginaα,β: duas inclinações que definem a curvatura da superfície da páginay₁ ... yₙ: offsets verticais denspans horizontais na páginaxᵢ: offsets horizontais de vários pontos de referência dentro de cada span
Superfície 3D e erro de reprojeção
- A forma 3D da página é representada como uma superfície criada ao varrer uma curva ao longo do eixo local
y - A coordenada horizontal
xda página é mapeada para o deslocamento da superfície na direçãoz, e a seção horizontal é modelada com uma spline cúbica- os dois extremos da spline são fixados em 0
- a forma da spline é determinada apenas pelas inclinações das extremidades
α,β
- Quando os parâmetros de pose e curvatura são definidos, cada coordenada
(x, y)da página é projetada para uma posição específica no plano da imagem - O método encontra keypoints dos spans horizontais de texto na foto original e, a partir de uma estimativa inicial, busca os parâmetros que minimizam o erro de reprojeção desses keypoints
- Antes da otimização, assumindo ausência de curvatura, os pontos reprojetados ficam em linha reta; depois da otimização, os pontos projetados pelo modelo quase coincidem com os keypoints detectados
Pipeline de processamento de imagem
-
Recorte da borda da página
- Em vez de usar a imagem inteira, recorta-se apenas a região central com uma margem fixa para evitar áreas desnecessárias nas bordas
- Não é usada detecção inteligente da borda da página
-
Detecção de contornos de texto
- Aplica-se inicialmente um adaptive threshold
- É feita dilatação morfológica) com uma caixa horizontal para conectar pixels de máscara horizontalmente adjacentes
- É feita erosão) com uma caixa vertical para remover ruído com altura de um pixel
- Após análise de componentes conectados, blobs altos ou grossos demais são filtrados
- Os contornos de texto restantes são aproximados como segmentos de reta de melhor ajuste com PCA
-
Complemento à detecção de linhas horizontais
- Como algumas entradas eram tabelas com muito texto vertical, quando não havia detecção suficiente de texto horizontal o método também tentava detectar linhas horizontais ou rules
Construção dos spans de texto e amostragem de pontos de referência
- Para agrupar os contornos detectados no mesmo span horizontal, são criadas arestas candidatas para todos os pares de contornos e calculado um custo
- Se dois contornos se sobrepõem demais no sentido do comprimento, estão distantes demais ou têm grande diferença angular, o custo é definido como infinito
- O custo das arestas válidas é calculado como uma combinação linear de distância e mudança angular
- Após ordenar as arestas por custo, usa-se um método ganancioso de tempo quadrático que conecta apenas quando os contornos dos dois lados ainda não foram ligados
- Como a maior parte do tempo de execução é gasta na otimização, a complexidade quadrática desta etapa não foi um grande problema
- Depois que os spans são formados, spans pequenos demais para ajudar a determinar o modelo são removidos
- Como o modelo de parâmetros exige pontos de referência discretos, é selecionado um keypoint a cada cerca de 20 pixels de contorno de texto
Geração de valores iniciais e otimização com Powell
- A direção média de todos os spans é estimada com PCA
- Usando o componente principal obtido pelo PCA, são definidos analiticamente as coordenadas iniciais
x,ye a pose de uma página plana sem curvatura - A reprojeção obtém o offset
zdos pontos do objeto ao amostrar a spline cúbica e depois projeta no plano da imagem com funções do OpenCVcv2.solvePnPcv2.projectPoints
- Para minimizar o erro de reprojeção, usa-se
scipy.optimize.minimizecom o solver'Powell'- Ele é usado como uma ferramenta de otimização sem derivadas no estilo caixa-preta
- O problema em si corresponde a mínimos quadrados não lineares
- Não houve muita experimentação com outros solvers ou com solvers especializados em mínimos quadrados não lineares
- Quase 100% do tempo de execução do programa é gasto nesta etapa de otimização
Remapeamento e geração da imagem de saída
- Após a otimização, apenas
r,t,α,βsão separados para criar a transformação de coordenadas - O dewarp propriamente dito é obtido projetando uma malha densa de pontos da página 3D com
cv2.projectPointse passando essas coordenadas de imagem paracv2.remap - O resultado final é salvo como PNG binário usando
cv2.adaptiveThresholde Pillow
Resultados de exemplo e tempo de execução
- O repositório no GitHub inclui várias example images
- As estatísticas abaixo foram medidas em um único MacBook Pro de 2012
| Entrada | Spans | Keypoints | Parâmetros | Tempo de otimização | Tempo total |
|---|---|---|---|---|---|
boston_cooking_a.jpg |
38 | 554 | 600 | 23.3 s | 24.8 s |
boston_cooking_b.jpg |
38 | 475 | 521 | 18.0 s | 18.8 s |
linguistics_thesis_a.jpg |
20 | 161 | 189 | 5.1 s | 6.1 s |
linguistics_thesis_b.jpg |
7 | 89 | 104 | 4.2 s | 5.3 s |
- Mesmo o menor modelo tem 104 parâmetros, e o maior tem 600, então não se trata de um pequeno problema de otimização
- A velocidade da otimização pode melhorar com outras abordagens ou com uso de linguagem compilada
Limitações restantes
- A abordagem como um todo veio de ler um pouco do conhecimento de base e formular o problema inteiro como a saída de um processo de otimização
- Isso lembra deformable part models e active appearance models, mas não é tão sofisticado quanto eles
- Leptonica e CTM tentam modelar e corrigir não apenas a distorção vertical, mas também a distorção horizontal
- Esta implementação não cobre a correção da distorção horizontal
- Como a spline cúbica não é parametrizada por arc-length, o texto fica ligeiramente comprimido em regiões onde a inclinação da spline é grande
- Como o projeto era principalmente um proof-of-concept, esse problema não foi levado adiante
- O código final está disponível no repositório do GitHub, e os comentários detalhados ainda não foram reforçados o suficiente
1 comentários
Comentários do Hacker News
É preciso ter cuidado ao aplicar thresholding forte na saída, como o autor fez
Ele funciona muito bem em páginas de texto comum, mas vi várias páginas do Google Books em que ilustrações ou pequenas notas de rodapé ficavam destruídas a ponto de se tornarem ilegíveis
Se a cópia digitalizada do Google Books for o único material disponível, você fica completamente travado
Depois de encontrar esses pontos de referência, imagino que seja possível aplicar esses parâmetros à imagem original
É frustrante que, em 2024, apps de scanner de documentos ainda não tragam esse recurso embutido por padrão
Ter um modelo de deformação de página de baixa dimensionalidade para otimizar parece ser o ponto central que faz esse método funcionar bem
Este é um problema perfeito para o tamanho da YC. Algumas semanas até chegar ao mercado, e o custo de lançamento deve ficar na casa de algumas centenas de milhares de dólares
O app de celular da Apple exige ajustes manuais demais, e o Office Lens / Microsoft Lens, da Microsoft, recebe avaliações do tipo “as bordas acabam enlouquecendo e fica horrível”
Portanto, parece haver mercado para um produto que simplesmente funcione bem, e também uma saída possível vendendo para candidatos óbvios a aquisição
Devem ter considerado complexo e matemático demais e, em vez disso, decidido que criar um modelo para vasculhar a atividade dos usuários nas redes sociais e refinar o timing das notificações melhoraria mais as métricas de uso
No esforço para reduzir o churn, os tomadores de decisão acabaram decidindo de forma rigorosamente orientada por dados
Depois que John Warnock deixou o cargo de CEO da Adobe, ele se envolveu mais profundamente com a Octavo, uma empresa que preservava livros históricos raros
Um dos desafios que eles enfrentavam era desfazer a curvatura de páginas digitalizadas que não podiam ser prensadas para ficarem planas
https://en.m.wikipedia.org/wiki/Rare_Book_Room
O texto foi excelente
Poderia até servir de referência na empresa como exemplo de como documentar de forma eficaz um projeto técnico e suas decisões
Na universidade, tentei criar um app para escanear anotações diferenciadas por cor e encontrei outro problema
As cores variavam do topo para a base da página, dificultando distinguir de forma confiável caneta azul de caneta verde
Um dia preciso voltar a olhar isso
Isso efetivamente remove variações de cor/brilho de baixa frequência
É algo usado com frequência para eliminar sombras quando se fotografa papel, e imagino que funcione do mesmo jeito para gradientes de cor
Parece bom o bastante
Mas o modelo de deformação parece um pouco global demais
Algumas distorções mais complexas do papel não são capturadas pelo modelo e aparecem como distorções residuais no resultado final
Deu erro durante a instalação:
ERROR: Could not find a version that satisfies the requirement cv2>=3.0 (from versions: none)ERROR: No matching distribution found for cv2>=3.0Abri uma issue no GitHub
Muito legal
Seria bom ter um app de digitalização de documentos decente para usar no celular, que fizesse bem correção de distorção, thresholding e geração de PDF
Por enquanto estou preso ao Adobe Scan, que entrega os melhores resultados entre os que testei, mas a correção de distorção ainda é bem ruim
Foi realmente interessante de ler
Parece um texto de 2016 que eu deixei passar, e gostei de como ele mostra o fluxo completo: “havia este problema, aplicamos uma técnica inteligente e obtivemos uma solução que funciona bem”
Pessoalmente, acho que nunca vou precisar disso, mas é um ótimo exemplo de como abordar um problema de uma boa maneira e fazer concessões razoáveis dentro do que os resultados e as expectativas permitem
O texto também é bem escrito e bem explicado
Se você não precisa mostrar o livro visualmente e só quer fazer OCR, talvez dê para pular esta etapa
O Google resolveu esse problema há mais de 10 anos: https://hardware.slashdot.org/story/09/05/15/1834246/how-goo...
Se o manuscrito for realmente valioso, também é possível fazer correção de distorção sem contato usando tomografia por raios X: https://scrollprize.org/tutorial1
O lado do Google usava hardware, e essa história de tomografia por raios X soa muito a ChatGPT
Ainda assim, o método deste texto é bom e simples para 2016