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

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

Trong chương này chúng tôi trình bày các phép tính là nền tảng của xử lý ảnh số. Các phép toán này có thể được chia thành bốn loại: tính toán dựa trên biểu đồ tần số của ảnh, dựa trên toán học đơn giản, dựa trên tích chập, và dựa trên hình thái toán học. Ngoài ra, các phép toán này còn được miêu tả trên khía cạnh thực hiện cài đặt, bao gồm các phép toán điểm, phép toán địa phương, hoặc phép toán toàn cục, như được đã đề cập đến ở Mục 2.2.1.

Phép toán dựa trên biểu đồ tần số

Một lớp các phép toán quan trọng đối với điểm được dựa trên việc xử lý biểu đồ tần số của ảnh hoặc của một vùng. Những ví dụ quan trọng nhất sẽ được trình bày dưới đây.

Kéo giãn độ tương phản

Thông thường, ảnh được quét theo cách mà các giá trị độ sáng thu được không tận dụng hết toàn bộ khoảng động cho phép. Điều này có thể dễ thấy từ biểu đồ các giá trị độ sáng trên Hình 6. Bằng cách kéo giãn biểu đồ tần số dọc theo cả khoảng động ta có thể khắc phục được tình trạng này. Nếu ảnh được cho phép có độ sáng đi từ 0 đến 2B − 1 (xem Mục 2.1), thì thường ta nên gắn giá trị 0% (hoặc cực tiểu như định nghĩa ở Mục 3.5.2) với giá trị 0 và giá trị 100% (hoặc cực đại) với giá trị 2B − 1. Phép chuyển đổi thích hợp sẽ là:

\displaystyle{ b[m,n] = \left(2^B - 1\right) \bullet \frac{ a[m,n] - \text{min} } {\text{max} - \text{min}}}

Tuy vậy, công thức này phần nào nhạy đối với các điểm biệt lập; một công thức kém nhạy nhưng tổng quát hơn được cho bởi:

