quantizer about upng.js HOT 23 CLOSED

Guys, clearly you are both smart. Let's drop the ego and work together for the best solution. No one wins in an argument. Keep up the great work!

from upng.js.

Hi, are you sure you are using the latest source code, which I uploaded to GitHub five days ago?

When finding the closest color for each palette pixel, there is a fast and a slow (exact) method. The exact is used when the input is smaller than 20 MB.

from upng.js.

@photopea Seems so, I pulled the code at commit cb463cb. There is one later thought, which lists no changes.

When finding the closest color for each palette pixel, there is a fast and a slow (exact) method. The exact is used when the input is smaller than 20 MB.

Yes I saw that branching, tbh - it looks weird to me, not really backed up by any metrics beside calc penalty for "image being big"?

from upng.js.

Hi, regarding the palette smaller than 512: there was a bug when computing the highest eigenvector of a matrix. It happened for "regular" inputs such as yours.

I think I fixed it. Could you test a new version?

from upng.js.

Thanks, it works. 👍

from upng.js.

And what about other problems? Could you check if they are fixed now?

from upng.js.

There are not really issues left beside the npm package update.

About finding the nearest color:
I willl stick with my cubic partitions, as it is as fast as your fast approximation for images > 20 MB, but gives closer colors as in your exact search.

from upng.js.

I am not a user of npm and I usually dont like to learn how to use new native programs. If you put it on NPM, I can provide a link in our README.

I don't know what you mean by cubic partitions. If the palette is given, UPNG.js should find the closest palette color to each pixel, so when you say you find even closer colors, it does not make any sense to me :/

from upng.js.

... UPNG.js should find the closest palette color to each pixel ...

Your fast approximation does not imho, it cuts the search only to visited subtrees missing closer colors on neighboring paths.

from upng.js.

@jerch Yes, that is true, our fast method does not find the closest color.

So your method is faster than our fast method and finds closer colors?

from upng.js.

Yes, it is basically as fast as your fast one, but finds closer matches as the slower one.

from upng.js.

Interesting. Could you describe your method? Are you sure it works well with all kinds of palettes (images)? What is the time complexity of finding a color?

from upng.js.

@photopea Sure. It is basically spatial partitioning into 16x16x16 cubes of the RGB room (thus 4096 cubes). Every cube maps to 2 palette color "clouds" - first one containing all palette colors within the outer cube sphere or (nearest if empty), second one within the sphere of r=42 (~ the outer sphere of 4 cubes). The mappings are created once after palette creation.
For color matching the cube key is simply derived from the higher 4 color channel bits, on cube level I simply do a brute force euclidian distance test against the first sphere points, and if the distance of the tested color to the cube center is bigger than my certainty range (r=8), I test also against the second sphere colors.

So basically this is a cubic approximation of a spherical problem with 2 certainty levels. The error rate can be changed by changing the radius of both spheres. The values I ended up with are about as fast as your fast approx., but with error rates below 1% typically. I also tested other cube resolutions, but found the 16x16x16 cubes as sweep spot for well distributed palettes with 64 to 256 colors.

Runtime behavior:

