• Không có kết quả nào được tìm thấy

Chương 2:KỸ THUẬT PHÁT HIỆN XƯƠNG NHỜ PHÉP TOÁN HÌNH THÁI

2.1. Các phép toán hình thái và các tính chất

2.1.2. Một số tính chất của phép toán hình thái

2.1.2.3. Hệ quả

a) ((X B) B) B=(X B), b) ((X B) B) B=(X B), Thật vậy, từ định lý trên ta có: X (X B) B, Do đó, theo tính chất gia tăng ta có:

(( )

X B X B B) B, (0.24)

Mặt khác cũng theo định lý trên ta có: (X B) B X X

((X B) B) B X B, (0.25)

Từ (1.24) và (1.25) ta có:

((X B) B) B=X B.

Và ((X B) B) B=X B.

(Phát triển kỹ thuật dò biên, phát hiện biên và ứng dụng/Tr. 15)

BÙI DUY MẠNH-CT1201-HPU Trang 25 2.2. Kỹ thuật tìm xƣơng nhờ phép toán hình thái

2.2.1. Trích biên ( Boundary Extraction )

Với ảnh đầu vào là ảnh xám, thì ta có thể xử lý phân đoạn ảnh bằng các ngưỡng của ảnh. Trong hình ảnh mỗi điểm ảnh có giá trị xám riêng, giá trị này được giới hạn trong khoản 0 tới 255. Vì vậy ta có thể thông qua lược đồ màu để lựa chọn các mức xám thích hợp. Khi chuyển sang ảnh nhị phân các điểm ảnh có giá trị lơn hơn ngưỡng này đều được gán là 255 hoặc nếu không thì sẽ được gán là 0. ngược lại những điểm ảnh nào có giá trị nằm trong ngưỡng đều được đặt là 1, những điểm ảnh này là điểm ảnh cấu thành đối tượng trong ảnh nhị phân.

Trong ảnh nhị phân, đối tượng được cấu thành bởi các điểm ảnh liên thông có giá trị là 1, Xét một thí dụ ở hình 2.16 có 9 điểm ảnh dọc, 9 điểm ảnh ngang. Những điểm ảnh tạo lên biên là những điểm ảnh thuộc đối tượng đó nhưng trong 8 điểm lân cận phải có ít nhất một điểm ảnh có giá trị là 0.

Biên của tập hợp A phụ thuộc vào kích thước của phần tử cấu trúc. Độ dày của đường viền bao quanh đối tượng phụ thuộc vào kích thước của phần từ cấu trúc. Cho 1 thí dụ, nếu một phần tử cấu trúc có kích thước 3x3 sinh ra độ dày đường viền là 1 thì với phần tử cấu trúc có kích thước 5x5 sẽ sinh ra đường viền của đối tượng có độ dày là 3.

Khi đó, biên của tập hợp A, ký hiệu là A, được xác định bởi công thức:

A A (A B), (1.33)

Hình 2.6: Quá trình tìm biên của đối tƣợng trên ảnh nhị phân.

A1

A

B

A

A

1

A B

BÙI DUY MẠNH-CT1201-HPU Trang 26

2.2.2. Làm đầy (Region Filling)

Làm đầy vùng của một đối tượng từ biên là bổ xung giá trị 1 vào toàn bộ vùng ở phía bên trong biên của đối tượng. Cho một ảnh nhị phân A, các điểm ảnh ở biên của đối tượng trong hình ảnh A có giá trị là 1 và các điểm ảnh khác có giá trị là 0. Ta bắt đầu quá trình làm đầy bằng cách gán giá trị 1 vào điểm ảnh p ở bên trong biên của đối tượng, sau đó lặp đi lặp lại phép giãn nhị phân giữa điểm ảnh với phần tử cấu trúc B dưới giới hạn đặt ra bởi phép bù của tập hợp A (Ac). Bởi vì nếu hạn chế không được đặt thì chương trình sẽ lặp đi lặp lại phép gán này, dẫn tới sảy ra hiện tượng tràn qua các cùng khác trên ảnh, thậm chí toàn bộ ảnh.

Với X0=p và B là phần tử cấu trúc, phép làm đầy vùng trong ảnh sẽ được xác định bởi công thức:

Xk=(Xk-1 B) Ac, Với k=1,2,3,…k-1. (1.34) Thuật toán sẽ dừng khi Xk=Xk-1.

Thí dụ, ở hình 2.17, A là ảnh ban đầu chỉ chứa biên của đối tượng ( giá trị là 1 ), B là phần tử cấu trúc có kích thước 3x3 và hình dạng chữ thập.

