Image Energy Sucker (Redimensionamento de Imagem Inteligente)

Bom, hoje vou postar sobre outro projetinho interessante que fiz na faculdade, com meu amigo Gabriel, na matéria de processamento de imagens do mestrado. Ele “se chama-se” Image Energy Sucker Tabajara :-P.

Qual foi a idéia do projetinho? Bom, a idéia era fazer um algoritmo de redimensionamento inteligente de imagens que tentasse retirar partes de pouca relevância ao todo e mantivesse o mais importante, fazendo isso sem deformações.

No método convencional, tanto a montanha quanto o golfinho sofreram deformações

Note que o barco não foi deformado no redimensionamento por energia.

Claro que não criamos nada novo. Tiramos a idéia desse vídeo ninja do maluquinho que alias foi contratado depois pela Adobe, que incorporou essa funcionalidade na nova versão do photoshops.

Porém o mais legal foi que fizemos sem ler o paper do cara. Olhamos o vídeo e pensamos em como descobrir a “energia” da imagem, ou seja, as partes mais relevantes, para então remover as menos relevantes. Logo, todas as soluções são nossas, são simplese baseadas somente nos resultados exibidos no vídeo dele.

Antes de explicar como fizemos a bagaça, acho que vale a pena postar um video do programa funcionando para entender melhor o que fizemos:

Veja que os resultados são parecidos com o do vídeo do maluquinho (pelo menos eu acho;-) ), mas não tão bons quanto os dele. Além disso, nosso algoritmo só diminui a imagem, não faz o processo inverso como o  dele. Tentamos também implementar a remoção de pessoas ou objetos da foto aplicando uma mascara de energia negativa infinita pra elas, mas nem chegamos perto dos resultados que o cara apresenta no videozin nessa funcionalidade.

Para explicar o algoritmo, podemos separá-lo em duas partes: a parte responsável por determinar a energia da imagem e a parte responsável por remover

Determinando a Energia da Imagem

Bom, para guiar nosso algoritmo, era preciso definir quais partes da imagem eram relevantes ou não. Chamamos isso de “determinação da energia da imagem”, também conhecido com “image-aurea-calculator-algorithm” (ui).

Mesmo tentando descobrir a “energia” da imagem, o algoritmo não tem nada de exotérico. Determinamos que quanto mais energia, mais relevante a área à imagem era.

A primeira idéia para calcular a “energia” da imagem foi o calculo da derivada da imagem. “Mas hein?! Derivada agente não usa só na aula de calculo??!” diriam alguns. A resposta é “NÃO!!!”, a derivada serve para calcular a divergência pontual de alguma função, e para gente, quanto mais a imagem mudar, mais alto será o valor de sua derivada, mais “informação” estará presente naquela parte da imagem e, portanto, mais energia teremos naquela parte da imagem.

Dito isso, cabe agora aprender a derivar uma imagem. Mas antes, para simplificar os cálculos (bom, nós usamos essa simplificação no programa também… hehe), vamos sempre considerar que a imagem é uma imagem em escala de cinza. Isso significa que cada pixel, ao invés de ter os 3 canais de cor (red,Green,blue), tem somente um canal que indica a intensidade entre branco e preto e, para nós, varia de 0 (preto) a 255 (branco). Bom, quem já brincou com algoritmos de processamento de imagem já está acostumado com isso. Ah, e para ficar claro, nosso algortimo de conversão de imagem para escala de cinza usou a média dos 3 canais de cores [ PIXELescalacinza = ( R+G+B) / 3 ].

Bom, talvez eu esteja explicando muito do calculo de derivada de uma imagem, que é só uma ferramenta para o funcionamento de todo o algoritmo. Porém eu sempre fui meio tapado para entender essas coisas mais conceituais e vou tentar explicar (tomara que esteja certo) da maneira mais simples possível (como “se vocês fossem crianças de 6 anos” uahuhaa quote do filme Philadelphia… “bom, mas não se irritem” porque eu sempre quis que me explicassem calculo, derivada, essas merdas todas, como se eu fosse a pessoa mais burra da face da terra). Se você já manja de derivada de imagem, pode continuar com o “artigo”. Caso contrário, de um pulo no post sobre derivada da imagem que vale a pena (quando este estiver pronto). Ah, todas as explicações vou levar em conta a direção horizontal. Ou seja, a derivada da imagem será horizontal e, na hora do resize, faremos o resize na horizontal. Uma vez explicado no sentido horizontal, o sentido vertical é trival e será deixado como exercício (hehe, sacaniei… auhhuaua)

