优化算法

程序结构合理性与时间复杂度

机械地将denoise12和denoise7合并在一起,虽然达到了效果,但是程序结构上显然不合理,时间复杂度也大大加重。

程序结构

因为两种降噪算法在大部分的操作上是相似的,甚至是相同的,那么很简单地想到将其有机复合,简而言之就是精简相同或类似的步骤,并将关键处理步骤穿插在一起。

这样的方法很容易想到,但是修改起来费时费力,容易出bug。因为一开始编写程序时,由于没有全面学透python的原因,没有使用面向对象的思想,而是简单使用了面向过程的写法,尽管使用了结构体的思想,但程序看起来还是不够有条理,而且后期难以管理。

所以我尝试使用C++给出更好的解决方案(CPicture.h):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#pragma once
#include <opencv2/opencv.hpp>
#include <string>
#include <vector>
#include <numeric>
#include <iostream>

using namespace std;
using namespace cv;

class CPicture {
public:
string address; //图像地址
Mat img; //图像Mat
vector<Mat> channels; //BGR通道
vector<vector<vector<int>>> noises; //BGR噪声
public:
//无参构造
CPicture();
//含参构造
CPicture(string& str, int k);
//去噪函数
Mat denoise();
private:
int m_k = 1; //多尺度指数
int m_threshold = 1; //阈值
private:
//噪声检测
vector<vector<int>> noise_check(Mat& channel);
//不考虑位置d7
vector<int> division71(vector<vector<int>>& ary);
//考虑位置d7
vector<int> division72(vector<vector<int>>& ary);
//处理特殊值
vector<int> special_check(vector<vector<int>>& ary);
//一维到二维
vector<int> oned2twod(int x);
//缩小图像
vector<vector<Mat>> shrink(Mat& channel);
//搜索最佳可赋值
int find_best(Mat& channel, vector<vector<int>>& noise, int x, int y);
};

发现算法本身存在的问题

“找不出来,再找一遍”的方法本身就已经是下策了,如果能从根本上解决问题,自然是最好。

下面是考虑位置的划分方法的判断区分度部分的代码片段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# python3.8
# 判断区分度
max1 = 0
for i in range(8):
if result[i] == 1 and p[i] > max1:
max1 = p[i]
min2 = 255
for i in range(8):
if result[i] == 2 and p[i] < min2:
min2 = p[i]
if int(max1 - min2) < 10:
return result, False
else:
return result, True

这已经是修改过的代码,原本的min2的初始值会使算法不合理。

但是由于CvMat中的值的数据类型较为特殊(为uchar),会使得max1-min2溢出数据范围,导致判断区分度部分异常,从而噪声检测无法进行。

那么,索性进行不判断区分度的尝试。因为单纯从该部分来看,这只会导致本不是噪声点却被修改的可能性上升,但是修改值却不可能会是噪声,所以猜测影响应该不大。

再进一步思考,其实考虑位置的区分度算法虽然与不考虑位置的区分度算法有所差异,但是效果应该是近似的,所以,对于同一块区域来说,不考虑位置的区分度结果完全可以共享给关于该块区域的所有算法。

另外,还调整了一些不合理的参数、阈值。

实现效果

image-20210725225144442

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
# python3.8
# utf-8
import cv2 as cv
import numpy as np

threshold = 4


class PixelChannel:
def __init__(self, channel, noise, row, col):
self.noise = noise
self.channel = channel
self.row = row
self.col = col


class Part:
def __init__(self, x, y, area):
self.x = x
self.y = y
self.area = area


