# Fit best polygon to a discrete contour

I have a discrete contour represented by a set of points. The contour looks like a polygon but if you zoom you see that the edges are rugged (that's because it was obtained while working on a finite differences grid)

I would like to fit a polygon to this contour (which is closest in the least-squares sense). Are there any simple known algorithms to do this?

• Maybe try finding the convex hull of the points used to generate the above image and then merge resulting line segments based on them having similar directions to their neighbor line segments. Based on a proper threshold used for merging line segments, you should be able to end up with the proper polygon. This should generalize to any convex polygon fairly easily in theory. – spektr Oct 5 '16 at 17:32

The Hough Transform is an image processing algorithm for extracting features for an image. The classical version of the algorithm is designed to extract lines from a binary image (such as this).

Given the ability to do this, you can make a script fairly easily. Here's one using the hough transform (and associated utilities) in Matlab. It probably requires the image processing toolbox, but hopefully you can track that down.

The only shortcut present in this code is that I told the "houghpeaks" function to search for 4 lines. You can be smarter than this by doing other peak detection methods in the Hough space (read the wiki if you're not familiar with the output of the Hough transform, https://en.wikipedia.org/wiki/Hough_transform).

One caveat is that the Hough transform will only give you whole lines. You'll have to post-process them to get line segments. This example works particularly well without any of that since the input was a convex polygon whose vertices were at/near the edge of the image.

clear all
close all
clc

% Load image (I suspect your input may be different, but the same ideas hold)

% Make a black/white image using the "blue" as the new white values
bw = img(:,:,1) ~= 255;

% Use hough transform to find lines
[H,theta,rho] = hough(bw);
P = houghpeaks(H,4);
lines = houghlines(bw,theta,rho,P);

% Visualization
imagesc(bw); colormap gray;
hold on;
for l = 1:length(lines)
plot([lines(l).point1(1) lines(l).point2(1)], ...
[lines(l).point1(2) lines(l).point2(2)],'r');
end

• This is an interesting approach. Thank you. It does what I have in mind, but it seems to depend upon the resolution of the image and the thickness of the contour. – Beni Bogosel Oct 7 '16 at 9:19
• Yeah, like many image processing methods, it takes a little bit of care to ensure that you're giving it a good input. The hough transform generally requires some preprocessing (generally edge-finding) to get reliable results. If you can guarantee that your polygon is convex, the convex-hull approach in a comment above could be more reliable. The image you provided happened to be a perfect input for matlab's default hough transform settings, so the script above worked well. – Tyler Olsen Oct 7 '16 at 15:23
• Yes, I've managed to run the script and see the results. I may use it in a first stage as it works straight away for polygonal contours. Thank you for providing a code example which made it easier to test. :) – Beni Bogosel Oct 7 '16 at 16:45

There is a approach that uses notions from Discrete Geometry: Discrete Geometry is a discipline that works with objects defined as sets of pixels that try to mimic their standard counterparts. It defines discrete segments, discrete circles, discrete planes etc... In your case, there is an algorithm [1] that has a definition of what a discrete segment is, and that reconstructs in the input image the set of maximal segments, i.e. segments that cannot be further extended by adding new pixels to them. See also the extensions to fuzzy data [2,3]. The approach was successfully applied to 3D reconstruction from multiview images [4]

[1] I. DEBLED-RENNESSON, J.-P. REVEILLES, A linear algorithm for segmentation of digital curves, International Journal of Pattern Recognition and Artificial Intelligence, Volume 9, N. 6, December 1995.

[2] I. DEBLED-RENNESSON, J.-L. REMY and J. ROUYER-DEGLI, Linear segmentation of discrete curves into fuzzy segments, Discrete Applied Mathematics, 151:122-137, October 2005.

[3] I. DEBLED-RENNESSON, F. FESCHET and J. ROUYER-DEGLI, Optimal blurred segments decomposition of noisy shapes in linear time, Computers & Graphics, 30(1), 2006.

• Thank you for all these references. I'll look them up. Maybe these approaches also apply to piecewise smooth discrete contours (not only polygons) and that also interests me. – Beni Bogosel Oct 7 '16 at 9:23
• Yes, to my knowledge there are some volumetric versions (discrete planes / discrete polygons), see Isabelle Debled's publication list: dblp.uni-trier.de/pers/hd/d/Debled=Rennesson:Isabelle – BrunoLevy Oct 7 '16 at 12:23

I am quite surprised why no-one mentioned the famous Douglas Peucker Algorithm for polyline simplification. Since you have contour points in hand, you could benefit from it directly. Contour approximation in OpenCV uses this method. See this for usage. and you could also find a MATLAB implementation here or here.