Hough transform circle detection algorithm for image processing

Previously, I wrote an article describing the principle of Hoff transformation and detecting straight lines using Hoff transformation, and found that the visits were barbaric.

Many, a little beyond my expectation, many people leave messages saying the code is not well written, there are no comments, and the structure is not very clear, so

I started a second post, introducing the Hough transform circle detection algorithm, with as many detailed comments as possible, introducing the code

Structure. Enable more people to understand and understand.

1: Mathematical principle of Hoff transformation for circle detection

According to the polar coordinates, the coordinates of any point on the circle can be expressed as above, so for any circle, suppose

If the center pixel point p(x0, y0) is known, and the radius of the circle is known, then rotation 360 is derived from the polar coordinate equation for each

Similarly, if you only know the pixel point on the image, the radius of the circle, and rotate 360 degrees, you will sit at the center point

The scalar value must be the strongest. This is the mathematical principle of Hoff transformation to detect circles.

Two: algorithm flow

The algorithm can be roughly divided into the following steps

3. Operation effect

The image is transformed from spatial coordinates to polar effects, with the brightest point being the center of the circle.

The image is transformed from polar to spatial coordinates, and the result of the detection shows that:

Four: Key Code Analysis

Personally, I think this comment is already very detailed, and I wrote it in Chinese

	/**
	 * Hoff transformation processing - detecting the number of circles whose radius size matches
	 * 1. Converting image pixels from 2D space coordinates to polar space
	 * 2. Normalize the intensity of each point in polar space to be between 0 and 255
	 * 3. Find pixel points in 2D space based on the R value of the polar coordinates equal to the input parameter (radius of the circle)
	 * 4. Give the result color (red) to the found spatial pixel points
	 * 5. Returns the result 2D spatial pixel collection
	 * @return int []
	 */
	public int[] process() {

		// For a polar transformation of a circle, we need a 360-degree spatial gradient overlay
		acc = new int[width * height];
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				acc[y * width + x] = 0;
			}
		}
		int x0, y0;
		double t;
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {

				if ((input[y * width + x] & 0xff) == 255) {

					for (int theta = 0; theta < 360; theta++) {
						t = (theta * 3.14159265) / 180; // Angle value 0 ~ 2*PI
						x0 = (int) Math.round(x - r * Math.cos(t));
						y0 = (int) Math.round(y - r * Math.sin(t));
						if (x0 < width && x0 > 0 && y0 < height && y0 > 0) {
							acc[x0 + (y0 * width)] += 1;
						}
					}
				}
			}
		}

		// now normalise to 255 and put in format for a pixel array
		int max = 0;

		// Find max acc value
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {

				if (acc[x + (y * width)] > max) {
					max = acc[x + (y * width)];
				}
			}
		}

		// Normalizing gray values in polar space based on maximum
		int value;
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				value = (int) (((double) acc[x + (y * width)] / (double) max) * 255.0);
				acc[x + (y * width)] = 0xff000000 | (value << 16 | value << 8 | value);
			}
		}
		
		// Draw discovered circles
		findMaxima();
		System.out.println("done");
		return output;
	}

Complete algorithm source code, all commented

package com.gloomyfish.image.transform.hough;
/***
 * 
 * The incoming image is a binary image with a black background and a white target foreground color
 * @author gloomyfish
 * 
 */
public class CircleHough {

	private int[] input;
	private int[] output;
	private int width;
	private int height;
	private int[] acc;
	private int accSize = 1;
	private int[] results;
	private int r; // The radius size of the circle

	public CircleHough() {
		System.out.println("Hough Circle Detection...");
	}

