Tổng quan về xử lý ảnh
Xử lý ảnh
Xử lý ảnh là một lĩnh vực khoa học gồm tất cả những gì liên quan đến việc thao tác ảnh nhằm đưa ra được ảnh như mong muốn
Xử lý ảnh liên quan đến việc làm việc với các hình ảnh đã có, trong khi đồ họa máy tính tập trung vào việc tạo ra hình ảnh thực hoặc ảo trên máy tính Đồ họa có thể bao gồm các đối tượng hai hoặc ba chiều, trong khi xử lý ảnh có thể làm việc với nhiều hơn ba chiều.
Hình 1: Sơ đồ tổng quát của một hệ thống nhận dạng trong xử lý ảnh
Trong sơ đồ, ảnh được xử lý qua hệ thống thu nhận ảnh, bao gồm các thiết bị như camera, máy quét scanner và máy chụp hình Sau khi thu nhận, ảnh sẽ được lấy mẫu và số hóa, rồi phân tích theo các loại ảnh khác nhau Các loại ảnh được lưu trữ dưới nhiều định dạng file như Bitmap, PCX, và Gif, nhưng trong đồ án này, chỉ hiển thị ảnh dưới dạng file Bitmap Cuối cùng, ảnh sau khi phân tích sẽ được lưu trữ và phương pháp phân tích sẽ được chọn tùy theo từng ứng dụng cụ thể.
Vì vậy: Mục đích của xử lý ảnh là:
• Biến đổi ảnh và làm cho ảnh đẹp
Thu nhận ảnh Số hóa Phân tích ảnh
• Tự động phân tích nhận dạng ảnh hay đoán nhận ảnh và đánh giá các nội dung của ảnh.
Ảnh và điểm ảnh
Trong quá trình số hóa, tín hiệu liên tục được chuyển đổi thành tín hiệu rời rạc thông qua việc lấy mẫu và lượng tử hóa Điểm ảnh được coi là biểu diễn cường độ sáng hoặc một đặc trưng của ảnh tại một tọa độ nhất định Do đó, ảnh được hình thành từ một tập hợp các điểm ảnh.
Mức xám ( Gray level)
Mức xám là quá trình mã hóa cường độ sáng của mỗi điểm ảnh thành giá trị số, thường sử dụng 16, 32 hoặc 64 mức Mã hóa 256 mức, phổ biến nhất, được thực hiện bằng 8 bit, cho phép mỗi pixel có thể được mã hóa từ 0 đến 255.
Pixel ( Picture element)
Ảnh là một biểu diễn liên tục của không gian độ sáng, nhưng để xử lý ảnh bằng máy tính, cần phải số hóa chúng Quá trình này bao gồm việc chuyển đổi tín hiệu liên tục thành tín hiệu rời rạc thông qua lấy mẫu và lượng hóa, giúp phân biệt các điểm ảnh mà mắt thường không thể nhận ra Mỗi điểm ảnh được cấu thành từ các pixel, với mỗi pixel chứa một cặp tọa độ x, y và màu sắc Số lượng thông tin mà một pixel có thể lưu trữ có thể là 1, 4, 8 hoặc nhiều hơn.
Biểu diễn ảnh
Trong biểu diễn ảnh, người ta dùng các phần tử đặc trưng của ảnh là pixel
Hàm hai biến có thể được coi là chứa thông tin về biểu diễn ảnh, trong khi việc xử lý ảnh số yêu cầu mã hóa và lượng tử hóa Lượng tử hóa ảnh là quá trình chuyển đổi tín hiệu tương tự thành tín hiệu số, biến đổi ảnh đã được lấy mẫu thành một số hữu hạn mức xám.
Một số mô hình thường được dùng trong xử lý ảnh, mô hình toán, mô hình thống kê.
Tăng cường và khôi phục ảnh
Tăng cường ảnh là bước quan trọng tạo tiền đề cho xử lý ảnh, gồm một loạt các kỹ thuật như: lọc độ tương phản, khử nhiễu, nổi màu…
Khôi phục ảnh là nhằm loại bỏ các suy giảm trong ảnh.
Biến đổi ảnh
Biến đổi ảnh là một thuật ngữ chỉ các ma trận đơn vị và kỹ thuật dùng để biến đổi hình ảnh Một số loại biến đổi phổ biến bao gồm biến đổi Fourier, Sin, Cosin, Hadamard, tích Kronecker và biến đổi Karhunen-Loeve.
Phân tích ảnh
Việc xác định các độ đo định lượng của một bức ảnh là rất quan trọng để có được một mô tả đầy đủ về nội dung của nó Các kỹ thuật được áp dụng trong quá trình này chủ yếu nhằm mục đích xác định biên của ảnh, giúp cải thiện khả năng phân tích và nhận diện hình ảnh.
Nhận dạng ảnh
Quá trình mô tả các đối tượng mà người ta muốn đặc tả thường diễn ra sau khi đã trích chọn các đặc tính chủ yếu của chúng Nhận dạng là bước quan trọng giúp xác định và làm rõ các đặc điểm của đối tượng.
Có hai kiểu mô tả đối tượng đó là: mô tả tham số ( nhận dạng theo tham số ) và mô tả theo cấu trúc ( nhận dạng theo cấu trúc).
Nén ảnh
Dữ liệu ảnh, giống như các loại dữ liệu khác, cần được lưu trữ và truyền tải qua mạng, tuy nhiên, lượng thông tin để biểu diễn một bức ảnh là rất lớn Vì vậy, việc nén dữ liệu hoặc giảm lượng thông tin là một nhu cầu thiết yếu.
Các định dạng cơ bản trong xử lý ảnh
Trong xử lý ảnh, việc mã hóa ảnh thu nhận vào máy tính là cần thiết Khi lưu trữ dưới dạng tệp tin, hình ảnh sẽ được số hóa Một số định dạng ảnh phổ biến đã được chuẩn hóa bao gồm GIF, BMP, PCX, IMG và TIFF.
Ảnh IMG là loại ảnh đen trắng, trong đó phần đầu chứa 16 byte thông tin cần thiết Ảnh IMG được nén theo từng dòng, với mỗi dòng bao gồm các gói (pack) và các dòng giống nhau sẽ được nén thành một gói duy nhất.
Định dạng ảnh PCX là một trong những định dạng cổ điển, thường được sử dụng để lưu trữ hình ảnh Nó áp dụng phương pháp nén dữ liệu ảnh RLE (Run-Length-Encoding), cho phép nén và giải nén dữ liệu theo từng dòng ảnh.
• Ảnh TIFF: Là ảnh mà dữ liệu chứa trong tệp thường được tổ chức thành các nhóm dòng ( cột) quét của dữ liệu ảnh
Định dạng ảnh GIF (Graphics Interchange Format) khắc phục những vấn đề mà các định dạng khác gặp phải khi số lượng ảnh tăng lên GIF cung cấp chất lượng hình ảnh cao với độ phân giải đồ họa tốt, cho phép hiển thị trên hầu hết các thiết bị phần cứng.
• Ảnh BMP ( Windows Bitmap): Là một định dạng tập tin hình ảnh khá phổ biến, cấu trúc tập tin ảnh bao gồm 4 phần:
•• Bitmap Header (14 bytes): giúp nhận dạng tập tin bitmap
•• Bitmap Information (40 bytes): lưu một số thông tin chi tiết giúp hiển thị ảnh
•• Color Palette (4*x bytes), x là số màu của ảnh: định nghĩa các màu sẽ được sử dụng trong ảnh
•• Bitmap Data: lưu dữ liệu ảnh.
Một số khái niệm cơ bản trong phát hiện biên
Khái niệm biên
Biên là ranh giới phân biệt giữa các đối tượng trong ảnh, đóng vai trò quan trọng trong phân tích hình ảnh Một điểm ảnh được coi là biên khi có sự thay đổi đột ngột về mức xám Tập hợp các điểm biên sẽ tạo thành đường bao của ảnh Cụ thể, một điểm được xác định là biên nếu nó là điểm đen và có ít nhất một điểm trắng lân cận.
Tại sao phải tìm biên
Tìm biên là quá trình làm nổi bật các điểm ảnh có sự biến đổi lớn về độ sáng so với xung quanh, đóng vai trò quan trọng trong phân tích ảnh Việc này cần thiết để khắc phục tình trạng suy biến của ảnh do nhiều nguyên nhân khác nhau, nhằm tăng cường và khôi phục lại chất lượng hình ảnh.
Tìm biên là quá trình xác định các đường bao quanh của đối tượng, giúp tăng cường độ tương phản giữa biên và nền, từ đó làm cho biên trở nên dễ dàng nhận diện.
Hiện nay, có nhiều định nghĩa về đường biên, mỗi định nghĩa áp dụng trong những trường hợp cụ thể Ba loại đường biên chính bao gồm: đường biên lý tưởng, đường biên bậc thang và đường biên thực (không trơn).
Hình 2: Các đường biên a, Đường biên lý tưởng b, Đường biên bậc thang c, Đường biên thực
Đường biên lý tưởng là sự thay đổi giá trị cấp xám tại một vị trí xác định trong ảnh Khi sự thay đổi cấp xám giữa các vùng trong ảnh lớn, đường biên sẽ dễ dàng nhận ra hơn Trong trường hợp này, sự thay đổi xảy ra tại một điểm, do đó, đường biên có độ rộng bằng một điểm ảnh và vị trí của đường biên chính là nơi xảy ra sự thay đổi cấp xám.
Đường biên bậc thang xuất hiện khi có sự thay đổi cấp xám qua nhiều điểm ảnh, với vị trí của nó là điểm chính giữa giữa cấp xám thấp và cao Trong toán học, đường biên được xem là một đường thẳng, nhưng khi ảnh được số hóa, nó trở thành những đường không trơn, phản ánh sự phức tạp trong quá trình xử lý hình ảnh.
• Đường biên thực ( không trơn) Đường biên thực xuất hiện khi sự thay đổi cấp xám tại nhiều điểm ảnh nhưng không trơn.
Các khái niệm về nhiễu
Trong thực tế, nhiễu luôn tồn tại và xuất hiện một cách ngẫu nhiên, khiến việc dự đoán nhiễu trở nên khó khăn Tuy nhiên, chúng ta có thể mô tả nhiễu dựa trên độ lệch tiêu chuẩn và giá trị trung bình của nó Trong phân tích ảnh, hai loại nhiễu chính mà chúng ta cần chú ý là nhiễu độc lập tín hiệu (nhiễu cộng).
Nhiễu ảnh là một tập hợp ngẫu nhiên các mức xám độc lập với dữ liệu ảnh, được cộng thêm vào các điểm ảnh, dẫn đến việc ảnh bị nhiễu Loại nhiễu này thường xảy ra khi ảnh được truyền điện tử từ nơi này đến nơi khác Nếu A là ảnh không nhiễu và N là nhiễu xuất hiện trong quá trình truyền, thì ảnh A' có nhiễu sẽ được tính bằng công thức A' = A + N.
Với A và N là hai biến độc lập, giả thuyết cho rằng nhiễu N có thể có các thuộc tính thống kê khác nhau Tuy nhiên, trong trường hợp chung, N được giả định tuân theo phân bố chuẩn với trung bình bằng 0 và độ lệch tiêu chuẩn đã được xác định.
Việc tạo ra ảnh nhiễu nhân tạo với các đặc trưng đã được xác định không phải là điều quá phức tạp Những bức ảnh này đóng vai trò quan trọng trong việc kiểm chứng các thuật toán phát hiện biên, đặc biệt là trong trường hợp nhiễu phụ thuộc tín hiệu.
Trong trường hợp này, giá trị nhiễu tại mỗi điểm ảnh được xác định bởi mức xám tại điểm đó Loại nhiễu này thường khó ước lượng nhưng ít quan trọng hơn và có thể được kiểm soát hiệu quả nếu thực hiện việc lấy mẫu ảnh một cách hợp lý.
Khi ảnh được nhập chính xác, việc kiểm soát nhiễu trở nên hiệu quả Nếu A là ảnh không nhiễu và N là nhiễu xuất hiện trong quá trình truyền tải, thì ảnh A' có nhiễu được tính bằng công thức: A' = A * N.
Quy trình phát hiện biên
B1: Do ảnh ghi được thường có nhiễu, vì vậy cần lọc bỏ nhiễu theo các phương pháp đã tìm hiểu ở trên
B2: Làm nổi biên sử dụng các toán tử phát hiện biên
B3: Định vị biên là một kỹ thuật quan trọng, nhưng cần lưu ý rằng việc làm nổi biên có thể gây ra tác dụng phụ, dẫn đến sự xuất hiện của một số biên giả Do đó, việc loại bỏ các biên giả này là cần thiết để đảm bảo độ chính xác trong quá trình xử lý.
B4: Liên kết và trích chọn biên.
Các phương pháp đánh giá thuật toán phát hiện biên
Đánh giá Pratt
Dựa vào những phân tích trên, năm 1978 Pratt đã đề xuất ra hàm :
Trong đó: I A : số lượng điểm biên tìm được bằng phương pháp tìm biên
Số lượng các điểm biên thực sự trên ảnh thử nghiệm được ký hiệu là i, trong khi d(i) đại diện cho khoảng cách giữa điểm thứ i trên ảnh thử nghiệm và các điểm tìm biên do phương pháp xác định Hằng số α = 1/9 được Pratt đề xuất Giá trị E là một hàm của khoảng cách giữa vị trí biên đo được và vị trí thực tế, tuy nhiên nó chỉ liên quan gián tiếp đến lỗi âm và lỗi dương.
Đánh giá Kitchen-Rosenfeld
Năm 1981, Kitchen và Rosenfeld đã giới thiệu một mô hình đánh giá dựa trên tính liên kết cục bộ của biên, tập trung vào độ lệch giữa một điểm biên và các điểm biên láng giềng, thay vì vị trí thực tế của biên Phương pháp này bổ sung cho phương pháp Pratt, với bước đầu tiên là xác định một hàm để kiểm tra sự xuất hiện của điểm biên lân cận bên trái.
Nếu láng giềng K là một điểm biên
Trong bài viết này, chúng ta sẽ xem xét các khái niệm về hướng của biên tại một điểm cụ thể, bao gồm các hướng d, d0 và d1 Hướng d0 đại diện cho biên tại điểm láng giềng bên phải, trong khi d1 là hướng của láng giềng bên phải theo chiều ngược kim đồng hồ Hàm a được định nghĩa để đo độ lệch góc giữa hai góc bất kỳ, a(α, β) Ngoài ra, còn có một hàm tương tự để đo hướng liên tục về phía bên phải của điểm biên đang xét.
Nếu láng giềng K là một điểm biên
Trong trường hợp khác, độ đo sự tiếp tục được xác định bằng trung bình các giá trị lớn nhất của L(K) và R(K), được gọi là C Biên phải được thể hiện bằng một đường mảnh có độ rộng một pixel, trong khi các biên có độ rộng lớn hơn một pixel cho thấy sự xuất hiện của lỗi âm, có thể do thuật toán phát hiện nhiều lần cùng một biên thực Độ mảnh T được xác định là 6 điểm ảnh trong một vùng ảnh kích thước 3x3, với tâm là điểm ảnh đang xét, và bỏ qua tâm vùng cùng hai điểm ảnh được xác định bởi L(K) và R(K) là các điểm biên Ước lượng tổng thể của phương pháp phát hiện biên được trình bày như sau.
E 2 = γ C+(1- γ) T Trong đó : γ là một hằng số và ở đây sử dụng: γ = 0,8
CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN CỔ ĐIỂN
Cơ sở về các phép toán tìm biên
Tìm biên là quá trình xác định các đường bao quanh đối tượng trong ảnh, nhưng thường gặp khó khăn do nhiễu Trước khi áp dụng các thuật toán tìm biên, cần thực hiện bước tiền xử lý để loại bỏ nhiễu Phương pháp tìm biên dựa trên sự biến đổi lớn về giá trị độ sáng của các điểm ảnh khi đi qua biên, trong khi sự biến đổi này ở các điểm thuộc đối tượng là nhỏ Do đó, việc làm nổi bật các điểm ảnh có sự biến đổi lớn về độ sáng ở các vùng đồng nhất sẽ giúp xác định biên ảnh Từ đó, có hai phương pháp phát hiện biên chính: phương pháp tìm biên trực tiếp và phương pháp tìm biên gián tiếp.
Phương pháp tìm biên trực tiếp là kỹ thuật phát hiện biên dựa vào sự biến thiên độ sáng của điểm ảnh Kỹ thuật này sử dụng đạo hàm, trong đó đạo hàm bậc nhất cho ra các phương pháp như Gradient, Sobel và Prewitt, trong khi đạo hàm bậc hai sử dụng kỹ thuật Laplace Các phương pháp này sẽ được mô tả chi tiết hơn ở phần dưới.
Phương pháp tìm biên gián tiếp là kỹ thuật phân chia ảnh thành các vùng, trong đó các điểm ảnh có đặc điểm tương đồng Ranh giới giữa những vùng này được xác định là biên, giúp nhận diện và phân tích cấu trúc của ảnh một cách hiệu quả.
Phương pháp phát hiện biên trực tiếp và gián tiếp là hai bài toán đối lập, với khả năng xác định biên từ các vùng đã biết và ngược lại Tuy nhiên, trong một số trường hợp, việc xác định biên có thể gặp khó khăn, chẳng hạn như trong tình huống biên hở.
Phương pháp tìm biên trực tiếp thường hiệu quả với các ảnh ít bị nhiễu, nhưng lại kém hiệu quả khi độ sáng biến thiên không đột ngột Ngược lại, phương pháp tìm biên gián tiếp xử lý tốt trong những trường hợp này, mặc dù cài đặt tương đối phức tạp Trong phương pháp tìm biên trực tiếp, có hai dạng chính cần được xem xét.
Phương pháp tìm biên bằng bộ lọc tuyến tính bao gồm hai cách tiếp cận chính: xử lý lân cận cục bộ và xử lý tổng thể Xử lý lân cận sử dụng các ma trận hệ số lọc nhỏ, trong khi xử lý tổng thể thực hiện trên toàn bộ ảnh, tương đương với việc sử dụng ma trận hệ số lọc có kích thước bằng kích thước của ảnh Các phương pháp nổi bật trong nhóm này bao gồm Gradient, Sobel, Prewitt và Laplace.
Phương pháp tìm biên phi tuyến không dựa vào lọc tuyến tính mà thay vào đó sử dụng các phép toán phi tuyến như lựa chọn và so sánh Các phép toán này được áp dụng trong các phương pháp như hình chóp và Kisrch.
Sau khi xác định các khái niệm cơ bản cho phương pháp tách cạnh, câu hỏi đặt ra là làm thế nào để phát hiện cạnh Cạnh được định nghĩa là sự thay đổi cấp xám hoặc thay đổi chu tuyến màu, thể hiện qua sự biến thiên ngẫu nhiên và phức tạp của các mức xám Mỗi cạnh có một giá trị Gradient nhất định; khi Gradient tại một điểm lớn, sự thay đổi cấp xám cũng lớn, cho phép nhận diện cạnh Để phát hiện cạnh, có thể sử dụng toán tử đạo hàm (phương pháp phát hiện biên trực tiếp) để nhận dạng những nơi có sự thay đổi cường độ lớn, hoặc áp dụng phương pháp dựa mẫu, nơi cạnh được mô hình hóa bởi một mẫu nhỏ.
Cạnh trong hình ảnh được xác định bởi sự thay đổi cấp xám, và toán tử nhạy cảm với sự thay đổi này chính là toán tử đạo hàm Toán tử đạo hàm thể hiện tốc độ thay đổi của hàm số, với tốc độ thay đổi cấp xám lớn ở gần các cạnh và nhỏ trong các khu vực có cấp xám ổn định.
Khi làm việc với ảnh hai chiều, cần xem xét sự thay đổi cấp xám theo nhiều hướng khác nhau Do đó, đạo hàm riêng theo hai hướng x và y được áp dụng để đánh giá hướng của cạnh Bằng cách sử dụng đạo hàm x và y như các thành phần hướng cạnh, ta có thể tính toán vector tổng Toán tử liên quan đến đạo hàm trong trường hợp này là Gradient, và nếu coi ảnh như một hàm hai biến A(x, y), thì Gradient được định nghĩa một cách cụ thể.
A đây là một vector hai chiều
Ảnh không phải là một hàm và không thể được vi phân hóa theo cách thông thường Thay vào đó, chúng ta sử dụng sai phân để xấp xỉ đạo hàm, vì ảnh số là tín hiệu rời rạc, do đó đạo hàm không tồn tại Một xấp xỉ đơn giản là toán tử 1: x1A(x, y) = A(x, y) - A(x-1, y) và y1A(x, y) = A(x, y) - A(x, y-1).
Trong trường hợp các cấp xám biến đổi giữa các điểm ảnh là tuyến tính, giá trị đạo hàm thể hiện độ nghiêng của đường thẳng Các phương pháp sử dụng đạo hàm bậc nhất hoạt động hiệu quả khi độ sáng thay đổi rõ rệt Tuy nhiên, khi mức xám thay đổi chậm và miền chuyển tiếp trải rộng, phương pháp sử dụng đạo hàm bậc hai sẽ mang lại hiệu quả tốt hơn Lúc này, toán tử 2 sẽ được xấp xỉ với các đạo hàm bậc hai.
Toán tử này đối xứng với điểm ảnh (x, y) mà không xét đến giá trị của điểm ảnh tại đó Bất kỳ toán tử nào tính Gradient đều cho ra vector chứa thông tin về độ lớn và hướng của Gradient tại điểm ảnh Độ lớn của vector Gradient được xác định bởi độ dài cạnh huyền của tam giác với hai cạnh còn lại là x và y, phản ánh độ lớn tại điểm ảnh Hướng của cạnh tại mỗi điểm ảnh được xác định bởi góc giữa cạnh huyền và các trục x, y Công thức tính độ lớn gradient là
Và hướng của cạnh xấp xỉ bằng: Gdir = arctg x A y
Độ lớn của cạnh được xác định là một số thực, thường làm tròn thành số nguyên Điểm ảnh có gradient vượt quá ngưỡng xác định được coi là điểm cạnh, trong khi các điểm khác không được xem là như vậy Hai toán tử tách cạnh sẽ sử dụng giá trị trung vị trong khoảng các cấp xám làm ngưỡng Trong phần tiếp theo, tôi sẽ trình bày chi tiết các phương pháp tìm biên.
Phương pháp tìm biên dựa trên kĩ thuật lọc tuyến tính
Kỹ thuật lọc tuyến tính là quá trình xếp chồng ảnh đầu vào với hạt nhân tương ứng, dựa trên hai phép toán cơ bản: phương pháp Gradient và phương pháp Laplace Mỗi phương pháp này thường trải qua các giai đoạn chính để xác định biên.
• Chọn toán tử thực hiện
• Chọn phương pháp xác định điểm biên
• Liên kết các điểm biên
Sau đây các phép toán tìm biên sẽ được trình bày
2.2.1 Phương pháp đạo hàm bậc nhất Gradient
Phương pháp Gradient là kỹ thuật dò biên cục bộ dựa vào cực đại của đạo hàm Gradient được định nghĩa là một vector có các thành phần thể hiện tốc độ thay đổi giá trị của điểm ảnh theo hai hướng x và y Các thành phần của Gradient được tính bằng công thức: \( f(x, y) = \frac{\partial f}{\partial x} \) và \( f(x, y) = \frac{\partial f}{\partial y} \).
Với dx, dy là các khoảng cách giữa các điểm theo hướng x và hướng y ( tính theo số điểm) Trong thực tế người ta hay dùng với dx= dy =1
Với một ảnh liên tục f(x,y), các đạo hàm riêng giúp xác định vị trí cực đại cục bộ theo hướng biên Gradient của ảnh này được biểu diễn bởi hàm f(x,y) dọc theo r, với góc θ được định nghĩa theo tọa độ cực.
Ta có: f( x, y) = f( r cos θ, r sin θ) dr dy x f dr dx x f dr df -f x cos θ + f y sin θ d dy y f d dx x f d df -f x r sin θ + f y r.cos θ
Hướng xảy ra khi: 0 d df
- f x r sin θ + f y r cos θ =0 tg θ fy fx θ = arctg fy fx
Và max d df = fx 2 fy 2
Khi đó θ r là hướng của biên
Mặc dù chúng ta thường nói về việc lấy đạo hàm của ảnh, thực chất chỉ là mô phỏng và xấp xỉ đạo hàm thông qua kỹ thuật nhân chập Bởi vì ảnh số là tín hiệu rời rạc, nên khái niệm đạo hàm không thực sự tồn tại trong trường hợp này.
Các bước tiến hành như sau:
2 Với mỗi điểm ảnh I(x, y) ta tính Gradient I(x, y):
3 Tìm các điểm biên I'(x, y) = Gradient I(x, y)
Khi gradient I(x, y) nhỏ hơn hoặc bằng θ, đạo hàm I'(x, y) sẽ bằng 0 Việc xấp xỉ đạo hàm bậc nhất theo các hướng x và y được thực hiện thông qua hai mặt nạ nhân chập tương ứng, từ đó cho phép phát hiện biên hiệu quả Phương pháp này cũng có thể tạo ra nhiều mặt nạ khác nhau bằng cách áp dụng kỹ thuật lấy đạo hàm trái, phải và trung tâm.
Các bước tiến hành như sau:
1 Với mỗi điểm ảnh I(x, y) ta tính:
2.2.2 Phương pháp đạo hàm bậc 2 Laplace
Các phương pháp lấy đạo hàm bậc 1 hiệu quả khi độ sáng thay đổi rõ nét, nhưng khi mức xám thay đổi chậm và miền chuyển tiếp trải rộng, phương pháp sử dụng đạo hàm bậc 2, hay còn gọi là phương pháp Laplace, sẽ mang lại hiệu quả cao hơn Toán tử Laplace được định nghĩa như sau:
Toán tử Laplace sử dụng nhiều loại mặt nạ khác nhau để xấp xỉ rời rạc đạo hàm bậc hai, với công thức: 2f = f(x+1, y) + f(x, y+1) - 4f(x, y) + f(x-1, y) + f(x, y-1) Dưới đây là các kiểu mặt nạ thường được áp dụng trong thực tiễn.
Các bước tiến hành như sau:
1 Với mỗi điểm ảnh I(x, y) ta tính:
2 Tìm các điểm biên I'(x, y) = Ibiên(x, y)
Một số phương pháp tìm biên phi tuyến
Các toán tử tìm biên được trình bày là các toán tử tuyến tính tổng quát, cho phép tạo ra ảnh đầu ra từ ảnh đầu vào thông qua tổ hợp tuyến tính của các điểm với hệ số bộ lọc tương ứng Quá trình này không bao gồm các bước trung gian như so sánh, sắp xếp hay lựa chọn, cũng như không có các phép tính phân chia phức tạp Bài viết sẽ giới thiệu một số kỹ thuật cơ bản theo phương pháp này.
2.3.1 Phương pháp tìm biên theo hình chóp ( pyramid edge detection)
Trong một số trường hợp, ảnh có thể chứa nhiều loại đường biên, bao gồm đường biên dài, ngắn, hoặc không có đường biên Để cải thiện chất lượng hình ảnh, cần loại bỏ các đường biên không quan trọng như đường biên ngắn, mờ và không kết nối, đồng thời làm nổi bật các đường biên đậm và dài Một giải pháp hiệu quả cho vấn đề này là phương pháp tìm biên theo hình chóp, giúp xác định và giữ lại những đường biên thực sự quan trọng trong ảnh.
Ảnh gốc được chia thành 4 phần bằng cách chia đôi độ dài mỗi chiều Mỗi giá trị điểm ảnh trong ảnh nhỏ một phần tư mới được tính bằng trung bình cộng của bốn điểm ảnh tương ứng trong ảnh gốc, theo công thức đã được xác định.
• Cứ thế lặp lại cho đến khi ảnh mới được tạo ra, với biên thực đã được phát hiện, còn các biên khác thì mất
Sử dụng phương pháp tìm biên cho ảnh nhỏ nhất, sau đó áp dụng lại phương pháp này tại các điểm biên đã phát hiện để xác định bốn điểm tương ứng trong ảnh lớn.
• Quá trình cứ tiếp tục được thực hiện cho đến khi đường biên thực của ảnh gốc được xuất hiện
Quá trình thực hiện này giúp làm mờ các đường biên ngắn và không rõ ràng, đồng thời làm nổi bật các đường biên thực sự Mỗi bước tìm kiếm biên từ ảnh nhỏ chỉ tập trung vào những điểm đã xác định là biên, bỏ qua các điểm không phải biên, mặc dù chúng vẫn có thể tạo ra biên trong một số trường hợp.
4 điểm tương ứng của nó trong ảnh lớn Ta xét ví dụ sau:
Từ ảnh gốc I new ( chia 4) ( B)
Nếu chọn ngưỡng là 1.5 thì ta có biên :
Với mỗi biên của B ta lại tìm biên với 4 điểm tương ứng của nó trên ảnh gốc, khi đó sẽ được biên thực là C:
2.3.2 Phương pháp toán tử tìm biên la bàn Kirsch
Toán tử này được xây dựng trên cơ sở cửa số (3 x 3, 5 x 5, ….)
Cửa sổ 3 x 3 được mô tả như sau: Mỗi điểm ảnh đầu ra là giá trị lớn nhất trong 8 kết quả xếp chồng của cửa sổ với ma trận ảnh Sau mỗi lần xếp chồng, cửa sổ lọc sẽ được quay một góc 45 độ để sử dụng cho lần xếp chồng tiếp theo.
Lần 1 dùng cửa sổ xếp chồng sau:
Lần 2 quay cửa sổ đi một góc 45 0 thu được mặt nạ:
Lần thứ 8 sau lần quay đầu tiên (a) đi một góc 315 0 là:
Giá trị lớn nhất trong 8 lần xếp chồng tương ứng với một điểm ảnh sẽ xác định kết quả điểm ảnh đầu ra, được mô tả qua phép toán h(p) = [max {|5*.
Trong bài viết này, phép toán a, b được xác định là phần dư của phép chia (a+b) cho 8, trong khi F(j) đại diện cho giá trị của phần dư thứ j trong cửa sổ lọc Các phần tử trong cửa sổ lọc được sắp xếp theo chiều kim đồng hồ, với phần tử thứ 9 đóng vai trò là phần tử trung tâm.
Kỹ thuật dò biên tổng quát
2.4.1 Các khái niệm cơ bản
Ảnh là một mảng số thực 2 chiều (Iij) với kích thước (m n), trong đó mỗi phần tử Iij (i = 0, ,m; j = 0, ,n) đại diện cho mức xám tại tọa độ (i,j) Ảnh được gọi là nhị phân khi các giá trị Iij chỉ nhận 0 hoặc 1 Chúng ta chỉ xem xét ảnh nhị phân, vì bất kỳ ảnh nào cũng có thể chuyển đổi về dạng nhị phân thông qua quá trình phân ngưỡng Trong đó, tập hợp các điểm có giá trị 1 được gọi là điểm vùng, và tập hợp các điểm có giá trị 0 được gọi là điểm nền.
• Các điểm 4 và 8-láng giềng
Giả sử (i,j) là một điểm ảnh, các điểm 4-láng giềng là các điểm kề trên, dưới, trái, phải của điểm (i, j) :
Và những điểm 8-láng giềng gồm:
Trên hình 1 các điểm P 0 , P2, P4, P6 là các 4-láng giềng của điểm P, còn các điểm P 0 , P1, P2, P3, P4, P5, P6, P7 là các 8-láng giềng của P
Hình 3 Ma trận 8-láng giềng kề nhau
Cho 1 dãy P 1 , P 2 ……… Pn là một dãy liên thông khi P n P 1
4 - liên thông: Khi các P là liên thông 4 láng giềng và nó là một láng giềng
8 - liên thông: Khi nó là một chu trình và các P là liên thông 8 láng giềng
• Chu tuyến của một đối tƣợng ảnh
Chu tuyến của một đối tượng ảnh là dãy các điểm P1,…,Pn, trong đó mỗi điểm Pi và Pi+1 là các 8-láng giềng của nhau (i=1,…,n-1), và điểm P1 cũng là 8-láng giềng của điểm cuối cùng trong chu tuyến.
Pn, i Q không thuộc đối tượng ảnh và Q là 4-láng giềng của Pi (hay nói cách khác i thì Pi là biên 4) Kí hiệu
Tổng các khoảng cách giữa hai điểm liên tiếp trong chu tuyến được gọi là độ dài của chu tuyến, ký hiệu là Len(C) Hướng giữa hai điểm Pi và Pi+1 được xác định là chẵn nếu chúng là các điểm láng giềng, ngược lại, nếu không phải là láng giềng, thì hướng này được coi là lẻ.
Hình 4 Ví dụ về chu tuyến của đối tƣợng ảnh
2.4.2 Các kỹ thuật dò biên a, Kỹ thuật Freeman
Tư tưởng: Xuất phát từ một điểm bất kỳ, nếu gặp trắng thì rẽ trái, gặp đen thì rẽ phải
Cải tiến kỹ thuật trên ( Đỗ Ngọc Kỷ - 1992 ) đưa ra: Gặp trắng rẽ trái, gặp đen lùi lại và rẽ phải b, Kỹ thuật nới lỏng
Tạo khớp điểm ảnh giữa các biên của ảnh, với điều kiện rằng hai điểm P và Q sẽ tạo thành khớp khi và chỉ khi thỏa mãn các tiêu chí nhất định.
| I P - I Q | ≥ θ ( θ là ngưỡng ) c, Kỹ thuật dò biên theo cặp nền - vùng
Biểu diễn đối tượng ảnh theo chu tuyến thường dựa trên các kỹ thuật dò biên
Có hai kỹ thuật dò biên cơ bản Kỹ thuật đầu tiên là phân tích ảnh biên từ ảnh vùng sau khi đã qua một lần duyệt, coi nó như một đồ thị và sau đó áp dụng các thuật toán duyệt cạnh của đồ thị.
Kỹ thuật thứ hai dựa trên ảnh vùng, kết hợp đồng thời quá trình dò biên và tách biên Ở đây ta quan tâm cách tiếp cận thứ hai
Bài viết đề cập đến việc xem xét một vùng ảnh 8-liên thông được bao quanh bởi các điểm nền, trong khi vùng 4-liên thông được coi là trường hợp đối ngẫu.
Về cơ bản, các thuật toán dò biên trên một vùng đều bao gồm các bước sau:
Xác định điểm biên xuất phát
Dự báo và xác định điểm biên tiếp theo Lặp bước 2 cho đến khi gặp điểm xuất phát
Các thuật toán dò biên tạo ra những đường biên đa dạng do sự khác biệt trong tiêu chuẩn và định nghĩa về điểm biên cũng như quan hệ liên thông.
Kết quả của toán tử dò biên tại điểm biên r_i dẫn đến điểm biên r_{i+1}, là một trong các 8-láng giềng của r_i Các toán tử này thường được xây dựng dưới dạng hàm đại số Boolean dựa trên các 8-láng giềng của r_i, và sự xây dựng này phụ thuộc vào định nghĩa về quan hệ liên thông và điểm biên, gây khó khăn trong việc khảo sát các đặc tính của đường biên Thêm vào đó, mỗi bước dò biên cần kiểm tra tất cả các 8-láng giềng của từng điểm, dẫn đến hiệu suất thuật toán thấp Để khắc phục những hạn chế này, thay vì chỉ sử dụng một điểm biên, ta áp dụng cặp điểm biên (một thuộc A), tạo thành tập nền vùng được ký hiệu là NV, và phân tích toán tử dò biên thành hai bước.
Xác định cặp điểm nền vùng tiếp theo
Lựa chọn điểm biên Trong đó bước thứ nhất thực hiện chức năng của một ánh xạ trên tập NV lên
NV và bước thứ hai thực hiện chức năng chọn điểm biên
Thuật toán dò biên tổng quát
Bước 1: Xác định cặp nền-vùng xuất phát
Bước 2: Xác định cặp nền-vùng tiếp theo
Bước 3: Lựa chọn điểm biên
Bước 4: Nếu gặp lại cặp xuất phát thì dừng, nếu không quay lại bước 2
Việc xác định cặp nền-vùng xuất phát được thực hiện bằng cách duyệt ảnh từ trên xuống dưới và từ trái qua phải, sau đó kiểm tra điều kiện chọn cặp nền-vùng Vì việc chọn điểm biên chỉ mang tính chất quy ước, ánh xạ xác định cặp nền-vùng tiếp theo được gọi là toán tử dò biên.
Giả sử T là một ánh xạ như sau: T : NV NV
(b, r) (b', r' ) Gọi T là một toán tử dò biên cơ sở nếu nó thoả mãn điều kiện: b’,r’ là các 8- láng giềng của r
Giả sử (b,r) NV; gọi K(b,r) là hàm chọn điểm biên Biên của một dạng có thể định nghĩa theo một trong ba cách:
Tập những điểm thuộc có mặt trên NV, tức là K(b,r)= r
Tập những điểm thuộc A có trên NV, tức là K(b,r)= b
Tập những điểm ảo nằm giữa cặp nền-vùng, tức là K(b,r) là những điểm nằm giữa hai điểm b và r
Cách định nghĩa thứ ba liên kết mỗi cặp nền-vùng với một điểm biên riêng biệt, trong khi cách định nghĩa thứ nhất và thứ hai cho phép một số cặp nền-vùng chia sẻ cùng một điểm biên.
PHƯƠNG PHÁP PHÁT HIỆN BIÊN DỰA VÀO
Các phép toán hình thái cơ bản
Hình thái học là lĩnh vực nghiên cứu cấu trúc và hình học topo của đối tượng trong ảnh Các phép toán hình thái chủ yếu được xây dựng dựa trên hai phép toán cơ bản: phép "giãn" (Dilation) và phép "co" (Erosion) Những phép toán này đóng vai trò quan trọng trong việc phân tích và xử lý hình ảnh.
Cho I (x, y) là một ảnh, T ( i, j ) là một ma trận mẫu a, Định nghĩa Dilation
Với ảnh đa cấp xám: D (x, y) I = I T(x, y) = Max( I (x-i, y-j) + T(i, j) )
Hoặc D(I) = Max ( I (x-i, y-j) + T' (i, j) ) với T' = Rot 180 ( T ) b, Định nghĩa Erosion
Với ảnh đa cấp xám: E (x, y) I = I T(x, y) = Min ( I (x-i, y-j) - T(i, j) ) c, Định nghĩa OPEN
Phép toán mở (OPEN) của I theo T là tập hợp các điểm của ảnh I sau khi đã co và giãn nở liên liếp theo T.
Phép toán đóng (CLOSE) của I theo cấu trúc T là tập hợp các điểm của ảnh I sau khi đã giãn nở và co liên liếp theo T
Cho ảnh: Ma trận mẫu:
Thuật toán phát hiện biên dựa vào phép toán hình thái
Giả thiết E (D(I))= (I T) T có thể xem như là một tập xấp xỉ trên của tập
Và D (E(I)) = (I T) T thể xem như là một tập xấp xỉ dưới của tập I theo mẫu T
Tập CLOSE (I, T) và OPEN (I, T) được coi là xấp xỉ biên của tập I theo mẫu T, ký hiệu quá trình xấp xỉ này là I © T Để đạt được kết quả chính xác, việc xác định biên cần phải thực hiện một cách đối xứng, dẫn đến việc định nghĩa một dãy các phần tử cấu trúc.
Trong đó T i và T i-1 được quay đi một góc và được sử dụng lần lượt theo trình tự I © {T} = n i 1
Thuật toán phát hiện biên:
Vào: Ma trận ảnh I và dãy mẫu T = { T i , 1≤ i≤ n}
Ra: Biên của đối tượng theo mẫu T
CLOSE (I, T) = (I T) T Xấp xỉ trên của I ( chứa I )
OPEN (I, T) = (I T) T Xấp xỉ dưới của I ( thuộc I )
I © T = CLOSE (I, T) \ OPEN (I,T) Xấp xỉ biên của I theo mẫu T
Ứng dụng của các phép toán hình thái trong nhận dạng biên ảnh 32 CHƯƠNG IV: MỘT SỐ PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG
Biên, hay còn gọi là đường biên, là các đường giới hạn của các đối tượng trong ảnh, thể hiện ranh giới giữa đối tượng và nền Việc xác định ranh giới này dựa vào các điểm thuộc đối tượng và nền, cho phép chúng ta xác định biên thông qua các phép toán hình thái.
Những điểm ảnh trên biên của một đối tượng là những điểm ảnh có ít nhất một điểm ảnh lân cận thuộc nền Việc xác định lân cận nền cần được tìm kiếm, và không thể tạo ra một cấu trúc đơn giản để thực hiện phép co hoặc phép dãn dò ra biên Mặc dù một phép co bằng phần tử cấu trúc đơn giản có thể xoá những điểm biên, nhưng điều này có thể được áp dụng để thiết kế một phép toán hình thái dò biên Biên có thể được tách ra bằng cách sử dụng phép co, sau đó ảnh được co sẽ được trừ đi bởi ảnh gốc, để lại những điểm ảnh đã được co, chính là biên.
Hình 5 : Kết quả làm mảnh a) Ảnh ban đầu b) Áp dụng Erosion c) Ảnh ban đầu – đi ảnh đã biến đổi
CHƯƠNG IV: MỘT SỐ PHƯƠNG PHÁP PHÁT HIỆN BIÊN NÂNG CAO
Ngoài các phương pháp phát hiện biên đã được đề cập trong chương 2, còn có một số phương pháp phức tạp và hiệu quả hơn, sử dụng mô hình toán học của biên Một số phương pháp tiêu biểu bao gồm Canny, Shen-Castan và Marr-Hildreth Bài viết này sẽ tóm lược một số phương pháp này.
Phương pháp Canny
4.1.1 Cơ sở lý thuyết của thuật toán a, Nguyên lý của thuật toán
Năm 1986, Canny tại phòng thí nghiệm MIT đã phát triển một phương pháp phát hiện biên nổi tiếng Ông đã xác định một tập hợp các mục tiêu cho phương pháp này và đề xuất một cách tối ưu để đạt được những mục tiêu đó, được biết đến với tên gọi là phương pháp Canny.
Canny đưa ra ba điểm chính mà một phương pháp phát hiện biên phải xác định được đó là:
Mức lỗi trong phương pháp cần đảm bảo hiệu quả chỉ tại các điểm biên, do đó phải xác định tất cả các biên mà không bỏ sót Để đạt được điều này, khoảng cách giữa các điểm biên được tìm thấy trong thuật toán và biên thực tế cần phải được tối thiểu hóa.
Hiệu suất của phương pháp phát hiện biên không được phép chỉ ra nhiều biên khi chỉ có một biên tồn tại Canny giả định rằng nhiễu trong ảnh tuân theo phân bố Gauss và cho rằng phương pháp tìm biên thực chất là một bộ lọc nhân xoắn có khả năng làm mịn nhiễu và xác định cạnh Vấn đề đặt ra là tìm ra bộ lọc tối ưu nhất, đáp ứng ba tiêu chuẩn đã đề ra.
Về mặt một chiều, đáp ứng của bộ lọc f với biên G được tính bởi tích phân chập:
G ( -x ) f ( x ) dx ở đây ta giả sử đáp ứng của bộ lọc ở ngoài khoảng [ -w, w ] là bằng 0 Ba tiêu chuẩn trên được biểu diễn toán học như sau:
The Signal-to-Noise Ratio (SNR) is the ratio of the output signal to the noise, also known as the error rate A higher SNR value is desirable, as it indicates a greater amount of signal and less interference.
Giá trị Localization thể hiện mối quan hệ nghịch đảo giữa khoảng cách từ biên tìm được đến biên thực Giá trị này càng lớn thì khoảng cách từ biên tìm được đến biên thực càng nhỏ, điều này đồng nghĩa với việc đạt được độ chính xác cao hơn trong quá trình xác định biên.
Giá trị X ZC là một ràng buộc quan trọng, thể hiện khoảng cách trung bình giữa các điểm 0 và f' Điều này có nghĩa là trong một khu vực nhỏ, sẽ không có nhiều sự đáp ứng của f đối với cùng một biên.
Canny đã phát triển bộ lọc f nhằm tối ưu hóa tỷ số tín hiệu trên nhiễu (SNR) trong xLocalization, đồng thời đáp ứng ràng buộc X ZC Do kết quả quá phức tạp để biểu diễn một cách giải tích, ông đã đưa ra một xấp xỉ hiệu quả, đó là đạo hàm bậc nhất của hàm Gaussian Hàm Gaussian có dạng cụ thể như sau:
2 x Đạo hàm bậc nhất của Gaussian theo x của G(x):
Hàm Gaussian trong không gian hai chiều có dạng sau:
Đạo hàm của hàm G theo cả hai hướng x và y cho phép xây dựng bộ lọc tối ưu Canny trong phát hiện biên Việc nhân chập ảnh đầu vào với G' tạo ra ảnh E, giúp cải thiện rõ rệt các đường biên, ngay cả khi có nhiễu xuất hiện.
Nhân xoắn là một phép toán dễ thực hiện nhưng có chi phí tính toán cao, đặc biệt với mảng hai chiều Tuy nhiên, phép nhân xoắn với mảng Gaussian hai chiều có thể được tách thành hai phép nhân xoắn với mặt nạ Gaussian một chiều Việc vi phân có thể được thực hiện thông qua phép tính chập với mảng một chiều, tạo ra hai thành phần: thành phần x từ việc nhân xoắn với G' và thành phần y còn lại.
4.1.2 Mô tả thuật toán a Các bước của thuật toán
Giải thuật phát hiện biên Canny được trình bày như sau:
1 Đọc ảnh I cần xử lý
2 Tạo một mặt nạ G để nhân xoắn với I Độ lệch tiêu chuẩn của mặt nạ này chính là tham số để tách cạnh
3 Tạo một mặt nạ cho đạo hàm bậc nhất của Gassian theo hướng x, y và gọi là Gx, Gy và giá trị vẫn được giữ như ở bước 2
4 Nhân xoắn ảnh I cùng với G dọc theo các hàng tạo ảnh thành phần x gọi là I x và theo các cột tạo ra ảnh I y
5 Nhân xoắn I x với Gx để sinh ra I' x : thành phần x của I được nhân xoắn với đạo hàm của Gaussian, và nhân xoắn Iy với Gy để tạo ra I' y
6 Nếu lúc này bạn muốn xem kết quả, thành phần x, y phải được kết hợp khi đó độ lớn tại điểm ( x, y ) được tính như sau:
M( x, y ) = I x ' x , y 2 I ' y x , y 2 Độ lớn được tính theo kiểu đã tính đối với Gradient b Giải thích thuật toán
Phần cài đặt thuật toán này có trong phần cuối cùng của đề tài này, sau đây là phần giải thích về chương trình
Chương trình chính là mở file ảnh và đọc nó, đồng thời đọc các tham số như độ lệch tiêu chuẩn
Hàm Canny thực hiện các tính toán chính trong quá trình xử lý hình ảnh, bắt đầu bằng việc tính mặt nạ lọc Gaussian và đạo hàm của nó Kích thước của mặt nạ lọc phụ thuộc vào độ lệch tiêu chuẩn, và chương trình tự động xác định kích thước này.
Tiếp theo, để làm mịn ảnh, chúng ta sử dụng tính nhân xoắn như trong bước 4 với hàm separable_convolution, đầu vào là ảnh và mặt nạ, và hàm trả về các thành phần x, y (gọi là smx và smy) Ở bước 5, phép nhân xoắn được thực hiện bằng cách gọi hàm dxy_separable_convolution hai lần, một lần cho x và một lần cho y, tạo ra các ảnh thành phần dx và dy Các thành phần này được nhân xoắn với G' thông qua hàm norm, giúp làm nổi bật các cạnh theo chiều ngang và dọc Để lọc ra các điểm cạnh, phương pháp nonmaximum suppression được Canny đề xuất Ý tưởng chính của phương pháp này là mỗi điểm cạnh có một hướng liên kết với nó, trong đó độ lớn của Gradient tại các điểm cạnh lớn hơn so với các điểm lân cận, do đó, những giao điểm không phải là cực đại địa phương sẽ bị loại bỏ.
Hình 6 minh họa nhƣ sau:
Hình 6 minh họa quá trình sử dụng hình học để phân tích điểm cạnh trong một vùng 3x3 Mũi tên chỉ ra hướng Gradient tại mỗi điểm cạnh, với độ dài mũi tên tỉ lệ thuận với độ lớn của Gradient Quá trình nonmaximum yêu cầu điểm chính giữa phải có Gradient lớn hơn các láng giềng trên phương Gradient Bắt đầu từ điểm trung tâm, di chuyển theo hướng Gradient đến điểm láng giềng thứ nhất và ngược lại đến điểm láng giềng thứ hai để xác định độ lớn Gradient Mặc dù trong trường hợp lý tưởng, hướng Gradient là ngang, thực tế cho thấy điều này không xảy ra thường xuyên Khi hướng Gradient là tùy ý, nó thường dẫn đến vị trí giữa hai điểm Để ước lượng giá trị Gradient tại một điểm, cần xem xét Gradient của các điểm láng giềng, giả định rằng sự thay đổi của Gradient là một hàm liên tục và có thể được mô tả bằng hàm tuyến tính giữa hai điểm bất kỳ.
A kỳ chỗ nào giữa các điểm cũng có thể được xấp xỉ bằng một phếp nội suy tuyến tính
Trong hình (b), Gradient tại các điểm khác nhau cho thấy rằng việc di chuyển theo Gradient từ điểm trung tâm sẽ dẫn chúng ta đến những điểm được đánh dấu là x, trong khi di chuyển ngược lại sẽ đưa chúng ta đến những điểm được đánh dấu là y Ở hình (c), chúng ta chỉ xem xét các điểm được đánh dấu x Tại điểm A, chúng ta phân tích các điểm láng giềng B và C Vector thành phần của Gradient tại A được ký hiệu là Ax và Ay, và quy ước tương tự được áp dụng cho các điểm B và C.
Mỗi điểm trên đường lưới có tọa độ nguyên, nghĩa là điểm A và B khác nhau một đơn vị khoảng cách theo hướng x Để xác định đường lưới nào sẽ bị cắt đầu tiên khi di chuyển từ A theo hướng Gradient, chúng ta cần nội suy tuyến tính độ lớn Gradient từ hai điểm trên đường lưới và vị trí giao điểm (Px, Py) Trong hình (c), giao điểm được đánh dấu bằng dấu '+' và nằm giữa B và C, với độ lớn Gradient tại điểm này được đánh giá dựa trên các yếu tố đã nêu.
Trong đó hàm Norm tính độ lớn Gradient
Tất cả các điểm trong ảnh đã được lọc đều được xử lý bằng cách đánh giá độ lớn của Gradient tại hai vị trí bên cạnh điểm cạnh, với yêu cầu độ lớn Gradient của điểm cạnh phải lớn hơn các láng giềng Có tổng cộng 8 trường hợp chính để kiểm tra trong trường hợp tổng quát Mặc dù có nhiều cách tính tắt để nâng cao hiệu quả, phương pháp này vẫn là cơ bản nhất trong các thuật toán của Canny Hàm nonmax_supress tính toán độ lớn tại các điểm dựa trên phương pháp này và đặt giá trị bằng 0 trừ khi điểm đó là cực đại địa phương.
Phương pháp Shen - Castan
Canny đã thiết lập một bộ tiêu chuẩn hợp lý cho việc tách cạnh, nhưng không có lý do gì để coi đây là phương pháp tối ưu nhất Khái niệm tối ưu là tương đối và có thể tồn tại những phương pháp tốt hơn Bài viết này sẽ khảo sát thuật toán phát hiện biên Shen-Castan, một phương pháp hiệu quả trong nhiều trường hợp ảnh khác nhau.
4.2.1 Cơ sở lý thuyết của thuật toán a, Nguyên lý của thuật toán
Shen và Castan đồng tình với quan điểm của Canny về phương pháp phát hiện điểm biên, nhưng họ đã đề xuất một hàm tối ưu khác, mang tính chất tối thiểu hóa theo một chiều.
Hàm cực tiểu CN được coi là bộ lọc làm mịn tối ưu cho việc phát hiện biên Tuy nhiên, Shen và Castan đã chỉ ra rằng thuật toán này có thể nhận diện nhiều cạnh mặc dù thực tế chỉ có một cạnh duy nhất tồn tại.
Hàm lọc tối ưu mà họ đưa ra được gọi là bộ lọc hàm mũ đối xứng vô hạn ISEF ( Infinine Symmetric Exponential Filter) : f(x) 2
Bộ lọc Shen và Castan mang lại tỉ lệ tín hiệu/nhiễu tốt hơn so với bộ lọc Canny, đồng thời cung cấp giá trị Localization cao hơn Nguyên nhân có thể là do thuật toán Canny sử dụng bộ lọc tối ưu xấp xỉ theo đạo hàm của bộ lọc Gauss, trong khi Shen và Castan áp dụng bộ lọc tối ưu trực tiếp Tuy nhiên, phương pháp của Shen - Castan không đưa ra các tiêu chuẩn đa đáp ứng, điều này có thể dẫn đến việc sinh ra nhiễu và làm mờ biên.
Bộ lọc ISEF trong không gian hai chiều có công thức: f( x, y ) = a e -P(|x|+|y|)
Công thức này áp dụng cho ảnh bằng cách xem nó như đạo hàm của bộ lọc Gaussian, thực hiện lọc một chiều theo hướng x và sau đó theo hướng y Shen và Castan đã nâng cấp bộ lọc này thành bộ lọc hồi tiếp một chiều.
Hàm bộ lọc f nói trên là một hàm số thực liên tục Nó có thể được viết lại dưới dạng rời rạc và lấy mẫu như sau: f[ i, j ] b y x b b
1 1 Để nhân chập ảnh như bộ lọc này, trước hết ta tiến hành lọc đệ quy theo hướng x và thu được r [ i, j ] như sau: y 1 [ i, j ] b b
Cùng với các điều kiện biên:
I [ i, j ] = 0 y 1 [ i, 0 ] = 0 y 2 [ i, M+1] = 0 Sau đó tiến hành lọc trên r[ i, j ] theo hướng y, sẽ tạo ra kết quả cuối cùng của bộ lọc: y[ i, j ] như sau: y 1 [ i, j ] b b
Với các điều kiện biên:
Việc sử dụng lọc đệ quy giúp tăng tốc độ xử lý đáng kể so với nhân chập Sau khi hoàn tất quá trình lọc ảnh, thách thức tiếp theo là phát hiện các điểm biên, được thực hiện bằng cách xác định các giao điểm không của toán tử Laplace.
4.2.2 Hoạt động thuật toán a, Các bước của thuật toán
Dựa trên những phân tích ở trên ta có thể đưa ra một thuật toán tìm biên như sau:
1 Đọc ảnh từ tệp cần xử lý
2 Lọc ảnh bằng phương pháp lọc đệ quy theo công thức ở trên
3 Tìm các giao điểm không sau khi áp dụng toán tử Laplace
4 Thực hiện quá trình phân nghưỡng b, Giải thích thuật toán
Việc đọc ảnh từ tệp được thực hiện bằng thủ tục Input_Bitmap
Sau khi thực hiện bước 2 của thuật toán, chúng ta sử dụng đệ quy với hàm ISEF để lọc ảnh Quá trình lọc được chia thành hai phần: hàm ISEF_vert thực hiện lọc theo chiều dọc và hàm ISEF_horiz thực hiện lọc theo chiều ngang Tham số b, do người dùng nhập vào, được sử dụng để điều chỉnh mức độ lọc.
Để xác định các điểm cạnh trong bước 3 của thuật toán, chúng ta cần áp dụng toán tử Laplace để tìm các giao điểm Theo nghiên cứu của Shen và Castan, một phương pháp xấp xỉ toán tử Laplace có thể thực hiện nhanh chóng bằng cách lấy ảnh gốc trừ đi ảnh đã được làm mịn, sau đó tạo ra ảnh nhị phân Cụ thể, nếu ảnh gốc là I và ảnh lọc là S, chúng ta có thể thực hiện phép toán này để tìm các điểm cạnh.
Giới hạn dài Laplace (band-limited Laplacian) của ảnh được xác định bởi công thức B = S - 1 Từ đó, ảnh nhị phân Laplace (Binary Laplacian Image - BLI) được tạo ra bằng cách gán giá trị 1 cho các điểm ảnh dương trong B và giá trị 0 cho các điểm ảnh còn lại, thông qua hàm compute_bli trong mã nguồn Những điểm nằm trên đường biên giữa các vùng trong BLI có thể được coi là điểm biên, và có thể áp dụng một số phương pháp cải thiện ảnh để nâng cao chất lượng đường biên.
Việc nâng cấp đầu tiên trong phương pháp phát hiện biên là sử dụng kỹ thuật loại bỏ giao điểm không lỗi (false zero-crossing suppression), tương tự như phép giới hạn không cực đại (nonmaximum suppression) trong phương pháp Canny Tại mỗi điểm biên, đạo hàm bậc hai sẽ cho kết quả giao điểm không, cho thấy Gradient tại đó là cực đại hoặc cực tiểu Nếu dấu của đạo hàm bậc hai thay đổi từ dương sang âm, thì giao điểm không đó được gọi là giao điểm không dương, và ngược lại, nếu thay đổi từ âm sang dương, thì gọi là giao điểm không âm Giả thiết rằng giao điểm không dương có Gradient dương và giao điểm không âm có Gradient âm Tất cả các giao điểm không khác đều được coi là sai và không được xem là điểm cạnh, quá trình này được thực hiện bởi hàm is_candidate_edge trong chương trình ISEF.
Khi ảnh gốc bị nhiễu nặng, việc sử dụng hàm ngưỡng chuẩn có thể không hiệu quả Các điểm biên có thể áp dụng một hàm ngưỡng tổng thể cho Gradient, nhưng Shen và Castan đã đề xuất phương pháp gọi là phù hợp Gradient (adaptive gradient method) Phương pháp này sử dụng một cửa sổ độ rộng cố định W, đặt vào các điểm biên trong BLI sao cho tâm của cửa sổ trùng với tâm điểm biên Nếu đúng là điểm biên, cửa sổ sẽ chia thành hai phần có mức xám khác nhau, được phân tách bởi một biên (đường bao zero-crossing) Xấp xỉ Gradient tốt nhất tại điểm này là sự sai khác giữa hai mức xám của hai vùng, với một vùng tương ứng với giá trị 0 trong BLI và vùng kia có giá trị 1.
Cuối cùng là việc phân nghưỡng trễ tương tự như trong thuật toán Canny.
Phương pháp phát hiện biên Marr- Hildreth
4.3.1 Cơ sở lý thuyết chung
Theo Marr (1980), xử lý ảnh nhằm mục tiêu tạo ra những điểm cốt yếu, đồng thời cung cấp một diễn tả toàn diện về bức ảnh Điều này giúp xác định độ phản xạ, độ sáng của bề mặt, cũng như hướng và khoảng cách của chúng so với người xem.
Sự diễn tả ở mức thấp nhất được ông gọi là phác họa cơ bản ( primal sketch) là thành phần chính của các biên
Marr đưa ra một giải thuật phát hiện biên mô tả như sau:
1 Nhân chập ảnh I với một hàm Gaussian 2 chiều
2 Tính Laplace của ảnh sau khi đã nhân chập, giá trị này gọi là L
3 Điểm biên là những điểm có sự đi qua điểm 0 trong L ( zero crossing) (2 giá trị đối xứng nhau qua điểm đó trong L là đối dấu nhau)
Hàm G được sử dụng trong tích chập trên là một hàm Gaussian 2 chiều :
Để thực hiện phép nhân chập trên ảnh số, cần chuyển đổi hàm Gaussian thành ảnh 2 chiều Sau khi hoàn tất phép nhân chập, toán tử Laplace sẽ được áp dụng để xử lý ảnh.
Giá trị Laplace của hàm Gaussian có thể được tính bằng cách sử dụng sai phân, trong đó thứ tự thực hiện không quan trọng Sau khi tính toán, ta có thể thu nhận giá trị hàm này thành ảnh và tạo ra một mặt nạ nhân chập, cho phép áp dụng để đạt được kết quả tương tự Giá trị Laplace của hàm Gaussian (LoG) là một phần quan trọng trong quá trình này.
Zero crossing tại điểm P chỉ ra rằng hai điểm lân cận đối xứng nhau trên một hướng có dấu hiệu trái ngược Cụ thể, nếu biên tại điểm P là đối xứng, thì giá trị tại điểm bên trái P sẽ khác dấu so với điểm bên phải P Do đó, cần kiểm tra bốn trường hợp: trên/dưới, trái/phải và hai đường chéo Việc kiểm tra này cần được thực hiện cho mọi điểm ảnh trong Laplace của hàm Gaussian.
Trên cơ sở lý thuyết đã trình bày ta có thể đưa ra các bước cho một phép phát hiện biên sử dụng phương pháp Marr- Hildreth như sau:
1 Đọc ảnh cần xử lý I
2 Dựa vào giá trị độ lệch tiêu chuẩn σ, ta xây dựng một ma trận Gaussian theo công thức trên Kích thước của ma trận được tính theo số kích thước tối đa của ma trận sao cho phần tử cuối cùng của ma trận có giá trị lớn hơn giá trị nào đó
3 Tính ma trận vuông Laplace của Gaussian ( LoG ) dựa trên ma trận Gaussian ở trên theo công thức đã cho
4 Nhân chập ma trận ảnh với LoG, được ma trận biên độ Gradient (MaG)
5 Tính ma trận Zero crossing với ma trận MaG vừa th được Các điểm có thể là biên là các điểm có giá trị 1 trong ma trận Zero crossing
6 Lấy ngưỡng và hiển thị ảnh ỨNG DỤNG CÁC PHƯƠNG PHÁP PHÁT HIỆN BIÊN
Sau khi nghiên cứu các phương pháp và thuật toán phát hiện biên, tôi đã áp dụng những thuật toán này vào nhiều lĩnh vực, bao gồm tìm xương thông qua làm mảnh ảnh, phát hiện góc nghiêng văn bản, và nhận dạng đối tượng chuyển động Tuy nhiên, do hạn chế về thời gian và trình độ, phần cuối của đồ án này sẽ tóm tắt ứng dụng của phát hiện biên trong việc tìm xương dựa trên làm mảnh.
Xương là hình dạng cơ bản của đối tượng, chứa ít điểm ảnh, giúp chúng ta thu thập thông tin cơ bản về đối tượng.
Thuật toán tìm xương dựa trên làm mảnh là một trong những thuật toán quan trọng trong xử lý ảnh Nó được phân loại thành hai loại: thuật toán làm mảnh song song và thuật toán làm mảnh tuần tự Quá trình làm mảnh thực chất là việc xoá dần các biên theo một thứ tự và điều kiện nhất định để thu được xương của đối tượng.
Hình 7: Minh họa quá trình làm mảnh Thuật toán làm mảnh tổng quát bao gồm các bước cơ bản sau:
Bước 1: Dò biên theo thuật toán dò biên chuẩn trên Nhằm phát hiện tất cả các đường biên của đối tượng
Bước 2: Đối với mỗi đường biên, cần kiểm tra tính thỏa mãn của điểm biên dựa trên các thông tin đã khai báo trước Nếu điểm biên thỏa mãn điều kiện xoá, hãy tiến hành xóa nó đi.
Bước 3: Nếu không còn điểm biên nào được đánh dấu xoá thì dừng, ngược lại thì quay lại bước 1
Sự khác biệt giữa các thuật toán nằm ở điều kiện xóa, và các điều kiện này sẽ dẫn đến những thuật toán làm mảnh khác nhau Mỗi thuật toán đều có những ưu điểm và nhược điểm riêng.
Một số thông tin khai báo trước cơ bản: a) Điều kiện đảm bảo tính liên thông
Một điểm ảnh được coi là điểm liên thông khi có ít nhất hai điểm nền không gần nhau trong 8-láng giềng Điều này giúp đảm bảo rằng các điểm biên trong quá trình xoá không bị loại bỏ các thành phần liên thông.
Hình 8: Điểm liên thông b) Điều kiện đảm bảo xương có dạng mảnh
Điểm biên được gọi là điểm xương dạng mảnh nếu nó có điểm láng giềng treo góc, với điểm láng giềng này có màu đối tượng khác màu nền của hai láng giềng kề nó Điểm cô lập là điểm không có láng giềng nào, tức là chỉ có một điểm Điểm cuối của đường thẳng là điểm có duy nhất một láng giềng Điểm liên kết là điểm mà khi loại bỏ nó, tính liên thông sẽ bị mất Việc áp dụng tiêu chuẩn này kết hợp với thuật toán tìm xương dựa trên làm mảnh theo điều kiện xoá từ các thuật toán đã biết sẽ giúp thu được xương dạng mảnh mà vẫn đảm bảo tính liên thông.
Hình 9 Xương dạng mảnh đảm bảo một số tiêu chuẩn đề ra