Chương 9: Thuật toán (Phần 2)

Trở về Mục lục cuốn sách

Các phép toán làm trơn

Những thuật toán này được áp dụng nhằm giảm nhiễu và/hoặc chuẩn bị ảnh cho khâu xử lý tiếp theo, chẳng hạn như phân đoạn. Ta phân biệt giữa các thuật toán tuyến tính và phi tuyến; loại thứ nhất phù hợp với phân tích trong miền Fourier còn loại thứ hai thì không. Ta cũng phân biệt giữa cách thực hiện dựa trên một giá lọc có hình chữ nhật và thực hiện dựa trên giá lọc có hình tròn.

Bộ lọc tuyến tính

Một số thuật toán lọc sẽ được trình bày cùng với những loại giá tiện dụng nhất.

 •  Lọc đồng đều – Hình ảnh ra được dựa trên phép tính trung bình địa phương của bộ lọc đầu vào, trong đó mọi giá trị nằm bên trong giá lọc có trọng số bằng nhau. Trong miền không gian liên tục (x, y), hàm rải điểm (PSF) và hàm truyền được cho trong Bảng 4–T.1 đối với trường hợp chữ nhật và trong Bảng 4–T.3 đối với trường hợp (trụ) tròn. Với miền không gian rởi rạc [m, n] các giá trị lọc là các mẫu của trường hợp miền liên tục. Những ví dụ cho trường hợp chữ nhật (J = K = 5) và trường hợp tròn (R = 2. 5) được chỉ ra trên Hình 26.

(a) Lọc chữ nhật (J = K = 5)         (b) Lọc tròn (R = 2. 5)

Hình 26: Các bộ lọc đồng đều phục vụ làm trơn ảnh

Lưu ý rằng trong cả hai trường hợp, bộ lọc đều được chuẩn hóa sao cho ∑ h[j, k] = 1. Điều này được thực hiện để nếu đầu vào a[m, n] là hằng số thì ảnh đầu ra c[m, n] cũng là hằng số như vậy. Lý luận giải thích có thể được tìm thấy từ thuộc tính của biến đổi Fourier đã đề cập đến trong PT 26). Như có thể thấy được từ Bảng 4, cả hai bộ lọc này đều có các hàm truyền với vùng lõm âm và do đó có thể dẫn đến đảo pha như đã thấy ở Hình 23. Cách thực hiện lọc hình vuông có tính phân ly và tăng dần; cách lọc hình tròn có tính tăng dần.1 2

 •  Lọc tam giác – Ảnh đầu ra được dựa trên phép trung bình địa phương của bộ lọc đầu vào trong đó các giá trị bên trong giá lọc thì có những trọng số khác nhau. Nói chung, bộ lọc này có thể được xem như tích chập của hai bộ lọc đồng đều (giống hệt nhau), hoặc là cùng hình chữ nhật, hoặc tròn, và điều này dẫn đến hệ quả trực tiếp đối với độ phức tạp tính toán.3 4 (Xem Bảng 13.) Trong miền không gian liên tục, hàm rải điểm và hàm truyền được cho trong Bảng 4–T.2 đối với trường hợp giá chữ nhật và trong Bảng 4–T.4 với trường hợp giá (trục) tròn. Như đã thấy ở Bảng 4 các hàm truyền của các bộ lọc này không có vùng lõm âm và do vậy không bộc lộ hiện tượng đảo pha. Các ví dụ cho trường hợp giá chữ nhật (J = K = 5) và giá tròn (R = 2. 5) được chỉ ra ở Hình 27. Một lần nữa, bộ lọc được chuẩn hóa sao cho ∑ h[j, k] = 1.

(a) Bộ lọc hình kim tự tháp (J = K = 5)          (b) Bộ lọc hình nón (R = 2. 5)

Hình 27: Các bộ lọc hình tam giác phục vụ việc làm trơn ảnh

 •  Lọc Gauss – Ứng dụng của nhân Gauss để làm trơn ảnh đã trở thành cực kỳ phổ biến. Điều này là do những thuộc tính nhất định của nhân Gauss (như định lý giới hạn trung tâm, tích không gian-băng thông5 nhỏ nhất) cũng như một số lĩnh vực ứng dụng khác như phát hiện đường ngăn (edge) và phân tích không gian tỉ lệ. Hàm rải điểm và hàm truyền đối với nhân Gauss trong không gian liên tục được cho ở Bảng 4–T6. Bộ lọc Gauss có tính phân ly:

h(x,y) = g_{2D}(x,y) = \left( \frac{1}{\sqrt{2\pi}\sigma} e^{-(x^2 /\,2\sigma^2)} \right)  \bullet \left( \frac{1}{\sqrt{2\pi}\sigma} e^{-(y^2 /\,2\sigma^2)} \right)

 = g1D(x) • g1D(y)

