-
Notifications
You must be signed in to change notification settings - Fork 0
/
convolution.py
213 lines (170 loc) · 9.51 KB
/
convolution.py
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
import numpy as np
# a simple function similar to np.pad()
def pad(signal: np.ndarray, pad_width: int, mode: str = 'fill', fill_value: int = 0) -> np.ndarray:
"""
Pad an array with specified padding options.
Args:
signal (np.ndarray): The input array to be padded.
pad_width (int): The width of padding to apply to each side of the array.
mode (str, optional): The padding mode. Options are:
- 'fill': Pads with `fill_value`.
- 'circular': Circular padding where values wrap around.
- 'symmetric': Pads symmetrically by mirroring the values at the edges. Defaults to 'fill'.
fill_value (int, optional): The value used for padding when `mode` is 'fill'. Defaults to 0.
Raises:
ValueError: If `mode` is not one of 'fill', 'circular', or 'symmetric'.
ValueError: If the number of dimensions in `signal` is not 1D or 2D.
Returns:
np.ndarray: The padded array with the same shape as `signal` adjusted by `pad_width`.
"""
output = np.full(shape= [i + 2 * pad_width for i in signal.shape], fill_value= fill_value)
# add signal to the center of the output
if signal.ndim == 1:
output[pad_width: signal.shape[0] + pad_width] = signal
if mode == 'circular':
output[:pad_width], output[-pad_width:] = output[-2 * pad_width: -pad_width], output[pad_width: 2 * pad_width]
elif mode == 'symmetric':
output[:pad_width], output[-pad_width:] = output[pad_width: 2 * pad_width][::-1], output[-2 * pad_width: -pad_width][::-1]
elif mode != 'fill':
raise ValueError(f"Invalid `mode` value: {mode}; should be 'fill' or 'circular' or 'symmetric'.")
elif signal.ndim == 2:
output[pad_width: signal.shape[0] + pad_width, pad_width: signal.shape[1] + pad_width] = signal
if mode == 'circular':
# Iterate through the rows and columns of the new array
for i in range(output.shape[0]):
for j in range(output.shape[1]):
# Calculate the corresponding position in the original array
# Wrap around the edges if necessary
new_i = (i - pad_width) % signal.shape[0]
new_j = (j - pad_width) % signal.shape[1]
# Assign the value from the original array to the new array
output[i, j] = signal[new_i, new_j]
elif mode == 'symmetric':
for i in range(pad_width):
# pad the top and bottom edges
output[i, :] = output[2 * pad_width - i - 1, :]
output[-i - 1, :] = output[pad_width + i + 1 , :]
# pad the left and right edges
output[:, i] = output[:, 2 * pad_width - i - 1]
output[:, -i - 1] = output[:, pad_width + i + 1]
elif mode != 'fill':
raise ValueError(f"Invalid `mode` value: {mode}; should be 'fill' or 'circular' or 'symmetric'.")
else:
raise ValueError(f"Invalid `signal` dim: {signal.ndim}; should be 1D or 2D.")
return output
# a simple function similar to np.convolve()
def convolve_1d(signal: np.ndarray, filter: np.ndarray, mode: str = 'full', boundary: str = 'fill', fill_value: int = 0, correlation: bool = False) -> np.ndarray:
"""
Convolve two 1-dimensional arrays with options for boundary handling and mode.
Args:
signal (np.ndarray): The input array (of length M) to be convolved.
filter (np.ndarray): The filter array (of length N) to be applied on the signal.
mode (str, optional): The convolution mode. Options are:
- 'full': Returns the full discrete linear convolution (size: M+N-1).
- 'valid': Returns only the elements that do not rely on zero-padding (size: M-N+1).
- 'same': Returns the same size as the signal (size: M). Defaults to 'full'.
boundary (str, optional): The boundary handling mode. Options are:
- 'fill': Pads with `fill_value`.
- 'circular': Circular padding where values wrap around.
- 'symmetric': Pads symmetrically by mirroring the values at the edges. Defaults to 'fill'.
fill_value (int, optional): The value used for padding when `boundary` is 'fill'. Defaults to 0.
correlation (bool, optional): If `True`, computes the cross-correlation instead of convolution. Defaults to False.
Raises:
ValueError: If `signal` or `filter` is not a 1D array.
ValueError: If `mode` is not one of 'full', 'valid', or 'same'.
Returns:
np.ndarray: The result of the convolution or correlation operation.
"""
# check if signal is 1D or raise an error
if signal.ndim != 1:
raise ValueError("Expected 'signal' to be 1-dimensional")
# check if filter is 1D or raise an error
if filter.ndim != 1:
raise ValueError("Expected 'filter' to be 1-dimensional")
# mode
if mode == 'full':
pad_width = filter.shape[0] - 1
output_length = signal.shape[0] + filter.shape[0] - 1
elif mode == 'valid':
pad_width = 0
output_length = signal.shape[0] - filter.shape[0] + 1
elif mode == 'same':
pad_width = (filter.shape[0] - 1) // 2
output_length = signal.shape[0]
else:
raise ValueError(f"Invalid `mode` value: {mode}; should be 'fill' or 'circular' or 'symmetric'.")
# padding signal if needed
padded_signal = pad(signal, pad_width= pad_width, mode= boundary, fill_value= fill_value)
# reverse of filter
if not correlation:
filter_reversed = filter[::-1]
# convolution
output = np.empty(shape= output_length)
for i in range(output_length):
output[i] = np.dot(padded_signal[i: i + filter.shape[0]], filter_reversed)
return output
# a simple function similar to scipy.signal.convolve2d
def convolve_2d(signal: np.ndarray, filter: np.ndarray, mode: str = 'full', boundary: str = 'fill', fill_value: int = 0, correlation: bool = False) -> np.ndarray:
"""
Convolve two 2-dimensional arrays with options for boundary handling and mode.
Args:
signal (np.ndarray): The input 2D array to be convolved.
filter (np.ndarray): The filter 2D array to be applied on the signal.
mode (str, optional): The convolution mode. Options are:
- 'full': Returns the full discrete linear convolution (size: M+N-1).
- 'valid': Returns only the elements that do not rely on zero-padding (size: M-N+1).
- 'same': Returns the same size as the signal (size: M). Defaults to 'full'.
boundary (str, optional): The boundary handling mode. Options are:
- 'fill': Pads with `fill_value`.
- 'circular': Circular padding where values wrap around.
- 'symmetric': Pads symmetrically by mirroring the values at the edges. Defaults to 'fill'.
fill_value (int, optional): The value used for padding when `boundary` is 'fill'. Defaults to 0.
correlation (bool, optional): If `True`, computes the cross-correlation instead of convolution. Defaults to False.
Raises:
ValueError: If `signal` or `filter` is not a 2D array.
ValueError: If `mode` is not one of 'full', 'valid', or 'same'.
Returns:
np.ndarray: The result of the convolution or correlation operation.
"""
# check if signal is 2D or raise an error
if signal.ndim != 2:
raise ValueError("Expected 'signal' to be 2-dimensional")
# check if filter is 2D or raise an error
if filter.ndim != 2:
raise ValueError("Expected 'filter' to be 2-dimensional")
# mode
if mode == 'full':
pad_width = filter.shape[0] - 1
output_length = (signal.shape[0] + filter.shape[0] - 1, signal.shape[1] + filter.shape[0] - 1)
elif mode == 'valid':
pad_width = 0
output_length = (signal.shape[0] - filter.shape[0] + 1, signal.shape[1] - filter.shape[0] + 1)
elif mode == 'same':
pad_width = (filter.shape[0] - 1) // 2
output_length = signal.shape
else:
raise ValueError(f"Invalid `mode` value: {mode}; should be 'fill' or 'circular' or 'symmetric'.")
# padding signal if needed
padded_signal = pad(signal, pad_width= pad_width, mode= boundary, fill_value= fill_value)
# reverse of filter
if not correlation:
filter_reversed = np.flip(np.flip(filter, axis= 1), axis= 0)
# convolution
output = np.empty(shape= output_length)
for row in range(output_length[0]):
for col in range(output_length[1]):
output[row, col] = np.multiply(padded_signal[row: row + filter.shape[0], col: col + filter.shape[1]], filter_reversed).sum()
return output
if __name__ == '__main__':
arr1 = np.arange(5)
filter_1 = np.array([1, 2, 3])
arr2 = np.arange(25).reshape(5, 5)
filter_2 = np.arange(9).reshape(3, 3)
print(pad(signal=arr1, pad_width=2, mode='fill', fill_value=2))
print(pad(signal=arr1, pad_width=2, mode='circular'))
print(pad(signal=arr1, pad_width=2, mode='symmetric'))
print(pad(signal=arr2, pad_width=2, mode='fill', fill_value=0))
print(pad(signal=arr2, pad_width=2, mode='circular'))
print(pad(signal=arr2, pad_width=2, mode='symmetric'))
print(convolve_1d(arr1, filter_1, mode='same', boundary='fill', fill_value=0))
print(convolve_2d(arr2, filter_2, mode='valid', boundary='fill', fill_value=0))