CorePNG - New LossLess codec

[MfA]

LOCO-I in it's original form wont work all that well for anime ... so if anyone feels adventurous and wants to host a LOCO-I based codec on CoreCodec Id call it CorePURE or something, in the end it will probably be pretty heavily modified anyway.

It would be very little work to take one of the existing open source JPEG-LS implementations (there are plenty, and JPEG-LS <=> LOCO-I) and hack it into CorePNG.

[General Lee D. Mented]

Originally posted by MfA
GLDM, why not try out the hilbert scan in FFV1? (I assume you are using that scan, it is generally considered to be the best.) If that works then it wouldnt be too hard to experiment with wavelets too in the same framework, CABAC is a lot speedier than BWT ...

A possible explanation of why raster order scanning could work better can be found here.

Actually WARP's scanmatrix was using a hilbert or peano scan (websites don't seem to agree often on which is which), but after some research I found that a recursive quadrant scan like hilbert but without the rotations should work better in most cases, because the lack of rotation means a higher probability of getting matching sequences of symbols. It's also much simpler to code, especially as the number of dimensions of the scan space increases (not an issue here but believe me doing a 3D hilbert for a hologram is annoying to write, even the 2D one was irritating).

So, the scan I gave jccston was this quadrantscan, which is basicly a rotationless hilbert. He reported that zipping a bmp usually produced better compession using my scan, but a png of both images usually produced better compression on the standard (raster) scan. Which leads me to suspect that png has some optimizations that take things like horizontal resolution into account before calling zlib.

[MfA]

Which filter-type does CorePNG use?

[Marc FD]

huhu a new lossless codec. fun because i started again to play with that a few days ago ^^.

and to be honest i don't see how zlib compression on images could be _that_ good ^^;;

seems there is a yv12 version, i eager to try it out. ^^

we'll soon see if CorePNG outperform both a unrestricted huffyuv in yv12 and a little guy's (me) poor-man's compression lossless stuff =)

EDIT : CoreCodec.org seems down here in france T_T... could s.o. attach the last working yv12 version please :)

[jcsston]

Originally posted by MfA
Which filter-type does CorePNG use?

It uses all of them, I believe libpng adaptively chooses which to use depending on the first row of the image.
You can choose in the codec options which filters will be enabled and used or if any at all will be used.

and to be honest i don't see how zlib compression on images could be _that_ good ^^;;

zlib compression is only half of PNG, a good deal of the compression comes from the filters too.

CoreCodec.org seems down here in france T_T... could s.o. attach the last working yv12 version please

I put up a mirror here until cc.org is back up and running.

[MfA]

Filters 2-4 will access irrelevant values with the hilbert scan right?

[Marc FD]

hum, isn't impressive in yv12.

some % under vble & huffyuv (3-5%), but much more than 10x slower ^^;

but the test clip i use for lossless coding is a very hard one, even video codecs don't compress it much ^^.

[TheXung]

Originally posted by MfA
LOCO-I in it's original form wont work all that well for anime ... so if anyone feels adventurous and wants to host a LOCO-I based codec on CoreCodec Id call it CorePURE or something, in the end it will probably be pretty heavily modified anyway.

I dunno about that. Some of my testing shows that on keyframes, JPEG-LS wins hands down:

first number is the jpeg-ls, second is the png

frame from akira:
226k/240k

frames from simpsons:
262k/291k
343k/399k
260k/296k

though the sources for the test were from divx encodes so there is artifacting in there. And this is using adaptive filtering for png

[MfA]

With synthetic sources with large evenly coloured surfaces JPEG-LS is often outperformed, I guess there usually is too much noise for that to be an issue though.

[BoNz1]

Wow, what a coincidence. It appears that JPEG-LS was developed at my university. If you like I may be able to track down the people who wrote this and direct them to you if you are interested in writting an encoder.

[General Lee D. Mented]

Originally posted by MfA
Filters 2-4 will access irrelevant values with the hilbert scan right?

2 and 4 should be irrelevant, as the vertical construction of the image is destroyed. However, I'd expect filters 1 and 3 to perform better. I tried enabling and disabling filters and even using none, but still always got bad results with the quadrant scan.

