Tài liệu Nén ảnh trong thông tin số thế hệ sau (TT)

-1MỞ ĐẦU Tính cấp thiết của đề tài Hiện nay, với việc triển khai mạng thông tin thế hệ sau, nhiều ứng dụng mới ra đời như truyền tín hiệu video trên các phương tiện thông tin di động, đa môi trường. Nâng cao hiệu quả sử dụng tài nguyên băng tần của các phương tiện đó là bài toán phải nén tín hiệu video hiệu quả nhất. Vì vậy, đề tài này là một chủ đề cấp thiết cho việc ứng dụng truyền video trên các mạng viễn thông đa môi trường thế hệ mới. Mục tiêu nghiên cứu Tìm các thuật toán hợp lý để ước lượng chuyển động của ảnh trong video sao cho dễ tính toán, đảm bảo độ bám chuyển động của ảnh một cách tốt nhất. - Nghiên cứu đề xuất ứng dụng thuật toán ước lượng chuyển động trong không gian nhiều chiều với nghiệm ước lượng chuyển động tối ưu, độ bám tốt. - Tăng hiệu quả sử dụng băng tần truyền dẫn bằng các thuật toán không cần sử dụng tín hiệu đào tạo. - Thuật toán ước lượng làm việc ổn định trong điều kiện kênh có nhiễu. Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu Luận án nghiên cứu các phương pháp nén video số, ứng dụng truyền video trong mạng thông tin di động thế hệ mới. Đây là một phạm vi rộng, bao gồm: lượng tử hóa, ước lượng chuyển động của ảnh, mã hóa - giải mã. Luận án tập trung vào việc nghiên cứu các thuật toán ước lượng chuyển động của ảnh, phân tích các kết quả nghiên cứu chuyển động ảnh đã có trước đây; nghiên cứu các thuật toán ước lượng về mặt toán học từ đó tìm ra thuật toán ước lượng hợp lý để đạt mục tiêu đề ra. Từ phân tích toán học, luận án dùng công cụ mô phỏng để kiểm chứng. -2Ý nghĩa khoa học và thực tiễn của đề tài Ý nghĩa khoa học: Làm phong phú hơn về lý luận ước lượng chuyển động của ảnh bằng thuật toán lặp, đó là: - Dùng thuật toán Kalman: Đây là phương pháp lặp, sử dụng trong không gian nhiều chiều và chỉ ra nghiệm tối ưu của ước lượng chuyển động. - Dùng thuật toán mù: Đây là phương pháp lặp, không cần sử dụng tham chiếu trước mà chỉ cần mối tương quan giữa hai khung ảnh là ước lượng được chuyển động của ảnh. Ý nghĩa thực tiễn: Mở ra khả năng tính toán mới để ước lượng ảnh nhanh hơn, có độ bám chuyển động tốt hơn, tránh được những thông tin dư thừa do độ bám chuyển động không tốt gây ra. Nội dung của luận án Mở đầu: Giới thiệu bài toán và phương pháp nghiên cứu. Chương 1 - Tổng quan về nén video: Giới thiệu vai trò, vị trí, yêu cầu, mô hình hệ thống và một số kỹ thuật nén video. Chương 2 - Tổng quan về ước lượng chuyển động của ảnh: Đây là chương đưa ra những kiến thức cơ bản về ước lượng chuyển động của ảnh, những thuật toán hiện có, đánh giá ưu điểm và nhược điểm của những thuật toán hiện có. Chương 3 - Ước lượng chuyển động bằng các giải pháp mới: Đề xuất áp dụng những thuật toán mới cho việc ước lượng chuyển động của ảnh, đó là thuật toán Kalman và thuật toán mù. Chương 4 - Một số kết quả tính toán số: Trình bày một số kết quả mô phỏng từ đó đưa ra nhận xét, so sánh hiệu năng giữa phương pháp Bayes và phương pháp Kalman. Kết luận và kiến nghị: Nêu lên các kết quả đã đạt được của luận án và chỉ ra các hướng nghiên cứu tiếp theo. -3CHƢƠNG 1 TỔNG QUAN VỀ NÉN VIDEO 1.1. Giới thiệu Để truyền được các chương trình video trên các hệ thống thông tin di động, một bài toán đặt ra là phải nén hình ảnh để tiết kiệm băng tần truyền dẫn mà vẫn đảm bảo chất lượng hình ảnh. Trong hoàn cảnh mạng NGN và di động thế hệ sau tiếp tục đòi hỏi phải hoàn thiện hơn các thuật toán nén - giải nén tín hiệu video với mục đích làm cho chất lượng hình ảnh tốt hơn, sử dụng băng tần truyền dẫn hiệu quả hơn. 1.2. Độ dƣ trong tín hiệu video, nhu cầu cần thiết nén video 1.2.1. Độ dƣ trong tín hiệu video Mục này trình bày về độ dư trong tín hiệu video, gồm: Độ dư thống kê của ảnh (độ dư không gian, độ dư thời gian, độ dư mã) và độ dư khả năng nhìn thấy. Việc nhận biết độ dư trong tín hiệu video và tìm kiếm giải pháp để loại bỏ độ dư đó chính là nén dữ liệu. 1.2.2. Nhu cầu cần thiết nén video Những thành tựu đạt được trong công nghệ điện tử - viễn thông tin học đã tạo điều kiện phát triển các kỹ thuật truyền video đáp ứng nhu cầu ngày càng tăng trong các ứng dụng cuộc sống hàng ngày như điện thoại video, hội nghị video, truyền hình độ phân giải cao… Để làm được điều đó, cần thiết phải nén video. 1.3. Khái niệm về nén video Mục này trình bày khái quát về: Khái niệm về nén video, mô hình, chức năng cơ bản, đặc điểm của các phần tử trong hệ thống nén video. Hình 1.5 chỉ ra mô hình nén video tổng quát. 1.4. Yêu cầu về ứng dụng nén video, một số kỹ thuật nén video 1.4.1. Yêu cầu về ứng dụng nén video Mục này trình bày một số yêu cầu về ứng dụng nén video, gồm: Các đặc tính video, yêu cầu truyền dẫn, các đặc tính và hiệu năng của hệ thống nén, yêu cầu về tỷ lệ méo và yêu cầu về tiêu chuẩn. -4- Ik + Lỗi dự đoán E k Bộ toán tử không gian (T) - Bộ mã hóa độ dài biến đổi (VLC) Bộ lượng tử (Q) Dự đoán Pk Bộ lượng tử nghịch đảo -1 (Q ) Ngoài khung-Mở Trong khung-Đóng ^ I^k-m và Ek-n Nén chuyển động Bộ nhớ khung trễ Ik Ước lượng chuyển động Bộ toán tử không gian đảo (T -1 ) Các véctơ chuyển động Ike hoặc Eke Chuyển khối con ngoài khung được mã hóa hoặc Lỗi dự đoán trong khung được mã hóa và Véctơ chuyển động Bộ mã hóa độ dài biến đổi (VLC) MVk Hình 1.5 Hệ thống nén video tổng quát 1.4.2. Một số kỹ thuật nén video Mục này trình bày một số kỹ thuật nén video cơ bản, bao gồm: - Mã entropy và mã dự đoán: Là mã tiếp cận entropy của nguồn; DPCM sử dụng mô hình nguồn Markov được dùng trong các chuẩn MPEG-1 và H.261. Tuy nhiên, bộ mã hoá này tương đối phức tạp; VLC được dùng kết hợp với DPCM để giảm tốc độ bit. - Mã chuyển đổi khối bằng biến đổi DCT: Gói hầu hết năng lượng tín hiệu gốc vào một số ít các hệ số biến đổi, bỏ qua hệ số chứa ít hoặc không chứa năng lượng. Có ưu điểm là IDCT không tạo ra bất kỳ sự gián đoạn rõ nét nào ở các rìa khối; các biến đổi rời rạc tạo nên tín hiệu được tái cấu trúc có chu kỳ; nhược điểm là tính toán chủ yếu trên giải tích cổ điển, khá phức tạp. - Bù và ước lượng chuyển động: Dựa vào nền tĩnh và sự chuyển động của các ảnh gần. Nếu nền không thay đổi giữa hai khung thì hiệu của chúng bằng 0 và hai khung có thể được mã hoá thành một. Các vật thể chuyển động có thể được phát hiện bằng cách phối hợp vật thể cận cảnh giữa hai khung -5CHƢƠNG 2 TỔNG QUAN VỀ ƢỚC LƢỢNG CHUYỂN ĐỘNG CỦA ẢNH 2.1. Giới thiệu Ước lượng chuyển động là quá trình quan trọng trong việc mô tả, phân tích dãy ảnh, bám mục tiêu và mã hóa video. Việc mô tả và ứng dụng có những yêu cầu khác nhau, do đó phải sử dụng các phương pháp ước lượng chuyển động khác nhau. Chương 2 của luận án tập trung vào việc nghiên cứu các phương pháp ước lượng chuyển động video và so sánh các phương pháp đó, từ đó định hướng cho các giải pháp mới được đề xuất ở chương 3 của luận án. 2.2. Ƣớc lƣợng chuyển động và các phƣơng pháp ƣớc lƣợng chuyển động 2.2.1. Ƣớc lƣợng chuyển động Ước lượng chuyển động là một bộ phận cấu thành trong bài toán mã hoá nén video. Trong ước lượng chuyển động, điểm s=[h, v]T trong khung hiện tại ở thời điểm t sẽ liên quan đến một điểm trong khung tham chiếu trước đó ở thời điểm t-t: f t (s)  ft t (s  x(s)) (2.1) Mục đích của ước lượng chuyển động là đi tìm véctơ chuyển động x(s)=[xh(s), xv(s)]T. Chú ý rằng x(s) không nhất thiết phải là véctơ chuyển động toàn điểm. Như vậy, phương pháp ước lượng chuyển động có thể cần phải truy cập các giá trị cường độ tại các vị trí không lấy mẫu trong khung tham chiếu. Phương pháp nội suy song tuyến tính thường được sử dụng vì nó dung hòa tốt giữa chất lượng nội suy và độ phức tạp tính toán [47]. Nó được định nghĩa như sau: f (h, v)  (1  h f )(1  v f ) f (hi , vi )  h f (1  v f ) f (hi  1, vi ) (2.3)  (1  h f )v f f (hi , vi  1)  h f v f f (hi  1, vi  1) trong đó (hi,vi) và (hf,vf) tương ứng là các phần nguyên và phần phân của các tọa độ điểm (h,v). -6Các mô hình tất định và xác suất Trong mô hình tất định, chuyển động được xem là một đại lượng tất định chưa biết. Bằng cách cực đại xác suất của dãy video quan sát được theo sự chuyển động chưa biết có thể ước lượng được đại lượng tất định này. Công thức ước lượng tương ứng thường được xem là bài toán ML. Trong mô hình xác suất, chuyển động được xem là một biến ngẫu nhiên. Tập các véctơ chuyển động tạo thành trường ngẫu nhiên. Trường này thường được mô hình hoá bằng trường ngẫu nhiên Markov (MRF). Việc ước lượng chuyển động có thể được công thức hoá bằng bài toán MAP. Các mô hình tham số và phi tham số Trong mô hình tham số, chuyển động được biểu thị bằng một tập các tham số chuyển động. Như vậy, bài toán ước lượng chuyển động trở thành bài toán ước lượng các tham số chuyển động. Với mô hình tham số, ràng buộc để làm theo đúng quy tắc bài toán ước lượng chuyển động giả định sai được đưa vào trong mô hình chuyển động một cách đầy đủ. Trong mô hình phi tham số, sự ràng buộc rõ ràng (ví dụ: tính trơn tru của trường chuyển động) được đưa vào để làm theo đúng quy tắc bài toán giả định sai về ước lượng chuyển động. Vùng hỗ trợ Vùng hỗ trợ là một tập các điểm mà mô hình chuyển động áp dụng. Vùng hỗ trợ có thể lớn như một khung hoặc nhỏ như một điểm, có thể có kích thước cố định hoặc thay đổi và có thể có hình dạng cân đối hoặc hình dạng tùy ý. 2.2.2. Các phƣơng pháp ƣớc lƣợng chuyển động Mục này giới thiệu một số phương pháp ước lượng chuyển động thường được sử dụng, đưa ra nhận xét những ưu điểm và nhược điểm của từng phương pháp, bao gồm: - Các phương pháp vi phân: Dựa vào mối quan hệ giữa các biến đổi về không gian và thời gian của cường độ. Các phương pháp này chấp nhận một số giả thiết hạn chế là véctơ chuyển động x phải nhỏ, -7trái lại thì nghiệm của bài toán sẽ kém chính xác và nhạy cảm đối với nhiễu. - Các phương pháp hồi quy điểm: Dựa vào sự tối thiểu theo gradient lặp đi lặp lại của lỗi dự đoán. Ước lượng phụ thuộc nhiều vào gradient không gian. Các phương pháp này phải chọn cỡ bước điều khiển phù hợp để dung hoà giữa tốc độ hội tụ và độ chính xác ước lượng. Có thể dễ hội tụ đến các điểm tối ưu cục bộ trong bề mặt lỗi. Vùng có cường độ ít thay đổi, các gián đoạn trong trường chuyển động và những dịch chuyển lớn là không thể xử lý hiệu quả. - Các phương pháp miền tần số: Dựa trên thuộc tính khai triển Fourier, khi dịch chuyển tịnh tiến trong miền không gian tương ứng với dịch pha tuyến tính trong miền tần số. Phương pháp tương quan pha có một số tính chất đặc biệt: Độ phức tạp tính toán nhỏ, đặc biệt khi sử dụng FFT; không nhạy cảm với những thay đổi độ sáng. - Các phương pháp phối hợp khối: Dựa vào việc chia khung ảnh thành các khối con và ước lượng chuyển động cho từng khối. Tuỳ vào việc lựa chọn hàm phối hợp (như NCCF, SSD, SAD) mà có hiệu quả khác nhau. So sánh về chất lượng dự đoán thì: SSD  SAD  NCCF. So sánh về độ phức tạp tính toán thì SAD có độ phức tạp tính toán thấp nhất bởi vì nó không đòi hỏi có phép nhân. - Các phương pháp lặp truyền thống: Đều thuộc họ thuật toán độ dốc, dựa trên toán tử gradient do đó vẫn còn hạn chế là tốc độ hội tụ chậm, độ bám thay đổi của hình ảnh không cao; độ ổn định không cao và vẫn cần có giá trị tham chiếu để so sánh. -8CHƢƠNG 3 ƢỚC LƢỢNG CHUYỂN ĐỘNG BẰNG CÁC GIẢI PHÁP MỚI 3.1. Giới thiệu Trong chương 3, luận án đề xuất những giải pháp ước lượng mới và được phân ra thành hai loại chính là: - Ước lượng chuyển động của ảnh bằng thuật toán Kalman: Mục tiêu đạt được là sử dụng ưu thế của thuật toán Kalman là lặp và có độ bám chuyển động tốt hơn so với các phương pháp gradient đồng thời phát huy được ưu thế của thuật toán Bayes là xét đặc điểm tự nhiên của dãy ảnh. - Ước lượng chuyển động của ảnh bằng các thuật toán mù: Mục tiêu đạt được là giải quyết bài toán không cần các thông tin huấn luyện thuật toán như đòi hỏi trong các phương pháp gradient nhằm nâng cao độ sử dụng băng tần truyền dẫn và mở rộng cho trường hợp nhiễu loạn bất kỳ. 3.2. Ƣớc lƣợng chuyển động bằng Kalman 3.2.1. Đặt bài toán Trong [4] đã giả thiết: z biểu diễn khung của một dãy ảnh tại thời điểm t. Trường chuyển động x1 biểu thị độ lệch giữa z1 và z2 cho mỗi pixel tại các thời điểm t1, t2 tương ứng. Trường phân vùng z bao gồm một số nhãn tại mọi pixel, mỗi nhãn biểu thị một mục tiêu chuyển động: xn  n (n  1, 2,..., N ) cho mỗi vị trí của pixel trên lưới ; N là tổng số mục tiêu chuyển động. Mục tiêu bài toán là ước lượng sự chuyển động x với các giá trị z đã cho [10], [29]. Trong nghiên cứu này, luận án giả thiết: a) Tập các giá trị đo z1 , z2 ,..., zk ký hiệu bằng véctơ z là các giá trị biết trước. b) Mối quan hệ vật lý giữa trạng thái tự nhiên sẽ được ước lượng và các giá trị đo được biểu thị bằng quan hệ: (3.1) z  g (x, v) Thực tế mối quan hệ giữa z và độ dịch chuyển x là tuyến tính: -9(3.2) z  Hx  v trong đó z là véctơ đo (k×1), x là véctơ trạng thái (n×1) và v là véctơ nhiễu (q×1). c) Hàm mật độ phân bố xác suất đồng thời p(x,v) và hàm mật độ biên tương ứng p(x,) và p(v). d) Hàm mật độ xác suất của nhiễu và trạng thái là độc lập: (3.3) p(x, v)  p(x) p( v) p(x) là Gauss với E (x)  xˆ  (3.4)  Cov(x)  P0  p( v) là Gauss với E ( v)  0   Cov( v)  R  (3.5) 3.2.2. Ƣớc lƣợng chuyển động của ảnh bằng thuật toán Kalman 1- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán Kalman một bƣớc Trước đây, hầu hết các công trình đánh giá chuyển động, người ta thường sử dụng luật Bayes để ước lượng véctơ trạng thái chuyển động x. Việc giải quyết bài toán này trở nên rất khó khăn khi số trạng thái tăng lên, và mối quan hệ giữa chúng là phi tuyến. Để giải quyết vấn đề này, nghiên cứu sinh xuất phát từ suy nghĩ kế thừa được điểm mạnh của phương pháp Bayes là xét được bản chất của nội dung ảnh và tìm cách hạn chế nhược điểm của phương pháp Bayes là tốc độ hội tụ chậm, độ bám chuyển động của ảnh không cao để đưa ra giải pháp sử dụng thuật toán Kalman trong ước lượng trạng thái chuyển động x. Dựa vào định luật Bayes, thực hiện các bước tính như sau [25]: 1) Tính p(z) theo (3.6) 2) Tính p(x,z) theo (3.7) và p ( z x) theo (3.8) 3) Tính p ( x z ) : Sử dụng một số phép biến đổi toán học, p ( x z ) được tính như sau: -10- p(x z )  HP0 HT  R  2  n2 P0 12 12 R 12 (3.11)  exp{1 2(x  xˆ )T P 1 (x  xˆ )} (3.13) P  P0  P0 HT (HP0 HT  R)1 HP0 ˆx  x  PHT R 1 (z  Hxˆ ) (3.14) E[x]  x 4) Vì p ( x z ) là Gauss, ước lượng trung bình có điều kiện và ước lượng minimax đều trùng nhau và được tính bởi x̂ . Từ định luật Bayes, bằng một số biến đổi đơn giản ta đã nhận được phương pháp lặp (3.14). Trong (3.14) chỉ đúng khi xét ảnh chuyển từ trạng thái t-1 sang t, nghĩa là chuyển một bước. 2- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán Kalman nhiều bƣớc Giải quyết bài toán ước lượng chuyển động ảnh qua nhiều bước cũng tương tự như bài toán ước lượng chuyển động ảnh một bước, chỉ khác là trạng thái thay đổi từ trạng thái này sang trạng thái khác theo mối quan hệ động. Nếu coi giá trị cần tính của trạng thái ảnh tại thời điểm thứ k+1 là xk+1 khi đã tính được giá trị trước đó là xk, mối quan hệ đó được biểu thị bằng một cặp phương trình [25]: xk 1  f (xk , w k )  (3.15)  z k 1  h(xk 1 , v k 1 )  ở đây xk+1 là véctơ trạng thái ảnh tại thời điểm k+1, vk+1 là nhiễu đo tại thời điểm k+1, zk+1 là giá trị đo có được tại thời điểm k+1, wk là véctơ nhiễu tại thời điểm k. Tập giá trị đo Zk+1 = (z1,…,zk+1). Hàm mật độ xác suất p(x k z1 ,..., z k )  p(x k Z k ) và p ( w k , v k 1 x k ) đại diện cho các thành phần nhiễu phụ thuộc vào xk. Bài toán đặt ra là ước lượng trạng thái ảnh xk+1 dựa vào các đại lượng đo z1,…,zk+1. Xuất phát từ luật Bayes và trình tự tính như được nêu trong phần 1 mục 3.2.2 ta có [25]: -111) Tính p(x k 1 x k ) : Có thể đạt được qua thí nghiệm hoặc theo phép giải tích khi biết p ( w k , v k 1 x k ) , p ( x k Z k ) và (3.15). 2) Tính p(z k 1 x k , x k 1 ) : Suy ra từ p ( w k , v k 1 x k ) và (3.15). 3) Tính p(x k 1 , z k 1 Z k ) theo (3.16) từ đó có thể trực tiếp tính được hàm mật độ biên p (x k 1 Z k ) và p (z k 1 Z k ) . 4) Tính p (x k 1 Z k 1 ) theo (3.18) 5) Ước lượng xk+1 từ p (x k 1 Z k 1 ) đã tính ở (3.18) giống hệt như được nêu tại phần 1 mục 3.2.2. Sử dụng thuật toán Kalman, với mô hình vật lý trạng thái ảnh theo (3.19)-(3.21), bằng một số phép biến đổi toán học ta có: p(x k 1 Z k 1 )  HM k 1HT  R  2  n2 R 12 12 M k 1 12 (3.27)  exp{1 2(x k 1  xˆ k 1 )T Pk11 (x k 1  xˆ k 1 )} xˆ k 1  xˆ k  M k 1HT (HM k 1HT  R)1 (z k 1  Hxˆ k ) (3.28) (3.30) Pk 1  Mk 1  M k 1HT (HM k 1HT  R)1 HM k 1 T T (3.31) Mk 1  Pk   Q Như vậy từ bài toán ước lượng trạng thái chuyển động của ảnh trực tiếp bằng luật Bayes, luận án đã chuyển sang tính bằng thuật toán Kalman rất thuận lợi vì là phương pháp lặp nên dễ thực hiện bằng các bộ xử lý số; đồng thời do chuyển sang dạng các phương trình trạng thái, giải bằng thuật toán Kalman nên tốc độ hội tụ, độ bám chuyển động ảnh tốt hơn. Nhận xét: Ước lượng chuyển động của ảnh là một vấn đề rất quan trọng nhằm loại bỏ các thông tin thừa trong chuyển động ảnh, làm cho hiệu quả nén ảnh tốt hơn. Các giải pháp từ trước tới nay người ta thường dùng ước lượng trên cơ sở luật Bayes và tính toán trực tiếp theo các phân bố xác suất có điều kiện của nó. Đây là một bài toán giải rất khó khi số biến tăng lên đặc biệt khi cần nén ảnh màu, ảnh 3 chiều. Để giải quyết bài toán đó, chúng tôi đã kế tục luật Bayes và biến nó sang dạng đại số, sử dụng phương pháp lặp trên cơ sở thuật -12toán Kalman vừa giảm được độ phức tạp tính toán, vừa tăng tốc độ tính toán và độ bám quĩ đạo chuyển động của ảnh theo các ưu điểm của thuật toán Kalman. 3.3. Ƣớc lƣợng chuyển động tối ƣu của ảnh trong video 3.3.1. Đặt bài toán Trong mục 3.2, từ ước lượng chuyển động ảnh bằng Bayes, luận án đã đưa ra giải pháp dùng thuật toán lặp Kalman để ước lượng chuyển động của ảnh trong video nhằm hạn chế nhược điểm của phương pháp Bayes nhưng vẫn giữ được bản chất nội dung chuyển động của ảnh. Từ đây xuất hiện bài toán tìm ước lượng tốt nhất của chuyển động ảnh xˆ k tại thời điểm tk . Ở đây luận án sử dụng thuật toán Kalman để ước lượng chuyển động tối ưu của dãy ảnh sao cho sai số trung bình bình phương trong ước lượng chuyển động của dãy ảnh là bé nhất. 3.3.2. Ƣớc lƣợng chuyển động tối ƣu của ảnh trong video Luận án ứng dụng thuật toán đã nêu tại mục 3.2 vào trường hợp khi chuyển động của ảnh được đặc trưng bằng phương trình sai phân tuyến tính đồng nhất [25]: xk   k ,k 1xk 1 (3.32) Khi có ước lượng xˆ k 1 tại thời điểm tk 1 , có thể dự đoán ước lượng chuyển động của ảnh tại thời điểm tk là xˆ k   k ,k 1xˆ k 1 . Giá trị đo z k tại thời điểm tk có thể được sử dụng để cải tiến ước lượng này. Trên cơ sở xˆ k và giá trị đo z k : z k  H k xk  v k (3.33) Khi E[ v k ]  0 thì giá trị đo trung bình tại thời điểm tk là H k xˆ k . Sai số trong ước lượng được phản ảnh bằng sai số theo giá trị đo kỳ vọng ek  z k  Hk k ,k 1xˆ k 1 . Ước lượng là một hàm tuyến tính của các giá trị đo mới. Ở đây ta phải xác định một ma trận chưa biết K k sao cho ước lượng xˆ k được cho bởi: xˆ k   k ,k 1xˆ k 1  K k [z k  H k  k ,k 1xˆ k 1 ] (3.34) Bài toán đặt ra ở đây là phải xác định ma trận K k sao cho: -13(3.35) E[(xˆ k  xk )T (xˆ k  xk )] là bé nhất và khi đó giá trị xˆ k được gọi là tốt nhất theo nghĩa sai số trung bình bình phương bé nhất. Ma trận K k này còn được gọi là ma trận trọng số hoặc ma trận độ lợi. Với một số giả thiết, sử dụng các phép biến đổi toán học ta có: (3.37) Pk k ,k 1Pk 1Tk ,k 1 T T 1   (3.42) K k  Pk H k [H k Pk H k  R k ] Pk  Pk  K k H k Pk (3.43) Các phương trình (3.34), (3.37), (3.42) và (3.43) chính là các giá trị ước lượng chuyển động của ảnh tối ưu theo giải pháp lọc Kalman. Nhận xét: Với việc sử dụng lọc Kalman để ước lượng chuyển động của ảnh, chúng ta đã đưa việc giải một bài toán xác suất theo luật Bayes khó khăn về việc giải bằng phương pháp lặp. Ở đây còn chỉ ra được nghiệm để đảm bảo sai số trung bình bình phương là bé nhất. Đồng thời luận án cũng chỉ ra được việc chọn độ lợi K k tối ưu trong thuật toán Kalman để ước lượng chuyển động ảnh nhằm đảm bảo nghiệm là tốt nhất. 3.4. Ƣớc lƣợng chuyển động của ảnh bằng phƣơng pháp mù 3.4.1. Đặt bài toán Tuy phương pháp Kalman đem lại hiệu quả rất tốt trong ước lượng chuyển động của ảnh do độ bám tốt nhưng có những điều kiện ràng buộc mà nội thân thuật toán Kalman đòi hỏi là hàm mật độ xác suất của h, v, d là Gauss. Trong thực tế, những điều kiện ràng buộc đó là khá chặt. Ngoài ra, chúng ta cũng biết rằng thuật toán mù có một số đặc điểm: - Khi kênh có can nhiễu đủ mạnh hoặc các tham số kênh biến đổi nhanh, lúc đó nếu dùng các dãy đào tạo từ bên phát truyền đến bên thu thì sẽ bị sai lệch và làm cho quá trình đào tạo không còn chính xác và hiệu quả. - Nếu phải dùng các thuật toán có đào tạo thì nó sẽ chiếm dụng một phần kênh truyền dẫn, làm giảm hiệu suất sử dụng của kênh. -14- Trong hệ thống đa truy nhập, di động, quá trình đào tạo cần đồng bộ hoặc cần gửi các tập đào tạo theo từng thời điểm kết nối mới và phải cài đặt lại đồng bộ. Đây là điều khó thực hiện được. Để khắc phục hạn chế đó và không cần các mẫu đào tạo trong tính toán của thuật toán, luận án đưa ra giải pháp mù. 3.4.2. Ƣớc lƣợng chuyển động của ảnh bằng phƣơng pháp mù 1- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán kỳ vọng hợp lý max.max Trong [10] hoặc [29] thì điều kiện ràng buộc đối với ma trận H là H(x * )  0 . Đây là điều kiện ràng buộc chặt mà không phải các hệ thống thực bao giờ cũng đúng. Để khắc phục điều đó, luận án sẽ sử dụng một số biến đổi phụ để đưa hệ thống phương trình tuyến tính như đã nói ở mục 2.2.2 về dạng: (3.44) Hx  v  z hoaëc Hx  z  v m×n m trong đó H=[hij]IR là mô hình ma trận, zIR là véctơ đo chuyển động của ảnh, vIRm là véctơ sai số đo, xIRn là véctơ chuyển động của ảnh cần ước lượng. Trong mục 2.2.2, luận án đã tìm véctơ x sao cho (2.33) là bé nhất. Ở mục này, lựa chọn của nghiên cứu sinh là đi tìm véctơ x sao cho tối thiểu hàm mục tiêu: (3.45) J p (x)  z - Hx p  v(x) p , p 1 trong đó véctơ sai số đo v có dạng: T (3.46) v(x)  v1 (x), v2 (x),..., vm (x) với các thành phần của v được biểu thị: n vi (x)  zi  hTi x  zi   hij x j , (i  1, 2,..., m) (3.47) j 1 Với một vài giả thiết, sử dụng các phép biến đổi toán học từ (3.48) đến (3.56), thuật toán kỳ vọng hợp lý max.max có dạng: x j (k ) m z x j (k  1)  m  hij T i , ( j  1, 2,..., n) (3.57)  i hij i 1 hi x(k ) Nhận xét: Với bài toán ước lượng chuyển động của ảnh bằng thuật toán kỳ vọng hợp lý max.max đã giúp chúng ta vượt qua được -15khó khăn là các phần tử của ma trận H không nhất thiết phải dương và không cần tính giá trị đào tạo trong thuật toán lặp. 2- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán kỳ dị Tikhonov Đặt bài toán là phải ước lượng chuyển động của ảnh x khi có nhiễu tác động vào véctơ kết quả đo chuyển động z và các thành phần của ma trận H. Trong hoàn cảnh này, nghiệm của bài toán đã giải ở phần 1 mục 3.4.2 bây giờ sẽ bị sai lệch nhiều và thường không có giá trị. Để làm giảm bớt ảnh hưởng đó, phần này của luận án sẽ sử dụng giải pháp ước lượng mù của Tikhonov [57]. Theo lý thuyết kỳ dị thì hàm năng lượng kỳ dị (hàm sẽ được cực tiểu) là tổng trọng số của hai thành phần: J (x, )  J d (x)   J x (x) (3.58) trong đó Jd là năng lượng số liệu và Jx là ràng buộc làm trơn (còn được gọi là năng lượng của bộ ổn định). Khi (3.58) có dạng biểu diễn thống kê Bayes (x)  exp J x (x) thì phân bố có điều kiện của x và z có thể viết dưới dạng [57]: (3.60) p(z, x)  c exp J d (x)   J x (x) Do đó, tiêu chí cực đại phân bố tiên nghiệm p(x z) của ảnh x tương đương với cực tiểu hàm mục tiêu J(x,). Từ hàm mục tiêu trên, để giải quyết bài toán suy biến, chọn p = 2 trong (3.45), ta có: 1 1 2 T J (x)  z  Hx 2   z  Hx   z  Hx  2 2 (3.61) 1 T 1m 2  v v   vi 2 2 i 1 n vi (x)  zi  hTi x  zi   hij x j j 1 (3.62) Hàm mục tiêu đạt cực tiểu toàn bộ khi gradient của nó bằng 0: (3.63) J (x)  HT  z  Hx   0 T 1 T Do đó x*  (H H) H z . Từ (3.61), nghiệm kỳ dị có thể được xác định đơn giản bằng nghiệm của bài toán sau: -16x( )  arg minn J (x, ) (3.64) xIR   1 2 2 (3.65) z  Hx 2   x 2 ,   0 2 Ở đây tham số suy biến  điều khiển làm trơn nghiệm kỳ dị. Sử dụng phương pháp gradient dốc nhất ta thu được một hệ thống phương trình vi phân [57]: dx (3.66)    HT  z  Hx    x  dt Chú ý rằng việc cực tiểu hàm năng lượng J(x,) trong (3.65) theo x tương đương với việc giải phương trình: (3.67) (HT H   I)x  HT z Có thể sử dụng lý thuyết khai triển kỳ dị (SVD) để giải phương trình (3.67). Giả thiết ma trận H , cấp m  n có hạng n (m  n) , có khai triển kỳ dị như sau: n (3.69) H  U VT    i ui vTi i 1 trong đó cả U  [u1 , u2 ,..., u m ]  IR mm và V  [ v1 , v 2 ,..., v n ]  IR nn là các ma trận trực giao và  là ma trận giả đường chéo m  n với n hàng trên cùng chứa đường chéo diag{ 1 , 2 ,..., n } với  1   2  ...   n và (m  n) hàng phía dưới bằng 0. Có thể chỉ ra rằng nếu {ui } và {v i } tương ứng là các cột của U và V, thì nghiệm suy biến Tikhonov cực tiểu tiêu chuẩn bình phương bé nhất đối với phương trình (3.67) được xấp xỉ bằng [57]: n n 2 uT z i x* ( )   2 i  i  v i    vi (3.70) i 1    i 1      i i i i J (x, )  trong đó i  uTi z và   0 là tham số kỳ dị. Một phương pháp khác để giải quyết bài toán kỳ dị (3.61) gọi là phương pháp khai triển kỳ dị cắt cụt, trong đó người ta bỏ qua các giá trị suy biến nhỏ nhất bằng cách cắt bỏ những thành phần trong tổng của (3.70) ứng với r  n. Nhận xét: Phương pháp kỳ dị Tikhonov liên quan chặt chẽ với ước lượng Bayes. Trong phương pháp này, thống kê bậc hai của tập -17quan sát được sử dụng để tạo nên mô hình thông tin tiên nghiệm cho giải pháp kỳ dị. Phương pháp này giải quyết được khó khăn như đã nói về ước lượng Bayes. 3- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán Kaczmarz và thuật toán Kaczmarz mở rộng Bài toán đặt ra là khi véctơ kết quả đo chuyển động của ảnh z và các thành phần của ma trận H đều bị ảnh hưởng bởi nhiễu thì sẽ giải quyết ra sao. Phần này của luận án sẽ trả lời câu hỏi đó. Giả thiết trong quá trình ước lượng chuyển động của ảnh, nhiễu N tác động vào các thành phần của ma trận số liệu đặc trưng bằng ma trận H và véctơ kết quả đo chuyển động của ảnh z có sai số n. Khi đó, phương trình hệ thống có dạng: (3.82)  H®óng  N  x  z®óng  n  z trong đó Hđúng là ma trận số liệu khi không có nhiễu. zđúng là véctơ kết quả đo chuyển động của ảnh khi không có sai số. Hãy xác định nghiệm x của mô hình (3.82) trong trường hợp: - Nhiễu Gauss có trung bình bằng 0. - Nhiễu là bất kỳ. Để giải bài toán này, luận án chọn giải pháp tìm x sao cho cực tiểu đại lượng:  H trong đó 1     2 F  (1   ) z 2 F (3.83)  , H và z tương ứng là nhiễu loạn của ma  2 n 2 N trận H và véctơ z. Khảo sát hàm mục tiêu sai số trung bình bình phương chuẩn: (3.84) J (x)  E{eT (k )e(k )} trong đó véctơ sai số e được xác định theo công thức sau: (3.85) e(k )  z  Hx(k )  (z ®óng  n)  (H®óng  N)x(k ) với Hđúng và zđúng là các tham số đúng chưa biết. Hàm mục tiêu (3.84) cũng có thể được tính như trong (3.86). Việc cực tiểu hàm mục tiêu -18- J (x) theo x sẽ cho ta nghiệm chệch vì các thành phần nhiễu là các hàm của x. Để tránh vấn đề này, luận án sử dụng hàm mục tiêu sai số trung bình bình phương cải tiến để tạo nên ước lượng không chệch trên cơ sở bài toán tổng bình phương bé nhất (TLS) theo (3.87) [57]. Để đưa ra thuật toán thích nghi lặp, luận án biểu diễn hàm mục tiêu như sau: m J ( x )   J i ( x) trong đó J i (x)  E{ 2 (k )}  i 1 2 i (3.88) 1 E{e (k )} và ei  zi  hTi x ( hTi là hàng 2  +xT x thứ i của H). Khi đó các thành phần gradient tức thời có thể được tính theo (3.89). Do đó, thuật toán lặp thời gian rời rạc lợi dụng phương pháp gradient dốc nhất có thể được viết dưới dạng: x(k  1)  x(k )   (k )ei ( k )[h i +ei ( k ) x( k )] i  k modulo ( m  1) ei (k )  zi  hTi x  k  ei (k )    xT (k )x(k )   xT (k )x(k ) (3.90) (3.91) Vì thành phần (   xT (k )x(k ))1 luôn luôn dương, do đó có thể đưa (3.90) về dạng đơn giản hơn: x(k  1)  x(k )   (k )ei ( k )[h i +ei ( k ) x( k )] (3.92) i  k modulo ( m  1) Kaczmarz đã sử dụng khái niệm trung bình khối đối với tất cả các chỉ số i trong một chu trình lặp để đưa ra một thuật toán lặp mới và luận án đã sử dụng nó để ước lượng chuyển động của ảnh:  zi  hTi x(k )  zi  hTi x(k ) h  x(k )  (3.93)  i 2 T n i 1  j 1 r h   x ( k ) x( k ) j ij   m x(k  1)  x(k )   (k )  trong đó 0   (k )  2 là tốc độ học đã chuẩn hóa và rj là số các phần tử hij khác không của cột j. -19Nhận xét: Trong trường hợp có nhiễu tác động vào các thành phần của ma trận H và véctơ kết quả đo chuyển động của ảnh z có sai số, bằng cách sử dụng hàm mục tiêu (3.88) luận án đã sử dụng thuật toán lặp mù đơn giản [57] để ước lượng chuyển động của ảnh mà phương pháp Bayes và các phương pháp lặp trước đây chưa tính đến. 4- Ƣớc lƣợng chuyển động của ảnh bằng thuật toán tổng bình phƣơng thích nghi mở rộng Bài toán đặt ra là nếu các thành phần của nhiễu có tương quan tương hỗ thì sẽ giải nó như thế nào. Để giải quyết bài toán đó, nghiên cứu sinh sử dụng thuật toán bình phương thích nghi mở rộng đã được [57] đưa ra với giả thiết: - Các thành phần của nhiễu là có tương quan tương hỗ. - Ma trận phương sai của nhiễu đã biết trước hoặc có thể ước lượng được. - Nhiễu và véctơ x(k) độc lập thống kê. Trong hoàn cảnh tổng quát này, [57] đã sử dụng hàm mục tiêu có dạng như sau:  1 T  1  x  H H x    J ( x)    T  1  1  x  R NN  x      T (3.94) Tiếp đó là cực tiểu hàm mục tiêu (3.49). Để đơn giản và tăng tốc độ tính toán, việc chọn các hệ số phụ thuộc vào mỗi bước lặp sao cho làm giảm hàm mục tiêu tức thời: T  1   zi  T  1   x(k )  h   zi hi   x(k )    i   (3.95) J (x(k ))   T  1   1   x(k )  R NN (k )  x(k )      -20theo từng bước lặp bằng cách dịch các hệ số dọc theo hướng ngược với hướng gradient của J(x(k)) đối với các giá trị hệ số hiện tại. Chúng ta sẽ sử dụng chỉ số thời gian rời rạc k cho ma trận tương quan của nhiễu để chỉ ra rằng thống kê của nhiễu có thể thay đổi theo thời gian. Chúng ta cũng giả thiết rằng có thể khai triển ma trận tương quan của nhiễu R NN (k ) như sau:  r (k ) (rnN (k ))T  R NN (k )   nn (3.96)  rnN (k ) R NN (k )  trong đó rnn(k) là đại lượng tương ứng với tự tương quan của nhiễu trong z, rnN(k) là véctơ chứa thành phần tương quan chéo của các thành phần nhiễu trong zi và hi, RNN(k) là ma trận tự tương quan của các thành phần nhiễu trong véctơ hồi quy hi. Việc tính toán gradient của J(x(k)) theo véctơ hệ số được cho bởi: J (x(k ))  2(ei (k )hi  ei 2 (k )(rnN (k )  R NN (k )x(k ))) (3.97) (x(k )) trong đó ei ( k ) là chuẩn hóa lỗi ước lượng được xác định như sau: ei (k ) ei (k )  (3.98) T  1   1   x(k )  R NN (k )  x(k )      Luận án sử dụng thuật toán tổng bình phương mở rộng: x(k  1)  x(k )   ei (k )(hi +ei (k )(rnN (k )  R NN (k )x(k ))) (3.99) Nhận xét: Những công trình ước lượng chuyển động của ảnh trước đây người ta mới dừng lại ở giả thiết khi nhiễu hoặc sai số đo chuyển động của ảnh có phân bố Gauss, trung bình bằng 0. Ở mục này luận án đã mở rộng: - Không những chỉ có nhiễu tác động vào giá trị đo chuyển động của ảnh mà còn có nhiễu tác động vào các phần tử của ma trận H. - Không dừng lại ở giả thiết là nhiễu Gauss mà là nhiễu bất kỳ.