$latex b[m,n] = \left\{ \begin{array} {cc}
0 & a[m,n] \le p_\text{th\^ap} \% \\
\displaystyle{ \left(2^B – 1\right) \bullet \frac{ a[m,n] – p_\text{th\^ap} } {p_\text{cao} – p_\text{th\^ap}} } &
p_\text{th\^ap}\% < a[m,n] < p_\text{cao}\% \\
\left(2^B – 1\right) & a[m,n] \ge p_\text{cao}\% \\
\end{array}
\right. $

Ở dạng công thức này ta có thể chọn các giá trị 1% và 99% lần lượt cho pthấp% và pcao%, thay vì các giá trị 0% và 100% ở PT (77). Cũng có thể áp dụng phép toán kéo giãn độ tương phản cho một vùng bằng cách từ biểu đồ tần số của vùng để xác định nên các giới hạn thích hợp cho thuật toán. Lưu ý rằng trong các PT (77) và (78) có thể bỏ thừa số 2B − 1 để đơn giản chuẩn hóa khoảng độ sáng về 0 ≤ b[m, n] ≤ 1. Điều này đồng nghĩa với việc biểu diễn độ sáng cuối cùng của điểm ảnh dưới dạng các số thực thay vì số nguyên; với các máy tính hiện đại có tốc độ nhanh và RAM lớn thì điều này hoàn toàn khả thi.

Cân bằng hóa

Khi muốn so sánh hai hoặc nhiều ảnh theo một cơ sở riêng, chẳng hạn “vân ảnh” (image texture), thường thì trước hết ta chuẩn hóa biểu đồ tần số về một dạng “tiêu chuẩn”. Điều này có thể đặc biệt hữu ích khi ảnh đã được thu nhận trong nhiều môi trường khác nhau. Kĩ thuật chuẩn hóa biểu đồ tần số thường gặp nhất là cân bằng hóa biểu đồ tần số, trong đó ta cố gắng thay đổi biểu đồ tần số qua cách áp dụng hàm b = f(a) để tạo ra một biểu đồ tần số không đổi với tất cả mọi giá trị độ sáng. Điều này dẫn đến phân bố độ sáng trong đóng mọi giá trị đều có khả năng xuất hiện như nhau. Thật không may là với một tấm ảnh bất kì, ta chỉ có thể xử lý gần đúng kết quả như vậy.

Với một hàm f( ⋅ ) “thích hợp”, mối liên hệ giữa hàm mật độ xác suất đầu vào, hàm mật độ xác suất đầu ra, và hàm f( ⋅ ) được cho bởi:

pb(b)db = pa(a)da → df = pa(a)da / pb(b)

Từ PT (79) ta thấy được rằng “thích hợp” nghĩa là f( ⋅ ) phải khả vi và df / da ≥ 0. Khi cân bằng hóa biểu đồ ta số, ta muốn pb(b) =  hằng số và điều này có nghĩa là:

f(a) = (2B − 1) P(a)

trong đó P(a) là hàm phân bố xác suất như đã định nghĩa trong Mục 3.5.1 và minh họa trên HÌnh 6a. Nói cách khác, hàm phân bố xác suất sau khi phân lượng được chuẩn hóa từ 0 đến 2B − 1 trong bảng phục vụ việc cân bằng hóa biểu đồ tần số. Các Hình 21a-c minh họa hiệu ứng của việc giãn độ tương phản và cân bằng biểu đồ tần số đối với một tấm ảnh tiêu chuẩn. Cách cân bằng hóa biểu đồ tần số cũng có thể áp dụng được cho một vùng ảnh.

Hình 21. Trái, (a) Ảnh gốc. Giữa, (b) Giãn độ tương phản. Phải, (c) Cân bằng biểu đồ tần số.

Các phép toán khác dựa trên biểu đồ tần số

Biểu đồ tần số của một vùng ảnh có thể được dùng để điều khiển các bộ lọc dùng riêng cho vùng đó. Các ví dụ gồm có lọc cực tiểu, lọc trung vị và lọc cực đại.1 các khái niệm cực tiểu, trung vị và cực đại đã được giới thiệu ở Hình 6. Những bộ lọc dựa trên các khái niệm này sẽ được trình bày có hệ thống ở các Mục 9.4.2 và 9.6.10.

Toán tử dựa trên số học

Trong mục này ta phân biệt giữa số học trên hệ nhị phân và số học thông thường. Với trường hợp nhị phân, có hai giá trị độ sáng “0” và “1”. Với trường hợp thông thường ta bắt đầu bằng 2B giá trị hay cấp độ sáng nhưng việc xử lý ảnh có thể phát sinh ra nhiều cấp nữa. Vì vậy, nhiêu phần mềm cho phép biểu diễn 16-bit hoặc 32-bit độ sáng điểm ảnh để tránh vấn đề tràn số.

Phép toán nhị phân

Các toán tử dựa trên số học nhị phân (Boole) hình thành nên cơ sở cho một bộ công cụ mà ta sẽ trình bày ở đây và sâu hơn ở Mục 9.6, hình thái toán học. Các toán tử liệt kê phía dưới là những toán tử tính theo điểm và vì vậy có nhiều cách thực hiện, bao gồm cả việc tra bảng. Những kí hiệu tiêu chuẩn cho tập hợp cơ bản các phép tính nhị phân là:

$latex \begin{array}{ll}
NOT & c = \bar{a} \\
OR & c = a + b \\
AND & c = a \cdot b \\
XOR & c = a \oplus b = a\cdot \bar{b} + \bar{a} \cdot b \\
SUB \quad & c = a \backslash b = a – b = a \cdot \bar{b}
\end{array}$

Ở đây ta ngầm hiểu rằng mỗi phép toán được thực hiện trên cơ sở từng điểm ảnh một. Chẳng hạn, c[m, n] = a[m, n] ⋅ [m, n] ∀ m, n. Định nghĩa của từng phép toán là:

 (82)

Các phép toán này được minh họa trên Hình 22 trong đó các giá trị “1” có màu đen và “0” có màu trắng.

Hình 22. Ví dụ về các phép toán theo điểm nhị phân.

Phép toán SUB( ⋅ ) có thể sẽ rất có ích khi ảnh a biểu diễn một vùng mà ta cần phân tích một cách có hệ thống còn ảnh b biểu diễn các đối tượng mà đã phân tích rồi, và bây giờ có thể bỏ đi. Các đối tượng này sẽ bị trừ đi từ vùng ảnh.

Phép toán số học

Các phép toán theo điểm trên thang độ sáng hình thành nên cơ sở của xử lý ảnh đều dựa trên toán số học thông thường; chúng bao gồm

Phép toán
Định nghĩa KIểu dữ liệu thông dụng
ADD c = a + b số nguyên
SUB c = a − b số nguyên
MUL c = a • b số nguyên hoặc phẩy động
DIV c = a / b phẩy động2
LOG c = log(a) phẩy động
EXP c = exp(a) phẩy động
SQRT  c = √a
phẩy động
TRIG c = sin / cos / tan(a)
phẩy động
INVERT3 c = (2B − 1) − a số nguyên

(83)

Các phép toán dựa trên tích chập

Tích chập, phép toán địa phương được miêu tả ở Mục 3.1, đóng vai trò trung tâm của xử lý ảnh hiện đại. Ý tưởng cơ bản là một khung có hình dạng và kích thước hữu hạn, gọi là giá (support), được quét qua ảnh. Giá trị của điểm ảnh đầu ra sẽ bằng trung bình trọng số của các điểm ảnh đầu vào trong khung này, với trọng số là giá trị của các giá trị lọc được gán cho mỗi điểm ảnh thuộc về khung. Một tấm khung như vậy cùng với các trọng số được gọi là nhân của tích chập. Điều này trực tiếp dẫn tới công thức biến thể của PT (3). Nếu lọc h[j, k] bằng 0 bên ngoài khung (là hình chữ nhật có kích thước J × K là số lẻ) bao quanh điểm gốc {j =  − J0,  − J0 + 1, …,  − 1, 0, 1, …, J0 − 1, J0, k =  − K0,  − K0 + 1, …,  − 1, 0, 1, …, K0 − 1, K0} thì bằng PT (4), tích chập có thể được viết lại theo dạng tổng hữu hạn như sau:

c[m, n] = a[m, n] ⊗ h[m, n] = ∑ j=−J0J0 ∑ k=−K0K0  h[j, k] a[m − j, n − k]

Có thể coi phương trình này hơn cả một cơ chế mẫu làm nhòe hoặc làm nét hình ảnh. Ngoài ra, PT (84) còn minh họa tính chất địa phương của phép toán này, các PT (10) và (24) khẳng định rằng phép toán có thể được thực hiện bằng cách dùng miền Fourier vốn đòi hỏi một phép tính toàn cục: phép biến đổi Fourier. Cả hai khía cạnh này sẽ được thảo luận ngay sau đây.

Kiến thức cơ bản

Trong nhiều hệ tạo ảnh, một mô hình thích hợp cho việc chuyển đổi tín hiệu vật lý a(x, y) sang tín hiệu điện tử c(x, y) là tích chập của tín hiệu đầu vào với phản hồi xung của hệ thống đầu đo. Hệ thống này có thể bao gồm quang hệ lẫn hệ thống điện. Nếu mỗi hệ nhỏ trên có thể được coi là tuyến tính, bất biến đối với chuyển dịch (linear, shift-invariant, LSI) thì mô hình tích chập là phù hợp. Các định nghĩa của hai đặc tính hệ được cho như sau:

Tuyến tính—

Nếu a1 → c1a2 → c2
Thì w1 ⋅ a1 + w2 ⋅ a2 → w1 ⋅ c1 + w2 ⋅ c2

(85)

Bất biến với dịch chuyển—

Nếu a(x, y) → c(x, y)
Thì a(x − x0, y − y0) → c(x − x0, y − y0)

(86)

trong đó w1w2 là các hằng số phức bất kì còn x0y0 là các tọa độ tương ứng với các phép tịnh tiến không gian bất kì.

Đến đây ta có hai nhận xét. Thứ nhất, bản chất tuyến tính ngụ ý (bằng cách chọn w1 = w2 = 0) rằng “đầu vào bằng 0” sẽ cho “đầu ra bằng 0”. Lượng offset ở PT (70) nghĩa là những tín hiệu máy ảnh như vậy không phải là đầu ra của một hệ tuyến tính và do đó (nó chặt chẽ thì) kết quả tích chập không áp dụng được. Thật may là, có thể dễ dàng sửa chữa hiệu ứng phi tuyến này. (Xem Mục 10.1.)

Thứ hai, các thấu kính quang học có độ phóng đại, M khác 1 ×  đều không bất biến đối với dịch chuyển; một sự dịch chuyển bằng 1 đơn vị trên ảnh đầu vào a(x, y) sẽ gây ra dịch chuyển M đơn vị trên ảnh đầu ra c(x, y). Do đặc tính Fourier miêu tả ở PT (25) trường hợp này vẫn có thể tính được bằng lý thuyết hệ tuyến tính.

Nếu một điểm sáng δ(x, y) dạng xung được ghi lại trên hệ thống LSI thì phản hồi xung của hệ thống đó được gọi là hàm rải điểm (point spread function, PSF). Ảnh đầu ra khi đó sẽ trở thành tích chập của ảnh đầu với PSF. Biến đổi Fourier của PSF được gọi là hàm truyền quang (optical transfer function, OTF). Với các quang hệ có dạng đối xứng vòng, không có quang sai, và nhiễu xạ hữu hạn, thì PSF được cho bởi đĩa Airy như trên Bảng 4–T.5. OTF của đĩa Airy cũng được trình bày trên Bảng 4–T.5. [Bảng 4 ở Chương 3]

Nếu khung tích chập không phải là PSF có nhiễu xạ hữu hạn của thấu kính mà là hiệu ứng từ sự chệch tiêu cự (defocus) của thấu kính thì một mô hình phù hợp cho h(x, y) là một trụ tròn bán kính a như trên Bảng 4–T.3. Hiệu ứng của một mẫu kiểm tra được minh họa trên Hình 23.

a) Mẫu kiểm tra                        b) Ảnh có hiệu ứng chệch tiêu cự

