1. Giới thiệu
Khi học xử lý tín hiệu, điều khiển hay thị giác máy tính, nhiều người thường thấy phép tích chập (convolution) với những công thức khá dài và khó nhớ. Tuy nhiên, nếu bỏ qua cách viết bằng tổng hay tích phân, thì có một cách hiểu rất trực quan:
Tích chập thực chất chính là phép nhân đa thức.
Ý tưởng này đúng không chỉ với tín hiệu một chiều mà còn mở rộng sang ảnh hai chiều, dữ liệu ba chiều và thậm chí dữ liệu nhiều chiều.
Nói cách khác, thay vì nhớ công thức tích chập, ta chỉ cần nhớ cách nhân hai đa thức, còn công thức tích chập sẽ tự xuất hiện.
2. Trường hợp 1D
Giả sử có hai tín hiệu
x = [1 2 3]h = [4 5]
Ta coi chúng là hệ số của hai đa thức
X(z) = 1 + 2z + 3z²H(z) = 4 + 5z
Bây giờ chỉ việc nhân hai đa thức như học phổ thông.
Bước 1
1 × (4 + 5z)= 4 + 5z
Bước 2
2z × (4 + 5z)= 8z + 10z²
Bước 3
3z² × (4 + 5z)= 12z² + 15z³
Cộng tất cả lại
4+ (5+8)z+ (10+12)z²+15z³
thu được
4 + 13z + 22z² + 15z³
Do đó hệ số là
[4 13 22 15]
Đây cũng chính là kết quả của
conv([1 2 3],[4 5])
Như vậy
Tích chập 1D chính là phép nhân hai đa thức một biến.
3. Tại sao công thức tích chập lại xuất hiện?
Giả sử
X(z)=x0+x1z+x2z²+...
H(z)=h0+h1z+h2z²+...
Khi nhân hai đa thức, hệ số của z² sẽ được tạo bởi
x0·h2+x1·h1+x2·h0
Hệ số của z³ sẽ được tạo bởi
x0·h3+x1·h2+x2·h1+x3·h0
Nếu viết tổng quát thì chính là
yk = Σ xi h(k-i)
Đây chính là công thức tích chập trong sách giáo khoa.
Nói cách khác,
Công thức tích chập không phải tự nhiên sinh ra. Nó chính là quy tắc cộng các hệ số khi nhân hai đa thức.
4. Trường hợp 2D
Bây giờ xét ma trận
A =1 23 4
Ta coi mỗi phần tử là hệ số của đa thức hai biến.
A(x,y)= 1+2y+3x+4xy
Trong đó
- x biểu diễn theo hàng
- y biểu diễn theo cột
Giả sử
B =5 6
tương ứng với
B(x,y)=5+6y
Bây giờ ta vẫn nhân đa thức như bình thường.
(1+2y+3x+4xy)(5+6y)
Ta được
5+16y+12y²+15x+38xy+24xy²
Nếu sắp các hệ số theo đúng vị trí của x và y thì thu được
5 16 1215 38 24
Đây chính là kết quả của
conv2(A,B)
Điều đáng chú ý là
Không có phép toán mới nào cả.
Ta chỉ đang nhân đa thức, nhưng thay vì có một biến, giờ có hai biến.
5. Minh họa trực quan cho 2D
Trong 1D
1 +2z +3z²
ta dùng
z
để biểu diễn vị trí.
Trong 2D ta cần hai hướng
x → hàngy → cột
Do đó
1 23 4
được viết thành
1+2y+3x+4xy
Ta thấy
1 → góc trên trái2y → dịch sang phải3x → dịch xuống dưới4xy → vừa xuống vừa sang phải
Như vậy mỗi phần tử của ma trận tương ứng với một đơn thức.
6. Trường hợp 3D
Giả sử có tensor
A(i,j,k)
Thay vì hai biến, bây giờ ta dùng ba biến
xyz
Một phần tử
A(2,1,3)
sẽ tương ứng với
x²yz³
Toàn bộ tensor sẽ trở thành một đa thức ba biến.
Ví dụ
A(:,:,1)=1 2
A(:,:,2)=3 4
được viết thành
1+2y+3z+4yz
Nếu
B(:,:,1)5 6
thì
B=5+6y
Khi nhân
(1+2y+3z+4yz)(5+6y)
ta thu được đúng các hệ số của phép
convn(A,B)
Điểm khác duy nhất là
- 1D dùng một biến
- 2D dùng hai biến
- 3D dùng ba biến
Nhưng bản chất vẫn chỉ là nhân đa thức.
7. Tổng quát N chiều
Nếu dữ liệu có N chiều thì ta dùng N biến
x1,x2,...,xN
Mỗi phần tử của tensor sẽ tương ứng với một đơn thức
x1^i1 x2^i2 ... xN^iN
Sau đó chỉ việc nhân hai đa thức nhiều biến.
Các hệ số sau khi nhân chính là kết quả của phép tích chập N chiều.