Khi đó thuật toán sẽ thực hiện lần lượt theo trình tự như sau:

Bước 1: Thuật toán sẽ gán giá trị 1 cho một điểm ảnh p bên trong vùng biên.

Bước 2: Áp dụng phép giãn nhị phân từ điểm ảnh p với phần tử cấu trúc B, đồng thời lấy giao của kết quả phép giãn với phần bù của tập hợp A. Như vậy, sau khi lấy giao của hai tập hợp thì phần nào có giá trị là 1 tương xứng với giá trị 1 của phần bù tập hợp A thì được giữ nguyên, phần nào có giá trị 1 tương xứng với giá trị 0 của phần bù tập hợp A thì sẽ được gán là 0. Quá trình này sẽ được lặp đi lặp lại cho đến khi tất cả các điểm ảnh tương ứng bên trong biên của đối tượng được gán là 1.

Bước 3: Cuối cùng lấy hợp giữa X7 và biên A ta sẽ được đối tượng đã được làm đầy từ biên vùng trong ảnh (Hình 2.17).

BÙI DUY MẠNH-CT1201-HPU Trang 27 Hình 2.7: Quá trình làm đầy đối tƣợng trong ảnh.

2.2.3.Tách các thành phần liên thông (Extraction of Connected Components)

Trong thực tế, bài toán tách thành phần liên thông trong ảnh nhị phân đóng vai trò quan trọng trong các ứng dụng phân tích ảnh tự động.Tương tự như phép làm đầy vùng.

Quá trình thực hiện thuật toán cũng được lặp đi lặp lại với phép tách các thành phần liên thông.

Cho một ảnh nhị phân trong đó đối tượng là tập hợp A bao gồm một số thành phần liên thông. Những điểm ảnh nào thuộc đối tượng thì được đánh dấu là 1 và điểm ảnh nào nằm ngoài đối tượng thì được đánh dấu là 0. Ta có thể tách các thành phần liên thông

BÙI DUY MẠNH-CT1201-HPU Trang 28 bằng cách gán một điểm ảnh ở trong đối tượng rồi từ điểm ảnh đó, lặp đi lặp lại phép giãn nhị phân với phần tử cấu trúc dưới hạn chế đặt ra bởi tập hợp A.

Với X0=p và B là phần tử cấu trúc. Khi đó phép tách các thành phần liên thông được xác định bởi công thức:

Xk = (Xk 1 B) A, k= 1,2,3… (1.35)

Hình 2.8: Quá trình tách các thành phần liên thông trong ảnh bằng phép toán hình thái.

2.2.4. Bao Lồi (Convex Hull)

Ta có thể hình dung bao lồi của một đối tượng giống như một dải băng cao su bao quanh đối tượng. Vì thế dải băng cao su này được căng qua các phần lõm theo các viền lồi của đối tượng. Kết quả là tạo ra một hình dạng đối tượng không có đoạn nào bị lõm.

Bao lồi có thể được biến đổi bởi phép toán Hit-or-Miss với 4 phần tử cấu trúc luân phiên

BÙI DUY MẠNH-CT1201-HPU Trang 29 quay 900. Cho A là một ảnh nhị phân và phần tử cấu trúc Bi với i=1,2,3,4, khi đó ta có 4 phần tử cấu trúc tương ứng như sau:

(1.36) Trong các phần tử cấu trúc trên những phần tử được đánh dấu là những phần tử không cần quan tâm. Đầu tiên cho X0i A, sau đó lặp đi lặp lại thuật toán theo công thức sau:

Xki (X s* B) A, i=1,2,3,4 và k=1,2,3…k-1 (1.37) Khi Xki Xki 1 tức là chúng đồng quy (converge) thì quá trình xử lý dừng lại và đặt

i i

D Xconv, Khi đó bao lồi của A sẽ là:

4

1

( ) i

i

C A

D , (1.38)

Nói cách khác, thuật toán sẽ thực hiện phép biến đổi Hit-or-Miss giữa tập hợp A với phần tử cấu trúc B1 trên toàn bộ đối tượng cho đến khi đối tượng không có gì thay đổi nữa thì dừng lại và đặt Di Xconvi , sau đó hợp tập hợp A với kết quả Di, quá trình này sẽ được thực hiện lần lượt với B B B2, 3, 4. Cuối cùng hợp của 4 tập Dicho ta bao lồi của A.

Xét thí dụ trong một chu trình xử lý ảnh sử dụng phép bao lồi (Hình 2.19). Với tập hợp A là tập hợp các phần tử tạo lên một đối tượng trong ảnh, Ac là phần bù của tập hợp A. B là phần tử cấu trúc gồm có B1, và B2.

