Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/binreduce.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 binreduce.c
29 * <pre>
30 *
31 * Subsampled 2x reduction
32 * PIX *pixReduceBinary2()
33 *
34 * Rank filtered 2x reductions
35 * PIX *pixReduceRankBinaryCascade()
36 * PIX *pixReduceRankBinary2()
37 *
38 * Permutation table for 2x rank binary reduction
39 * l_uint8 *makeSubsampleTab2x(void)
40 * </pre>
41 */
42
43 #ifdef HAVE_CONFIG_H
44 #include <config_auto.h>
45 #endif /* HAVE_CONFIG_H */
46
47 #include <string.h>
48 #include "allheaders.h"
49
50 /*------------------------------------------------------------------*
51 * Subsampled reduction *
52 *------------------------------------------------------------------*/
53 /*!
54 * \brief pixReduceBinary2()
55 *
56 * \param[in] pixs
57 * \param[in] intab [optional]; if null, a table is made here
58 * and destroyed before exit
59 * \return pixd 2x subsampled, or NULL on error
60 *
61 * <pre>
62 * Notes:
63 * (1) After folding, the data is in bytes 0 and 2 of the word,
64 * and the bits in each byte are in the following order
65 * (with 0 being the leftmost originating pair and 7 being
66 * the rightmost originating pair):
67 * 0 4 1 5 2 6 3 7
68 * These need to be permuted to
69 * 0 1 2 3 4 5 6 7
70 * which is done with an 8-bit table generated by makeSubsampleTab2x().
71 * </pre>
72 */
73 PIX *
74 pixReduceBinary2(PIX *pixs,
75 l_uint8 *intab)
76 {
77 l_uint8 byte0, byte1;
78 l_uint8 *tab;
79 l_uint16 shortd;
80 l_int32 i, id, j, ws, hs, wpls, wpld, wplsi;
81 l_uint32 word;
82 l_uint32 *datas, *datad, *lines, *lined;
83 PIX *pixd;
84
85 if (!pixs || pixGetDepth(pixs) != 1)
86 return (PIX *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
87
88 pixGetDimensions(pixs, &ws, &hs, NULL);
89 if (hs <= 1)
90 return (PIX *)ERROR_PTR("hs must be at least 2", __func__, NULL);
91 wpls = pixGetWpl(pixs);
92 datas = pixGetData(pixs);
93 pixSetPadBits(pixs, 0);
94
95 if ((pixd = pixCreate(ws / 2, hs / 2, 1)) == NULL)
96 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
97 pixCopyResolution(pixd, pixs);
98 pixScaleResolution(pixd, 0.5, 0.5);
99 wpld = pixGetWpl(pixd);
100 datad = pixGetData(pixd);
101
102 tab = (intab) ? intab : makeSubsampleTab2x();
103 if (!tab) {
104 pixDestroy(&pixd);
105 return (PIX *)ERROR_PTR("tab not made", __func__, NULL);
106 }
107
108 /* e.g., if ws = 65: wd = 32, wpls = 3, wpld = 1 --> trouble */
109 wplsi = L_MIN(wpls, 2 * wpld); /* iterate over this number of words */
110
111 for (i = 0, id = 0; i < hs - 1; i += 2, id++) {
112 lines = datas + i * wpls;
113 lined = datad + id * wpld;
114 for (j = 0; j < wplsi; j++) {
115 word = *(lines + j);
116 word = word & 0xaaaaaaaa; /* mask */
117 word = word | (word << 7); /* fold; data in bytes 0 & 2 */
118 byte0 = word >> 24;
119 byte1 = (word >> 8) & 0xff;
120 shortd = (tab[byte0] << 8) | tab[byte1];
121 SET_DATA_TWO_BYTES(lined, j, shortd);
122 }
123 }
124
125 if (!intab) LEPT_FREE(tab);
126 return pixd;
127 }
128
129
130 /*------------------------------------------------------------------*
131 * Rank filtered binary reductions *
132 *------------------------------------------------------------------*/
133 /*!
134 * \brief pixReduceRankBinaryCascade()
135 *
136 * \param[in] pixs 1 bpp
137 * \param[in] level1 threshold, in the set {0, 1, 2, 3, 4}
138 * \param[in] level2 threshold, in the set {0, 1, 2, 3, 4}
139 * \param[in] level3 threshold, in the set {0, 1, 2, 3, 4}
140 * \param[in] level4 threshold, in the set {0, 1, 2, 3, 4}
141 * \return pixd, or NULL on error
142 *
143 * <pre>
144 * Notes:
145 * (1) This performs up to four cascaded 2x rank reductions.
146 * (2) Use level = 0 to truncate the cascade.
147 * </pre>
148 */
149 PIX *
150 pixReduceRankBinaryCascade(PIX *pixs,
151 l_int32 level1,
152 l_int32 level2,
153 l_int32 level3,
154 l_int32 level4)
155 {
156 PIX *pix1, *pix2, *pix3, *pix4;
157 l_uint8 *tab;
158
159 if (!pixs)
160 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
161 if (pixGetDepth(pixs) != 1)
162 return (PIX *)ERROR_PTR("pixs must be binary", __func__, NULL);
163 if (level1 > 4 || level2 > 4 || level3 > 4 || level4 > 4)
164 return (PIX *)ERROR_PTR("levels must not exceed 4", __func__, NULL);
165
166 if (level1 <= 0) {
167 L_WARNING("no reduction because level1 not > 0\n", __func__);
168 return pixCopy(NULL, pixs);
169 }
170
171 if ((tab = makeSubsampleTab2x()) == NULL)
172 return (PIX *)ERROR_PTR("tab not made", __func__, NULL);
173
174 pix1 = pixReduceRankBinary2(pixs, level1, tab);
175 if (level2 <= 0) {
176 LEPT_FREE(tab);
177 return pix1;
178 }
179
180 pix2 = pixReduceRankBinary2(pix1, level2, tab);
181 pixDestroy(&pix1);
182 if (level3 <= 0) {
183 LEPT_FREE(tab);
184 return pix2;
185 }
186
187 pix3 = pixReduceRankBinary2(pix2, level3, tab);
188 pixDestroy(&pix2);
189 if (level4 <= 0) {
190 LEPT_FREE(tab);
191 return pix3;
192 }
193
194 pix4 = pixReduceRankBinary2(pix3, level4, tab);
195 pixDestroy(&pix3);
196 LEPT_FREE(tab);
197 return pix4;
198 }
199
200
201 /*!
202 * \brief pixReduceRankBinary2()
203 *
204 * \param[in] pixs 1 bpp
205 * \param[in] level rank threshold: 1, 2, 3, 4
206 * \param[in] intab [optional]; if null, a table is made here
207 * and destroyed before exit
208 * \return pixd 1 bpp, 2x rank threshold reduced, or NULL on error
209 *
210 * <pre>
211 * Notes:
212 * (1) pixd is downscaled by 2x from pixs.
213 * (2) The rank threshold specifies the minimum number of ON
214 * pixels in each 2x2 region of pixs that are required to
215 * set the corresponding pixel ON in pixd.
216 * (3) Rank filtering is done to the UL corner of each 2x2 pixel block,
217 * using only logical operations. Then these pixels are chosen
218 * in the 2x subsampling process, subsampled, as described
219 * above in pixReduceBinary2().
220 * </pre>
221 */
222 PIX *
223 pixReduceRankBinary2(PIX *pixs,
224 l_int32 level,
225 l_uint8 *intab)
226 {
227 l_uint8 byte0, byte1;
228 l_uint8 *tab;
229 l_uint16 shortd;
230 l_int32 i, id, j, ws, hs, wpls, wpld, wplsi;
231 l_uint32 word1, word2, word3, word4;
232 l_uint32 *datas, *datad, *lines, *lined;
233 PIX *pixd;
234
235 if (!pixs)
236 return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
237
238 if (pixGetDepth(pixs) != 1)
239 return (PIX *)ERROR_PTR("pixs not binary", __func__, NULL);
240 if (level < 1 || level > 4)
241 return (PIX *)ERROR_PTR("level must be in set {1,2,3,4}",
242 __func__, NULL);
243
244 pixGetDimensions(pixs, &ws, &hs, NULL);
245 if (hs <= 1)
246 return (PIX *)ERROR_PTR("hs must be at least 2", __func__, NULL);
247 wpls = pixGetWpl(pixs);
248 datas = pixGetData(pixs);
249 pixSetPadBits(pixs, 0);
250
251 if ((pixd = pixCreate(ws / 2, hs / 2, 1)) == NULL)
252 return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
253 pixCopyResolution(pixd, pixs);
254 pixScaleResolution(pixd, 0.5, 0.5);
255 wpld = pixGetWpl(pixd);
256 datad = pixGetData(pixd);
257
258 tab = (intab) ? intab : makeSubsampleTab2x();
259 if (!tab) {
260 pixDestroy(&pixd);
261 return (PIX *)ERROR_PTR("tab not made", __func__, NULL);
262 }
263
264 /* e.g., if ws = 65: wd = 32, wpls = 3, wpld = 1 --> trouble */
265 wplsi = L_MIN(wpls, 2 * wpld); /* iterate over this number of words */
266
267 switch (level)
268 {
269
270 case 1:
271 for (i = 0, id = 0; i < hs - 1; i += 2, id++) {
272 lines = datas + i * wpls;
273 lined = datad + id * wpld;
274 for (j = 0; j < wplsi; j++) {
275 word1 = *(lines + j);
276 word2 = *(lines + wpls + j);
277
278 /* OR/OR */
279 word2 = word1 | word2;
280 word2 = word2 | (word2 << 1);
281
282 word2 = word2 & 0xaaaaaaaa; /* mask */
283 word1 = word2 | (word2 << 7); /* fold; data in bytes 0 & 2 */
284 byte0 = word1 >> 24;
285 byte1 = (word1 >> 8) & 0xff;
286 shortd = (tab[byte0] << 8) | tab[byte1];
287 SET_DATA_TWO_BYTES(lined, j, shortd);
288 }
289 }
290 break;
291
292 case 2:
293 for (i = 0, id = 0; i < hs - 1; i += 2, id++) {
294 lines = datas + i * wpls;
295 lined = datad + id * wpld;
296 for (j = 0; j < wplsi; j++) {
297 word1 = *(lines + j);
298 word2 = *(lines + wpls + j);
299
300 /* (AND/OR) OR (OR/AND) */
301 word3 = word1 & word2;
302 word3 = word3 | (word3 << 1);
303 word4 = word1 | word2;
304 word4 = word4 & (word4 << 1);
305 word2 = word3 | word4;
306
307 word2 = word2 & 0xaaaaaaaa; /* mask */
308 word1 = word2 | (word2 << 7); /* fold; data in bytes 0 & 2 */
309 byte0 = word1 >> 24;
310 byte1 = (word1 >> 8) & 0xff;
311 shortd = (tab[byte0] << 8) | tab[byte1];
312 SET_DATA_TWO_BYTES(lined, j, shortd);
313 }
314 }
315 break;
316
317 case 3:
318 for (i = 0, id = 0; i < hs - 1; i += 2, id++) {
319 lines = datas + i * wpls;
320 lined = datad + id * wpld;
321 for (j = 0; j < wplsi; j++) {
322 word1 = *(lines + j);
323 word2 = *(lines + wpls + j);
324
325 /* (AND/OR) AND (OR/AND) */
326 word3 = word1 & word2;
327 word3 = word3 | (word3 << 1);
328 word4 = word1 | word2;
329 word4 = word4 & (word4 << 1);
330 word2 = word3 & word4;
331
332 word2 = word2 & 0xaaaaaaaa; /* mask */
333 word1 = word2 | (word2 << 7); /* fold; data in bytes 0 & 2 */
334 byte0 = word1 >> 24;
335 byte1 = (word1 >> 8) & 0xff;
336 shortd = (tab[byte0] << 8) | tab[byte1];
337 SET_DATA_TWO_BYTES(lined, j, shortd);
338 }
339 }
340 break;
341
342 case 4:
343 for (i = 0, id = 0; i < hs - 1; i += 2, id++) {
344 lines = datas + i * wpls;
345 lined = datad + id * wpld;
346 for (j = 0; j < wplsi; j++) {
347 word1 = *(lines + j);
348 word2 = *(lines + wpls + j);
349
350 /* AND/AND */
351 word2 = word1 & word2;
352 word2 = word2 & (word2 << 1);
353
354 word2 = word2 & 0xaaaaaaaa; /* mask */
355 word1 = word2 | (word2 << 7); /* fold; data in bytes 0 & 2 */
356 byte0 = word1 >> 24;
357 byte1 = (word1 >> 8) & 0xff;
358 shortd = (tab[byte0] << 8) | tab[byte1];
359 SET_DATA_TWO_BYTES(lined, j, shortd);
360 }
361 }
362 break;
363 }
364
365 if (!intab) LEPT_FREE(tab);
366 return pixd;
367 }
368
369
370 /*!
371 * \brief makeSubsampleTab2x()
372 *
373 * \return tab table of 256 permutations, or NULL on error
374 *
375 * <pre>
376 * Notes:
377 * Permutation table for 2x rank binary reduction
378 * This table permutes the bits in a byte, from
379 * 0 4 1 5 2 6 3 7
380 * to
381 * 0 1 2 3 4 5 6 7
382 * </pre>
383 */
384 l_uint8 *
385 makeSubsampleTab2x(void)
386 {
387 l_uint8 *tab;
388 l_int32 i;
389
390 tab = (l_uint8 *) LEPT_CALLOC(256, sizeof(l_uint8));
391 for (i = 0; i < 256; i++) {
392 tab[i] = ((i & 0x01) ) | /* 7 */
393 ((i & 0x04) >> 1) | /* 6 */
394 ((i & 0x10) >> 2) | /* 5 */
395 ((i & 0x40) >> 3) | /* 4 */
396 ((i & 0x02) << 3) | /* 3 */
397 ((i & 0x08) << 2) | /* 2 */
398 ((i & 0x20) << 1) | /* 1 */
399 ((i & 0x80) ); /* 0 */
400 }
401 return tab;
402 }