) (03/31/91)
I need some suggestions for compression of B/W line drawings for an on line data base. I don't care if the compression is slow, but I would like to do decompression on the fly and directly to the screen. A slightly lossy technique would be OK as the original images aren't all that good. With so much white space there has got to be something that will be fairly compact!! Thanks in advance for any help. ******************************************************************* Albrecht Jander Microwave Packaging Lab. Washington University in St. Louis E-mail> aj6818@cec1.wustl.edu ***********************************************************************
micro@imada.dk (Klaus Pedersen) (04/03/91)
aj6818@cec1.wustl.edu (Albrecht!) writes: >I need some suggestions for compression of B/W line drawings for an on line >data base. I don't care if the compression is slow, but I would like to >do decompression on the fly and directly to the screen. A slightly lossy >technique would be OK as the original images aren't all that good. >With so much white space there has got to be something that will be fairly >compact!! After all this math. teori in this newsgroup it's nice to see a call for some ad-hog code. There is one thing I don't understand, though. Why are you keeping the images as bitmap and not vectores? Anyway, the most simple way I can think of is, to encode the distance between 'on' pixels. One can encode the distance in bytes after the following scheme: 1 : turn on the pixel at the cursor, and move the cursor one pixel 2 : move 1 pixels, turn on the pixel at the cursor, and move 1 pixel 3 : move 2 pixels, turn on the pixel at the cursor, and move 1 pixel . : 255 : move 254 pixels, turn on the pixel at the cursor, and move 1 pixel 0 : (surprice) move 254 pixels and don't set pixel, and move 1 pixel (or simply "move 255 pixels to the left") (I think of the screen as a long line of pixels) With this scheme you can set the first pixel, the second, ..., the 254., the 255. (0,1). You can make all black (1,1,...,1). You can make all white (0,0,...,0). When you have made the byte array, you probaly want to Hoffman code them. If your line drawings have more than 1 set pixel for each 8 clear (in mean), your 'run length' coded file will be longer than your bit-image... (but then you should use 3 bits to encode the length...) Huffman will solve this problem automatic, by giving each 'length token' a length which is optimal. (or as optimal it can be with a integer number of bits per token). But If there is _very_ few pixels on pixels in your drawings, then you probaly don't want to make your code more complex with Huffman. And the win will probaly be very small... Klaus (micro@imada.dk) (now lets hear the *real* experts...)
ge@dbf.kun.nl (Ge' Weijers) (04/03/91)
aj6818@cec1.wustl.edu (Albrecht!) writes: >I need some suggestions for compression of B/W line drawings for an on line >data base. I don't care if the compression is slow, but I would like to >do decompression on the fly and directly to the screen. A slightly lossy >technique would be OK as the original images aren't all that good. >With so much white space there has got to be something that will be fairly >compact!! If you're pictures are fairly simple a compression scheme like runlength encoding should give good performance. You might want to try the scheme used in fax machines. See International Digital Facsimile Coding Standards Roy Hunter and A. Harry Robinson Proceedings of the IEEE, vol. 68, no. 7, july 1980 which describes the group-3 fax coding procedure, a.k.a. the MREAD algorithm. It uses Huffman codes to compress the run-lengths. You can simplify the algorithm somewhat for your purposes as you do not need to recover from communication errors (i.e. only use the two-dimensional compression, assuming the actual image is preceded by a blank line). Ge' Weijers -- Ge' Weijers Internet/UUCP: ge@cs.kun.nl Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge) University of Nijmegen, Toernooiveld 1 6525 ED Nijmegen, the Netherlands tel. +3180652483 (UTC-2)
nbvs@cl.cam.ac.uk (Nicko van Someren) (04/05/91)
>aj6818@cec1.wustl.edu (Albrecht!) writes: > >>I need some suggestions for compression of B/W line drawings for an on line >>data base. I don't care if the compression is slow, but I would like to >>do decompression on the fly and directly to the screen. A slightly lossy >>technique would be OK as the original images aren't all that good. > >>With so much white space there has got to be something that will be fairly >>compact!! On real line drawings the best way to store it is probably as lines. Why don't you vectorise the lines and store the vectors. It should decompress quite fast... +-----------------------------------------------------------------------------+ | Nicko van Someren, nbvs@cl.cam.ac.uk, (44) 223 358707 or (44) 860 498903 | +-----------------------------------------------------------------------------+