	public void init(int[] inputIn, int widthIn, int heightIn, int radius) {
		r = radius;
		width = widthIn;
		height = heightIn;
		input = new int[width * height];
		output = new int[width * height];
		input = inputIn;
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				output[x + (width * y)] = 0xff000000; //Default image background color is black
			}
		}
	}

	public void setCircles(int circles) {
		accSize = circles; // Number of detections
	}
	
	/**
	 * Hoff transformation processing - detecting the number of circles whose radius size matches
	 * 1. Converting image pixels from 2D space coordinates to polar space
	 * 2. Normalize the intensity of each point in polar space to be between 0 and 255
	 * 3. Find pixel points in 2D space based on the R value of the polar coordinates equal to the input parameter (radius of the circle)
	 * 4. Give the result color (red) to the found spatial pixel points
	 * 5. Returns the result 2D spatial pixel collection
	 * @return int []
	 */
	public int[] process() {

		// For a polar transformation of a circle, we need a 360-degree spatial gradient overlay
		acc = new int[width * height];
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				acc[y * width + x] = 0;
			}
		}
		int x0, y0;
		double t;
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {

				if ((input[y * width + x] & 0xff) == 255) {

					for (int theta = 0; theta < 360; theta++) {
						t = (theta * 3.14159265) / 180; // Angle value 0 ~ 2*PI
						x0 = (int) Math.round(x - r * Math.cos(t));
						y0 = (int) Math.round(y - r * Math.sin(t));
						if (x0 < width && x0 > 0 && y0 < height && y0 > 0) {
							acc[x0 + (y0 * width)] += 1;
						}
					}
				}
			}
		}

		// now normalise to 255 and put in format for a pixel array
		int max = 0;

		// Find max acc value
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {

				if (acc[x + (y * width)] > max) {
					max = acc[x + (y * width)];
				}
			}
		}

		// Normalizing gray values in polar space based on maximum
		int value;
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				value = (int) (((double) acc[x + (y * width)] / (double) max) * 255.0);
				acc[x + (y * width)] = 0xff000000 | (value << 16 | value << 8 | value);
			}
		}
		
		// Draw discovered circles
		findMaxima();
		System.out.println("done");
		return output;
	}

	private int[] findMaxima() {
		results = new int[accSize * 3];
		int[] output = new int[width * height];
		
		// Get the maximum number of first accSize values
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				int value = (acc[x + (y * width)] & 0xff);

				// if its higher than lowest value add it and then sort
				if (value > results[(accSize - 1) * 3]) {

					// add to bottom of array
					results[(accSize - 1) * 3] = value; //pixel value
					results[(accSize - 1) * 3 + 1] = x; // Coordinate X
					results[(accSize - 1) * 3 + 2] = y; // Coordinate Y

					// shift up until its in right place
					int i = (accSize - 2) * 3;
					while ((i >= 0) && (results[i + 3] > results[i])) {
						for (int j = 0; j < 3; j++) {
							int temp = results[i + j];
							results[i + j] = results[i + 3 + j];
							results[i + 3 + j] = temp;
						}
						i = i - 3;
						if (i < 0)
							break;
					}
				}
			}
		}

		// Draw a circle on the original image based on the found radius R, the center point pixel coordinates p(x, y)
		System.out.println("top " + accSize + " matches:");
		for (int i = accSize - 1; i >= 0; i--) {
			drawCircle(results[i * 3], results[i * 3 + 1], results[i * 3 + 2]);
		}
		return output;
	}

	private void setPixel(int value, int xPos, int yPos) {
		/// output[(yPos * width) + xPos] = 0xff000000 | (value << 16 | value << 8 | value);
		output[(yPos * width) + xPos] = 0xffff0000;
	}

	// draw circle at x y
	private void drawCircle(int pix, int xCenter, int yCenter) {
		pix = 250; // Color value, default to white

		int x, y, r2;
		int radius = r;
		r2 = r * r;
		
		// Draw the top, bottom, left and right four points of a circle
		setPixel(pix, xCenter, yCenter + radius);
		setPixel(pix, xCenter, yCenter - radius);
		setPixel(pix, xCenter + radius, yCenter);
		setPixel(pix, xCenter - radius, yCenter);

		y = radius;
		x = 1;
		y = (int) (Math.sqrt(r2 - 1) + 0.5);
		
		// The edge filling algorithm, in fact, can directly cycle through all the pixels and calculate the distance to the center point to do so
		// This method was written by someone else and found to be superb, super good!
		while (x < y) {
			setPixel(pix, xCenter + x, yCenter + y);
			setPixel(pix, xCenter + x, yCenter - y);
			setPixel(pix, xCenter - x, yCenter + y);
			setPixel(pix, xCenter - x, yCenter - y);
			setPixel(pix, xCenter + y, yCenter + x);
			setPixel(pix, xCenter + y, yCenter - x);
			setPixel(pix, xCenter - y, yCenter + x);
			setPixel(pix, xCenter - y, yCenter - x);
			x += 1;
			y = (int) (Math.sqrt(r2 - x * x) + 0.5);
		}
		if (x == y) {
			setPixel(pix, xCenter + x, yCenter + y);
			setPixel(pix, xCenter + x, yCenter - y);
			setPixel(pix, xCenter - x, yCenter + y);
			setPixel(pix, xCenter - x, yCenter - y);
		}
	}

	public int[] getAcc() {
		return acc;
	}

}

UI class for testing:

package com.gloomyfish.image.transform.hough;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.image.BufferedImage;
import java.io.File;

