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

Trở lại Mục lục cuốn sách

9.6 Các phép toán dựa trên hình thái ảnh

Ở Chương 1 ta đã định nghĩa ảnh như một hàm (biên độ) của hai biến (tọa độ) số thực a(x, y) hoặc hai biến rời rạc, a[m, n]. Một cách định nghĩa ảnh khác có thể dựa trên khái niệm rằng ảnh bao gồm một tập hợp các tọa độ, hoặc là liên tục hoặc rời rạc. Theo nghĩa này, tập hợp thì tương ứng với các điểm hoặc điểm ảnh nằm trong các vật thuộc ảnh. Điều này được minh họa trên Hình 35, ở đây ảnh gồm hai vật, hay hai tập hợp AB. Lưu ý rằng bắt buộc phải có hệ tọa độ. Tạm thời bây giờ ta chỉ xét những giá trị điểm ảnh nhị phân như đã đề cập đến ở các Mục 2.1 và 9.2.1. Hơn nữa, ta chỉ giới hạn thảo luận trong không gian rời rạc (Z2). Những phân tích tổng quát hơn có thể được tìm thấy trong1 2 3

Hình 35: Một ảnh nhị phân gồm hai tập hợp AB tương ứng hai vật.

Vật A gồm các điểm ảnh α có chung thuộc tính nào đó:

Vật –   A = {α ∣ thuộc tính(α) == TRUE}       (123)

Ví dụ, vật B trên Hình 35 chứa {[0,0], [1,0], [0,1]}.

Nền của A được cho bởi Ac (phần bù của A) và được định nghĩa là những phần tử không thuộc vào A:

Nền –     Ac = {αα ∉ A}         (124)

Trên Hình 3 ta giới thiệu khái niệm về liền kề. Bây giờ chúng ta hãy quan sát để thấy rằng nếu một vật A được định nghĩa trên cơ sở liên thông–C (C = 4, 6, hoặc 8) thì nền Ac sẽ có độ liên thông là 12 − C. Mấu chốt của điều này được minh họa trên lưới tọa độ Đề-các ở Hình 36.

Hình 36: Một ảnh nhị phân yêu cầu định nghĩa cẩn thận khái niệm vật cùng với độ liên thông của nền.

9.6.1 Những định nghĩa cơ bản

Các phép toán cơ bản đối với vật là phép tính với tập hợp hợp, giao, { ∪ ,  ∩ , c}tịnh tiến:

 •  Tịnh tiến – Cho một véc-tơ x và một tập hợp A. Phép tịnh tiến, A + x, được định nghĩa là:

A + x = {α + xα ∈ A}       (125)

Lưu ý rằng, vì ta đang thao tác trên ảnh số hợp thành từ nhiều điểm ảnh có các tọa độ nguyên (Z2), điều này gây nên ràng buộc về véc-tơ tịnh tiến x.

Các phép toán Minkowski đối với tập hợp cơ bản—cộng và trừ—bây giờ có thể được định nghĩa. Trước hết, ta lưu ý rằng những phần tử riêng rẽ hợp thành B không chỉ là điểm ảnh mà còn là véc-tơ vì chúng có một tọa độ rõ ràng so với [0,0]. Cho trước hai tập hợp AB:

Phép cộng Minkowski –     A ⊕ B =  ∪βB (A + β)      (126)

Phép trừ Minkowski –       A ⊖ B =  ∩βB (A + β)      (127)

9.6.2 Các phép giãn nở và bào mòn

Từ hai phép toán Minkowski nói trên ta định nghĩa các phép toán hình thái cơ bản, đó là giãn nở (dilation) và bào mòn (erosion):

Giãn nở –     D(A, B) = A ⊕ B =  ∪βB (A + β)         (128)

Bào mòn –     E(\textbf{A}, \textbf{B}) = \textbf{A} \ominus \tilde{\textbf{B}} =  \cap_{\beta \in \textbf{B}} (\textbf{A} + \beta)        (129)

trong đó \tilde{\textbf{B}} = \{ -\beta | \beta \in \textbf{B} \} . Hai phép toán này được minh họa trên Hình 37 khi áp dụng cho các vật ở Hình 35.

(a) Giãn nở D(A, B)           (b) bào mòn E(A, B)

Hình 37: Ảnh nhị phân gồm hai tập hợp vật thể AB. Ba điểm ảnh trên B được “mã hóa màu” cũng như ảnh hưởng của chúng đến kết quả.

Dù tập hợp A hoặc B đều có thể được coi như là “ảnh” song A thường được coi là ảnh còn B được gọi là phần tử cấu trúc (structuring element). Phần tử cấu trúc đối với hình thái toán học thì cũng như nhân của tích chập đối với lý thuyết lọc tuyến tính.

