Image Overlap LT835

发布时间：2020-12-14 04:31:54 所属栏目：大数据来源：网络整理

导读：Two images A and B are given,represented as?binary,square matrices of the same size.? (A binary matrix has only 0s and 1s as values.) We translate one image however we choose (sliding it left,right,up,or down any number of units),and place

Two images A and B are given,represented as?binary,square matrices of the same size.? (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left,right,up,or down any number of units),and place it on top of the other image.? After,the overlap of this translation is the number of positions that have a 1 in both images.

(Note also that a translation does not include any kind of rotation.)

What is the largest possible overlap?

Example 1:

Input: A = [[1,1,0],[0,?           [0,0]]
?      B = [[0,1],1]]
Output: 3
Explanation: We slide A to right by 1 unit and down by 1 unit.

Notes:?

1 <= A.length = A[0].length = B.length = B[0].length <= 30
0 <=?A[i][j],B[i][j] <= 1

Idea 1. Fix image A,there are 4 directions to move image B,moving up (+rowOffset),moving down (-rowOffset),

moving left(+colOffset),moving right(-colOffset)

For example,moving up and left (1,1),? for the first cell,i=0,j = 0,A[i][j] -> B[i+1][j+1],

　　A[0][0]: B[1][1],A[0][1]: B[1][2],A[1][1]: B[2][2],? ? A[2][2] -> B[3][3] out of boundary

Time complexity: O(n^4)

Space complexity: O(1)

 1 class Solution {
 2     public int largestOverlap(int[][] A,int[][] B) {
 3         int result = 0;
 4         int aM = A.length;
 5         int aN = A[0].length;
 6         
 7         int bM = B.length;
 8         int bN = B[0].length;
 9         
10         for(int rOffset = -bM; rOffset < bM; ++rOffset) {
11             for(int cOffset = -bN; cOffset < bN; ++cOffset) {
12                 int curr = 0;
13                 for(int i = 0; i < aM; ++i) {
14                     for(int j = 0; j < aN; ++j) {
15                         if(A[i][j] == 1 &&(i + rOffset >= 0 && i + rOffset < bM
16                                           && j + cOffset >=0 && j + cOffset < bN
17                                           && B[i+rOffset][j+cOffset] == 1)) {
18                             ++curr;
19                         }
20                     }
21                 }
22                 result = Math.max(result,curr);
23             }
24         }
25         
26         return result;
27     }
28 }

Idea 2. Instead of doing 2N horizonal sliding,2N vertical Sliding and counting N^2 overlap areas like idea 1,especially if the matrix is sparse,extracting the positions of all the ones in A and B,doing a pairwise match,if the difference A[i][j] = 1,B[p][q] = 1,moving B[p][q] to A[i][j] needs [p-i,q - j] offset movement,looping all pairs of ones and accumulate the ones with the same offset,how to store the sum by the offset? 2-D array or 1-D array or HashMap?

Note. transfer index from 2D to 1D,normally (i,j) -> (i*N + j),but this does not guarantee?uniqueness,different (i,j) pair could map to the same (i*N + j),(1,-1) and (0,1) to 1 where N = 2,or alternatively,map the range (-N,N) to (0,N),i * 2N + j instead

Time complexity: O(N^4)

Space complexity: O(N^2)

 1 class Solution {
 2     public int largestOverlap(int[][] A,int[][] B) {
 3         int N = A.length;        
 4         
 5         int[][] count = new int[2*N][2*N];
 6         for(int i = 0; i < N; ++i) {
 7             for(int j = 0; j < N; ++j) {
 8                 if(A[i][j] == 1) {
 9                     for(int p = 0; p < N; ++p) {
10                         for(int q = 0; q < N; ++q) {
11                             if(B[p][q] == 1) {
12                                 ++count[i-p + N][j-q + N];
13                             }
14                         }
15                     }
16                 }
17             }
18         }
19         
20         int result = 0;
21         for(int[] row: count) {
22             for(int val: row) {
23                 result = Math.max(result,val);
24             }
25         }
26         return result;
27     }
28 }

Idea 2.b getting all pairs of ones first(N^2),instead of 4 loops (N^4),1D as key

Time complexity: O(N^2 + La * Lb),worst case,dense matrix La* Lb = O(N^4)

Space complexity: O(N^2)

 1 class Solution {
 2     public int largestOverlap(int[][] A,int[][] B) {
 3         int N = A.length;        
 4         
 5         List<int[]> La = new ArrayList<>();
 6         List<int[]> Lb = new ArrayList<>();
 7         
 8         for(int i = 0; i < N; ++i) {
 9             for(int j = 0; j < N; ++j) {
10                 if(A[i][j] == 1) {
11                     La.add(new int[] {i,j});
12                 }
13                 if(B[i][j] == 1) {
14                     Lb.add(new int[] {i,j});
15                 }
16             }
17         }
18         
19         Map<Integer,Integer> count = new HashMap<>();
20         for(int[] a: La) {
21             for(int[] b: Lb) {
22                 int diff = (a[0] - b[0] + N)* 2*N + (a[1] - b[1] + N);
23                 count.put(diff,count.getOrDefault(diff,0) + 1);
24             }
25         }
26        
27         int result = 0;
28         for(int val: count.values()) {
29             result = Math.max(result,val);
30         }
31         
32         return result;
33     }
34 }

String : i0 - i1 + " " + j0 - j1

 1 class Solution {
 2     public int largestOverlap(int[][] A,j});
15                 }
16             }
17         }
18         
19         Map<String,Integer> count = new HashMap<>();
20         for(int[] a: La) {
21             for(int[] b: Lb) {
22                 String key = (a[0] - b[0]) + " " + (a[1] - b[1]);
23                 count.put(key,count.getOrDefault(key,0) + 1);
24             }
25         }
26         
27         int result = 0;
28         for(int val: count.values()) {
29             result = Math.max(result,val);
30         }
31         return result;
32     }
33 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!