# 取左上角
def half_1(pixel_channel):
row = pixel_channel.row
col = pixel_channel.col
half_row = row // 2
half_col = col // 2
channel = np.zeros((half_row + 1, half_col + 1), dtype=type(pixel_channel.channel))
for i in range(0, row, 2):
for j in range(0, col, 2):
channel[i // 2][j // 2] = pixel_channel.channel[i][j]
result = PixelChannel(channel, noise_check(channel), half_row, half_col)
return result


# 取右上角
def half_2(pixel_channel):
row = pixel_channel.row
col = pixel_channel.col
half_row = row // 2
half_col = col // 2
channel = np.zeros((half_row + 1, half_col + 1), dtype=type(pixel_channel.channel))
for i in range(0, row, 2):
for j in range(1, col, 2):
channel[i // 2][j // 2] = pixel_channel.channel[i][j]
result = PixelChannel(channel, noise_check(channel), half_row, half_col)
return result


# 取左下角
def half_3(pixel_channel):
row = pixel_channel.row
col = pixel_channel.col
half_row = row // 2
half_col = col // 2
channel = np.zeros((half_row + 1, half_col + 1), dtype=type(pixel_channel.channel))
for i in range(1, row, 2):
for j in range(0, col, 2):
channel[i // 2][j // 2] = pixel_channel.channel[i][j]
result = PixelChannel(channel, noise_check(channel), half_row, half_col)
return result


# 取右下角
def half_4(pixel_channel):
row = pixel_channel.row
col = pixel_channel.col
half_row = row // 2
half_col = col // 2
channel = np.zeros((half_row + 1, half_col + 1), dtype=type(pixel_channel.channel))
for i in range(1, row, 2):
for j in range(1, col, 2):
channel[i // 2][j // 2] = pixel_channel.channel[i][j]
result = PixelChannel(channel, noise_check(channel), half_row, half_col)
return result


# 建立像素通道类
def create_pixel_channel(img_channel):
(row, col) = img_channel.shape
result = PixelChannel(img_channel, noise_check(img_channel), row, col)
return result


# 不考虑位置
def division1(_8area):
result = [0] * 8
p1 = [_8area[0][0], _8area[0][1], _8area[0][2], _8area[1][2], _8area[2][2], _8area[2][1], _8area[2][0],
_8area[1][0]]
p = sorted(p1)
q = [abs(int(p[0]) - int(p[1])), abs(int(p[1]) - int(p[2])), abs(int(p[2]) - int(p[3])), abs(int(p[3]) - int(p[4])),
abs(int(p[4]) - int(p[5])), abs(int(p[5]) - int(p[6])), abs(int(p[6]) - int(p[7]))]
# 判断区分度
if max(q) < 10:
return result, False
max_index = q.index(max(q))
for i in range(0, max_index + 1):
result[p1.index(p[i])] = 1
for i in range(8):
if result[i] != 1:
result[i] = 2
return result, True


# 考虑位置
def division2(_8area):
result = [0] * 8
p = [_8area[0][0], _8area[0][1], _8area[0][2], _8area[1][2],
_8area[2][2], _8area[2][1], _8area[2][0], _8area[1][0]]
d = [int(p[0]) - int(p[1]), int(p[1]) - int(p[2]), int(p[2]) - int(p[3]), int(p[3]) - int(p[4]),
int(p[4]) - int(p[5]), int(p[5]) - int(p[6]), int(p[6]) - int(p[7]), int(p[7]) - int(p[0])]
max_index = 0
min_index = 0
for i in range(1, 8):
if d[i] > d[max_index]:
max_index = i
if d[i] < d[min_index]:
min_index = i
if max_index == min_index:
pass
elif max_index > min_index:
for i in range(0, min_index + 1):
result[i] = 1
for i in range(min_index + 1, max_index + 1):
result[i] = 2
if max_index < 7:
for i in range(max_index + 1, 8):
result[i] = 1
elif max_index < min_index:
for i in range(0, max_index + 1):
result[i] = 2
for i in range(max_index + 1, min_index + 1):
result[i] = 1
if min_index < 7:
for i in range(min_index + 1, 8):
result[i] = 2
return result, True


# 一维数组映射到二维
def _1d_2_2d(x):
if x == 0:
return 0, 0
elif x == 1:
return 0, 1
elif x == 2:
return 0, 2
elif x == 3:
return 1, 2
elif x == 4:
return 2, 2
elif x == 5:
return 2, 1
elif x == 6:
return 2, 0
elif x == 7:
return 1, 0


# 特殊值处理
def special_check(_8area):
p = [_8area[0][0], _8area[0][1], _8area[0][2], _8area[1][2],
_8area[2][2], _8area[2][1], _8area[2][0], _8area[1][0]]
p_sum = int(p[0]) + int(p[1]) + int(p[2]) + int(p[3]) + int(p[4]) + int(p[5]) + int(p[6]) + int(p[7])
max_differ = 0
max_index = 0
for i in range(8):
if abs(int(p[i]) - (p_sum - int(p[i])) // 7) > max_differ:
max_differ = abs(int(p[i]) - (p_sum - int(p[i])) // 7)
max_index = i
if max_differ > 4:
return _1d_2_2d(max_index)
else:
return -1, -1


def noise_check(img_channel):
(row, col) = img_channel.shape
result = [[0] * col for i in range(row)]
for i in range(1, row - 1):
for j in range(1, col - 1):
# _8_area = type(img_channel)
_8_area = [[0] * 3 for i in range(3)]
_8_area[0][0] = img_channel[i - 1][j - 1]
_8_area[0][1] = img_channel[i - 1][j]
_8_area[0][2] = img_channel[i - 1][j + 1]
_8_area[1][2] = img_channel[i][j + 1]
_8_area[2][2] = img_channel[i + 1][j + 1]
_8_area[2][1] = img_channel[i + 1][j]
_8_area[2][0] = img_channel[i + 1][j - 1]
_8_area[1][0] = img_channel[i][j - 1]
# 不考虑位置
part1, flag1 = division1(_8_area)
# 考虑位置
part2, flag2 = division2(_8_area)
if flag1 == False or flag2 == False:
continue
# 处理特殊值
sx, sy = special_check(_8_area)
if sx != -1:
result[i - 1 + sx][j - 1 + sy] += 1
# 比较
for k in range(8):
if part1[k] != part2[k]:
x, y = _1d_2_2d(k)
result[i - 1 + x][j - 1 + y] += 1
return result


# 找到最合适的值
def find_best(pixel_channel, x, y):
p = pixel_channel.channel[x][y]
# 建立领域列表
neighborhood = []
if pixel_channel.row > x - 1 >= 0 and pixel_channel.col > y - 1 >= 0 and pixel_channel.noise[x - 1][
y - 1] < threshold:
neighborhood.append(pixel_channel.channel[x - 1][y - 1])
if pixel_channel.row > x - 1 >= 0 and pixel_channel.col > y >= 0 and pixel_channel.noise[x - 1][y] < threshold:
neighborhood.append(pixel_channel.channel[x - 1][y])
if pixel_channel.row > x - 1 >= 0 and pixel_channel.col > y + 1 >= 0 and pixel_channel.noise[x - 1][
y + 1] < threshold:
neighborhood.append(pixel_channel.channel[x - 1][y + 1])
if pixel_channel.row > x >= 0 and pixel_channel.col > y + 1 >= 0 and pixel_channel.noise[x][y + 1] < threshold:
neighborhood.append(pixel_channel.channel[x][y + 1])
if pixel_channel.row > x + 1 >= 0 and pixel_channel.col > y + 1 >= 0 and pixel_channel.noise[x + 1][
y + 1] < threshold:
neighborhood.append(pixel_channel.channel[x + 1][y + 1])
if pixel_channel.row > x + 1 >= 0 and pixel_channel.col > y >= 0 and pixel_channel.noise[x + 1][y] < threshold:
neighborhood.append(pixel_channel.channel[x + 1][y])
if pixel_channel.row > x + 1 >= 0 and pixel_channel.col > y - 1 >= 0 and pixel_channel.noise[x + 1][
y - 1] < threshold:
neighborhood.append(pixel_channel.channel[x + 1][y - 1])
if pixel_channel.row > x >= 0 and pixel_channel.col > y - 1 >= 0 and pixel_channel.noise[x][y - 1] < threshold:
neighborhood.append(pixel_channel.channel[x][y - 1])

# 搜索与给定点最接近的非噪声点
# 建立差值列表
d = []
for i in range(len(neighborhood)):
d.append(abs(int(neighborhood[i]) - int(p)))
if len(d) == 0:
return p
min_index = d.index(min(d))

return neighborhood[min_index]


# 考虑缩小二分之一图像
def repair(pixel_channel, half_channel):
# 左上角
for i in range(half_channel[0].row):
for j in range(half_channel[0].col):
if half_channel[0].noise[i][j] >= threshold:
pixel_channel.noise[i * 2][j * 2] += half_channel[0].noise[i][j]

# 右上角
for i in range(half_channel[1].row):
for j in range(half_channel[1].col):
if half_channel[1].noise[i][j] >= threshold:
pixel_channel.noise[i * 2][j * 2 + 1] += half_channel[1].noise[i][j]

# 左下角
for i in range(half_channel[2].row):
for j in range(half_channel[2].col):
if half_channel[2].noise[i][j] >= threshold:
pixel_channel.noise[i * 2 + 1][j * 2] += half_channel[2].noise[i][j]

# 右下角
for i in range(half_channel[3].row):
for j in range(half_channel[3].col):
if half_channel[3].noise[i][j] >= threshold:
pixel_channel.noise[i * 2 + 1][j * 2 + 1] += half_channel[3].noise[i][j]

for i in range(pixel_channel.row):
for j in range(pixel_channel.col):
if pixel_channel.noise[i][j] >= threshold:
pixel_channel.channel[i][j] = find_best(pixel_channel, i, j)

return pixel_channel


def main():
# 图像地址
img_address = "img_noise.png"
# 以BGR方式读入图像
img = cv.imread(img_address, 1)
cv.imshow("img_noise.png", img)
# 通道分离
channel_b, channel_g, channel_r = cv.split(img)
# 建立像素通道类
b = create_pixel_channel(channel_b)
g = create_pixel_channel(channel_g)
r = create_pixel_channel(channel_r)
# 缩小二分之一
half_b = [half_1(b), half_2(b), half_3(b), half_4(b)]
half_g = [half_1(g), half_2(g), half_3(g), half_4(g)]
half_r = [half_1(r), half_2(r), half_3(r), half_4(r)]

new_img = cv.merge((repair(b, half_b).channel, repair(g, half_g).channel, repair(r, half_r).channel))

cv.imwrite("denoised_img.png", new_img)
cv.imshow("denoised_img.png", new_img)
cv.waitKey()
cv.destroyAllWindows()


if __name__ == '__main__':
main()