Page 2 of 3 FirstFirst 123 LastLast
Results 31 to 60 of 64

Thread: iz: New fast lossless RGB photo compression

  1. #31
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Without full optimization enabled it is about 7 times slower but it works with wine here.

  2. #32
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    thanks Shelwien for compiling.


    the executable still crashes on my 64bit win7.

  3. #33
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,130
    Thanks
    179
    Thanked 919 Times in 467 Posts
    With my test file?

  4. #34
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    your test file works, but none of my 24.bit ppm images..

  5. #35
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Okey, I never give up

    I tantalized google until I was able to install and run a Windows cross compiler on my Linux box. The result does work with wine, but somebody please test if this also works on Windows: http://skulpture.maxiom.de/playground/iz.exe

    It is an 32-bit binary, not sure if this will work on 64-bit Windows, or if it has to be compiled specifically for that.

    This binary requires at least an MMX processor! No MMX => Crash!

  6. #36
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Quote Originally Posted by Stephan Busch View Post
    thanks Shelwien for compiling.


    the executable still crashes on my 64bit win7.
    It probably crashes because of the missing optimization. The predictor accesses pixels outside the image borders, unless it gets inlined and the compiler optimizes away the unused pixel accesses.

  7. #37
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    maybe the image is too large? http://www.squeezechart.com/nikon24.ppm - does it compress on your systems?

  8. #38
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Cross compiling is fun, I could actually create a Win64-bit executable on my 32-bit system: http://skulpture.maxiom.de/playground/iz64.exe

    This one I could not test, though. You can emulate Windows API with wine, but not a new processor :P

    So would be nice if someone could confirm if it works.

    I also ran the complete LPCB benchmark using wine, and the timings are identical compared to the Linux binary.

  9. #39
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Quote Originally Posted by Stephan Busch View Post
    maybe the image is too large? http://www.squeezechart.com/nikon24.ppm - does it compress on your systems?
    Yes, with large images, Windows probably allocates separate pages of memory which results in access violation with the unoptimized binary. Please try the binaries from comment #35 or #38 (ideally both, since I am interested how big the performance improvement is when using a native 64-bit binary).

  10. #40
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    Hey Christoph,

    your 64-bit build works on my system. IZ is incredibly fast and compresses better than .png in some cases.
    I will put online results tomorrow.

  11. #41
    Tester
    Black_Fox's Avatar
    Join Date
    May 2008
    Location
    [CZE] Czechia
    Posts
    471
    Thanks
    26
    Thanked 9 Times in 8 Posts
    Quote Originally Posted by cfeck View Post
    It is an 32-bit binary, not sure if this will work on 64-bit Windows, or if it has to be compiled specifically for that.
    32-bit binaries should work on 64-bit Windows as well as 64-bit.
    I am... Black_Fox... my discontinued benchmark
    "No one involved in computers would ever say that a certain amount of memory is enough for all time? I keep bumping into that silly quotation attributed to me that says 640K of memory is enough. There's never a citation; the quotation just floats like a rumor, repeated again and again." -- Bill Gates

  12. #42
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post

    Thumbs up iz.exe CB6E0119 ok

    Executable from #35 with CRC32 CB6E0119 was able to compress this 66.2M (23 MP) picture of the moon, attachment here is Zip file wrapper around a ZPAQ fileClick image for larger version. 

Name:	moon.png 
Views:	349 
Size:	73.8 KB 
ID:	1895 You may notice I had to rotate the moon to make it fit into the ZPAQ file ( Used pzpaq -7 moon.ppm, pzpaq 0.06 )

    Ran on Win7 Professional 32bit ( version 6.1 Build 7601 Service Pack 1 )
    Attached Files Attached Files
    Last edited by Karhunen; 23rd March 2012 at 21:36. Reason: add platform

  13. #43
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Karhunen, thanks for the confirmation. Note that IZ only works with color images, though.

  14. #44
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    Karhunen, thanks for the confirmation. Note that IZ only works with color images, though.
    Yes, but since this image is 1003 unique colors, and has a watermark in the bottom right hand corner, ( which I blow up below ) it is "technically" in color.

    Click image for larger version. 