Có 4 cách khác nhau để thực hiện nhân Gauss:

– Tích chập có dùng một số hữu hạn các mẫu (N0) Gauss làm nhân. Người ta thường chọn N0 = ⌈3σ hoặc ⌈5σ.

g_{1D}[n] = \left\{ \begin{array}{cc}  \displaystyle{\frac{1}{\sqrt{2\pi}\sigma} e^{-(n^2 /\,2\sigma^2)}} & |n| \le N_0 \\  0 & |n| > N_0 \\  \end{array} \right.

– Tích chập lặp lại có dùng bộ lọc đồng đều làm nhân.

g1D[n] ≈ u[n] ⊗ u[n] ⊗ u[n]

u[n] = \left\{ \begin{array}{cc}  1\, / \,(2N_0 + 1) & |n| \le N_0 \\  0 & |n| > N_0 \\  \end{array} \right.

Thật ra cách làm (đối với mỗi chiều) thường có dạng:

c[n] = ((a[n] ⊗ u[n]) ⊗ u[n]) ⊗ u[n]

Cách làm này tận dụng phép xấp xỉ dựa trên định lý giới hạn trung tâm. Với một giá trị σ mong muốn ở PT (96), ta dùng N0 = ⌈σ mặc dù điều này hạn chế lựa chọn của ta: σ cần lấy các giá trị nguyên.

– Phép nhân trong miền tần số. Vì biến đổi Fourier của dạng Gauss cũng là một dạng Gauss (xem Bảng 4 –T.6), điều này có nghĩa là ta dễ dàng chuẩn bị được một bộ lọc H(Ω , Ψ) = G2D(Ω , Ψ) để dùng với PT (92). Nhằm tránh những hiệu ứng chặt cụt trong miền tần số gây ra bởi phạm vi vô hạn của dạng Gauss, điều quan trọng là chọn được một giá trị σ đủ lớn. Việc chọn σ > k / π trong đó k = 3 hoặc 4 thường là đạt yêu cầu.

– Dùng một bộ lọc đệ quy. Một bộ lọc kiểu này có phản hồi xung vô hạn và do đó có giá vô hạn. Lọc Gauss phân ly có thể được lập 6 bằng việc áp dụng trình tự sau đối với từng phương khi σ ≥ 0. 5.

i) Chọn σ dựa trên mục tiêu của việc lọc;
ii) Xác định tham số q dựa theo PT (98);
iii) Dùng PT (99) để xác định các hệ số {b0, b1, b2, b3, B} cho bộ lọc;          (97)
iv) Áp dụng phương trình sai phân tiến, PT (100);
v) Áp dụng phương trình sai phân lùi, PT (101);

Mối quan hệ giữa σ mong muốn và q được cho bởi:

q = \left\{ \begin{array}{cc}  0.98711\sigma - 0.96330 & \sigma \ge 2.5 \\  3.97156 -4.14554 \sqrt{1 - 0.26891\sigma} & 0.5 \le \sigma \le 2.5 \\  \end{array} \right.

Các hệ số lọc {b0, b1, b2, b3, B} được định nghĩa bởi:

b0 = 1. 57825 + (2. 44413q) + (1. 4281q2) + (0. 422205q3)
b1 = (2. 44413q) + (2. 85619q2) + (1. 26661q3)
b2 =  − (1. 4281q2) − 1. 2661q3)                                             (99)
b3 = 0. 422205q3
B = 1 − (b1 + b2 + b3) / b0

Phương trình sai phân tiến một chiều nhận vào một hàng (hoặc cột) số liệu đầu vào, a[n], rồi trả lại một kết quả đầu ra trực tiếp, w[n], cho bởi:

w[n] = Ba[n] + (b1w[n − 1] + b2w[n − 2] + b3w[n − 3]) / b0

Phương trình sai phân lùi một chiều nhận vào kết quả trực tiếp w[n] rồi tính ra đầu ra c[n] cho bởi:

c[n] = Bw[n] + (b1c[n + 1] + b2c[n + 2] + b3c[n + 3]) / b0

Phương trình tiến được áp dụng từ n = 0 lên đến n = N − 1, còn phương trình lùi được áp dụng từ n = N − 1 xuống đến n = 0.

Hiệu năng tương đối giữa các cách thực hiện lọc Gauss khác nhau nói trên có thể được diễn tả như sau. Dùng thang đo mức chính xác là sai số căn bình phương (root-square error) \sqrt{\sum_{n=-\infty}^{+\infty} |g[n|\sigma] - h[n]|^2} giữa một dạng Gauss thực, có phạm vi vô hạn, g[nσ], với một dạng xấp xỉ Gauss, h[n], thì các thuật toán trên sẽ cho kết quả như ở Hình 28a. Tốc độ tương đối giữa các thuật toán khác nhau được thể hiện ở Hình 28b.

