Ứng dụng phân cụm cho ảnh chỉ số trong lĩnh vực giấu tin trong ảnh

- TRẦN MẠNH THẮNG TRẦN MẠNH THẮNG TÊN ĐỀ TÀI LUẬN VĂN Ứng dụng phân cụm ảnh chỉ số trong lĩnh vực giấu tin trong ảnh TOÁN TIN LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: Toán Tin KHOÁ 2009 Hà Nội – 2011 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- Trần Mạnh Thắng TÊN ĐỀ TÀI LUẬN VĂN Ứng dụng phân cụm cho ảnh chỉ số trong lĩnh vực giấu tin trong ảnh LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: Toán Tin NGƯỜI HƯỚNG DẪN KHOA HỌC : 1.
- Tổng quan về luận văn Giới thiệu về giấu tin Giới thiệu về giấu tin Định nghĩa kỹ thuật giấu tin Phân loại các kỹ thuật giấu tin Các ứng dụng chính của giấu tin Môi trường giấu tin Định dạng ảnh bitmap Giới thiệu về ảnh bitmap (bmp Bitmap Header Bitmap Information Color Palette Bitmap Data Tại sao cần phân cụm trong giấu tin Chương 2.
- Thuật toán giấu tin trên ảnh bitmap Tổng quan về modul Định nghĩa và ví dụ Modul con Tích và tổng trực tiếp các modul Modul thương Modul tự do Đồng cấu Modul Sơ đồ giấu tin ứng dụng lí thuyết modul Tính đúng đắn của thuật toán Sơ đồ giải thuật Chương trình ứng dụng giấu tin trong ảnh bitmap Giấu tin trong ảnh nhị phân Giấu tin trong ảnh chỉ số 8bpp Giấu tin trong ảnh 24bpp Chương 3.
- Phân cụm ảnh chỉ số Thuật toán phân cụm K-Means Phân cụm ảnh bitmap Vấn đề khởi tạo tâm cụm.
- Ứng dụng phân cụm trong giấu tin Ứng dụng phân cụm trên ảnh bitmap 24bpp Ứng dụng trên ảnh bitmap 8bpp Điểm cô lập Ứng dụng phân cụm trên ảnh bitmap 8bpp Kết luận và tài liệu tham khảo Lời cảm ơn Lời đầu tiên tác giả xin bày tỏ lòng biết ơn chân thành và sâu sắc tới PSG.
- Học viên: Trần Mạnh Thắng Lớp: Toán Tin – Toán ứng dụng Chương 1.
- Tổng quan về luận văn 1.1 Giới thiệu về giấu tin 1.1.1 Định nghĩa kỹ thuật giấu tin Giấu thông tin là kỹ thuật nhúng (embedding) một lượng thông tin số nào đó vào trong một đối tượng dữ liệu số khác.
- Yêu cầu cơ bản của giấu tin là đảm bảo tính chất ẩn của thông tin được gsiấu đồng thời không ảnh hưởng đến chất lượng của dữ liệu gốc.
- Bảo mật thông tin bằng giấu tin có hai khía cạnh.
- Hai là bảo mật chính đối tượng được dùng để giấu dữ liệu, chẳng hạn như ứng dụng bảo vệ bản quyền, phát hiện xuyên tạc thông tin (watermarking).
- Hình 1.1 Lược đồ giấu tin Hình 1.2 Lược đồ giải mã tin 1.1.2 Phân loại các kỹ thuật giấu tin Các kĩ thuật giấu tin mới được chú ý phát triển mạnh trong khoảng 10 năm trở lại đây nên việc phân loại còn chưa được thống nhất.
- Sơ đồ phân loại sau được đưa ra năm 1999 và được nhiều người chấp nhận: 5Hình 1.3 Phân loại kỹ thuật giấu tin.
- Giấu tin mật: tập trung vào các kỹ thuật giấu tin sao cho thông tin giấu được càng nhiều càng tốt và quan trọng là người khác khó phát hiện được một đối tượng có bị giấu tin bên trong hay không bằng kỹ thuật thông thường.
- Thủy vân số: đây là kỹ thuật đánh dấu vào đối tượng nhằm khẳng định bản quyền sở hữu hay phát hiện xuyên tạc thông tin.
- 1.1.3 Các ứng dụng chính của giấu tin Giấu tin mật (Steganography): các thông tin cần bảo mật được giấu trong các đối tượng vỏ và các đối tượng này có thể được truyền công khai tới người nhận mà không gây bất cứ sự chú ý nào của đối phương.
- Người nhận sẽ sử dụng thuật toán và khóa nào đó (đã thỏa thuận giữa 2 người) để khôi phục lại thông tin mật.
- Yêu cầu kĩ thuật là tỉ lệ giấu tin cần lớn nhưng bằng các giác quan không thể nhận thấy được sự khác biệt của đối tượng trước và sau khi giấu tin vào.
- 6Bảo vệ bản quyền (Copyright Protection): đây là ứng dụng phổ biến nhất của thủy vân số.
- Một thông tin nào đó mang ý nghĩa quyền sở hữu tác giả (gọi là thủy vân) được nhúng vào trong các sản phẩm số, thuỷ vân đó chỉ một mình người chủ sở hữu hợp pháp các sản phẩm đó có và được dùng làm minh chứng cho bản quyền sản phẩm.
- Xác thực thông tin (Authentication): một thông tin được giấu trong đối tượng số để nhận biết xem đối tượng đó có bị thay đổi hay không.
- Đây là ứng dụng của thủy vân dễ vỡ.
- Giấu vân tay hay dán nhãn (Fingerprinting and Labeling): kỹ thuật này đựơc sử dụng để nhận diện người gửi hay người nhận của một thông tin nào đó.
- Ví dụ như các vân khác nhau sẽ được nhúng vào các bản copy khác nhau của thông tin gốc trước khi chuyển cho nhiều người.
- Điều khiển truy cập (Copy control): các thuỷ vân trong những trường hợp này được sử dụng để điều khiển truy cập đối với các thông tin.
- 1.1.4 Môi trường giấu tin Kỹ thuật giấu tin đã được nghiên cứu và áp dụng trong nhiều môi trường dữ liệu khác nhau như trong dữ liệu đa phương tiện, trong sản phẩm phần mềm và gần đây là những nghiên cứu trên môi trường cơ sở dữ liệu quan hệ.
- Trong các môi trường dữ liệu đó thì dữ liệu đa phương tiện là môi trường chủ yếu trong các kỹ thuật giấu tin.
- a) Giấu tin trong Audio Giấu thông tin trong audio mang những đặc điểm riêng khác với giấu thông tin trong các đối tượng đa phương tiện khác.
- Kỹ thuật giấu thông tin trong audio 7phụ thuộc vào hệ thống thính giác HAS (Human Auditory System).
- Vấn đề khó khăn ở đây là hệ thống thính giác của con người nghe được các tín hiệu ở các giải tần rộng và công suất lớn nên đã gây khó khăn đối với các phương pháp giấu tin trong audio.
- Vấn đề khó khăn thứ hai đối với giấu thông tin trong audio là kênh truyền tin.
- Kênh truyền hay băng thông chậm sẽ ảnh hưởng đến chất lượng thông tin sau khi giấu.
- Giấu thông tin trong audio đòi hỏi yêu cầu rất cao về tính đồng bộ và tính an toàn của thông tin.
- Các phương pháp giấu thông tin trong audio đều lợi dụng điểm yếu trong hệ thống thính giác của con người.
- b) Giấu tin trong Video Giấu tin trong video đang được quan tâm và được phát triển mạnh mẽ cho nhiều ứng dụng như điều khiển truy cập thông tin, nhận thực thông tin và bảo vệ bản quyền tác giả.
- c) Giấu tin trong ảnh Giấu tin trong ảnh chiếm tỉ lệ lớn nhất trong các chương trình ứng dụng, các phần mềm, hệ thống giấu tin trong đa phương tiện bởi lượng thông tin được trao đổi bằng ảnh là rất lớn và hơn nữa giấu thông tin trong ảnh cũng đóng vai trò hết sức quan trọng trong các hầu hết các ứng dụng bảo vệ an toàn thông tin như: nhận thực thông tin, xác định xuyên tạc thông tin, bảo vệ bản quyền tác giả, điều khiển truy cập, giấu thông tin mật.
- Thông tin sẽ được giấu cùng với dữ liệu ảnh nhưng chất lượng ảnh ít thay đổi và chẳng ai biết được đằng sau ảnh đó mang những thông tin có ý nghĩa.
- Ngày nay, khi ảnh số đã được sử dụng rất phổ biến thì giấu thông tin trong ảnh đã đem lại rất nhiều những ứng dụng quan trọng trên nhiều lĩnh vực trong đời sống xã hội.
- Trong luận văn này, tác giả cũng chỉ nghiên cứu thuật toán Modul giấu thông tin trong ảnh chỉ số bitmap.
- 81.2 Định dạng ảnh bitmap 1.2.1 Giới thiệu về ảnh bitmap (bmp) BMP là một định dạng tập tin hình ảnh khá phổ biến do Microsoft đề xuất, có phần mở rộng là .bmp hoặc .dib (Device Independent Bitmap).
- 1.2.2 Bitmap Header Gồm 14 bytes lưu thông tin về tập tin bitmap: Tên trường Số byte Ý nghĩa Type 2 Nhận dạng kiểu file, chứa 2 ký tự bm Size 4 Kích thước file Reserved 4 Để dành Offset 4 Vị trí bắt đầu vùng Data 91.2.3 Bitmap Information Gồm 40 bytes lưu thông tin chi tiết về ảnh: Tên trường Số byte Ý nghĩa HeaderSize 4 Số byte của vùng BitmapInfo, mặc định là 40 Width 4 Độ rộng của ảnh tính theo Pixel Height 4 Độ cao của ảnh tính theo Pixel Planes 2 Số planes mầu BitPerPixel 2 Số bit biểu diễn 1 Pixel SizeImage 4 Kích thước ảnh XPixelsPerMeter 4 Độ phân giải ảnh theo chiều ngang YPixelsPerMeter 4 Độ phân giải ảnh theo chiều dọc ColorsUsed 4 Số lượng mầu trong bảng mầu ColorsImportant 4 Số mầu quan trọng 1.2.4 Color Palette Bảng mầu là tập các mầu sử dụng trong ảnh, mỗi mầu được lưu trữ bằng 4 bytes xếp liền nhau theo cấu trúc Blue-Green-Red và một byte dự trữ.
- Các mầu được liệt kê trong trong file 1 bit, 4 bit, 8 bit được gọi là Indexed, còn 24 bit được gọi là True.
- 1.3 Tại sao cần phân cụm trong giấu tin Như tác giả đã đề cập định dạng ảnh bitmap là ảnh không nén, có thể dễ dàng truy xuất nội dung của ảnh và cài đặt các thuật toán trên đó.
- Tuy nhiên ảnh bitmap có một số nhược điểm.
- Định dạng ảnh này không phổ biến trong môi trường truyền tin trên Internet nên khi thực thi giấu tin trên ảnh bitmap sẽ gây nghi ngờ.
- Để khắc phục 2 nhược điểm này, tác giả đề xuất ứng dụng phân cụm trong giấu tin.
- Đối với ảnh bitmap 24bpp, ảnh này có dung lượng lớn thì chúng ta sử dụng phân cụm ảnh thành 8bpp để giảm dung lượng.
- Với ảnh bitmap trước khi gửi đi trên Internet chúng ta sẽ chuyển đổi sang ảnh gif – định dạng ảnh phổ biến trên Internet.
- Tuy nhiên để chuyển ảnh bitmap sang ảnh gif chúng ta cần có ảnh bitmap 8bpp, vì thế cần phân cụm để chuyển các ảnh bitmap 24bpp sang ảnh bitmap 8bpp.
- Ngoài ra chúng ta có thể thấy rằng ảnh bitmap 8bpp được xây dựng cùng với bảng palete 256 mầu, do đó nếu chúng ta thực hiện phân cụm ảnh ta có thể xây dựng palete mầu riêng, điều này giúp chúng ta nâng cao chất lượng ảnh chứa tin và tăng khả năng bảo mật khi giấu tin.
- Thuật toán giấu tin trên ảnh bitmap 2.1 Tổng quan về modul 2.1.1 Định nghĩa và ví dụ Định nghĩa 1.1.
- Định nghĩa modul trái Cho V là một vành có đơn vị 1 ≠ 0 và Mlà một nhóm cộng Abel, Mlà một V-modul nếu cùng với một ánh xạ µ từ VM×vào M, tạo nên một phép toán tác động trái của V trên M: VM M.
- .mv mv vm=a Một số ví dụ về V −modul: Ví dụ 1.1: Mỗi Ideal I của một vành V là một V−modul.
- Đặc biệt, bản thân V cũng là một V −modul.
- 12Nhận xét: Các modul với vành hệ tử là một trường F được gọi là không gian vecto trên trường F.
- Chẳng hạn, mọi trường đều là một không gian vecto trên bất kỳ trường con nào của nó và, nói riêng ra, trên chính nó.
- Ví dụ 1.3: Mỗi nhóm Abel cộng M đều được xem là một Z−modul với phép toán nhân ngoài xác định như sau: ...nx x x x=+++(tổng gồm n số hạng x) với ,nZxM∈∈ Nhận xét: Từ các ví dụ nêu trên ta có thể thấy khái niệm modul là khái niệm tổng quát của các khái niệm: vành.
- ()ax ax a x−=−=−với mọi ,xMa V∈∈ 2.1.2 Modul con Định nghĩa 1.3.
- Một tập con không rỗng N của một V−modul M được gọi là một V −modul con của M, nếu bản thân N cùng với hai phép toán trong M làm cho N trở thành một V −modul.
- Khi N là một modul con của modul M, thì ta nói rằng M là một modul mở rộng của N.
- Nói cách khác, một tập con không rỗng N của M là một modul con của M nếu và chỉ nếu N là nhóm con của nhóm Abel cộng của M và là ổn định dưới phép nhân vô hướng của M, tức là ax N∈với mọi ,aVx N.
- Các modul con của một không gian vecto thường được gọi là các không gian con.
- Từ các nhận xét trên, ta có định lí để kiểm tra V−modul con : Định lí 1.2.
- Một tập conNcủa mộtV−modulMlà mộtV−modul con của Mnếu và chỉ nếu : 0MN∈ và.
- Một số ví dụ: Ví dụ 1.4: Với một V −modul M, thì luôn tồn tại hai modul con tầm thường là: modul con không {0} và bản thân M.
- 13Ví dụ 1.5: Mọi nhóm con N của nhóm Abel cộng M đều là modul con của M, xem là một modul trên vành Zcác số nguyên.
- Giả sử {}INαα∈là một họ tùy ý các modul con của một V −modul M, khi đó ta có : (i) INαα∈Ivà INαα∈∑là các V−modul con của M.
- (ii) Nếu họ {}INαα∈lồng nhau, thì INαα∈Ucũng là một V−modul con của M.
- Chú ý : Nếu {}0INNαβαβ≠∈⎡⎤=⎢⎥⎣⎦∑Ivới mọi Iα∈, thì INNαα∈=∑được gọi là tổng trực tiếp trong của các modul con của họ đã cho, còn các Nαđược gọi là các hạng tử trực tiếp của N.Tổng trực tiếp được viết là INαα.
- Định nghĩa 1.4.
- Giả sử S là một tập con tùy ý cho trước của một V −modul M, khi đó giao của tất cả các modul con chứa S của Mcũng là một modul con của M.
- Modul con này được gọi là một modul con của Msinh bởi S.
- Nếu modul con sinh bởi S chính là M, thì ta nói rằng S là một hệ sinh của M.
- NếuMcó một hệ sinh hữu hạn, thì ta nói Mlà một modul hữu hạn sinh.
- Nếu hệ sinh của Mchỉ gồm một phần tử, thì Mđược gọi là một modul đơn sinh.
- Nhận xét: Nếu S là tập rỗng, thì modul con sinh bởi S chính là modul con {}0 và nó cũng là modul con sinh bởi tập {}0 .
- Một phần tử x của một modul M trên V gọi là một tổ hợp tuyến tính của các phần tử trong một tập con S của M nếu và chỉ nếu tồn tại một số hữu hạn những phần tử 12, ,...,nxxx trong S sao cho ta có: 1niiixax==∑với các hệ tử 12, ,...,nxxx trong V.
- Cũng như không gian vecto hay ideal ta thấy ngay modul con sinh bởi S chính là tập tất cả các tổ hợp tuyến tính của các phần tử của S .
- 142.1.3 Tích và tổng trực tiếp các modul Cho I là một tập khác rỗng.
- Giả sử ()IMαα∈ là một bộ tùy ý các V−modul chỉ số hóa bởi I .
- Khi đó ta kiểm tra được ngay *Mlà một V−modul .
- Modul này được gọi là tích trực tiếp của các một bộ các V−modul ()IMαα∈.
- Cũng ngay lập tức, ta thấy SMαα∈⊕là một V−modul con của *M.
- Và SMαα∈⊕ được gọi là tổng trực tiếp của bộ các V−modul ()IMαα∈.
- Đặc biệt Z−modul nZđược gọi là một lưới nguyên trong không gian n−chiều thực nR.
- Lưới nguyên nZluôn là một thách thức muôn thuở của toán học.
- 2.1.4 Modul thương Giả sử Nlà một modul con của một V−modul M.
- Ta nhận được một V−modul MNvới hai phép toán trên.
- Modul này được gọi là modul thương của Mtheo N.
- Ví dụ 1.6: Trường số hữu tỉ Q là một Z−modul và Zchính là một Z−modul con của Q.
- Ta nhận được Z−modul thương /QZ là một modul chỉ bao gồm các phần lẻ của một số hữu tỉ.
- Tập con S không rỗng của một V−modul Mđược gọi là một tập độc lập tuyến tính, nếu từ mỗi đẳng thức 11 2 2.
- Nếu trái lại thì S được gọi là một tập phụ thuộc tuyến tính.
- Một modul Mcó một hệ sinh S độc lập tuyến tính thì nó được gọi là một modul tự do và tập Sđược gọi là một cơ sở của M.
- Vậy nV là một V−modul tự do, và cơ sở vừa nêu được gọi là cơ sở tự nhiên hay cơ sở chính tắc của nó.
- Ví dụ 1.8: Mọi không gian vecto đều la một modul tự do, vì nó luôn có các cơ sở.
- Các cơ sở hữu hạn của cùng một V−modul tự do hữu hạn sinh Mcó cùng một số phần tử.
- Số phần tử đó được gọi là hạng của V−modul tự do Mvà kí hiệu là ()rM.
- Một modul tự do không hữu hạn sinh, được gọi là có hạng vô hạn.
- Một ánh xạ ftừ một V−modul Mvào một V −modul N gọi là một đồng cấu modul hay ánh xạ tuyến tính nếu f thỏa mãn hai tính chất sau:

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt