in imagecore/image/colorpalette.cpp [55:268]
static int computeHistogram(ImageRGBA* frameImage, RGBA* ccolors, double* colorPct, int numColors)
{
unsigned int width = frameImage->getWidth();
unsigned int height = frameImage->getHeight();
bool useHsv = numColors == 1;
int kHistSize = useHsv ? 16 : 24;
const int searchSizeX = useHsv ? 1 : 4;
const int searchSizeY = useHsv ? 2 : 1;
const int searchSizeZ = useHsv ? 4 : 1;
const int kHistPadding = max(searchSizeX, max(searchSizeY, searchSizeZ));
const int kHistTotalSize = kHistSize + kHistPadding * 2;
float* histogramAlloc = (float*)calloc(kHistTotalSize * kHistTotalSize * kHistTotalSize, sizeof(float));
float* histogram = histogramAlloc + (kHistPadding + kHistPadding * kHistTotalSize + kHistPadding * kHistTotalSize * kHistTotalSize);
float3* floatImage = (float3*)malloc(width * height * sizeof(float3));
unsigned int framePitch;
uint8_t* buffer = frameImage->lockRect(width, height, framePitch);
START_CLOCK(ColorConversionHistogram);
for( unsigned int y = 0; y < height; y++ ) {
for( unsigned int x = 0; x < width; x++ ) {
const RGBA* rgba = (RGBA*)(&buffer[y * framePitch + x * 4]);
if (useHsv) {
floatImage[y * width + x] = ColorSpace::srgbToHsv(ColorSpace::byteToFloat(*rgba));
} else {
floatImage[y * width + x] = ColorSpace::srgbToLab(ColorSpace::byteToFloat(*rgba));
}
if( rgba->a > 128 ) {
const float3& c = floatImage[y * width + x];
unsigned int hx = clamp(0, kHistSize - 1, (int)(c.x * (float)kHistSize));
unsigned int hy = clamp(0, kHistSize - 1, (int)(c.y * (float)kHistSize));
unsigned int hz = clamp(0, kHistSize - 1, (int)(c.z * (float)kHistSize));
int idx = INDEX_HIST(hx, hy, hz);
float saturation = sqrtf(((c.y - 0.5f) * (c.y - 0.5f) + (c.z - 0.5f) * (c.z - 0.5f)));
float luminance = fabs(c.x - 0.5f);
histogram[idx] += useHsv ? 1.0f : fmaxf(luminance, saturation);
}
}
}
END_CLOCK(ColorConversionHistogram);
START_CLOCK(Search);
std::vector<int> vAreaMaxX;
std::vector<int> vAreaMaxY;
std::vector<int> vAreaMaxZ;
for( int i = 0; i < numColors; i++ ) {
int areaMaxX = 0;
int areaMaxY = 0;
int areaMaxZ = 0;
float maxAreaSum = 0.0f;
for( int x = 0; x < kHistSize; x++ ) {
for( int y = 0; y < kHistSize; y++ ) {
for( int z = 0; z < kHistSize; z++ ) {
float sum = 0;
for( int sx = -searchSizeX; sx <= searchSizeX; sx++ ) {
int wrappedX = x + sx;
if (useHsv) {
// Hue in HSV is circular, so we wrap instead of clamp.
if( wrappedX >= kHistSize ) {
wrappedX = wrappedX - kHistSize;
} else if( wrappedX < 0 ) {
wrappedX = kHistSize + wrappedX - 1;
}
}
for( int sy = -searchSizeY; sy <= searchSizeY; sy++ ) {
int index = INDEX_HIST(wrappedX, y + sy, z);
for( int sz = -searchSizeZ; sz <= searchSizeZ; sz++ ) {
sum += histogram[index + sz];
}
}
}
if( sum > maxAreaSum ) {
areaMaxX = x;
areaMaxY = y;
areaMaxZ = z;
maxAreaSum = sum;
}
}
}
}
if( maxAreaSum > 0.0f ) {
vAreaMaxX.push_back(areaMaxX);
vAreaMaxY.push_back(areaMaxY);
vAreaMaxZ.push_back(areaMaxZ);
if( numColors > 1 ) {
for( int sx = -searchSizeX; sx <= searchSizeX; sx++ ) {
int wrappedX = areaMaxX + sx;
if( useHsv ) {
// Hue in HSV is circular, so we wrap instead of clamp.
if( wrappedX >= kHistSize ) {
wrappedX = wrappedX - kHistSize;
} else if( wrappedX < 0 ) {
wrappedX = kHistSize + wrappedX - 1;
}
}
for( int sy = -searchSizeY; sy <= searchSizeY; sy++ ) {
int index = INDEX_HIST(wrappedX, areaMaxY + sy, areaMaxZ);
for( int sz = -searchSizeZ; sz <= searchSizeZ; sz++ ) {
histogram[index + sz] = -fabs(histogram[index + sz]);
}
}
}
}
}
}
END_CLOCK(Search);
START_CLOCK(Sort);
int numOutColors = 0;
WeightedColor* weightedColors = (WeightedColor*)malloc(numColors * sizeof(WeightedColor));
SECURE_ASSERT(vAreaMaxX.size() == vAreaMaxY.size() && vAreaMaxX.size() == vAreaMaxZ.size());
for( int m = 0; m < min((int)vAreaMaxX.size(), numColors); m++ ) {
int areaMaxX = vAreaMaxX[m];
int areaMaxY = vAreaMaxY[m];
int areaMaxZ = vAreaMaxZ[m];
std::vector<unsigned char> rDim;
std::vector<unsigned char> gDim;
std::vector<unsigned char> bDim;
std::vector<RGBA> colors;
int rAvg = 0;
int gAvg = 0;
int bAvg = 0;
int mmax = 0;
for( unsigned int y = 0; y < height; y++ ) {
for( unsigned int x = 0; x < width; x++ ) {
const RGBA* rgba = (RGBA*)(&buffer[y * framePitch + x * 4]);
const float3& c = floatImage[y * width + x];
int hx = clamp(0, kHistSize - 1, (int)(c.x * (float)kHistSize));
int hy = clamp(0, kHistSize - 1, (int)(c.y * (float)kHistSize));
int hz = clamp(0, kHistSize - 1, (int)(c.z * (float)kHistSize));
if( (useHsv && rgba->a > 128 && (wrappedDist(hx, areaMaxX, kHistSize) <= searchSizeX && abs(hy - areaMaxY) <= searchSizeY && abs(hz - areaMaxZ) <= searchSizeZ))
|| (!useHsv && rgba->a > 128 && (abs(hx - areaMaxX) <= searchSizeX && abs(hy - areaMaxY) <= searchSizeY && abs(hz - areaMaxZ) <= searchSizeZ))) {
rAvg += rgba->r;
gAvg += rgba->g;
bAvg += rgba->b;
rDim.push_back(rgba->r);
gDim.push_back(rgba->g);
bDim.push_back(rgba->b);
colors.push_back(*rgba);
mmax++;
}
}
}
double pct = (double)colors.size() / (double)(width * height);
if( pct > 0.001f) {
std::sort(rDim.begin(), rDim.end());
std::sort(gDim.begin(), gDim.end());
std::sort(bDim.begin(), bDim.end());
int medianR = rDim.size() > 0 ? rDim.at(rDim.size() / 2) : 0;
int medianG = gDim.size() > 0 ? gDim.at(gDim.size() / 2) : 0;
int medianB = bDim.size() > 0 ? bDim.at(bDim.size() / 2) : 0;
RGBA outColor(0, 0, 0, 255);
int closestColorDist = 10000000;
for( unsigned i = 0; i < colors.size(); i++ ) {
const RGBA& c = colors.at(i);
float dr = c.r - medianR;
float dg = c.g - medianG;
float db = c.b - medianB;
float dist = (dr * dr) + (dg * dg) + (db * db);
if( dist < closestColorDist ) {
weightedColors[numOutColors].color = c;
weightedColors[numOutColors].pct = pct;
closestColorDist = dist;
if( dist == 0 ) {
break;
}
}
}
numOutColors++;
}
}
std::sort(weightedColors, weightedColors + numOutColors);
for( int i = 0; i < numOutColors; i++ ) {
ccolors[i] = weightedColors[numOutColors - i - 1].color;
colorPct[i] = weightedColors[numOutColors - i - 1].pct;
}
END_CLOCK(Sort);
free(weightedColors);
weightedColors = NULL;
free(floatImage);
floatImage = NULL;
free(histogramAlloc);
histogramAlloc = NULL;
return numOutColors;
}