From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ffbox0-bg.mplayerhq.hu (ffbox0-bg.ffmpeg.org [79.124.17.100]) by master.gitmailbox.com (Postfix) with ESMTP id 7E08645081 for ; Tue, 3 Jan 2023 18:50:16 +0000 (UTC) Received: from [127.0.1.1] (localhost [127.0.0.1]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTP id C8ED568BD77; Tue, 3 Jan 2023 20:50:14 +0200 (EET) Received: from relay8-d.mail.gandi.net (relay8-d.mail.gandi.net [217.70.183.201]) by ffbox0-bg.mplayerhq.hu (Postfix) with ESMTPS id 57EE468B7C0 for ; Tue, 3 Jan 2023 20:50:08 +0200 (EET) Received: (Authenticated sender: michael@niedermayer.cc) by mail.gandi.net (Postfix) with ESMTPSA id 2288D1BF207 for ; Tue, 3 Jan 2023 18:50:06 +0000 (UTC) Date: Tue, 3 Jan 2023 19:50:04 +0100 From: Michael Niedermayer To: FFmpeg development discussions and patches Message-ID: <20230103185004.GY3806951@pb2> References: <20221105152617.1809282-1-u@pkh.me> <20221106170941.GW1814017@pb2> <20221106173022.GX1814017@pb2> <20230102215733.GX3806951@pb2> MIME-Version: 1.0 In-Reply-To: Subject: Re: [FFmpeg-devel] Rework color quantization in palette{gen,use} X-BeenThere: ffmpeg-devel@ffmpeg.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: FFmpeg development discussions and patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: FFmpeg development discussions and patches Content-Type: multipart/mixed; boundary="===============3567622799950455324==" Errors-To: ffmpeg-devel-bounces@ffmpeg.org Sender: "ffmpeg-devel" Archived-At: List-Archive: List-Post: --===============3567622799950455324== Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="JEmpv92YMa79g021" Content-Disposition: inline --JEmpv92YMa79g021 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Jan 03, 2023 at 12:05:22AM +0100, Cl=C3=A9ment B=C5=93sch wrote: > On Mon, Jan 02, 2023 at 10:57:33PM +0100, Michael Niedermayer wrote: > [...] > > > So I did a lot of experiments, and the explanation for the desaturated > > > output at low number of colors can be found at the end of this articl= e: > > > http://blog.pkh.me/p/39-improving-color-quantization-heuristics.html > >=20 > > interresting and its impressive how much reseacrh you did here > > i hope this will get applied >=20 > Thanks. I was actually planning to push in the next 12 hours or so, unless > there is an objection. >=20 > > also i hape a bit that it will get > > extended to include clustering as in ELBG cuz it seems a bit odd > > to have this sort of alternative filters neither does all .... >=20 > Yeah at some point we probably want to group the clustering and vector > quantization logics in a common module. But there are lot of questions API > wise wrt its relationship with perceptual and other color systems. >=20 > > > I still think it's acceptable to lean toward desaturated colors when > > > reducing the number of colors, but you may disagree. > >=20 > > I think a key aspect of desaturation has not been mentioned. > > That is mixing, i mean dithering is some sort of mixing, in the sense of > > an artist mixing several pigment/dyes/colors. > > If you have black and white a 50% mixture gives 50% gray. other ratios > > would give us all values between white and black though with dithering > > some ratios work better like 50% looks good while ratios very close to > > 0 and 100% but not exacty 0 and 100 look bad with few highly vissible > > black or white pixels in a see of the opposing color. > >=20 > > Now this results in 2 things at least. > > 1. We should be able to improve color quantization by this. > > If we have colors A and B the (A+B)/2 point is basically free, its dit= her > > pattern looks good on any high resolution display and if we consider s= uch > > points there are more of course like maybe (A+B+C+D)/4 we can cover mo= re > > output colors with a smaller palette. >=20 > That's interesting. Basically you'd free certain slots of the palette if > you detect that this particular color is at the mid point of two others in > the palette? And so you could use that slot for another tint=E2=80=A6 >=20 > Yeah I don't know what to do with this information, it looks not trivial > to implement. If we simplify the problem a bit and instead of considering 3d we just look= at 1d then for example to represent all colors between 0 and 128 either as a solid color or by 2 colors 50:50% then we need only 19 colors of these valu= es {0,2,6,8,10,16,28,40,52,64,76,88,100,112,118,120,122,126,128} if we have fewer colors in 1d we can cover these Full n=3D 4 cover=3D9 avg=3D2.666667 {0,2,6,8} Full n=3D 5 cover=3D13 avg=3D3.769231 {0,2,6,10,12} Full n=3D 6 cover=3D17 avg=3D4.823529 {0,2,6,10,14,16} Full n=3D 7 cover=3D21 avg=3D5.857143 {0,2,4,10,16,18,20} Full n=3D 8 cover=3D27 avg=3D6.888889 {0,2,6,8,18,20,24,26} Full n=3D 9 cover=3D33 avg=3D 9.969697 {0,2,4,10,16,22,28,30,32} Full n=3D10 cover=3D41 avg=3D10.878049 {0,2,6,8,18,22,32,34,38,40} Full n=3D11 cover=3D45 avg=3D10.644444 {0,2,6,8,18,22,26,36,38,42,44} Full n=3D12 cover=3D55 avg=3D14.727273 {0,2,6,8,18,22,32,36,46,48,52,54} Full n=3D13 cover=3D65 avg=3D18.415385 {0,2,6,8,18,22,32,42,46,56,58,62,64} Full n=3D14 cover=3D73 avg=3D18.931507 {0,2,6,8,18,22,32,40,50,54,64,66,70,= 72} Full n=3D15 cover=3D81 avg=3D25.172840 {0,2,6,8,10,16,28,40,52,64,70,72,74,= 78,80} Full n=3D16 cover=3D93 avg=3D30.193548 {0,2,6,8,10,16,28,40,52,64,76,82,84,= 86,90,92} Full n=3D17 cover=3D105 avg=3D35.209524 {0,2,6,8,10,16,28,40,52,64,76,88,94= ,96,98,102,104} Full n=3D18 cover=3D111 avg=3D33.261261 {0,2,6,10,14,18,20,42,44,66,68,90,9= 2,96,100,104,108,110} so what about 3d ? if we have a 3d cube and we create a palette with the 1d list from above for 6 colors we end up with a 6x6x6 palette of 216 colors where with the 50:50 = mixes we cover the full 17x17x17=3D4913 cube, all points of it that is. same for = the 6x6x7 (17x17x21=3D6069) cases. this might be an interresting alternative to the = 332 palette or maybe it could be used as start point for some optimized palette, remoci= ng unused colors and adding new by some clustering I didnt try any of this on an actual image. Its not as simple as using that= palette as the dither algorithm also needs to be redesigned to actually use the rig= ht color pairs. Dither would generally use the closest color and thats not tru= e here for many pairs also gamma needs to be handled correctly for all this because mixing white = and black pixels will only look like 50% gray when gamma is handled correctly As i didnt try it, i have 0 idea how bad it would look. I was primarly inte= rrested in the nummeric/math aspect behind this which is why i played a bit with th= ese numbers thx [...] --=20 Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB The day soldiers stop bringing you their problems is the day you have stopp= ed=20 leading them. They have either lost confidence that you can help or conclud= ed=20 you do not care. Either case is a failure of leadership. - Colin Powell --JEmpv92YMa79g021 Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iF0EABEIAB0WIQSf8hKLFH72cwut8TNhHseHBAsPqwUCY7R41QAKCRBhHseHBAsP q4I6AJ0VdeogukeniXVIO0SuU8pekkuiiQCeKbkBKwe8FQnAAM+pVBc3bYE9ldQ= =UCsT -----END PGP SIGNATURE----- --JEmpv92YMa79g021-- --===============3567622799950455324== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". --===============3567622799950455324==--