Pixel Konvertierung
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Von OptimierungsBeispiele. (vergiss nicht: Optimiere nicht, optimiere später, ...)

Folgende - nicht so seltene Problem - wurde in dclc im Nov 2001 aufgeworfen. Nach einer kurzen Diskussion hat Hans Eder die beiden Hauptvarianten implementiert und mir den Code und seine Benchmark-Ergebnisse zugeschickt und die Verwendung hier zugelassen. -- HelmutLeitner


Der OP hat TrueColorBilder und möchte auf Grund der RGB-Werte eine ja-nein Entscheidung möglichst effizient durchführen. Die konkrete Aufgabenstellung wurde noch nicht genannt, aber die gleiche Situation wäre bei einer Umwandlung TrueColorBilder -> MonoChromBilder? gegeben (ähnliche Aufgabenstellungen ergeben sich auch bei der Umwandlung in Bilder mit Farbpaletten).

Der auf der Hand liegende Lösungsansatz besteht darin, die Berechnung nicht für jedes einzelne Pixel durchzuführen, sondern TabellenStattBerechnungen zu verwenden. Offen sind die Fragen nach der optimalen Repräsentation dieser Tabellen und der bestmöglichen Performance. Siehe auch SpeicherplatzFürPerformance.


Variante 1: Bit-Array simulieren

Es gibt genug leicht verfügbaren Code um einen Bit-Array der Dimension 2^24 zu simulieren (z.B. www.snippets.org). Natürlich kostet die Positionsberechnung und der Zugriff auf das Einzelbit ein wenig Rechenzeit.

Vorteile:

Nachteile:

Variante 2: Char-Array und Reduktion der Auflösung

Man kann meist auf einen Teil der Präzision in der Einzelfarbe (1-3 Bit) verzichten (z.B. durch r>>=2; g>>=2; b>>=2) und dann mit einem normalen komfortablen Array:

char ColorDecisionArray[64][64][64];

arbeiten.

Vorteile:

Nachteile:

Auf meinem Rechner (Pentium 166, C++Builder 3.0) ist die Variante 2 rund 
doppelt so schnell wie die Variante 1 (3100 gegen 1500 Durchläufe 
in 2 Sekunden). Ich habe versucht eine möglichst wirklichkeitsnahe 
und faire Testumgebung für dieses Problem zu erstellen.

Hier mein Testprogramm:

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

#define TESTLEN 1024
#define LOOPTIME 2.0

typedef unsigned long ul;

unsigned char ColorDecisionArray [64][64][64];          /* 256 kByte*/
unsigned char ColorDecisionBitArray [32L*32*32*8*8*8/8]; /* 2 Mbyte  */
unsigned char col[TESTLEN];

#define COLOR_DECISION_GET(R, G, B, V)                              {                                                                     unsigned long  pos = ((ul)(G&248)<<13) | ((ul)(R&248)<<8)                              | ((B&248)<<3) | ((G&7)<<3)                                         | (R&7);                                         V =  (unsigned char)((ColorDecisionBitArray [pos] >> (B&7) )&1);  }

#define COLOR_DECISION_SET(R, G, B, V)                              {                                                                     unsigned long  pos = ((ul)(G&248)<<13) | ((ul)(R&248)<<8)                              | ((B&248)<<3)  | ((G&7)<<3)                                        | (R&7);                                         if ( V == 0 )                                                           ColorDecisionBitArray [pos] &= (unsigned char)(~(1 <<(B&7)));   else                                                                    ColorDecisionBitArray [pos] |= (unsigned char)( (1 <<(B&7))); }

int main(void)
{
  int n, i;
  clock_t start;
  unsigned char red[TESTLEN], green[TESTLEN], blue[TESTLEN];
  unsigned char *r,*g,*b,*c;

  for (i=0; i<TESTLEN; i++)
  {
    red[i]  = (unsigned char)rand();
    green[i]= (unsigned char)rand();
    blue[i] = (unsigned char)rand();
  }

  for (n=0, start=clock(); ((clock()-start)/CLK_TCK)<LOOPTIME; n++)
  {
    for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++)
      ColorDecisionArray[*r>>2][*g>>2][*b>>2] = *c;
    for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++)
      *c = ColorDecisionArray[*r>>2][*g>>2][*b>>2];
  }
  printf("Highscore Leitner    : %d Loops\n",n);

  for (n=0, start=clock(); ((clock()-start)/CLK_TCK)<LOOPTIME; n++)
  {
    for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++)
      COLOR_DECISION_SET(*r, *g, *b, *c);
    for (c=col,r=red,g=green,b=blue,i=0; i<TESTLEN; i++,r++,g++,b++,c++)
      COLOR_DECISION_GET(*r, *g, *b, *c);
  }
  printf("Highscore Klemm      : %d Loops\n",n);

  return 0;
}

mfg hans eder

Anmerkung 1: Die Schleifendurchläufe sind nur als qualitatives Maß für die Geschwindigkeit zu sehen, weil oben der - allerdings nicht sehr große - Schleifenoverhead mitgemessen wurden.

Anmerkung 2: Das Mischen der Bits in der Variante 2 ergibt eine geringfügige Verbesserung der Performance, vermutlich auf Grund der von Frank Klemm ins Spiel gebrachten besseren "Lokalität" der Zugriffe!? Eine vereinfachte Variante mit konventioneller Bitanordnung ist interessanterweise um einige Prozent langsamer.

Anmerkung 3: Die Ergebnisse könne teilweise stark vom Prozessor abhängig sein. Auf einem 750 MHz Athlon / Win98 / Borland C 5.0x war das Verhältnis ca. 18000:12000 Schleifendurchläufe in den gleichen 2 Sekunden.


KategorieOptimierung KategorieC KategorieCee KategorieProgrammierBeispiele
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 29. November 2007 8:44 (diff))
Suchbegriff: gesucht wird
im Titel
im Text