• cube construction with color mappings: ~20 ms (thats fairly stable even for different palette sizes, seems the cube amount is the dominating factor (it is ~80 ms for 32768 cubes of 8x8x8 size, or <5ms for 512 cubes of 32x32x32)
• color matching:
  • cube key derivation in O(1)
  • brute force euclidian distance: O (n) for n colors in the inner sphere, for well distributed palette colors O(1) (cube maps only to 1 color)

The speed benefit comes from the fact, that the partitioning cuts off most palette colors to be tested, roughly by 4096 (not quite that much as the sphere covers more than the cube itself). Furthermore most cubes will only hold one color, which makes the match for colors within those cubes in O(1). And here is the catch - for lousy distributed palettes the algo will fall short, the worst case is all palette colors being populated into one cube - boom, again full ED testing. To avoid that, one can introduce subcubes, if the color count gets too high for a single cube. Note that this somewhat forms an octree, and yes I basically took the partitioning idea from my octree experiments. Still the certainty areas of the spherical search around the cubes is abit tricky.

Edit: Forgot one thing - a cube will always map to at least one palette color as the nearest. This is an important shortcut to avoid expensive neighboring cube searches for cubes, that have no palette color within one of the spheres. The idea here is to make the second sphere big enough, that a far distance nearest color would not change within the cube length of 16 (or if it changes, the distance would still be very large, thus the match gets not much "better").

from upng.js.

What you describe is usually called a "Grid structure". It works well, if you are sure, that the samples are "uniformly distributed", without many "clusters" with a high density.

If your are sure that your palettes are always so nice, you can keep using it. However, I am afraid to use such method, as I think palettes are rarely that "nice" for classic images. In the worst case, you would have O(n) for every search.

If you decide to switch to octrees (for either exact or approximate search), I don't think it would be any faster than the methods that are currently in UPNG.js .

from upng.js.

If your are sure that your palettes are always so nice, you can keep using it. However, I am afraid to use such method, as I think palettes are rarely that "nice" for classic images. In the worst case, you would have O(n) for every search.

I disagree, it is not a matter of nice palette color distribution, but how far one goes into subcubes if the higher level cube still holds too many colors. If you restrict "colors per cube" to only 4 you would have to go two bits deeper only. The benefit compared to octrees is the fact, that such a tree has a higher base than 2 (in one dimension), thus can faster exclude uninteresting parts of the tree. The search is like O(log2 n) vs. O(logx n) for x >> 2. Note that the higher tree branching does not negatively impact runtime at color matching phase, as the cube key can always be derived in O(1).
Ofc higher cube resolution impacts the construction phase - it is trading color matching runtime for initial runtime and space (but this happens only once). And the fact, that any cube always contains a nearest color cuts the expensive neighboring checks/search, which are always needed otherwise to find the real closest match.

Note that for exact match your algo also has a worst case of O(n), if the tree happens to be quite unbalanced or the neighboring search ends up including all nodes (given you do proper ascending neighboring checks).

Edit: Imho plain octrees will perform worse than my "4096-tree" above, but still would show a benefit compared to direct kd tree usage for these reasons:

• octrees guarantee a depth of 8 levels for the RGB room, where kd trees have to descend deeper for colors > 256
• a fixed octree does not aim for balancing, where a kd tree should be balanced to keep things in log, but kd tree rebalancing is expensive
• for the true NN result the neighboring search can get really expensive in a kd tree - while the descending nicely works in log (if balanced), the variable plane shapes can cause the need to expand the search to almost n palette colors again (during backtracking/ascending), this also would happen in a straight octree, that does not include "shortcuts" to far away NN points, but again the cube index derivation directly from the color allows to "jump" over there without exhaustive neighbor subtree walking.

from upng.js.

It is hard for me to argue with you, as I can not see your implementation.

Could you test your method on at least 30 different photographs? Is it always faster than our fast method? Or if it is equally fast, does it always find closer neighbours (i.e. the total error of the image is lower)?

from upng.js.

Sorry, this is getting redundant and I dont know how to answer to that beside saying, that everything is already stated above (including a pointer to my simplified impl). Whether you want to try that (or a modified version with better skewed color distribution support) out for your needs is up to you, I am not in the position to try to "convince" you.

from upng.js.

Ok, I still think, that our implementation works better than yours in practical cases. I will close it now.

But thanks for letting us know about the bug with finding a 512 item palette.

from upng.js.

Ok, I still think, that our implementation works better than yours in practical cases.

Yes please have it your way, although runtime and accuracy speaks otherwise.

from upng.js.

You never mentioned on how many and what kind of images (palettes) you tested it on. I think you can not make such claims without testing it properly on many inputs.

from upng.js.

A test with several pictures does not prove anything, just math/algo thoughts can. It has been shown that an octree with local spherical search can find the nearest in O(log log n), which is almost constant. Plus it being fixed, thus easy to derive the keys, which cuts down the work for a single step by a constant factor. Now do the maths - with a higher branching factor, the log gets a higher base. And so on...
I know that O(log1000 log1000 (n/1000)) is still closer to O(log n) than anything else, but those shifts in constants is what makes r-trees and other weird spatial tree concepts showing an advantage over more general concepts like a "dimension-rotating binary tree".

But if you insist - I tested this with ~50 images, from real pictures, greyscale with/without color tint (sepia) to hard to digest graphics with gradients. Btw the hardest one in terms of wrong colors was my palette image with ~12% error rate compared to a full NN search. For most pictures the error rate was far below 1%, not like your fast approx with 10 to 30% for my set of pictures.

from upng.js.

@jerch Do you think you could extend your grid method to make it find the closest color? That would be really useful.

from upng.js.

@photopea Yes, I think that would be possible with true voronoi tessellation during construction, will see if thats still ok in terms of construction runtime.

from upng.js.