Hình 23: Tích chập của một mẫu kiểm tra với mô trình trụ có bán kính a = 4. 5 điểm ảnh.

HIệu ứng của chệch tiêu cự không chỉ giới hạn ở hiện tượng ảnh bị mờ hoặc “làm trơn”. Các chỗ lõm âm gần như tuần hoàn của hàm truyền trên Bảng 4–T.3 tạo ra một sự chuyển pha 180° theo đó màu đen chuyển thành màu trắng và ngược lại. Có thể dễ dàng thấy được chuyển pha trên Hình 23b.

Tích chập trên miền không gian

Để miêu tả các bộ lọc dựa trên tích chập ta dùng quy ước sau. Cho trước một bộ lọc h[j, k] với kích thước J × K = 2J0 + 1 × 2K0 + 1, ta sẽ xét tọa độ [j = 0, k = 0] nằm ở tâm ma trận lọc, h. Điều này được minh họa trên Hình 24. Điểm “tâm” được xác định rõ khi kích thước bộ lọc là số lẻ.

$latex
\textbf{h} = \left[ \begin{array}{ccccccc}
h[-J_0, -K_0] & \dots & \dots & h[0,-K_0] & \dots & \dots & h[J,-K_0] \\
\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
\vdots & \dots & h[-1,-1] & h[0,-1] & h[1,-1] & \dots & \vdots \\
h[-J_0, 0] & \dots & h[-1,0] & h[0,0] & h[1,0] & \dots & h[J_0, 0] \\
\vdots & \dots & h[-1,1] & h[0,1] & h[1,1] & \dots & \vdots \\
\vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
h[-J_0, K_0] & \dots & \dots & h[0,K_0] & \dots & \dots & h[J_0,K_0] \\
\end{array} \right] $