Name:	watermark.png 
Views:	319 
Size:	6.7 KB 
ID:	1904

  15. #45
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by cfeck View Post
    Hi all, I finally managed to release a first preview of "iz" (ImageZero). HI am very interested in any kind of feedback, since I am new to this forum. Thanks, Christoph
    Now that I have studied the code a bit,may I ask a question? In how far is this different from lossless JPEG, actually? (Not JPEG-LS, which is a different code)

    If you look into the "Pink Book", you find a description of the lossless JPEG mode which, unless I'm mistaken, a duplicate of your code. Basically, it is prediction (one out of six predictors there) plus static Huffman coding of the residual.

  16. #46
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Quote Originally Posted by thorfdbg View Post
    If you look into the "Pink Book", you find a description of the lossless JPEG mode which, unless I'm mistaken, a duplicate of your code. Basically, it is prediction (one out of six predictors there) plus static Huffman coding of the residual.
    If you are publically accusing me of code duplication, please provide a link so that others can compare. IZ does not use Huffman coding for the residuals; the residual bits are stored verbatim. And prediction is even used by PNG.

  17. #47
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by cfeck View Post
    If you are publically accusing me of code duplication, please provide a link so that others can compare. IZ does not use Huffman coding for the residuals; the residual bits are stored verbatim. And prediction is even used by PNG.
    Sorry for not formulating carefully. I'm not asking about the code (implementation), I'm asking about the method (algorithm). The JPEG lossless algorithm is described in the ISO standard of JPEG of course: ISO/IEC 10918-1 aka ITU-T T.81. If you're looking for a copy, you find one in the "Pink Book" (Pennebaker, Mitchell: JPEG Still Image Data Compression Standard) which you surely find in a library. I believe ITU might even hand out copies for free. A verbatim copy of the residuals is also a Huffman code, btw. So, in other words, what can't a careful implementation of JPEG do what your code can?

  18. #48
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    In how far is this different from lossless JPEG, actually?
    Okey, I found the source of a LJPEG decoder at http://web.aanet.com.au/~ospiropo/do...peg/ljpeg.html and compared it against IZ (and other similar lossless algorithms).

    Similarities:
    - Both use 3-pixel prediction (PNG, SFALIC, PCIF, and JPEG-LS also do)
    - Both store the residual bits uncompressed, which indeed makes them identical on first look (I had the initial impression that residuals bits are stored inside the Huffman code in LJPEG, sorry for not having checked earlier)

    Differences:
    - IZ has different 3-pixel predictors, they are not available in LJPEG (but can be found in SFALIC or JPEG-LS)
    - IZ does minimal context modeling, and selects Huffman tables according to the pixel's context value (pixel context modeling is also used in SFALIC and JPEG-LS, but is more complex there)
    - IZ stores only one Huffman code for each RGB pixel, whereas LJPEG needs three (this is unique to IZ, as far as I know)
    - Due to this, IZ can only handle RGB images, whereas all other methods support single-component (grayscale) images

    Additionally, IZ is designed with high-performance in mind. For example, it limits Huffman code lengths to 6 bits to avoid big tables or out-of-table handling as in LJPEG.

    So, in other words, what can't a careful implementation of JPEG do what your code can?
    JPEG can do more than IZ, obviously (it's like comparing LZ4 and WinZip). Since the LJPEG source is only a decoder, I cannot compare the performance on my machine to give numbers, but according to the LPCB page, LJPEG even compresses worse and decompresses slower than PNG. If you know of a "careful implementation" (which is faster), let me know, and exact benchmarks can be made.

  19. #49
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by cfeck View Post
    Differences: - IZ has different 3-pixel predictors, they are not available in LJPEG (but can be found in SFALIC or JPEG-LS) - IZ does minimal context modeling, and selects Huffman tables according to the pixel's context value (pixel context modeling is also used in SFALIC and JPEG-LS, but is more complex there) - IZ stores only one Huffman code for each RGB pixel, whereas LJPEG needs three (this is unique to IZ, as far as I know) - Due to this, IZ can only handle RGB images, whereas all other methods support single-component (grayscale) images.
    Thanks, I see. So you have context modelling plus a single symbol per triple. This was kind of what I was asking for.
    Quote Originally Posted by cfeck View Post
    Additionally, IZ is designed with high-performance in mind. For example, it limits Huffman code lengths to 6 bits to avoid big tables or out-of-table handling as in LJPEG.
    True, but I wasn't worried about this too much.
    Quote Originally Posted by cfeck View Post
    ...but according to the LPCB page, LJPEG even compresses worse and decompresses slower than PNG. If you know of a "careful implementation" (which is faster), let me know, and exact benchmarks can be made.
    As far as compression performance goes, my measurements agree with yours for the Huffman lossless mode. AC coded lossless mode performs a bit better than PNG. On the JPEG core-1 test image set, PNG compresses to 12.9 bpp, Huffman lossless JPEG to 14.9, Huffman lossless AC coded to 12.7, LS to 11.8. There are a couple of other possibilites for lossless coding, including the hierarchical mode, but I would spare the details. As far as speed is concerned, I do not have any valid data - my implementation of lossless JPEG is surely suboptimal and not fast. I would have access to a fast inhouse version of it, though that would be pretty much an apples to oranges comparison because *that* code is partially in assembler.

  20. #50
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    AFIAK assemby language is not an important aspect in general programming anymore, except when code size is important or one needs to implement a feature not supported by the compiler. Because of the need to parellize instructions, avoid cache misses, and other complicated architecture, the ability to expect performance gains from assembly on modern CPUs is a thing of the past.

  21. #51
    Member
    Join Date
    Apr 2012
    Location
    Stuttgart
    Posts
    437
    Thanks
    1
    Thanked 96 Times in 57 Posts
    Quote Originally Posted by Karhunen View Post
    AFIAK assemby language is not an important aspect in general programming anymore, except when code size is important or one needs to implement a feature not supported by the compiler. Because of the need to parellize instructions, avoid cache misses, and other complicated architecture, the ability to expect performance gains from assembly on modern CPUs is a thing of the past.
    Well, it pretty much depends, and I wouldn't say so in general. Once you have identified bottlenecks in the code - if there are bottlenecks - it usually *does* pay off to replace these by assembly language if you can. Speed improvements can reach around 100% if done right, i.e. one can indeed double the speed in certain situations. For example, even though gcc does support the vector instructions of modern processors (SSE,SSE2) the code it generates if you use them is generally pretty clumpsy, and manually tuning the code makes a lot of difference. I'm not making this up, this comes from experience with our in-house JPEG and JPEG 2000 implementations. However, saying in general that everything should be in assembly is equally wrong. Most parts of a compression program are non-critical and work wonderful in C or C++ already and improvements you can gain are pretty small.

  22. #52
    Member Karhunen's Avatar
    Join Date
    Dec 2011
    Location
    USA
    Posts
    91
    Thanks
    2
    Thanked 1 Time in 1 Post
    I think that is what I meant to say, in that one would have to know Amdahl's Law for the new routine i.e. the speedup proffered by the faster code versus the amount of time spent in the routine that benefits from it. One would have to know the performance of the old vs. new version of a program in total to know whether maintaining lower level code was $ well spent.
    Incidentally, I have some assembler for a bubble-sort somewhere, anyone interested ?

  23. #53
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    for example, 7-zip contains assembly code for CRC32 calculation that is 2x faster than compiler-generated one

  24. #54
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Alex benchmarked the current version (see his LPCB page): It decompresses 3.5x faster compared to PNG, putting it to the edge of the Pareto frontier curve.

    IZ also has a homepage now: http://imagezero.maxiom.de/

    Still waiting for feedback, not sure if anyone is actually interested in it.

  25. #55
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    872
    Thanks
    457
    Thanked 175 Times in 85 Posts
    It compresses better than PNG on my testfiles and it it really fast. I like that.
    What is planned for upcoming releases? Do you have a roadmap?

  26. #56
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    I am interested....could you please provide a brief (or maybe even detailed ) decription of the algorithm?

  27. #57
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    The best way to understand the algorithm is to read the "encodePixel" source code, lines 14-24 at http://gitorious.org/imagezero/image...ster/encoder.h

    The first part (lines 14-19) computes a transformed difference between the current pixel "pix" fetched from pointer "p" and the predicted pixel "pp". Prediction is by default computed as the arithmetic mean of (x+y)/2 and x+y-xy. Other predictors, including simpler ones and a median edge detector, can be selected via template argument "predictor". Transformations are R-=G, B-=G, then converting residuals to unsigned values using 2*abs(e)-(e<0).

    The second part (lines 21-24) writes the unsigned residual bits to the bit stream. The number of bits needed ("nl = needed length") is encoded using an 1...6 bit Huffman code. The selected table depends on the context "cx", which includes the previously needed length.

    Regarding future work, it depends on interest. It does not make sense to put work into something nobody plans to use. API design, stream format, and possible future features should reflect intended usage; having a too flexible design will adversely affect its performance.

  28. #58
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    I get that x and y are the pixels above and left from the current one...That's much simpler than I thought...Why is it stronger than PNG on some images? PNG has similar predictors and can choose them differently in different parts of an image, then LZ, then Huffman...it looks to me that it should always win.

    Also, can you give me a rough idea about how fast are individual parts of the codec (prediction and Huffman)?

    As to flexibility, I don't see why would it affect performance negatively. You can make number of colour components a template parameter and loop over it, compiler should be able to unroll a loop that has always 1-3-4 iterations. The same with component sizes, they could just be ints of different sizes. And you could add one more parameter, image dimension.

    I ask not because I intend to use it (I might, but it's unlikely) but because of research interest. I've been thinking about a fast, flexible image encoder recently.

  29. #59
    Member cfeck's Avatar
    Join Date
    Jan 2012
    Location
    Germany
    Posts
    50
    Thanks
    0
    Thanked 17 Times in 9 Posts
    Quote Originally Posted by m^2 View Post
    Why is it stronger than PNG on some images?
    LZ is known to be unsuitable for noisy data (natural photos), so it is not surprising PNG can be beaten For a starter, IZ can switch tables per pixel.

    Quote Originally Posted by m^2 View Post
    Also, can you give me a rough idea about how fast are individual parts of the codec (prediction and Huffman)?
    Huffman costs about 10%, prediction about 25% of total time. Measured by replacing variable length symbols from tables with fixed length symbols, or by replacing 3-pixel predictor with 1-pixel "predictor" respectively.

    Quote Originally Posted by m^2 View Post
    As to flexibility, I don't see why would it affect performance negatively
    Certain features would: Write overflow/read underflow handling, or ability to code in chunks (you need to save/restore state, and that will wreck the inlining).

    Regarding different number of components: IZ is not designed for single-component images. For RGBA data, the alpha channel should be handled separately (e.g. using run-length codes), so it is not a matter of simply increasing the component counter.

  30. #60
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,612
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by cfeck View Post
    LZ is known to be unsuitable for noisy data (natural photos), so it is not surprising PNG can be beaten For a starter, IZ can switch tables per pixel.
    Need to look into it.

    Quote Originally Posted by cfeck View Post
    Huffman costs about 10%, prediction about 25% of total time. Measured by replacing variable length symbols from tables with fixed length symbols, or by replacing 3-pixel predictor with 1-pixel "predictor" respectively.
    Mhm...thanks. I expected Huffman to be much more expensive....just to be sure, you measure pure CPU time, right?


    Quote Originally Posted by cfeck View Post
    Certain features would: Write overflow/read underflow handling, or ability to code in chunks (you need to save/restore state, and that will wreck the inlining).
    My I/O model is like this:
    A ring buffer split into parts:
    -output data that has been written to the output (and stays unused)
    -output data being currently written to the buffer
    -history data
    -input data being currently processed
    -data yet to be processed
    -data being read from the input
    I/O is async, done with callbacks. With this there's no explicit state saving or restoration, it's just that the processing thread has to take care of boundaries (and handling orders to read/write chunks).
    I don't see how I/O under/overflow handling would cause problems, it seems to me that it's just checking if input size is divisible by the size of a pixel (or maybe row/layer/subspace) and whether all bytes ordered to be written have been written.

    Quote Originally Posted by cfeck View Post
    Regarding different number of components: IZ is not designed for single-component images. For RGBA data, the alpha channel should be handled separately (e.g. using run-length codes), so it is not a matter of simply increasing the component counter.
    Yes, adding a separate channel would be more efficient. For my use, single-component is what matters and RGB is something extra that I may invest in if I get time; In such case abstracting dimension away is a no-extra-cost option to handle the alpha channel too.
    Last edited by m^2; 9th October 2012 at 20:46.

Page 2 of 3 FirstFirst 123 LastLast

Similar Threads

  1. Unknown Moscow - Photo Gallery
    By encode in forum The Off-Topic Lounge
    Replies: 17
    Last Post: 23rd October 2013, 14:41
  2. FLIC - a new fast lossless image compressor
    By Alexander Rhatushnyak in forum Data Compression
    Replies: 25
    Last Post: 10th January 2013, 19:46
  3. Comparison of lossless PNG compression tools
    By Surfer in forum Data Compression
    Replies: 54
    Last Post: 19th September 2011, 22:58
  4. lossless data compression
    By SLS in forum Data Compression
    Replies: 21
    Last Post: 15th March 2011, 11:35
  5. Replies: 13
    Last Post: 2nd April 2010, 23:46

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •