/src/gdal/alg/gdalmediancut.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /****************************************************************************** |
2 | | * |
3 | | * Project: CIETMap Phase 2 |
4 | | * Purpose: Use median cut algorithm to generate an near-optimal PCT for a |
5 | | * given RGB image. Implemented as function GDALComputeMedianCutPCT. |
6 | | * Author: Frank Warmerdam, warmerdam@pobox.com |
7 | | * |
8 | | ****************************************************************************** |
9 | | * Copyright (c) 2001, Frank Warmerdam |
10 | | * Copyright (c) 2007-2010, Even Rouault <even dot rouault at spatialys.com> |
11 | | * |
12 | | * SPDX-License-Identifier: MIT |
13 | | ****************************************************************************** |
14 | | * |
15 | | * This code was based on the tiffmedian.c code from libtiff (www.libtiff.org) |
16 | | * which was based on a paper by Paul Heckbert: |
17 | | * |
18 | | * "Color Image Quantization for Frame Buffer Display", Paul |
19 | | * Heckbert, SIGGRAPH proceedings, 1982, pp. 297-307. |
20 | | * |
21 | | */ |
22 | | |
23 | | #include "cpl_port.h" |
24 | | #include "gdal_alg.h" |
25 | | #include "gdal_alg_priv.h" |
26 | | |
27 | | #include <climits> |
28 | | #include <cstring> |
29 | | |
30 | | #include <algorithm> |
31 | | #include <limits> |
32 | | |
33 | | #include "cpl_conv.h" |
34 | | #include "cpl_error.h" |
35 | | #include "cpl_float.h" |
36 | | #include "cpl_progress.h" |
37 | | #include "cpl_vsi.h" |
38 | | #include "gdal.h" |
39 | | #include "gdal_priv.h" |
40 | | |
41 | | template <typename T> static T *HISTOGRAM(T *h, int n, int r, int g, int b) |
42 | 0 | { |
43 | 0 | const int index = (r * n + g) * n + b; |
44 | 0 | return &h[index]; |
45 | 0 | } Unexecuted instantiation: gdalmediancut.cpp:unsigned int* HISTOGRAM<unsigned int>(unsigned int*, int, int, int, int) Unexecuted instantiation: gdalmediancut.cpp:unsigned int const* HISTOGRAM<unsigned int const>(unsigned int const*, int, int, int, int) Unexecuted instantiation: gdalmediancut.cpp:unsigned long long* HISTOGRAM<unsigned long long>(unsigned long long*, int, int, int, int) Unexecuted instantiation: gdalmediancut.cpp:unsigned long long const* HISTOGRAM<unsigned long long const>(unsigned long long const*, int, int, int, int) |
46 | | |
47 | | #ifndef MAKE_COLOR_CODE_defined |
48 | | #define MAKE_COLOR_CODE_defined |
49 | | |
50 | | static int MAKE_COLOR_CODE(int r, int g, int b) |
51 | 0 | { |
52 | 0 | return r | (g << 8) | (b << 16); |
53 | 0 | } |
54 | | #endif |
55 | | |
56 | | // NOTE: If changing the size of this structure, edit |
57 | | // MEDIAN_CUT_AND_DITHER_BUFFER_SIZE_65536 in gdal_alg_priv.h and take into |
58 | | // account ColorIndex in gdaldither.cpp. |
59 | | typedef struct |
60 | | { |
61 | | GUInt32 nColorCode; |
62 | | int nCount; |
63 | | GUInt32 nColorCode2; |
64 | | int nCount2; |
65 | | GUInt32 nColorCode3; |
66 | | int nCount3; |
67 | | } HashHistogram; |
68 | | |
69 | | typedef struct colorbox |
70 | | { |
71 | | struct colorbox *next, *prev; |
72 | | int rmin, rmax; |
73 | | int gmin, gmax; |
74 | | int bmin, bmax; |
75 | | GUIntBig total; |
76 | | } Colorbox; |
77 | | |
78 | | template <class T> |
79 | | static void splitbox(Colorbox *ptr, const T *histogram, |
80 | | const HashHistogram *psHashHistogram, int nCLevels, |
81 | | Colorbox **pfreeboxes, Colorbox **pusedboxes, |
82 | | GByte *pabyRedBand, GByte *pabyGreenBand, |
83 | | GByte *pabyBlueBand, T nPixels); |
84 | | |
85 | | template <class T> |
86 | | static void shrinkbox(Colorbox *box, const T *histogram, int nCLevels); |
87 | | |
88 | | static Colorbox *largest_box(Colorbox *usedboxes); |
89 | | |
90 | | /************************************************************************/ |
91 | | /* GDALComputeMedianCutPCT() */ |
92 | | /************************************************************************/ |
93 | | |
94 | | /** |
95 | | * Compute optimal PCT for RGB image. |
96 | | * |
97 | | * This function implements a median cut algorithm to compute an "optimal" |
98 | | * pseudocolor table for representing an input RGB image. This PCT could |
99 | | * then be used with GDALDitherRGB2PCT() to convert a 24bit RGB image into |
100 | | * an eightbit pseudo-colored image. |
101 | | * |
102 | | * This code was based on the tiffmedian.c code from libtiff (www.libtiff.org) |
103 | | * which was based on a paper by Paul Heckbert: |
104 | | * |
105 | | * \verbatim |
106 | | * "Color Image Quantization for Frame Buffer Display", Paul |
107 | | * Heckbert, SIGGRAPH proceedings, 1982, pp. 297-307. |
108 | | * \endverbatim |
109 | | * |
110 | | * The red, green and blue input bands do not necessarily need to come |
111 | | * from the same file, but they must be the same width and height. They will |
112 | | * be clipped to 8bit during reading, so non-eight bit bands are generally |
113 | | * inappropriate. |
114 | | * |
115 | | * @param hRed Red input band. |
116 | | * @param hGreen Green input band. |
117 | | * @param hBlue Blue input band. |
118 | | * @param pfnIncludePixel function used to test which pixels should be included |
119 | | * in the analysis. At this time this argument is ignored and all pixels are |
120 | | * utilized. This should normally be NULL. |
121 | | * @param nColors the desired number of colors to be returned (2-256). |
122 | | * @param hColorTable the colors will be returned in this color table object. |
123 | | * @param pfnProgress callback for reporting algorithm progress matching the |
124 | | * GDALProgressFunc() semantics. May be NULL. |
125 | | * @param pProgressArg callback argument passed to pfnProgress. |
126 | | * |
127 | | * @return returns CE_None on success or CE_Failure if an error occurs. |
128 | | */ |
129 | | |
130 | | extern "C" int CPL_STDCALL GDALComputeMedianCutPCT( |
131 | | GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue, |
132 | | int (*pfnIncludePixel)(int, int, void *), int nColors, |
133 | | GDALColorTableH hColorTable, GDALProgressFunc pfnProgress, |
134 | | void *pProgressArg) |
135 | | |
136 | 0 | { |
137 | 0 | VALIDATE_POINTER1(hRed, "GDALComputeMedianCutPCT", CE_Failure); |
138 | 0 | const int nXSize = GDALGetRasterBandXSize(hRed); |
139 | 0 | const int nYSize = GDALGetRasterBandYSize(hRed); |
140 | 0 | if (nYSize == 0) |
141 | 0 | return CE_Failure; |
142 | 0 | if (static_cast<GUInt32>(nXSize) < |
143 | 0 | std::numeric_limits<GUInt32>::max() / static_cast<GUInt32>(nYSize)) |
144 | 0 | { |
145 | 0 | return GDALComputeMedianCutPCTInternal( |
146 | 0 | hRed, hGreen, hBlue, nullptr, nullptr, nullptr, pfnIncludePixel, |
147 | 0 | nColors, 5, static_cast<GUInt32 *>(nullptr), hColorTable, |
148 | 0 | pfnProgress, pProgressArg); |
149 | 0 | } |
150 | 0 | else |
151 | 0 | { |
152 | 0 | return GDALComputeMedianCutPCTInternal( |
153 | 0 | hRed, hGreen, hBlue, nullptr, nullptr, nullptr, pfnIncludePixel, |
154 | 0 | nColors, 5, static_cast<GUIntBig *>(nullptr), hColorTable, |
155 | 0 | pfnProgress, pProgressArg); |
156 | 0 | } |
157 | 0 | } |
158 | | |
159 | | #ifndef IsColorCodeSet_defined |
160 | | #define IsColorCodeSet_defined |
161 | | |
162 | | static inline bool IsColorCodeSet(GUInt32 nColorCode) |
163 | 0 | { |
164 | 0 | return (nColorCode >> 31) == 0; |
165 | 0 | } |
166 | | #endif |
167 | | |
168 | | static inline int FindColorCount(const HashHistogram *psHashHistogram, |
169 | | GUInt32 nColorCode) |
170 | 0 | { |
171 | |
|
172 | 0 | GUInt32 nIdx = nColorCode % PRIME_FOR_65536; |
173 | 0 | while (true) |
174 | 0 | { |
175 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode)) |
176 | 0 | { |
177 | 0 | return 0; |
178 | 0 | } |
179 | 0 | if (psHashHistogram[nIdx].nColorCode == nColorCode) |
180 | 0 | { |
181 | 0 | return psHashHistogram[nIdx].nCount; |
182 | 0 | } |
183 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode2)) |
184 | 0 | { |
185 | 0 | return 0; |
186 | 0 | } |
187 | 0 | if (psHashHistogram[nIdx].nColorCode2 == nColorCode) |
188 | 0 | { |
189 | 0 | return psHashHistogram[nIdx].nCount2; |
190 | 0 | } |
191 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode3)) |
192 | 0 | { |
193 | 0 | return 0; |
194 | 0 | } |
195 | 0 | if (psHashHistogram[nIdx].nColorCode3 == nColorCode) |
196 | 0 | { |
197 | 0 | return psHashHistogram[nIdx].nCount3; |
198 | 0 | } |
199 | | |
200 | 0 | do |
201 | 0 | { |
202 | 0 | nIdx += 257; |
203 | 0 | if (nIdx >= PRIME_FOR_65536) |
204 | 0 | nIdx -= PRIME_FOR_65536; |
205 | 0 | } while (IsColorCodeSet(psHashHistogram[nIdx].nColorCode) && |
206 | 0 | psHashHistogram[nIdx].nColorCode != nColorCode && |
207 | 0 | IsColorCodeSet(psHashHistogram[nIdx].nColorCode2) && |
208 | 0 | psHashHistogram[nIdx].nColorCode2 != nColorCode && |
209 | 0 | IsColorCodeSet(psHashHistogram[nIdx].nColorCode3) && |
210 | 0 | psHashHistogram[nIdx].nColorCode3 != nColorCode); |
211 | 0 | } |
212 | 0 | } |
213 | | |
214 | | static inline int *FindAndInsertColorCount(HashHistogram *psHashHistogram, |
215 | | GUInt32 nColorCode) |
216 | 0 | { |
217 | 0 | GUInt32 nIdx = nColorCode % PRIME_FOR_65536; |
218 | 0 | while (true) |
219 | 0 | { |
220 | 0 | if (psHashHistogram[nIdx].nColorCode == nColorCode) |
221 | 0 | { |
222 | 0 | return &(psHashHistogram[nIdx].nCount); |
223 | 0 | } |
224 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode)) |
225 | 0 | { |
226 | 0 | psHashHistogram[nIdx].nColorCode = nColorCode; |
227 | 0 | psHashHistogram[nIdx].nCount = 0; |
228 | 0 | return &(psHashHistogram[nIdx].nCount); |
229 | 0 | } |
230 | 0 | if (psHashHistogram[nIdx].nColorCode2 == nColorCode) |
231 | 0 | { |
232 | 0 | return &(psHashHistogram[nIdx].nCount2); |
233 | 0 | } |
234 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode2)) |
235 | 0 | { |
236 | 0 | psHashHistogram[nIdx].nColorCode2 = nColorCode; |
237 | 0 | psHashHistogram[nIdx].nCount2 = 0; |
238 | 0 | return &(psHashHistogram[nIdx].nCount2); |
239 | 0 | } |
240 | 0 | if (psHashHistogram[nIdx].nColorCode3 == nColorCode) |
241 | 0 | { |
242 | 0 | return &(psHashHistogram[nIdx].nCount3); |
243 | 0 | } |
244 | 0 | if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode3)) |
245 | 0 | { |
246 | 0 | psHashHistogram[nIdx].nColorCode3 = nColorCode; |
247 | 0 | psHashHistogram[nIdx].nCount3 = 0; |
248 | 0 | return &(psHashHistogram[nIdx].nCount3); |
249 | 0 | } |
250 | | |
251 | 0 | do |
252 | 0 | { |
253 | 0 | nIdx += 257; |
254 | 0 | if (nIdx >= PRIME_FOR_65536) |
255 | 0 | nIdx -= PRIME_FOR_65536; |
256 | 0 | } while (IsColorCodeSet(psHashHistogram[nIdx].nColorCode) && |
257 | 0 | psHashHistogram[nIdx].nColorCode != nColorCode && |
258 | 0 | IsColorCodeSet(psHashHistogram[nIdx].nColorCode2) && |
259 | 0 | psHashHistogram[nIdx].nColorCode2 != nColorCode && |
260 | 0 | IsColorCodeSet(psHashHistogram[nIdx].nColorCode3) && |
261 | 0 | psHashHistogram[nIdx].nColorCode3 != nColorCode); |
262 | 0 | } |
263 | 0 | } |
264 | | |
265 | | template <class T> |
266 | | int GDALComputeMedianCutPCTInternal( |
267 | | GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue, |
268 | | GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand, |
269 | | int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits, |
270 | | T *panHistogram, // NULL, or >= size (1<<nBits)^3 * sizeof(T) bytes. |
271 | | GDALColorTableH hColorTable, GDALProgressFunc pfnProgress, |
272 | | void *pProgressArg) |
273 | | |
274 | 0 | { |
275 | 0 | VALIDATE_POINTER1(hRed, "GDALComputeMedianCutPCT", CE_Failure); |
276 | 0 | VALIDATE_POINTER1(hGreen, "GDALComputeMedianCutPCT", CE_Failure); |
277 | 0 | VALIDATE_POINTER1(hBlue, "GDALComputeMedianCutPCT", CE_Failure); |
278 | | |
279 | 0 | CPLErr err = CE_None; |
280 | | |
281 | | /* -------------------------------------------------------------------- */ |
282 | | /* Validate parameters. */ |
283 | | /* -------------------------------------------------------------------- */ |
284 | 0 | const int nXSize = GDALGetRasterBandXSize(hRed); |
285 | 0 | const int nYSize = GDALGetRasterBandYSize(hRed); |
286 | |
|
287 | 0 | if (GDALGetRasterBandXSize(hGreen) != nXSize || |
288 | 0 | GDALGetRasterBandYSize(hGreen) != nYSize || |
289 | 0 | GDALGetRasterBandXSize(hBlue) != nXSize || |
290 | 0 | GDALGetRasterBandYSize(hBlue) != nYSize) |
291 | 0 | { |
292 | 0 | CPLError(CE_Failure, CPLE_IllegalArg, |
293 | 0 | "Green or blue band doesn't match size of red band."); |
294 | |
|
295 | 0 | return CE_Failure; |
296 | 0 | } |
297 | | |
298 | 0 | if (pfnIncludePixel != nullptr) |
299 | 0 | { |
300 | 0 | CPLError(CE_Failure, CPLE_IllegalArg, |
301 | 0 | "GDALComputeMedianCutPCT() doesn't currently support " |
302 | 0 | "pfnIncludePixel function."); |
303 | |
|
304 | 0 | return CE_Failure; |
305 | 0 | } |
306 | | |
307 | 0 | if (nColors <= 0) |
308 | 0 | { |
309 | 0 | CPLError(CE_Failure, CPLE_IllegalArg, |
310 | 0 | "GDALComputeMedianCutPCT(): " |
311 | 0 | "nColors must be strictly greater than 1."); |
312 | |
|
313 | 0 | return CE_Failure; |
314 | 0 | } |
315 | | |
316 | 0 | if (nColors > 256) |
317 | 0 | { |
318 | 0 | CPLError(CE_Failure, CPLE_IllegalArg, |
319 | 0 | "GDALComputeMedianCutPCT(): " |
320 | 0 | "nColors must be lesser than or equal to 256."); |
321 | |
|
322 | 0 | return CE_Failure; |
323 | 0 | } |
324 | | |
325 | 0 | if (pfnProgress == nullptr) |
326 | 0 | pfnProgress = GDALDummyProgress; |
327 | | |
328 | | /* ==================================================================== */ |
329 | | /* STEP 1: create empty boxes. */ |
330 | | /* ==================================================================== */ |
331 | 0 | if (static_cast<GUInt32>(nXSize) > |
332 | 0 | cpl::NumericLimits<T>::max() / static_cast<GUInt32>(nYSize)) |
333 | 0 | { |
334 | 0 | CPLError(CE_Warning, CPLE_AppDefined, |
335 | 0 | "GDALComputeMedianCutPCTInternal() not called " |
336 | 0 | "with large enough type"); |
337 | 0 | } |
338 | |
|
339 | 0 | T nPixels = 0; |
340 | 0 | if (nBits == 8 && pabyRedBand != nullptr && pabyGreenBand != nullptr && |
341 | 0 | pabyBlueBand != nullptr && |
342 | 0 | static_cast<GUInt32>(nXSize) <= |
343 | 0 | cpl::NumericLimits<T>::max() / static_cast<GUInt32>(nYSize)) |
344 | 0 | { |
345 | 0 | nPixels = static_cast<T>(nXSize) * static_cast<T>(nYSize); |
346 | 0 | } |
347 | |
|
348 | 0 | const int nCLevels = 1 << nBits; |
349 | 0 | const int nCLevelsCube = nCLevels * nCLevels * nCLevels; |
350 | 0 | T *histogram = nullptr; |
351 | 0 | HashHistogram *psHashHistogram = nullptr; |
352 | 0 | if (panHistogram) |
353 | 0 | { |
354 | 0 | if (nBits == 8 && static_cast<GUIntBig>(nXSize) * nYSize <= 65536) |
355 | 0 | { |
356 | | // If the image is small enough, then the number of colors |
357 | | // will be limited and using a hashmap, rather than a full table |
358 | | // will be more efficient. |
359 | 0 | histogram = nullptr; |
360 | 0 | psHashHistogram = reinterpret_cast<HashHistogram *>(panHistogram); |
361 | 0 | memset(psHashHistogram, 0xFF, |
362 | 0 | sizeof(HashHistogram) * PRIME_FOR_65536); |
363 | 0 | } |
364 | 0 | else |
365 | 0 | { |
366 | 0 | histogram = panHistogram; |
367 | 0 | memset(histogram, 0, nCLevelsCube * sizeof(T)); |
368 | 0 | } |
369 | 0 | } |
370 | 0 | else |
371 | 0 | { |
372 | 0 | histogram = |
373 | 0 | static_cast<T *>(VSI_CALLOC_VERBOSE(nCLevelsCube, sizeof(T))); |
374 | 0 | if (histogram == nullptr) |
375 | 0 | { |
376 | 0 | return CE_Failure; |
377 | 0 | } |
378 | 0 | } |
379 | 0 | Colorbox *box_list = |
380 | 0 | static_cast<Colorbox *>(CPLMalloc(nColors * sizeof(Colorbox))); |
381 | 0 | Colorbox *freeboxes = box_list; |
382 | 0 | freeboxes[0].next = &freeboxes[1]; |
383 | 0 | freeboxes[0].prev = nullptr; |
384 | 0 | for (int i = 1; i < nColors - 1; ++i) |
385 | 0 | { |
386 | 0 | freeboxes[i].next = &freeboxes[i + 1]; |
387 | 0 | freeboxes[i].prev = &freeboxes[i - 1]; |
388 | 0 | } |
389 | 0 | freeboxes[nColors - 1].next = nullptr; |
390 | 0 | freeboxes[nColors - 1].prev = &freeboxes[nColors - 2]; |
391 | | |
392 | | /* ==================================================================== */ |
393 | | /* Build histogram. */ |
394 | | /* ==================================================================== */ |
395 | | |
396 | | /* -------------------------------------------------------------------- */ |
397 | | /* Initialize the box datastructures. */ |
398 | | /* -------------------------------------------------------------------- */ |
399 | 0 | Colorbox *freeboxes_before = freeboxes; |
400 | 0 | freeboxes = freeboxes_before->next; |
401 | 0 | if (freeboxes) |
402 | 0 | freeboxes->prev = nullptr; |
403 | |
|
404 | 0 | Colorbox *usedboxes = freeboxes_before; |
405 | 0 | usedboxes->next = nullptr; |
406 | 0 | usedboxes->rmin = 999; |
407 | 0 | usedboxes->gmin = 999; |
408 | 0 | usedboxes->bmin = 999; |
409 | 0 | usedboxes->rmax = -1; |
410 | 0 | usedboxes->gmax = -1; |
411 | 0 | usedboxes->bmax = -1; |
412 | 0 | usedboxes->total = |
413 | 0 | static_cast<GUIntBig>(nXSize) * static_cast<GUIntBig>(nYSize); |
414 | | |
415 | | /* -------------------------------------------------------------------- */ |
416 | | /* Collect histogram. */ |
417 | | /* -------------------------------------------------------------------- */ |
418 | | |
419 | | // TODO(schwehr): Move these closer to usage after removing gotos. |
420 | 0 | const int nColorShift = 8 - nBits; |
421 | 0 | int nColorCounter = 0; |
422 | 0 | GByte anRed[256] = {}; |
423 | 0 | GByte anGreen[256] = {}; |
424 | 0 | GByte anBlue[256] = {}; |
425 | |
|
426 | 0 | GByte *pabyRedLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize)); |
427 | 0 | GByte *pabyGreenLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize)); |
428 | 0 | GByte *pabyBlueLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize)); |
429 | |
|
430 | 0 | if (pabyRedLine == nullptr || pabyGreenLine == nullptr || |
431 | 0 | pabyBlueLine == nullptr) |
432 | 0 | { |
433 | 0 | err = CE_Failure; |
434 | 0 | goto end_and_cleanup; |
435 | 0 | } |
436 | | |
437 | 0 | for (int iLine = 0; iLine < nYSize; iLine++) |
438 | 0 | { |
439 | 0 | if (!pfnProgress(iLine / static_cast<double>(nYSize), |
440 | 0 | "Generating Histogram", pProgressArg)) |
441 | 0 | { |
442 | 0 | CPLError(CE_Failure, CPLE_UserInterrupt, "User Terminated"); |
443 | 0 | err = CE_Failure; |
444 | 0 | goto end_and_cleanup; |
445 | 0 | } |
446 | | |
447 | 0 | err = GDALRasterIO(hRed, GF_Read, 0, iLine, nXSize, 1, pabyRedLine, |
448 | 0 | nXSize, 1, GDT_Byte, 0, 0); |
449 | 0 | if (err == CE_None) |
450 | 0 | err = GDALRasterIO(hGreen, GF_Read, 0, iLine, nXSize, 1, |
451 | 0 | pabyGreenLine, nXSize, 1, GDT_Byte, 0, 0); |
452 | 0 | if (err == CE_None) |
453 | 0 | err = GDALRasterIO(hBlue, GF_Read, 0, iLine, nXSize, 1, |
454 | 0 | pabyBlueLine, nXSize, 1, GDT_Byte, 0, 0); |
455 | 0 | if (err != CE_None) |
456 | 0 | goto end_and_cleanup; |
457 | | |
458 | 0 | for (int iPixel = 0; iPixel < nXSize; iPixel++) |
459 | 0 | { |
460 | 0 | const int nRed = pabyRedLine[iPixel] >> nColorShift; |
461 | 0 | const int nGreen = pabyGreenLine[iPixel] >> nColorShift; |
462 | 0 | const int nBlue = pabyBlueLine[iPixel] >> nColorShift; |
463 | |
|
464 | 0 | usedboxes->rmin = std::min(usedboxes->rmin, nRed); |
465 | 0 | usedboxes->gmin = std::min(usedboxes->gmin, nGreen); |
466 | 0 | usedboxes->bmin = std::min(usedboxes->bmin, nBlue); |
467 | 0 | usedboxes->rmax = std::max(usedboxes->rmax, nRed); |
468 | 0 | usedboxes->gmax = std::max(usedboxes->gmax, nGreen); |
469 | 0 | usedboxes->bmax = std::max(usedboxes->bmax, nBlue); |
470 | |
|
471 | 0 | bool bFirstOccurrence; |
472 | 0 | if (psHashHistogram) |
473 | 0 | { |
474 | 0 | int *pnColor = FindAndInsertColorCount( |
475 | 0 | psHashHistogram, MAKE_COLOR_CODE(nRed, nGreen, nBlue)); |
476 | 0 | bFirstOccurrence = (*pnColor == 0); |
477 | 0 | (*pnColor)++; |
478 | 0 | } |
479 | 0 | else |
480 | 0 | { |
481 | 0 | T *pnColor = |
482 | 0 | HISTOGRAM(histogram, nCLevels, nRed, nGreen, nBlue); |
483 | 0 | bFirstOccurrence = (*pnColor == 0); |
484 | 0 | (*pnColor)++; |
485 | 0 | } |
486 | 0 | if (bFirstOccurrence) |
487 | 0 | { |
488 | 0 | if (nColorShift == 0 && nColorCounter < nColors) |
489 | 0 | { |
490 | 0 | anRed[nColorCounter] = static_cast<GByte>(nRed); |
491 | 0 | anGreen[nColorCounter] = static_cast<GByte>(nGreen); |
492 | 0 | anBlue[nColorCounter] = static_cast<GByte>(nBlue); |
493 | 0 | } |
494 | 0 | nColorCounter++; |
495 | 0 | } |
496 | 0 | } |
497 | 0 | } |
498 | | |
499 | 0 | if (!pfnProgress(1.0, "Generating Histogram", pProgressArg)) |
500 | 0 | { |
501 | 0 | CPLError(CE_Failure, CPLE_UserInterrupt, "User Terminated"); |
502 | 0 | err = CE_Failure; |
503 | 0 | goto end_and_cleanup; |
504 | 0 | } |
505 | | |
506 | 0 | if (nColorShift == 0 && nColorCounter <= nColors) |
507 | 0 | { |
508 | | #if DEBUG_VERBOSE |
509 | | CPLDebug("MEDIAN_CUT", "%d colors found <= %d", nColorCounter, nColors); |
510 | | #endif |
511 | 0 | for (int iColor = 0; iColor < nColorCounter; iColor++) |
512 | 0 | { |
513 | 0 | const GDALColorEntry sEntry = {static_cast<GByte>(anRed[iColor]), |
514 | 0 | static_cast<GByte>(anGreen[iColor]), |
515 | 0 | static_cast<GByte>(anBlue[iColor]), |
516 | 0 | 255}; |
517 | 0 | GDALSetColorEntry(hColorTable, iColor, &sEntry); |
518 | 0 | } |
519 | 0 | goto end_and_cleanup; |
520 | 0 | } |
521 | | |
522 | | /* ==================================================================== */ |
523 | | /* STEP 3: continually subdivide boxes until no more free */ |
524 | | /* boxes remain or until all colors assigned. */ |
525 | | /* ==================================================================== */ |
526 | 0 | while (freeboxes != nullptr) |
527 | 0 | { |
528 | 0 | auto ptr = largest_box(usedboxes); |
529 | 0 | if (ptr != nullptr) |
530 | 0 | splitbox(ptr, histogram, psHashHistogram, nCLevels, &freeboxes, |
531 | 0 | &usedboxes, pabyRedBand, pabyGreenBand, pabyBlueBand, |
532 | 0 | nPixels); |
533 | 0 | else |
534 | 0 | freeboxes = nullptr; |
535 | 0 | } |
536 | | |
537 | | /* ==================================================================== */ |
538 | | /* STEP 4: assign colors to all boxes */ |
539 | | /* ==================================================================== */ |
540 | 0 | { |
541 | 0 | Colorbox *ptr = usedboxes; |
542 | 0 | for (int i = 0; ptr != nullptr; ++i, ptr = ptr->next) |
543 | 0 | { |
544 | 0 | const GDALColorEntry sEntry = { |
545 | 0 | static_cast<GByte>(((ptr->rmin + ptr->rmax) << nColorShift) / |
546 | 0 | 2), |
547 | 0 | static_cast<GByte>(((ptr->gmin + ptr->gmax) << nColorShift) / |
548 | 0 | 2), |
549 | 0 | static_cast<GByte>(((ptr->bmin + ptr->bmax) << nColorShift) / |
550 | 0 | 2), |
551 | 0 | 255}; |
552 | 0 | GDALSetColorEntry(hColorTable, i, &sEntry); |
553 | 0 | } |
554 | 0 | } |
555 | |
|
556 | 0 | end_and_cleanup: |
557 | 0 | CPLFree(pabyRedLine); |
558 | 0 | CPLFree(pabyGreenLine); |
559 | 0 | CPLFree(pabyBlueLine); |
560 | | |
561 | | // We're done with the boxes now. |
562 | 0 | CPLFree(box_list); |
563 | 0 | freeboxes = nullptr; |
564 | 0 | usedboxes = nullptr; |
565 | |
|
566 | 0 | if (panHistogram == nullptr) |
567 | 0 | CPLFree(histogram); |
568 | |
|
569 | 0 | return err; |
570 | 0 | } Unexecuted instantiation: int GDALComputeMedianCutPCTInternal<unsigned int>(void*, void*, void*, unsigned char*, unsigned char*, unsigned char*, int (*)(int, int, void*), int, int, unsigned int*, void*, int (*)(double, char const*, void*), void*) Unexecuted instantiation: int GDALComputeMedianCutPCTInternal<unsigned long long>(void*, void*, void*, unsigned char*, unsigned char*, unsigned char*, int (*)(int, int, void*), int, int, unsigned long long*, void*, int (*)(double, char const*, void*), void*) |
571 | | |
572 | | /************************************************************************/ |
573 | | /* largest_box() */ |
574 | | /************************************************************************/ |
575 | | |
576 | | static Colorbox *largest_box(Colorbox *usedboxes) |
577 | 0 | { |
578 | 0 | Colorbox *b = nullptr; |
579 | |
|
580 | 0 | for (Colorbox *p = usedboxes; p != nullptr; p = p->next) |
581 | 0 | { |
582 | 0 | if ((p->rmax > p->rmin || p->gmax > p->gmin || p->bmax > p->bmin) && |
583 | 0 | (b == nullptr || p->total > b->total)) |
584 | 0 | { |
585 | 0 | b = p; |
586 | 0 | } |
587 | 0 | } |
588 | 0 | return b; |
589 | 0 | } |
590 | | |
591 | | static void shrinkboxFromBand(Colorbox *ptr, const GByte *pabyRedBand, |
592 | | const GByte *pabyGreenBand, |
593 | | const GByte *pabyBlueBand, GUIntBig nPixels) |
594 | 0 | { |
595 | 0 | int rmin_new = 255; |
596 | 0 | int rmax_new = 0; |
597 | 0 | int gmin_new = 255; |
598 | 0 | int gmax_new = 0; |
599 | 0 | int bmin_new = 255; |
600 | 0 | int bmax_new = 0; |
601 | 0 | for (GUIntBig i = 0; i < nPixels; i++) |
602 | 0 | { |
603 | 0 | const int iR = pabyRedBand[i]; |
604 | 0 | const int iG = pabyGreenBand[i]; |
605 | 0 | const int iB = pabyBlueBand[i]; |
606 | 0 | if (iR >= ptr->rmin && iR <= ptr->rmax && iG >= ptr->gmin && |
607 | 0 | iG <= ptr->gmax && iB >= ptr->bmin && iB <= ptr->bmax) |
608 | 0 | { |
609 | 0 | if (iR < rmin_new) |
610 | 0 | rmin_new = iR; |
611 | 0 | if (iR > rmax_new) |
612 | 0 | rmax_new = iR; |
613 | 0 | if (iG < gmin_new) |
614 | 0 | gmin_new = iG; |
615 | 0 | if (iG > gmax_new) |
616 | 0 | gmax_new = iG; |
617 | 0 | if (iB < bmin_new) |
618 | 0 | bmin_new = iB; |
619 | 0 | if (iB > bmax_new) |
620 | 0 | bmax_new = iB; |
621 | 0 | } |
622 | 0 | } |
623 | |
|
624 | 0 | CPLAssert(rmin_new >= ptr->rmin && rmin_new <= rmax_new && |
625 | 0 | rmax_new <= ptr->rmax); |
626 | 0 | CPLAssert(gmin_new >= ptr->gmin && gmin_new <= gmax_new && |
627 | 0 | gmax_new <= ptr->gmax); |
628 | 0 | CPLAssert(bmin_new >= ptr->bmin && bmin_new <= bmax_new && |
629 | 0 | bmax_new <= ptr->bmax); |
630 | 0 | ptr->rmin = rmin_new; |
631 | 0 | ptr->rmax = rmax_new; |
632 | 0 | ptr->gmin = gmin_new; |
633 | 0 | ptr->gmax = gmax_new; |
634 | 0 | ptr->bmin = bmin_new; |
635 | 0 | ptr->bmax = bmax_new; |
636 | 0 | } |
637 | | |
638 | | static void shrinkboxFromHashHistogram(Colorbox *box, |
639 | | const HashHistogram *psHashHistogram) |
640 | 0 | { |
641 | 0 | if (box->rmax > box->rmin) |
642 | 0 | { |
643 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
644 | 0 | { |
645 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
646 | 0 | { |
647 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
648 | 0 | { |
649 | 0 | if (FindColorCount(psHashHistogram, |
650 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
651 | 0 | { |
652 | 0 | box->rmin = ir; |
653 | 0 | goto have_rmin; |
654 | 0 | } |
655 | 0 | } |
656 | 0 | } |
657 | 0 | } |
658 | 0 | } |
659 | 0 | have_rmin: |
660 | 0 | if (box->rmax > box->rmin) |
661 | 0 | { |
662 | 0 | for (int ir = box->rmax; ir >= box->rmin; --ir) |
663 | 0 | { |
664 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
665 | 0 | { |
666 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
667 | 0 | { |
668 | 0 | if (FindColorCount(psHashHistogram, |
669 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
670 | 0 | { |
671 | 0 | box->rmax = ir; |
672 | 0 | goto have_rmax; |
673 | 0 | } |
674 | 0 | } |
675 | 0 | } |
676 | 0 | } |
677 | 0 | } |
678 | | |
679 | 0 | have_rmax: |
680 | 0 | if (box->gmax > box->gmin) |
681 | 0 | { |
682 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
683 | 0 | { |
684 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
685 | 0 | { |
686 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
687 | 0 | { |
688 | 0 | if (FindColorCount(psHashHistogram, |
689 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
690 | 0 | { |
691 | 0 | box->gmin = ig; |
692 | 0 | goto have_gmin; |
693 | 0 | } |
694 | 0 | } |
695 | 0 | } |
696 | 0 | } |
697 | 0 | } |
698 | | |
699 | 0 | have_gmin: |
700 | 0 | if (box->gmax > box->gmin) |
701 | 0 | { |
702 | 0 | for (int ig = box->gmax; ig >= box->gmin; --ig) |
703 | 0 | { |
704 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
705 | 0 | { |
706 | 0 | int ib = box->bmin; |
707 | 0 | for (; ib <= box->bmax; ++ib) |
708 | 0 | { |
709 | 0 | if (FindColorCount(psHashHistogram, |
710 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
711 | 0 | { |
712 | 0 | box->gmax = ig; |
713 | 0 | goto have_gmax; |
714 | 0 | } |
715 | 0 | } |
716 | 0 | } |
717 | 0 | } |
718 | 0 | } |
719 | | |
720 | 0 | have_gmax: |
721 | 0 | if (box->bmax > box->bmin) |
722 | 0 | { |
723 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
724 | 0 | { |
725 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
726 | 0 | { |
727 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
728 | 0 | { |
729 | 0 | if (FindColorCount(psHashHistogram, |
730 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
731 | 0 | { |
732 | 0 | box->bmin = ib; |
733 | 0 | goto have_bmin; |
734 | 0 | } |
735 | 0 | } |
736 | 0 | } |
737 | 0 | } |
738 | 0 | } |
739 | | |
740 | 0 | have_bmin: |
741 | 0 | if (box->bmax > box->bmin) |
742 | 0 | { |
743 | 0 | for (int ib = box->bmax; ib >= box->bmin; --ib) |
744 | 0 | { |
745 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
746 | 0 | { |
747 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
748 | 0 | { |
749 | 0 | if (FindColorCount(psHashHistogram, |
750 | 0 | MAKE_COLOR_CODE(ir, ig, ib)) != 0) |
751 | 0 | { |
752 | 0 | box->bmax = ib; |
753 | 0 | goto have_bmax; |
754 | 0 | } |
755 | 0 | } |
756 | 0 | } |
757 | 0 | } |
758 | 0 | } |
759 | | |
760 | 0 | have_bmax:; |
761 | 0 | } |
762 | | |
763 | | /************************************************************************/ |
764 | | /* splitbox() */ |
765 | | /************************************************************************/ |
766 | | template <class T> |
767 | | static void splitbox(Colorbox *ptr, const T *histogram, |
768 | | const HashHistogram *psHashHistogram, int nCLevels, |
769 | | Colorbox **pfreeboxes, Colorbox **pusedboxes, |
770 | | GByte *pabyRedBand, GByte *pabyGreenBand, |
771 | | GByte *pabyBlueBand, T nPixels) |
772 | 0 | { |
773 | 0 | T hist2[256] = {}; |
774 | 0 | int first = 0; |
775 | 0 | int last = 0; |
776 | |
|
777 | 0 | enum |
778 | 0 | { |
779 | 0 | RED, |
780 | 0 | GREEN, |
781 | 0 | BLUE |
782 | 0 | } axis; |
783 | | |
784 | | // See which axis is the largest, do a histogram along that axis. Split at |
785 | | // median point. Contract both new boxes to fit points and return. |
786 | 0 | { |
787 | 0 | int i = ptr->rmax - ptr->rmin; |
788 | 0 | if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin) |
789 | 0 | axis = RED; |
790 | 0 | else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin) |
791 | 0 | axis = GREEN; |
792 | 0 | else |
793 | 0 | axis = BLUE; |
794 | 0 | } |
795 | | // Get histogram along longest axis. |
796 | 0 | const GUInt32 nIters = (ptr->rmax - ptr->rmin + 1) * |
797 | 0 | (ptr->gmax - ptr->gmin + 1) * |
798 | 0 | (ptr->bmax - ptr->bmin + 1); |
799 | |
|
800 | 0 | switch (axis) |
801 | 0 | { |
802 | 0 | case RED: |
803 | 0 | { |
804 | 0 | if (nPixels != 0 && nIters > nPixels) |
805 | 0 | { |
806 | 0 | const int rmin = ptr->rmin; |
807 | 0 | const int rmax = ptr->rmax; |
808 | 0 | const int gmin = ptr->gmin; |
809 | 0 | const int gmax = ptr->gmax; |
810 | 0 | const int bmin = ptr->bmin; |
811 | 0 | const int bmax = ptr->bmax; |
812 | 0 | for (T iPixel = 0; iPixel < nPixels; iPixel++) |
813 | 0 | { |
814 | 0 | int iR = pabyRedBand[iPixel]; |
815 | 0 | int iG = pabyGreenBand[iPixel]; |
816 | 0 | int iB = pabyBlueBand[iPixel]; |
817 | 0 | if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax && |
818 | 0 | iB >= bmin && iB <= bmax) |
819 | 0 | { |
820 | 0 | hist2[iR]++; |
821 | 0 | } |
822 | 0 | } |
823 | 0 | } |
824 | 0 | else if (psHashHistogram) |
825 | 0 | { |
826 | 0 | T *histp = &hist2[ptr->rmin]; |
827 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
828 | 0 | { |
829 | 0 | *histp = 0; |
830 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
831 | 0 | { |
832 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
833 | 0 | { |
834 | 0 | *histp += FindColorCount( |
835 | 0 | psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib)); |
836 | 0 | } |
837 | 0 | } |
838 | 0 | histp++; |
839 | 0 | } |
840 | 0 | } |
841 | 0 | else |
842 | 0 | { |
843 | 0 | T *histp = &hist2[ptr->rmin]; |
844 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
845 | 0 | { |
846 | 0 | *histp = 0; |
847 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
848 | 0 | { |
849 | 0 | const T *iptr = |
850 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, ptr->bmin); |
851 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
852 | 0 | *histp += *iptr++; |
853 | 0 | } |
854 | 0 | histp++; |
855 | 0 | } |
856 | 0 | } |
857 | 0 | first = ptr->rmin; |
858 | 0 | last = ptr->rmax; |
859 | 0 | break; |
860 | 0 | } |
861 | 0 | case GREEN: |
862 | 0 | { |
863 | 0 | if (nPixels != 0 && nIters > nPixels) |
864 | 0 | { |
865 | 0 | const int rmin = ptr->rmin; |
866 | 0 | const int rmax = ptr->rmax; |
867 | 0 | const int gmin = ptr->gmin; |
868 | 0 | const int gmax = ptr->gmax; |
869 | 0 | const int bmin = ptr->bmin; |
870 | 0 | const int bmax = ptr->bmax; |
871 | 0 | for (T iPixel = 0; iPixel < nPixels; iPixel++) |
872 | 0 | { |
873 | 0 | const int iR = pabyRedBand[iPixel]; |
874 | 0 | const int iG = pabyGreenBand[iPixel]; |
875 | 0 | const int iB = pabyBlueBand[iPixel]; |
876 | 0 | if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax && |
877 | 0 | iB >= bmin && iB <= bmax) |
878 | 0 | { |
879 | 0 | hist2[iG]++; |
880 | 0 | } |
881 | 0 | } |
882 | 0 | } |
883 | 0 | else if (psHashHistogram) |
884 | 0 | { |
885 | 0 | T *histp = &hist2[ptr->gmin]; |
886 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
887 | 0 | { |
888 | 0 | *histp = 0; |
889 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
890 | 0 | { |
891 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
892 | 0 | { |
893 | 0 | *histp += FindColorCount( |
894 | 0 | psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib)); |
895 | 0 | } |
896 | 0 | } |
897 | 0 | histp++; |
898 | 0 | } |
899 | 0 | } |
900 | 0 | else |
901 | 0 | { |
902 | 0 | T *histp = &hist2[ptr->gmin]; |
903 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
904 | 0 | { |
905 | 0 | *histp = 0; |
906 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
907 | 0 | { |
908 | 0 | const T *iptr = |
909 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, ptr->bmin); |
910 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
911 | 0 | *histp += *iptr++; |
912 | 0 | } |
913 | 0 | histp++; |
914 | 0 | } |
915 | 0 | } |
916 | 0 | first = ptr->gmin; |
917 | 0 | last = ptr->gmax; |
918 | 0 | break; |
919 | 0 | } |
920 | 0 | case BLUE: |
921 | 0 | { |
922 | 0 | if (nPixels != 0 && nIters > nPixels) |
923 | 0 | { |
924 | 0 | const int rmin = ptr->rmin; |
925 | 0 | const int rmax = ptr->rmax; |
926 | 0 | const int gmin = ptr->gmin; |
927 | 0 | const int gmax = ptr->gmax; |
928 | 0 | const int bmin = ptr->bmin; |
929 | 0 | const int bmax = ptr->bmax; |
930 | 0 | for (T iPixel = 0; iPixel < nPixels; iPixel++) |
931 | 0 | { |
932 | 0 | const int iR = pabyRedBand[iPixel]; |
933 | 0 | const int iG = pabyGreenBand[iPixel]; |
934 | 0 | const int iB = pabyBlueBand[iPixel]; |
935 | 0 | if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax && |
936 | 0 | iB >= bmin && iB <= bmax) |
937 | 0 | { |
938 | 0 | hist2[iB]++; |
939 | 0 | } |
940 | 0 | } |
941 | 0 | } |
942 | 0 | else if (psHashHistogram) |
943 | 0 | { |
944 | 0 | T *histp = &hist2[ptr->bmin]; |
945 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
946 | 0 | { |
947 | 0 | *histp = 0; |
948 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
949 | 0 | { |
950 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
951 | 0 | { |
952 | 0 | *histp += FindColorCount( |
953 | 0 | psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib)); |
954 | 0 | } |
955 | 0 | } |
956 | 0 | histp++; |
957 | 0 | } |
958 | 0 | } |
959 | 0 | else |
960 | 0 | { |
961 | 0 | T *histp = &hist2[ptr->bmin]; |
962 | 0 | for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib) |
963 | 0 | { |
964 | 0 | *histp = 0; |
965 | 0 | for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir) |
966 | 0 | { |
967 | 0 | const T *iptr = |
968 | 0 | HISTOGRAM(histogram, nCLevels, ir, ptr->gmin, ib); |
969 | 0 | for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig) |
970 | 0 | { |
971 | 0 | *histp += *iptr; |
972 | 0 | iptr += nCLevels; |
973 | 0 | } |
974 | 0 | } |
975 | 0 | histp++; |
976 | 0 | } |
977 | 0 | } |
978 | 0 | first = ptr->bmin; |
979 | 0 | last = ptr->bmax; |
980 | 0 | break; |
981 | 0 | } |
982 | 0 | } |
983 | | // Find median point. |
984 | 0 | T *histp = &hist2[first]; |
985 | 0 | int i = first; // TODO(schwehr): Rename i. |
986 | 0 | { |
987 | 0 | T sum = 0; |
988 | 0 | T sum2 = static_cast<T>(ptr->total / 2); |
989 | 0 | for (; i <= last && (sum += *histp++) < sum2; ++i) |
990 | 0 | { |
991 | 0 | } |
992 | 0 | } |
993 | 0 | if (i == first) |
994 | 0 | i++; |
995 | | |
996 | | // Create new box, re-allocate points. |
997 | 0 | Colorbox *new_cb = *pfreeboxes; |
998 | 0 | *pfreeboxes = new_cb->next; |
999 | 0 | if (*pfreeboxes) |
1000 | 0 | (*pfreeboxes)->prev = nullptr; |
1001 | 0 | if (*pusedboxes) |
1002 | 0 | (*pusedboxes)->prev = new_cb; |
1003 | 0 | new_cb->next = *pusedboxes; |
1004 | 0 | *pusedboxes = new_cb; |
1005 | |
|
1006 | 0 | histp = &hist2[first]; |
1007 | 0 | { |
1008 | 0 | T sum1 = 0; |
1009 | 0 | for (int j = first; j < i; j++) |
1010 | 0 | sum1 += *histp++; |
1011 | 0 | T sum2 = 0; |
1012 | 0 | for (int j = i; j <= last; j++) |
1013 | 0 | sum2 += *histp++; |
1014 | 0 | new_cb->total = sum1; |
1015 | 0 | ptr->total = sum2; |
1016 | 0 | } |
1017 | 0 | new_cb->rmin = ptr->rmin; |
1018 | 0 | new_cb->rmax = ptr->rmax; |
1019 | 0 | new_cb->gmin = ptr->gmin; |
1020 | 0 | new_cb->gmax = ptr->gmax; |
1021 | 0 | new_cb->bmin = ptr->bmin; |
1022 | 0 | new_cb->bmax = ptr->bmax; |
1023 | 0 | switch (axis) |
1024 | 0 | { |
1025 | 0 | case RED: |
1026 | 0 | new_cb->rmax = i - 1; |
1027 | 0 | ptr->rmin = i; |
1028 | 0 | break; |
1029 | 0 | case GREEN: |
1030 | 0 | new_cb->gmax = i - 1; |
1031 | 0 | ptr->gmin = i; |
1032 | 0 | break; |
1033 | 0 | case BLUE: |
1034 | 0 | new_cb->bmax = i - 1; |
1035 | 0 | ptr->bmin = i; |
1036 | 0 | break; |
1037 | 0 | } |
1038 | | |
1039 | 0 | if (nPixels != 0 && |
1040 | 0 | static_cast<T>(new_cb->rmax - new_cb->rmin + 1) * |
1041 | 0 | static_cast<T>(new_cb->gmax - new_cb->gmin + 1) * |
1042 | 0 | static_cast<T>(new_cb->bmax - new_cb->bmin + 1) > |
1043 | 0 | nPixels) |
1044 | 0 | { |
1045 | 0 | shrinkboxFromBand(new_cb, pabyRedBand, pabyGreenBand, pabyBlueBand, |
1046 | 0 | nPixels); |
1047 | 0 | } |
1048 | 0 | else if (psHashHistogram != nullptr) |
1049 | 0 | { |
1050 | 0 | shrinkboxFromHashHistogram(new_cb, psHashHistogram); |
1051 | 0 | } |
1052 | 0 | else |
1053 | 0 | { |
1054 | 0 | shrinkbox(new_cb, histogram, nCLevels); |
1055 | 0 | } |
1056 | |
|
1057 | 0 | if (nPixels != 0 && static_cast<T>(ptr->rmax - ptr->rmin + 1) * |
1058 | 0 | static_cast<T>(ptr->gmax - ptr->gmin + 1) * |
1059 | 0 | static_cast<T>(ptr->bmax - ptr->bmin + 1) > |
1060 | 0 | nPixels) |
1061 | 0 | { |
1062 | 0 | shrinkboxFromBand(ptr, pabyRedBand, pabyGreenBand, pabyBlueBand, |
1063 | 0 | nPixels); |
1064 | 0 | } |
1065 | 0 | else if (psHashHistogram != nullptr) |
1066 | 0 | { |
1067 | 0 | shrinkboxFromHashHistogram(ptr, psHashHistogram); |
1068 | 0 | } |
1069 | 0 | else |
1070 | 0 | { |
1071 | 0 | shrinkbox(ptr, histogram, nCLevels); |
1072 | 0 | } |
1073 | 0 | } Unexecuted instantiation: gdalmediancut.cpp:void splitbox<unsigned int>(colorbox*, unsigned int const*, HashHistogram const*, int, colorbox**, colorbox**, unsigned char*, unsigned char*, unsigned char*, unsigned int) Unexecuted instantiation: gdalmediancut.cpp:void splitbox<unsigned long long>(colorbox*, unsigned long long const*, HashHistogram const*, int, colorbox**, colorbox**, unsigned char*, unsigned char*, unsigned char*, unsigned long long) |
1074 | | |
1075 | | /************************************************************************/ |
1076 | | /* shrinkbox() */ |
1077 | | /************************************************************************/ |
1078 | | template <class T> |
1079 | | static void shrinkbox(Colorbox *box, const T *histogram, int nCLevels) |
1080 | 0 | { |
1081 | 0 | if (box->rmax > box->rmin) |
1082 | 0 | { |
1083 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
1084 | 0 | { |
1085 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
1086 | 0 | { |
1087 | 0 | const T *histp = |
1088 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin); |
1089 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
1090 | 0 | { |
1091 | 0 | if (*histp++ != 0) |
1092 | 0 | { |
1093 | 0 | box->rmin = ir; |
1094 | 0 | goto have_rmin; |
1095 | 0 | } |
1096 | 0 | } |
1097 | 0 | } |
1098 | 0 | } |
1099 | 0 | } |
1100 | 0 | have_rmin: |
1101 | 0 | if (box->rmax > box->rmin) |
1102 | 0 | { |
1103 | 0 | for (int ir = box->rmax; ir >= box->rmin; --ir) |
1104 | 0 | { |
1105 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
1106 | 0 | { |
1107 | 0 | const T *histp = |
1108 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin); |
1109 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
1110 | 0 | { |
1111 | 0 | if (*histp++ != 0) |
1112 | 0 | { |
1113 | 0 | box->rmax = ir; |
1114 | 0 | goto have_rmax; |
1115 | 0 | } |
1116 | 0 | } |
1117 | 0 | } |
1118 | 0 | } |
1119 | 0 | } |
1120 | | |
1121 | 0 | have_rmax: |
1122 | 0 | if (box->gmax > box->gmin) |
1123 | 0 | { |
1124 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
1125 | 0 | { |
1126 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
1127 | 0 | { |
1128 | 0 | const T *histp = |
1129 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin); |
1130 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
1131 | 0 | { |
1132 | 0 | if (*histp++ != 0) |
1133 | 0 | { |
1134 | 0 | box->gmin = ig; |
1135 | 0 | goto have_gmin; |
1136 | 0 | } |
1137 | 0 | } |
1138 | 0 | } |
1139 | 0 | } |
1140 | 0 | } |
1141 | | |
1142 | 0 | have_gmin: |
1143 | 0 | if (box->gmax > box->gmin) |
1144 | 0 | { |
1145 | 0 | for (int ig = box->gmax; ig >= box->gmin; --ig) |
1146 | 0 | { |
1147 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
1148 | 0 | { |
1149 | 0 | const T *histp = |
1150 | 0 | HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin); |
1151 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
1152 | 0 | { |
1153 | 0 | if (*histp++ != 0) |
1154 | 0 | { |
1155 | 0 | box->gmax = ig; |
1156 | 0 | goto have_gmax; |
1157 | 0 | } |
1158 | 0 | } |
1159 | 0 | } |
1160 | 0 | } |
1161 | 0 | } |
1162 | | |
1163 | 0 | have_gmax: |
1164 | 0 | if (box->bmax > box->bmin) |
1165 | 0 | { |
1166 | 0 | for (int ib = box->bmin; ib <= box->bmax; ++ib) |
1167 | 0 | { |
1168 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
1169 | 0 | { |
1170 | 0 | const T *histp = |
1171 | 0 | HISTOGRAM(histogram, nCLevels, ir, box->gmin, ib); |
1172 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
1173 | 0 | { |
1174 | 0 | if (*histp != 0) |
1175 | 0 | { |
1176 | 0 | box->bmin = ib; |
1177 | 0 | goto have_bmin; |
1178 | 0 | } |
1179 | 0 | histp += nCLevels; |
1180 | 0 | } |
1181 | 0 | } |
1182 | 0 | } |
1183 | 0 | } |
1184 | | |
1185 | 0 | have_bmin: |
1186 | 0 | if (box->bmax > box->bmin) |
1187 | 0 | { |
1188 | 0 | for (int ib = box->bmax; ib >= box->bmin; --ib) |
1189 | 0 | { |
1190 | 0 | for (int ir = box->rmin; ir <= box->rmax; ++ir) |
1191 | 0 | { |
1192 | 0 | const T *histp = |
1193 | 0 | HISTOGRAM(histogram, nCLevels, ir, box->gmin, ib); |
1194 | 0 | for (int ig = box->gmin; ig <= box->gmax; ++ig) |
1195 | 0 | { |
1196 | 0 | if (*histp != 0) |
1197 | 0 | { |
1198 | 0 | box->bmax = ib; |
1199 | 0 | goto have_bmax; |
1200 | 0 | } |
1201 | 0 | histp += nCLevels; |
1202 | 0 | } |
1203 | 0 | } |
1204 | 0 | } |
1205 | 0 | } |
1206 | | |
1207 | 0 | have_bmax:; |
1208 | 0 | } Unexecuted instantiation: gdalmediancut.cpp:void shrinkbox<unsigned int>(colorbox*, unsigned int const*, int) Unexecuted instantiation: gdalmediancut.cpp:void shrinkbox<unsigned long long>(colorbox*, unsigned long long const*, int) |
1209 | | |
1210 | | // Explicitly instantiate template functions. |
1211 | | template int GDALComputeMedianCutPCTInternal<GUInt32>( |
1212 | | GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue, |
1213 | | GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand, |
1214 | | int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits, |
1215 | | GUInt32 *panHistogram, GDALColorTableH hColorTable, |
1216 | | GDALProgressFunc pfnProgress, void *pProgressArg); |
1217 | | |
1218 | | template int GDALComputeMedianCutPCTInternal<GUIntBig>( |
1219 | | GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue, |
1220 | | GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand, |
1221 | | int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits, |
1222 | | GUIntBig *panHistogram, GDALColorTableH hColorTable, |
1223 | | GDALProgressFunc pfnProgress, void *pProgressArg); |