Hình 24: Hệ tọa độ mô tả h[j, k]

Khi ta xem kĩ lưỡng tổng trong tích chập (PT (84)), một số vấn đề trở nên rõ ràng.

 •  Việc định giá công thức (84) với m = n = 0 trong khi viết lại giới hạn của tổng tích chập dựa trên cách chọn “tâm” là h[j, k] cho thấy rằng các giá trị a[j, k] có thể cần đến lại nằm ngoài biên của ảnh:

c[0, 0] = ∑ j=−J0+J0 ∑ k=−K0+K0 h[j, k] a[ − j,  − k]

Câu hỏi đặt ra là—ta nên gán những giá trị nào cho ảnh a[m, n] với m < 0, m ≥ M, n < 0, và n ≥ N? Không có “đáp án” nào cho câu hỏi này. Chỉ có những cách khác nhau mà ta có quyền lựa chọn, với giả sử rằng ta hiểu được hệ quả từ việc lựa chọn của mình. Những phương án tiêu chuẩn gồm có a) mở rộng hình ảnh với điểm ảnh có giá trị độ sáng đều (có thể bằng 0), b) mở rộng hình ảnh tuần hoàn, c) mở rộng hình ảnh bằng cách lấy đối xứng gương qua các đường biên, hoặc d) mở rộng bằng các giữ nguyên mãi các giá trị biên. Những phương án này được minh họa trên Hình 25.

