QGIS API Documentation  3.8.0-Zanzibar (11aff65)
qgsmediancut.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  qgsmediancut.cpp
3  -------------------------
4  begin : December 20 , 2016
5  copyright : (C) 2007 by Marco Hugentobler ( parts from qgswmshandler)
6  (C) 2014 by Alessandro Pasotti ( parts from qgswmshandler)
7  (C) 2016 by David Marteau
8  email : marco dot hugentobler at karto dot baug dot ethz dot ch
9  a dot pasotti at itopen dot it
10  david dot marteau at 3liz dot com
11  ***************************************************************************/
12 
13 /***************************************************************************
14  * *
15  * This program is free software; you can redistribute it and/or modify *
16  * it under the terms of the GNU General Public License as published by *
17  * the Free Software Foundation; either version 2 of the License, or *
18  * (at your option) any later version. *
19  * *
20  ***************************************************************************/
21 
22 #include "qgsmediancut.h"
23 
24 #include <QList>
25 #include <QMultiMap>
26 #include <QHash>
27 
28 namespace QgsWms
29 {
30 
31  typedef QList< QPair<QRgb, int> > QgsColorBox; //Color / number of pixels
32  typedef QMultiMap< int, QgsColorBox > QgsColorBoxMap; // sum of pixels / color box
33 
34  namespace
35  {
36 
37  void imageColors( QHash<QRgb, int> &colors, const QImage &image )
38  {
39  colors.clear();
40  int width = image.width();
41  int height = image.height();
42 
43  const QRgb *currentScanLine = nullptr;
44  QHash<QRgb, int>::iterator colorIt;
45  for ( int i = 0; i < height; ++i )
46  {
47  currentScanLine = ( const QRgb * )( image.scanLine( i ) );
48  for ( int j = 0; j < width; ++j )
49  {
50  colorIt = colors.find( currentScanLine[j] );
51  if ( colorIt == colors.end() )
52  {
53  colors.insert( currentScanLine[j], 1 );
54  }
55  else
56  {
57  colorIt.value()++;
58  }
59  }
60  }
61  }
62 
63  bool minMaxRange( const QgsColorBox &colorBox, int &redRange, int &greenRange, int &blueRange, int &alphaRange )
64  {
65  if ( colorBox.size() < 1 )
66  {
67  return false;
68  }
69 
70  int rMin = std::numeric_limits<int>::max();
71  int gMin = std::numeric_limits<int>::max();
72  int bMin = std::numeric_limits<int>::max();
73  int aMin = std::numeric_limits<int>::max();
74  int rMax = std::numeric_limits<int>::min();
75  int gMax = std::numeric_limits<int>::min();
76  int bMax = std::numeric_limits<int>::min();
77  int aMax = std::numeric_limits<int>::min();
78 
79  int currentRed = 0;
80  int currentGreen = 0;
81  int currentBlue = 0;
82  int currentAlpha = 0;
83 
84  for ( auto colorBoxIt = colorBox.constBegin() ; colorBoxIt != colorBox.constEnd(); ++colorBoxIt )
85  {
86  currentRed = qRed( colorBoxIt->first );
87  if ( currentRed > rMax )
88  {
89  rMax = currentRed;
90  }
91  if ( currentRed < rMin )
92  {
93  rMin = currentRed;
94  }
95 
96  currentGreen = qGreen( colorBoxIt->first );
97  if ( currentGreen > gMax )
98  {
99  gMax = currentGreen;
100  }
101  if ( currentGreen < gMin )
102  {
103  gMin = currentGreen;
104  }
105 
106  currentBlue = qBlue( colorBoxIt->first );
107  if ( currentBlue > bMax )
108  {
109  bMax = currentBlue;
110  }
111  if ( currentBlue < bMin )
112  {
113  bMin = currentBlue;
114  }
115 
116  currentAlpha = qAlpha( colorBoxIt->first );
117  if ( currentAlpha > aMax )
118  {
119  aMax = currentAlpha;
120  }
121  if ( currentAlpha < aMin )
122  {
123  aMin = currentAlpha;
124  }
125  }
126 
127  redRange = rMax - rMin;
128  greenRange = gMax - gMin;
129  blueRange = bMax - bMin;
130  alphaRange = aMax - aMin;
131  return true;
132  }
133 
134  bool redCompare( QPair<QRgb, int> c1, QPair<QRgb, int> c2 )
135  {
136  return qRed( c1.first ) < qRed( c2.first );
137  }
138 
139  bool greenCompare( QPair<QRgb, int> c1, QPair<QRgb, int> c2 )
140  {
141  return qGreen( c1.first ) < qGreen( c2.first );
142  }
143 
144  bool blueCompare( QPair<QRgb, int> c1, QPair<QRgb, int> c2 )
145  {
146  return qBlue( c1.first ) < qBlue( c2.first );
147  }
148 
149  bool alphaCompare( QPair<QRgb, int> c1, QPair<QRgb, int> c2 )
150  {
151  return qAlpha( c1.first ) < qAlpha( c2.first );
152  }
153 
154  QRgb boxColor( const QgsColorBox &box, int boxPixels )
155  {
156  double avRed = 0;
157  double avGreen = 0;
158  double avBlue = 0;
159  double avAlpha = 0;
160  QRgb currentColor;
161  int currentPixel;
162 
163  double weight;
164 
165  for ( auto colorBoxIt = box.constBegin(); colorBoxIt != box.constEnd(); ++colorBoxIt )
166  {
167  currentColor = colorBoxIt->first;
168  currentPixel = colorBoxIt->second;
169  weight = static_cast<double>( currentPixel ) / boxPixels;
170  avRed += ( qRed( currentColor ) * weight );
171  avGreen += ( qGreen( currentColor ) * weight );
172  avBlue += ( qBlue( currentColor ) * weight );
173  avAlpha += ( qAlpha( currentColor ) * weight );
174  }
175 
176  return qRgba( avRed, avGreen, avBlue, avAlpha );
177  }
178 
179 
180  void splitColorBox( QgsColorBox &colorBox, QgsColorBoxMap &colorBoxMap,
181  QMap<int, QgsColorBox>::iterator colorBoxMapIt )
182  {
183 
184  if ( colorBox.size() < 2 )
185  {
186  return; //need at least two colors for a split
187  }
188 
189  //a,r,g,b ranges
190  int redRange = 0;
191  int greenRange = 0;
192  int blueRange = 0;
193  int alphaRange = 0;
194 
195  if ( !minMaxRange( colorBox, redRange, greenRange, blueRange, alphaRange ) )
196  {
197  return;
198  }
199 
200  //sort color box for a/r/g/b
201  if ( redRange >= greenRange && redRange >= blueRange && redRange >= alphaRange )
202  {
203  std::sort( colorBox.begin(), colorBox.end(), redCompare );
204  }
205  else if ( greenRange >= redRange && greenRange >= blueRange && greenRange >= alphaRange )
206  {
207  std::sort( colorBox.begin(), colorBox.end(), greenCompare );
208  }
209  else if ( blueRange >= redRange && blueRange >= greenRange && blueRange >= alphaRange )
210  {
211  std::sort( colorBox.begin(), colorBox.end(), blueCompare );
212  }
213  else
214  {
215  std::sort( colorBox.begin(), colorBox.end(), alphaCompare );
216  }
217 
218  //get median
219  double halfSum = colorBoxMapIt.key() / 2.0;
220  int currentSum = 0;
221  int currentListIndex = 0;
222 
223  auto colorBoxIt = colorBox.begin();
224  for ( ; colorBoxIt != colorBox.end(); ++colorBoxIt )
225  {
226  currentSum += colorBoxIt->second;
227  if ( currentSum >= halfSum )
228  {
229  break;
230  }
231  ++currentListIndex;
232  }
233 
234  if ( currentListIndex > ( colorBox.size() - 2 ) ) //if the median is contained in the last color, split one item before that
235  {
236  --currentListIndex;
237  currentSum -= colorBoxIt->second;
238  }
239  else
240  {
241  ++colorBoxIt; //the iterator needs to point behind the last item to remove
242  }
243 
244  //do split: replace old color box, insert new one
245  QgsColorBox newColorBox1 = colorBox.mid( 0, currentListIndex + 1 );
246  colorBoxMap.insert( currentSum, newColorBox1 );
247 
248  colorBox.erase( colorBox.begin(), colorBoxIt );
249  QgsColorBox newColorBox2 = colorBox;
250  colorBoxMap.erase( colorBoxMapIt );
251  colorBoxMap.insert( halfSum * 2.0 - currentSum, newColorBox2 );
252  }
253 
254  } // namespace
255 
256  void medianCut( QVector<QRgb> &colorTable, int nColors, const QImage &inputImage )
257  {
258  QHash<QRgb, int> inputColors;
259  imageColors( inputColors, inputImage );
260 
261  if ( inputColors.size() <= nColors ) //all the colors in the image can be mapped to one palette color
262  {
263  colorTable.resize( inputColors.size() );
264  int index = 0;
265  for ( auto inputColorIt = inputColors.constBegin(); inputColorIt != inputColors.constEnd(); ++inputColorIt )
266  {
267  colorTable[index] = inputColorIt.key();
268  ++index;
269  }
270  return;
271  }
272 
273  //create first box
274  QgsColorBox firstBox; //QList< QPair<QRgb, int> >
275  int firstBoxPixelSum = 0;
276  for ( auto inputColorIt = inputColors.constBegin(); inputColorIt != inputColors.constEnd(); ++inputColorIt )
277  {
278  firstBox.push_back( qMakePair( inputColorIt.key(), inputColorIt.value() ) );
279  firstBoxPixelSum += inputColorIt.value();
280  }
281 
282  QgsColorBoxMap colorBoxMap; //QMultiMap< int, ColorBox >
283  colorBoxMap.insert( firstBoxPixelSum, firstBox );
284  QMap<int, QgsColorBox>::iterator colorBoxMapIt = colorBoxMap.end();
285 
286  //split boxes until number of boxes == nColors or all the boxes have color count 1
287  bool allColorsMapped = false;
288  while ( colorBoxMap.size() < nColors )
289  {
290  //start at the end of colorBoxMap and pick the first entry with number of colors < 1
291  colorBoxMapIt = colorBoxMap.end();
292  while ( true )
293  {
294  --colorBoxMapIt;
295  if ( colorBoxMapIt.value().size() > 1 )
296  {
297  splitColorBox( colorBoxMapIt.value(), colorBoxMap, colorBoxMapIt );
298  break;
299  }
300  if ( colorBoxMapIt == colorBoxMap.begin() )
301  {
302  allColorsMapped = true;
303  break;
304  }
305  }
306 
307  if ( allColorsMapped )
308  {
309  break;
310  }
311  }
312 
313  //get representative colors for the boxes
314  int index = 0;
315  colorTable.resize( colorBoxMap.size() );
316  for ( auto colorBoxIt = colorBoxMap.constBegin(); colorBoxIt != colorBoxMap.constEnd(); ++colorBoxIt )
317  {
318  colorTable[index] = boxColor( colorBoxIt.value(), colorBoxIt.key() );
319  ++index;
320  }
321  }
322 
323 } // namespace QgsWms
324 
325 
QList< QPair< QRgb, int > > QgsColorBox
Median cut implementation.
void medianCut(QVector< QRgb > &colorTable, int nColors, const QImage &inputImage)
Median cut implementation used when reducing RGB colors to palletized colors.
QMultiMap< int, QgsColorBox > QgsColorBoxMap