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 * ptra1_reg.c
29 *
30 * Testing basic ptra operations
31 */
32
33 #include "allheaders.h"
34
35 static void MakePtrasFromPixa(PIXA *pixa, L_PTRA **ppapix, L_PTRA **ppabox,
36 l_int32 copyflag);
37 static PIXA *ReconstructPixa(L_PTRA *papix, L_PTRA *pabox, l_int32 choose);
38 static PIXA *ReconstructPixa1(L_PTRA *papix, L_PTRA *pabox);
39 static PIXA *ReconstructPixa2(L_PTRA *papix, L_PTRA *pabox);
40 static void DisplayResult(PIXA *pixac, PIXA **ppixa, l_int32 w, l_int32 h,
41 l_int32 newline);
42
43 #define CHOOSE_RECON 2 /* 1 or 2 */
44
45
main(int argc,char ** argv)46 int main(int argc,
47 char **argv)
48 {
49 l_int32 i, n, w, h, nactual, imax;
50 BOX *box;
51 BOXA *boxa;
52 PIX *pixs, *pixd, *pix;
53 PIXA *pixas, *pixat, *pixac;
54 L_PTRA *papix, *pabox, *papix2, *pabox2;
55 static char mainName[] = "ptra1_reg";
56
57 if (argc != 1)
58 return ERROR_INT(" Syntax: ptra1_reg", mainName, 1);
59
60 setLeptDebugOK(1);
61 pixac = pixaCreate(0);
62
63 if ((pixs = pixRead("lucasta.1.300.tif")) == NULL)
64 return ERROR_INT("pixs not made", mainName, 1);
65 pixGetDimensions(pixs, &w, &h, NULL);
66 boxa = pixConnComp(pixs, &pixas, 8);
67 pixDestroy(&pixs);
68 boxaDestroy(&boxa);
69 n = pixaGetCount(pixas);
70
71 /* Fill ptras with clones and reconstruct */
72 fprintf(stderr, "Fill with clones and reconstruct\n");
73 MakePtrasFromPixa(pixas, &papix, &pabox, L_CLONE);
74 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
75 ptraDestroy(&papix, 0, 1);
76 ptraDestroy(&pabox, 0, 1);
77 DisplayResult(pixac, &pixat, w, h, 1);
78
79 /* Remove every other one for the first half;
80 * with compaction at each removal */
81 fprintf(stderr, "Remove every other in 1st half, with compaction\n");
82 MakePtrasFromPixa(pixas, &papix, &pabox, L_COPY);
83 for (i = 0; i < n / 2; i++) {
84 if (i % 2 == 0) {
85 pix = (PIX *)ptraRemove(papix, i, L_COMPACTION);
86 box = (BOX *)ptraRemove(pabox, i, L_COMPACTION);
87 pixDestroy(&pix);
88 boxDestroy(&box);
89 }
90 }
91 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
92 ptraDestroy(&papix, 0, 1);
93 ptraDestroy(&pabox, 0, 1);
94 DisplayResult(pixac, &pixat, w, h, 0);
95
96 /* Remove every other one for the entire set,
97 * but without compaction at each removal */
98 fprintf(stderr,
99 "Remove every other in 1st half, without & then with compaction\n");
100 MakePtrasFromPixa(pixas, &papix, &pabox, L_COPY);
101 for (i = 0; i < n; i++) {
102 if (i % 2 == 0) {
103 pix = (PIX *)ptraRemove(papix, i, L_NO_COMPACTION);
104 box = (BOX *)ptraRemove(pabox, i, L_NO_COMPACTION);
105 pixDestroy(&pix);
106 boxDestroy(&box);
107 }
108 }
109 ptraCompactArray(papix); /* now do the compaction */
110 ptraCompactArray(pabox);
111 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
112 ptraDestroy(&papix, 0, 1);
113 ptraDestroy(&pabox, 0, 1);
114 DisplayResult(pixac, &pixat, w, h, 0);
115
116 /* Fill ptras using insert at head, and reconstruct */
117 fprintf(stderr, "Insert at head and reconstruct\n");
118 papix = ptraCreate(n);
119 pabox = ptraCreate(n);
120 for (i = 0; i < n; i++) {
121 pix = pixaGetPix(pixas, i, L_CLONE);
122 box = pixaGetBox(pixas, i, L_CLONE);
123 ptraInsert(papix, 0, pix, L_MIN_DOWNSHIFT);
124 ptraInsert(pabox, 0, box, L_FULL_DOWNSHIFT);
125 }
126 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
127 ptraDestroy(&papix, 0, 1);
128 ptraDestroy(&pabox, 0, 1);
129 DisplayResult(pixac, &pixat, w, h, 1);
130
131 /* Reverse the arrays by swapping */
132 fprintf(stderr, "Reverse by swapping\n");
133 MakePtrasFromPixa(pixas, &papix, &pabox, L_CLONE);
134 for (i = 0; i < n / 2; i++) {
135 ptraSwap(papix, i, n - i - 1);
136 ptraSwap(pabox, i, n - i - 1);
137 }
138 ptraCompactArray(papix); /* already compact; shouldn't do anything */
139 ptraCompactArray(pabox);
140 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
141 ptraDestroy(&papix, 0, 1);
142 ptraDestroy(&pabox, 0, 1);
143 DisplayResult(pixac, &pixat, w, h, 0);
144
145 /* Remove at the top of the array and push the hole to the end
146 * by neighbor swapping (!). This is O(n^2), so it's not a
147 * recommended way to copy a ptra. [joke] */
148 fprintf(stderr,
149 "Remove at top, pushing hole to end by swapping -- O(n^2)\n");
150 MakePtrasFromPixa(pixas, &papix, &pabox, L_CLONE);
151 papix2 = ptraCreate(0);
152 pabox2 = ptraCreate(0);
153 while (1) {
154 ptraGetActualCount(papix, &nactual);
155 if (nactual == 0) break;
156 ptraGetMaxIndex(papix, &imax);
157 pix = (PIX *)ptraRemove(papix, 0, L_NO_COMPACTION);
158 box = (BOX *)ptraRemove(pabox, 0, L_NO_COMPACTION);
159 ptraAdd(papix2, pix);
160 ptraAdd(pabox2, box);
161 for (i = 1; i <= imax; i++) {
162 ptraSwap(papix, i - 1, i);
163 ptraSwap(pabox, i - 1, i);
164 }
165 }
166 ptraCompactArray(papix); /* should be empty */
167 ptraCompactArray(pabox); /* ditto */
168 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
169 ptraDestroy(&papix, 0, 1);
170 ptraDestroy(&pabox, 0, 1);
171 DisplayResult(pixac, &pixat, w, h, 1); /* nothing there */
172 pixat = ReconstructPixa(papix2, pabox2, CHOOSE_RECON);
173 ptraDestroy(&papix2, 0, 1);
174 ptraDestroy(&pabox2, 0, 1);
175 DisplayResult(pixac, &pixat, w, h, 0);
176
177 /* Remove and insert one position above, allowing minimum downshift.
178 * If you specify L_AUTO_DOWNSHIFT, because there is only 1 hole,
179 * it will do a full downshift at each insert. This is a
180 * situation where the heuristic (expected number of holes)
181 * fails to do the optimal thing. */
182 fprintf(stderr, "Remove and insert one position above (min downshift)\n");
183 MakePtrasFromPixa(pixas, &papix, &pabox, L_CLONE);
184 for (i = 1; i < n; i++) {
185 pix = (PIX *)ptraRemove(papix, i, L_NO_COMPACTION);
186 box = (BOX *)ptraRemove(pabox, i, L_NO_COMPACTION);
187 ptraInsert(papix, i - 1, pix, L_MIN_DOWNSHIFT);
188 ptraInsert(pabox, i - 1, box, L_MIN_DOWNSHIFT);
189 }
190 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
191 ptraDestroy(&papix, 0, 1);
192 ptraDestroy(&pabox, 0, 1);
193 DisplayResult(pixac, &pixat, w, h, 1);
194
195 /* Remove and insert one position above, but this time
196 * forcing a full downshift at each step. */
197 fprintf(stderr, "Remove and insert one position above (full downshift)\n");
198 MakePtrasFromPixa(pixas, &papix, &pabox, L_CLONE);
199 for (i = 1; i < n; i++) {
200 pix = (PIX *)ptraRemove(papix, i, L_NO_COMPACTION);
201 box = (BOX *)ptraRemove(pabox, i, L_NO_COMPACTION);
202 ptraInsert(papix, i - 1, pix, L_AUTO_DOWNSHIFT);
203 ptraInsert(pabox, i - 1, box, L_AUTO_DOWNSHIFT);
204 }
205 /* ptraCompactArray(papix);
206 ptraCompactArray(pabox); */
207 pixat = ReconstructPixa(papix, pabox, CHOOSE_RECON);
208 ptraDestroy(&papix, 0, 1);
209 ptraDestroy(&pabox, 0, 1);
210 DisplayResult(pixac, &pixat, w, h, 0);
211
212 pixd = pixaDisplay(pixac, 0, 0);
213 pixDisplay(pixd, 100, 100);
214 pixWrite("/tmp/junkptra1.png", pixd, IFF_PNG);
215 pixDestroy(&pixd);
216 pixaDestroy(&pixac);
217 pixaDestroy(&pixas);
218 return 0;
219 }
220
221
222 static void
MakePtrasFromPixa(PIXA * pixa,L_PTRA ** ppapix,L_PTRA ** ppabox,l_int32 copyflag)223 MakePtrasFromPixa(PIXA *pixa,
224 L_PTRA **ppapix,
225 L_PTRA **ppabox,
226 l_int32 copyflag)
227 {
228 l_int32 i, n;
229 BOX *box;
230 PIX *pix;
231 L_PTRA *papix, *pabox;
232
233 n = pixaGetCount(pixa);
234 papix = ptraCreate(n);
235 pabox = ptraCreate(n);
236 for (i = 0; i < n; i++) {
237 pix = pixaGetPix(pixa, i, copyflag);
238 box = pixaGetBox(pixa, i, copyflag);
239 ptraAdd(papix, pix);
240 ptraAdd(pabox, box);
241 }
242
243 *ppapix = papix;
244 *ppabox = pabox;
245 return;
246 }
247
248
249 static PIXA *
ReconstructPixa(L_PTRA * papix,L_PTRA * pabox,l_int32 choose)250 ReconstructPixa(L_PTRA *papix,
251 L_PTRA *pabox,
252 l_int32 choose)
253 {
254 PIXA *pixa;
255
256 if (choose == 1)
257 pixa = ReconstructPixa1(papix, pabox);
258 else
259 pixa = ReconstructPixa2(papix, pabox);
260 return pixa;
261 }
262
263
264 /* Reconstruction without compaction */
265 static PIXA *
ReconstructPixa1(L_PTRA * papix,L_PTRA * pabox)266 ReconstructPixa1(L_PTRA *papix,
267 L_PTRA *pabox)
268 {
269 l_int32 i, imax, nactual;
270 BOX *box;
271 PIX *pix;
272 PIXA *pixat;
273
274 ptraGetMaxIndex(papix, &imax);
275 ptraGetActualCount(papix, &nactual);
276 fprintf(stderr, "Before removal: imax = %4d, actual = %4d\n",
277 imax, nactual);
278
279 pixat = pixaCreate(imax + 1);
280 for (i = 0; i <= imax; i++) {
281 pix = (PIX *)ptraRemove(papix, i, L_NO_COMPACTION);
282 box = (BOX *)ptraRemove(pabox, i, L_NO_COMPACTION);
283 if (pix) pixaAddPix(pixat, pix, L_INSERT);
284 if (box) pixaAddBox(pixat, box, L_INSERT);
285 }
286
287 ptraGetMaxIndex(papix, &imax);
288 ptraGetActualCount(papix, &nactual);
289 fprintf(stderr, "After removal: imax = %4d, actual = %4d\n\n",
290 imax, nactual);
291
292 return pixat;
293 }
294
295
296 /* Reconstruction with compaction */
297 static PIXA *
ReconstructPixa2(L_PTRA * papix,L_PTRA * pabox)298 ReconstructPixa2(L_PTRA *papix,
299 L_PTRA *pabox)
300 {
301 l_int32 i, imax, nactual;
302 BOX *box;
303 PIX *pix;
304 PIXA *pixat;
305
306 ptraGetMaxIndex(papix, &imax);
307 ptraGetActualCount(papix, &nactual);
308 fprintf(stderr, "Before removal: imax = %4d, actual = %4d\n",
309 imax, nactual);
310
311 /* Remove half */
312 pixat = pixaCreate(imax + 1);
313 for (i = 0; i <= imax; i++) {
314 if (i % 2 == 0) {
315 pix = (PIX *)ptraRemove(papix, i, L_NO_COMPACTION);
316 box = (BOX *)ptraRemove(pabox, i, L_NO_COMPACTION);
317 if (pix) pixaAddPix(pixat, pix, L_INSERT);
318 if (box) pixaAddBox(pixat, box, L_INSERT);
319 }
320 }
321
322 /* Compact */
323 ptraGetMaxIndex(papix, &imax);
324 ptraGetActualCount(papix, &nactual);
325 fprintf(stderr, "Before compaction: imax = %4d, actual = %4d\n",
326 imax, nactual);
327 ptraCompactArray(papix);
328 ptraCompactArray(pabox);
329 ptraGetMaxIndex(papix, &imax);
330 ptraGetActualCount(papix, &nactual);
331 fprintf(stderr, "After compaction: imax = %4d, actual = %4d\n",
332 imax, nactual);
333
334 /* Remove the rest (and test compaction with removal) */
335 while (1) {
336 ptraGetActualCount(papix, &nactual);
337 if (nactual == 0) break;
338
339 pix = (PIX *)ptraRemove(papix, 0, L_COMPACTION);
340 box = (BOX *)ptraRemove(pabox, 0, L_COMPACTION);
341 pixaAddPix(pixat, pix, L_INSERT);
342 pixaAddBox(pixat, box, L_INSERT);
343 }
344
345 ptraGetMaxIndex(papix, &imax);
346 ptraGetActualCount(papix, &nactual);
347 fprintf(stderr, "After removal: imax = %4d, actual = %4d\n\n",
348 imax, nactual);
349
350 return pixat;
351 }
352
353
354 static void
DisplayResult(PIXA * pixac,PIXA ** ppixa,l_int32 w,l_int32 h,l_int32 newline)355 DisplayResult(PIXA *pixac,
356 PIXA **ppixa,
357 l_int32 w,
358 l_int32 h,
359 l_int32 newline)
360 {
361 PIX *pixd;
362
363 pixd = pixaDisplay(*ppixa, w, h);
364 pixSaveTiled(pixd, pixac, 1, newline, 30, 8);
365 pixDestroy(&pixd);
366 pixaDestroy(ppixa);
367 return;
368 }
369