Hình 25: Ví dụ các phương án khác nhau để mở rộng hình ảnh ra khỏi phạm vi chính thức của nó. Xem đoạn diễn giải ở trên.

 •  Khi tổng trong tích chập được viết dưới dạng tiêu chuẩn (PT (3)) với một ảnh a[m, n] có kích thước M × N:

c[m, n] = ∑ j=0M−1 ∑ k=0N−1 a[j, k] h[m − j, n − k]

ta thấy rằng phần nhân của tích chập h[j, k] được đối xứng qua điểm j = k = 0 để tạo ra h[−j,  −k] trước khi nó được tịnh tiến đi [m, n] như được chỉ ra ở PT (88). Trong khi một số nhân của tích chập thường dùng, trên phương diện này, có dạng đối xứng, h[j, k] = h[−j, −k], song nhiều nhân thì không. (Xem Mục 9.5.) Do đó cần phải cẩn thận khi thực hiện lập các bộ lọc có yêu cầu đối xứng.

 •  Độ phức tạp tính toán đối với một nhân J × K của tích chập được lập trên miền không gian của ảnh kích thước N × NO(J ⋅ K) trong đó độ phức tạp được đo theo từng điểm ảnh trên cơ sở số lần phép tính nhân và cộng (multiplies-and-adds, MADDs).

 •  Giá trị được tính bằng một tích chập từ độ sáng là số nguyên cho a[m, n] có thể tạo ra kết quả là số hữu tỉ hoặc số có dấu chấm động c[m, n]. Do đó, việc chỉ tính với các giá trị độ sáng số nguyên sẽ gây ra lỗi làm tròn.

 •  Xét kĩ PT (84) cho thấy một khả năng khác để thực hiện tính tích chập. Nếu tích chập có nhân h[j, k] phân ly được, nghĩa là nếu nhân có thể được viết thành:

h[j, k] = hrow[k] • hcol[j]

thì bộ lọc có thể được thực hiện như sau:

c[m, n] = ∑ j=−J0J0 {∑ k=−K0K0 hrow[k] a[m − j, n − k]} hcol[j]

Điều này nghĩa là thay vì áp dụng một bộ lọc hai chiều, ta có thể áp dụng hai bộ lọc một chiều, bộ lọc thứ nhất theo hướng k và bộ lọc thứ hai theo hướng j. Với ảnh N × N thì điều này nói chung sẽ làm giảm độ phức tạp tính toán đối với mỗi điểm ảnh, từ O(J ⋅ K) xuống còn O(J + K).

Một cách viết phân ly khác là lưu ý rằng nhân của tích chập (Hình 24) là ma trận h và, nếu phân ly được, h có thể được viết thành:

[h] = [hcol] • [hrow]t

(J × K) = (J × 1) • (1 × K)

