Oi galera!
Quero montar um algoritmo que encontre retangulos em uma dada imagem. Nao tenho ideia de por onde começar. Nunca vi nada do genero.
Alguem poderia me dar uma luz?
Grato
Pode começar estudando processamento de imagens, algoritmos de detecção de bordas, reconhecimento de padrão e por ai vai…
Da pra encontrar varios algoritmos prontos na net.
Dá uma pesquizada na Web por SIFT.
+++
Se não me engano, Sobel também pode ajudar você.
Eu já usei Sobel para detecção das bordas dentro de uma imagem.
clone_zealot,
O problema de se usar o SOBEL, seria se além do retangulo, tivesse outras formas.
Além disso, se o retangulo estivesse em qualquer ângulo, a detecção ficaria complicada.
Mikhas,
Pode dar mais detalhes da aplicação em que será usado esse reconhecimento/detecção ?
+++
Prezado Mikhas,
Se ainda lhe interessar, vou dar aqui uma “pincelada” sobre rotulação de componentes conexos dentro de imagens binárias (preto e branco).
Entenda que para que a entrada seja uma imagem colorida, diversas transformações deverão ser feitas para que a mesma chegue ao “preto e branco” e uso deste algoritmo. Não faz parte deste escopo explicar estas etapas. Tomarei também que a imagem possui o fundo branco (número 1) e as “figuras” estão desenhadas na cor preta (número 0). Um exemplo de imagem com 2 figuras está apresentado abaixo.
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1 0 0 0
0 0 0 0 1 1 1 0 0 0 1
1 0 0 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1
Para não entrar com muitos conceitos, vou diretamente ao algoritmo. Depois, se for de interesse aprender os conceitos, compreenda bem o texto que segue.
A idéia aqui é percorrer uma dada imagem de cima pra baixo, da esquerda para a direita. Pela natureza desta sequência, quando você estiver analisando um ponto P na imagem, os pontos à sua esquerda e acima já terão sido analisados.
Quando o ponto P analisado tiver a cor do fundo (branca), passaremos adiante. Caso ele tenha a cor preta, analisaremos os pixels E e C, que são os pixels à esquerda e acima, respectivamente. Se E e C possuírem o valor 1 (cor branca), atribua um novo rótulo a P. Se apenas um deles (E ou C) possuírem a cor preta, atribua este rótulo a P. Se ambos tiverem a cor preta e seus rótulos forem iguais, atribua este rótulo a P. Caso contrário, se ambos tiverem a cor preta e seus rótulos forem diferentes, então atribua o rótulo de C a P e substitua todas as ocorrências do rótulo E pelo rótulo de C. A quantidade de rótulos atribuídos será igual ao número de figuras dentro da imagem, e as figuras estarão representadas na matriz de rotulação (matriz mRot do algoritmo).
Algoritmo:
BufferedImage bufi = ImageIO.read(getClass().getResourceAsStream("imagem.bmp"));
int imagemW = bufi.getWidth();
int imagemH = bufi.getHeight();
// Criando a matriz, que será inicializada
// com o número 0 por toda ela.
int[][] mRot = new int[imagemH][imagemW];
// A variável abaixo armazenará qual rótulo
// será o próximo a ser utilizado.
int proximoRotulo = 1;
// Já irei armazenar o número de rótulos
// atribuídos, para sabermos quantas figuras
// encontramos na imagem.
int numTotalRotulos = 0;
// Abaixo temos o algoritmo para preenchimento
// da matriz mRot.
for(int y=0; y<imagemH; y++)
{
for(int x=0; x<imagemW; x++)
{
// pixel atual, pixel da esquerda e pixel acima
// preenchidos ou não.
Boolean pixelPPreto, pixelCPreto, pixelEPreto;
pixelPPreto = (new Color(bufi.getRGB(x, y))).Equals(Color.BLACK);
pixelCPreto = (y > 0) ? (new Color(bufi.getRGB(x, y-1))).Equals(Color.BLACK) : false;
pixelEPreto = (x > 0) ? (new Color(bufi.getRGB(x-1, y))).Equals(Color.BLACK) : false;
// Buscando os rótulos dos pixels acima e à esquerda
int rotuloC = pixelCPreto ? mRot[y-1][x] : 0;
int rotuloE = pixelEPreto ? mRot[y][x-1] : 0;
// - Se ambos não possuem rótulo, P recebe um novo rótulo;
// - Se um deles possui rótulo, P recebe este rótulo;
// - Se ambos possuem mesmos rótulos, P recebe este rótulo;
// - Se ambos possuem rótulos diferentes, atribua
// a P um destes rótulos e substitua todas as
// ocorrências do outro rótulo.
int rotuloP;
if(rotuloC == 0 && rotuloE == 0)
{
rotuloP = proximoRotulo++;
// Novo rótulo encontrado.
numTotalRotulos++;
}
else if(rotuloC == rotuloE)
rotuloP = rotuloC;
else if(rotuloC == 0 || rotuloE == 0)
rotuloP = (rotuloC != 0) ? rotuloC : rotuloE;
else if(rotuloC != rotuloE)
{
// Atribua a P o rótulo de C
rotuloP = rotuloC;
// Substitua todos os rótulos de E
// da figura pelo de C
for(int yTmp = 0; yTmp < imagemH; yTmp++)
for(int xTmp = 0; xTmp < imagemW; xTmp++)
if(mRot[yTmp][xTmp] == rotuloE)
mRot[yTmp][xTmp] = rotuloC;
// Um rótulo foi removido.
numTotalRotulos--;
}
mRot[y][x] = rotuloP;
}
}Ao final do algoritmo, a variável numTotalRotulos terá a quantidade de figuras encontradas dentro da imagem.
[color=darkblue]Agora, vamos a um pouco mais de conceitos. [/color]
Para reconhecer uma figura, devemos analisar a vizinhança de cada pixel, para saber se ele está “conectado” a outras “regiões” (que denominei aqui de figuras) e saber se a vizinhança está na mesma figura ou se a vizinhança faz parte de outra figura. Ou seja, se as “regiões” estão separadas. A análise desta vizinhança chama-se “determinação de componentes conexos”. E a vizinhança pode ser tomada como vizinhança-de-4 ou vizinhança-de-8.
Na vizinhança-de-4, a gente analisa o pixel acima, o pixel abaixo, o da esquerda e o da direita. Na representação abaixo, apenas os pixels X são vizinhos do pixel P.
0 x 0
x P x
0 x 0
Na vizinhança-de-8, a gente analisa também os pixels das diagonais, como mostrado abaixo.
x x x
x P x
x x x
Por exemplo, Se dois pixels estão em diagonal e são da cor preta (representado abaixo por 0), e todos os outros da vizinhança são da cor branca (representado abaixo por 1), eles fazem parte da mesma figura somente se a vizinhança-de-8 for utilizada. Mas não fazem parte da mesma figura se a vizinhança-de-4 for utilizada. Abaixo ilustro a situação:
1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 1
Ou seja, pela vizinhança-de-4, temos duas figura diferentes. E pela vizinhança-de-8, temos uma única figura.
O algoritmo passado acima para detecção de figuras em uma imagem considera a vizinhança-de-4. Ou seja, uma linha em diagonal seria contada como N figuras, com N sendo o tamanho da linha diagonal. Se o algoritmo utilizasse o conceito de vizinhança-de-8, a linha diagonal seria considerada como uma única figura. Contudo, este algoritmo é um pouco mais complexo, devido ao mesmo considerar também o valor dos pixels diagonais a P.
Se for do interesse, publique aqui uma dúvida e eu escreverei o algoritmo considerando a vizinhança-de-8. Contudo, seria uma boa prática tentar criá-lo sozinho.
Qualquer dúvida, é só perguntar!
P.S.: Não testei o algoritmo. Escrevi na munheca. Se algum erro de sintaxe ou de compilação for encontrado, favor comentar.
Abraços,
Thales Medeiros.