Here's a couple examples to play with if you like:

http://www.gldm.net/orig.png
http://www.gldm.net/quadrant.png

and the function, if anyone wants to play with that too:

void QuadrantScan(int** order, int hmin, int vmin, 
		 int hmax, int vmax, int size, int &current)
{

	int hmintemp, vmintemp, hmaxtemp, vmaxtemp;

	if (size == 1) // 1x1 array
		if(order[vmin][hmin] != 0)
		{
			order[vmin][hmin] = current;  // store order seen
			current++;
		}
		else
			; // don't store if marked out
	else{
		size /= 2;

		hmintemp = hmin;
		vmintemp = vmin;
		hmaxtemp = hmax - size;
		vmaxtemp = vmax - size;
		QuadrantScan(order, hmintemp, vmintemp,
			    hmaxtemp, vmaxtemp, size, current);

		hmintemp = hmin;
		vmintemp = vmin + size;
		hmaxtemp = hmax - size;
		vmaxtemp = vmax;
		QuadrantScan(order, hmintemp, vmintemp,
			    hmaxtemp, vmaxtemp, size, current);

		hmintemp = hmin + size;
		vmintemp = vmin + size;
		hmaxtemp = hmax;
		vmaxtemp = vmax;
		QuadrantScan(order, hmintemp, vmintemp,
			    hmaxtemp, vmaxtemp, size, current);

		hmintemp = hmin + size;
		vmintemp = vmin;
		hmaxtemp = hmax;
		vmaxtemp = vmax - size;
		QuadrantScan(order, hmintemp, vmintemp,
			    hmaxtemp, vmaxtemp, size, current);

	}

	return;
}

How to use it:
int** order is a 2D array of ints initialized to 1s used as a lookup table, to know what linear order a given 2D pixel falls in. Note that the array must be SQUARE and POWER of 2. Note int size is the length of the SIDE of the square array, not is entire area. If you need to handle cases with non-square areas or anything that doesn't fit perfect, load 1s in the area you plan to use, and 0s in the area you want masked out. For example, on a 512x512 array, if your image is 512x384, fill the first 384 lines with 1s, and the last 128 with 0s to generate a proper lookup table. This works for any pixel mask including random.

Once the table is made, forward transform looks like this:

destination[order[i][j]] = source[i][j];

reverse transform:

destination[i][j] = source[order[i][j]];

Note the 2D->1D translation by the table. If you want 2D->2D or some other combintation I'll leave the / and % conversion of 2D coordinates to and from a linear index for your own coding fun.

[TheXung]

Originally posted by MfA
With synthetic sources with large evenly coloured surfaces JPEG-LS is often outperformed, I guess there usually is too much noise for that to be an issue though.

I've yet to implement PNG but what exactly does it have over JPEG-LS that makes it so good for large evenly coloured surfaces? I mean, JPEG-LS does have a run-mode that should do just that (which by the way, I also haven't found code for in the LOCO 0.4 codec).


GLDM, that sure is a fancy scan you got going. However wouldn't a scan that makes objects only a pixel tall have a negative effect on prediction accuracy?

[General Lee D. Mented]

Originally posted by TheXung
I've yet to implement PNG but what exactly does it have over JPEG-LS that makes it so good for large evenly coloured surfaces? I mean, JPEG-LS does have a run-mode that should do just that (which by the way, I also haven't found code for in the LOCO 0.4 codec).


GLDM, that sure is a fancy scan you got going. However wouldn't a scan that makes objects only a pixel tall have a negative effect on prediction accuracy?

I'm not sure, there might be something in that paper MFA linked to. I looked through it, but didn't understand alot of the math parts.

The scan looks fancy but it's really a simple idea. You just take a square, and divide it into 4 parts. Then divide each of those into 4 parts, until your squares are only 1 pixel big. Then as the recursive functions return, they each assign a square a number in the order that they return. The hilbert and peano space-filling curves do the same, except in their scan each subdivision can be a rotation (90/-90/180 degrees) of the order of the caller. Mine always uses the same order at every level so it's more likely to produce the same results for similar features in the image.

