1、1,Chapter 6,BTC與中國書法壓縮,2,6.1 Introduction,Block Truncation Coding基因演算法與AMBTC中國書法壓縮,3,6.2BTC (Block Truncation Coding),Bitmap=,X=,8,8,4,6,4,m: Bitmap中的總 bit 數q: Bitmap 中1 的個數,6.3 AMBTC (Absolute Moment Block),5,Single Bitmap AMBTC of Color Images,R G B,Common bitmap,6,Single Bitmap AMBTC of Color Ima
2、ges,R G BRx0=187 Rx1=199 Gx0=97 Gx1=132 Bx0=107 Bx1=127,針對 AMBTC而言 ，壓縮率,7,How to find the best common bitmap,B=common bitmapxi=(ri,gi,bi)The best common bitmap might be found by calculating the MSEB for all 2m bitmaps and choosing the one with the minimum MSEB,8,6.3.1 Genetic Algorithms,SelectionThe
3、 chromosome with fitness will be selected in the next generation and ones with worse fitness will die outCrossoverTo exchange the genes between the two parent chromosomesMutationTo select a gene randomly from a given chromosome and alters it,GA -AMBTC,10,Initialize the mating pool,C1,C4,C5,C12,C8,C9
4、,N=12,11,Calculate the fitness value for each chromosome (selection),k: the kth interaction,12,Reproduction with threshold measure,If Max(fitnessi)-Average(fitnessi)threshold, then replace worse chromosomes with new chromosomesAdd new chromosomes rate=30%,13,Crossover,The probability of crossover is
5、 always largePc=0.8,Ci,Cj,14,Mutation,The probability of mutation is always smallPm=0.001,Ci,Ci,15,The MSE results with 44 block size,16,The MSE results with 88 block size,17,Comparison of convergence for randomly initialization and AMBTC-initialization,18,Comparison of adding new chromosomes and wi
6、thout adding new chromosomes, block size 44,19,The results of different crossover methods, block size 44,20,Combined with the proposed crossover method and the addition of new chromosomes as a control mechanism, can get good results in fewer iterations for single bitmap AMBTCThe performance of the G
7、A AMBTC is significantly better than that of other related schemes,21,6.4 中國書法壓縮,22,Chinese calligraphy ImagesImage compression methodsVector quantization (VQ)S-tree New S-tree (proposed method)Experimental resultsConclusions,23,6.4.1 S-tree,Binary imagesFor example:,第一刀先垂直切,24,The bintree of the ex
8、ample,Bintree,S-tree,53 bits,樹葉顏色,樹的結構,25,Problems of S-tree,We do not need to divide the bounded images too finelySolution: the proportion threshold of the bounded imageSometimes it is not worth to divide the bounded images at allSolution: the process of retrenching the bintree,26,6.4.2 New S-tree,
9、A gray level image is transferred into a binary image firstThe proportion threshold of the bounded image is providedThe process of retrenching the bintree is added,27,Example of New S-tree,Binary image,28,Flag bit 02: white / 12: blackLinear tree table 02: the internal node / 12: the leaf nodeColor
10、tableFlag bit = 1202: the black block / 102: the white block112: the raw data blockFlag bit = 0202: the white block / 102: the black block112: the raw data block,29,The original bintree,Flag bit=1|a|=1 (in the linear tree table) + 1 (in the color table)|b|=1 (in the linear tree table) + 2 (in the co
11、lor table)|i| =1 (in the linear tree table),30,The bintree at the beginning phase of the retrenching process,Flag bit=0|i| =1 (in the linear tree table) +2 (in the color table) + 2 (in the raw data table) 1 11 10,31,The bintree after the retrenching process,47 bits,32,Experiment results,33,34,35,36,
12、37,38,The image quality of proportion threshold,39,The compression ratio of proportion threshold,40,The compression time of proportion threshold,41,New S-tree Chinese calligraphyLow compression ratio(10%-40%) of the storage of S-tree savedFast execution time(only 10% of the execution time of VQ needed)Good image quality(the same visual quality as VQ),
