In this project I have demonstrated how to implement the RANSAC algorithm for Lines and then extended the principles and done an implementation for Circles

https://medium.com/@saurabh.dasgupta1/outlier-detection-using-the-ransac-algorithm-de52670adb4a

I have used the following tools to author the Python scripts that accompany this article.

1. Visual Studio 2019
2. with Python project templates
3. Python 3.7 engine

• Run the script GenerateNoisyLine.py to generate a rectangular image with 1 line in a random orientation and salt-pepper noise
• The resulting image will be generated in the subfolder .\out

• Run the script RANSAC.py to find the best fitting line in a noisy image
• The input file is controlled by a variable inside RANSAC.py and the this file should be placed in the subdirectory .\input
• The output is generated in the form of a new image which has the RANSAC line superimposed over the original line

The folder hierarchy is as follows:

• RansacLineHelper.py - RANSAC algorithm implementation for Line
• RansacCircleHelper.py - RANSAC algorithm implementation for of Circle

• LineModel.py - Implements a class that represents the equation of a straight line in ax+by+c=0
• CircleModel.py - Implements a class that represents the a Circle given the center and a radius
• Point.py - Implements a class which represents a 2d point
• RansacHelper.py - Implements the core RANSAC algorithm
• Util.py - Utility functions

• ExecRANSACLine.py - Outermost Python script which can be executed from the command line
• ExecRANSACCircle.py - Outermost Python script which can be executed from the command line
• GenerateNoisyLine.py - Outermost Python script which will generate a random straight line with salt-pepper noise
• GenerateNoisyCircle.py - Outermost Python script which will generate a random arc of a circle with salt-pepper noise
• GenerateNoisyLineGaussian.py - Outermost Python script which will generate a random line with Gaussian noise around the line on a background with salt-pepper noise
• .\input\ - The folder containing input files
• .\output\ - The folder where the resulting images are published

• test_??.py - These are unit test classes for all the algorithms

If you are using Visual Studio 2019 as your Python IDE then you can configure the project properties of RANSAC and specify the Search path property For other environments, the PYTHONPATH environment variable should be set to the physical location of Common folder

Notice the outliers on the bottom right of the image

The algorithm is agnostic of outliers and hence the circle is skewed towards the right

Notice how the algorithm has eliminated the outliers and found a nice fitting circle

RANSAC for straight lines relies on least squares algorithm to find the line which fits a set of points. When I started implementing RANSAC for circles, I was unsure of what would be the best mathematical approach to fit a circle to a set of points. Unlike the least squares method for lines, the equivalent approach for circles is non-linear and hard to solve without an interative approach I used the Gradient Descent Approach and this worked well. However, GD is an iterative approach and fairly expense. In the later stages I learnt of Randy Bullock's approach which reduces the non-learn optimization problem to a liner problem

The function run in the Python class RansacCircleHelper.py prepares a short list of circles which meet the initial threshold criteria. At this stage, each of the candidate circles are formed by sampling 3 points in random. This step can be multi-threaded.

• Implementing Randy Bullock's circle fitting algorithm. This has significantly improved performance (nearly an order of magnitude)
• Fixing sampling fraction bug. This was hard coded to 0.25. Selecting a low value such as 0.01 for a dense 200X200 image can significantly improve performance (Example 3)

• Wikipedia article on RANSAC (https://en.wikipedia.org/wiki/Random_sample_consensus)
• Youtube lecture (https://www.youtube.com/watch?v=BpOKB3OzQBQ)
• Deriving the least squares regression (https://online.stat.psu.edu/stat414/node/278/)
• Weighted least squares (https://towardsdatascience.com/when-and-how-to-use-weighted-least-squares-wls-models-a68808b1a89d)
• Hough transform (https://en.wikipedia.org/wiki/Hough_transform)
• Finding the maxima and minima (https://clas.sa.ucsb.edu/staff/lee/Max%20and%20Min's.htm)
• Overview of various circle fitting algorithm (https://arxiv.org/pdf/cs/0301001.pdf)
• Least squares circle fitting algorithm by Randy Bullock (https://www.dtcenter.org/sites/default/files/community-code/met/docs/write-ups/circle_fit.pdf)