/*====================================================================*
- Copyright (C) 2001 Leptonica. All rights reserved.
- This software is distributed in the hope that it will be
- useful, but with NO WARRANTY OF ANY KIND.
- No author or distributor accepts responsibility to anyone for the
- consequences of using this software, or for whether it serves any
- particular purpose or works at all, unless he or she says so in
- writing. Everyone is granted permission to copy, modify and
- redistribute this source code, for commercial or non-commercial
- purposes, with the following restrictions: (1) the origin of this
- source code must not be misrepresented; (2) modified versions must
- be plainly marked as such; and (3) this notice may not be removed
- or altered from any source or modified source distribution.
*====================================================================*/
/*
* ccthin.c
*
* PIX *pixThin()
* PIX *pixThinGeneral()
* PIX *pixThinExamples()
*/
#include <stdio.h>
#include <stdlib.h>
#include "allheaders.h"
/* ------------------------------------------------------------
* These sels (and their rotated counterparts) are the useful
* 3x3 Sels for thinning. The notation is based on
* "Connectivity-preserving morphological image transformations,"
* a version of which can be found at
* http://www.leptonica.com/papers/conn.pdf
* ------------------------------------------------------------ */
/* Sels for 4-connected thinning */
static const char *sel_4_1 = " x"
"oCx"
" x";
static const char *sel_4_2 = " x"
"oCx"
" o ";
static const char *sel_4_3 = " o "
"oCx"
" x";
static const char *sel_4_4 = " o "
"oCx"
" o ";
static const char *sel_4_5 = " ox"
"oCx"
" o ";
static const char *sel_4_6 = " o "
"oCx"
" ox";
static const char *sel_4_7 = " xx"
"oCx"
" o ";
static const char *sel_4_8 = " x"
"oCx"
"o x";
static const char *sel_4_9 = "o x"
"oCx"
" x";
/* Sels for 8-connected thinning */
static const char *sel_8_1 = " x "
"oCx"
" x ";
static const char *sel_8_2 = " x "
"oCx"
"o ";
static const char *sel_8_3 = "o "
"oCx"
" x ";
static const char *sel_8_4 = "o "
"oCx"
"o ";
static const char *sel_8_5 = "o x"
"oCx"
"o ";
static const char *sel_8_6 = "o "
"oCx"
"o x";
static const char *sel_8_7 = " x "
"oCx"
"oo ";
static const char *sel_8_8 = " x "
"oCx"
"ox ";
static const char *sel_8_9 = "ox "
"oCx"
" x ";
/* Sels for both 4 and 8-connected thinning */
static const char *sel_48_1 = " xx"
"oCx"
"oo ";
static const char *sel_48_2 = "o x"
"oCx"
"o x";
#ifndef NO_CONSOLE_IO
#define DEBUG_SELS 0
#endif /* ~NO_CONSOLE_IO */
/*----------------------------------------------------------------*
* CC-preserving thinning *
*----------------------------------------------------------------*/
/*!
* pixThin()
*
* Input: pixs (1 bpp)
* type (L_THIN_FG, L_THIN_BG)
* connectivity (4 or 8)
* maxiters (max number of iters allowed; use 0 to iterate
* until completion)
* Return: pixd, or null on error
*
* Notes:
* (1) See "Connectivity-preserving morphological image transformations,"
* Dan S. Bloomberg, in SPIE Visual Communications and Image
* Processing, Conference 1606, pp. 320-334, November 1991,
* Boston, MA. A web version is available at
* http://www.leptonica.com/papers/conn.pdf
* (2) We implement here two of the best iterative
* morphological thinning algorithms, for 4 c.c and 8 c.c.
* Each iteration uses a mixture of parallel operations
* (using several different 3x3 Sels) and serial operations.
* Specifically, each thinning iteration consists of
* four sequential thinnings from each of four directions.
* Each of these thinnings is a parallel composite
* operation, where the union of a set of HMTs are set
* subtracted from the input. For 4-cc thinning, we
* use 3 HMTs in parallel, and for 8-cc thinning we use 4 HMTs.
* (3) A "good" thinning algorithm is one that generates a skeleton
* that is near the medial axis and has neither pruned
* real branches nor left extra dendritic branches.
* (4) To thin the foreground, which is the usual situation,
* use type == L_THIN_FG. Thickening the foreground is equivalent
* to thinning the background (type == L_THIN_BG), where the
* opposite connectivity gets preserved. For example, to thicken
* the fg using 4-connectivity, we thin the bg using Sels that
* preserve 8-connectivity.
*/
PIX *
pixThin(PIX *pixs,
l_int32 type,
l_int32 connectivity,
l_int32 maxiters)
{
PIX *pixd;
SEL *sel;
SELA *sela;
PROCNAME("pixThin");
if (!pixs)
return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
if (pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
if (type != L_THIN_FG && type != L_THIN_BG)
return (PIX *)ERROR_PTR("invalid fg/bg type", procName, NULL);
if (connectivity != 4 && connectivity != 8)
return (PIX *)ERROR_PTR("connectivity not 4 or 8", procName, NULL);
if (maxiters == 0) maxiters = 10000;
sela = selaCreate(4);
if (connectivity == 4) {
sel = selCreateFromString(sel_4_1, 3, 3, "sel_4_1");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_2, 3, 3, "sel_4_2");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_3, 3, 3, "sel_4_3");
selaAddSel(sela, sel, NULL, 0);
} else { /* connectivity == 8 */
sel = selCreateFromString(sel_8_2, 3, 3, "sel_8_2");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_3, 3, 3, "sel_8_3");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_5, 3, 3, "sel_8_5");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_6, 3, 3, "sel_8_6");
selaAddSel(sela, sel, NULL, 0);
}
pixd = pixThinGeneral(pixs, type, sela, maxiters);
selaDestroy(&sela);
return pixd;
}
/*!
* pixThinGeneral()
*
* Input: pixs (1 bpp)
* type (L_THIN_FG, L_THIN_BG)
* sela (of Sels for parallel composite HMTs)
* maxiters (max number of iters allowed; use 0 to iterate
* until completion)
* Return: pixd, or null on error
*
* Notes:
* (1) See notes in pixThin(). That function chooses among
* the best of the Sels for thinning.
* (2) This is a general function that takes a Sela of HMTs
* that are used in parallel for thinning from each
* of four directions. One iteration consists of four
* such parallel thins.
*/
PIX *
pixThinGeneral(PIX *pixs,
l_int32 type,
SELA *sela,
l_int32 maxiters)
{
l_int32 i, j, r, nsels, same;
PIXA *pixahmt;
PIX **pixhmt; /* array owned by pixahmt; do not destroy! */
PIX *pixd, *pixt;
SEL *sel, *selr;
PROCNAME("pixThinGeneral");
if (!pixs)
return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
if (pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
if (type != L_THIN_FG && type != L_THIN_BG)
return (PIX *)ERROR_PTR("invalid fg/bg type", procName, NULL);
if (!sela)
return (PIX *)ERROR_PTR("sela not defined", procName, NULL);
if (maxiters == 0) maxiters = 10000;
/* Set up array of temp pix to hold hmts */
nsels = selaGetCount(sela);
pixahmt = pixaCreate(nsels);
for (i = 0; i < nsels; i++) {
pixt = pixCreateTemplate(pixs);
pixaAddPix(pixahmt, pixt, L_INSERT);
}
pixhmt = pixaGetPixArray(pixahmt);
if (!pixhmt)
return (PIX *)ERROR_PTR("pixhmt array not made", procName, NULL);
#if DEBUG_SELS
pixt = selaDisplayInPix(sela, 35, 3, 15, 4);
pixDisplayWithTitle(pixt, 100, 100, "allsels", 1);
pixDestroy(&pixt);
#endif /* DEBUG_SELS */
/* Set up initial image for fg thinning */
if (type == L_THIN_FG)
pixd = pixCopy(NULL, pixs);
else /* bg thinning */
pixd = pixInvert(NULL, pixs);
/* Thin the fg, with up to maxiters iterations */
for (i = 0; i < maxiters; i++) {
pixt = pixCopy(NULL, pixd); /* test for completion */
for (r = 0; r < 4; r++) { /* over 90 degree rotations of Sels */
for (j = 0; j < nsels; j++) { /* over individual sels in sela */
sel = selaGetSel(sela, j); /* not a copy */
selr = selRotateOrth(sel, r);
pixHMT(pixhmt[j], pixd, selr);
selDestroy(&selr);
if (j > 0)
pixOr(pixhmt[0], pixhmt[0], pixhmt[j]); /* accum result */
}
pixSubtract(pixd, pixd, pixhmt[0]); /* remove result */
}
pixEqual(pixd, pixt, &same);
pixDestroy(&pixt);
if (same) {
L_INFO_INT("%d iterations to completion", procName, i);
break;
}
}
if (type == L_THIN_BG)
pixInvert(pixd, pixd);
pixaDestroy(&pixahmt);
return pixd;
}
/*!
* pixThinExamples()
*
* Input: pixs (1 bpp)
* type (L_THIN_FG, L_THIN_BG)
* index (into specific examples; valid 1-9; see notes)
* maxiters (max number of iters allowed; use 0 to iterate
* until completion)
* selfile (<optional> filename for output sel display)
* Return: pixd, or null on error
*
* Notes:
* (1) See notes in pixThin(). The examples are taken from
* the paper referenced there.
* (2) Here we allow specific sets of HMTs to be used in
* parallel for thinning from each of four directions.
* One iteration consists of four such parallel thins.
* (3) The examples are indexed as follows:
* Thinning (e.g., run to completion):
* index = 1 sel_4_1, sel_4_5, sel_4_6
* index = 2 sel_4_1, sel_4_7, sel_4_7_rot
* index = 3 sel_48_1, sel_48_1_rot, sel_48_2
* index = 4 sel_8_2, sel_8_3, sel_48_2
* index = 5 sel_8_1, sel_8_5, sel_8_6
* index = 6 sel_8_2, sel_8_3, sel_8_8, sel_8_9
* index = 7 sel_8_5, sel_8_6, sel_8_7, sel_8_7_rot
* Thickening:
* index = 8 sel_4_2, sel_4_3 (e.g,, do just a few iterations)
* index = 9 sel_8_4 (e.g., do just a few iterations)
*/
PIX *
pixThinExamples(PIX *pixs,
l_int32 type,
l_int32 index,
l_int32 maxiters,
const char *selfile)
{
PIX *pixd, *pixt;
SEL *sel;
SELA *sela;
PROCNAME("pixThinExamples");
if (!pixs)
return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
if (pixGetDepth(pixs) != 1)
return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
if (type != L_THIN_FG && type != L_THIN_BG)
return (PIX *)ERROR_PTR("invalid fg/bg type", procName, NULL);
if (index < 1 || index > 9)
return (PIX *)ERROR_PTR("invalid index", procName, NULL);
if (maxiters == 0) maxiters = 10000;
switch(index)
{
case 1:
sela = selaCreate(3);
sel = selCreateFromString(sel_4_1, 3, 3, "sel_4_1");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_5, 3, 3, "sel_4_5");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_6, 3, 3, "sel_4_6");
selaAddSel(sela, sel, NULL, 0);
break;
case 2:
sela = selaCreate(3);
sel = selCreateFromString(sel_4_1, 3, 3, "sel_4_1");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_7, 3, 3, "sel_4_7");
selaAddSel(sela, sel, NULL, 0);
sel = selRotateOrth(sel, 1);
selaAddSel(sela, sel, "sel_4_7_rot", 0);
break;
case 3:
sela = selaCreate(3);
sel = selCreateFromString(sel_48_1, 3, 3, "sel_48_1");
selaAddSel(sela, sel, NULL, 0);
sel = selRotateOrth(sel, 1);
selaAddSel(sela, sel, "sel_48_1_rot", 0);
sel = selCreateFromString(sel_48_2, 3, 3, "sel_48_2");
selaAddSel(sela, sel, NULL, 0);
break;
case 4:
sela = selaCreate(3);
sel = selCreateFromString(sel_8_2, 3, 3, "sel_8_2");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_3, 3, 3, "sel_8_3");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_48_2, 3, 3, "sel_48_2");
selaAddSel(sela, sel, NULL, 0);
break;
case 5:
sela = selaCreate(3);
sel = selCreateFromString(sel_8_1, 3, 3, "sel_8_1");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_5, 3, 3, "sel_8_5");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_6, 3, 3, "sel_8_6");
selaAddSel(sela, sel, NULL, 0);
break;
case 6:
sela = selaCreate(4);
sel = selCreateFromString(sel_8_2, 3, 3, "sel_8_2");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_3, 3, 3, "sel_8_3");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_8, 3, 3, "sel_8_8");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_9, 3, 3, "sel_8_9");
selaAddSel(sela, sel, NULL, 0);
break;
case 7:
sela = selaCreate(4);
sel = selCreateFromString(sel_8_5, 3, 3, "sel_8_5");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_6, 3, 3, "sel_8_6");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_8_7, 3, 3, "sel_8_7");
selaAddSel(sela, sel, NULL, 0);
sel = selRotateOrth(sel, 1);
selaAddSel(sela, sel, "sel_8_7_rot", 0);
break;
case 8: /* thicken for this one; just a few iterations */
sela = selaCreate(2);
sel = selCreateFromString(sel_4_2, 3, 3, "sel_4_2");
selaAddSel(sela, sel, NULL, 0);
sel = selCreateFromString(sel_4_3, 3, 3, "sel_4_3");
selaAddSel(sela, sel, NULL, 0);
pixt = pixThinGeneral(pixs, type, sela, maxiters);
pixd = pixRemoveBorderConnComps(pixt, 4);
pixDestroy(&pixt);
break;
case 9: /* thicken for this one; just a few iterations */
sela = selaCreate(1);
sel = selCreateFromString(sel_8_4, 3, 3, "sel_8_4");
selaAddSel(sela, sel, NULL, 0);
pixt = pixThinGeneral(pixs, type, sela, maxiters);
pixd = pixRemoveBorderConnComps(pixt, 4);
pixDestroy(&pixt);
break;
default:
return (PIX *)ERROR_PTR("invalid index", procName, NULL);
}
if (index <= 7)
pixd = pixThinGeneral(pixs, type, sela, maxiters);
/* Optionally display the sels */
if (selfile) {
pixt = selaDisplayInPix(sela, 35, 3, 15, 4);
pixWrite(selfile, pixt, IFF_PNG);
pixDestroy(&pixt);
}
selaDestroy(&sela);
return pixd;
}