unit optimise;
{$N+}
{$UNDEF RAPIDE}  {si rapide, cr‚ation d'une table de correspondance
                  approximative pour la restitution des couleurs}
{$UNDEF NBPIXEL}   {critŠres de classement, voir article}
{$UNDEF VOLUME}
{$DEFINE PRODUIT}
{$UNDEF MATHEM}

interface
uses global;

type
  pHistVB=^histVB;
  histVB=array[0..31,0..31] of longint;

var hist:array[0..31] of pHistVB;

procedure initOptim(nbCoul,maxValeur:integer);
procedure ChercheCouleurs(var pal:tPalette);

{----------------------------IMPLEMENTATION---------------------------------}
implementation
uses crt;
type
  pBoite=^Boite;
  boite=record
    minR,minV,minB,maxR,maxV,maxB:byte;
    nbPixel:longint; nbCoulDiff,volume:word;
  end;


var listBox:array[0..255] of pBoite;
    nbCouleurs,maxVal:integer;
{-----------------------------INIT OPTIM ----------------------------------}
procedure initOptim(nbCoul,maxValeur:integer);
var i:integer;
begin
  nbCouleurs:=nbCoul-1; {reserve une couleur pour le fond}
  maxVal:=maxValeur;
  for i:=0 to 31 do begin
    new(hist[i]); {cr‚e variable histogramme}
    fillChar(hist[i]^,sizeOf(histVB),0);
  end;
  ClrScr; writeln('PremiŠre passe: cr‚ation de l''histogramme.. Patience');
  for i:=0 to 255 do new(listBox[i]);
end;

{------------------------GESTION LISTE CYCLIQUE----------------------------}
function suivant(n:integer):integer;
begin
  suivant:=(n+1) mod 256;
end;

function precedent(n:integer):integer;
begin
  precedent:=(n+255) mod 256;
end;

{------------------------OPERATIONS SUR LES BOITES--------------------------}
function critere(numero:integer):longint;
begin
   with listBox[numero]^ do
{$IFDEF NBPIXEL}   {version normale: popularit‚}
         critere:=nbPixel;
{$ENDIF}
{$IFDEF VOLUME}    {version: taille de la boite}
         critere:=volume;
{$ENDIF}
{$IFDEF PRODUIT}   {version compromis taille-popularit‚}
         critere:=nbpixel*volume;
{$ENDIF}
{$IFDEF MATHEM}    {version critŠre ‚ecart quadratique}
         critere:=nbPixel*(sqr(maxR-minR)+sqr(maxV-minV)+sqr(maxB-minB));
{$ENDIF}
end;


procedure reclasse(premier,dernier:integer);
{remet la derniŠre boite en position correcte, apres premier}
var courant,apres:integer; pProv:pBoite;
begin
  courant:=precedent(dernier); apres:=dernier;
  while (courant<>premier) and
        ( ((listBox[courant]^.volume=1) and (listBox[apres]^.volume<>1))  or
         (critere(courant)<critere(apres)) )
        do begin
    pProv:=listBox[courant];
    listBox[courant]:=listBox[apres];
    listBox[apres]:=pProv;
    courant:=precedent(courant); apres:=precedent(apres);
  end;
end;

