Leptonica  1.83.1
Image processing and image analysis suite
colorseg.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
42 #ifdef HAVE_CONFIG_H
43 #include <config_auto.h>
44 #endif /* HAVE_CONFIG_H */
45 
46 #include "allheaders.h"
47 
48  /* Maximum allowed iterations in Phase 1. */
49 static const l_int32 MAX_ALLOWED_ITERATIONS = 20;
50 
51  /* Factor by which max dist is increased on each iteration */
52 static const l_float32 DIST_EXPAND_FACT = 1.3;
53 
54  /* Octcube division level for computing nearest colormap color using LUT.
55  * Using 4 should suffice for up to 50 - 100 colors, and it is
56  * very fast. Using 5 takes 8 times as long to set up the LUT
57  * for little perceptual gain, even with 100 colors. */
58 static const l_int32 LEVEL_IN_OCTCUBE = 4;
59 
60 
61 static l_int32 pixColorSegmentTryCluster(PIX *pixd, PIX *pixs,
62  l_int32 maxdist, l_int32 maxcolors,
63  l_int32 debugflag);
64 
65 /*------------------------------------------------------------------*
66  * Unsupervised color segmentation *
67  *------------------------------------------------------------------*/
132 PIX *
134  l_int32 maxdist,
135  l_int32 maxcolors,
136  l_int32 selsize,
137  l_int32 finalcolors,
138  l_int32 debugflag)
139 {
140 l_int32 *countarray;
141 PIX *pixd;
142 
143  if (!pixs)
144  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
145  if (pixGetDepth(pixs) != 32)
146  return (PIX *)ERROR_PTR("must be rgb color", __func__, NULL);
147 
148  /* Phase 1; original segmentation */
149  pixd = pixColorSegmentCluster(pixs, maxdist, maxcolors, debugflag);
150  if (!pixd)
151  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
152  if (debugflag) {
153  lept_mkdir("lept/segment");
154  pixWriteDebug("/tmp/lept/segment/colorseg1.png", pixd, IFF_PNG);
155  }
156 
157  /* Phase 2; refinement in pixel assignment */
158  countarray = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
159  pixAssignToNearestColor(pixd, pixs, NULL, LEVEL_IN_OCTCUBE, countarray);
160  if (debugflag)
161  pixWriteDebug("/tmp/lept/segment/colorseg2.png", pixd, IFF_PNG);
162 
163  /* Phase 3: noise removal by separately closing each color */
164  pixColorSegmentClean(pixd, selsize, countarray);
165  LEPT_FREE(countarray);
166  if (debugflag)
167  pixWriteDebug("/tmp/lept/segment/colorseg3.png", pixd, IFF_PNG);
168 
169  /* Phase 4: removal of colors with small population and
170  * reassignment of pixels to remaining colors */
171  pixColorSegmentRemoveColors(pixd, pixs, finalcolors);
172  return pixd;
173 }
174 
175 
198 PIX *
200  l_int32 maxdist,
201  l_int32 maxcolors,
202  l_int32 debugflag)
203 {
204 l_int32 w, h, newmaxdist, ret, niters, ncolors, success;
205 PIX *pixd;
206 PIXCMAP *cmap;
207 
208  if (!pixs)
209  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
210  if (pixGetDepth(pixs) != 32)
211  return (PIX *)ERROR_PTR("must be rgb color", __func__, NULL);
212 
213  pixGetDimensions(pixs, &w, &h, NULL);
214  if ((pixd = pixCreate(w, h, 8)) == NULL)
215  return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
216  cmap = pixcmapCreate(8);
217  pixSetColormap(pixd, cmap);
218  pixCopyResolution(pixd, pixs);
219 
220  newmaxdist = maxdist;
221  niters = 0;
222  success = TRUE;
223  while (1) {
224  ret = pixColorSegmentTryCluster(pixd, pixs, newmaxdist,
225  maxcolors, debugflag);
226  niters++;
227  if (!ret) {
228  ncolors = pixcmapGetCount(cmap);
229  if (debugflag)
230  L_INFO("Success with %d colors after %d iters\n", __func__,
231  ncolors, niters);
232  break;
233  }
234  if (niters == MAX_ALLOWED_ITERATIONS) {
235  L_WARNING("too many iters; newmaxdist = %d\n",
236  __func__, newmaxdist);
237  success = FALSE;
238  break;
239  }
240  newmaxdist = (l_int32)(DIST_EXPAND_FACT * (l_float32)newmaxdist);
241  }
242 
243  if (!success) {
244  pixDestroy(&pixd);
245  return (PIX *)ERROR_PTR("failure in phase 1", __func__, NULL);
246  }
247 
248  return pixd;
249 }
250 
251 
267 static l_int32
269  PIX *pixs,
270  l_int32 maxdist,
271  l_int32 maxcolors,
272  l_int32 debugflag)
273 {
274 l_int32 rmap[256], gmap[256], bmap[256];
275 l_int32 w, h, wpls, wpld, i, j, k, found, ret, index, ncolors;
276 l_int32 rval, gval, bval, dist2, maxdist2;
277 l_int32 countarray[256];
278 l_int32 rsum[256], gsum[256], bsum[256];
279 l_uint32 *ppixel;
280 l_uint32 *datas, *datad, *lines, *lined;
281 PIXCMAP *cmap;
282 
283  if (!pixs)
284  return ERROR_INT("pixs not defined", __func__, 1);
285  if (!pixd)
286  return ERROR_INT("pixd not defined", __func__, 1);
287 
288  w = pixGetWidth(pixs);
289  h = pixGetHeight(pixs);
290  maxdist2 = maxdist * maxdist;
291  cmap = pixGetColormap(pixd);
292  pixcmapClear(cmap);
293  for (k = 0; k < 256; k++) {
294  rsum[k] = gsum[k] = bsum[k] = 0;
295  rmap[k] = gmap[k] = bmap[k] = 0;
296  }
297 
298  datas = pixGetData(pixs);
299  datad = pixGetData(pixd);
300  wpls = pixGetWpl(pixs);
301  wpld = pixGetWpl(pixd);
302  ncolors = 0;
303  for (i = 0; i < h; i++) {
304  lines = datas + i * wpls;
305  lined = datad + i * wpld;
306  for (j = 0; j < w; j++) {
307  ppixel = lines + j;
308  rval = GET_DATA_BYTE(ppixel, COLOR_RED);
309  gval = GET_DATA_BYTE(ppixel, COLOR_GREEN);
310  bval = GET_DATA_BYTE(ppixel, COLOR_BLUE);
311  ncolors = pixcmapGetCount(cmap);
312  found = FALSE;
313  for (k = 0; k < ncolors; k++) {
314  dist2 = (rval - rmap[k]) * (rval - rmap[k]) +
315  (gval - gmap[k]) * (gval - gmap[k]) +
316  (bval - bmap[k]) * (bval - bmap[k]);
317  if (dist2 <= maxdist2) { /* take it; greedy */
318  found = TRUE;
319  SET_DATA_BYTE(lined, j, k);
320  countarray[k]++;
321  rsum[k] += rval;
322  gsum[k] += gval;
323  bsum[k] += bval;
324  break;
325  }
326  }
327  if (!found) { /* Add a new color */
328  ret = pixcmapAddNewColor(cmap, rval, gval, bval, &index);
329 /* lept_stderr(
330  "index = %d, (i,j) = (%d,%d), rgb = (%d, %d, %d)\n",
331  index, i, j, rval, gval, bval); */
332  if (ret == 0 && index < maxcolors) {
333  countarray[index] = 1;
334  SET_DATA_BYTE(lined, j, index);
335  rmap[index] = rval;
336  gmap[index] = gval;
337  bmap[index] = bval;
338  rsum[index] = rval;
339  gsum[index] = gval;
340  bsum[index] = bval;
341  } else {
342  if (debugflag) {
343  L_INFO("maxcolors exceeded for maxdist = %d\n",
344  __func__, maxdist);
345  }
346  return 1;
347  }
348  }
349  }
350  }
351 
352  /* Replace the colors in the colormap by the averages */
353  for (k = 0; k < ncolors; k++) {
354  rval = rsum[k] / countarray[k];
355  gval = gsum[k] / countarray[k];
356  bval = bsum[k] / countarray[k];
357  pixcmapResetColor(cmap, k, rval, gval, bval);
358  }
359 
360  return 0;
361 }
362 
363 
406 l_ok
408  PIX *pixs,
409  PIX *pixm,
410  l_int32 level,
411  l_int32 *countarray)
412 {
413 l_int32 w, h, wpls, wpld, wplm, i, j, success;
414 l_int32 rval, gval, bval, index;
415 l_int32 *cmaptab;
416 l_uint32 octindex;
417 l_uint32 *rtab, *gtab, *btab;
418 l_uint32 *ppixel;
419 l_uint32 *datas, *datad, *datam, *lines, *lined, *linem;
420 PIXCMAP *cmap;
421 
422  if (!pixd)
423  return ERROR_INT("pixd not defined", __func__, 1);
424  if ((cmap = pixGetColormap(pixd)) == NULL)
425  return ERROR_INT("cmap not found", __func__, 1);
426  if (!pixs)
427  return ERROR_INT("pixs not defined", __func__, 1);
428  if (pixGetDepth(pixs) != 32)
429  return ERROR_INT("pixs not 32 bpp", __func__, 1);
430  if (level < 1 || level > 6)
431  return ERROR_INT("level not in [1 ... 6]", __func__, 1);
432 
433  /* Set up the tables to map rgb to the nearest colormap index */
434  success = TRUE;
435  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
436  cmaptab = pixcmapToOctcubeLUT(cmap, level, L_MANHATTAN_DISTANCE);
437  if (!rtab || !gtab || !btab || !cmaptab) {
438  L_ERROR("failure to make a table\n", __func__);
439  success = FALSE;
440  goto cleanup_arrays;
441  }
442 
443  pixGetDimensions(pixs, &w, &h, NULL);
444  datas = pixGetData(pixs);
445  datad = pixGetData(pixd);
446  wpls = pixGetWpl(pixs);
447  wpld = pixGetWpl(pixd);
448  if (pixm) {
449  datam = pixGetData(pixm);
450  wplm = pixGetWpl(pixm);
451  }
452  for (i = 0; i < h; i++) {
453  lines = datas + i * wpls;
454  lined = datad + i * wpld;
455  if (pixm)
456  linem = datam + i * wplm;
457  for (j = 0; j < w; j++) {
458  if (pixm) {
459  if (!GET_DATA_BIT(linem, j))
460  continue;
461  }
462  ppixel = lines + j;
463  rval = GET_DATA_BYTE(ppixel, COLOR_RED);
464  gval = GET_DATA_BYTE(ppixel, COLOR_GREEN);
465  bval = GET_DATA_BYTE(ppixel, COLOR_BLUE);
466  /* Map from rgb to octcube index */
467  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab,
468  &octindex);
469  /* Map from octcube index to nearest colormap index */
470  index = cmaptab[octindex];
471  if (countarray)
472  countarray[index]++;
473  SET_DATA_BYTE(lined, j, index);
474  }
475  }
476 
477 cleanup_arrays:
478  LEPT_FREE(cmaptab);
479  LEPT_FREE(rtab);
480  LEPT_FREE(gtab);
481  LEPT_FREE(btab);
482  return (success) ? 0 : 1;
483 }
484 
485 
504 l_ok
506  l_int32 selsize,
507  l_int32 *countarray)
508 {
509 l_int32 i, ncolors, val;
510 l_uint32 val32;
511 NUMA *na, *nasi;
512 PIX *pixt1, *pixt2;
513 PIXCMAP *cmap;
514 
515  if (!pixs)
516  return ERROR_INT("pixs not defined", __func__, 1);
517  if (pixGetDepth(pixs) != 8)
518  return ERROR_INT("pixs not 8 bpp", __func__, 1);
519  if ((cmap = pixGetColormap(pixs)) == NULL)
520  return ERROR_INT("cmap not found", __func__, 1);
521  if (!countarray)
522  return ERROR_INT("countarray not defined", __func__, 1);
523  if (selsize <= 1)
524  return 0; /* nothing to do */
525 
526  /* Sort colormap indices in decreasing order of pixel population */
527  ncolors = pixcmapGetCount(cmap);
528  na = numaCreate(ncolors);
529  for (i = 0; i < ncolors; i++)
530  numaAddNumber(na, countarray[i]);
532  numaDestroy(&na);
533  if (!nasi)
534  return ERROR_INT("nasi not made", __func__, 1);
535 
536  /* For each color, in order of decreasing population,
537  * do a closing and absorb the added pixels. Note that
538  * if the closing removes pixels at the border, they'll
539  * still appear in the xor and will be properly (re)set. */
540  for (i = 0; i < ncolors; i++) {
541  numaGetIValue(nasi, i, &val);
542  pixt1 = pixGenerateMaskByValue(pixs, val, 1);
543  pixt2 = pixCloseSafeCompBrick(NULL, pixt1, selsize, selsize);
544  pixXor(pixt2, pixt2, pixt1); /* pixels to be added to type 'val' */
545  pixcmapGetColor32(cmap, val, &val32);
546  pixSetMasked(pixs, pixt2, val32); /* add them */
547  pixDestroy(&pixt1);
548  pixDestroy(&pixt2);
549  }
550  numaDestroy(&nasi);
551  return 0;
552 }
553 
554 
574 l_ok
576  PIX *pixs,
577  l_int32 finalcolors)
578 {
579 l_int32 i, ncolors, index, tempindex;
580 l_int32 *tab;
581 l_uint32 tempcolor;
582 NUMA *na, *nasi;
583 PIX *pixm;
584 PIXCMAP *cmap;
585 
586  if (!pixd)
587  return ERROR_INT("pixd not defined", __func__, 1);
588  if (pixGetDepth(pixd) != 8)
589  return ERROR_INT("pixd not 8 bpp", __func__, 1);
590  if ((cmap = pixGetColormap(pixd)) == NULL)
591  return ERROR_INT("cmap not found", __func__, 1);
592  if (!pixs)
593  return ERROR_INT("pixs not defined", __func__, 1);
594  ncolors = pixcmapGetCount(cmap);
595  if (finalcolors >= ncolors) /* few enough colors already; nothing to do */
596  return 0;
597 
598  /* Generate a mask over all pixels that are not in the
599  * 'finalcolors' most populated colors. Save the colormap
600  * index of any one of the retained colors in 'tempindex'.
601  * The LUT has values 0 for the 'finalcolors' most populated colors,
602  * which will be retained; and 1 for the rest, which are marked
603  * by fg pixels in pixm and will be removed. */
604  na = pixGetCmapHistogram(pixd, 1);
605  if ((nasi = numaGetSortIndex(na, L_SORT_DECREASING)) == NULL) {
606  numaDestroy(&na);
607  return ERROR_INT("nasi not made", __func__, 1);
608  }
609  numaGetIValue(nasi, finalcolors - 1, &tempindex); /* retain down to this */
610  pixcmapGetColor32(cmap, tempindex, &tempcolor); /* use this color */
611  tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
612  for (i = finalcolors; i < ncolors; i++) {
613  numaGetIValue(nasi, i, &index);
614  tab[index] = 1;
615  }
616 
617  pixm = pixMakeMaskFromLUT(pixd, tab);
618  LEPT_FREE(tab);
619 
620  /* Reassign the masked pixels temporarily to the saved index
621  * (tempindex). This guarantees that no pixels are labeled by
622  * a colormap index of any colors that will be removed.
623  * The actual value doesn't matter, as long as it's one
624  * of the retained colors, because these pixels will later
625  * be reassigned based on the full set of colors retained
626  * in the colormap. */
627  pixSetMasked(pixd, pixm, tempcolor);
628 
629  /* Now remove unused colors from the colormap. This reassigns
630  * image pixels as required. */
631  pixRemoveUnusedColors(pixd);
632 
633  /* Finally, reassign the pixels under the mask (those that were
634  * given a 'tempindex' value) to the nearest color in the colormap.
635  * This is the function used in phase 2 on all image pixels; here
636  * it is only used on the masked pixels given by pixm. */
637  pixAssignToNearestColor(pixd, pixs, pixm, LEVEL_IN_OCTCUBE, NULL);
638 
639  pixDestroy(&pixm);
640  numaDestroy(&na);
641  numaDestroy(&nasi);
642  return 0;
643 }
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
#define GET_DATA_BIT(pdata, n)
Definition: arrayaccess.h:123
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:683
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:126
l_ok pixcmapAddNewColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval, l_int32 *pindex)
pixcmapAddNewColor()
Definition: colormap.c:481
l_ok pixcmapGetColor32(PIXCMAP *cmap, l_int32 index, l_uint32 *pval32)
pixcmapGetColor32()
Definition: colormap.c:827
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:923
l_ok pixcmapClear(PIXCMAP *cmap)
pixcmapClear()
Definition: colormap.c:768
l_ok makeRGBToIndexTables(l_int32 cqlevels, l_uint32 **prtab, l_uint32 **pgtab, l_uint32 **pbtab)
makeRGBToIndexTables()
Definition: colorquant1.c:1342
l_int32 * pixcmapToOctcubeLUT(PIXCMAP *cmap, l_int32 level, l_int32 metric)
pixcmapToOctcubeLUT()
Definition: colorquant1.c:3807
l_ok pixRemoveUnusedColors(PIX *pixs)
pixRemoveUnusedColors()
Definition: colorquant1.c:3891
void getOctcubeIndexFromRGB(l_int32 rval, l_int32 gval, l_int32 bval, l_uint32 *rtab, l_uint32 *gtab, l_uint32 *btab, l_uint32 *pindex)
getOctcubeIndexFromRGB()
Definition: colorquant1.c:1449
l_ok pixColorSegmentRemoveColors(PIX *pixd, PIX *pixs, l_int32 finalcolors)
pixColorSegmentRemoveColors()
Definition: colorseg.c:575
PIX * pixColorSegmentCluster(PIX *pixs, l_int32 maxdist, l_int32 maxcolors, l_int32 debugflag)
pixColorSegmentCluster()
Definition: colorseg.c:199
PIX * pixColorSegment(PIX *pixs, l_int32 maxdist, l_int32 maxcolors, l_int32 selsize, l_int32 finalcolors, l_int32 debugflag)
pixColorSegment()
Definition: colorseg.c:133
static l_int32 pixColorSegmentTryCluster(PIX *pixd, PIX *pixs, l_int32 maxdist, l_int32 maxcolors, l_int32 debugflag)
pixColorSegmentTryCluster()
Definition: colorseg.c:268
l_ok pixAssignToNearestColor(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 level, l_int32 *countarray)
pixAssignToNearestColor()
Definition: colorseg.c:407
l_ok pixColorSegmentClean(PIX *pixs, l_int32 selsize, l_int32 *countarray)
pixColorSegmentClean()
Definition: colorseg.c:505
PIX * pixGenerateMaskByValue(PIX *pixs, l_int32 val, l_int32 usecmap)
pixGenerateMaskByValue()
Definition: grayquant.c:802
PIX * pixCloseSafeCompBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixCloseSafeCompBrick()
Definition: morph.c:1644
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:357
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:720
NUMA * numaGetSortIndex(NUMA *na, l_int32 sortorder)
numaGetSortIndex()
Definition: numafunc1.c:2664
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1642
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1582
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:608
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1074
PIX * pixCreate(l_int32 width, l_int32 height, l_int32 depth)
pixCreate()
Definition: pix1.c:315
l_ok pixSetMasked(PIX *pixd, PIX *pixm, l_uint32 val)
pixSetMasked()
Definition: pix3.c:163
PIX * pixXor(PIX *pixd, PIX *pixs1, PIX *pixs2)
pixXor()
Definition: pix3.c:1654
PIX * pixMakeMaskFromLUT(PIX *pixs, l_int32 *tab)
pixMakeMaskFromLUT()
Definition: pix3.c:1046
NUMA * pixGetCmapHistogram(PIX *pixs, l_int32 factor)
pixGetCmapHistogram()
Definition: pix4.c:621
@ COLOR_BLUE
Definition: pix.h:330
@ COLOR_RED
Definition: pix.h:328
@ COLOR_GREEN
Definition: pix.h:329
@ L_SORT_DECREASING
Definition: pix.h:523
@ L_MANHATTAN_DISTANCE
Definition: pix.h:739
l_int32 lept_mkdir(const char *subdir)
lept_mkdir()
Definition: utils2.c:2138