Verfügbare Informationen zu "Projekt C++ / Computergraphik: MedianCut-Algorithmus"
Qualität des Beitrags: Beteiligte Poster: timo Forum: 14. Info Forenbeschreibung: Informatiker der NTA-Isny aus dem Unterforum: C++ Antworten: 1 Forum gestartet am: Donnerstag 15.06.2006 Sprache: deutsch Link zum Originaltopic: Projekt C++ / Computergraphik: MedianCut-Algorithmus Letzte Antwort: vor 16 Jahren, 9 Monaten, 14 Tagen, 8 Stunden, 46 Minuten
Alle Beiträge und Antworten zu "Projekt C++ / Computergraphik: MedianCut-Algorithmus"
Re: Projekt C++ / Computergraphik: MedianCut-Algorithmus
timo - 14.07.2007, 14:04Projekt C++ / Computergraphik: MedianCut-Algorithmus
Aufgabenstellung
Projektthema: Farbkonvertierung 24 Bit in 8 Bit
Erstellen Sie ein lauffähiges Programm, um ein 24-Bit Bitmap-Bild in ein 8-Bit Bitmap Bild zu konvertieren (Farbreduzierung), dabei soll geeigneter Algorithmus angewandet werden (beispielsweise Median-Cut, der Bearbeiter kann jedoch den Algorithmus selbst bestimmen).
Wichtig: Das Programm wurde in C++ von Microsoft Visual Studio 2005 erstellt.
Einführung Farbquantizierung / MedianCut
A. Einführung
Quantisierung meint die Konvertierung eines Bildes mit einem kontinuierlichen Farbgamut in ein Bild mit diskretem Farbgamut bzw. die Konvertierung eines Bildes mit diskretem Farbgamut in ein Bild mit diskretem Farbgamut geringerer Farbauflösung. Quantisierungsabbildung ändert die Farbauflösung eines Bildes. Basis der Quantisierung ist die Quantisierungsfunktion q : C → C', die einen kontinuierlichen oder einen diskreten Farbraum C in einen diskreten Farbraum C' abbildet.
B. Median Cut-Algorithmus
„Die Aufgabe des Median Cut-Algorithmus 1) [Medianschnitt-Verfahren] ist die Erstellung einer Farbtabelle. Zuerst wird das Originalbild analysiert: alle im Originalbild vorhandenen Farben werden im RGB-Würfel markiert. Die Idee des Verfahrens ist es, aus dem RGB-Würfel rekursiv Teilwürfel zu erstellen. Dabei sollen die so entstandenen Teilwürfel möglichst die gleiche Anzahl an Farben aus dem Originalbild enthalten. Sei m die gewünschte Anzahl von Farben der Farbpalette. Dann werden die entstandenen Teilwürfel rekursiv weiter zerlegt, bis man m einzelne Würfel erhalten hat. Diese repräsentieren dann jeweils eine Farbe aus der resultierenden Farbtabelle. Aus den verbleibenden Farben in einem Teilwürfel berechnet man den Mittelwert und erstellt die Farbtabelle“. 2)
Quellen
1) HECKBERT, P., Color Image Quantization for Frame Buffer Display, Computer Graphics 16/3 (1982) 297-307.
2) LICKER, J., Farbquantisierung, in: http://www.uni-koblenz.de/~cg/veranst/ws0001/sem/Licker-neu.pdf (Vorlage für den Algorithmus MedianCut).
COMGRA2.CPP
#define WIN32_LEAN_AND_MEAN // Makro und Konstante
// Selten verwendete Teile der Windows-Header nicht einbinden.
#include <iostream>
#include <conio>
#include <windows>
#include <stdio>
#include <tchar>
#include ".\CBmpFile.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[]) // Globale Funktion
// Benötigt, wegen internen Vorgängen zur Verwaltung der
// Programmdateien (Projekt-Dateien von Visual Studio 2005)
{
cout << endl << "main() argc: " << argc;
FILE * l_fileOutputFile = fopen("ausgabe.bmp", "wb");
// Es wird ein benutzerdefinierter Datentyp für die Ergebnisdatei
// erzeugt, anschließend wird die Ergebnisdatei geöffnet
CBmpFile input("eingabe.bmp");
// Es wird ein Objekt 'input' erzeugt für das Lesen der
// original Bilddatei
input.getFile(*l_fileOutputFile);
// Methode: Vorbereitung der OutputImageDatei
input.convertTo8Bit();
// Ruft Methode auf um 24 Bit in 8 Bit zu konvertieren,
// diese Methode ruft den Algorthmus MEDIAN CUT auf
input.getCopy(*l_fileOutputFile);
// Methode: Kopiere Daten in OutputImageDatei
CBmpFile input2("palette.bmp");
// Es wird ein Objekt 'input2' erzeugt, ließt durch den
// Konstruktor den Header der Datei 'palette.bmp' ein
// und gibt die Header-Informationen auf dem Bildschirm
// aus
fclose(l_fileOutputFile);
getch();
return 0;
}
CMEDIANCUT.H
#pragma once
#include <list>
struct Point
// Attribut der Klasse Block
// Wir stellen jeden Pixel als eine einfache Struktur für jedes
// nicht negative Byte dar
{
unsigned char x[3];
};
class Block
{
Point minCorner, maxCorner;
// Wir stellen einen Block durch Speichern der Pixel
// aus zwei entgegengesetzten Ecken dar. Im einen Pixel
// sind die kleinst möglichen Koordinaten, im anderen Punkt
// die größt möglichen Koordinaten des Pixels gespeichert.
Point *points; //Struktur-Pointer
int pointsLength;
// Um den Algorithmus zu verbessern wird auf die Pixel
// mit Zeiger und Längenkodierung zugegriffen
public:
Block(Point *points, int pointsLength); // Konstruktor
Point *getPoints();
int numPoints() const;
int longestSideIndex() const;
int longestSideLength() const;
bool operator<(const Block& rhs) const; // Operatorüberladung "<"-Zeichen
void shrink();
private:
};
// Darstellung einer generischen Klasse mit Template in C++
template <int>
class CoordinatePointComparator
{
public:
bool operator()(Point left, Point right)
{
return left.x[index] < right.x[index];
}
};
// Deklaration des MedianCut-Algorithmus außerhalb der Klasse
std::list<Point> medianCut(Point* image, int numPoints, unsigned int desiredSize);
CMEDIANCUT.CPP
#include <limits>
#include <queue>
#include <algorithm>
#include "./CMediancut.h"
Block::Block(Point *points, int pointsLength)
// Konstruktor initialisiert Quader (Array of Points).
// Im größtmöglichen Quader sind punktuelle Farben der
// Teilfragmente vorhanden
{
this->points = points;
this->pointsLength = pointsLength;
for(int i=0; i < 3; i++)
{
minCorner.x[i] = std::numeric_limits<unsigned>::min();
maxCorner.x[i] = std::numeric_limits<unsigned>::max();
}
// printf ("\n--- Block::Block 01\n");
}
Point * Block::getPoints()
// Ermittlung der Koordinaten und der Größe der Teilfragmente
{
// printf ("\n--- Block::getPoints 02\n");
return points;
}
int Block::numPoints() const
{
// printf ("\n--- Block::numPoints 03\n");
return pointsLength;
}
int Block::longestSideIndex() const
// Algorithmus, welcher herausfindet, welche Seite des
// Quaders die größte Länge besitzt
{
// printf ("\n--- Block::longestSideIndex 04\n");
int m = maxCorner.x[0] - minCorner.x[0];
int maxIndex = 0;
for(int i=1; i <3> m)
{
m = diff;
maxIndex = i;
}
}
return maxIndex;
}
int Block::longestSideLength() const
// Größte Seite des Quaders ermittelt
{
// printf ("\n--- Block::longestSideLength 05\n");
int i = longestSideIndex();
return maxCorner.x[i] - minCorner.x[i];
}
bool Block::operator<const>longestSideLength() < rhs.longestSideLength();
}
void Block::shrink()
// Quader verkleinern, dass die punktuellen Teilfragmente
// gerade noch enthalten sind (kleinster umschreibender Quader)
{
// printf ("\n--- Block::shrink 07\n");
int i,j;
for(j=0; j<3; j++)
{
minCorner.x[j] = maxCorner.x[j] = points[0].x[j];
}
for(i=1; i < pointsLength; i++)
{
for(j=0; j<3; j++)
{
if (minCorner.x[j] < points[i].x[j])
minCorner.x[j] = minCorner.x[j];
else
minCorner.x[j] = points[i].x[j];
if (maxCorner.x[j] < points[i].x[j])
maxCorner.x[j] = minCorner.x[j];
else
maxCorner.x[j] = points[i].x[j];
}
}
}
std::list<Point> medianCut(Point* image, int numPoints, unsigned int desiredSize)
// Der Algorithmus MEDIAN CUT ist Globale Funktion und erzeugt die Farbpalette
{
std::priority_queue<Block> blockQueue;
Block initialBlock(image, numPoints);
initialBlock.shrink();
// Repräsentanten-Wahl: Primärfarbanteile der verbleibenden Punkte
// im Quader getrennt ermittelt durch Arithmetisches Mittel
blockQueue.push(initialBlock);
while (blockQueue.size() <desiredSize> 1)
{
Block longestBlock = blockQueue.top();
blockQueue.pop();
Point * begin = longestBlock.getPoints();
Point * median = longestBlock.getPoints() + (longestBlock.numPoints()+1)/2;
Point * end = longestBlock.getPoints() + longestBlock.numPoints();
switch(longestBlock.longestSideIndex())
{
case 0: std::nth_element(begin, median, end, CoordinatePointComparator<0>()); break;
case 1: std::nth_element(begin, median, end, CoordinatePointComparator<1>()); break;
case 2: std::nth_element(begin, median, end, CoordinatePointComparator<2>()); break;
}
Block block1(begin, median-begin), block2(median, end-median);
block1.shrink();
block2.shrink();
blockQueue.push(block1);
blockQueue.push(block2);
}
std::list<Point> result;
while(!blockQueue.empty())
{
Block block = blockQueue.top();
blockQueue.pop();
Point * points = block.getPoints();
int sum[3] = {0};
for(int i=0; i < block.numPoints(); i++)
{
for(int j=0; j < 3; j++)
{
sum[j] += points[i].x[j];
}
}
Point averagePoint;
for(int j=0; j < 3; j++)
{
averagePoint.x[j] = sum[j] / block.numPoints();
}
result.push_back(averagePoint);
}
printf ("\n--- Block::list<Point> medianCut 08\n");
return result;
}
CBMPFILE.H
/* pragma once wird verwendet, damit der Compiler nicht dieselben Include-
Dateien mehrmals einbindet.
*/
#pragma once
#include <stdio>
#include <iostream>
#include <math>
#include "./CMediancut.h"
// Farbkonvertierung 24 in 8 bit mit Algorithmus Mediancut
#include <list>
// STL Bibliothek. CPP
class CBmpFile
// Klasse zur Konvertierung des Bmp-File
{
public:
CBmpFile(const char * l_pcFile);
~CBmpFile();
// Konstruktor/Destruktor: Lesen & Ausgabe von der Image-Struktur
void convertTo8Bit();
// Methode: Image Konvertieren nach 8Bit-Modus (Farbpalette)
void getFile(FILE & l_fileOutputFile);
// Methode: Vorbereitung der OutputImageDatei
void getCopy(FILE & l_fileOutputFile);
// Methode: Kopiere Daten in OutputImageDatei
void convertWriteFile( FILE* outputFile);
// Methode: Erzeuge Ausgabedatei im 8 Bit-Modus (Header u. Farben ändern)
private:
long getImageInfo(long, int);
// Image = Header-Dateien im BMP File
// Adresse und Definition der Struktur von der Imagedatei
// l_iRows i_iCols l_iFileSize l_iPixel i_iColors * l_pcData
FILE *l_fileImageFile;
int l_iRows;
int l_iCols;
int l_iFileSize;
int l_iPixel;
int l_iColors;
unsigned char *l_pcData;
};
CBMPFILE.CPP
#include "CBmpFile.h"
CBmpFile::CBmpFile(const char * l_pcFile) // Deklaration des Konstruktors (außerhalb der Klasse)
// Methode: Lesen & Ausgabe von der Header-Struktur
{
l_fileImageFile = fopen(l_pcFile, "rb");
fseek(l_fileImageFile, 0L, SEEK_END);
l_iCols = (int)getImageInfo( 18, 4);
l_iRows = (int)getImageInfo( 22, 4);
l_iFileSize = (int)getImageInfo( 2, 4);
l_iPixel = (int)getImageInfo( 28, 2);
l_iColors = (int)getImageInfo( 46, 4);
printf ("\n--- PRINT DATA TO SCREEN \n"); // Testausgabe
printf("Width: %d\n", l_iCols);
printf("Height: %d\n", l_iRows);
printf("File size: %ld\n", l_iFileSize);
}
CBmpFile::~CBmpFile()
// Methode: Datei schliessen und mit Destruktur,
// allokierter Speicherplatz freigeben.
{
fclose(l_fileImageFile);
printf ("\n--- CBmpFile::~CBmpFile 02 \n");
}
void CBmpFile::convertTo8Bit()
// Methode: Image konvertieren nach 8Bit-Modus (Farbpalette)
{
printf ("\n--- CBmpFile::convertTo8Bit 03 \n");
FILE *l_filePalette;
l_filePalette = fopen("palette.bmp","wb");
//Farbpalette erzeugen
int numPoints = l_iCols*l_iRows;
Point* points = (Point*)malloc(sizeof(Point) * numPoints);
fseek(l_fileImageFile, 54, SEEK_SET);
for(int i = 0; i < numPoints; i++)
{
fread(&points[i], 3, 1, l_fileImageFile);
}
std::list<Point> palette = medianCut(points, numPoints, 256);
// OriginalHeader für Farbpaletten Bild
unsigned char *ptrC;
unsigned char dummy;
dummy = '0';
ptrC = &dummy;
fseek(l_fileImageFile, 0L, SEEK_SET);
fseek(l_filePalette, 0L, SEEK_SET);
for(int i=0; i<54> 280 Hex
*pLong = (unsigned long) 256;
fseek(l_filePalette, 22, SEEK_SET);
fwrite(pLong, sizeof(unsigned long), 1, l_filePalette);
// 640 Dezimal -> 280 Hex
fseek(l_filePalette, 54, SEEK_SET);
std::list<Point>::iterator iter;
int blub = 0;
for (iter = palette.begin() ; iter != palette.end(); iter++)
{
for(int j = 0; j<256>x[0], sizeof(char), 1, l_filePalette); //rot
fwrite(&iter->x[1], sizeof(char), 1, l_filePalette); //grün
fwrite(&iter->x[2], sizeof(char), 1, l_filePalette); //blau
}
blub++;
}
if(blub<256)
{
for(int i = blub; i<256;i++)
{
for(int j = 0; j<256;j++){
fwrite("256", sizeof(char), 1, l_filePalette); //rot
fwrite("256", sizeof(char), 1, l_filePalette); //grün
fwrite("256", sizeof(char), 1, l_filePalette); //blau
}
}
}
fclose(l_filePalette);
}
void CBmpFile::getFile(FILE &l_fileOutputFile)
// Methode: Vorbereitung der OutputImageDatei
{
printf ("\n--- CBmpFile::getFile 04 \n");
unsigned char *ptrC;
unsigned char dummy;
unsigned char *pChar;
int redValue, greenValue, blueValue, alphaValue;
dummy = '0';
ptrC = &dummy;
pChar = &dummy;
fseek(l_fileImageFile, 0L, SEEK_SET);
fseek(&l_fileOutputFile, 0L, SEEK_SET);
for(int i=0; i<=50; i++)
{
fread(ptrC, sizeof(char), 1, l_fileImageFile);
fwrite(ptrC, sizeof(char), 1, &l_fileOutputFile);
}
fseek(l_fileImageFile, 54, SEEK_SET);
fseek(&l_fileOutputFile, 54, SEEK_SET);
/*----------- Farbinformationen der Originaldatei einlesen -----------*/
for(int r=0; r<=l_iRows-1; r++)
{
for(int c=0; c<=l_iCols-1; c++)
{
fread(pChar, sizeof(char), 1, l_fileImageFile); // read Schmitt S.231
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
fread(pChar, sizeof(char), 1, l_fileImageFile);
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
fread(pChar, sizeof(char), 1, l_fileImageFile);
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
}
}
}
long CBmpFile::getImageInfo(long offset, int numberOfChars)
// Image = Header-Dateien im BMP File
{
printf ("\n--- CBmpFile::getImageInfo 05 \n");
unsigned char *ptrC; // Zeiger auf ausgelesene Daten
long value=0L; // Speichert Rückgabewert
unsigned char dummy; // Initialisierung des Zeigers
dummy = '0';
ptrC = &dummy;
fseek(l_fileImageFile, offset, SEEK_SET);
for(int i=1; i<=numberOfChars; i++)
{
fread(ptrC, sizeof(char), 1, l_fileImageFile); // Schmitt S.231
// printf("READ1 i = %d %x \n ",i, (*ptrC) );
value = (long)(value + (*ptrC)*((long)pow(256.0, (double)(i-1))));
// Berechnet aus Bytes den dezimalen Wert
}
return(value);
}
void CBmpFile::getCopy(FILE &l_fileOutputFile)
// Methode: Kopiere Daten in OutputImageDatei
{
printf ("\n--- CBmpFile::getCopy 06 \n");
unsigned char *ptrC;
unsigned char dummy;
unsigned char *pChar;
int redValue, greenValue, blueValue, grayValue;
dummy = '0';
ptrC = &dummy;
pChar = &dummy;
fseek(l_fileImageFile, 0L, SEEK_SET);
fseek(&l_fileOutputFile, 0L, SEEK_SET);
for(int i=0; i<50> Methode: Erzeuge Ausgabedatei im 8 Bit-Modus
/*
Erzeuge mit dieser Anweisung eine Kopie der Original Eingabe-Datei
for(int r=0; r<=l_iRows-1; r++)
{
for(int c=0; c<=l_iCols-1; c++)
{
fread(pChar, sizeof(char), 1, l_fileImageFile); // read Schmitt S.231
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
fread(pChar, sizeof(char), 1, l_fileImageFile);
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
fread(pChar, sizeof(char), 1, l_fileImageFile);
fwrite(pChar, sizeof(char), 1, &l_fileOutputFile);
}
}
*/
}
void CBmpFile::convertWriteFile(FILE *outputFile)
// Methode: Erzeuge Ausgabedatei im 8 Bit-Modus (Header und Farben ändern)
{
printf ("\n--- CBmpFile::convertWriteFile 07 \n");
int i=0;
int j,k,ell;
unsigned char *ptrC;
unsigned char dummy;
int redValue, greenValue, blueValue, alphaValue;
dummy = '0';
ptrC = &dummy;
/*---- Dateizeiger auf 54 Byte setzen für 24 bit BMP und
Dateizeiger wird auf 54+4*256 Byte gesetzt wegen Farbtabelle -----*/
fseek(outputFile, 54L, SEEK_SET);
// fseek Setzt Dateipositionszeiger.
// SEEK_SET setzt Dateipositionszeiger an den Dateianfang.
// SEEK_END setzt Dateipositionszeiger an das Dateiende.
// offset = n . Der Parameter offset gibt dabei die Anzahl Bytes an, um die
// der Dateipositionszeiger relativ zu basis (SEEK_SET, SEEK_CUR, SEEK_END)
// versetzt werden soll. (SEEK_CUR = Aktuelle Position der Datei)
// offset=OL wie rewind(Dateiname)
for( ell=0 ; ell < 4 ; ell++ )
{
for( k=0 ; k < 8 ; k++ )
{
for( j=0; j < 8 ; j++ )
{
*ptrC = 0; //Alpha - LookUpTable
fwrite(ptrC, sizeof(char), 1, outputFile);
*ptrC = ell*32; //Blau
fwrite(ptrC, sizeof(char), 1, outputFile);
*ptrC = k*32; //Grün
fwrite(ptrC, sizeof(char), 1, outputFile);
*ptrC = j*32; //Rot
fwrite(ptrC, sizeof(char), 1, outputFile);
i++;
}
}
}
printf("\n Ende Farbtabelle i = %d",i); // Testausgabe
/*----------- Farbinformationen der Originaldatei einlesen -----------*/
for(int r=0; r<=l_iRows-1; r++)
{
for(int c=0; c<l_iCols> Blau -----*/
fread(ptrC, sizeof(char), 1, l_fileImageFile); // read Schmitt S.231
blueValue = *ptrC;
/*----- Erstes Byte -> Grün -----*/
fread(ptrC, sizeof(char), 1, l_fileImageFile);
greenValue = *ptrC;
/*----- Erstes Byte -> Rot -----*/
fread(ptrC, sizeof(char), 1, l_fileImageFile);
redValue = *ptrC;
// Farbposition in der Look-Up-Table (Farbtabelle)
alphaValue = (int)(0.299*redValue + 0.587*greenValue + 0.114*blueValue);
*ptrC = alphaValue;
fwrite(ptrC, sizeof(char), 1, outputFile);
}
}
}
Mit folgendem Code, können Sie den Beitrag ganz bequem auf ihrer Homepage verlinken
Weitere Beiträge aus dem Forum 14. Info
Kostenlose bücher - gepostet von ravekev am Sonntag 08.10.2006
Klasusur Computer-Graphik - gepostet von timo am Samstag 14.07.2007
Programm vom Temme - gepostet von ravekev am Sonntag 13.05.2007
UltraStar - gepostet von ravekev am Montag 19.02.2007
Rede vom Nockherberg 07 - gepostet von Anonymous am Montag 12.03.2007
Bézier-Kurve - gepostet von timo am Dienstag 24.07.2007
Sorber-Verabschiedung - gepostet von ravekev am Mittwoch 19.09.2007
Ähnliche Beiträge wie "Projekt C++ / Computergraphik: MedianCut-Algorithmus"
Praktika Java / Computergraphik - timo (Samstag 14.07.2007)
Gauß-Algorithmus - OzzKaa (Sonntag 29.10.2006)