9c5db4731eef30b81b1a2e73d42b045b29f2583c
1 /*
2 Copyright 2005, 2006 by Gerald Friedland, Kristian Jantz and Lars Knipping
4 Conversion to C++ for Inkscape by Bob Jamison
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
10 http://www.apache.org/licenses/LICENSE-2.0
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 */
18 #include "siox.h"
20 #include <math.h>
21 #include <stdarg.h>
22 #include <map>
25 namespace org
26 {
28 namespace siox
29 {
33 //########################################################################
34 //# C L A B
35 //########################################################################
37 static std::map<unsigned long, CieLab> clabLookupTable;
39 /**
40 * Convert integer A, R, G, B values into an pixel value.
41 */
42 static unsigned long getRGB(int a, int r, int g, int b)
43 {
44 if (a<0) a=0;
45 else if (a>255) a=255;
47 if (r<0) r=0;
48 else if (r>255) r=255;
50 if (g<0) g=0;
51 else if (g>255) g=255;
53 if (b<0) b=0;
54 else if (b>255) b=255;
56 return (a<<24)|(r<<16)|(g<<8)|b;
57 }
61 /**
62 * Convert float A, R, G, B values (0.0-1.0) into an pixel value.
63 */
64 static unsigned long getRGB(float a, float r, float g, float b)
65 {
66 return getRGB((int)(a * 256.0),
67 (int)(r * 256.0),
68 (int)(g * 256.0),
69 (int)(b * 256.0));
70 }
74 //#########################################
75 //# Root approximations for large speedup.
76 //# By njh!
77 //#########################################
78 static const int ROOT_TAB_SIZE = 16;
79 static float cbrt_table[ROOT_TAB_SIZE +1];
81 double CieLab::cbrt(double x)
82 {
83 double y = cbrt_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1]
84 y = (2.0 * y + x/(y*y))/3.0;
85 y = (2.0 * y + x/(y*y))/3.0; // polish twice
86 return y;
87 }
89 static float qn_table[ROOT_TAB_SIZE +1];
91 double CieLab::qnrt(double x)
92 {
93 double y = qn_table[int(x*ROOT_TAB_SIZE )]; // assuming x \in [0, 1]
94 double Y = y*y;
95 y = (4.0*y + x/(Y*Y))/5.0;
96 Y = y*y;
97 y = (4.0*y + x/(Y*Y))/5.0; // polish twice
98 return y;
99 }
101 double CieLab::pow24(double x)
102 {
103 double onetwo = x*qnrt(x);
104 return onetwo*onetwo;
105 }
108 static bool _clab_inited_ = false;
109 void CieLab::init()
110 {
111 if (!_clab_inited_)
112 {
113 cbrt_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.3333);
114 qn_table[0] = pow(float(1)/float(ROOT_TAB_SIZE*2), 0.2);
115 for(int i = 1; i < ROOT_TAB_SIZE +1; i++)
116 {
117 cbrt_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.3333);
118 qn_table[i] = pow(float(i)/float(ROOT_TAB_SIZE), 0.2);
119 }
120 _clab_inited_ = true;
121 }
122 }
126 /**
127 * Construct this CieLab from a packed-pixel ARGB value
128 */
129 CieLab::CieLab(unsigned long rgb)
130 {
131 init();
133 //First try looking up in the cache
134 std::map<unsigned long, CieLab>::iterator iter;
135 iter = clabLookupTable.find(rgb);
136 if (iter != clabLookupTable.end())
137 {
138 CieLab res = iter->second;
139 C = res.C;
140 L = res.L;
141 A = res.A;
142 B = res.B;
143 }
146 int ir = (rgb>>16) & 0xff;
147 int ig = (rgb>> 8) & 0xff;
148 int ib = (rgb ) & 0xff;
150 float fr = ((float)ir) / 255.0;
151 float fg = ((float)ig) / 255.0;
152 float fb = ((float)ib) / 255.0;
154 //printf("fr:%f fg:%f fb:%f\n", fr, fg, fb);
155 if (fr > 0.04045)
156 //fr = (float) pow((fr + 0.055) / 1.055, 2.4);
157 fr = (float) pow24((fr + 0.055) / 1.055);
158 else
159 fr = fr / 12.92;
161 if (fg > 0.04045)
162 //fg = (float) pow((fg + 0.055) / 1.055, 2.4);
163 fg = (float) pow24((fg + 0.055) / 1.055);
164 else
165 fg = fg / 12.92;
167 if (fb > 0.04045)
168 //fb = (float) pow((fb + 0.055) / 1.055, 2.4);
169 fb = (float) pow24((fb + 0.055) / 1.055);
170 else
171 fb = fb / 12.92;
173 fr = fr * 100.0;
174 fg = fg * 100.0;
175 fb = fb * 100.0;
177 // Use white = D65
178 float x = fr * 0.4124 + fg * 0.3576 + fb * 0.1805;
179 float y = fr * 0.2126 + fg * 0.7152 + fb * 0.0722;
180 float z = fr * 0.0193 + fg * 0.1192 + fb * 0.9505;
182 float vx = x / 95.047;
183 float vy = y / 100.000;
184 float vz = z / 108.883;
186 //printf("vx:%f vy:%f vz:%f\n", vx, vy, vz);
187 if (vx > 0.008856)
188 //vx = (float) pow(vx, 0.3333);
189 vx = (float) cbrt(vx);
190 else
191 vx = (7.787 * vx) + (16.0 / 116.0);
193 if (vy > 0.008856)
194 //vy = (float) pow(vy, 0.3333);
195 vy = (float) cbrt(vy);
196 else
197 vy = (7.787 * vy) + (16.0 / 116.0);
199 if (vz > 0.008856)
200 //vz = (float) pow(vz, 0.3333);
201 vz = (float) cbrt(vz);
202 else
203 vz = (7.787 * vz) + (16.0 / 116.0);
205 C = 0;
206 L = 116.0 * vy - 16.0;
207 A = 500.0 * (vx - vy);
208 B = 200.0 * (vy - vz);
210 // Cache for next time
211 clabLookupTable[rgb] = *this;
213 }
217 /**
218 * Return this CieLab's value a a packed-pixel ARGB value
219 */
220 unsigned long CieLab::toRGB()
221 {
222 float vy = (L + 16.0) / 116.0;
223 float vx = A / 500.0 + vy;
224 float vz = vy - B / 200.0;
226 float vx3 = vx * vx * vx;
227 float vy3 = vy * vy * vy;
228 float vz3 = vz * vz * vz;
230 if (vy3 > 0.008856)
231 vy = vy3;
232 else
233 vy = (vy - 16.0 / 116.0) / 7.787;
235 if (vx3 > 0.008856)
236 vx = vx3;
237 else
238 vx = (vx - 16.0 / 116.0) / 7.787;
240 if (vz3 > 0.008856)
241 vz = vz3;
242 else
243 vz = (vz - 16.0 / 116.0) / 7.787;
245 float x = 95.047 * vx; //use white = D65
246 float y = 100.000 * vy;
247 float z = 108.883 * vz;
249 vx = x / 100.0;
250 vy = y / 100.0;
251 vz = z / 100.0;
253 float vr =(float)(vx * 3.2406 + vy * -1.5372 + vz * -0.4986);
254 float vg =(float)(vx * -0.9689 + vy * 1.8758 + vz * 0.0415);
255 float vb =(float)(vx * 0.0557 + vy * -0.2040 + vz * 1.0570);
257 if (vr > 0.0031308)
258 vr = (float)(1.055 * pow(vr, (1.0 / 2.4)) - 0.055);
259 else
260 vr = 12.92 * vr;
262 if (vg > 0.0031308)
263 vg = (float)(1.055 * pow(vg, (1.0 / 2.4)) - 0.055);
264 else
265 vg = 12.92 * vg;
267 if (vb > 0.0031308)
268 vb = (float)(1.055 * pow(vb, (1.0 / 2.4)) - 0.055);
269 else
270 vb = 12.92 * vb;
272 return getRGB(0.0, vr, vg, vb);
273 }
276 /**
277 * Squared Euclidian distance between this and another color
278 */
279 float CieLab::diffSq(const CieLab &other)
280 {
281 float sum=0.0;
282 sum += (L - other.L) * (L - other.L);
283 sum += (A - other.A) * (A - other.A);
284 sum += (B - other.B) * (B - other.B);
285 return sum;
286 }
288 /**
289 * Computes squared euclidian distance in CieLab space for two colors
290 * given as RGB values.
291 */
292 float CieLab::diffSq(unsigned int rgb1, unsigned int rgb2)
293 {
294 CieLab c1(rgb1);
295 CieLab c2(rgb2);
296 float euclid = c1.diffSq(c2);
297 return euclid;
298 }
301 /**
302 * Computes squared euclidian distance in CieLab space for two colors
303 * given as RGB values.
304 */
305 float CieLab::diff(unsigned int rgb0, unsigned int rgb1)
306 {
307 return (float) sqrt(diffSq(rgb0, rgb1));
308 }
312 //########################################################################
313 //# T U P E L
314 //########################################################################
316 /**
317 * Helper class for storing the minimum distances to a cluster centroid
318 * in background and foreground and the index to the centroids in each
319 * signature for a given color.
320 */
321 class Tupel {
322 public:
324 Tupel()
325 {
326 minBgDist = 0.0f;
327 indexMinBg = 0;
328 minFgDist = 0.0f;
329 indexMinFg = 0;
330 }
331 Tupel(float minBgDistArg, long indexMinBgArg,
332 float minFgDistArg, long indexMinFgArg)
333 {
334 minBgDist = minBgDistArg;
335 indexMinBg = indexMinBgArg;
336 minFgDist = minFgDistArg;
337 indexMinFg = indexMinFgArg;
338 }
339 Tupel(const Tupel &other)
340 {
341 minBgDist = other.minBgDist;
342 indexMinBg = other.indexMinBg;
343 minFgDist = other.minFgDist;
344 indexMinFg = other.indexMinFg;
345 }
346 Tupel &operator=(const Tupel &other)
347 {
348 minBgDist = other.minBgDist;
349 indexMinBg = other.indexMinBg;
350 minFgDist = other.minFgDist;
351 indexMinFg = other.indexMinFg;
352 return *this;
353 }
354 virtual ~Tupel()
355 {}
357 float minBgDist;
358 long indexMinBg;
359 float minFgDist;
360 long indexMinFg;
362 };
366 //########################################################################
367 //# S I O X I M A G E
368 //########################################################################
370 /**
371 * Create an image with the given width and height
372 */
373 SioxImage::SioxImage(unsigned int widthArg, unsigned int heightArg)
374 {
375 init(width, height);
376 }
378 /**
379 * Copy constructor
380 */
381 SioxImage::SioxImage(const SioxImage &other)
382 {
383 pixdata = NULL;
384 cmdata = NULL;
385 assign(other);
386 }
388 /**
389 * Assignment
390 */
391 SioxImage &SioxImage::operator=(const SioxImage &other)
392 {
393 assign(other);
394 return *this;
395 }
398 /**
399 * Clean up after use.
400 */
401 SioxImage::~SioxImage()
402 {
403 if (pixdata) delete[] pixdata;
404 if (cmdata) delete[] cmdata;
405 }
407 /**
408 * Returns true if the previous operation on this image
409 * was successful, else false.
410 */
411 bool SioxImage::isValid()
412 {
413 return valid;
414 }
416 /**
417 * Sets whether an operation was successful, and whether
418 * this image should be considered a valid one.
419 * was successful, else false.
420 */
421 void SioxImage::setValid(bool val)
422 {
423 valid = val;
424 }
427 /**
428 * Set a pixel at the x,y coordinates to the given value.
429 * If the coordinates are out of range, do nothing.
430 */
431 void SioxImage::setPixel(unsigned int x,
432 unsigned int y,
433 unsigned int pixval)
434 {
435 if (x > width || y > height)
436 return;
437 unsigned long offset = width * y + x;
438 pixdata[offset] = pixval;
439 }
441 /**
442 * Set a pixel at the x,y coordinates to the given r, g, b values.
443 * If the coordinates are out of range, do nothing.
444 */
445 void SioxImage::setPixel(unsigned int x, unsigned int y,
446 unsigned int a,
447 unsigned int r,
448 unsigned int g,
449 unsigned int b)
450 {
451 if (x > width || y > height)
452 return;
453 unsigned long offset = width * y + x;
454 unsigned int pixval = ((a << 24) & 0xff000000) |
455 ((r << 16) & 0x00ff0000) |
456 ((g << 8) & 0x0000ff00) |
457 ((b ) & 0x000000ff);
458 pixdata[offset] = pixval;
459 }
463 /**
464 * Get a pixel at the x,y coordinates given. If
465 * the coordinates are out of range, return 0;
466 */
467 unsigned int SioxImage::getPixel(unsigned int x, unsigned int y)
468 {
469 if (x > width || y > height)
470 return 0L;
471 unsigned long offset = width * y + x;
472 return pixdata[offset];
473 }
475 /**
476 * Return the image data buffer
477 */
478 unsigned int *SioxImage::getImageData()
479 {
480 return pixdata;
481 }
483 /**
484 * Set a confidence value at the x,y coordinates to the given value.
485 * If the coordinates are out of range, do nothing.
486 */
487 void SioxImage::setConfidence(unsigned int x,
488 unsigned int y,
489 float confval)
490 {
491 if (x > width || y > height)
492 return;
493 unsigned long offset = width * y + x;
494 cmdata[offset] = confval;
495 }
497 /**
498 * Get a confidence valueat the x,y coordinates given. If
499 * the coordinates are out of range, return 0;
500 */
501 float SioxImage::getConfidence(unsigned int x, unsigned int y)
502 {
503 if (x > width || y > height)
504 return 0.0;
505 unsigned long offset = width * y + x;
506 return cmdata[offset];
507 }
509 /**
510 * Return the confidence data buffer
511 */
512 float *SioxImage::getConfidenceData()
513 {
514 return cmdata;
515 }
518 /**
519 * Return the width of this image
520 */
521 int SioxImage::getWidth()
522 {
523 return width;
524 }
526 /**
527 * Return the height of this image
528 */
529 int SioxImage::getHeight()
530 {
531 return height;
532 }
534 /**
535 * Initialize values. Used by constructors
536 */
537 void SioxImage::init(unsigned int widthArg, unsigned int heightArg)
538 {
539 valid = true;
540 width = widthArg;
541 height = heightArg;
542 imageSize = width * height;
543 pixdata = new unsigned int[imageSize];
544 cmdata = new float[imageSize];
545 for (unsigned long i=0 ; i<imageSize ; i++)
546 {
547 pixdata[i] = 0;
548 cmdata[i] = 0.0;
549 }
550 }
552 /**
553 * Assign values to that of another
554 */
555 void SioxImage::assign(const SioxImage &other)
556 {
557 if (pixdata) delete[] pixdata;
558 if (cmdata) delete[] cmdata;
559 valid = other.valid;
560 width = other.width;
561 height = other.height;
562 imageSize = width * height;
563 pixdata = new unsigned int[imageSize];
564 cmdata = new float[imageSize];
565 for (unsigned long i=0 ; i<imageSize ; i++)
566 {
567 pixdata[i] = other.pixdata[i];
568 cmdata[i] = other.cmdata[i];
569 }
570 }
573 /**
574 * Write the image to a PPM file
575 */
576 bool SioxImage::writePPM(const std::string fileName)
577 {
579 FILE *f = fopen(fileName.c_str(), "wb");
580 if (!f)
581 return false;
583 fprintf(f, "P6 %d %d 255\n", width, height);
585 for (unsigned int y=0 ; y<height; y++)
586 {
587 for (unsigned int x=0 ; x<width ; x++)
588 {
589 unsigned int rgb = getPixel(x, y);
590 //unsigned int alpha = (rgb>>24) & 0xff;
591 unsigned int r = ((rgb>>16) & 0xff);
592 unsigned int g = ((rgb>> 8) & 0xff);
593 unsigned int b = ((rgb ) & 0xff);
594 fputc((unsigned char) r, f);
595 fputc((unsigned char) g, f);
596 fputc((unsigned char) b, f);
597 }
598 }
599 fclose(f);
600 return true;
601 }
604 #ifdef HAVE_GLIB
606 /**
607 * Create an image from a GdkPixbuf
608 */
609 SioxImage::SioxImage(GdkPixbuf *buf)
610 {
611 if (!buf)
612 return;
614 unsigned int width = gdk_pixbuf_get_width(buf);
615 unsigned int height = gdk_pixbuf_get_height(buf);
616 init(width, height); //DO THIS NOW!!
619 guchar *pixldata = gdk_pixbuf_get_pixels(buf);
620 int rowstride = gdk_pixbuf_get_rowstride(buf);
621 int n_channels = gdk_pixbuf_get_n_channels(buf);
623 //### Fill in the cells with RGB values
624 int row = 0;
625 for (unsigned int y=0 ; y<height ; y++)
626 {
627 guchar *p = pixldata + row;
628 for (unsigned int x=0 ; x<width ; x++)
629 {
630 int r = (int)p[0];
631 int g = (int)p[1];
632 int b = (int)p[2];
633 int alpha = (int)p[3];
635 setPixel(x, y, alpha, r, g, b);
636 p += n_channels;
637 }
638 row += rowstride;
639 }
641 }
644 /**
645 * Create a GdkPixbuf from this image
646 */
647 GdkPixbuf *SioxImage::getGdkPixbuf()
648 {
649 bool has_alpha = true;
650 int n_channels = has_alpha ? 4 : 3;
652 guchar *pixdata = (guchar *)
653 malloc(sizeof(guchar) * width * height * n_channels);
654 if (!pixdata)
655 return NULL;
657 int rowstride = width * n_channels;
659 GdkPixbuf *buf = gdk_pixbuf_new_from_data(pixdata,
660 GDK_COLORSPACE_RGB,
661 has_alpha, 8, width, height,
662 rowstride, NULL, NULL);
664 //### Fill in the cells with RGB values
665 int row = 0;
666 for (unsigned int y=0 ; y < height ; y++)
667 {
668 guchar *p = pixdata + row;
669 for (unsigned x=0 ; x < width ; x++)
670 {
671 unsigned int rgb = getPixel(x, y);
672 p[0] = (rgb >> 16) & 0xff;//r
673 p[1] = (rgb >> 8) & 0xff;//g
674 p[2] = (rgb ) & 0xff;//b
675 if ( n_channels > 3 )
676 {
677 p[3] = (rgb >> 24) & 0xff;//a
678 }
679 p += n_channels;
680 }
681 row += rowstride;
682 }
684 return buf;
685 }
687 #endif /* GLIB */
692 //########################################################################
693 //# S I O X
694 //########################################################################
696 //##############
697 //## PUBLIC
698 //##############
700 /**
701 * Confidence corresponding to a certain foreground region (equals one).
702 */
703 const float Siox::CERTAIN_FOREGROUND_CONFIDENCE=1.0f;
705 /**
706 * Confidence for a region likely being foreground.
707 */
708 const float Siox::FOREGROUND_CONFIDENCE=0.8f;
710 /**
711 * Confidence for foreground or background type being equally likely.
712 */
713 const float Siox::UNKNOWN_REGION_CONFIDENCE=0.5f;
715 /**
716 * Confidence for a region likely being background.
717 */
718 const float Siox::BACKGROUND_CONFIDENCE=0.1f;
720 /**
721 * Confidence corresponding to a certain background reagion (equals zero).
722 */
723 const float Siox::CERTAIN_BACKGROUND_CONFIDENCE=0.0f;
725 /**
726 * Construct a Siox engine
727 */
728 Siox::Siox()
729 {
730 sioxObserver = NULL;
731 init();
732 }
734 /**
735 * Construct a Siox engine
736 */
737 Siox::Siox(SioxObserver *observer)
738 {
739 init();
740 sioxObserver = observer;
741 }
744 /**
745 *
746 */
747 Siox::~Siox()
748 {
749 cleanup();
750 }
753 /**
754 * Error logging
755 */
756 void Siox::error(char *fmt, ...)
757 {
758 char msgbuf[256];
759 va_list args;
760 va_start(args, fmt);
761 vsnprintf(msgbuf, 255, fmt, args);
762 va_end(args) ;
763 #ifdef HAVE_GLIB
764 g_warning("Siox error: %s\n", msgbuf);
765 #else
766 fprintf(stderr, "Siox error: %s\n", msgbuf);
767 #endif
768 }
770 /**
771 * Trace logging
772 */
773 void Siox::trace(char *fmt, ...)
774 {
775 char msgbuf[256];
776 va_list args;
777 va_start(args, fmt);
778 vsnprintf(msgbuf, 255, fmt, args);
779 va_end(args) ;
780 #ifdef HAVE_GLIB
781 g_message("Siox: %s\n", msgbuf);
782 #else
783 fprintf(stdout, "Siox: %s\n", msgbuf);
784 #endif
785 }
789 /**
790 * Progress reporting
791 */
792 bool Siox::progressReport(float percentCompleted)
793 {
794 if (!sioxObserver)
795 return true;
797 bool ret = sioxObserver->progress(percentCompleted);
799 if (!ret)
800 {
801 trace("User selected abort");
802 keepGoing = false;
803 }
805 return ret;
806 }
811 /**
812 * Extract the foreground of the original image, according
813 * to the values in the confidence matrix.
814 */
815 SioxImage Siox::extractForeground(const SioxImage &originalImage,
816 unsigned int backgroundFillColor)
817 {
818 trace("### Start");
820 init();
821 keepGoing = true;
823 SioxImage workImage = originalImage;
825 //# fetch some info from the image
826 width = workImage.getWidth();
827 height = workImage.getHeight();
828 pixelCount = width * height;
829 image = workImage.getImageData();
830 cm = workImage.getConfidenceData();
831 labelField = new int[pixelCount];
833 trace("### Creating signatures");
835 //#### create color signatures
836 std::vector<CieLab> knownBg;
837 std::vector<CieLab> knownFg;
838 CieLab *imageClab = new CieLab[pixelCount];
839 for (unsigned long i=0 ; i<pixelCount ; i++)
840 {
841 float conf = cm[i];
842 unsigned int pix = image[i];
843 CieLab lab(pix);
844 imageClab[i] = lab;
845 if (conf <= BACKGROUND_CONFIDENCE)
846 knownBg.push_back(lab);
847 else if (conf >= FOREGROUND_CONFIDENCE)
848 knownFg.push_back(lab);
849 }
851 /*
852 std::vector<CieLab> imageClab;
853 for (int y = 0 ; y < workImage.getHeight() ; y++)
854 for (int x = 0 ; x < workImage.getWidth() ; x++)
855 {
856 float cm = workImage.getConfidence(x, y);
857 unsigned int pix = workImage.getPixel(x, y);
858 CieLab lab(pix);
859 imageClab.push_back(lab);
860 if (cm <= BACKGROUND_CONFIDENCE)
861 knownBg.push_back(lab); //note: uses CieLab(rgb)
862 else if (cm >= FOREGROUND_CONFIDENCE)
863 knownFg.push_back(lab);
864 }
865 */
867 if (!progressReport(10.0))
868 {
869 error("User aborted");
870 workImage.setValid(false);
871 delete[] imageClab;
872 delete[] labelField;
873 return workImage;
874 }
876 trace("knownBg:%d knownFg:%d", knownBg.size(), knownFg.size());
879 std::vector<CieLab> bgSignature ;
880 if (!colorSignature(knownBg, bgSignature, 3))
881 {
882 error("Could not create background signature");
883 workImage.setValid(false);
884 delete[] imageClab;
885 delete[] labelField;
886 return workImage;
887 }
889 if (!progressReport(30.0))
890 {
891 error("User aborted");
892 workImage.setValid(false);
893 delete[] imageClab;
894 delete[] labelField;
895 return workImage;
896 }
899 std::vector<CieLab> fgSignature ;
900 if (!colorSignature(knownFg, fgSignature, 3))
901 {
902 error("Could not create foreground signature");
903 workImage.setValid(false);
904 delete[] imageClab;
905 delete[] labelField;
906 return workImage;
907 }
909 //trace("### bgSignature:%d", bgSignature.size());
911 if (bgSignature.size() < 1)
912 {
913 // segmentation impossible
914 error("Signature size is < 1. Segmentation is impossible");
915 workImage.setValid(false);
916 delete[] imageClab;
917 delete[] labelField;
918 return workImage;
919 }
921 if (!progressReport(30.0))
922 {
923 error("User aborted");
924 workImage.setValid(false);
925 delete[] imageClab;
926 delete[] labelField;
927 return workImage;
928 }
931 // classify using color signatures,
932 // classification cached in hashmap for drb and speedup purposes
933 trace("### Analyzing image");
935 std::map<unsigned int, Tupel> hs;
937 unsigned int progressResolution = pixelCount / 10;
939 for (unsigned int i=0; i<pixelCount; i++)
940 {
941 if (i % progressResolution == 0)
942 {
943 float progress =
944 30.0 + 60.0 * (float)i / (float)pixelCount;
945 //trace("### progress:%f", progress);
946 if (!progressReport(progress))
947 {
948 error("User aborted");
949 delete[] imageClab;
950 delete[] labelField;
951 workImage.setValid(false);
952 return workImage;
953 }
954 }
956 if (cm[i] >= FOREGROUND_CONFIDENCE)
957 {
958 cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
959 }
960 else if (cm[i] <= BACKGROUND_CONFIDENCE)
961 {
962 cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
963 }
964 else // somewhere in between
965 {
966 bool isBackground = true;
967 std::map<unsigned int, Tupel>::iterator iter = hs.find(i);
968 if (iter != hs.end()) //found
969 {
970 Tupel tupel = iter->second;
971 isBackground = tupel.minBgDist <= tupel.minFgDist;
972 }
973 else
974 {
975 CieLab lab = imageClab[i];
976 float minBg = lab.diffSq(bgSignature[0]);
977 int minIndex = 0;
978 for (unsigned int j=1; j<bgSignature.size() ; j++)
979 {
980 float d = lab.diffSq(bgSignature[j]);
981 if (d<minBg)
982 {
983 minBg = d;
984 minIndex = j;
985 }
986 }
987 Tupel tupel(0.0f, 0, 0.0f, 0);
988 tupel.minBgDist = minBg;
989 tupel.indexMinBg = minIndex;
990 float minFg = 1.0e6f;
991 minIndex = -1;
992 for (unsigned int j = 0 ; j < fgSignature.size() ; j++)
993 {
994 float d = lab.diffSq(fgSignature[j]);
995 if (d < minFg)
996 {
997 minFg = d;
998 minIndex = j;
999 }
1000 }
1001 tupel.minFgDist = minFg;
1002 tupel.indexMinFg = minIndex;
1003 if (fgSignature.size() == 0)
1004 {
1005 isBackground = (minBg <= clusterSize);
1006 // remove next line to force behaviour of old algorithm
1007 //error("foreground signature does not exist");
1008 //delete[] labelField;
1009 //workImage.setValid(false);
1010 //return workImage;
1011 }
1012 else
1013 {
1014 isBackground = minBg < minFg;
1015 }
1016 hs[image[i]] = tupel;
1017 }
1019 if (isBackground)
1020 cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
1021 else
1022 cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
1023 }
1024 }
1027 delete[] imageClab;
1029 trace("### postProcessing");
1032 //#### postprocessing
1033 smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
1034 normalizeMatrix(cm, pixelCount);
1035 erode(cm, width, height);
1036 keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.0/*sizeFactorToKeep*/);
1038 //for (int i=0; i < 2/*smoothness*/; i++)
1039 // smooth(cm, width, height, 0.333f, 0.333f, 0.333f); // average
1041 normalizeMatrix(cm, pixelCount);
1043 for (unsigned int i=0; i < pixelCount; i++)
1044 {
1045 if (cm[i] >= UNKNOWN_REGION_CONFIDENCE)
1046 cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
1047 else
1048 cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
1049 }
1051 keepOnlyLargeComponents(UNKNOWN_REGION_CONFIDENCE, 1.5/*sizeFactorToKeep*/);
1052 fillColorRegions();
1053 dilate(cm, width, height);
1055 if (!progressReport(100.0))
1056 {
1057 error("User aborted");
1058 delete[] labelField;
1059 workImage.setValid(false);
1060 return workImage;
1061 }
1064 //#### We are done. Now clear everything but the background
1065 for (unsigned long i = 0; i<pixelCount ; i++)
1066 {
1067 float conf = cm[i];
1068 if (conf < FOREGROUND_CONFIDENCE)
1069 image[i] = backgroundFillColor;
1070 }
1072 delete[] labelField;
1074 trace("### Done");
1075 keepGoing = false;
1076 return workImage;
1077 }
1081 //##############
1082 //## PRIVATE
1083 //##############
1085 /**
1086 * Initialize the Siox engine to its 'pristine' state.
1087 * Performed at the beginning of extractForeground().
1088 */
1089 void Siox::init()
1090 {
1091 limits[0] = 0.64f;
1092 limits[1] = 1.28f;
1093 limits[2] = 2.56f;
1095 float negLimits[3];
1096 negLimits[0] = -limits[0];
1097 negLimits[1] = -limits[1];
1098 negLimits[2] = -limits[2];
1100 clusterSize = sqrEuclidianDist(limits, 3, negLimits);
1101 }
1104 /**
1105 * Clean up any debris from processing.
1106 */
1107 void Siox::cleanup()
1108 {
1109 }
1114 /**
1115 * Stage 1 of the color signature work. 'dims' will be either
1116 * 2 for grays, or 3 for colors
1117 */
1118 void Siox::colorSignatureStage1(CieLab *points,
1119 unsigned int leftBase,
1120 unsigned int rightBase,
1121 unsigned int recursionDepth,
1122 unsigned int *clusterCount,
1123 const unsigned int dims)
1124 {
1126 unsigned int currentDim = recursionDepth % dims;
1127 CieLab point = points[leftBase];
1128 float min = point(currentDim);
1129 float max = min;
1131 for (unsigned int i = leftBase + 1; i < rightBase ; i++)
1132 {
1133 point = points[i];
1134 float curval = point(currentDim);
1135 if (curval < min) min = curval;
1136 if (curval > max) max = curval;
1137 }
1139 //Do the Rubner-rule split (sounds like a dance)
1140 if (max - min > limits[currentDim])
1141 {
1142 float pivotPoint = (min + max) / 2.0; //average
1143 unsigned int left = leftBase;
1144 unsigned int right = rightBase - 1;
1146 //# partition points according to the dimension
1147 while (true)
1148 {
1149 while ( true )
1150 {
1151 point = points[left];
1152 if (point(currentDim) > pivotPoint)
1153 break;
1154 left++;
1155 }
1156 while ( true )
1157 {
1158 point = points[right];
1159 if (point(currentDim) <= pivotPoint)
1160 break;
1161 right--;
1162 }
1164 if (left > right)
1165 break;
1167 point = points[left];
1168 points[left] = points[right];
1169 points[right] = point;
1171 left++;
1172 right--;
1173 }
1175 //# Recurse and create sub-trees
1176 colorSignatureStage1(points, leftBase, left,
1177 recursionDepth + 1, clusterCount, dims);
1178 colorSignatureStage1(points, left, rightBase,
1179 recursionDepth + 1, clusterCount, dims);
1180 }
1181 else
1182 {
1183 //create a leaf
1184 CieLab newpoint;
1186 newpoint.C = rightBase - leftBase;
1188 for (; leftBase < rightBase ; leftBase++)
1189 {
1190 newpoint.add(points[leftBase]);
1191 }
1193 //printf("clusters:%d\n", *clusters);
1195 if (newpoint.C != 0)
1196 newpoint.mul(1.0 / (float)newpoint.C);
1197 points[*clusterCount] = newpoint;
1198 (*clusterCount)++;
1199 }
1200 }
1204 /**
1205 * Stage 2 of the color signature work
1206 */
1207 void Siox::colorSignatureStage2(CieLab *points,
1208 unsigned int leftBase,
1209 unsigned int rightBase,
1210 unsigned int recursionDepth,
1211 unsigned int *clusterCount,
1212 const float threshold,
1213 const unsigned int dims)
1214 {
1217 unsigned int currentDim = recursionDepth % dims;
1218 CieLab point = points[leftBase];
1219 float min = point(currentDim);
1220 float max = min;
1222 for (unsigned int i = leftBase+ 1; i < rightBase; i++)
1223 {
1224 point = points[i];
1225 float curval = point(currentDim);
1226 if (curval < min) min = curval;
1227 if (curval > max) max = curval;
1228 }
1230 //Do the Rubner-rule split (sounds like a dance)
1231 if (max - min > limits[currentDim])
1232 {
1233 float pivotPoint = (min + max) / 2.0; //average
1234 unsigned int left = leftBase;
1235 unsigned int right = rightBase - 1;
1237 //# partition points according to the dimension
1238 while (true)
1239 {
1240 while ( true )
1241 {
1242 point = points[left];
1243 if (point(currentDim) > pivotPoint)
1244 break;
1245 left++;
1246 }
1247 while ( true )
1248 {
1249 point = points[right];
1250 if (point(currentDim) <= pivotPoint)
1251 break;
1252 right--;
1253 }
1255 if (left > right)
1256 break;
1258 point = points[left];
1259 points[left] = points[right];
1260 points[right] = point;
1262 left++;
1263 right--;
1264 }
1266 //# Recurse and create sub-trees
1267 colorSignatureStage2(points, leftBase, left,
1268 recursionDepth + 1, clusterCount, threshold, dims);
1269 colorSignatureStage2(points, left, rightBase,
1270 recursionDepth + 1, clusterCount, threshold, dims);
1271 }
1272 else
1273 {
1274 //### Create a leaf
1275 unsigned int sum = 0;
1276 for (unsigned int i = leftBase; i < rightBase; i++)
1277 sum += points[i].C;
1279 if ((float)sum >= threshold)
1280 {
1281 float scale = (float)(rightBase - leftBase);
1282 CieLab newpoint;
1284 for (; leftBase < rightBase; leftBase++)
1285 newpoint.add(points[leftBase]);
1287 if (scale != 0.0)
1288 newpoint.mul(1.0 / scale);
1289 points[*clusterCount] = newpoint;
1290 (*clusterCount)++;
1291 }
1292 }
1293 }
1297 /**
1298 * Main color signature method
1299 */
1300 bool Siox::colorSignature(const std::vector<CieLab> &inputVec,
1301 std::vector<CieLab> &result,
1302 const unsigned int dims)
1303 {
1305 unsigned int length = inputVec.size();
1307 if (length < 1) // no error. just don't do anything
1308 return true;
1310 CieLab *input = (CieLab *) malloc(length * sizeof(CieLab));
1312 if (!input)
1313 {
1314 error("Could not allocate buffer for signature");
1315 return false;
1316 }
1317 for (unsigned int i=0 ; i < length ; i++)
1318 input[i] = inputVec[i];
1320 unsigned int stage1length = 0;
1321 colorSignatureStage1(input, 0, length, 0,
1322 &stage1length, dims);
1324 unsigned int stage2length = 0;
1325 colorSignatureStage2(input, 0, stage1length, 0,
1326 &stage2length, length * 0.001, dims);
1328 result.clear();
1329 for (unsigned int i=0 ; i < stage2length ; i++)
1330 result.push_back(input[i]);
1332 free(input);
1334 return true;
1335 }
1339 /**
1340 *
1341 */
1342 void Siox::keepOnlyLargeComponents(float threshold,
1343 double sizeFactorToKeep)
1344 {
1345 for (unsigned long idx = 0 ; idx<pixelCount ; idx++)
1346 labelField[idx] = -1;
1348 int curlabel = 0;
1349 int maxregion= 0;
1350 int maxblob = 0;
1352 // slow but easy to understand:
1353 std::vector<int> labelSizes;
1354 for (unsigned long i=0 ; i<pixelCount ; i++)
1355 {
1356 int regionCount = 0;
1357 if (labelField[i] == -1 && cm[i] >= threshold)
1358 {
1359 regionCount = depthFirstSearch(i, threshold, curlabel++);
1360 labelSizes.push_back(regionCount);
1361 }
1363 if (regionCount>maxregion)
1364 {
1365 maxregion = regionCount;
1366 maxblob = curlabel-1;
1367 }
1368 }
1370 for (unsigned int i=0 ; i<pixelCount ; i++)
1371 {
1372 if (labelField[i] != -1)
1373 {
1374 // remove if the component is to small
1375 if (labelSizes[labelField[i]] * sizeFactorToKeep < maxregion)
1376 cm[i] = CERTAIN_BACKGROUND_CONFIDENCE;
1378 // add maxblob always to foreground
1379 if (labelField[i] == maxblob)
1380 cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
1381 }
1382 }
1384 }
1388 int Siox::depthFirstSearch(int startPos,
1389 float threshold, int curLabel)
1390 {
1391 // stores positions of labeled pixels, where the neighbours
1392 // should still be checked for processing:
1394 //trace("startPos:%d threshold:%f curLabel:%d",
1395 // startPos, threshold, curLabel);
1397 std::vector<int> pixelsToVisit;
1398 int componentSize = 0;
1400 if (labelField[startPos]==-1 && cm[startPos]>=threshold)
1401 {
1402 labelField[startPos] = curLabel;
1403 componentSize++;
1404 pixelsToVisit.push_back(startPos);
1405 }
1408 while (pixelsToVisit.size() > 0)
1409 {
1410 int pos = pixelsToVisit[pixelsToVisit.size() - 1];
1411 pixelsToVisit.erase(pixelsToVisit.end() - 1);
1412 unsigned int x = pos % width;
1413 unsigned int y = pos / width;
1415 // check all four neighbours
1416 int left = pos - 1;
1417 if (((int)x)-1>=0 && labelField[left]==-1 && cm[left]>=threshold)
1418 {
1419 labelField[left]=curLabel;
1420 componentSize++;
1421 pixelsToVisit.push_back(left);
1422 }
1424 int right = pos + 1;
1425 if (x+1 < width && labelField[right]==-1 && cm[right]>=threshold)
1426 {
1427 labelField[right]=curLabel;
1428 componentSize++;
1429 pixelsToVisit.push_back(right);
1430 }
1432 int top = pos - width;
1433 if (((int)y)-1>=0 && labelField[top]==-1 && cm[top]>=threshold)
1434 {
1435 labelField[top]=curLabel;
1436 componentSize++;
1437 pixelsToVisit.push_back(top);
1438 }
1440 int bottom = pos + width;
1441 if (y+1 < height && labelField[bottom]==-1
1442 && cm[bottom]>=threshold)
1443 {
1444 labelField[bottom]=curLabel;
1445 componentSize++;
1446 pixelsToVisit.push_back(bottom);
1447 }
1449 }
1450 return componentSize;
1451 }
1455 /**
1456 *
1457 */
1458 void Siox::fillColorRegions()
1459 {
1460 for (unsigned long idx = 0 ; idx<pixelCount ; idx++)
1461 labelField[idx] = -1;
1463 //int maxRegion=0; // unused now
1464 std::vector<int> pixelsToVisit;
1465 for (unsigned long i=0; i<pixelCount; i++)
1466 { // for all pixels
1467 if (labelField[i]!=-1 || cm[i]<UNKNOWN_REGION_CONFIDENCE)
1468 {
1469 continue; // already visited or bg
1470 }
1472 unsigned int origColor = image[i];
1473 unsigned long curLabel = i+1;
1474 labelField[i] = curLabel;
1475 cm[i] = CERTAIN_FOREGROUND_CONFIDENCE;
1477 // int componentSize = 1;
1478 pixelsToVisit.push_back(i);
1479 // depth first search to fill region
1480 while (pixelsToVisit.size() > 0)
1481 {
1482 int pos = pixelsToVisit[pixelsToVisit.size() - 1];
1483 pixelsToVisit.erase(pixelsToVisit.end() - 1);
1484 unsigned int x=pos % width;
1485 unsigned int y=pos / width;
1486 // check all four neighbours
1487 int left = pos-1;
1488 if (((int)x)-1 >= 0 && labelField[left] == -1
1489 && CieLab::diff(image[left], origColor)<1.0)
1490 {
1491 labelField[left]=curLabel;
1492 cm[left]=CERTAIN_FOREGROUND_CONFIDENCE;
1493 // ++componentSize;
1494 pixelsToVisit.push_back(left);
1495 }
1496 int right = pos+1;
1497 if (x+1 < width && labelField[right]==-1
1498 && CieLab::diff(image[right], origColor)<1.0)
1499 {
1500 labelField[right]=curLabel;
1501 cm[right]=CERTAIN_FOREGROUND_CONFIDENCE;
1502 // ++componentSize;
1503 pixelsToVisit.push_back(right);
1504 }
1505 int top = pos - width;
1506 if (((int)y)-1>=0 && labelField[top]==-1
1507 && CieLab::diff(image[top], origColor)<1.0)
1508 {
1509 labelField[top]=curLabel;
1510 cm[top]=CERTAIN_FOREGROUND_CONFIDENCE;
1511 // ++componentSize;
1512 pixelsToVisit.push_back(top);
1513 }
1514 int bottom = pos + width;
1515 if (y+1 < height && labelField[bottom]==-1
1516 && CieLab::diff(image[bottom], origColor)<1.0)
1517 {
1518 labelField[bottom]=curLabel;
1519 cm[bottom]=CERTAIN_FOREGROUND_CONFIDENCE;
1520 // ++componentSize;
1521 pixelsToVisit.push_back(bottom);
1522 }
1523 }
1524 //if (componentSize>maxRegion) {
1525 // maxRegion=componentSize;
1526 //}
1527 }
1528 }
1533 /**
1534 * Applies the morphological dilate operator.
1535 *
1536 * Can be used to close small holes in the given confidence matrix.
1537 */
1538 void Siox::dilate(float *cm, int xres, int yres)
1539 {
1541 for (int y=0; y<yres; y++)
1542 {
1543 for (int x=0; x<xres-1; x++)
1544 {
1545 int idx=(y*xres)+x;
1546 if (cm[idx+1]>cm[idx])
1547 cm[idx]=cm[idx+1];
1548 }
1549 }
1551 for (int y=0; y<yres; y++)
1552 {
1553 for (int x=xres-1; x>=1; x--)
1554 {
1555 int idx=(y*xres)+x;
1556 if (cm[idx-1]>cm[idx])
1557 cm[idx]=cm[idx-1];
1558 }
1559 }
1561 for (int y=0; y<yres-1; y++)
1562 {
1563 for (int x=0; x<xres; x++)
1564 {
1565 int idx=(y*xres)+x;
1566 if (cm[((y+1)*xres)+x] > cm[idx])
1567 cm[idx]=cm[((y+1)*xres)+x];
1568 }
1569 }
1571 for (int y=yres-1; y>=1; y--)
1572 {
1573 for (int x=0; x<xres; x++)
1574 {
1575 int idx=(y*xres)+x;
1576 if (cm[((y-1)*xres)+x] > cm[idx])
1577 cm[idx]=cm[((y-1)*xres)+x];
1578 }
1579 }
1580 }
1582 /**
1583 * Applies the morphological erode operator.
1584 */
1585 void Siox::erode(float *cm, int xres, int yres)
1586 {
1587 for (int y=0; y<yres; y++)
1588 {
1589 for (int x=0; x<xres-1; x++)
1590 {
1591 int idx=(y*xres)+x;
1592 if (cm[idx+1] < cm[idx])
1593 cm[idx]=cm[idx+1];
1594 }
1595 }
1596 for (int y=0; y<yres; y++)
1597 {
1598 for (int x=xres-1; x>=1; x--)
1599 {
1600 int idx=(y*xres)+x;
1601 if (cm[idx-1] < cm[idx])
1602 cm[idx]=cm[idx-1];
1603 }
1604 }
1605 for (int y=0; y<yres-1; y++)
1606 {
1607 for (int x=0; x<xres; x++)
1608 {
1609 int idx=(y*xres)+x;
1610 if (cm[((y+1)*xres)+x] < cm[idx])
1611 cm[idx]=cm[((y+1)*xres)+x];
1612 }
1613 }
1614 for (int y=yres-1; y>=1; y--)
1615 {
1616 for (int x=0; x<xres; x++)
1617 {
1618 int idx=(y*xres)+x;
1619 if (cm[((y-1)*xres)+x] < cm[idx])
1620 cm[idx]=cm[((y-1)*xres)+x];
1621 }
1622 }
1623 }
1628 /**
1629 * Normalizes the matrix to values to [0..1].
1630 */
1631 void Siox::normalizeMatrix(float *cm, int cmSize)
1632 {
1633 float max= -1000000.0f;
1634 for (int i=0; i<cmSize; i++)
1635 if (max<cm[i] > max)
1636 max=cm[i];
1638 if (max<=0.0 || max==1.0)
1639 return;
1641 float alpha=1.00f/max;
1642 premultiplyMatrix(alpha, cm, cmSize);
1643 }
1645 /**
1646 * Multiplies matrix with the given scalar.
1647 */
1648 void Siox::premultiplyMatrix(float alpha, float *cm, int cmSize)
1649 {
1650 for (int i=0; i<cmSize; i++)
1651 cm[i]=alpha*cm[i];
1652 }
1654 /**
1655 * Blurs confidence matrix with a given symmetrically weighted kernel.
1656 *
1657 * In the standard case confidence matrix entries are between 0...1 and
1658 * the weight factors sum up to 1.
1659 */
1660 void Siox::smooth(float *cm, int xres, int yres,
1661 float f1, float f2, float f3)
1662 {
1663 for (int y=0; y<yres; y++)
1664 {
1665 for (int x=0; x<xres-2; x++)
1666 {
1667 int idx=(y*xres)+x;
1668 cm[idx]=f1*cm[idx]+f2*cm[idx+1]+f3*cm[idx+2];
1669 }
1670 }
1671 for (int y=0; y<yres; y++)
1672 {
1673 for (int x=xres-1; x>=2; x--)
1674 {
1675 int idx=(y*xres)+x;
1676 cm[idx]=f3*cm[idx-2]+f2*cm[idx-1]+f1*cm[idx];
1677 }
1678 }
1679 for (int y=0; y<yres-2; y++)
1680 {
1681 for (int x=0; x<xres; x++)
1682 {
1683 int idx=(y*xres)+x;
1684 cm[idx]=f1*cm[idx]+f2*cm[((y+1)*xres)+x]+f3*cm[((y+2)*xres)+x];
1685 }
1686 }
1687 for (int y=yres-1; y>=2; y--)
1688 {
1689 for (int x=0; x<xres; x++)
1690 {
1691 int idx=(y*xres)+x;
1692 cm[idx]=f3*cm[((y-2)*xres)+x]+f2*cm[((y-1)*xres)+x]+f1*cm[idx];
1693 }
1694 }
1695 }
1697 /**
1698 * Squared Euclidian distance of p and q.
1699 */
1700 float Siox::sqrEuclidianDist(float *p, int pSize, float *q)
1701 {
1702 float sum=0.0;
1703 for (int i=0; i<pSize; i++)
1704 {
1705 float v = p[i] - q[i];
1706 sum += v*v;
1707 }
1708 return sum;
1709 }
1716 } // namespace siox
1717 } // namespace org
1719 //########################################################################
1720 //# E N D O F F I L E
1721 //########################################################################