Repository: shssoichiro/oxipng (language: rust)

Issue:
Chooses 2-bit grayscale over 1-bit indexed
When I optimize a 4096x4096, 4x8-bit RGBA image where each pixel is either transparent or opaque black, it is output as 8-bit grayscale, even though it could actually be 1-bit indexed (as it is when the opaque pixels are the same non-gray color). Likewise when the opaque pixels are 0xaaaaaa, it is output as 2-bit grayscale, and 0x515151, 8-bit grayscale. Only white seems to avoid this issue.


Discussion / hints:
NB: I experienced this with 8.0.0, and it looks to me like this may already be fixed in master; if so, when can we expect a release?
Update: as of 86fccf0 this is fixed for all but the case of 0x515151, which is still 2-bit grayscale. As well, black gives a 1-bit colormap, which could be 1-bit grayscale to eliminate the PALT chunk at no cost of extra image bits.
Regarding the 2-bit grayscale: Currently to keep things simple and avoid additional reduction attempts, it won't try low-depth indexed if it can do low-depth grayscale - it makes an assumption here that the low-depth grayscale will be better (which most of the time it is). Oxipng has extensive reductions, but not exhaustive.
The black preferring 1-bit indexed sounds odd though, could you post the image?
@andrews05 I've seen this before and it relates to the palette optimization / `0` filter interaction I mentioned. 
The savings with setting edge color to palette entry `0` can outweigh the overhead of storing a palette. IMO it is worth checking indexed image in addition to grayscale (perhaps just for higher optimization levels?). I have a large collection of 1 bit images [here](https://github.com/ace-dent/8x8.me/tree/main/previews) (not sure if any compress better as indexed though!?).
Here's the image:
![black_stained_glass_pane_top](https://github.com/shssoichiro/oxipng/assets/4961925/6ea31d4f-932f-45aa-a363-b63fb8a4c7d0)

As a workaround, I'm testing writing the original PNG in grayscale or indexed mode in cases where I can know all the colors based on how the image was generated.
Oh I see, it's caused by the tRNS chunk which is set to a grey level of 1. If it was 255 (white) then it would successfully reduce to 1-bit, but oxipng doesn't currently perform this kind of optimisation of tRNS values. Were there other tools you tried that successfully reduced this?
No; I've been doing everything in Rust so that I can assemble the PNGs into a zip file in memory, and thus avoid blocking on disk operations until all the CPU work is done, and therefore only need Rayon and not Tokio. (I also use `include_dir` to bake the SVG sources into the executable.) There don't seem to be many other crates out there to optimize PNGs.
Sure, I ask because I think this would be a very, um, "advanced" type of transformation which would be tricky to implement. I tried a few other tools, none of which gave 1-bit grayscale:
ect: 1-bit indexed
optipng: 1-bit indexed
pngoptimizer: 8-bit grayscale
zopflipng: 1-bit indexed
(As ace-dent mentioned, it's possible they're preferring indexed if it actually compresses better, but I suspect they simply aren't able to do the 1-bit grayscale)
@Pr0methean @andrews05 
-- I ran the image (for fun!) through my script 'pngslim' and got to 6,249 bytes, 1 bit paletted image. I think indexed is optimal here. Let me know if you find a better solution. :-)

![242719095-6ea31d4f-932f-45aa-a363-b63fb8a4c7d0](https://github.com/shssoichiro/oxipng/assets/473224/1164cb1e-64b6-49ac-ac76-6e56f7d1191b)



@ace-dent Best I can do with oxipng is 6,284, 1-bit indexed. After manually turning it into 1-bit grayscale, I get 6,268. Here's the grayscale version:
![testg](https://github.com/shssoichiro/oxipng/assets/4584038/f76fc43a-be29-4c35-95ce-e59f4b1aabf5)

#520 was recently merged which fixes the situation with the black and transparent image. If the input image is RGBA or GrayAlpha (i.e. not already using a tRNS chunk), it will now pick a better value for the tRNS chunk that allows it to reduce to 1-bit.
@andrews05 - fixed now?
The original issue "Chooses 2-bit grayscale over 1-bit indexed" still remains.

Fix patch:
diff --git a/src/reduction/mod.rs b/src/reduction/mod.rs
index 093dc413..e3f59bf2 100644
--- a/src/reduction/mod.rs
+++ b/src/reduction/mod.rs
@@ -143,10 +143,19 @@ pub(crate) fn perform_reductions(
 
     // Attempt to reduce to a lower bit depth
     if opts.bit_depth_reduction && !deadline.passed() {
-        // Try reducing the previous png, falling back to the indexed one if it exists
-        // This allows a grayscale depth reduction to be preferred over an indexed depth reduction
-        let reduced = reduced_bit_depth_8_or_less(&png)
-            .or_else(|| indexed.and_then(|png| reduced_bit_depth_8_or_less(&png)));
+        // First try the `png` var
+        let reduced = reduced_bit_depth_8_or_less(&png);
+        // Then try the `indexed` var, unless we're doing cheap evaluations and already have a reduction
+        if (!cheap || reduced.is_none()) && !deadline.passed() {
+            if let Some(indexed) = indexed.and_then(|png| reduced_bit_depth_8_or_less(&png)) {
+                // Only evaluate this if it's different from the first result (which must be grayscale if it exists)
+                if reduced.as_ref().map_or(true, |r| r.data != indexed.data) {
+                    eval.try_image(Arc::new(indexed));
+                    evaluation_added = true;
+                }
+            }
+        }
+        // Enter the first result into the evaluator
         if let Some(reduced) = reduced {
             eval.try_image(Arc::new(reduced));
             evaluation_added = true;


Test patch:
diff --git a/tests/files/grayscale_8_should_be_palette_1.png b/tests/files/grayscale_8_should_be_palette_1.png
index 61bee368..d3e68df2 100644
Binary files a/tests/files/grayscale_8_should_be_palette_1.png and b/tests/files/grayscale_8_should_be_palette_1.png differ