Luận văn Nắn chỉnh biến dạng hình học và ứng dụng

iểm A, phép dịch A + x được xác định bởi:  |A x x A     + Các phép toán tập hợp Minkowski: Cho A, B là các tập hợp điểm: Phép cộng Minkowski:   B A B A       Phép trừ Minkowski:   B A B A       + Phép giãn ảnh và co ảnh Từ hai phép toán Minkowski, ta có phép toán hình thái cơ bản là phép giãn ảnh và co ảnh : Phép giãn ảnh (Dilation):    , b D A B A B A        Phép co ảnh (Erosion):      , B E A B A B A         Trong đó:  |B B     Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 + Một số tính chất: Giao hoán:    , ,D A B A B B A D B A     Không giao hoán :    , ,E A B E B A Kết hợp:    A B C A B C     Dịch chuyển bất biến:    A B x A B x     + Ví dụ minh họa: (a) Giãn ảnh D(A,B) (b) Co ảnh E(A,B) Hình 1.4 Phép co và giãn ảnh A và B có thể được xem là các đối tượng ảnh và B được gọi là phần tử cấu trúc. Thông thường, phép giãn ảnh làm tăng kích thước đối tượng ảnh trong khi phép co ảnh làm giảm kích thước. Điều này tùy thuộc vào việc chọn phần tử cấu trúc. Có hai phần tử cấu trúc phổ biến thường được dùng là tập hợp kề- 4 và tập hợp kề-8 trong hệ tọa độ Đềcác: Ý nghĩa: - Phép giãn ảnh biến đổi giá trị của các điểm nền kề-4 (hoặc kề-8) với điểm ảnh thành các điểm ảnh, do vậy, nó làm tăng kích thước các điểm ảnh. - Phép co ảnh biến đổi giá trị của các điểm ảnh kề-4 (hoặc kề-8) với điểm nền thành các điểm nền, do vậy, nó làm giảm kích thước các điểm ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 Ví dụ: (a) B = N4 (b) B= N8 Hình 1.5 Minh họa phép co và giãn ảnh Các điểm ảnh gốc là các điểm màu xám, các điểm thêm vào là các điểm có màu đen. * Phép mở và đóng ảnh Chúng ta có thể kết hợp phép giãn ảnh và co ảnh để tạo nên hai toán tử quan trọng hơn: Mở ảnh:     , , ,O A B A B D E A B B  Đóng ảnh:     , , ,C A B A B E D A B B     + Một số tính chất: - Đối ngẫu:         , , , , C C C C C A B O A B O A B C A B   - Dịch chuyển:         , , , , O A x B O A B x C A x B C A B x       Ý nghĩa: - Phép mở ảnh sẽ mở rộng những khoảng trống giữa các phần tiếp xúc trong đối tượng ảnh, làm cho ảnh bớt gai hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 - Phép đóng ảnh sẽ làm mất đi những khoảng trống nhỏ trong ảnh, làm mất đi nhiễu trong ảnh. * Một số kết quả Các toán tử cấu trúc thường được áp dụng: 8 1 1 1 1 1 1 1 1 1 B N           1 - - - - 1 - - - - B          2 - 1 - 1 - 1 - 1 - B          (a) (b) (c) a) Ảnh A b) Giãn ảnh với 2B c) Co ảnh với 2B Hình 1.6 Kết quả phép co và giãn ảnh d) Mở ảnh với 2B e) Đóng ảnh với 2B f) it-and-Miss với B1 và B2 Hình 1.7 Kết quả phép mở và đóng ảnh * Phép toán HitAndMiss Cho một ảnh A và hai phần tử cấu trúc B1 và B2, ta có: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24               1 2 1 2 1 2 1 2 , , is , , , , , C CE A B E A B HitM s A B B E A B E A B E A B E A B          với B1 và B2 là giới hạn và rời rạc nhau  1 2B B  (phép toán này còn được gọi là xác định viền mẫu, mẫu B1 cho đối tượng ảnh và mẫu B2 cho nền ảnh) + Đường viền các điểm kề 4:  8,A A E A N   + Đường viền các điểm kề 8:  4,A A E A N   Cách biểu diễn khác: Biểu diễn phần tử cấu trúc dưới dạng ma trận (gồm B1 và B2) + Cách thực hiện: dịch chuyển điểm gốc của phần tử cấu trúc lần lượt trên các điểm ảnh theo thứ tự từ trên xuống dưới, từ trái qua phải, nếu các điểm nền và điểm ảnh của phần tử cấu trúc khớp với trên ảnh thì ta giữ lại điểm ảnh đó, nếu không ta đặt thành điểm nền. 4 phần tử cấu trúc được sử dụng để tìm góc của ảnh trong phép toán HitAndMiss (thực chất là một phần tử quay theo 4 hướng khác nhau) Sau khi tìm được góc theo các phần tử cấu trúc trên, ta kết hợp chúng lại để được kết quả là các góc lồi của ảnh. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 * Xương ảnh Khái niệm: Xương ảnh là tập hợp các đường độ dày là 1, đi qua phần giữa của đối tượng ảnh và bảo toàn được tính chất hình học của đối tượng ảnh. Tuy nhiên, không dễ dàng để nhận ra xương ảnh: Ví dụ: Hình 1.9 Tìm kiếm xương ảnh Trong ví dụ (a), ta không thể tìm được đường thẳng có độ dày 1 đi qua giữa đối tượng mà phản ánh được tính chất đơn giản của đối tượng. Trong ví dụ (b), ta không thể bỏ đi một điểm trong đối tượng kề 8 mà giữ được tính chất hình học của đối tượng. Công thức cơ bản: - Các tập hợp con của xương ảnh Sk(A):      , , 0,1,...kS A E A kB E A kB B k K     với K là giá trị lớn nhất của k trước khi Sk(A) trở thành rỗng. (a) (b) Hình 1.8 Sử dụng phép toán HitAndMiss để tìm góc lồi của một ảnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 ta có:    , ,E A kB B E A kB Xương ảnh là hợp của các tập con xương ảnh: 0 ( ) ( ) K k k S A S A   Như vậy, đối tượng ảnh ban đầu có thể được tái tạo lại từ các tập con xương ảnh, phần tử cấu trúc B và giá trị K:    0 K k k A S A kB    Tuy nhiên, công thức này không phải lúc nào cũng bảo toàn được tính chất hình học của ảnh. + Phép toán làm gầy ảnh: Công thức:    1 2 1 2, , itMis , ,Thin A B B A H s A B B  Tùy thuộc vào cách chọn B1, B2 mà ta có các thuật toán làm gầy ảnh khác nhau. Một cách biểu diễn khác: Phần tử cấu trúc được dùng để tìm xương ảnh (điểm gốc ở tâm của phần tử cấu trúc). Tại mỗi bước lặp, ảnh sẽ được làm gầy bởi phần tử cấu trúc bên trái, sau đó đến phần tử cấu trúc bên phải, tiếp theo với phép quay 90o hai phần tử cấu trúc trên. Quá trình được lặp đi lặp lại cho đến khi phép toán làm gầy không dẫn đến sự thay đổi nào nữa. Hình 1.10 Ví dụ về phép toán làm gầy ảnh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Chương 2 MỘT SỐ KỸ THUẬT NẮN CHỈNH BIẾN DẠNG HÌNH HỌC Như ta đã bàn trong chương 1, công việc nắn chỉnh thường có nhiều bước, nhưng mục đích cuối cùng là nắn chỉnh bề mặt của một vật (đối tượng) sao cho sau khi nắn chỉnh đối tượng sẽ không bị cong, bị vênh hay nhăn nheo, và hình ảnh trông sẽ đẹp hơn. Ta có thể định nghĩa: Nắn chỉnh ảnh là quá trình thao tác trên một đối tượng ảnh số, sao cho khi ảnh ở bất kỳ hình dạng nào như cong, vênh, bị bóp méo,… đều có thể được điều chỉnh. Công việc của nắn chỉnh ảnh thực chất là đi thay đổi hay di chuyển các Pixel (điểm ảnh) của hình ảnh từ vị trí này sang vị trí khác . Sau quá trình nắn chỉnh chúng ta sẽ áp dụng kỹ thuật nội suy ảnh để thu được ảnh có chất lượng tốt hơn cả về mầu sắc và độ tương phản. 2.1. Nắn chỉnh trên cơ sở phân vùng ảnh Trong trường hợp các điểm đặc trưng được sắp xếp để tạo thành một lưới bao phủ lên bề mặt ảnh, khi đó ảnh gồm nhiều phần ghép lại với nhau. Để nắn chỉnh ảnh, chỉ cần nội suy các phần tương ứng của lưới. Tùy thuộc vào lưới được tạo thành là lưới gì sẽ có kỹ thuật nắn chỉnh tương ứng. Nếu là lưới tam giác ta có thuật toán biến đổi trên cơ sở phân hình tam giác, nếu là lưới tứ giác ta có thuật toán biến đổi trên cơ sở phân hình tứ giác v.v.. Khi phân tích ảnh người ta dùng phương pháp phân vùng tam giác và phân vùng tứ giác. Trong đó kỹ thuật nội suy thường sử dụng là nội suy tam giác (Affine Interpolation) và nội suy tứ giác (Trilinear Interpolation và Bilinear). a. Nội suy tam giác Để biến đổi lưới tam giác này thành lưới tam giác kia ta thực hiện nội suy từng tam giác tương ứng cho nhau. Cách đơn giản nhất là sử dụng kỹ thuật ánh xạ dựa trên hệ toạ độ Barycentric. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Ở giai đoạn xác định các điểm đặc trưng (phần sau) chúng ta tạo ra xây dựng một lưới các tam giác cho ảnh gốc và ảnh đích thoả mãn điều kiện: Trong đó: Ti là diện tích của tam giác thứ i S là diện tích của ảnh. Đồng thời 3 đỉnh của tam giác là 3 điểm đặc trưng được xác định trên đối tượng ảnh và có sự tham chiếu một - một giữa các điểm này. Dựa trên lưới các đặc trưng vừa xây dựng được, ứng với mỗi điểm ảnh cần nội suy, hàm biến đổi sẽ xác định toạ độ của nó rồi xác định hai điểm có cùng toạ độ trên ảnh đích và ảnh gốc. Sau đó gán giá trị màu của điểm ảnh đích bằng giá trị màu của điểm gốc tương ứng. * Cơ sở lý thuyết + Khái niệm về toạ độ Barycentric Với mỗi điểm M(xm,ym) nằm trong tam giác ABC thì chúng ta đều có thể biểu diễn toạ độ của nó theo toạ độ các đỉnh của tam giác như sau: Giải hệ phương trình này ta được một nghiệm duy nhất: ( - ) ( - ) - ( - ) ( - ) ( - ) ( - ) - ( - ) ( - ) ya yc xa xm xa xc ya ym v ya yc xa xb xa xc ya yb  ( - ) ( - ) - ( - ) ( - ) ( - ) ( - ) - ( - ) ( - ) ya ym xa xb xa xm ya yb w ya yc xa xb xa xc ya yb  u = 1-v-w Ti = S i Ti  Tj =  xm = u  xa + v  xb + w  xc ym = u  ya + v  yb + w  yc u+v+ w = 1 u,v, w  0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Chúng ta nói rằng điểm M có toạ độ là (u, v, w) đối với tam giác ABC. + Một số đặc điểm cần chú ý của toạ độ Barycentric Đối với mỗi điểm toạ độ của nó là duy nhất. Toạ độ của một điểm phụ thuộc vào tỉ lệ các khoảng cách từ nó đến các đỉnh của tam giác chứ không phải là khoảng cách tuyệt đối giữa chúng. Nếu khoảng cách tương đối của điểm cần biểu diễn đến điểm cơ sở nhỏ thì hệ số tương ứng với nó sẽ lớn. Hình 2.1 sẽ minh hoạ cho khái niệm hệ toạ độ Barycentric. Đến đây thuật toán đã hoàn toàn rõ ràng. Vậy các bước phải thực hiện đối với thuật toán này là: Xây dựng lưới tam giác cho ảnh gốc và ảnh đích Đối với mỗi cặp tam giác tương ứng với ảnh gốc và ảnh đích ta nội suy tam giác ở ảnh gốc thành tam giác ở ảnh đích. Một vấn đề nảy sinh là làm sao có thể tìm được tất cả các điểm thuộc tam giác ABC một cách hiệu quả? Có nhiều phương án để giải quyết vấn đề này, phần sau đây sẽ giới thiệu một phương pháp khá hiệu quả. * Phương pháp xác định tất cả các điểm thuộc một tam giác Phương pháp này gồm có các bước như sau: Tìm các giá trị xmax, xmin, ymax, ymin đối với các đỉnh của tam giác. (0,1,0) (1,0,0) (0,0,1) Hình 2.1 Hệ toạ độ Barycentric M Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 For a = ymin to ymax do - Tìm giao điểm của đường thẳng y=a với 3 cạnh của tam giác. - Chỉ xét các giao điểm có hoành độ thuộc [xmin,xmax] và sắp xếp các giao điểm theo chiều tăng dần của hoành độ. - Các điểm nằm trên đường thẳng y=a và có hoành độ thuộc đoạn [x_min,x_max] là thuộc tam giác (với x_ thể hiện hoành độ giao điểm). Sử dụng thuật toán tam giác người ta có thể xác định được tọa độ các điểm bị bóp méo dựa vào cặp điểm đặc trưng. Các điểm này được xác định dựa vào việc xác định tam giác nào là cơ sở, cặp điểm nào là cơ sở. Việc xác định cặp điểm đặc trưng có thể dựa vào thuật toán sau Trước tiên định nghĩa một ánh xạ T cho các đỉnh của tam giác: M(A)=A', M(B)=B', M(C)=C'. Các điểm còn lại sẽ được ánh xạ theo toạ độ Barycentric (1, 2, 3) nghĩa là: X= 1*A+2*B+3*C Trong đó: i  0 và 1+ 2+ 3 =1 Khi đó điểm Y là ánh xạ của X qua M được tính toán như sau: Y = M(X) = M(1*A+2*B+3*C) = 1* M (A) +2*M(B) +3*M(C) = 1*A'+2*B'+3*C' y = ymin y = ymax x = x m ax x = x m in Hình 2.2 Tìm tất cả các điểm thuộc tam giác theo dòng quét Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 b. Phân vùng tứ giác Nếu lưới xây dựng trên ảnh nguồn và đích tương ứng là lưới tứ giác, ta cần nội suy các tứ giác cho nhau. Để thực hiện điều này ta dùng phép nội suy Bilinear. Phép nội suy Bilinear xác định một hàm biến đổi từ một hình vuông kích thước 0,1x0,1 tới một tứ giác trong không gian (tứ giác này không nhất thiết phải đồng phẳng). Phép biến đổi được thực hiện tương đương với hai việc: Thứ nhất là nội suy trên các cạnh AD và BC thu được điểm P và Q. P = (1-v)A +vD Q = (1-v)B +vC Việc tiếp theo là nội suy trên đoạn PQ sử dụng thông số u: B(u,v)=(1-u)P +uQ 2.2. Nắn chỉnh trên cơ sở tập các điểm đặc trưng Thuật toán có hướng tiếp cận dựa trên cơ sở các cặp điểm đặc trưng như đã trình bầy ở trên. Do vậy, điều quan trọng là làm sao có thể biểu diễn được một điểm bất kỳ theo tập các đặc trưng khi mà lực lượng của tập lớn. Tuy nhiên, thuật toán lợi dụng tính chất phân vùng của đối tượng ảnh để Hình 2.4 Nội suy Bilinear Hình 2.3. Nội suy tam giác Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 giảm nhẹ lực lượng hệ cơ sở từ tập các đặc trưng ban đầu giúp cho việc biểu diễn là khả thi. Việc xác định các điểm đặ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 điểm đặ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 hình học. Để đạ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 điểm đặc trưng. Thông thường nắn chỉnh hình dạng người ta dùng phương pháp bình phương bé nhất hoặc giá trị trung bình nhỏ nhất trên cơ sở thông tin thu được từ các điểm đặc trưng. Phương pháp bình phương nhỏ nhất (OLS) là một thủ thuật toán học được sử dụng để ước lượng mối tương quan giữa các biến khác nhau. Kiểu tương quan đơn giản nhất là: 0 1i i iY b b X e   Kết quả quá trình ước lượng các hệ số b0 và b1 được gọi là b0 mũ và b1 mũ. Các hệ số này được sử dụng để ước lượng biến phụ thuộc Yi mũ. Chúng ta có thể nói rằng:  0 1i iY b b X    Chênh lệch giữa giá trị thực tế Yi và giá trị ước lượng  iY là bằng yếu tố sai số ei. Điều này có thể viết dưới dạng:  0 1i i i ii i Y b b X e Y Y e        Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Minh họa lên đồ thị. Minh họa ei lên đồ thị. Mục đích của phương pháp OLS là tối thiểu hóa tổng 2 2 1 2,e e và 2 3e . Hình 2.5 Đồ thị biểu diễn giá trị ước lượng Y Hình 2.6 Đồ thị biểu diễn giá trị chênh lệch ei Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 Minh họa Yi lên đồ thị. Đường tuyến tính liên hệ X và Y được tính bằng phương pháp OLS là đáng tin cậy bởi vì nó tối thiểu hóa tổng bình phương các sai số. Nghĩa là nó tối thiểu hóa: 2 ie Tương đương với tối thiểu hóa:  2( )i iY Y Điều này có ba đặc điểm cơ bản: 1. Đường hồi quy đi qua điểm ( , )X Y , điểm này là trung bình các dữ liệu. 2. Tổng bình phương các sai số hay các phần dư là bằng 0. 3. Phương pháp OLS đưa ra những ước lượng "tốt nhất" phụ thuộc vào các khái niệm cũng như các điều kiện. Các Khái Niệm. Sai Số Ước Lượng Chuẩn[2] (SEE). 1 2 2 EE 2 ie S n         Hình 2.7 Đồ thị biểu diễn giá trị thực Yi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Tổng bình phương tất cả các sai lệch[3] (TSS). 2( )iTSS Y Y  Ta có: TSS = RSS + ESS. Mô hình giải thích bao nhiêu biến động của biến phụ thuộc! R2 sẽ giải quyết vấn đề này. R2 là tỉ lệ giữa tổng bình phương tất cả các sai lệch của biến giải thích với tổng bình phương tất cả các sai lệch, hay: 2 ES 1 S RSS R TSS TSS    R2 cao nghĩa là mô hình ước lượng được giải thích được một mức độ cao biến động của biến phụ thuộc. Nếu R2 bằng 0. Nghĩa là mô hình không đưa ra thông tin nào về biến phụ thuộc và dự đoán tốt nhất về giá trị của biến phụ thuộc là giá trị trung bình của nó. Các biến "giải thích" thực sự không đưa ra được một giải thích nào. Hình 2.8 Đồ thị biểu diễn tổng bình phương tất cả các điểm sai lệch Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 Minh họa lên đồ thị. Với phương pháp bình phương bé nhất ta có thể xây dựng được tọa độ điểm cần nắn chỉnh như sau: Với một điểm (x,y) ở ảnh gốc phải chuyển sang toạ độ (u,v) tương ứng ở ảnh đích. Phép chuyển đổi này là xác định mối quan hệ giữa (x,y) và (u,v) và ngược lại. Chuyển đổi ngược được biểu diễn như sau: T -1 (x,y)  u,v (1.1) Chuyển đổi thuận sẽ là: T(u,v)  x, y (1.2) Giải pháp chung là xác định cặp hàm đa thức: N N   aij Pi(x) Pj(y) i=0 j=i (1.3) N N   bij Pi(x) Pj(y) i=0 j=i Hình 2.9 Đồ thị biểu diễn sự biến động của các biến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Trong đó, hàm P thông thường là đa thức Chebychev và các tham số aij và bij được xác định bằng phương pháp bình phương bé nhất hoặc giá trị trung bình nhỏ nhất. Để xác định đa thức bậc N ta phải có ít nhất k=(N+1)(N+2)/2 điểm đặc trưng. Trong bài toán này, hệ toạ độ được sử dụng là hệ toạ độ Đề các nên chỉ cần ba hay nhiều hơn điểm đặc trưng cho đa thức bậc nhất (N=1). Quan hệ (1.1) sẽ trở thành phương pháp đa thức. T ([F(uc,vc)]k, [xc,yc]k, x, y)  u,v (1.4) Trong đó, cặp (uc , vc) và (xc, yc) là cặp toạ độ biểu diễn trường của các điểm đặc trưng và (N+1)(N+2)/2  k. Biến đổi Affine sáu tham số hay được sử dụng để mô hình hoá biến đổi từ vị trí toạ độ ảnh gốc sang vị trí ảnh đích. Hình thức của chúng như sau: u = 0 x + 1 y + 2 v = 3 x + 4 y + 5 Trong đó, (x,y) là điểm ở ảnh gốc cần ánh xạ sang ảnh đích. (u ,v) là toạ độ ảnh đích. Các hệ số  được ước lượng bằng phương pháp bình phương tối thiểu. Giả sử ta đã chọn n điểm đặc trưng trên ảnh gốc và ảnh đích, các giá trị  được tính toán như sau: Đặt: 1 1; i n i n i i i i x y x y n n        ; 1 1 2 2 1 1 ( )( ) ( )( ) ; và ( ) ( ) i n i n i i i i i i i n i n i i i i x x y y x x y y p q y y x x                           -1 N Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 Ta có: 1 0 1 2 1 ( )( ) 1 ( ) i n i i i i i n i i x x u x q x x                1 1 1 2 1 1 ( )( ) ( )( ) ( ) ( )( ) i n i n i i i i i i i i n i n i i i i i y y u x q x x y y y y q x x y y                              2 0 1 1 1 ( ) i n i i i u x x x y n           1 1 3 2 1 1 ( )( ) ( )( ) ( ) ( )( ) i n i n i i i i i i i i i n i n i i i i i x x v y p y y v y x x p x x y y                              1 4 3 2 1 ( )( ) 1 ( ) i n i i i i i n i i y y v y p y y                5 4 2 1 1 ( ) i n i i i v y y y y n           Phương pháp này rất hiệu quả khi nắn chỉnh các vùng có diện tích không lớn. Tuy nhiên không có giải pháp nào để xác định kích thước vùng đó là bao nhiêu là phù hợp với phép biến đổi này mà chỉ phụ thuộc vào kinh nghiệm và thực nghiệm. Nếu ảnh gốc có các mặt cần nắn chỉnh lớn thì chia thành các vùng nhỏ hơn và thực hiện biến đổi riêng rẽ từng vùng con này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 Để có được kết quả như vậy, ta cần có các phép biến đổi toạ độ của các điểm ảnh, cụ thể theo thuật toán thì ta biến đổi toạ độ (x,y) thành (u,v). có thể thể hiện bằng hình ảnh như sau: Thực chất của việc biến đổi toạ độ x, y là thực hiện kéo x đi một góc α khi đó: x = u + T*v , y = v Khi kéo y đi một góc α thì x = u , y = v + T*u Kết quả kéo sẽ được : x= fx(u,v) , y= fy(u,v) Nắn chỉnh Ảnh nguồn Ảnh đích Hình 2.10 Ảnh gốc và ảnh bị nắn chỉnh Hình 2.11 Nắn chỉnh bằng cách biến đổi tọ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 40 Thuật toán có thể viết như sau: For ( int u= 0; u< umax; u++) { For (int v=0; v<vmax; v++) { Float x = fx(u,v); Float y=fy(u,v); Dst (x,y) = Src (u,v); } } Kết quả của thuật toán: Như đã nói ở thuật toán trên trước khi để nắn chỉnh được ảnh gốc thì ta cần xác định được các cặp điểm đặc trưng. Đây là bước đầu tiên cũng là bước quan trọng trong nắn chỉnh ảnh. Ảnh nguồn Ảnh đích Hình 2.12 Mô tả sự biến đổi của tọa độ các điểm ảnh Hình 2.13 Mô tả kết quả thuật toán biến đổi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 2.3. Kỹ thuật nắn chỉnh dựa trên cơ sở vector Trong trường hợp trên giữa các điểm điều khiển không có sự ràng buộc nào. Khi các điểm đặc trưng được xác định sao cho chúng tạo thành từng cặp điểm, tức là các vector, ta sẽ có phương thức nắn chỉnh trên cơ sở các vector. a. Chuyển đổi với một cặp vector Xét trường hợp chỉ có một cặp vector: PQ trên ảnh đích và P’Q’ trên ảnh nguồn. Khi đó với mỗi điểm X trên ảnh đích, điểm X’ tương ứng với X trên ảnh nguồn được tính như sau: 2 2 . . ( ) PX PQ u PQ PX perpendicular PQ V PQ         Đặt ' 'A B = perpendicular( ' 'P Q  ) )''()''('' ABvPQuPX  Trong đó: Perpendicular() trả lại vector vuông góc, cùng chiều dài với vector vào. Hướng của perpendicular() có thể chọn một trong hai hướng: Nếu quay perpendicular() một góc 900 theo chiều kim đồng hồ quanh gốc của vector perpendicular() thì perpendicular() có hướng trùng với hướng của vector vào. Nếu quay perpendicular() một góc 900 ngược chiều kim đồng hồ quanh gốc của vector perpendicular() thì perpendicular() có hướng trùng với hướng của vector vào. Nếu đã chọn hướng nào thì trong suốt quá trình thực hiện biến đổi phải tuân theo hướng đã chọn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 Giá trị u thể hiện chiều dài của đoạn thẳng và v là khoảng cách tới đường thẳng. Giá trị của u tăng từ 0 đến 1 khi điểm ảnh tiến từ P đến Q và nhỏ hơn 0 hoặc lớn hơn 1 thì sẽ vượt qua vùng giới hạn. Giá trị của v là khoảng cách từ điểm ảnh đến đoạn thẳng. Nếu có một cặp vector thì thuật toán biến đổi được cho như sau: Với mỗi điểm ảnh X trên ảnh đích: Tìm cặp giá trị tương ứng (u,v) Tìm điểm X’ trên ảnh nguồn dựa trên (u,v) vừa xác định ImgDestination.X = ImgSource.X’ Hình 2.15 minh hoạ cho thuật toán, cách tìm điểm X’ khi biết PQ, P’Q’ và điểm ảnh X. Trong đó ảnh góc trên bên trái là ảnh gốc, các ảnh còn lại là các ảnh kết quả với đoạn thẳng được xác định tương ứng. Hình 2.14 Cặp đoạn thẳng đơn Hình 2.15 Một số kết quả minh họa của thuật toán Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 b. Chuyển đổi với nhiều cặp vector Biến đổi với nhiều cặp vector sẽ phức tạp hơn so với một cặp vector. Trong thuật toán này chúng ta sẽ tính toán thêm các giá trị weight cho sự biến đổi của từng vector. Mỗi điểm X’ sẽ được tính toán cho từng cặp vector. Độ dịch chuyển Di=Xi’-X đo sự sai khác giữa vị trí của điểm ảnh nguồn và đích. Một trọng số dựa trên những độ dịch chuyển này sẽ được tính toán. Trọng số này sẽ được xác định bởi khoảng cách từ X đến vector. Giá trị trọng số này được thêm với X để xác định điểm X’ cần lấy trên ảnh nguồn. Trường hợp vector đơn sẽ là một trường hợp đặc biệt của trường hợp nhiều vector nếu như giá trị weight không bao giờ là 0 tại mọi điểm trên ảnh. Giá trị weight là lớn nhất nếu điểm ảnh nằm đúng trên vector và sẽ là bé nhất nếu nó nằm xa vector nhất. Công thức tính weight được cho như sau: ( ) b plength W a dist        Trong đó: Length là chiều dài của vector, dist là khoảng cách từ điểm ảnh đến vector, a, b, p là các hằng số dùng để thay đổi quan hệ giữa các vector. Nếu a tiến tới 0 và dist đúng bằng 0 thì weight tiến tới vô cực. Khi đó điểm ảnh nằm trên vector gốc sẽ được ánh xạ đúng đến vị trí tương ứng trên vectơ đích. Giá trị a lớn sẽ cho kết quả nắn chỉnh tốt hơn (trơn hơn). Giá trị b thể hiện sự tác động của chiều dài vector đến các điểm ảnh. Nếu b lớn thì điểm ảnh chỉ bị tác động bởi một vector có khoảng cách đến nó ngắn nhất. Nếu b=0 thì điểm ảnh sẽ bị tác động như nhau đối với mọi vector. Giá trị hay sử dụng của b là [0.5;2]. Giá trị của p là [0;1]. Nếu p = 0 thì tất cả các weight không phụ thuộc vào chiều dài vector. Nếu p=1 thì vector nào dài hơn sẽ có weight lớn hơn. Thuật toán được cho như sau: For mỗi điểm X trên ảnh đích DSUM=(0,0) Weightsum =0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 For mỗi vector PiQi Tính u, v dựa trên Pi,Qi Tính X’i dựa trên u,v và Pi’Qi’ Di=Xi’-X dist = khoảng cách từ X tới PiQi weight= ((lengthp)/(a+dist))b DSUM=DSUM+Di*weight weightsum=weightsum+weight X’=X+DSUM/weightsum ImgDestination.X=ImgSource.X’ Hình 2.16 là một minh hoạ cho việc tính toán điểm X’ trên cơ sở biết X và các cặp vector tương ứng. Hình 2.16 Nhiều cặp vector Hình 2.17 Kết quả của thuật toán Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 Với kỹ thuật vector khi thực hiện bóp méo một hình ảnh thì hình ảnh không còn ở trạng t