TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM KHOA TOÁN ~ TIN BỘ MÔN TIN NGUYÊN THÁI HỌC TÌM HIỂU ICA VÀ GIẢI THUẬT FASTICA pO AN TOT NGHIỆP CỬ NHÂN SƯ PHAM TIN KHOA TOÁN -— TIN BO MON TIN TÌM HIỂU ICA VÀ GIẢI THUẬT FASTICA Sinh viên thực hiện: NGUYEN THÁI HỌC Giảng viên hướng dẫn: NGUYÊN VIÊT HƯNG THU VIỆ +; Prone Đat-Học Su-E - HO CHI-F1 Wye. tw ‘ Lời cảm ơn Sau gần hai tháng làm việc cật lực cuối cùng thì em cũng đã hoan thành được dé án tốt nghiệp của minh. Mặc dù kiến thức trong đồ án này chí là một phần nhỏ trong kho tang kiến thức của chuyên dé xử lý hình ảnh bằng ICA nhưng đối với em nó mang lại một kiến thức mới vô cùng hữu ích. Đó là thành quả của gan hai tháng trời nghiên cứu học tập.
Và xa hơn nữa chính là kết quả của bốn năm đèn sách dưới mái trường Đại Học Sư Phạm. Có được thành tựu dù không lớn lao nhưng nó cũng đã thé hiện phan nào sự cé gắng của bản thân cũng như sự chỉ bảo tận tinh của các thầy cô đã day bảo em trong suốt thời gian học vừa qua. Em xin chân thành cảm ơn đến tắt cá các thay cô trong Khoa Toán Tin đặc biệt là Tổ Bộ môn Tin Học đã tận tỉnh chỉ bảo truyền đạt những kinh nghiệm kiến thức cho chúng em để chúng em có được những cơ sé kiến thức cần thiết hoàn thanh đồ án này. Những kỷ niệm những ân tinh mà thầy Quang Tắn.
thiy Ngọc Trung, thầy Bao. đối với chúng em sẽ mãi là những kỷ niệm đẹp chúng em sẽ mãi không bao giờ quên. Vượt lên trên cả em xin chân thành cảm ơn thay Nguyễn Viết Hung, thay đã hướng dẫn em hoản thành tốt đồ án nay. Thầy đã cung cấp cho em rất nhiễu tai liệu hỗ trợ cũng như kinh nghiệm cần thiết cho việc nghiên cứu dé tải này.
Mặc dù thay có rất nhiều công việc nhưng mỗi lan chúng em gặp những vướng mắc thay luôn sẵn sàng gặp mặt dé giúp đỡ. Tuy đã rất cố gắng nhằm đạt được những gì tốt nhất cho dé án nay nhưng do kiến thức có hạn và đo đây là lĩnh vực mới nên việc tìm kiếm tải liệu khó khăn do vậy đồ án này nhất định sẽ có những khiếm khuyết cần được sửa chữa và bé sung. Kính mong các thầy cô cùng các bạn đọc thông cam và nhiệt tinh đóng góp những ý kiến nhằm khắc phục những khiếm khuyết của đồ án. Một lần nữa em xin gửi lời cảm ơn đến tat cả các thay cô đã day bảo em trong suốt thời gian qua.
Bàitoắn:-—-——--——=~-=~====e==s======s=>=>ms=>s=z=~===mrr=r=rr==sr=r==========~ Ố ~ Ul. Xử lý thành phan độc lập: --------------~===~~===x~~=——>~~~~=~~>—~~~~=z>====s==== | = 2. Định nghĩa ÍCA;-=------<-===~--============re=ee===s=r=sr=xsreesrrr==exee = tie Sự da nghĩa của ICA: —---—---~——-——-~-~=~=~et=—=~=teeree~==t==~======e>= 13 - 2. Minh hoa của ICA: -——----«~------=========<=========sn=rsess=~=srxee=e=====e= -14- 2.
Sựđộc lậ p7 --------=-----=-s-~-««=====~e==xe=====se=rrr===rxssree========= 18- là gì 3. Định nghĩa và những thuộc tính cơ ban: -------=--===«=««==-===e============ 18 - 3. Các biến không tương quan với nhau thì chỉ phần nào độc lập: ------- 19 - 3. Tại sao các biến Gaussian bị ngăn cấm ? -----—---«=«===s=see=s=======x -19- IV.
Những nguyên lý của sự đánh giá ICA: --«=-----=««===«~====ses=ee=====—==~= 2] ~ 4. “Nongaussian là độc lip”:—-------------------------------------------------- 21- 4.2, Đơn vị đo của Nongaussian: -«--~-««-=--<-<=<=<=x=se==e=s~==s~ễs=xe==r=====ee 23 - 42ZJ. :Ngpeuita\:—— tr Sẽ, sẽ 6c c. Những phép tính gan đúng của Negentrpy:--------------------—-—-- -29 - 4.
Cực tiểu hóa thông tin chung: --------—--«««««=«««=e===seee~=s===szsr=essr= 3] + ASA | Wiking thin Cang! Sex. Định nghĩa ICA bằng thông tin chung: ------------------------------ -32- 4.4, Sự có khả năng xảy ra ước lượng cực đại: -----------------------+------- -33- 4. Sự có khả năng xảy fa:-=--------======xe==~~==~====r~~~x~=z~~~r~~~~=~~ 33- 4. Nguyên lý thông tin lớn nhất: ---------------~-~~==~~-~~~~~~~==~==~e~=~ -34- 4.
Su kết nối đến thông tin chung:--—----«-«--~«~-=s=ee=es-sesse==ee==== 34 « 4. ICA và sự thực hiện phép chiéu:-------------------------------------—---- 3Š - V,. Tiền sử lý cho ICA: -=-~---=--~~-=~+xe==>>~T~T~—~=~=====~~~~~~sereeee=seeeexrerrssee kW Sih, Trọng tâm: --==«e«=s=s========sr====s===s=sre============x=r=======r===~===== -37- 5. Đẩy mạnh việc tiền xử lý--—-—--~--~«-=e-=eeeeeeeererererrrrr=rrrrrrerr—rer - 40 - VỊ.
Thuật toán FasửCA: --------------—====—==s==rreeesseeeeeeeesesee 4l- 6. FastiCA đối với một đơn vị ---------—---------------------------------- 4 | - 6. FastICA đối với nhiều đơn Vị; ------------------—------------—------2===== -43- 6. FasiCA va khả năng xảy ra cực đại: -----«-=--«----««~====s===s=======ee= 45- 6.
Các thuộc tính của thuật toán FastICA:------------------------------------ 46- VII. Ứng dụng của ÍCA:-------«-«=«=««===~=~~=~-~xx==~==~~~~=~~~eeer=======x=rerrrsrre 47- 7. Su tách biệt của các công cụ tạo tác dụng trong đữ liệu MEG: ------- 47 - 7. _ Việc tìm kiếm những thừa số ẩn trong dữ liệu tài chính.
Giảm độ nhoè trong các hình ảnh tự nhiên: -----------«--====~==~===~=== S&- VIII. — Kết luận: -------------------------=~--~--~~==~==~~==~==~==~~~~~~~~=~~~~~~~~~~~~= - 59- Bài toán: Hình dung rằng bạn ở trong một phòng có hai người đang đồng thời nói chuyện. Bạn có hai Micro, bạn giấu chúng ở những vị trí khác nhau. Những Micro cho bạn hai tín hiệu thời gian được ghi, chúng ta có thể biểu thị bởi x;(t) và x;(U, với x; và x; là những biên độ, và t là chỉ số thời gian.
Mỗi tín hiệu được ghi lại này là một tổng của những tín hiệu lời nói được phát ra bởi hai người nói, chúng ta biểu thị chúng bởi s,(U và s;(t). Chúng ta có thể biểu diễn vấn để này như một phương trình tuyến tính: Xi(L = âiiŠ¡ + â¡z§2 (1) X(t) = 42¡S¡ + ap2S> (2) trong đó a¡¡, 4;2, 42), và a;; là vai tham số phụ thuộc vào các khoảng cách của những Micro từ những người nói. Rất hữu ích nếu bây giờ bạn có thể đánh giá hai tính hiệu lời nói nguyên bản s;(t) và s¿( mà chỉ sử dụng những tín hiệu được ghi lại x;(t) và xz(t). Vấn để này được gọi là bài toán pha trộn hỗn tạp.
Trong thời gian hiện nay, chúng ta bỏ qua bất kỳ sự trì hoãn thời gian hoặc hệ số phụ khác nào từ mô hình hỗn hợp được đơn giản hoá của chúng ta. Như một sự minh hoa, xem xét những dạng sóng trong (hình |) và (hình 2). Hình |: Hinh 2 Tất nhiên, những điều này không là tính hiệu lời nói hiện thực. nhưng đủ cho sự minh hoa này.
Những tín hiệu lời nói nguyên bản gốc có thể được xem xét một vài thứ như trong hình | và những tín hiệu hỗn tạp có thể xem xét như trong hình 2. Vấn để là khôi phục dữ liệu trong hình ¡ chỉ sử dụng dữ liệu trong hình 2. Thật sự nếu cúng ta biết những tham số aj, chúng ta có thể giải phương trình tuyến tính (1) bằng những phương pháp cổ điển. Tuy nhiên, nếu bạn không biết a, thì bài toán xem xét khó hơn nhiều.
Một cách tiếp cận bài toán này sẽ sử dụng vài thông tin vé những thuộc tính thống kê của những tín hiệu s(t) để ước lượng aj. Thật sự và có lẽ ngạc nhiên, có thể s,(t) va s;(t) ở mỗi thời điểm t là độc lập thống kê. Điều này không phải là một giả thiết không hiện thực trong nhiều trường hợp, và nó không cần phải thật chính xác trong thực tế. Kỹ thuật được phát triển mới đây của phân tích thành phan độc lập, hoặc ICA, có thể sử dung để ước lượng a, dựa vào thông tin vé sự độc lập của chúng, nó cho phép chúng ta phân tích Hình 3 Như có thể nhìn thấy được, những tín hiệu này rất gần những tín hiệu nguồn nguyên ban của chúng được nghịch đảo, nhưng những diéu này không đáng kể.
Phân tích thành phan độc lập được phát triển trước tiên để giải quyết những vấn để liên quan mật thiết đến bài toán pha trộn hỗn tạp. Ké từ khi sự quan tâm đế ICA tăng lên, nó đã trở nên dễ hiểu hơn. nguyên lý này còn có nhiều ứng dụng thú vị khác nữa. Vi dụ, xem xét hoạt động của việc ghi điện não dé (EEG).
Dữ liệu EEG gồm có nhién sự ghi những điện thé trong nhiều vị trí khác nhau trên da đầu. Những điện thế này có lẽ được phát sinh bởi việc trốn lẫn vài thành phần nầm bên dưới hoạt động của não. Tình trạng này tương tự với bài toán pha trộn hỗn tạp : chúng ta muốn tìm những thành phẩn nguyên bản hoạt động của não, nhưng chúng ta có thể chi quan sát những sự pha trộn của các thành phần. ICA có thể phát hiện thông tin thú vị về hoạt đông não bằng cách cung cấp quyền truy cập đến những thành phin độc lập của nó.
Một vấn để khác, ứng dụng khác nhau của ICA về sự trích ra đặc tính. Một vấn để cơ bản trong xử lí tín hiệu số sẽ tìm thấy những sự trình bày thích hợp cho hình ảnh, âm thanh hoặc các loại dữ liệu khác với những nhiệm vụ như nén ảnh và giảm tạp âm. Những sự trình bày dữ liệu thường là những phép biến đổi tuyến tính được dựa vào chuẩn mà những phép biến đổi tuyến tính được sử dụng rộng rãi trong sử lý ảnh Fourier, sương mù, những sự biến đổi cosin. Mỗi chúng có những thuộc tính thuận lợi của chính mình.
Nó đa số là rất hữu ích để đánh giá phép biến đổi tuyến tính từ bản thân dữ liệu, trong trường hợp này sự biến đổi có thể lý tưởng được làm thích nghi với loại dữ liệu đang được xử lý. Hình 4 cho thấy ring những hàm cơ sở đang tồn tại bởi ICA từ những miến vá của những hình ảnh tự nhiên. yPLaolts a|ePdpsLC8WeDaỊMEBPNSWRTIH5MfẽENm ' + ` 4 Hinh Mỗi cửa sổ hình ảnh trong tập hợp của việc sấp xếp hình ảnh là một chồng của những cửa sổ này để hệ số trong chồng là độc lập. Sự trích ra những đặc tính trong ICA sẽ được giải thích rd hơn trong phan sau Tất cả những ứng dụng của ICA được mô tả ở trên có thể thật sự được công thức hoá trong một khung toán học hợp nhất.
Đây là một phương thức rất chung của sự xử lý tín hiệu và sự phân tích dữ liệu. - 10+ Xử lý thành phần độc lập: 2. Định nghĩa ICA: Để định nghĩa ICA một cách chính xác, chúng ta có thể sử dụng mô hình thống kê “những biến ẩn". Giả sử chúng ta quan sát n sự pha trộn tuyến tính x), Xz,.
X_ của n thành phần độc lập: Xj = AS; + ApS? +. + 4iaS„ với Vj (3) Bay giờ chúng ta có thể bỏ qua chỉ số thời gian t ; trong mô hình ICA, chúng ta giả sử rằng mỗi sự kết hợp x; cũng như mỗi thành phần độc lập s là một biến ngẫu nhiên, thay vì là một tín hiệu thời gian thích hợp. Những giá trị được quan sát x,t), chẳng hạn như những tính hiệu Micro trong “bai toán pha trộn hỗn tạp” là một ví dụ điển hình của biến ngẩu nhiên này. Không mất tính tổng quát, chúng ta giả sử rằng cả những biến pha trộn và những thành phan độc lập đều vô nghĩa: nếu không đúng thì những biến có thể quan sát được x, có thể luôn được đặt vào trung tâm bằng cách trừ đi trung bình cộng để tạo nên mô hình vô nghĩa.