Thang đo sai số căn-bình phương rất bảo thủ và vì vậy mọi bộ lọc, chỉ trừ “Lọc đồng đều 3 × ” với σ lớn, đều đủ chính xác. Lọc đệ quy là loại nhanh nhất không phụ thuộc vào σ; các loại khác có thể chậm hơn đáng kể. Chẳng hạn, loại FFT [biến đổi Fourier nhanh] chậm hơn 3,1 lần với N = 256. Ngoài ra, loại FFT còn đòi hỏi N là một hợp số có nhiều ước.

a) So sánh độ chính xác        b) So sánh tốc độ

Hình 28: So sánh các thuật toán Gauss khác nhau với N = 256. Chú thích được dùng chung cho cả hai biểu đồ.

 •  Các loại lọc khác – Phương pháp miền Fourier cho phép ta lập một loạt bộ lọc dựa trên những thuật toán làm trơn khác nhau. Khi đó, các bộ lọc làm trơn sẽ là những bộ lọc thông thấp. Nhìn chung, một bộ lọc thông thấp có pha bằng không là rất thich hợp vì nó không tạo nên biến dạng pha. Tầm quan trọng của pha đã được minh họa ở các Hình 5 và 23. Khi những đặc tính miền tần số có thể biểu diễn được dưới dạng giải tích, điều này có thể dẫn đến các dạng thiết lập H(Ω , Ψ) khá dễ dàng. Những dạng có thể lựa chọn bao gồm các bộ lọc thông thấp “Airy” và “Tắt dần theo hàm mũ” trong Bảng 4–T.5 và T.8.

Lọc phi tuyến

Người ta đã phát triển một loạt những bộ lọc làm trơn phi tuyến tính. Mặc dù nói chung, chúng không thể áp dụng được phép phân tích Forier, nhưng các thuộc tính của chúng cũng như lĩnh vực áp dụng đã được nghiên cứu rộng rãi.

 •  Lọc trung vị – Đặc trưng thống kê “trung vị” đã được đề cập đến ở Mục 3.5.2. Lọc trung vị được dựa trên việc di chuyển một khung trên một ảnh (như ở tích chập) và tính giá trị điểm ảnh đầu ra chính bằng giá trị trung vị các độ sáng của vùng trong khung ảnh đầu vào. Nếu khung có kích thước J × K ta có thể sắp xếp toàn bộ J • K điểm ảnh theo giá trị độ sáng tăng dần. Nếu J • K là số lẻ thì số trung vị sẽ bằng số thứ (J • K + 1) / 2 trong danh sách các độ sáng đã sắp xếp. Lưu ý rằng giá trị được chọn sẽ bằng đúng một trong số các độ sáng đã có mà không có sai số làm tròn nào, nếu ta muốn làm việc riêng với các giá trị độ sáng là số nguyên. Thuật toán như được miêu tả ở trên có độ phức tạp chung với mỗi điểm ảnh là O(J • K • log(J • K)). Thật may là, một thuật toán nhanh (Huang và nnk7 đề xuất) có thể giảm độ phức tạp xuống còn O(K) với giả sử rằng J ≥ K.

Một biến thể khác cùng chủ đề với lọc trung vị và cũng rất hữu dụng, đó là lọc hạng phần trăm. Theo đó điểm ảnh ở tâm khung không phải được thay bởi giá trị độ sáng 50% (trung vị) mà là giá trị độ sáng p% trong đó p% biến thiên từ 0% (lọc cực tiểu) đến 100% (lọc cực đại). Các giá trị khác với (p = 50)% nói chung đều không tương ứng với lọc làm trơn.

 •  Lọc Kuwahara – Các đường ranh giới có ảnh hưởng lớn đến sự nhìn ảnh của mắt thường (xem Hình 15) cũng như đến phân tích ảnh. Do vậy, rất cần làm trơn được ảnh mà không ảnh hưởng đến độ sắc nét và, nếu có thể, đến vị trí của ranh giới. Một bộ lọc đạt được mục tiêu trên được gọi là lọc bảo tồn ranh giới và một ví dụ cụ thể là lọc Kuwahara8. Mặc dù bộ lọc này có thể được thực hiện với nhiều kiểu hình dạng khung khác nhau, nhưng thuật toán ở đây sẽ chỉ dùng với khung hình vuông kích thước J = K = 4L + 1 trong đó L là số nguyên. Khung được chia thành bốn vùng như chỉ ra trên Hình 29.