import javax.imageio.ImageIO;
import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class HoughUI extends JFrame implements ActionListener, ChangeListener {
	/**
	 * 
	 */
	public static final String CMD_LINE = "Line Detection";
	public static final String CMD_CIRCLE = "Circle Detection";
	private static final long serialVersionUID = 1L;
	private BufferedImage sourceImage;
// 	private BufferedImage houghImage;
	private BufferedImage resultImage;
	private JButton lineBtn;
	private JButton circleBtn;
	private JSlider radiusSlider;
	private JSlider numberSlider;
	public HoughUI(String imagePath)
	{
		super("GloomyFish-Image Process Demo");
		try{
			File file = new File(imagePath);
			sourceImage = ImageIO.read(file);
		} catch(Exception e){
			e.printStackTrace();
		}
		initComponent();
	}
	
	private void initComponent() {
		int RADIUS_MIN = 1;
		int RADIUS_INIT = 1;
		int RADIUS_MAX = 51;
		lineBtn = new JButton(CMD_LINE);
		circleBtn = new JButton(CMD_CIRCLE);
		radiusSlider = new JSlider(JSlider.HORIZONTAL, RADIUS_MIN, RADIUS_MAX, RADIUS_INIT);
		radiusSlider.setMajorTickSpacing(10);
		radiusSlider.setMinorTickSpacing(1);
		radiusSlider.setPaintTicks(true);
		radiusSlider.setPaintLabels(true);
		numberSlider = new JSlider(JSlider.HORIZONTAL, RADIUS_MIN, RADIUS_MAX, RADIUS_INIT);
		numberSlider.setMajorTickSpacing(10);
		numberSlider.setMinorTickSpacing(1);
		numberSlider.setPaintTicks(true);
		numberSlider.setPaintLabels(true);
		
		JPanel sliderPanel = new JPanel();
		sliderPanel.setLayout(new GridLayout(1, 2));
		sliderPanel.setBorder(BorderFactory.createTitledBorder("Settings:"));
		sliderPanel.add(radiusSlider);
		sliderPanel.add(numberSlider);
		JPanel btnPanel = new JPanel();
		btnPanel.setLayout(new FlowLayout(FlowLayout.RIGHT));
		btnPanel.add(lineBtn);
		btnPanel.add(circleBtn);
		
		
		JPanel imagePanel = new JPanel(){

			private static final long serialVersionUID = 1L;

			protected void paintComponent(Graphics g) {
				if(sourceImage != null)
				{
					Graphics2D g2 = (Graphics2D) g;
					g2.drawImage(sourceImage, 10, 10, sourceImage.getWidth(), sourceImage.getHeight(),null);
					g2.setPaint(Color.BLUE);
					g2.drawString("Original Map", 10, sourceImage.getHeight() + 30);
					if(resultImage != null)
					{
						g2.drawImage(resultImage, resultImage.getWidth() + 20, 10, resultImage.getWidth(), resultImage.getHeight(), null);
						g2.drawString("final result,Red is the test result", resultImage.getWidth() + 40, sourceImage.getHeight() + 30);
					}
				}
			}
			
		};
		this.getContentPane().setLayout(new BorderLayout());
		this.getContentPane().add(sliderPanel, BorderLayout.NORTH);
		this.getContentPane().add(btnPanel, BorderLayout.SOUTH);
		this.getContentPane().add(imagePanel, BorderLayout.CENTER);
		
		// setup listener
		this.lineBtn.addActionListener(this);
		this.circleBtn.addActionListener(this);
		this.numberSlider.addChangeListener(this);
		this.radiusSlider.addChangeListener(this);
	}
	
	public static void main(String[] args)
	{
		String filePath = System.getProperty ("user.home") + "/Desktop/" + "zhigang/hough-test.png";
		HoughUI frame = new HoughUI(filePath);
		// HoughUI frame = new HoughUI("D:\\image-test\\lines.png");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setPreferredSize(new Dimension(800, 600));
		frame.pack();
		frame.setVisible(true);
	}

	@Override
	public void actionPerformed(ActionEvent e) {
		if(e.getActionCommand().equals(CMD_LINE))
		{
			HoughFilter filter = new HoughFilter(HoughFilter.LINE_TYPE);
			resultImage = filter.filter(sourceImage, null);
			this.repaint();
		}
		else if(e.getActionCommand().equals(CMD_CIRCLE))
		{
			HoughFilter filter = new HoughFilter(HoughFilter.CIRCLE_TYPE);
			resultImage = filter.filter(sourceImage, null);
			// resultImage = filter.getHoughSpaceImage(sourceImage, null);
			this.repaint();
		}
		
	}

	@Override
	public void stateChanged(ChangeEvent e) {
		// TODO Auto-generated method stub
		
	}
}

Five: Image preprocessing for detecting circles and straight lines by Hough transform

When using Hough transform to detect circles and straight lines, the image must be preprocessed, grayed, extracted

The edge of the image is suppressed using a non-maximum signal to get a pixel wide edge. This step changes the Hoff transformation

Replacement is very important. Otherwise, it may result in severe distortion in Hough transform detection.

For the first time I blogged on Mac, I apologize for the poor editing!