Find the center of each circle in the image

Question

I have this image

and wanted to catch the x and y of the center of each circle. I have tried several ways, but in none have I succeeded. My question is if there is any java lib to do this or any specific algorithm, if yes please tell me.

Answer 1

The answer you already have is very good and provides a simple and very efficient algorithm for the example image provided. However, it may not work well for more complex images, containing, for example, overlapping or incomplete noise or circles (in the corners of the image). Since you have not provided details of your problem domain, perhaps these variations may occur.

In that sense, a very cool alternative is the Hough transformed. This algorithm allows finding in an image any kind of way which can be parameterizable by means of a mathematical equation (such as lines, circles, ellipses, etc.).

Mathematical Principle

The mathematical principle of this algorithm is easily explained by considering the simplest example: the identification of lines in an image. Consider the charts below:

Suppose an image contains a set of points that, if linked, trace a line (left image). The general equation of a line is . So, at any point in the image, coordinates , there are infinite lines that pass through it (the clearest lines in the image): just vary the parameters (the inclination of the straight line) and (the height it cuts on the axle ) for the values fixed. Naturally, this holds true for any other point. And as you can see from the drawing on the left, there is only one line that goes through all the points (the darkest line in the image). This means that for all these points, the equation of this specific line has the same value of and .

Instead of representing each point in space , we represent them in space (also called parametric space, illustrated in the figure on the right). In this space, a point of the original space is now described by a straight line (due to the adjustment in the equation to consider the parameters as variables) with all combinations of values and which, remember, describe all possible lines that pass that point in original space . Thus, when there is a line that connects all points in the original space, the lines in the parameter space that describe each of the points coincide in an exact location: in the values of the parameters and which precisely satisfy the equation of the line in the original space.

Thus, the algorithm simply works in parametric space and tests, point by point and for each possible value of and , where these intersections are. He does this by constructing a z-dimensional matrix (see figure below) where z is the number of parameters in the representative equation as sought. This matrix stores "counts" of occurrences of parameter values (so much so that it is commonly called a matrix of accumulators) at discrete intervals. For example, in the case of the previous line equation, the matrix is the following:

The values of this matrix are initialized to 0 and as the algorithm is executed they are incremented every time any point of the original image has a line with parameters and in the range used. In the end, simply choose the parameter pair with the most "votes" (with the largest accumulator). It will indicate the best estimated line that goes through all points analyzed.

I hope that explanation is sufficient. But if you need one step-by-step explanation, this video (in English) can be very helping.

It is more common to use the representation of the equation in polar form when detecting straight lines (, in which represents the normal vector to the line and is the angle of that vector relative to the horizontal axis), because this avoids having to deal with cases where the value of the parameter is infinite (the line is inclined 90º).

In the case of the detection of circles (their interest), it is commonly used the equation of the circle in parametric form (where are the coordinates of the center of the circle, is its radius and is the angle relative to the horizontal axis):

This algorithm has the advantages of being reasonably simple and easy to implement, being robust to noise (because noise generates less "votes"/accumulators) and partial data (data from only part of a circle, for example, still generate enough accumulators for the same set of parameters). The main drawback is that it becomes computationally costly as the number of parameters grows. In the example of the straight line the matrix was two-dimensional because 2 parameters were used. In the case of the circle there are 3, causing us now to have a three-dimensional matrix to manipulate.

Implementation

I built an example code in the simplest and most didactic way possible. It follows below. It is worth noting the following:

1 - It was made even thinking about the didactics. So it is not as optimized as it could be. For example, the storage space of the accumulator array could be reduced according to the minimum and maximum radius setting, and I simply allocate the maximum area even if I don’t use it completely. In addition, the ordering of the found circles and the elimination of similar circles was made very simple and direct, with more than one scan of the matrix of accumulators. Surely there are better ways to do that.

2 - The definition of parameters limits was made empirically. For example, in the case of the angle I simply divided the matrix into 360 degrees, in 1 degree intervals. And in the case of lightning, it goes from the minimum set to the maximum calculated (half of the diagonal image), also in 1 pixel intervals. That’s not necessarily the right way to do it. Analyzing existing code, it is perceived that it is more common to make the angular interval be 1/8 of the smallest radius (I admit I don’t know exactly the reason for this, but it certainly has to do with storage performance vs detection result performance).

3 - Although this is a simple and easy to implement algorithm, in practice it’s not worth it reimplement it. There are numerous implementations available, and the most suitable is that of Opencv - that also can be used in Java.

Here’s the code:

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("http://i.stack.imgur.com/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);
    }

}

