[xiph-cvs] cvs commit: w3d/docs Makefile bibliography.tex colorspace.tex entropycoder.tex intro.tex main.tex quantizer.tex wavelet.tex
Holger Waechtler
holger at xiph.org
Mon Jun 25 00:56:11 PDT 2001
holger 01/06/25 00:56:11
Modified: . Makefile README TODO
WHAT_THE_HECK_IS_THIS_CODE_DOING main.c rle.h
tarkin.h wavelet.c wavelet.h yuv.c yuv.h
Added: . _test_bitcoder.c _test_huffman.c _test_rle.c
tarkin.c wavelet_xform.c
docs Makefile bibliography.tex colorspace.tex
entropycoder.tex intro.tex main.tex quantizer.tex
wavelet.tex
Removed: . coder.c.in coder.h
Log:
- rewrote wavelet xform code, it now allows filters with different
numbers of vanishing moments. Slower but cleaner and simpler to
play with different wavelets.
- wrote a new single-pass coefficient encoder/quantizer
- some initial documentation in the docs/ directory.
- regression tests for bitcoder, huffman coder and RLE/Huffmann entropy coder
- some code to write the bitstreams in files; not yet complete and something
to never get finished -- we'll use OGG streams sooner or later ;)
Revision Changes Path
1.3 +19 -11 w3d/Makefile
Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/Makefile,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- Makefile 2001/03/28 13:46:58 1.2
+++ Makefile 2001/06/25 07:56:07 1.3
@@ -1,31 +1,39 @@
CC = gcc
RM = rm -rf
-CFLAGS = -g -O0 -Wall -DTYPE=int16_t
-LFLAGS =
+CFLAGS = -g -O0 -Wall -DTYPE=int16_t -DRLECODER
+LFLAGS = -g
-OBJS = coder.o main.o wavelet.o yuv.o
+OBJS = wavelet.o wavelet_xform.o yuv.o tarkin.o main.o
SRCS = $(OBJS:.o=.c)
+TEST_TARGETS = _test_bitcoder _test_rle _test_huffman
+TEST_OBJS = $(TEST_TARGETS:=.o)
+TEST_SRCS = $(TEST_OBJS:.o=.c)
TARGET = main
-all: .depend $(TARGET)
+all: $(TARGET)
-$(TARGET): .depend $(OBJS)
+$(TARGET): $(OBJS)
$(CC) $(LFLAGS) $(OBJS) -o $@
-coder.c: coder.c.in rle.h
- cpp -P $< | indent -i3 -kr -bad > $@
-
.c.o: .depend
$(CC) $(CFLAGS) -c $<
clean:
- $(RM) $(OBJS) $(TARGET) core .depend .depend.bak rle.histogram *.ppm coder.c
+ $(RM) $(OBJS) $(TARGET) gmon.out core .depend .depend.bak rle.histogram *.ppm
+ $(RM) $(TEST_TARGETS) $(TEST_OBJS)
+
+
+test: .depend $(TEST_TARGETS)
+ ./_test_bitcoder
+ ./_test_huffman
+ ./_test_rle
-.depend: $(SRCS)
+.depend: $(SRCS) $(TEST_SRCS)
+ $(RM) .depend
touch .depend
- makedepend -f.depend -- $(CFLAGS) -- $(SRCS) coder.c.in
+ sh makedepend -f.depend -- $(CFLAGS) -- $(SRCS) $(TEST_SRCS)
-include .depend
1.2 +1 -2 w3d/README
Index: README
===================================================================
RCS file: /usr/local/cvsroot/w3d/README,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- README 2001/02/13 01:36:52 1.1
+++ README 2001/06/25 07:56:07 1.2
@@ -1,8 +1,7 @@
This is a video codec based on an integer wavelet in 3 dimensions (x,
y, and time/frame). What documentation exists so far is on the
vorbis-dev and (now) tarkin-dev mailing lists at xiph.org. Some brief
-documentation (to be expanded on later) is also in
-"WHAT_THE_HECK_IS_THIS_CODE_DOING".
+documentation can be found in the w3d/docs directory.
For sample / test streams, see http://media.xiph.org/
(and feel free to submit more streams if you have them).
1.3 +18 -4 w3d/TODO
Index: TODO
===================================================================
RCS file: /usr/local/cvsroot/w3d/TODO,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- TODO 2001/03/28 13:46:58 1.2
+++ TODO 2001/06/25 07:56:07 1.3
@@ -1,7 +1,21 @@
- - write avitow3d/quicktimetow3d/player/recorder (a libsndfile/libaudiofile alike video library would be great !)
- - (4,4) - Wavelets
- - arithmetic binary entropy coders may be faster, simpler and more efficient
+Here only the wavelet-related TODO's:
+
+ - arithmetic binary entropy coders may be faster, simpler and more efficient;
+ implement the ZP-Coder
+ - design/implement a stream format
+ - write avitotarkin/quicktimetotarkin/mpegtotarkin/player/recorder
+ (a libsndfile/libaudiofile alike video library would be great !)
- profile
- - rewrite wavelet xform code, the current implementation forces cache misses
+ - add special transform functions for large strides to prevent cache misses
- introduce fast paths in coefficient decoder if (mps == 0)
- mmx/3dnow/sse/altivec
+
+
+other TODO's:
+
+ - think about a multiresolution multidimensional motion detection scheme
+ - 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
+ mask seperation algorithm
+
1.2 +17 -14 w3d/WHAT_THE_HECK_IS_THIS_CODE_DOING
Index: WHAT_THE_HECK_IS_THIS_CODE_DOING
===================================================================
RCS file: /usr/local/cvsroot/w3d/WHAT_THE_HECK_IS_THIS_CODE_DOING,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- WHAT_THE_HECK_IS_THIS_CODE_DOING 2001/02/13 00:56:02 1.1
+++ WHAT_THE_HECK_IS_THIS_CODE_DOING 2001/06/25 07:56:07 1.2
@@ -1,8 +1,17 @@
+This is deprecated. Take a look in the w3d/docs directory.
+
+The command line semantics are changed. You have to call the test program
+now like this:
+
+./main ../clips/venuscubes-ppm/AnimSpace00%03d.ppm 1000 400 400 4 4
+
+------------------------------------------------------------------------------
+
Hi,
this is a experimental 3d-integer-wavelet-video compression codec. Since the
-integer wavelet transformation is reversible and a reversible rgb-yuv conversion
+integer wavelet transform is reversible and a reversible rgb-yuv conversion
is used (you can understand it as (1,2) integer wavelet transform, too), this
codec should be lossless if you transmit the whole bitstream.
The Y/U/V-bitstreams are embedded, thus you can simply get lossy compression
@@ -12,7 +21,7 @@
Here is how the current code works:
-First we grab N_FRAMES (defined in main.c) frames from a video4linux device.
+First we grab a block of N_FRAMES frames (defined in main.c) of .ppm files.
Then each pixel becomes transformed into a YUV-alike colorspace. Take a look in
yuv.c to see how it is done. Each component is then transformed into frequency
space by applying the wavelet transform in x, y and frame direction.
@@ -38,20 +47,14 @@
You can call the test program like this:
- $ ./main 20000 5000 5000 /dev/video1
+ $ ./main 20000 5000 5000 ../clips/%i.ppm
-which means: images are grabbed from '/dev/video1', the Y component bitstream
-is limited to 20000 Bytes, the U and V bitstreams to 5000 Bytes.
-The last argument may be omitted.
-
-Since video_device_grab_frame() uses a read() call to grab the image, it may
-not work with some bttv drivers. Rewrite this function for mmap()'d access if
-you want. Or even better, write something to read frames from mpeg/quicktime/avi
-movies. And design a simple file format with multiplexed bitstreams. And write
-a player. And ...
-Take a look in the TODO file.
+which means: images are grabbed from directory ../clips/0.ppm, ../clips/1.ppm,
+etc. The Y component bitstream is limited to 20000 Bytes, the U and V bitstreams
+to 5000 Bytes. If the last argument is omitted, frames are taken from current
+directory.
Good Luck,
-- Holger Waechtler <hwaechtler at users.sourceforge.net>
+- Holger <hwaechtler at users.sourceforge.net>
1.4 +58 -46 w3d/main.c
Index: main.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/main.c,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- main.c 2001/03/28 14:32:53 1.3
+++ main.c 2001/06/25 07:56:07 1.4
@@ -1,9 +1,9 @@
+#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "wavelet.h"
-#include "coder.h"
#include "yuv.h"
#include "rle.h"
@@ -143,31 +143,41 @@
int i, ycount, ucount, vcount;
int ylimit, ulimit, vlimit;
int width = -1, height = -1, frames = 0, frame = 0;
+ int a_moments, s_moments;
- if (argc == 5)
- fmt = argv[4];
- else if (argc != 4) {
+ if (argc == 1) {
+ ylimit = 1000;
+ ulimit = 150;
+ vlimit = 150;
+ a_moments = 2;
+ s_moments = 2;
+ } else if (argc == 7) {
+ fmt = argv[1];
+ ylimit = strtol (argv[2], 0, 0);
+ ulimit = strtol (argv[3], 0, 0);
+ vlimit = strtol (argv[4], 0, 0);
+ a_moments = strtol (argv[5], 0, 0);
+ s_moments = strtol (argv[6], 0, 0);
+ } else {
printf ("\n"
- " usage: %s <ylimit> <ulimit> <vlimit> <input filename format string>\n"
+ " usage: %s <input filename format string> <ylimit> <ulimit> <vlimit> <a_m> <s_m>\n"
"\n"
- " ylimit, ulimit, vlimit: cut Y/U/V bitstream after limit bytes/frame\n"
" input ppm filename format: optional, \"%%i.ppm\" by default\n"
+ " ylimit, ulimit, vlimit: cut Y/U/V bitstream after limit bytes/frame\n"
+ " a_m, s_m: number of vanishing moments of the\n"
+ " analysis/synthesis filter, (2,2) by default\n"
"\n", argv[0]);
exit (-1);
}
- ylimit = strtol (argv[1], 0, 0);
- ulimit = strtol (argv[2], 0, 0);
- vlimit = strtol (argv[3], 0, 0);
-
if (read_ppm_info (fmt, &width, &height) < 0)
exit (-1);
rgb = malloc (width * height * 3 * N_FRAMES);
rgb2 = malloc (width * height * 3 * N_FRAMES);
- bitstream[0] = malloc (width * height * N_FRAMES);
- bitstream[1] = malloc (width * height * N_FRAMES);
- bitstream[2] = malloc (width * height * N_FRAMES);
+ bitstream[0] = malloc (width * height * N_FRAMES*2);
+ bitstream[1] = malloc (width * height * N_FRAMES*2);
+ bitstream[2] = malloc (width * height * N_FRAMES*2);
if (!rgb || !rgb2 || !bitstream[0] || !bitstream[1] || !bitstream[2]) {
printf ("memory allocation failed.\n");
@@ -203,21 +213,21 @@
return (-1);
}
- save_ppm ("orig%i.ppm", rgb, width, height, frame, frames);
+ save_ppm ("orig%03d.ppm", rgb, width, height, frame, frames);
- rgb2yuv (rgb, y->data, u->data, v->data, width * height * frames, 3);
+ rgb24_to_yuv (rgb, y->data, u->data, v->data, width * height * frames, 3);
/*
- save_ppm16 ("y%i.ppm", y->data, width, height, frame, frames);
- save_ppm16 ("u%i.ppm", u->data, width, height, frame, frames);
- save_ppm16 ("v%i.ppm", v->data, width, height, frame, frames);
+ save_ppm16 ("y%03d.ppm", y->data, width, height, frame, frames);
+ save_ppm16 ("u%03d.ppm", u->data, width, height, frame, frames);
+ save_ppm16 ("v%03d.ppm", v->data, width, height, frame, frames);
*/
- wavelet_3d_buf_fwd_xform (y);
- wavelet_3d_buf_fwd_xform (u);
- wavelet_3d_buf_fwd_xform (v);
-
- save_ppm16 ("y.coeff%i.ppm", y->data, width, height, frame, frames);
- save_ppm16 ("u.coeff%i.ppm", u->data, width, height, frame, frames);
- save_ppm16 ("v.coeff%i.ppm", v->data, width, height, frame, frames);
+ wavelet_3d_buf_fwd_xform (y, a_moments, s_moments);
+ wavelet_3d_buf_fwd_xform (u, a_moments, s_moments);
+ wavelet_3d_buf_fwd_xform (v, a_moments, s_moments);
+
+ save_ppm16 ("y.coeff%03d.ppm", y->data, width, height, frame, frames);
+ save_ppm16 ("u.coeff%03d.ppm", u->data, width, height, frame, frames);
+ save_ppm16 ("v.coeff%03d.ppm", v->data, width, height, frame, frames);
ycount = width * height * frames;
ucount = width * height * frames;
@@ -227,40 +237,42 @@
if (ucount > frames * ulimit) ucount = frames * ulimit;
if (vcount > frames * vlimit) vcount = frames * vlimit;
- ycount = encode_coeff3d (y, bitstream [0], ycount);
- ucount = encode_coeff3d (u, bitstream [1], ucount);
- vcount = encode_coeff3d (v, bitstream [2], vcount);
-
- decode_coeff3d (y2, bitstream [0], ycount);
- decode_coeff3d (u2, bitstream [1], ucount);
- decode_coeff3d (v2, bitstream [2], vcount);
+ ycount = wavelet_3d_buf_encode_coeff (y, bitstream [0], ycount*2);
+ ucount = wavelet_3d_buf_encode_coeff (u, bitstream [1], ucount*2);
+ vcount = wavelet_3d_buf_encode_coeff (v, bitstream [2], vcount*2);
+
+ wavelet_3d_buf_decode_coeff (y2, bitstream [0], ycount);
+ wavelet_3d_buf_decode_coeff (u2, bitstream [1], ucount);
+ wavelet_3d_buf_decode_coeff (v2, bitstream [2], vcount);
for (i=0; i<width*height*frames; i++) {
rgb [3*i] = (y->data[i] == y2->data [i]) ? 0 : ~0;
rgb [3*i+1] = (u->data[i] == u2->data [i]) ? 0 : ~0;
rgb [3*i+2] = (v->data[i] == v2->data [i]) ? 0 : ~0;
-/*if (y->data[i] != y2->data [i]) {
- printf ("%i: %i <-> %i\n", i, y->data[i], y2->data[i]);
+/*
+if (y->data[i] != y2->data [i]) {
+ printf ("error %i: %i <-> %i\n", i, y->data[i], y2->data[i]);
bit_print (y->data[i]);
bit_print (y2->data[i]);
-}*/
+}
+*/
}
- save_ppm ("coeffdiff%i.ppm", rgb, width, height, frame, frames);
+ save_ppm ("coeffdiff%03d.ppm", rgb, width, height, frame, frames);
- save_ppm16 ("y.rcoeff%i.ppm", y2->data, width, height, frame, frames);
- save_ppm16 ("u.rcoeff%i.ppm", u2->data, width, height, frame, frames);
- save_ppm16 ("v.rcoeff%i.ppm", v2->data, width, height, frame, frames);
+ save_ppm16 ("y.rcoeff%03d.ppm", y2->data, width, height, frame, frames);
+ save_ppm16 ("u.rcoeff%03d.ppm", u2->data, width, height, frame, frames);
+ save_ppm16 ("v.rcoeff%03d.ppm", v2->data, width, height, frame, frames);
- wavelet_3d_buf_inv_xform (y2);
- wavelet_3d_buf_inv_xform (u2);
- wavelet_3d_buf_inv_xform (v2);
+ wavelet_3d_buf_inv_xform (y2, a_moments, s_moments);
+ wavelet_3d_buf_inv_xform (u2, a_moments, s_moments);
+ wavelet_3d_buf_inv_xform (v2, a_moments, s_moments);
- save_ppm16 ("yr%i.ppm", y2->data, width, height, frame, frames);
- save_ppm16 ("ur%i.ppm", u2->data, width, height, frame, frames);
- save_ppm16 ("vr%i.ppm", v2->data, width, height, frame, frames);
+ save_ppm16 ("yr%03d.ppm", y2->data, width, height, frame, frames);
+ save_ppm16 ("ur%03d.ppm", u2->data, width, height, frame, frames);
+ save_ppm16 ("vr%03d.ppm", v2->data, width, height, frame, frames);
- yuv2rgb (y2->data, u2->data, v2->data, rgb2, width * height * frames, 3);
+ yuv_to_rgb24 (y2->data, u2->data, v2->data, rgb2, width * height * frames, 3);
save_ppm ("out%03d.ppm", rgb2, width, height, frame, frames);
1.2 +57 -81 w3d/rle.h
Index: rle.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/rle.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- rle.h 2001/03/28 13:46:58 1.1
+++ rle.h 2001/06/25 07:56:07 1.2
@@ -1,75 +1,38 @@
#ifndef __RLE_H
#define __RLE_H
-#include <stdio.h>
-#include <stdint.h>
+#include "bitcoder.h"
+#if defined(RLECODER)
-#define RLE_HISTOGRAM 1
+#define OUTPUT_BIT(rlecoder,bit) rlecoder_write_bit(rlecoder,bit)
+#define INPUT_BIT(rlecoder) rlecoder_read_bit(rlecoder)
+#define OUTPUT_BIT_DIRECT(coder,bit) bitcoder_write_bit(&(coder)->bitcoder,bit)
+#define INPUT_BIT_DIRECT(rlecoder) bitcoder_read_bit(&(rlecoder)->bitcoder)
+#define ENTROPY_CODER RLECoderState
+#define ENTROPY_ENCODER_INIT(coder,limit) rlecoder_encoder_init(coder,limit)
+#define ENTROPY_ENCODER_DONE(coder) rlecoder_encoder_done(coder)
+#define ENTROPY_ENCODER_FLUSH(coder) rlecoder_encoder_flush(coder)
+#define ENTROPY_DECODER_INIT(coder,bitstream,limit) \
+ rlecoder_decoder_init(coder,bitstream,limit)
+#define ENTROPY_DECODER_DONE(coder) /* nothing to do ... */
+#define ENTROPY_CODER_IS_EMPTY(coder) bitcoder_is_empty(&(coder)->bitcoder)
+#define ENTROPY_CODER_BITSTREAM(coder) ((coder)->bitcoder.bitstream)
+#endif
-typedef struct {
- int bit_count; /* number of valid bits in byte */
- uint8_t byte; /* buffer to save bits */
- int byte_count; /* number of bytes written */
- uint8_t *bitstream;
- size_t limit; /* don't write more bytes to bitstream ... */
-} BitCoderState;
+#define RLE_HISTOGRAM 1
+
typedef struct {
- int mps; /* more probable symbol */
- int count; /* have seen count+1 mps's */
+ int mps; /* more probable symbol */
+ uint32_t count; /* have seen count+1 mps's */
BitCoderState bitcoder;
} RLECoderState;
-static inline
-void bitcoder_write_bit (BitCoderState *s, int bit)
-{
- s->byte <<= 1;
-
- if (bit)
- s->byte |= 1;
-
- s->bit_count++;
- if (s->bit_count == 8 && s->byte_count < s->limit) {
- s->bitstream [s->byte_count++] = s->byte;
- s->bit_count = 0;
- }
-}
-
-
-static inline
-int bitcoder_read_bit (BitCoderState *s)
-{
- int ret;
-
- if (s->bit_count == 0 && s->byte_count < s->limit) {
- s->byte = s->bitstream [s->byte_count++];
- s->bit_count = 8;
- }
-
- ret = (s->byte & 0x80) >> 7;
- s->byte <<= 1;
- s->bit_count--;
-
- return ret;
-}
-
-
-static inline
-size_t bitcoder_flush (BitCoderState *s)
-{
- if (s->bit_count > 0 && s->byte_count < s->limit)
- s->bitstream [s->byte_count++] = s->byte;
-
-printf ("%s: %i bytes written.\n", __FUNCTION__, s->byte_count);
- return s->byte_count;
-}
-
-
/*
* Ugly.
*/
@@ -115,6 +78,7 @@
}
}
+
/*
* special handling if (x > 2^32 - 2) ???
*/
@@ -154,13 +118,13 @@
int i;
bitcoder_write_bit (s, 0);
for (i=7; i>=0; i--)
- bitcoder_write_bit (s, x & (1 << i));
+ bitcoder_write_bit (s, (x >> i) & 1);
} else {
int i;
x -= 0xff;
bitcoder_write_bit (s, 1);
for (i=31; i>=0; i--)
- bitcoder_write_bit (s, x & (1 << i));
+ bitcoder_write_bit (s, (x >> i) & 1);
}
}
@@ -171,6 +135,7 @@
uint32_t max_runlength;
#endif
+
/*
* bit should be 0 or 1 !!!
*/
@@ -182,15 +147,14 @@
memset (histogram, 0, 512*sizeof(uint32_t));
max_runlength = 0;
#endif
- s->mps = bit ? 1 : 0;
+ s->mps = bit & 1;
s->count = 0;
huffmancoder_write (&s->bitcoder, bit ? 1 : 0);
}
- if ((bit & 1) == s->mps)
+ if ((bit & 1) == s->mps) {
s->count++;
- else {
-
+ } else {
#ifdef RLE_HISTOGRAM
if (s->count < 511)
histogram [s->count-1]++;
@@ -199,7 +163,6 @@
if (max_runlength < s->count)
max_runlength = s->count-1;
#endif
-
huffmancoder_write (&s->bitcoder, s->count-1);
s->mps = ~s->mps & 1;
s->count = 1;
@@ -226,13 +189,39 @@
+static inline
+void rlecoder_encoder_init (RLECoderState *s, uint32_t limit)
+{
+ s->mps = -1;
+ s->count = 0;
+ bitcoder_encoder_init (&s->bitcoder, limit);
+}
-/*
- * returns the number of valid bytes in
+
+/**
+ * once you called this, you better should not encode any more symbols ...
*/
static inline
-size_t rlecoder_done (RLECoderState *s)
+uint32_t rlecoder_encoder_flush (RLECoderState *s)
{
+ huffmancoder_write (&s->bitcoder, s->count-1);
+
+ return bitcoder_flush (&s->bitcoder);
+}
+
+
+static inline
+void rlecoder_decoder_init (RLECoderState *s, uint8_t *bitstream, uint32_t limit)
+{
+ s->mps = -1;
+ s->count = 0;
+ bitcoder_decoder_init (&s->bitcoder, bitstream, limit);
+}
+
+
+static inline
+void rlecoder_encoder_done (RLECoderState *s)
+{
#ifdef RLE_HISTOGRAM
FILE *f = fopen ("rle.histogram", "w");
int i;
@@ -242,22 +231,9 @@
fprintf (f, "%i %u\n", i, histogram[i]);
fclose (f);
#endif
-
- return bitcoder_flush (&s->bitcoder);
+ bitcoder_encoder_done (&s->bitcoder);
}
-
-static inline
-void bit_print (TYPE byte)
-{
- int bit = 8*sizeof(TYPE);
-
- do {
- bit--;
- printf ((byte & (1 << bit)) ? "1" : "0");
- } while (bit);
- printf ("\n");
-}
#endif
1.3 +36 -14 w3d/tarkin.h
Index: tarkin.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- tarkin.h 2001/03/28 13:46:58 1.2
+++ tarkin.h 2001/06/25 07:56:07 1.3
@@ -1,33 +1,55 @@
#ifndef __TARKIN_H
#define __TARKIN_H
-typedef enum { TARKIN_RGB, TARKIN_RGBA, TARKIN_GRAYSCALE, TARKIN_ALPHA } VideoChannelType;
+#include "wavelet.h"
+typedef enum {
+ TARKIN_GRAYSCALE,
+ TARKIN_RGB24, /* tight packed RGB */
+ TARKIN_RGB32, /* 32bit, no alphachannel */
+ TARKIN_RGBA, /* dito w/ alphachannel */
+ TARKIN_ARGB,
+ TARKIN_BGRA
+} TarkinColorFormat;
+
+typedef enum {
+ TARKIN_SIGNATURE_NOT_FOUND = -2,
+ TARKIN_IO_ERROR = -1,
+ TARKIN_OK = 0
+} TarkinError;
+
typedef struct {
- char *name;
- VideoChannelType type;
- uint32 n_component;
- WaveletBuf3D **waveletbuf [2];
- uint32 *frames_in_readbuf;
- uint32 bitrate;
-} TarkinVideoChannel;
+ uint32_t width;
+ uint32_t height;
+ uint32_t frames_per_buf;
+ uint32_t bitrate;
+ TarkinColorFormat format;
+} TarkinVideoLayerDesc;
typedef struct {
+ TarkinVideoLayerDesc desc;
+ Wavelet3DBuf *waveletbuf;
+ uint32_t frames_in_readbuf;
+} TarkinVideoLayer;
+
+
+typedef struct {
int fd;
- ogg_stream_state os;
- uint32 n_videochannels;
- TarkinVideoChannel *channel;
+ uint32_t n_layers;
+ TarkinVideoLayer *layer;
} TarkinStream;
TarkinStream* tarkin_stream_new (int fd);
void tarkin_stream_destroy (TarkinStream *s);
-int tarkin_read_frame (TarkinStream *s, uint8 *buf);
+uint32_t tarkin_read_frame (TarkinStream *s, uint8_t *buf);
-int tarkin_write_set_bitrate (TarkinStream *s, uint32 bitrate);
-int tarkin_write_frame (TarkinStream *s, uint8 *buf);
+uint32_t tarkin_write_set_bitrate (TarkinStream *s, uint32_t bitrate);
+uint32_t tarkin_write_frame (TarkinStream *s, uint8_t *buf);
+uint32_t tarkin_write_frame (TarkinStream *s, uint8_t *buf);
#endif
+
1.3 +379 -104 w3d/wavelet.c
Index: wavelet.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- wavelet.c 2001/03/28 13:46:58 1.2
+++ wavelet.c 2001/06/25 07:56:07 1.3
@@ -1,11 +1,20 @@
#include <stdlib.h>
#include "wavelet.h"
+#include "rle.h"
+
+/**
+ * (The transform code is in wavelet_xform.c)
+ */
+
+
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MAX3(a,b,c) (MAX(a,MAX(b,c)))
+
-Wavelet3DBuf* wavelet_3d_buf_new (uint32_t width, uint32_t height, uint32_t frames)
+Wavelet3DBuf* wavelet_3d_buf_new (uint32_t width, uint32_t height,
+ uint32_t frames)
{
Wavelet3DBuf* buf = (Wavelet3DBuf*) malloc (sizeof (Wavelet3DBuf));
uint32_t _w = width;
@@ -69,8 +78,6 @@
}
-
-
void wavelet_3d_buf_destroy (Wavelet3DBuf* buf)
{
if (buf) {
@@ -92,150 +99,418 @@
+#define SIGN_SHIFT 15
+
static inline
-void __fwd_xform__ (Wavelet3DBuf *buf, TYPE *data, int stride, int n)
+void encode_coeff (ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [],
+ TYPE coeff)
{
- TYPE *d = buf->scratchbuf;
- TYPE *x = data;
- TYPE *s = data;
- int i, k=n/2;
+ int sign = (coeff >> SIGN_SHIFT) & 1;
+ int i = 8;
+
+ do {
+ int this_bit = (coeff >> i) & 1;
+ int bit_is_significand = sign ^ this_bit;
+
+ if (bit_is_significand) {
+ OUTPUT_BIT(&significand_bitstream[i], 1);
+ OUTPUT_BIT(&significand_bitstream[i], sign);
+ break;
+ } else {
+ OUTPUT_BIT(&significand_bitstream[i], 0);
+ if (i == 0)
+ OUTPUT_BIT(&significand_bitstream[i], sign);
+ }
+ } while (--i >= 0);
+
+ while (--i >= 0)
+ OUTPUT_BIT(&insignificand_bitstream[i], ((coeff >> i) ^ sign) & 1);
+}
+
+static TYPE coefficient_table [][2] = {
+ { 1, ~1 }, // 000000001
+ { 2, ~2 }, // 000000010
+ { 4, ~4 }, // 000000100
+ { 8, ~8 }, // 000001000
+ { 16, ~16 }, // 000010000
+ { 32, ~32 }, // 000100000
+ { 64, ~64 }, // 001000000
+ { 128, ~128 }, // 010000000
+ { 256, ~256 } // 100000000
+};
+
- for (i=0; i<((n&1) ? k : (k-1)); i++) /* highpass coefficients */
- d [i] = x [(2*i+1)*stride] - ((x [2*i*stride] + x[(2*i+2)*stride]) >> 1);
- if (!(n & 1)) /* n is even */
- d [k-1] = x[(n-1)*stride] - x[(n-2)*stride];
+static inline
+TYPE decode_coeff (ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [])
+{
+ int i = 8;
+ TYPE coeff = 0;
- s [0] = x[0] + (d[0] >> 1); /* lowpass coefficients */
+ do {
+ if (ENTROPY_CODER_IS_EMPTY(&significand_bitstream[i]))
+ continue;
+
+ if (INPUT_BIT(&significand_bitstream[i])) {
+ int sign;
+
+ if (ENTROPY_CODER_IS_EMPTY(&significand_bitstream[i]))
+ continue;
+
+ sign = INPUT_BIT(&significand_bitstream[i]);
+ coeff = coefficient_table [i][sign];
+ break;
+ } else if (i == 0) {
+ if (ENTROPY_CODER_IS_EMPTY(&significand_bitstream[i]))
+ continue;
- for (i=1; i<k; i++)
- s [i*stride] = x [2*i*stride] + ((d [i-1] + d[i]) >> 2);
+ if (INPUT_BIT(&significand_bitstream[i]))
+ coeff = ~0;
+ }
+ } while (--i >= 0);
- if (n & 1 || n <=2) /* n is odd */
- s [k*stride] = x[(n-1)*stride] + (d[k-1] >> 1);
+ while (--i >= 0) {
+ if (ENTROPY_CODER_IS_EMPTY(&insignificand_bitstream[i]))
+ continue;
- for (i=0; i<n/2; i++)
- x [(n-k+i)*stride] = d [i];
+ coeff ^= INPUT_BIT(&insignificand_bitstream[i]) << i;
+ }
+
+ return coeff;
}
+
+#if 1
+
static inline
-void __inv_xform__ (Wavelet3DBuf *buf, TYPE *data, int stride, int n)
+void encode_quadrant (const Wavelet3DBuf* buf,
+ int level, int quadrant, uint32_t w, uint32_t h, uint32_t f,
+ ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [])
{
- int i, k=n/2;
- TYPE *s = buf->scratchbuf;
- TYPE *d = buf->scratchbuf + n - k;
- TYPE *x = data;
+ uint32_t x, y, z;
- for (i=0; i<k+1; i++)
- s [i] = x [i*stride];
+ for (z=0; z<f; z++) {
+ for (y=0; y<h; y++) {
+ for (x=0; x<w; x++) {
+ unsigned int index = buf->offset [level] [quadrant]
+ + z * buf->width * buf->height
+ + y * buf->width + x;
- for (i=0; i<n/2; i++)
- d [i] = x [(n-k+i)*stride];
+ encode_coeff (significand_bitstream, insignificand_bitstream,
+ buf->data [index]);
+ }
+ }
+ }
+}
- x [0] = s[0] - (d[0] >> 1);
- for (i=1; i<k; i++)
- x [2*i*stride] = s [i] - ((d [i-1] + d[i]) >> 2);
+static
+void encode_coefficients (const Wavelet3DBuf* buf,
+ ENTROPY_CODER s_stream [],
+ ENTROPY_CODER i_stream [])
+{
+ int level;
- if (n & 1 || n <= 2) /* n is odd */
- x [(n-1)*stride] = s[k] - (d[k-1] >> 1);
+ encode_coeff (s_stream, i_stream, buf->data[0]);
- for (i=0; i<((n&1) ? k : (k-1)); i++)
- x [(2*i+1)*stride] = d [i] + ((x [2*i*stride] + x[(2*i+2)*stride]) >> 1);
+ for (level=0; level<buf->scales-1; level++) {
+ uint32_t w, h, f, w1, h1, f1;
- if (!(n & 1)) /* n is even */
- x [(n-1)*stride] = d[k-1] + x[(n-2)*stride];
+ w = buf->w [level];
+ h = buf->h [level];
+ f = buf->f [level];
+ w1 = buf->w [level+1] - w;
+ h1 = buf->h [level+1] - h;
+ f1 = buf->f [level+1] - f;
+
+ if (w1 > 0) encode_quadrant(buf,level,1,w1,h,f,s_stream,i_stream);
+ if (h1 > 0) encode_quadrant(buf,level,2,w,h1,f,s_stream,i_stream);
+ if (f1 > 0) encode_quadrant(buf,level,3,w,h,f1,s_stream,i_stream);
+ if (w1 > 0 && h1 > 0) encode_quadrant(buf,level,4,w1,h1,f,s_stream,i_stream);
+ if (w1 > 0 && f1 > 0) encode_quadrant(buf,level,5,w1,h,f1,s_stream,i_stream);
+ if (h1 > 0 && f1 > 0) encode_quadrant(buf,level,6,w,h1,f1,s_stream,i_stream);
+ if (h1 > 0 && f1 > 0 && f1 > 0)
+ encode_quadrant (buf,level,7,w1,h1,f1,s_stream,i_stream);
+ }
}
+static inline
+void decode_quadrant (Wavelet3DBuf* buf,
+ int level, int quadrant, uint32_t w, uint32_t h, uint32_t f,
+ ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [])
+{
+ uint32_t x, y, z;
+ for (z=0; z<f; z++) {
+ for (y=0; y<h; y++) {
+ for (x=0; x<w; x++) {
+ unsigned int index = buf->offset [level] [quadrant]
+ + z * buf->width * buf->height
+ + y * buf->width + x;
+ buf->data [index] = decode_coeff (significand_bitstream,
+ insignificand_bitstream);
+ }
+ }
+ }
+}
-void wavelet_3d_buf_fwd_xform (Wavelet3DBuf* buf)
+
+static
+void decode_coefficients (Wavelet3DBuf* buf,
+ ENTROPY_CODER s_stream [],
+ ENTROPY_CODER i_stream [])
{
int level;
- for (level=buf->scales-1; level>0; level--) {
- uint32_t w = buf->w[level];
- uint32_t h = buf->h[level];
- uint32_t f = buf->f[level];
-
- if (w > 1) {
- int row, frame;
- for (frame=0; frame<f; frame++) {
- for (row=0; row<h; row++) {
- TYPE *data = buf->data + (frame * buf->height + row) * buf->width;
- __fwd_xform__ (buf, data, 1, w);
- }
- }
- }
+ buf->data[0] = decode_coeff (s_stream, i_stream);
- if (h > 1) {
- int col, frame;
- for (frame=0; frame<f; frame++) {
- for (col=0; col<w; col++) {
- TYPE *data = buf->data + frame * buf->width * buf->height + col;
- __fwd_xform__ (buf, data, buf->width, h);
- }
- }
- }
+ for (level=0; level<buf->scales-1; level++) {
+ uint32_t w, h, f, w1, h1, f1;
- if (f > 1) {
- int i, j;
- for (j=0; j<h; j++) {
- for (i=0; i<w; i++) {
- TYPE *data = buf->data + j*buf->width + i;
- __fwd_xform__ (buf, data, buf->width * buf->height, f);
- }
- }
- }
+ w = buf->w [level];
+ h = buf->h [level];
+ f = buf->f [level];
+ w1 = buf->w [level+1] - w;
+ h1 = buf->h [level+1] - h;
+ f1 = buf->f [level+1] - f;
+
+ if (w1 > 0) decode_quadrant(buf,level,1,w1,h,f,s_stream,i_stream);
+ if (h1 > 0) decode_quadrant(buf,level,2,w,h1,f,s_stream,i_stream);
+ if (f1 > 0) decode_quadrant(buf,level,3,w,h,f1,s_stream,i_stream);
+ if (w1 > 0 && h1 > 0) decode_quadrant(buf,level,4,w1,h1,f,s_stream,i_stream);
+ if (w1 > 0 && f1 > 0) decode_quadrant(buf,level,5,w1,h,f1,s_stream,i_stream);
+ if (h1 > 0 && f1 > 0) decode_quadrant(buf,level,6,w,h1,f1,s_stream,i_stream);
+ if (h1 > 0 && f1 > 0 && f1 > 0)
+ decode_quadrant (buf,level,7,w1,h1,f1,s_stream,i_stream);
}
}
+#else
+static inline
+void encode_coefficients (const Wavelet3DBuf* buf,
+ ENTROPY_CODER s_stream [],
+ ENTROPY_CODER i_stream [])
+{
+ uint32_t i;
+ for (i=0; i<buf->width*buf->height*buf->frames; i++)
+ encode_coeff(s_stream, i_stream, buf->data[i]);
+}
+static inline
+void decode_coefficients (Wavelet3DBuf* buf,
+ ENTROPY_CODER s_stream [],
+ ENTROPY_CODER i_stream [])
+{
+ uint32_t i;
-void wavelet_3d_buf_inv_xform (Wavelet3DBuf* buf)
+ for (i=0; i<buf->width*buf->height*buf->frames; i++)
+ buf->data[i] = decode_coeff(s_stream, i_stream);
+}
+#endif
+
+
+static
+uint32_t setup_limittabs (ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [],
+ uint32_t significand_limittab [],
+ uint32_t insignificand_limittab [])
{
- int level;
+ uint32_t byte_count = 0;
+ int i;
- for (level=1; level<buf->scales; level++) {
- uint32_t w = buf->w[level];
- uint32_t h = buf->h[level];
- uint32_t f = buf->f[level];
-
- if (f > 1) {
- int i, j;
- for (j=0; j<h; j++) {
- for (i=0; i<w; i++) {
- TYPE *data = buf->data + j*buf->width + i;
- __inv_xform__ (buf, data, buf->width * buf->height, f);
- }
- }
- }
+ for (i=0; i<9; i++) {
+ uint32_t bytes = ENTROPY_ENCODER_FLUSH(&significand_bitstream[i]);
+bytes=i > 3 ? 200 : 20*i;
+ significand_limittab[i] = bytes;
+ byte_count += bytes;
+ }
+
+ for (i=0; i<9; i++) {
+ uint32_t bytes = ENTROPY_ENCODER_FLUSH(&insignificand_bitstream[i]);
+bytes=i > 5 ? 100 : 10*i;
- if (h > 1) {
- int col, frame;
- for (frame=0; frame<f; frame++) {
- for (col=0; col<w; col++) {
- TYPE *data = buf->data + frame * buf->width * buf->height + col;
- __inv_xform__ (buf, data, buf->width, h);
- }
- }
- }
+ insignificand_limittab[i] = bytes;
+ byte_count += bytes;
+ }
- if (w > 1) {
- int row, frame;
- for (frame=0; frame<f; frame++) {
- for (row=0; row<h; row++) {
- TYPE *data = buf->data + (frame * buf->height + row) * buf->width;
- __inv_xform__ (buf, data, 1, w);
- }
- }
- }
+ return byte_count;
+}
+
+
+/**
+ * write 'em binary for now, should be easy to compress ...
+ */
+static
+uint8_t* write_limittabs (uint8_t *bitstream,
+ uint32_t significand_limittab [],
+ uint32_t insignificand_limittab [])
+{
+ int i;
+
+ for (i=0; i<9; i++) {
+ *(uint32_t*) bitstream = significand_limittab[i];
+printf("significand_limittab[%i] == %u\n", i, significand_limittab[i]);
+ bitstream += 4;
+ }
+
+ for (i=0; i<9; i++) {
+ *(uint32_t*) bitstream = insignificand_limittab[i];
+printf("insignificand_limittab[%i] == %u\n", i, insignificand_limittab[i]);
+ bitstream += 4;
+ }
+
+ return bitstream;
+}
+
+
+static
+uint8_t* read_limittabs (uint8_t *bitstream,
+ uint32_t significand_limittab [],
+ uint32_t insignificand_limittab [])
+{
+ int i;
+
+ for (i=0; i<9; i++) {
+ significand_limittab[i] = *(uint32_t*) bitstream;
+//printf("> significand_limittab[%i] == %u\n", i, significand_limittab[i]);
+ bitstream += 4;
+ }
+
+ for (i=0; i<9; i++) {
+ insignificand_limittab[i] = *(uint32_t*) bitstream;
+//printf("> insignificand_limittab[%i] == %u\n", i, insignificand_limittab[i]);
+ bitstream += 4;
+ }
+
+ return bitstream;
+}
+
+
+/**
+ * for now we simply concatenate the entropy coder bitstreams
+ */
+static
+void merge_bitstreams (uint8_t *bitstream,
+ ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [],
+ uint32_t significand_limittab [],
+ uint32_t insignificand_limittab [])
+{
+ int i;
+
+ for (i=0; i<9; i++) {
+ memcpy (bitstream,
+ ENTROPY_CODER_BITSTREAM(&significand_bitstream[i]),
+ significand_limittab[i]);
+
+ bitstream += significand_limittab[i];
+ }
+
+ for (i=0; i<9; i++) {
+ memcpy (bitstream,
+ ENTROPY_CODER_BITSTREAM(&insignificand_bitstream[i]),
+ insignificand_limittab[i]);
+
+ bitstream += significand_limittab[i];
+ }
+}
+
+
+static
+void split_bitstreams (uint8_t *bitstream,
+ ENTROPY_CODER significand_bitstream [],
+ ENTROPY_CODER insignificand_bitstream [],
+ uint32_t significand_limittab [],
+ uint32_t insignificand_limittab [])
+{
+ uint32_t byte_count;
+ int i;
+
+ for (i=0; i<9; i++) {
+ byte_count = significand_limittab[i];
+ ENTROPY_DECODER_INIT(&significand_bitstream[i], bitstream, byte_count);
+ bitstream += byte_count;
+ }
+
+ for (i=0; i<9; i++) {
+ byte_count = significand_limittab[i];
+ ENTROPY_DECODER_INIT(&insignificand_bitstream[i], bitstream, byte_count);
+ bitstream += byte_count;
}
}
+
+int wavelet_3d_buf_encode_coeff (const Wavelet3DBuf* buf,
+ uint8_t *bitstream,
+ uint32_t limit)
+{
+ ENTROPY_CODER significand_bitstream [9];
+ ENTROPY_CODER insignificand_bitstream [9];
+ uint32_t significand_limittab [9];
+ uint32_t insignificand_limittab [9];
+ uint32_t byte_count;
+ int i;
+
+ for (i=0; i<9; i++) {
+ ENTROPY_ENCODER_INIT(&significand_bitstream[i], limit);
+ ENTROPY_ENCODER_INIT(&insignificand_bitstream[i], limit);
+ }
+
+ encode_coefficients (buf, significand_bitstream, insignificand_bitstream);
+
+ byte_count = setup_limittabs (significand_bitstream,
+ insignificand_bitstream,
+ significand_limittab,
+ insignificand_limittab);
+
+ bitstream = write_limittabs (bitstream,
+ significand_limittab, insignificand_limittab);
+
+ merge_bitstreams (bitstream, significand_bitstream, insignificand_bitstream,
+ significand_limittab, insignificand_limittab);
+
+ for (i=0; i<9; i++) {
+ ENTROPY_ENCODER_DONE(&significand_bitstream[i]);
+ ENTROPY_ENCODER_DONE(&insignificand_bitstream[i]);
+ }
+
+ return byte_count;
+}
+
+
+void wavelet_3d_buf_decode_coeff (Wavelet3DBuf* buf,
+ uint8_t *bitstream,
+ uint32_t byte_count)
+{
+ ENTROPY_CODER significand_bitstream [9];
+ ENTROPY_CODER insignificand_bitstream [9];
+ uint32_t significand_limittab [9];
+ uint32_t insignificand_limittab [9];
+ int i;
+
+ for (i=0; i<buf->width*buf->height*buf->frames; i++)
+ buf->data[i] = 0xff;
+
+ bitstream = read_limittabs (bitstream,
+ significand_limittab, insignificand_limittab);
+
+ split_bitstreams (bitstream, significand_bitstream, insignificand_bitstream,
+ significand_limittab, insignificand_limittab);
+
+ decode_coefficients (buf, significand_bitstream, insignificand_bitstream);
+
+ for (i=0; i<9; i++) {
+ ENTROPY_DECODER_DONE(&significand_bitstream[i]);
+ ENTROPY_DECODER_DONE(&insignificand_bitstream[i]);
+ }
+}
1.3 +18 -2 w3d/wavelet.h
Index: wavelet.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- wavelet.h 2001/03/28 13:46:58 1.2
+++ wavelet.h 2001/06/25 07:56:07 1.3
@@ -23,7 +23,23 @@
extern void wavelet_3d_buf_destroy (Wavelet3DBuf* buf);
-extern void wavelet_3d_buf_fwd_xform (Wavelet3DBuf* buf);
-extern void wavelet_3d_buf_inv_xform (Wavelet3DBuf* buf);
+/**
+ * transform buf->data
+ * a_moments is the number of vanishing moments of the analyzing
+ * highpass filter,
+ * s_moments the one of the synthesizing lowpass filter.
+ */
+extern void wavelet_3d_buf_fwd_xform (Wavelet3DBuf* buf,
+ int a_moments, int s_moments);
+extern void wavelet_3d_buf_inv_xform (Wavelet3DBuf* buf,
+ int a_moments, int s_moments);
+
+extern int wavelet_3d_buf_encode_coeff (const Wavelet3DBuf* buf,
+ uint8_t *bitstream,
+ uint32_t limit);
+
+extern void wavelet_3d_buf_decode_coeff (Wavelet3DBuf* buf,
+ uint8_t *bitstream,
+ uint32_t limit);
#endif
1.5 +11 -11 w3d/yuv.c
Index: yuv.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/yuv.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- yuv.c 2001/03/28 12:55:42 1.4
+++ yuv.c 2001/06/25 07:56:07 1.5
@@ -1,21 +1,21 @@
#include "yuv.h"
-void rgb2yuv (uint8_t *rgb, int16_t *y, int16_t *u, int16_t *v, uint32_t count, uint32_t rgbstride)
+void rgb24_to_yuv (uint8_t *rgb, int16_t *y, int16_t *u, int16_t *v, uint32_t count, uint32_t rgbstride)
{
int i;
#if defined(TARKIN_YUV_EXACT)
for (i=0; i<count; i++, rgb+=rgbstride) {
- y [i] = ((int16) 77 * rgb [0] + 150 * rgb [1] + 29 * rgb [2]) / 256;
- u [i] = ((int16) -44 * rgb [0] - 87 * rgb [1] + 131 * rgb [2]) / 256;
- v [i] = ((int16) 131 * rgb [0] - 110 * rgb [1] - 21 * rgb [2]) / 256;
+ y [i] = ((int16_t) 77 * rgb [0] + 150 * rgb [1] + 29 * rgb [2]) / 256;
+ 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;
}
#else
for (i=0; i<count; i++, rgb+=rgbstride) {
- u [i] = rgb [0] - rgb [1];
- v [i] = rgb [2] - rgb [1];
- y [i] = rgb [1] + ((u [i] + v [i]) >> 2);
+ v [i] = rgb [0] - rgb [1];
+ u [i] = rgb [2] - rgb [1];
+ y [i] = rgb [1] + (u [i] + v [i]) / 4;
}
#endif
}
@@ -28,7 +28,7 @@
}
-void yuv2rgb (int16_t *y, int16_t *u, int16_t *v, uint8_t *rgb, uint32_t count, uint32_t rgbstride)
+void yuv_to_rgb24 (int16_t *y, int16_t *u, int16_t *v, uint8_t *rgb, uint32_t count, uint32_t rgbstride)
{
int i;
@@ -40,9 +40,9 @@
}
#else
for (i=0; i<count; i++, rgb+=rgbstride) {
- rgb [1] = CLAMP(y [i] - ((u [i] + v [i]) >> 2));
- rgb [2] = CLAMP(v [i] + rgb [1]);
- rgb [0] = CLAMP(u [i] + rgb [1]);
+ rgb [1] = CLAMP(y [i] - (u [i] + v [i]) / 4);
+ rgb [2] = CLAMP(u [i] + rgb [1]);
+ rgb [0] = CLAMP(v [i] + rgb [1]);
}
#endif
}
1.3 +3 -3 w3d/yuv.h
Index: yuv.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/yuv.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- yuv.h 2001/03/28 12:55:54 1.2
+++ yuv.h 2001/06/25 07:56:07 1.3
@@ -1,11 +1,11 @@
#ifndef __YUV_H
-#define __YUF_H
+#define __YUV_H
#include <stdint.h>
-extern void rgb2yuv (uint8_t *rgb, int16_t *y, int16_t *u, int16_t *v, uint32_t count, uint32_t rgbstride);
-extern void yuv2rgb (int16_t *y, int16_t *u, int16_t *v, uint8_t *rgb, uint32_t count, uint32_t rgbstride);
+extern void rgb24_to_yuv (uint8_t *rgb, int16_t *y, int16_t *u, int16_t *v, uint32_t count, uint32_t rgbstride);
+extern void yuv_to_rgb24 (int16_t *y, int16_t *u, int16_t *v, uint8_t *rgb, uint32_t count, uint32_t rgbstride);
#endif
1.1 w3d/_test_bitcoder.c
Index: _test_bitcoder.c
===================================================================
/**
* Bitcoder regression test
*/
#define TEST(x) \
if(!(x)) { \
fprintf(stderr, "Test ("#x") FAILED !!!\n"); \
exit (-1); \
}
#undef BITCODER
#undef RLECODER
#define BITCODER
#include <time.h>
#include "bitcoder.h"
#define MAX_COUNT 650000 /* write/read up to 650000 bits */
#define N_TESTS 100 /* test 100 times */
int main ()
{
uint32_t j;
fprintf(stdout, "\nBitCoder Test (N_TESTS == %u, bitstreams up to %u bits)\n",
N_TESTS, MAX_COUNT);
for (j=1; j<=N_TESTS; j++) {
uint8_t *bitstream;
uint8_t *bit;
uint32_t limit = 0;
uint32_t count;
fprintf (stdout, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b%u/%u", j, N_TESTS);
fflush (stdout);
srand (time(NULL));
while (limit == 0)
limit = rand() * 1.0 * MAX_COUNT / RAND_MAX;
bit = (uint8_t*) malloc (limit);
/**
* check encoding ...
*/
{
BitCoderState encoder;
uint32_t i;
bitcoder_encoder_init (&encoder, limit);
for (i=0; i<limit; i++) {
bit[i] = (rand() > RAND_MAX/2) ? 0 : 1;
bitcoder_write_bit (&encoder, bit[i]);
}
count = bitcoder_flush (&encoder);
TEST(count == limit/8 || count == limit/8 + 1);
bitstream = (uint8_t*) malloc (count);
memcpy (bitstream, encoder.bitstream, count);
bitcoder_encoder_done (&encoder);
}
/**
* decoding ...
*/
{
BitCoderState decoder;
uint32_t i;
bitcoder_decoder_init (&decoder, bitstream, limit);
for (i=0; i<limit; i++) {
TEST(bit[i] == bitcoder_read_bit (&decoder));
}
}
free (bit);
}
fprintf (stdout, "\ndone.\n\n");
return 0;
}
1.1 w3d/_test_huffman.c
Index: _test_huffman.c
===================================================================
/**
* RLEcoder regression test, Huffman encoder
*/
#define TEST_EQUAL(x,y) \
if(!(x) == (y)) { \
fprintf(stderr, "Test ("#x" == "#y") FAILED !!!\n"); \
fprintf(stderr, "%u: (%u <-> %u)\n", i, x, y); \
exit (-1); \
}
#undef RLECODER
#undef BITCODER
#define BITCODER
#include <time.h>
#include "rle.h"
#define MAX_COUNT 10000 /* write/read up to 65000 values */
#define N_TESTS 100 /* test 100 times */
int main ()
{
uint32_t j;
fprintf(stdout, "\nBitCoder/Huffman Test "
"(N_TESTS == %u, bitstreams up to %u values)\n",
N_TESTS, MAX_COUNT);
for (j=1; j<=N_TESTS; j++) {
uint8_t *bitstream;
uint32_t *val;
uint32_t limit = 0;
uint32_t count;
fprintf (stdout, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b%u/%u", j, N_TESTS);
fflush (stdout);
srand (time(NULL));
while (limit == 0)
limit = rand() * 1.0 * MAX_COUNT / RAND_MAX;
val = (uint32_t*) malloc (limit * sizeof(uint32_t));
/**
* check encoding ...
*/
{
ENTROPY_CODER encoder;
uint32_t i;
ENTROPY_ENCODER_INIT(&encoder, 20*limit);
for (i=0; i<limit; i++) {
val[i] = rand() * 1000.0 / RAND_MAX - 128;
huffmancoder_write(&encoder, val[i]);
}
count = ENTROPY_ENCODER_FLUSH(&encoder);
bitstream = (uint8_t*) malloc (count * sizeof(uint32_t));
memcpy (bitstream, ENTROPY_CODER_BITSTREAM(&encoder), count);
ENTROPY_ENCODER_DONE(&encoder);
}
/**
* decoding ...
*/
{
ENTROPY_CODER decoder;
uint32_t i;
ENTROPY_DECODER_INIT(&decoder, bitstream, count);
for (i=0; i<limit; i++) {
uint32_t b = huffmancoder_read(&decoder);
TEST_EQUAL(val[i], b);
}
}
free (val);
}
fprintf (stdout, "\ndone.\n\n");
return 0;
}
1.1 w3d/_test_rle.c
Index: _test_rle.c
===================================================================
/**
* RLEcoder regression test
*/
#define TEST(x) \
if(!(x)) { \
fprintf(stderr, "Test ("#x") FAILED !!!\n"); \
exit (-1); \
}
#undef BITCODER
#undef RLECODER
#define RLECODER
#include <time.h>
#include "rle.h"
#define MAX_COUNT 650000 /* write/read up to 650000 bits */
#define N_TESTS 100 /* test 100 times */
int main ()
{
uint32_t j;
fprintf(stdout, "\nRLECoder Test (N_TESTS == %u, bitstreams up to %u bits)\n",
N_TESTS, MAX_COUNT);
for (j=1; j<=N_TESTS; j++) {
uint8_t *bitstream;
uint8_t *bit;
uint32_t limit = 0;
uint32_t count;
fprintf (stdout, "\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b%u/%u", j, N_TESTS);
fflush (stdout);
srand (time(NULL));
while (limit == 0)
limit = rand() * 1.0 * MAX_COUNT / RAND_MAX;
bit = (uint8_t*) malloc (limit);
/**
* check encoding ...
*/
{
ENTROPY_CODER encoder;
uint32_t i;
ENTROPY_ENCODER_INIT(&encoder, limit);
for (i=0; i<limit; i++) {
bit[i] = (rand() > RAND_MAX/2) ? 0 : 1;
OUTPUT_BIT(&encoder, bit[i]);
}
count = ENTROPY_ENCODER_FLUSH(&encoder);
bitstream = (uint8_t*) malloc (count);
memcpy (bitstream, ENTROPY_CODER_BITSTREAM(&encoder), count);
ENTROPY_ENCODER_DONE(&encoder);
}
/**
* decoding ...
*/
{
ENTROPY_CODER decoder;
uint32_t i;
ENTROPY_DECODER_INIT(&decoder, bitstream, limit);
for (i=0; i<limit; i++) {
int b = INPUT_BIT(&decoder);
TEST(bit[i] == b);
}
}
free (bit);
}
fprintf (stdout, "\ndone.\n\n");
return 0;
}
1.1 w3d/tarkin.c
Index: tarkin.c
===================================================================
/**
* Not yet working.
*
* Everything here should get oggetized. But for now I don't
* want to struggle with packets, so I simply write everything
* binary.
*/
#include <stdlib.h>
#include <unistd.h>
#include <ctype.h>
#include <string.h>
#include "tarkin.h"
#if __BYTE_ORDER == __LITTLE_ENDIAN
#define LE32_TO_CPU(x)
#define CPU_TO_LE32(x)
#elif __BYTE_ORDER == __BIG_ENDIAN
#define LE32_TO_CPU(x) x = (((x & 0x000000ff) << 24) | ((x & 0x0000ff00) << 8) \
| ((x & 0x00ff0000) >> 8) | ((x & 0xff000000) << 24))
#define CPU_TO_LE32(x) x = (((x & 0x000000ff) << 24) | ((x & 0x0000ff00) << 8) \
| ((x & 0x00ff0000) >> 8) | ((x & 0xff000000) << 24))
#else
#error unknown endianess !!
#endif
static
int read_tarkin_header (int fd, TarkinStream *s)
{
char signature [6];
if (read (fd, signature, 6) < 6)
return TARKIN_IO_ERROR;
if (!strncmp(signature, "tarkin", 6) == 0)
return TARKIN_SIGNATURE_NOT_FOUND;
if (read (fd, &s->n_layers, 4) < 4)
return TARKIN_IO_ERROR;
LE32_TO_CPU(s->n_layers);
return 0;
}
static
int read_layer_descs (int fd, TarkinStream *s)
{
int i;
s->layer = (TarkinVideoLayer*) calloc (1, s->n_layers * sizeof(TarkinVideoLayer));
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;
}
LE32_TO_CPU(s->layer[i].width);
LE32_TO_CPU(s->layer[i].height);
LE32_TO_CPU(s->layer[i].frames_per_buf);
LE32_TO_CPU(s->layer[i].bitrate);
LE32_TO_CPU(s->layer[i].format);
}
return 0;
}
TarkinStream* tarkin_stream_new (int fd)
{
TarkinStream *s = (TarkinStream*) calloc (1, sizeof(TarkinStream));
if (!s)
return NULL;
s->fd = fd;
return s;
}
void tarkin_stream_destroy (TarkinStream *s)
{
int i;
if (!s)
return;
for (i=0; i<s->n_layers; i++)
if (s->layer[i].waveletbuf)
wavelet_3d_buf_destroy (s->layer[i].waveletbuf);
free(s->layer);
free(s);
}
uint32_t tarkin_read_frame (TarkinStream *s, uint8_t *buf)
{
if (s->n_layers == 0) {
if (read_tarkin_header(s->fd, s) != 0) {
tarkin_stream_destroy (s);
return 0;
}
if (read_layer_descs(s->fd, s) != 0) {
tarkin_stream_destroy (s);
return 0;
}
}
return 0;
}
uint32_t tarkin_write_set_bitrate (TarkinStream *s, uint32_t bitrate);
uint32_t tarkin_write_frame (TarkinStream *s, uint8_t *buf);
1.1 w3d/wavelet_xform.c
Index: wavelet_xform.c
===================================================================
#include <stdlib.h>
#include <assert.h>
#include "wavelet.h"
static
void fwd_analyze_1 (const TYPE *x, TYPE *d, int stride, int n)
{
int i, k=n/2;
for (i=0; i<k; i++)
d[i] = x[(2*i+1)*stride] - x[2*i*stride];
}
static
void fwd_synthesize_1 (const TYPE *x, TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
for (i=0; i<k; i++)
s[i*stride] = x[2*i*stride] + d[i] / 2;
if (n & 1)
s[k*stride] = x[2*k*stride] + d[k-1] / 2;
}
static
void inv_analyze_1 (TYPE *x, const TYPE *d, int stride, int n)
{
int i, k=n/2;
for (i=0; i<k; i++)
x[(2*i+1)*stride] = d[i] + x[2*i*stride];
}
static
void inv_synthesize_1 (TYPE *x, const TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
for (i=0; i<k; i++)
x[2*i*stride] = s[i] - d[i] / 2;
if (n & 1)
x[2*k*stride] = s[k] - d[k-1] / 2;
}
static
void fwd_analyze_2 (const TYPE *x, TYPE *d, int stride, int n)
{
int i, k=n/2;
if (n & 1) {
for (i=0; i<k; i++)
d[i] = x[(2*i+1)*stride] - (x[2*i*stride] + x[(2*i+2)*stride]) / 2;
} else {
for (i=0; i<k-1; i++)
d[i] = x[(2*i+1)*stride] - (x[2*i*stride] + x[(2*i+2)*stride]) / 2;
d[k-1] = x[(n-1)*stride] - x[(n-2)*stride];
}
}
static
void fwd_synthesize_2 (const TYPE *x, TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
s[0] = x[0] + d[1] / 2;
for (i=1; i<k; i++)
s[i*stride] = x[2*i*stride] + (d[i-1] + d[i]) / 4;
if (n & 1)
s[k*stride] = x[2*k*stride] + d[k-1] / 2;
}
static inline
void inv_analyze_2 (TYPE *x, const TYPE *d, int stride, int n)
{
int i, k=n/2;
if (n & 1) {
for (i=0; i<k; i++)
x[(2*i+1)*stride] = d[i] + (x[2*i*stride] + x[(2*i+2)*stride]) / 2;
} else {
for (i=0; i<k-1; i++)
x[(2*i+1)*stride] = d[i] + (x[2*i*stride] + x[(2*i+2)*stride]) / 2;
x[(n-1)*stride] = d[k-1] + x[(n-2)*stride];
}
}
static inline
void inv_synthesize_2 (TYPE *x, const TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
x[0] = s[0] - d[1] / 2;
for (i=1; i<k; i++)
x[2*i*stride] = s[i] - (d[i-1] + d[i]) / 4;
if (n & 1)
x[2*k*stride] = s[k] - d[k-1] / 2;
}
static
void fwd_analyze_4 (const TYPE *x, TYPE *d, int stride, int n)
{
int i, k=n/2;
d[0] = x[stride] - (x[0] + x[2*stride]) / 2;
if (n & 1) {
for (i=1; i<k-1; i++)
d[i] = x[(2*i+1)*stride]
- ((uint32_t) 9 * (x[2*i*stride] + x[(2*i+2)*stride])
- (x[(2*i-2)*stride] + x[(2*i+4)*stride])) / 16;
if (k > 1)
d[k-1] = x[(2*k-1)*stride] - (x[(2*k-2)*stride] + x[2*k*stride]) / 2;
} else {
for (i=1; i<k-2; i++)
d[i] = x[(2*i+1)*stride]
- ((uint32_t) 9 * (x[2*i*stride] + x[(2*i+2)*stride])
- (x[(2*i-2)*stride] + x[(2*i+4)*stride])) / 16;
if (k > 2)
d[k-2] = x[(2*k-3)*stride] - (x[(2*k-4)*stride]
+ x[(2*k-2)*stride]) / 2;
if (k > 1)
d[k-1] = x[(n-1)*stride] - x[(n-2)*stride];
}
}
static
void fwd_synthesize_4 (const TYPE *x, TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
s[0] = x[0] + d[1] / 2;
if (k > 1)
s[stride] = x[2*stride] + (d[0] + d[1]) / 4;
for (i=2; i<k-1; i++)
s[i*stride] = x[2*i*stride]
+ ((uint32_t) 9 * (d[i-1] + d[i]) - (d[i-2] + d[i+1])) / 32;
if (k > 2)
s[(k-1)*stride] = x[(2*k-2)*stride] + (d[k-2] + d[k-1]) / 4;
if (n & 1)
s[k*stride] = x[2*k*stride] + d[k-1] / 2;
}
static
void inv_analyze_4 (TYPE *x, const TYPE *d, int stride, int n)
{
int i, k=n/2;
x[stride] = d[0] + (x[0] + x[2*stride]) / 2;
if (n & 1) {
for (i=1; i<k-1; i++)
x[(2*i+1)*stride] = d[i]
+ ((uint32_t) 9 * (x[2*i*stride] + x[(2*i+2)*stride])
- (x[(2*i-2)*stride] + x[(2*i+4)*stride])) / 16;
if (k > 1)
x[(2*k-1)*stride] = d[k-1] + (x[(2*k-2)*stride] + x[2*k*stride]) / 2;
} else {
for (i=1; i<k-2; i++)
x[(2*i+1)*stride] = d[i]
+ (9 * (x[2*i*stride] + x[(2*i+2)*stride])
- (x[(2*i-2)*stride] + x[(2*i+4)*stride])) / 16;
if (k > 2)
x[(2*k-3)*stride] = d[k-2] + (x[(2*k-4)*stride]
+ x[(2*k-2)*stride]) / 2;
if (k > 1)
x[(n-1)*stride] = d[k-1] + x[(n-2)*stride];
}
}
static
void inv_synthesize_4 (TYPE *x, const TYPE *s, const TYPE *d, int stride, int n)
{
int i, k=n/2;
x[0] = s[0] - d[1] / 2;
if (k > 1)
x[2*stride] = s[1] - (d[0] + d[1]) / 4;
for (i=2; i<k-1; i++)
x[2*i*stride] = s[i] - ((uint32_t) 9 * (d[i-1] + d[i])
- (d[i-2] + d[i+1])) / 32;
if (k > 2)
x[(2*k-2)*stride] = s[k-1] - (d[k-2] + d[k-1]) / 4;
if (n & 1)
x[2*k*stride] = s[k] - d[k-1] / 2;
}
static inline
void copyback_d (TYPE *x, const TYPE *d, int stride, int n)
{
int i, k=n/2;
for (i=0; i<k; i++)
x [(n-k+i)*stride] = d[i];
}
static inline
void copy_s_d (const TYPE *x, TYPE *s_d, int stride, int n)
{
int i;
for (i=0; i<n; i++)
s_d[i] = x [i*stride];
}
typedef
void (*FwdSFnc) (const TYPE *x, TYPE *s, const TYPE *d, int stride, int n);
typedef
void (*FwdAFnc) (const TYPE *x, TYPE *d, int stride, int n);
typedef
void (*InvSFnc) (TYPE *x, const TYPE *s, const TYPE *d, int stride, int n);
typedef
void (*InvAFnc) (TYPE *x, const TYPE *d, int stride, int n);
static FwdSFnc fwd_synthesize [] = { NULL, fwd_synthesize_1, fwd_synthesize_2,
NULL, fwd_synthesize_4 };
tatic FwdAFnc fwd_analyze [] = { NULL, fwd_analyze_1, fwd_analyze_2,
NULL, fwd_analyze_4 };
tatic InvSFnc inv_synthesize [] = { NULL, inv_synthesize_1, inv_synthesize_2,
NULL, inv_synthesize_4 };
tatic InvAFnc inv_analyze [] = { NULL, inv_analyze_1, inv_analyze_2,
NULL, inv_analyze_4 };
static inline
void fwd_xform (TYPE *scratchbuf, TYPE *data, int stride, int n,
int a_moments, int s_moments)
{
TYPE *x = data;
TYPE *d = scratchbuf;
TYPE *s = data;
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
fwd_analyze [a_moments] (x, d, stride, n);
fwd_synthesize [s_moments] (x, s, d, stride, n);
copyback_d (x, d, stride, n);
}
static inline
void inv_xform (TYPE *scratchbuf, TYPE *data, int stride, int n,
int a_moments, int s_moments)
{
int k=n/2;
TYPE *x = data;
TYPE *s = scratchbuf;
TYPE *d = scratchbuf + n - k;
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
copy_s_d (data, scratchbuf, stride, n);
inv_synthesize [s_moments] (x, s, d, stride, n);
inv_analyze [a_moments] (x, d, stride, n);
}
void wavelet_3d_buf_fwd_xform (Wavelet3DBuf* buf, int a_moments, int s_moments)
{
int level;
for (level=buf->scales-1; level>0; level--) {
uint32_t w = buf->w[level];
uint32_t h = buf->h[level];
uint32_t f = buf->f[level];
if (w > 1) {
int row, frame;
for (frame=0; frame<f; frame++) {
for (row=0; row<h; row++) {
TYPE *data = buf->data + (frame * buf->height + row) * buf->width;
fwd_xform (buf->scratchbuf, data, 1, w, a_moments, s_moments);
}
}
}
if (h > 1) {
int col, frame;
for (frame=0; frame<f; frame++) {
for (col=0; col<w; col++) {
TYPE *data = buf->data + frame * buf->width * buf->height + col;
fwd_xform (buf->scratchbuf, data, buf->width, h,
a_moments, s_moments);
}
}
}
if (f > 1) {
int i, j;
for (j=0; j<h; j++) {
for (i=0; i<w; i++) {
TYPE *data = buf->data + j*buf->width + i;
fwd_xform (buf->scratchbuf, data, buf->width * buf->height, f,
a_moments, s_moments);
}
}
}
}
}
void wavelet_3d_buf_inv_xform (Wavelet3DBuf* buf, int a_moments, int s_moments)
{
int level;
for (level=1; level<buf->scales; level++) {
uint32_t w = buf->w[level];
uint32_t h = buf->h[level];
uint32_t f = buf->f[level];
if (f > 1) {
int i, j;
for (j=0; j<h; j++) {
for (i=0; i<w; i++) {
TYPE *data = buf->data + j*buf->width + i;
inv_xform (buf->scratchbuf, data, buf->width * buf->height, f,
a_moments, s_moments);
}
}
}
if (h > 1) {
int col, frame;
for (frame=0; frame<f; frame++) {
for (col=0; col<w; col++) {
TYPE *data = buf->data + frame * buf->width * buf->height + col;
inv_xform (buf->scratchbuf, data, buf->width, h,
a_moments, s_moments);
}
}
}
if (w > 1) {
int row, frame;
for (frame=0; frame<f; frame++) {
for (row=0; row<h; row++) {
TYPE *data = buf->data + (frame * buf->height + row) * buf->width;
inv_xform (buf->scratchbuf, data, 1, w, a_moments, s_moments);
}
}
}
}
}
1.1 w3d/docs/Makefile
Index: Makefile
===================================================================
RM = rm -f
TARGET = main.ps
$(TARGET):
$(RM) $(TARGET).gz
latex $(TARGET:.ps=.tex)
latex $(TARGET:.ps=.tex)
dvips $(TARGET:.ps=.dvi) -o $(TARGET)
gzip $(TARGET)
clean:
$(RM) $(TARGET) $(TARGET).gz $(TARGET:.ps=.dvi) *.log *.aux
1.1 w3d/docs/bibliography.tex
Index: bibliography.tex
===================================================================
\begin{thebibliography}{888}
\bibitem{salomon}
David Salomon, "Data Compression: the complete reference", 2nd ed.,
Springer Verlag New York, 2000,
(good book about data compression in general -- partially available on David Salomon's homepage)
\bibitem{compressionpointer}
a site with many data compression links: \verb|www.compressionpointer.org|
\bibitem{athome}
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)
\bibitem{icip97}
A.R. Calderbank, Ingrid Daubechies, Wim Sweldens, Boon-Lock Yeo,
"Lossless Image Compression using Integer to Integer Wavelet Transforms",
(brief introduction to integer transforms, \verb|icip97.ps|)
\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)
\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|)
\end{thebibliography}
1.1 w3d/docs/colorspace.tex
Index: colorspace.tex
===================================================================
\section{ Colorspace Conversion }
\subsection{ exact YUV }
An Integer implementation of the exact RGB to YUV transform is given by
\begin{eqnarray}
Y &=& ( 77 R + 150 G + 29 B) / 256 \nonumber\\
U &=& (-44 R - 87 G + 131 B) / 256 \nonumber\\
V &=& (131 R - 110 G - 21 B) / 256 \nonumber\\
\nonumber
\end{eqnarray}
You get the reversed transform by inverting this matrix. I don't have the
integer representation here, simply multiply all values by 256/256 if you
really need one \dots
\begin{eqnarray}
R &=& Y + 1.371 V \nonumber\\
G &=& Y - 0.698 V - 0.336 U \nonumber\\
B &=& Y + 1.732 U \nonumber\\
\nonumber
\end{eqnarray}
\subsection{ something like YUV but faster }
Since the wavelet transform is expansive, all computations have to be done using
at least 16bit Integers when transforming 8bit Integers. Thus we have to copy
the entire image into a buffer of 16bit Integers. The following transform is
cheap enough to be done on-the-fly while copying data:
\begin{eqnarray}
V &=& R - G \nonumber\\
U &=& B - G \nonumber\\
Y &=& G + (U + V) / 4 \nonumber\\
\nonumber
\end{eqnarray}
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.
As usual we can generate the inverse transform by running the algorithm
backwards and inverting all operations:
\begin{eqnarray}
G &=& Y - (U + V) / 4 \nonumber\\
B &=& U + G \nonumber\\
R &=& V + G \nonumber\\
\nonumber
\end{eqnarray}
If someone needs as 'exact YUV to this colorspace' transform he can simply
multiply the two transform matrices together.
1.1 w3d/docs/entropycoder.tex
Index: entropycoder.tex
===================================================================
\section{ Entropy Coder }
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.
Any Volunteers ?
1.1 w3d/docs/intro.tex
Index: intro.tex
===================================================================
\section{ Introduction }
Hi, this is some preliminary documentation to the tarkin/w3d code. It's written
to document the code, explain and discuss the used algorithms and help those
ones who want to read or modify the code.
It's neither complete nor written to learn everything about compression
algorithms. If you want more general introductions to data compressions please
take a look in the Bibliography to find some pointers.
The first section will give a brief overview over the compression codec.
Then all parts of the encoder/decoder will be described in the order they appear
in the encoder. Have fun !
\section{ Overview }
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
less bits to encode and can be compressed well by entropy coders.
An RGB image is first transformed into a YUV-alike colorspace to decorrelate in
color direction, U and V are usually much smaller than the RGB components.
Y is a weighted average of the red, green and blue color component.
Then each color component is then transformed into frequency space using a
lifting integer wavelet transform. This is again decorrelating, this time in
image space direction. Our wavelet transform implementation can handle 1D-,
2D- and 3D-data. The resulting coefficients are then quantized and entropy
coded, these areas still need a lot of work, thus they are not yet documented.
1.1 w3d/docs/main.tex
Index: main.tex
===================================================================
\documentclass[10pt,a4paper]{article}
\begin{document}
\include{intro}
\include{colorspace}
\include{wavelet}
\include{quantizer}
\include{entropycoder}
\include{bibliography}
\end{document}
1.1 w3d/docs/quantizer.tex
Index: quantizer.tex
===================================================================
\section{ The Coefficient Quantizer }
I'll describe this as soon it works \dots
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).
When you don't transmit the entire bitstream you quantize and threshold the
coefficients implicitly by cutting away insignificand bits and small
coefficients.
1.1 w3d/docs/wavelet.tex
Index: wavelet.tex
===================================================================
\section{ Wavelet filters }
This section will desribe the filters used for image decomposition implemented
in \verb|wavelet_xform.c|. The current code allows arbitrary combinations of
high- and lowpass filters.
\subsection{ Analyzing highpass filters }
The following table lists the highpass filters. Order is the number of vanishing
moments of the filter.
\begin{center}
\scriptsize
\begin{tabular}{cl}
\hline
order & filter \\
\hline
1 & $d_{i} = x_{2i+1} - x_{2i}$ \\
2 & $d_{i} = x_{2i+1} - [x_{2i} + x_{2i+2}] / 2$ \\
4 & $d_{i} = x_{2i+1} - [9 (x_{2i} + x_{2i+2}) - (x_{2i-2} + x_{2i+4})] / 16$ \\
6 & $d_{i} = x_{2i+1} - [150 (x_{2i} + x_{2i+2}) - 25 (x_{2i-2} + x_{2i+4}) + 3 (x_{2i-4} + x_{2i+6})] / 256$ \\
\hline
\end{tabular}
\end{center}
The highpass filter with 6 vanishing moments is not yet implemented. I'm not
sure if this would make sense, it's wide support will probably cause ringing
and could make the transform slow.
All highpass filters are expanding because of differencing (8 bit input force
\mbox{9 bit} output). To avoid overflows we have to use 16bit-Integers when
transforming 8bit images.
\subsection{ Synthesizing Lowpass filters }
\begin{center}
\scriptsize
\begin{tabular}{cl}
\hline
order & filter \\
\hline
1 & $s_{i} = x_{2i} + d_{i} / 2$ \\
2 & $s_{i} = x_{2i} + [d_{i-1} + d_{i}] / 4$ \\
4 & $s_{i} = x_{2i} + [9 (d_{i-1} + d_{i}) - (d_{i-2} + d_{i+1})] / 32$ \\
\hline
\end{tabular}
\end{center}
Lowpass filtering is an averaging operation and preserves the number of
required bits to represent the coefficients.
\subsection{ Applying the Transform to a row of data }
Here you see how handling of no-power-of-two-sizes is done at the example of the
(1,1) wavelet.
We use a mirrored low-order filter at the right boundary when $n$ is odd:
\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$ & for $0 \le i < n/2$ \\
& $s_{i}$ & $=$ & $x_{2i} + d_{i} / 2$ & for $0 \le i < n/2$ \\
\hline
$n$ is odd: & $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$ & for $0 \le i < n/2$ \\
& $s_{i}$ & $=$ & $x_{2i} + d_{i} / 2$ & for $0 \le i < n/2$ \\
& $s_{i}$ & $=$ & $x_{2i} - d_{i} / 2$ & for $i = n/2$ \\
\hline
\end{tabular}
\end{center}
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$.
\subsection{ The inverse Transform }
To reconstruct the original data we simply can reverse all operations and apply
them in reversed direction:
\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $x_{2i}$ & $=$ & $s_{i} - d_{i} / 2$ & for $0 \le i < n/2$ \\
& $x_{2i+1}$ & $=$ & $d_{i} + x_{2i}$ & for $0 \le i < n/2$ \\
\hline
$n$ is odd: & $x_{2i}$ & $=$ & $s_{i} - d_{i} / 2$ & for $0 \le i < n/2$ \\
& $x_{2i}$ & $=$ & $s_{i} + d_{i} / 2$ & for $i = n/2$ \\
& $x_{2i+1}$ & $=$ & $d_{i} + x_{2i}$ & for $0 \le i < n/2$ \\
\hline
\end{tabular}
\end{center}
\subsection{ Higher Order Filters }
The smooth high-order filter kernels have a wider support and need some special
handling at boundaries. Here we simply insert low-order wavelets. Below the
example of the Highpass with 2 vanishing moments:
\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $d_{i}$ & $=$ & $x_{2i+1} - [x_{2i} + x_{2i+2}] / 2$
& for $0 \le i < n/2-1$ \\
& $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$ & for $i = n/2-1$ \\
\hline
\end{tabular}
\end{center}
--- >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