Slashdot Mirror
A New Web Image Format
MrP- writes: "BetaNews is reporting that a company called LizardTech has developed a new image format for the Web called DjVu." Apparently, it differentiates between forground and background components of an image, and compresses each appropriately. Good idea, but I'm skeptical of improvements (especially because they say it's "20 times faster then gifs" -- which measure compression in terms of speed? And they also say it compresses faster then pdf, but pdf isn't really an
image format). No Linux support. And I don't see any source code on the format, so don't expect it to get a lot of support on any major Web sites, regardless of the compression.
DjVu is almost three years old. It was developed by AT&T not LizardTech. LizardTech just bought it about 8 months ago. It is not, was not, and will never be designed to replace PDF, GIF, JPEG, or PNG. I have been using DjVu as the core of a web based document management system for over a year and a half. It is absolutely bar none the best, fastest, and most cross platform way to go from paper->web out there.
Look at the ways to get a scanned document on the web:
1) GIF, PNG, JPEG: Large filesize or bad rendering. If I need to send a 300dpi page to a web browser, the browser isn't going to let a user pan and zoom on it and it certainly won't print it correctly. JPEG is the only one of the three formats that actually has a place to store the document DPI regardless.
2) PDF: Creating a pdf from a scanned image means either encapsulating a lossy or losless image in a file or doing OCR and risking unreliable information.
DjVu regularly achieves compression ratios of 1200:1 or more at very very acceptible quality. There is a IW44 fractal compressed background layer and a loslessly compressed foreground layer. The information is progressive also. As the file downloads the foreground shows, then the background, then the color information loads. Example documents on the DjVu website have shown entire 300 dpi full color sharper image catalogs compressed to fit on a floppy disk.
Btw not only are djvu plugins available for windows, macintosh, linux, and solaris. Let's not forget HP-UX and IRIX. How's that for covering the bases? If youre not supported, you can write your own for your particular flavor of UNIX.
Geez get it straight.
~GoRK
Did anybody even follow the LizardTech link? Right on the front page is a link to a page describing DjVu. The whole product ("image format") seems geared towards scanning in Real Life documents and presenting them online. If you *read* the page it explains why it claims it is faster (first downloads high contrast data, then photographs and graphics, clarifying the image as it goes) and smaller (some wavelet kung foo). I don't see anywhere where they are pitching this as competition for gif or png, so everybody put down the flamethrowers. This is a very small niche product for digitizing and presenting real life mundane documents.
It's 10 PM. Do you know if you're un-American?
Compression speed DOES matter. First of all, many things on the web are compressed on the fly - you just don't see it. gzip is used, as far as I know, for most of it. Partly due to its modest processor usage. You try serving up a million pages all compressed using something like bzip2 on a rackmount server with only two processors - you'll quickly melt the metal.
Dave
'Round the firewall,
Out the modem,
Through the router,
Down the wire,
Barclay family motto:
Aut agere aut mori.
(Either action or death.)
Here's my own image compressor. It's just like jpeg but I had to trim the source a bit to fit inside the teeny-tiny submission box. I hope you can still understand it.
./en 50 | bzip2 > image.4a
./de > image2.pgm
8 ]-23.5)*LQ:1.0)*co[B*u+C*x]*\
) ;O=0.0; } } M+=\
N Zao~}mUehkvlok";
The codec emits a byte stream considerably larger than the raw image (4x) but this stream is easily compressed by bzip2 or gzip. It reads and writes portable gray map (.pgm) files (both ascii and binary). If you want color I suggest you transform the image into YUV colorspace and compress each plane seperately. The color planes should be downsampled 4:1 (2x2 blocks) and compressed at very low quality (less than 15).
Build instructions:
Save the code as 4a.c
gcc -O2 -ansi -Wall -o en -DMAGICK=1.0 4a.c -lm
cp en de
Running the program:
convert image.gif image.pgm
cat image.pgm |
cat image.4a | bunzip2 |
convert image2.pgm image2.gif
To make a pgm from a jpeg use:
djpeg -grayscale -pnm image.jpg > image.pgm
Hints:
Try quality settings from 15 to 200.
Bad input causes core dumps.
The image is cropped if the dimensions aren't divisible by 8.
====================
/* 4a by Ryan Salsbury */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define D(a,i) a=(i); while (a--) {
#define i int
#define d double
#define szi sizeof(i)
#define szd sizeof(d)
#define gc() getchar()
#define pc(c) putchar(c)
#define w while
#define v void
#define L goto
#define _9 2+7
#define _27 3+24
#define di(F,A,B,C,G,E) \
v F(i j,i h,G* M,E* S){ d O = 0.0; i x,y,u,q,s,t; D(t,h/8)D(s,j/8)D(y,8)D(x,8)\
D(q,8)D(u,8)O+=M[u+q*j]*(A?ca[u]*ca[q]*(lQ[u+q*
co[B*q+C*y]; } } S[x+y*j]=O*(A?1.0:ca[x]*ca[y]/(lQ[x+y*8]-23.5)/LQ
8; S+=8; } M+=j*7; S+=j*7; } }
i nm()
{
i c = gc(), a = 0;
L0: if (c > 32) L L1;
c = gc();
L L0;
L1: if (c - 35) L L2;
L3: if (c == 10) L L0;
c = gc();
L L3;
L2: if (c <= _9*_27 || c >= _27*_9) return a;
a=a*10+c-48;
c = gc();
L L2;
}
v rp(i* x, i* y, d** X)
{
d K, *V;
i h, m, p, G, H, I = gc()*gc();
*x = (p=nm())&~7;
*y = nm()&~7;
m = nm();
*X = V = malloc(256 + szd **x **y);
K = MAGICK;
D(G,*y) D(H,p)
if (I==4240) h = gc();
else h = nm();
*V++ = h*K - 128.0;
} V-=p-*x;
}
}
v wp(i x, i y, d* V)
{
i n;
printf("P2\n%i %i\n255\n", x, y);
D(n,x*y)
i l = *V+++128.0;
l = l&~0xff ? l>>31?0:255 : l;
printf((n%20)?"%i ":"%i\n", l);
}
pc(10);
}
d co[64], ca[8], LQ;
char* lQ = "%! %,9CK\"\"#(.IJF##%,9HRG#&*0Ca[L'*7GQtoY,5FN\\pweA
di(fw,0,1,8,d,i)
di(rv,1,8,1,i,d)
i main(i argc, char* argv[])
{
char T[32];
i x, y, *pi;
d* ui;
d p = 0.1963495408494;
d pp = 0.3535533905933;
D(y,8) D(x,8)
co[x+y*8] = cos((2*x+1)*y*p); }
ca[y] = y?0.5:pp; }
if (argv[0][strlen(argv[0])-1] == 'n')
{
LQ = 100.0 / ((argc-2) ? 70 : atoi(argv[1]));
rp(&x, &y, &ui);
pi = malloc(x*y*szi);
fw(x, y, ui, pi);
printf("%i\n%i\n%f\n", x, y, LQ);
fwrite(pi,szi,x*y,stdout);
}
else
{
x = nm();
y = nm();
LQ = atof(fgets(T,32,stdin));
ui = malloc(x*y*szd);
pi = malloc(x*y*szi);
fread(pi,szi,x*y,stdin);
rv(x, y, pi, ui);
wp(x, y, ui);
}
return 0;
}
I'm willing to bet those weren't in fact FIF files, but FITS files. FITS (flexible image transport system) is the de facto standard for astronomical images these days.
The problem is compressing them. The ideas behind decompressing fractals are easy; use the self similarity inherent in pictures (a tree looks much like another tree, so build a picture of a forest by layering trees and then correcting the errors).
But figuring this out ammounts to exhaustive search. Apparently IFS had decent heuristics that got decent compression in only a few minutes. I think this is what was licenced, and that the file-format was open? This was a while ago, so I'm filling in the gaps in memory by guessing.
Can it detect the difference between art and pornography?
I don't make the rules. I just make fun of them.
The BetaNews article is actually very misleading - it is confusing two of LizardTech's products.
DjVu is a document format (like PDF), not an image format, and the techniques mentioned in the article refer to compression of documents.
LizardTech do have a compressed image format. This is called MrSID, and uses completely different techniques for compression.
I would be interested to see an independent comparison between MrSID and PNG - unless there are huge advantages of using the proprietry MrSID format over the OS PNG format, I don't predict much of a future for MrSID on the web (although it would seem that LizardTech are touting it more for internal use rather than for general distribution anyway).
[Happosai]
I don't know why the summary on Slashdot says "No Linux support". LizardTech has both decoders and encoders available for Linux.
Also the summary picks on LizardTech's use of speed as a feature. While this isn't a standard measurement, it is a way to tell people that you will get your images faster because the files are smaller. That's not a big crime. They also do talk more specifically about their format producing smaller files, so they do understand real measurements. BTW, while it is possible that they say elsewhere that DjVu compresses faster than pdf, what I saw was that the documents download faster, not compress faster.
The Slashdot write-up complains about LizardTech's comparison of DjVu with pdf, pointing out that pdf isn't an image format. True, but the LizardTech description refers to DjVu as "DjVu for Documents", and their web page describes why DjVu is good for documents. Images seem to be just part of the data they need to handle.
Finally, I haven't seen any source for Acrobat either, but it is very popular on the Internet, so lack of source won't necessarily keep LizardTech from succeeding with DjVu.
Is DjVu actually any good? I have no idea. Slamming the product with incorrect and misleading comments doesn't help one decide, though.
My algorithm was lossless and what strikes me the most is the speed - my algorithm was notable for the speed of decompression, and we used it in particular just because it was so much faster than GIF, which was a significant advantage when you were scanning through lots of images on CDROM. While I only implemented it for 8-bit indexed images I felt it would likely work fine for any bit depth or color space.
Medior was later purchased by AOL and renamed to AOL Productions. I think AOL Productions isn't around anymore but lots of old Medior people still work for AOL, for example former Medior President Barry Shuler is a high-level exec at AOL.
Basically, my invention worked by dividing the image up into lots of little subregions and encoding each pixel in a given subregion in the minimum number of bits required to encode the number of colors that occurred in that region.
For example, in an image that was black on top and white on the bottom, I'd have two subreqions with zero bits each and a single element color table that was either black or white.
If it was snow - black and white pixels randomly intermixed - the whole image would be one bit with a two-element color table containing black and white.
The big trick was to divide the image in a good way, in such a way that the whole image was reduced the most and the size of the data required to reconstruct the regions wasn't too big. In practice I found it worked OK to start with lots of small fixed-size squares then merge adjacent squares that had similar color schemes.
I wrote a document for Medior that described what I invented in great detail and what I predicted this could be made to do. What I actually got it to do in practice was not nearly what it was capable of, but this was because of the limited time available to implement it.
Michael D. Crawford
GoingWare Inc
-- Could you use my software consulting serv
Like so many other factors, speed is one that does matter if in the extreme, but once it's good enough, it has very little importance. Size is arguably more important, because every byte saved is saved every time you use the file, while time saved is only saved during compression, which is often batched.
So for time, order of magnitude seems to be the differentiator, while size has a linear importance.
I hope that the GIF thing doesnt happen again.. ;)
Wait till it's a "standart" then ask for license fees.
The idea sounds pretty nice, but I'd like to see quality / compression ratio comparisions with hard numbers
Before you email me, remember: "There is no god!"
A few years ago a company came up with a compression which was actually rather good, using fractals. It was called FIF. They made the mistake of greed ovtaking common sense and tried to charge for a license to write compressors for it... The result - when is the last time you saw an FIF file?
If these guys don't have an open format they will simply go the same way.
See DjVu "non-commercial" site.
--Daniel
I am one of the four persons who created DjVu in the first place. The events took place in AT&T-Labs Research between 1997 and 1999.
Hope this helps :-).
- Leon Bottou, AT&T-Labs Research.
The article has it about right. Png is vastly superior - excellent lossless compression, sometimes better than lossy methods (plus technical features like a full alpha channel), and, most importantly for its dominance over gif, it is unencumbered by patents or closed source algorithms.
Speed of compression is not a factor in compression - otherwise we would use bmps or xpms, which have zero compression time - because they're uncompressed. Size matters. Speed doesn't.
I really can't see much market, and very little application for this compression. On-the-fly compression of images for web download would be redundant, since a png would be smaller than this format, so the speedy on-the-fly compression of uncompressed images is pointless.
And in any case, modern PCs are more than powerful enough to almost transparently display well compressed images, so a simpler format is about 10 years out of time.
If it was open source, it could perhaps have a market in replacing things like xpms, which are used in games for processing speed, but even it was, the benefit would be marginal, since hard disk space is, relative to image size, almost infinite, so compressing them slightly wouldn't make much difference - and for download those images would be gzipped anyway.
Free Anne Tomlinson!!
Not so fast - they have a plugin available for Netscape and IE at:
. pl?tsb=443224
http://www.lizardtech.com/cgi-bin/products/desc
Cheers,
Tim
It's official. Most of you are morons.
And how the heck does it figure out what the "foreground" and "background" components are, anyway?
As it only works on scans of paper documents, "background" is bland paper-texture, perhaps coloured. You can easily use an edge-detection filter to work out which is which.
Does my bum look big in this?
As I understand it, it is possible to set different compression factors (from lossless to very lossy) on different polygonal regions of a JPEG file.
Since JPEG is already fairly-well supported, why not use it? The only thing that needs to be changed is the image-creation software; it needs to know how to detect the difference between background and foreground content. Image-creation software also has a huge advantage here; layers (and their relative z-Indexes) give great hints as to what is, and what isn't, "background"
--
Do daemons dream of electric sleep()?
The photographs need moderate colour AND spatial resolution (say 24 bit, 72 DPI). This is a very old idea. Colour print systems in the 70's used it. What's neat is the idea of "gating" the lower resolution colour data through the higher resolution "shape mask" to get the properties of both, at least for real world pages.
Appropriate (and quite well known) compression techniques are then used on the 2 channels.
The wavelet technique you describe sounds like it would get the frequency separation concept in a more "implicit" way. DjVu is very explicit. BugBear
Ignorance is curable. Stupid is forever.
I wish people would get off the "if it's not OSS it must suck" bullshit attitude. LizardTech has some really well-designed software, and if it bothers you that they're proprietary (and IMHO, grossly overpriced), then bigod go out and clone it. Having an OSS equivalent of MrSID and DjVu, especially in a form that would be usable to the point-and-drool crowd, would be a very strong selling point for getting Linux into the MS/Adobe-dominated document archiving market.
--
Proud member of the Weirdo-American community.
Have a look at:
http://cgi.netscape.com/cgi-bin/pi_moreinfo.cgi?P
Will
per mere, per terras
Um, you can't arbitrarily change a license for software (that you have already licensed.)
If you have a free open-source encoder, you can continue using it for no cost. No $2000 fee.
retrorocket.o not found, launch anyway?
He posted this two years ago: DjVu plug-in available on Linux/Irix/Solaris/Mac. First post by sengan:
:-)
New Image Compression Algorithm claims 1000:1 ratio
Hasdi
The big problem I have with this article is that DJVu isn't a "new image format". It doesn't even display things inline (like GIF, PNG and JPEG). It is however an excellent alternative to PDF if size of file is your main concern.
The extensive references to "speed" when compared to GIFs and PDFs could be one of two things. They could be talking about Download speed (my personal experiences show DjVu files to be about 10 times smaller than GIFs and even more when compared to PDFs. Or, they might be speaking of encoding speed which DjVu seems to excel in
Here is a problem however: the command line encoder used to be free for non-commercial use. I was using DjVu for encoding swim-team documents for a small non-scholarship collegiate swim team. Certainly this counts as non-commercial. HOwever, the new version from Lizard Tech would cost me $2,000 USD to run. That is absurd by comparison. So I'm abandoning DjVu since I can no longer afford the encoder.
Incidentally, if you want to see how it worked for me, I used it on nearly every swim meet results page for a few years. Here is an example, just click on the links next to the word "Splits" in each event: http://www.k-swimming.org/cgi-bin/swimming/results /meet_view.pl?8
Werd.
First you have to have a good format, then it has to be accessible and affordable, then it has to be accepted. For the life of me, I can't figure out why PNG hasn't replaced GIF.
Actually, though, that's part of the final hurdle -- a Catch-22. No one will adopt it until web pages and browsers support it. Web pages won't support it until browsers do and browsers have no reason to until web page creators demand it.
And why exactly is "fractal compression" so much better than wavelet-based?
.|` Clouds cross the black moonlight,
~Tim
--
~Tim
--
Rushing on down to the circle of the turn
They have a browser plugin for Linux/x86/glibc2 available for download here
Yes, I know that link is broken becauseBe careful. People in masks cannot be trusted.
DjVu has been around for 2 years, and isn't anything new. In fact, it wasn't actually designed by Lizardtech - it was developed as an Open Source technology in the Olivetti and Oracle Researtch labs in Camridge, UK, and was sold when US telco AT&T purcahsed the labs.
Hence the Open Source products generally only seem to be there to satisfy existing licensing requirements from prior to Lizardtech's purchase. It's doubtful Lizardtech tend to encorage that aspect of the technology, and they're only promoting the closed source stuff.
However, the compression is indeed very real and the cross platform nature makes it quite useful for archiving stuff that won't be modified frequently in the future - remeber, that text ain't vectorized, it's just another layered image, AFAICT.
GIF = "jif"
JPEG = "JAY-peg"
PNG = "ping"
DjVu = "duh-ju-voo"
So you have the choice between drooling on yourself or saying "deja vu," which has more syllables, tone changes, and stops than its nearest competitors. Plus the danger of the illiterate calling it "day-JAH-voo."
-----
Go ahead, blame me... I voted for Nader!
-----
Go ahead, blame me... I voted for Nader!
There's another competitor to MrSID by Iterated Systems called MediaBin. We were helping Iterated out from an actual field use (we're a prepress/graphic arts shop) but they were more interested in the science and not implementation. Looks like MediaBin is their offering.
Lately we've been much more interested in MrSID and have been using it a little bit, but are hoping to include it in our home brewed media management system.
Jason
It appears that they've simply filtered the documents into 2 layers.
One for bilevel compression, say using CCITT group 4 compression (Faxes use group 3, group 4 is better ratio, but bigger disaster if you drop a bit), or maybe JBIG (IBM have a patent on the statistical model of the Q boxes, not on the actual compression algorithm, so all you need are your own Q boxes). Both of the above compare the current line with the previous line, and barf horribly when given dithered bilevel images, such as newspaper photos, or noisy scans.
The second layer is the full colour one, and can be implimented as a JPEG.
Tiff 6 supports all of the above.
The 3GB Tiff document they talk about on their site was probably 3GB using the "uncompressed" setting. Apples and Oranges, as they say.
The world doesn't need any new de-facto "standards" when there are perfectly good present non-proprietory standards which can do the same.
FP
Also FatPhil on SoylentNews, id 863
> IMHO there's very little need for highly compressed images on the web right now.
If you download a whole book with text + pictures, then it would make a difference.
Today, scans of archives avalaible on the web are often ugly 1bits-per-pixels low-res scan embedded in PDFs. And that suck badly / is almost unreadable.
So, DjVu _is_ something interesting for reading non-copyrighted papers, research work, FOI publications, or public domains archives.
> but considering the format's not open
As many others have already pointed, the format is open.
Cheers,
--fred
1 reply beneath your current threshold.
Code commentary is like sex.
If it's good, it's VERY good.
My office has been taken over by iPod people.
Corporate digital asset collections
Real estate sites
Online catalogs/retail companies
Auction sites
Libraries
Medical sites
Geospatial imagery/government agencies
Corporations are storing everything digitally now: pictures, instructions, etc and need are searching for a way to manage all of this. This product is attempt to fill that void.
In a nutshell, this will be a specialized format that we will see for businesses that need to pass digital assets to the user.
I have a positive modifier on Troll. When I mod someone Troll their karma should go UP!
Its more a document archiving format than a new web image format [although it happens to be viewable over the web] - as the article states although its non vectorized, it uses layered bitmaps to create more efficiently encodable data chunks.
:-)
And, actually, there is Linux support, and source code available. Just Lizardtech aren't going out of the way to tell anybody about it - see my above post
Now the claims on the document format bother me. First, they compare it against PDF which we all know is large and bloated to begin with. Sure, if I took any document and separated out the text and formatting and images, compressed it down I'd probably have a "new" revolutionary document format. Doesn't this just sound like HTML? I've written server side scripts and client applets that will compress HTML the same way, and I think my results would be about the same as this (and perhaps faster?). You'll still need their plug-in to view their documents. They also say that a 2.5gb TIFF is compressed down to 3mb. Wow. I can do that now if I convert the TIFF to JPEG with little loss of quality. I really don't see what the big deal is about.
I wish the /. reporters would do a little research before they go posting messages that send the readers into a frenzy of clicking and sending off emails to friends about the next wave sweeping the internet.
liB
The main attraction of DjVu is that your scanned documents are tiny (typically less than 50KB) which makes it feasible for putting them on the web. Just about every other format results in files too big for easy distribution on the web. Interestingly, you can convert a *.ps.gz file into a DjVu file, and see a dramatic improvement in file size while preserving almost all of the detail. I am not talking about simple pages here, by very complex ones with a mixture or real images / artwork, and text.
Apologies for any mistakes, but I think that I got most of it right.
-- GWF
The Computational Beauty of Nature
LizardTech had a booth at Seybold this year, and let me tell you this technology is very, very impressive. They demonstrated extremely high-res files at various zoom points--and explained that the files were very small. This thing also worked lightning fast. Except for a just-visible delay, zooming happens almost instantly. Another thing: I'm fairly sure it was doing raster, not vector. In any case, it was obvious it went way beyond PNG.
> Apparently, it differentiates between forground and background components of an image, and compresses each appropriately.
Yeah, but can it detect the difference between nude and naked?
Sheesh, evil *and* a jerk. -- Jade
Wait - I get it ;,)