Hình 29: Bốn vùng hình vuông được định nghĩa trong bộ lọc Kuwahara. Ở ví dụ này L = 1 và do đó J = K = 5. Mỗi vùng có kích thước [(J + 1) / 2] × [(K + 1) / 2].

Ở mỗi vùng trong số bốn vùng này (i = 1, 2, 3, 4), độ sáng trung bình mi (trong PT (34)), và phương saii, si2 ở PT (36), được đo đạc. Kết quả giá trị đầu ra của điểm ảnh trung tâm của khung chính là giá trị trung bình của vùng có phương sai nhỏ nhất.

Tóm tắt các thuật toán làm trơn

Bảng sau đây tóm lược những thuộc tính của các thuật toán làm trơn đã trình bày. Kích thước của bộ lọc được coi như có dạng chữ nhật J × K, và không mất tính tổng quát, ta có thể giả sử J ≥ K. Kích thước của ảnh là N × N.

Thuật toán     Miền   Loại Giá  Phân ly/Tăng dần   Độ phức tạp/điểm ảnh 
Đồng đều Không gian Tuyến tính Vuông Có / Có O(hằng số)
Đồng đều Không gian Tuyến tính Tròn Ko / Có O(K)
Tam giác Không gian Tuyến tính   Vuông   Có / Ko O(hằng số)a
Tam giác Không gian Tuyến tính Tròn Ko / Ko O(K)a
Gauss    Không gian   Tuyến tính a Có / Ko O(hằng số)a
Trung vị Không gian Phi tuyến Vuông Ko / Có O(K)a
Kuwahara Không gian Phi tuyến Vuônga Ko / Ko O(J • K)
Loại khác Tần số Tuyến tính — / — O(logN)

Bảng 13: Đặc tính của các bộ lọc làm trơn. aXem giải thích trong nội dung đoạn văn.

Các ví dụ về hiệu ứng gây bởi các thuật toán làm trơn khác nhau được thể hiện trên Hình 30.

a) Ảnh gốc           b) Đồng đều 5 × 5        c) Gauss (σ = 2. 5)

d) Trung vị 5 × 5            e) Kuwahara 5 × 5

Hình 30: Minh họa các loại bộ lọc làm trơn tuyến tính và phi tuyến.

Phép toán dựa trên đạo hàm

Cũng như thao tác làm trơn, việc lấy các đạo hàm không gian trên ảnh số là những phép toán cơ bản trong xử lý ảnh. Vấn đề nền tảng ở đây là, dựa theo định nghĩa toán học của đạo hàm, việc lấy đạo hàm là không thể. Một ảnh số không phải là hàm liên tục a(x, y) của các biến không gian, mà là một hàm rời rạc a[m, n] của các tọa độ không gian là số nguyên. Do đó, những thuật toán trình bày dưới đây chỉ được xem như là xấp xỉ cho các đạo hàm thật của hình ảnh gốc, vốn có tính liên tục theo không gian.

Hơn nữa, như ta có thể thấy từ thuộc tính Fourier ở PT (27), việc lấy đao hàm đã nhân phổ tính hiệu với u, hoặc v. Điều này nghĩa là các nhiễu tần số cao sẽ bị khuếch đại trong ảnh đầu ra. Giải pháp chung cho vấn đề này là kết hợp các phép lấy đạo hàm với phép toán trừ khử nhiễu cao tần; hay nói ngắn gọn là làm trơn kết hợp với phép lấy đạo hàm mong muốn.

Đạo hàm bậc nhất

Vì ảnh là một hàm của hai (hay nhiều) biến, ta cần phải xác định phương mà đạo hàm được lấy theo. Với trường hợp hai chiều, ta có phương ngang, phương dọc, hoặc một phương bất kì xét bằng tổ hợp giữa hai phương ngang, dọc. Nếu đặt hx là bộ lọc (ma trận) đạo hàm theo phương ngang, hy là bộ lọc (ma trận) đạo hàm theo phương dọc, và hθ là là bộ lọc (ma trận) đạo hàm theo góc bất kì, thì:

[hθ] = cosθ • [hx] + sinθ • [hy]

 •  Bộ lọc gra-đien – Cũng có thể tạo ra một đạo hàm véc-tơ, biểu diễn bởi một gra-đien a[m, n], của ảnh:

\nabla a = (\partial a / \partial x) \vec{i_x} + (\partial a / \partial y) \vec{i_y} =  \left( h_x \otimes a \right) \vec{i_x} + \left( h_y \otimes a \right) \vec{i_y}

trong đó \vec{i_x}\vec{i_y} là các véc-tơ đơn vị lần lượt theo các phương ngang và dọc. Từ đó dẫn đến hai đại lượng sau:

Độ lớn gra-đien – $latex |\nabla a| = \sqrt{\left( h_x \otimes a \right)^2 + \left( h_y \otimes a \right)^2}$

