Efficient Equidistant Point Sampling on Closed Contours in OpenCV

Question

For a project, I extracted closed contours from silhouette images (MPEG-7 Core Experiment CE-Shape-1 Test Set) using OpenCV’s findContours with RETR_EXTERNAL and CHAIN_APPROX_NONE. I need an efficient way to sample n equidistant points (Euclidean distance) on these contours for further processing, including curvature computation.

Initially, I calculated distances manually between contour points, but it was slow and inaccurate for complex shapes. I then explored algorithms like uniform arc length sampling, hoping for OpenCV implementations or integration guidance, but found limited resources:

import numpy as np
import cv2 as cv
    
def reduceContour(original_contour, length_original_contour, precomputed_distances, starting_index, pointwise_distance):
    reduced_contour = []
    i = starting_index
    while True:
        reduced_contour.append(original_contour[i])
        j = i
        while True:
            i = (i + 1) % length_original_contour
            if i == starting_index:
                return np.array(reduced_contour)
            elif precomputed_distances[min(i, j)][max(i, j) - min(i, j) - 1] > pointwise_distance:
                i = (i - 1) % length_original_contour
                break

color_image = cv.imread('ray.png', cv.IMREAD_COLOR)
grayscale_image = cv.cvtColor(color_image, cv.COLOR_BGR2GRAY)
_, binary_image = cv.threshold(grayscale_image, 127, 255, 0)
contours, _ = cv.findContours(binary_image, cv.RETR_EXTERNAL, cv.CHAIN_APPROX_NONE)
original_contour = contours[0]
length_original_contour = len(original_contour)
print('Length of the original contour:', length_original_contour)
precomputed_distances = [[np.linalg.norm(original_contour[i] - original_contour[j]) for j in range(i + 1, length_original_contour)] for i in range(length_original_contour)]
starting_index = int(input('Starting index: '))
length_reduced_contour = int(input('Length of the reduced contour: '))
pointwise_distance = cv.arcLength(original_contour, True) / length_reduced_contour
reduced_contour = reduceContour(original_contour, length_original_contour, precomputed_distances, starting_index, pointwise_distance)
print('Actual length of the reduced contour:', len(reduced_contour))
cv.drawContours(color_image, [original_contour], 0, (0, 255, 0), 2)
cv.drawContours(color_image, [reduced_contour], 0, (0, 0, 255), 2)
cv.imwrite('ray_result.png', color_image)
cv.imshow('Result', color_image)
cv.waitKey(0)
cv.destroyAllWindows()

Here are the results:

• Length of the original contour: 478
• Starting index: 0
• Length of the reduced contour: 30
• Actual length of the reduced contour: 26

A binary image from MPEG-7 Core Experiment CE-Shape-1 Test Set Obtained results

I’m seeking guidance on efficient sampling methods, whether through recommended OpenCV functions or established algorithms. Concrete code examples or implementation insights would be invaluable, along with any expertise or best practices from the OpenCV community. I’m open to alternative approaches and ultimately aim for accurate and efficient sampling for my computations.

Answer 1

You can generate points that are uniformally sampled between a range of values using np.linspace. Use these indices to then get uniformally samples points from the raw contour that you get by passing CHAIN_APPROX_NONE.

Again, it's very hard answering your question without an example image and the other requirements of stackoverflow. So please read the how to ask.

Here is a code that I used on an example of a red circle, that I approximate with different number of points:

im = cv2.imread("RedContour.png") # read image
imRGB = cv2.cvtColor(im, cv2.COLOR_BGR2RGB) # convert to RGB for easy plotting with matplotlib
imGray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY) # convert to gray for threhshold
_, thresh = cv2.threshold(imGray, 127, 255, cv2.THRESH_BINARY_INV) # inverse thresh to get red blob
contour, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE) # get contour with not approximation
X,Y = np.array(contour[0]).T # unpack contour to X and Y coordinates
X = X[0] # ==//==
Y = Y[0] # ==//==
fig = plt.figure() # for plotting
for numPoints in range(3, 22): # loop different approximations #
    fig.clf() # for plotting
    resampleIndices = np.linspace(0, len(Y) - 1, numPoints, dtype=int) # generate uniformally distant indices
    resampledX = X[resampleIndices] #  ==//==
    resampledY = Y[resampleIndices] #  ==//==
    modifiedContour = np.dstack((resampledX, resampledY)) # re-do contour
    imModifiedContour = cv2.drawContours(imRGB.copy(), contour, -1, (0,0,255), 5) # draw raw contour in blue 
    imModifiedContour = cv2.drawContours(imModifiedContour, modifiedContour, -1, (0,0,0), 5) # draw modified contour
    plt.imshow(imModifiedContour) # for plotting
    plt.axis("off") # ==//==
    plt.title("Approximated with "+str(numPoints-1)+" points") # ==//==
    fig.canvas.draw() # ==//==

I did an animation as a result:

Some notes, if you use numPoints = 2, you will get the first and last points of the contour, which are very close to each other, so technically numPoints = 3 is the one that will generate the line.

V2.0: since you added the fish image, here are the results using the same approach with 30 points:

There are some minor changes to the range of the incides, it should be till the length - number of points, to accound for the fact that the contour is closed, here is the code:

im = cv2.imread("ray.png") # read image
imRGB = cv2.cvtColor(im, cv2.COLOR_BGR2RGB) # convert to RGB for easy plotting with matplotlib
imGray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY) # convert to gray for threhshold
_, thresh = cv2.threshold(imGray, 127, 255, cv2.THRESH_BINARY) # inverse thresh to get red blob
contour, _ = cv2.findContours(thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE) # get contour with not approximation
X,Y = np.array(contour[0]).T # unpack contour to X and Y coordinates
X = X[0] # ==//==
Y = Y[0] # ==//==
numPoints = 30 # specify the number of points that you want
resampleIndices = np.linspace(0, len(Y) - len(Y)//numPoints, numPoints, dtype=int) # generate uniformally distant indices until len(X) - len(X)//numPoints to accound for the end of the contour
resampledX = X[resampleIndices] #  ==//==
resampledY = Y[resampleIndices] #  ==//==
modifiedContour = np.dstack((resampledX, resampledY)) # re-do contour
imModifiedContour = cv2.drawContours(imRGB.copy(), contour, -1, (0,0,255), 1) # draw raw contour in blue 
imModifiedContour = cv2.drawContours(imModifiedContour, modifiedContour, -1, (255,0,0), 1) # draw modified contour
plt.figure()
plt.imshow(imModifiedContour) # for plotting
plt.scatter(resampledX, resampledY, color = "g")
plt.axis("off") # ==//==
plt.title("Approximated with "+str(numPoints)+" points") # ==//==

Now given the fact that the contour is closed, this approach should work, since you are uniformally sampling accross a range that is within the bound of a closed contour. However, I feel that in this case the arc length is what will stay almost the same and not the euclidean distance. I am working now on the euclidean, to see if I can help you further...