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

227 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ì Txyxty N j jjii    hay 1 0 , (1) 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,                           2 1 2 1 cossin sincosy x x y   (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. xTy 1 (3) 228 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ì ITTTT tt  **vµ TT *t-1 (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 ITTTT tt  vµ TT t1- (5) Chú ý rằng phần tử i, j của TTt 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ì hay          1 0 2exp1 N i ik N ikjf N F  F = Wf (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)       N ikj N i ki  2exp 1 , (7) 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 229 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à  nmkiFG N i N k kim,n ,,, 1 0 1 0 ,      (8) 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      nkTmiTi,k,m,n cr ,, (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):    miTnkTFG r N i N k kinm ,, 1 0 1 0 ,,              (10) 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à      nkTmiTi,k,m,n ,, (11) Và biểu thức (8) có thể viết lại như sau     TFTGnkTFmiTG N k cki N i nm             hay 1 0 , 1 0 , ,, (12) 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à ttGTTGTTF **11   (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) 230 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à ttGTTF  (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 TGTFTFTG  vµ (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à kj N i ikij t TTITT , 1 0 ,, * *     hay (17) 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à 231  qjpiqpG  ,,  (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à        nqTmpTnkTmiTF N i N k qkpinm ,,,, 1 0 1 0 ,,              (19) 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à W              1,10,1 1,00,0 NNN N ww ww    (20) Trong đó N ikj ki eN w 2 , 1   (21) 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ổ, 232 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à              112/2 2/02 NiNf N iN Nif N i s N N i (23) 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                xfxfxjxf N uxjuuFxfuF x1exp2exp 00         (24) 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          yxfNvNuFyxfvuF yx ,12/,2/,,  (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. 233 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                           1 0 1 0 2 12cos 2 12cos,, N i N k c N nk N mikignmnmG  (27) Và biến đổi ngược của nó là                           1 0 1 0 2 12cos 2 12cos,, N m N n c N nk N minmGnmkig  (28) Trong đó các hệ số là     Nm N m N  1210 i víµ v  (29) 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 CgCG c  (30) Trong đó ma trận hạt nhân có các phần tử          N mimCi,m 1 12  cos (31) 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                           1 0 1 0 2 11sin 2 11sin, 1 2, N i N k s N nk N mikig N nmG  (32) Và                           1 0 1 0 2 11sin 2 11sin, 1 2, N m N n s N nk N minmG N kig  (33) DST có các phần tử ma trận hạt nhân           1 11sin 1 2 , N ki N T ki  (34) 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) 234            1 0 1 0 ,, 21 N i N k kinm knimN casg N G  (35) Và DHT ngược hai chiều            1 0 1 0 ,, 21 N m N n nmki knimN casG N g  (36) Là giống nhau và sử dụng hàm cơ sở        4/cos2sincos  cas (37) Là hàm cosin được dịch 450 sang phải             N ikcas N T ki 2 1 , (38) 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                vHvFvHvFvGxhxfxg oe  * (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. 235 Đối với trường hợp 2  2, ma trận hạt nhân sẽ là         11 11 2 1 2 1 2H (40) 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.        2/2/ 2/2/11 NN NN N HH HH N H N (41) Đố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à 5 2 6 1 4 3 7 0 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 22 1 8                                  H (42) 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