Hướng gra-đien – ψ(∇a) = arctan{(hy ⊗ a / hx ⊗ a)}

Độ lớn gra-đien đôi khi được xấp xỉ bởi:

Độ lớn gra-đien xấp xỉ – ∣∇a∣ ≅ ∣hx ⊗ a∣ + ∣hy ⊗ a

Kết quả cuối cùng của những phép tính trên phụ thuộc nhiều vào việc chọn hxhy. Một số cách chọn (hx, hy) sẽ được trình bày sau đây.

 •  Các bộ lọc đạo hàm cơ bản – Các bộ lọc này được cho bởi:

\begin{array}{l}  i) \left[ \textbf{h}_x \right] = \left[ \textbf{h}_y \right]^t = [1 \quad -1] \\  ii) \left[ \textbf{h}_x \right] = \left[ \textbf{h}_y \right]^t = [1 \quad 0 \quad -1] \\  \end{array}

trong đó “t” dùng để chỉ chuyển vị ma trận. Hai bộ lọc này khác hẳn nhau về các đặc trưng độ lớn Fourier và pha Fourier. Với khoảng tần số 0 ≤ Ω  ≤ π, các đặc trưng này được cho bởi:

\begin{array}{llll}  i) [\textbf{h}] = [1 \quad -1] & \overset{F}{\leftrightarrow} & |H(\Omega)| = 2|\sin(\Omega/2)|; & \varphi(\Omega)=(\pi-\Omega)/2 \\  ii) [\textbf{h}] = [1 \quad 0 \quad -1] & \overset{F}{\leftrightarrow} & |H(\Omega)| = 2|\sin \Omega|; & \varphi(\Omega)=\pi/2 \\  \end{array}

Dạng thứ hai (ii) khử được các số hạng có tần số cao (Ω  ≈ π) trong khi dạng thứ nhất (i) thì không. Dạng thứ nhất dẫn tới chuyển pha; dạng thứ hai thì không.

 •  Lọc gra-đien Prewitt – Các bộ lọc này được cho bởi:

\begin{array}{l}  [\textbf{h}_x] = \frac{1}{3} \left[ \begin{array}{ccc}  1 & 0 & -1 \\ 1 & 0 & -1 \\ 1 & 0 & -1  \end{array} \right] = \frac{1}{3} \left[ \begin{array}{c}1\\1\\1\\ \end{array} \right]  \bullet [1 \quad 0 \quad -1] \\  {  [\textbf{h}_y] = \frac{1}{3} \left[ \begin{array}{ccc}  1 & 1 & 1 \\ 0 & 0 & 0 \\ -1 & -1 & -1  \end{array} \right] = \frac{1}{3} \left[ \begin{array}{c}1\\\-1\\ \end{array} \right]  \bullet [1 \quad 1 \quad 1]  }  \end{array}

Cả hxhy đều phân ly được. Trong bộ lọc này, ngoài ý nghĩa về mặt tính toán còn có ý nghĩa về phân tích. Mỗi bộ lọc nhận vào đạo hàm theo một phương bằng PT (107)ii rồi làm trơn theo phương vuông góc bằng một dạng 1-chiều của bộ lọc đồng đều như đã mô tả ở Mục 9.4.1.

 •  Bộ lọc gra-đien Sobel – Các bộ lọc này được cho bởi:

\begin{array}{l}  [\textbf{h}_x] = \frac{1}{4} \left[ \begin{array}{ccc}  1 & 0 & -1 \\ 2 & 0 & -2 \\ 1 & 0 & -1  \end{array} \right] = \frac{1}{4} \left[ \begin{array}{c}1\\2\\1\\ \end{array} \right]  \bullet [1 \quad 0 \quad -1] \\  {  [\textbf{h}_y] = \frac{1}{4} \left[ \begin{array}{ccc}  1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1  \end{array} \right] = \frac{1}{4} \left[ \begin{array}{c}1\\\-1\\ \end{array} \right]  \bullet [1 \quad 2 \quad 1]  }  \end{array}

Một lần nữa, hxhy đều phân ly được. Mỗi bộ lọc nhận vào đạo hàm theo một phương bằng PT (107)ii rồi làm trơn theo phương vuông góc bằng một dạng 1-chiều của bộ lọc tam giác như đã mô tả ở Mục 9.4.1.

 •  Các bộ lọc gra-đien khác – Các kĩ thuật đa dạng trong trong xử lý tín hiệu 1-chiều để thiết kế bộ lọc số đã cho ta những công cụ mạnh để thiết kế các dạng một chiều cho hxhy. Chẳng hạn, dùng thuật toán thiết kế bộ lọc Parks-McClellan, ta có thể chọn các dải tần số nơi mà ta muốn lấy đạo hàm đồng thời chỉ định các dải tần số nơi ta muốn triệt tiêu nhiễu. Thuật toán sẽ tạo ra một bộ lọc lẻ, gồm các số thực, với kích thước nhỏ nhất thỏa mãn yêu cầu đặt ra.

