I have two images, where part of one image is present in another, however the position is not necessarily equal.

These two example images are significantly less complex than the typical drawing, so no keypoint feature matching methods will work. The objective is to find the coordinates of the top left corner of the second image that optimally joins to the two images together.

My approach is simply brute force, with a count of the black pixels to determine when the most amount of overlap has been achieved. This method works most the time, however for large images is obviously extremely slow.

Im hoping to accelerate this either with GPU acceleration or just optimisation of the method. Numba @jit decorators arent compatible with mask based numpy indexing so that wont work - the only obvious thing I can think of is cython. Cupy has also not produced good results.

Separate to reducing the number of loops (reducing search space or increasing step) are there any obvious accelerations that can be made?

 def get_overlap_box(box1, box2):
    # Unpack the coordinates of the two boxes
    x1, y1, w1, h1 = box1
    x2, y2, w2, h2 = box2

    # Calculate the horizontal overlap
    x_overlap = max(0, min(x1   w1, x2   w2) - max(x1, x2))

    # Calculate the vertical overlap
    y_overlap = max(0, min(y1   h1, y2   h2) - max(y1, y2))

    # Calculate the top-left corner of the overlap box
    x_overlap_start = max(x1, x2)
    y_overlap_start = max(y1, y2)
    return [x_overlap_start, y_overlap_start, x_overlap, y_overlap]

def find_join_point(img1, img2, step=2):
    im1h, im1w = img1.shape
    im2h, im2w = img2.shape
    canvas1 = img1.copy()
    canvas2 = img2.copy()
    count = []
    black_pixel_count_dict_reverse = {}
    for x in tqdm.tqdm(range(- im2w, im1w, step)):
        for y in range(- im2h, im1h, step):
            # get the coordinates of the two images relative to the top left corner of the first image
            box2 = [x, y, im2w, im2h]
            box1 = [0, 0, im1w , im1h]
            # Get coordinates of the overlapping box relative to the first image
            box3 = get_overlap_box(box1, box2)
            # extract the overlapping region from both canvases for comaparison
            sampleregion1 = canvas1[box3[1]:box3[3]   box3[1], box3[0]:box3[2]   box3[0]]
            replacement = sampleregion1.copy()
            sampleregion2 = canvas2[box3[1] - y:box3[3]   box3[1] - y, box3[0] - x:box3[2]   box3[0] - x]
            #Dont continue for completely white sample regions
            if np.all(sampleregion1 == 255) or np.all(sampleregion2 == 255):
                continue
            # merge the two overlapping regions
            sampleregion1[sampleregion2 == 0] = 0
            # replace the orignal with the new sample region
            canvas1[box3[1]:box3[3]   box3[1], box3[0]:box3[2]   box3[0]] = sampleregion1
            # count the black pixels across both images
            black_pixel_count = np.count_nonzero(canvas1 == 0) - np.count_nonzero(sampleregion2 == 0)
            black_pixel_count_dict_reverse[black_pixel_count] = [x, y]
            # reset the first canvas
            canvas1[box3[1]:box3[3]   box3[1], box3[0]:box3[2]   box3[0]] = replacement
            # keep the count for analysis later
            count.extend([black_pixel_count])
    # find the x,y position with the minimum black pixel count
    optimum = black_pixel_count_dict_reverse[min(count)]
    print(optimum)
    return optimum

Thanks in advance.

CodePudding user response：

If there is only translation between the two images and no rotation, what you need is to find the maximum of the cross correlation between the two images.

This is handled nicely by skimage.registration.phase_cross_correlation, and my solution below is taken from scikit-image's image registration example.

import skimage.registration

shift, _, _ = skimage.registration.phase_cross_correlation(img1, img2)

You can also use the upsample_factor keyword argument of phase_cross_correlation if you want subpixel precision of the shift between your two images.