Phép giãn nở nói chung sẽ làm các vật tăng kích thước, lớn lên; bào mòn làm các vật co lại. Lượng và cách làm tăng hoặc giảm kích thước thì tùy thuộc vào sự lựa chọn phần tử cấu trúc. Làm giãn nở hoặc bào mòn mà không chỉ định phần tử cấu trúc thì chẳng có nghĩa lý gì, cũng như ý định lọc thông thấp một hình ảnh mà không chỉ định bộ lọc. Hai phần tử cấu trúc thông dụng nhất trên lưới Đề-các là các tập liên thông-4 và liên thông-8, N4N8. Chúng được minh họa trên Hình 38.

(a) N4           (b) N8

Hình 38: Các phần tử cấu trúc tiêu chuẩn, N4N8.

Các phép giãn nởbào mòn có những thuộc tính sau:

Giao hoán –   D(A, B) = A ⊕ B = B ⊕ A = D(B, A)    (130)

Phi giao hoán –    E(A, B) ≠ E(B, A)     (131)

Kết hợp –     A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C   (132)

Bất biến với tịnh tiến –    A ⊕ (B + x) = (A ⊕ B) + x    (133)

Đối ngẫu –      D^c (\textbf{A}, \textbf{B}) = E (\textbf{A}^c, \tilde{\textbf{B}}) (134) E^c (\textbf{A}, \textbf{B}) = D (\textbf{A}^c, \tilde{\textbf{B}})

Với A là vật và Ac là nền, PT (134) phát biểu rằng phép giãn nở đối với vật thì tương đương với phép bào mòn đối với nền. Tương tự, phép bào mòn đối với vật tương đương với phép giãn nở đối với nền.

Trừ những trường hợp đặc biệt:

Không đảo ngược –      D(E(A, B), B) ≠ A ≠ E(D(A, B), B)       (135)

Phép bào mòn có thuộc tính tịnh tiến sau:

Bất biến với tịnh tiến –        A ⊖ (B + x) = (A + x) ⊖ B = (A ⊖ B) + x        (136)

Giãn nởbào mòn có các thuộc tính quan trọng sau. Với một phần tử cấu trúc B bất kì và hai vật A1A2 sao cho A1 ⊂ A2 (A1 là tập con đích thực của A2):

Tăng theo A–        D(A1, B) ⊂ D(A2, B)     (137)
                                E(A1, B) ⊂ E(A2, B)

Với hai phần tử cấu trúc B1B2 sao cho B1 ⊂ B2:

Giảm theo B–            E(A, B1) ⊃ E(A, B2)    (138)

Định lý phân tách dưới đây cho phép tìm được các hiệu quả để lập các bộ lọc hình thái.

Giãn nở –     A ⊕ (B ∪ C) = (A ⊕ B) ∪ (A ⊕ C) = (B ∪ C) ⊕ A   (139)

Bào mòn –    A ⊖ (B ∪ C) = (A ⊖ B) ∪ (A ⊖ C)     (140)

Bào mòn –     (A ⊖ B) ⊖ C = A ⊖ (B ⊕ C)    (141)

