sábado, 4 de outubro de 2008

O Desentortador

Eu confesso que fiquei apreensivo quando soube que teria que passar vários meses na Califórnia. Afinal, Mountain View não é nenhuma San Francisco, eu tinha medo de morrer de tédio enquanto estivesse lá. Mas, felizmente, meu medo esvaiu-se quando eu descobri O Sebo!


O Sebo é um lugar lindo e maravilhoso onde você pode comprar The Diamond Age por apenas 50 cents, e inúmeros outros livros por preços tão baixos quanto esse. Na foto acima, você pode ver uma pequena porção do paraíso, mostrando apenas a parte de sci-fi, e apenas os autores das letras D até L. Sim, O Sebo é um lugar gigante e com diversão garantida pra várias semanas.

Depois de encher a mochila com livros, eu tive vontade de tirar uma foto deles pra mandar pros amigos. Foi então que eu tive um problema. Eu estava tentando tirar a foto à noite, e se eu colocasse a câmera exatamente sobre o livro, o flash estourava, e tudo que saía na foto era um grande borrão branco. Sem flash também não funcionava, ficava escuro demais pra câmera conseguir estabilizar a imagem.

Eu resolvi esse problema inclinando a câmera em relação ao plano do livro. Isso certamente resolve o problema do flash, mas em compensação o livro fica torto na foto. Uma solução simples seria simplesmente esperar amanhecer e tirar a foto do livro com a luz do dia. Mas é claro que optei por uma alternativa mais bizarra :) Resolvi escrever um software que desentortasse a foto do livro automaticamente!

Pra isso, vamos começar com a foto original do livro torto:


Pra começar o desentortamento, a primeira coisa que precisamos descobrir é onde estão as bordas do livro, que vão definir como vai ser a rotação que iremos fazer. Achar as bordas é fácil, basta identificar a fronteira entre livro e não-livro. Para isso, eu usei um algoritmo simples de crescimento de região:


Não ficou a coisa mais perfeita do mundo: está cheio de ruído em volta, e o algoritmo ainda vazou pra dentro do livro (a mesa era marrom, da mesma cor do urso na capa, e ele se perdeu com isso).

A boa notícia é que nenhuma dessas coisas importa! O que eu quero achar são as bordas, que tem uma direção preferencial bem determinada. Se eu utilizar a transformada de Hough, tanto o ruído quanto o vazamento devem sumir, e de fato é o que acontece. Essa é a transformada da imagem acima:


A transformada de Hough leva retas em pontos, então as quatro retas que formam a borda do livro viram quatro pontos bem brilhantes na transformada. É simples agora usar um threshold pra identificar esses pontos, e aplicar a transformada inversa pra achar as retas na imagem original:

Nessa imagem eu tracei linhas vermelhas nas retas identificadas pela transformada. Estamos quase lá, mas um problema da transformada de Hough é que ela acha retas, e não segmentos de retas. O que me interessa na verdade são os vértices do livro, então eu preciso achar as intersecções entre essas retas.

O detalhe é que quatro retas em posição geral determinam seis pontos, e não quatro. No caso da imagem acima, por exemplo, as retas verticais se encontram no ponto de fuga, bem acima do livro. A solução que eu usei foi adotar uma gambiarra heurística de considerar apenas os quatro pontos mais próximos do centro da imagem original. Além disso, também é legal converter os pontos pra coordenadas polares em relação ao centro da imagem, assim podemos ordená-los pelo ângulo.

Tendo os quatro vértices, agora é só aplicar uma transformação afim na imagem que a leve pra um retângulo e o trabalho está terminado né? Quem dera hehe. Se você fizer isso, a imagem fica com uma deformação não-linear: achatada na parte de cima, e esticada na parte de baixo.


Na década de 90, todo guri metido a programador fazia sua própria engine 3D pra imitar o Doom e o Quake; quem passou por essa época reconhece na hora a origem da deformação. O que está acontecendo é um problema de inverse perspective-correct texture mapping. A perspectiva introduz um fator do tipo 1/z na sua textura, e você precisa compensar isso quando for mapear na imagem. Vamos fazer a correção de perspectiva então:


Yatta! Finalmente temos a imagem final, desentortada como queríamos :) Na verdade, nós desentortamos a imagem em um único eixo, dá pra ver claramente que além do pitch essa imagem também precisava de correção no roll, mas isso fica como exercício pro leitor.

Eu implementei todos os passos descritos acima em python, usando a biblioteca PIL. Ele roda rapidinho, uns 3s por imagem apenas. O source é o abaixo:

Source do desentortador em python

Se alguém quiser reaproveitar o código pra fazer alguma coisa útil com ele (hehe), sinta-se à vontade. Salvo indicação em contrário, todos os programas desse blog são disponibilizados sob a Licença Crowley (Do what you want shall be the whole of the License).

PS: Ah sim, como vocês repararam, a partir de agora o blog vai ter desenhos também! Eu gostaria de dizer que se funcionou pro Chrome, deve funcionar pra mim também; mas a verdade é que a Aleph já fazia a mesma coisa lá na década de 80 :)

