Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/ccthin.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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
27 /*!
28 * \file ccthin.c
29 * <pre>
30 *
31 * PIXA *pixaThinConnected()
32 * PIX *pixThinConnected()
33 * PIX *pixThinConnectedBySet()
34 * SELA *selaMakeThinSets()
35 * </pre>
36 */
37
38 #ifdef HAVE_CONFIG_H
39 #include <config_auto.h>
40 #endif /* HAVE_CONFIG_H */
41
42 #include "allheaders.h"
43
44 /* ------------------------------------------------------------
45 * The sels used here (and their rotated counterparts) are the
46 * useful 3x3 Sels for thinning. They are defined in sel2.c,
47 * and the sets are constructed in selaMakeThinSets().
48 * The notation is based on "Connectivity-preserving morphological
49 * image transformations", a version of which can be found at
50 * http://www.leptonica.com/papers/conn.pdf
51 * ------------------------------------------------------------ */
52
53 /*----------------------------------------------------------------*
54 * CC-preserving thinning *
55 *----------------------------------------------------------------*/
56 /*!
57 * \brief pixaThinConnected()
58 *
59 * \param[in] pixas of 1 bpp pix
60 * \param[in] type L_THIN_FG, L_THIN_BG
61 * \param[in] connectivity 4 or 8
62 * \param[in] maxiters max number of iters allowed;
63 * use 0 to iterate until completion
64 * \return pixds, or NULL on error
65 *
66 * <pre>
67 * Notes:
68 * (1) See notes in pixThinConnected().
69 * </pre>
70 */
71 PIXA *
72 pixaThinConnected(PIXA *pixas,
73 l_int32 type,
74 l_int32 connectivity,
75 l_int32 maxiters)
76 {
77 l_int32 i, n, d, same;
78 PIX *pix1, *pix2;
79 PIXA *pixad;
80 SELA *sela;
81
82 if (!pixas)
83 return (PIXA *)ERROR_PTR("pixas not defined", __func__, NULL);
84 if (type != L_THIN_FG && type != L_THIN_BG)
85 return (PIXA *)ERROR_PTR("invalid fg/bg type", __func__, NULL);
86 if (connectivity != 4 && connectivity != 8)
87 return (PIXA *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
88 if (maxiters == 0) maxiters = 10000;
89
90 pixaVerifyDepth(pixas, &same, &d);
91 if (d != 1)
92 return (PIXA *)ERROR_PTR("pix are not all 1 bpp", __func__, NULL);
93
94 if (connectivity == 4)
95 sela = selaMakeThinSets(1, 0);
96 else /* connectivity == 8 */
97 sela = selaMakeThinSets(5, 0);
98
99 n = pixaGetCount(pixas);
100 pixad = pixaCreate(n);
101 for (i = 0; i < n; i++) {
102 pix1 = pixaGetPix(pixas, i, L_CLONE);
103 pix2 = pixThinConnectedBySet(pix1, type, sela, maxiters);
104 pixaAddPix(pixad, pix2, L_INSERT);
105 pixDestroy(&pix1);
106 }
107
108 selaDestroy(&sela);
109 return pixad;
110 }
111
112
113 /*!
114 * \brief pixThinConnected()
115 *
116 * \param[in] pixs 1 bpp
117 * \param[in] type L_THIN_FG, L_THIN_BG
118 * \param[in] connectivity 4 or 8
119 * \param[in] maxiters max number of iters allowed;
120 * use 0 to iterate until completion
121 * \return pixd, or NULL on error
122 *
123 * <pre>
124 * Notes:
125 * (1) See "Connectivity-preserving morphological image transformations,"
126 * Dan S. Bloomberg, in SPIE Visual Communications and Image
127 * Processing, Conference 1606, pp. 320-334, November 1991,
128 * Boston, MA. A web version is available at
129 * http://www.leptonica.com/papers/conn.pdf
130 * (2) This is a simple interface for two of the best iterative
131 * morphological thinning algorithms, for 4-c.c and 8-c.c.
132 * Each iteration uses a mixture of parallel operations
133 * (using several different 3x3 Sels) and serial operations.
134 * Specifically, each thinning iteration consists of
135 * four sequential thinnings from each of four directions.
136 * Each of these thinnings is a parallel composite
137 * operation, where the union of a set of HMTs are set
138 * subtracted from the input. For 4-cc thinning, we
139 * use 3 HMTs in parallel, and for 8-cc thinning we use 4 HMTs.
140 * (3) A "good" thinning algorithm is one that generates a skeleton
141 * that is near the medial axis and has neither pruned
142 * real branches nor left extra dendritic branches.
143 * (4) Duality between operations on fg and bg require switching
144 * the connectivity. To thin the foreground, which is the usual
145 * situation, use type == L_THIN_FG. Thickening the foreground
146 * is equivalent to thinning the background (type == L_THIN_BG),
147 * where the alternate connectivity gets preserved.
148 * For example, to thicken the fg with 2 rounds of iterations
149 * using 4-c.c., thin the bg using Sels that preserve 8-connectivity:
150 * Pix *pix = pixThinConnected(pixs, L_THIN_BG, 8, 2);
151 * (5) This makes and destroys the sela set each time. It's not a large
152 * overhead, but if you are calling this thousands of times on
153 * very small images, you can avoid the overhead; e.g.
154 * Sela *sela = selaMakeThinSets(1, 0); // for 4-c.c.
155 * Pix *pix = pixThinConnectedBySet(pixs, L_THIN_FG, sela, 0);
156 * using set 1 for 4-c.c. and set 5 for 8-c.c operations.
157 * </pre>
158 */
159 PIX *
160 pixThinConnected(PIX *pixs,
161 l_int32 type,
162 l_int32 connectivity,
163 l_int32 maxiters)
164 {
165 PIX *pixd;
166 SELA *sela;
167
168 if (!pixs)
169 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
170 if (pixGetDepth(pixs) != 1)
171 return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
172 if (type != L_THIN_FG && type != L_THIN_BG)
173 return (PIX *)ERROR_PTR("invalid fg/bg type", __func__, NULL);
174 if (connectivity != 4 && connectivity != 8)
175 return (PIX *)ERROR_PTR("connectivity not 4 or 8", __func__, NULL);
176 if (maxiters == 0) maxiters = 10000;
177
178 if (connectivity == 4)
179 sela = selaMakeThinSets(1, 0);
180 else /* connectivity == 8 */
181 sela = selaMakeThinSets(5, 0);
182
183 pixd = pixThinConnectedBySet(pixs, type, sela, maxiters);
184
185 selaDestroy(&sela);
186 return pixd;
187 }
188
189
190 /*!
191 * \brief pixThinConnectedBySet()
192 *
193 * \param[in] pixs 1 bpp
194 * \param[in] type L_THIN_FG, L_THIN_BG
195 * \param[in] sela of Sels for parallel composite HMTs
196 * \param[in] maxiters max number of iters allowed;
197 * use 0 to iterate until completion
198 * \return pixd, or NULL on error
199 *
200 * <pre>
201 * Notes:
202 * (1) See notes in pixThinConnected().
203 * (2) This takes a sela representing one of 11 sets of HMT Sels.
204 * The HMTs from this set are run in parallel and the result
205 * is OR'd before being subtracted from the source. For each
206 * iteration, this "parallel" thin is performed four times
207 * sequentially, for sels rotated by 90 degrees in all four
208 * directions.
209 * (3) The "parallel" and "sequential" nomenclature is standard
210 * in digital filtering. Here, "parallel" operations work on the
211 * same source (pixd), and accumulate the results in a temp
212 * image before actually applying them to the source (in this
213 * case, using an in-place subtraction). "Sequential" operations
214 * operate directly on the source (pixd) to produce the result
215 * (in this case, with four sequential thinning operations, one
216 * from each of four directions).
217 * </pre>
218 */
219 PIX *
220 pixThinConnectedBySet(PIX *pixs,
221 l_int32 type,
222 SELA *sela,
223 l_int32 maxiters)
224 {
225 l_int32 i, j, r, nsels, same;
226 PIXA *pixahmt;
227 PIX **pixhmt; /* array owned by pixahmt; do not destroy! */
228 PIX *pix1, *pix2, *pixd;
229 SEL *sel, *selr;
230
231 if (!pixs)
232 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
233 if (pixGetDepth(pixs) != 1)
234 return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
235 if (type != L_THIN_FG && type != L_THIN_BG)
236 return (PIX *)ERROR_PTR("invalid fg/bg type", __func__, NULL);
237 if (!sela)
238 return (PIX *)ERROR_PTR("sela not defined", __func__, NULL);
239 if (maxiters == 0) maxiters = 10000;
240
241 /* Set up array of temp pix to hold hmts */
242 nsels = selaGetCount(sela);
243 pixahmt = pixaCreate(nsels);
244 for (i = 0; i < nsels; i++) {
245 pix1 = pixCreateTemplate(pixs);
246 pixaAddPix(pixahmt, pix1, L_INSERT);
247 }
248 pixhmt = pixaGetPixArray(pixahmt);
249 if (!pixhmt) {
250 pixaDestroy(&pixahmt);
251 return (PIX *)ERROR_PTR("pixhmt array not made", __func__, NULL);
252 }
253
254 /* Set up initial image for fg thinning */
255 if (type == L_THIN_FG)
256 pixd = pixCopy(NULL, pixs);
257 else /* bg thinning */
258 pixd = pixInvert(NULL, pixs);
259
260 /* Thin the fg, with up to maxiters iterations */
261 for (i = 0; i < maxiters; i++) {
262 pix1 = pixCopy(NULL, pixd); /* test for completion */
263 for (r = 0; r < 4; r++) { /* over 90 degree rotations of Sels */
264 for (j = 0; j < nsels; j++) { /* over individual sels in sela */
265 sel = selaGetSel(sela, j); /* not a copy */
266 selr = selRotateOrth(sel, r);
267 pixHMT(pixhmt[j], pixd, selr);
268 selDestroy(&selr);
269 if (j > 0)
270 pixOr(pixhmt[0], pixhmt[0], pixhmt[j]); /* accum result */
271 }
272 pixSubtract(pixd, pixd, pixhmt[0]); /* remove result */
273 }
274 pixEqual(pixd, pix1, &same);
275 pixDestroy(&pix1);
276 if (same) {
277 /* L_INFO("%d iterations to completion\n", __func__, i); */
278 break;
279 }
280 }
281
282 /* This is a bit tricky. If we're thickening the foreground, then
283 * we get a fg border of thickness equal to the number of
284 * iterations. This border is connected to all components that
285 * were initially touching the border, but as it grows, it does
286 * not touch other growing components -- it leaves a 1 pixel wide
287 * background between it and the growing components, and that
288 * thin background prevents the components from growing further.
289 * This border can be entirely removed as follows:
290 * (1) Subtract the original (unthickened) image pixs from the
291 * thickened image. This removes the pixels that were originally
292 * touching the border.
293 * (2) Get all remaining pixels that are connected to the border.
294 * (3) Remove those pixels from the thickened image. */
295 if (type == L_THIN_BG) {
296 pixInvert(pixd, pixd); /* finish with duality */
297 pix1 = pixSubtract(NULL, pixd, pixs);
298 pix2 = pixExtractBorderConnComps(pix1, 4);
299 pixSubtract(pixd, pixd, pix2);
300 pixDestroy(&pix1);
301 pixDestroy(&pix2);
302 }
303
304 pixaDestroy(&pixahmt);
305 return pixd;
306 }
307
308
309 /*!
310 * \brief selaMakeThinSets()
311 *
312 * \param[in] index into specific sets
313 * \param[in] debug 1 to output display of sela
314 * \return sela, or NULL on error
315 *
316 * <pre>
317 * Notes:
318 * (1) These are specific sets of HMTs to be used in parallel for
319 * for thinning from each of four directions.
320 * (2) The sets are indexed as follows:
321 * For thinning (e.g., run to completion):
322 * index = 1 sel_4_1, sel_4_2, sel_4_3
323 * index = 2 sel_4_1, sel_4_5, sel_4_6
324 * index = 3 sel_4_1, sel_4_7, sel_4_7_rot
325 * index = 4 sel_48_1, sel_48_1_rot, sel_48_2
326 * index = 5 sel_8_2, sel_8_3, sel_8_5, sel_8_6
327 * index = 6 sel_8_2, sel_8_3, sel_48_2
328 * index = 7 sel_8_1, sel_8_5, sel_8_6
329 * index = 8 sel_8_2, sel_8_3, sel_8_8, sel_8_9
330 * index = 9 sel_8_5, sel_8_6, sel_8_7, sel_8_7_rot
331 * For thickening (e.g., just a few iterations):
332 * index = 10 sel_4_2, sel_4_3
333 * index = 11 sel_8_4
334 * (3) For a very smooth skeleton, use set 1 for 4 connected and
335 * set 5 for 8 connected thins.
336 * </pre>
337 */
338 SELA *
339 selaMakeThinSets(l_int32 index,
340 l_int32 debug)
341 {
342 SEL *sel;
343 SELA *sela1, *sela2, *sela3;
344
345 if (index < 1 || index > 11)
346 return (SELA *)ERROR_PTR("invalid index", __func__, NULL);
347
348 sela2 = selaCreate(4);
349 switch(index)
350 {
351 case 1:
352 sela1 = sela4ccThin(NULL);
353 selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
354 selaAddSel(sela2, sel, NULL, L_COPY);
355 selaFindSelByName(sela1, "sel_4_2", NULL, &sel);
356 selaAddSel(sela2, sel, NULL, L_COPY);
357 selaFindSelByName(sela1, "sel_4_3", NULL, &sel);
358 selaAddSel(sela2, sel, NULL, L_COPY);
359 break;
360 case 2:
361 sela1 = sela4ccThin(NULL);
362 selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
363 selaAddSel(sela2, sel, NULL, L_COPY);
364 selaFindSelByName(sela1, "sel_4_5", NULL, &sel);
365 selaAddSel(sela2, sel, NULL, L_COPY);
366 selaFindSelByName(sela1, "sel_4_6", NULL, &sel);
367 selaAddSel(sela2, sel, NULL, L_COPY);
368 break;
369 case 3:
370 sela1 = sela4ccThin(NULL);
371 selaFindSelByName(sela1, "sel_4_1", NULL, &sel);
372 selaAddSel(sela2, sel, NULL, L_COPY);
373 selaFindSelByName(sela1, "sel_4_7", NULL, &sel);
374 selaAddSel(sela2, sel, NULL, L_COPY);
375 sel = selRotateOrth(sel, 1);
376 selaAddSel(sela2, sel, "sel_4_7_rot", L_INSERT);
377 break;
378 case 4:
379 sela1 = sela4and8ccThin(NULL);
380 selaFindSelByName(sela1, "sel_48_1", NULL, &sel);
381 selaAddSel(sela2, sel, NULL, L_COPY);
382 sel = selRotateOrth(sel, 1);
383 selaAddSel(sela2, sel, "sel_48_1_rot", L_INSERT);
384 selaFindSelByName(sela1, "sel_48_2", NULL, &sel);
385 selaAddSel(sela2, sel, NULL, L_COPY);
386 break;
387 case 5:
388 sela1 = sela8ccThin(NULL);
389 selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
390 selaAddSel(sela2, sel, NULL, L_COPY);
391 selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
392 selaAddSel(sela2, sel, NULL, L_COPY);
393 selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
394 selaAddSel(sela2, sel, NULL, L_COPY);
395 selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
396 selaAddSel(sela2, sel, NULL, L_COPY);
397 break;
398 case 6:
399 sela1 = sela8ccThin(NULL);
400 sela3 = sela4and8ccThin(NULL);
401 selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
402 selaAddSel(sela2, sel, NULL, L_COPY);
403 selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
404 selaAddSel(sela2, sel, NULL, L_COPY);
405 selaFindSelByName(sela3, "sel_48_2", NULL, &sel);
406 selaAddSel(sela2, sel, NULL, L_COPY);
407 selaDestroy(&sela3);
408 break;
409 case 7:
410 sela1 = sela8ccThin(NULL);
411 selaFindSelByName(sela1, "sel_8_1", NULL, &sel);
412 selaAddSel(sela2, sel, NULL, L_COPY);
413 selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
414 selaAddSel(sela2, sel, NULL, L_COPY);
415 selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
416 selaAddSel(sela2, sel, NULL, L_COPY);
417 break;
418 case 8:
419 sela1 = sela8ccThin(NULL);
420 selaFindSelByName(sela1, "sel_8_2", NULL, &sel);
421 selaAddSel(sela2, sel, NULL, L_COPY);
422 selaFindSelByName(sela1, "sel_8_3", NULL, &sel);
423 selaAddSel(sela2, sel, NULL, L_COPY);
424 selaFindSelByName(sela1, "sel_8_8", NULL, &sel);
425 selaAddSel(sela2, sel, NULL, L_COPY);
426 selaFindSelByName(sela1, "sel_8_9", NULL, &sel);
427 selaAddSel(sela2, sel, NULL, L_COPY);
428 break;
429 case 9:
430 sela1 = sela8ccThin(NULL);
431 selaFindSelByName(sela1, "sel_8_5", NULL, &sel);
432 selaAddSel(sela2, sel, NULL, L_COPY);
433 selaFindSelByName(sela1, "sel_8_6", NULL, &sel);
434 selaAddSel(sela2, sel, NULL, L_COPY);
435 selaFindSelByName(sela1, "sel_8_7", NULL, &sel);
436 selaAddSel(sela2, sel, NULL, L_COPY);
437 sel = selRotateOrth(sel, 1);
438 selaAddSel(sela2, sel, "sel_8_7_rot", L_INSERT);
439 break;
440 case 10: /* thicken for this one; use just a few iterations */
441 sela1 = sela4ccThin(NULL);
442 selaFindSelByName(sela1, "sel_4_2", NULL, &sel);
443 selaAddSel(sela2, sel, NULL, L_COPY);
444 selaFindSelByName(sela1, "sel_4_3", NULL, &sel);
445 selaAddSel(sela2, sel, NULL, L_COPY);
446 break;
447 case 11: /* thicken for this one; use just a few iterations */
448 sela1 = sela8ccThin(NULL);
449 selaFindSelByName(sela1, "sel_8_4", NULL, &sel);
450 selaAddSel(sela2, sel, NULL, L_COPY);
451 break;
452 }
453
454 /* Optionally display the sel set */
455 if (debug) {
456 PIX *pix1;
457 char buf[32];
458 lept_mkdir("/lept/sels");
459 pix1 = selaDisplayInPix(sela2, 35, 3, 15, 4);
460 snprintf(buf, sizeof(buf), "/tmp/lept/sels/set%d.png", index);
461 pixWrite(buf, pix1, IFF_PNG);
462 pixDisplay(pix1, 100, 100);
463 pixDestroy(&pix1);
464 }
465
466 selaDestroy(&sela1);
467 return sela2;
468 }