What this does is produce a scan order that gives you a 1x1 pixel, surrounded by its neighbors that compose a 2x2 square, surrounded by 3 other 2x2s to make a 4x4, then an 8x8, 16x16, etc. This way, when you compress the resulting stream of pixels, large areas of similar color should be all next to each other in a line. Which I would think would be easier to compress but apparently not.

[Marc FD]

finished my stuff. it's funny because it looks a lot like LOCO-I, (well it's less complex) but i didn't have read anything about LOCO when i designed the algo. i had only tested felics (which behaved bad but gave me good ideas)

tested in yv12, it compress more than the corePNG codec (about -10%) and is 2.5x faster. (iframes only coding)

still plain C and lazily optimised.

i'll do some asm-ing, to see how fast it could be ^^.

btw, sorry if you feel i hijack the thread, i'd like to keep clear it's not my intention at all, just the discution seemed to turn around lossless coding so ... ^^

[zettai]

MarC, can you please include RGB24, 32 and YUY2 modes as well? It's great having a lossless codec but if you are developing video in RGB it's no fun having to have a lossy colour conversion

[MfA]

I think the dictionary based coding is better at representing reoccuring long runs of the same color. A 2D oriented RLE can help here.

For truly synthetic images there are also dither patterns which dictionary based coding can deal better with, and gradients which can be perfectly predicted. Having long strings of perfectly predicted pixels isnt a good case for JPEG-LS, if you wanted to support near lossless coding you would really want to fix that too.

GLDM, if you do that to the pattern it is no longer a continuous curve ... I dont think that is a good idea.

[General Lee D. Mented]

Originally posted by MfA
I think the dictionary based coding is better at representing reoccuring long runs of the same color. A 2D oriented RLE can help here.

For truly synthetic images there are also dither patterns which dictionary based coding can deal better with, and gradients which can be perfectly predicted. Having long strings of perfectly predicted pixels isnt a good case for JPEG-LS, if you wanted to support near lossless coding you would really want to fix that too.

GLDM, if you do that to the pattern it is no longer a continuous curve ... I dont think that is a good idea.

The continuous curve is a nice mathematical concept, but when applied to a 2D field of discrete pixels it's kinda pointless to maintain continuity since the pixels are discrete anyway. The main reason hilbert is used in scans is because of how it converts 2D locality to 1D locality. i.e. the scan traverses pixels in an ever widening area without jumping to a distant pixel like a scanline does at the end, and I preserved that property. I mean sure if it was continuous the last pixel of the current block would be next to the first pixel of the subsequent block, but I don't think that's going to produce a significant benefit. The only case where it does is when the trans-block boundary of the level you're on is predictable in the direction the curve is moving at that time. I think you'll lose more in efficieny because your scan order of a given block is constantly rotating, so if you had say, an 8x8 macroblock with 2 identical 4 pixel objects it you won't usually get the same pixel order and hence it won't be predictable.

There's situations in which either algorithm has advantages and disadvantages.

[esby]

I'm having trouble to access the website associated with the codec.

Can someone confirme if the site is down until further notice,
or if it should be back up in time or somewhere else?
(--> how i get the codec )

esby

[Atamido]

Originally posted by General Lee D. Mented
Here's a couple examples to play with if you like:

http://www.gldm.net/orig.png
http://www.gldm.net/quadrant.png

I honestly would have suspected that PNG would have compressed the quadrant picture better because of the way that colors are isolated to lines, but apparently my understanding of it is to short. This picture actually compresses far worse if turned verticaly, but this is not always the case. I tried to get jcsston to add an option where the image would be rotated 90 degrees and recompressed to see if it got any smaller, but he didn't want to. I guess increasing encoding/decoding time for such a marginal improvement in encoding size wasn't a priority.

[jcsston]

Originally posted by esby
I'm having trouble to access the website associated with the codec.

Can someone confirme if the site is down until further notice,
or if it should be back up in time or somewhere else?
(--> how i get the codec )

esby

I put up a mirror here until corecodec.org is back up and running.

I guess increasing encoding/decoding time for such a marginal improvement in encoding size wasn't a priority.

In my tests it didn't make any difference in size with rotating.