19 comentários:

  1. "A solução que eu usei foi adotar uma gambiarra, ops! heurística.."

    Vc me mata de rir Ricardo!

    Achei genial o programinha... eu desentortava estas coisas na mão mesmo, (através do Photoshop), mas agora meus problemas acabaram! ;-)

    ResponderExcluir
  2. Quer a solução tabajara e sem software?

    Pega uma folha de papel branca, dobra em quatro e tapa o flash, o papel funciona como um filtro e acaba com o problema do espelhamento e estouro de brilho ehehehe. Eu sempre uso esse recurso aqui.

    ResponderExcluir
  3. Ou então coloca num scanner hehe.

    Minha busca não era pela solução mais fácil, era pela mais divertida :)

    ResponderExcluir
  4. Só quem trabalha em processamento de imagem saberá dar valor ao que aqui está. Estão aqui envolvidos vários conceitos. É preciso saber que existem, e depois saber aplicar_los

    eu gostei mt

    parabens

    ResponderExcluir
  5. acender a luz não resolve o problema?! oO

    ResponderExcluir
  6. Legal, Ricardo ! Linkei esse seu post em meu blog, para meus alunos de CVIP.
    Gostei dos desenhos ! São de sua autoria ?

    ResponderExcluir
  7. Não são não :)

    Se eu tivesse desenhado, saíria algo próximo do xkcd hehe

    ResponderExcluir
  8. Kudos!
    Ricardo sempre indo pelo caminho mais dificil...
    Eu usaria o photoshop, até mesmo porque não sei implementar um algorítimo desses.

    ResponderExcluir
  9. Simplesmente incrivel, parabens RicBit, invejo a sua capacidade de raciocinio!

    ResponderExcluir
  10. Legal o post! Dá uma aplicacao bem interessante de proc. de imagens com um problema concreto. Está de parabéns.
    :-)

    Será que os resultados não seriam melhores se vc usasse um detector de bordas logo no início?

    Eu já vi uma abordagem para achar quadrados onde após dilatar os pixels, ocorria a extracao dos contornos e aproximacao com formas quadradas.

    O critério de descarte (ou aceitacao) se baseava na relacao dos angulos nos vertices dos contornos após a aproximacao.

    A vantagem desta abordagem é que iria funcionar se vc tivesse múltiplas formas quadradas (e.g. mais de 1 revista) na imagem de entrada.


    []s


    Adenilson

    ResponderExcluir
  11. Eu tentei usar o operador de sobel ao invés do crescimento de região na primeira etapa; mas ele estava bem mais sensível ao ruído, e acabei descartando :)

    ResponderExcluir
  12. Parabéns!! Excelente exemplo que demonstra que a teoria pode ajudar na prática. Muito bem escrito o programa.

    ResponderExcluir
  13. Muito bom. Já pensou em converter esse código para um plugin do Gimp? Acredito que seria uma funcionalidade muito bem vinda ao projeto. (inclusive, Gimp tem suporte a Python-fu, plugins em Python)

    Quando eu precisei desentortar fotos desse tipo, eu usei a ferramenta de perspectiva do Gimp. Tem uma opção para ligar o reverso da perspectiva, o que é uma mão-na-roda neste caso. Mas, ainda assim, é um trabalho bem manual.

    Aí eu lembro que o que eu quis des-deformar eram fotos de CDs, que, como se sabe, são redondos. Isso implica que seu algoritmo não funciona nesse caso.

    ResponderExcluir
  14. É mesmo, dá pra fazer um plugin de gimp. Boa sugestão :D

    O jeito não-bizarro de desentortar o CD seria colocá-lo em cima de uma caixinha e usar as bordas da caixinha como guia, mas customizar o algoritmo pra círculos é bem mais legal :)

    ResponderExcluir
  15. Grande Ricardo!

    Engraçado que eu conheço algumas dessas técnicas de manipulação de imagem só pelo código e não pelo nome. Tirando a transformação afim, já tinha visto os outros só de código, hehehe.

    E a idéia do Plugin para GIMP é excelente!

    Abraços

    ResponderExcluir
  16. Oi Ricardo,

    Eu estudo processamento de imagens e achei muito interessante seu código, parabéns!
    Eu tentei reproduzí-lo, mas a imagem resultante da aplicação do algoritmo "crescimento por região" resultou em uma imagem totalmente preta(??). Você tem alguma idéia do que pode estar acontecendo?
    Aproveitando essa postagem, gostaria de saber como você faz para selecionar apenas os vértices da borda do livro a partir da transformada de Hough.

    Grato,

    Thiago

    ResponderExcluir
  17. Thiago, entra no source do programa, e mude a semente do crescimento de região, ou então a tolerância. O blogger reescalou a imagem e minha semente não funciona na imagem reescalada.

    Pra achar os vértices na transformada eu pego os pontos mais brilhantes!

    ResponderExcluir