procedure creeBoite(num:integer; miR,maR,miV,maV,miB,maB:byte);
var i,j,k:byte;
begin
  with listbox[num]^ do begin
    nbPixel:=0;  {nombre de pixels de l'image dans la boite}
    nbCoulDiff:=0;  {nombre de couleurs diff‚rentes dans la boite}
    minR:=32; minV:=32; minB:=32; maxR:=0; maxV:=0; maxB:=0;
    for i:=miR to maR-1 do for j:=miV to maV-1 do for k:=miB to maB-1 do
      if hist[i]^[j,k]<>0 then begin
        inc(nbPixel,hist[i]^[j,k]);
        inc(nbCoulDiff);
        if i<minR then minR:=i; if i>maxR then maxR:=i;
        if j<minV then minV:=j; if j>maxV then maxV:=j;
        if k<minB then minB:=k; if k>maxB then maxB:=k;
    end;
    inc(maxR); inc(maxV); inc(maxB);
    volume:=(maxR-minR)*(maxV-minV)*(maxB-minB);
  end;
end;


procedure coupeBoite(tete:integer; var queue,nb:integer);
{place en queue et suivant(queue) la boite de tete coup‚e en deux}
const axeR=1; axeV=2; axeB=3;
var maxLong:integer; Axe,pos,j,k:byte;
    moitie,compteur:longint;
begin
  with listBox[tete]^ do begin
    {recherche de l'axe de coupe}
    maxlong:=maxV-minV; Axe:=axeV; {d'abord vert de luminance sup‚rieure}
    if (maxR-minR)>maxLong then begin maxLong:=maxR-minR; axe:=axeR; end;
    if (maxB-minB)>maxLong then begin maxLong:=maxB-minB; axe:=axeB; end;
    moitie:=nbPixel div 2; compteur:=0;
    {recherche de la position de coupe}
    case axe of
      axeR: begin
              pos:=minR;
              while (compteur<moitie) and (pos<maxR-1) do begin
                for j:=minV to maxV-1 do for k:=minB to maxB-1 do
                  inc(compteur,hist[pos]^[j,k]);
                inc(pos);
              end;
              creeBoite(queue,minR,pos,minV,maxV,minB,maxB);
              reclasse(tete,queue);
              if compteur<nbPixel then begin
                queue:=suivant(queue); {il est permis d'‚craser la tete!}
                creeBoite(queue,pos,maxR,minV,maxV,minB,maxB);
                reclasse(tete,queue);
                inc(nb);
              end;
            end;
      axeV: begin pos:=minV;
              while (compteur<moitie) and (pos<maxV-1) do begin
                for j:=minR to maxR-1 do for k:=minB to maxB-1 do
                  inc(compteur,hist[j]^[pos,k]);
                inc(pos);
              end;
              creeBoite(queue,minR,maxR,minV,pos,minB,maxB);
              reclasse(tete,queue);
              if compteur<nbPixel then begin
                queue:=suivant(queue); {il est permis d'‚craser la tete!}
                creeBoite(queue,minR,maxR,pos,maxV,minB,maxB);
                reclasse(tete,queue);
                inc(nb);
              end;
            end;
      axeB: begin pos:=minB;
              while (compteur<moitie) and (pos<maxB-1) do begin
                for j:=minR to maxR-1 do for k:=minV to maxV-1 do
                  inc(compteur,hist[j]^[k,pos]);
                inc(pos);
              end;
              creeBoite(queue,minR,maxR,minV,maxV,minB,pos);
              reclasse(tete,queue);
              if compteur<nbPixel then begin
                queue:=suivant(queue); {il est permis d'‚craser la tete!}
                creeBoite(queue,minR,maxR,minV,maxV,pos,maxB);
                reclasse(tete,queue);
                inc(nb);
              end;
            end;
    end; {case axe}
  end;
end;

procedure chercheCorrespondance(pos,nbcoul:integer);
{cr‚e le tableau de correspondance entre couleur 5 bits et palette}
var i,j,k,l:byte; adresse:word;
begin
  for i:=1 to nbCoul do with listBox[pos]^ do begin
    for j:=minR to maxR-1 do for k:=minV to maxV-1 do for l:=minB to maxB-1 do
    begin
      adresse:=(j shl 10) + (k shl 5) + l;
      maTable^[adresse]:=i;
    end;
    pos:=suivant(pos);
  end; {for}
end;

procedure calculMoyenne(pos,nbCoul:integer; var pal:tPalette);
{calcul de la couleur moyenne de chaque boite … mettre dans la palette}
var  i,j,k,l,ratio:byte; totR,totV,totB,poid:longint;  prov:word;
begin
  ratio:=256 div (maxval+1);
  for i:=1 to nbCoul do with pal[i] do with listBox[pos]^ do begin
    totR:=0; totV:=0; totB:=0;
    for j:=minR to maxR-1 do for k:=minV to maxV-1 do for l:=minB to maxB-1 do
    begin
      poid:=hist[j]^[k,l];
      if poid<>0 then begin  {reconversion 5 bits -> 8 bits}
        inc(totR,(j shl 3 + 4)*poid);
        inc(totV,(k shl 3 + 4)*poid);
        inc(totB,(l shl 3 + 4)*poid);
      end;
    end;
    {prov: moyenne 8 bits de la composante de couleur}
    {les composantes r v b de la palette sont obtenues par filtrage des bits,
    ratio valant 4 normalement (6 bits)}
    prov:=totR div nbPixel;  r:=prov div ratio;
    prov:=totV div nbPixel;  v:=prov div ratio;
    prov:=totB div nbPixel;  b:=prov div ratio;
    pos:=suivant(pos);
  end;
  with pal[0] do begin r:=0; v:=0; b:=0; end; {fond noir}
end;

{------------------OPTIMISATION DES COULEURS------------------------------}
procedure ChercheCouleurs(var pal:tPalette);
var i,tete,queue,nb,nbCoul:integer;
begin
  writeln('Recherche des couleurs');
  tete:=0; queue:=1; nb:=1;
  creeboite(tete,0,32,0,32,0,32);
  if listBox[tete]^.nbCoulDiff<nbCouleurs then
    nbCoul:=listBox[tete]^.nbCoulDiff else nbCoul:=nbCouleurs;
  while (nb<nbCoul) do begin
    if listbox[tete]^.volume=1 then listbox[queue]^:=listBox[tete]^
      {on ne peut plus couper, trop petit}
    else begin {on coupe en deux}
      coupeBoite(tete,queue,nb);
      gotoxy(1,4); write(nb:3,' couleurs');
    end;
    queue:=suivant(queue);
    tete:=suivant(tete);
  end;
  calculMoyenne(tete,nbcoul,pal);
  for i:=0 to 31 do dispose(hist[i]); {libŠre place occup‚e par histo}
  new(maTable); fillChar(maTable^,sizeOf(maTable^),0);
  {cr‚e tableau 'maTable' pour recherche couleur rapide,
  Attention c'est une approximation...
  Ne pas appeler 'ChercheCorrespondance' si on veut plus de pr‚cision!}
  {$IFDEF RAPIDE} chercheCorrespondance(tete,nbCoul); {$ENDIF}
  for i:=0 to 255 do dispose(listBox[i]);
end;

begin end.

















