XỬ LÝ ẢNH - CHƯƠNG 18

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

121
lượt xem 29
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: XỬ LÝ ẢNH - CHƯƠNG 18

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 k hô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à g iá 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ụ t hể, 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ệ t hố 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ả p hầ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ệ t hố 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ó t hể 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à t rá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ý k hô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ệ t hố 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à t huậ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 ỳ t rong 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ệ t hố 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ư k hô 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 để p hâ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à  (18.1) A   H ( D)dD 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 T T  T Db 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à k hô 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à p hâ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à p hâ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   2rr 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  2r (4) r Theo định nghĩa, lược đồ của ảnh là, A H B D   L (5) D D 0 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  2r A / r H B D   L  (6) D / r d / drB p r  D  0 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 1  D  (7) p 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    RT    AT     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 để g iả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ể g iả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) r D  0 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  pD r (11) Trong đó r là k ho ả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
p D  D p D   (12) B  L H B D   D  0 r biểu thức này chỉ ra rằng gradient đường biên trung bình đơn thuần là tỷ số g iữ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à k hô 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à k hé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ả t hiế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 để g iả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ó t hể 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ó t hể 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ì p hâ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ó t hể có ích trong việc thiết lập hai giá t rị 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ẻ t rê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ể g iả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à t huậ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ó t hể 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ự p hâ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)  (13) f ( x , y )  2 f ( x, y ) x 2 y 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 1  x2  y2   1 2 2 2 2 2 (14)   1  e e 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ì t hế 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.61. 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   2 1/ 2  2 (15) g ( x, y )  f ( x, y )  f ( x  1, y  1)  f ( x  1, y )  f ( x, y  1) 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ý g iố 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á t rị 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ư g iá 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ề p hí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á q uá 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 ỳ t rong 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á t rị, 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ó t hể 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 ỹ t huậ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ì t hế 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ẽ g iả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