From fba8dd39307b922bb440f2755e3901b80d0c3889 Mon Sep 17 00:00:00 2001 From: Aaron Spike Date: Tue, 13 Jun 2006 01:43:48 +0000 Subject: patch [ 1503865 ] Siox performance patch (bzr r1208) --- src/trace/siox.cpp | 245 +++++++++++++++++++++++++++++++++++------------------ 1 file changed, 164 insertions(+), 81 deletions(-) (limited to 'src/trace/siox.cpp') diff --git a/src/trace/siox.cpp b/src/trace/siox.cpp index b0632567c..9c5db4731 100644 --- a/src/trace/siox.cpp +++ b/src/trace/siox.cpp @@ -34,7 +34,7 @@ namespace siox //# C L A B //######################################################################## -static std::map clabLookupTable; +static std::map clabLookupTable; /** * Convert integer A, R, G, B values into an pixel value. @@ -71,17 +71,71 @@ static unsigned long getRGB(float a, float r, float g, float b) +//######################################### +//# Root approximations for large speedup. +//# By njh! +//######################################### +static const int ROOT_TAB_SIZE = 16; +static float cbrt_table[ROOT_TAB_SIZE +1]; + +double CieLab::cbrt(double x) +{ + double y = cbrt_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1] + y = (2.0 * y + x/(y*y))/3.0; + y = (2.0 * y + x/(y*y))/3.0; // polish twice + return y; +} + +static float qn_table[ROOT_TAB_SIZE +1]; + +double CieLab::qnrt(double x) +{ + double y = qn_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1] + double Y = y*y; + y = (4.0*y + x/(Y*Y))/5.0; + Y = y*y; + y = (4.0*y + x/(Y*Y))/5.0; // polish twice + return y; +} + +double CieLab::pow24(double x) +{ + double onetwo = x*qnrt(x); + return onetwo*onetwo; +} + + +static bool _clab_inited_ = false; +void CieLab::init() +{ + if (!_clab_inited_) + { + cbrt_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.3333); + qn_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.2); + for(int i = 1; i < ROOT_TAB_SIZE +1; i++) + { + cbrt_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.3333); + qn_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.2); + } + _clab_inited_ = true; + } +} + + + /** - * Construct this CLAB from a packed-pixel ARGB value + * Construct this CieLab from a packed-pixel ARGB value */ -CLAB::CLAB(unsigned long rgb) +CieLab::CieLab(unsigned long rgb) { + init(); + //First try looking up in the cache - std::map::iterator iter; + std::map::iterator iter; iter = clabLookupTable.find(rgb); if (iter != clabLookupTable.end()) { - CLAB res = iter->second; + CieLab res = iter->second; C = res.C; L = res.L; A = res.A; @@ -97,18 +151,22 @@ CLAB::CLAB(unsigned long rgb) float fg = ((float)ig) / 255.0; float fb = ((float)ib) / 255.0; + //printf("fr:%f fg:%f fb:%f\n", fr, fg, fb); if (fr > 0.04045) - fr = (float) pow((fr + 0.055) / 1.055, 2.4); + //fr = (float) pow((fr + 0.055) / 1.055, 2.4); + fr = (float) pow24((fr + 0.055) / 1.055); else fr = fr / 12.92; if (fg > 0.04045) - fg = (float) pow((fg + 0.055) / 1.055, 2.4); + //fg = (float) pow((fg + 0.055) / 1.055, 2.4); + fg = (float) pow24((fg + 0.055) / 1.055); else fg = fg / 12.92; if (fb > 0.04045) - fb = (float) pow((fb + 0.055) / 1.055, 2.4); + //fb = (float) pow((fb + 0.055) / 1.055, 2.4); + fb = (float) pow24((fb + 0.055) / 1.055); else fb = fb / 12.92; @@ -125,18 +183,22 @@ CLAB::CLAB(unsigned long rgb) float vy = y / 100.000; float vz = z / 108.883; + //printf("vx:%f vy:%f vz:%f\n", vx, vy, vz); if (vx > 0.008856) - vx = (float) pow(vx, 0.3333); + //vx = (float) pow(vx, 0.3333); + vx = (float) cbrt(vx); else vx = (7.787 * vx) + (16.0 / 116.0); if (vy > 0.008856) - vy = (float) pow(vy, 0.3333); + //vy = (float) pow(vy, 0.3333); + vy = (float) cbrt(vy); else vy = (7.787 * vy) + (16.0 / 116.0); if (vz > 0.008856) - vz = (float) pow(vz, 0.3333); + //vz = (float) pow(vz, 0.3333); + vz = (float) cbrt(vz); else vz = (7.787 * vz) + (16.0 / 116.0); @@ -153,9 +215,9 @@ CLAB::CLAB(unsigned long rgb) /** - * Return this CLAB's value a a packed-pixel ARGB value + * Return this CieLab's value a a packed-pixel ARGB value */ -unsigned long CLAB::toRGB() +unsigned long CieLab::toRGB() { float vy = (L + 16.0) / 116.0; float vx = A / 500.0 + vy; @@ -212,31 +274,41 @@ unsigned long CLAB::toRGB() /** - * Computes squared euclidian distance in CLAB space for two colors + * Squared Euclidian distance between this and another color + */ +float CieLab::diffSq(const CieLab &other) +{ + float sum=0.0; + sum += (L - other.L) * (L - other.L); + sum += (A - other.A) * (A - other.A); + sum += (B - other.B) * (B - other.B); + return sum; +} + +/** + * Computes squared euclidian distance in CieLab space for two colors * given as RGB values. */ -float CLAB::diffSq(unsigned int rgb1, unsigned int rgb2) +float CieLab::diffSq(unsigned int rgb1, unsigned int rgb2) { - CLAB c1(rgb1); - CLAB c2(rgb2); - float euclid=0.0f; - euclid += (c1.L - c2.L) * (c1.L - c2.L); - euclid += (c1.A - c2.A) * (c1.A - c2.A); - euclid += (c1.B - c2.B) * (c1.B - c2.B); + CieLab c1(rgb1); + CieLab c2(rgb2); + float euclid = c1.diffSq(c2); return euclid; } /** - * Computes squared euclidian distance in CLAB space for two colors + * Computes squared euclidian distance in CieLab space for two colors * given as RGB values. */ -float CLAB::diff(unsigned int rgb0, unsigned int rgb1) +float CieLab::diff(unsigned int rgb0, unsigned int rgb1) { return (float) sqrt(diffSq(rgb0, rgb1)); } + //######################################################################## //# T U P E L //######################################################################## @@ -743,6 +815,8 @@ bool Siox::progressReport(float percentCompleted) SioxImage Siox::extractForeground(const SioxImage &originalImage, unsigned int backgroundFillColor) { + trace("### Start"); + init(); keepGoing = true; @@ -759,26 +833,42 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, trace("### Creating signatures"); //#### create color signatures - std::vector knownBg; - std::vector knownFg; - std::vector imageClab; + std::vector knownBg; + std::vector knownFg; + CieLab *imageClab = new CieLab[pixelCount]; + for (unsigned long i=0 ; i= FOREGROUND_CONFIDENCE) + knownFg.push_back(lab); + } + + /* + std::vector imageClab; for (int y = 0 ; y < workImage.getHeight() ; y++) for (int x = 0 ; x < workImage.getWidth() ; x++) { float cm = workImage.getConfidence(x, y); unsigned int pix = workImage.getPixel(x, y); - CLAB lab(pix); + CieLab lab(pix); imageClab.push_back(lab); if (cm <= BACKGROUND_CONFIDENCE) - knownBg.push_back(lab); //note: uses CLAB(rgb) + knownBg.push_back(lab); //note: uses CieLab(rgb) else if (cm >= FOREGROUND_CONFIDENCE) knownFg.push_back(lab); } + */ if (!progressReport(10.0)) { error("User aborted"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } @@ -786,11 +876,12 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, trace("knownBg:%d knownFg:%d", knownBg.size(), knownFg.size()); - std::vector bgSignature ; + std::vector bgSignature ; if (!colorSignature(knownBg, bgSignature, 3)) { error("Could not create background signature"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } @@ -799,16 +890,18 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, { error("User aborted"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } - std::vector fgSignature ; + std::vector fgSignature ; if (!colorSignature(knownFg, fgSignature, 3)) { error("Could not create foreground signature"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } @@ -820,6 +913,7 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, // segmentation impossible error("Signature size is < 1. Segmentation is impossible"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } @@ -828,6 +922,7 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, { error("User aborted"); workImage.setValid(false); + delete[] imageClab; delete[] labelField; return workImage; } @@ -835,6 +930,8 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, // classify using color signatures, // classification cached in hashmap for drb and speedup purposes + trace("### Analyzing image"); + std::map hs; unsigned int progressResolution = pixelCount / 10; @@ -844,10 +941,12 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, if (i % progressResolution == 0) { float progress = - 30.0 + 60.0 * (float)i / (float)progressResolution; + 30.0 + 60.0 * (float)i / (float)pixelCount; + //trace("### progress:%f", progress); if (!progressReport(progress)) { error("User aborted"); + delete[] imageClab; delete[] labelField; workImage.setValid(false); return workImage; @@ -868,17 +967,17 @@ SioxImage Siox::extractForeground(const SioxImage &originalImage, std::map::iterator iter = hs.find(i); if (iter != hs.end()) //found { - Tupel tupel = iter->second; + Tupel tupel = iter->second; isBackground = tupel.minBgDist <= tupel.minFgDist; } else { - CLAB lab = imageClab[i]; - float minBg = sqrEuclidianDist(lab, bgSignature[0]); - int minIndex=0; + CieLab lab = imageClab[i]; + float minBg = lab.diffSq(bgSignature[0]); + int minIndex = 0; for (unsigned int j=1; j= threshold) { float scale = (float)(rightBase - leftBase); - CLAB newpoint; + CieLab newpoint; for (; leftBase < rightBase; leftBase++) newpoint.add(points[leftBase]); @@ -1200,8 +1297,8 @@ void Siox::colorSignatureStage2(CLAB *points, /** * Main color signature method */ -bool Siox::colorSignature(const std::vector &inputVec, - std::vector &result, +bool Siox::colorSignature(const std::vector &inputVec, + std::vector &result, const unsigned int dims) { @@ -1210,7 +1307,7 @@ bool Siox::colorSignature(const std::vector &inputVec, if (length < 1) // no error. just don't do anything return true; - CLAB *input = (CLAB *) malloc(length * sizeof(CLAB)); + CieLab *input = (CieLab *) malloc(length * sizeof(CieLab)); if (!input) { @@ -1389,7 +1486,7 @@ void Siox::fillColorRegions() // check all four neighbours int left = pos-1; if (((int)x)-1 >= 0 && labelField[left] == -1 - && CLAB::diff(image[left], origColor)<1.0) + && CieLab::diff(image[left], origColor)<1.0) { labelField[left]=curLabel; cm[left]=CERTAIN_FOREGROUND_CONFIDENCE; @@ -1398,7 +1495,7 @@ void Siox::fillColorRegions() } int right = pos+1; if (x+1 < width && labelField[right]==-1 - && CLAB::diff(image[right], origColor)<1.0) + && CieLab::diff(image[right], origColor)<1.0) { labelField[right]=curLabel; cm[right]=CERTAIN_FOREGROUND_CONFIDENCE; @@ -1407,7 +1504,7 @@ void Siox::fillColorRegions() } int top = pos - width; if (((int)y)-1>=0 && labelField[top]==-1 - && CLAB::diff(image[top], origColor)<1.0) + && CieLab::diff(image[top], origColor)<1.0) { labelField[top]=curLabel; cm[top]=CERTAIN_FOREGROUND_CONFIDENCE; @@ -1416,7 +1513,7 @@ void Siox::fillColorRegions() } int bottom = pos + width; if (y+1 < height && labelField[bottom]==-1 - && CLAB::diff(image[bottom], origColor)<1.0) + && CieLab::diff(image[bottom], origColor)<1.0) { labelField[bottom]=curLabel; cm[bottom]=CERTAIN_FOREGROUND_CONFIDENCE; @@ -1611,20 +1708,6 @@ float Siox::sqrEuclidianDist(float *p, int pSize, float *q) return sum; } -/** - * Squared Euclidian distance of p and q. - */ -float Siox::sqrEuclidianDist(const CLAB &p, const CLAB &q) -{ - float sum=0; - sum += (p.L - q.L) * (p.L - q.L); - sum += (p.A - q.A) * (p.A - q.A); - sum += (p.B - q.B) * (p.B - q.B); - return sum; -} - - - -- cgit v1.2.3