color divergence in sixel with fewer colors than color registers

[dankamongmen]

with quantanal improved in #2502, we're now seeing divergence on a more complex, but still simple, image:

[schwarzgerat](0) $ ./quantanal ../data/chunli23.png
analyzing ../data/chunli23.png...
 source pixels: 99x46
 rendered: 99x46 18216B
 control sequence: 3134 bytes (17.2%)
 00004554 pixels analyzed Δr 318498 Δg 3546 Δb 3600
 Colors: 17 vs 27
 4554px Δr 318498 (69.9) Δg 3546 (0.779) Δb 3600 (0.791)
 avg diff per pixel: 71.5
done with ../data/chunli23.png.
[schwarzgerat](0) $

we're for some reason using 10 more colors, and missing by a wide 71.5 per. adding NOINTERPOLATION makes things worse:

[schwarzgerat](0) $ ./quantanal ../data/chunli23.png
analyzing ../data/chunli23.png...
 source pixels: 99x46
 rendered: 99x46 18216B
 control sequence: 3134 bytes (17.2%)
 00004554 pixels analyzed Δr 315107 Δg 5968 Δb 3489
 Colors: 17 vs 97
 4554px Δr 315107 (69.2) Δg 5968 (1.31) Δb 3489 (0.766)
 avg diff per pixel: 71.3
done with ../data/chunli23.png.
[schwarzgerat](0) $

meanwhile, on another, we drastically reduce the number of colors:

[schwarzgerat](0) $ ./quantanal ../data/worldmap.png
analyzing ../data/worldmap.png...
 source pixels: 475x860
 rendered: 475x860 1634000B
 control sequence: 130695 bytes (7.998%)
 00408500 pixels analyzed Δr 828526 Δg 899641 Δb 877151
 Colors: 233 vs 43
 408500px Δr 828526 (2.03) Δg 899641 (2.2) Δb 877151 (2.15)
 avg diff per pixel: 6.38
done with ../data/worldmap.png.
[schwarzgerat](0) $

[dankamongmen]

even more oddly, i only see 11 colors in chunli23.png, fewer than we count in quantanal. ahhh, perhaps becuase of the initial reduction from rgb to sixel space? we really oughtn't be doing that so early--it loses precision!

[dankamongmen]

yep that's why

[dankamongmen]

[0->10] hi: 18 6 0 lo: 18 6 0
[10->8] hi: 94 75 62 lo: 94 75 62
[10->8] hi: 94 87 69 lo: 94 75 62
[11->4] hi: 94 94 94 lo: 94 94 94
[12->12] hi: 18 40 72 lo: 18 40 72
[13->13] hi: 43 18 9 lo: 43 18 9
[14->14] hi: 94 87 69 lo: 94 87 69
[15->15] hi: 31 12 3 lo: 31 12 3
[1->9] hi: 0 21 53 lo: 0 21 53
[2->0] hi: 0 31 56 lo: 0 31 56
[2->0] hi: 18 40 72 lo: 0 31 56
[3->3] hi: 25 6 0 lo: 25 6 0
[3->3] hi: 31 12 3 lo: 25 6 0
[3->3] hi: 43 18 9 lo: 25 6 0
[4->11] hi: 43 28 9 lo: 43 28 9
[5->2] hi: 37 56 81 lo: 37 56 81
[6->5] hi: 56 28 15 lo: 56 28 15
[7->6] hi: 69 40 28 lo: 69 40 28
[8->1] hi: 59 72 90 lo: 59 72 90
[9->7] hi: 84 53 43 lo: 84 53 43
FOUND COLOR 0 0 25 50
FOUND COLOR 10 0 0 0
FOUND COLOR 11 25 25 0
FOUND COLOR 1 50 50 75
FOUND COLOR 2 25 50 75
FOUND COLOR 3 25 0 0
FOUND COLOR 4 75 75 75
FOUND COLOR 5 50 25 0
FOUND COLOR 6 50 25 25
FOUND COLOR 7 75 50 25
FOUND COLOR 8 75 75 50
FOUND COLOR 9 0 0 50

