Cấu trúc dữ liệu - Chương 1: Các khái niệm cơ bản

1Nguyễn Thị Oanh Bộ môn HTTT – Viện CNTT & TT oanhnt@soict.hut.edu.vn Chương 1: Các khái niệm cơ bản 2Nội dung 1. Văn bản (text) 2. Đồ họa và ảnh động (vector graphics and animation) 3. Âm thanh (Digital Audio) 4. Ảnh số (Digital Image) 5. Video số (Digital Video) 31. Văn bản 4DL văn bản – Chứa thông tin chủ đạo – Input: bàn phím, các chương trình nhận dạng âm thanh và ký tự, dữ liệu lưu trên đĩa, phụ đề phim, 5DL văn bản  Kích thước lưu trữ: không đáng kể so với các dữ liệu đa phương tiện khác  Định dạng: đa dạng: – Văn bản thường (file ASCII) – Văn bản có cấu trúc, được định dạng (màu sắc, độ bóng, ...) (html, xml, RTF, Word, mã nguồn của chương trình C, latex, PDF, ) 6DL văn bản - Nén  Nén không làm mất mát thông tin  Dự trên thực tế: – tần suất xuất hiện của các ký tự khác nhau  Một số kỹ thuật: – Huffman coding – Run-length Coding – Lempel Zip -Welch Coding (LZW) 7Huffman Coding  Dựa trên tần suất xuất hiện của item (ký tự)  Từ nào xuất hiện nhiều thì dùng ít bít để mã hóa và ngược lại  Mã cho mỗi ký tự được lưu trong Code book tương ứng cho mỗi tài liệu. VD:  Xác định code book ? Ký tự Tần suất Mã F 0.8 1 T 0.16 01 X 0.02 001 Z 0.02 000 8Run-length Coding  Dựa trên số lần lặp liên tục của các ký tự  Kết quả: @8ebt@7n eeeeeeeebtnnnnnnn 1 run, length = 8 8 e@ Ký tự đăc biệt để chỉ rằng đang mã hóa 9LZW  Dựa trên tần suất lặp của các cụm ký tự  Xây dựng từ điển cho các cụm ký tự  Ví dụ: Giả sử tài liệu có 10.000 ký tự Chia thành 2000 các cụm ký tự Trong đó có 500 cụm khác nhau – Không nén: 10.000 x 8 bit = 80.000 bit – LZW: 2000 x 9 bit = 18.000 bit (để biểu diễn được 500 token, cần 9 bit) Token Chuỗi ký tự .. 10 2. Đồ họa và ảnh động 11 Đồ họa và ảnh động  Đồ họa – Pixel-based graphic: xử lý giống ảnh số – Vector-based graphic:  Mô hình được định nghĩa trước  Không gian lưu trữ: thấp  Dễ lấy nội dung  Ảnh động: – Pixel-based: giống video – Vector-based: giống vector-based graphic nhưng có thêm thông số về thời gian 12 3. Âm thanh 13 DL âm thanh Tiếng động, tiếng nói (văn bản đi kèm), nhạc, phim, các chương trình dịch tự động từ văn bản, 14 DL âm thanh – Tín hiệu âm thanh là tín hiệu tương tự và liên tục – Input : microphone số hóa và lưu trữ – Không gian lưu trữ lớn :  CD Quality Audio : 16-bit sampling at 44.1 KHz  1 phút của 1 Mono CD (chưa nén): 5Mb  1 phút của Stereo CD (chưa nén) : 10Mb – Thường được nén lại để giảm kích thước (mp3, aac, Flac, Ogg Vorbis, ) 15 ADC (Analog-to-Digital Converter) – Lấy mẫu (Sampling) – Lượng tử hóa (Quantization) – Mã hóa (Encoding) 16 Một số kỹ thuật nén – Lượng tử phi tuyến – Predictive Coding – Chuẩn nén audio : MPEG – Audio 17 4. Ảnh số 18 Ảnh số – Ảnh số là một chuỗi các điểm ảnh để biểu diễn 1 vùng sẽ được hiển thị trên màn hình của người sử dụng – Input : caméra, scan, sinh ra từ các chương trình mô phỏng hay các phần mềm tạo và xử lý ảnh – Định dạng : jpg, png, bmp, tiff, – Kích thước lưu trữ : phụ thuộc vào kích thước ảnh, độ phân giải, kỹ thuật nén (nếu có).  1 bit / 1 pixel (ảnh nhị phân)  8 bits/ 1pixel (ảnh đa mức xám)  24 bits / 1pixel (ảnh màu) – Ảnh thường được nén để giảm không gian lưu trữ 19 Ảnh xám 64 60 69 100 149 151 176 182 179 65 62 68 97 145 148 175 183 181 65 66 70 95 142 146 176 185 184 66 66 68 90 135 140 172 184 184 66 64 64 84 129 134 168 181 182 59 63 62 88 130 128 166 185 180 60 62 60 85 127 125 163 183 178 62 62 58 81 122 120 160 181 176 63 64 58 78 118 117 159 180 176 Mức xám - 8 bits: 0 - đen 255 - trắng Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 20 Ảnh màu -Mỗi điểm ảnh có 3 thành phần màu: R, G, B -1 ảnh số = 3 ma trận giá trị số để biểu diễn cường độ R, G, B tương ứng - Ngoài RGB còn có các hệ tọa độ màu khác: YUV, HSV 21 Tham số 210 209 204 202 197 247 143 71 64 80 84 54 54 57 58 206 196 203 197 195 210 207 56 63 58 53 53 61 62 51 201 207 192 201 198 213 156 69 65 57 55 52 53 60 50 216 206 211 193 202 207 208 57 69 60 55 77 49 62 61 221 206 211 194 196 197 220 56 63 60 55 46 97 58 106 209 214 224 199 194 193 204 173 64 60 59 51 62 56 48 204 212 213 208 191 190 191 214 60 62 66 76 51 49 55 214 215 215 207 208 180 172 188 69 72 55 49 56 52 56 209 205 214 205 204 196 187 196 86 62 66 87 57 60 48 208 209 205 203 202 186 174 185 149 71 63 55 55 45 56 207 210 211 199 217 194 183 177 209 90 62 64 52 93 52 208 205 209 209 197 194 183 187 187 239 58 68 61 51 56 204 206 203 209 195 203 188 185 183 221 75 61 58 60 60 200 203 199 236 188 197 183 190 183 196 122 63 58 64 66 205 210 202 203 199 197 196 181 173 186 105 62 57 64 63 x = 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 y = Source : Tal Hassner. Computer Vision. Weizmann Institute of Science (Israel). 22 Kỹ thuật nén  Dựa trên: – dư thừa trong ảnh (lặp giá trị) – dư thừa theo khả năng nhận thức (nhìn thấy) của con người  Ví dụ: 2 điểm lân cận ở 2 hàng liền nhau thì có giá trị gần giống nhau mà con người khó phân biệt – với các mẫu khác nhau, độ nhạy cảm về nhận thức là khác nhau  Mục tiêu: – Giữ lại các thông tin quan trọng và loại bỏ các TT khác 23 Kỹ thuật nén – Spatial Subsampling – Prediction Coding – Transform Coding – Vector Quantization (tương tự LZW) – Fractal Image Coding – Chuẩn nén JPEG – 24 5. Video số 25 Video số  Vidéo/Animation: – Video số gồm một chuỗi các khung hình (frames) (frame rate: 25, 30, 50 frames /giây) – Input : video camera số hóa – Định dạng: đa dạng (mp4, avi, ) – Không gian lưu trữ : tốn nhất  Tùy thuộc và độ phân giải và kích thước, 1 khung hình có thể cần 1MB  Video 512 x 512 đơn sắc : 25 x 0.25 = 6.25 Mb/1giây (chưa nén)  PAL video (720x 576 pixel / khung màu) : 1.2 x 25 = 30Mb/giây (chưa nén)  High Definition DVD (1440 x1080 = 1.5 Megapixels/frame) : 4.5 x 25 = 112.5Mb /giây (chưa nén) – Dữ liệu phải được nén 26 Frame rate – Đủ lớn để thấy truyền tải sự chuyển động liên tục (>= 25 frames/s) – Băng thông để truyền tải tín hiệu:  frame rate càng lớn thì băng thông phải lớn ( thỏa hiệp: frame rate: 25 frames/s) – Tốc độ làm tươi màn hình hiển thị (>=50 lần /s)  Giải pháp cho hệ thống tivi: 2:1 interlace 27 Nén – Dựa vào dư thừa về mặt không gian (giữa các điểm ảnh) (spatial redundancy): sử dụng các KT nén ảnh – Dựa vào dư thừa về mặt thời gian (giữa các khung hình) (temporal redundancy): Motion estimation and Compensation 28