Convolution - Tích chập giải thích bằng code thực tế

Hiệu đính lại bài viết. Sau khi đăng lên, một số chuyên gia góp ý thực ra thuật toán áp dụng trong CNN là cross correlation chứ không phải là convolution. Nhiều lập trình viên viết thư viện Deep Learning có chút nhầm lẫn hoặc quen miệng giữa 2 thuật toán này bởi chúng rất giống nhau. Nếu Kernel matrix đối xứng trên với dưới, trái và phải thì kết quả Convolution và Correlation giống hệt nhau.

Tham khảo thêm ở đây nhé 
Do convolutional neural networks flip the kernel?
https://www.youtube.com/watch?v=MQm6ZP1F6ms
https://www.youtube.com/watch?v=C3EEy8adxvc

Convolution là một kỹ thuật quan trọng xử lý ảnh (digital image processing). Nó có mặt trong hầu hết các thuật toán làm mờ (Gausian Blur), hay làm rõ các đường (edge detector). Trong nhận dạng ảnh (deep learning image processing), convolution layer là một tầng biến đổi ma trận đầu vào để làm rõ và tách ra các đặc tính của hình ảnh mà vẫn bảo toàn tính tương quan không gian giữa đầu ra và đầu vào.

Convolution hay còn gọi là tích chập cũng được sử dụng trong phép biến đổi Fourrier nhưng sẽ biến đổi từ miền thời gian sang tần số hoặc ngược lại.

Khi tôi xem các paper về Convolution tôi thấy các hàm toán học rất trừu tượng, ngược lại xem các ví dụ mẫu Keras, TensorFlow, thì convolution layer chỉ được đóng gói sẵn nên cũng khó hình dung nó sẽ làm gì. Bài viết này sẽ trình bày nhiều bước khác nhau tôi lập trình hàm convolution bằng Python trong ngày nghỉ lễ 2/9/2019
Toàn bộ code tôi để ở đây https://github.com/TechMaster/CythonOpenCV/tree/master/Convolution

Bước 1: Thí nghiệm xử lý ảnh trực quan trên setosa.io

Hãy vào web site này http://setosa.io/ev/image-kernels/ để trải nghiệm với kernel khác nhau kết quả đầu ra sẽ khác nhau như thế nào. Nếu hiểu được thí nghiệm này, các bước tiếp theo bạn sẽ thấy rất dễ dàng.

Bước 2: Thí nghiệm với ma trận đủ nhỏ

Trước tiên hãy thử nghiệm với ma trận image đầu vào đủ nhỏ để tính toán thủ công và kiểm tra kết quả đã!

Bên trái là ma trận đầu vào, có thể là ảnh. Bên phải là kernel là một ma trận dùng để biến đổi ma trận đầu vào trong 2 vòng lặp lồng nhau convolution.
Từ trái qua phải, từ trên xuống dưới dịch chuyển cửa sổ có kích thước bằng với kernel trên ma trận đầu vào, thực hiện phép nhân từng phần tử cùng vị trí ở ma trận cửa số với kernel rồi tính tổng ra giá trị scalar điền vào ma trận kết quả. Đây gọi là dot product

Có vài điểm cần lưu ý:

• Tích chập biến đổi các điểm ảnh nằm kề nhau trong ma trận cửa sổ
• Ma trận kernel có hàng và cột là số lẻ để giá trị dot product gán được vào ô chính giữa, ma trận đầu dôi một hàng, một cột 
• Không nhất thiết phải bằng nhau, như thông thường kernel là ma trận vuông
• Kết quả sau tích chập convolution sẽ bị hụt đi vài hàng và cột. Ví dụ kernel matrix là (3x3), thì hụt 2 hàng, 2 cột, kernel matrix (4, 4) sẽ hụt 3 hàng, 3 cột.

Bước 3: Code thử nghiệm

Đây là code ban đầu chưa tối ưu, dùng nhiều vòng lặp lồng nhau, quan trọng là dễ hiểu. Định nghĩa convolve_nest_loop trong file convolute_lib.py

def convolve_nest_loop(img, kernel):
    img_height = img.shape[0]
    img_width = img.shape[1]

    kernel_height = kernel.shape[0]
    kernel_width = kernel.shape[1]

    H = (kernel_height - 1) // 2
    W = (kernel_width - 1) // 2

    out = np.zeros((img_height, img_width))

    for i in np.arange(H, img_height - H):
        for j in np.arange(W, img_width - W):
            sum = 0
            for k in np.arange(-H, H + 1):
                for l in np.arange(-W, W + 1):
                    a = img[i + k, j + l]
                    w = kernel[H + k, W + l]
                    sum += (w * a)
            out[i, j] = sum
    return out

• line 5, 6: kernel_height, kernel_width luôn là số lẻ để kết quả dot product trả về ghi vào vị trí tâm chính giữa ma trận cửa sổ !
• line 8, 9: H, W là một nửa hàng và nửa cột sau khi loại đi đường nằm chính giữa
• line 11: out là ma trận kết quả, có kích thước bằng ma trận đầu vào, được khởi tạo ban đầu là toàn giá trị 0.
• line 13, 14: Hai vòng lặp ngoài cùng biến đếm i cho hàng, j cho cột. Biến đếm i, j thay đổi để dịch chuyển ma trận cửa sổ.
• line 16, 17: Hai vòng lặp k, l thực hiện phép dot product giữa ma trận cửa sổ với kernel

Tại sao vòng lặp i, j không bằng đầu từ 0 mà lại bắt đầu từ H, W? Hãy thử nhìn vào hình minh hoạ và tự trả lời nhé.
Hãy chạy thử file này https://github.com/TechMaster/CythonOpenCV/blob/master/Convolution/Convolute_Basic1.py

import numpy as np

import convolute_lib as cnn

in_img = np.array([[1, 0, 0, 1, 0],
                   [0, 1, 1, 0, 1],
                   [1, 0, 1, 0, 1],
                   [1, 0, 0, 1, 1],
                   [0, 1, 1, 0, 1]
                   ])

kernel = np.array([[1, 0, 0],
                   [0, 1, 1],
                   [1, 0, 1]])


out_img = cnn.convolve_nest_loop(in_img, kernel)
with np.printoptions(suppress=True):
    print(out_img)

Kết quả ra được là ma trận cùng kích thước bằng ma trận đầu vào nhưng xung quanh viền toàn là số 0, thực chất các phần tử này không được ghi giá trị vào trong phép tích chập.

[[0. 0. 0. 0. 0.]
 [0. 5. 1. 3. 0.]
 [0. 2. 3. 3. 0.]
 [0. 2. 2. 5. 0.]
 [0. 0. 0. 0. 0.]]

Bước 4: thay 2 vòng lặp bằng np.tensordot

logic code này có thể thay bằng numpy tensordot . Code ngọn và chạy nhanh hơn

sum = 0
for k in np.arange(-H, H + 1):
    for l in np.arange(-W, W + 1):
       a = img[i + k, j + l]
       w = kernel[H + k, W + l]
       sum += (w * a)
       out[i, j] = sum

Tốc độ nhanh hơn 3-5 lần với tensordot. Xem hàm def convolve_np(img, kernel) nhé

for i in np.arange(H, img_height - H):
    for j in np.arange(W, img_width - W):
        out[i - H, j - W] = np.tensordot(img[i - H:i + H + 1, j - W:j + W + 1], kernel, axes=((0, 1), (0, 1)))

Bước 5: bỏ padding zero ở ma trận đầu ra hoặc thêm padding zero ở ma trận đầu vào

Trong file convolute_lib.py có một số hàm :

• def convolve_nest_loop(img, kernel): dùng 2 nested loop để tính dot product
• def convolve_np(img, kernel): thay nested loop bằng tensordot
• def convolve_np2(img, kernel): loại bỏ padding zero ở ma trận đầu ra, số hàng và cột hụt đi
• def convolve_np4(img, kernel): thêm padding zero vào ma trận đầu vào để đầu ra có kích thước bằng ma trận đầu vào

File thực hành là https://github.com/TechMaster/CythonOpenCV/blob/master/Convolution/Convolute_Basic.py

Chúng ta chỉ tập trung vào def convolve_np4(img, kernel): vì nó giữ nguyên kích thước ma trận sau biến đổi. Trong các bài tiếp theo tôi sẽ giải thích cơ chế của pool layer trong Convolution Network, pool layer mới thực sự thu nhỏ lại kích thước của ma trận.

def convolve_np4(img, kernel):
    img_height = img.shape[0]
    img_width = img.shape[1]

    kernel_height = kernel.shape[0]
    kernel_width = kernel.shape[1]

    H = (kernel_height - 1) // 2
    W = (kernel_width - 1) // 2

    out = np.zeros((img_height, img_width))

    img = cv2.copyMakeBorder(img, H, H, W, W, cv2.BORDER_REPLICATE)

    for i in np.arange(H, img_height + 1):
        for j in np.arange(W, img_width + 1):
            out[i - H, j - W] = np.tensordot(img[i - H:i + H + 1, j - W:j + W + 1], kernel, axes=((0, 1), (0, 1)))

    return out

Bước 6: kiểm thử hàm convolute

Để kiểm tra hàm convolute có lập trình đúng hay không hãy sử dụng kernel là ma trận identity, phần tử chính giữa bằng 1, còn lại bằng 0 tất .
Kết quả ma trận đầu ra phải giống hết ma trận đầu vào là được.

• Line 3 import thư viện convolute_lib vừa viết
• Line 12 định nghĩ ma trận identity
• Line 17 gọi hàm convolve_np4

import numpy as np

import convolute_lib as cnn

in_img = np.array([[1, 0, 0, 1, 0],
                   [0, 1, 1, 0, 1],
                   [1, 0, 1, 0, 1],
                   [1, 0, 0, 1, 1],
                   [0, 1, 1, 0, 1]
                   ])

identity = np.array((
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]))

out_img = cnn.convolve_np4(in_img, identity)
with np.printoptions(suppress=True):
    print(out_img)

Kết luận

• Convolution, tích chập thực ra cũng đơn giản nhỉ, mấy vòng lặp for là xử lý ngon lành. Tuy nhiên trong ứng dụng thực tế, tăng tốc xử lý hàm này mới là chuyện đáng bàn
• Thay vì chỉ đọc nhiều paper công thức toán trừu tượng, mình chọn cách lập trình để kiểm chứng. Tất nhiên mình cũng tham khảo từ nhiều tác giả khác, trong khi lập trình rút ra được nhiều điều thú vị như xử lý padding zero, tối ưu tốc độ thực thi, tại sao trong 2 vòng lặp dịch ma trận cửa sổ của hàm convolve_np4 lại phải cộng thêm 1 ở giá trị stop...
• Trong bài sau, mình sử dụng thư viện convolution code ở bài này để tạo ra một loạt hiệu ứng xử lý ảnh rất cool.