QGIS API Documentation 3.37.0-Master (fdefdf9c27f)
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
28namespace 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 const int width = image.width();
41 const 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 QMultiMap<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 const 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 const QgsColorBox newColorBox1 = colorBox.mid( 0, currentListIndex + 1 );
246 colorBoxMap.insert( currentSum, newColorBox1 );
247
248 colorBox.erase( colorBox.begin(), colorBoxIt );
249 const 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 QMultiMap<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
Median cut implementation.
QList< QPair< QRgb, int > > QgsColorBox
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