Xem mẫu
- Ch¬ng 18
NHẬN DẠNG MẪU:
PHÂN ĐOẠN ẢNH
18.1. GIỚI THIỆU
Từ trước đến nay, trong cuốn sách này, chúng ta đã xem xét những phương pháp
chủ yếu để cải thiện ảnh hiển thị. Trong chương 16, tham vọng chúng ta là đạt được
một ảnh gần giống hơn so với ảnh ban đầu, ảnh không suy biến.
Trong chương này và hai chương tiếp theo, chúng ta sẽ đưa ra một vài hướng
phân tích nội dung của một ảnh. Nghĩa là chúng ta cố gắng tìm ra những gì có trong
ảnh. Chúng ta sẽ xem xét hai cách tiếp cận, nhận dạng mẫu thống kê và mạng nơ ron,
mỗi một phương pháp đều có thể áp dụng vào ảnh số. Các cuốn sách đã viết nhiều
về cả hai phương pháp này, giúp độc giả những người mong muốn tiếp tục tìm hiểu
với những giới thiệu về lĩnh vực này rất nhiều.
Trong 3 chương về nhận dạng mẫu này, chúng ta sẽ đưa ra một tập các chủ đề về
lĩnh vực này. Trong thực tế, chúng ta nghiên cứu nhận dạng mẫu thống kê, được thực
hiện bằng các kỹ thuật xử lý ảnh số. Việc này trước hết bao gồm việc định vị và cô
lập các đối tượng trong một ảnh và sau đó nhận biết (phân loại) những đối tượng đó
sử dụng kỹ thuật dựa trên lý thuyết quyết định thống kê. Chúng ta cũng xem qua việc
sử dụng mạng nơ ron nhân tạo cho việc nhận dạng mẫu.
18.1.1. Nhận dạng mẫu thống kê
Chi nhánh thị giác máy của lĩnh vực trí tuệ nhân tạo được nghiên cứu bằng cách
phát triển các thuật giải phân tích nội dung ảnh. Một sự đa dạng của những phương
pháp tiếp với mục đích hiểu ảnh đã được dùng, nhưng việc hiểu nó là nền tảng cho
sự nhận thức toàn bộ quá trình nhận dạng mẫu, tuy nhiên nó có thể được thực hiện.
Nhận dạng mẫu thống kê giả thiết rằng ảnh có thể chứa một hay nhiều đối tượng
và mỗi đối tượng đó thuộc một trong các kiểu, các loại hay các lớp mẫu đã định
nghĩa trước đây. Trong khi có thể thực hiện nhận dạng mẫu bằng nhiều cách, chúng
ta chỉ quan tâm tới việc thực hiện nó bằng các kỹ thuật xử lý ảnh số.
Cho một ảnh số có chứa một vài đối tượng, quá trình nhận dạng mẫu gồm có 3
pha chính. (Xem Hình 18-1) Pha đầu tiên được gọi là phân đoạn ảnh hay cô lập đối
tượng, trong đó mỗi đối tượng được tìm ra và ảnh của nó tách ra khỏi cảnh còn lại.
Pha thứ hai gọi là trích chọn đặc trưng. Đây là pha mà các đối tượng được đo
lường. Một số đo là giá trị của một tính chất nào đó có thể xác định số lượng của một
đối tượng. Một đặc trưng là một hàm của một hay nhiều số đo, được tính toán sao
cho nó có thể nó xác định được một tính chất quan trọng nào đấy của đối tượng. Quá
trình trích chọn đặc trưng tạo ra một tập các đặc trưng, cùng nhận được, bao gồm vec
tơ đặc trưng. Điều này đã làm giảm khối lượng thông tin (so với ảnh ban đầu) biểu
diễn mọi tin tức mà các quyết định thống kê phải dựa vào đó. Thật là hữu ích để nhận
thức hoá một không gian n chiều mà trong đó mọi vec tơ đặc trưng n phần tử có thể
có đều tập trung vào. Vì thế, một đối tượng riêng biệt bất kỳ đều tương ứng với một
điểm trong không gian đặc trưng.
Pha thứ ba trong nhận dạng mẫu là phân loại, đầu ra của nó chỉ đơn thuần là một
quyết định về lớp các đối tượng. Mỗi đối tượng được coi như thuộc một loại cụ thể,
và sự nhận dạng được thực hiện như một quá trình phân loại. Từng đối tượng được
350
- ấn định vào một trong nhiều nhóm (lớp) đã thiết lập trước đó biểu diễn cho tất cả các
loại đối tượng có thể có trong ảnh. Một lỗi không phân loại nhầm sẽ xảy ra nếu đối
tượng bị ấn định vào một lớp không thích hợp. Khả năng để xảy ra điều này là tỉ số
lỗi phân loại nhầm.
Sự phân loại chỉ dựa vào vec tơ đặc trưng. Trong hai chương tiếp theo, chúng ta
sẽ xem xét kỹ thuật phân loại xuất phát từ các phạm trù trong lý thuyết quyết định
thống kê và mạng nơ ron.
HÌNH 18-1
Hình 18-1 Ba pha nhận dạng mẫu
18.1.2. Ví dụ về nhận dạng mẫu
Các khái niệm cơ bản về nhận dạng mẫu thống kê có thể được minh hoạ tốt nhất
bằng một ví dụ. Giả sử chúng ta muốn thực hiện một hệ thống sắp xếp trái cây đổ
xuống trên một băng truyền. Việc sắp xếp thực sự có thể bị ảnh hưởng bởi các phần
có thể di chuyển từ trên xuống và làm chệch hướng đi của các loại trái cây khác nhau
ra khỏi băng truyền và rơi vào trong các hộp chuyên chở thích hợp, như minh hoạ
trong hình 18-2. Hãy giả sử rằng đó là các quả là các trái anh đào, các quả táo, chanh
và các quả nho. Những gì chúng ta cần là một hệ thống xử lý ảnh mà có thể quan sát
các quả đang đến gần, phân ra từng loại và thả phần đã phân loại thích hợp đúng lúc
vào hộp đựng trái cây tương ứng.
HÌNH 18-2
Hình 18-2 Hệ thống sắp xếp trái cây
Chúng ta có thể cài đặt một camera truyền hình số trên băng truyền và thực hiện
quyết định phân loại bằng một máy tính. Với ví dụ này, hãy xác định hai tham số cho
từng mẫu trái cây: đờng kính và màu sắc của nó. Chương trình máy tính sẽ xử lý
351
- từng ảnh số hoá và tính đường kính trái cây theo đơn vị milimet và một tham số biểu
thị màu sắc.
Giả sử chúng ta sử dụng một camera TV màu và chương trình tính độ sáng của
từng đối tượng theo các kênh đỏ, lục và lam. (Xem chương 21) Sau đó có thể nhận
được một đặc trưng (ví dụ tỷ lệ độ sáng đỏ-lục) nhận các giá trị thấp cho quả màu
vàng và các giá trị cao cho quả màu đỏ. Chúng ta có thể gọi tham số này là độ đo sắc
đỏ.
Hình 18-3 cho thấy không gian hai đặc trưng chiều định nghĩa bằng hai tham số,
đường kính và sắc đỏ, và các nhóm được đưa ra tương ứng với mỗi một trong bốn
lớp quả. Bằng cách đặt các đường quyết định xấp xỉ trong không gian đặc trưng,
chúng ta có thể phân chia nó ra thành mỗi vùng thuộc một lớp và thiết lập một quy
tắc phân loại.
Khi một quả nào đó đến gần camera TV, nó sẽ được xác định, và các đặc trưng
xác định một điểm trong không gian hai chiều. Tuỳ thuộc vào nơi mà điểm này nằm
trong không gian, mà trái cây được ấn định vào một trong bốn lớp. Ngay khi quyết
định phân loại được thực hiện, cơ chế bỏ vào phần mà sau đó sẽ được làm lệch
hướng đi để đẩy quả vào trong thùng chứa thích hợp.
HÌNH 18-3
Hình 18-3 Không gian đặc trưng
Trong khi hệ thống tiền xử lý không được sử dụng rộng rãi trong ngành công
nghiệp đóng gói trái cây, nhưng nó đáp ứng được việc minh hoạ nhận dạng mẫu
thống kê. Vai trò của thống kê trong thiết kế và hoạt động của hệ thống sẽ trở nên rõ
ràng hơn ở hai chương tiếp theo. Bây giờ đủ điều kiện để nói rằng mỗi lớp quả tạo ra
một PDF trong không gian đặc trưng. Các dòng quyết định có thể được xác định, từ
tác động qua lại giữa các PDF đó, theo cách để tránh hay có ít ra là tối thiểu hoá, các
lỗi phân loại nhầm.
18.1.3. Thiết kế hệ thống nhận biết mẫu
Thiết kế một hệ thống nhận biết mẫu thường được thực hiện theo năm bước liệt kê
trong bảng 18.1: thiết kế bộ định đối tượng, chọn lựa đặc trưng, thiết kế bộ phân loại
và thực hiện việc đánh giá.
Bộ định vị đối tượng là thuật toán tách ảnh của đối tượng riêng biệt trong một ảnh
phức hợp. Việc phân tách các đối tượng được gọi là phân đoạn ảnh hay phân đoạn
cảnh, sẽ được trình bày trong chương này. Chọn lựa đặc trưng có tác dụng quyết
định thuộc tính của đối tượng (kích thức, hình dạng,…). điểm khác biệt nhất giữa các
lớp đối tượng cần phải tính toán. Thiết kế bộ phân loại bao gồm việc thiết lập một cơ
sở toán học cho thủ tục phân loại. Các tham số có thể điều chỉnh (ngưỡng quyết
định) của chính bộ phân loại bắt buộc phải có trong công đoạn huấn luyện bộ lọc.
352
- Cuối cùng, nó thường cần được thiết lập các tỷ lệ lỗi phân loại khi hệ thống hoạt
động. Đây là bước thực hiện việc đánh giá.
18.2. QUÁ TRÌNH PHÂN ĐOẠN ẢNH
Chúng ta có thể định nghĩa quá trình phân đoạn ảnh như là việc phân chia một ảnh
số thành các vùng rời nhau (không chờm lên nhau). Đối với mục đích của chúng ta,
một vùng là một tập liên thông của các điểm ảnh-tức là, một tập trong đó tất cả các
điểm ảnh gần kề hay sát nhau. Định nghĩa chuẩn của tính liên thông như sau: giữa
hai điểm ảnh bất kỳ trong một tập liên thông, tồn tại một đường liên thông trong
phạm vi tập, ở đó một đường liên thông là một đường luôn luôn di chuyển giữa các
điểm ảnh lân cận. Do đó, trong một tập liên thông, bạn có thể tìm thấy một đường
liên thông giữa hai điểm ảnh bất kỳ trong tập.
BẢNG 18-1 THIẾT KẾ HỆ THỐNG NHẬN DẠNG MẪU
Bước Hàm
1. Thiết kế bộ định vị đối tượng Chọn thuật giải phân đoạn ảnh để phân
tách các đối tượng riêng biệt trong ảnh.
2. Lựa chọn đặc trưng Quyết định các tính chất đối tượng mà có
thể phân biệt các loại đối tượng tốt nhất
và làm thế nào để đo lường chúng.
3. Thiết kế bộ phân loại Thiết lập cơ sở toán học cho thuật giải
phân loại, và lựa chọn kiểu cấu trúc của
bộ phân loại để sử dụng.
4. Huấn luyện bộ phân loại Cố định các tham số điều chỉnh khác
nhau (các đường biên quyết định,…)
trong bộ phân loại cho phù hợp với đối
tượng được phân loại.
5. Đánh giá hiệu suất Đánh giá tỷ số các lỗi phân loại nhầm có
thể nhận được khác nhau.
Có hai quy tắc liên thông, và một trong số đó có thể chấp nhận. Nếu chỉ các điểm
lân cận bên (trên, dưới, trái, phải) được coi là thuộc liên kết, thì đây là liên thông 4
và các đối tượng là liên kết 4. Vì thế, mỗi điểm ảnh chỉ có 4 lân cận để có thể liên
kết. Thêm vào đó, nếu các điểm ảnh lân cận chéo (lân cận 450) cũng được tính đến
trong liên kết thì chúng ta có liên thông 8, và các đối tượng là liên kết 8. Mỗi điểm
ảnh có 8 lân cận để có thể liên kết. Cũng có thể sử dụng quy tắc liên thông kia, miễn
là thích hợp. Thông thường liên thông 8 mang lại kết quả được coi là gần với trực
giác của con người hơn cả.
Khi một người quan sát một cảnh, quá trình xử lý đặt trong hệ thống thị giác sẽ
phân đoạn cảnh đó cho người đó. Việc này được thực hiện hiệu quả đến nỗi ta trông
nó không như một cảnh phức tạp, nhưng đúng hơn là người ta coi điều đó như là tập
hợp cáca đối tượng. Tuy nhiên, bằng xử lý số, chúng ta phải tách các đối tượng trong
một ảnh bằng cách phân chia ảnh thành tập các điểm ảnh, mỗi tập là ảnh của một đối
tượng. Trong khi công việc phân đoạn ảnh hầu như không có bản sao trong kinh
nghiệm nhìn nhận của con người, thì đây là một công việc không tầm thường trong
phân tích ảnh số.
Phân đoạn ảnh có thể tiếp cận từ ba lý thuyết phối cảnh khác nhau. Trong trường
hợp chúng ta tiếp cận vùng, ta ấn định mỗi điểm ảnh cho một đối tượng hay vùng cụ
thể. Trong phương pháp tiếp cận đường biên, ta chỉ thử định vị các đường biên đã có
giữa các vùng. Trong phương pháp tiếp cận đỉnh, ta có thể tìm cách nhận biết các
điểm biên và sau đó liên kết chúng với nhau tạo thành đường biên cần có. Tất cả ba
cách tiếp cận đều hữu dụng trong việc nhìn nhận vấn đề.
353
- Trong chương này, chúng ta xem xét một vài kỹ thuật phân tách các đối tượng
trong một ảnh số. Mỗi lần phân tách, các đối tượng có thể được đo lường và phân
loại. Các kỹ thuật cho những hoạt động này được chỉ ra trong hai chương tiếp theo.
18.3. PHÂN ĐOẠN ẢNH BẰNG PHÂN NGƯỠNG
Phân ngưỡng là một kỹ thuật phổ biến để tiếp cận vùng, hữu ích đối với những
cảnh có chứa những đối tượng đồng màu trên nền tương phản. Mục đích là để đơn
giản trong tính toán và luôn xác định được những vùng có các đường biên đóng và
liên thông.
Khi sử dụng qui tắc phân ngưỡng để phân vùng ảnh, người ta ấn định tất cả những
điểm ảnh nằm bên trên mức xám ngưỡng thuộc về đối tượng. Còn tất cả những điểm
ảnh không nằm trên mức xám ngưỡng sẽ nằm ngoài đối tượng. Đường bao là tập tất
cả những điểm nằm bên trong và mỗi điểm có ít nhất một điểm lân cận nằm ngoài
đối tượng.
Phân ngưỡng sẽ được thực hiện hoàn hảo nếu đối tượng được xét có mức xám bên
trong đồng nhất và nằm trên nền có mức xám đồng nhất khác. Nếu một vài tính chất
(ngoài mức xám, tính kết cấu chẳng hạn) của các đối tượng khác nền của chúng, thì
đầu tiên người ta có thể chuyển đổi tính chất đó thành mức xám. Sau đó tiến hành
phân ngưỡng mức xám để có thể phân vùng ảnh.
18.3.1. Phân ngưỡng tổng thể
Trong quá trình xác định đường biên bằng phân ngưỡng đơn giản nhất, giá trị mức
xám ngưỡng là hằng số được sử dụng trong toàn bộ ảnh. Nếu mức xám nền là hằng
số hợp lý và nếu các đối tượng đều có độ tương phản xấp xỉ bằng nhau, thì một
ngưỡng tổng thể cố định thường được dùng để qui định mức xám ngưỡng hợp lý
được chọn.
18.3.2. Phân ngưỡng thích nghi
Trong nhiều trường hợp mức xám nền không phải là hằng số và độ tương phản
của các đối tượng trong ảnh hoàn toàn khác nhau, thường xảy ra trường hợp một
ngưỡng áp dụng thích hợp cho một vùng ảnh này nhưng lại không thích hợp cho
những vùng khác. Trong những trường hợp đó, thuận tiện nhất là sử dụng mức xám
ngưỡng là một hàm biến thiên chậm theo vị trí trong ảnh.
Hình 18-4 cho thấy ảnh hiển vi của các nhiễm sắc thể từ một tế bào máu người.
Trong ảnh này, mức xám nền thay đổi do sự chiếu sáng không đồng đều và độ tương
phản thay đổi từ nhiễm sắc thể này sang nhiễm sắc thể khác. Trong hình 18-4a, một
mức xám ngưỡng không đổi được sử dụng cho toàn bộ ảnh để phân tách các nhiễm
sắc thể. Mỗi nhiễm sắc thể được bao bởi một đường và một dãy số. Trong hình 18-
4b, ngưỡng được thay đổi từ nhiễm sắc thể này sang nhiễm sắc thể khác tương xứng
với nền cục bộ và độ tương phản của nhiễm sắc thể. Điều này đã tạo ra một vài sai số
phân đoạn-trong đó nhiều nhiễm sắc thể bị dính vào nhau hay các nhiễm sắc thể
riêng biệt bị phá vỡ. Một nghiên cứu tương tự cho thấy rằng độ chính xác của phép
đo diện tích các nhiễm sắc thể đã được cải tiến bằng phân ngưỡng thích nghi. Trong
hình 18-4b, ngưỡng đối với mỗi nhiễm sắc thể được đặt xấp xỉ mức trung bình giữa
mức xám trung bình của đối tượng và mức xám nền cục bộ.
18.3.3. Lựa chọn ngưỡng tối ưu
Trừ phi đối tượng trong ảnh có các mặt cực kỳ dốc đứng, còn thì giá trị chính xác
của mức xám ngưỡng có thể có tác động đáng kể lên vị trí đường biên và toàn bộ
kích thước đối tượng được trích chọn. Nghĩa là các số đo kích thước liên tiếp-khu
vực riêng biệt-nhạy cảm với mức xám ngưỡng. Vì lý do đó mà chúng ta cần sự tối ưu
hay ít ra cũng là phương pháp thiết lập ngưỡng.
354
- HÌNH 18-4
Hình 18-4 Phân ngưỡng tổng thể và thích nghi
18.3.3.1. Kỹ thuật lược đồ mức xám
Một ảnh chứa một đối tượng trên nền tương phản có lược đồ mức xám nhị thức
(bimodal) (hình 18-5). Hai đỉnh tương ứng với số lượng tương đối lớn các điểm trong
và ngoài đối tượng. Vùng lõm giữa các đỉnh tương ứng với các điểm tương đối ít
xuất hiện xung quanh biên của đối tượng. Trong các trường hợp như thế này, lược đồ
mức xám thường được dùng để thiết lập mức xám ngưỡng.
Diện tích một đối tượng xác định bởi mức xám ngưỡng T là
A H ( D)dD (18.1)
T
Lưu ý rằng việc tăng ngưỡng T thêm một lượng T chỉ hơi làm giảm diện tích nếu
ngưỡng tương ứng với vùng lõm trong lược đồ mức xám. Bởi vậy, việc lấy ngưỡng
tại vùng lõm của lược đồ sẽ tối thiểu hoá tính nhậy cảm của phép đo vùng với các sai
số nhỏ trong sự chọn ngưỡng.
H (D )
A H ( D)dD
T
A
Db T T T D0
D
Hình 18-5 Lược đồ mức xám nhị thức
Nếu ảnh hay vùng trong ảnh chứa đối tượng bị nhiễu và không lớn lắm thì chính
lược đồ mức xám sẽ bị nhiễu. Nhiễu sẽ làm mờ đi vị trí của vùng lõm, trừ phi vùng
lõm rõ nét một cách khác thường. Điều này có thể khắc phục trong một phạm vi nào
đó bằng cách làm trơn lược đồ mức xám, bằng cách sử dụng tích chập hay bằng một
thủ tục điều chỉnh đường cong. Nếu hai đỉng có kích thước không giống nhau, thì
việc làm trơn có xu hướng dịch chuyển vị trí rất ít. Tuy nhiên, dễ dàng định vị các
đỉnh và tương đối ổn định khi làm trơn. Một phương pháp có khả năng tin cậy hơn để
đặt ngưỡng tại một vị trí cố định nào đó liên quan tới hai đỉnh-có lẽ là điểm giữa. hai
đỉnh thể hiện phương thức (xuất hiện nhiều nhất) các mức xám của các điểm bên
trong và bên ngoài đối tượng. Nói chung, các tham số này có thể được đánh giá
chính xác hơn mức xám thường ít xuất hiện nhất-tức là vùng lõm trong lược đồ.
355
- Người ta có thể tạo thành một lược đồ mức xám chỉ có những điểm có độ lớn
gradient tương đối cao, ví dụ 10% cao nhất. Việc này ước lượng số lượng lớn điểm
ảnh bên trong và bên ngoài dtvà có thể làm cho vùng lõm trên lược đồ dễ truy cập
hơn. Người ta cũng có thể chia lược đồ theo gradient trung bình của những điểm ảnh
tại mỗi mức xám để tăng cường vùng lõm hơn nữa hay lấy mức xám trung bình của
những điểm ảnh có gradient cao để xác phân ngưỡng.
Bộ lọc Laplace là một toán tử đạo hàm bậc hai hai chiều. Lọc Laplace theo sau
làm trơn và phân ngưỡng tại mc bằng 0 hay cao hơn một chút có xu hướng phân
vùng đối tượng tại các chéo 0 của đạo hàm bậc hai, tương ứng với những điểm uốn
trên các biên của đối tượng. Lược đồ hai chiều của mức xám và gradient cũng có thể
được dùng để thiết lập tiêu chuẩn phân đoạn.
18.3.3.2. Phân ngưỡng thích nghi
Kỹ thuật phân vùng thích nghi trong hình 18-4b được thực hiện bằng kỹ thuật hai
bước. Trước khi qua bước thứ nhất, ảnh được chia làm nhiều khu vực 100 100
điểm ảnh. Từ lược đồ mức xám của mỗi khu vực, một ngưỡng được xác định giữa
đỉnh nền và đỉnh dữ liệu. Các khu vực chứa các lược đồ đơn thức đều bị bỏ qua.
Trong bước thứ nhất, các đường biên của đối tượng đã định nghĩa sử dụng
ngưỡng mức xám là một hằng số trong phạm vi khu vực, nhưng khác các khu vực
còn lại. Các đối tượng định nghĩa như vậy không được trích chọn từ ảnh, nhưng mức
xám bên trong trung bình của mỗi đối tượng được tính đến.
Trong bước thứ hai, mỗi đối tượng được lập ngưỡng của chính nó nằm giữa mức
mức xám bên trong và mức xám của nền của khu vực chính. Xem xét trong hình 18-
4 cho thấy rằng số các chi tiết nhỏ giảm từ bảy xuống còn hai, trong khi số các tan rã
giảm từ một tới không.
18.3.4. Phân tích các điểm
Trong nhiều trường hợp quan trọng, đây là điều cần thiết để tìm ra các đối tượng
có hình dạng gần như tròn. Việc phát triển dưới đây chủ yếu tập trung vào các đối
tượng hình tròn. Hạn chế của chúng ta đối với các đối tượng hình tròn cho phép ta
tiếp tục lựa chọn ngưỡng tối ưu hơn là những ngỡng khác. Các khái niệm đã trình
bày dù sao cũng hữu ích đối với nhiều trường hợp tổng quát hơn.
18.3.4.1. Định nghĩa
Giả sử một ảnh B(x,y) chứa một điểm đơn. Theo định nghĩa, ảnh này chứa một
điểm (x0,y0) có mức xám cực đại. Nếu chúng ta thiết lập toạ độ cực có tâm là (x0,y0),
sao cho ảnh được cho bởi Bp(r,), thì
B p r1 , B p r2 , nếu r2 > r1 (2)
với mọi . Chúng ta gọi B(x,y) là điểm đơn điệu nếu dấu đẳng thức không xảy ra
trong biểu thức (2). Nghĩa là mức xám hoàn toàn giảm theo một đường kéo dài ra
theo hướng bất kỳ từ tâm (x0,y0). Đối với các điểm đơn điệu, không có một đỉnh bằng
phẳng, và (x0,y0) là duy nhất.
Một trường hợp đặc biệt quan trọng có thể xảy ra nếu tất cả các đường viền của
một điểm đơn điệu là những đường tròn tâm (x0,y0). Chúng ta gọi trường hợp đặc biệt
đó là điểm đường tròn đồng tâm (concentric circular spot-CCS). Với ý nghĩa gần
đúng, điều này thường miêu tả ảnh không nhiễu của các vì sao trong kính thiên văn,
các tế bào nào đó trong kính hiển vi và rất nhiều loại ảnh quan trọng khác. Nhiễu
thường làm cho các ảnh thực sai khác với các định nghĩa của chúng, nhưng dù sao lý
thuyết cũng có thể chứng tỏ tính hữu ích.
Đối một CCS, hàm Bp(r,) độc lập đối với , ta gọi nó là hàm chiếu điểm. Đường
cong này có ích cho chọn lựa ngưỡng. Ví dụ, chúng ta có thể xác định điểm uốn và
356
- chọn ngưỡng mức xám để đặt đường biên tại điểm có độ dốc lớn nhất. Đây là sự gầm
đúng mà mắt người có thể phân biệt được đường biên khi xem một ảnh chứa cạnh
trơn, và đó là sự khá ổn định dưới tác động của việc làm trơn và thêm nhiễu. Đường
bao này có thể đánh giá không đúng mức kích thước thật sự của các đối tượng. Các
điểm duy nhất khác thuộc hình chiếu, ví dụ như độ lớn cực đại của đạo hàm bậc hai
cũng có thể được sử dụng.
Nếu chúng ta phân ngưỡng một điểm đơn điệu tại một mức xám T, chúng ta định
nghĩa một đối tượng có một diện tích và chu vi xác định. Khi chúng ta thay đổi T
trong bộ dải mức xám, chúng ta tạo ra hàm diện tích ngưỡng A(T) và hàm chu vi
ngưỡng p(T). Cả hai hàm này đều là duy nhất đối với một điểm bất kỳ. Cả hai đều là
liên tục đối với các điểm đơn điệu, và mỗi một hàm đủ xác định CCS một cách đầy
đủ. Như nội dung của định nghĩa, hai điểm là tương đương p nếu chúng có các hàm
chu vi giống hệt nhau và tương đương H nếu chúng có các lược đồ giống như nhau.
Từ đó ta có các điểm tương đương H có các hàm diện tích ngưỡng giống nhau.
18.3.4.2. Lược đồ và tóm tắt
Giả sử một ảnh CCS B(x,y) được cho bởi một hàm tóm tắt Bp(r) của nó. Bây giờ
chúng ta tìm kiếm một biểu thức cho một lược đồ điểm dưới dạng hàm tóm tắt. Giả
sử chúng ta phân ngưỡng B(x,y) tại mức xám D và phân lại tại mức xám D + D.
Giả thiết này định nghĩa hai vòng tròn bao quanh có bán kính r và r + r, như trong
hình 18-6. Diện tích của hình tròn giữa các đường viền là
A r 2 r r 2rr
2
(3)
Trong đó xấp xỉ thu được bằng giả thiết r là rất nhỏ và bỏ qua r2
Biểu thức 3 có thể sắp xếp lại như sau
A
2r (4)
r
Theo định nghĩa, lược đồ của ảnh là,
A
H B D L (5)
D 0 D
HÌNH 18-6
Hình 18-6 Phân ngưỡng một điểm tròn đồng tâm
Chúng ta có thể chia tử số và mẫu số cho r và thay biểu thức (4) vào tử số ta
được
A / r 2r
H B D L (6)
D 0 D / r d / drB p r
357
- Để đạt được đẳng thức ngoài cùng bên phải, chúng ta phải ghi nhớ rằng cả r và
D đều tiến tới 0, và chúng ta thừa nhận đạo hàm của hàm tóm tắt trong mẫu số.
Chúng ta chưa chấm dứt, bởi vì vế phải của biểu thức (6) là một hàm của r thay vì
của một hàm của D. Do B(x,y) là ảnh của điểm đơn điệu, Bp(r) là một hàm đơn điệu
giảm, và do đó, tồn tại hàm ngược của nó là
r D B p1 D (7)
Bây giờ chúng ta có thể thay nó vào trong tử và mẫu số của biểu thức (6) để tạo
lược đồ một hàm mức xám. Chú ý rằng, vì hàm tóm tắt Bp(r) đơn điệu giảm với r,
nên mẫu số của biểu thức (6) âm. Biểu thức này bỏ dấu trừ trong tử số tạo lược đồ
dương, như mong muốn.
18.3.4.3. Tóm tắt diện tích nhận được
Bây giờ chúng ta tìm kiếm một biểu thức tóm tắt một CCS dưới dạng lược đồ của
nó. Bán kính của đối tượng hình tròn thu được bằng phân ngưỡng một CCS tại mức
xám T là
1/ 2 1/ 2
1 1
RT AT H B D dD (8)
2 T
Đối với một điểm đơn điệu, lược đồ HB(D) khác 0 giữa giá trị mức xám lớn nhất
và nhỏ nhất của nó. Nghĩa đó là hàm diện tích A(T) là đơn điệu tăng, và vì vậy cũng
đúng cho hàm R(T). Vì thế, tồn tại hàm nghịch đảo của biểu thức (8) và chính là tóm
tắt. Cho nên, chúng ta có thể tính tóm tắt diện tích nhận được của một CCS bằng
cách tích phân lược đồ để được hàm diện tích, công việc đầu tiên là lấy căn bậc hai
và sau đó nghịch đảo hàm.
18.3.4.4. Tóm tắt chu vi nhận được
Phân ngưỡng một CCS tại mức xám T tạo ra một dy hình trong có bán kính
1
R T P T (9)
2
Trong đó p(T) là hàm chu vi. Giống như với kỹ thuật trước, tóm tắt chỉ đơn thuần
là hàm nghịch đảo của biểu thức (9). Do đó nếu biết hàm chu vi thì có thể thu được
hàm tóm tắt bằng nghịch đảo biểu thức (9).
18.3.4.5. Các điểm không tròn và các điểm nhiễu
Chúng ta có thể thu được hầu như dễ dàng tóm tắt một ảnh chứa một CCS không
nhiễu đơn giản bằng cách lấy các mức xám theo dòng quét chứa đỉnh. Tuy nhiên, đối
với các điểm không tròn và các điểm nhiễu các kỹ thuật đã đề cập trước đây có thể
hữu ích. Ví dụ, ta có thể sử dụng lược đồ của một điểm không tròn để thu được tóm
tắt của CCS tương đương H và chọn mức xám để cực đại hoá độ dốc đường biên.
Trong các trường hợp khác, nó hữu dụng để tính hàm chu vi và xác định tóm tắt của
CCS tương đương p. Mỗi kỹ thuật có thể tạo ra một ngưỡng thích hợp đối với ảnh
sắp đến.
Trong ảnh số hoá của một cảnh tự nhiên, mức nhiễu thường cao đến nỗi một dòng
quét đơn không thể nhận biết chính xác một điểm uốn thuộc hàm tóm tắt trở thành
khác biệt. Tuy nhiên, các tóm tắt diện tích nhận được và chu vi nhận được được tính
bằng cách sử dụng đa số hay tất cả các điểm ảnh biên trong đối tượng. Quá trình này
dùng để giảm nhiễu vốn có bằng cách lấy trung bình. Thêm vào đó, việc giảm nhiễu
có thể bị ảnh hưởng bằng việc làm trơn lược đồ hay hàm chu vi trước khi tính tóm
tắt, hay làm trơn chín hàm tóm tắt. Tóm tắt diện tích nhận được tính toán dễ dàng
hơn, và nó có các tính chất đối xử phân biệt nhiễu cấp cao.
358
- Nhiễu ngẫu nhiên trong ảnh thường tạo ra các ngưỡng đường biên bị lởm chởm.
Trong khi điều này có thể ảnh hưởng đôi chút lên hàm diện tích, nó có xu hướng tạo
ra các sai lầm lớn trên các hàm chu vi. Mặc dù có thể giảm các lỗi bằng cách xây
dựng quá trình làm trơn đường biên thành thủ tục tính chu vi, đơn giản hoá công việc
tính toán trên khía cạnh tóm tắt diện tích nhận được.
Sieracki, Reichenback, và Webb đã so sánh chín phương pháp chọn ngưỡng, trong
đó có hai phương pháp dựa trên tóm tắt diện tích nhận được (độ lớn tối đa của đạo
hàm bậc nhất và đạo hàm bậc hai) đối với việc tính toán đường kính của các vi hạt
huỳnh quang. Phát biểu một cách tổng quát, họ đã tìm thấy phương thức sau là chính
xác nhất trong chín phương pháp đối với các hạt có kích thước và cường độ khác
nhau. Nó cũng đã thực hiện tốt cho các tế bào trong việc cấy ghép mô. Tìm kiếm giá
trị lớn nhất của đạo hàm bậc nhất, giống các phương pháp đã kiểm tra khác, có xu
hướng đánh giá kích thước của các vật thể không đúng mức.
18.3.5. Gradient đường biên trung bình
Đối với các điểm không tròn, các tóm tắt CCS tương đương H và tương đương p
là không thể chấp nhận cho việc lấy ngưỡng mức xám. Đối với các đối tượng có hình
dạng tuỳ ý, chúng ta có thể xem xét gradient trung bình xung quanh đường biên như
một hàm mức xám ngưỡng định nghĩa đường biên.
Giả sử môt điểm đơn điệu không tròn phân ngưỡng tại các mức xám D và D + D
như đã cho trong hình 18-7. Tại một điểm a nào đó trên đường biên ngoài. r khoảng
cách vuông góc với đường biên bên trong. Vì r là vuông góc với một đường viền
nên nó nằm theo hướng vec tơ gradient tại điểm a. Độ lớn của vec tơ gradient tại
điểm a trên đường biên ngoài là
D
B L (10)
D 0 r
HÌNH 18-7
Hình 18-7 Phân ngưỡng một điểm không tròn
Vì chúng ta quan tâm đến gradient trung bình quanh đường biên, nên chúng ta có
thể tính trung bình |B| quanh đường biên ngoài một cách đơn giản. Nếu r nhỏ so
chu vi thì diện tích giữa hai đường biên là
A pD r (11)
Trong đó r là khoảng cách vuông góc trung bình từ đường biên bên ngoài tới
đường biên bên trong và p(D) là hàm chu vi. Để nhận được gradient trung bình xung
quanh đường biên, chúng ta chỉ cần thay r cho r trong biểu thức (10). Việc này
tạo ra
359
- D p D
B L p D (12)
D 0 r H B D
biểu thức này chỉ ra rằng gradient đường biên trung bình đơn thuần là tỷ số giữa
hàm chu vi với lược đồ.
Hàm gradient đường biên trung bình không khó tính toán cho lắm, và nó dễ dàng
nhận ra ngưỡng mức xám cực đại hoá độ dốc của đường biên. Đối với ảnh nhiễu,
hàm chu vi và lược đồ cần phải làm trơn trước khi tính hàm gradient đường biên
trung bình.
18.3.6. Các đối tượng có dạng tổng quát
Mặc dù một vài kết quả trước đây được trình bày chủ yếu cho các loại đối tượng
bị giới hạn, dù sao chúng cũng hữu dụng đối với các trường hợp tổng quát hơn. Giả
sử một ảnh chứa các đối tượng có một khuôn dạng tổng quát trên một nền mức xám
thấp. Trong khi các đối tượng có thể có đỉnh tương đối bằng phẳng, không đơn điệu
và không phải là đỉnh duy nhất, chúng thường có các mặt mà độ dốc giảm đều xuống
tới nền. PSF của các hệ thống quang học không cho phép các mặt có độ dốc vô hạn
trong ảnh thực. Trên các mặt khác của các đối tượng, các đường viền là khép kín và
thường là các đường cong lồi có mặt lõm cục bộ.
Chúng ta có thể giả thiết mỗi mức xám ngưỡng định nghĩa một đường cong khép
kín đơn lẻ cho mỗi đối tượng. Với các điều kiện này, chúng ta chỉ cần xem xét phạm
vi mức xám tương ứng với các mặt dốc của đối tượng. Bây giờ ta bốn phương pháp
thiết lập mức xám ngưỡng T có độ dốc cực đại:
1. Chúng ta có thể chọn T tại khu vực thấp nhất trong lược đồ. Đây là kỹ thuật
đơn giản nhất và nó tối thiểu hoá tính nhạy cảm của phép đo diện tích với biến
đổi nhỏ theo T.
2. Chúng ta có thể chọn T tương ứng với các điểm uốn trong tóm tắt CCS tương
đương H. Đây là một phép tính đơn giản và nó bao gồm cả việc tính trung
bình để giảm nhiễu.
3. Chúng ta có thể chọn T để cực đại hoá gradient đường biên trung bình. Bao
gồm việc tính hàm chu vi, nhưng không đòi hỏi xấp xỉ hoá đối với các điểm
ảnh tương đương.
4. Chúng ta có thể chọn T tương ứng với điểm uốn trong hàm tóm tắt CCS tương
đương p.
Bất kỳ một trong các phương pháp trước đây đều có thể được thực hiện cho công
việc hàng ngày. Đối với những nghiên cứu lớn, chúng ta có thể sử dụng một trong
các phương pháp để mô tả đặc điểm các đối tượng mà chúng ta nghiên cứu. Sau đó
một phương pháp nhanh chóng trực tiếp có thể sử dụng cho các công việc thông
thường. Ví dụ, nếu một phân tích tóm tắt chứng minh rằng ngưỡng mức xám quang
học đối với các ảnh sao đã phân tách trong các ảnh thiên văn xuất hiện ở giữa mức
xám đỉnh và nền, sau đó phương pháp đã đơn giản hoá này được thực hiện cho công
việc bình thường.
18.3.7. Thuật toán đường phân nước (Watershed)
Một thuật toán có liên quan tới ngưỡng thích hợp là thuật toán đường phân nước.
Hình 18-8 minh hoạ cách tiếp cận việc thực hiện. Chúng ta giả thiết các đối tượng
trong hình đều có mức xám thấp, trên một nền có mức xám cao. Hình cho thấy các
mức xám trên một dòng quét cắt ngang qua hai đối tượng nằm sát nhau.
Ban đầu ảnh được phân ngưỡng tại một mức xám thấp, mức xám này phân đoạn
ảnh thành một lượng các đối tượng thích hợp, nhưng với các đường biên thì mức
xám này là quá nhỏ. Sau đó ngưỡng được tăng từ từ, mỗi làm một mức xám. Các
đường biên của các đối tượng sẽ mở rộng khi tăng ngưỡng. Tuy nhiên, khi chúng tiếp
360
- xúcvới đối tượng không được phép hoà trộn vào đối tượng. Vì vậy, các điểm tiếp xúc
đầu tiên này trở thành đường biên giữa các đối tượng liền kề. Quá trình được chấm
dứt trước khi ngưỡng tiến tới mức xám nền-tức là, tại điểm khi đường biên của các
đối tượng được phân tách tốt là một tập hoàn chỉnh.
HÌNH 18-8
Hình 18-8 Thuật toán đường phân nước
Thay vì phân ngưỡng ảnh một cách đơn giản các ảnh tại mức xám tối ưu, thì
phương pháp tiếp cận đường phân nước bắt đầu bằng một ngưỡng là quá thấp, nhưng
ngưỡng dó phân tách hoàn toàn các đối tượng riêng biệt. Sau đó khi ngưỡng được
tăng từ từ đến mức tối ưu, thì việc hợp nhất các đối tượng là không được phép. Nó có
thể giải quyết vấn đề đặt ra khi thực hiện phân ngưỡng tổng thể với các đối tượng
quá gần nhau. Việc phân đoạn cuối cùng sẽ chính xác (chẳng hạn, mỗi đối tượng
thực sự trong ảnh đều có một đường biên) nếu và chỉ nếu việc phân đoạn tại ngưỡng
ban đầu là chính xác.
Cả ngưỡng mức xám ban đầu và cuối cùng phải được chọn lựa tốt. Nếu ngưỡng
ban đầu quá thấp, thì các đối tượng tương phản thấp đầu tiên sẽ bị bỏ qua và sau đó
hợp nhất các đối tượng sát nhau khi tăng ngưỡng. Nếu ngưỡng ban đầu quá cao, thì
các đối tượng sẽ được hợp nhất với nhau ngay từ đầu. Giá trị ngưỡng cuối cùng xác
định các đường biên cuối cùng điều chỉnh các đối tượng tốt đến mức nào. Các
phương pháp chọn ngưỡng được bàn tới trong chương này có thể có ích trong việc
thiết lập hai giá trị trên.
18.4. CÁC PHƯƠNG PHÁP PHÂN ĐOẠN TRÊN CƠ SỞ GRADIENT
Những tiếp cận vùng trước đây thực hiện sự phân đoạn bằng cách phân chia ảnh
thành các tập điểm trong và ngoài. Ngược lại, mục đích của tiếp cận biên là tìm kiếm
các biên trực tiếp bằng độ lớn gradient của chúng. Trong phần nàu, chúng ta sẽ đề
cập đến ba phương pháp nêu trên.
18.4.1. Tìm đường biên
Giả sử chúng ta bắt đầu với ảnh độ lớn gradient (hình 7-5) tính từ một ảnh chứa
một đối tượng đơn lẻ trên một nền tương phản. Chúng ta có thể bắt đầu quá trình tìm
đường biên bằng việc xác định các điểm ảnh có mức xám cao nhất (điểm ảnh có
gradient cao nhất trong ảnh ban đầu) như điểm đầu tiên của đường biên, vì nó chắc
chắn phải nằm trên đường biên. Nếu một vài điểm có mức xám cực đại, thì ta lựa
chọn tuỳ ý.
Tiếp theo chúng ta tìm kiếm các lân cận 3 3 mà tâm là điểm biên đầu tiên và coi
điểm lâm cận với mức xám cực đại như điểm biên thứ hai. Nếu hai điểm lân cận có
cùng mức xám cực đại, ta chọn tuỳ ý. Tại điểm này, chúng ta bắt đầu lặp lại quá trình
tìm kiếm điểm biên tiếp theo, từ các điểm biên hiện tại và các điểm trước đó. Làm
361
- việc với lân cận 3 3 tâm tại điểm biên hiện tại, chúng ta xem xét lân cận đối diện
điểm biên trước và các lân cận trên mỗi cạnh của nó (Hình18.9). Điểm biên tiếp theo
là điểm có mức xám cao nhất trong ba điểm trên. Nếu cả ba hay hay điểm biên liền
kề có chung mức xám cao nhất, thì chúng ta chọn điểm giữa. Nếu hai điểm không
liền kề có chung mức xám cao nhất, ta chọn tuỳ ý.
Trong ảnh không nhiễu của một điểm đơn điệu, thuật toán này sẽ phát biện đường
biên gradient cực đại; tuy nhiên, những lượng nhiễu nhỏ có thể là biên tạm thời. Có
thể giảm ảnh hưởng của nhiễu bâừng cách làm trơn ảnh gradient trước khi tìm biên
hay bằng cách thực hiện tìm kiếm rệp (tracking bug). Dù sao, quá trình tìm biên
không chắc chắn đối với các biên kín và thuật toán tìm biên có thể chạy ra ngoài
phạm vi ảnh.
HÌNH 18-9
Hình 18-9 Tìm biên
Tìm kiếm rệp là một thuật toán "côn trùng" làm việc như sau. Trước hết chúng ta
định nghĩa một cửa sổ trung bình hình chữ nhật (con rệp), thường có các trọng số
đồng đều (hình 18-10). Hai hay vài điểm biên cuối cùng định nghĩa hướng hiện tại
của đường biên. Phần sau của con rệp được đặt tại điểm biên hiện hành, với trục của
nó hướng theo chiều hiện hành. Rồi sau đó con rệp hướng sang cạnh khác với góc .
Trong mỗi vị trí, ta tính gradient trung bình dưới co rệp. Điểm biên tiếp theo được
coi như một trong những điểm ảnh dưới phần đầu của con rệp khi nó nằm tại vị trí
gradient trung bình cao nhất. Rõ ràng, tìm kiếm rệp một thủ tục tìm biên bao quát
hơn về mặt không gian đã miêu tả trước đây. Con rệp có kích thước lớn hơn sẽ thực
hiện quá trình làm trơn ảnh gradient và khiến cho nó ít nhạy cảm với nhiễu. Nó cũng
hạn chế sự thay đổi đột ngột chiều đi của đường biên.
Kích thước và hình dạng của con rệp có thể thay đổi để đạt được sự thực hiện tốt
nhất. Có thể làm tăng “tính ì” của con rệp bằng cách giảm góc trông . Trong thực tế,
hình dạng đúng của con rệp hình như có ảnh hưởng đoi chút đến sự thực hiện của nó.
Những con rệp tìm gradient thường chỉ hữu ích trong những ảnh nhiễu vô cùng thấp
hay trong tình huống mà sự can thiệp của con người có thể ngăn chặn được những sai
lầm tai hại.
HÌNH 18-10
362
- Hình 18-10 Con rệp tìm biên
18.4.2. Phân ngưỡng ảnh gradient
Nếu chúng ta phân ngưỡng một ảnh gradient tại mức xám có mức độ, thì chúng ta
tìm cả đối tượng lẫn nền dưới một ngưỡng và đa số các điểm biên nằm bên trên nó
(hình 18-11). Phương pháp phân đoạn của Kirsch lợi dụng hiện tượng này. Trong kỹ
thuật này, đầu tiên ta phân ngưỡng gradient tại một mức thấp vừa phải để xác định
đối tượng và nền, chúng được tách biệt bằng dải các điểm biên trên mức ngưỡng. Sau
đó ngưỡng được tăng dần lên. Điều này làm cho cả đối tượng và nền đều tăng. Khi
chúng tiếp xúc, chúng không được phép hợp nhất lại với nhau, đúng hơn là các điểm
tiếp xúc định nghĩa đường biên. Đây là một ứng dụng của thuật toán đường phân
nước đối với ảnh gradient.
§èi tîng
T2
Gradient
Ngìng
T1
x
Hình 18-11 Thuật toán phân đoạn ảnh Kirsch
Trong khi chi phí tính toán cho phương pháp Kirsch đắt hơn so với việc phân
ngưỡng, thì nó xu hướng tao ra các đường biên gradient cực đại, và nó tránh được
nhiều vấn đề về cấc con rệp tìm gradient. Đối với ảnh nhiều đối tượng, sự phân đoạn
sẽ chính xác nếu và chỉ nếu nó được thực hiện chính xác bởi bước phân ngưỡng ban
đầu. Làm trơn ảnh gradient trước sẽ tạo ra các đường biên trơn hơn.
18.4.3. Phát hiện biên Laplace
Laplace là toán tử đạo hàm có hướng bậc hai đối với các hàm hai chiều. Nó được
định nghĩa bởi
2 2
2 f ( x, y) f ( x , y ) f ( x, y ) (13)
x 2 y 2
nó thường được thực hiện số bằng một trong các hạt nhân tích chập cho trong
hình 18-12.
Bởi vì là đạo hàm bậc hai, nên Laplace sẽ tạo ra một một chéo 0 dốc đứng tại biên
(hình 18-13). Laplace là toán tử tuyến tính bất biến dịch và hàm truyền đạt của nó
bằng 0 tại gốc của không gian tần số. Vì thế, một ảnh lọc Laplace sẽ có mức xám
trung bình 0.
0 -1 0 -1 -1 -1
-1 4 -1 -1 8 -1
0 -1 0 -1 -1 -1
363
- Hình 18-12 Các hạt nhân tích chập Laplace
HÌNH 18-13
Hình 18-13 Đạo hàm biên
Nếu một ảnh không nhiễu có các biên sắc nét, Laplace sẽ tìm thấy chúng. Ảnh nhị
phân thu được từ việc phân ngưỡng ảnh lọc Laplace tại mức xám 0 sẽ tạo ra các
đường viền đóng và liên thông khi các điểm bên trong đã được đánh giá. (Xem phần
18.7) Tuy nhiên, vì sự có mặt của nhiễu tác động nên cần lọc thông thấp trước khi
dùng kỹ thuật Laplace.
Một bộ lọc thông thấp Gauss là một chọn lựa thích hợp cho quá trình làn trơn
trước này. Vì tích chập có tính kết hợp [chơng 9, biểu thức (39)], nên ta có thể kết
hợp đáp ứng xung Laplace và Gauss thành hạt nhân Laplace của Gauss riêng biệt:
x2 y 2 x 2 y2
21 2 2 1 x2 y2 2 2
e 1 e (14)
2 2 4 2 2
Đáp ứng xung này có thể tách ra theo x và y và vì thế có thể thực hiện một cách
hiệu quả. Nó có hình dạng của đáp ứng xung bộ lọc thông dải tổng quát đã đề cập
trong chương 11, đó là một đỉnh dương trong một mặt âm (hình 18-14). Tham số
điều chỉnh độ rộng của đỉnh giữa và vì thế nó điều chỉnh khối lượng làm trơn. Thực
tế, nó được xấp xỉ với độ chênh lệch của bộ lọc Gauss trong phần 11.4.1 (chương 11,
biểu thức (12)) khi tỷ lệ độ lẹch tiêu chuẩn là 2 = 1.61.
HÌNH 18-14
Hình 18-14 Bộ lọc Laplace của Gauss: (a) đáp ứng xung; (b) hàm truyền đạt
364
- 18.5. PHÁT HIỆN BIÊN VÀ LIÊN KẾT
Một phương pháp tiếp cận khác để thiết lập các đường biên đối tượng trong ảnh là
đầu tiên ta xem xét từng điểm ảnh và lân cận trực tiếp của nó để xác định điểm ảnh
có thực sự nằm trên đường biên của đối tượng hay không. Các điểm ảnh đáp ứng
những đặc tính yêu cầu đó gọi là các điểm biên. Một ảnh mà trong đó mức xám phản
ánh cường độ mỗi điểm ảnh tương ứng thoả mãn các yêu cầu của một điểm biên gọi
là ảnh biên hay bản đồ biên. Ảnh này cũng có thể được hiển thị như một ảnh biên nhị
phân chỉ đưa ra vị trí (không phải độ lớn) các điểm biên. Một ảnh được mã hoá trực
tiếp theo biên, thay vì độ lớn, gọi là ảnh biên có hướng.
Bình thường một biên ảnh cho thấy hình dáng phác hoạ của từng đối tượng qua
các điểm biên, nhưng hiếm khi thấy những đường biên dạng đóng, liên thông như
thế, chúng rất cần thiết cho phân đoạn ảnh. Vì vậy, đòi hỏi phải có một bước khác
trước khi trích chọn đối tượng. Liên kết điểm biên là quá trình kết hợp các điểm biên
gần nhau để tạo ra một đường biên đóng, liên thông. Quá trình này điền vào những
hỗ hổng do nhiễu và các tác động sắc thái để lại.
18.5.1. Phát hiện biên
Nếu điểm ảnh nằm trên đường biên của một đối tượng trong ảnh thì lân cận của
nó sẽ là một vùng chuyển tiếp mức xám. Hai đặc tính chủ yếu đáng chú ý là độ dốc
và hướng chuyển tiếp. Đó là độ lớn và hướng của véc tơ gradient.
Các toán tử phát hiện biên xem xét từng điểm ảnh lân cận và xác định độ dốc
cũng như hướng của chuyển tiếp mức xám. Có nhiều cách để thực hiện điều này,
nhưng đa số đều dựa trên nhân chập với một tập các mặt nạ đạo hàm có hướng.
Toán tử biên Roberts. Một toán tử vi phân để tìm biên là toán tử biên Roberts,
được cho bởi
g ( x, y ) f ( x, y )
2
f ( x 1, y 1) f ( x 1, y ) f ( x, y 1)
2 1/ 2
(15)
trong đó f(x,y) là ảnh vào với toạ độ điểm ảnh (x,y) nguyên. Căn bậc hai bên trong
làm cho hoạt động của quá trình xử lý giống với hệ thống thị giác của con người.
Toán tử biên Sobel. Hình 18-5 trình bày hai ma trận tích chập dưới dạng toán tử
biên Sobel. Mỗi điểm trong ảnh được nhân chập với cả hai hạt nhân. Một hạt nhân
tương ứng tối đa với biên dọc và ma trận kia để tìm biên ngang. Giá trị lớn nhất của
hai tích chập là giá trị đầu ra cho điểm ảnh đó. Kết quả cho ta một ảnh độ lớn biên.
-1 -2 -1 -1 0 1
0 0 0 -2 0 2
1 2 1 -1 0 1
Hình 18-15 Toán tử Sobel
Toán tử biên Prewitt. Hai hạt nhân tích chập cho trong hình 18-16 tạo thành toán
tử biên Prewitt. Cũng giống như đối với toán tử Sobel, mỗi điểm ảnh được nhân chập
với cả hai hạt nhân và giá trị cực đại sẽ xác định điểm ra. Kết quả của toán tử Prewitt
cũng như vậy, tạo ra ảnh độ lớn biên.
-1 -1 -1 -1 0 1
0 0 0 -1 0 1
1 1 1 -1 0 1
365
- Hình 18-16 Toán tử Prewitt
Toán tử Kirsch. Tám hạt nhân tích chập cho trong hình 18-17 là toán tử Kirsch.
Mỗi điểm trong ảnh được nhân chập với tất cả tám mặt nạ này. Mỗi mặt nạ tương
ứng với cực đại của một hướng biên trong hướng chung. Giá trị cực đại của tám
hướng được lấy làm giá trị cho điểm ra của ảnh độ lớn biên. Chỉ số của mặt nạ cực
đại tương ứng mã hoá hướng của biên.
HÌNH 18-17
Hình 18-7 Toán tử Kirsch
Thực hiện bộ phát hiện biên. Nhìn bề ngoài, các ảnh biên được tạo ra bằng các
toán tử phát hiện biên có vẻ rất giống nhau. Chúng thường giống như dòng kẻ mà
người ta phác thảo trên một bức tranh. Toán tử Roberts là các ma trận 2 2, thích
hợp nhất cho các chuyển tiếp đột ngột trong ảnh nhiễu thấp. Còn các toán tử khác
được sử dụng trong trường hợp chuyển tiếp từ từ và ảnh bị nhiễu nhiều hơn.
Bình thường, đối với các bộ phát hiện biên hai mặt nạ, biên độ lớn hơn được coi
như giá trị ra. Việc này khiến chúng có phần nhậy cảm với hướng của biên. Có thể
thu được đáp ứng nhiều chiều thích hợp hơn bằng cách lấy căn hai tổng bình phương.
Việc này xấp xỉ hoá biên độ gradient chính xác hơn.
Chú ý rằng các toán tử Sobel và Prewitt 3 3 có thể tổng quát hoá thành tám
hướng và sử dụng như toán tử Kirsch để thu được các ảnh hướng biên.
18.5.2. Liên kết biên
Nếu các cạnh có thể tin tưởng được và mức nhiễu là thấp, thì ta có thể phân
ngưỡng ảnh biên (Xem lại hình 7-7) và làm mảnh ảnh nhị phân thu được (Xem phần
18.7.4.2) còn lại các đường biên đóng, liên thông có độ rộng bằng một điểm đơn.
Tuy nhiên, dưới những điều kiện ít lý tưởng hơn một ảnh biên như vậy sẽ có chỗ
trống phải điền đầy.
Các lỗ trống nhỏ có thể điền đầy đơn giản bằng cách tìm kiếm một lân cận 5 5
hay lớn hơn có tâm là một điểm kết thúc, đối với các điểm kết thúc khác và sau đó
điền đầy bằng các điểm đường biên như yêu cầu để liên kết chúng. Tuy nhiên, trong
các ảnh phức tạp có nhiều điểm biên, việc này có thể vượt ra ngoài đoạn ảnh. Để
khắc phục sự vượt quá khả năng phân đoạn ảnh, ta có thể yêu cầu hai điểm kết thúc
có chung cường độ và hướng biên, trong phạm vi cho phép, trước khi liên kết chúng.
18.5.2.1. Tìm kiếm Heuristic
Giả sử chúng ta có một lỗ trống trong đường biên của ảnh biên. Nhưng nó quá dài
để có thể điền chính xác bằng đường thẳng, thực ra nó có thể không phải là một lỗ
trống trong cùng một đường biên, hay có lẽ cả hai. Chúng ta có thể thiết lập, như một
phép đo số lượng, một hàm có thể tính cho mọi đường liên kết giữa hai điểm kết
thúc, mà chúng ta gọi là A và B.
366
- Chúng ta bắt đầu bằng việc đánh giá các lân cận của A như một ứng cử viên nhận
bước đầu tiên tiến về phía B. Thông thường chỉ ba lân cận của A nằm theo hướng
chung với B sẽ xem xét. Chúng ta chọn một điểm mà có thể cực đại hoá hàm đặc
trưng biên từ A tới điểm đó. Sau đó nó trở thành điểm đầu tiên cho bớc lặp tiếp theo.
Cuối cùng, khi chúng ta đạt tới B, hàm đặc trưng biên đối với đường mới tạo ra được
đem so sánh với một ngưỡng. Nếu biên mới tạo ra không thích hợp, nó sẽ bị bỏ đi.
Việc tính toán trong kỹ thuật tìm kiếm Heuristic sẽ trở thành tốn kém nếu hàm đặc
trưng biên phức tạp và lỗ hổng được đánh giá quá nhiều và dài. Các kỹ thuật trên
thực hiện tốt đối với các ảnh tương đối đơn giản, nhưng không cần thiết phải quy về
trên đường tối ưu toàn bộ giữa các điểm kết thúc.
18.5.2.2. Hiệu chỉnh đường cong
Nếu các điểm biên nằm rải rác, nó có thể được hiệu chỉnh một đường cong tuyến
tính từng đoạn hay đường cong chốt bậc cao hơn (higher order spline curve) qua
chúng để thiết lập một đường biên thích hợp cho việc trích chọn các đối tượng. Các
kỹ thuật hiệu chỉnh đường cong thông dụng được đề cập trong phần 19.5. Ở đây,
chúng ta đề cập đến phương pháp tuyến tính từng đoạn gọi là hiệu chỉnh lặp.
Giả sử chúng ta có một nhóm các điểm biên nằm rải rác giữa hai điểm cụ thể A và
B và chúng ta mong muốn chọn lựa một tập con các điểm này để tạo ra các nút của
một đường tuyến tính từng đoạn từ A tới B. Chúng ta bắt đầu thực hiện một đường
thẳng từ A tới B. Sau đó chúng ta tính khoảng cách vuông góc từ đường đó đến từng
điểm biên còn lại. Điểm xa nhất trở thành nút tiếp theo trên đường đi, bây giờ đường
đi có hai nhánh. Quá trình được lặp lại trên mỗi nhánh mới cho đến khi không còn
điểm biên nào nằm trên nhiều hơn một khoảng cách cố định nào đó kể từ nhánh gần
nhất. Khi việc này được thực hiện cho mọi cặp điểm (A, B) xung quanh đối tượng, nó
tạo ra một đa giác gần đúng với đường biên.
18.5.2.3. Biến đổi Hough
Đường thẳng y = mx + b có thể được biểu diễn trong toạ độ cực như sau
x cos y sin (16)
Trong đó (,) định nghĩa một vec tơ từ gốc toạ độ tới điểm gần nhất nằm trên
đường (hình 18-18a). Vec tơ này sẽ vuông góc với đường thẳng.
Chúng ta có thể thừa nhận một không gian hai chiều được định nghĩa bằng hai
tham số và . Một đường bất kỳ trong mặt phẳng x, y đều tương ứng với một điểm
trong không gian đó. Vì vậy, biến đổi Hough của một đường thẳng trong không gian
x, y là một điểm trong không gian và .
Bây giờ xem xét một điểm (x1, y1) riêng biệt trong mặt phẳng x, y. Có rất nhiều
đường thẳng đi qua điểm này và mỗi một trong những đường thẳng đó đều tương
ứng với một điểm trong không gian , . Tuy nhiên, những điểm này phải thoả mãn
biểu thức (16) với x1 và y1 là các hằng số. Vì vậy, quỹ tích của tất cả những đường
thẳng trên trong mặt phẳng x, y đều là một đường sin trong không gian tham số và
một điểm bất kỳ trong mặt phẳng x, y (hình 18-18b) đều tương ứng với một đường
cong hình sin trong không gian , (hình 18-18c).
Nếu chúng ta có tập các điểm biên xi, yi nằm trên đường thẳng có tham số 0 và
0, thì mỗi điểm sẽ tương ứng với một đường cong trong không gian , . Tuy nhiên,
tất cả các đường cong phải giao nhau tại điểm (0, 0).
367
- HÌNH 18-18
Hình 18-18 Biến đổi Hough: (a) một đường thẳng biểu diễn trong toạ độ cực;
(b) mặt phẳng x, y; (c) mặt phẳng ,
Vì thế, để tìm một đoạn thẳng có các điểm nằm trên đó, chúng ta có thể lập một
lược đồ hai chiều trong không gian , . Với mỗi điểm biên (xi, yi), ta tăng tất cả các
ống của lược đồ trong không gian , tương ứng với biến đổi Hough (đường cong
hình sin) đối với điểm đó. Khi chúng ta thực hiện điều này cho tất cả các điểm biên,
thống chứa (0, 0) sẽ cực đại tại khu vực đó. Vì vậy, chúng ta tìm kiếm lược đồ
không gian , cho các cực đại cục bộ và nhận được các tham số của các đoạn biên
tuyến tính.
18.6. PHÁT TRIỂN VÙNG
Phát triển vùng là một cách tiếp cận sự phân đoạn ảnh mà đã nhận được sự chú ý
đáng kể trong đoạn thị giác máy của lĩnh vực trí tuệ nhân tạo. Với các tiếp cận này, ta
bắt đầu chia ảnh thành nhiều vùng nhỏ. Vùng ban đầu có thể là những lân cận nhỏ
hay thậm chí là những điểm ảnh đơn lẻ. Trong mỗi vùng, ta xác định những tính chất
được định nghĩa một cách thích hợp, phản ánh thành viên trong một đối tượng. Tính
chất phân biệt các điểm ảnh trong các đối tượng khác nhau có thể bao gồm mức xám
trung bình, kết cấu hay thông tin màu sắc. Vì thế, bước đầu tiên ấn định cho mỗi
vùng một tập các tham số mà các giá trị của chúng phản ảnh các đối tượng chứa
chúng.
Tiếp theo, tất cả các đường biên giữa các vùng liền kề được xét đến. Lợi dụng sự
khác nhau về các tính chất lấy trung bình giữa các vùng liền kề để xác định cường độ
đường biên. Một đường biên đã cho là mạnh nếu các tính chất trên cách cạnh của
đường biên đó khác nhau một cách đáng kể và là yếu nếu ngược lại. Các đường biên
mạnh được thừa nhận là có giá trị, trong khi các đường biên yếu bị huỷ bỏ và bị hợp
nhất vào các vùng lân cận.
Quá trình được lặp lại bằng cách luân phiên tính lại các tính chất đối tượng thành
viêndv các vùng được mở rộng và sau đó huỷ bỏ các đường biên yếu. Quá trình hợp
nhất vùng được tiếp tục cho đến khi đạt đến một điểm không có đường biên đủ yếu
để có thể huỷ bỏ. Sau đó hoàn thành việc phân đoạn ảnh. Kiểm tra thủ tục này cho ta
dấu vết các vùng bên trong đối tượng cứ lớn lên cho đến khi các đường biên của
chúng thông tinương ứng với các biên của đối tượng.
Việc tính toán các thuật toán phát triển vùng đắt hơn so với các kỹ thuật đơn giản
hơn, nhưng việc phát triển vùng có thể lợi dụng một vài tính chất của ảnh trực tiếp và
đồng thời trong định nghĩa vị trí đường biên cuối cùng. Có lẽ nó cho thất triển vọng
lớn nhất trong sự phân đoạn các ảnh tự nhiên, trong đó mặt mạnh của những kiến
thức trước đây là không sẵn có.
Hình 18-19 trình bày bốn giai đoạn trong việc phát triển vùng của một thớ cơ nhìn
qua kính hiển vi. Trong ví dụ này, gradient thấp là tính chất thành viên của vùng nền.
Ảnh dưới bên phải cho thấy đường biên cuối cùng.
368
- HÌNH 18-19
Hình 18-19 Ví dụ về phát triển vùng
18.7. XỬ LÝ ẢNH NHỊ PHÂN
Các ảnh nhị phân-ảnh chỉ có hai mức xám-tạo thành một tập con các ảnh số quan
trọng. Một ảnh nhị phân (ví dụ một hình chiếu hay một phác đồ) thường có được từ
một phép phân đoạng ảnh. nếu sự phân đoạn ban đầu không đáp ứng hoàn toàn, thì
một dạng xử lý nào đó thực hiện trên ảnh nhị phân có thể cải thiện tình huống.
Nhắc lại rằng có hai nguyên tắc liên thông (liên thông 4 và liên thông 8) và ta phải
sử dụng một trong hai nguyên tắc (Phần 18.2). Tiếp cận liên thông 4 nhận biết chỉ
các điểm ảnh liền kề ngang và dọc như các lân cận, trong khi liên thông 8 coi 8 điểm
ảnh gần nhất như lân cận. Đối với nhiều ứng dụng, liên thông 0 được sử dụng nhiều
hơn.
Tích chập một ảnh nhị phân với hạt nhân 3 3 trong hình 18-20 tạo ra một ảnh 9
bit (512 mức xám) trong đó mức xám của mỗi điểm ảnh xác định cấu hình của lân
cận nhị phân 3 3 có tâm tại điểm đó. Các phép toán lân cận vì thế mà có thể được
thực hiện bằng một bảng tra cứu 512 mục với một bit đầu ra. Một phép toán có thể
được thực bằng phần mềm hay trong một phần cứng được thiết kế đặc biết, sử dụng
bảng tra cứu thường có hiệu quả hơn so với một vài phép thực hiện khác.
HÌNH 18-20
Hình 18-20 Mã hoá lân cận nhị phân
Tiếp cận này có thể sử dụng để thực hiện mọt phép toán logic gọi là biến đổi đúng
(hit) hay sai (miss). Bảng tra cứu được nạp vào để tìm kiếm một mẫu nào đo-ví dụ,
cả 9 điểm ảnh đều là màu đen. Đầu ra là 1 hay 0, tuỳ thuộc vào việc lân cận có tương
xứng với mặt nạ hay không. Nếu một lúc nào đó mẫu là tương xứng (đúng), thì điểm
ảnh trung tâm sẽ được đặt là màu trắng và điểm ảnh trung tâm của tất cả các cấu hình
khác giữ nguyên không thay đổi (sai), phép toán sẽ giảm các đối tượng chỉ đặc thành
nét phác thảo của chúng bằng cách đánh giá các điểm bên trong.
369
nguon tai.lieu . vn