Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/runlength.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 runlength.c
29 * <pre>
30 *
31 * Label pixels by membership in runs
32 * PIX *pixStrokeWidthTransform()
33 * static PIX *pixFindMinRunsOrthogonal()
34 * PIX *pixRunlengthTransform()
35 *
36 * Find runs along horizontal and vertical lines
37 * l_int32 pixFindHorizontalRuns()
38 * l_int32 pixFindVerticalRuns()
39 *
40 * Find max runs along horizontal and vertical lines
41 * l_int32 pixFindMaxRuns()
42 * l_int32 pixFindMaxHorizontalRunOnLine()
43 * l_int32 pixFindMaxVerticalRunOnLine()
44 *
45 * Compute runlength-to-membership transform on a line
46 * l_int32 runlengthMembershipOnLine()
47 *
48 * Make byte position LUT
49 * l_int32 makeMSBitLocTab()
50 *
51 * Here we're handling runs of either black or white pixels on 1 bpp
52 * images. The directions of the runs in the stroke width transform
53 * are selectable from given sets of angles. Most of the other runs
54 * are oriented either horizontally along the raster lines or
55 * vertically along pixel columns.
56 * </pre>
57 */
58
59 #ifdef HAVE_CONFIG_H
60 #include <config_auto.h>
61 #endif /* HAVE_CONFIG_H */
62
63 #include <string.h>
64 #include <math.h>
65 #include "allheaders.h"
66
67 static PIX *pixFindMinRunsOrthogonal(PIX *pixs, l_float32 angle, l_int32 depth);
68
69 /*-----------------------------------------------------------------------*
70 * Label pixels by membership in runs *
71 *-----------------------------------------------------------------------*/
72 /*!
73 * \brief pixStrokeWidthTransform()
74 *
75 * \param[in] pixs 1 bpp
76 * \param[in] color 0 for white runs, 1 for black runs
77 * \param[in] depth of pixd: 8 or 16 bpp
78 * \param[in] nangles 2, 4, 6 or 8
79 * \return pixd 8 or 16 bpp, or NULL on error
80 *
81 * <pre>
82 * Notes:
83 * (1) The dest Pix is 8 or 16 bpp, with the pixel values
84 * equal to the stroke width in which it is a member.
85 * The values are clipped to the max pixel value if necessary.
86 * (2) %color determines if we're labelling white or black strokes.
87 * (3) A pixel that is not a member of the chosen color gets
88 * value 0; it belongs to a width of length 0 of the
89 * chosen color.
90 * (4) This chooses, for each dest pixel, the minimum of sets
91 * of runlengths through each pixel. Here are the sets:
92 * nangles increment set
93 * ------- --------- --------------------------------
94 * 2 90 {0, 90}
95 * 4 45 {0, 45, 90, 135}
96 * 6 30 {0, 30, 60, 90, 120, 150}
97 * 8 22.5 {0, 22.5, 45, 67.5, 90, 112.5, 135, 157.5}
98 * (5) Runtime scales linearly with (%nangles - 2).
99 * </pre>
100 */
101 PIX *
102 pixStrokeWidthTransform(PIX *pixs,
103 l_int32 color,
104 l_int32 depth,
105 l_int32 nangles)
106 {
107 l_float32 angle, pi;
108 PIX *pixh, *pixv, *pixt, *pixg1, *pixg2, *pixg3, *pixg4;
109
110 if (!pixs || pixGetDepth(pixs) != 1)
111 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
112 if (depth != 8 && depth != 16)
113 return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", __func__, NULL);
114 if (nangles != 2 && nangles != 4 && nangles != 6 && nangles != 8)
115 return (PIX *)ERROR_PTR("nangles not in {2,4,6,8}", __func__, NULL);
116
117 /* Use fg runs for evaluation */
118 if (color == 0)
119 pixt = pixInvert(NULL, pixs);
120 else
121 pixt = pixClone(pixs);
122
123 /* Find min length at 0 and 90 degrees */
124 pixh = pixRunlengthTransform(pixt, 1, L_HORIZONTAL_RUNS, depth);
125 pixv = pixRunlengthTransform(pixt, 1, L_VERTICAL_RUNS, depth);
126 pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);
127 pixDestroy(&pixh);
128 pixDestroy(&pixv);
129
130 pixg2 = pixg3 = pixg4 = NULL;
131 pi = 3.1415926535f;
132 if (nangles == 4 || nangles == 8) {
133 /* Find min length at +45 and -45 degrees */
134 angle = pi / 4.0f;
135 pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);
136 }
137
138 if (nangles == 6) {
139 /* Find min length at +30 and -60 degrees */
140 angle = pi / 6.0f;
141 pixg2 = pixFindMinRunsOrthogonal(pixt, angle, depth);
142
143 /* Find min length at +60 and -30 degrees */
144 angle = pi / 3.0f;
145 pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);
146 }
147
148 if (nangles == 8) {
149 /* Find min length at +22.5 and -67.5 degrees */
150 angle = pi / 8.0f;
151 pixg3 = pixFindMinRunsOrthogonal(pixt, angle, depth);
152
153 /* Find min length at +67.5 and -22.5 degrees */
154 angle = 3.0 * pi / 8.0f;
155 pixg4 = pixFindMinRunsOrthogonal(pixt, angle, depth);
156 }
157 pixDestroy(&pixt);
158
159 if (nangles > 2)
160 pixMinOrMax(pixg1, pixg1, pixg2, L_CHOOSE_MIN);
161 if (nangles > 4)
162 pixMinOrMax(pixg1, pixg1, pixg3, L_CHOOSE_MIN);
163 if (nangles > 6)
164 pixMinOrMax(pixg1, pixg1, pixg4, L_CHOOSE_MIN);
165 pixDestroy(&pixg2);
166 pixDestroy(&pixg3);
167 pixDestroy(&pixg4);
168 return pixg1;
169 }
170
171
172 /*!
173 * \brief pixFindMinRunsOrthogonal()
174 *
175 * \param[in] pixs 1 bpp
176 * \param[in] angle in radians
177 * \param[in] depth of pixd: 8 or 16 bpp
178 * \return pixd 8 or 16 bpp, or NULL on error
179 *
180 * <pre>
181 * Notes:
182 * (1) This computes, for each fg pixel in pixs, the minimum of
183 * the runlengths going through that pixel in two orthogonal
184 * directions: at %angle and at (90 + %angle).
185 * (2) We use rotation by shear because the forward and backward
186 * rotations by the same angle are exact inverse operations.
187 * As a result, the nonzero pixels in pixd correspond exactly
188 * to the fg pixels in pixs. This is not the case with
189 * sampled rotation, due to spatial quantization. Nevertheless,
190 * the result suffers from lack of exact correspondence
191 * between original and rotated pixels, also due to spatial
192 * quantization, causing some boundary pixels to be
193 * shifted from bg to fg or v.v.
194 * </pre>
195 */
196 static PIX *
197 pixFindMinRunsOrthogonal(PIX *pixs,
198 l_float32 angle,
199 l_int32 depth)
200 {
201 l_int32 w, h, diag, xoff, yoff;
202 PIX *pixb, *pixr, *pixh, *pixv, *pixg1, *pixg2, *pixd;
203 BOX *box;
204
205 if (!pixs || pixGetDepth(pixs) != 1)
206 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
207
208 /* Rasterop into the center of a sufficiently large image
209 * so we don't lose pixels for any rotation angle. */
210 pixGetDimensions(pixs, &w, &h, NULL);
211 diag = (l_int32)(sqrt((l_float64)(w * w + h * h)) + 2.5);
212 xoff = (diag - w) / 2;
213 yoff = (diag - h) / 2;
214 pixb = pixCreate(diag, diag, 1);
215 pixRasterop(pixb, xoff, yoff, w, h, PIX_SRC, pixs, 0, 0);
216
217 /* Rotate about the 'center', get the min of orthogonal transforms,
218 * rotate back, and crop the part corresponding to pixs. */
219 pixr = pixRotateShear(pixb, diag / 2, diag / 2, angle, L_BRING_IN_WHITE);
220 pixh = pixRunlengthTransform(pixr, 1, L_HORIZONTAL_RUNS, depth);
221 pixv = pixRunlengthTransform(pixr, 1, L_VERTICAL_RUNS, depth);
222 pixg1 = pixMinOrMax(NULL, pixh, pixv, L_CHOOSE_MIN);
223 pixg2 = pixRotateShear(pixg1, diag / 2, diag / 2, -angle, L_BRING_IN_WHITE);
224 box = boxCreate(xoff, yoff, w, h);
225 pixd = pixClipRectangle(pixg2, box, NULL);
226
227 pixDestroy(&pixb);
228 pixDestroy(&pixr);
229 pixDestroy(&pixh);
230 pixDestroy(&pixv);
231 pixDestroy(&pixg1);
232 pixDestroy(&pixg2);
233 boxDestroy(&box);
234 return pixd;
235 }
236
237
238 /*!
239 * \brief pixRunlengthTransform()
240 *
241 * \param[in] pixs 1 bpp
242 * \param[in] color 0 for white runs, 1 for black runs
243 * \param[in] direction L_HORIZONTAL_RUNS, L_VERTICAL_RUNS
244 * \param[in] depth 8 or 16 bpp
245 * \return pixd 8 or 16 bpp, or NULL on error
246 *
247 * <pre>
248 * Notes:
249 * (1) The dest Pix is 8 or 16 bpp, with the pixel values
250 * equal to the runlength in which it is a member.
251 * The length is clipped to the max pixel value if necessary.
252 * (2) %color determines if we're labelling white or black runs.
253 * (3) A pixel that is not a member of the chosen color gets
254 * value 0; it belongs to a run of length 0 of the
255 * chosen color.
256 * (4) To convert for maximum dynamic range, either linear or
257 * log, use pixMaxDynamicRange().
258 * </pre>
259 */
260 PIX *
261 pixRunlengthTransform(PIX *pixs,
262 l_int32 color,
263 l_int32 direction,
264 l_int32 depth)
265 {
266 l_int32 i, j, w, h, wpld, bufsize, maxsize, n;
267 l_int32 *start, *end, *buffer;
268 l_uint32 *datad, *lined;
269 PIX *pixt, *pixd;
270
271 if (!pixs)
272 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
273 if (pixGetDepth(pixs) != 1)
274 return (PIX *)ERROR_PTR("pixs not 1 bpp", __func__, NULL);
275 if (depth != 8 && depth != 16)
276 return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", __func__, NULL);
277
278 pixGetDimensions(pixs, &w, &h, NULL);
279 if (direction == L_HORIZONTAL_RUNS)
280 maxsize = 1 + w / 2;
281 else if (direction == L_VERTICAL_RUNS)
282 maxsize = 1 + h / 2;
283 else
284 return (PIX *)ERROR_PTR("invalid direction", __func__, NULL);
285 bufsize = L_MAX(w, h);
286 if (bufsize > 1000000) {
287 L_ERROR("largest image dimension = %d; too big\n", __func__, bufsize);
288 return NULL;
289 }
290
291 if ((pixd = pixCreate(w, h, depth)) == NULL)
292 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
293 datad = pixGetData(pixd);
294 wpld = pixGetWpl(pixd);
295
296 start = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));
297 end = (l_int32 *)LEPT_CALLOC(maxsize, sizeof(l_int32));
298 buffer = (l_int32 *)LEPT_CALLOC(bufsize, sizeof(l_int32));
299
300 /* Use fg runs for evaluation */
301 if (color == 0)
302 pixt = pixInvert(NULL, pixs);
303 else
304 pixt = pixClone(pixs);
305
306 if (direction == L_HORIZONTAL_RUNS) {
307 for (i = 0; i < h; i++) {
308 pixFindHorizontalRuns(pixt, i, start, end, &n);
309 runlengthMembershipOnLine(buffer, w, depth, start, end, n);
310 lined = datad + i * wpld;
311 if (depth == 8) {
312 for (j = 0; j < w; j++)
313 SET_DATA_BYTE(lined, j, buffer[j]);
314 } else { /* depth == 16 */
315 for (j = 0; j < w; j++)
316 SET_DATA_TWO_BYTES(lined, j, buffer[j]);
317 }
318 }
319 } else { /* L_VERTICAL_RUNS */
320 for (j = 0; j < w; j++) {
321 pixFindVerticalRuns(pixt, j, start, end, &n);
322 runlengthMembershipOnLine(buffer, h, depth, start, end, n);
323 if (depth == 8) {
324 for (i = 0; i < h; i++) {
325 lined = datad + i * wpld;
326 SET_DATA_BYTE(lined, j, buffer[i]);
327 }
328 } else { /* depth == 16 */
329 for (i = 0; i < h; i++) {
330 lined = datad + i * wpld;
331 SET_DATA_TWO_BYTES(lined, j, buffer[i]);
332 }
333 }
334 }
335 }
336
337 pixDestroy(&pixt);
338 LEPT_FREE(start);
339 LEPT_FREE(end);
340 LEPT_FREE(buffer);
341 return pixd;
342 }
343
344
345 /*-----------------------------------------------------------------------*
346 * Find runs along horizontal and vertical lines *
347 *-----------------------------------------------------------------------*/
348 /*!
349 * \brief pixFindHorizontalRuns()
350 *
351 * \param[in] pix 1 bpp
352 * \param[in] y line to traverse
353 * \param[in] xstart returns array of start positions for fg runs
354 * \param[in] xend returns array of end positions for fg runs
355 * \param[out] pn the number of runs found
356 * \return 0 if OK; 1 on error
357 *
358 * <pre>
359 * Notes:
360 * (1) This finds foreground horizontal runs on a single scanline.
361 * (2) To find background runs, use pixInvert() before applying
362 * this function.
363 * (3) %xstart and %xend arrays are input. They should be
364 * of size w/2 + 1 to insure that they can hold
365 * the maximum number of runs in the raster line.
366 * </pre>
367 */
368 l_ok
369 pixFindHorizontalRuns(PIX *pix,
370 l_int32 y,
371 l_int32 *xstart,
372 l_int32 *xend,
373 l_int32 *pn)
374 {
375 l_int32 inrun; /* boolean */
376 l_int32 index, w, h, d, j, wpl, val;
377 l_uint32 *line;
378
379 if (!pn)
380 return ERROR_INT("&n not defined", __func__, 1);
381 *pn = 0;
382 if (!pix)
383 return ERROR_INT("pix not defined", __func__, 1);
384 pixGetDimensions(pix, &w, &h, &d);
385 if (d != 1)
386 return ERROR_INT("pix not 1 bpp", __func__, 1);
387 if (y < 0 || y >= h)
388 return ERROR_INT("y not in [0 ... h - 1]", __func__, 1);
389 if (!xstart)
390 return ERROR_INT("xstart not defined", __func__, 1);
391 if (!xend)
392 return ERROR_INT("xend not defined", __func__, 1);
393
394 wpl = pixGetWpl(pix);
395 line = pixGetData(pix) + y * wpl;
396
397 inrun = FALSE;
398 index = 0;
399 for (j = 0; j < w; j++) {
400 val = GET_DATA_BIT(line, j);
401 if (!inrun) {
402 if (val) {
403 xstart[index] = j;
404 inrun = TRUE;
405 }
406 } else {
407 if (!val) {
408 xend[index++] = j - 1;
409 inrun = FALSE;
410 }
411 }
412 }
413
414 /* Finish last run if necessary */
415 if (inrun)
416 xend[index++] = w - 1;
417
418 *pn = index;
419 return 0;
420 }
421
422
423 /*!
424 * \brief pixFindVerticalRuns()
425 *
426 * \param[in] pix 1 bpp
427 * \param[in] x line to traverse
428 * \param[in] ystart returns array of start positions for fg runs
429 * \param[in] yend returns array of end positions for fg runs
430 * \param[out] pn the number of runs found
431 * \return 0 if OK; 1 on error
432 *
433 * <pre>
434 * Notes:
435 * (1) This finds foreground vertical runs on a single scanline.
436 * (2) To find background runs, use pixInvert() before applying
437 * this function.
438 * (3) %ystart and %yend arrays are input. They should be
439 * of size h/2 + 1 to insure that they can hold
440 * the maximum number of runs in the raster line.
441 * </pre>
442 */
443 l_ok
444 pixFindVerticalRuns(PIX *pix,
445 l_int32 x,
446 l_int32 *ystart,
447 l_int32 *yend,
448 l_int32 *pn)
449 {
450 l_int32 inrun; /* boolean */
451 l_int32 index, w, h, d, i, wpl, val;
452 l_uint32 *data, *line;
453
454 if (!pn)
455 return ERROR_INT("&n not defined", __func__, 1);
456 *pn = 0;
457 if (!pix)
458 return ERROR_INT("pix not defined", __func__, 1);
459 pixGetDimensions(pix, &w, &h, &d);
460 if (d != 1)
461 return ERROR_INT("pix not 1 bpp", __func__, 1);
462 if (x < 0 || x >= w)
463 return ERROR_INT("x not in [0 ... w - 1]", __func__, 1);
464 if (!ystart)
465 return ERROR_INT("ystart not defined", __func__, 1);
466 if (!yend)
467 return ERROR_INT("yend not defined", __func__, 1);
468
469 wpl = pixGetWpl(pix);
470 data = pixGetData(pix);
471
472 inrun = FALSE;
473 index = 0;
474 for (i = 0; i < h; i++) {
475 line = data + i * wpl;
476 val = GET_DATA_BIT(line, x);
477 if (!inrun) {
478 if (val) {
479 ystart[index] = i;
480 inrun = TRUE;
481 }
482 } else {
483 if (!val) {
484 yend[index++] = i - 1;
485 inrun = FALSE;
486 }
487 }
488 }
489
490 /* Finish last run if necessary */
491 if (inrun)
492 yend[index++] = h - 1;
493
494 *pn = index;
495 return 0;
496 }
497
498
499 /*-----------------------------------------------------------------------*
500 * Find max runs along horizontal and vertical lines *
501 *-----------------------------------------------------------------------*/
502 /*!
503 * \brief pixFindMaxRuns()
504 *
505 * \param[in] pix 1 bpp
506 * \param[in] direction L_HORIZONTAL_RUNS or L_VERTICAL_RUNS
507 * \param[out] pnastart [optional] start locations of longest runs
508 * \return na of lengths of runs, or NULL on error
509 *
510 * <pre>
511 * Notes:
512 * (1) This finds the longest foreground runs by row or column
513 * (2) To find background runs, use pixInvert() before applying
514 * this function.
515 * </pre>
516 */
517 NUMA *
518 pixFindMaxRuns(PIX *pix,
519 l_int32 direction,
520 NUMA **pnastart)
521 {
522 l_int32 w, h, i, start, size;
523 NUMA *nasize;
524
525 if (pnastart) *pnastart = NULL;
526 if (direction != L_HORIZONTAL_RUNS && direction != L_VERTICAL_RUNS)
527 return (NUMA *)ERROR_PTR("direction invalid", __func__, NULL);
528 if (!pix || pixGetDepth(pix) != 1)
529 return (NUMA *)ERROR_PTR("pix undefined or not 1 bpp", __func__, NULL);
530
531 pixGetDimensions(pix, &w, &h, NULL);
532 nasize = numaCreate(w);
533 if (pnastart) *pnastart = numaCreate(w);
534 if (direction == L_HORIZONTAL_RUNS) {
535 for (i = 0; i < h; i++) {
536 pixFindMaxHorizontalRunOnLine(pix, i, &start, &size);
537 numaAddNumber(nasize, size);
538 if (pnastart) numaAddNumber(*pnastart, start);
539 }
540 } else { /* vertical scans */
541 for (i = 0; i < w; i++) {
542 pixFindMaxVerticalRunOnLine(pix, i, &start, &size);
543 numaAddNumber(nasize, size);
544 if (pnastart) numaAddNumber(*pnastart, start);
545 }
546 }
547
548 return nasize;
549 }
550
551
552 /*!
553 * \brief pixFindMaxHorizontalRunOnLine()
554 *
555 * \param[in] pix 1 bpp
556 * \param[in] y line to traverse
557 * \param[out] pxstart [optional] start position
558 * \param[out] psize the size of the run
559 * \return 0 if OK; 1 on error
560 *
561 * <pre>
562 * Notes:
563 * (1) This finds the longest foreground horizontal run on a scanline.
564 * (2) To find background runs, use pixInvert() before applying
565 * this function.
566 * </pre>
567 */
568 l_ok
569 pixFindMaxHorizontalRunOnLine(PIX *pix,
570 l_int32 y,
571 l_int32 *pxstart,
572 l_int32 *psize)
573 {
574 l_int32 inrun; /* boolean */
575 l_int32 w, h, j, wpl, val, maxstart, maxsize, length, start;
576 l_uint32 *line;
577
578 if (pxstart) *pxstart = 0;
579 if (!psize)
580 return ERROR_INT("&size not defined", __func__, 1);
581 *psize = 0;
582 if (!pix || pixGetDepth(pix) != 1)
583 return ERROR_INT("pix not defined or not 1 bpp", __func__, 1);
584 pixGetDimensions(pix, &w, &h, NULL);
585 if (y < 0 || y >= h)
586 return ERROR_INT("y not in [0 ... h - 1]", __func__, 1);
587
588 wpl = pixGetWpl(pix);
589 line = pixGetData(pix) + y * wpl;
590 inrun = FALSE;
591 start = 0;
592 maxstart = 0;
593 maxsize = 0;
594 for (j = 0; j < w; j++) {
595 val = GET_DATA_BIT(line, j);
596 if (!inrun) {
597 if (val) {
598 start = j;
599 inrun = TRUE;
600 }
601 } else if (!val) { /* run just ended */
602 length = j - start;
603 if (length > maxsize) {
604 maxsize = length;
605 maxstart = start;
606 }
607 inrun = FALSE;
608 }
609 }
610
611 if (inrun) { /* a run has continued to the end of the row */
612 length = j - start;
613 if (length > maxsize) {
614 maxsize = length;
615 maxstart = start;
616 }
617 }
618 if (pxstart) *pxstart = maxstart;
619 *psize = maxsize;
620 return 0;
621 }
622
623
624 /*!
625 * \brief pixFindMaxVerticalRunOnLine()
626 *
627 * \param[in] pix 1 bpp
628 * \param[in] x column to traverse
629 * \param[out] pystart [optional] start position
630 * \param[out] psize the size of the run
631 * \return 0 if OK; 1 on error
632 *
633 * <pre>
634 * Notes:
635 * (1) This finds the longest foreground vertical run on a scanline.
636 * (2) To find background runs, use pixInvert() before applying
637 * this function.
638 * </pre>
639 */
640 l_ok
641 pixFindMaxVerticalRunOnLine(PIX *pix,
642 l_int32 x,
643 l_int32 *pystart,
644 l_int32 *psize)
645 {
646 l_int32 inrun; /* boolean */
647 l_int32 w, h, i, wpl, val, maxstart, maxsize, length, start;
648 l_uint32 *data, *line;
649
650 if (pystart) *pystart = 0;
651 if (!psize)
652 return ERROR_INT("&size not defined", __func__, 1);
653 *psize = 0;
654 if (!pix || pixGetDepth(pix) != 1)
655 return ERROR_INT("pix not defined or not 1 bpp", __func__, 1);
656 pixGetDimensions(pix, &w, &h, NULL);
657 if (x < 0 || x >= w)
658 return ERROR_INT("x not in [0 ... w - 1]", __func__, 1);
659
660 wpl = pixGetWpl(pix);
661 data = pixGetData(pix);
662 inrun = FALSE;
663 start = 0;
664 maxstart = 0;
665 maxsize = 0;
666 for (i = 0; i < h; i++) {
667 line = data + i * wpl;
668 val = GET_DATA_BIT(line, x);
669 if (!inrun) {
670 if (val) {
671 start = i;
672 inrun = TRUE;
673 }
674 } else if (!val) { /* run just ended */
675 length = i - start;
676 if (length > maxsize) {
677 maxsize = length;
678 maxstart = start;
679 }
680 inrun = FALSE;
681 }
682 }
683
684 if (inrun) { /* a run has continued to the end of the column */
685 length = i - start;
686 if (length > maxsize) {
687 maxsize = length;
688 maxstart = start;
689 }
690 }
691 if (pystart) *pystart = maxstart;
692 *psize = maxsize;
693 return 0;
694 }
695
696
697 /*-----------------------------------------------------------------------*
698 * Compute runlength-to-membership transform on a line *
699 *-----------------------------------------------------------------------*/
700 /*!
701 * \brief runlengthMembershipOnLine()
702 *
703 * \param[in] buffer into which full line of data is placed
704 * \param[in] size full size of line; w or h
705 * \param[in] depth 8 or 16 bpp
706 * \param[in] start array of start positions for fg runs
707 * \param[in] end array of end positions for fg runs
708 * \param[in] n the number of runs
709 * \return 0 if OK; 1 on error
710 *
711 * <pre>
712 * Notes:
713 * (1) Converts a set of runlengths into a buffer of
714 * runlength membership values.
715 * (2) Initialization of the array gives pixels that are
716 * not within a run the value 0.
717 * </pre>
718 */
719 l_ok
720 runlengthMembershipOnLine(l_int32 *buffer,
721 l_int32 size,
722 l_int32 depth,
723 l_int32 *start,
724 l_int32 *end,
725 l_int32 n)
726 {
727 l_int32 i, j, first, last, diff, max;
728
729 if (!buffer)
730 return ERROR_INT("buffer not defined", __func__, 1);
731 if (!start)
732 return ERROR_INT("start not defined", __func__, 1);
733 if (!end)
734 return ERROR_INT("end not defined", __func__, 1);
735
736 if (depth == 8)
737 max = 0xff;
738 else /* depth == 16 */
739 max = 0xffff;
740
741 memset(buffer, 0, 4 * size);
742 for (i = 0; i < n; i++) {
743 first = start[i];
744 last = end[i];
745 diff = last - first + 1;
746 diff = L_MIN(diff, max);
747 for (j = first; j <= last; j++)
748 buffer[j] = diff;
749 }
750
751 return 0;
752 }
753
754
755 /*-----------------------------------------------------------------------*
756 * Make byte position LUT *
757 *-----------------------------------------------------------------------*/
758 /*!
759 * \brief makeMSBitLocTab()
760 *
761 * \param[in] bitval either 0 or 1
762 * \return table: for an input byte, the MS bit location, starting at 0
763 * with the MSBit in the byte, or NULL on error.
764 *
765 * <pre>
766 * Notes:
767 * (1) If %bitval == 1, it finds the leftmost ON pixel in a byte;
768 * otherwise if %bitval == 0, it finds the leftmost OFF pixel.
769 * (2) If there are no pixels of the indicated color in the byte,
770 * this returns 8.
771 * </pre>
772 */
773 l_int32 *
774 makeMSBitLocTab(l_int32 bitval)
775 {
776 l_int32 i, j;
777 l_int32 *tab;
778 l_uint8 byte, mask;
779
780 tab = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
781 for (i = 0; i < 256; i++) {
782 byte = (l_uint8)i;
783 if (bitval == 0)
784 byte = ~byte;
785 tab[i] = 8;
786 mask = 0x80;
787 for (j = 0; j < 8; j++) {
788 if (byte & mask) {
789 tab[i] = j;
790 break;
791 }
792 mask >>= 1;
793 }
794 }
795 return tab;
796 }