How the code works

The first step is to limit the data to be processed. If the Hough transform were applied to all pixels of the original image, it would take too long and potentially generate too much confusion (many similar accumulators). So, first I produce a binary image (containing only black and white color) only with the edges found on the image. The best way to do that is to apply the sobel filter by means of convolution in the space domain followed by a limiarization simple (I won’t explain this process in detail for lack of space, but read the Wikipedia links and analyze the code to understand).

Note this line of code in the method getEdges:

oRet.setRGB(x, y, iMag > 254 ? Color.WHITE.getRGB() : Color.BLACK.getRGB());

The value 254 there is the threshold used for limiarization. I mean virtually ignore (I make it equal to black) any value of magnitude of the gradient that is less than or equal to 254. This leaves the edges more thin, and reduces information (edge pixels) on the resulting image. Vc can/should adjust this threshold according to your problem area.

So the Hough transform is applied only to blank pixels on the border image (i.e., only to the edge pixels). This approach is very common in the literature, because these are the essential pixels for the detection of shapes. :)

The result of executing this code for your example image (read directly from your post) is this:

I made an example image with some variations that may be difficult to detect in the previous simpler algorithm:

The result of the code for this image is this:

Note that you need to change to 7 the maximum number of circles in the method call 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);
. . .

On the importance of intermediate processing

The Sobel filter applied before the Hough transform is critical to the quality of the result. Another widely used alternative is the canny filter. Still, depending on the type of image used, you may need also apply other filters for reducing noise (using, for example, a gaussian filter or even simpler filters like the mean and median.

An example is for detecting Real coins in the image below. Since only the edge detection still leaves many border pixels due to the texture of the coins, the final result (for the detection of 10 circles with the above algorithm) is not exactly as expected:

Note that a small circle on the 5 cent coin further to the right was detected with many accumulators. This error may be due to the empirical choices described above, and perhaps could be corrected by adjusting the minimum radius (if you know beforehand the size of the smallest coin in the image, for example). But note how the border image has many details. They not only make processing take longer but also do not help in detecting optimal circles.

Answer 2

This problem seems to be very difficult, but it is not.

Before presenting my solution, I advise you to use these java libraries:

import javax.imageio.ImageIO
import java.awt.image.BufferedImage

Well, my solution is this:

Reading:

• First of all, create a matrix with the dimensions of the input image.

• Walk pixel by pixel of the input image, and put zeros in the coordinates of the matrix that represent the white in the photo, and ones for the ones that represent the red. At the end, you will have a binary matrix representing the photo, 0 == white, 1 == red.

Processing:

• Walk through each coordinate of the matrix seeing if the current coordinate is 1, if it is, that means that you just tangent a circle, that is, touched on its "highest" point (seen from a 2D frame), store this coordinate somewhere. Well, think with me, if I am in Brazil and dig a hole in a straight line and perpendicular to the plane I am standing on, I will leave at the other end of the Earth(Tokyo? ), right? If I measure the length of this "tunnel", I have the diameter of the Earth(considering the Earth a perfect circle), don’t I? So pretend the pixel we’re standing on is Brazil and our circle is the Earth, we’ll dig a hole out of it. How are you gonna do that? Do a for or while, and in this loop, you will walk only in Y, that is, you will walk "down", while the content of the current coordinate is 1, you have not arrived in Japan yet, when the coordinate is 0, welcome to Tokyo, if you have unlucky, you will face Kim Jong Yun in North Korea, I was already kkkk. Inside this Loop add a counter, this counter will have the diameter of the circle when you arrive in Tókio, ie, exit the circle. If you found the diameter, 99.9% of the problem is already dead. You have the tangent point and the diameter, with this, you can find the center, because the center will be = (X , coordinate Y of the tangent point minus the radius).
• Now you have to delete the circle that you just calculated the center, how do you do that? Very quiet, as I said, found the diameter already was. You will calculate a square in which our circle is a circle inscribed on it. Starting from the center, you will add and decrease the ray in both X and Y, that is, you will have four coordinates at the end of the calculations. ALL points within this area delimited by these coordinates will be set to 0, that is, our circle has been deleted and we can do all this again for the next.

You get the idea? You will walk pixel by pixel until you touch the circle, NECESSARILY the first point you touch will be the most "high", IE, if you walk "low" you will reach the other end going through the whole diameter.

Hug!

Answer 3

I think everything is simple, too complicated!!

//************************************************************
//* (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);
} 

complete code in C.

No complications and calculations. Remember theory is a practical thing is another.