1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 - This software is distributed in the hope that it will be
4 - useful, but with NO WARRANTY OF ANY KIND.
5 - No author or distributor accepts responsibility to anyone for the
6 - consequences of using this software, or for whether it serves any
7 - particular purpose or works at all, unless he or she says so in
8 - writing. Everyone is granted permission to copy, modify and
9 - redistribute this source code, for commercial or non-commercial
10 - purposes, with the following restrictions: (1) the origin of this
11 - source code must not be misrepresented; (2) modified versions must
12 - be plainly marked as such; and (3) this notice may not be removed
13 - or altered from any source or modified source distribution.
14 *====================================================================*/
15
16 /*
17 * runlength.c
18 *
19 * Label pixels by membership in runs
20 * PIX *pixRunlengthTransform()
21 *
22 * Find runs along horizontal and vertical lines
23 * l_int32 pixFindHorizontalRuns()
24 * l_int32 pixFindVerticalRuns()
25 *
26 * Compute runlength-to-membership transform on a line
27 * l_int32 runlengthMembershipOnLine()
28 *
29 * Make byte position LUT
30 * l_int32 makeMSBitLocTab()
31 */
32
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include "allheaders.h"
37
38
39 /*-----------------------------------------------------------------------*
40 * Label pixels by membership in runs *
41 *-----------------------------------------------------------------------*/
42 /*!
43 * pixRunlengthTransform()
44 *
45 * Input: pixs (1 bpp)
46 * color (0 for white runs, 1 for black runs)
47 * direction (L_HORIZONTAL_RUNS, L_VERTICAL_RUNS)
48 * depth (8 or 16 bpp)
49 * Return: pixd (8 or 16 bpp), or null on error
50 *
51 * Notes:
52 * (1) The dest Pix is 8 or 16 bpp, with the pixel values
53 * equal to the runlength in which it is a member.
54 * The length is clipped to the max pixel value if necessary.
55 * (2) The color determines if we're labelling white or black runs.
56 * (3) A pixel that is not a member of the chosen color gets
57 * value 0; it belongs to a run of length 0 of the
58 * chosen color.
59 * (4) To convert for maximum dynamic range, either linear or
60 * log, use pixMaxDynamicRange().
61 */
62 PIX *
pixRunlengthTransform(PIX * pixs,l_int32 color,l_int32 direction,l_int32 depth)63 pixRunlengthTransform(PIX *pixs,
64 l_int32 color,
65 l_int32 direction,
66 l_int32 depth)
67 {
68 l_int32 i, j, w, h, wpld, bufsize, maxsize, n;
69 l_int32 *start, *end, *buffer;
70 l_uint32 *datad, *lined;
71 PIX *pixt, *pixd;
72
73 PROCNAME("pixRunlengthTransform");
74
75 if (!pixs)
76 return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
77 if (pixGetDepth(pixs) != 1)
78 return (PIX *)ERROR_PTR("pixs not 1 bpp", procName, NULL);
79 if (depth != 8 && depth != 16)
80 return (PIX *)ERROR_PTR("depth must be 8 or 16 bpp", procName, NULL);
81
82 pixGetDimensions(pixs, &w, &h, NULL);
83 if (direction == L_HORIZONTAL_RUNS)
84 maxsize = 1 + w / 2;
85 else if (direction == L_VERTICAL_RUNS)
86 maxsize = 1 + h / 2;
87 else
88 return (PIX *)ERROR_PTR("invalid direction", procName, NULL);
89 bufsize = L_MAX(w, h);
90
91 if ((pixd = pixCreate(w, h, depth)) == NULL)
92 return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
93 datad = pixGetData(pixd);
94 wpld = pixGetWpl(pixd);
95
96 if ((start = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL)
97 return (PIX *)ERROR_PTR("start not made", procName, NULL);
98 if ((end = (l_int32 *)CALLOC(maxsize, sizeof(l_int32))) == NULL)
99 return (PIX *)ERROR_PTR("end not made", procName, NULL);
100 if ((buffer = (l_int32 *)CALLOC(bufsize, sizeof(l_int32))) == NULL)
101 return (PIX *)ERROR_PTR("buffer not made", procName, NULL);
102
103 /* Use fg runs for evaluation */
104 if (color == 0)
105 pixt = pixInvert(NULL, pixs);
106 else
107 pixt = pixClone(pixs);
108
109 if (direction == L_HORIZONTAL_RUNS) {
110 for (i = 0; i < h; i++) {
111 pixFindHorizontalRuns(pixt, i, start, end, &n);
112 runlengthMembershipOnLine(buffer, w, depth, start, end, n);
113 lined = datad + i * wpld;
114 if (depth == 8) {
115 for (j = 0; j < w; j++)
116 SET_DATA_BYTE(lined, j, buffer[j]);
117 } else { /* depth == 16 */
118 for (j = 0; j < w; j++)
119 SET_DATA_TWO_BYTES(lined, j, buffer[j]);
120 }
121 }
122 } else { /* L_VERTICAL_RUNS */
123 for (j = 0; j < w; j++) {
124 pixFindVerticalRuns(pixt, j, start, end, &n);
125 runlengthMembershipOnLine(buffer, h, depth, start, end, n);
126 if (depth == 8) {
127 for (i = 0; i < h; i++) {
128 lined = datad + i * wpld;
129 SET_DATA_BYTE(lined, j, buffer[i]);
130 }
131 } else { /* depth == 16 */
132 for (i = 0; i < h; i++) {
133 lined = datad + i * wpld;
134 SET_DATA_TWO_BYTES(lined, j, buffer[i]);
135 }
136 }
137 }
138 }
139
140 pixDestroy(&pixt);
141 FREE(start);
142 FREE(end);
143 FREE(buffer);
144 return pixd;
145 }
146
147
148 /*-----------------------------------------------------------------------*
149 * Find runs along horizontal and vertical lines *
150 *-----------------------------------------------------------------------*/
151 /*!
152 * pixFindHorizontalRuns()
153 *
154 * Input: pix (1 bpp)
155 * y (line to traverse)
156 * xstart (returns array of start positions for fg runs)
157 * xend (returns array of end positions for fg runs)
158 * &n (<return> the number of runs found)
159 * Return: 0 if OK; 1 on error
160 *
161 * Notes:
162 * (1) This finds foreground horizontal runs on a single scanline.
163 * (2) To find background runs, use pixInvert() before applying
164 * this function.
165 * (3) The xstart and xend arrays are input. They should be
166 * of size w/2 + 1 to insure that they can hold
167 * the maximum number of runs in the raster line.
168 */
169 l_int32
pixFindHorizontalRuns(PIX * pix,l_int32 y,l_int32 * xstart,l_int32 * xend,l_int32 * pn)170 pixFindHorizontalRuns(PIX *pix,
171 l_int32 y,
172 l_int32 *xstart,
173 l_int32 *xend,
174 l_int32 *pn)
175 {
176 l_int32 inrun; /* boolean */
177 l_int32 index, w, h, d, j, wpl, val;
178 l_uint32 *line;
179
180 PROCNAME("pixFindHorizontalRuns");
181
182 if (!pn)
183 return ERROR_INT("&n not defined", procName, 1);
184 *pn = 0;
185 if (!pix)
186 return ERROR_INT("pix not defined", procName, 1);
187 pixGetDimensions(pix, &w, &h, &d);
188 if (d != 1)
189 return ERROR_INT("pix not 1 bpp", procName, 1);
190 if (y < 0 || y >= h)
191 return ERROR_INT("y not in [0 ... h - 1]", procName, 1);
192 if (!xstart)
193 return ERROR_INT("xstart not defined", procName, 1);
194 if (!xend)
195 return ERROR_INT("xend not defined", procName, 1);
196
197 wpl = pixGetWpl(pix);
198 line = pixGetData(pix) + y * wpl;
199
200 inrun = FALSE;
201 index = 0;
202 for (j = 0; j < w; j++) {
203 val = GET_DATA_BIT(line, j);
204 if (!inrun) {
205 if (val) {
206 xstart[index] = j;
207 inrun = TRUE;
208 }
209 }
210 else {
211 if (!val) {
212 xend[index++] = j - 1;
213 inrun = FALSE;
214 }
215 }
216 }
217
218 /* Finish last run if necessary */
219 if (inrun)
220 xend[index++] = w - 1;
221
222 *pn = index;
223 return 0;
224 }
225
226
227 /*!
228 * pixFindVerticalRuns()
229 *
230 * Input: pix (1 bpp)
231 * x (line to traverse)
232 * ystart (returns array of start positions for fg runs)
233 * yend (returns array of end positions for fg runs)
234 * &n (<return> the number of runs found)
235 * Return: 0 if OK; 1 on error
236 *
237 * Notes:
238 * (1) This finds foreground vertical runs on a single scanline.
239 * (2) To find background runs, use pixInvert() before applying
240 * this function.
241 * (3) The ystart and yend arrays are input. They should be
242 * of size h/2 + 1 to insure that they can hold
243 * the maximum number of runs in the raster line.
244 */
245 l_int32
pixFindVerticalRuns(PIX * pix,l_int32 x,l_int32 * ystart,l_int32 * yend,l_int32 * pn)246 pixFindVerticalRuns(PIX *pix,
247 l_int32 x,
248 l_int32 *ystart,
249 l_int32 *yend,
250 l_int32 *pn)
251 {
252 l_int32 inrun; /* boolean */
253 l_int32 index, w, h, d, i, wpl, val;
254 l_uint32 *data, *line;
255
256 PROCNAME("pixFindVerticalRuns");
257
258 if (!pn)
259 return ERROR_INT("&n not defined", procName, 1);
260 *pn = 0;
261 if (!pix)
262 return ERROR_INT("pix not defined", procName, 1);
263 pixGetDimensions(pix, &w, &h, &d);
264 if (d != 1)
265 return ERROR_INT("pix not 1 bpp", procName, 1);
266 if (x < 0 || x >= w)
267 return ERROR_INT("x not in [0 ... w - 1]", procName, 1);
268 if (!ystart)
269 return ERROR_INT("ystart not defined", procName, 1);
270 if (!yend)
271 return ERROR_INT("yend not defined", procName, 1);
272
273 wpl = pixGetWpl(pix);
274 data = pixGetData(pix);
275
276 inrun = FALSE;
277 index = 0;
278 for (i = 0; i < h; i++) {
279 line = data + i * wpl;
280 val = GET_DATA_BIT(line, x);
281 if (!inrun) {
282 if (val) {
283 ystart[index] = i;
284 inrun = TRUE;
285 }
286 }
287 else {
288 if (!val) {
289 yend[index++] = i - 1;
290 inrun = FALSE;
291 }
292 }
293 }
294
295 /* Finish last run if necessary */
296 if (inrun)
297 yend[index++] = h - 1;
298
299 *pn = index;
300 return 0;
301 }
302
303
304 /*-----------------------------------------------------------------------*
305 * Compute runlength-to-membership transform on a line *
306 *-----------------------------------------------------------------------*/
307 /*!
308 * runlengthMembershipOnLine()
309 *
310 * Input: buffer (into which full line of data is placed)
311 * size (full size of line; w or h)
312 * depth (8 or 16 bpp)
313 * start (array of start positions for fg runs)
314 * end (array of end positions for fg runs)
315 * n (the number of runs)
316 * Return: 0 if OK; 1 on error
317 *
318 * Notes:
319 * (1) Converts a set of runlengths into a buffer of
320 * runlength membership values.
321 * (2) Initialization of the array gives pixels that are
322 * not within a run the value 0.
323 */
324 l_int32
runlengthMembershipOnLine(l_int32 * buffer,l_int32 size,l_int32 depth,l_int32 * start,l_int32 * end,l_int32 n)325 runlengthMembershipOnLine(l_int32 *buffer,
326 l_int32 size,
327 l_int32 depth,
328 l_int32 *start,
329 l_int32 *end,
330 l_int32 n)
331 {
332 l_int32 i, j, first, last, diff, max;
333
334 PROCNAME("runlengthMembershipOnLine");
335
336 if (!buffer)
337 return ERROR_INT("buffer not defined", procName, 1);
338 if (!start)
339 return ERROR_INT("start not defined", procName, 1);
340 if (!end)
341 return ERROR_INT("end not defined", procName, 1);
342
343 if (depth == 8)
344 max = 0xff;
345 else /* depth == 16 */
346 max = 0xffff;
347
348 memset(buffer, 0, 4 * size);
349 for (i = 0; i < n; i++) {
350 first = start[i];
351 last = end[i];
352 diff = last - first + 1;
353 diff = L_MIN(diff, max);
354 for (j = first; j <= last; j++)
355 buffer[j] = diff;
356 }
357
358 return 0;
359 }
360
361
362
363 /*-----------------------------------------------------------------------*
364 * Make byte position LUT *
365 *-----------------------------------------------------------------------*/
366 /*!
367 * makeMSBitLocTab()
368 *
369 * Input: bitval (either 0 or 1)
370 * Return: table (giving, for an input byte, the MS bit location,
371 * starting at 0 with the MSBit in the byte),
372 * or null on error.
373 *
374 * Notes:
375 * (1) If bitval == 1, it finds the leftmost ON pixel in a byte;
376 * otherwise if bitval == 0, it finds the leftmost OFF pixel.
377 * (2) If there are no pixels of the indicated color in the byte,
378 * this returns 8.
379 */
380 l_int32 *
makeMSBitLocTab(l_int32 bitval)381 makeMSBitLocTab(l_int32 bitval)
382 {
383 l_int32 i, j;
384 l_int32 *tab;
385 l_uint8 byte, mask;
386
387 PROCNAME("makeMSBitLocTab");
388
389 if ((tab = (l_int32 *)CALLOC(256, sizeof(l_int32))) == NULL)
390 return (l_int32 *)ERROR_PTR("tab not made", procName, NULL);
391
392 for (i = 0; i < 256; i++) {
393 byte = (l_uint8)i;
394 if (bitval == 0)
395 byte = ~byte;
396 tab[i] = 8;
397 mask = 0x80;
398 for (j = 0; j < 8; j++) {
399 if (byte & mask) {
400 tab[i] = j;
401 break;
402 }
403 mask >>= 1;
404 }
405 }
406
407 return tab;
408 }
409
410
411