Download code

Jump to: navigation, search

Back to Median_cut_algorithm_(C_Plus_Plus)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

median_cut.h

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Median_cut_algorithm_(C_Plus_Plus)?oldid=19175
14 */
15 
16 #ifndef _MEDIAN_CUT_H_
17 #include <list>
18 const int NUM_DIMENSIONS = 3;
19 
20 struct Point
21 {
22     unsigned char x[NUM_DIMENSIONS];
23 };
24 
25 class Block
26 {
27     Point minCorner, maxCorner;
28     Point* points;
29     int pointsLength;
30 public:
31     Block(Point* points, int pointsLength);
32     Point * getPoints();
33     int numPoints() const;
34     int longestSideIndex() const;
35     int longestSideLength() const;
36     bool operator<(const Block& rhs) const;
37     void shrink();
38 private:
39     template <typename T>
40     static T min(const T a, const T b)
41     {
42         if (a < b)
43             return a;
44         else
45             return b;
46     }
47 
48     template <typename T>
49     static T max(const T a, const T b)
50     {
51         if (a > b)
52             return a;
53         else
54             return b;
55     }
56 };
57 template <int index>
58 class CoordinatePointComparator
59 {
60 public:
61     bool operator()(Point left, Point right)
62     {
63         return left.x[index] < right.x[index];
64     }
65 };
66 std::list<Point> medianCut(Point* image, int numPoints, unsigned int desiredSize);
67 #endif /* #ifndef _MEDIAN_CUT_H_ */


hijacker
hijacker
hijacker
hijacker

build.log

1 /tmp/litprog923923/median_cut_sample.cpp: In function 'int main(int, char**)':
2 /tmp/litprog923923/median_cut_sample.cpp:21:33: error: 'atoi' was not declared in this scope
3 /tmp/litprog923923/median_cut_sample.cpp:22:61: error: 'malloc' was not declared in this scope
4 /tmp/litprog923923/median_cut_sample.cpp:24:33: error: 'fopen' was not declared in this scope
5 /tmp/litprog923923/median_cut_sample.cpp:27:39: error: 'fread' was not declared in this scope
6 /tmp/litprog923923/median_cut_sample.cpp:29:18: error: 'fclose' was not declared in this scope


hijacker
hijacker
hijacker
hijacker

median_cut.cpp

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Median_cut_algorithm_(C_Plus_Plus)?oldid=19175
 14 */
 15 
 16 #include <limits>
 17 #include <queue>
 18 #include <algorithm>
 19 #include "median_cut.h"
 20 
 21 Block::Block(Point* points, int pointsLength)
 22 {
 23     this->points = points;
 24     this->pointsLength = pointsLength;
 25     for(int i=0; i < NUM_DIMENSIONS; i++)
 26     {
 27         minCorner.x[i] = std::numeric_limits<unsigned char>::min();
 28         maxCorner.x[i] = std::numeric_limits<unsigned char>::max();
 29     }
 30 }
 31 Point * Block::getPoints()
 32 {
 33     return points;
 34 }
 35 
 36 int Block::numPoints() const
 37 {
 38     return pointsLength;
 39 }
 40 int Block::longestSideIndex() const
 41 {
 42     int m = maxCorner.x[0] - minCorner.x[0];
 43     int maxIndex = 0;
 44     for(int i=1; i < NUM_DIMENSIONS; i++)
 45     {
 46         int diff = maxCorner.x[i] - minCorner.x[i];
 47         if (diff > m)
 48         {
 49             m = diff;
 50             maxIndex = i;
 51         }
 52     }
 53     return maxIndex;
 54 }
 55 int Block::longestSideLength() const
 56 {
 57     int i = longestSideIndex();
 58     return maxCorner.x[i] - minCorner.x[i];
 59 }
 60 bool Block::operator<(const Block& rhs) const
 61 {
 62     return this->longestSideLength() < rhs.longestSideLength();
 63 }
 64 void Block::shrink()
 65 {
 66     int i,j;
 67     for(j=0; j<NUM_DIMENSIONS; j++)
 68     {
 69         minCorner.x[j] = maxCorner.x[j] = points[0].x[j];
 70     }
 71     for(i=1; i < pointsLength; i++)
 72     {
 73         for(j=0; j<NUM_DIMENSIONS; j++)
 74         {
 75             minCorner.x[j] = min(minCorner.x[j], points[i].x[j]);
 76             maxCorner.x[j] = max(maxCorner.x[j], points[i].x[j]);
 77         }
 78     }
 79 }
 80 std::list<Point> medianCut(Point* image, int numPoints, unsigned int desiredSize)
 81 {
 82     std::priority_queue<Block> blockQueue;
 83     Block initialBlock(image, numPoints);
 84     initialBlock.shrink();
 85     blockQueue.push(initialBlock);
 86     while (blockQueue.size() < desiredSize)
 87     {
 88         Block longestBlock = blockQueue.top();
 89         blockQueue.pop();
 90         Point * begin  = longestBlock.getPoints();
 91 	Point * median = longestBlock.getPoints() + (longestBlock.numPoints()+1)/2;
 92 	Point * end    = longestBlock.getPoints() + longestBlock.numPoints();
 93 	switch(longestBlock.longestSideIndex())
 94 	{
 95 	case 0: std::nth_element(begin, median, end, CoordinatePointComparator<0>()); break;
 96 	case 1: std::nth_element(begin, median, end, CoordinatePointComparator<1>()); break;
 97 	case 2: std::nth_element(begin, median, end, CoordinatePointComparator<2>()); break;
 98 	}
 99 
100 	Block block1(begin, median-begin), block2(median, end-median);
101 	block1.shrink();
102 	block2.shrink();
103         blockQueue.push(block1);
104         blockQueue.push(block2);
105     }
106     std::list<Point> result;
107     while(!blockQueue.empty())
108     {
109         Block block = blockQueue.top();
110         blockQueue.pop();
111         Point * points = block.getPoints();
112 
113         int sum[NUM_DIMENSIONS] = {0};
114         for(int i=0; i < block.numPoints(); i++)
115         {
116             for(int j=0; j < NUM_DIMENSIONS; j++)
117             {
118                 sum[j] += points[i].x[j];
119             }
120         }
121 
122         Point averagePoint;
123         for(int j=0; j < NUM_DIMENSIONS; j++)
124         {
125             averagePoint.x[j] = sum[j] / block.numPoints();
126         }
127 
128         result.push_back(averagePoint);
129     }
130     return result;
131 }
132 


hijacker
hijacker
hijacker
hijacker

median_cut_sample.cpp

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Median_cut_algorithm_(C_Plus_Plus)?oldid=19175
14 */
15 
16 #include <iostream>
17 #include "median_cut.h"
18 
19 int main(int argc, char* argv[]) {
20     FILE * raw_in;
21     int numPoints = atoi(argv[2]) * atoi(argv[3]);
22     Point* points = (Point*)malloc(sizeof(Point) * numPoints);
23 
24     raw_in = fopen(argv[1], "rb");
25     for(int i = 0; i < numPoints; i++)
26     {
27         fread(&points[i], 3, 1, raw_in);
28     }
29     fclose(raw_in);
30 
31     std::list<Point> palette =
32         medianCut(points, numPoints, atoi(argv[4]));
33 
34     std::list<Point>::iterator iter;
35     for (iter = palette.begin() ; iter != palette.end(); iter++)
36     {
37         std::cout << (int)iter->x[0] << " "
38                   << (int)iter->x[1] << " "
39                   << (int)iter->x[2] << std::endl;
40     }
41 
42     return 0;
43 }


hijacker
hijacker
hijacker
hijacker