[xiph-cvs] cvs commit: w3d/tools Makefile
Holger Waechtler
holger at xiph.org
Thu Sep 13 09:27:37 PDT 2001
holger 01/09/13 09:27:37
Modified: . Makefile TODO _test_rle.c bitcoder.h rle.h
tarkin-io.c tarkin.c tarkin.h tarkin_dec.c
tarkin_enc.c wavelet_coeff.c wavelet_xform.c yuv.c
docs Makefile bibliography.tex colorspace.tex
entropycoder.tex intro.tex quantizer.tex
wavelet.tex
tools Makefile
Log:
- major cleanup, bug fixes and workarounds
- wrote some new docu
- rewrote truncation table setup
- added Lxy colorspace, still buggy
wavelet code seems to work now, compression can still get improved by
implementing an adaptive huffman coder and compress truncation tables.
Read docu (w3d/docs) for details -- type make to create a compressed
postscript.
Revision Changes Path
1.17 +23 -3 w3d/Makefile
Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/Makefile,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -r1.16 -r1.17
--- Makefile 2001/09/07 10:56:29 1.16
+++ Makefile 2001/09/13 16:27:33 1.17
@@ -1,9 +1,28 @@
CC = gcc
RM = rm -rf
-CFLAGS = -g -O3 -Wall -DTYPE=int16_t -DRLECODER #-DDBG_XFORM -DDBG_MEMLEAKS
-LFLAGS = -g #-lefence
+CFLAGS = -g -O2 -Wall
+# use 16 bit signed integers as wavelet coefficients
+CFLAGS+= -DTYPE=int16_t
+
+# we'll actually use TYPE_BITS bits of type (e.g. 9 magnitude + 1 sign)
+CFLAGS+= -DTYPE_BITS=10
+
+# use the rle entropy coder
+CFLAGS+= -DRLECODER
+
+# simple malloc debugging
+CFLAGS+= -DDBG_MEMLEAKS
+
+# dump a lot debug images
+CFLAGS+= -DDBG_XFORM
+
+# disable assertions
+#CFLAGS+= -DNDEBUG
+
+LFLAGS = -g -lefence
+
OBJS = mem.o pnm.o wavelet.o wavelet_xform.o wavelet_coeff.o \
yuv.o tarkin.o tarkin-io.o
@@ -27,9 +46,10 @@
clean:
$(RM) $(OBJS) $(TARGET) gmon.out core .depend .depend.bak rle.histogram
- $(RM) *.ppm *.pgm
$(RM) $(TEST_TARGETS) $(TEST_OBJS)
$(RM) tarkin_enc tarkin_dec tarkin_enc.o tarkin_dec.o
+ $(RM) *.ppm *.pgm
+ $(RM) stream.tarkin
test: .depend $(TEST_TARGETS)
1.8 +21 -6 w3d/TODO
Index: TODO
===================================================================
RCS file: /usr/local/cvsroot/w3d/TODO,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- TODO 2001/09/07 10:56:29 1.7
+++ TODO 2001/09/13 16:27:33 1.8
@@ -1,17 +1,29 @@
-Open bugs and stuff required to fix them:
+
+Most important things:
- - a bug in the yuv<->rgb24conversion, shows up in the clouds sequence
+ - the entropy coder, replace static huffman
+ - oggetize the stream format (Jack? Help!)
- clean up the pnsr tools
+ - write docs and do some performance analysis, compare to other codecs
+ - think about a multiresolution multidimensional motion flow detection scheme,
+ Marco posted a good paper comparing different algorithms to do this
+
+
+Open bugs and stuff required to fix them:
+
+ - wavelet xform bug at short rows, see workaround in wavelet_xform.c
+ - (4,x) and (x,4) wavelet implementations have a bug which causes round-off
+ errors in the two least significand bits
Wavelet-related TODO's:
- - oggetize the stream format
- - improve truncation table setup, the current code is pretty dumb
+ - remove unecessairy copying in inverse xform
+ - improve truncation table setup
- try other approaches to encode coefficients, jack was talking about VQ
and reuse vorbis code
- write avitotarkin/quicktimetotarkin/mpegtotarkin/player/recorder
- (a libsndfile/libaudiofile alike video library would be great !)
+ (a libsndfile/libaudiofile/libao alike video library would be great !)
- profile
- add special transform functions for large strides to prevent cache misses
- mmx/3dnow/sse/altivec
@@ -19,7 +31,10 @@
Other:
- - think about a multiresolution multidimensional motion detection scheme
+ - u and v buffers could get quarter size already at color conversion
+ this would speed up the whole algorithm; perhaps this should get
+ configurable
+ - fast internal 16bitY/U/V->15/16bitRGB for display could make sense
- the wavelet codec could be used for still image compression too
(we just have to define a file format with all goodies you can imagine;)
- to make it perfect someone has to write a good bilevel compressor and
1.5 +13 -1 w3d/_test_rle.c
Index: _test_rle.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/_test_rle.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- _test_rle.c 2001/09/07 10:56:29 1.4
+++ _test_rle.c 2001/09/13 16:27:33 1.5
@@ -78,8 +78,20 @@
ENTROPY_DECODER_INIT(&decoder, bitstream, count);
for (i=0; i<limit; i++) {
- int b = INPUT_BIT(&decoder);
+ int b;
+ int skip;
+
+ b = INPUT_BIT(&decoder);
TEST(bit[i] == b);
+
+ skip = ENTROPY_CODER_RUNLENGTH(&decoder);
+ if (skip > 0 && ENTROPY_CODER_MPS(&decoder) == 0) {
+ int j;
+ for (j=0; j<skip; j++)
+ TEST(bit[i+j] == 0);
+ ENTROPY_CODER_SKIP(&decoder, skip);
+ i += skip;
+ }
}
}
1.9 +2 -1 w3d/bitcoder.h
Index: bitcoder.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/bitcoder.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- bitcoder.h 2001/09/07 10:56:30 1.8
+++ bitcoder.h 2001/09/13 16:27:33 1.9
@@ -18,7 +18,7 @@
#define ENTROPY_DECODER_DONE(coder) /* nothing to do ... */
#define ENTROPY_CODER_BITSTREAM(coder) (coder)->bitstream
-#define ENTROPY_CODER_MPS 1
+#define ENTROPY_CODER_MPS(coder) 1
#define ENTROPY_CODER_RUNLENGTH(coder) 0
#define ENTROPY_CODER_SKIP(coder,skip)
@@ -74,6 +74,7 @@
s->bitstream [s->byte_count++] = s->byte << (8 - s->bit_count);
//printf ("%s: %i bytes written.\n", __FUNCTION__, s->byte_count);
+//printf ("%s: last bit %i\n", __FUNCTION__, s->bit_count);
return s->byte_count;
}
1.10 +2 -2 w3d/rle.h
Index: rle.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/rle.h,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- rle.h 2001/09/07 10:56:30 1.9
+++ rle.h 2001/09/13 16:27:33 1.10
@@ -23,8 +23,8 @@
#define ENTROPY_CODER_EOS(coder) ((coder)->bitcoder.eos)
#define ENTROPY_CODER_MPS(coder) ((coder)->mps)
-#define ENTROPY_CODER_RUNLENGTH(coder) ((coder)->count+1)
-#define ENTROPY_CODER_SKIP(coder,skip) do { (coder)->count -= skip-1; } while (0)
+#define ENTROPY_CODER_RUNLENGTH(coder) ((coder)->count)
+#define ENTROPY_CODER_SKIP(coder,skip) do { (coder)->count -= skip; } while (0)
#endif
1.4 +7 -7 w3d/tarkin-io.c
Index: tarkin-io.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin-io.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- tarkin-io.c 2001/07/09 06:03:09 1.3
+++ tarkin-io.c 2001/09/13 16:27:33 1.4
@@ -37,12 +37,12 @@
uint32_t n_layers = s->n_layers;
if (write (fd, signature, 6) < 6)
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
CPU_TO_LE32(n_layers);
if (write (fd, &n_layers, 4) < 4)
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
return TARKIN_OK;
}
@@ -63,7 +63,7 @@
CPU_TO_LE32(layer.format);
if (write (fd, &layer, sizeof(TarkinVideoLayer)) < sizeof(TarkinVideoLayer)) {
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
}
}
@@ -88,13 +88,13 @@
char signature [6];
if (read (fd, signature, 6) < 6)
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
if (!strncmp(signature, "tarkin", 6) == 0)
- return TARKIN_SIGNATURE_NOT_FOUND;
+ return -TARKIN_SIGNATURE_NOT_FOUND;
if (read (fd, &s->n_layers, 4) < 4)
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
LE32_TO_CPU(s->n_layers);
@@ -109,7 +109,7 @@
for (i=0; i<s->n_layers; i++) {
if (read (fd, &s->layer[i], sizeof(TarkinVideoLayer)) < sizeof(TarkinVideoLayer)) {
tarkin_stream_destroy (s);
- return TARKIN_IO_ERROR;
+ return -TARKIN_IO_ERROR;
}
LE32_TO_CPU(s->layer[i].width);
LE32_TO_CPU(s->layer[i].height);
1.11 +32 -35 w3d/tarkin.c
Index: tarkin.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin.c,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -r1.10 -r1.11
--- tarkin.c 2001/09/07 10:56:30 1.10
+++ tarkin.c 2001/09/13 16:27:33 1.11
@@ -54,9 +54,9 @@
-int tarkin_stream_write_layer_descs (TarkinStream *s,
- uint32_t n_layers,
- TarkinVideoLayerDesc desc [])
+TarkinError tarkin_stream_write_layer_descs (TarkinStream *s,
+ uint32_t n_layers,
+ TarkinVideoLayerDesc desc [])
{
TarkinError err;
uint32_t max_bitstream_len = 0;
@@ -92,8 +92,7 @@
layer->color_inv_xform = yuv_to_rgba;
break;
default:
- BUG("unknown color format");
- break;
+ return -TARKIN_INVALID_COLOR_FORMAT;
};
layer->waveletbuf = (Wavelet3DBuf**) CALLOC (layer->n_comp,
@@ -104,18 +103,18 @@
desc[i].frames_per_buf);
max_bitstream_len += layer->desc.bitstream_len
- + 5000
- + 2 * 9 * sizeof(uint32_t) * layer->n_comp; // truncation tables
+ + 2 * 10 * sizeof(uint32_t) * layer->n_comp; // truncation tables
}
if ((err = write_tarkin_header(s->fd, s)) != TARKIN_OK)
return err;
- err = write_layer_descs(s->fd, s);
+ if ((err = write_layer_descs(s->fd, s)) != TARKIN_OK)
+ return err;
s->bitstream = (uint8_t*) MALLOC (max_bitstream_len);
- return err;
+ return TARKIN_OK;
}
@@ -129,21 +128,33 @@
TarkinVideoLayer *layer = &s->layer[i];
for (j=0; j<layer->n_comp; j++) {
+ uint32_t comp_bitstream_len;
uint32_t bitstream_len;
+ /**
+ * implicit 6:1:1 subsampling
+ */
+ if (j == 0)
+ comp_bitstream_len = 6*layer->desc.bitstream_len/(layer->n_comp+5);
+ else
+ comp_bitstream_len = layer->desc.bitstream_len/(layer->n_comp+5);
+
+ wavelet_3d_buf_dump ("color-%d-%03d.pgm",
+ s->current_frame, j,
+ layer->waveletbuf[j], j == 0 ? 0 : 128);
+
wavelet_3d_buf_fwd_xform (layer->waveletbuf[j],
layer->desc.a_moments,
layer->desc.s_moments);
wavelet_3d_buf_dump ("coeff-%d-%03d.pgm",
- s->current_frame - s->current_frame_in_buf, j,
+ s->current_frame, j,
layer->waveletbuf[j], 128);
bitstream_len = wavelet_3d_buf_encode_coeff (layer->waveletbuf[j],
s->bitstream,
- j == 0 ?
- layer->desc.bitstream_len :
- layer->desc.bitstream_len/4);
+ comp_bitstream_len);
+
write_tarkin_bitstream (s->fd, s->bitstream, bitstream_len);
}
}
@@ -152,19 +163,13 @@
uint32_t tarkin_stream_write_frame (TarkinStream *s, uint8_t **rgba)
{
- uint32_t i, j;
+ uint32_t i;
for (i=0; i<s->n_layers; i++) {
TarkinVideoLayer *layer = &s->layer[i];
layer->color_fwd_xform (rgba[i], layer->waveletbuf,
s->current_frame_in_buf);
-
- for (j=0; j<layer->n_comp; j++)
- wavelet_3d_buf_dump ("color-%d-%03d.pgm",
- s->current_frame - s->current_frame_in_buf, j,
- layer->waveletbuf[j], j == 0 ? 0 : 128);
-
}
s->current_frame_in_buf++;
@@ -197,9 +202,6 @@
for (i=0; i<s->n_layers; i++) {
TarkinVideoLayer *layer = &s->layer[i];
- if (layer->desc.format != TARKIN_RGB24)
- exit (-1);
-
switch (layer->desc.format) {
case TARKIN_GRAYSCALE:
layer->n_comp = 1;
@@ -236,8 +238,7 @@
}
max_bitstream_len += layer->desc.bitstream_len
- + 5000
- + 2 * 9 * sizeof(uint32_t) * layer->n_comp;
+ + 2 * 10 * sizeof(uint32_t) * layer->n_comp;
}
s->bitstream = (uint8_t*) MALLOC (max_bitstream_len);
@@ -247,23 +248,19 @@
-int tarkin_stream_get_layer_desc (TarkinStream *s,
- uint32_t layer_id,
- TarkinVideoLayerDesc *desc)
+TarkinError tarkin_stream_get_layer_desc (TarkinStream *s,
+ uint32_t layer_id,
+ TarkinVideoLayerDesc *desc)
{
if (layer_id > s->n_layers-1)
- return -1;
+ return -TARKIN_INVALID_LAYER;
memcpy (desc, &(s->layer[layer_id].desc), sizeof(TarkinVideoLayerDesc));
- return 0;
+ return TARKIN_OK;
}
-/**
- * read all layers of the next frame to buf[0..n_layers]
- * returns the number of this frame on success, -1 on error
- */
uint32_t tarkin_stream_read_frame (TarkinStream *s, uint8_t **rgba)
{
uint32_t i, j;
@@ -292,7 +289,7 @@
layer->desc.s_moments);
wavelet_3d_buf_dump ("rcolor-%d-%03d.pgm",
- s->current_frame - s->current_frame_in_buf, j,
+ s->current_frame, j,
layer->waveletbuf[j], j == 0 ? 0 : 128);
}
}
1.7 +57 -16 w3d/tarkin.h
Index: tarkin.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- tarkin.h 2001/07/16 16:10:51 1.6
+++ tarkin.h 2001/09/13 16:27:33 1.7
@@ -23,9 +23,11 @@
} TarkinColorFormat;
typedef enum {
- TARKIN_SIGNATURE_NOT_FOUND = -2,
- TARKIN_IO_ERROR = -1,
- TARKIN_OK = 0
+ TARKIN_OK = 0,
+ TARKIN_IO_ERROR,
+ TARKIN_SIGNATURE_NOT_FOUND,
+ TARKIN_INVALID_LAYER,
+ TARKIN_INVALID_COLOR_FORMAT
} TarkinError;
@@ -62,20 +64,59 @@
} TarkinStream;
-extern TarkinStream* tarkin_stream_new (int fd);
-extern void tarkin_stream_destroy (TarkinStream *s);
+extern
+TarkinStream* tarkin_stream_new (int fd);
-extern int tarkin_stream_get_layer_desc (TarkinStream *s,
- uint32_t layer_id,
- TarkinVideoLayerDesc *desc);
-extern uint32_t tarkin_stream_read_header (TarkinStream *s);
-extern uint32_t tarkin_stream_read_frame (TarkinStream *s, uint8_t **buf);
-
-extern int tarkin_stream_write_layer_descs (TarkinStream *s,
- uint32_t n_layers,
- TarkinVideoLayerDesc desc []);
-extern uint32_t tarkin_stream_write_frame (TarkinStream *s, uint8_t **buf);
-extern void tarkin_stream_flush (TarkinStream *s);
+extern
+void tarkin_stream_destroy (TarkinStream *s);
+
+
+/**
+ * Copy layer description of layer into desc
+ */
+extern
+TarkinError tarkin_stream_get_layer_desc (TarkinStream *s,
+ uint32_t layer_id,
+ TarkinVideoLayerDesc *desc);
+
+/**
+ * Return value: number of layers, 0 on i/o error
+ */
+extern
+uint32_t tarkin_stream_read_header (TarkinStream *s);
+
+
+/**
+ * Read all layers of the next frame to buf[0..n_layers]
+ * returns the number of this frame on success, -1 on error
+ */
+extern
+uint32_t tarkin_stream_read_frame (TarkinStream *s, uint8_t **buf);
+
+
+/**
+ * Setup file configuration by writing layer descriptions
+ * Has to be done once after creating the stream
+ */
+extern
+TarkinError tarkin_stream_write_layer_descs (TarkinStream *s,
+ uint32_t n_layers,
+ TarkinVideoLayerDesc desc []);
+
+/**
+ * Write a single frame. This means that content is copied into
+ * a wavelet buffer. As soon this gets filled, the stream will be
+ * flushed implicitly.
+ * Each pointer in buf points to an layer imaged described by the
+ * tarkin_stream_write_layer_descs() call
+ */
+extern
+uint32_t tarkin_stream_write_frame (TarkinStream *s, uint8_t **buf);
+
+
+extern
+void tarkin_stream_flush (TarkinStream *s);
+
#endif
1.3 +2 -2 w3d/tarkin_dec.c
Index: tarkin_dec.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin_dec.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- tarkin_dec.c 2001/07/09 06:03:09 1.2
+++ tarkin_dec.c 2001/09/13 16:27:33 1.3
@@ -42,10 +42,10 @@
tarkin_stream_get_layer_desc (tarkin_stream, 0, &layer);
- rgb = MALLOC (layer.width * layer.height * 3);
+ rgb = MALLOC (layer.width * layer.height * (layer.format == TARKIN_GRAYSCALE ? 1 : 3));
while (tarkin_stream_read_frame (tarkin_stream, &rgb) != 0xffffffff) {
- snprintf(ofname, 11, "out%03d.ppm", frame);
+ snprintf(ofname, 11, layer.format == TARKIN_GRAYSCALE ? "out%03d.pgm" : "out%03d.ppm", frame);
printf ("write '%s'\n", ofname);
write_pnm (ofname, rgb, layer.width, layer.height);
1.12 +6 -2 w3d/tarkin_enc.c
Index: tarkin_enc.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin_enc.c,v
retrieving revision 1.11
retrieving revision 1.12
diff -u -r1.11 -r1.12
--- tarkin_enc.c 2001/09/07 10:56:30 1.11
+++ tarkin_enc.c 2001/09/13 16:27:33 1.12
@@ -16,9 +16,11 @@
"\n"
" input ppm filename format: optional, \"%%i.ppm\" by default\n"
" bitrate: cut Y/U/V bitstream after limit bytes/frame\n"
- " (something like 10000 makes sense here)\n"
+ " (something like 3000 makes sense here)\n"
" a_m, s_m: number of vanishing moments of the\n"
" analysis/synthesis filter, (2,2) by default\n"
+ "\n"
+ " The resulting stream.tarkin will have bitrate*frame+sizeof(header) bytes.\n"
"\n", program_name);
exit (-1);
}
@@ -52,8 +54,10 @@
snprintf (fname, 256, fmt, 0);
type = read_pnm_header (fname, &layer[0].width, &layer[0].height);
- if (type < 0)
+ if (type < 0) {
+ printf (" failed opening '%s' !!\n", fname);
exit (-1);
+ }
layer[0].format = (type == 3) ? TARKIN_RGB24 : TARKIN_GRAYSCALE;
1.5 +93 -105 w3d/wavelet_coeff.c
Index: wavelet_coeff.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet_coeff.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- wavelet_coeff.c 2001/09/07 10:56:30 1.4
+++ wavelet_coeff.c 2001/09/13 16:27:33 1.5
@@ -4,18 +4,15 @@
-#define SIGN_SHIFT 15
-
-
static inline
void encode_coeff (ENTROPY_CODER significand_bitstream [],
ENTROPY_CODER insignificand_bitstream [],
TYPE coeff)
{
TYPE mask [2] = { 0, ~0 };
- int sign = (coeff >> SIGN_SHIFT) & 1;
+ int sign = (coeff >> (8*sizeof(TYPE)-1)) & 1;
TYPE significance = coeff ^ mask[sign];
- int i = 10;
+ int i = TYPE_BITS;
do {
i--;
@@ -35,31 +32,28 @@
ENTROPY_CODER insignificand_bitstream [])
{
TYPE mask [2] = { 0, ~0 };
- TYPE significance;
+ TYPE significance = 0;
int sign;
- int i = 10;
+ int i = TYPE_BITS;
do {
i--;
- significance = INPUT_BIT(&significand_bitstream[i]) << i;
- if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
- return 0;
+ significance |= INPUT_BIT(&significand_bitstream[i]) << i;
+// if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
+// return 0;
} while (!significance && i > 0);
sign = INPUT_BIT(&significand_bitstream[i]);
- if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
- return 0;
+// if (ENTROPY_CODER_EOS(&significand_bitstream[i]))
+// return 0;
- while (--i >= 0) {
+ while (--i >= 0)
significance |= INPUT_BIT(&insignificand_bitstream[i]) << i;
- };
return (significance ^ mask[sign]);
}
-
-
static inline
uint32_t skip_0coeffs (Wavelet3DBuf* buf,
ENTROPY_CODER s_stream [],
@@ -67,29 +61,28 @@
uint32_t limit)
{
int i;
- uint32_t min = limit;
+ uint32_t skip = limit;
- for (i=0; i<10; i++) {
- if (ENTROPY_CODER_MPS(&s_stream[i]) == 0) {
+ for (i=0; i<TYPE_BITS; i++) {
+ if (ENTROPY_CODER_MPS(&s_stream[i]) != 0) {
+ return 0;
+ } else {
uint32_t runlength = ENTROPY_CODER_RUNLENGTH(&s_stream[i]);
- if (min > runlength)
- min = runlength;
- if (min <= 2)
+ if (i==0)
+ runlength /= 2; /* sign bits are in this bitplane ... */
+ if (skip > runlength)
+ skip = runlength;
+ if (skip <= 2)
return 0;
- } else {
- return 0;
}
}
- if (min > limit)
- min = limit;
+ ENTROPY_CODER_SKIP(&s_stream[0], 2*skip); /* kill sign+significance bits */
- for (i=0; i<10; i++) {
- ENTROPY_CODER_SKIP(&s_stream[i], min);
- ENTROPY_CODER_SKIP(&i_stream[i], min);
- }
+ for (i=1; i<TYPE_BITS; i++)
+ ENTROPY_CODER_SKIP(&s_stream[i], skip);
- return min;
+ return skip;
}
@@ -182,8 +175,8 @@
return;
}
}
- } else
- x++;
+ }
+ x++;
} while (x < w);
y++;
} while (y < h);
@@ -242,86 +235,81 @@
ENTROPY_CODER s_stream [],
ENTROPY_CODER i_stream [])
{
- uint32_t i = 0;
+ uint32_t i;
- while (i < buf->width*buf->height*buf->frames) {
- int skip;
+ for (i=0; i<buf->width*buf->height*buf->frames; i++) {
+ uint32_t skip;
buf->data[i] = decode_coeff(s_stream, i_stream);
skip = skip_0coeffs (buf, s_stream, i_stream,
buf->width*buf->height*buf->frames - i);
- if (skip > 0)
- i += skip;
- else
- i++;
+ i += skip;
}
}
#endif
-static
-uint32_t insignificand_truncation_table [10] = {
-// 1, 2, 4, 8, 16, 12, 64, 128, 256, 512
-// 100, 100, 100, 100, 100, 100, 100, 100, 100, 100
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 48
-};
-
static
-uint32_t significand_truncation_table [9] = { //1, 2, 4, 8, 16, 32, 64, 128, 256 };
-// 100, 100, 100, 100, 100, 100, 100, 100, 100
- 24, 24, 24, 24, 24, 24, 24, 24, 48
-};
-
-
-static
uint32_t setup_limittabs (ENTROPY_CODER significand_bitstream [],
ENTROPY_CODER insignificand_bitstream [],
uint32_t significand_limittab [],
uint32_t insignificand_limittab [],
uint32_t limit)
{
- uint32_t byte_count = 0;
+ uint32_t significand_limit;
+ uint32_t insignificand_limit;
+ uint32_t byte_count;
int i;
-printf ("%s: limit == %u\n", __FUNCTION__, limit);
- limit -= 2 * 10 * sizeof(uint32_t); /* 2 limittabs, coded binary */
-printf ("%s: rem. limit == %u\n", __FUNCTION__, limit);
-
- for (i=0; i<10; i++) {
- uint32_t bytes = ENTROPY_ENCODER_FLUSH(&insignificand_bitstream[i]);
-
- insignificand_limittab[i] =
- limit * insignificand_truncation_table[i] / 2048;
-
- if (bytes < insignificand_limittab[i])
- insignificand_limittab[i] = bytes;
-printf ("insignificand_limittab[%i] == %u / %u\n", i, insignificand_limittab[i], bytes);
- byte_count += insignificand_limittab[i];
- }
+ assert (limit > 2 * TYPE_BITS * sizeof(uint32_t)); /* limit too small */
+
+ printf ("%s: limit == %u\n", __FUNCTION__, limit);
+ byte_count = 2 * TYPE_BITS * sizeof(uint32_t); /* 2 binary coded limittabs */
+ limit -= byte_count;
+ printf ("%s: rem. limit == %u\n", __FUNCTION__, limit);
+
+ significand_limit = limit * 4 / 8;
+ insignificand_limit = limit - significand_limit;
- for (i=9; i>0; i--) {
- uint32_t bytes = ENTROPY_ENCODER_FLUSH(&significand_bitstream[i]);
+ printf ("significand limit == %u\n", significand_limit);
+ printf ("insignificand limit == %u\n", insignificand_limit);
- significand_limittab[i] = limit * significand_truncation_table[9-i] / 2048
- + (10-i)*(limit - byte_count)/10;
+ for (i=TYPE_BITS-1; i>=0; i--) {
+ uint32_t s_bytes, i_bytes;
- if (significand_limittab[i] > limit - byte_count)
- significand_limittab[i] = limit - byte_count;
+ if (i > 0) {
+ significand_limittab[i] = (significand_limit + 1) / 2;
+ insignificand_limittab[i] = (insignificand_limit + 1) / 2;
+ } else {
+ significand_limittab[i] = significand_limit;
+ insignificand_limittab[i] = insignificand_limit;
+ }
+
+ s_bytes = ENTROPY_ENCODER_FLUSH(&significand_bitstream[i]);
+ i_bytes = ENTROPY_ENCODER_FLUSH(&insignificand_bitstream[i]);
+
+ if (s_bytes < significand_limittab[i])
+ significand_limittab[i] = s_bytes;
- if (bytes < significand_limittab[i])
- significand_limittab[i] = bytes;
-printf ("significand_limittab[%i] == %u / %u\n", i, significand_limittab[i], bytes);
+ if (i_bytes < insignificand_limittab[i])
+ insignificand_limittab[i] = i_bytes;
+ significand_limit -= significand_limittab[i];
+ insignificand_limit -= insignificand_limittab[i];
+
byte_count += significand_limittab[i];
+ byte_count += insignificand_limittab[i];
+
+ printf ("insignificand_limittab[%i] == %u / %u\n",
+ i, insignificand_limittab[i], i_bytes);
+ printf (" significand_limittab[%i] == %u / %u\n",
+ i, significand_limittab[i], s_bytes);
}
- significand_limittab[0] = limit - byte_count;
- byte_count += significand_limittab[0];
+ printf ("byte_count == %u\n", byte_count);
-printf ("significand_limittab[%i] == %u\n", 0, significand_limittab[0]);
-printf ("byte_count == %u\n", byte_count);
return byte_count;
}
@@ -336,12 +324,12 @@
{
int i;
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
*(uint32_t*) bitstream = significand_limittab[i];
bitstream += 4;
}
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
*(uint32_t*) bitstream = insignificand_limittab[i];
bitstream += 4;
}
@@ -357,15 +345,15 @@
{
int i;
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
significand_limittab[i] = *(uint32_t*) bitstream;
-printf ("significand_limittab[%i] == %u\n", i, significand_limittab[i]);
+ printf ("significand_limittab[%i] == %u\n", i, significand_limittab[i]);
bitstream += 4;
}
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
insignificand_limittab[i] = *(uint32_t*) bitstream;
-printf ("insignificand_limittab[%i] == %u\n", i, insignificand_limittab[i]);
+ printf ("insignificand_limittab[%i] == %u\n", i, insignificand_limittab[i]);
bitstream += 4;
}
@@ -374,7 +362,7 @@
/**
- * for now we simply concatenate the entropy coder bitstreams
+ * concatenate entropy coder bitstreams
*/
static
void merge_bitstreams (uint8_t *bitstream,
@@ -385,7 +373,7 @@
{
int i;
- for (i=9; i>=0; i--) {
+ for (i=TYPE_BITS-1; i>=0; i--) {
memcpy (bitstream,
ENTROPY_CODER_BITSTREAM(&significand_bitstream[i]),
significand_limittab[i]);
@@ -393,7 +381,7 @@
bitstream += significand_limittab[i];
}
- for (i=9; i>=0; i--) {
+ for (i=TYPE_BITS-1; i>=0; i--) {
memcpy (bitstream,
ENTROPY_CODER_BITSTREAM(&insignificand_bitstream[i]),
insignificand_limittab[i]);
@@ -413,13 +401,13 @@
uint32_t byte_count;
int i;
- for (i=9; i>=0; i--) {
+ for (i=TYPE_BITS-1; i>=0; i--) {
byte_count = significand_limittab[i];
ENTROPY_DECODER_INIT(&significand_bitstream[i], bitstream, byte_count);
bitstream += byte_count;
}
- for (i=9; i>=0; i--) {
+ for (i=TYPE_BITS-1; i>=0; i--) {
byte_count = insignificand_limittab[i];
ENTROPY_DECODER_INIT(&insignificand_bitstream[i], bitstream, byte_count);
bitstream += byte_count;
@@ -431,14 +419,14 @@
uint8_t *bitstream,
uint32_t limit)
{
- ENTROPY_CODER significand_bitstream [10];
- ENTROPY_CODER insignificand_bitstream [10];
- uint32_t significand_limittab [10];
- uint32_t insignificand_limittab [10];
+ ENTROPY_CODER significand_bitstream [TYPE_BITS];
+ ENTROPY_CODER insignificand_bitstream [TYPE_BITS];
+ uint32_t significand_limittab [TYPE_BITS];
+ uint32_t insignificand_limittab [TYPE_BITS];
uint32_t byte_count;
int i;
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
ENTROPY_ENCODER_INIT(&significand_bitstream[i], limit);
ENTROPY_ENCODER_INIT(&insignificand_bitstream[i], limit);
}
@@ -455,7 +443,7 @@
merge_bitstreams (bitstream, significand_bitstream, insignificand_bitstream,
significand_limittab, insignificand_limittab);
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
ENTROPY_ENCODER_DONE(&significand_bitstream[i]);
ENTROPY_ENCODER_DONE(&insignificand_bitstream[i]);
}
@@ -468,10 +456,10 @@
uint8_t *bitstream,
uint32_t byte_count)
{
- ENTROPY_CODER significand_bitstream [10];
- ENTROPY_CODER insignificand_bitstream [10];
- uint32_t significand_limittab [10];
- uint32_t insignificand_limittab [10];
+ ENTROPY_CODER significand_bitstream [TYPE_BITS];
+ ENTROPY_CODER insignificand_bitstream [TYPE_BITS];
+ uint32_t significand_limittab [TYPE_BITS];
+ uint32_t insignificand_limittab [TYPE_BITS];
int i;
memset (buf->data, 0,
@@ -485,7 +473,7 @@
decode_coefficients (buf, significand_bitstream, insignificand_bitstream);
- for (i=0; i<10; i++) {
+ for (i=0; i<TYPE_BITS; i++) {
ENTROPY_DECODER_DONE(&significand_bitstream[i]);
ENTROPY_DECODER_DONE(&insignificand_bitstream[i]);
}
1.4 +16 -0 w3d/wavelet_xform.c
Index: wavelet_xform.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet_xform.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- wavelet_xform.c 2001/07/09 06:03:10 1.3
+++ wavelet_xform.c 2001/09/13 16:27:33 1.4
@@ -261,6 +261,14 @@
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
+ /* XXX FIXME: Ugly hack to workaround */
+ /* the short-row bug in high */
+ /* order xform functions */
+ if (n < 9)
+ a_moments = s_moments = 2;
+ if (n < 5)
+ a_moments = s_moments = 1;
+
fwd_analyze [a_moments] (x, d, stride, n);
fwd_synthesize [s_moments] (x, s, d, stride, n);
copyback_d (x, d, stride, n);
@@ -278,6 +286,14 @@
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
+
+ /* XXX FIXME: Ugly hack to workaround */
+ /* the short-row bug in high */
+ /* order xform functions */
+ if (n < 9)
+ a_moments = s_moments = 2;
+ if (n < 5)
+ a_moments = s_moments = 1;
copy_s_d (data, scratchbuf, stride, n);
inv_synthesize [s_moments] (x, s, d, stride, n);
1.8 +40 -0 w3d/yuv.c
Index: yuv.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/yuv.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- yuv.c 2001/09/07 10:56:30 1.7
+++ yuv.c 2001/09/13 16:27:33 1.8
@@ -1,5 +1,7 @@
#include "yuv.h"
+/*#define TARKIN_YUV_EXACT*/
+/*#define TARKIN_YUV_LXY*/
static inline
@@ -24,6 +26,12 @@
u [i] = ((int16_t) -44 * rgb [0] - 87 * rgb [1] + 131 * rgb [2]) / 256;
v [i] = ((int16_t) 131 * rgb [0] - 110 * rgb [1] - 21 * rgb [2]) / 256;
}
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgb+=3) {
+ y [i] = ((int16_t) 54 * rgb [0] + 182 * rgb [1] + 18 * rgb [2]) / 256;
+ u [i] = rgb [0] - y [i];
+ v [i] = rgb [2] - y [i];
+ }
#else
for (i=0; i<count; i++, rgb+=3) {
v [i] = rgb [0] - rgb [1];
@@ -48,6 +56,12 @@
rgb [1] = CLAMP(y [i] - 0.698 * v [i] - 0.336 * u [i]);
rgb [2] = CLAMP(y [i] + 1.732 * u [i]);
}
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgb+=3) {
+ rgb [1] = CLAMP(y [i] - (76 * u [i] - 26 * v [i]) / 256);
+ rgb [0] = CLAMP(y [i] + u [i]);
+ rgb [2] = CLAMP(y [i] + v [i]);
+ }
#else
for (i=0; i<count; i++, rgb+=3) {
rgb [1] = CLAMP(y [i] - (u [i] + v [i]) / 4);
@@ -72,6 +86,12 @@
u [i] = ((int16_t) -44 * rgb [0] - 87 * rgb [1] + 131 * rgb [2]) / 256;
v [i] = ((int16_t) 131 * rgb [0] - 110 * rgb [1] - 21 * rgb [2]) / 256;
}
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgb+=4) {
+ y [i] = ((int16_t) 54 * rgb [0] + 182 * rgb [1] + 18 * rgb [2]) / 256;
+ u [i] = rgb [0] - y [i];
+ v [i] = rgb [2] - y [i];
+ }
#else
for (i=0; i<count; i++, rgb+=4) {
v [i] = rgb [0] - rgb [1];
@@ -96,6 +116,12 @@
rgb [1] = CLAMP(y [i] - 0.698 * v [i] - 0.336 * u [i]);
rgb [2] = CLAMP(y [i] + 1.732 * u [i]);
}
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgb+=4) {
+ rgb [1] = CLAMP(y [i] - (76 * u [i] - 26 * v [i]) / 256);
+ rgb [0] = CLAMP(y [i] + u [i]);
+ rgb [2] = CLAMP(y [i] + v [i]);
+ }
#else
for (i=0; i<count; i++, rgb+=4) {
rgb [1] = CLAMP(y [i] - (u [i] + v [i]) / 4);
@@ -122,6 +148,13 @@
v [i] = ((int16_t) 131 * rgba [0] - 110 * rgba [1] - 21 * rgba [2]) / 256;
a [i] = rgba [3];
}
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgba+=4) {
+ y [i] = ((int16_t) 54 * rgba [0] + 182 * rgba [1] + 18 * rgba [2]) / 256;
+ u [i] = rgba [0] - y [i];
+ v [i] = rgba [2] - y [i];
+ a [i] = rgba [3];
+ }
#else
for (i=0; i<count; i++, rgba+=4) {
v [i] = rgba [0] - rgba [1];
@@ -147,6 +180,13 @@
rgba [0] = CLAMP(y [i] + 1.371 * v [i]);
rgba [1] = CLAMP(y [i] - 0.698 * v [i] - 0.336 * u [i]);
rgba [2] = CLAMP(y [i] + 1.732 * u [i]);
+ rgba [3] = a [i];
+ }
+#elif defined(TARKIN_YUV_LXY)
+ for (i=0; i<count; i++, rgba+=4) {
+ rgba [1] = CLAMP(y [i] - (76 * u [i] - 26 * v [i]) / 256);
+ rgba [0] = CLAMP(y [i] + u [i]);
+ rgba [2] = CLAMP(y [i] + v [i]);
rgba [3] = a [i];
}
#else
1.2 +1 -0 w3d/docs/Makefile
Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/Makefile,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- Makefile 2001/06/25 07:56:10 1.1
+++ Makefile 2001/09/13 16:27:35 1.2
@@ -11,3 +11,4 @@
clean:
$(RM) $(TARGET) $(TARGET).gz $(TARGET:.ps=.dvi) *.log *.aux
+
1.2 +18 -3 w3d/docs/bibliography.tex
Index: bibliography.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/bibliography.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- bibliography.tex 2001/06/25 07:56:10 1.1
+++ bibliography.tex 2001/09/13 16:27:35 1.2
@@ -1,4 +1,8 @@
+Marco maintains an interesting link and paper collection, the URL is posted
+regulary on the takin-dev mailing list.
+
+
\begin{thebibliography}{888}
\bibitem{salomon}
@@ -12,7 +16,8 @@
\bibitem{athome}
-Denis Zorin, Wim Sweldens, ????, "Building your own Wavelets at Home",
+Denis Zorin, Wim Sweldens, ????,
+"Building your own Wavelets at Home",
(good introduction to lifting wavelets, available as \verb|athome.ps| on the homepages of the authors)
@@ -21,17 +26,27 @@
"Lossless Image Compression using Integer to Integer Wavelet Transforms",
(brief introduction to integer transforms, \verb|icip97.ps|)
+\bibitem{opticalflow}
+J.L. Barron, D.J. Fleet, S.S. Beauchemin,
+"Performance of Optical Flow Techniques",
+A really good introduction how to determine the motion flow in image sequences;
+it compares different approaches and algorithms. Online available as
+\verb|barron92performance.ps.gz|.
+Take a look!
+
\bibitem{noise}
Marcus J. Nadenau, Julien Reichel, Murat Kunt,
"Visually improved image compression by combining conventional wavelet codec
-with texture modelling", (available as \verb|Noise_IEEE_Final.pdf| on the web)
+with texture modelling",
+(available as \verb|Noise_IEEE_Final.pdf| on the web)
\bibitem{zcoder}
L\'eon Bottou, Paul G. Howard, Yoshua Bengio,
"The Z-Coder Adaptive Binary Coder",
(a fast and effective binary entropy coder; paper is available on AT\&T's
-DjVu homepage \verb|djvu.att.com|)
+DjVu homepage \verb|djvu.att.com|. We won't use this because of unresolved
+patent issues but nevertheless it's a nice and fast algorithm)
\end{thebibliography}
1.2 +12 -1 w3d/docs/colorspace.tex
Index: colorspace.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/colorspace.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- colorspace.tex 2001/06/25 07:56:10 1.1
+++ colorspace.tex 2001/09/13 16:27:35 1.2
@@ -39,7 +39,7 @@
You can understand this transform as reversible (1,2) - wavelet transform on a row
of three data items. It is expanding (8 input bits require 9 output bits) because
-of the subtraction.
+of the subtraction -- but this doesn't matter since we need 16bit integers anyway.
As usual we can generate the inverse transform by running the algorithm
backwards and inverting all operations:
@@ -53,4 +53,15 @@
If someone needs as 'exact YUV to this colorspace' transform he can simply
multiply the two transform matrices together.
+
+\subsection{ The Lxy Colorspace }
+
+I implemented an integer version of the Lxy colorspace as suggested on the
+tarkin-dev mailing list. It's not well tested and seems to be buggy due to
+roundoff errors.
+You can enable it by defining \verb|TARKIN_YUV_LXY| on top of file \verb|yuv.c|.
+
+Feel free to fix bugs and send patches.
+
+
1.2 +21 -3 w3d/docs/entropycoder.tex
Index: entropycoder.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/entropycoder.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- entropycoder.tex 2001/06/25 07:56:10 1.1
+++ entropycoder.tex 2001/09/13 16:27:35 1.2
@@ -1,8 +1,26 @@
\section{ Entropy Coder }
+\label{entropy}
-For now we use a simple combined Runleght-Huffman-Coder. This is not very
-efficient and should be replaced for example by an arithmetic entropy coder.
+The coefficient scanner outputs two raw bitstreams for each bitplane which
+have some special properties which make them easy to compress.
+The more significand bitplanes of the coefficients are almost empty, thus
+the corresponding bitstreams have very long runs of $0$-bits. This makes
+them easy to compress using a Runlength Coder. The bitstreams describing
+the first significand bits of smaller coefficients have similiar properties
+but a bit shorter runs.
-Any Volunteers ?
+Runlengths are the written as pair of two codes into the new compressed stream:
+\verb|number of required bits| and
+\verb|binary written runlength|. The first bit of runlength can be omitted;
+it's always $1$. The number of bits required to code the runlength are huffman
+coded. This is currently done with an ugly and pretty inefficient static
+huffman coder, it should better done with an adaptive huffman coder or a
+range coder. (Any Volunteers?)
+
+Insignificand bits (the bits of a coefficient after the first significand bit)
+are almost random, it doesn't makes sense to spend much energy on trying
+to compress them. But some of them -- especially for low frequency
+coefficients -- need to be transmitted in order to prevent a DC offset or low
+frequency color floating.
1.2 +30 -1 w3d/docs/intro.tex
Index: intro.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/intro.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- intro.tex 2001/06/25 07:56:10 1.1
+++ intro.tex 2001/09/13 16:27:35 1.2
@@ -13,7 +13,36 @@
in the encoder. Have fun !
-\section{ Overview }
+\section{ Overview about the highlevel part }
+\subsection{ Or: How it may work when it's done }
+
+The incoming images should get transformed into a motion flow field. This
+has some nice properties which makes it well to compress. It's
+complexity is independent of image object complexities and speeds. It only
+depends on the number of objects in the image and their speed divergence --
+the worst case would be a image with hundrets of small fast moving objects.
+Since the human eye has similiar troubles in analyzing such images we
+can hope that artifacts here won't matter.
+Such smooth motion fields are ideal to compress using wavelets -- a panorama
+move could be stored theoretically in the DC coefficient \dots
+
+To encode a block of frames (say 16 or 32 for example) we may first encode
+a I-Frame, the first or center image of this block by wavelet compressing it.
+Then the motion fields relative to this frame get wavelet compressed (3D or
+2D+Frame differencing) and transmitted. Since some cases can't be
+efficiently expressed in motion fields (imagine an object which was outside the
+reference image and is now moving in) we need some additional error correction
+informations, these can be simple differences of the reconstructed image after
+application of the relative motion field and the original images. These
+differences could get wavelet encoded and then transmitted.
+
+For now have we the wavelet transform code, the coefficient encoder and a
+working but not very efficient entropy coder. Since the above steps all require
+these tools I think we have a base we can work on. What we need now is the
+motion flow detection and the putting-it-all-together-framework.
+
+
+\section{ Overview about the lowlevel part }
Almost all steps in the compression codec try to transform data into a
representation with a few large numbers and many smaller ones which need
1.2 +35 -8 w3d/docs/quantizer.tex
Index: quantizer.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/quantizer.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- quantizer.tex 2001/06/25 07:56:10 1.1
+++ quantizer.tex 2001/09/13 16:27:35 1.2
@@ -1,14 +1,41 @@
-\section{ The Coefficient Quantizer }
+\section{ Quantizing, Merging the Bitstreams }
-I'll describe this as soon it works \dots
+The relevant code is in \verb|wavelet_coeff.c|.
-The relevant code is in \verb|wavelet.c|.
-For now only this: we don't quantize the coefficients explizitly but transmit
-them bitplane-by-bitplane (significand and insignificand bits in different
-bitstreams, thus two streams per bitplane).
+Wavelet coefficients are scanned linear in each quadrant, in the 2D case like
+this: $HL$ $LH$ $LL$, then $HL^1$ $LH^1$ $LL^1$ in $HH$ and so forth.
+We don't quantize the coefficients explizitly but transmit
+them bitplane-by-bitplane (significand and insignificand bits in different
+bitstreams, thus two streams per bitplane). Signs get encoded in the bitstream
+of the first significand bitplane.
-When you don't transmit the entire bitstream you quantize and threshold the
-coefficients implicitly by cutting away insignificand bits and small
+All bitplanes are encoded in parallel, so we only need a single pass to
+transmit all coefficients. Later the resulting bitstreams get entropy coded
+(see section \ref{entropy}) and merged (see below).
+When you don't transmit the entire bitstream you quantize and threshold the
+coefficients implicitly by cutting away insignificand bits and small
coefficients.
+
+
+\subsection { Merging the Bitstreams }
+
+After Coefficient scanning and entropy coding we have a set of about 9 or 10
+bitstreams. The function \verb|merge_bitstreams()| merges them into a single
+stream which will be written to the file.
+This is process is controlled by truncation tables which are created in
+\verb|setup_limittabs()|. There we can easy play with different approaches to
+cut+merge the bitstreams.
+
+Currently each less significand bitstream gets about half as long as its
+next more significand bitstream. Significand bitstreams get $4/8$ of the
+bit budget, insignificand ones the rest.
+Another approach would be to try to give all streams equal lengths, this
+would mean to transmit equal energies at all frequencies.
+
+Unfortunally we have to transmit these tables in order to reconstruct the per
+bitplane streams, this done using binary 32bit numbers for now. At low
+bitrates we quickly spend half of the bit budget on the truncation tables.
+Since these tables contain mostly small numbers they should compress well
+and we should compress them.
1.2 +2 -2 w3d/docs/wavelet.tex
Index: wavelet.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/wavelet.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- wavelet.tex 2001/06/25 07:56:10 1.1
+++ wavelet.tex 2001/09/13 16:27:35 1.2
@@ -81,13 +81,13 @@
Now we have a lowpass filtered image on the left and the highpass coefficients
on the right side of the row. This Filter is applied again to the lowpass image
-on the left ($n$ is now $(n+1)/2$ until $n$ becomes $1$.
+on the left ($n$ is now $(n+1)/2$) until $n$ becomes $1$.
\subsection{ The inverse Transform }
-To reconstruct the original data we simply can reverse all operations and apply
+To reconstruct the original data we can simply reverse all operations and apply
them in reversed direction:
\begin{center}
1.5 +3 -3 w3d/tools/Makefile
Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/tools/Makefile,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- Makefile 2001/08/07 14:18:07 1.4
+++ Makefile 2001/09/13 16:27:36 1.5
@@ -4,7 +4,7 @@
CFLAGS = -g -O0 -Wall -I.. -DTYPE=uint16_t
LFLAGS = -g
-TARGETS = ppmdiff yuv2ppm deinterlace
+TARGETS = pnmdiff yuv2ppm deinterlace
OBJS = $(TARGETS:=.o) ../pnm.o
SRCS = $(OBJS:.o=.c)
@@ -12,8 +12,8 @@
all: $(OBJS) $(TARGETS)
-ppmdiff: ppmdiff.o ../pnm.o
- $(CC) $(LFLAGS) ppmdiff.o ../pnm.o -o $@
+pnmdiff: pnmdiff.o ../pnm.o
+ $(CC) $(LFLAGS) pnmdiff.o ../pnm.o -o $@
yuv2ppm: yuv2ppm.o ../pnm.o
$(CC) $(LFLAGS) yuv2ppm.o ../pnm.o -o $@
--- >8 ----
List archives: http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'cvs-request at xiph.org'
containing only the word 'unsubscribe' in the body. No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.
More information about the commits
mailing list