Re: [Algorithms] Palette-based Quantization

[Simon F. <sim...@po...>]

=20=0D=0AKevin Bewsey wrote:=0D=0A>=20=0D=0A> Hello,=0D=0A> Well I timed it=
, it was 3 minutes.  I am pretty sure it takes=20=0D=0A> so long for these =
reasons.=0D=0A> 1. The palette was stored in a file, And instead of reading=
=20=0D=0A> it in once, and storing it in a array. I did a binary read=20=0D=
=0A> for every pixel.=0D=0A>=20=0D=0A> 2. The code is in c#=0D=0A>=20=0D=0A=
> I really appreciate the comment about color space vs R3 space=20=0D=0A> b=
y Pete Brubaker.  I was going to use this same code for both=20=0D=0A> pall=
etized normal maps and palletized light maps.=0D=0A>=20=0D=0A> What worries=
 me about creating a bsp tree or kd tree. Is it=20=0D=0A> should create err=
ors.  I thought about doing this originally=20=0D=0A> so that every leave c=
ontained only one palette entry,=20=0D=0A> However, It seemed like this wou=
ld generate errors since=20=0D=0A> splitting planes could pass very close t=
o a palette point.=0D=0A>=20=0D=0A> Simon, did this problem occur with your=
 bsp tree=3F=0D=0A=0D=0AKevin,=0D=0A=0D=0ANo,  it didn't because that was o=
nly the first step to identify a=0D=0Astarting candidate.=20=0D=0A=0D=0AEac=
h palette entry also had a short list of other nearby palette=0D=0Acandidat=
es, P1, P2, P3 etc, sorted in increasing distance from the=0D=0Astarting ca=
ndidate (call those distances D1, D2, D3 etc). Once you'd=0D=0Ameasured the=
 distance from the starting candidate to the pixel, call=0D=0Athat distance=
 D0, you could use that as a threshold to immediately=0D=0Aeliminate some n=
umber of the nearby members. (I think it was those=0D=0Avalues of Dn > 1/2 =
D0 (or 1/4 if you used distance squared)). Any that=0D=0Awere still in the =
threshold you had to measure the distance.=20=0D=0A=0D=0AIf any of Dx ended=
 being closer, the algorithm then jumped to their list=0D=0Aand restarted t=
he algorithm=0D=0A=0D=0AObviously, it takes a bit of time to set up the nea=
rest neighbour lists,=0D=0Abut I think it can be sped up by using the bsp t=
ree to prune the size of=0D=0Athe potential sets.=20=0D=0A=0D=0AIf you are =
mapping a lot of images to the same palette it could help a=0D=0Alot. IIRC,=
 I found that the number of "evaluations" (including the=0D=0Ainitial Binar=
y search) averaged out at about 9~10 dotprod or Distance=0D=0Acalcs per sea=
rch.=0D=0A=0D=0A=0D=0AOf course, now that I've typed this, I remember the m=
ain reason I used=0D=0Athis approach is that I was using 16-D vectors (i.e.=
 each code =3D 4 RGBA=0D=0Apixels), but I used a different (simpler) approa=
ch a long time ago to do=0D=0ARGB palette matching. This was based on dyman=
ically evaluated voxels and=0D=0Aa hash table. (The technique worked for fo=
r 3D but is horrible for=0D=0Ahigher dimensions).=0D=0A=0D=0AI really can't=
 remember all the details but it went something like this:=0D=0A=0D=0ADivid=
e your colour space into a virtual N*N*N grid where N is a power of=0D=0A2,=
 say 32 or 64. Map the pixel to the voxel and look up the voxel in the=0D=0A=
hash table. (Only create a voxel entry if you actually need it!)=0D=0A=0D=0A=
Each (evaluated) voxel contains a list of all possible closest palette=0D=0A=
colours, i.e. it contains all palette entries entirely inside the voxel=0D=0A=
+ all those outside the voxel whose minimum distance to ANY point in the=0D=
=0Avoxel is closer than the minimum *Maximum* distance to ANY point in the=0D=
=0Avoxel for all the candidates.=0D=0A=0D=0AThis generally reduced the numb=
er of tests by a large margin, but I=0D=0Athink for some colour distributio=
ns I found two levels of voxel=0D=0Aheirarchy helped.=0D=0A=0D=0ASimon=0D=0A=0D=
=0A******************=0D=0AThis e-mail has been sent from Imagination Techn=
ologies Limited.=0D=0APowerVR, Metagence, Ensigma and PURE Digital are divi=
sions=0D=0Aof Imagination Technologies Limited.=0D=0A=0D=0AThe information =
contained in this e-mail, including any attachment,=0D=0Ais confidential an=
d may be legally privileged.  It is intended solely=0D=0Afor the addressee(=
s) and access to this e-mail by anyone else is=0D=0Aunauthorised.  If you a=
re not the intended recipient, any disclosure,=0D=0Acopying or distribution=
 or use of the information contained in this=20=0D=0Ae-mail, is prohibited =
and may be unlawful.  If you have received this=0D=0Ae-mail in error, pleas=
e notify the sender by return e-mail and then=0D=0Adelete it from your syst=
em.=0D=0A=0D=0AInternet communications cannot be guaranteed to be secure,=0D=
=0Aerror or virus-free.  The sender does not accept liability for any error=
s=0D=0Aor omissions which arise as a result.=0D=0A=0D=0AAny views expressed=
 in this message are those of the author, except=0D=0Awhere the author spec=
ifies and, with authority, states them to be the=0D=0Aviews of Imagination =
Technologies Limited.=0D=0A