CODEWITHSUNDEEP
opencvcomputer-visionpattern-matchingsignal-processing
DalekSupreme
DalekSupreme

Reputation: 1513

Fill irreguar grid points

So I have a set of an incomplete set of 2d points following a certain pattern.

enter image description here

You can see in the example image that some points are missing. I tried to fit a grid but I find that although the points seem to be arranged in a straight line there can be a slight deviation. I tried to find an algorithm that fills the rest of the image with dots but I did not find any. I tried to estimate the horizontal and vertical frequency of the dots using FFT but the frequency also tends to vary a bit.

Is there any obvious algorithm I am missing here that can solve this problem?

Upvotes: 1

Views: 210

Answers (1)

TLousky
TLousky

Reputation: 303

You can treat this like a 2D point cloud problem, and use tessellation as one way to fill the gaps. The tricky bit that still requires a good solution is to decide what is a hole and what isn't. Here I've implemented a naive triangle area based method to decide. You can fine-tune the area threshold value to improve it or figure out another way.

enter image description here

import cv2
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Polygon
from scipy.spatial import Delaunay

gray     = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
thresh   = cv2.threshold( gray, 50, 255, cv2.THRESH_BINARY )[1]
contours = cv2.findContours( thresh, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE )

def get_center( rect ):
    x,y,w,h = rect
    return np.array([x+w/2, y+h/2])

points, points_orig = [np.array([ get_center(cv2.boundingRect(c)) for c in contours[1] ])]*2
points[:,1] = im.shape[0] - points[:,1] # Flip Y to plot correctly without image

# Use Delaunay triangulation to calculate triangles from points
tri   = Delaunay(points)
tris  = np.array([ points[i] for i in tri.simplices ]) # Get arrays of coordinates
areas = np.array([ cv2.contourArea(np.array([t]).astype('int')) for t in tris ])

thresh = np.mean( areas ) # Set area threshold to mean triangle area

f, axs = plt.subplots(2, 2, figsize=(20,20))

for ax, t in zip(axs.flat, ['Original Points', 'Tesselated', 'Holes', 'Mesh without holes']):
    ax.scatter( points[:,0], points[:,1], color='red', zorder=2 )
    ax.set_facecolor('black')
    ax.set_title( t, color='white')
    ax.axis('off')
    
for ax in axs.flat[1:]:
    ax.triplot(points[:,0], points[:,1], tri.simplices, zorder=1, color='gray')

masks = [ areas > thresh, areas <= thresh ]
for ax, mask, color in zip(axs[1], masks, ['cornflowerblue', 'indianred']):
    plottris = tris[ mask ]
    for t in plottris:
        p = Polygon(t, facecolor=color, edgecolor=None, zorder=0)
        ax.add_patch(p)

f.set_facecolor('black')
plt.show()

Upvotes: 2

Related Questions