those deets entries look a bit askance, though maybe i'm forgetting something...

[dankamongmen]

yeah these hi/lo values are fubar:

FOUND COLOR 11 25 25 0
FOUND COLOR 11 25 25 0
FOUND COLOR 11 25 25 0
FOUND COLOR 11 25 25 0
000 206 hi 18/40/72 lo 0/31/56
001 69 hi 59/72/90 lo 59/72/90
002 78 hi 37/56/81 lo 37/56/81
003 343 hi 43/18/9 lo 25/6/0
004 72 hi 94/94/94 lo 94/94/94
005 187 hi 56/28/15 lo 56/28/15
006 155 hi 69/40/28 lo 69/40/28
007 124 hi 84/53/43 lo 84/53/43
008 178 hi 94/87/69 lo 94/75/62
009 83 hi 0/21/53 lo 0/21/53
010 35 hi 18/6/0 lo 18/6/0
011 226 hi 43/28/9 lo 43/28/9

[dankamongmen]

ok the 56 is floor(0x90100/255). so that's sixel space. likewise floor(0x50100/255) == 31...though how we're ending up with different hi vs lo remains confusing.

[dankamongmen]

so is this all due to our preclumping, where we're applying that large mask?

FOUND COLOR 0 0 25 50 (orig 0xff905000)
000 4 hi 0/31/56 lo 0/31/56
FOUND COLOR 0 0 25 50 (orig 0xffb86830)
000 5 hi 18/40/72 lo 0/31/56

differences of 40, 24, and 48. we start with a mask of 0xc0, aka two bits, aka enclumpenings of 64, so yeah, that's wide enough to take them. still, if we're storing with full precision, we ought be able to get them out losslessly. so it looks like that's where our breakage is.

[dankamongmen]

yeah we're always averaging in refine_color(), stupid stupid stupid.

[dankamongmen]

definite bug in extract_color_table(), argh!

[dankamongmen]

alright, i think i've found one trick that wins us back a good bit of quality, testing for performance regression...

[dankamongmen]

yeah that seems to improve the visual a decent bit, though our average error changes very little...

[dankamongmen]

alright, bold new idea for the relaxation algorithm: initially, we take a 323 MSB liftup from the channels. use that as a key into a 256-element table. now the full extraction is O(1) per pixel (currently O(lgn)), at the cost of a possibly sparse color table. but use that same sparsity as a topological guide to our relaxation, relying on some locality. if need be at the end, compress the table down -- this can be delayed until encoding time, and done on the fly. this ought be a very substantial improvement, i think.

[ghost]

I would really like to port your encoder sometime to Java for the vastly superior speed and quality over other sixel encoders. Do you have a planned milestone spot in the future that would be a good place to start from?

[dankamongmen]

progress thus far indicates about a 50% cut in sixel quantization runtime, fuckin' sweet

[dankamongmen]

I would really like to port your encoder sometime to Java for the vastly superior speed and quality over other sixel encoders. Do you have a planned milestone spot in the future that would be a good place to start from?

righjt now the encoder's no good =] i'm bringing it up to at least libsixel territory now. libsixel uses straight-up maxmedian cut (as you do, iirc), of which i'm not a tremendous fan. i think octrees are likely the way to go, though i've been playing around with kohonen neural networks. my deep dislike for statistical/ML methods means i probably won't go that way, either. right now i'm experimenting with static octree preclustering + my own "relaxation" approach, and it is showing very positive results. #1452 then suggests getting rid of the final iteration of relaxation, which i think is a great idea, but we'll see.

i'm down to a bit under 50% of my old rendering time with just the octree preclustering, but i've got a bug in there for images that are fewer than 256 colors. i should have it knocked out tonight, hopefully.

