Đề tài Phát hiện biên, biểu diễn Fourier Elliptic và ứng dụng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN PHẠM NGỌC QUÝ PHÁT HIỆN BIÊN, BIỂU DIỄN FOURIER ELLIPTIC VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN ` Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên i ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN PHẠM NGỌC QUÝ PHÁT HIỆN BIÊN, BIỂU DIỄN FOURIER ELLIPTIC VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 604801 ` LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Ngƣời hƣớng dẫn khoa học: TS. Phạm Việt Bình Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên i MỤC LỤC Lời cảm ơn .................................................................................................... i Danh mục các ký hiệu, các chữ viết tắt ......................................................... ii Danh mục các hình ...................................................................................... iii MỞ ĐẦU ..................................................................................................... 1 CHƢƠNG 1. TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN ..................................... 3 1.1. Một số khái niệm cơ bản trong xử lý ảnh ............................................... 3 1.1.1. Xử lý ảnh. .................................................................................. 3 1.1.2 Quá trình thu nhận, biểu diễn và lưu giữ ảnh ............................... 3 1.1.3 Histogram của ảnh ...................................................................... 7 1.1.4 Nhận dạng ảnh ............................................................................ 8 1.2 Biên ảnh và vai trò trong nhận dạng ảnh ................................................. 9 1.2.1 Khái niệm về biên ảnh và các phương pháp phát hiện biên cơ bản........................................................................................... 9 1.2.2 Vai trò của biên trong nhận dạng ảnh ........................................ 14 1.2.3 Biểu diễn biên dựa trên mô tả Fourier ....................................... 14 1.2.3.1 Phương pháp dựa trên mô tả Fourier................................. 16 1.2.3.2 Phương pháp góc quay ............................................... 19 CHƢƠNG 2: MỘT SỐ PHƢƠNG PHÁP PHÁT HIỆN BIÊN VÀ PHÉP BIỂU DIỄN FORIER ELLIPTIC ............................................................. 22 2.1 Một số phương pháp phát hiện biên ...................................................... 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ii 2.1.1. Phương pháp phát hiện biện trực tiếp ....................................... 22 2.1.2 Phương pháp phát hiện biên gián tiếp ........................................ 31 2.1.3 Phương pháp phát hiện biên kết hợp.......................................... 32 2.1.4 Phát hiện biên dựa vào trung bình cục bộ .................................. 38 2.1.5 Cải thiện và nâng cao chất lượng biên ảnh ................................ 40 2.2 Phép biến đổi Fourier ........................................................................... 49 2.2.1 Định nghĩa ................................................................................ 49 2.2.1 Elliptic Fourier .......................................................................... 50 2.2.3 Biến đổi Fourier rời rạc ............................................................. 55 2.2.4 Các thuộc tính khác của biến đổi Fourier .................................. 61 CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM ..................................................... 62 3.1 Giới thiệu ............................................................................................. 62 3.2 Số hóa biên đối tượng ảnh .................................................................... 62 3.2 Chương trình thử nghiệm ..................................................................... 66 KẾT LUẬN ................................................................................................................. 70 TÀI LIỆU THAM KHẢO ............................................................................................ 72 Tiếng Việt .................................................................................................. 72 Tiếng Anh .................................................................................................. 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên i LỜI CẢM ƠN Trong quá trình làm luận văn thạc sĩ với đề tài “Phát hiện biên, biểu diễn Fourier Elliptic và ứng dụng”, em đã nhận được nhiều đóng góp và tạo điều kiện của các thầy cô và đồng nghiệp. Lời đầu tiên em xin chân thành cảm ơn tới toàn thể các thầy cô, những người đã giảng dạy em. Đặc biệt, em xin tỏ lòng cảm ơn chân thành và sâu sắc tới thầy thầy Phạm Việt Bình, người đã luôn tận tình hướng dẫn, định hướng, và có những chỉ bảo cặn kẽ em trong thời suốt thời gian qua. Em rất cảm ơn các bạn, các đồng nghiệp đã động viên, khích lệ, cũng như trao đổi tài liệu cho em trong thời gian làm luận văn. Em cũng chân thành mong được sự đóng góp ý kiến của các thầy, các cô và các đồng nghiệp để em có phát triển đề tài trong thời gian tới. Xin chân thành cảm ơn ! Thái Nguyên, ngày 12 tháng 11 năm 2009 Học viên Phạm Ngọc Quý Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ii Danh mục các ký hiệu, các chữ viết tắt CSDL Cơ sở dữ liệu FD (Fourier descriptors) - Mô tả Fourier Pixel Điểm ảnh Radius Bán kính RGB Không gian màu RGB Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên iii Danh mục các hình Hình 1.1 Các giai đoạn chính trong quá trình xử lý ảnh ................................ 3 Hình 1.2 Điểm 8 láng giềng và điểm 4 láng giềng ........................................ 6 Hình 1.3(a) Đồ thị biểu diễn Histogram ảnh ................................................. 8 Hình 1.3(b) Ảnh gốc..................................................................................... 8 Hình 1.3(c) Histogram của ảnh gốc theo RGB và Gray ................................ 8 Hình 1.4 Ví dụ chu tuyến của đối tượng ảnh .............................................. 12 Hình 1.5 Phân loại biểu diễn hình dạng và các kỹ thuật biểu diễn .............. 15 Hình 1.6 Biểu diễn góc quay ...................................................................... 20 Hình 1.7 Biểu diễn góc quay trong trường hợp có thay đổi nhỏ .................. 21 Hình 2.1 Mô hình 8 hướng ......................................................................... 23 Hình 2.2 Ảnh trước khi dò biên .................................................................. 24 Hình 2.3 Ảnh sau khi dò biên ..................................................................... 25 Hình 2.4 (a) Ảnh gốc (b) Đạo hàm bậc nhất (c) Đạo hàm bậc hai ............... 25 Hình 2.5(a) Ảnh gốc (b) Ảnh biên dùng Laplace H1 (a) Ảnh biên H2 ......... 27 Hình 2.6 Minh họa biểu diễn biên nhờ các phép hình thái .......................... 30 Hình 2.7 Ảnh gốc ....................................................................................... 33 Hình 2.8 Ảnh đen trắng .............................................................................. 33 Hình 2.9 Ảnh đen trắng dùng hàm ConvertRGB ........................................ 34 Hình 2.10 Ảnh đen trắng ............................................................................ 34 Hình 2.11 Biên của ảnh đen trắng............................................................... 35 Hình 2.12 Ảnh gốc ..................................................................................... 36 Hình 2.13 Ảnh biên với cách đánh giá độ chênh lệch mức xám của điểm ảnh ..................................................................................................... 36 Hình 2.14 So sánh với mức xám trung bình của cửa sổ ảnh trong trường hợp N=5 .......................................................................................... 36 Hình 2.15 Xác định điểm biên thực sự ....................................................... 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên iv Hình 2.16 Ảnh biên kết hợp phương pháp kết hợp với N =5 ...................... 37 Hình 2.17 Ma trận điểm ảnh trước và sau lọc ............................................. 39 Hình 2.18 Các ảnh biên kết quả thu được theo thuật toán đề xuất ............... 39 Hình 2.19 Lấy tổ hợp các điểm ảnh lân cận ................................................ 41 Hình 2.20 Một số kiểu mặt nạ sử dụng cho kỹ thuật lọc phi tuyến.............. 41 Hình 2.21 Minh họa thuật toán hậu xử lý ................................................... 46 Hình 2.22 Ví dụ về chain code ................................................................... 51 Hình 2.23 Minh họa sự kết hợp của chuỗi mã 4, 8-láng giềng ................... 52 Hình 2.24 Minh họa chuỗi mã .................................................................... 54 Hình 2.25 Biển đổi xung mẫu ..................................................................... 57 Hình 2.26 Ảnh dùng biến đổi Fourier rời rạc 2D ........................................ 58 Hình 2.27 (a) Ảnh mặt (b) Biển đổi ảnh mặt .............................................. 60 Hình 2.28 Biến đổi Fourier 2D ................................................................... 61 Hình 3.1 Thuật toán số hóa biên ảnh của đối tượng ảnh ............................. 63 Hình 3.2 Thuật toán chaincodeal ................................................................ 64 Hình 3.3 Lá gấc ban đầu ............................................................................. 66 Hình 3.4 Lá gấc sau khi Histogram ............................................................ 67 Hình 3.5 Lá gấc sau khi chain code ............................................................ 67 Hình 3.6 (a) Lá gấc trước khi được xử lý .................................................... 68 Hình 3.6 (b) Lá gấc sau khi được xử lý ...................................................... 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên v Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 PHẦN MỞ ĐẦU Xử lý ảnh là một lĩnh vực đã và đang được quan tâm của nhiều nhà khoa học trong và ngoài nước bởi tính phong phú và lợi ích của nó được ứng dụng trong khoa học kỹ thuật, kinh tế, xã hội và đời sống con người. Lĩnh vực xử lý ảnh liên quan tới nhiều ngành khác như: hệ thống tin học, trí tuệ nhân tạo, nhận dạng, viễn thám, y học, nông học... Hiện nay, thông tin hình ảnh đóng vai trò rất quan trọng trong trao đổi thông tin, bởi phần lớn thông tin mà con người thu được thông qua thị giác. Do vậy, vấn đề nhận dạng trong xử lý ảnh, đặc biệt là nhận dạng biên ảnh đang được quan tâm bởi yêu cầu ứng dụng đa dạng của chúng trong thực tiễn. Mục đích đặt ra cho xử lý ảnh được chia thành hai phần chính: phần thứ nhất liên quan đến những khả năng từ các ảnh thu lại các ảnh để rồi từ các ảnh đã được cải biến nhận được nhiều thông tin để quan sát và đánh giá bằng mắt, chúng ta coi như là sự biến đổi ảnh (image transformation) hay sự làm đẹp ảnh (image enhancement). Phần hai nhằm vào nhận dạng hoặc đoán nhận ảnh một cách tự động, đánh giá nội dung các ảnh. Quá trình nhận dạng ảnh nhằm phân loại các đối tượng thành các lớp đối tượng đã biết (supervised learning) hoặc thành những lớp đối tượng chưa biết (unsupervised learning). Sau quá trình tăng cường và khôi phục (đối với những ảnh có nhiễu), giai đoạn tiếp theo, người ta phải trích rút các đặc tính quan trọng, quyết định của ảnh cần nhận dạng. Các đặc tính đó có thể là đặc tính hình học, đặc tính ngữ cảnh. Các đặc tính hình học chứa những thông tin về vị trí, kích thước hình học, hình dạng của các đối tượng trong ảnh, là đặc tính rất quan trọng trong xử lý nhận dạng ảnh. Các đặc tính này thường được trích rút ra thông qua việc xác định các đường biên các đối tượng trong ảnh. Biên chứa các thông tin về Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 hình dạng ngoài của đối tượng ảnh. Có thể nói xác định biên là một trong những vấn đề quan trọng và hấp dẫn trong lĩnh vực nghiên cứu xử lý ảnh bởi khả năng biểu đạt cấu trúc đối tượng và tính ứng dụng rộng rãi của nó vào việc giải quyết nhiều bài toán khó như: nhận dạng tự động, thị thực máy tính, hoạt hình… Bên cạnh đó, trong những năm gần đây các nghiên cứu về biên ảnh và phép biến đổi Fourier đã và đang được ứng dụng rộng rãi. Thực tế này đặt ra các bài toán như: đưa những ứng dụng đó vào xã hội và đời sống con người. Một số nhóm nghiên cứu trong và ngoài nước đã đưa ra các phương pháp giải quyết kết hợp các phương pháp phát hiện biên và phép biến đổi Fourier để hoàn thành những ứng dụng góp phần vào sự phát triển trong xã hội. Chình vì những ứng dụng thực tiễn đó em đã nghiên cứu luận văn thạc sĩ với đề tài “Phát hiện biên, biểu diễn Forier Elliptic và ứng dụng”. Luận văn gồm phần mở đầu, phần kết luận, và 3 chương nội dung: Chương 1: Tổng quan về xử lý ảnh và biên. Chương 2: Một số phương pháp phát hiện biên và phép biểu diễn Fourier Elliptic. Chương 3: Chương trình thử nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 CHƢƠNG 1: TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ BIÊN 1.1. Một số khái niệm cơ bản trong xử lý ảnh 1.1.1. Xử lý ảnh Xử lý ảnh(Image processing) là đối tượng nghiên cứu của lĩnh vực thị giác máy, là quá trình biến đổi từ một ảnh ban đầu sang một ảnh mới với các đặc tính mà tuân theo ý muốn của việc xử lý. Xử lý ảnh có thể là quá trình phân tích, phân lớp các đối tượng, làm tăng chất lượng, phân đoạn và tìm biên, gán nhãn cho vùng hay quá trình biên dịch các thông tin hình ảnh của ảnh. Hình dưới sẽ minh họa các giai đoạn chính trong quá trình xử lý ảnh. Hình 1.1. Các giai đoạn chính trong quá trình xử lý ảnh 1.1.2. Quá trình thu nhận, biểu diễn và lƣu giữ ảnh 1.1.2.1.Quá trình thu nhận ảnh Ảnh tồn tại trong thực tế là một ảnh liên tục cả về không gian cũng như về giá trị độ sáng, và việc thu nhận ảnh có thể dùng Scanner, camera... Muốn đưa ảnh liên tục trong thực tế vào máy tính để xử lý cần phải qua một khâu trung gian đó là quá trình số hoá. Số hoá là quá trình rời rạc hoá về không gian và lượng tử hoá về giá trị.Quá trình rời rạc hoá về không gian là quá trình thu nhận những điểm rời rạc từ một ảnh liên tục, nhưng phải đảm bảo bằng mắt thường không phân biệt được hai điểm kề nhau. Quá trình này cũng HÖ Q.®Þnh L•u tr÷ SENSOR Sè ho¸ Thu nhËn ¶nh NhËn d¹ng camera L•u tr÷ Ph©n tÝch ¶nh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 chính là việc tìm cách biểu diễn cả một ảnh lớn có vô số điểm, bởi một số hữu hạn điểm, sao cho không làm mất đi hay thay đổi tính chất của ảnh, để việc lưu trữ và xử lý ảnh được dễ dàng. Còn quá trình lượng tử hoá về giá trị là quá trình rời rạc hoá về mặt giá trị để có thể đơn giản hoá việc tính toán và đưa vào máy để xử lý. Tuỳ theo từng loại ảnh, độ chính xác yêu cầu và khả năng xử lý của máy tính mà ta có các mức lượng tử thích hợp. Ví dụ với ảnh 256 cấp xám, ta phải dùng 256 mức lượng tử và biểu diễn trong máy tính bằng 8 bits. 1.1.2.2. Quá trình biểu diễn ảnh Sau quá trình số hoá sẽ thu được một ma trận tương ứng với ảnh cần xét, mỗi phần tử của ma trận tương ứng với một điểm ảnh. Ảnh thường được biểu diễn bởi một mảng hai chiều I(n,p) gồm n dòng và p cột. Như vậy, ảnh gồm nxp pixels và người ta thường kí hiệu I(x,y) để chỉ một pixel cụ thể trong ảnh. Các điểm này được đặc trưng bằng toạ độ màu (R,G,B) tương ứng với nó trên hệ toạ độ màu cơ bản sau: Trong đó R = Red, G = Green, B = Blue Hệ toạ độ (R,G,B ) là hệ cơ bản nhất, người ta đã chứng minh được R,G,B là ba màu độc lập, là một hệ cơ sở. Hầu như các màu khác nhau trong Black Blue Cyan White Green Yellow Red Mag Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 thực tế đều có thể biểu diễn bởi toạ độ của chúng trong hệ toạ độ này, tức là từ ba màu này chúng ta có thể tổng hợp được nhiều màu trong thực tế. Xét một số trường hợp đặc biệt sau:  Màu đen (Black) tạo bởi R=B=G=0  Màu vàng (Yellow) tạo bởi R=G=1, B=0  Màu tím (Magenta) tạo bởi R=B=1, G=0  Màu xanh (Cyan) tạo bởi R=0, G=B=1  Màu trắng (White) tạo bởi R=G=B=1 Từ đó ta có thể thấy rằng, ảnh đa cấp sáng là trường hợp đặc biệt của ảnh màu, trong đó các thành phần tọa độ màu tương ứng bằng nhau (R=G=B=1). Về mặt toán học có thể xem ảnh là một hàm hai biến f(x,y) với x,y là các biến tọa độ. Giá trị số ở điểm (x,y) tương ứng với giá trị xám hoặc độ sáng của ảnh (x là các cột còn y là các hàng). Giá trị của hàm ảnh f(x,y) được hạn chế trong phạm vi của các số nguyên dương. 0 = f(x,y) = fmax Thông thường đối với ảnh xám, giá trị fmax là 255 ( 2 8 =256) và mỗi phần tử ảnh được mã hóa bởi một byte. Ảnh có thể được biểu diễn theo một trong hai mô hình: mô hình Vector hoặc mô hình Raster.  Mô hình Raster: là mô hình biểu diễn ảnh thông dụng nhất hiện nay. Ảnh được biểu diễn dưới dạng ma trận các điểm ảnh. Tùy theo nhu cầu thực tế mà mỗi điểm ảnh có thể được biểu diễn bởi một hay nhiều bit. Mô hình Raster thuận lợi cho việc thu nhận, hiển thị và in ấn.  Mô hình Vector: Bên cạnh mục đích tiết kiệm không gian lưu trữ, dễ dàng hiển thị và in ấn, các ảnh biểu diễn theo mô hình vector còn có ưu điểm cho phép dễ dàng lựa chọn, sao chép, di chuyển, tìm kiếm … Theo những yêu cầu này thì kỹ thuật biểu diễn vector tỏ ra ưu việt hơn. Trong mô hình này, người ta sử dụng hướng vector của các điểm ảnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 lân cận để mã hóa và tái tạo lại hình ảnh ban đầu. Các ảnh vector được thu nhận trực tiếp từ các thiết bị số hóa như Digitalize hoặc được chuyển đổi từ các ảnh Raster thông qua các chương trình vector hóa. Khi xử lý các ảnh Raster chúng ta có thể quan tâm đến mối quan hệ trong vùng lân cận của các điểm ảnh. Các điểm ảnh có thể xếp hàng trên một lưới (raster) hình vuông, lưới hình lục giác hoặc theo một cách hoàn toàn ngẫu nhiên với nhau. Cách sắp xếp theo hình vuông là được quan tâm đến nhiều nhất và có hai loại: điểm 4 láng giềng (4 liền kề) hoặc 8 láng giềng (8 liền kề). Hình dưới đây minh họa điểm 4 láng giềng và điêm 8 láng giềng. 1.1.2.3. Lưu giữ ảnh Trong sự phát triển công nghệ thông tin nói chung, một vấn đề lớn chi phối các hoạt động thuộc lĩnh vực này là vấn đề bộ nhớ. Cần thiết phát triển quá trình xử lý thông tin sao cho nhanh chóng và chính xác, song cũng cần phát triển khả năng lưu trữ, bảo toàn các thông tin này. Các thế hệ máy tính ngày nay đã có bộ nhớ rất lớn, song bao giờ nó cũng ít đối với những gì chúng ta muốn lưu trữ và xử lý. Trong kĩ thuật xử lý ảnh cũng vậy, vì lượng thông tin chứa trong một bức ảnh là khá lớn, lên việc lưu giữ nó là vấn đề cần quan tâm. Trong thực tế ma trận điểm ảnh tạo ra bởi quá trình số hoá, được H×nh 1.2 : §iÓm 8 l¸ng giÒng vµ ®iÓm 4 l¸ng giÒng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 lưu trữ trong máy tính dưới dạnh các files và thường thì các files này được nén để tiết kiệm bộ nhớ . Hầu hết các files ảnh đều có phần đề ở đầu files để ghi những thông tin cơ bản về ảnh như: Kích thước ảnh, số planes, số bits cho một điểm ảnh ... Trong thực tế, ta hay gặp và xử lý đầu vào là các ảnh bitmap đó là ảnh được tạo ra từ các điểm ảnh. Ngoài ra trong quá trình thực hiện, sau một số phép biến đổi có thể chuyển nó về dạng vectơ có đơn vị là các đường để tiện cho việc lưu giữ. 1.1.3. Histogram của ảnh Như ta đã biết, mỗi điểm có một giá trị độ sáng nào đó. Histogram của ảnh là đồ thị cho biết tần suất hiện các điểm ảnh với các mức biến thiên độ sáng. Thí dụ: Có một ảnh 100 điểm , độ sáng của ảnh được phân thành 5 mức sáng: level1, level2,..., level 5. Số điểm ảnh của các mức tương ứng là 20,