Tenho essa imagem
e queria pegar o x e o y do centro de cada circulo. Já tentei de várias maneiras, mas em nenhuma tive sucesso. Minha pergunta é se existe alguma lib java para fazer isso ou algum algoritmo específico, se sim por favor me indique.
Tenho essa imagem
e queria pegar o x e o y do centro de cada circulo. Já tentei de várias maneiras, mas em nenhuma tive sucesso. Minha pergunta é se existe alguma lib java para fazer isso ou algum algoritmo específico, se sim por favor me indique.
A resposta que você já tem é muito boa e fornece um algoritmo simples e muito eficiente para a imagem de exemplo fornecida. Entretanto, ele pode não funcionar bem para imagens mais complexas, contendo, por exemplo, ruído ou círculos sobrepostos ou incompletos (nos cantos da imagem). Como você não forneceu detalhes do seu domínio de problema, talvez essas variações possam ocorrer.
Nesse sentido, uma alternativa muito bacana é a Transformada de Hough. Esse algoritmo permite encontrar em uma imagem qualquer tipo de forma que seja parametrizável por meio de uma equação matemática (tais como retas, círculos, elípses, etc).
O princípio matemático desse algoritmo é facilmente explicado considerando o exemplo mais simples: a identificação de retas em uma imagem. Considere os gráficos abaixo:
Suponha que uma imagem contém um conjunto de pontos que, se ligados, traçam uma reta (imagem da esquerda). A equação geral de uma reta é . Assim, em um ponto qualquer da imagem, de coordenadas , há infinita retas que passam por ele (as retas mais claras na imagem): basta variar os parâmetros (a inclinação da reta) e (a altura que ela corta no eixo ) para os valores fixos. Naturalmente, isso vale para qualquer outro ponto. E como se pode perceber pelo desenho da esquerda, há apenas uma reta que passa por todos os pontos (a reta mais escura na imagem). Isso significa que para todos esses pontos, a equação dessa reta específica tem o mesmo valor de e .
Ao invés de representar cada ponto no espaço , nós os representarmos no espaço (também chamado de espaço paramétrico, ilustrado na figura da direita). Nesse espaço, um ponto do espaço original agora é descrito por uma reta (devido ao ajuste na equação para considerar os parâmetros como variáveis) com todas as combinações de valores e que, lembre-se, descrevem todas as retas possíveis que passam naquele ponto no espaço original . Desse modo, quando existe uma reta que liga todos os pontos no espaço original, as retas no espaço de parâmetro que descrevem cada um dos pontos coincidem em um local exato: nos valores dos parâmetros e que justamente satisfazem a equação da reta no espaço original.
Assim, o algoritmo simplesmente trabalha no espaço paramétrico e vai testando, ponto a ponto e para cada possível valor de e , onde se encontram esses cruzamentos. Ele faz isso construindo uma matriz z-dimensional (vide figura abaixo) onde z
é o número de parâmetros na equação representativa da forma que se busca. Essa matriz armazena "contagens" de ocorrências dos valores dos parâmetros (tanto que é comumente chamada de matriz de acumuladores) em intervalos discretos. Por exemplo, no caso da equação da reta anterior, a matriz é a seguinte:
Os valores dessa matriz são inicializados para 0
e conforme o algoritmo é executado eles são incrementados toda vez que um ponto qualquer da imagem original tiver uma reta com parâmetros e no intervalo utilizado. No final, basta escolher o par de parâmetros com mais "votos" (com maior acumulador). Ele indicará a melhor reta estimada que passa por todos os pontos analisados.
Eu espero que essa explicação seja suficiente. Mas se precisar de uma explicação passo-a-passo, esse vídeo (em inglês) pode ser de muita ajuda.
É mais comum utilizar na detecção de retas a representação da equação na forma polar (, em que representa o vetor normal à reta e é o ângulo desse vetor em relação ao eixo horizontal), porque assim se evita ter de tratar casos em que o valor do parâmetro é infinito (a reta está inclinada em 90º).
No caso da detecção de círculos (o seu interesse), utiliza-se comumente a equação da circunferência na forma paramétrica (onde são as coordenadas do centro do círculo, é seu raio e é o ângulo em relação ao eixo horizontal):
Esse algoritmo tem como vantagens ser razoavelmente simples e fácil de implementar, ser robusto à ruído (pois o ruído gera menos "votos"/acumuladores) e a dados parciais (os dados de apenas parte de um círculo, por exemplo, ainda assim geram bastante acumuladores para um mesmo conjunto de parâmetros). A principal desvantagem é que ele se torna computacionalmente custoso conforme o número de parâmetros cresce. No exemplo da reta a matriz era bidimensional pois utilizava-se 2 parâmetros. No caso do círculo são 3, fazendo com que agora tenhamos uma matriz tridimensional para manipular.
Eu construí um código de exemplo, da forma mais simples e didática possível. Ele segue abaixo. Vale notar o seguinte:
1 - Ele foi feito pensando mesmo na didática. Então não está tão otimizado quanto poderia. Por exemplo, o espaço de armazenamento da matriz de acumuladores poderia ser diminuido conforme a configuração de raio mínimo e máximo, e eu simplesmente aloco a área máxima mesmo que não a utilize completamente. Além disso, a ordenação dos círculos encontrados e a eliminação de círculos semelhantes foi feita de forma bem simples e direta, com mais de uma varredura da matriz de acumuladores. Certamente há formas melhor de fazer isso.
2 - A definição dos limites de parâmetros foi feita de forma empírica. Por exemplo, no caso do ângulo eu simplesmente dividi a matriz em 360 graus, em intervalos de 1 grau. E no caso do raio, ele vai do mínimo configurado ao máximo calculado (a metade da diagonal da imagem), também em intervalos de 1 pixel. Essa não é necessariamente a forma correta de se fazer. Analisando código existente, percebe-se que é mais comum fazer o intervalo angular ser 1/8 do menor raio (admito que não sei exatamente a razão disso, mas certamente tem a ver com desempenho de armazenamento vs desempenho de resultado de detecção).
3 - Apesar de esse ser um algoritmo simples e fácil de implementar, na prática não vale a pena reimplementá-lo. Há inúmeras implementações disponíveis, e a mais indicada é a do OpenCV - que também pode ser utilizado em Java.
Eis o código:
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.Image;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.net.URL;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class Teste {
/**
* Inner class para representação de círculos.
*/
public static class Circle {
/** Coordenada x do centro do círculo. */
public int x;
/** Coordenada y do centro do círculo. */
public int y;
/** Raio do círculo em pixels. */
public int r;
/**
* Construtor da classe.
* @param x Coordenada x do centro do círculo.
* @param y Coordenada y do centro do círculo.
* @param r Raio do círculo em pixels.
*/
public Circle(int x, int y, int r) {
this.x = x;
this.y = y;
this.r = r;
}
/**
* Verifica se os círculos são similares segundo um limiar.
* @param oOther Instância do outro círculo para comparação.
* @param iThreshold Inteiro com o limiar para comparação.
* @return Verdadeiro se os círculos são similares segundo
* o limiar dado, falso caso contrário.
*/
public boolean similarTo(Circle oOther, int iThreshold) {
return Math.abs(oOther.x - x) <= iThreshold &&
Math.abs(oOther.y - y) <= iThreshold &&
Math.abs(oOther.r - r) <= iThreshold;
}
};
/**
* Cria uma janela para exibição da imagem dada.
* @param oImage Objeto BufferedImage com a imagem a ser exibida.
* @param sTitle String com o título da janela.
* @return Instância de JFrame com a janela criada.
*/
private static JFrame showImage(Image oImage, String sTitle) {
JFrame oWindow = new JFrame();
JPanel oPanel = new JPanel(new BorderLayout());
JLabel oWidget = new JLabel(new ImageIcon(oImage));
oPanel.add(oWidget);
oWindow.add(oPanel);
oWindow.setVisible(true);
oWindow.setTitle(sTitle);
oWindow.pack();
oWindow.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
return oWindow;
}
/** Máscara para cálculo do gradiente por convolução no eixo X. */
private static int[][] SOBEL_X = {
{ -1, 0, +1 },
{ -2, 0, +2 },
{ -1, 0, +1 },
};
/** Máscara para cálculo do gradiente por convolução no eixo Y. */
private static int[][] SOBEL_Y = {
{ +1, +2, +1 },
{ 0, 0, 0 },
{ -1, -2, -1 },
};
/**
* Processa a imagem (por convolução) para extração das bordas.
* @param oImage BufferedImage com a instância da imagem original.
* @return BufferedImage com a imagem binária contendo apenas as bordas (em
* branco) sobre o fundo (em preto).
*/
private static BufferedImage getEdges(BufferedImage oImage) {
BufferedImage oRet = new BufferedImage(oImage.getWidth(), oImage.getHeight(), oImage.getType());
// Percorre a imagem para fazer a convolução
for(int x = 0; x < oImage.getWidth(); x++) {
for(int y = 0; y < oImage.getHeight(); y++) {
// Calcula as somas ponderadas pelas máscaras no pixel atual
int iSumX = 0, iSumY = 0;
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
int xl = x + (i - 1);
int yl = y + (j - 1);
int iValue;
if(xl >= 0 && xl < oImage.getWidth() && yl >= 0 && yl < oImage.getHeight()) {
Color oColor = new Color(oImage.getRGB(xl, yl));
iValue = (int) Math.ceil((0.21 * oColor.getRed() + 0.72 * oColor.getGreen() + 0.07 * oColor.getBlue()));
}
else { // Considera pixels fora da imagem com o mesmo valor do pixel atual
Color oColor = new Color(oImage.getRGB(x, y));
iValue = (int) Math.ceil((0.21 * oColor.getRed() + 0.72 * oColor.getGreen() + 0.07 * oColor.getBlue()));
}
iSumX += iValue * SOBEL_X[i][j];
iSumY += iValue * SOBEL_Y[i][j];
}
}
// Calcula a magnitude do gradiente no pixel e atualiza a imagem de retorno
int iMag = (int) Math.ceil(Math.sqrt(Math.pow(iSumX, 2) + Math.pow(iSumY, 2)));
oRet.setRGB(x, y, iMag > 254 ? Color.WHITE.getRGB() : Color.BLACK.getRGB());
}
}
return oRet;
}
/**
* Cria uma tabela de referência para os cálculos envolvendo seno e cosseno,
* como forma de otimizar o desempenho do algoritmo.
* @param iMaxRadius Inteiro com o maior raio buscado (utilizado na definição
* do tamanho da estrutura de dados).
* @return Matriz de 3 dimensões com os dados do seno e cosseno dos diferentes
* ângulos possíveis, já multiplicados pelos valores de raio possíveis.
*/
private static int[][][] buildLookupTable(int iMaxRadius) {
// A tabela tem espaço para 2 valores (do seno e do cosseno), n raios
// (sendo n a metade da diagonal da imagem = raio do maior círculo
// possível) e 360 graus (theta).
int aTable[][][] = new int[2][iMaxRadius + 1][361];
for(int iRadius = 0; iRadius <= iMaxRadius; iRadius++) {
for(int iAngle = 0; iAngle <= 360; iAngle++) {
double dRad = Math.PI * iAngle / 180; // ângulo em radianos
int iCos = (int) (iRadius * Math.cos(dRad));
int iSin = (int) (iRadius * Math.sin(dRad));
aTable[0][iRadius][iAngle] = iSin;
aTable[1][iRadius][iAngle] = iCos;
}
}
return aTable;
}
/**
* Processa a imagem de bordas (pela transformada de Hough de círculos) para extração
* dos círculos.
* @param oImage BufferedImage com a instância da imagem binária com as bordas.
* @param iMinRadius Inteiro com o menor raio a ser procurado.
* @param iMaxRadius Inteiro com o maior raio a ser procurado.
* @param iMaxCircles Inteiro com o número máximo de círculos a ser devolvido.
* @return
*/
private static Circle[] getCircles(BufferedImage oImage, int iMinRadius, int iMaxRadius, int iMaxCircles) {
// Constroi a tabela de lookup (pra agilizar os cálculos)
int aTable[][][] = buildLookupTable(iMaxRadius);
// Calcula os acumuladores na imagem, segundo a equação paramétrica do círculo
int aAcc[][][] = new int[oImage.getWidth()][oImage.getHeight()][iMaxRadius+1];
for(int x = 0; x < oImage.getWidth(); x++) {
for(int y = 0; y < oImage.getHeight(); y++) {
// Ignora pixels que não contêm bordas
if(oImage.getRGB(x, y) == Color.BLACK.getRGB())
continue;
for(int iRadius = iMinRadius; iRadius <= iMaxRadius; iRadius++) {
for(int iAngle = 0; iAngle <= 360; iAngle++) {
int a = x + aTable[1][iRadius][iAngle];
int b = y + aTable[0][iRadius][iAngle];
if(a >= 0 && a < oImage.getWidth() && b >= 0 && b < oImage.getHeight())
aAcc[a][b][iRadius]++;
}
}
}
}
// Cria estrutura ordenada pelos acumuladores
Map<Integer, Circle> mAcc = new TreeMap<Integer, Circle>(new Comparator<Integer>()
{
@Override
public int compare(Integer i, Integer j) {
return j.compareTo(i);
}
});
for(int a = 0; a < aAcc.length; a++) {
for(int b = 0; b < aAcc[a].length; b++) {
for(int r = 0; r < aAcc[a][b].length; r++) {
int iAcc = aAcc[a][b][r];
mAcc.put(iAcc, new Circle(a, b, r));
}
}
}
// Move os dados para um array, já removendo as duplicidades
ArrayList<Circle> aRet = new ArrayList<Circle>();
for (Map.Entry<Integer, Circle> oCur: mAcc.entrySet()) {
// Procura no ArrayList por um círculo parecido
// Se existir, ignora. Caso contrário, adiciona.
boolean bExist = false;
for(Circle oExist: aRet) {
if(oCur.getValue().similarTo(oExist, 10))
{
bExist = true;
break;
}
}
if(!bExist)
aRet.add(oCur.getValue());
}
// Devolve o número de círculos desejado
return aRet.subList(0, iMaxCircles).toArray(new Circle[0]);
}
public static void main(String[] args) {
// Carrega a imagem original
BufferedImage oImage = null;
try {
URL oURL = new URL("https://i.sstatic.net/FWgw0.png");
oImage = ImageIO.read(oURL);
}
catch (IOException e) {
System.out.println("Oops! Não foi possível carregar a imagem.");
System.exit(-1);
}
// Exibe a imagem original
JFrame oSource = showImage(oImage, "Imagem original");
// Processa a imagem original para detecção das bordas
BufferedImage oEdges = getEdges(oImage);
// Exibe a imagem com as bordas detectadas
JFrame oTarget = showImage(oEdges, "Imagem com as bordas");
oTarget.setLocation(oSource.getLocation().x + oSource.getWidth(), oSource.getLocation().y);
// Aplica a transformada de Hough para o círculo
int iMinRadius = 10;
int iMaxRadius = (int) Math.ceil(Math.sqrt(Math.pow(oImage.getWidth(), 2) + Math.pow(oImage.getHeight(), 2)) / 2);
int iMaxCircles = 4;
Circle[] aCircles = getCircles(oEdges, iMinRadius, iMaxRadius, iMaxCircles);
// Desenha os círculos na imagem original
Graphics2D g = oImage.createGraphics();
g.setPaint(Color.BLACK);
g.setStroke(new BasicStroke(2, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
for(int i = 0; i < aCircles.length; i++) {
Circle oCircle = aCircles[i];
g.drawLine(oCircle.x-5, oCircle.y, oCircle.x+5, oCircle.y);
g.drawLine(oCircle.x, oCircle.y-5, oCircle.x, oCircle.y+5);
g.drawOval(oCircle.x - oCircle.r, oCircle.y - oCircle.r, 2 * oCircle.r, 2 * oCircle.r);
}
g.dispose();
// Exibe a imagem com as anotações dos círculos encontrados
JFrame oFinal = showImage(oImage, "Imagem original anotada");
oFinal.setLocation(oTarget.getLocation().x + oTarget.getWidth(), oTarget.getLocation().y);
}
}
O primeiro passo é limitar os dados a serem processados. Se a Transformada de Hough fosse aplicada sobre todos os pixels da imagem original, ia demorar demais e potencialmente gerar muita confusão (muitos acumuladores parecidos). Assim, primeiramente eu produzo uma imagem binária (contendo só cor preta e branca) apenas com as bordas encontradas na imagem. O melhor modo de fazer isso é aplicar o filtro Sobel por meio de convolução no domínio espacial seguido de uma limiarização simples (não vou explicar esse processo em detalhes por falta de espaço, mas leia os links da Wikipedia e analise o código pra entender).
Note essa linha de código no método
getEdges
:oRet.setRGB(x, y, iMag > 254 ? Color.WHITE.getRGB() : Color.BLACK.getRGB());
O valor
254
ali é o limiar utilizado para limiarização. Ou seja, eu praticamente ignoro (faço ser igual à cor preta) qualquer valor de magnitude do gradiente que seja menor ou igual a 254. Isso deixa as bordas mais finas, e reduz informação (pixels de borda) na imagem resultante. Vc pode/deve ajustar esse limiar conforme o seu domínio de problema.
Então, a transformada de Hough é aplicada apenas aos pixels em branco na imagem de bordas (ou seja, apenas aos pixels de borda). Essa abordagem é muito comum na literatura, pois esses são os pixels essenciais para a detecção de formas. :)
O resultado da execução desse código para a sua imagem de exemplo (lida diretamente da sua postagem) é esse:
Eu fiz uma imagem de exemplo com algumas variações que podem ser difícies de detectar no algoritmo mais simples anterior:
O resultado do código para essa imagem é esse:
Note que você precisa alterar para 7 o número máximo de círculos na chamada do método getCircles
:
. . .
int iMinRadius = 10;
int iMaxRadius = (int) Math.ceil(Math.sqrt(Math.pow(oImage.getWidth(), 2) + Math.pow(oImage.getHeight(), 2)) / 2);
int iMaxCircles = 7; // ALTERE AQUI CONFORME O NÚMERO DE CÍRCULOS EXISTENTES
Circle[] aCircles = getCircles(oEdges, iMinRadius, iMaxRadius, iMaxCircles);
. . .
O filtro de Sobel aplicado antes da transformada de Hough é fundamental para a qualidade do resultado. Outra alternativa bastante utilizada é o filtro de Canny. Ainda assim, dependendo do tipo de imagem utilizada, talvez você precise também aplicar outros filtros para redução de rúido (usando, por exemplo, um filtro Gaussiano ou até mesmo filtros mais simples como a média e mediana.
Um exemplo é para a detecção de moedas de Real na imagem abaixo. Como apenas a detecção de bordas ainda deixa muitos pixels de borda devido à textura das moedas, o resultado final (para a detecção de 10 círculos com o algoritmo acima) não é exatamente o esperado:
Note que um círculo pequeno na moeda de 5 centavos mais à direita foi detectado com muitos acumuladores. Esse erro talvez deva-se às escolhas empíricas descritas anteriormente, e talvez pudesse ser corrigido com o ajuste do raio mínimo (se você souber de antemão o tamanho da menor moeda na imagem, por exemplo). Mas note como a imagem de bordas tem muitos detalhes. Eles fazem não somente o processamento demorar mais como também não ajudam na detecção de círculos ideais.
Esse problema parece ser muito difícil, mas não é.
Antes de apresentar a minha solução, aconselho que use essas bibliotecas do java:
import javax.imageio.ImageIO
import java.awt.image.BufferedImage
Bem, minha solução é essa:
Leitura:
Antes de tudo, crie uma matriz com as dimensões da imagem de entrada.
Ande pixel por pixel da imagem de entrada, e coloque zeros nas coordenadas da matriz que representam o branco na foto, e uns para as que representam o vermelho. No final, você terá uma matriz binária que representa a foto, 0 == branco, 1 == vermelho.
Processamento:
Sacou a ideia? Vai andando pixel a pixel até tocar o circulo, NECESSARIAMENTE o primeiro ponto que você tocar vai ser o mais "alto", ou seja, se você andar pra "baixo" vai chegar na outra extremidade percorrendo todo o diâmetro.
Abraço!
Acho que tudo é simples, muita complicação!!
//************************************************************
//* (hBitmap, x, y, Width, Height) imagem em preto e branco.
//************************************************************
HB_FUNC (BT_BITMAPBLACKONWHITE)
{
HDC memDC;
HBITMAP hBitmap;
register INT x, y;
INT x1, y1, Width, Height, c;
COLORREF nCor;
hBitmap = (HBITMAP) hb_parnl (1);
x1 = (INT) hb_parnl (2);
y1 = (INT) hb_parnl (3);
Width = (INT) hb_parnl (4);
Height = (INT) hb_parnl (5);
memDC = CreateCompatibleDC(NULL);
SelectObject(memDC, hBitmap);
for (y = y1; y < (y1 + Height); y++)
{
for (x = x1; x < (x1 + Width); x++)
{
nCor = GetPixel(memDC, x, y);
if (nCor < RGB(50,50,50))
{
SetPixel(memDC, x, y, RGB(255,255,255));
}
else if (nCor > RGB(60,60,60) & nCor <= RGB(255,255,255))
{
SetPixel(memDC, x, y, RGB(0,0,0));
}
else
SetPixel(memDC, x, y, RGB(255,255,255));
}
}
DeleteDC(memDC);
}
código completo em C.
Sem complicações e cálculos. Lembre-se teoria é uma coisa pratica é outra.