Fractal Image Compression (Nén ảnh phân đoạn)

định . Điều kiện này thì đủ tốt để dừng lại nếu cần thiết vì nó chỉ hiệu quả trên việc tái tạo hình ảnh chứ không hiệu quả trên mã hóa . 5. Tính duy nhất ( Uniqueness ) của ƒ. Hàm ƒ(p) chỉ có một điểm cố định tương ứng p* .Điều này có nghĩa là phương trình chỉ có một cách giải duy nhất . Điều này thì hiệu quả đối với mã hơn là đối với hình ảnh trong cùng một hàm . Ở đây tất cả các hàm đều cố gắng để thực hiện điều kiện này . I.3.1. Sử dụng Vector trong hàm mã hóa . Trong các hình ảnh mã hóa bằng khối Fractal thì thông thường được thể hiện bởi vector . Hàm được biết như là một chuyển đổi affine của mặt phẳng . Ở đây , khi đó sẽ có kích thước là n2 . Hệ số K là một ma trận chuyển đổi có kích thước n2 x n2 và là một vector chuyển đổi với kích thước n2 . Bởi vì việc nén yêu cầu vector chuyển đổi thông thường được chọn là , trong đó c là vô hướng và là một vector với tất cả các phần tử đều bằng 1 ( vector cơ sở ) . , với i = 1 , , n2 là giá trị riêng của K . Bán kính quang phổ của K được xác định bởi : (2) Hàm là thu nhỏ nếu ρ(K) < 1 . Lược đồ lặp cho ta thấy điều đó nếu là thu nhỏ . nghiệm cho phương trình này là (3) Nếu không là thu nhỏ thì điểm cố định có thể vẫn được tính toán bằng cách giải phương trình bằng : (4) nếu là một ma trận khả nghịch . Ma trận là ma trận kích thước n2 x n2 đồng nhất . Phương trình có một nghiệm giải duy nhất nếu và chỉ nếu và cũng có yêu cầu tương tự với i = 1,..,n2 . I.3.2. Sử dụng ma trận trong hàm mã hóa. Bởi vì hình ảnh thường được xem như là các ma trận . Chúng ta đã từng được học trường hợp mà khi đó ma trận được sử dụng như là các biến trong hàm . Ở đây , ta sẽ thảo luận sơ về hàm ƒ(P) = AP + C . Một trong các hàm khá tốt để sử dụng khi hình ảnh được xác định là các ma trận là ƒ(P) = AP + C , trong đó A , P và C là các ma trận kích thước nxn . P là một ma trận ảnh , A tạo ra một chuyển đổi và C là một chuyển đổi . Hàm này là thu gọn nếu ρ(A) < 1 . Nếu ƒ(P) là thu gọn thì phương trình có thể được giải quyết như sau : (5) Còn nếu hàm không có tính thu nhỏ thì điểm cố định có thể được tìm thấy bởi phương trình P* = AP* + C và nó cho ta một nghiệm : P* = (In – A)-1C (6) trong đó , ma trận (In – A) phải là ma trận khả nghịch . Phương trình có một nghiệm duy nhất nếu và chỉ nếu det(In – A) ≠ 0 , nghĩa là với i = 1,, n . Ma trận C có thể được chọn là C = cE , trong đó c là vô hướng và E là ma trận với tất cả các phần tử đều bằng 1 . Sự chọn lựa này sẽ sinh ra tỉ lệ nén cao . Một sự chọn lựa hợp lý của c chính là giá trị trung bình của ảnh gốc P0 . Nhưng với hàm này thì chúng ta thấy rằng P* = (In – A)-1C có bậc 1 bởi vì C có bậc 1 . Trong trường hợp này tất cả các cột của P* sẽ trở nên bằng nhau . Chính vì thế , chúng ta phải tìm ra một sự chọn lựa tốt hơn C = cE cho ma trận C . Sự lựa chọn tốt nhất chính là C = cIn , trong đó c vẫn làvô hướng và In là ma trận đồng nhất . Ma trận này có bậc n và nó cho ta một khả năng nén tốt ở cùng thời điểm . Với sự chọn lựa này của ma trận C thì nghiệm phương trình sẽ là : P* = c(In – A) -1 . (7) Trong trường hợp vector , một số sự chọn lựa khác của ma trận K đều dẫn đến cùng một điểm cố định . Nhưng với phương trình ƒ(P) = AP + C chỉ có ma trận A cho nghiệm chính xác P* = P0 với . Ma trận A có thể được xem như là một chuyển đổi không tuyến tính của ma trận P . Chúng ta đã nghiên cứu đặc tính của biến đổi này nhưng nó dường như không hiệu quả như là một số các biến đổi khác được sử dụng trong việc mã hóa chuyển đổi . Trong một số trường hợp , nó có thể là ý tưởng tốt để mở rộng hàm thành ƒ(P) = A(P – C + dIn)+ C , trong đó d là vô hướng và In là ma trận đồng nhất kích thước nxn . Hàm này đều có yêu cầu về tính thu nhỏ và nghiệm duy nhất . Nếu nó có tính thu nhỏ thì điểm cố định được tính bằng : (8) Trong hàm này , ma trận C có thể được chọn là C = cE mà không gây ra bất cứ vấn đề nào với bậc của điểm cố định . Hàm được mở rộng này sẽ được sử dụng ở phần sau . I.3.3 Điều kiện có tính thu nhỏ của các hàm . Tất cả ba loại hàm ở trên đều có cùng các yêu cầu về tính thu nhỏ . Bán kính quang phổ của một vài ma trận phải nhỏ hơn một . Đối với hàm ƒ(P) = APB + C thì dễ dàng để thấy rằng ρ(A) < 1 và ρ(B) < 1 thì cho ta một hàm có tính thu nhỏ , suy ra ρ(A)ρ(B) < 1 . Phần này chúng ta sẽ nghiên cứu làm như thế nào mà chúng ta có thể chắc rằng ρ(X) < 1 , trong đó X = [xij] là một ma trận kích thước nxn . Hai cách khác sẽ được thể hiện cùng với một trường hợp đặc biệt cho hàm ƒ(P) = AP + C . Trong việc mã hóa khối Fractal , quy phạm X , ||X|| , thường được sử dụng để mô tả tính thu nhỏ và các hàm được gọi là hàm có tính thu nhỏ nếu ||X|| < 1 . Bởi vì chúng ta có ρ(X) ≤ ||X|| thì trường hợp ||X|| < 1 là đủ nhưng không là điều kiện cần thiết cho ρ(X) < 1 . Trường hợp đặc biệt : ρ(X) < 1 < ||X|| thì được gọi là tính thu nhỏ . Bởi vì ||X|| < 1 là đủ nhưng không là điều kiện cần thiết cho tính thu nhỏ , nó sẽ không được sử dụng trong đây . I.3.3.1 . Các ma trận hình tam giác . Nếu ma trận X là ma trận có dạng tam giác thì giá trị riêng của X sẽ bằng với giá trị của các phần tử trên đường chéo .Vì thế , bằng việc giới hạn giá trị của các phần tử trên đường chéo lại thành : -1 < xij < 1 , (9) với i = 1,.., n , thì điều kiện ρ(X) sẽ được thoả mãn . Bằng cách chọn ma trận như là một ma trận dạng tam giác thì một vài kỹ thuật nén cũng sẽ được thực hiện . Tuy nhiên , số lượng các ma trận khả thi X cho điểm cố định sẽ bị mất . Điều này không quá quan trọng đối với bởi vì K có nhiều mức tự do . Nhưng đối với ƒ(P) = AP + C , chỉ có một ma trận cho P* = P0 và vì thế A có lẻ không là một ma trận tam giác . Cuối cùng , ƒ(P) = APB + C là khả thi để tìm ra hai ma trận tam giác A và B , đáp ứng được điều kiện số hai được nêu ra ở trên , nhưng nó sẽ có lẽ không thoả mãn được điều kiện 3 . Vì thế , ma trận dạng tam giác được sử dụng tốt nhất trong trường hợp vector , . I.3.3.2 . Giám sát các giá trị của từng phần tử . Một cách khác để quản lý giátri riêng của một ma trận là giữ chúng ở mức thấp . Các quan hệ sau tồn tại giữa những phần tử của một ma trận và bán kính quang phổ của chúng : (10) (11) Một cách để thực hiện điều này là sự khắt khe trong việc giới hạn các phần tử bởi : < xi,j < (12) Chúng tasẽ kiểm tra một cách dễ dàng trong việc tìm ra ma trận A và B đối với hàm ƒ(P) = A(P – C + dIn)B + C trong khi vẫn giữ giá trị của các phần tử trong trong khoảng . Điều này sẽ cho thấy một cách rõ ràng là tại sao chúng ta sử dụng hàm mở rộng mà không sử dụng hàm gốc ƒ(P) = APB + C . Chúng ta sẽ sử dụng LU-Factorization ( nhưng một loại Factorization khác cũng có thể được sử dụng ) . Giả sử rằng điểm cố định có thể đạt được độ gần đúng nhất bởi hai điều kiện sau : Pt = C + dAB (13) Giả sử cho trước một ma trận C , chúng ta tính thừa số LU ( LU-Factorize) RtLU = P0 – C (14) Trong đó , R là ma trận hoán vị , L là ma trận tam giác nữa dưới và U là ma trận tam giác nữa trên . Sau đó , thiết lập Pt = P0 ta có : dAB = RtLU (15) Chúng ta hãy định nghĩa hai vô hướng lmax va umax lmax > | Li,j | (16) và umax > | Ui,j | (17) Chúng ta có thể chọn ma trận A , B và vô hướng d như sau : (18) (19) (20) Điều này sẽ cho ta một hàm có tính thu nhỏ bởi vì giá trị của tất cả các phần tử trong ma trận A và B sẽ luôn nằm trong một khoảng nhất định . Ta sử dụng ảnh Lena như là ảnh gốc P0 và thiết lập C = cE như là giá trị trung bình của P0 . Sau đó , chúng ta sẽ có ρ(A) ρ(B) = 4.1 – 10-5 . Điều này có nghĩa là chúng ta thực hiện sự thu nhỏ rất tốt . Thật sự là chỉ cần một lần lặp là đủ khi tái tạo lại hình ảnh . Hình 14a thể hiện ảnh ban đầu Pt và hình 14b thể hiện kết quả của ƒ(Pt) . Thử nghiệm này thì không thoả mãn được điều kiện 3 nhưng nó cho thấy giá trị của các phần tử là quan trọng có liên quan đến tính thu nhỏ . Còn với các điều kiện khác thì có thể được áp dụng cho các phần tử đó . Trong ví dụ này với ma trận tam giác thì hầu hết các phần tử có giá trị 0 nhưng một vài phần tử có thể có giá trị cao hơn và vẫn thỏa mãn được điều kiện (10) và (11) . Hình 14a . Aûnh với Pt Hình 14(b) . Ảnh với ƒ(Pt) . I.3.4 . So sánh với một vài phương thức mã hóa khác . I.3.4.1 .Mã hóa Run-length . Đây là kỹ thuật mã hóa không mất được sử dụng trên source với sự xuất hiện liên tục bằng các kí tự . Một sự mã hóa sẽ cho ta hai phần tử , chiều dài của sự liên tục và kí tự trong sự liên tục đó . Cho ví dụ , việc mã hóa của source p1,p1,p3,p3,p3,p3,p7,. Sẽ là (p1,2) , (p3,4) Nếu chúng ta thay bằng cách sử dụng hàm để mô tả điều này , chúng ta sẽ có một ma trận chuyển đổi như sau ; (21) Và vector chuyển đổi là : (22) Chúng ta thấy rằng ma trận luôn luôn được cố định thành ma trận band ( band matrix ) và tất cả các thông tin đều nằm trong một vector . Hơn nữa , vector có thể được biểu diễn (p1,2) , (p3,4) giống như là mã hóa run-length . Điều này sẽ cho ta một hàm có tính thu nhỏ bởi vì với i = 1, 2, ,n2 . Thực sự là như thế bởi vì ta có ||K|| ≥ 1 . Nó sẽ thực hiện n2 lần lặp trước khi điểm cố định được tính ra bởi vì chỉ một phần tử trong P* là được tính trong mỗi lần lặp . Nếu nghiên cứu K , ta sẽ thấy rằng ta có ||Ki|| ≥ 1 với i = 1, ., n2 – 1 và |||| < 1 . Thay cho việc lặp , chúng ta có thể sử dụng quá trình đơn giản hóa (34) để tái tạo lại hình ảnh . I.3.4.2 . Mã hóa Ziv-Lempel . Đây cũng là một kỹ thuật mã hóasource không mất giống như mã hóa run-length . Nó sử dụng chuỗi các kí tự được mã hóa để mã hóa chuỗi các kí tự tiếp theo . Các kí tự được mã hóa sau cùng thì được lưu vào vùng đệm có chiều dài L . Một từ mã ( codeword ) mô tả nội dụng gồm ba phần . Phần tử đầu tiên chứa toạ độ của kí tự đầu tiên trong vùng đệm như là những kí tự mà chúng ta cần mã hóa . Thành phần thứ hai cho biết chiều dài của chuỗi các kí tự so khớp và là phần chúng ta muốn mã hóa . Nếu nó được được thiết lập là 0 thì kí tự được mã hóa kế tiếp không được cấp phát trong vùng đệm . Thành phần cuối cùng thì chứa các kí tự sinh ra sau khi các kí tự đã được so khớp . Sự xuất hiện của từ mã (0,0,pj) cho ta một hàng toàn bằng 0 trong K và phần tử pj trong . Số phần tử không bằng 0 còn lại trong ma trận K sẽ hầu hết bằng 1 , giống với mã hóa run-length . Nếu ma trận K có một phần tử khác 0 trong một hàng thì một hàng giống như thế sẽ bằng 0 trong . Từ mã ( L – ( L – 1 ) ,1,pj+2) sẽ cho một hàng đều bằng một trước các phần tử trên đường chéo trong K . Trên một hàng kế tiếp , tất cả các phần tử trong K đều bằng 0 và sẽ chứa pj+2 . Từ mã ( L – ( L – 2 ) ,2,pj+5) sẽ cho sáu hàng trong ma trận chuyển đổi K . (23) và cũng sáu hàng trong vector chuyển đổi . (24) Trong (43) , chỉ những phần tử khác không ( bằng 1 ) mới được thể hiện , còn các phần tử bằng 0 trong một vài trường hợp được thể hiện bằng chấm đứt . Ma trận chuyển đổi sẽ luôn là dạng tam giác với tất cả các phần tử trên đường chéo bằng 0 . Vì thế , hàm này sẽ có tính thu nhỏ như mã hóa run-length . I.3.4.3 . Mã hóa tiên đoán trước . Trong phương thức mã hóa có mất này , các giá trị trên điểm ảnh gần giống với các điểm ảnh thực mà chúng ta muốn mã hóa thì được sử dụng để dự đoán cho các giá trị của nó . Sau đó , chỉ một sai số nhỏ giữa giá trị được dự đoán và giá trị ban đầu là được truyền đi . Cho một ví dụ , điểm ảnh pi,j được dự đoán là từ 3 điểm ảnh được mã hóa gần nhất . Chúng ta chỉ sử dụng những điểm ảnh được mã hóa thực sự để tìm ra hệ nhân quả . Để ghi điều này ra như một bộ nén hàm , chúng ta đầu tiên phải thể hiện hình ảnh bởi một vector dạng cột bằng cách sắp xếp các cột trong ma trận ảnh . Sau đó , ma trận chuyển đổi được bố trí như sau : (25) và sai số được tập họp trong vector chuyển đổi : (26) Mã hóa tiên đoán trước cũng có thể là không mất , nghĩa là sai số chính xác được truyền đi . I.4. Lượng tử hóa . Là quá trình làm giảm đi số bit cần lưu trữ . Đây là quá trình khá quan trọng trong việc đạt được tỉ số nén cao . Ví dụ như với một thành phần có tám khả năng có thể xẩy ra . Với mỗi khả năng ta sử dụng một byte để lưu trữ => mất khoảng tám byte . Nhưng ta có thể tiết kiệm được không gian lưu trữ bằng việc sử dụng các bit trong một byte . 0 0 0 : khả năng 1 . 0 0 1 : khả năng 2 . 0 1 0 : khả năng 3 . 1 1 1 : khả năng 8 . Chính vì thế , ta chỉ cần 3 bit là đủ để giải quyết vấn đề trên . Quá trình lượng tử hóa không chỉ được sử dụng trong nén ảnh mà cũng được dùng rất phổ biến trong nén văn bản và âm thanh . I.5. Mã hóa Fractal với ảnh màu . Phần này đưa ra một phương pháp mã hóa ảnh màu dựa trên nền tảng hệ thống chức năng được lặp lại đều đặn ( Recurrent Iterated Function Systems ) – RIFSs . Để mã hóa một hình ảnh đa quang phổ , chúng ta áp dụng một RIFS để mã hóa dữ liệu bao gồm 3 lớp ảnh . Trong phương thức được đưa ra này , việc ánh xạ không chỉ giữa các khối vào một hình ảnh quang phổ riêng biệt mà còn giữa những khối các ảnh quang phổ khác nhau được thực hiện với sự ràng buột về tính thu nhỏ . Dựa theo các kết quả cho thấy rằng mã hóa Fractal dựa trên nền tảng RIFS là hữu ích cho việc mã hóa đồng thời một tập các ảnh bởi việc mô tả sự tồn tại giống nhau giữa một cặp ảnh . Thêm vào đó , việc đưa ra phương thức mã hóa ảnh màu có thể được áp dụng cho các ảnh subband và sự liên tục các ảnh động bao gồm tập các ảnh có thành phần sắc xám giống nhau . Image 1 Image 2 Image 1 Image 2 a . b. Hình 13 . IFS cho sự mã hóa hai ảnh . (a) ánh xạ nội bộ ( intramapping ) . (b) ánh xạ liên thông ( intermapping ) . Từ khi những ý tưởng về mã hóa ảnh Fractal được thể hiện thì các loại kỹ thuật mã hóa đạt được sự gần đến với hình ảnh phẳng lặng và liên tục đã được phát triển . Khái niệm về sự hấp dẫn của Fractal thể hiện trong ảnh tự nhiên bởi một qui luật rất đơn giản , mã hóa ảnh Fractal tận dụng tính tự giống nhau đang tồn tại trong ảnh . Chất lượng ảnh được tái tạo lại bằng kỹ thuật mã hóa Fractal thì phụ thuộc vào cách diễn tả của tính tự giống nhau đó . Để thể hiện tính tương tự nhau , một sự chuyển đổi giữa hai khối ảnh sẽ được thực hiện . Đối với việc mã hóa ảnh liên tục , subband và ảnh màu thì mỗi một tập các ảnh sẽ được xem như là một bộ phận của một bộ IFS , và mỗi thành phần thì được mã hóa độc lập bằng phương thức mã hóa Fractal thông thường . Trong phương thức được đưa ra dựa trên nền tảng một IFS tái diễn liên tục ( RIFS) , một tập các hình ảnh được mãhóa cùng một lúc . Trong đó sự ánh xạ không chỉ giữa các khối trong cùng một hình ảnh mà còn có thể giữa các ảnh khác nhau . Nếu sự tương tự tồn tại giữa bất kỳ một cặp nào trong hình ảnh thì phương thức dựa trên RIFS sử dụng sự tương tự đó ánh xạ lẫn nhau . Vì thế , phương thức mã hóa ảnh Fractal dựa trên nền tảng RIFS là thích hợp cho việc mã hóa ảnh liên tục , subband và màu . Bằng việc mô phổng trên máy tính , chúng ta nghiên cứu các tính chất của phương thức mã hóa trên nền tảng RIFS cho các ảnh đa quang phổ như là ảnh màu RGB và YCbCr . Ngoài ra , kỹ thuật mã hóa ảnh Fractal dựa trên IFS được áp dụng độc lập cho mỗi hình ảnh đa quang phổ và sự thực thi này được so sánh với giải thuật được đưa ra dựa trên RIFS . I.5.1 . Hệ thống hàm được lặp lại liên tục (Recurrent Iterated Function Systems ) . Chúng ta hãy xem xét một IFS được xác định giữa hai ảnh . Chúng ta có thể mã hóa một cách đơn giản mỗi hình ảnh một cách độc lập bằng một IFS , Wj , j = 1,2,. như là hình 1a . Ngoài ra , trên hình 1b , một IFS giữa hai ảnh khác nhau được thiết lập . hình 1a mô tả những điểm tương tự nhau trong một hình ảnh , ngược lại , hình 1b lại mô tả sự tương tự đó nhưng giữa hai ảnh khác nhau . Trong những hình ảnh đa quang phổ như là các ảnh màu , mỗi hình ảnh có 3 lớp domain : ảnh R , G và B . Mỗi ảnh đa quang phổ đó có intersimilariy tương tự như là intersimilarity . intersimilarity giữa các ảnh là một đặc tính quan trọng cho việc xây dựng lại ảnh của RIFS . Thật vậy , các ảnh đa quang phổ có nét tương tự trên các ảnh đơn quang phổ khác nhau trong điều kiện mẫu có bề mặt sắc xám ( gray surface ) . Một RIFS W : H à H với bộ dữ liệu n thuộc tập con không rỗng ( nonempty ) ( B1 ,B2 , , Bn) được định nghĩa bởi (26) trong đó H = H1 x H2 x x Hn . Ở đây , Hi là một tập của các tập con không rỗng của complete metric space Xi với metric Hausdorff hi được liên hợp của nó . Mỗi Wij : Hi à Hj của RIFS W được cho bởi : , (27) trong đó , Wij biểu diễn ánh xạ từ Bi đến Bj . Với i = j , Wij biểu diễn một intramapping do một IFS thông thường xác định . Sự thu nhỏ s của RIFS W được cho là maximun của tính thu nhỏ wijk . Tập (B1, , Bn) , bao gồm một vài các quang phổ khác nhau được xem như làmột vector ảnh đơn trong RIFS . Vector ảnh này có hai loại mẫu sắc xám ( hoặc đơn quang phổ ) bên trong một hình ảnh : sự tự giống nhau ( seft – similarity ) thông thường thì được xác định bên trong ảnh cho trước và tính tương tự quang phổ , cái mà mô tả quan hệ giữa một cặp ảnh đơn quang phổ khác biệt nhau . I.5.2. Các phương thức mã hóa Fractal cho ảnh màu . Có một vài kỹ thuật khá tốt để mã hóa ảnh đa quang phổ dựa trên RIFS . Do một vài sự hạn chế , ở đây ta chỉ quan tâm đến ảnh RGB và YCbCr . Phương thức đơn giản nhất là áp dụng IFS riêng rẽ cho mỗi thành phần của ảnh đa quang phổ . Phương thức này xem mỗi ảnh đa quang phổ như là một ảnh độc lập đơn giản . Đây là trường hợp đơn giản nhất của RIFS , và nó không tận dụng được sự dư thừa tồn tại giữa những ảnh đơn quang phổ khác nhau . Trong việc mã hóa ảnh màu , sự tương quan giữa ba lớp ảnh là một đặc tính cơ bản và quan trọng . Chính vì thế , phương thức này thật sự không hiệu quả . Một phương thức khả thi khác có thể được áp dụng để mã hóa ảnh liên tục . Thay cho ba lần ánh xạ Fractal 2-D , nó chỉ dùng một lần ánh xạ 3-D bằng cách xem một tập ảnh như là một vùng 3-D được thể hiện bằng tọa độ không gian (x,y) và tọa độ quang phổ (c) . Bởi vì phải xử lý một số lượng lớn các pixel trong một vùng cho nên phương pháp này cần nhiều thông số để bảo đảm chất lượng ảnh khi ảnh được tái tạo lại . Một trường hợp đặc biệt của RIFS là sử dụng cùng một địa chỉ domain cho ba ảnh khác nhau và xem pixel như là một vector bao gồm ba thành phần là đỏ , xanh lá cây và xanh dương . Nhân tố mức ( scaling ) và giá trị độ chói được tính cho mỗi ảnh đơn quang phổ . Nó sử dụng sự tương quan giữa ba thành phần đơn quang phổ bằng việc vector hóa . Trong trường hợp mã hóa ảnh Fractal dựa trên RIFS , ba ánh xạ được xác định cho ba thành phần của ảnh màu RGB . Cho ví dụ , một khối domain tương ứng với một khối range của thành phần màu đỏ được tìm kiếm đầu tiên trong Domain Block Pool màu đỏ , nơi chính là phiên bản thu nhỏ của ảnh màu đỏ . Sau đó , các thành phần màu xanh dương và xanh lá cây được dùng tiếp như là Domain Block Pool thứ 2 và thứ 3 . Domain Block Pool sinh ra sai số khoảng cách nhỏ nhất giữa ba Domain Block Pool thì sẽ được chọn như là một địa chỉ của khối domain thích hợp . Hình 14 thể hiện tất cả ánh xạ intermapping và intramapping mã hóa ảnh màu RGB . Hình 15 . Các ánh xạ intermapping và intramapping . I.5.3. Những kết quả mô phổng và đánh giá. Hình ảnh Lena , kích thước 512x512 , lượng tử hóa ở mức 24bit . Sự thực thi của phương thức mã hóa dựa trên RIFS được so sánh với phương thức IFS . Việc so sánh này sử dụng cùng một hàm thu nhỏ . Những kết quả mô phổng thể hiện tính chất của intramapping , intra- và intermapping và vector hóa . Để áp dụng qui tắc của IFS , Jacquin giới thiệu công nghệ mã hóa khối ( block-coding ) dựa trên những sự chuyển đổi ảnh có tính thu nhỏ được lặp lại . Sự biến đổi hình ảnh bao gồm các phần hình học và các khối . Trong cách thực hiện của chúng ta , giá trị trung bình của các khối domain được sử dụng như là phép toán thu nhỏ không gian và sự ánh xạ khối Ck được xác định bởi : (28) Công thức trên được sử dụng cho phần khối , trong đó và biểu diễn khối range thứ k và khối domain tương ứng với nó của mỗi mặt đơn quang phổ , ứng với từng vị trí . Hằng số là nhân tố thang đo được lượng tử thành 5 bit . Kí hiệu và thể hiện mức trung bình của các khối domain và range . Các ánh xạ cùng kích thước ( isometric mapping ) thì không được sử dụng , và được lượng tử hóa với 7 bit . Đối với phương thức mã hóa dựa trên RIFS , domain tìm các khối được giới hạn trong vùng 15x15 gần nhất , trung tâm tương ứng với khối range , và vùng tìm kiếm của ảnh đơn quang phổ khác sẽ được chọn với cùng phương thức . Để có được một tỉ lệ nén ổn định cho từng phương thức , một vùng tìm kiếm 31x31 được sử dụng cho phương thức sử dụng IFS . Tuy nhiên , vẫn phải sử dụng thông tin địa chỉ domain thông thường cho ba lớp màu . Vì thế , các phương thức dựa trên IFS và RIFS có tỉ lệ bit khá tốt . Mỗi lớp của RGB có cùng độ phân giải , ngược lại YCbCr thì có độ phân giải lần lượt là 4 : 2 : 0 . Chính vì thế , vị trí (x,y) của ảnh đơn quang phổ Y tương ứng là (x/2,y/2) của Cb và Cr . Các khối domain khả thi bên trong vùng tìm kiếm sẽ được sử dụng để chọn ra một khối domain tốt nhất , dựa trên việc tính tổng của các sai số bình phương . Sự thực thi của mỗi phương thức được so sánh trong điều kiện của tỉ lệ bit , PSNR ( Peak Signal-to-Noise Ratio ) và PSNR trung bình ( Average PSNR – APSNR ) . PSNR được xác định bởi : trong đó , SE biểu thị tổng bình phương các sai số của mỗi thành phần và Np là số lượng pixel . Tương tự , APSNR cũng được xác định bằng : trong đó , TSE là tổng của các SE , và Nc là số thành phần màu . Chúng ta sử dụng khối range 8x8 và khối domain là 16x16 . Phương thức mã hóa Fractal dựa trên IFS và RIFS sử dụng các mẫu sắc xám của một hình ảnh gốc như là thông tin về hình dạng ; vì thế , giá trị sắc xám chính xác là không cần thiết và vùng domain chất lượng cao không phải là tới hạn của ánh xạ Fractal đáng tin cậy . Sự tồn tại của các mẫu giống nhau thì quan trọng hơn là chất lượng của các vùng domain . Vì thế , chúng ta lấy mẫu con từ hình ảnh theo chiều ngang và dọc bởi hệ số hai và sử dụng trị bình quân của bốn pixel trong việc phát sinh ra domain pool đã được tinh giảm. Bảng 1 cho thấy tỉ lệ bit , PSNR và APSNR của phương thức dựa trên IFS , RIFS của ảnh lena bằng RGB và YCbCr . Trong việc mã hóa ảnh màu YCbCr , thành phần Cb và Cr được lượng tử hóa trong cùng một bảng lượng tử hóa , bởi vì chúng cho thấy các đặc tính tương tự trong việc phân tích sự mô phổng . Việc cấp phát bit tối ưu cho YCrCb bằng cách xem xét độ ưu tiên của mỗi thành phần đơn quang phổ là không được tính toán . Vì thế , bảng 4 chỉ thể hiện các đặc tính của intra-và intermapping cho bộ màu RGB và YCbCr dưới cùng một điều kiện . Bảng 4 . PSNR và APSNR cho ảnh RGB và YCbCr. Sự mô phổng việc tính toán trên đây cho thấy PSNR của ảnh RGB ( YCbCr ) được tái tạo lại bằng phương thức dựa trên RIFS thì lớn hơn là IFS , với 0.31 và 0.7 dB . Sự gia tăng APSNR của bộ màu YCbCr thì cao hơn là bộ màu RGB . Trong RIFS , hai bit thêm vào là cần thiết để thể hiện vùng domain được chọn . Tuy nhiên , phương thức dựa trên RIFS cần tìm nhiều vùng domain hơn là IFS . Trong cùng một vùng tìm kiếm , RIFS sẽ mất khoảng thời gian gấp ba lần IFS , bởi vì RIFS tìm kiếm đến ba vùng domain . Thời gian tính toán có thể được làm giảm bằng việc tính toán song song cùng lúc . Bảng 5 . Thời gian chọn của các vùng màu . Bảng 5 thể hiện tỉ lệ phần trăm thời gian mà mỗi thành phần của ba quang phổ đơn được chọn như là một vùng domain . Chúng được chọn với các đặc tính tương tự đối với ảnh RGB , điều đã nói với chúng ta rằng ảnh đa quang phổ có tính tương tự không chỉ bên trong chính nó mà còn ở giữa các quang phổ đơn . Đối với ảnh màu YCbCr , bởi vì vùng range của các thành phần màu và vùng domain của quang phổ độ chói có cùng một độ phân giải . Thành phần độ chói Y chủ yếu là được chọn như là một khối domain cho việc mã hóa thành phần Y và cũng tốt như đối với Cr và Cb . II . Lược đồ Giải mã . Bộ Giải Nén FRC file Lặp i Lần TGA file Hình 16 . Lược đồ giải mã . I .1. Lược đồ giải mã . Một RIFS được tạo ra với giải thuật ở trên bao gồm một danh sách các ánh xạ affine , mỗi ánh xạ được chỉ định là của một range . Bởi vì mỗi ánh xạ là hội tụ ở chiều độ chói ( nhân tố tương phản nhỏ hơn một ) , chúng ta có thể ứng dụng định lý ánh xạ hội tụ ( Contractive Mapping theorem ) để giải mã hình ảnh . Bắt đầu từ một hình ảnh bất kỳ , người giải nén có thể áp dụng lặp một RIFS , tiến trình này sẽ hội tụ về một điểm cố định của RIFS . Nếu bộ nén tìm ra một RIFS tốt cho ảnh này thì nghĩa là nếu việc cắt dán của tất cả các domain đã được chuyển đổi gần với hình ảnh ban đầu thì điểm cố định của RIFS cũng gần với ảnh ban đầu này . Để thực hiện việc lặp lại một RIFS , người giải nén lấy danh sách các ánh xạ affine và áp dụng nó cho mỗi lần chạy . Điều này chuyển đổi một tập các domain sang một tập các range . Bởi vì các range đã được chọn là không chồng lấp và bao phủ toàn bộ ảnh nguồn , kết quả là một ảnh mới hoàn chỉnh hiện ra . Người giải nén có thể sau đó lặp lại toàn bộ quá trình cho đến khi sự hội tụ được hoàn thành , nghĩa là cho đến khi có rất ít sự khác biệt giữa hình ảnh vào và hình ảnh kết quả . Việc hội tụ nói chung là đạt được từ 6 – 10 lần lặp . Bây giờ chúng ta có thể hiểu rõ hơn là tại sao các ánh xạ affine được chọn là thu nhỏ trong cả 2 chiều : độ chói và không gian . Việc thu nhỏ trong chiều độ chói là cần thiết để chắc rằng quá trình giải nén là hội tụ . Thu nhỏ không gian là hữu ích để tạo ra sự chi tiết trong hình ảnh tại bất kỳ mức nào , và vì thế ta có sự xấp xỉ tốt nhất với hình ảnh ban đầu . Không có hội tụ không gian thì tiến trình vẫn hội tụ nhưng nó sẽ hội tụ thành một ảnh dạng khối ( blocky ) , và không có bất kỳ độ tương phản nào trong mỗi khối đó . Với thu nhỏ không gian , độ tương phản sẽ xuất hiện trên tất cả các range , khởi đầu bởi thành phần ánh sáng trong các ánh xạ affine , được đưa vào trong mỗi khối range để ngày càng ít đi sự khác biệt sau mỗi lần lặp . Chúng ta hãy quan sát hình “Lena” . Ở lần lặp đầu tiên , các chi tiết đã dần lộ ra . Đến lần thứ hai thi chúng càng rõ hơn và đến lần thứ 8 thì chúng ta đã có một ảnh hoàn chỉnh , tương đương với hình ảnh ban đầu . Hình 17 . Ảnh sau một , hai ,,và tám lần giải nén . I.2 . Sự phụ thuộc độ phân giải . Để khởi tạo lại một hình ảnh , người giải nén bắt đầu lặp với một hình ảnh tùy ý có cùng kích thước với hình ảnh ban đầu . Nhưng điều gì sẽ xẩy ra nếu người giải nén bắt đầu với một hình ảnh lớn gấp 2 lần ảnh ban đầu ? Kết quả của quá trình giải nén cũng sẽ là một ảnh lớn gấp 2 lần ảnh ban đầu . Tuy nhiên , bởi vì các ánh xạ affine được sử dụng để mã hóa hình ảnh thì không phụ thuộc vào độ phân giải cho nên việc giải nén sẽ không bị khối ( blocky ) , điều này chúng ta sẽ đạt được nếu chúng ta có bản sao đơn giản các điểm ảnh của hình ảnh nguồn . Nó vẫn có được sự chi tiết tại bất kỳ mức nào . Quan sát ảnh “Lena” được giải nén lớn hơn gấp 4 lần và ảnh “Lena” được phóng to gấp 4 lần . Ta thấy ảnh được giải nén trông chi tiết hơn , rõ ràng hơn là ảnh được phóng to . Có sự khác biệt như thế vì trong quá trình giải nén ảnh , một số các chi tiết giả tạo đã được đưa vào ảnh , làm cho ảnh trông rõ ràng vàmịn màng hơn , điều mà khi chúng ta không thể có được khi phóng to ảnh . Hình 18a . Ảnh Lena được giải nén lớn gấp 4 lần . Hình 18b . Ảnh Lena được phóng to gấp 4 lần . Hình ảnh thu được thông qua việc giản nén Fractal thì trông tự nhiên hơn . Quá trình giải nén sẽ tạo ra những chi tiết giả tạo , điều mà không thấy xuất hiện trong hình ảnh gốc , nhưng chúng ta sẽ thật sự nhìn thấy khi chúng được phóng to . Đây là một đặc tính hữu ích nhưng nó cũng có giới hạn . Nếu chúng ta cố gắng phóng to quá lớn , chúng ta sẽ không thấy được các mãnh nhỏ trên bề mặt ảnh , nhưng hơn nữa là chúng ta sẽ thấy được các chi tiết giả tạo . Tỉ lệ nén được đưa ra trước bởi chủ trương của nén Fractal có thể nhỏ bé trong một vài trường hợp . Giả sử rằng một ảnh có kích thước 320x200 pixel , với kích thước ban đầu là 64KB , đã được nén với tỉ lệ nén là 32 : 1 . Kết quả sau khi nén là 2KB . Bây giờ giải nén hình ảnh này với mức 4 ( scale factor = 4 ) . Nó sẽ tạo ra một hình ảnh có kích thước là 1280x800 pixel , với kích thước sau khi giải nén là 64x16 = 1024 KB . Vì thế nó sẽ có tỉ lệ nén là 1024/2 = 512 : 1 , điều này là sai . Lý do là hình ảnh được giải nén đã chứa các chi tiết giả tạo , cái mà không có thể hiện ở hình ảnh gốc . Nhưng thông tin gốc vẫn sẽ được nén với tỉ lệ 32 : 1 , phần còn lại của các thông tin được tạo ra một cách giả tạo bởi quá trình giải nén . CHƯƠNG V Thiết Kế Chương Trình Các Module chính . Lưu đồ chương trình . Chi tiết tại mỗi bước . Lưu đồ khối chức năng . I . Các module chính . Chương trình được viết bằng ngôn ngữ Java , sử dụng các gói Javax.swing để lập trình giao diện . Bởi vì được viết bằng java cho nên nó có khả năng tương thích rất cao đối với các hệ điều hành khác như Linux , Macintos , Lindow Phần mềm bao gồm các chức năng nén và giải nén file , thiết lập cấu hình nén và giải nén thông qua một file nền và một form giao diện . Phần mềm có khả năng nén một hoặc nhiều file “ *.tga ” và giải nén nhiều file cùng lúc . Chương trình gồm có 11 module chính ( thực hiện quá trình nén và giải nén file ) và các module con ( cho phần giao diện ) bao gồm : FCSubheader,FCHeader : là module lưu giữ các header của file đã được nén (*.FRC) bao gồm các thông tin cho quá trình giải nén . FCfile : đây là lớp dùng để đọc và ghi thông tin , lưu trữ các cấu trúc dùng cho FRC file . FCPixelpool : lớp lưu giữ các pixelpool , chuyển đổi các thông tin về màu rgb thành các mãng dữ liệu để xử lý . FCRange : Lưu các range sau khi đã được phân chia và chuyển đổi thành kiểu dữ liệu mãng hai chiều . FCDomain, DCDomainPool : Lưu giữ tất cả các domain và các phương thức để tìm ra một domain tốt nhất cho việc chuyển đổi . FCEncoder , FCEncoderInfo : Đây là module chính của quá trình mã hóa file . FCEncoderInfo chứa các thông tin , cấu hình cho việc mã hóa và FCEncoder mã hóa các dữ liệu và ghi vào file FRC . FCDecoder , FCDecoderInfo : Hai module này cũng giống hai module trên , bao gồm các thông tin , cấu hình và qui trình giải mã cho các file FRC . Các module còn lại là các module dùng cho việc thiết lập các giao diện người dùng . II.Lưu đồ chương trình. Lược đồ nén Lược đồ giải nén III. Chi tiết tại mỗi bước . IV.Lưu đồ khối chức năng . CHƯƠNG VI Thử Nghiệm So Sánh & Hướng Phát Triển Thử nghiệm . So sánh với một vài phương thức mã hóa thông dụng hiện tại . Ưu khuyết điểm và hướng phát triển . I . Thử nghiệm . Thử nghiệm được thực hiện trên các ảnh ngẫu nhiên , bao gồm ảnh Grayscale và ảnh màu RGB . Thử nghiệm sẽ nén các ảnh ở các mức ( chất lượng ) khác nhau và được giải nén ở cùng số lần . Sau đây là bảng so sánh ảnh “sunset.tga”, kích thước ban đầu là 57KB , cấu hình máy P4 1.7GHz . Ảnh được nén ở hai dạng là màu ở độ phân giải 160x120x24b và grayscale là 160x120x8b . Quality Image GrayScale Color Compression Time (s) Ratio (%) Compression Time (s) Ratio (%) 1 0.3 99.601 0.5 99.55 2 0.5 99.6008 0.8 99.43 3 0.7 99.6077 1 99.44 4 1 99.37 3 98.67 5 2 99.32 7 98.37 6 3 99.23 14 97.04 7 5 99.2 40 95.99 8 7 99.04 60 93.98 9 20 98.85 90 91.54 Bảng 6 . Thể hiện thời gian nén và tỉ lệ nén . Từ bảng trên , ta thấy với phương pháp nén ảnh phân đoạn thì ta luôn có một tỉ lệ nén tuyệt vời . Nhưng bù lại , thời gian nén khá cao cũng là một nhượt điểm của phương pháp này . Khi nén ảnh grayscale thì ta luôn có thời gian cùng tỉ lệ nén vượt trội hơn so với khi nén ảnh màu . Điều này được giải thích là : vì nén ảnh màu phải mã hóa 3 lớp màu cùng với nhiều thông số lưu trữ cho việc tái tạo lại ảnh nhiều hơn là ảnh grayscale . Theo như nhận xét thì nén ảnh với quality = 7 là đạt được chất lượng ảnh rất tốt ( gần 96% so với hình ảnh gốc ) . Còn với các mức quality còn lại là không cần thiết . Với các mức quality thấp hơn , ta sẽ thấy hình ảnh rất tệ , hay bị “blocky” ở một vài vùng . Còn với các mức quality cao hơn thì có rất ít sự khác biệt , với mắt thường thì ta khó lòng phân biệt được . II. So sánh với một vài phương thức mã hóa thông dụng hiện tại . Ở đây , ta sẽ so sánh với hai phương thức nén ảnh phổ biến nhất , đó là file GIF và JPG . Việc so sánh được thực hiện trên ba file ảnh ngẫu nhiên khác nhau là sunset.tga , lena.tga và water.tga . Ba file đều có cùng độ phân giải 160x120x24b và kích thước 57KB . Máy có cấu hình P4 1.7 , 256MB RAM . 1.Thời gian nén . Ảnh màu . Ảnh GrayScale . 2.Thời gian giải nén . Ảnh màu . Ảnh GrayScale 3.Tỉ số nén . Ảnh màu . Ảnh GrayScale . Qua ba biểu đồ so sánh trên ta thấy rằng nén Fractal rất lợi điểm về tỉ số nén . Trong một vài trường hợp ( nhất là đối với ảnh GrayScale ) , ta có thể đạt được tỉ số nén gần như tuyệt đối ( 98% ) . Còn với file JPG và GIF thì không thể vượt qua được tỉ lệ ngưỡng (93%) . Đây là một sự hữu ích của Fractal . Ngược lại về tỉ số nén thì nén Fractal vẫn còn khá chậm so với hai phương thức trên trong quá trình nén ảnh màu , và tương đối so với ảnh GrayScale . Nén JPEG dùng cơ chế chuyển đổi DCT ( Discrete Cosin Transform ) dựa trên nền tảng các biến đổi Fourier nên cho tốc độ khá nhanh ( tham khảo thêm ở sách “Data Compression Book” của Mark Nelson và Jean-Loup Gailly) . Nén GIF thì dùng giải thuật nén LZW với việc chuyển đổi một dãy các giá trị pixel thành giá trị số để lưu trữ . Phương pháp này cho ta tốc độ rất nhanh ( tham khảo thêm trong GIF Format có rất nhiều trên net ) . So sánh về tốc độ giải nén thì các giải thuật có tốc độ ngang nhau . Fractal chỉ chậm hơn một ích với ảnh màu và tương đương với ảnh GrayScale . Nói về chất lượng ảnh thì hình ảnh được tái tạo lại với Fractal thì rất tốt , sánh ngang với JPG file và cũng không thua gì GIF file . Ngoài việc đạt được tỉ số nén cao , Fractal còn rất có lợi trong việc phóng to hay thu nhỏ ảnh . Với các phương pháp nén khác thì ta không thể phóng to ảnh ngoài việc trợ giúp của các phần mềm xem ảnh phổ biến . Thêm vào đó , ảnh khi được phóng to sẽ bị “blocky” , có nghĩa là các chi tiết ảnh sẽ có dạng khối vuông , hình ảnh không còn mịn màng như lúc ban đầu . Ngược lại ,Fractal không những có khả năng phóng to được ảnh còn tạo cho ảnh độ tự nhiên , mịn màng rất tốt . Đây là một thế mạnh của phương pháp nén ảnh Fractal . III.Ưu khuyết điểm và phương hướng phát triển . Chương trình được viết bằng ngôn ngữ java nên có tính phổ biến rộng rãi . Giao diện thân thiện người dùng và dể dàng sử dụng . Các file được nén có tỉ số nén rất cao , phù hợp với khả năng lưu trữ hữu hạn của phần cứng . Ngoài ra chất lượng nén cũng rất tốt , có thể dể dàng phóng to thu nhỏ ảnh mà không làm mất đi sự tự nhiên vốn có của ảnh . Giao diện chương trình được viết cho việc tích hợp thêm các giải thuật nén khác một cách dễ dàng nhất . Mặc dù đã rất cố gắng nhưng chương trình ngoài những ưu điểm đạt được vẫn chưa được hoàn chỉnh và còn nhiều khuyết điểm . Khuyết điểm lớn nhất của chương trình là tốc độ thực thi còn khá chậm và đây là một điều thật sự cần được cải tiến trong tương lai . Vì giải thuật được thực hiện chủ yếu là trên các ma trận nên việc cải tiến tốc độ có hai khả năng . Phân loại domain vào các lớp domain , từ đó , các range chỉ phải so sánh với các domain thuộc cùng lớp với mình , giảm đi được rất nhiều thời gian so sánh . Tinh chỉnh để tăng tốc các vòng lặp cùng với việc dùng ngôn ngữ khác có hổ trợ mạnh cho việc tính toán ma trận như là ngôn ngữ Matlab . Cùng với việc tăng tốc chương trình thì việc cải tiến phần mềm cũng rất đáng được quan tâm . Hiện nay , chương trình chỉ mới hổ trợ cho file *.tga . Trong tương lai sẽ hổ trợ thêm cho các file *.bmp , *.raw Cùng với việc tăng thêm các chức năng cho phần mềm như tạo gói , view inside hoặc outside Cuối cùng là tích hợp với các giải thuật nén văn bản và âm thanh khác để tạo thành một chương trình nén hoàn chỉnh . CHƯƠNG VII Kết Luận Trong quá trình tìm hiểu kỹ thuật nén ảnh bằng phương pháp phân đoạn , cơ bản đồ án đã tìm hiểu được kỹ thuật nén ảnh nói chung và kỹ thuật nén phân đoạn nói riêng . Đồ án cũng đã thực hiện được gần đầy đủ các yêu cầu đặt ra như nén , giải nén ảnh , cấu hình nén cùng với giao diện được viết mở rộng cho việc tích hợp các kỹ thuật nén khác . Với việc tìm hiểu quá trình phân đoạn , sử dụng hàm ( chuyển đổi affine ) để mã hóa (ảnh Grayscale lẫn ảnh màu ) , lượng tử hóa thông tin cho thấy hiệu suất nén phụ thuộc như thế nào vào các quá trình này . Đồ án cũng so sánh được các ưu điểm vượt trội so với các phương pháp nén khác đang có mặt trên thị trường . Tuy nhiên , phương pháp nén nào cũng tồn tại các ưu khuyết điểm của nó và còn tùy thuộc vào kiểu file cần nén , mục đích của việc nén . Quá trình thực nghiệm đã cho thấy nén Fractal có hiệu suất nén vượt trội hẳn các phương pháp nén khác . Tuy nhiên , nó tỏ ra khá chậm vì phải thực hiện việc so sánh giữa các range và domain cùng với các biến đổi khá phức tạp . Trong môi trường bùng nổ thông tin như hiện nay , việc lưu trữ ảnh đối với các cơ sở dữ liệu là một thách thức lớn . Do đó , việc sử dụng giải pháp nén là rất cần thiết . Ở đây , đồ án chỉ đi sâu vào việc nghiêng cứu một phương pháp nén ảnh hiệu quả về hiệu suất nén nên có một số phần hạn chế so với các kỹ thuật nén khác trên thị trường . Do đó , hướng phát triển của đồ án là cải thiện hơn nữa tốc độ chương trình , mở rộng ra cho các file ảnh khác như *.bmp , *.raw cùng với việc tích hợp thêm các giải thuật nén văn bản và âm thanh để chương trình trở nên hoàn thiện hơn , đáp ứng được nhu cầu ngày càng đa dạng ở nước ta . Tuy nhiên , do kinh nghiệm còn hạn chế , việc tiếp cận các kỹ thuật nén trong thời gian ngắn nên không tránh khỏi những sai sót nhất định , việc tìm hiểu chưa thật sâu sắc tất cả các khía cạnh . Rất mong sự góp ý của các thầy cô và các bạn để chương trình ngày càng hoàn chỉnh hơn . Xin chân thành cảm ơn . PHỤ LỤC Adaptive compression . Là công nghệ nén dữ liệu sử dụng một mô hình có thể hoặc sử dụng một mô hình cố định cho toàn bộ chuỗi được nén hoặc là hiệu chỉnh mô hình như là một chuỗi được xử lý . Một ví dụ cho công nghệ nén đáp ứng là giải thuật nén LZW . JPEG JPEG có nghĩa là Joint Protographic Experts Group . Hình ảnh được nén dưới dạng JPEG là lossy compression . Một lượng dữ liệu nén có thể thay đổi , với kết quả là mất đi hoặc tăng lên trong cùng một phương pháp . JPEG dùng chuyển đổi DCT ( discrete cosin transform ) để nén dữ liệu .Hầu hết các giải thuật nén giống như JPEG ngày nay lợi dụng sức mạnh của phần cứng , còn về giải thuật phần mềm thì vẫn còn khá chậm . Nén JPEG có thể đạt được tỉ lệ nén khá cao và chất lượng hình ảnh cũng rất tốt . Discrete Cosine Transform . DCT được sử dụng trong nén JPEG . DCT thì tương tự với chuyển đổi Fast Fourier Transform mà trong đó nó chuyển đổi một tập dữ liệu từ các miền không gian thành các miền tần số và ngược lại . Một hình ảnh đồ họa được chuyển đổi bởi DCT thành một tập thông tin liên tục , nó có thể được nén hiệu quả với việc sử dụng lossy compression . Lossless compression . Lossless compression được sử dụng để nén một chuỗi văn bản để nó có thể được bung ra thành một phiên bản giống hệt như chuỗi ban đầu . Kiểu nén này thường được yêu cầu cho các file dữ liệu . Lossy compression . Lossy compression chỉ đến một công nghệ mà ở đó dòng dữ liệu được nén không thể bung ra thành một phiên bản chính xác với dòng dữ liệu ban đầu . Nó có thể được sử dụng trong việc lưu trữ số thay cho tín hiệu tương tự , cũng như là hình ảnh đồ họa hay các mẫu âm thanh . Khả năng mất đi một lượng nhỏ dữ liệu cho phép nén file với tỉ số nén cao hơn . Lossy compression thỉnh thoảng được xem như là noisy compression . Intermapping Ta tạm dịch là ánh xạ liên thông , là các ánh xạ giữa các vùng khác nhau với nhau . Ánh xạ liên thông giúp cho việc tránh bỏ xót các domain thích hợp trong quá trình so khớp giữa domain và range . Intramapping Ta tạm dịch là ánh xạ cục bộ , có nghĩa là các ánh xạ chỉ nằm trong một vùng duy nhất đã chọn . Trong quá trình so khớp giữa range và domain thì ánh xạ cục bộ là luôn luôn cần thiết để tìm ra một cặp tốt nhất ( không mất nhiều thời gian như là ánh xạ liên thông ) . Contractive Contractive có thể dịch là thu nhỏ , co lại hoặc là hội tụ . Nghĩa là một ánh xạ ( hay một hàm ) là contractive khi và chỉ khi hàm hoặc ánh xạ đó sẽ hội tụ về một điểm ( nghiệm ) . IFS Iterated Function System – IFS , là hệ thống các chức năng được lặp lại , nghĩa là hệ thống này sẽ lặp đi lặp lại các chức năng nào đó để có thể đạt được một giải pháp . Trong Fractal Image Compression thì IFS sẽ lặp lại các hàm mã hóa để đạt được sự hội tụ . Domain Block Pool . Là những vùng chứa các khối domain . Các vùng này được sinh ra bằng các trượt một cửa sổ có kích thước 2Bx2B . Pixed point Điểm cố định – pixed point , được dùng để ám chỉ chung cho kết quả của quá trình IFS ( hay hàm mã hóa ) . Nó có thể là nghiệm của một phương trình hay là một điểm hội tụ của một ánh xạ . Virtual codebook Là một cơ sở dữ liệu dùng để lưu trữ các từ mã hay là các mẫu dùng cho việc so sánh . Ứng dụng phổ biến của virtual codebook chính là cơ sở dữ liệu từ điển . Với mỗi từ ngữ bên ngoài, ta so sánh nó với các mẫu trong codebook để tìm ra thông tin về từ đó . Domain Tạm dịch là miền . Ở trong Fractal Image Compression , domain là những vùng thường lớn hơn range và có các tính chất tương tự với range ( về không gian và đô chói ) . Thông thường , domain có kích thước lớn gấp hai lần range để bảo đảm việc ánh xạ từ domain sang range là hội tụ ( contractive ). Range Là những vùng được phân chia trên hình ảnh , có kích thước tùy ý và bao phủ toàn bộ bề mặt hình ảnh . Affine transform Chuyển đổi affine là quá trình sử dụng các hàm để mã hóa dữ liệu . Các hàm dùng để mã hóa phải có tính chất contractive . Blocky Khi ta phóng to một hình ảnh bất kỳ khoảng từ năm lần trở lên , tasẽ thấy trên bề mặt của ảnh xuất hiện những khối vuông , đó chính là hiệu ứng blocky của hình ảnh . TÀI LIỆU THAM KHẢO “The Data Compression Book second editor” ; Mark Nelson , Jean-Loup Gailly , 1991 – M & T Books , New York -1996. Harri Raittinen, Kimmo Kaski; “Fractal Based Image Compression with Affine Transformations,”IEEE Data Compression Conference Proceedings ‘93, James Storer (editor),pp. 244-253, 1993. Dan Popescu, Hong Yan; “Fractal-Based Method for Color Image Compression,” Journalof Electronic Imaging, vol. 4, no. 1, pp. 23-30, 1995. Fisher,Y. et al., Fractal Image Compression : Theory and Application , Springer Verlag , New York , 1995 . Yuval Fisher, Bill Jacobs, Roger Boss; “Fractal Image Compression Using Iterated Transforms,”in Image and Text Compression, edited by James Storer, Kluwer Academic Publishers,ISBN 0-7923-9243-4, pp. 35-61, 1992. Arnaud Jacquin; “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations,” IEEE Transactions on Image Processing, vol. 1, no. 1, January 1992,pp. 18-30. John Hutchinson; “Fractals and Self-Similarity,” Indiana University Mathematics Journal,vol. 30, no. 5, pp. 713-747, 1981. Bernd Hurtgen, Paul Mols, Stephan Simon; “Fractal Transform Coding of Color Images,”Proceedings of the SPIE: Visual Communications and Image Processing, pp. 1683-1691,1994. [ftp://links.uwaterloo.ca:/pub/Fractals/Papers/External/hurtgen94e.ps.gz] John Kominek; “Algorithm for Fast Fractal Image Compression,” Proceedings of SPIE:Digital Video Compression: Algorithms and Technologies 1995, vol. 2419, pp. 296-305,1995. [ftp://links.uwaterloo.ca:/pub/Fractals/Papers/Waterloo/kominek95a.ps.gz] Dietmar Saupe, Raouf Hamzaoui; “Complexity Reduction Methods for Fractal Image Compression,” Conference Proceedings of Image Processing: Mathematical Methods and Applications, J. Blackledge (editor), pp. xxx-yyy, 1995. [ftp://links.uwaterloo.ca:/pub/Fractals/Papers/External/saupe95a.ps.gz] Behnam Bani-Eqbal; “Speeding Up Fractal Image Compression,” Proceedings of SPIE:Still-Image Compression, vol. 2418, pp. 67-74, 1995. [ftp://links.uwaterloo.ca:/pub/Fractals/Papers/External/bani95.ps.gz]