trong đó “t” dùng để chỉ phép chuyển vị ma trận. Nói cách khác, h có thể được diễn đạt bởi tích ngoài của một véc-tơ cột [hcol] với một véc-tơ hàng [hrow].

 •  Với những bộ lọc nhất định, ta có thể tìm thấy một dạng thực hiện tăng dần của một tích chập. Khi khung tích chập di chuyển qua ảnh (xem PT (88)), cột bên trái nhất của ảnh bên dưới khung được chuyển ra khi mà một cột mới của ảnh được đưa vào khung từ phía bên phải. Những thuật toán hiệu quả có thể lợi dụng được điều này4 và, khi được kết hợp với những bộ lọc phân ly được như đề cập ở trên, điều này có thể dẫn đến những thuật toán với độ phức tạp tính toán trên mỗi điểm ảnh là O(hằng số).

Tích chập trên miền tần số

Trong Mục 3.4 chúng ta đã nhận định rằng một phương pháp khác để thực hiện lọc ảnh thông qua tích chập. Dựa trên PT (24) có vẻ là ta đạt được kết quả giống như ở PT (84) bằng chuỗi phép tính sau:

i) Tính A(Ω , Ψ) = F{a[m, n]}
ii) Nhân A(Ω , Ψ) với đại lượng đã tính từ trước H(Ω , Ψ) = F{h[m, n]}                     (92)
iii) Tính kết quả c[m, n] = F − 1A(Ω , Ψ) • H(Ω , Ψ)

 •  Trong khi có vẻ như trình tự tính toán trên, PT (92) khéo léo tránh được vấn đề gắn với tích chập trực tiếp trên miền không gian—cụ thể là, xác định các giá trị trên ảnh từ bên ngoài các đường biên của ảnh đó. Thật ra, phương pháp miền Fourier chỉ cần “giả sử” rằng ảnh được lặp lại tuần hoàn bên ngoài các đường biên của nó, như được minh họa trên Hình 25b. Cách này được gọi là tích chập vòng. Nếu tích chập vòng không chấp nhận được thì các khả năng khác trên Hình 25 có thể được thực hiện bằng cách đặt ảnh a[m, n] và bộ lọc H(Ω , Ψ) trong những ma trận lớn hơn rồi thực hiện cơ chế mở rộng ảnh mong muốn cho ảnh a[m, n] một cách rõ ràng.

 •  Độ phức tạp tính toán trên mỗi điểm ảnh trong phương pháp Fourier đối với ảnh N × N và tích chập có nhân K × KO(log2N) MADD phức độc lập với K. Ở đây ta đã giả sử rằng N > K, và N là một hợp số có nhiều ước, chẳng hạn như lũy thừa của 2. (Xem thêm Mục 2.1.) Giả thiết thứ hai cho phép ta áp dụng thuật toán hiệu quả có tên Biến đổi Fourier nhanh (Fast Fourier Transform, FFT). Điều ngạc nhiên là con đường gián tiếp dẫn bởi PT (92) có thể còn nhanh hơn con đường trực tiếp theo PT (84). Nói chung, điều này yêu cầu rằng K2 ≫ log2N. Khoảng của KN mà điều nói trên còn đúng thì phụ thuộc vào chi tiết cụ thể từng cách thực hiện. Đối với máy tính và với gói phần mềm xử lý số liệu của các tác giả viết tài liệu này, với ảnh có N = 256, phương pháp Fourier nhanh hơn phương pháp tích chập khi K ≥ 15. (Cần lưu ý rằng trong phép so sánh này tích chập trực tiếp chỉ bao gồm phép tính đối với số nguyên còn phương pháp miền Fourier yêu cầu tính số phức có chứa dấu chấm động.)


  1. 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.
  2. Nói nôm na là số có phần thập phân
  3. Phép đảo màu
  4. Groen, F.C.A., R.J. Ekkers, and R. De Vries, Image processing with personal computers. Signal Processing, 1988. 15: p. 279-291
Advertisements

2 phản hồi

Filed under Cơ sở

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

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

  2. Pingback: Chương 10: Các kĩ thuật xử lý (Phần 1) | 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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s