📄 477-505.html
字号:
<!DOCTYPE HTML PUBLIC "html.dtd"><HTML><HEAD><TITLE>The Data Compression Book-:Fractal Image Compression</TITLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><SCRIPT><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes');}//--></SCRIPT></HEAD><BODY BGCOLOR="#FFFFFF" VLINK="#DD0000" TEXT="#000000" LINK="#DD0000" ALINK="#FF0000"><TD WIDTH="540" VALIGN="TOP"><!-- <CENTER><TABLE><TR><TD><FORM METHOD="GET" ACTION="http://search.itknowledge.com/excite/cgi-bin/AT-foldocsearch.cgi"><INPUT NAME="search" SIZE="20" VALUE=""><BR><CENTER><INPUT NAME="searchButton" TYPE="submit" VALUE="Glossary Search"></CENTER><INPUT NAME="source" TYPE="hidden" VALUE="local" CHECKED> <INPUT NAME="bltext" TYPE="hidden" VALUE="Back to Search"><INPUT NAME="sp" TYPE="hidden" VALUE="sp"></FORM></TD><TD><IMG SRC="http://www.itknowledge.com/images/dotclear.gif" WIDTH="15" HEIGHT="1"></TD><TD><FORM METHOD="POST" ACTION="http://search.itknowledge.com/excite/cgi-bin/AT-subscriptionsearch.cgi"><INPUT NAME="search" SIZE="20" VALUE=""><BR><CENTER><INPUT NAME="searchButton" TYPE="submit" VALUE=" Book Search "></CENTER><INPUT NAME="source" TYPE="hidden" VALUE="local" CHECKED> <INPUT NAME="backlink" TYPE="hidden" VALUE="http://search.itknowledge.com:80/excite/AT-subscriptionquery.html"><INPUT NAME="bltext" TYPE="hidden" VALUE="Back to Search"><INPUT NAME="sp" TYPE="hidden" VALUE="sp"></FORM></TD></TR></TABLE></CENTER> --><!-- ISBN=1558514341//--><!-- TITLE=The Data Compression Book-//--><!-- AUTHOR=Mark Nelson//--><!-- PUBLISHER=IDG Books Worldwide, Inc.//--><!-- IMPRINT=M & T Books//--><!-- CHAPTER=13//--><!-- PAGES=477-505//--><!-- UNASSIGNED1//--><!-- UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="474-477.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="506-509.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><H4 ALIGN="LEFT"><A NAME="Heading15"></A><FONT COLOR="#000077">The decompression module</FONT></H4><P>The decompression code uses the same traverse_image() function as the compressor, to ensure that both use exactly the same partitioning strategy. The only difference is that during the traversal, the decoder only reads the encoded affine maps; it does not actually generates the output image at this step.</P><P>Once the affine maps have been read in, the decoder starts with a random initial image and calls refine_image() a number of times selected by the user. For each iteration, refine_image() goes through all the maps and applies them to the current image. The “pure” method would compute a separate new image and then swap the roles of the old and new image. However the convergence towards the final image happens to be quicker if we overwrite the same image while applying the affine maps; for the same quality of reconstructed image we need fewer iterations. Overwriting the same image also reduces the memory requirements since we need only a buffer for one image instead of two.</P><P>After the image has been reconstructed, the decoder calls the function average_boundaries() to smooth the transition between adjacent ranges. This is only done for large ranges (8x8 and 16x16), since averaging the small 4x4 ranges can degrade the image quality.</P><H3><A NAME="Heading16"></A><FONT COLOR="#000077">The complete code listing</FONT></H3><P>The complete listing of FRAC.C follows.</P><!-- CODE //--><PRE>/*********************** Start of FRAC.C *********************** * * This is the FRAC module, which implements a graphics fractal compression * program. It needs to be linked with the standard support routines. * Copyright 1995 Jean-loup Gailly */#include <stdio.h>#include <stdlib.h>#include <math.h>#include "bitio.h"#include "errhand.h"#ifdef unix# define float double /* better accuracy but more memory usage */#endifchar *CompressionName = "Fractal compression";char *Usage ="infile outfile [-q quality] [-d density] [-h h_size] [-v v_size]\n\ quality from 1..20, domain density from 0..2\n\Decompression parameters:\n\ infile outfile [-i iterations] [-s scale]\n";typedef unsigned char image_data;typedef unsigned long uns_long;/* * Maximum gray level in an image */#define MAX_GREY 255/* * Number of classes. Each class corresponds to one specific ordering * of the image brightness in the four quadrants of a range or domain. * There are 4*3*2 = 24 classes. */#define NCLASSES 24/* * Minimum and maximum number of bits for the side of a range. The actual * range sizes are between 1<<MIN_BITS and 1<<MAX_BITS. To simplify the * implementation and avoid ridiculously small ranges, MIN_BITS must be >= 2. * This implementation also requires MAX_BITS <= 7. */#define MIN_BITS 2#define MAX_BITS 4/* * Maximum contrast factor in a range to domain mapping. */#define MAX_CONTRAST 1.0/* * Bit sizes for encodings of contrast and brightness in an affine map. * Using smaller sizes increases compression and degrades image quality. */#define CONTRAST_BITS 4#define BRIGHTNESS_BITS 6#define MAX_QCONTRAST ((1<<CONTRAST_BITS)-1) /* max quantized contrast */#define MAX_QBRIGHTNESS ((1<<BRIGHTNESS_BITS)-1) /* max quantized brightness *//* * De-quantize an integer value in the range 0 .. imax to the range 0.0 .. max * while preserving the mapping 0 -> 0.0 and imax -> max. */#define dequantize(value, max, imax) ((double)(value)*(max)/(double)imax)/* * Compute the square of a pixel value and return the result as unsigned long */#define square(pixel) (uns_long)(pixel)*(pixel)/* * Range data: range[i][j] is the brightness at row i and column j */image_data **range;/* * Domain data, summed over 4 pixels: domain[i][j] is the sum of the * pixel values at (2j, 2i), (2j+1, 2i), (2j, 2i+1) and (2j+1, 2i+1) */unsigned **domain;/* * Cumulative range data, kept only for pixels of even coordinates. * cum_range[i][j] is the sum of all pixel values strictly above and to the * left of pixel (2j, 2i). In particular, cum_range[y_size/2][x_size/2] is * the sum of all pixel values in the image. This table is also used for * the cumulative domain data. */uns_long **cum_range;/* * Cumulative squared range data, kept only for pixels of even coordinates. * cum_range2[i][j] is the sum of the squares of all pixel values strictly * above and to the left of pixel (2j, 2i). In particular, * cum_range2[y_size/2][x_size/2] is the sum of all the squared pixel values * in the image. */float **cum_range2;/* * Cumulative squared domain data. cum_domain2[i][j] is the sum of the squares * of all domain values strictly above and to the left of domain (j,i), which * corresponds to pixel (2j, 2i). The values in cum_domain2 are scaled by * a factor of 16.0 to avoid some multiplications. */float **cum_domain2;/* * Domain density: domains of size s*s are located every (s>>dom_density) * pixels. The density factor can range from 0 to 2 (smallest domains * have a size of 8 and must start on even pixels boundaries). Density * factors 1 and 2 get better image quality but significantly slow * down compression. */int dom_density = 0;/* * Maximum tolerated mean square error between original image and * reconstructed uncompressed image. */double max_error2;/* * The fractal (compressed) file */BIT_FILE *frac_file;/* * Information common to all domains of a certain size: info[s] describes * domains of size 1<<(s+1), corresponding to ranges of size 1<<s */struct domain_info { int pos_bits; /* Number of bits required to encode a domain position */ int x_domains; /* Number of domains in x (horizontal) dimension */} dom_info[MAX_BITS+1];/* * Each domain is described by a `domain_data' structure. * domain_head[c][s] is the head of the list of domains of class c * and size 1<<(s+1) (corresponding to ranges of size 1<<s). */typedef struct domain_struct { int x; /* horizontal position */ int y; /* vertical position */ float d_sum; /* sum of all values in the domain */ float d_sum2; /* sum of all squared values in the domain */ struct domain_struct *next; /* next domain in same class */} domain_data;domain_data *domain_head[NCLASSES][MAX_BITS+1];/* * Ranges are described by a `range_data' structure. This structure * is computed on the fly for each range as it is compressed. */typedef struct range_struct { int x; /* horizontal position */ int y; /* vertical position */ int s_log; /* log base 2 of the range size */ double r_sum; /* sum of all values in the range */ double r_sum2; /* sum of all squared values in the range */} range_data;/* * Range to domain mappings are described by an `affine_map' structure. */typedef struct map_struct { int contrast; /* quantized best contrast between range and domain */ int brightness; /* quantized best brightness offset */ double error2; /* sum of squared differences between range and domain */} affine_map;/* * Function prototypes for both ANSI and K&R. */#ifdef __STDC__# define OF(args) args#else# define OF(args) ()#endif/* * Functions used for compression */void CompressFile OF((FILE *input, BIT_FILE *output, int argc, char*argv[]));void compress_init OF((int x_size, int y_size, FILE *image_file));void compress_cleanup OF((int y_size));void classify_domains OF((int x_size, int y_size, int s));int find_class OF((int x, int y, int size));void compress_range OF((int x, int y, int s_log));void find_map OF((range_data *rangep, domain_data *dom, affine_map*map));/* * Functions used for decompression */void ExpandFile OF((BIT_FILE *input, FILE *output, int argc, char*argv[]));void decompress_range OF((int x, int y, int s_log));void refine_image OF((void));void average_boundaries OF((void));/* * Functions common to compression and decompression */typedef void (*process_func) OF((int x, int y, int s_log));void traverse_image OF((int x, int y, int x_size, int y_size, process_func process));int quantize OF((double value, double max, int imax));void dominfo_init OF((int x_size, int y_size, int density));void *xalloc OF((unsigned size));void **allocate OF((int rows, int columns, int elem_size));void free_array OF((void **array, int rows));int bitlength OF((uns_long val)); /**********************************/ /* Functions used for compression */ /**********************************//* ===================================================================== * This is the main compression routine. By the time it gets called, * the input and output files have been properly opened, so all it has to * do is the compression. Note that the compression routine optionally * accepts additional parameters: * - the quality value, ranging from 0 to 20. It is used as average tolerated * error between the original image and its uncompressed version. (Non * integer values are also accepted.)⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -