00001
00002 /***************************************************************************
00003  *  histogram.cpp - Implementation of the histogram
00004  *
00005  *  Generated: Tue Jun 14 11:11:29 2005
00006  *  Copyright  2005  Tim Niemueller [www.niemueller.de]
00007  *             2008  Daniel Beck
00008  *
00009  ****************************************************************************/
00010
00011 /*  This program is free software; you can redistribute it and/or modify
00012  *  it under the terms of the GNU General Public License as published by
00013  *  the Free Software Foundation; either version 2 of the License, or
00014  *  (at your option) any later version. A runtime exception applies to
00015  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00016  *
00017  *  This program is distributed in the hope that it will be useful,
00018  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00019  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00020  *  GNU Library General Public License for more details.
00021  *
00022  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00023  */
00024
00025 #include <fvutils/statistical/histogram.h>
00026 #include <fvutils/statistical/histogram_file.h>
00027 #include <fvutils/statistical/histogram_block.h>
00028
00029 #include <core/exceptions/software.h>
00030
00031 #include <iostream>
00032 #include <fstream>
00033 #include <vector>
00034 #include <cstdlib>
00035 #include <algorithm>
00036 #include <cstring>
00037
00038 using namespace std;
00039 using namespace fawkes;
00040
00041 
00042 /** @class Histogram <fvutils/statistical/histogram.h>
00043  * Histogram.
00044  * Histrogram with 2D or 3D coordinates for buckets.
00045  */
00046 
00047 /** Constructor.
00048  * @param width width of histogram plane
00049  * @param height height of histogram plane
00050  * @param depth depth of the histogram
00051  * @param num_undos number of possible undos
00052  */
00053 Histogram::Histogram(unsigned int width, unsigned int height,
00054                      unsigned int depth, unsigned int num_undos)
00055 {
00056   if ( (width == 0) || (height == 0) || (depth == 0) ) {
00057     throw Exception("Width or height or depth is zero.");
00058   }
00059
00060   this->width        = width;
00061   this->height       = height;
00062   this->depth        = depth;
00063   this->undo_num     = num_undos;
00064   this->undo_current = 0;
00065
00066   if (depth == 1) {
00067     dimension = 2;
00068   } else {
00069     dimension = 3;
00070   }
00071
00072   histogram_block = new HistogramBlock(FIREVISION_HISTOGRAM_TYPE_32, H_UNKNOWN,
00073                                        width, height, depth);
00074   histogram = (unsigned int*) histogram_block->data_ptr();
00075
00076   histogram_size = width * height * depth * sizeof(unsigned int);
00077
00078   undo_overlay = (unsigned int **)malloc(undo_num * sizeof(unsigned int *));
00079   for (unsigned int i = 0; i < undo_num; ++i) {
00080     undo_overlay[i] = (unsigned int *)malloc(histogram_size);
00081   }
00082
00083   undo_num_vals = (unsigned int *)malloc(undo_num * sizeof(unsigned int));
00084
00085   reset();
00086 }
00087
00088 
00089 /** Constructor. 
00090  * @param block construct a histogram from the given histogram block
00091  */
00092 Histogram::Histogram(HistogramBlock* block)
00093 {
00094   width = block->width();
00095   height = block->height();
00096   depth = block->depth();
00097
00098   if (depth == 1) {
00099     dimension = 2;
00100   } else {
00101     dimension = 3;
00102   }
00103
00104   undo_num = 1;
00105   undo_current = 0;
00106
00107   histogram_block = block;
00108   histogram = (unsigned int*) histogram_block->data_ptr();
00109   histogram_size = width * height * depth * sizeof(unsigned int);
00110
00111   undo_overlay = (unsigned int **)malloc(undo_num * sizeof(unsigned int *));
00112   for (unsigned int i = 0; i < undo_num; ++i) {
00113     undo_overlay[i] = (unsigned int *)malloc(histogram_size);
00114   }
00115
00116   undo_num_vals = (unsigned int *)malloc(undo_num * sizeof(unsigned int));
00117 }
00118
00119 
00120 /** Destructor. */
00121 Histogram::~Histogram()
00122 {
00123   delete histogram_block;
00124   for (unsigned int i = 0; i < undo_num; ++i) {
00125     free(undo_overlay[i]);
00126   }
00127   free(undo_overlay);
00128   free(undo_num_vals);
00129 }
00130
00131 
00132 /** Add point.
00133  * @param p point
00134  */
00135 void
00136 Histogram::operator+=(point_t *p)
00137 {
00138   if ( dimension != 2 ) {
00139     throw Exception("Trying to add 2-dim data to 3-dim histogram");
00140   }
00141
00142   if (p->x >= width || p->y >= height) {
00143     throw OutOfBoundsException("Point lies outside of histogram range");
00144   }
00145
00146   unsigned int index = p->y * width + p->x;
00147   histogram[index] += 1;
00148   undo_overlay[undo_current][index] += 1;
00149   ++number_of_values;
00150   undo_num_vals[undo_current] += 1;
00151 }
00152
00153 
00154 /** Add point.
00155  * @param p point
00156  */
00157 void
00158 Histogram::operator+=(point_t p)
00159 {
00160   if ( dimension != 2 ) {
00161     throw Exception("Trying to add 2-dim data to 3-dim histogram");
00162   }
00163
00164   if (p.x >= width || p.y >= height) {
00165     throw OutOfBoundsException("Point lies outside of histogram range");
00166   }
00167
00168   unsigned int index = p.y * width + p.x;
00169   histogram[index] += 1;
00170   undo_overlay[undo_current][index] += 1;
00171   ++number_of_values;
00172   undo_num_vals[undo_current] += 1;
00173 }
00174
00175 
00176 /** Get histogram data buffer.
00177  * @return histogram
00178  */
00179 unsigned int *
00180 Histogram::get_histogram()
00181 {
00182   return histogram;
00183 }
00184
00185 
00186 /** Obtain the histogram block of this histogram.
00187  * @return pointer to the histogram block
00188  */
00189 HistogramBlock *
00190 Histogram::get_histogram_block()
00191 {
00192   return histogram_block;
00193 }
00194
00195 
00196 /** Obtain dimensions of the histogram.
00197  * @param width reference to the variable where the width is stored
00198  * @param height reference to the variable where the height is stored
00199  * @param depth reference to the variable where the depth is stored
00200  */
00201 void
00202 Histogram::get_dimensions(unsigned int& width, unsigned int& height, unsigned int& depth)
00203 {
00204   width = this->width;
00205   height = this->height;
00206   depth = this->depth;
00207 }
00208
00209 
00210 /** Get value from histogram.
00211  * @param x x coordinate in histogram plane
00212  * @param y y coordinate in histogram plane
00213  */
00214 unsigned int
00215 Histogram::get_value(unsigned int x, unsigned int y)
00216 {
00217   return histogram_block->get_value(x, y);
00218 }
00219
00220 
00221 /** Get value from histogram.
00222  * @param x x coordinate in histogram plane
00223  * @param y y coordinate in histogram plane
00224  * @param z z coordinate in the histogram
00225  */
00226 unsigned int
00227 Histogram::get_value(unsigned int x, unsigned int y, unsigned int z)
00228 {
00229   return histogram_block->get_value(x, y, z);
00230 }
00231
00232 
00233 /** Set value in histogram.
00234  * @param x x coordinate in histogram plane
00235  * @param y y coordinate in histogram plane
00236  * @param value value
00237  */
00238 void
00239 Histogram::set_value(unsigned int x, unsigned int y, unsigned int value)
00240 {
00241   unsigned int old_value = histogram_block->get_value(x, y);
00242   histogram_block->set_value(x, y, value);
00243   number_of_values += value - old_value;
00244
00245   unsigned int index = y * width + x;
00246   if ( value > old_value ) {
00247     // The value got incremented, add to overlay
00248     undo_overlay[undo_current][index] += value - old_value;
00249   } else {
00250     if ( (old_value - value) < undo_overlay[undo_current][index] ) {
00251       undo_overlay[undo_current][index] -= (old_value - value);
00252     } else {
00253       // We cannot handle values smaller than the original value, this is
00254       // due to choosing unsigned int as datatype, right now this should suffice
00255       undo_overlay[undo_current][index] = 0;
00256     }
00257   }
00258 }
00259
00260 
00261 /** Set value in histogram.
00262  * @param x x coordinate in histogram plane
00263  * @param y y coordinate in histogram plane
00264  * @param z z coordinate in the histogram
00265  * @param value value
00266  */
00267 void
00268 Histogram::set_value(unsigned int x, unsigned int y, unsigned int z, unsigned int value)
00269 {
00270   unsigned int old_value = histogram_block->get_value(x, y, z);
00271   histogram_block->set_value(x, y, z, value);
00272
00273   number_of_values += value - old_value;
00274   unsigned int index = z * width * height + y * width + x;
00275   if ( value > old_value ) {
00276     // The value got incremented, add to overlay
00277     undo_overlay[undo_current][index] += value - old_value;
00278   } else {
00279     if ( (old_value - value) < undo_overlay[undo_current][index] ) {
00280       undo_overlay[undo_current][index] -= (old_value - value);
00281     } else {
00282       // We cannot handle values smaller than the original value, this is
00283       // due to choosing unsigned int as datatype, right now this should suffice
00284       undo_overlay[undo_current][index] = 0;
00285     }
00286   }
00287 }
00288
00289 
00290 /** Increase the value of the histogram at given position.
00291  * @param x x coordinate in the histogram
00292  * @param y y coordinate in the histogram
00293  * @param z z coordinate in the histogram
00294  */
00295 void
00296 Histogram::inc_value(unsigned int x, unsigned int y, unsigned int z)
00297 {
00298   unsigned int old_value = histogram_block->get_value(x, y, z);
00299   histogram_block->set_value(x, y, z, ++old_value);
00300
00301   ++number_of_values;
00302
00303   unsigned int index = z * width * height + y * width + x;
00304   undo_overlay[undo_current][index] = 1;
00305 }
00306
00307 
00308 /** Add value to value in histogram at given location.
00309  * @param x x coordinate in histogram
00310  * @param y y coordinate in histogram
00311  * @param z z coordinate in histogram
00312  * @param value the value to add
00313  */
00314 void
00315 Histogram::add(unsigned int x, unsigned int y, unsigned int z, unsigned int value)
00316 {
00317   unsigned int cur_value = histogram_block->get_value(x, y, z);
00318   histogram_block->set_value(x, y, z, cur_value + value);
00319
00320   number_of_values += value;
00321
00322   unsigned int index = z * width * height + y * width + x;
00323   undo_overlay[undo_current][index] = value;
00324 }
00325
00326 
00327 /** Substract value from value in histogram at given location.
00328  * @param x x coordinate in histogram
00329  * @param y y coordinate in histogram
00330  * @param z z coordinate in histogram
00331  * @param value the value to substract
00332  */
00333 void
00334 Histogram::sub(unsigned int x, unsigned int y, unsigned int z, unsigned int value)
00335 {
00336   unsigned int cur_value = histogram_block->get_value(x, y, z);
00337   if (value < cur_value) {
00338     set_value(x, y, z, cur_value - value);
00339   } else {
00340     set_value(x, y, z, 0);
00341   }
00342
00343   number_of_values -= value;
00344
00345   unsigned int index = z * width * height + y * width + x;
00346   if ( value < undo_overlay[undo_current][index] )
00347     {
00348       undo_overlay[undo_current][index] -= value;
00349     }
00350   else
00351     {
00352       undo_overlay[undo_current][index] = 0;
00353     }
00354 }
00355
00356 
00357 /** Reset histogram. */
00358 void
00359 Histogram::reset()
00360 {
00361   histogram_block->reset();
00362   //  memset(histogram, 0, histogram_size);
00363   number_of_values = 0;
00364   for (unsigned int i = 0; i < undo_num; ++i) {
00365     switch_undo( i );
00366     reset_undo();
00367   }
00368   switch_undo( 0 );
00369 }
00370
00371 
00372 /** Print to stream.
00373  * @param s stream
00374  */
00375 void
00376 Histogram::print_to_stream(std::ostream &s)
00377 {
00378   for (unsigned int z = 0; z < depth; ++z) {
00379     for (unsigned int y = 0; y < height; ++y) {
00380       for (unsigned int x = 0; x < width; ++x) {
00381 //      cout << histogram[z * width * height + y * width + x] << " ";
00382         cout << histogram_block->get_value(x, y, z) << " ";
00383       }
00384     }
00385     cout << endl;
00386   }
00387   cout << endl;
00388 }
00389
00390 
00391 /** Save to file.
00392  * @param filename file name to save to
00393  * @param formatted_output one value per line
00394  */
00395 void
00396 Histogram::save(const char *filename, bool formatted_output)
00397 {
00398   HistogramFile histogram_file;
00399   histogram_file.set_owns_blocks(false);
00400   histogram_file.add_histogram_block(histogram_block);
00401   histogram_file.write(filename);
00402
00403   cout << "Histogram: Saved histogram in file \"" << filename << "\"." << endl;
00404 }
00405
00406 
00407 /** Load from file.
00408  * @param filename file name to read from
00409  */
00410 bool
00411 Histogram::load(const char *filename)
00412 {
00413   HistogramFile histogram_file;
00414   histogram_file.read(filename);
00415
00416   if ( histogram_file.num_blocks() != 1 )
00417     {
00418       printf("load() aborted: file contains more than one histogram");
00419       return false;
00420     }
00421
00422   histogram_block = (HistogramBlock*) histogram_file.blocks().front();
00423   histogram = (unsigned int*) histogram_block->data_ptr();
00424   histogram_size = width * height * depth * sizeof(unsigned int);
00425
00426   for (unsigned int i = 0; i < undo_num; ++i) {
00427     free(undo_overlay[i]);
00428   }
00429   free(undo_overlay);
00430
00431   undo_overlay = (unsigned int **)malloc(undo_num * sizeof(unsigned int *));
00432   for (unsigned int i = 0; i < undo_num; ++i) {
00433     undo_overlay[i] = (unsigned int *)malloc(histogram_size);
00434   }
00435
00436   return true;
00437 }
00438
00439 
00440 /** Reset undo. */
00441 void
00442 Histogram::reset_undo()
00443 {
00444   memset(undo_overlay[undo_current], 0, histogram_size);
00445   undo_num_vals[undo_current] = 0;
00446 }
00447
00448 
00449 /** Undo. */
00450 void
00451 Histogram::undo()
00452 {
00453   for (unsigned int z = 0; z < depth; ++z) {
00454     for (unsigned int y = 0; y < height; ++y) {
00455       for (unsigned int x = 0; x < width; ++x) {
00456         unsigned int index = z * width * height + y * width + x;
00457         histogram[index] -= undo_overlay[undo_current][index];
00458       }
00459     }
00460   }
00461   number_of_values -= undo_num_vals[undo_current];
00462   reset_undo();
00463 }
00464
00465 
00466 /** Switch undo to another undo buffer.
00467  * @param undo_id switch to buffer with this ID
00468  * @return returns current undo buffer ID
00469  */
00470 unsigned int
00471 Histogram::switch_undo( unsigned int undo_id )
00472 {
00473   unsigned int undo_last = undo_current;
00474
00475   if (undo_id >= undo_num) {
00476     cout << "Histogram::resetUndo: ID out of range" << endl;
00477   } else {
00478     undo_current = undo_id;
00479   }
00480
00481   return undo_last;
00482 }
00483
00484 
00485 /** Get number of undos.
00486  * @return number of undos
00487  */
00488 unsigned int
00489 Histogram::get_num_undos()
00490 {
00491   return undo_num;
00492 }
00493
00494 
00495 /** Get median of all values.
00496  * @return median
00497  */
00498 unsigned int
00499 Histogram::get_median()
00500 {
00501   vector< unsigned int > *values = new vector< unsigned int >( width * height * depth);
00502
00503   values->clear();
00504   for (unsigned int z = 0; z < depth; ++z) {
00505     for (unsigned int y = 0; y < height; ++y) {
00506       for (unsigned int x = 0; x < width; ++x) {
00507         values->push_back( histogram_block->get_value(x, y, z) );
00508       }
00509     }
00510   }
00511
00512   sort(values->begin(), values->end());
00513
00514   unsigned int median = values->at( values->size() / 2 );
00515
00516   delete values;
00517
00518   return median;
00519 }
00520
00521 
00522 /** Get average of all values.
00523  * @return average
00524  */
00525 unsigned int
00526 Histogram::get_average()
00527 {
00528   unsigned int sum = 0;
00529   unsigned int num = 0;
00530   for (unsigned int z = 0; z < depth; ++z) {
00531     for (unsigned int y = 0; y < height; ++y) {
00532       for (unsigned int x = 0; x < width; ++x) {
00533         if ( histogram[z * width * height + y * width + x ] ) {
00534           sum += histogram_block->get_value(x, y, z);
00535           num++;
00536         }
00537       }
00538     }
00539   }
00540
00541   return (sum / num);
00542 }
00543
00544 
00545 /** Get sum of all values.
00546  * @return sum of values
00547  */
00548 unsigned int
00549 Histogram::get_sum() const
00550 {
00551   unsigned int sum = 0;
00552   for (unsigned int z = 0; z < depth; ++z) {
00553     for (unsigned int y = 0; y < height; ++y) {
00554       for (unsigned int x = 0; x < width; ++x) {
00555         if ( histogram[z * width * height + y * width + x ] ) {
00556           sum += histogram_block->get_value(x, y, z);
00557         }
00558       }
00559     }
00560   }
00561
00562   return sum;
00563 }