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ự thay đổi đột ngột về mức xám của điểm ảnh Một điểm ảnh được xem là biên nếu nó có sự khác biệt rõ rệt với các điểm lân cận, tạo thành đường bao của ảnh Chẳng hạn, trong ảnh nhị phân, một điểm đen được coi là biên nếu nó 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ỉ với vài nét, người xem vẫn có thể nhận ra đó là bàn Điều này cho thấy rằng trong phân lớp nhận diện đối tượng, việc nhận diện chỉ dựa vào biên có thể đủ, nhưng để đạt yêu cầu cao hơn về chi tiết như vân gỗ hay màu sắc, thông tin biên đơn thuần là chưa đủ.
Trong toán học, điểm biên của ảnh được xác định là những điểm có sự biến đổi đột ngột về độ xám, và tập hợp các điểm này được gọi là đường biên 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 đáng kể khối lượng dữ liệu cần tính toán bằng cách 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 của 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 trong các đối tượng Định nghĩa toán học về biên là cơ sở 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 vùng thường nhỏ, trong khi biến thiên mức xám tại các điểm vùng giáp ranh lại lớn.
1.1.2 Phân loại các kỹ thuật phát hiện biên
Trong lĩnh vực toán học, biên được định nghĩa thông qua hai phương pháp phát hiện 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 của độ sáng điểm ảnh, sử dụng kỹ thuật đạo hàm Đạo hàm bậc nhất tạo ra phương pháp Gradient, trong khi đạo hàm bậc hai dẫn đến kỹ thuật Laplace, cả hai đều thuộc về phương pháp dò biên cục bộ Bên cạnh đó, phương pháp "đi theo đường bao" còn được áp dụng, gọi là phương pháp dò biên tổng thể, dựa trên nguyên lý quy hoạch hoạt động.
Khi phân chia ảnh thành các vùng, đường biên giữa các khu vực đó được gọi là biên 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, với 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, 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
Để xử lý ảnh thu nhận có nhiễu, bước đầu tiên là khử nhiễu bằng các kỹ thuật khác nhau Sau khi khử nhiễu, bước tiếp theo là làm nổi biên để tăng cường độ rõ nét của 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 vấn đề đố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 cần phân tích 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ử được thiết kế để phát hiện 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 tìm kiếm 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 được áp dụng, 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 cả 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 các đườ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 Toán tử Sobel có hình dạng như đã mô tả.
Hình 1-2: Toán tử Sobel 1.1.4.1.2Toán tử Prewitt
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
Giống như phương pháp Sobel, chúng ta tính toán đường biên ngang và dọc riêng biệt bằng cách sử dụng hai mặt nạ như hình 1-4, sau đó tổng hợp để tạo ra đườ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ả thu được thường bị ảnh hưởng nhiều 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 đặc trưng bằng một vector xác định đường bao, không phân chia hình dạng thành các phần Đo khoảng cách giữa các vector đặc trưng thường được áp dụng để đánh giá độ tương tự của hình dạng.
Phương pháp tiếp cận cấu trúc trong phân tách hình dạng chia các đường bao thành các đoạn dựa trên điều kiện phân tách Biểu diễn cuối cùng thường sử dụng chuỗi, đồ thị hoặc cây, với các biện pháp tương tự được thực hiện thông qua việc kết hợp chúng một cách hợp lý Các thuật toán đối sánh chuỗi và đồ thị được áp dụng để đo độ tương tự hình dạng, nhằm đạt được kết quả chính xác.
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 giữa hai hình dạng thường được thực hiện đơn giản thông qua việc sử dụng các độ đo khoảng cách, như khoảng cách Euclide.
Euclide, hoặc khoảng cách cityblock, và nó cũng thường được sử dụng trong các ứng dụng thực tế.
Hình dạng toàn cục đượ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 các mô tả hình dạng chính xác, cần kết hợp với những 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ả 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 Những mô tả này thường chỉ phân biệt được hình dạng có sự khác biệt lớn, do đó chúng thường được dùng để lọc và loại bỏ các 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 mô tả hình dạng độc lập Ví dụ, độ lệch tâm của hình dạng trong hình 1-7(a) gần bằng 1 (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ẽ mô tả tốt 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 rất khác nhau, vì vậy độ lệch tâm sẽ là mô tả chính xác 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ây dài, dây cung và diện tích.
Dấu hiệu đặc trưng 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 đồ dấu hiệu để sử dụng cho đố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 việc đối sánh Do đó, dấu hiệu đặc trưng hình dạng thường không được sử dụng trực tiếp để mô tả hình dạng.
Momen biên có khả năng giảm kích thước của 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à mr và momen tóm là àr, có thể sử dụng công thức ước tính như sau:
Trong đó, N là số các điểm biên
Mô tả momen đường bao, được thể hiện qua công thức M r = M r / (M 2) r / 2, giúp mô tả tính bất biến của hình dạng dưới các phép biến đổi như dịch chuyển, quay và co dãn Ưu điểm của phương pháp này là dễ thực hiện, nhưng việc gán các momen bậc cao hơn với các giải thích 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 chuỗi tổng quát S = S1, S2, …, Sn Mỗi Si đại diện cho một phần tử của mã xích, có thể là cạnh của đa giác, hình vuông hoặc mặt spline Các phần tử này 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 Những chuỗi này không chỉ dùng để mô tả hình dạng mà còn có thể được sử dụng làm đầu vào cho các ứng dụng khác.
Mã xích mô tả đường biên đối tượng bằng chuỗi đoạn thẳng đơn vị với 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, trong đó một đường cong được biểu diễn bằng chuỗi vector đơn vị chiều dài và giới hạn hướng cho phép, gọi là phương pháp vector đơn vị 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à sau đó được lấy mẫu 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 sao cho 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 Hơn nữa, 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 này sẽ được dùng để biểu diễn hình dạng của đối tượng.
Mã xích có nhiều hạn chế trong việc biểu diễn hình dạng và đối sánh do bị ảnh hưởng bởi nhiễu đường biên và biến dạng, cùng với đó là kích thước dài của chuỗi mã Thông thường, mã xích được sử dụng làm đầ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ủa các phân đoạn đường thẳng có độ dài và định hướng quy đị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ố Các hình ảnh kỹ thuật số thường được xử lý theo định dạng lưới, đảm bảo 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ácnhà 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ể đối sánh và độ đo tương tự Đố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 Hơn nữa, nó dễ dẫn đến sự nhập nhằng do giá trị mức xám lặp lại và nhiễu ảnh Do đó, bài toán đối sánh ảnh thuộc nhóm bài toán giả định yếu Để biế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, ràng buộc hình học và giả thiết trong một giới hạn nhất định 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 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à các 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 Mẫu, thường có kích thước m*n với m=n, được cắt từ ảnh và sử dụng để tìm kiếm trong ảnh thứ hai, với vị trí trung tâm là điểm ảnh chính Việc so sánh được thực hiện trong một vùng tìm kiếm hạn chế, nơi giá trị độ đo tương tự được tính toán cho từng vị trí của mẫu Các điểm tương ứng với tâm của mẫu sẽ có độ đo tương tự lớn nhất hoặc nhỏ nhất, và trong quy trình quan trắc, các công nghệ như tương quan chéo và đối sánh bình phương nhỏ nhất thường được áp dụng Thêm vào đó, thông tin tương hỗ và khoảng cách ảnh cũng có thể được sử dụng để cải thiện kết quả.
Ngược lại với phương pháp đối sánh dựa trên vùng, các phương pháp dựa trên đặc trưng sử dụng các toán tử trực tiếp trên các giá trị mức xám để so sánh các đặc trưng được trích chọn như điểm, cạnh hoặc vùng Quy trình đố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 ả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 cao với độ dốc gradient lớn Những điểm này cần có tính khác biệt và bất biến trước các biến đổi hình học và phổ, đảm bảo sự ổn định, tức là phải 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ổ đánh giá Chỉ những cửa sổ có giá trị tham số vượt ngưỡng mới được chấp nhận là điểm đặc trưng Danh sách điểm đặc trưng của mỗi ảnh sẽ được đối sánh với tọa độ và mô tả của nó Trong nghiên cứu của Luhmann và Altrogge (1986), ba toán tử điểm đặc trưng được đề xuất, bao gồm Moravec.
Forstner và Dreschler Tuy nhiên Moravec và Forstner hoạt động tốt hơn với việc tìm kiếm các điểm đặc trưng theo các điều kiện hình học khác nhau.
Các cạnh trong hình ảnh được xem như những đ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 hiển thị Quá trình trích chọn cạnh là một nhiệm vụ phức tạp, 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, 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 các điểm ảnh nào là điểm cạnh.
Liên kết các điểm cạnh thành các cạnh
Nhómcá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 giúp phát hiện sự thay đổi giá trị mức xám trong ảnh bằng cách sử dụng đạo hàm bậc nhất của các hàm mức xám để xác định cực trị và vị trí điểm cạnh Một số toán tử cạnh phổ biến có thể được áp dụng trong quá trình này.
Toán tử Sobel, do Robert Cross phát triển, là một công cụ mạnh mẽ trong việc phát hiện biên của hình ảnh Cả hai toán tử này đều dựa trên hướng, giúp phát hiện các cạnh theo chiều ngang và chiều dọc Đặc biệt, toán tử Sobel ít bị ảnh hưởng bởi nhiễu trong ảnh nhờ vào việc xem xét 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 Sau khi áp dụng toán tử Laplacian lên ảnh gốc, các điểm cạnh sẽ có giá trị bằng zero Toán tử LoG tương tự như toán tử đạo hàm bậc nhất và được mô tả chi tiết trong các 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 trong việc mô tả nội dung ảnh, nhưng việc biểu diễn và mô tả chúng gặp nhiều khó khăn Khi một đối tượng 3-D được chiếu lên mặt phẳng 2-D, một chiều thông tin sẽ bị mất, dẫn đến việc hình dạng chỉ phản ánh một phần của đối tượng Thêm vào đó, hình dạng thường bị hỏng, biến dạng, cắt bỏ, nhiễu và trùng lặp, làm cho quá trình nhận diện trở nên phức tạp hơn.
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 Đã có 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 khoảng cách giữa các bin, được sử dụng để 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 áp 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 dưới dạng 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:
Độ đo khoảng cách Hausdorff rất nhạy cảm với nhiễu và các điểm ngoại lai, điều này dẫn đến việc cá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 được xác định bởi một số giá trị của f, trong đó f thường được đặt là 1/2 Ví dụ, giá trị vi phân thứ nhất là lớn nhất, trong khi giá trị vi phân 1/2 là trung bình Một ưu điểm nổi bật của việc đối sánh hình dạng thông qua khoảng cách Hausdorff là khả năng đối sánh cục bộ Tuy nhiên, cần lưu ý rằ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 đóng vai trò quan trọng trong việc 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 biến đổi phi tuyến và có thể có cấu trúc nhập nhằng Để giải quyết những vấn đề 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 nhận diện hình ảnh Đặc biệt, khoảng cách này 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ự, cấu trúc thành phần của chúng lại 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 nhưng 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 nhau, trong khi hình (b) và hình (c) lại có nhiều điểm tương đồng Điều này cho thấy khoảng cách trong nhạy cảm với cấu trúc thành phần nhưng không nhạy cảm với cấu trúc khớp nối, làm cho nó trở thành một 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 tính toán.
Việc áp dụng khoảng cách trong như một giải pháp thay thế cho 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à liên thông trong R², trong đó 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 gặp, có thể xuất hiện nhiều đường dẫn ngắn nhất giữa các điểm đã cho 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 xác định qua các đường biên, trong đó chỉ những điểm biên được sử dụng làm dấu hiệu nhận diện Hơn nữa, hình dạng có thể được xấp xỉ bằng một đa giác, đượ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, trong đó mỗi điểm mẫu được xem như một nút trong đồ thị Tiếp theo, nếu đoạn nối giữa hai điểm mẫu p1 và p2 hoàn toàn nằm trong đối tượng, một cạnh sẽ được thêm vào giữa p1 và p2 với trọng số tương ứng 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 là áp dụng thuật toán tìm đường đi ngắn nhất cho đồ thị, 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 thời gian O(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 Sau đó, việc xây dựng đồ thị có độ phức tạp O(n³) Khi đồ thị đã hoàn tất, 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³) Tổng độ phức tạp tính toán của toàn bộ quá trình là 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 bộ 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 của các điểm đại diện xung quanh những đ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 của mối quan hệ tọa độ của n - 1 điểm còn lại.
Trong bài viết này, chúng ta xem xét việc chia các bin đều trong không gian log-polar Hình 2-4 minh họa quá trình tính toán với các biểu đồ (a) và (b) thể hiện các điểm mẫu trên hai hình dạng khác nhau Biểu đồ (c) là một ví dụ về 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 trong (d) với các điểm được đánh dấu trong (a), và (e) cho các điểm trong (b), trong khi (f) đại diện cho hình tam giác Hình (d) và (e) cho thấy ngữ cảnh hình dạng của hai điểm tương tự nhau, trong khi ngữ cảnh hình dạng trong (f) lại rất khác biệ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 đến n đến 0 đến m, trong đó p i được đối sánh với q (i) nếu p(i) khác 0; ngược lại, không có đối sánh Hàm chi phí đối sánh C( ) được định nghĩa theo cách này.
Trong đó, c(i, 0) = τ đại diện cho chi phí phạt khi điểm p_i không được đối sánh, và với 1 ≤ j ≤ m, c(i, j) là chi phí đối sánh giữa p_i và q_j Đo lường này được thực hiện thông qua hàm thống kê χ² theo công thức đã nêu.
(2.13) Ở đây, hA,ivà 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 đồ.
Do các đường bao được cung cấp theo thứ tự tự nhiên cho các chuỗi điểm p1, p2,…, pn và q1, q2,…, qm, điều này vô tình hạn chế khả năng đối sánh Để khắc phục vấn đề này, kỹ thuật Quy hoạch động (DP) đã được áp dụng nhằm giải quyết vấn đề đối sánh hiệu quả DP là một phương pháp phổ biến trong việc giải quyết 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 điều kiện n >= m Sự đối sánh từ A đến B được định nghĩa là một ánh xạ từ các chỉ số 1, 2, …, n đến các chỉ số 0, 1, 2, của hình B.
…, 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 đối sánh, trong khi với 1