Vultr DocsLatest Content

Image Overlap

Updated on 09 June, 2025
Image Overlap header image

Problem Statement

You are provided with two identical-sized binary matrices, img1 and img2, where each matrix is n x n in dimension and comprises only binary values (0 and 1). The task is to determine the maximum possible overlap of 1s when one image is translated over another in any non-rotational direction you choose—meaning translations can be up, down, left, or right. The overlapping regions between the two images that show 1 in the same position for both images contribute to the overlap count. If during the translation a 1 exits the boundary of the matrix, it’s eliminated and doesn’t count towards the overlap. Your objective is to compute this maximum overlap of 1s after performing any number of translations.

Examples

Example 1

Input:

img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]

Output:

3

Explanation:

We translate img1 to right by 1 unit and down by 1 unit.
The number of positions that have a 1 in both images is 3 (shown in red).

Example 2

Input:

img1 = [[1]], img2 = [[1]]

Output:

1

Example 3

Input:

img1 = [[0]], img2 = [[0]]

Output:

0

Constraints

  • n == img1.length == img1[i].length
  • n == img2.length == img2[i].length
  • 1 <= n <= 30
  • img1[i][j] is either 0 or 1.
  • img2[i][j] is either 0 or 1.

Approach and Intuition

The problem revolves around translating one matrix in all possible directions over the other and then counting the overlap of 1s convincingly. Here's an intuitive breakdown of how this can be approached:

  1. Translate the img1 in all possible directions encompassing every potential shift from -n to +n horizontally (left-right) and vertically (up-down). This gives an extensive combination but can be limited to translations that make sense (i.e., do not shift the image completely off the other).
  2. For each valid translation of img1, overlap it with img2 and count the positions where both images have 1. This effectively can be done by aligning the corners or any side of img1 still within bounds of img2 and counting overlaps.
  3. Keep track of the maximum count of overlapping 1s obtained through all possible translations.
  4. The result is the highest number from the above step which indicates the maximum overlap possible.

This approach doesn’t involve complex transformations but straightforward translations and overlap counting, adhering to the constraints provided regarding matrix size and values. The non-inclusivity of rotations in translation simplifies the problem to 2-dimensional space exploration. Thus, efficiently iterating through potential translations and counting overlaps becomes the crux of the solution.

Solutions

  • Java
  • Python
java 
class Solution {

    protected int applyConvolution(int[][] matrix1, int[][] matrix2, int deltaX, int deltaY) {
        int sum = 0;
        for (int i = 0; i < matrix1.length; ++i)
            for (int j = 0; j < matrix1.length; ++j)
                sum += matrix1[i][j] * matrix2[i + deltaY][j + deltaX];
        return sum;
    }

    public int maximumOverlap(int[][] A, int[][] B) {

        int size = A.length;
        int[][] extendedB = new int[3 * size - 2][3 * size - 2];
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j)
                extendedB[i + size - 1][j + size - 1] = B[i][j];

        int maxOverlap = 0;
        for (int xShift = 0; xShift < 2 * size - 1; ++xShift)
            for (int yShift = 0; yShift < 2 * size - 1; ++yShift) {
                maxOverlap = Math.max(maxOverlap,
                    applyConvolution(A, extendedB, xShift, yShift));
            }

        return maxOverlap;
    }
}

The provided Java program calculates the maximum overlap between two square binary matrices A and B. It employs a method akin to a two-dimensional convolution to determine how one matrix can be overlaid onto another to maximize overlapping ones (overlaid elements both being 1). Here's how the program operates:

  • Initialization of Extended Matrix (extendedB): The program first initializes an extended matrix extendedB which is of size (3 * size - 2) x (3 * size - 2). It places the matrix B in the middle of this extended matrix, creating padding of zeros around it, thus allowing A to be shifted over various parts of B without array bounds issues.

  • Convolution Application: The applyConvolution method is defined to calculate the overlap between the matrix A and a translated portion of matrix B. For each valid position (deltaY, deltaX) within extendedB, this method computes the sum of products between aligned elements of A and those of B at the shifted position.

  • Maximal Overlap Calculation: In the maximumOverlap method, nested loops iterate over all possible x and y shifts where A can be fully laid over areas of extendedB that originally corresponds to B. The shift ranges from 0 to 2 * size - 1. With each shift configuration, applyConvolution is called to compute the overlap, and the maximum value is updated accordingly.

By the end of execution, maximumOverlap returns the highest value of overlap found, showcasing the maximum extent to which the matrix A can be overlaid onto matrix B with the greatest number of coinciding ones. This solution efficiently handles the matrix translation and computation of overlap, utilizing an extended matrix to avoid the need for boundary checking during the convolution application.

python 
class Solution:
    def maximumOverlap(self, img1: List[List[int]], img2: List[List[int]]) -> int:

        import numpy as np
        img1 = np.array(img1)
        img2 = np.array(img2)

        size = len(img1)
        # Padding img2 for convolution operation
        img2_padded = np.pad(img2, size - 1, mode='constant', constant_values=0)

        largest_overlap_count = 0
        for shift_x in range(size * 2 - 1):
            for shift_y in range(size * 2 - 1):
                # Extract section from the padded img2
                section = img2_padded[shift_x:shift_x + size, shift_y:shift_y + size]
                # Perform element-wise multiplication and count non-zero entries
                overlap = np.sum(img1 * section)
                largest_overlap_count = max(largest_overlap_count, overlap)

        return largest_overlap_count

The Python solution provided addresses the problem of finding the maximum overlap between two binary images, represented as 2D lists. Utilizing the power of NumPy, a popular library for numerical computing in Python, the solution involves several key operations:

  • Convert both image lists (img1 and img2) into NumPy arrays for efficient manipulation.
  • Pad the second image (img2) with zeros on all sides. The padding size equals the length of the image minus one, ensuring that it can completely overlap with img1 in any direction.
  • Initialize a variable to keep track of the highest number of overlapping 1s (largest_overlap_count).
  • Use two nested loops to shift the extracted section of the padded img2 across all possible positions over img1.
  • For each possible position (determined by shift_x and shift_y), extract a section of img2_padded that aligns with the dimensions of img1. Perform an element-wise multiplication between this section and img1.
  • Sum the resultant array to count overlapping 1s and update largest_overlap_count if this sum is higher than previously recorded values.

The final result, largest_overlap_count, provides the maximum overlap count, crucial for applications like image registration or motion estimation where alignment of features is key. This approach leverages NumPy's array operations for efficient computation, making it suitable for large images or real-time applications.

Comments

No comments yet.