Tài liệu Nghiên cứu vài kỹ thuật nắn chỉnh và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Lê Thị Thuỷ NGHIÊN CỨU MỘT SỐ KỸ THUẬT NẮN CHỈNH VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ Hà Nội – 2007 MỤC LỤC BẢNG CÁC TỪ VIẾT TẮT........................................................................... 3 DANH MỤC CÁC BẢNG .............................................................................. 3 DANH MỤC CÁC HÌNH VẼ………………………………………….........3 Chương 1. TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ NẮN CHỈNH .................. 9 BIẾN DẠNG .................................................................................................... 9 1.1. Xử lý ảnh và vấn đề cơ bản trong xử lý ảnh ......................................... 9 1.1.1. Xử lý ảnh là gì .................................................................................. 9 1.1.2. Một số khái niệm trong xử lý ảnh .................................................. 10 1.1.3. Các vấn đề cơ bản trong xử lý ảnh ................................................. 11 1.2. Nắn chỉnh biến dạng và ứng dụng ........................................................ 15 1.2.1. Phân loại nắn chỉnh biến dạng ....................................................... 15 1.2.2. Xác định cơ sở để nắn chỉnh ......................................................... 17 1.2.3. Một số ứng dụng của nắn chỉnh biến dạng .................................... 18 Chương 2. MỘT SỐ KỸ THUẬT NẮN CHỈNH BIẾN DẠNG................ 25 2.1. Nắn chỉnh trên cơ sở tập các điểm điều khiển ................................... 25 2.2. Nắn chỉnh trên cơ sở các vector ........................................................... 27 2.2.1. Chuyển đổi với một cặp vector ...................................................... 27 2.2.2. Chuyển đổi với nhiều cặp vector ................................................... 29 2.3. Nắn chỉnh trên cơ sở phân vùng ảnh .................................................. 32 2.3.1. Phân hình tam giác ......................................................................... 32 2.3.2. Phân hình tứ giác ............................................................................ 34 2.3.3. Kỹ thuật biến đổi dựa trên lưới B-Spline ....................................... 35 2.4. Kỹ thuật nắn chỉnh dựa trên hàm radial ............................................ 37 2.4.1. Xác định hàm ánh xạ ...................................................................... 37 1 2.4.2. Phân loại RBFT .............................................................................. 38 2.4.3. Lựa chọn hàm cơ sở g .................................................................... 40 2.4.4. Tính giải được ................................................................................ 41 2.4.5. Nhận xét ......................................................................................... 44 2.5. Nắn chỉnh dựa trên biên của đối tượng .............................................. 46 2.5.1. Các khái niệm cơ bản ..................................................................... 46 2.5.2. Phương thức Peel-and-resample .................................................... 48 2.5.3. Phương thức lan truyền sóng.......................................................... 53 Chương 3. ỨNG DỤNG NẮN CHỈNH BIẾN DẠNG ................................ 57 3.1. Nắn chỉnh sách ....................................................................................... 57 3.1.1. Bài toán .......................................................................................... 57 3.1.2. Tạo mẫu sách .................................................................................. 57 3.1.3. Thuật toán nắn chỉnh khung đối tượng .......................................... 58 3.1.4. Thuật toán biểu diễn bề mặt ........................................................... 59 3.2. Nắn chỉnh răng ....................................................................................... 61 3.2.1. Bài toán .......................................................................................... 61 3.2.2. Cấu tạo mặt người .......................................................................... 61 3.2.3. Hệ thống mã hóa các hành vi của khuôn mặt ................................ 66 3.2.4. Chương trình nắn chỉnh răng ......................................................... 67 2 BẢNG CÁC TỪ VIẾT TẮT Kí hiệu AU FACs Từ Tiếng Anh Giải thích Action Unit Đơn vị hành vi Facial Action Coding System Hệ thống mã hóa hành vi của khuôn mặt RBF Radial Basis Function Hàm cơ sở radial RBFT RBF Transformation Chuyển đổi dựa trên RBF DANH MỤC CÁC BẢNG Trang Bảng 3.1. Các đơn vị hành vi của khuôn mặt ............................................... 66 Bảng 3.2. Tập các đơn vị hành vi biểu thị một số trạng thái ........................ 66 DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Các giai đoạn chính trong xử lý ảnh ............................................. 10 Hình 1.2. Ví dụ về nắn chỉnh biến dạng ...................................................... 13 Hình 1.3. Ảnh mẫu và ảnh bị biến dạng của một hệ thống thu nhận ảnh ..... 19 Hình 1.4. Quá trình trưởng thành của cây ..................................................... 19 Hình 1.5. Quá trình biến đổi của con cóc ..................................................... 20 Hình 1.6. Biến đổi của một cái ống............................................................... 20 Hình 1.7. Các hình dạng của cùng một lớp ................................................... 21 Hình 1.8. Ba trạng thái tiến hóa của con ....................................................... 21 3 Hình 1.9. Dùng kỹ thuật nắn chỉnh để tạo ra dãy hoạt hình của quả bóng .. 22 Hình 1.10. Cross dissolve ............................................................................. 23 Hình 1.11. Cái ống bị biến đổi do thu hẹp, uốn cong, xoắn ......................... 23 Hình 1.12. Đối sánh hình .............................................................................. 24 Hình 2.1. Ảnh thu nhận , Ảnh mong muốn .................................................. 27 Hình 2.2. Cặp đoạn thẳng đơn ...................................................................... 29 Hình 2.3. Ví dụ minh hoạ ............................................................................. 29 Hình 2.4. Nhiều cặp vector ........................................................................... 31 Hình 2.5. Kết quả của thuật toán ................................................................... 31 Hình 2.6. Nội suy tam giác............................................................................ 32 Hình 2.7. Hệ toạ độ Barycentric ................................................................... 33 Hình 2.8. Phép nội suy Bilinear .................................................................... 34 Hình 2.9. Kết quả phép nội suy Bilinear ....................................................... 34 Hình 2.10. Khung lưới B-Spline của hai ảnh ................................................ 35 Hình 2.11. Xác định các điểm tương ứng cho mỗi đường quét .................... 36 Hình 2.12. Trái:Ba hàm radial với tham số cục bộ thảo luận trong bài. ....... 42 Hình 2.13. RBFT sử dụng một điểm điều khiển ........................................... 45 Hình 2.14. Chỉnh sửa đặc trưng khuôn mặt ................................................. 46 Hình 2.15. ý tưởng ánh xạ biên trong nắn chỉnh ảnh .................................... 47 Hình 2.16. Nguyên lý nắn chỉnh dùng phép erosion .................................... 49 Hình 2.17. Xác định biên sử dụng phép dilation .......................................... 50 Hình 2.18. Kết quả của phương thức peel-and-resample ............................. 52 Hình 2.19. Dùng ràng buộc liên kết để duy trì quan hệ láng giềng .............. 54 Hình 2.20. Nắn chỉnh ảnh dùng phương thức lan truyền sóng ..................... 55 Hình 3.1. Ví dụ ảnh gốc và ảnh đích mong muốn ........................................ 58 Hình 3.2. Điểm điều khiển đích thay đổi sau khi đã xác định được hàm F .. 59 Hình 3.3. Lưới trên một mặt của ảnh gốc và ảnh đích ................................. 60 Hình 3.4. Ảnh kết qủa của quá trình nắn chỉnh sách .................................... 61 4 Hình 3.5. Cơ và hướng di chuyển của xương hàm dưới ............................... 62 Hình 3.6. Các cơ xung quanh mồm và hướng cơ ......................................... 62 Hình 3.7. Các điểm điều khiển của mồm ...................................................... 63 Hình 3.8. Các vùng trên khuôn mặt .............................................................. 63 Hình 3.9. Vùng ảnh hưởng của cơ tuyến tính ............................................... 65 Hình 3.10 . Cơ tuyến tính ............................................................................. 65 Hình 3.11. Phần tử hình trụ tam giác biểu diễn cơ sinh học ........................ 66 Hình 3.12. Các đặc trưng khi sửa răng cửa hàm dưới .................................. 68 Hình 3.13. B-spline gồm các đoạn đường cong từ Q3 tới Q9 ....................... 70 Hình 3.14. Ảnh trước và sau nắn chỉnh ....................................................... 72 5 MỞ ĐẦU Trong thực tế đối tượng được thu nhận thường bị biến dạng do các thiết bị điện tử và quang học, hoặc do chính bản thân đối tượng được thu nhận. Ví dụ: ảnh chụp bề mặt trái đất từ vệ tinh bị méo do bề mặt cong của trái đất, ảnh chụp cuốn sách thường có một đầu to đầu nhỏ do cách đặt máy ảnh v.v..Nắn chỉnh biến dạng nhằm hiệu chỉnh các khuyết điểm của đối tượng là khâu tiền xử lý quan trọng trong xử lý ảnh. Trong những năm gần đây công nghệ thông tin phát triển với tốc độ chóng mặt về cả phần cứng và phần mền. Sự phát triển của công nghệ thông tin đã thúc đẩy sự phát triển của nhiều lĩnh vực xã hội khác như y học, giáo dục, giải trí, kinh tế v.v.. Sự phát triển của phần cứng cả về phương diện thu nhận, hiển thị, cùng với tốc độ xử lý đã mở ra nhiều hướng mới cho sự phát triển phần mềm, đặt biệt là Công nghệ xử lý ảnh cũng như Công nghệ thực tại ảo đã ra đời và thâm nhập mạnh mẽ vào đời sống của con người. Nắn chỉnh biến dạng cũng không nằm ngoài quy luật phát triển đó. Ban đầu nắn chỉnh biến dạng chỉ là các ứng dụng có tính chất sửa lỗi mà các hệ thống phần cứng không thể khắc phục được. Chẳng bao lâu sau nó là thành phần không thể thiếu trong nhận dạng và đối sánh, chẳng hạn nhận dạng tội phạm tự động trong ngành công an thay vì phải cầm ảnh của họ để đối chiếu với hàng trăm đối tượng đáng nghi khác có trong máy tính, hoặc xác định độ trùng khớp của một đối tượng với tập đối tượng cho trước trong khảo cổ học để nghiên cứu quá trình tiến hóa của sự vật, hiện tượng v.v.. Các nhà làm phim cũng nhờ đến nắn chỉnh biến dạng để tạo ra các thước phim miêu tả sự thay đổi của một đối tượng theo thời gian hoặc quá trình biến đổi từ đối tượng này đến đối tượng khác với chất lượng không thua kém gì các thước phim sử dụng thiết bị thu nhận. Rõ ràng bài toán nắn chỉnh biến dạng rất có ý nghĩa đối với sự phát 6 triển của xử lý ảnh nói chung và sự phát triển của xã hội nói riêng. Hiện nay, nắn chỉnh biến dạng đã xâm nhập vào một lĩnh vực hết sức mới mẻ và khó khăn vì nó có liên quan đến tính mạng con người. Đó là lĩnh vực y học. Cụ thể là ứng dụng trong các thẩm mỹ viện. Trong những năm gần đây, đời sống xã hội được nâng cao, người dân có điều kiện để quan tâm hơn đến vẻ đẹp của mình, nhất là khuôn mặt. Đứng trước nhu cầu đó, nhiều trung tâm chăm sóc sắc đẹp đã ra đời. Người ta có thể chỉnh sửa mí mắt, nâng mũi, sửa hàm răng, thay đổi kiểu tóc v.v.. Nhưng không phải ai sửa cũng đẹp lên, trong trường hợp này tôi muốn đề cập đến “độ phù hợp” của các đối tượng trên khuôn mặt. Phải có sự hài hòa thì mới tạo ra vẻ đẹp. Tuy nhiên khuôn mặt ta hợp với kiểu tóc nào, đôi hoa tai nào, hàm răng nào v.v.. hiện nay mới chỉ dựa vào con mắt thẩm mỹ của các nhà thiết kế. Các bộ phận trên cơ thể con người không giống như bộ quần áo cứ thử nếu không hợp thì thay bộ khác được và đã có không ít trường hợp sau khi chỉnh sửa khuôn mặt đã không đạt được mong muốn. Từ thực tế này xử lý ảnh đã vào cuộc với mong muốn có thể cho người bệnh xem trước kết quả dự đóan hình ảnh của họ sau khi điều trị. Dựa vào đó người bệnh cũng như bác sỹ có cơ sở vững chắc hơn để quyết định nên thay đổi cái gì và thay đổi như thế nào cho phù hợp. Một trong những kỹ thuật trọng yếu được sử dụng ở đây chính là nắn chỉnh biến dạng. Cùng với sự phát triển của thực tại ảo, nó sẽ tiến xa hơn nữa là xây dựng các mô hình ảo cho sinh viên ngành y thực tập trước khi đủ khả năng thực hành trên người thật. Đây là nhu cầu thiết thực vì hiện tại để có người thật cho sinh viên thực hành không phải điều đơn giản. Xu hướng này mở ra cả một chân trời rộng lớn cho thực tại ảo và cũng là cho nắn chỉnh biến dạng. Như vậy bài toán nắn chỉnh biến dạng là cơ sở để xây dựng nhiều ứng dụng quan trọng và cần thiết. Nhất là trong lĩnh vực y tế, một hướng đi khó nhưng có nhiều triển vọng và có ý nghĩa thực tiễn cao. 7 Trên đây đã điểm qua tầm quan trọng của bài toán nắn chỉnh biến dạng, đặt biệt là hiệu chỉnh khuôn mặt trong y tế. Nhận thức được điều này, tôi đã chọn đề tài luận văn: ”Nghiên cứu một số kỹ thuật nắn chỉnh và ứng dụng”. Bố cục của luận văn bao gồm phần mở đầu, phần kết luận và ba chương nội dung được tổ chức như sau: Chương 1: Tổng quan về xử lý ảnh và nắn chỉnh biến dạng Chương này trình bầy một số khái niệm trong xử lý ảnh, các vấn đề cơ bản của xử lý ảnh. Đồng thời cũng trình bầy khái niệm, cách phân loại và các ứng dụng cơ bản của nắn chỉnh biến dạng. Chương 2: Một số kỹ thuật nắn chỉnh biến dạng Các kỹ thuật được trình bày dựa vào đặc trưng được xác định để phục vụ cho nắn chỉnh. Đặc trưng đó có thể là điểm điều khiển, phân vùng ảnh, vector, biên của đối tượng v.v.. Chương 3: Ứng dụng nắn chỉnh biến dạng Trong luận văn này trình bầy ứng dụng nắn chỉnh sách dựa trên các điểm đặc trưng và nắn chỉnh răng dựa trên phân vùng ảnh. Kèm theo là một số kết quả cài đặt của hai ứng dụng này. 8 Chương 1TỔNG QUAN VỀ XỬ LÝ ẢNH VÀ NẮN CHỈNH BIẾN DẠNG 1.1. Xử lý ảnh và vấn đề cơ bản trong xử lý ảnh [11] 1.1.1. Xử lý ảnh là gì Xử lý ảnh là một lĩnh vực đang được quan tâm và đã trở thành một môn học chuyên ngành của các sinh viên hệ kỹ sư, hệ cử nhân ngành công nghệ thông tin. Xử lý ảnh có liên quan đến nhiều ngành khác nhau như: hệ thống tin học, lý thuyết thông tin, lý thuyết thống kê, trí tụê nhân tạo, nhận dạng v.v.. Trong những năm qua, xử lý ảnh đã đạt được nhiều thành tựu đáng khích lệ. Xử lý ảnh là khoa học thao tác trên hình ảnh. Nó bao trùm một phạm vi rộng lớn của các kỹ thuật hiện đang được ứng dụng rất nhiều. Ví dụ như các kỹ thuật làm nổi bật hình ảnh, tăng độ sáng của một số đường nét vùng ảnh, tạo một ảnh mới từ các vị trí của các ảnh khác, phục hồi ảnh, nắn chỉnh biến dạng v.v.. Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh XỬ LÝ ẢNH Ảnh “tốt hơn” Kết luận Ảnh có thể xem là tập hợp các điểm ảnh. Trong đó, mỗi điểm ảnh được 9 xem như là đặc trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí điểm ảnh của đối tượng trong không gian và do đó nó có thể xem như một hàm n biến P(c1, c2, ..., cn). Sơ đồ tổng quát của một hệ thống xử lý ảnh: Hệ quyết định Thu nhận ảnh (Scanner, Camera,Sensor) Tiền xử lý Trích chọn đặc điểm Hậu xử lý Đối sánh rút ra kết luận Lưu trữ Hình 1.1. Các giai đoạn chính trong xử lý ảnh 1.1.2. Một số khái niệm trong xử lý ảnh Như đã đề cập trong phần trước, chúng ta đã thấy được một cách khái quát các vấn đề chính trong xử lý ảnh. Để hiểu chi tiết hơn, trước tiên ta xem xét hai khái niệm (thuật ngữ) thường dùng trong xử lý ảnh, đó là Pixel (phần tử ảnh) và Grey level (mức xám), tiếp theo là tóm tắt các vấn đề chính.  Pixel (Picture Element): phần tử ảnh Ảnh trong thực tế là một ảnh liên tục về không gian và về giá tri độ sáng. Để có thể xử lý ảnh bằng máy tính cần thiết phải tiến hành số hóa ảnh. Trong quá trình số hóa, người ta biến đổi tín hiệu liên tục sang tín hiệu rời rạc thông qua quá trình lấy mẫu (rời rạc hóa về không gian) và lượng hóa thành phần giá trị mà về nguyên tắc bằng mắt thường không phân biệt được hai điểm kề nhau. Trong quá trình này, người ta sử dụng khái niệm Picture element mà ta quen gọi hay viết là Pixel – phần tử ảnh. Như vậy mỗi ảnh là một tập hợp các pixel. Mỗi pixel gồm một cặp tọa độ (x, y) và giá trị màu. Cặp tọa độ (x, y) tạo nên độ phân giải (resolution). Như màn hình máy 10 tính có nhiều loại với độ phân giải khác nhau: màn hình CGA có độ phân giải là 320 x 320; màn hình VGA là 640 x 350, v.v.. Như vậy, một ảnh là một tập hợp các điểm ảnh. Khi được số hóa, nó thường được biểu diễn bởi bảng hai chiều I(n, p): n dòng và p cột. Ta nói ảnh gồm n x p pixels. Người ta thường ký hiệu I(x, y) để chỉ một pixel.  Gray level: Mức xám Mức xám là kết quả sự mã hóa tương ứng một cường độ sáng của mỗi điểm ảnh với một giá trị số - kết quả của quá trình lượng hóa. Cách mã hóa kinh điển thường dùng 16, 32 hay 64 mức. Mã hóa 256 mức là phổ dụng nhất do lý do kỹ thuật. Vì 2^8 = 256 (0, 1, …, 255), nên với 256 mức, mỗi pixel sẽ được mã hóa bởi 8 bit. 1.1.3. Các vấn đề cơ bản trong xử lý ảnh a) Biểu diễn ảnh Trong biểu diễn ảnh, người ta thường dùng các phần tử đặc trưng của ảnh là pixel. Nhìn chung có thể xem một hàm hai biến chứa các thông tin như biểu diễn của một ảnh. Mỗi ảnh được biểu diễn dưới dạng ma trận điểm ảnh. Các mô hình biểu diễn ảnh cho ta một mô tả logic hay định lượng các tính chất của hàm này. Trong biểu diễn ảnh cần chú ý đến tính trung thực của ảnh hoặc các tiêu chí “thông minh” để đo chất lượng ảnh hoặc tính hiệu quả của các kỹ thuật xử lý. Việc xử lý ảnh số yêu cầu các ảnh phải được mẫu hoá và lượng tử hoá. Việc lượng tử hoá ảnh là chuyển đổi tín hiệu tương tự sang tín hiệu số của một ảnh đã lấy mẫu sang một số hữu hạn mức xám. Một số mô hình thường được dùng trong biểu diễn ảnh: mô hình toán, mô hình thống kê. Trong mô hình toán, ảnh hai chiều được biểu diễn nhờ các hàm hai biến trực giao gọi là các hàm cơ sở. Với mô hình thống kê, một ảnh 11 được coi như một phần tử của một tập hợp đặc trưng bởi các đại lượng như: kỳ vọng toán học, hiệp biến, phương sai, moment. b) Tiền xử lý Nắn chỉnh biến dạng: Nắn chỉnh biến dạng thực hiện việc biến đổi hình học giữa hai ảnh: ảnh nguồn và ảnh đích. Sự biến đổi hình học định nghĩa mối quan hệ giữa các điểm ảnh nguồn và điểm ảnh đích. Mối quan hệ này có thể được xác định bằng các hàm toán học được áp dụng trên toàn bộ ảnh hoặc chỉ trên một vùng ảnh nào đó. Trong nhiều trường hợp ngoài việc xác định các hàm toán học để nắn chỉnh ảnh, còn phải xác định thêm các đặc trưng sử dụng trong quá trình nắn chỉnh. Xét về mặt tác động của thuật toán nắn chỉnh thì có hai khuynh hướng: tác động toàn cục và tác động cục bộ. Để tạo ra tác động toàn cục ta áp dụng thuật toán, tiêu chí như nhau đối với mọi điểm ảnh. Còn tác động cục bộ thì việc nắn chỉnh chỉ áp dụng trên một số vùng ảnh, các vùng khác giữ nguyên. Các thuật toán nắn chỉnh toàn cục có tốc độ xử lý tương đối nhanh. Tuy nhiên chỉ áp dụng được đối với các yêu cầu đơn giản như co, giãn ảnh, bóp méo cả ảnh thành tứ giác hay một số hiệu ứng khác như mắt cá, kính núp v.v.. Thuật toán nắn chỉnh cục bộ cho kết quả ấn tượng hơn. Tuy nhiên để có thể nắn chỉnh theo từng vùng, phải xác định thêm tập các đặc trưng. Ngoài ra việc xây dựng thuật toán cũng tương đối phức tạp. Ảnh thu nhận nhờ các thiết bị điện tử và quang học thường bị biến dạng hình học. Khi đó, phương pháp hiệu chỉnh ảnh được mô tả dưới dạng phương trình biến đổi ảnh biến dạng f(x,y) thành ảnh lý tưởng f’ (x’, y’) như sau:  x'  hx ( x, y)   y'  hy ( x, y) 12 Trong đó hx, hy là các phương trình tuyến tính (biến dạng do phối cảnh) hay bậc hai (biến dạng do ống kính camera). a) Ảnh đầu vào b) Ảnh mong muốn Hình 1.2. Ví dụ về nắn chỉnh biến dạng Tăng cường ảnh, khôi phục ảnh: Tăng cường ảnh là bước quan trọng, tạo tiền đề cho xử lý ảnh. Nó 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, v.v… Khôi phục ảnh là nhằm loại bỏ các suy giảm trong ảnh. Với một hệ thống tuyến tính, ảnh của một đối tượng có thể được biểu diễn bởi: g ( x, y)        h( x, y,  ,  ) f ( ,  )d (    ( x, y)) Trong đó: - (x,y) là hàm biểu diễn nhiễu cộng. - f(,) là hàm biểu diễn đối tượng. - g(x,y) là ảnh thu nhận. - h(x,y;,) là hàm tán xạ điểm(Point Spread Function-PSF). Một vấn đề khôi phục ảnh tiêu biểu là tìm một xấp xỉ của f(,) khi PSF của nó có thể đo lường hay quan sát trước được, ảnh mờ và các tính chất xác xuất của quá trình nhiễu. 13 Biến đổi ảnh: Thuật ngữ biến đổi ảnh thường dùng để nói tới một lớp các ma trận đơn vị và các kỹ thuật dùng để biến đổi ảnh. Cũng như các tín hiệu một chiều được biểu diễn bởi một chuỗi các hàm cơ sở, ảnh cũng có thể được biểu diễn bởi một chuỗi rời rạc các ma trận cơ sở gọi là ảnh cơ sở. Có nhiều loại biến đổi được dùng như: - Biến đổi Fourier, Sin, Cosin, Hadmard v.v.. - Tích Kronecker - Biến đổi KL (Kroecker Loeve): biến đổi này có nguồn gốc từ khai triển của các quá trình ngẫu nhiên gọi là phương pháp trích chọn các thành phần chính. Do phải xử lý nhiều thông tin, các phép toán nhân và cộng trong khai triển là khá lớn. Do vậy, các biến đổi trên nhằm làm giảm thứ nguyên của ảnh để việc xử lý ảnh được hiệu quả hơn. c) Trích chọn đặc điểm Phân tích ảnh liên quan đến việc xác định các độ đo định lượng của một ảnh để đưa ra một mô tả đầy đủ về ảnh. Các kỹ thuật được mô tả ở đây nhằm mục đích xác định biên của ảnh. Có nhiều kỹ thuật khác nhau như lọc vi phân hay dò theo quy hoạch động. Người ta cũng dùng các kỹ thuật để phân vùng ảnh. Từ ảnh thu được, người ta tiến hành kỹ thuật tách hay hợp dựa theo các tiêu chuẩn đánh giá như: màu sắc, cường độ, v.v…Các phương pháp được biết đến như QuadTree, mảnh hóa biên, nhị phân hóa đường biên. Cuối cùng phải kể đến các kỹ thuật phân lớp dựa theo cấu trúc. d) Nhận dạng ảnh Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tượng mà người 14 ta muốn đặc tả nó. Quá trình nhận dạng thường đi sau quá trình trích chọn các đặc tính chủ yếu của đối tượng. Có hai kiểu mô tả đối tượng: - Mô tả tham số (nhận dạng theo tham số) - Mô tả theo cấu trúc(nhận dạng theo cấu trúc) Trên thực tế, người ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tượng khác nhau như: nhận dạng ảnh vân tay, nhận dạng chữ(chữ cái, chữ số, chữ có dấu). Nhận dạng chữ in hoặc đánh máy phục vụ cho việc tự động hóa quá trình đọc tài liệu, tăng nhanh tốc độ và thu nhận thông tin từ máy tính. Nhận dạng chữ viết tay (với mức độ ràng buộc khác nhau về cách viết, kiểu chữ v.v..) phục vụ cho nhiều lĩnh vực. Ngoài hai kỹ thuật nhận dạng trên, hiện nay một kỹ thuật nhận dạng mới dựa vào mạng nơron đang được áp dụng và cho kết quả khả quan. 1.2. Nắn chỉnh biến dạng và ứng dụng [3, 4] 1.2.1. Phân loại nắn chỉnh biến dạng Có rất nhiều tiêu chí để phân lớp các thuật toán nắn chỉnh biến dạng. Xét trên phương diện cấu trúc ảnh, người ta chia nắn chỉnh thành hai loại là nắn chỉnh ảnh 2D và 3D. Nắn chỉnh ảnh 2D đã đạt được những mục tiêu quan trọng trong việc tìm ra các giải pháp để chuyển đổi không gian cũng như trong việc quản lý các đặc trưng. Trong khi đó nắn chỉnh 3D vẫn còn rất xa so với những thành công của 2D. Nói chung, các kỹ thuật nắn chỉnh 2D đòi hỏi nhiều công đoạn xử lý thủ công. Hầu hết các phương thức 3D đã được đề xuất chỉ giới hạn đối với một số mô hình đối tượng mà đã biết trước cách biểu diễn của mô hình đó vì độ phức tạp của thuật toán phụ thuộc vào một số yếu tố như: cách biểu diễn đối tượng, độ lồi, chủng loại. Nếu phân chia theo luồng dữ liệu biến đổi thì có thể phân lớp nắn chỉnh 15 thành 2 lớp: các phương pháp tính xuôi và các phương pháp tính ngược. Trong các phương pháp tính xuôi, các điểm ảnh trên ảnh nguồn được xử lý theo từng dòng quét và các kết quả được thiết lập trên ảnh đích. Trong khi đó các phương pháp tính ngược ánh xạ ngược các điểm ảnh đích tới các điểm ảnh nguồn. Đối với các ảnh số thì việc thực thi theo các phương pháp tính xuôi thường không cho kết quả tốt. Do vậy, hầu hết các thuật toán hiện nay đều là các phương pháp tính ngược. Nếu xét đến công cụ dùng để xác định đặc trưng cho đối tượng khi thực hiện nắn chỉnh, ta phân nắn chỉnh thành 3 loại cơ bản: các kỹ thuật nắn chỉnh dựa trên phân vùng ảnh, các kỹ thuật nắn chỉnh dựa trên các điểm đặc trưng và các kỹ thuật dựa trên vector. Với các kỹ thuật dựa trên việc phân vùng ảnh, trước tiên miền không gian của ảnh nguồn được chia thành một tập các vùng nhỏ. Tương tự như vậy, ảnh đích cũng được chia thành tập các vùng nhỏ tương ứng. Sau đó ảnh được nắn chỉnh bằng cách chuyển đổi tương ứng mỗi vùng của ảnh nguồn thành mảnh của ảnh đích. Một trong những phương thức đầu tiên của kỹ thuật dựa trên phân mảnh là thuật toán nắn chỉnh 2-pass mesh. Với phương thức này, mỗi chuyển đổi 2-pass sẽ thay thế một chuyển đổi 2-D thành một dãy các chuyển đổi 1-D trực giao. Ngoài ra còn có các phương thức nắn chỉnh dựa trên phân vùng khác như phân vùng dựa trên phân hình tam giác v.v.. Với nắn chỉnh dựa trên các điểm đặc trưng, người ta dùng các điểm quan trọng làm ánh xạ cơ sở, tức là đã xác định được trước ánh xạ của các điểm đặc trưng. Từ các cặp điểm đặc trưng tương ứng ở trên ảnh nguồn và ảnh đích ta xác định được ánh xạ của các điểm còn lại xuất phát từ vị trí của nó trên ảnh gốc. Một số phương thức dựa trên điểm đặc trưng coi nắn chỉnh như là một hàm nội suy dữ liệu thưa. Sử dụng hàm nội suy để nội suy tất cả các điểm còn lại. Đại diện tiêu biểu là kỹ thuật dựa trên hàm cơ sở radial sẽ 16 được giới thiệu trong chương 2 của luận văn này, nó được ứng dụng trong việc tổng hợp khuôn mặt đơn giản. Hàm cơ sở radial là hàm hiệu quả trong nội suy dữ liệu thưa mà không cần hướng ưu tiên. Cách tiếp cận tương tự là thay vì dùng hàm cơ sở radial người ta dùng các hàm thin-plate splines như là cơ sở của hàm nội suy. Kỹ thuật nắn chỉnh dựa trên vector sử dụng các cặp vector làm cơ sở để biến đổi ảnh. Beier và Neely là những người đầu tiên đề xuất kỹ thuật này . Mỗi cặp vector định nghĩa một ánh xạ tọa độ giữa chúng. Độ dịch chuyển của bất kỳ điểm nào trong ảnh sẽ bằng tổng trọng số của các ánh xạ do tất cả các cặp vector đã được xác định. 1.2.2. Xác định cơ sở để nắn chỉnh Để thực hiện nắn chỉnh, trước hết phải xác định các đặc trưng tương ứng giữa ảnh nguồn và ảnh đích. Đặc trưng có thể là vector, điểm điều khiển, hoặc phân ảnh thành các mảnh khác nhau v.v.. Đây là bước đầu tiên và cũng là bước rất quan trọng trong nắn chỉnh biến dạng vì hiệu quả của quá trình nắn chỉnh phụ thuộc rất nhiều vào việc xác định sự tương ứng giữa hai ảnh. Việc xác định các đặc trưng của ảnh nhằm cung cấp các thông tin về đối tượng giúp cho sự việc nắn chỉnh được thực hiện thuận lợi. Các công thức nắn chỉnh bao giờ cũng được đưa ra dựa trên các đặc trưng và xây dựng các công thức nắn chỉnh là đại diện cho một thuật toán nắn chỉnh biến dạng. Để đạt được chất lượng nắn chỉnh hình tốt, chúng ta phải nội suy từng phần của ảnh gốc sang các phần tương ứng bên ảnh đích. Điều này có nghĩa là ta đã biểu diễn được thông tin của đối tượng và ánh xạ từng phần của chúng cho nhau. Đây cũng chính là mục đích của giai đoạn xác định các đặc trưng. Nói chung, việc xác định các đặc trưng của đối tượng vẫn là công việc thủ công chủ yếu là do người sử dụng nhập vào hoàn toàn hoặc là với sự trợ giúp một phần của máy tính. Người ta cũng đã đưa ra được thuật toán biến 17 đổi tự động xác định các đặc trưng của ảnh. Tuy nhiên, nó chỉ xác định được trong trường hợp các ảnh đầu vào tương đối giống nhau và đối tượng ảnh tương đối đơn giản hơn nữa tốc độ của nó lại rất chậm. 1.2.3. Một số ứng dụng của nắn chỉnh biến dạng a) Y t ế Trong thực tế có rất nhiều tình huống trong đó người ta mong muốn làm sao có thể xem trước được hình ảnh kết quả để đưa ra quyết định hoặc để thực hiện các thí nghiệm ảo. Ví dụ dự đoán hình ảnh một người nào đó tại một thời điểm trong tương lai để xác định tội phạm, dự đoán kết quả khi chỉnh sửa một bộ phận trên cơ thể tại các thẩm mỹ viện để quyết định có nên chỉnh sửa hay không, hoặc dự đoán hình ảnh để tạo các thí nghiệm ảo trong y tế giúp các sinh viên ngành y tiếp cận thực hành trước khi thực hiện trên người thật v.v.. Rõ ràng phỏng đoán trước hình ảnh kết quả là là nhu cầu không thể thiếu trong giai đoạn công nghệ thông tin phát triển như hiện nay nhất là trong lĩnh vực y tế nhằm hạn chế đến mức thấp nhất những rủi ro trong quá trình điều trị. Xử lý ảnh với các kỹ thuật nắn chỉnh biến dạng sẽ phần nào giúp hạn chế điều đó. Tuy nhiên, đây cũng là huớng đi còn mới mẻ đối với xử lý ảnh và cũng là vấn đề khó vì muốn thực hiện được các chương trình áp dụng trong y tế đòi hỏi phải có sự hiểu biết về cấu tạo sinh học của con nguời. Vì thế sẽ cần một thời gian chuẩn bị trước khi có thể đi đến thử nghiệm thực tế. b) Chỉnh sửa hình học Ảnh thường bị biến dạng do các thiết bị thu nhận ảnh như camera, scanner v.v.. Để chỉnh sửa hình dạng hình học bị biến dạng từ quá trình thu nhận ảnh, có thể sử dụng các kỹ thuật nắn chỉnh biến dạng. Trước tiên phải có một ảnh mẫu (hình 1.3a) và một ảnh đã được thu nhận có các mẫu bị biến dạng (hình 1.3b). Sau đó áp dụng hàm biến đổi T cho ảnh bị biến dạng để thu 18 được ảnh tương tự ảnh mẫu ban đầu. Biến đổi T có thể áp dụng cho bất cứ ảnh nào muốn chỉnh sửa hình dạng. Hình 1.3. Ảnh mẫu và ảnh bị biến dạng của một hệ thống thu nhận ảnh dạng cơ sở c) Mô phỏng thay đổi hình dạng trong tự nhiên Hình dạng của đối tượng trong thế giới tự nhiên luôn trải qua quá trình biến đổi không ngừng. Đó là do sự kế thừa các đặc tính của tự nhiên: mọi sự vật được sinh ra, lớn lên rồi chết đi. Cơ thể của chúng thay đổi hình dạng là kết quả của các cơ chế sinh học phức tạp. Quá trình lớn lên tạo ra các tác động bên trong, các tác động này làm cho cơ thể phát triển. Kết quả là hình dạng của chúng bị thay đổi. Nhìn chung quá trình biến đổi do cơ chế này rất phức tạp. Các hình dạng đơn giản tiến hoá dần thành các cấu hình phức tạp hơn. Chúng phát triển bắt đầu từ một cá thể chỉ là một đốm nhỏ, dần dần thành cá thể hoàn thiện có các bộ phận phân biệt và các đặc trưng rõ rệt. Ví dụ cụ thể là một cái cây: từ một hạt mầm lớn lên thành một cây hoàn thiện có thân, lá v.v..Hình 1.4 minh hoạ một số trạng thái trong quá trình phát triển của cây. Hình 1.4. Quá trình trưởng thành của cây 19