Tentativa de Explicação de Derivada de Imagem (link futuro para uma explicação de derivada de imagens… serio, se realmente for preciso eu faço… eu já fiz o texto mas tem q fazer vários gráficos e imagens…. então, se alguém precisar muito eu posto – não que isso possa ajudar muito… )

Como visto (ou não) ai no link de cima, a derivada da imagem dá uma função de determinação de energia da imagem. Veja exemplo

Imagem original e sua derivada (horizontal)

Outra função que utilizamos para definir a “energia” da imagem foi a própria imagem em escala de cinza. A explicação para isso é: “cagada”. “Cagada” porque erramos o algoritmo da primeira vez e usamos como função de energia a imagem em escala de cinza ao invés da derivada e obtivemos bons resultados. Quando percebemos que tínhamos errado, colamos a derivada e não ficou tão bom. Então criamos a função de energia pela “luminosidade”, que nada mais é que a escala de cinza.  Damos opção para o usuário escolher varias funções para descobrir a energia da imagem, como a derivada, a luminosidade, a derivada+luminosidade, enfim, cada imagem pode ter um resultado diferente dependendo da função de descrição de energia.

Algoritmo de Resize

Uma vez calculada a “energia da imagem”, criamos um heurística para melhor remover as linhas da imagem com menor energia. Esse processo é feito em etapas, como se segue:

Primeira etapa: lembrando que no exemplo estamos fazendo o resize no sentido horizontal. Logo, dividimos a imagem em n colunas (não lembro como calculamos n, mas posso dizer que ele é N ótimo.. kkk). Bom, na imagem abaixo tem X colunas. Cada coluna contem a média de energia da região. Desse modo, podemos determinar qual coluna da imagem, ou qual região da imagem, tem a menor energia.

Energia da imagem e sua BiTree que auxilia na tomada de decisão sobre qual região da imagem atacar.

Segunda Etapa: sabendo qual região tem a menor energia, precisamos tirar uma coluna para dar resize da imagem na horizontal. Contudo, essa linha não pode ser qualquer linha, tem que ser, no mundo ideal, a linha de menor energia da imagem. Para descobrir qual é essa linha, usamos um algoritmo guloso (ui) (artigo da wikipédia US e BR | BR – http://pt.wikipedia.org/wiki/Algoritmo_guloso | US – http://en.wikipedia.org/wiki/Greedy_algorithm ).  A primeira versão do algoritmo guloso consistia em achar o pixel de menor energia da primeira linha e, a partir desse pixel, executar o seguinte algoritmo: pega os 3 pixels vizinhos da linha de cima, escolhe o de menor energia, marca ele para ser retirado e continua o processo até chegar no topo.  O problema dessa heurística de algoritmo guloso é que muitas vezes ele saia da região demarcada pela coluna de menor energia média da imagem. Então, fizemos uma segunda versão que tenta ficar sempre nos limites de coluna e depois outras  versões que ao invés de iniciar na primeira linha da coluna (parte de baixo), começava na ultima linha (parte de cima) ou na linha de menor energia e mandava um algoritmo guloso pra cima e outro pra baixo.

Linhas retiradas pelo algoritmo guloso

Energia Infinita (ou nula)

Olhando o vídeo do cara do siggraph também nos deu vontade de fazer algo para remover partes da imagem ou até preservar essas partes. Para isso, adicionamos uma opção que possibilita entrar com uma mascara que vai informar a região que tem energia infinita (ou seja, vai ser preservada, nunca vai ser removida) e a região que tem energia nula (o famigerado –infinito… o buraco negro da energia… ou seja, indica que com certeza aquela região vai ser removida). Nos testes realizados pela Anvisa nós não tivemos bons resultados em humanos, então use por sua conta e risco.

Redução de 100 linhas sem uso de mascara

Redimensionamento de 100 linhas horizontais com mascara positiva e negativa. Sempre sobra um resto da pessoa. A imagem também não ajuda muito, é muito pequena etc, mas dá para entender o conceito de mascaras.

Resultados

Mais um bom resultado (o que não acontece sempre). Reduzi 50 linhas horizontais e a mulher foi preservada, mesmo sem usar mascara. O método convencional deformou a imagem, como esperado.

O programinha é bem simples né? O código estará disponível no Google Code com a licença mais chulé possível (assim que eu tiver tempo), acho que é aquela que você pode alterar o código, usar ele para fins comerciais, enfim. Não lembro se a versão que está lá é a ultima, mas provavelmente a única coisa que mudei foram as heurísticas do algoritmo guloso. Qualquer duvida, use os comentários que minha secretária seleciona as melhores (ou mais fáceis) duvidas para eu responder! Uahuhahuauha

Anúncios

Deixe um comentário

Arquivado em Computação Gráfica, Desenvolvimento, Geek, Java, Processamento de Imagens

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s