Leptonica  1.82.0
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  PROCNAME("pixColorSegment");
144 
145  if (!pixs)
146  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
147  if (pixGetDepth(pixs) != 32)
148  return (PIX *)ERROR_PTR("must be rgb color", procName, NULL);
149 
150  /* Phase 1; original segmentation */
151  pixd = pixColorSegmentCluster(pixs, maxdist, maxcolors, debugflag);
152  if (!pixd)
153  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
154  if (debugflag) {
155  lept_mkdir("lept/segment");
156  pixWriteDebug("/tmp/lept/segment/colorseg1.png", pixd, IFF_PNG);
157  }
158 
159  /* Phase 2; refinement in pixel assignment */
160  countarray = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
161  pixAssignToNearestColor(pixd, pixs, NULL, LEVEL_IN_OCTCUBE, countarray);
162  if (debugflag)
163  pixWriteDebug("/tmp/lept/segment/colorseg2.png", pixd, IFF_PNG);
164 
165  /* Phase 3: noise removal by separately closing each color */
166  pixColorSegmentClean(pixd, selsize, countarray);
167  LEPT_FREE(countarray);
168  if (debugflag)
169  pixWriteDebug("/tmp/lept/segment/colorseg3.png", pixd, IFF_PNG);
170 
171  /* Phase 4: removal of colors with small population and
172  * reassignment of pixels to remaining colors */
173  pixColorSegmentRemoveColors(pixd, pixs, finalcolors);
174  return pixd;
175 }
176 
177 
200 PIX *
202  l_int32 maxdist,
203  l_int32 maxcolors,
204  l_int32 debugflag)
205 {
206 l_int32 w, h, newmaxdist, ret, niters, ncolors, success;
207 PIX *pixd;
208 PIXCMAP *cmap;
209 
210  PROCNAME("pixColorSegmentCluster");
211 
212  if (!pixs)
213  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
214  if (pixGetDepth(pixs) != 32)
215  return (PIX *)ERROR_PTR("must be rgb color", procName, NULL);
216 
217  pixGetDimensions(pixs, &w, &h, NULL);
218  if ((pixd = pixCreate(w, h, 8)) == NULL)
219  return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
220  cmap = pixcmapCreate(8);
221  pixSetColormap(pixd, cmap);
222  pixCopyResolution(pixd, pixs);
223 
224  newmaxdist = maxdist;
225  niters = 0;
226  success = TRUE;
227  while (1) {
228  ret = pixColorSegmentTryCluster(pixd, pixs, newmaxdist,
229  maxcolors, debugflag);
230  niters++;
231  if (!ret) {
232  ncolors = pixcmapGetCount(cmap);
233  if (debugflag)
234  L_INFO("Success with %d colors after %d iters\n", procName,
235  ncolors, niters);
236  break;
237  }
238  if (niters == MAX_ALLOWED_ITERATIONS) {
239  L_WARNING("too many iters; newmaxdist = %d\n",
240  procName, newmaxdist);
241  success = FALSE;
242  break;
243  }
244  newmaxdist = (l_int32)(DIST_EXPAND_FACT * (l_float32)newmaxdist);
245  }
246 
247  if (!success) {
248  pixDestroy(&pixd);
249  return (PIX *)ERROR_PTR("failure in phase 1", procName, NULL);
250  }
251 
252  return pixd;
253 }
254 
255 
271 static l_int32
273  PIX *pixs,
274  l_int32 maxdist,
275  l_int32 maxcolors,
276  l_int32 debugflag)
277 {
278 l_int32 rmap[256], gmap[256], bmap[256];
279 l_int32 w, h, wpls, wpld, i, j, k, found, ret, index, ncolors;
280 l_int32 rval, gval, bval, dist2, maxdist2;
281 l_int32 countarray[256];
282 l_int32 rsum[256], gsum[256], bsum[256];
283 l_uint32 *ppixel;
284 l_uint32 *datas, *datad, *lines, *lined;
285 PIXCMAP *cmap;
286 
287  PROCNAME("pixColorSegmentTryCluster");
288 
289  if (!pixs)
290  return ERROR_INT("pixs not defined", procName, 1);
291  if (!pixd)
292  return ERROR_INT("pixd not defined", procName, 1);
293 
294  w = pixGetWidth(pixs);
295  h = pixGetHeight(pixs);
296  maxdist2 = maxdist * maxdist;
297  cmap = pixGetColormap(pixd);
298  pixcmapClear(cmap);
299  for (k = 0; k < 256; k++) {
300  rsum[k] = gsum[k] = bsum[k] = 0;
301  rmap[k] = gmap[k] = bmap[k] = 0;
302  }
303 
304  datas = pixGetData(pixs);
305  datad = pixGetData(pixd);
306  wpls = pixGetWpl(pixs);
307  wpld = pixGetWpl(pixd);
308  ncolors = 0;
309  for (i = 0; i < h; i++) {
310  lines = datas + i * wpls;
311  lined = datad + i * wpld;
312  for (j = 0; j < w; j++) {
313  ppixel = lines + j;
314  rval = GET_DATA_BYTE(ppixel, COLOR_RED);
315  gval = GET_DATA_BYTE(ppixel, COLOR_GREEN);
316  bval = GET_DATA_BYTE(ppixel, COLOR_BLUE);
317  ncolors = pixcmapGetCount(cmap);
318  found = FALSE;
319  for (k = 0; k < ncolors; k++) {
320  dist2 = (rval - rmap[k]) * (rval - rmap[k]) +
321  (gval - gmap[k]) * (gval - gmap[k]) +
322  (bval - bmap[k]) * (bval - bmap[k]);
323  if (dist2 <= maxdist2) { /* take it; greedy */
324  found = TRUE;
325  SET_DATA_BYTE(lined, j, k);
326  countarray[k]++;
327  rsum[k] += rval;
328  gsum[k] += gval;
329  bsum[k] += bval;
330  break;
331  }
332  }
333  if (!found) { /* Add a new color */
334  ret = pixcmapAddNewColor(cmap, rval, gval, bval, &index);
335 /* lept_stderr(
336  "index = %d, (i,j) = (%d,%d), rgb = (%d, %d, %d)\n",
337  index, i, j, rval, gval, bval); */
338  if (ret == 0 && index < maxcolors) {
339  countarray[index] = 1;
340  SET_DATA_BYTE(lined, j, index);
341  rmap[index] = rval;
342  gmap[index] = gval;
343  bmap[index] = bval;
344  rsum[index] = rval;
345  gsum[index] = gval;
346  bsum[index] = bval;
347  } else {
348  if (debugflag) {
349  L_INFO("maxcolors exceeded for maxdist = %d\n",
350  procName, maxdist);
351  }
352  return 1;
353  }
354  }
355  }
356  }
357 
358  /* Replace the colors in the colormap by the averages */
359  for (k = 0; k < ncolors; k++) {
360  rval = rsum[k] / countarray[k];
361  gval = gsum[k] / countarray[k];
362  bval = bsum[k] / countarray[k];
363  pixcmapResetColor(cmap, k, rval, gval, bval);
364  }
365 
366  return 0;
367 }
368 
369 
412 l_ok
414  PIX *pixs,
415  PIX *pixm,
416  l_int32 level,
417  l_int32 *countarray)
418 {
419 l_int32 w, h, wpls, wpld, wplm, i, j, success;
420 l_int32 rval, gval, bval, index;
421 l_int32 *cmaptab;
422 l_uint32 octindex;
423 l_uint32 *rtab, *gtab, *btab;
424 l_uint32 *ppixel;
425 l_uint32 *datas, *datad, *datam, *lines, *lined, *linem;
426 PIXCMAP *cmap;
427 
428  PROCNAME("pixAssignToNearestColor");
429 
430  if (!pixd)
431  return ERROR_INT("pixd not defined", procName, 1);
432  if ((cmap = pixGetColormap(pixd)) == NULL)
433  return ERROR_INT("cmap not found", procName, 1);
434  if (!pixs)
435  return ERROR_INT("pixs not defined", procName, 1);
436  if (pixGetDepth(pixs) != 32)
437  return ERROR_INT("pixs not 32 bpp", procName, 1);
438  if (level < 1 || level > 6)
439  return ERROR_INT("level not in [1 ... 6]", procName, 1);
440 
441  /* Set up the tables to map rgb to the nearest colormap index */
442  success = TRUE;
443  makeRGBToIndexTables(level, &rtab, &gtab, &btab);
444  cmaptab = pixcmapToOctcubeLUT(cmap, level, L_MANHATTAN_DISTANCE);
445  if (!rtab || !gtab || !btab || !cmaptab) {
446  L_ERROR("failure to make a table\n", procName);
447  success = FALSE;
448  goto cleanup_arrays;
449  }
450 
451  pixGetDimensions(pixs, &w, &h, NULL);
452  datas = pixGetData(pixs);
453  datad = pixGetData(pixd);
454  wpls = pixGetWpl(pixs);
455  wpld = pixGetWpl(pixd);
456  if (pixm) {
457  datam = pixGetData(pixm);
458  wplm = pixGetWpl(pixm);
459  }
460  for (i = 0; i < h; i++) {
461  lines = datas + i * wpls;
462  lined = datad + i * wpld;
463  if (pixm)
464  linem = datam + i * wplm;
465  for (j = 0; j < w; j++) {
466  if (pixm) {
467  if (!GET_DATA_BIT(linem, j))
468  continue;
469  }
470  ppixel = lines + j;
471  rval = GET_DATA_BYTE(ppixel, COLOR_RED);
472  gval = GET_DATA_BYTE(ppixel, COLOR_GREEN);
473  bval = GET_DATA_BYTE(ppixel, COLOR_BLUE);
474  /* Map from rgb to octcube index */
475  getOctcubeIndexFromRGB(rval, gval, bval, rtab, gtab, btab,
476  &octindex);
477  /* Map from octcube index to nearest colormap index */
478  index = cmaptab[octindex];
479  if (countarray)
480  countarray[index]++;
481  SET_DATA_BYTE(lined, j, index);
482  }
483  }
484 
485 cleanup_arrays:
486  LEPT_FREE(cmaptab);
487  LEPT_FREE(rtab);
488  LEPT_FREE(gtab);
489  LEPT_FREE(btab);
490  return (success) ? 0 : 1;
491 }
492 
493 
512 l_ok
514  l_int32 selsize,
515  l_int32 *countarray)
516 {
517 l_int32 i, ncolors, val;
518 l_uint32 val32;
519 NUMA *na, *nasi;
520 PIX *pixt1, *pixt2;
521 PIXCMAP *cmap;
522 
523  PROCNAME("pixColorSegmentClean");
524 
525  if (!pixs)
526  return ERROR_INT("pixs not defined", procName, 1);
527  if (pixGetDepth(pixs) != 8)
528  return ERROR_INT("pixs not 8 bpp", procName, 1);
529  if ((cmap = pixGetColormap(pixs)) == NULL)
530  return ERROR_INT("cmap not found", procName, 1);
531  if (!countarray)
532  return ERROR_INT("countarray not defined", procName, 1);
533  if (selsize <= 1)
534  return 0; /* nothing to do */
535 
536  /* Sort colormap indices in decreasing order of pixel population */
537  ncolors = pixcmapGetCount(cmap);
538  na = numaCreate(ncolors);
539  for (i = 0; i < ncolors; i++)
540  numaAddNumber(na, countarray[i]);
542  numaDestroy(&na);
543  if (!nasi)
544  return ERROR_INT("nasi not made", procName, 1);
545 
546  /* For each color, in order of decreasing population,
547  * do a closing and absorb the added pixels. Note that
548  * if the closing removes pixels at the border, they'll
549  * still appear in the xor and will be properly (re)set. */
550  for (i = 0; i < ncolors; i++) {
551  numaGetIValue(nasi, i, &val);
552  pixt1 = pixGenerateMaskByValue(pixs, val, 1);
553  pixt2 = pixCloseSafeCompBrick(NULL, pixt1, selsize, selsize);
554  pixXor(pixt2, pixt2, pixt1); /* pixels to be added to type 'val' */
555  pixcmapGetColor32(cmap, val, &val32);
556  pixSetMasked(pixs, pixt2, val32); /* add them */
557  pixDestroy(&pixt1);
558  pixDestroy(&pixt2);
559  }
560  numaDestroy(&nasi);
561  return 0;
562 }
563 
564 
584 l_ok
586  PIX *pixs,
587  l_int32 finalcolors)
588 {
589 l_int32 i, ncolors, index, tempindex;
590 l_int32 *tab;
591 l_uint32 tempcolor;
592 NUMA *na, *nasi;
593 PIX *pixm;
594 PIXCMAP *cmap;
595 
596  PROCNAME("pixColorSegmentRemoveColors");
597 
598  if (!pixd)
599  return ERROR_INT("pixd not defined", procName, 1);
600  if (pixGetDepth(pixd) != 8)
601  return ERROR_INT("pixd not 8 bpp", procName, 1);
602  if ((cmap = pixGetColormap(pixd)) == NULL)
603  return ERROR_INT("cmap not found", procName, 1);
604  if (!pixs)
605  return ERROR_INT("pixs not defined", procName, 1);
606  ncolors = pixcmapGetCount(cmap);
607  if (finalcolors >= ncolors) /* few enough colors already; nothing to do */
608  return 0;
609 
610  /* Generate a mask over all pixels that are not in the
611  * 'finalcolors' most populated colors. Save the colormap
612  * index of any one of the retained colors in 'tempindex'.
613  * The LUT has values 0 for the 'finalcolors' most populated colors,
614  * which will be retained; and 1 for the rest, which are marked
615  * by fg pixels in pixm and will be removed. */
616  na = pixGetCmapHistogram(pixd, 1);
617  if ((nasi = numaGetSortIndex(na, L_SORT_DECREASING)) == NULL) {
618  numaDestroy(&na);
619  return ERROR_INT("nasi not made", procName, 1);
620  }
621  numaGetIValue(nasi, finalcolors - 1, &tempindex); /* retain down to this */
622  pixcmapGetColor32(cmap, tempindex, &tempcolor); /* use this color */
623  tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
624  for (i = finalcolors; i < ncolors; i++) {
625  numaGetIValue(nasi, i, &index);
626  tab[index] = 1;
627  }
628 
629  pixm = pixMakeMaskFromLUT(pixd, tab);
630  LEPT_FREE(tab);
631 
632  /* Reassign the masked pixels temporarily to the saved index
633  * (tempindex). This guarantees that no pixels are labeled by
634  * a colormap index of any colors that will be removed.
635  * The actual value doesn't matter, as long as it's one
636  * of the retained colors, because these pixels will later
637  * be reassigned based on the full set of colors retained
638  * in the colormap. */
639  pixSetMasked(pixd, pixm, tempcolor);
640 
641  /* Now remove unused colors from the colormap. This reassigns
642  * image pixels as required. */
643  pixRemoveUnusedColors(pixd);
644 
645  /* Finally, reassign the pixels under the mask (those that were
646  * given a 'tempindex' value) to the nearest color in the colormap.
647  * This is the function used in phase 2 on all image pixels; here
648  * it is only used on the masked pixels given by pixm. */
649  pixAssignToNearestColor(pixd, pixs, pixm, LEVEL_IN_OCTCUBE, NULL);
650 
651  pixDestroy(&pixm);
652  numaDestroy(&na);
653  numaDestroy(&nasi);
654  return 0;
655 }
#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:708
PIXCMAP * pixcmapCreate(l_int32 depth)
pixcmapCreate()
Definition: colormap.c:125
l_ok pixcmapAddNewColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval, l_int32 *pindex)
pixcmapAddNewColor()
Definition: colormap.c:496
l_ok pixcmapGetColor32(PIXCMAP *cmap, l_int32 index, l_uint32 *pval32)
pixcmapGetColor32()
Definition: colormap.c:864
l_ok pixcmapResetColor(PIXCMAP *cmap, l_int32 index, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapResetColor()
Definition: colormap.c:966
l_ok pixcmapClear(PIXCMAP *cmap)
pixcmapClear()
Definition: colormap.c:801
l_ok makeRGBToIndexTables(l_int32 cqlevels, l_uint32 **prtab, l_uint32 **pgtab, l_uint32 **pbtab)
makeRGBToIndexTables()
Definition: colorquant1.c:1353
l_int32 * pixcmapToOctcubeLUT(PIXCMAP *cmap, l_int32 level, l_int32 metric)
pixcmapToOctcubeLUT()
Definition: colorquant1.c:3850
l_ok pixRemoveUnusedColors(PIX *pixs)
pixRemoveUnusedColors()
Definition: colorquant1.c:3936
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:1462
l_ok pixColorSegmentRemoveColors(PIX *pixd, PIX *pixs, l_int32 finalcolors)
pixColorSegmentRemoveColors()
Definition: colorseg.c:585
PIX * pixColorSegmentCluster(PIX *pixs, l_int32 maxdist, l_int32 maxcolors, l_int32 debugflag)
pixColorSegmentCluster()
Definition: colorseg.c:201
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:272
l_ok pixAssignToNearestColor(PIX *pixd, PIX *pixs, PIX *pixm, l_int32 level, l_int32 *countarray)
pixAssignToNearestColor()
Definition: colorseg.c:413
l_ok pixColorSegmentClean(PIX *pixs, l_int32 selsize, l_int32 *countarray)
pixColorSegmentClean()
Definition: colorseg.c:513
PIX * pixGenerateMaskByValue(PIX *pixs, l_int32 val, l_int32 usecmap)
pixGenerateMaskByValue()
Definition: grayquant.c:816
PIX * pixCloseSafeCompBrick(PIX *pixd, PIX *pixs, l_int32 hsize, l_int32 vsize)
pixCloseSafeCompBrick()
Definition: morph.c:1682
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:366
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:754
NUMA * numaGetSortIndex(NUMA *na, l_int32 sortorder)
numaGetSortIndex()
Definition: numafunc1.c:2751
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
l_ok pixSetColormap(PIX *pix, PIXCMAP *colormap)
pixSetColormap()
Definition: pix1.c:1699
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
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:1688
PIX * pixMakeMaskFromLUT(PIX *pixs, l_int32 *tab)
pixMakeMaskFromLUT()
Definition: pix3.c:1062
NUMA * pixGetCmapHistogram(PIX *pixs, l_int32 factor)
pixGetCmapHistogram()
Definition: pix4.c:633
@ COLOR_BLUE
Definition: pix.h:206
@ COLOR_RED
Definition: pix.h:204
@ COLOR_GREEN
Definition: pix.h:205
@ L_SORT_DECREASING
Definition: pix.h:730
@ L_MANHATTAN_DISTANCE
Definition: pix.h:946
Definition: array.h:71
Definition: pix.h:139
l_int32 lept_mkdir(const char *subdir)
lept_mkdir()
Definition: utils2.c:2218