CHƯƠNG 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Việc so sánh các đối tượng nói chung và logo nói riêng qua ảnh là rất cần thiết. Để xác nhận hai đối tượng giống nhau thì chúng phải có hình dáng, màu sắc và kết cấu bề mặt giống nhau. Hiện nay với mỗi sự so sánh của mỗi trong 3 đặc điểm có rất nhiều phương pháp. Chương tiếp theo sẽ giới thiệu một số phương pháp phổ biến và mạnh thường được áp dụng hiện nay trong thực tế.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 CHƯƠNG 2 MỘT SỐ KỸ THUẬT SO KHỚP QUA ẢNH HIỆN NAY 2.1 So sánh sự tương xứng về hình dạng 2.1 Dùng khoảng cách Hausdorff [6] Khoảng cách Hausdorff là một trong những phương pháp đối sánh hình dạng dựa trên tương quan cổ điển. Khoảng cách Hausdorff thường được sử dụng để xác định vị trí trong một ảnh và đo độ tương tự trong hình dạng. Cho hai tập hợp điểm hữu hạn A={ a1, …, ap } and B = { b1, …, bq } khoảng cách Hausdorff được định nghĩa là H(A, B) = max(h(A,B), h(B, A)) (2.1) Trong đó h(A, B) = max min ||a-b|| (2.|| là một số chỉ tiêu cơ bản giữa các điểm của A và B (ví dụ: chuẩn L2 hoặc Euclide). Hàm h (A, B) được gọi là Hausdorff có hướng khoảng cách từ A đến B.
Nó xác định điểm aA xa nhất từ bất kỳ điểm nào của B và đo khoảng cách từ a đến láng giềng gần nhất của nó trong B (sử dụng định chuẩn||. Theo trực giác, nếu h (A, B) = d, thì mỗi điểm của A phải nằm trong khoảng cách d của một số điểm B và cũng có một số điểm của A chính xác là khoảng cách d từ điểm B gần nhất (điểm không phù hợp).1 a) Khoảng cách Hausdorff giữa 2 tập hợp A và B: dH( A , B) = và b) giữa 2 tập hợp X và Y. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Khoảng cách Hausdorff H(A, B) là max của h(A, B) và h(B, A).
Do đó, nó đo lường mức độ của không khớp giữa hai bộ bằng cách đo khoảng cách của điểm A xa nhất so với bất kỳ điểm nào của B và ngược lại. Tính khoảng cách Hausdoff [6] Từ định nghĩa về khoảng cách Hausdorff trong (2.2), chúng ta có H(A, B) = max(h(A, B), h(B, A)) = max(max min ||a-b||, max min ||a-b|| ) a∈A b∈B a∈A b∈B (2.3) Nếu chúng ta định nghĩa d(x) = minb∈B ||x - b|| and d’(x) = mina∈A ||a - x|| (2.4) Chúng ta có H ( A, B) max max d a , max d ' b aA bB (2.5) nghĩa là, H (A, B) có thể thu được bằng cách tính d(a) và d’(b) cho tất cả a A và bB, tương ứng. Công thức tính toán khoảng cách Hausdorff như là một hàm biến đổi: H A, B t max max min a (b t ) , max min a (b t ) aA bB bB aA max max min a t ) b , max min a (b t ) aA bB bB aA max max d (a t ), max d (b t ) ' aA bB (2.6) Ứng dụng khoảng cách Hausdorff so khớp đối tượng Với độ đo khoảng cách ở trên còn nhạy cảm với nhiễu. Do đó, khoảng cách Hausdorff đã được cải tiến bởi Rucklidge: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.7) Trong đó là giá trị vi phân thứ của g(x) trên tập x với một vài giá trị của f là 0 và 1.Ví dụ, giá trị vi phân thứ nhất chính là lớn nhất và giá trị vi phân 1/2 là trung bình.
Trong thực tế f thường đặt là 1/2. Ưu điểm của so khớp hình dạng sử dụng khoảng cách Hausdroff chính là hình dạng có thể được đối sánh cục bộ. Tuy nhiên khoảng cách này là không bất biến với các phép tịnh tiến, phép co dãn và phép quay.2 Dùng phương pháp Shape Context Phương pháp Shape Context nguyên thủy ra đời năm 2000 đề xuất của Serge Belongie và and Jitendra Malik thuộc Department of Electrical Engineering and Computer Sciences University of California at Berkeley, USA qua bài báo [7]. Shape Context được cải tiến với các mức hiệu quả hơn qua các công bố [8], [9].
Shape contexts có thể thực hiện so khớp các ảnh xám, ảnh đen trắng, qua một số ví dụ trong hình 2.2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Thực hiện truy vấn trên tập dữ liệu ETH-80 bằng phương pháp shape contexts. Cột đầu tiên là đối tượng truy vấn. Năm cột còn lại hiển thị kết quả so khớp gần nhất với từng đối tượng truy vấn.3 Truy vấn trên tập dữ liệu Kimia. Cột 1: hình ảnh truy vấn.
Cột 2-4: hình ảnh phù hợp, được sắp xếp theo độ tương tự. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 So khớp mẫu cột trái và độ giống nhau [8] Trong khuôn khổ luận văn em trình bày phương pháp trong [7] để so khớp hình dạng trong nhiệm vụ so khớp logo. Trước hết cần nhắc lại một số kiến thức của xử lý ảnh. Histogram: Định nghĩa đơn giản về Histogram trong xử lý ảnh số Lược đồ xám (histogram) của một ảnh là một hàm cung cấp tần suất xuất hiện của mỗi mức xám.
Lược đồ xám được biểu diễn với trục hoành biểu diễn số mức xám từ 0 đến N, N là số mức xám thường lấy là 255. Trục tung biểu diễn số điểm ảnh cho một mức xám (số điểm ảnh có cùng mức xám). Quan sát histogram của một ảnh có thể biết ảnh đó sáng hay tối. Nếu phân bố histogram lệch về bên phải thì đó là ảnh sáng (hình 2.
Nếu phân bố lệch về bên trái thì đó là ảnh tối (hình 2. Số điểm ảnh Số điểm ảnh a) b) Mức xám Mức xám Hình 2.5 Histogram của một ảnh xám Để hiểu rõ hơn chúng ta cần thấy rằng Histogram một dạng đồ thị cho phép khám phá, hiển thị dạng phân phối tần suất của một tập dữ liệu liên tục. Nó cho phép chúng ta kiểm tra dạng phân phối (chẳng hạn, phân phối chuẩn), các điểm dị biệt, độ trôi, độ nhọn của tập dữ liệu.6 Một đồ thị dạng histogram độ tuổi và tần suất LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 Xây dựng đồ thị histogram cho một biến liên tục Giả sử, chúng ta có một tập dữ liệu về tuổi của 20 lần quan sát như sau: Bảng 2.1 Dữ liệu tuổi Lần Tuổi Số người Quan sát 1 36 1 2 25 1 3 38 1 4 46 1 5 55 1 6 68 1 7 72 1 8 55 1 9 36 1 10 38 1 11 67 1 12 45 1 13 22 1 14 48 1 15 91 1 16 46 1 17 52 1 18 61 1 19 58 1 20 55 1 Để xây dựng đồ thị histogram từ một biến liên tục, việc đầu tiên là cần phải chuyển dữ liệu sang dạng các khoảng (interval), mà chúng ta gọi là các ngăn (bins). Trong ví dụ trên, biến tuổi được chia thành các bins, mỗi bin đại diện cho một nhóm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Mỗi bin gồm có số các quan sát thỏa mãn điều kiện của bin xuất hiện trong tập dữ liệu. Thông tin của mẫu dữ liệu trên được thể hiện dưới dạng các bins như trong bảng 2.2 Thông tin của mẫu dữ liệu Bin Tần số Các quan sát (tuổi) 20-30 2 25, 22 30-40 4 36, 38, 36, 38 40-50 4 46, 45, 48, 46 50-60 5 55, 55, 52, 58, 55 60-70 3 68, 67, 61 70-80 1 72 80-90 0 - 90-100 1 91 Chọn bề rộng cho các bins Chú ý chọn độ lớn các bin không quá nhỏ hoặc quá lớn. Như vậy histogram sẽ khó quan sát.7 Các bin của histogram quá nhỏ a) hoặc quá lớn b) Chúng ta có thể thấy rằng, ở đồ thị histogram bên trái thì độ rộng của bin là quá nhỏ bởi vì nó cho thấy quá nhiều các dữ liệu riêng rẻ và không thể hiện được dạng phân phối của tập dữ liệu. Ở phía ngược lại, ở đồ thị histogram bên phải thì các bins quá lớn và chúng ta cũng không thể phát hiện được dạng phân phối của dữ liệu.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 19 Các đồ thị histogram dựa vào diện tích chứ không phải là chiều cao của các thanh: Đối với đồ thị histogram, phần diện tích của thanh thể hiện tần số xuất hiện của mỗi bin. Điều này có nghĩa rằng chiều cao của thanh không cần thiết thể hiện số lần xuất hiện của mỗi quan sát trong mỗi bin. Tích số giữa chiều cao và chiều rộng của bin sẽ cho biết tần số xuất hiện của mỗi bin. Không giống đồ thị thanh (bar chart) đồ thị histogram không có các khoảng trống (gaps) giữa các thanh (mặc dù một vài thanh có thể có khoảng trống vì tần suất xuất hiện của nó bằng 0).
Điều này bởi vì, đồ thị histogram đặc trưng cho một dữ liệu liên tục. Ngoài ra, sự khác nhau chủ yếu giữa đồ thị histogram và đồ thị thanh (bar) là đồ thị histogram chỉ sử dụng để hiển thị tần số xuất hiện của các quan sát trong tập dữ liệu liên tục mà tập dữ liệu này được chia thành các khoảng (lớp) được gọi là các bins. Ngược lại, các đồ thị dạng thanh có thể được sử dụng cho các tập dữ liệu thuộc kiểu khác như thứ tự (ordinal) và định danh (nominal).8 Một ảnh a) và b) histogram của nó • Phương pháp Phương pháp của các tác giả [3] cho phép khắc phục các yếu tố khó khăn khi so khớp như các ảnh xoay, dịch, … Shape context: Là một cách mô tả các hình dạng cho phép đo độ tương tự hình dạng và phục hồi các điểm tương ứng điểm. Ý tưởng cơ bản là chọn n điểm trên LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 20 các đường biên của hình.
Đối với mỗi điểm pi trên hình, hãy xem xét các vectơ n - 1 thu được bằng cách kết nối pi với tất cả các điểm khác. Tập hợp tất cả các vectơ này là một mô tả phong phú về hình dạng được cục bộ hóa tại điểm đó nhưng quá chi tiết. Ý tưởng chính là sự phân phối trên các vị trí tương đối là một mô tả mạnh mẽ, nhỏ gọn và có tính phân biệt cao. Đối với mỗi pi điểm trên hình đầu tiên, chúng ta muốn tìm ra phù hợp “tốt nhất” điểm qj trên hình thứ hai.
Đối với điểm pi, histogram thô của tọa độ tương đối của n - 1 điểm còn lại.8) được định nghĩa là shape contexts của pi.