Lấy ví dụ, nếu muốn có bộ lọc có các đặc tính đạo hàm trong một dải thông (với trọng số 1,0) ở khoảng tần số 0. 0 ≤ Ω  ≤ 0. 3π và một dải chặn (trọng số 3,0) ở khoảng 0. 32π ≤ Ω  ≤ π, thì thuật toán sẽ tạo ra bộ lọc gồm 7 mẫu tối ưu sau đây:

[hx] = [hy]t = (1 / 16348)[ − 3571 8212  − 15580 0 11580  − 8212 3571]

Khi đó gra-đien có thể được tính theo PT (103).

 •  Lọc gra-đien Gauss – Trong xử lý ảnh số hiện đại, một trong các kĩ thuật thông dụng nhất là dùng bộ lọc Gauss (xem Mục 9.4.1) để hoàn thành việc làm trơn mong muốn và dùng một trong các đạo hàm được liệt kê ở PT (107). Vì vậy, ta có thể bắt đầu bằng việc áp dụng lọc Gauss đệ quy theo PT (97) rồi theo PT (107)ii để thu được các bộ lọc đạo hàm trơn mong muốn: hxhy. Ngoài ra, để đạt hiệu quả tính toán, ta có thể kết hợp hai bước này thành:

w[n] = (B / 2)(a[n + 1] − a[n − 1]) + (b1w[n − 1] + b2w[n − 2] + b3w[n − 3]) / b0

c[n] = Bw[n] + (b1c[n + 1] + b2c[n + 2] + b3c[n + 3]) / b0

trong đó các hệ số đã được định nghĩa ở PT (99). Phương trình thứ nhất (tiến) được áp dụng từ n = 0 lên đến n = N − 1 còn phương trình thứ hai (lùi) được áp dụng từ n = N − 1 xuống đến n = 0.

 •  Tóm tắt – Những ví dụ về hiệu ứng của các thuật toán đạo hàm khác nhau đối với dạng có nhiễu của Hình 30a (SNR = 29 dB) được thể hiện trên Hình 31a-c. Hiểu ứng của các thuật toán gra-đien độ lớn khác nhau đối với Hình 30a được thể hiện trên Hình 32a-c. Sau khi xử lý, các ảnh đều được giãn tương phản như PT (77) để phục vụ mục đích hiển thị.

(a) Đạo hàm đơn giản – PT (107)ii     (b)  Sobel – PT (110)      (c)  Gauss (σ = 1. 5) & PT (107)ii

Hình 31: Áp dụng các thuật toán khác nhau cho hx – đạo hàm phương ngang.

(a)  Đạo hàm đơn giản – PT (107)ii       (b)  Sobel – PT (110)      (c)  Gauss (σ = 1. 5) & PT (107)ii

Hình 32: Các thuật toán khác nhau cho gra-đien độ lớn ∣∇a.

Gra-đien độ lớn nắm giữ những giá trị lớn nơi đó có những lằn ranh giới đậm trong ảnh. Việc chọn phù hợp giá trị σ trong đạo hàm dựa theo Gauss (Hình 31c) hoặc gra-đien (Hình 32c) cho phép tính được gần như tất cả các dạng khác—đơn giản, Prewitt, Sobel, v.v. Theo nghĩa này, đạo hàm Gauss thể hiện một tập hợp bao trùm các bộ lọc đạo hàm.

Đạo hàm bậc hai

Dĩ nhiên là ta có thể tính các đạo hàm bậc cao hơn của hàm hai biến số. Trong xử lý ảnh, như ta sẽ thấy ở các Mục 10.2.1 và 10.3.2, những đạo hàm bậc hai hay toán tử Laplace đóng vai trò quan trọng. Toán tử Laplace được định nghĩa bởi:

2a = ∂2a / ∂x2 + ∂2a / ∂y2 = (h2x ⊗ a) + (h2y ⊗ a)

trong đó h2xh2y là các bộ lọc đạo hàm bậc hai. Trong miền tần số ta có, với bộ lọc Laplace (từ PT (27)):

$latex \nabla^2 a \overset{F}{\leftrightarrow} -\left(u^2 + v^2 \right) A(u,v)$

Hàm truyền của một toán tử Laplace tương ứng với parabol H(u, v) =  − (u2 + v2).

 •  Bộ lọc đạo hàm bậc hai cơ bản – Bộ lọc này được cho bởi:

