import numpy as np
array = np.array([[np.nan, 255, 255, 0, 0, 0, 0, 0, 255, np.nan],
[np.nan, 255, 255, 255, 0, 0, 0, 0, 255, np.nan],
[np.nan, 255, 255, 255, 255, 0, 0, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 0, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 0, 0, 0, 255, 255, np.nan],
[np.nan, 255, 255, 0, 0, 0, 0, 0, 255, np.nan],
[np.nan, 255, 255, 255, 0, 0, 0, 0, 255, np.nan],
[np.nan, 255, 255, 255, 255, 0, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 0, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan],
[np.nan, 255, 255, 255, 255, 255, 255, 255, 255, np.nan]])
预期输出是
[[255, 255, 255, 255, 255, 255, 255, 255],
[255, 255, 255, 255, 0, 255, 255, 255, ],
[255, 255, 255, 0, 0, 0, 255, 255],
[255, 255, 0, 0, 0, 0, 0, 255],
[255, 255, 255, 0, 0, 0, 0, 255],
[255, 255, 255, 255, 0, 255, 255, 255],
[255, 255, 255, 255, 255, 255, 255, 255],
[255, 255, 255, 255, 255, 255, 255, 255],
[255, 255, 255, 255, 255, 255, 255, 255],
[255, 255, 255, 255, 0, 255, 255, 255],
[255, 255, 255, 255, 255, 255, 255, 255]]
m, n = array.shape
# Initialize the maximum submatrix size and its starting indices
max_submatrix_size = 0
max_submatrix_start_i = 0
max_submatrix_start_j = 0
# Iterate over all possible starting indices of the window
for i in range(m):
for j in range(n):
# Initialize the window size
window_size = 0
# Expand the window until it reaches the end of the array or encounters a non-255 value
while i + window_size < m and j + window_size < n and array[i + window_size, j + window_size] == 255:
window_size += 1
# Update the maximum submatrix size and its starting indices
if window_size > max_submatrix_size:
max_submatrix_size = window_size
max_submatrix_start_i = i
max_submatrix_start_j = j
# Shrink the window size and check again
for k in range(1, window_size + 1):
if i + k >= m or j + k >= n or array[i + k, j + k] != 255:
break
# Update the maximum submatrix size and its starting indices
if k + 1 > max_submatrix_size:
max_submatrix_size = k + 1
max_submatrix_start_i = i
max_submatrix_start_j = j
window_size = k
break
# Extract the largest submatrix
largest_submatrix = array[max_submatrix_start_i:max_submatrix_start_i + max_submatrix_size,
max_submatrix_start_j:max_submatrix_start_j + max_submatrix_size]
print(largest_submatrix)
我得到的输出是
[[255. 255. 255. 0. 0. 0. 255. 255.]
[255. 255. 0. 0. 0. 0. 0. 255.]
[255. 255. 255. 0. 0. 0. 0. 255.]
[255. 255. 255. 255. 0. 255. 255. 255.]
[255. 255. 255. 255. 255. 255. 255. 255.]
[255. 255. 255. 255. 255. 255. 255. 255.]
[255. 255. 255. 255. 255. 255. 255. 255.]
[255. 255. 255. 255. 0. 255. 255. 255.]]
我尝试过使用滑动窗口，但没有从中得到太多帮助（如果有人可以解决它）。如果有的话，还要考虑最大子矩阵内部可以有 nan 值的情况。如果可能的话也可以建议不同的方法。
这是一个递归函数。如果矩阵非常稀疏并且超过递归深度，您可以将其更改为使用
whiledef largest_submatrix(arr):
"""
Obtain the largest submatrix
"""
def find_index(arr, idx):
"""
Obtain the row and col slices containing non-na values
"""
n,m = arr.shape
if len(idx) == 2:
row1, row2 = (idx[0], idx[0] + 1) if idx[0] < n else (idx[0] - 1, idx[0])
col1, col2 = (idx[1], idx[1] + 1) if idx[1] < m else (idx[1] - 1, idx[1])
idx = row1, row2, col1,col2,0
else: row1, row2, col1, col2,_ = idx
# move up
if arr[row1-1:row2, col1:col2].all():
row1 = row1 - 1 if row1> 0 else 0
# move down
if arr[row1:row2+1, col1:col2].all():
row2 = row2 + 1 if row2 < n else n
# move left
if arr[row1:row2, col1-1:col2].all():
col1 = col1 - 1 if col1> 0 else 0
# move right
if arr[row1:row2, col1:col2+1].all():
col2 = col2 + 1 if col2 < m else m
# any movement? if yes, repeat the process above.
if (np.r_[row1, row2, col1, col2] != idx[:-1]).any():
return find_index(arr, (row1, row2, col1, col2, 0))
return row1, row2, col1, col2, (row1 - row2) * (col1 - col2)
def sub_indices(arr_bool, index, vals = None):
"""
Compare the slices and obtain the slices with the most values
"""
row, col = index
r1, r2, c1, c2, size = indices = find_index(arr_bool,(row[0], col[0]))
# slices with max region
vals = indices if vals is None or size > vals[-1] else vals
# any non-nan value not within the have not been traversed? Repeat
if (i2 := ~((r1 <= row) & (row <= r2) & (c1 <= col) & (col <= c2))).any():
return sub_indices(arr_bool, (row[i2], col[i2]), vals)
return vals
arr_bool = ~np.isnan(arr)
r1,r2, c1, c2,_= sub_indices(arr_bool, np.where(arr_bool))
return arr[r1:r2, c1:c2]
largest_submatrix(array)
array([[255., 255., 255., 255., 255., 255., 255., 255.],
[255., 255., 255., 255., 0., 255., 255., 255.],
[255., 255., 255., 0., 0., 0., 255., 255.],
[255., 255., 0., 0., 0., 0., 0., 255.],
[255., 255., 255., 0., 0., 0., 0., 255.],
[255., 255., 255., 255., 0., 255., 255., 255.],
[255., 255., 255., 255., 255., 255., 255., 255.],
[255., 255., 255., 255., 255., 255., 255., 255.],
[255., 255., 255., 255., 255., 255., 255., 255.],
[255., 255., 255., 255., 0., 255., 255., 255.],
[255., 255., 255., 255., 255., 255., 255., 255.]])
目前还不清楚
even