Hình 2.9: Một quá trình trong phép bao lồi.

BÙI DUY MẠNH-CT1201-HPU Trang 30 Thí dụ trên cho thấy một chu trình trong quá trình thực hiện phép bao lồi đối với đối tượng trong ảnh. Quá trình này sẽ được lặp đi lặp lại lần lượt với các phần tử cấu trúc khác nhau (1.37). Khi thuật toán kết thúc, tất cả các chỗ bị lõm hay thiếu hụt chi tiết sẽ được làm đầy. Xét một thí dụ tổng quát từ thí dụ trong hình 2.19, với

, và :

Hình 2.10: Phép bao lồi đối với đối tƣợng trong ảnh.

2.2.5. Làm mảnh(Thinning)

Thuật toán làm mảnh thường bao gồm nhiều lần lặp, mỗi lần lặp tất cả các điểm ảnh của đối tượng sẽ được kiểm tra, Các phần tử cấu trúc được thiết kế để tìm các điểm biên mà khi loại bỏ điểm ảnh trên đối tượng thì sẽ không làm ảnh hưởng tới các liên thông.

Nếu điểm ảnh nào mà thỏa mãn điều kiện của phần tử cấu trúc thì sẽ bị loại bỏ. Quá trình này cứ lặp đi lặp lại cho tới khi không còn điểm biên nào được xóa nữa.

Làm mảnh tập hợp A bởi phần tử cấu trúc B, ký kiệu , xác định bởi công thức sau:

BÙI DUY MẠNH-CT1201-HPU Trang 31

= , (1.39)

Để có thể làm mảnh một đối tượng A một cách hiệu quả hơn, ta dựa vào dãy các phần tử cấu trúc.

, (1.40)

Trong đó Nhận được từ , qua phép quay quanh tâm điểm của nó. Với khái niệm này ta định nghĩa phép làm mảnh bởi một dãy các phần tử cấu trúc theo công thức.

, (1.41)

Nói cách khác, quá trình làm mảnh A bởi , kết quả lại tiếp tục được được làm mảnh bởi cho đến . Lúc này đối tượng trong ảnh hầu như không thay đổi nữa.

Xét thí dụ quá trình làm mảnh (Hình 2.21). Quá trình làm mảnh đối tượng sẽ được lặp đi lặp lại cho đến khi đối tượng không có sự thay đổi nào thì dừng lại .

Theo công thức tổng quát ta có:

,

Như vậy, Trong thí dụ này quá trình làm mảnh được lặp đi lặp lại 2 lượt. Trong mỗi lần lặp đối tượng phải trải qua quá trình làm mảnh với 8 phần tử cấu trúc:

.

BÙI DUY MẠNH-CT1201-HPU Trang 32 Hình 2.11: Quá trình làm mảnh đối tƣợng trong hình ảnh.

2.2.6. Tìm khung xƣơng (Skeletonization)

Tìm khung xương cũng tương tự như làm mảnh, nhưng nó được dùng để tìm ra các chi tiết cấu trúc của đối tượng. Khung xương của đối tượng là tập hợp các điểm ảnh cách đều biên của đối tượng. Và có thể biểu diễn bằng phép co nhị phân và phép mở ảnh.

BÙI DUY MẠNH-CT1201-HPU Trang 33 Xét A là một ảnh nhị phân bao gồm các điểm ảnh thuộc đối tượng, được đặt nhãn là các số 1. Các điểm ảnh không thuộc đối tượng được đặt nhãn là các số 0. B là phần tử cấu trúc 3x3. Khi đó, nếu ký hiệu S(A) là khung xương của tập hợp A thì thuật toán tìm khung xương được xác định qua công thức:

, (1.42)

Trong đó: , (1.43)

(A ⊖ kB) là phép co k lần liên tiếp trên A. Tức là:

(A ⊖ kB )=((..( A ⊖ B)…) ⊖ B ….)⊖ B

Và K là Bước lặp cuối cùng trước khi A bị ăn mòn thành tập rỗng. Nói cách khác:

K = max{ k | (A ⊖ kB ) }

Công thức (1.42) và (1.43) khẳng định rằng khung xương S(A) có thể nhận được từ hợp các bộ khung xương con Sk(A). Có thể chứng minh rằng A có thể xây dựng lại từ các tập con này bằng cách sử dụng công thức:

A = , (1.44)

Trong đó ký hiệu k lần giãn nhị phân Sk(A), tức là:

=((..( Sk(A) ⊕B)…) B ….)⊕ B.

Xét thí dụ:

Hình 2.12: Quá trình thực hiện thuật toán tìm xƣơng.