[h2x] = [h2y]t = [1  −2 1]

và phổ tần số của bộ lọc này, theo từng phương, được cho bởi:

H(Ω ) = F{1 −2 1} = −2(1−cosΩ )       (116)

trên khoảng tần số  − π ≤ Ω  ≤ π. Hai bộ lọc 1-chiều có thể được dùng theo cách đã đề cập ở PT (113) hoặc kết hợp lại thành một bộ lọc 2-chiều như sau:

[\textbf{h}] = \left[  \begin{array}{ccc}  0 & 1 & 0 \\  1 & -4 & 1 \\  0 & 1 & 0 \\  \end{array}  \right]

và được dùng như ở PT (84).

 •  Toán tử Laplace trên miền tần số – Bộ lọc này là cách thực hiện quy trình tổng quát như ở PT (92), và đối với bộ lọc Laplace thì có dạng:

c[m, n] = F − 1{ − (Ω 2 + Ψ2)A(Ω , Ψ)}     (118)

 •  Bộ lọc đạo hàm bậc hai Gauss – Đây là sự mở rộng trực tiếp từ bộ lọc đạo hàm Gauss bậc nhất đã đề cập trước đây, và có thể áp dụng được độc lập theo từng phương. Trước hết ta áp dụng phép làm trơn Gauss với một giá trị σ được chọn trên cơ sở đặc trưng của bài toán. Sau đó, ta áp dụng bộ lọc đạo hàm bậc hai mong muốn, PT (115) hoặc PT (118). Một lần nữa, ta có quyền chọn giữa các thuật toán làm trơn Gauss khác nhau.

Để cho hiệu quả, ta có thể dùng dạng đệ quy và kết hợp hai bước—làm trơn và phép lấy đạo hàm—như sau:

\begin{array}{l}  w[n] = B\left(a[n] - a[n-1]\right) + \left(b_1 w[n-1] + b_2 w[n-2] + b_3 w[n-3]\right) / b_0 \\  c[n] = B\left(w[n+1] - w[n]\right) + \left(b_1 c[n+1] + b_2 c[n+2] + b_3 c[n+3]\right) / b_0 \\  \end{array}     (119)

trong đó các hệ số khác nhau đã định nghĩa ở PT (99). Một lần nữa, phương trình thứ nhất (tiến) được áp dụng từ n = 0 lên đến n = N − 1 còn phương trình thứ hai (lùi) được áp dụng từ n = N − 1 xuống đến n = 0.

 •  Các bộ lọc Laplace khác – Một lần nữa kĩ thuật thiết kế bộ lọc một chiều là phương pháp mạnh giúp ta tạo ra bộ lọc tối ưu cho từng bài toán cụ thể. Bằng cách dùng thuật toán thiết kế Parks-McClellan, ta có thể chọn những dải tần số ở đó cần lấy đạo hàm bậc hai và những dải tần số ở đó cần triệt tiêu nhiễu. Thuật toán sẽ tạo ra một bộ lọc chẵn, gồm các số thực, với ngắn nhất để đạt được những yêu cầu đặt ra.

Lấy ví dụ, nếu ta muốn một bộ lọc có các đặc tính của đạo hàm bậc hai trong một dải thông (trọng số 1,0) ở khoảng tần số 0.0 ≤ Ω  ≤ 0.3π và một dải chặn (trọng số 3.0) ở khoảng 0. 32π ≤ Ω  ≤ π, thì thuật toán trên sẽ cho ra bộ lọc tối ưu sau với 7 mẫu:

[hx] = [hy]t = (1 / 11043)  [ −3448  10145  1495  −16383  1495  10145  −3448]

Từ đó toán tử Laplace có thể được tính theo PT (113).

 •  Lọc SDGD – Một bộ lọc đặc biệt có ích trong việc tìm ranh giới và đo đạc vật thể là bộ lọc đạo hàm bậc hai theo hướng gra-đien (Second-Derivative-in-the-Gradient-Direction, SDGD). Bộ lọc này có dùng năm đạo hàm riêng phần sau:

\begin{array}{ccc}  \displaystyle{A_{xx} = \frac{\partial^2 a}{\partial x^2}} &  \displaystyle{A_{xy} = \frac{\partial^2 a}{\partial x \partial y}} &  \displaystyle{A_{x} = \frac{\partial a}{\partial x}} \\  \displaystyle{A_{yx} = \frac{\partial^2 a}{\partial x \partial y}} &  \displaystyle{A_{yy} = \frac{\partial^2 a}{\partial y^2}} &  \displaystyle{A_{y} = \frac{\partial a}{\partial y}} \\  \end{array}     (121)

Lưu ý rằng Axy = Ayx từ đó chỉ có tổng cộng là 5 đạo hàm.

