Bài giảng Xử lý ảnh - Chương 13: Biến đổi ảnh rời rạc

Chia sẻ: Lão Lão | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

67
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Biến đổi Fourier rời rạc (DFT), đã giới thiệu trong chương 10, là một trong những phép biến đổi tuyến tính rời rạc hữu ích trong xử lý ảnh số. Trong chương này, chúng ta sẽ nghiên cứu chủ đề tổng quát hơn, trình bày một vài biến đổi khác và một vài tính chất cũng như các ứng dụng của chúng.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Xử lý ảnh - Chương 13: Biến đổi ảnh rời rạc

Ch¬ng 13 BIẾN ĐỔI ẢNH RỜI RẠC 13.1. GIỚI THIỆU Biến đổi Fourier rời rạc (DFT), đã giới thiệu trong chương 10, là một trong những phép biến đổi tuyến tính rời rạc hữu ích trong xử lý ảnh số. Trong chương này, chúng ta sẽ nghiên cứu chủ đề tổng quát hơn, trình bày một vài biến đổi khác và một vài tính chất cũng như các ứng dụng của chúng. Ảnh mà chúng ta quan tâm thường ở dạng liên tục và cũng phải được cảm nhận ở dạng này. Bởi vì chúng ta bắt buộc phải làm việc với sự biểu diễn rời rạc của ảnh liên tục, nên nhiều quá trình xử lý ảnh số đòi hỏi chúng ta tuân thủ những nguyên tắc lấy mẫu và nội suy trong khi xử lý dữ liệu rời rạc. Tuy nhiên, một vài ứng dụng cho phép chúng ta xem xét ảnh số như một thực thể rời rạc mà không đề cập chi tiết đến lịch sử nguồn gốc của ảnh hay đối với ảnh liên tục cơ bản. Một ứng dụng điển hình là nén ảnh. Ở đây, người ta muốn mã hoá một ảnh thành một dạng dữ liệu nhỏ gọn hơn, mà không làm mất mát hay chỉ mất mát thông tin không cần thiết. Bình thường, vì lẽ quang học, lấy mẫu và nội suy đối với sự số hoá và hiển thị ảnh là không liên quan trực tiếp và ảnh số có thể xem xét đơn thuần như một tệp dữ liệu. Biểu diễn một ảnh là một biểu hiện đặc biệt của dữ liệu ảnh. Đây là một sự thể hiện dữ liệu ảnh theo một dạng hay một khuôn dạng đặc biệt. Một ảnh số có thể được biểu diễn như một ma trận hay như một vec tơ hàng. 13.2. BIẾN ĐỔI TUYẾN TÍNH 13.2.1. Biến đổi tuyến tính rời rạc một chiều Định nghĩa. Nếu x là vec tơ N  1 và T là ma trận N  N, thì N 1 yi   t i , j x j hay y  Tx (1) j 0 trong đó i = 0, ..., N-1 là biến đổi Fourier của vec tơ x. Ma trận T cũng được gọi là ma trận hạt nhân (kernel matrix) của phép biến đổi. Lưu ý rằng cách sử dụng từ hạt nhân khác với cách sử dụng thuật ngữ hạt nhân tích chập đã đề cập trong phần 9.3.4. Kết quả của phép biến đổi làmột vec tơ y, N  1 khác. Phép biến đổi là tuyến tính bởi vì y được thực hiện bằng một phép tổng bậc nhất của các phần tử đầu vào. Mỗi phần tử yi là tích của vec tơ đầu vào x với hàng thứ i của ma trận T. Ví dụ. Một ví dụ đơn giản của phép biến đổi tuyến tính là phép quay một vec tơ trong hệ thống toạ độ hai chiều. (Xem chương 8) Ở đây,  y 1  cos   sin    x1   y    sin   cos    x  (2)  2   2  Quay vec tơ x quanh gốc toạ độ một góc . Phép nghịch đảo. Sau phép biến đổi, vec tơ ban đầu có thể được khôi phục bằng phép biến đổi ngược. y  T 1 x (3) 227
Chứng tỏ rằng T không duy nhất. Như trên, mỗi phần tử của x lại là một tích, đây là tích giữa y và một hàng của T-1. Với ví dụ trước đây, thì điều này chẳng khác gì một phép quay cùng một góc theo chiều ngược lại. 13.2.1.1. Biến đổi đơn vị Đối với vec tơ chiều dài N đã cho, có rất nhiều ma trận biến đổi có thể được sử dụng. Tuy nhiên, những ma trận hữu ích hơn liên quan đến một lớp các thuộc tính nào đó. Nếu T là ma trận đơn vị, thì T -1  T *t vµ TT *t  T *t T  I (4) Trong đó * ký hiệu liên hợp phức cho mỗi phần tử của T và t ký hiệu phép chuyển vị. Nếu T là ma trận đơn vị và chỉ có các thành phần thực thì nó là ma trận trực giao, và được biểu diễn như sau T-1  T t vµ TT t  T t T  I (5) t Chú ý rằng phần tử i, j của TT chính là tích các hàng i và j của T. Biểu thức (5) chứng tỏ rằng các phần tử đều là 0, trừ phần tử i = j, trong trường hợp nó là đơn vị. Vì thế, các hàng của T là tập các vec tơ trực giao. Ví dụ: DFT một chiều. DFT là một ví dụ về biến đổi đơn vị, vì N 1 1  i  Fk  N f i 0 i exp  j 2k  hay F = Wf  N (6) Trong đó W là ma trận đơn vị (nhưng không trực giao) với các phần tử (phức) 1  i   i ,k  exp  j 2k  (7) Ni  N Nội suy. Bình thường, ma trận biến đổi T không đơn nhất (chẳng hạn, rank(T) = N), để có thể đảo ngược biến đổi, như biểu thức (3). Các hàng của T tạo thành một cơ sở trực giao (một tập các vec tơ cơ sở trực giao hay các vec tơ đơn vị) đối với không gian vec tơ N chiều của tất cả các vec tơ N  1. Điều này có nghĩa là một chuỗi N  1 bất kỳ có thể xem như biểu diễn một vec tơ ban đầu thành một điểm trong không gian N chiều. Hơn nữa, một biến đổi dạng biểu thức (1) bất kỳ có thể xem như là một biến đổi toạ độ, quay vec tơ trong không gian N chiều mà không thay đổi độ dài của vec tơ. Theo giả thiết thì một biến đổi tuyến tính đơn vị sinh ra vec tơ y, vec tơ N hệ số biến đổi, mỗi một hệ số được tính như là một tích của vec tơ vào x với một hàng của ma trận biến đổi T. Biến đổi ngược được tính toán tương tự, giống như một tập các tích thành phần của vec tơ hệ số biến đổi với các hàng của ma trận biến đổi ngược. Biến đổi tiến nói chung được coi là một quá trình phân tích, việc phá vỡ vec tơ tín hiệu ra thành các thành phần cơ bản. Các thành phần cơ bản này thường thấy ở dạng các vec tơ cơ sở. Các hệ số biến đổi chỉ rõ có thể tìm thấy bao nhiêu vec tơ trong mỗi thành phần được thể hiện trong tập những vec tơ riêng biệt được phân tích. Biến đổi ngược, nói cách khác, thường được coi là một quá trình tổng hợp (synthesis), tập hợp thành vec tơ ban đầu từ các thành phần của nó theo phép tổng. Ở đây, các hệ số biến đổi chỉ rõ khối lượng chính xác mỗi vec tơ cơ sở phải được thêm vào tập hợp để tái tạo lại vec tơ đầu vào đầy đủ và chính xác. Mấu chốt của quá trình này là nguyên tắc mà bất kỳ một vec tơ nào cũng có thể được phân tích duy nhất thành một tập các vec tơ biên độ cơ bản thích hợp và sau đó khôi phục lại bằng cách thêm các thành phần này lại với nhau để tái tạo vec tơ ban đầu. Điều này có ý nghĩa rằng số các hệ số biến đổi bằng với số các phần tử trong 228
vec tơ. Vì thế, số bậc tự do trước và sau biến đổi là như nhau và quá trình cũng không tạo ra hay phá huỷ thông tin. Một vec tơ được biến đổi là một sự biểu diễn của vec tơ ban đầu. Vì nó chứa cùng một số lượng các phân tử (và vì thế có cùng số bậc tự do) như vec tơ gốc và vì vec tơ gốc có thể khôi phục từ nó mà không sai sót, nên nó có thể được coi là một dạng lựa chọn của việc biểu diễn vec tơ ban đầu. Chương này xem xét một vài phương pháp lựa chọn cho việc biểu diễn tín hiệu và ảnh số, và lợi ích của mối phương pháp. 13.2.2. Biến đổi tuyến tính rời rạc hai chiều Biến đổi tuyến tính hai chiều nói chung là biến đổi ma trận F, N  N thành ma trận được biến đổi G (cũng là N  N) là N 1 N 1 Gm,n   Fi ,k i, k , m, n  (8) i 0 k 0 trong đó i, k, m và n là các biến rời rạc nằmg trong khoảng từ 0 đến N - 1 và (i,k,m,n) là hàm hạt nhân của phép biến đổi. Có thể xem (i,k,m,n) như là một ma trận khối N2  N2 có N hàng, mỗi hàng có N khối, mỗi khối lại là một ma trận N  N. Các khối được đánh chỉ số m, n và những phần tử của từng ma trận con N  N được đánh chỉ số i, k (Xem hình 13-1). Nếu có thể tách (i,k,m,n) ra thành tích các hàm thành phần hàng và cột-tức là, nếu i,k,m,n  Tr i, m Tc k , n (9) Thì biến đổi được gọi là tách được (separable). Nghĩa là nó có thể tiến hành trong hai bước-một phép toán theo hàng tiếp theo là một phép toán theo cột (hay ngược lại): N 1 N 1   Gm,n    Fi, k T k , n Tr i, m  (10) i 0  k 0  Hơn nữa, nếu hai hàm thành phần giống nhau thì biến đổi cũng được gọi là đối xứng (không được nhầm lẫn vpí ma trận đối xứng). Và i,k,m,n  T i, m T k , n  (11) Và biểu thức (8) có thể viết lại như sau N 1  N 1  Gm,n   T i, m  Fi ,k Tc k , n  hay G  TFT (12) i 0  k 0  Trong đó T là ma trận đơn vị, gọi là ma trận hạt nhân của biến đổi. Chúng ta sẽ sử dụng ký hiệu cho toàn bộ chương này, để biểu thị cho biến đổi đơn vị đối xứng, tách được và tổng quát. Biến đổi ngược là F  T 1GT 1  T *t GT *t (13) và nó khôi phục lại F một cách chính xác. Ví dụ: DFT hai chiều. DFT hai chiều là biến đổi đơn vị dc và tách được. Trong trường hợp này, T trong biểu thức (12) trở thành ma trận W do biểu thức (7). DFT ngược sử dụng W-1, là chuyển vị liên hợp của W. Cặp biến đổi Fourier rời rạc được biểu diễn như sau G = WFW và F = W*tGW*t (14) 229
HÌNH 13-1 Hình 13-1 Ma trận hạt nhân 13.2.2.1. Phép biến đổi trực giao Không giống như biến đổi Fourier, nhiều biến đổi chỉ có các thành phần thực trong ma trận hạt nhân T của chúng. Một ma trận đơn vị với các thành phần thực là trực giao và phép biến đổi ngược trở nên đơn giản là F  T t GT t (15) Nếu T là ma trận đối xứng, như thường gặp, thì biến đổi xuôi và ngược đều như nhau, để cho G  TFT vµ F  TGT (16) 13.3. HÀM VÀ ẢNH CƠ SỞ Khác nhau cơ bản giữa hai biến đổi đơn vị bất kỳ là sự lựa chọn các hàm cơ sở, tức là, các hàng của ma trận T. Ở đây, chúng ta sẽ xem xét các hàm cơ sở chi tiết hơn. 13.3.1. Hàm cơ sở Các hàng của ma trận hạt nhân tạo thành một tập các vec tơ cơ sở đối với không gian vec tơ N chiều. Các hàng là trực chuẩn; tức là N 1 TT *t  I hay T j ,i T * k ,i   j , k (17) i 0 Trong đó j,k là del ta Kronecker. Trong khi một tập các vec tơ trực chuẩn bất kỳ sẽ có lợi cho biến đổi tuyến tính, bình thường thì toàn bộ tập xuất phát từ cùng một dạng hàm cơ sở. Ví dụ, biến đổi Fourier sử dụng thành phần mũ phức như hàm cơ sở nguyên mẫu. Các hàm cơ sở riêng lẻ chỉ khác nhau về tần số. Một vec tơ không gian bất kỳ có thể được biểu diễn như tổng trọng số các vec tơ đơn vị cơ sở. Một biến đổi đơn vị một chiều (N  1) tương ứng với phép quay vec tơ trong không gian vec tơ N chiều. Hơn nữa, vì một ma trận ảnh N  N có thể sắp xếp để tạo thành vec tơ N2  1, một biến đổi hai chiều, đối xứng, tách được bất kỳ tương ứng với một phép quay vec tơ trong không gian N2 chiều. 13.3.2. Ảnh cơ sở Biến đổi hai chiều ngược có thể được coi như quá trình tái tạo ảnh bằng cách cộng tập các ảnh cơ sở thích hợp. Mỗi phần tử trong ma trận biến đổi G là một hệ số, được nhân với ảnh cơ sở tương ứng trong phép cộng. Một ảnh cơ sở có thể được tạo ra bằng biến đổi ngược một ma trận các hệ số chỉ chứa một phần tử khác 0, thường đặt bằng 1. Có N2 ma trận như vậy và chúng tạo ra N2 ảnh cơ sở. Đặt một ma trận hệ số là 230
G p ,q   i  p , j  q  (18) Trong đó i và j là chỉ số hàng và cột, p và q là các số nguyên xác định vị trí phần tử khác 0. Biến đổi ngược [biểu thức (13)] là N 1  N 1  Fm,n   T i, m   i  p ,k q T k , n   T  p, m T q , n  (19) i 0  k 0  Vì thế, đối với biến đổi đơn vị tách được, mỗi ảnh cơ sở là một tích hai hàng của ma trận biến đổi. Giống như đối với các tín hiệu một chiều, có thể coi các ảnh cơ sở như tập các thành phần cơ sở để phân tích một ảnh bất kỳ. Chúng cũng tạo nên những khối để tái tạo một ảnh bất kỳ. Biến đổi xuôi thực hiện sự phân tích bằng cách xác định các hệ số. Biến đổi ngược thực hiện sự khôi phục lại bằng cách cộng các ảnh cơ sở,căn cứ trên các hệ số đó. Bởi vì tồn tại rất nhiều tập ảnh cơ sở, cũng như tồn tại rất nhiều phép biến đổi. Vì vậy, một tập các ảnh cơ sở đặc trưng chỉ quan trọng trong ngữ cảnh của một biến đổi đặc biệt. 13.4. BIẾN ĐỔI ĐIỀU HOÀ Với những nguyên nhân đã đề cập đến trong chương 10, biến đổi Fourier đã nổi lên như một biến đổi đơn quan trọng nhất trong xử lý ảnh số. Tuy nhiên, nó có vài quan hệ cũng sử dụng các hàm cơ sở điều hoà. Chúng sẽ được đưa ra trong phần này, sau một bài thảo luận ngắn gọn về biến đổi Fourier. 13.4.1. Biến đổi Fourier rời rạc Đã được giới thiệu trong chương 10, DFT lại được xem xét ở đây, trong nội dung các biến đổi đơn vị tách biệt, cho phép chúng ta nêu ra những so sánh giữa nó và những biến đổi khác của cùng một kiểu. Ma trận hạt nhân đối với DFT (biểu thức (6) và (7)) là  w0, 0  w0, N 1    W      (20)  wN 1, 0  w N 1, N 1  Trong đó ik 1  j 2 N wi,k  e (21) N Bởi vì tính tuần hoàn của thành phần mũ phức, W bằng 1. Các DFT xuôi và ngược một chiều là F = Wf và f = W*t F (22) Trong đó f và F là các vec tơ tín hiệu và phổ. Nếu f là thực, thì nói chung, F sẽ có các thành phần phức. Chỉ nếu f đối xứng hoàn toàn thì F mới là thực. 13.4.1.1. Vec tơ phổ Hình 13-2 cho thấy nơi mà các thành phần tần sóoo khác nhau xuất hiện trong vec tơ phổ F, khi f là thực. Thành phần tần số 0 và thành phần tần số cao nhất (tương ứng với tần số Nyquist) xuất hiện chỉ một lần. Những thành phần còn lại được nhân đôi như các liên hợp phức. (Nhắc lại rằng phổ của một hàm thực là một hàm Hermite.) Nếu coi F như một vec tơ hàng, thì N/2 + 1 phần tử đầu tiên là nửa bên phải của phổ, 231
còn lại N/2 - 1 phần tử sau thuộc nửa bên trái. Tần số tương ứng với phần tử thứ i của F là  2i  N f N 0 i  N /2 si   (23)  2 N  i  f N / 2 1  i  N 1  N N Trong đó fN là tần số Nyquist (tần số cơ bản, bằng nửa tần số lấy mẫu). Nếu N/2 - 1 phần tử sau của f tạo thành một ảnh sao chép lại của các phần tử từ 1 đến N/2 - 1, thì F là chẵn và sẽ có giá trị thực. HÌNH 13-2 Hình 13-2 Vị trí các thành phần tần số khác nhau trong vec tơ phổ Ta có thể quay các phần tử của F đi một lượng N/2, sử dụng phép toán dịch phải (hay trái) vòng tròn, để tạo ra một vec tơ thích hợp cho việc vẽ phổ. Trong trường hợp đó, phần tử tần số 0 được định vị tại N/2, và tần số tăng theo cả hai chiều. Phần tử tần số Nyquist chỉ xuất hiện tại F0. Lý thuyết dịch của biến đổi Fourier (Xem phần 10.2.3) cung cấp một cách khác cũng đạt đến kết quả như vậy. Việc áp dụng lý thuyết dịch trong miền tần số cho ta  u  F u   f  x   F u  u 0   exp j 2x 0  f  x   exp jx  f  x    1 f  x  x (24)  N  Trong đó lượng dịch là u0 = N/2. Nghĩa là chúng ta chỉ đổi dấu của các phần tử đánh số lẻ của f(x) trước khi thực hiện DFT. 13.4.1.2. DFT hai chiều Các DFT hai chiều xuôi và ngược là G = WFW và F = W*tGW*t (25) Trong đó F là ảnh dạng ma trận và G là ma trận phổ của nó. Hình 13-3 cho thấy vị trí mà các thành phần tần số không gian khác nhau được định vị trong ma trận phổ G. sự sắp xếp lại bốn góc phần tư, cho trong hình, khiến cho việc hiển thị phổ thuận tiện hơn. Theo cách đó, tần số 0 nằm tại tâm của ma trận, và từ đây tần số tăng dần ra. Biểu thức (24) được tổng quát hoá cho trường hợp hai chiều thành x y F u , v   f  x, y   F u  N / 2, v  N / 2    1 f  x, y  (26) Và lại đổi dấu một nửa số phần tử trong ma trận ảnh F để có được phép dịch mong muốn. Nếu F đối xứng như trong hình 13-3(a) thì G sẽ có giá trị thực. 232
13.4.2. Biến đổi cosin rời rạc Biến đổi cosin rời rạc (Discrete Cosin Transform-DFT) hai chiều được định nghĩa như sau N 1 N 1  2i  1m   2k  1n  Gc m, n    m  n  g i, k  cos  cos   (27) i 0 k 0  2N   2N  Và biến đổi ngược của nó là N 1 N 1   2i  1m   2k  1n  g i, k     m  n Gc m, n  cos  cos   (28) m 0 n 0  2N   2N  Trong đó các hệ số là 1 2  0   vµ  m   víi 1  m  N (29) N N Giống như DFT, DCT có thể được biểu diễn như một phép toán ma trận đơn vi dưới dạng G c  CgC (30) Trong đó ma trận hạt nhân có các phần tử  2i  1m  C i,m   m cos   (31)  1N  Cũng giống như DFT, DCT có thể được tính bằng một thuật giải nhanh. Khác với DFT, DCT là thực. Nó được sử dụng rộng rãi trong nén ảnh. 13.4.3. Biến đổi sin Jain đã đưa ra định nghĩa biến đổi sin rời rạc như sau 2 N 1 N 1  i  1m  1   k  1n  1  Gs m, n    g i, k  sin   sin   (32) N  1 i 0 k 0  2N   2N  Và 2 N 1 N 1  i  1m  1   k  1n  1  g i, k    Gs m, n  sin   sin   (33) N  1 m 0 n 0  2N   2N  DST có các phần tử ma trận hạt nhân 2   i  1k  1  Ti ,k  sin   (34) N 1  N 1  Không giống các biến đổi điều hoà khác, DST được tính toán tiện lợi nhất với N = 2p, trong đó p là số nguyên. Nó có thể được thực hiện như phần ảo của một FFT (2N + 2) điểm có cấu trúc đặc biệt. DSt có một thuật giải thực hiện nhanh và các tính chất hay dùng trong các bài toán nén ảnh. 13.4.4. Biến đổi Hartley Năm 1942, Hartley đã đưa ra một biến đổi tích phân liên tục như là một bước tiếp theo của biến đổi Fourier. Sau đó Bracewell đã định nghĩa một biến đổi đơn vị rời rạc giống như vậy dựa trên biến đổi Hartley. Biến đổi Hartley rời rạc hai chiều (DHT) 233
N 1 N 1 1  2  Gm,n   g i ,k cas  im  kn  (35) N i 0 k 0 N  Và DHT ngược hai chiều N 1 N 1 1  2  g i ,k   G m,n cas  im  kn  (36) N m 0 n 0 N  Là giống nhau và sử dụng hàm cơ sở cas   cos   sin    2 cos   / 4 (37) Là hàm cosin được dịch 450 sang phải 1   ik  Ti ,k  cas 2 N  (38) N    Trong khi DFT biến đổi N số thực thành N số phức đối xứng liên hợp, hiển thịì DHT tạo thành N số thực. Như mong đợi, DHT có quan hệ gần gũi với DFT. Trong chương 10, chúng ta đã thấy rằng biến đổi Hartley đơn giản là phần thực trừ đi phân f ảo của biến đổi Fourier tương ứng. Cũng như vậy, biến đổi Fourier là phần chẵn trừ đi j lần phần lẻ của biến đổi Hartley. Lý thuyết tích chập của biến đổi Hartley chỉ hơi phức tạp hơn lý thuyết tích chập của biến đổi Fourier. Nó được biểu diễn như sau g  x   f  x  * h x   G v   F v H e v   F  v H o v  (39) Trong đó F(v) và G(v) là những biến đổi Hartley của f(x) và g(x) tương ứng, và He(v) và Ho(v) là các thành phần biến đổi Hartley chắn và lẻ của h(x). (Xem phần 10.2.1 về định nghĩa các thành phần chẵn và lẻ.) Trong trường hợp thường gặp là một trong các hàm là chẵn, số hạng thứ hai của biểu thức (39) triệt tiêu, và tích chập tương ứng với phép nhân trong miền biến đổi Hartley, giống như thực hiên biến đổi Fourier trong miền tần số. DHT là một bước tính toán kế tiếp của DFT. Có một thuật giải nhanh cho biến đổi Hartley. Đối với các ứng dụng lọc tuyến tính-đặc biệt nếu ma trận hạt nhân là đối xứng-DHT có thể làm giảm đáng kể khối lượng công việc tính toán, vì nó tránh được phép toán số học phức tạp. 13.4.5. Các biến đổi điều hoà khác Jain đã giới thiệu một họ các biến đổi đơn vị có các hàm cơ sở điều hoà. DFT, DHT và DST thuộc họ này. 13.5. BIẾN ĐỔI SÓNG CHỮ NHẬT Một vài biến đổi quan trọng trong xử lý ảnh số sử dụng các hàm cơ sở là những biến đổi sóng vuông hơn là sóng điều hoà. Nói chung, chúng tính toán nhanh vì nhiều phép nhân trở nên tầm thường. Trong phần này, chúng ta sẽ đề cập đến các biến đổi Hadamard, Walsh, nghiêng và Haar. Về cơ bản biến đổi Haar khác ba biến đổi kia và được xét đến kỹ hơn, trong nội dung của các biến đổi sóng con ở chương tiếp theo. 13.5.1. Biến đổi Hadamard Biến đổi Hadamard là biến đổi đối xứng, đơn vị có thể tách rời mà chỉ có các phần tử -1 và 1 trong ma trận hạt nhân của nó. Nó tồn tại với N = 2n, trong đó n là số nguyên. 234
Đối với trường hợp 2  2, ma trận hạt nhân sẽ là 1 1 1 1  H2    (40) 2 2 1  1 và với N lớn hơn, ma trận này có thể được tạo thành từ dạng ma trận khối. 1 1 H N / 2 H N /2  HN   (41) N N H N / 2 H N / 2  Đối với N = 2n bất kỳ, ma trận chỉ chứa các phần tử 1, miễn là hệ số N-1/2 không được phép nằm trước. Điều này khiến cho việc tính toán biến đổi ít phức tạp hơn. Ví dụ, với N = 8, ma trận biến đổi Hadamard là 1 1 1 1 1 1 1 1 0 1 1 1 1 1  1 1  1 7  1 1 1 1 1 1  1  1 3   1 1 1 1 1 1 1 1 1  4 H8  (42) 2 2 1 1 1 1 1  1  1  1 1   1 1 1 1 1 1 1 1  6 1 1 1 1 1 1 1 1 2   1 1 1 1 1 1 1  1 5 trong đó cột bên phải cho thấy số ký hiệu thay đổi theo hàng tương ứng. Chú ý rằng các cột này khác nhau đối với từng hàng. Ký hiệu số đến thay đổi này được gọi là sự phối hợp hàng. Chúng ta ta có thể sắp xếp thứ tự các hàng để tạo thành dãy tăng tần theo số hàng. Hạt nhân của biến đổi Hadamard có thứ tự, với N = 8, 1 1 1 1 1 1 1 1 0 1 1 1 1  1  1  1  1 1  1 1 1 1 1 1 1 1 2   1 1 1 1 1 1 1  1  1 3 H8  (43) 2 2 1 1 1 1 1 1 1 1  4   1 1 1 1 1 1 1  1 5 1 1 1 1 1 1 1 1  6   1 1 1 1 1  1 1  1 7 13.5.2. Biến đổi Walsh Các hàm cơ sở Hadamard thực tế là các hàm Walsh. Vì thế, biến đổi Hadamrd cũng đươck coi là biến đổi Walsh. 13.5.3. Biến đổi nghiêng Biến đổi nghiêng (slant) được thiết kế không chỉ có một hàm cơ bản không đổi thứ nhất mà còn một hàm tuyến tính thứ hai (hình 13-4). Hàm cơ bản thứ hai được làm nghiêng cho phù hợp với nền dốc tuyến tính hiện diện trong nhiều ảnh. Ma trận hạt nhân đơn vị đối với biến đổi nghiêng xuất phát từ ma trận Haar hay Hadamard 2  2, 235
1 1 1  S2    (44) 2 1  1 và lặp lại nó theo giản đồ  1 0 1 0  a 0 0  N bN  a N bN  SN  1  0 I 0 I  S N / 2 0  (45) 2  0 1 0 1  0 S N / 2   b 0 0  aN bN a N  N   0 I 0  I trong đó I là ma trận đồng nhất bậc N/2- 2 và 3N 2 N 2 1 a2 N  vµ b2 N  4N 2  1 4N 2  1 (4.40) Các hàm biến đổi nghiêng cơ bản xuất hiện tại các tần số từ 0 đến N-1. Biến đổi nghiêng cũng có một thuật giải biến đổi nhanh và được sử dụng trong nén ảnh. 0 4 1 5 2 6 3 7 Hình 13-4 Các hàm cơ bản biến đổi nghiêng với N = 8 13.5.4. Biến đổi Haar Biến đổi Haar là biến đổi đối xứng, đơn nhất có thể tách và sử dụng hàm Haar làm cơ sở. Nó tồn tại với N = 2n, trong đó n nguyên. 236
Trong khi các hàm biến đổi Fourier cơ bản chỉ khác nhau về tần số thì các hàm Haar thay đổi cả tỷ lệ lẫn vị trí. Điều này khiến cho bản chất cặp tỷ lệ-vị trí là hiển nhiên trong các hàm cơ bản của nó (hình 13-5). Đặc tính nêu trên phân biệt biến đổi Haar với các biến đổi khác đã đề cập trước đây và thiết lập điểm xuất phát cho các biến đổi sóng con, sẽ trình bày ở chương tiếp theo. Liên hệ hàm cơ sở. Bởi vì các hàm Haar thay đổi theo hai hướng (tỷ lệ và vị trí) nên chúng phải được xác định rõ bằng một cặp giản đồ liên hệ. Các hàm Haar được định nghĩa trên đoạn [0, 1] như dưới đây. Cho số nguyên 0  k  N  1 được xác định (duy nhất) bằng hai số nguyên khác, p và q, như sau k = 2p + q - 1 (47) Chú ý rằng với cấu trúc này, không chỉ k là hàm của p và q, mà p và q cũng là hàm của k. Với giá trị k > 0 bất kỳ, 2p là luỹ thừa 2 lớn nhất sao cho 2p  k và q-1 là số dư. Hàm Haar được định nghĩa bởi 1 h0 ( x)  N (482) và  1  p/2 q q 1 2 2 x  2p 2p  1 q 1  p / 2 2 x q hk ( x )   2 p (49) N 2 2p 0 c¸c trêng hîp cßn l¹i     Nếu chúng ta đặt x = i/N với i = 0, 1,..., N-1, thì biểu thức này tạo ra một tập các hàm cơ bản, mỗi hàm là một cặp xung vuông lẻ, ngoại trừ k = 0, như trong trường hợp nhiều biến đổi khác được đề cập ỏ đây, là hằng số. Hơn nữa, các hàm cơ bản thay đổi theo cả tỷ lệ (chiều rộng) lẫn vị trí. Chỉ số p xác định vị trí, còn q xác định độ dịch. Trong khi các biến đổi đã đề cập từ trước cho đến giờ sử dụng các hàm cơ sở có chiều rộng đầy đủ, thì các hàm Haar đều là cặp xung chữ nhật lẻ được lấy tỷ lệ, các phiên bản của một hàm “đơn nguyên” đã dịch. Tính chất này có hai chủ yếu. Thứ nhất, mặc dù các hàm cơ sở được nhận biết bằng chỉ số đơn k, nhưng chúng có tính chất tỷ lệ-vị trí đối ngẫu đượ xác định rõ bởi các chỉ số p và q. Vì thế, nó không được sáng tỏ cho lắm khi vẽ các hệ số biến đổi trên trục k so với vẽ trên, ví dụ, phổ tần số thông thường nhận được bằng biến đổi Fourier. Thứ hai, cho trước một tính chất đặc thù, ví dụ như cạnh, được thên vào tín hiệu tại một vài vị trí dọc theo trục x. Biến đổi Fourier, sẽ mã hoá vị trí này thành phổ pha phù hợp với lý thuyết dịch (Xem phần 10.2.3). Trong khi đặc tính vị trí được xác định duy nhất và có thể khôi phục một cách chính xác nhờ biến đổi Fourier ngược, thì có thể không nhìn thấy nó trong một thể hiện thích hợp nào đó của phổ. (Chú ý: nếu một đặc tính đơn làm tín hiệu nổi bật, thì đồ thị pha sẽ tuyến tính, với độ dốc liên quan đến đặc tính vị trí (như trong lý thuyết dịch) và có thể sử dụng điều này để định 237
vị đặc tính. Tuy nhiên, vô số các đặc trưng hay hiện diện của nhiễu thường khiến cho đồ thị pha phức tạp đến nỗi không thể hiểu được.) Ma trận hạt nhân đơn vị đối với biến đổi Haar 8  8 là  1 1 1 1 1 1 1 1   1 1 1 1 1 1 1  1    2 2  2  2 0 0 0 0    1  0 0 0 0 2 2  2  2 Hr  (50) 8 2 2 0 0 0 0 0 0     0 0 2 2 0 0 0 0   0 0 0 0 2 2 0 0     0 0 0 0 0 0 2  2  HÌNH 13-6 Hình 13-6 Ảnh cơ sở biến đổi haar với N = 8 13.6. BIẾN ĐỔI CĂN CỨ VÀO EIGEN VEC TƠ Hai biến đổi quan trọng sử dụng các hàm cơ sở xuất phát từ eigenanalysis. 13.6.1. Phân tích sinh (Eigenanalysis) Nhắc lại rằng đối với một ma trận A, N  N, có N hệ số tỷ lệ, k, k = 0, 1, ..., N -1, sao cho A  k I  0 (51) Các k được gọi là các giá trị sinh (eigenvalue) của ma trận. Hơn nữa, tập các vec tơ vk sao cho Avk  k v k (52) được gọi là các vec tơ sinh (eigenvector) của A. chúng là N  1 và mỗi vec tơ tương ứng với một trong những giá trị sinh. Các vec tơ sinh tạo thành tập cơ sở trực chuẩn. 13.6.2. Phân tích thành phần chính Hotelling đã phát triển một phép biến đổi tuyến tính, cho phép loại bỏ tương quan giữa các phần tử của vec tơ ngẫu nhiên và được gọi là “thứ tự các thành phần chính”. 238
Sau đó Karhunen và Loeve đã phát triển một phép biến đổi tín hiệu liên tục tương tự như vậy. Tiếp cận này dẫn đến khái niệm biến đổi ảnh rời rạc. Giả sử x là vec tơ ngẫu nhiên N  1; tức là, mỗi phần tử xi của x là một biến ngẫu nhiên. Vec tơ trung bình của x có thể được ước lượng từ một mẫu L của các vec tơ trên bằng công thức 1 L mx   xl L l 1 (53) Và ma trận hiệp biến là L  t C x    x  m x x  m x   1L  x x l ' l  m x m x' (54) l 1 Ma trận hiệp biến là ma trận N  1, thực và đối xứng. Các phần tử trên đường chéo là các biến trạng của các biến ngẫu nhiên riêng biệt, trong khi các phần tử ngoài đường chéo là các hiệp biến của chúng. Bây giờ để ma trận A định nghĩa một phép biến đổi tuyến tính, tạo ra một vec tơ y mới từ một vec tơ x bất kỳ bởi y  A x  m x  (55) Trong đó A được xây dựng sao cho các hàng của nó là các vec tơ sinh của Cx. Để thuận tiên, chúng ta sắp xếp các hàng theo thứ tự độ lớn các giá trị sinh giảm dần. Vec tơ biến đổi y là vec tơ ngẫu nhiên với trung bình 0. Ma trận hiệp biến của nó liên quan đến ma trận hiệp biến của x bởi C y  AC x A t (56) Vì các hàng của A là các vec tơ sinh của Cx, nên Cy là một ma trận đường chéo mà các giá trị sinh của Cx nằm trên đường chéo của nó. (Đây là kết quả của biểu thức (52)). Vì thế, 1 0  Cy     (57)   0  N  Và k cũng là các giá trị sinh của Cy. Bởi vì các phần tử nằm ngoài đường chéo của Cy bằng 0, nên các phần tử của y là không tương quan. Vì vậy, biến đổi tuyến tính A sẽ loại bỏ sự tương quan giữa các biến. Hơn nữa, mỗi biến k lại là biến trạng của yk, biến biến đổi thứ k. Lưu ý rằng biến đổi của biểu thức (55) có thể đảo ngược; tức là, chúng ta có thể tái tạo một vec tơ x từ vec tơ biến đổi y của nó theo x  A 1 y  m  A t y  m (58) Đẳng thức sau đúng vì A là đơn vị, thực, và trực giao. 13.6.2.1. Sự giảm chiều Chúng ta có thể giảm số chiều của các vec tơ y bằng cách bỏ qua một hay nhiều eigenvecter mang giá trị sinh nhỏ. Đặt B là ma trận M  N (M < N) có được từ A do bỏ đi các hàng thấp hơn, và giả sử rằng m = 0. Thì các vec tơ biến đổi sẽ nhỏ hơn (chảng hạn M  1) và được cho bởi  y  Bx (59) 239
Nhưng x cũng có thể tái tạo (gần đúng) lại bằng   x  Bt y (60) Sai số bình phương trung bình của xấp xỉ này là N MSE   k  M 1 k (61) Tức là, tổng tuyệt đối các giá trị sinh tương ứng với các vec tơ sinh bị loại bỏ. Thường thì các giá trị sinh biên độ thay đổi một cách đáng kể và có thể bỏ qua các giá trị nhỏ hơn mà không gặp phải sai số đáng kể. 13.6.3. Biến đổi Karhunen-Loeve Biểu thức (55) định nghĩa một biến đổi rời rạc (một chiều). Nó được gọi là biến đổi Karhunen-Loeve (hay K-L), biến đổi Hotelling, biến đổi vec tơ sinh hay phương pháp thành phần chính, tuỳ theo từng trường hợp. Chúng ta sẽ bám vào thực tiễn phổ biến của biến đổi Karhunen-Loeve. Khả năng giảm chiều của biến đổi Karhunen-Loeve khiến cho nó rất hữu ích đối với kỹ thuật nén ảnh. Ví dụ, các ảnh đa phổ có nhiều giá trị mức xám tại từng điểm ảnh, mỗi mức xám tương ứng với một dải phổ khác nhau. Vì vậy, ảnh đa phổ 1000  1000, kênh 24 có thể được xem như tập một triệu vec tơ phần tử 24 ngẫu nhiên (chẳng hạn các điểm ảnh). Có thể áp dụng kỹ thuật giảm chiều Karhunen-Loeve vào tập các vec tơ này. vì sự tương quan giữa các dải phỏ khác nhau của mọt ảnh đa phổ thường khá cao, nên nhiều giá trị sinh 24 sẽ nhỏ. Nghĩa là ngăn xếp các ảnh dơn sắc 24 có thể được biểu diễn với sai số nhỏ chỉ nhờ vào một vài ảnh thành phần chính. Mỗi ảnh thành phần được tính như tổng trọng số 24 ban đầu. Hơn nữa, mỗi ảnh trong tạp ban đầu có thể được khôi phục, một cách xấp xỉ, như một phép kết hợp tuyến tính của một vài ảnh thành phần chính. Ví dụ, việc này làm đơn giản hoá việc lưu trữ và phân loại các ảnh nhận được từ vệ tinh Trái đất. Nói chung, các ảnh cơ sở của biến đổi Karhunen-Loeve hai chiều phụ thuộc vào tính chất thống kê của ảnh đặc trưng biến đổi và không thể viết ra một cách rõ ràng. Tuy nhiên, nếu ảnh là quá trình Markov bậc nhất, nơi mà tương quan giữa các điểm ảnh giảm tuyến tính theo khoảng cách tách biệt giữa chúng, thì các ảnh cơ sở đối với biến đổi K-L có thể được viết rõ ràng. Giả thiết Markov thường khớp các ảnh hay gặp rất tốt. Hơn nữa, khi tương quan giữa các điểm ảnh kiền kề nhau được tiếp cận theo cách duy nhất, thì các hàm K-L cơ sở tiếp cận những theo biến đổi cosin rời rạc. Vì thế, DCT, tính toán dễ dàng, xấp xỉ với biến đổi K-L đối với các ảnh thường hay gặp. 13.6.4. Biến đổi SVD Một ma trận A N  N bất kỳ có thể biểu diễn như sau A  UV t (62) Trong đó các cột của U và V là các vec tơ sinh của AA', và A'A và  là ma trận đường chéo N  N chứa các giá trị đơn nhất của A trên đường chéo của nó. Vì U và V là trực giao,   U t AV (63) Biểu thức (63) vì thế là xuôi và biểu thức (62) là ngược, của cặp biến đổi đơn vị. Biến đổi này được gọi là biến đổi phân tích giá trị đơn nhất (SVD). Nếu A đối xứng thì U = V. 240
Chú ý rằng, không giống những biến đổi đã đề cập trong những phần trước đây, các ma trận hạt nhân U và V phụ thuộc vào ảnh A đã biến đổi. Nói chung, ta phải tính các vec tơ sinh của AA' và A'A cho từng ảnh qua quá trình biến đổi. Cũng cần lưu ý là do  là ma trận đường chéo, nên các phần tử của nó hầu như là khác 0. Vì thế, chúng ta có nén không mất mát theo hệ số N, và nó sẽ lớn hơn nếu A có vài giá trị 0 (hay không đáng kể) đơn nhất. Do đó, sự tính toán thêm sẽ làm nén dữ liệu trong nó một cách đáng kể. Bình thường, vài giá trị đơn nhất đủ nhỏ để có thể bỏ qua với sai số nhỏ. Vì thế nén “mất mát” được thực hiện nhờ bỏ qua các giá trị  i,j nhỏ hơn. Sai số bình phương trung bình do quá trình cắt bớt đơn giản là tổng các giá trị đơn nhất bị bỏ qua. Nhìn bên ngoài khả năng nén kỳ diệu của biến đổi SVD có phần không đúng. Mặc dù toàn bộ ảnh có thể được nén thành các phần tử đường chéo , nhưng các ma trận hạt nhân U và V là ma trận đơn vị đối với ảnh được nén. Những ma trận này sẽ được truyền, theo ảnh, trước khi xảy ra sự tái tạo tại bên nhận. Tuy nhiên, có lẽ một cặp ma trận hạt nhân có thể đáp ứng (gần đúng) cho một nhóm các ảnh như nhau. Ví dụ cụ thể. Biến đổi SVD được minh hoạ trong hình 13-7, sử dụng một ảnh 5  5 đối xứng. HÌNH 13-7 Hình 13-7 Biến đổi SVD của một ảnh 5  5 đối xứng 13.7. LỌC TRONG MIỀN BIẾN ĐỔI Trong chương 10, chúng ta đã thấy rằng lọc tuyến tính-hoạt động của một hệ thống tuyến tính bất biến dịch-có thể được mô phỏng như phép nhân phổ Fourier của một ảnh với một hàm truyền đạt định nghĩa trong miên tần số (chẳng hạn biến đổi). Trong khi kết quả quan trọng này chỉ đúng đối với biến đổi Fourier, thì các phép toán lọc ảnh giống nhau cũng có thể được mô phỏng bằng các biến đổi khác. Giống như biến đổi Fourier, biến đổi đơn vị tổng quát mở rộng một ảnh như một tổng trọng số các ảnh cơ sở. Quá trình biến đổi xuôi xác định các hệ số trọng số, trong khi quá trình biến đổi ngược tập hợp ảnh từ sự khai triển các ảnh cơ sở. Lọc trong miền biến đổi bao hàm sự thay dổi các hệ số trọng số trước khi tái tạo ảnh thông qua biến đổi ngược. Đối với lọc tuyến tính, biến đổi là biến đổi Fourier, và sự thay đổi được thực hiện bằng cách nhân phổ với một hàm truyền đạt. Trong trường hợp lọc tổng quát hơn, ma trận hệ số bị thay đổi (bằng phép nhân hay phép toán khác) và biến đổi ngược sẽ tọ ra ảnh lọc. Rõ ràng, đó là tính chất của các vec tơ cơ sở (và của các ảnh cơ sở thu được) nhằm thực hiện các hành động khác nhau của các biến đổi khác nhau. Ví dụ, sự phá huỷ của nhiễu điều hoà xuất hiện rất dày đặc trong miền biến đổi của một biến đổi 241
điều hoà và vì thế dễ dàng loại bỏ bằng cách thiết lập các hệ số tương ứng về 0. Các biến đổi sóng chữ nhật không phù hợp cho lắm đối với vấn đề loại bỏ nhiễu này, vì sự nhiễu tạp sẽ không thể phân biệt với tín hiệu trong miền biến đổi của chúng. Nói chung, nếu các thành phần tín hiệu (mong muốn) hay các thành phần nhiễu (không mong muốn) của ảnh tập trung trên một hay một vài ảnh cơ sở của một biến đổi riêng biệt, thì biến đổi sẽ hữu ích trong việc tách rời ra làm hai. Đó là do các thành phần nói trên được thể hiện dày đặc trong miền biến đổi. Sự trình bày tổng quát cũng được áp dụng vào những vấn đề loại bỏ nhiễu và phát hiện tín hiệu. 13.7.1. Phát hiện biên, dòng và điểm Hình 13-8 minh hoạ khả năng phát hiện biên của biến đổi Haar trên một ảnh 8  8. Vì biến đổi có khả năng tách được nên một tính chất của ảnh là dòng ngang hay dọc hay biên tạo ra các phần tử khác 0 chỉ trên hàng đầu tiên và cột đầu tiên của ảnh biến đổi. HÌNH 13-8 Hình 13-8 Phát hiện biên trên ảnh 8  8 Trong biến đổi Haar, đặc trưng tạo ra gần N/2 phần tử khác 0. Vị trí của đặc trưng xác định phần tử nào (và bao nhiêu) khác 0. Trong các biến đổi khác, tất cả N phần tử của hàng đầu tiên và cột đầu tiên nói chung là khác 0. Hình 13-9 trình bày vài biến đổi khác nhau của một ảnh chứa một xung nhọn. Tất cả N2 phần tử của các biến đổi này đều khác 0, ngoại trừ những phần tử của biến đổi Haar chỉ có 2N phần tử khác 0. Ngoài ra, vị trí của các phần tử khác 0 được xác định bằng vị trí của xung nhọn. HÌNH 13-9 Hình 13-9 Các biến đổi trên ảnh chứa một xung: (a) DST; (b) DCT; (c) Hadamard; (d) Haar. Đầu vào là ma trận 8  8, mọi vị trí đều là 0 ngoại trừ phần tử 242
trên bên trái 13.7.2. Thiết kế bộ lọc Bởi vì nó có mối liên quan gần với các hệ thống tuyến tính bất biến dịch, nên biến đổi Fourier có một nền tảng phát triển vững chắc để sử dụng trong các ứng dụng lọc ảnh. Lý thuyết về các biến đổi khác không được hỗ trợ nhiều lắm và chúng được sử dụng chủ yếu dựa trên thực nghiệm. Hiểu rõ sự giống và khác nhau giữa các biến đổi này sẽ giúp ta tìm kiếm các giải pháp mang tính khả thi. 13.8. TỔNG KẾT NHỮNG ĐIỂM QUAN TRỌNG 1. Các hàng của một ma trận biến đổi N  N là tập các vec tơ trực chuẩn. 2. Một biến đổi tuyến tính đơn vị sẽ tạo ra một vec tơ N hệ số biến đổi, mỗi hệ số lại là một tích bên trong của vec tơ đầu vào với một trong các hàng của ma trận biến đổi. 3. Biến đổi ngược được thực hiện tương tự, bằng các tích bên trong của vec tơ hệ số biến đổi với các hàng của ma trận biến đổi ngược. 4. Cũng có thể coi biến đổi ngược như việc tạo thành tổng trọng số các vec tơ cơ sở, trong đó các hệ số là các trọng số. 5. Đối với biến đổi đơn vị tách được, đối xứng hai chiều, các ảnh cơ sở là tích bên ngoài của các hàng trong ma trận biến đổi. BÀI TẬP 1. Các giá trị sinh của một ảnh đa phổ kênh 8 là [6.1 168 0.08 13 64 214 1.2 0.2]. Sai số RMS sẽ là bao nhiêu nếu bạn phân tích thành phần chung với tỷ lệ nén dữ liệu là 2:1. 2. Thiết kế một mặt nạ lọc biến đổi Haar 8  8 để loại bỏ các cạnh ngang nhỏ ra khỏi ảnh. DỰ ÁN 1. Phát triển một chương trình thực hiện biến đổi cosin rời rạc và sử dụng chương trình để chứng minh quá trình lọc thông cao đối với tăng cường ảnh. 2. Phát triển một chương trình thực hiện biến đổi Hartley rời rạc và sử dụng chương trình để chứng minh quá trình lọc thông thấp đối với việc giảm nhiễu. 3. Phát triển một chương trình phân tích thành phần chính để giảm ảnh màu 24  24 xuống thành ảnh trắng đen 16  16. Trình bày các ảnh chứng minh và giải thích trên kết quả suy giảm. 4. Phát triển một chương trình thực hiện biến đổi nghiêng và sử dụng chương trình để chứng tỏ cho sự loại bỏ sắc thái tuyến tính. 5. Phát triển một chương trình thực hiện biến đổi Haar và sử dụng chương trình để đưa ra các biên của một ảnh. 243