Biến hình xử lý ảnh

Trường Đại Học Khoa Học Tự Nhiên Khoa Toán -Tin học BIẾN HÌNH XỬ LÝ ẢNH Nhóm: Tiger NGUỸÊN NGỌC HIẾU: 0611041 NGUỸÊN MINH HIỀN: 0611037 HOÀNG VĂN TRƯỞNG: 0711242 GVHD: Phạm Thế Bảo I-GIỚI THIỆU: -Đề tài biến người thành Hổ :là đề tài dạng Morphing-Biến hình thái ảnh này thành ảnh kia. Morphing-là sự biến đổi hình thái của ảnh.Nó được ứng dụng trong sản xuất phim hoạt hình nói riêng và sản xuất phim nói chung. Khi sự biến hình diễn ra,ảnh ban đầu dần dần biến đổi và mờ dần,trong khi ảnh lúc sau đã bắt đầu biến đổi dần sang ảnh ban đầu rõ ràng hơn.Vì thế, những ảnh đầu tiên trong chuỗi ảnh gần giống với ảnh ban đầu,hình ảnh giữa của chuỗi ảnh là ảnh trung bình của ảnh ban đầu biến đổi một nửa sang ảnh lúc sau và ảnh lúc sau biến đổi một nửa sang ảnh ban đầu.Những ảnh cuối cùng của chuỗi ảnh gần giống với ảnh lúc sau.Ảnh giữa gữ vị trí then chốt;nếu ảnh giữa đạt yêu cầu thì cả chuỗi biến đổi ảnh đạt yêu cầu.Đối với việc biến đổi hai khuôn mặt,ảnh giữa thường trông rất khác biệt,như là người thật,nhưng đều không phải là người trong ảnh ban đầu hay trong ảnh lúc sau. +)Tóm lại Morphing=warp the shape + cross-dissolve color. Trong đó: Warp the shape la: Sự sắp xếp lại những điểm ảnh trong một bức ảnh, còn được gọi là làm méo ảnh (image distortion), biến đổi hình học ảnh (geometric image transformation). Được sử dụng trong xử lý ảnh và đồ họa máy tính. Có 2 cách làm biến dạng một ảnh. Cách thứ nhất, được gọi là ánh xạ xuôi, quét từng điểm ảnh của ảnh ban đầu, và sao chép chúng qua các vị trí tương ứng của ảnh lúc sau. Cách thứ hai, là ánh xạ ngược, thông qua điểm ảnh của ảnh lúc sau, lấy mẫu chúng sang các điểm ảnh đúng của ảnh ban đầu. Điều quan trọng nhất của ánh xạ ngược là mỗi điểm ảnh của ảnh lúc sau phải được chiếu lên vị trí tương ứng. Trong trường hợp ánh xạ xuôi, vài điểm ảnh của ảnh lúc sau có thể không được tô, và sẽ được nội suy. Ta tính toán sự biến dạng của ảnh theo ánh xạ ngược. Vấn đề có thể đặt ra là “tọa độ điểm ảnh nào của ảnh ban đầu mà ta lấy mẫu với mỗi điểm ảnh của ảnh lúc sau”. Cross-dissolve color. Là phân rã chéo. Để phân rã chéo ta dùng nội suy toàn ảnh Imagehalfway = t*Image1 + (1-t)*image2 với t [0,1] Yêu cầu : dùng các thuật toán xây dựng code biến 1 người thành 1 con Hổ.liên tục dưới dựng video. Ý tưởng cơ bản : 1)-phương pháp chia tam giác. Đưa vào tương quan tại các điểm có đặc trưng được chọn là chính. Định 1 lưới tam giác qua các điểm . +Trên cả 2 hinh. +Lúc này có tương quan theo tam giác-tam giác. 3.Biến dạng từng tam giác tách biệt từ nguồn sang đích. +Biến dạng affine-3 điểm +giống như biến dạnh kết cấu. Chia tam giác. +Bình thường độ phức tạp mũ. O(n3) Triangulation Algorithm. +Delaunay Triangulation by Duality- độ phức tạp chỉ còn :O(nlogn) 2)phương pháp xác định đường đặc trưng. -Chọn các dòng đặc trưng trên khuôn mặt trên 2 ảnh nguồn và đích, những dòng đặc trưng này tạo nên “reverse mapping” nghĩa là quét từng điểm ảnh trên ảnh đích rồi chọn mẫu những điểm ảnh chính xac tương ứng trên ảnh nguồn. Vấn đề đặt ra là : “tọa độ pixel nào trên ảnh nguồn sẽ được lấy mẫu tương ứng với mỗi pixel trên ảnh đích? ” Thực hiện: ở đây chúng tôi chon phương pháp 2. sử dụng thuật toán Feature – Based Image Metamorphosis can Shawn Neely van Thaddeus Beyer. II-THUẬT TOÁN. Các bước giải quyết bài toán: 0- Xác định các vector đặc trưng. 1-Biến đổi 1 cặp vector. 2- Biến đổi nhiều cặp vector 3-Morphing 2 hình. 4-Runtime 5-Một số ảnh trung gian 6-ưu nhược điểm của Morphing. 0-xác định vector đặc trưng. 1-Trường hợp 1 cặp vector Cơ sở toán học của Phương pháp Beier và Neely Cho véctơ a, b bất kỳ ta có: Ở đây là phép nhân tích vô hướng. Từ vị trí tương đối của a, b mà ta sẽ có các trường hợp riêng của Cho véctơ và một điểm X bất kì. Ta đặt u là đại lượng đại số sau: Khi đó u được gọi là đại lượng tỉ lệ theo véctơ . Gọi v là khoảng cách giữa điểm X và véctơ khi đó ta tính v như sau: Gọi là véctơ vuông góc với véctơ , khi đó tỉ số là véctơ đơn vị của véctơ vông góc với . Nhận xét rằng: , Với , ta có chính là độ dài hình chiếu của véctơ lên véctơ . Từ nhận xét trên ta tính như sau: Trong trường hợp này, là độ dài hình chiếu của véctơ lên véctơ vuông góc với véctơ hay bằng khoảng cách của điểm X tới véctơ . Cho trước một véctơ , xây dựng một ánh xạ từ điểm X sẽ có ảnh là điểm X’ dựa trên các hệ số và của điểm X. X’ sẽ được tính như sau: Thuật toán biến đổi mỗi tọa độ điểm ảnh bằng phép xoay,tịnh tiến,hoặc định tỉ lệ,theo đó sẽ biến đổi toàn bộ bức ảnh.Tất cả điểm ảnh dọc theo vectơ ảnh gốc được copy sang đầu vectơ ảnh đích.Vì tọa độ u chuẩn hóa theo chiều dài của vectơ, và tọa độ v thì không(nó luôn là khoảng cách của điểm ảnh),những hình ảnh được định tỉ lệ theo hướng của vectơ dựa vào tỉ lệ chiều dài của các vectơ.Tỉ số chỉ được định tỉ lệ theo hướng của vectơ.Ta thử định tỉ lệ tọa độ v theo hướng của vectơ,ta thấy tỉ lệ này luôn đồng nhất,nhưng nhận thấy rằng công thức đã cho là hữu ích hơn. Hình 2:ví dụ 1 cặp vectơ. Hình phía trên bên trái là ảnh gốc.Vectơ được xoay thành hình phía trên bên phải,được tịnh tiến thì hình phía dưới bên trái,và được lấy tỉ lệ thành hình phía dưới bên phải. Ta không thể nào hoàn tất phép xoay nếu 2 vectơ cùng chiều dài.Cặp vectơ có cùng chiều dài và cùng hướng nhưng vị trí xác định tịnh tiến khác nhau.Tất cả sự biến đổi dựa trên cặp vectơ này là afin,nhưng không phải tất cả biến đổi đều afin..trong trường hợp này,các tỉ lệ đồng nhất và các sự dịch chuyển là không xác định 2-trường hợp có nhiều véctơ: Trường hợp có nhiều véctơ: Đặt là độ lệch của các và tức là: Với lần lượt là các ảnh của đối với từng véctơ tương ứng . Đặt là trọng số của với véctơ tương ướng , tính theo công thức sau: Trong đó, là độ dài của véctơ tương ứng. a, b, p là các hằng số. là khoảng cách của tới tương ứng. Ý nghĩa của a, b, p: điều khiển tác động quan hệ của các đường thẳng. Nếu a là bằng không, thì nếu khoảng cách từ véctơ đến điểm X là bằng 0, cường đội là gần như không xác định. với giá trị này của a, ta biết rằng những điểm X nằm trên véctơ sẽ đi đến chính xác nơi mà ta muốn chúng đến. Với những giá trị a lớn sẽ thu được phép biến đổi mượt hơn. Giá trị b xác định cường độ của các véctơ khác nhau quan hệ như thế nào về khoảng cách. Nếu b có giá trị lớn thì điểm X chỉ chịu tác động của các véctơ nằm gần nó nhất. Giái trị của b được sử dụng hiểu quả nhất là . Giái trị thông thường của . Nếu p = 0 thì tất của các véctơ sẽ có cùng trọng số quan hệ. Nếu P = 1 thì véctơ có chiều dài dài hơn sẽ có trọng số lớn hơn véctơ có chiều dài ngắn hơn. X’ sẽ được tính như sau: Thuật toán Beier & Neely: For X DSUM = (0,0) weightsum = 0 For PiQi Tính u, v dựa trên PiQi Tính X’i dựa trên u, v và P’iQ’i Tính độ dịch chuyển Di = X’i – Xi cho véctơ hiện tại Dist = khoảng cách ngắn nhất từ X đến PiQi weight = (lengthp/(a + dist))b DSUM += Di * weight weightsum += weight X’ = X + DSUM/weight ảnh đích(X) = ảnh gốc (X’) Ở hình trên,X’ là vị trí mẫu thử của điểm ảnh ở vị trí X’.Vị trí đó là trọng số trung bình của 2 điểm ảnh ờ X1’ và X2’,được tính theo cặp vectơ thứ nhất và thứ hai. Nếu đặt giá trị a là 0,thì sẽ có 1 kết quả không xác định nếu 2 vectơ giao nhau.Mỗi vectơ sẽ có 1 trọng số xác định tại giao điểm.Khuôn mẫu hoạt hình khi làm việc với các chương trình là các mô hình mà mỗi vectơ có 1 trường tác động xung quanh,và buộc các điểm ảnh gần nó nằm trong các vị trí tương ứng có quan hệ với các vectơ chuyển động.Các điểm ảnh càng gần các vectơ thì chúng sẽ chuyển động theo vectơ đó bấp chấp sự chuyển động của các vectơ khác.mô hình này cung cấp cho người làm phim trực giác tốt về những gì diễn ra khi người đó thiết lập 1 sự biến hình. Với 2 hay nhiều vectơ,việc biến hình là không đơn giản.Hình bên trái là ảnh gốc,nó bị biến đổi bằng cách quay vectơ trên F quanh điểm đầu của nó.Cả hình bị biến đổi bởi phép biến hình này.Ta không thể nào lấy tỉ lệ đều hay thực hiện dịch chuyển với nhiều vectơ.Hầu hết các cặp vectơ cho kết quả biến hình afin.Tuy nhiên điều này vẫn thực hiện được khi thêm vào hay di chuyển các vectơ.Các điểm ảnh nằm gần vectơ nào dịch chuyển theo vectơ đó,những điểm ảnh cách đều 2 vectơ chịu tác động của cả 2 vectơ. 3-Morphing giữa 2 ảnh: Một phương pháp pha trộn 2 ảnh I0 và I1.Để làm điều này ta phải định nghĩa các vectơ tương ứng của 2 ảnh.Mỗi khung trung gian I của sự biến hình đều được định nghĩa bằng lập 1 tập hợp các đoạn vectơ bằng cách nội suy các vectơ tự vị trí của chúng ở I0 sang I1 .Cả 2 ảnh I0 và I1 đều bị bẻ cong về phía các vectơ trong I.Có 2 kết quả qua sự biến đổi này, lúc đầu ảnh hoàn toàn là I0 (không bị bẻ cong do ta vẫn chưa nội suy các vectơ theo I0),và lúc cuối ảnh hoàn toàn là I1.Có thể có trường hợp trong vài khung trung gian ,2 vectơ có thể giao nhau mặc dù chúng không giao nhau trong ảnh gốc. Ta thường có 2 cách để nội suy các vectơ.Đầu tiên là chỉ cần nội suy điểm cuối của mỗi vectơ.Cách 2 là nội suy vị trí trung tâm và hướng của vectơ,và nội suy chiều dài của vectơ.Trong trường hợp đầu tiên 1 vectơ quay sẽ co về giữa sự biến hình. Ngược lại, trường hợp còn lại không đơn giản cho người dùng bởi cách nội suy.Trong bất kì trường hợp nào,hãy để người dùng thấy được vị trí nội suy giúp lập nên tập hợp các vị trí đầu và cuối một cách hợp lý. 4- Running Time(Trong thuat toan) Running Time can thuật toán này phụ thuộc vào kích thước ảnh và số đường được chọn. Chúng ta phải đoán trước được ảnh sẽ biến đổi như thế nào, running time can 2 ảnh 170x185 với 10 dòng chọn diễn ra như sau: Thời gian Morph 2 ảnh : Elapsed time is 0.406000 seconds. Elapsed time is 0.360000 seconds. Ví dụ khác: Running time cho ảnh kích thước 254x248 cho 5 dòng chọn : First Image Morph: 1.6820 seconds Copying Pixels for first image: 0.4410 seconds Second Image Morph: 1.6620 seconds Copying Pixels for second image: 0.4010 seconds Results 5-Một số ảnh trung gian 6-Ưu điểm và khuyết điểm của morphing: Morphing có 1 ưu điểm lớn vượt trội phương pháp warping: đó là warping hao phí hơn. Các vị trí trong thuật toán là do người dùng tạo ra.Ví dụ khi biến đổi 2 khuôn mặt,người dùng có thể vẽ đoạn vectơ xuống dọc mũi,ngang qua mắt,dọc theo lông mày,xuống các đường biên của má,dọc theo đường tóc.Mọi thứ di chuyển đều theo ý muốn của người dùng,và các thứ khác phối hợp dực trên các vị trì này.Thêm vào các đoạn vectơ mới để làm tăng thêm tính điều khiển của trong khu vực đó mà không tác động lên các nơi khác. Những công cụ này dực trên cơ sở tiến đến độ tương phản với phương pháp warping.Trong bản đơn giản nhất của thuất toán đó,người dùng phải xác định có bao nhiêu điểm điều chỉnh để điều chỉnh bức ảnh.Người sùng lấy điểm này và di chuyển đến vị trí chính xác.những điểm còn lại không xác định bởi lỗi sai hay những điểm mà người dùng không thể tìm được nét đặc trưng vẫn có thể được dùng bởi thuật toán warping.Thường thì anh ta không đủ quyền điều khiển ở vài nơi hay quá nhiều ở nơi khác.Mỗi điểm gây ra lượng tác động như nhau lên các điểm khác.Các đường đặc trưng thường là đường chéo,ngược lại các đỉng bắt đầu thẳng đứng và giàn ngang,và rất khó để quyết định đỉnh nào đặt dọc theo dường chéo. Ta nhận thấy khi thử đặt 1 tá các điểm đan nhau nhau như là đẩy 1 sợi dây;nó như bị ép đến nơi mà ta không muốn nó đi..Với phương pháp điều khiển đoạn vectơ là tự nhiên.Dịch chuyển 1 vectơ vòng quanh có tác dụng có thể đoán được.Phần mở rộng của phương pháp warping cho phép ta làm mịn các lưới làm phương pháp pháp có ý nghĩa và hữu ích hơn. Một vấn đề khác với phương pháp này là thuật toán 2 vòng bị trục trặc do độ cong xoay vòng lớn(hiện tượng thắt cổ chai).Các ảnh trung gian có thể bị bẻ cong trong phạm vi thông tin bị mất.Ta có thể thực hiện thuật toán 1 vòng để tránh hiện tượng này. 2 khuyết điểm lớn nhất của phương pháp dựa trên vectơ đặc trưng là tốc độ và khả năng điều chỉnh.Vì nó mang tính tổng thể ,nên tất cả đoạn vectơ cần được tham chiếu cho mỗi điểm ảnh.Sự tương phản với việc nối lưới,có thể được điều khiển trong 1 vùng(thì xét 16 điểm nối nhau gần điểm ảnh nhất). Giữa các vectơ đôi lúc phát sinh nội suy không cần thiết.Vấn đề này thường được nó biểu hiện như 1 “bóng ma”của 1 phần hình ảnh được thể hiện trong vài phần không liên quan của ảnh nội suy,nguyên nhân là do sự kết hợp bất ngờ của các đoạn vectơ riêng biệt.Một 1 công cụ gỡ rối có thể hữu ích trong trường hợp này,trong đó người dùng có thể chỉ ra các điểm ảnh trong ảnh nội suy và ảnh gốc được biểu diễn,chỉ ra nơi xuất phát của điểm ảnh.Dùng thông tin này người dùng có thể di chuyển 1 vectơ hay thêm 1 vectơ mới để sửa chữa vấn đề. Ảnh phía trên bên trái là gốc,di chuyển theo vectơ ngang phía dưới tạo 1 bóng ma trên vectơ,nó được tạo từ những điểm ảnh được copy từ phần trên của F,ảnh phía dưới bên trái là hình được sửa,co dọc vectơ ghép với vectơ nằm ngang.Nếu vectơ dọc cân bằng chiều dài của nó vì lí do khác thì bóng ma có thể mất đi do chia vectơ dọc thành 2 phần như hình dưới bên phải.