Bộ lọc SDGD này kết hợp với các đạo hàm riêng phần như sau:

\displaystyle{SDGD(a) = \frac{A_{xx} A_x^2 + 2A_{xy} A_x A_y + A_{yy} A_y^2} {A_x^2 + A_y^2}}

Như có thể ta đã trông đợi, việc nhiều đạo hàm có mặt trong bộ lọc này khiến cho việc triệt tiêu nhiễu là quan trọng và các bộ lọc đạo hàm Gauss—cả bậc nhất và bậc hai—đều rất nên dùng, dù không bắt buộc.9 Các đạo hàm bậc nhất và bậc hai cũng nhất thiết phải có cùng dải thông và dải chặn. Điều này nghĩa là nêu bộ lọc đạo hàm bậc nhất h1x được cho bởi [1 0  − 1] (PT (107)ii) thì bộ lọc đạo hàm bậc hai cần được cho bởi h1x ⊗ h1x = h2x = [1 0  − 2 0 1].

 •  Tóm tắt – Hệ quả của những đạo hàm bậc hai khác nhau được minh họa trên Hình 33a-e. Tất cả các ảnh đều được giãn tương phản bằng PT (78) với các tham số 1% và 99%, để phục vụ việc hiển thị.

(a) Toán tử Laplace – PT (117)    (b) Parabol Fourier – PT (118)     (c) Gauss (σ = 1. 0) & PT (117)

(d) “Thiết kế” – PT (120)             (e) SDGD (σ = 1. 0) – PT (122)

Hình 33: Các thuật toán khác nhau cho bộ lọc kiểu Laplace và liên quan đến Laplace.

Các bộ lọc khác

Tồn tại một số vô hạn các bộ lọc, cả tuyến tính lẫn phi tuyến, có thể dùng để xử lý ảnh. Do vậy chúng tôi sẽ không thể mô tả nhiều hơn những loại cơ bản nhất ở trong mục này. Chi tiết về các loại bộ lọc khác có thể tìm thấy trong các tài liệu tham khảo cũng như trong tài liệu ứng dụng. Điều quan trọng là dùng một tập hợp thống nhất, gồm ít ảnh, nhưng phù hợp với lĩnh vực áp dụng để hiểu được các hiệu ứng của một bộ lọc hoặc lớp bộ lọc cho trước. Hiệu ứng của bộ lọc đối với ảnh thường có thể hiểu được bằng cách dùng ảnh có các miền rõ rệt với kích thước khác nhau để hiển thị hiệu ứng đối với cách ranh giới, hoặc bằng cách dùng các mẫu kiểm tra như “quét hình sin” để hiển thị các hiệu ứng trên miền tần số. Cách làm thứ nhất đã được dùng ở trên (các Hình 21, 23, và 30–33), còn cách thứ hai được thể hiện ở Hình 34 dưới đây.

(a) Lọc thông thấp       (b) Lọc dải thông           (c) Lọc thông cao

Hình 34: Các thuật toán khác nhau áp dụng cho ảnh kiểm tra dạng hình sin.


  1. Groen, F.C.A., R.J. Ekkers, and R. De Vries, Image processing with personal computers. Signal Processing, 1988. 15: p. 279-291.
  2. Verbeek, P.W., H.A. Vrooman, and L.J. Van Vliet, Low-Level Image Processing by Max-Min Filters. Signal Processing, 1988. 15: p. 249-258.
  3. Groen, F.C.A., R.J. Ekkers, and R. De Vries, Image processing with personal computers. Signal Processing, 1988. 15: p. 279-291.
  4. Verbeek, P.W., H.A. Vrooman, and L.J. Van Vliet, Low-Level Image Processing by Max-Min Filters. Signal Processing, 1988. 15: p. 249-258.
  5. space-bandwidth product
  6. Young, I.T. and L.J. Van Vliet, Recursive Implementation of the Gaussian Filter. Signal Processing, 1995. 44(2): p. 139-151.
  7. Huang, T.S., G.J. Yang, and G.Y. Tang, A Fast Two-Dimensional Median Filtering Algorithm. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1979. ASSP-27: p. 13-18.
  8. Kuwahara, M., et al., Processing of RI-angiocardiographic images, in Digital Processing of Biomedical Images, K. Preston and M. Onoe, Editors. 1976, Plenum Press: New York. p. 187-203.
  9. Van Vliet, L.J., Grey-scale measurements in multi-dimensional digitized images, PhD Thesis: Delft University of Technology, 1993.
Advertisements

%(count) bình luận

Filed under Cơ sở

One response to “Chương 9: Thuật toán (Phần 2)

  1. Pingback: Chương 1: Giới thiệu chung | Blog của Chiến

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s