假设我有一个二进制 40*40
矩阵。
在这个矩阵中,值可以是 1 或 0。
我需要解析整个矩阵,对于任何值 == 1,应用以下内容:
如果满足以下条件,则保留值 = 1,否则将值修改回 0:
条件:在N*N
的正方形中(以当前评估值为中心),我至少可以算出M个值== 1。
N和M是算法可以设置的参数,自然是N<20
(在这种情况下)和 M<(N*N - 1)
.
显而易见的算法是遍历整个图像,然后每次都有一个值 == 1。围绕该值执行另一次搜索。它会使 O^3 复杂的算法。有什么想法可以提高效率吗?
编辑:一些代码使这更容易理解。
让我们创建一个由 1 和 0 组成的随机初始化的 40*40 矩阵。 5%(任意选择)的值是 1,95% 是 0。
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
def display_array(image):
image_display_ready = image * 255
print(image_display_ready)
plt.imshow(image_display_ready, cmap='gray')
plt.show()
image = np.zeros([40,40])
for _ in range(80): # 5% of the pixels are == 1
i, j = np.random.randint(40, size=2)
image[i, j] = 1
# Image displayed on left below before preprocessing
display_array(image)
def cleaning_algorithm_v1(src_image, FAT, LR, FLAG, verbose=False):
"""
FAT = 4 # False Alarm Threshold (number of surrounding 1s pixel values)
LR = 8 # Lookup Range +/- i/j value
FLAG = 2 # 1s pixels kept as 1s after processing are flag with this value.
"""
rslt_img = np.copy(src_image)
for i in range(rslt_img.shape[0]):
for j in range(rslt_img.shape[1]):
if rslt_img[i, j] >= 1:
surrounding_abnormal_pixels = list()
lower_i = max(i - LR, 0)
upper_i = min(i + LR + 1, rslt_img.shape[0])
lower_j = max(j - LR, 0)
upper_j = min(j + LR + 1, rslt_img.shape[1])
abnormal_pixel_count = 0
for i_k in range(lower_i, upper_i):
for j_k in range(lower_j, upper_j):
if i_k == i and j_k == j:
continue
pixel_value = rslt_img[i_k, j_k]
if pixel_value >= 1:
abnormal_pixel_count += 1
if abnormal_pixel_count >= FAT:
rslt_img[i, j] = FLAG
rslt_img[rslt_img != FLAG] = 0
rslt_img[rslt_img == FLAG] = 1
return rslt_img
# Image displayed on right below after preprocessing
display_array(cleaning_algorithm_v1(image, FAT=10, LR=6, FLAG=2))
给出以下内容:
最佳答案
使用卷积怎么样?
您的内核将是一个由 1 组成的 NxN 窗口。在这种情况下,内核是可分离的,因此您可以将卷积处理为 2 个一维卷积。你可以这样做:
import numpy as np
from scipy.ndimage.filters import convolve1d
from time import time
mat = np.random.random_integers(0, 1, (40, 40))
N = 5
M = 15
window = np.ones((N, ), dtype=np.int)
start = time()
interm = convolve1d(mat, window, axis=0)
result = convolve1d(interm, window, axis=1)
[rows, cols] = np.where(result >= M)
result[:, :] = 0
result[(rows, cols)] = 1
end = time()
print "{} seconds".format(end - start)
0.00155591964722 seconds
不确定复杂性如何比较,但卷积在各种 python 深度学习库中得到了很好的优化。
关于python - 有优化这个算法的想法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51392673/