on the left is current algorithm, running in .9s±.2s when coming from page cache. on the right is the new algorithm, running in .5s±.1s when coming from page cache.

[dankamongmen]

(of that .5s, about .35s is due to writing out to the terminal, and the terminal rendering, so we're talking about .4s vs .1s for actual quantization, so a bit more speedup than advertised)

[dankamongmen]

[dankamongmen]

ok, i think i just got that bug resolved. things are looking very good...

[dankamongmen]

so we're seeing equal quality on most images now, while preserving nice speed pickups....except for notcursesIII.mov, on which we seem noticeably slower and crappier.

[dankamongmen]

likewise we're definitely slower and crappier on samoa.avi. very strange that this correlates with video, though probably not informative. huh.

[dankamongmen]

new algorithm:

[schwarzgerat](0) $ time ./ncplayer ../data/chunli* -t0 -q

real    0m7.650s
user    0m5.349s
sys     0m0.228s
[schwarzgerat](0) $ 

old:

[schwarzgerat](0) $ time ncplayer ../data/chunli* -t0 -q

real    0m10.964s
user    0m5.285s
sys     0m0.325s
[schwarzgerat](0) $ 

but then on worldmap.png, old beats new (and looks better);

[schwarzgerat](0) $ time ncplayer ../data/worldmap.png -t0 -q

real    0m0.241s
user    0m0.180s
sys     0m0.012s
[schwarzgerat](0) $ time ncplayer ../data/worldmap.png -t0 -q

real    0m0.244s
user    0m0.175s
sys     0m0.020s
[schwarzgerat](0) $

new:

[schwarzgerat](0) $ time ./ncplayer ../data/worldmap.png -t0 -q

real    0m0.267s
user    0m0.197s
sys     0m0.012s
[schwarzgerat](0) $ time ./ncplayer ../data/worldmap.png -t0 -q

real    0m0.269s
user    0m0.203s
sys     0m0.008s
[schwarzgerat](0) $

new pastes old on AllRGB images:

[schwarzgerat](0) $ time ./ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m6.671s
user    0m5.923s
sys     0m0.392s
[schwarzgerat](0) $ time ./ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m6.681s
user    0m5.955s
sys     0m0.348s
[schwarzgerat](0) $ time ./ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m6.712s
user    0m5.945s
sys     0m0.379s
[schwarzgerat](0) $ 

old:

[schwarzgerat](0) $ time ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m7.575s
user    0m6.826s
sys     0m0.372s
[schwarzgerat](0) $ time ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m7.507s
user    0m6.821s
sys     0m0.391s
[schwarzgerat](0) $ time ncplayer /media/chungus/images/allrgb/* -t0 -q

real    0m7.502s
user    0m6.827s
sys     0m0.398s
[schwarzgerat](0) $ 

soooooooooo AllRGB is going to fill up the color table on the initial pass, causing the second pass to abort immediately (it's also going to be dominated by writing/processing time, as they're 64MB RGB). meanwhile, very few colors are going to likewise cause very little second phase, since most will get slotted out to different octets in the first phase. so that points to our first phase being good, and our second phase being ass. it doesn't explain why we look shittier in that case, though. maybe a remaining bug in the second phase?

well, we ought be able to cut a chunk off that ass with the #1452 proposal. let's apply that and see where we get. if that doesn't win in all cases, i think we move to an all-octree solution, and call it a day.

[dankamongmen]

but yeah the original motivation for this bug, the divergence, is eliminated.

[dankamongmen]

[dankamongmen]

alright, we're now functional on images with more leaves than color registers, though it's a first-order merge and tends to look like shit. that ends functional necessities; i'm going to clean out the diagnostics and start some fine-tuning and numeric comparison. i expect to merge this tonight.

[dankamongmen]

here's some crude notcurses-demo data:

xterm 80x61 (880x1403)

new

             runtime│ frames│output(B)│    FPS│%r│%a│%w│TheoFPS║                
══╤════════╤════════╪═══════╪═════════╪═══════╪══╪══╪══╪═══════╣                
 1│   intro│   4.14s│    210│   3.79Mi│   50.7│ 6│ 1│47│  90.00║                
 2│    xray│  15.54s│    217│  14.91Mi│   14.0│ 1│ 0│19│  65.65║                
 3│     box│   6.88s│    100│   9.88Mi│   14.5│ 3│ 0│50│  26.56║                
 4│  keller│  13.72s│    866│   3.45Mi│   63.1│ 7│ 2│ 7│ 356.05║                
 5│    view│  22.05s│    962│  54.07Mi│   43.6│ 3│ 1│37│ 102.58║                
══╧════════╧════════╪═══════╪═════════╪═══════╧══╧══╧══╧═══════╝                
              62.34s│   2355│  86.11Mi│                 
             runtime│ frames│output(B)│    FPS│%r│%a│%w│TheoFPS║                
══╤════════╤════════╪═══════╪═════════╪═══════╪══╪══╪══╪═══════╣                
 1│   intro│   3.96s│    321│   6.71Mi│   81.2│ 9│ 2│39│ 156.45║                
 2│    xray│  15.48s│    233│  15.48Mi│   15.1│ 1│ 0│16│  85.47║                
 3│     box│   6.57s│    100│   9.36Mi│   15.2│ 5│ 0│46│  29.05║                
 4│  keller│  13.71s│    878│   3.46Mi│   64.1│ 6│ 2│ 7│ 385.39║                
 5│    view│  21.21s│    963│  54.08Mi│   45.4│ 3│ 1│36│ 110.45║                
══╧════════╧════════╪═══════╪═════════╪═══════╧══╧══╧══╧═══════╝                
              60.92s│   2495│  89.09Mi│                       

current

             runtime│ frames│output(B)│    FPS│%r│%a│%w│TheoFPS║                
══╤════════╤════════╪═══════╪═════════╪═══════╪══╪══╪══╪═══════╣                
 1│   intro│   4.18s│    327│   7.87Mi│   78.3│ 8│ 2│42│ 145.51║                
 2│    xray│  15.52s│    207│  14.80Mi│   13.3│ 0│ 0│17│  69.76║                
 3│     box│   7.07s│    100│  12.06Mi│   14.1│ 6│ 0│48│  25.60║                
 4│  keller│  13.63s│    864│   3.43Mi│   63.4│ 7│ 2│ 5│ 407.31║                
 5│    view│  39.62s│    961│  73.55Mi│   24.3│ 1│ 0│18│ 114.95║                
══╧════════╧════════╪═══════╪═════════╪═══════╧══╧══╧══╧═══════╝                
              80.01s│   2459│ 111.70Mi│               
             runtime│ frames│output(B)│    FPS│%r│%a│%w│TheoFPS║                
══╤════════╤════════╪═══════╪═════════╪═══════╪══╪══╪══╪═══════╣                
 1│   intro│   4.13s│    317│   7.71Mi│   76.7│ 8│ 2│42│ 143.30║                
 2│    xray│  15.53s│    206│  15.01Mi│   13.3│ 0│ 0│18│  68.25║                
 3│     box│   6.63s│    100│  10.13Mi│   15.1│ 6│ 0│45│  28.70║                
 4│  keller│  13.62s│    864│   3.43Mi│   63.5│ 7│ 2│ 5│ 404.63║                
 5│    view│  39.33s│    963│  73.55Mi│   24.5│ 1│ 0│18│ 117.42║                
══╧════════╧════════╪═══════╪═════════╪═══════╧══╧══╧══╧═══════╝                
              79.24s│   2450│ 109.82Mi│                        

contour is kinda unstable right now, and i'm not smart enough to copy-and-paste from xwayland into chrome on x so we only have xterm numbers. but alright! the only one where we would expect to see big timing changes is view, where indeed we kick it in the balls for a healthy 50% reduction in runtime. we'd expect some total frame count changes in xray, where time is constant and we drop frames, and we indeed have about a 10% gain there.

alright, this is looking good, performance-wise! let's get some detailed info from quantsixel.

[dankamongmen]

(from the same runs as above)

current

Bitmap emits:elides: 1420:306 (17.73%) 66.70MiB (59.70%) SuM: 0 (0.00%)
Bitmap emits:elides: 1376:299 (17.85%) 65.00MiB (59.18%) SuM: 0 (0.00%)

new

Bitmap emits:elides: 1444:304 (17.39%) 44.32MiB (49.74%) SuM: 0 (0.00%)

so it looks like we're emitting significantly smaller bitmaps, which surprises me. we'll want to look into that and determine why, i think. i mean, it's a good effect, but it needs to come from a righteous cause.

[dankamongmen]

alright, so we see a slight increase in accuracy on chunli23.png:

current

analyzing ../data/chunli23.png...
 source pixels: 99x46 rendered: 99x46 18216B
 control sequence: 3133 bytes (17.2%)
 00004554 pixels analyzed Δr 319236 Δg 2799 Δb 2877
 Colors: 17 vs 17
 4554px Δr 319236 (70.1) Δg 2799 (0.615) Δb 2877 (0.632)
 avg diff per pixel: 71.3
done with ../data/chunli23.png in 81.068ms.

new

analyzing ../data/chunli23.png...
 source pixels: 99x46 rendered: 99x46 18216B
 control sequence: 3116 bytes (17.11%)
 00004554 pixels analyzed Δr 317209 Δg 1271 Δb 1626
 Colors: 17 vs 17
 4554px Δr 317209 (69.7) Δg 1271 (0.279) Δb 1626 (0.357)
 avg diff per pixel: 70.3
done with ../data/chunli23.png in 81.758ms.

worldmap, as expected, looks worse (though it is slightly faster and smaller)

current

analyzing ../data/worldmap.png...
 source pixels: 475x860 rendered: 475x860 1634000B
 control sequence: 149102 bytes (9.125%)
 00408500 pixels analyzed Δr 773700 Δg 747897 Δb 840216
 Colors: 233 vs 54
 408500px Δr 773700 (1.89) Δg 747897 (1.83) Δb 840216 (2.06)
 avg diff per pixel: 5.78
done with ../data/worldmap.png in 500.359ms.

new

analyzing ../data/worldmap.png...
 source pixels: 475x860 rendered: 475x860 1634000B
 control sequence: 129291 bytes (7.913%)
 00408500 pixels analyzed Δr 1352655 Δg 1352043 Δb 1154968
 Colors: 233 vs 47
 408500px Δr 1352655 (3.31) Δg 1352043 (3.31) Δb 1154968 (2.83)
 avg diff per pixel: 9.45
done with ../data/worldmap.png in 439.945ms.

time to run ncplayer ../data/notcurses.png -q -t0

current

[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m0.998s
user    0m0.481s
sys     0m0.021s
[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m0.997s
user    0m0.497s
sys     0m0.008s
[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m1.017s
user    0m0.494s
sys     0m0.012s
[schwarzgerat](0) $ 

new

[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m0.834s
user    0m0.308s
sys     0m0.016s
[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m0.801s
user    0m0.311s
sys     0m0.013s
[schwarzgerat](0) $ time ./ncplayer ../data/notcurses.png -q -t0

real    0m0.805s
user    0m0.311s
sys     0m0.012s
[schwarzgerat](0) $ 

both current and new seem to generate a busted ncvisual on intake from sixel in notcurses.png using NCSCALE_STRETCH, generating:

analyzing ../data/notcurses.png...
 Image too large, scaling to display
 source pixels: 320x1280 rendered: 1380x880 4857600B
 control sequence: 805394 bytes (16.58%)
 00281600 pixels analyzed Δr 28101341 Δg 15579849 Δb 1586032error getting pixel at 320/0 (1380/880)
error getting pixel at 320/0 (1380/880)
error comparing sixels

ncplayer /media/chungus/images/allrgb/* -t0 -q:

current

real    0m29.891s
user    0m29.277s
sys     0m0.605s

new

real    0m37.361s
user    0m36.704s
sys     0m0.648s

so current beats new on these pathological images.

time to run quantanal on everything in ../data:

new

real    0m9.174s
user    0m8.779s
sys     0m0.392s
real    0m9.242s
user    0m8.815s
sys     0m0.423s

current

real    0m9.618s
user    0m9.134s
sys     0m0.477s
real    0m9.527s
user    0m9.171s
sys     0m0.353s

[dankamongmen]

ok, i'm thinking i'm gonna merge this, and work to improve the two cases that have regressed (smooth gradients result in more banding due to eliminating relaxation; large numbers of leaves lead to slowness and quality droppage). the causes of both problems are understood, and this is a much better foundation to work from going forward.

the first problem will be easier to solve -- we just need to add fast relaxation.

on the latter, we need better merging, but that's not going to give us any perf back, and we already have a perf deficit. we'll have to science up that bitch.

[dankamongmen]

i still don't understand why we're seeing such a high average diff on chunli23.png. we ought be able to match those 17 colors exactly, right? how many colors are truly in the image? identify -format %k says 17. in that case, if we have 17 colors (check this), they ought be pretty much exact, no?

[dankamongmen]

0xff001030 -> 784
0xff001040 -> 1040
0xff082050 -> 1312
0xff183070 -> 1840
0xff184870 -> 1864
0xff284890 -> 2377
0xff4868b0 -> 2922
0xff7088d8 -> 3467
0xff883800 -> 60
0xff905000 -> 84
0xffa0c0f0 -> 4037
0xffb0e0f0 -> 4069
0xffb86830 -> 877
0xffd09060 -> 1686
0xffe8b898 -> 2495
0xfff0f0f0 -> 4087

[dankamongmen]

#0;2;44;28;9#1;2;56;28;16#2;2;44;19;9#3;2;69;41;28#4;2;85;53;44#5;2;94;75;63

[dankamongmen]

44;28;9: 113 / 72 / 23 : 0x71 / 0x48 / 0x17 : 01110001 / 01001000 / 00010111 : 0100 1 ...

wait.

how is color_key() defined?

((r & 0xf0) << 4u) | (g & 0xf8) | ((b & 0xe0) >> 5u)

WTF?

we've got a 13-bit number there, with one bit undefined, you dumb chungus!

no wait....

rrrr gggg gbbb

ok it's fine i thought g was coming out. so back to above...

key: 0111 0100 1000 (0x748 == 1864)

which is indeed

0xff184870 -> 1864

0x714817 isn't that off from 0x704818, certainly not enough to yield that high an average difference...i think our tool might be fucked up.

[dankamongmen]

oh shit i wonder if we're counting transparent pixels or something

[dankamongmen]

yep!

[schwarzgerat](0) $ ./quantanal ../data/chunli23.png 
analyzing ../data/chunli23.png...
 source pixels: 99x46 rendered: 99x46 18216B
 control sequence: 3116 bytes (17.11%)
 00004554 pixels analyzed Δr 1035 Δg 1271 Δb 1626

 4554px Δr 1035 (0.227) Δg 1271 (0.279) Δb 1626 (0.357)
 avg diff per pixel: 0.863
done with ../data/chunli23.png in 82.056ms.
[schwarzgerat](0) $ 

[dankamongmen]

much better =]

[ghost]

I am just now realizing that the total sixel color space is (101)^3 a.k.a. 19.97 bits, not 24 bits. If your stats are looking at before/after differences in 24 bit space, you might actually be much closer to the best possible coverage.