TỔNG QUAN VỀ PHÁT HIỆN BIÊN VÀ ĐỐI SÁNH ẢNH
Biên và phát hiện biên
Biên là yếu tố quan trọng trong phân tích ảnh, với các kỹ thuật phân đoạn chủ yếu dựa vào sự xác định biên Điểm ảnh được coi là điểm biên khi có sự thay đổi đột ngột về mức xám, và tập hợp các điểm này tạo thành biên hoặc đường bao của ảnh Chẳng hạn, trong một ảnh nhị phân, một điểm đen có thể được xem là biên nếu có ít nhất một điểm trắng lân cận Để minh họa tầm quan trọng của biên, khi một họa sĩ phác thảo hình dáng của một cái bàn gỗ, chỉ cần vài nét cơ bản như mặt bàn và chân bàn đã đủ để người xem nhận diện Tuy nhiên, nếu yêu cầu thêm chi tiết như vân gỗ hay màu sắc, thông tin ban đầu sẽ không đủ để hoàn thành nhiệm vụ phân lớp nhận diện đối tượng.
Trong toán học, điểm biên của ảnh được xác định là những điểm có sự thay đổi đột ngột về độ xám, và đường biên là tập hợp của các điểm này Hình 1-1 minh họa một số kiểu đường biên thường gặp trong thực tế.
Hình 1-1: Một số kiểu đường biên thông dụng
Phát hiện biên là một công cụ quan trọng trong xử lý ảnh số, giúp giảm khối lượng dữ liệu cần tính toán bằng cách giữ lại những thông tin cần thiết và bảo toàn cấu trúc quan trọng trong bức ảnh Mục tiêu lý tưởng của phát hiện biên là xác định tất cả các đường bao của các đối tượng Định nghĩa toán học về biên là nền tảng cho các kỹ thuật phát hiện biên, trong đó sự biến thiên mức xám giữa các điểm trong một vùng thường nhỏ, trong khi biến thiên mức xám tại vùng giáp ranh (khi qua biên) lại lớn.
1.1.2 Phân loại các kỹ thuật phát hiện biên
Trong toán học, biên được định nghĩa và thường được phát hiện qua hai phương pháp chính: phát hiện biên trực tiếp và phát hiện biên gián tiếp Hai phương pháp này sẽ được trình bày chi tiết trong các phần tiếp theo của bài viết.
1.1.2.1 Phương pháp phát hiện biên trực tiếp
Phương pháp phát hiện biên dựa vào sự biến thiên giá trị độ sáng của điểm ảnh, với kỹ thuật đạo hàm là chủ yếu Khi lấy đạo hàm bậc nhất, ta sử dụng phương pháp Gradient, còn đạo hàm bậc hai cho phép áp dụng kỹ thuật Laplace Cả hai phương pháp này được gọi là phương pháp dò biên cục bộ Bên cạnh đó, phương pháp “đi theo đường bao” hay phương pháp dò biên tổng thể cũng được sử dụng, dựa trên nguyên lý quy hoạch hoạt động.
Khi phân chia ảnh thành các vùng, biên giữa các vùng đó được xác định là đường phân ranh Quá trình phân vùng ảnh thường dựa vào kết cấu bề mặt của ảnh.
Kỹ thuật dò biên và phân vùng ảnh là hai bài toán đối ngẫu, trong đó dò biên giúp phân lớp đối tượng và phân vùng ảnh cho phép phát hiện biên Phương pháp dò biên trực tiếp hiệu quả trong môi trường ít nhiễu, nhưng kém hiệu quả khi độ sáng biến thiên đột ngột Ngược lại, phương pháp dò biên gián tiếp mặc dù khó cài đặt nhưng lại hoạt động tốt khi sự biến thiên độ sáng nhỏ.
1.1.3 Quy trình phát hiện biên trực tiếp
Để cải thiện chất lượng hình ảnh, bước đầu tiên là khử nhiễu, sử dụng các kỹ thuật khử nhiễu khác nhau Sau đó, bước tiếp theo là làm nổi biên để tăng độ rõ nét cho hình ảnh.
Tiếp theo là làm nổi biên bởi các toán tử đạo hàm
Bước 3: Định vị điểm biên
Vì các kỹ thuật làm nổi biên có hiệu ứng phụ là tăng nhiễu, do vậy sẽ có một số điểm biên giả cần loại bỏ
Bước 4: Liên kết và trích chọn biên
Phát hiện biên và phân vùng ảnh là hai nhiệm vụ đối ngẫu, do đó có thể thực hiện việc phát hiện biên thông qua quá trình phân vùng ảnh.
1.1.4 Một số phương pháp phát hiện biên
Các phương pháp phát hiện biên truyền thống thường sử dụng phép tích chập giữa bức ảnh nghiên cứu và một bộ lọc 2D, hay còn gọi là mặt nạ.
Cấu trúc và giá trị của các toán tử phát hiện biên quyết định hướng đặc trưng mà chúng nhạy cảm với biên Một số toán tử phù hợp cho các đường biên theo hướng nằm ngang, trong khi những toán tử khác lại hiệu quả hơn trong việc phát hiện biên theo hướng thẳng đứng hoặc đường chéo.
Hiện nay, có nhiều phương pháp phát hiện biên, trong đó hai phương pháp cơ bản nhất là phương pháp Gradient và phương pháp Laplace.
1.1.4.1 Phương pháp Gradient Đạo hàm bậc nhất theo hướng ngang và dọc được tính theo công thức sau: x y f
Biên độ của vector gradient, hay độ lớn tổng cộng của giá trị đạo hàm tại biên, được xác định bằng cách kết hợp hai giá trị này theo một công thức cụ thể.
Hướng của gradient vector được xác định theo: tan 1 x y f G
Hướng của biên sẽ vuông góc với hướng của gradient vector này
Toán tử Sobel sử dụng hai mặt nạ kích thước [3 x 3], trong đó một mặt nạ là sự quay của mặt nạ kia đi một góc 90 độ Các mặt nạ này được thiết kế để phát hiện đường biên theo chiều đứng và chiều ngang hiệu quả Khi thực hiện phép convolution giữa ảnh và các mặt nạ, ta thu được các gradient theo chiều đứng Gx và chiều ngang Gy Hình dạng của toán tử Sobel được minh họa trong hình 1-2.
Phương pháp Prewitt gần giống với Sobel Đây là phương pháp lâu đời nhất, cổ điển nhất Toán tử Prewitt được mô tả trên hình 1-3
Tương tự như phương pháp Sobel, chúng ta tính toán đường biên theo chiều ngang và dọc một cách riêng biệt bằng cách sử dụng hai mặt nạ như hình 1-4, sau đó kết hợp chúng để xác định đường biên thực của ảnh Tuy nhiên, do kích thước nhỏ của mặt nạ Robert, kết quả nhận được dễ bị ảnh hưởng bởi nhiễu.
Mô tả hình dạng dựa trên đường bao
Mô tả hình dạng dựa trên biên chỉ khai thác thông tin từ đường bao của đối tượng Có hai phương pháp chính để mô tả đường bao hình dạng: phương pháp tiếp cận toàn cục và phương pháp tiếp cận cấu trúc.
Phương pháp tiếp cận toàn cục mô tả hình dạng bằng một vector xác định đường bao, không chia hình dạng thành các phần Để đo độ tương tự hình dạng, thường sử dụng độ đo khoảng cách giữa các vector đặc trưng từ đường biên.
Phương pháp tiếp cận cấu trúc hình dạng phân tách các đường bao thành các đoạn dựa trên điều kiện phân tách Kết quả cuối cùng thường được biểu diễn dưới dạng xâu, chuỗi hoặc đồ thị, với các biện pháp tương tự được thực hiện bằng cách kết hợp chúng một cách hợp lý Trong phương pháp này, chuỗi, đồ thị hoặc cây được sử dụng để đạt được kết quả mong muốn Thuật toán đối sánh chuỗi hoặc đồ thị sẽ được áp dụng để đo độ tương tự hình dạng.
1.2.1 Mô tả theo tiếp cận toàn cục
Kỹ thuật biểu diễn đường bao hình dạng toàn cục tính toán vector đặc trưng đa chiều từ thông tin đường bao của hình dạng Quá trình đối sánh hai hình dạng thường đơn giản, sử dụng các độ đo khoảng cách như khoảng cách Euclide hoặc khoảng cách cityblock, và được áp dụng rộng rãi trong các ứng dụng thực tế.
Hình dạng tổng thể được mô tả là đơn giản và nhỏ gọn, nhưng mô tả này không hoàn toàn chính xác Để có được những mô tả hình dạng chính xác hơn, cần kết hợp với các mô tả hình dạng khác.
1.2.1.1 Mô tả hình dạng đơn giản(Simple shape descriptors)
Hình dạng có thể được mô tả đơn giản thông qua các yếu tố như diện tích, vùng, hướng trục chính, độ tròn, độ uốn và độ lệch tâm Các mô tả này thường chỉ phân biệt được những hình dạng có sự khác biệt lớn, do đó chúng thường được sử dụng để lọc và loại bỏ những hình dạng sai hoặc kết hợp với các mô tả khác Tuy nhiên, chúng không phù hợp cho các mô tả độc lập Chẳng hạn, độ lệch tâm của hình dạng trong hình 1-7(a) gần bằng 1 vì (a=b), nhưng không phản ánh đúng hình dạng thon dài của nó; trong trường hợp này, độ tròn sẽ chính xác hơn Ngược lại, hai hình dạng trong hình 1-7(b) và 1-7(c) có độ tròn tương tự nhưng lại rất khác nhau, do đó độ lệch tâm là mô tả phù hợp hơn.
Hình 1-7: Minh họa độ lệch tâm của hình dạng
1.2.1.2 Dấu hiệu đặc trưng hình dạng
Dấu hiệu đặc trưng hình dạng mô tả hình dạng bằng hàm một chiều từ điểm biên, bao gồm các yếu tố như khoảng cách tâm, tọa độ cực, tọa độ phức hợp, góc tiếp tuyến, góc tích lũy, độ cong, chiều dài dây, dây cung và diện tích.
Dấu hiệu hình dạng không bị ảnh hưởng bởi dịch chuyển và co dãn, có thể được lượng tử hóa thành biểu đồ để sử dụng trong đối sánh và bất biến với phép quay Tuy nhiên, dấu hiệu hình dạng thường nhạy cảm với nhiễu và thay đổi trên đường bao, dẫn đến khả năng gây ra lỗi trong quá trình đối sánh hình dạng.
Vậy nên, dấu hiệu đặc trưng hình dạng thường không sử dụng trực tiếp để mô tả hình dạng
Momen biên có thể giúp giảm kích thước các biểu diễn trên đường bao Giả sử biên hình dạng được biểu diễn bởi dấu hiệu hình dạng Z(i), khi đó momen thứ r là m r và momen tầm là àr Công thức ước tính cho momen biên có thể được áp dụng trong trường hợp này.
Trong đó, N là số các điểm biên
Mô tả momen đường bao được sử dụng để thể hiện bất biến với các phép dịch chuyển, quay và co dãn của hình dạng Mặc dù dễ thực hiện, việc gán các momen bậc cao hơn với các khái niệm vật lý lại gặp nhiều khó khăn.
1.2.2 Mô tả theo tiếp cận cấu trúc
Một phương pháp phân tích hình dạng hiệu quả là biểu diễn hình dạng cấu trúc, trong đó hình dạng được chia thành các đoạn đường bao và mã hóa thành các chuỗi tổng quát: S=S1, S2, ….Sn Mỗi S i đại diện cho các phần tử của mã xích, như cạnh của đa giác, hình vuông hoặc mặt spline, và có thể chứa nhiều thuộc tính như chiều dài, độ cong trung bình, độ cong lớn nhất và khả năng uốn Các chuỗi này không chỉ có thể được sử dụng để mô tả hình dạng mà còn có thể làm đầu vào cho các phân tích khác.
Mã xích mô tả đường biên đối tượng bằng chuỗi các đoạn thẳng đơn vị theo hướng xác định, được giới thiệu bởi Freeman vào năm 1961 Phương pháp này cho phép mã hóa các cấu hình hình học bằng cách biểu diễn đường cong bằng chuỗi vector đơn vị chiều dài, thiết lập giới hạn hướng cho phép Trong thực hiện, hình ảnh được chồng lên lưới, từ đó các điểm biên được lấy xấp xỉ với điểm lưới gần nhất và mẫu hình ảnh được thu thập Từ một điểm khởi đầu trên biên, mã xích được tạo ra bằng cách mã hóa các đoạn thẳng biểu diễn biên Các đoạn thẳng đơn vị có thể định hướng theo 4, 8 hoặc N hướng (với N > 8 và N = 2k), trong đó mã xích sử dụng đoạn thẳng đơn vị định hướng theo N hướng được gọi là mã xích tổng quát.
Mã xích biểu diễn hình dạng không phụ thuộc vào lựa chọn điểm ảnh biên bắt đầu trong chuỗi Để chuẩn hóa chuỗi mã xích, cần tìm các điểm ảnh trong trình tự biên với kết quả mô tả là các số nguyên tối thiểu, từ đó sử dụng chúng làm điểm ảnh bắt đầu Biên có thể được thể hiện qua sự khác biệt về các chỉ thị tiếp theo trong chuỗi mã, thay vì chỉ số tương đối Quá trình chuẩn hóa sự khác biệt trong chuỗi mã được gọi là Shape number, và Shape number sẽ được dùng để biểu diễn hình dạng của đối tượng.
Mã xích được sử dụng để biểu diễn hình dạng và đối sánh, tuy nhiên có nhiều hạn chế như bị ảnh hưởng bởi nhiễu đường biên, biến dạng và kích thước chuỗi mã dài Thông thường, mã xích là đầu vào cho các phân tích ở mức độ cao, chẳng hạn như xấp xỉ đa giác và tìm điểm uốn.
Mã xích biểu diễn đường biên đối tượng thông qua chuỗi kết nối các phân đoạn đường thẳng có độ dài và định hướng nhất định Biểu diễn này thường dựa trên 4 hoặc 8 hướng kết nối, với hướng của mỗi phân đoạn được mã hóa bằng một lược đồ số Những hình ảnh kỹ thuật số thường được xử lý theo định dạng lưới, với khoảng cách đều giữa các hướng x và y Chuỗi mã có thể được tạo ra bằng cách định hướng các phân đoạn đường thẳng dọc theo biên theo chiều kim đồng hồ.
Đối sánh ảnh
1.3.1 Giới thiệu về đối sánh ảnh Đối sánh ảnh là một bài toán đã và đang thu hút được sự quan tâm của các nhà nghiên cứu và phát triển Mỗi khi bài toán này được giải quyết, nó mở ra rất nhiều các ứng dựng hữu ích như: tìm kiếm ảnh, nhận dạng, theo dõi và phát hiện đối tượng, ghép ảnh, v.v Đối sánh hai ảnh là tìm ra những vùng giống nhau trên hai ảnh Thông thường, để đối sánh ảnh cần so sánh các phần tử cơ bản cấu thành nên nó Giải pháp đầu tiên cho vấn đề đối sánh ảnh được đề xuất bởi Hobrough vào cuối những năm 1950 Hệ thống tự động tìm kiếm các điểm tương quan được giới thiệu lần đầu bởi công ty Wild Heerbrugg năm 1964 nhưng lại không được sử dụng phổ biến Tuy nhiên, ý tưởng áp dụng mối tương quan chéo của Hobrough lại được nhiều người sử dụng Từ những năm 1970, việc tập trung phát triển đối sánh ảnh và đối sánh tương quan gặt hái được nhiều thành công và được áp dụng trong hệ thống đo độ tương tự cho ảnh (Helava, 1978) Ngày nay, công nghệ đối sánh ảnh được tính hợp trong nhiều phần mềm xử lý ảnh được sử dụng như là một công cụ tính toán Có rất nhiều nghiên cứu được thực hiện với mong muốn tìm cặp điểm tương đồng trên hai bức ảnh Thuật toán tìm kiếm điểm tương đồng có thể thực hiện được trên ảnh 2D
Vấn đề chính của đối sánh ảnh là lựa chọn thực thể và độ đo tương tự để so sánh giữa các ảnh Đối sánh từng pixel không khả thi với ảnh lớn do yêu cầu tính toán cao và thời gian xử lý lâu, hoặc cần phần cứng mạnh hơn Thêm vào đó, vấn đề này thường dẫn đến sự nhập nhằng do giá trị mức xám lặp lại và nhiễu ảnh, khiến nó trở thành bài toán giả định yếu Để chuyển đổi thành bài toán giả định chặt, cần định nghĩa rõ ràng các thực thể, độ đo tương tự, ràng buộc hình học và giả thiết trong một giới hạn nhất định, nhằm hạn chế không gian giải pháp Hai phương pháp cơ bản trong đối sánh ảnh là phương pháp dựa trên vùng và phương pháp dựa trên đặc trưng, được sử dụng rộng rãi trong quan trắc và thị giác máy.
Bảng 1.1: Phương pháp đối sánh hình ảnh
Phương pháp đối sánh Độ tương tự Đối tượng đối sánh
Dựa trên vùng Tương quan, đối sánh hình vuông nhỏ nhất Giá trị mức xám
Dựa theo đặc trưng Hàm chi phí Điểm quan tâm, cạnh, vùng
Các giá trị mức xám là thực thể trong đối sánh dựa trên vùng, giúp giảm thiểu sự nhập nhằng khi so sánh từng điểm ảnh Để thực hiện điều này, các giá trị mức xám của các điểm ảnh lân cận được sử dụng Một phần ảnh cắt ra, gọi là mẫu, chứa m*n điểm ảnh (thường m=n), với vị trí trung tâm là điểm ảnh chính, do đó m và n thường là số lẻ Mẫu sẽ được so sánh với vùng ảnh tương tự trong ảnh thứ hai, trong một quy trình gọi là tìm kiếm dựa trên vùng hoặc tìm kiếm cửa sổ Độ đo tương tự được tính toán tại mỗi vị trí của mẫu trong vùng tìm kiếm, và điểm tương ứng với tâm mẫu sẽ có độ đo lớn nhất hoặc nhỏ nhất Trong các phương pháp quan trắc, tương quan chéo và đối sánh bình phương nhỏ nhất là những công nghệ phổ biến cho đối sánh dựa trên vùng, bên cạnh việc áp dụng thông tin tương hỗ và khoảng cách ảnh.
Phương pháp đối sánh dựa trên đặc trưng khác biệt so với đối sánh dựa trên vùng, vì nó sử dụng các toán tử trực tiếp trên các giá trị mức xám Các phương pháp này tập trung vào việc đối sánh các đặc trưng đã được trích chọn như điểm, cạnh hoặc vùng Thủ tục đối sánh dựa trên đặc trưng bao gồm ba bước, được điều chỉnh từ Forstner (1986).
Chọn các đặc trưng riêng biệt (điểm,cạnh, góc) trong các ảnh riêng biệt
Xây dựng danh sách sơ bộ các cặp ứng viên của các đặc trưng tương ứng dựa trên độ đo tương tự được lựa chọn
Lấy danh sách cuối cùng các cặp đặc trưng phù hợp với mô hình đối tượng
1.3.2 Đối sánh ảnh dựa trên đặc trưng
Các điểm đặc trưng trong hình ảnh được xác định bởi sự chênh lệch cao về giá trị mức xám hoặc hàm tương quan tự động lớn với độ dốc gradient cao Những điểm này cần phải có sự khác biệt và ổn định, không thay đổi dưới các biến đổi hình học và phổ, đảm bảo rằng mỗi điểm xuất hiện trong tất cả các ảnh được đối sánh (Forstner, 1986) Quy trình tìm kiếm các điểm đặc trưng trong ảnh đối sánh được thực hiện qua hai bước.
Tính toán các tham số đặc trưng ở mỗi cửa sổ của ảnh được chọn
So sánh giá trị của các tham số với một ngưỡng cho trước
Các tham số đặc trưng khác nhau cho mỗi toán tử, nhưng chủ yếu dựa trên giá trị mức xám bên trong cửa sổ được đánh giá Chỉ những cửa sổ có giá trị tham số vượt ngưỡng mới được công nhận là điểm đặc trưng Danh sách điểm đặc trưng của mỗi ảnh được đối sánh với tọa độ và mô tả của chúng Theo Luhmann và Altrogge (1986), ba toán tử điểm đặc trưng Moravec, Forstner và Dreschler đã được đề xuất, trong đó Moravec và Forstner cho kết quả tốt hơn trong việc tìm kiếm điểm đặc trưng dựa trên các điều kiện hình học khác nhau.
Các cạnh trong hình ảnh được coi là các điểm gián đoạn trong hàm mức xám, nơi mà giá trị mức xám thay đổi nhanh chóng trong một khu vực nhỏ Chúng thường tương ứng với đường bao của các đối tượng trong hình ảnh Quá trình trích xuất cạnh là một nhiệm vụ phức tạp và bao gồm nhiều bước khác nhau (Schenk, 1999).
Toán tử cạnh được sử dụng để xác định các điểm ảnh nằm trên cạnh bằng cách phát hiện giá trị mức xám không liên tục Một ngưỡng cho các giá trị mức xám khác nhau được thiết lập nhằm quyết định những điểm nào được coi là điểm cạnh.
Liên kết các điểm cạnh thành các cạnh
Nhóm các cạnh: tức là xác định phân đoạn đường thẳng, đường đa giác, đường gấp khúc, đường song song, v.v
Toán tử cạnh phát hiện sự thay đổi của giá trị mức xám trong ảnh thông qua đạo hàm bậc nhất, giúp xác định cực trị và vị trí điểm cạnh Hai toán tử phổ biến là Robert (Robert Cross) và Sobel (Sobel Operator), cả hai đều dựa trên hướng để phát hiện cạnh theo chiều ngang và chiều dọc Trong đó, toán tử Sobel ít bị ảnh hưởng bởi nhiễu ảnh nhờ vào việc tính toán với các điểm ảnh lân cận.
Toán tử Laplacian là một trong những toán tử đạo hàm bậc hai, giúp giảm thiểu ảnh hưởng của nhiễu trong ảnh mà không phụ thuộc vào hướng Khi kết hợp với toán tử Gaussian, nó có khả năng làm mịn ảnh, và sau khi áp dụng, các điểm cạnh sẽ có giá trị bằng không Toán tử LoG tương tự như toán tử đạo hàm bậc nhất, được mô tả chi tiết trong Hình 1-13 và 1-14.
ĐỐI SÁNH HÌNH DẠNG SỬ DỤNG NGỮ CẢNH HÌNH DẠNG
Giới thiệu
Hình dạng là một đặc trưng thị giác quan trọng, đóng vai trò cơ bản trong việc mô tả nội dung ảnh Tuy nhiên, việc biểu diễn và mô tả hình dạng gặp nhiều khó khăn do thông tin về đối tượng 3-D bị mất khi chiếu lên mặt phẳng 2-D Hình dạng được trích xuất từ hình ảnh chỉ phản ánh một phần của đối tượng, và vấn đề trở nên phức tạp hơn khi hình dạng thường bị hỏng, biến dạng, cắt bỏ, hoặc bị nhiễu và trùng lặp.
Biểu diễn hình dạng tập trung vào việc tìm kiếm các đặc trưng hình dạng quan trọng dựa trên thông tin từ đường bao và nội dung bên trong Nhiều kỹ thuật mô tả hình dạng đã được phát triển, bao gồm dấu hiệu hình dạng, ngữ cảnh hình dạng, ma trận hình dạng và phổ Phần này sẽ chủ yếu trình bày phương pháp mô tả hình dạng thông qua ngữ cảnh hình dạng.
Độ đo khoảng cách hình dạng
2.2.1 Khoảng cách min-max Được thực hiện dựa trên ý tưởng lấy phần giao của hai lược đồ cần so sánh, ta sẽ được một lược đồ, tính tổng các giá trị có được từ lược đồ này cho ta được độ đo min – max Đối với độ đo min: ta tính dựa vào giá trị min tại mỗi K bin
(2.1) Đối với độ đo max: ta tính dựa vào giá trị max tại mỗi K bin
2.2.2 Khoảng cách Euclid Đây là cách tính khoảng cách Euclid thông thường giữa các K bin:
2.2.4 Khoảng cách Chi Squared distance
Khoảng cách Chi Squared là chỉ số đo lường sự khác biệt giữa các bin trong việc so sánh các biểu đồ Công thức tính khoảng cách Chi Squared giữa hai biểu đồ được xác định như sau:
Khoảng cách Hausdorff là phương pháp đối sánh hình dạng dựa trên tương quan cổ điển, thường được sử dụng để xác định vị trí trong ảnh và đo độ tương tự giữa các hình dạng Hai hình dạng được biểu diễn thông qua tập hợp các điểm A={a1, a2,…, ap}.
B={b 1 , b 2 , …b q } thì khoảng cách giữa A và B được biểu diễn:
Khoảng cách Hausdorff có nhược điểm là nhạy cảm với nhiễu và các điểm ngoại lai, dẫn đến việc điểm đơn trong A và các điểm trong B có thể tạo ra giá trị h(A,B) lớn Để khắc phục vấn đề này, Rucklidge đã cải tiến khoảng cách Hausdorff.
Giá trị vi phân thứ f của hàm g(x) trên tập x, với một số giá trị của f là 0 và 1, cho thấy rằng giá trị vi phân thứ nhất là lớn nhất, trong khi giá trị vi phân 1/2 thường được sử dụng làm trung bình Thực tế, f thường được đặt là 1/2 Một ưu điểm của việc đối sánh hình dạng bằng khoảng cách Hausdorff là khả năng đối sánh cục bộ, nhưng khoảng cách này không bất biến trước các phép tịnh tiến, co dãn và quay.
2.2.6 Độ đo khoảng cách trong
Cấu trúc thành phần là yếu tố quan trọng trong phân loại hình dạng phức tạp, nhưng việc thu thập chúng không hề đơn giản, đặc biệt với các hình dạng có khớp nối Những hình dạng này thường trải qua biến đổi phi tuyến và có thể mang cấu trúc nhập nhằng Để khắc phục những thách thức này, kỹ thuật biểu diễn hình dạng gọi là khoảng cách trong đã được đề xuất.
Khoảng cách trong được xác định là khoảng cách ngắn nhất giữa các điểm trên đường biên của hình dạng, giúp xây dựng sự nhận diện cho hình ảnh Điều này cho thấy rằng khoảng cách trong không bị ảnh hưởng bởi các hình dạng khớp nối, như minh họa trong hình 2-1.
Hình 2-1: Ví dụ khoảng cách trong
Mặc dù hình (a) và hình (c) có sự phân bố không gian tương tự, nhưng cấu trúc thành phần của chúng hoàn toàn khác nhau Trong khi đó, hình (b) và hình (c) xuất phát từ cùng một loại hình dạng, chỉ khác nhau ở các khớp nối Khoảng cách giữa hai điểm trong hình (a) và hình (b) hoàn toàn khác biệt, trong khi sự tương đồng chủ yếu nằm ở hình (b) và hình (c) Ví dụ này cho thấy rằng khoảng cách trong không nhạy cảm với cấu trúc khớp nối nhưng nhạy cảm với cấu trúc thành phần, cho thấy khoảng cách trong là công cụ hữu ích cho việc đối sánh các hình dạng phức tạp Ngược lại, khoảng cách Euclidean không có những thuộc tính này, vì nó không xem xét các đoạn nét đứt chồng chéo khi định nghĩa khoảng cách.
Việc áp dụng khoảng cách trong để thay thế các độ đo tương tự khác giúp xây dựng mô tả hình dạng mới, có khả năng bất biến và không nhạy cảm với các hình dạng có cấu trúc khớp nối.
Hình O là một tập hợp đóng và có kết nối trong R², với hai điểm x và y thuộc O Khoảng cách giữa x và y, ký hiệu là d(x, y; O), được định nghĩa là độ dài của đường đi ngắn nhất nối hai điểm này trong hình O.
Hình 2-2: Ví dụ về khoảng cách trong của x và y trong hình O
Trong một số trường hợp hiếm, có thể có nhiều đường dẫn ngắn nhất giữa các điểm đã cho, và trong tình huống này, chúng ta có thể tự do lựa chọn một trong những đường dẫn ngắn nhất đó.
Hình dạng thường được định nghĩa qua các đường biên của nó, với những điểm biên này đóng vai trò là các điểm đánh dấu Hơn nữa, hình dạng có thể được xấp xỉ bằng một hình đa giác, hình đa giác này được tạo thành từ các điểm đã được đánh dấu.
Cách đơn giản nhất để tính toán khoảng cách trong là sử dụng thuật toán tìm đường dẫn ngắn nhất, thuật toán này được chia làm hai bước:
Bước đầu tiên trong quá trình xây dựng đồ thị là tạo ra các điểm mẫu, mỗi điểm mẫu được xem như một nút trong đồ thị Sau đó, với mỗi cặp điểm mẫu p1 và p2, nếu đoạn nối giữa p1 và p2 hoàn toàn nằm trong đối tượng, một cạnh sẽ được thêm vào đồ thị giữa p1 và p2, với trọng số là khoảng cách Euclidean ||p1 – p2||.
Một vài chú ý được đề cập tới đó là:
Thứ nhất: các điểm biên láng giềng thì luôn luôn liên thông với nhau
Thứ hai: Khoảng cách trong không sử dụng những điểm mẫu của đường biên lỗ hổng
Hình 2-3: Quá trình biểu diễn khoảng cách trong của đối tượng
Bước thứ hai trong quá trình tìm đường đi ngắn nhất cho đồ thị là áp dụng các thuật toán, trong đó thuật toán Floyd-Warshall được sử dụng với độ phức tạp O(n³), với n là số điểm lấy mẫu Đầu tiên, cần kiểm tra xem đoạn nối giữa hai điểm có nằm trong hình dạng hay không, tốn khoảng thời gian O(n) Sau đó, việc xây dựng đồ thị có độ phức tạp O(n³) Khi đồ thị đã hoàn thành, thuật toán tính toán tất cả các cặp có đường dẫn ngắn nhất cũng có độ phức tạp O(n³) Do đó, tổng độ phức tạp tính toán đạt O(n³).
Mô tả ảnh sử dụng ngữ cảnh hình dạng (Shape context)
Ngữ cảnh hình dạng là một mô tả tính năng quan trọng trong nhận dạng đối tượng, được giới thiệu bởi Belongie Nó thể hiện mối quan hệ phân bố không gian giữa các điểm đại diện xung quanh các điểm đặc trưng Cụ thể, với n điểm mẫu x1, x2, …, xn trên một hình dạng, ngữ cảnh hình dạng tại điểm xi được định nghĩa là biểu đồ hi thể hiện mối quan hệ tọa độ của n-1 điểm còn lại.
Trong nghiên cứu, các bin được phân bố đều trong không gian log-polar, với Hình 2-4 minh họa quá trình tính toán Biểu đồ (a) và (b) thể hiện các điểm được lấy mẫu trên hai hình dạng khác nhau Biểu đồ (c) là log-polar với 5 bin bán kính và 12 bin góc Ngữ cảnh hình dạng được thể hiện qua các điểm đánh dấu trong (d) và (e), cho thấy hai điểm liên quan có hình dạng tương tự Ngược lại, ngữ cảnh hình dạng trong (f) cho thấy sự khác biệt rõ rệt.
Hình 2-4: Tính toán ngữ cảnh hình dạng
Đối sánh hình dạng ngữ cảnh
2.4.1 Đối sánh shape sử dụng quy hoạch động
Bài toán đối sánh đường bao liên quan đến việc so sánh hai hình A và B, được mô tả thông qua các dãy điểm trên đường bao của chúng Cụ thể, hình A có n điểm p1, p2, …, pn, trong khi hình B có m điểm q1, q2, …, qm.
Giả sử n >= m, một đối sánh từ A đến B là ánh xạ từ 1, 2, …, n đến 0, 1, 2, …, m, trong đó p(i) được đối sánh với q((i)) nếu p(i) khác 0; ngược lại, sẽ không có đối sánh Hàm chi phí đối sánh C() được định nghĩa dựa trên các yếu tố này.
Trong đó, c(i, 0) = τ là giá trị phạt khi điểm pi không được đối sánh, và với 1 ≤ j ≤ m, c(i, j) là chi phí đối sánh giữa pi và qj Độ đo này được tính toán bằng cách sử dụng hàm thống kê χ² theo công thức sau:
(2.13) Ở đây, hA,i và hB,j là những biểu đồ ngữ cảnh hình dạng của pi và qj, và
K là số bin của biểu đồ
Các đường bao được cung cấp theo thứ tự cho các chuỗi điểm p1, p2,…pn và q1, q2,…qm, dẫn đến việc hạn chế sự đối sánh Để khắc phục vấn đề này, kỹ thuật Quy hoạch động (DP) đã được áp dụng, cho thấy tính hiệu quả trong việc giải quyết vấn đề đối sánh đường bao DP đã trở thành một công cụ phổ biến cho các bài toán liên quan đến đối sánh đường bao.
2.4.2 Đối sánh hình dạng dựa trên đồ thị
Bài toán đối sánh đường bao liên quan đến việc so sánh hai hình A và B thông qua các dãy điểm trên đường bao của chúng Cụ thể, ta có n điểm p1, p2, …, pn thuộc hình A và m điểm q1, q2, …, qm thuộc hình B, với giả sử n >= m Sự đối sánh π từ A đến B được định nghĩa như một ánh xạ từ các chỉ số 1, 2, …, n đến các chỉ số 0, 1, 2, …, m, nhằm xác định mối quan hệ giữa các điểm trên hai hình.
…, m trong đó p i được đối sánh với q (i) nếu (i) khác 0 và ngược lại thì không đối sánh nên được cực tiểu hóa chi phí đối sánh và được định nghĩa là
Trong bài toán này, c(i, 0) = τ đại diện cho hình phạt khi bỏ qua p i không được đối sánh, trong khi c(i, j) là chi phí để đối sánh p i với q j cho 1 ≤ j ≤ m Để giải quyết vấn đề này, chúng ta có thể áp dụng thuật toán ghép cặp trên đồ thị với trọng số nhỏ nhất.
2.4.2.1 Bài toán ghép cạnh với trọng số nhỏ nhất
Input: Đồ thị hai phần đầy đủ G = (X∪Y, E), X = {X 1 , X2, , Xn}, Y
= {Y1, Y2, , Yn} được cho bởi ma trận vuông C cỡ n×n, c[i, j] là trọng số cạnh nối đỉnh Xi với Yj Giả thiết c[i, j] ≥ 0 với mọi i, j
Output: Ghép cặp hoàn hảo với trọng số nhỏ nhất
2.4.2.2 Thuật toán Để cho gọn, ta gọi những cạnh trọng số 0 của G là những 0_cạnh Xét một ghép cặp M chỉ gồm những 0_cạnh
Những 0_cạnh thuộc M được phân chia thành hai loại: 0_cạnh đã ghép và 0_cạnh chưa ghép Để định hướng lại các 0_cạnh, ta sẽ hướng những 0_cạnh chưa ghép từ tập X sang tập Y, trong khi đó, những 0_cạnh đã ghép sẽ được hướng từ tập Y về tập X.
Đường xen kẽ là một đường đi đơn bắt đầu từ một đỉnh X chưa ghép, di chuyển theo các cạnh đã định hướng Trên đường xen kẽ, các cạnh chưa ghép và đã ghép sẽ xen kẽ nhau Để xác định những đỉnh có thể tiếp cận từ x ∈ X bằng đường xen kẽ, có thể áp dụng các thuật toán tìm kiếm trên đồ thị như BFS hoặc DFS Các đỉnh và cạnh được duyệt sẽ tạo thành một cây pha gốc từ đỉnh x.
Một đường mở là một đường xen kẽ đi từ một X_đỉnh chưa ghép tới một Y−đỉnh chưa ghép Như vậy:
Đường đi trực tiếp từ một X_ đỉnh chưa ghép tới một Y_đỉnh chưa ghép qua một 0_cạnh chưa ghép cũng là một đường mở
Dọc trên đường mở, số 0_cạnh chưa ghép nhiều hơn số 0_cạnh đã ghép đúng 1 cạnh
Khởi tạo một ghép cặp M = ∅
Để tìm cách ghép cho mọi đỉnh x∗ ∈ X, chúng ta bắt đầu từ đỉnh x∗ chưa ghép và sử dụng thuật toán tìm kiếm trên đồ thị, ưu tiên thuật toán BFS để tìm đường với ít cạnh nhất Có hai khả năng sẽ xảy ra trong quá trình tìm kiếm này.
Khi tìm thấy một đường mở, chúng ta loại bỏ các cạnh đã ghép khỏi tập M và thêm vào các cạnh chưa ghép Quá trình này tạo ra một ghép cặp mới với số lượng nhiều hơn ghép cặp cũ một cạnh, đồng thời đỉnh x∗ sẽ trở thành đã ghép.
Hoặc không tìm được đường mở, do ta dùng thuật toán tìm kiếm trên đồ thị nên có thể xác định được hai tập:
VisitedX = Tập những X_ đỉnh có thể đến được từ x∗ bằng một đường xen kẽ;
VisitedY = Tập những Y_đỉnh có thể đến được từ x∗ bằng một đường xen kẽ;
Gọi ∆ là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX và một đỉnh không thuộc VisitedY Rõ ràng rằng ∆ > 0, vì nếu ∆ = 0, sẽ tồn tại một cạnh (x, y) với x thuộc VisitedX và y không thuộc VisitedY.
Vì x∗ đến được x bằng một đường xen kẽ và (x, y) là một 0_cạnh nên x∗ cũng đến được y bằng một đường xen kẽ, dẫn tới y ∈ VisitedY, điều này vô lý
Biến đổi đồ thị G bằng cách giảm trọng số của các cạnh liên thuộc với mọi x ∈ VisitedX một giá trị ∆, đồng thời tăng trọng số của các cạnh liên thuộc với mọi y ∈ VisitedY cùng một giá trị ∆.
Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất phát ở x∗ cho tới khi tìm ra đường mở
Sau bước 2 thì mọi X_đỉnh đều được ghép, in kết quả về ghép cặp tìm được
Tìm ghép cặp lớn nhất với trọng số nhỏ nhất trong đồ thị, trong đó các cạnh không ghi trọng số được coi là 0_cạnh Những cạnh không vẽ có trọng số lớn không cần tính đến Các cạnh nét đậm thể hiện những cạnh đã ghép, trong khi các cạnh nét thanh là những cạnh chưa ghép.
2.4.2.3 Bài toán ghép cặp với trọng số lớn nhất
Input: Đồ thị hai phần đầy đủ G = (X∪Y, E), X = {X 1 , X2, , Xn}, Y {Y1, Y2, , Yn} được cho bởi ma trận vuông C cỡ n×n, c[i, j] là trọng số cạnh nối đỉnh Xi với Yj Giả thiết c[i, j] ≥ 0 với mọi i, j
Output: Ghép cặp hoàn hảo với trọng số lớn nhất
Để khởi tạo hai dãy Fx và Fy, cần đảm bảo điều kiện Fx[i] + Fy[j] ≥ c[i, j] với mọi i, j Một cách thực hiện là gán Fx[i] với giá trị lớn nhất trong dòng i của ma trận C, trong khi các giá trị Fy[j] có thể được đặt bằng 0.
Bước 2: Đối với mỗi đỉnh x∗ ∈ X, chúng ta thực hiện việc ghép x∗ bằng cách hiểu 0−cạnh là cạnh thỏa mãn điều kiện c[i, j] = Fx[i] + Fy[j] Bắt đầu từ đỉnh x∗, chúng ta sẽ thử tìm đường mở từ x∗, với hai khả năng có thể xảy ra.
THỰC NGHIỆM
Môi trường thực nghiệm
Hệ điều hành Windows 10 Pro 64-bit
Chương trình cài đặt trên môi trường visual studio 2017 với thư viện mã nguồn mở OpenCV (Open Source Computer Vision Library)
OpenCV là thư viện mã nguồn mở về thị giác máy tính và học máy, cung cấp nền tảng cho các ứng dụng nhằm nâng cao tri thức máy tính trong sản phẩm thương mại Với giấy phép BSD, OpenCV được hỗ trợ bởi nhiều công ty hàng đầu như Google, Yahoo, Microsoft, Intel, và IBM, trở thành công cụ mạnh mẽ và phổ biến trong giáo dục cũng như trong các công ty khởi nghiệp.
Thư viện OpenCV bao gồm nhiều giao diện dành cho C++, C, Python, Java, MATLAB và hỗ trợ cho các hệ điều hành khác nhau như Windows,
OpenCV 3.1 đã hoàn thiện giao diện sử dụng cho CUDA và OpenCL trên các nền tảng như Linux, Android và MacOS Được viết bằng ngôn ngữ C++, OpenCV cung cấp nhiều chức năng đa dạng Dưới đây là tóm tắt cơ bản về các nhóm hàm trong OpenCV.
Image and Video I/O Là các nhóm hàm cho phép đọc dữ liệu ảnh từ
General computer vision and image processing algorithms encompass functions that execute image processing techniques derived from video sources.
Graphic cung cấp các hàm để viết chữ và vẽ trên hình ảnh, giúp ghi nhãn và đánh dấu hiệu quả Những hàm này rất hữu ích trong việc tạo nhãn ảnh (label image) với kích thước và vị trí chính xác, đặc biệt khi phát triển chương trình nhận dạng nhiều đối tượng.
OpenCV cho Linux và MacOSX được cung cấp dưới dạng gói mã nguồn lưu trữ, yêu cầu người dùng xây dựng cả thư viện tĩnh và đối tượng chia sẻ Để cài đặt, người dùng cần xây dựng RPM trước hoặc biên dịch và cài đặt trực tiếp Hướng dẫn chi tiết cho cả hai phương pháp có thể tìm thấy trong tệp INSTALL Đối với Windows, quá trình cài đặt OpenCV sẽ sao chép các tệp vào thư mục người dùng chọn, với vị trí mặc định là C:/Program Files/OpenCV/.
Thư mục OpenCV bao gồm một số thư mục con, trong đó thư mục docs chứa các file HTML tài liệu cho tất cả các hàm và kiểu dữ liệu của OpenCV Từ tài liệu này, người dùng có thể tham khảo và thực hiện các ví dụ, cũng như tìm hiểu thêm về các thư mục khác trong OpenCV.
“samples” Những file header sẽ cần thiết khi ta dịch chương trình sử dụng OpenCV.
Đối sánh ảnh dựa trên ngữ cảnh hình dạng sử dụng opencv
3.2.1 Tìm đường bao và lấy mẫu các điểm trên đường bao
Bước 1: Đọc và hiển thị ảnh
Hàm đọc ảnh trong opencv: imread
Mat imread(const string&filename, int flags)
Filename: Tên ảnh đầu vào
CV_LOAD_IMAGE_ANYDEPTH: Nếu ảnh đầu vào có chiều sâu tương ứng thì ảnh trả về 16-bit/32-bit, còn ngược lại thì nó trả về ảnh 8- bit
CV_LOAD_IMAGE_COLOR: Nếu dùng hàm này, thì ảnh chuyển đổi thành ảnh một màu
CV_LOAD_IMAGE_GRAYSCALE: Nếu dùng hàm này, sẽ trả về hình ảnh đa mức xám
Hàm hiển thị ảnh trong opencv: imshow
Void imshow(const string & winname, InputArray mat)
Winname: Tên cửa sổ hiển thị ảnh
Image: Hình ảnh được hiển thị
Hàm imshow dùng để hiển thị hình ảnh trong một cửa sổ nhất định Khi cửa sổ được tạo với CV_WINDOW_AUTOSIZE, hình ảnh sẽ được hiển thị với kích thước gốc, nhưng vẫn bị giới hạn bởi độ phân giải màn hình Nếu không, hình ảnh sẽ được thu nhỏ để phù hợp với kích thước cửa sổ Hàm này có khả năng chia tỷ lệ hình ảnh tùy thuộc vào độ sâu của nó.
Ví dụ đọc và hiển thị ảnh:
Mat img = imread("D:/Anh/Shape1.jpg"); imshow("Shape", img);
Hình 3-1: Hình được hiển thị Shape
To find contours in an image, use the function findContours(currentQuery, _contoursQuery, RETR_LIST, CHAIN_APPROX_NONE) The parameter currentQuery refers to the input image, while contoursQuery stores the detected contours, with each contour saved as a vector of points.
RETR_LIST: Trả về tất cả các đường bao mà không thiết lập bất kỳ mối quan hệ thứ bậc nào
CHAIN_APPROX_NONE lưu trữ tất cả các điểm của đường bao, nghĩa là hai điểm liền nhau (x1, y1) và (x2, y2) sẽ nằm trong các láng giềng ngang, dọc và chéo, với điều kiện max(abs(x1 - x2), abs(y2 - y1)) = 1.
Kết quả tìm đường bao theo thủ tục trên được minh họa như hình 3-2:
Hình 3-2: Kết quả tìm biên bằng phương pháp Canny từ ảnh đầu vào
Bước 3: Lấy mẫu n điểm trên đường bao
Trong trường hợp số điểm thực tế trên đường bao nhỏ hơn n thì thêm các điểm vào cho đủ:
Lấy mẫu n điểm ngẫu nhiên trên đường bao sử dụng phương thức: random_shuffle(contoursQuery.begin(), contoursQuery.end()); vector contQuery; for (int i = 0; i < n; i++)
Việc tìm đường bao và lấy mẫu được thực hiện theo thủ tục sau: int k = _contoursQuery.size(); std::vector colors; for (int i = 0; i