Giãn nở nhiều lần –       n\textbf{B} =  \underbrace{(B \oplus B \oplus B \oplus \cdots \oplus B)}_{n \text{ l\^{a}\`{n}}}      (142)

Một định lý phân tách quan trọng được Vincent4 đề nghị. Đầu tiên, ta phải đưa ra một số định nghĩa. Một tập hợp lồi (trong không gian R2) là tập hợp trong đó một đoạn thẳng nối giữa hai điểm bất kì trong tập hợp sẽ gồm các điểm cũng thuộc tập hợp. Hiển nhiên là phải thận trọng khi áp dụng định nghĩa này cho các điểm ảnh rời rạc, vì khá niệm “đoạn thẳng” phải được hiểu một cách phù hợp trong Z2. Một tập hợp được gọi là bị chặn nếu mỗi phần tử của nó có một biên độ hữu hạn, trong trường hợp này là khoảng cách đến gốc tọa độ. Một tập hợp được gọi là đối xứng nếu \textbf{B} = \tilde{\textbf{B}}. Các tập hợp N4N8 trên Hình 38 là các ví dụ cho tập lồi, bị chặn và đối xứng.

Định lý Vincent, khi áp dụng cho ảnh gồm các điểm ảnh rời rạc, phát biểu rằng với một phần tử cấu trúc B đối xứng, bị chặn, không chứa lỗ hổng và chứa tâm của bản thân nó, [0, 0] ∈ B thì:

D(A, B) = A ⊕ B = A ∪ (∂A ⊕ B)

trong đó A là viền của vật thể. Điều này nghĩa là, A là tập hợp các điểm ảnh liền kề với điểm ảnh trên nền. Ý nghĩa của định lý này là ta không cần phải xử lý tất cả những điểm ảnh trên một vật thể để tính toán giãn nở (dùng PT (134)) hoặc bào mòn. Ta chỉ cần xử lý các điểm ảnh trên viền. Điều này cũng đúng với các phép toán suy diễn từ giãn nởbào mòn. Quá trình xử lý các điểm ảnh ở biên thay vì điểm ảnh trên vật thể có nghĩa là, trừ những ảnh kì dị (pathological) ra, độ phức tạp tính toán có thể được giảm từ O(N2) xuống còn O(N) với ảnh N × N. Một số thuật toán “nhanh” dựa trên kết quả này có thể tìm được trong tài liệu.5 6 7 Các thuật toán giãn nở và bào mòn đơn giản nhất thường được mô tả như sau.

 •  Giãn nở – Lấy ra mỗi điểm ảnh nhị phân thuộc vật thể (có giá trị “1”) và chuyển tất cả điểm ảnh thuộc nền (từ giá trị “0”) có liên thông-C đến điểm ảnh thuộc vật thể đó thành giá trị “1”.

 •  Bào mòn – Lấy ra mỗi điểm ảnh nhị phân thuộc vật thể (có giá trị “1”) có liên thông-C đến điểm ảnh thuộc nền và chuyển giá trị điểm ảnh thuộc vật thể thành “0”.

So sánh hai thủ tục này với PT (143) trong đó B = NC = 4 hoặc NC = 8, ta thấy được chúng tương đương với định nghĩa chính thức về giãn nở và bào mòn. Thủ tục này được minh họa cho trường hợp giãn nở trên Hình 39.

(a) B = N4             (b) B = N8

Hình 39: Minh họa cho phép giãn nở. Các điểm vật ban đầu có màu xám. Các điểm được thêm vào trong quá trình giãn nở được tô màu đen.

9.6.3 Tích chập Boole

Một vật (hay phần tử cấu trúc) nhị phân A bất kì có thể được biểu diễn bởi:

A ↔ ∑ k=−∞+∞ ∑ j=−∞+∞ a[j, k] • δ[m − j, n − k]

trong đó ∑  •  là các toán tử Boole OR và AND, như đã định nghĩa ở các PT (81) và (82), a[j, k] là một hàm đặc tính nhận vào các giá trị Boolean “1” và “0” như sau:

a[j,k] = \left\{ \begin{array}{cc}  1 & a \in \textbf{A} \\  0 & a \notin \textbf{A} \\  \end{array} \right.

δ[m, n] là một dạng Boole của hàm delta Dirac nhận vào các giá trị Boole “1” và “0” như sau:

\delta[j,k] = \left\{ \begin{array}{cc}  1 & j = k = 0 \\  0 & \text{tru\`{o}ng hop c\`{o}n la.i} \\  \end{array} \right.

Từ đó, phép giãn nở với các ảnh nhị phân có thể được viết thành:

D(A, B) = ∑ k=−∞+∞ ∑ j=−∞+∞ a[j, k] • b[m − j, n − k] = a ⊗ b    (147)

và vì các toán tử Boole OR và AND đều có tính giao hoán, mà ta lại có thể viết thành:

D(A, B) = ∑ k=− ∞+∞∑ j=−∞+∞ a[m − j, n − k] • b[j, k] = b ⊗ a = D(B, A)

Dùng định lý De Morgan:

\overline{(a+b)} = \overline{a} \bullet \overline{b} \quad \text{v\`a} \quad  \overline{(a \bullet b)} = \overline{a} + \overline{b}      (149)

đối với PT (148) cùng PT (134), phép bào mòn có thể được viết thành:

E(\textbf{A},\textbf{B}) = \prod_{k=-\infty}^{+\infty} \prod_{j=-\infty}^{+\infty}  \left( a[m-j,n-k] + \overline{b}[-j,-k]\right)

Như vậy, các phép giãn nởbào mòn đối với ảnh nhị phân có thể được xem như là một dạng tích chập với đại số Boole.

Ở Mục 9.3.2 ta đã thấy rằng, khi áp dụng tích chập, nhất thiết phải có một lựa chọn phù hợp cho điều kiện biên của ảnh; giãn nở và bào mòn—tích chập dạng Boole—cũng không phải ngoại lệ. Hai lựa chọn thông dụng nhất bao gồm: mọi thứ bên ngoài ảnh nhị phân đều là “0”, hoặc mọi thứ bên ngoài ảnh nhị phân đều là “1”.

9.6.4 Mở và Đóng

Ta có thể kết hợp giãn nởbào mòn lại để tạo ra hai phép toán cao cấp quan trọng sau:

Mở–     O(A, B) = A ∘ B = D(E(A, B), B)    (151)

Đóng–    C(\textbf{A},\textbf{B}) = \textbf{A} \bullet \textbf{B}= E(D(\textbf{A},\tilde{\textbf{B}}),\tilde{\textbf{B}})      (152)

Các phép mởđóng có những thuộc tính sau:

Đối ngẫu –    Cc(A, B) = O(Ac, B)    (153)
                       Oc(A, B) = C(Ac, B)

Tịnh tiến –    O(A + x, B) = O(A, B) + x    (154)
                       C(A + x, B) = C(A, B) + x

Đối với phép mở có phần tử cấu trúc B và các ảnh A, A1, và A2, trong đó A1 là ảnh con của A2 (A1 ⊆ A2):

Tính phi mở rộng –       O(A, B) ⊆ A              (155)

Đơn điệu tăng –      O(A1, B) ⊆ O(A2, B)        (156)

Đồng nhất –       O(O(A, B), B) = O(A, B)       (157)

Đối với phép đóng có phần tử cấu trúc B và các ảnh A, A1, và A2, trong đó A1 là ảnh con của A2 (A1 ⊆ A2):

Tính mở rộng –         A ⊆ C(A, B)        (158)

Đơn điệu tăng –       C(A1, B) ⊆ C(A2, B)      (159)

Đồng nhất –           C(C(A, B), B) = C(A, B)      (160)

Hai thuộc tính cho bởi các PT (155) và (84) quan trọng đối với hình thái toán học đến mức chúng có thể được xem là lý do để định nghĩa bào mòn với \tilde{\textbf{B}} thay vì B trong PT (129).

9.6.5 Phép Hit–and–Miss

Toán tử hit-or-miss được định nghĩa bởi Serra, nhưng ta sẽ gọi nó bằng cái tên hit-and-miss và được định nghĩa như sau. Cho một ảnh A cùng hai phần tử cấu trúc B1B2, các định nghĩa tập hợp và định nghĩa Boole gồm có:

Hit-and-Miss –    HitMiss (\textbf{A},\textbf{B}_1,\textbf{B}_2) = \left\{  \begin{array}{c}  E(\textbf{A},\textbf{B}_1) \cap E(\textbf{A}^c,\textbf{B}_2) \\  E(\textbf{A},\textbf{B}_1) \bullet E(\overline{\textbf{A}},\textbf{B}_2)  \end{array} \right.          (161)

trong đó B1B2 là các phàn tử cáu trúc biệt lập, bị chặn. Lưu ý cách dùng kí hiệu từ PT (81).) Hai tập hợp được gọi là biệt lập nếu B1 ∩ B2 = Ø, tập hợp rỗng. Theo ý nghĩa quan trọng, toán tử hit-and-miss là dạng tương đương về mặt hình thái của khớp mẫu, một kĩ thuật nổi tiếng để khớp các mẫu ảnh dựa trên tương quan chéo. Ở đây, ta có một mẫu B1 dùng cho vật và mẫu B2 dùng cho nền.

9.6.6 Tóm tắt những phép toán cơ bản

Kết quả của việc áp dụng những toán tử cơ bản nói trên đối với tấm ảnh kiểm tra sẽ được minh họa như sau. Trong Hình 40 có định nghĩa các phần tử cấu trúc khác nhau dùng để xử lý ảnh. Giá trị “–” biểu thị cho “không cần quan tâm”. Cả ba phần tử cấu trúc này đều có dạng đối xứng.

\textbf{B} = \textbf{N}_8 = \left[ \begin{array}{ccc}  1 & 1 & 1\\  1 & 1 & 1\\  1 & 1 & 1\\  \end{array} \right]  \quad  \textbf{B}_1 = \left[ \begin{array}{ccc}  - & - & -\\  - & 1 & -\\  - & - & -\\  \end{array} \right]  \quad  \textbf{B}_2 = \left[ \begin{array}{ccc}  - & 1 & -\\  1 & - & 1\\  - & 1 & -\\  \end{array} \right]
.                  (a)                                   (b)                                       (c)

Hình 40: Các phần tử cấu trúc B, B1, và B2 có kích thước 3 × 3 và đối xứng.

Kết quả của việc xử lý được cho thấy ở Hình 41 trong đó các giá trị nhị phân “1” được tô màu đen, còn “0” tô màu trắng.

a) Ảnh A                      b) giãn nở với 2B                c) bào mòn với 2B

           d) Mở với 2B              e) Đóng với 2B          f) Đường viền 8-c: A–E(A,N8)

Hình 41: Ví dụ về các phép toán hình thái khác nhau.

Phép toán mở có thể tách rời các vật vốn được nối với nhau trên ảnh nhị phân. Phép toán đóng có thể lấp đầy những lỗ hổng nhỏ. Cả hai phép toán đều làm làm trơn đường viền vật thể ở mức nhất định, kh cho trước một phần tử cấu trúc “trơn”. Phép mở làm trơn từ phía trong đường viền vật thể, còn phép đóng làm trơn từ phía ngoài viền. Ví dụ hit-and-miss này đã tìm thấy các điểm ảnh trên viền có liên thông-4. Một phương pháp khác tìm đường viền đơn giản là dùng hệ thức:

Đường viền liên thông-4 –        A = A − E(A, N8)        (162)

hoặc

Đường viền liên thông-8 –       A = A − E(A, N4)       (163)

9.6.7 Bộ khung

Có thể định nghĩa nôm na bộ khung là một biểu diễn dạng đường thẳng cho một vật thể:

i) có độ dày bằng 1 điểm ảnh,
ii) đi qua “tâm” của vật thể, và,             (164)
iii) giữ nguyên cấu trúc tô-pô của vật thể.

Những điều này không phải lúc nào cũng thực hiện được. Hình 42 cho ta thấy tại sao.

(a)                                      (b)

Hình 42: Các phản ví dụ cho ba yêu cầu nêu trên.

Ở ví dụ thứ nhất, Hình 42a, không thể phát sinh được một đường thẳng chỉ dày 1 điểm ảnh và ở tâm vật thể đồng thời cũng phát sinh một đường phản ánh được sự đơn giản của vật. Trên Hình 42b, không thể xóa bớt một điểm ảnh từ vật liên thông-8 đồng thời bảo tồn được tô-pô—đặc trưng biểu thị tính liên thông—của vật. Dù sao, đã có những kĩ thuật nhằm đạt mục đích này và tạo ra bộ khung.

Một công thức đơn giản được dựa trên nghiên cứu của Lantuéjoul.8 Tập con của khung Sk(A) được định nghĩa như sau:

Tập con của khung –          Sk(A) = E(A, kB) − [E(A, kB) ∘ B] k = 0, 1, …, K        (165)

trong đó K là giá trị lớn nhất của k trước khi tập hợp Sk(A) trở nên rỗng. (Từ PT (156), E(A, kB) ∘ B ⊆ E(A, kB) .) Phần tử cấu trúc B được chọn (trên Z2) để xấp xỉ một đĩa tròn, nghĩa là có dạng lồi, bị chặn, và đối xứng. Khi đó, bộ khung là hợp các tập con của khung:

Bộ khung –           S(A) = ⋃k=0K Sk(A)       (166)

Một hiệu ứng phụ tinh tế trong công thức này là đối tượng gốc có thể được tái tạo khi biết trước thông tin về các tập con của khung Sk(A), phần tử cấu trúc B, và K:

Tái tạo –         A = ⋃k=0K (Sk(A) ⊕ kB)       (167)

Tuy nhiên công thức tính bộ khung này không giữ được tô-pô, một yêu cầu đã nêu ở (164).

Một quan điểm khác là thực hiện làm mỏng, một cách bào mòn để giảm độ dày của một đối tượng mà không cho phép nó biến mất. Một thuật toán chung để làm mỏng được dựa trên phép toán hit-and-miss:

Làm mỏng –         Thin(A, B1, B2) = A − HitMiss(A, B1, B2)       (168)

Tùy theo lựa chọn cho B1B2, nhiều thuật toán làm mỏng— và qua các thuật toán lập khung được áp dụng lặp lại—có thể được thực hiện.

Một cách thiết lập rất thực dụng có thể được mô tả theo cách khác. Nếu ta hạn chế chỉ xét phạm vi lân cận 3 × 3, giống như phần tử cấu trúc B = N8 ở Hình 40a, thì ta có thể xem phép toán làm mỏng như một khung được quét qua quét lại ảnh (nhị phân) và đặt điểm ảnh trung tâm bằng “0” trong những trường hợp nhất định. Điểm ảnh trung tâm không bị chuyển thành “0” nếu và chỉ nếu:

i) tìm thấy một điểm ảnh cô lập (chẳng hạn, Hình 43a),
ii) xóa bỏ một điểm ảnh sẽ gây ra thay đổi tính liên thông (chẳng hạn Hình 43b),        (169)
iii) xóa bỏ một điểm ảnh sẽ làm ngắn lại một đoạn thẳng (chẳng hạn Hình 43c).

Các điểm ảnh được xóa bỏ qua mỗi lần lặp (nếu còn); quá trình này được gọi là bào mòn có điều kiện. Ba trường hợp kiểm tra của PT (169) được minh họa trên Hình 43. Nói chung tất cả các phép xoay khả dĩ và các biến thể phải được kiểm tra. Vì chỉ có 512 tổ hợp khả dĩ với trường hợp khung 3 × 3 trên ảnh nhị phân, điều này có thể dễ dàng thực hiện được với một bảng tra.

(a) Điểm cô lập           (b) Điểm liên thông           (c) Điểm cuối

Hình 43: Các trường hợp kiểm tra đối với điểm ảnh trung tâm trong phép bào mòn có điều kiện.

Chỉ khi điều kiện (i) được dùng thì mỗi vật sẽ được thu gọn về một điểm ảnh. Điều này là cần thiết nếu ta muốn đếm số vật trong ảnh. Nếu chỉ có điều kiện (ii) được dùng thì các lỗ hổng trên vật sẽ được phát hiện. Nếu các điều kiện (i + ii) được dùng thì mỗi vật sẽ được thu gọn về một điểm nếu nó không chứa lỗ hổng, hoặc thu về một vòng khép kín nếu nó có chứa lỗ hổng. nếu các điều kiện (i + ii + iii) được dùng thì “bộ khung hoàn thiện” sẽ được tạo ra xấp xỉ với PT (56). Hình 44a,b min họa cho các khả năng này.

9.6.8 Lan truyền

Sẽ rất tiện lợi nếu ta có thể tái tạo ảnh sau khi “trải qua” vài lượt bào mòn hoặc lấp đầy một vật vốn được định nghĩa, chẳng hạn, bằng đường biên. Cơ chế chính thức của cách làm này có một số tên gọi, như lấp đầy vùng (region-filling), tái tạo (reconstruction), và lan truyền (propagation). Định nghĩa chính thức sẽ được cho bởi thuật toán sau. Ta bắt đầu bằng một ảnh hạt nhân (seed image) S(0), một ảnh mặt nạ (mask image) A, và một phần tử cấu trúc B. Sau đó ta dùng giãn nở của S với phần tử cấu trúc B và lấy mặt nạ A để che theo thủ tục được lặp lại như sau:

Lần lặp k –     \textbf{S}^{(k)} = \left[ \textbf{S}^{(k-1)} \oplus \textbf{B} \right] \cap \textbf{A}  \text{ d\^{e}\'{n} khi } \textbf{S}^{(k)} = \textbf{S}^{(k-1)}        (170)

Với mỗi lần lặp ảnh hạt nhân sẽ lớn lên (qua giãn nở) nhưng vẫn nằm trong tập hợp (vật) được định nghĩa bởi A; S lan truyền để lấp đầy A. Những lựa chọn thông dụng nhất cho B bao gồm N4 hoặc N8. Trong việc sử dụng phép lan truyền có một số nhận xét trọng tâm như sau. Trước hết, trong một cách thực hiện trực tiếp, theo PT (170), chi phí tính toán là quá cao. Mỗi vòng lặp đòi hỏi O(N2) phép toán thực hiện trên một ảnh N × N và với số vòng lặp yêu cầu thì điều này có thể dẫn đến độ phức tạp O(N3). May mắn là có cách thực hiện thuật toán này bằng đệ quy trong đó thường chỉ cần một hoặc hai vòng lặp qua ảnh là đủ, tức là độ phức tạp còn O(N2). Thứ hai là, mặc dù cho đến giờ ta đã không để ý nhiều tới vấn đề liên thông của vật/nền (xem Hình 36), nhưng cơ bản là sự liên thông ngầm chứng tỏ ở B sẽ khớp với sự liên thông gắn với định nghĩa biên giới của A (xem các PT (162) và (163)). Sau cùng, như đã đề cập trước đây, việc chọn đúng (“0” hoặc “1”) cho điều kiện biên của ảnh là rất quan trọng. Sự lựa chọn này phụ thuộc vào ứng dụng.

9.6.9 Tóm tắt về các phép tạo khung và phép lan truyền

Việc ứng dụng hai phép toán này lên một tấm ảnh kiểm tra được minh họa ở Hình 44. Trên Hình 44a,b phép toán tạo khung được biểu diễn có điều kiện điểm ảnh cuối (PT (169)i+ii+iii) và không có điều kiện này (PT (169) i+ii). Phép toán lan truyền được minh họa trên Hình 44c. Ảnh gốc, có màu xám nhạt, được bào mòn bằng E(A, 6N8) để tạo ra ảnh hạt nhân màu đen. Sau đó ảnh gốc được dùng làm mặt nạ trong quá trình tạo ra kết quả sau cùng. Giá trị đường biên trong cả hai bức ảnh đều là “0”.

Một vài kĩ thuật dựa trên cách dùng phép toán dựng khung và lan truyền, kết hợp với cá phép toán hình thái khác sẽ được trình bày ở Mục 10.3.3.

Ảnh gốc = xám nhạt                 Mặt nạ = xám nhạt

                     ↓  Khung = đen   ↓                                    ↓  Hạt nhân = đen

                a) Khung với các điểm ảnh đầu cuối     b) Khung không có các điểm ảnh đầu cuối     c) Lan truyền với N8
                                    Điều kiện PT (169) i+ii+iii             Điều kiện PT (169) i+ii

Hình 44: Các ví dụ về tạo khung và lan truyền.

9.6.10 Xử lý hình thái giá trị xám

Kĩ thuật lọc hình thái có thể được mở rộng cho ảnh thang độ xám. Để đơn giản, chúng tôi giới hạn việc trình bày vào phần tử cấu trúc B baoo gồm một số hữu hạn các điểm, có tính lồi và bị chặn. Tuy nhiên, bây giờ thì phần tử cấu trúc đã có các giá trị xám ứng với mỗi vị trí toạ độ cũng giống như ở ảnh A.

 •  Phép giãn nở với thang độ xám, DG( • ), được cho bởi:

Giãn nở –   D_G (\textbf{A}, \textbf{B}) = \underset{[j,k] \in \textbf{B}} {\text{max}} \{a[m-j,n-k] + b[j, k]\}     (171)

Với một tọa độ đầu vào cho trước [m, n], phần tử cấu trúc được cộng với một phiên bản của ảnh đã dịch chuyển và giá trị lớn nhất gặp phải trong toàn miền J × K của B được lấy làm kết quả. Nếu việc dịch chuyển đòi hỏi các giá trị của ảnh A nằm ngoài miền M × N của A, thì cần có quyết định dùng mô hình mở rộng ảnh nào (xem thêm Mục 9.3.2).

 •  Phép bào mòn với thang độ xám, EG( • ), được cho bởi:

Bào mòn –   E_G (\textbf{A},\textbf{B}) = \underset{[j,k] \in \textbf{B}} {\text{min}} \{a[m+j,n+k] - b[j, k]\}     (172)

Tính đối ngẫu giữa bào mòn với thang độ xámgiãn nở với thang độ xám—đối trọng của PT (134) nhưng với trường hợp thang độ xám là:

Đối ngẫu –   EG(A, B) = –DG(-A, \tilde{\textbf{B}})     (173)
                      DG(A, B) = –EG(-A, \tilde{\textbf{B}})

trong đó “\tilde{\textbf{A}}” có nghĩa là a[j, k] → a[ − j,  − k] và “ − A” nghĩa là a[j, k] →  − a[j, k].

Các định nghĩa cho phép toán cấp cao hơn như mở dùng với thang độ xámđóng dùng với thang độ xám là:

Mở –        OG(A, B) = DG(EG(A, B), B)        (174)

Đóng –     C_G(\textbf{A}, \textbf{B}) = E_G (D_G (\textbf{A}, \tilde{\textbf{B}} ), \tilde{\textbf{B}} )     (175)

Tính đối ngẫu giữa mở với thang độ xámđóng với thang độ xám như sau:

Đối ngẫu –    OG(A, B) =  − CG( − A, B)     (176)
                       CG(A, B) =  − OG( − A, B)

Các thuộc tính quan trọng đã thảo luận từ trước như đồng nhất, bất biến đối với tịnh tiến, tăng theo A, v.v. cũng áp dụng được đối với xử lý hình thái thang độ xám. Về chi tiết, bạn có thể xem trong Giardina và Dougherty.9

Trong nhiều trường hợp, sự phức tạp bề ngoài của khâu xử lý hình thái thang độ xám có thể được giảm bớt đáng kể bằng việc dùng các phần tử cấu trúc đối xứng trong đó b[j, k] = b[ − j,  − k]. Những cách hay dùng nhất đều dựa trên B =  hằng số  = 0. Với trường hợp quan trọng này, và một lần nữa dùng đến [j, k] ∈ B, định nghĩa trên có thể thu gọn thành:

Giãn nở –        DG(A, B) =         (177)

Bào mòn –       EG(A, B) =            (178)

Mở –      O_G(\textbf{A},\textbf{B}) =\underset{\textbf{B}}{\text{max}} (\underset{\textbf{B}}{\text{min}} (\textbf{A}))     (179)

Đóng –    C_G(\textbf{A},\textbf{B}) =\underset{\textbf{B}}{\text{min}} (\underset{\textbf{B}}{\text{max}} (\textbf{A}))     (180)

Đến đây, kết luận đáng kể là các lọc cực đạilọc cực tiểu, được giới thiệu ở Mục 9.4.2, là các giãn nở với thang độ xám và bào mòn với thang độ xám cho phần tử cấu trúc riêng cho bởi hình dạng của khung lọc với với giá trị xám “0” ở bên trong khung. Các ví dụ về phép toán này đối với tín hiệu một chiều đơn giản được biểu thị trên Hình 45.

a) Hiệu ứng của giãn nởbào mòn 15 × 1    b) Hiệu ứng của mởđóng 15 × 1

Hình 45: Lọc hình thái đối với số liệu thang độ xám.

Với khung chữ nhật J × K lọc cực đại hoặc cực tiểu hai chiều đều phân ly được thành hai khung khung một chiều. Hơn nữa, lọc cực đại hoặc cực tiểu một chiều có thể được viết dưới dạng tăng dần. (Xem Mục 9.3.2.) Điều này có nghĩa là các phép giãn nở và bào mòn với thang độ xám ta có độ phức tạp tính toán với mỗi điểm ảnh là O(hằng số), nghĩa là độc lập với JK. (Xem thêm Bảng 13.)

Các phép toán định nghĩa nói trên có thể được dùng để tạo ra các thuật toán hình thái để làm trơn, xác định gra-đien và một dạng của toán tử Laplace. Tất cả đều được thiết lập từ những thành phần cơ bản nhất, trong trường hợp của giãn nở bào mòn trong thang độ xám; và trong mọi trường hợp thì các bộ lọc cực đạicực tiểu đều được lấy trên miền [j, k] ∈ B.

9.6.11 Làm trơn theo hình thái

Thuật toán này được dựa trên quan sát rằng, đối với một ảnh thang độ xám, một phép mở sẽ làm trơn ảnh từ phía trên mặt độ sáng cho bởi hàm a[m, n] và phép đóng sẽ làm trơn từ phía dưới. Ta dùng một phần tử cấu trúc B dựa theo các PT (84) và (178).

MorphSmooth(A, B) = CG(OG(A, B, B) = min(max(max(min(A))))        (181)

Lưu ý rằng ta đã lược bỏ các kí hiệu phần tử cấu trúc B phía dưới các toán tử maxmin để giữ cho công thức bớt rườm rà. Song việc dùng B ở đây được ngầm hiểu.

9.6.12 Gra-đien hình thái

Với các bộ lọc tuyến tính, lọc gra-đien cho ra dạng biểu diễn là một véc-tơ (PT (103)) có độ lớn (PT (104)) và hướng (PT (105)). Các dạng được đề cập đến ở đây sẽ phát sinh ra ước tính độ lớn gra-đien theo hình thái:

Gradient(A, B) = ½ (DG(A, B) − EG(A, B)) = ½ (max(A) − min(A))        (182)

9.6.13 Toán tử Laplace hình thái

Bộ lọc Laplace dựa theo hình thái có thể được định nghĩa bởi:

Laplacian(A, B) =  ½ ((DG(A, B) − A) − (A − EG(A, B))) =  ½ (DG(A, B) + EG(A, B) − 2A) = ½ (max(A) + min(A) − 2A)   (183)

9.6.14 Tóm tắt các bộ lọc hình thái

Hiệu ứng của các bộ lọc này được minh họa trên Hình 46. Tất cả tấm ảnh đều được xử lý bằng phần tử cấu trúc 3 × 3 được mô tả trong các PT từ (177) đến (183). Hình 46e được giãn tương phản theo PT (78) nhằm mục đích hiển thị với các tham số 1% và 99%. Các hình 46c,d,e cần được so sánh với các Hình 30, 32, và 33.

a) Giãn nở                b) Bào mòn                   c) Làm trơn

d) Gra-đien              e) Laplace

Hình 46: Các ví dụ về bộ lọc hình thái trên thang độ xám.


  1. Giardina, C.R. and E.R. Dougherty, Morphological Methods in Image and Signal Processing. 1988, Englewood Cliffs, New Jersey: Prentice–Hall. 321.
  2. Gonzalez, R.C. and R.E. Woods, Digital Image Processing. 1992, Reading, Massachusetts: Addison-Wesley. 716.
  3. Serra, J., Image Analysis and Mathematical Morphology. 1982, London: Academic Press.
  4. Vincent, L., Morphological transformations of binary images with arbitrary structuring elements. Signal Processing, 1991. 22(1): p. 3-23.
  5. Vincent, L., Morphological transformations of binary images with arbitrary structuring elements. Signal Processing, 1991. 22(1): p. 3-23.
  6. Van Vliet, L.J. and B.J.H. Verwer, A Contour Processing Method for Fast Binary Neighbourhood Operations. Pattern Recognition Letters, 1988. 7(1): p. 27-36.
  7. Young, I.T., et al., A new implementation for the binary and Minkowski operators. Computer Graphics and Image Processing, 1981. 17(3): p. 189- 210.
  8. Lantuéjoul, C., Skeletonization in Quantitative Metallography, in Issues of Digital Image Processing, R.M. Haralick and J.C. Simon, Editors. 1980, Sijthoff and Noordhoff: Groningen, The Netherlands.
  9. Giardina, C.R. and E.R. Dougherty, Morphological Methods in Image and Signal Processing. 1988, Englewood Cliffs, New Jersey: Prentice–Hall. 321.
Advertisements

2 phản hồi

Filed under Cơ sở

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

  1. Tôi vừa sửa một số lỗi trong các công thức của bài viết (124), (177), (178). Thành thật xin lỗi bạn đọc!

  2. Pingback: Cơ sở Xử lý ảnh | 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