1 | /**************************************************************************
|
---|
2 | *
|
---|
3 | * mgticprune.c -- Program to prune a textual image library
|
---|
4 | * Copyright (C) 1994 Stuart Inglis
|
---|
5 | *
|
---|
6 | * This program is free software; you can redistribute it and/or modify
|
---|
7 | * it under the terms of the GNU General Public License as published by
|
---|
8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
9 | * (at your option) any later version.
|
---|
10 | *
|
---|
11 | * This program is distributed in the hope that it will be useful,
|
---|
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | * GNU General Public License for more details.
|
---|
15 | *
|
---|
16 | * You should have received a copy of the GNU General Public License
|
---|
17 | * along with this program; if not, write to the Free Software
|
---|
18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
19 | *
|
---|
20 | * $Id: mgticprune.c 3745 2003-02-20 21:20:24Z mdewsnip $
|
---|
21 | *
|
---|
22 | **************************************************************************/
|
---|
23 |
|
---|
24 | #include "sysfuncs.h"
|
---|
25 |
|
---|
26 | #include "marklist.h"
|
---|
27 | #include "pbmtools.h"
|
---|
28 | #include "extractor.h"
|
---|
29 | #include "utils.h"
|
---|
30 | #include "match.h"
|
---|
31 |
|
---|
32 | marklistptr *avglib = NULL;
|
---|
33 | int avglibsize;
|
---|
34 | int libsize = 0;
|
---|
35 |
|
---|
36 |
|
---|
37 | void
|
---|
38 | usage ()
|
---|
39 | {
|
---|
40 | fprintf (stderr, "usage:\n"
|
---|
41 | "\tmgticbuild [-a n] [-s n] [-Q] libraryfile [pruned-library]\n");
|
---|
42 | exit (1);
|
---|
43 | }
|
---|
44 |
|
---|
45 |
|
---|
46 |
|
---|
47 |
|
---|
48 | /* foreach list in the avglib[] array, an average mark is returned */
|
---|
49 | marklistptr
|
---|
50 | average_library ()
|
---|
51 | {
|
---|
52 | marklistptr librarylist;
|
---|
53 | int i;
|
---|
54 | marktype avgmark;
|
---|
55 |
|
---|
56 | librarylist = NULL;
|
---|
57 | for (i = 0; i < libsize; i++)
|
---|
58 | {
|
---|
59 | if (avglib[i])
|
---|
60 | {
|
---|
61 | marklist_average (avglib[i], &avgmark);
|
---|
62 | avgmark.symnum = i;
|
---|
63 | marklist_addcopy (&librarylist, avgmark);
|
---|
64 | }
|
---|
65 | }
|
---|
66 | return librarylist;
|
---|
67 | }
|
---|
68 |
|
---|
69 |
|
---|
70 | void
|
---|
71 | average_space_enlarge ()
|
---|
72 | {
|
---|
73 | int j;
|
---|
74 |
|
---|
75 | if (libsize >= avglibsize)
|
---|
76 | {
|
---|
77 | avglib = (marklistptr *) realloc (avglib, (avglibsize + 100) * sizeof (marklistptr));
|
---|
78 | if (!avglib)
|
---|
79 | error_msg ("mgticprune", "out of memory in reallocating..", "");
|
---|
80 | for (j = avglibsize; j < avglibsize + 100; j++)
|
---|
81 | avglib[j] = NULL;
|
---|
82 | avglibsize += 100;
|
---|
83 | }
|
---|
84 | }
|
---|
85 |
|
---|
86 |
|
---|
87 | /* for each mark in 'origlist', if it can't be matched with one in
|
---|
88 | 'librarylist', then add to the librarylist, and update the relevant
|
---|
89 | avglib[] position */
|
---|
90 | void
|
---|
91 | greedy_add (marklistptr origlist, marklistptr * librarylist)
|
---|
92 | {
|
---|
93 | marklistptr step, step_i;
|
---|
94 | int i, j, notfound;
|
---|
95 | marktype d_i;
|
---|
96 |
|
---|
97 | for (i = 0, step_i = origlist; step_i; i++, step_i = step_i->next)
|
---|
98 | {
|
---|
99 | d_i = step_i->data;
|
---|
100 |
|
---|
101 | notfound = 1;
|
---|
102 | for (j = 0, step = *librarylist; step; j++, step = step->next)
|
---|
103 | {
|
---|
104 | if (NOT_SCREENED (d_i, step->data))
|
---|
105 | if (MATCH (&d_i, &step->data) < MATCH_VAL)
|
---|
106 | {
|
---|
107 | d_i.symnum = j;
|
---|
108 | marklist_addcopy (&avglib[j], d_i);
|
---|
109 | notfound = 0;
|
---|
110 | break;
|
---|
111 | }
|
---|
112 | }
|
---|
113 |
|
---|
114 | if (notfound)
|
---|
115 | {
|
---|
116 | d_i.symnum = libsize;
|
---|
117 | marklist_addcopy (librarylist, d_i);
|
---|
118 | marklist_addcopy (&avglib[libsize], d_i);
|
---|
119 | libsize++;
|
---|
120 | if (libsize >= avglibsize)
|
---|
121 | average_space_enlarge ();
|
---|
122 | }
|
---|
123 | }
|
---|
124 | }
|
---|
125 |
|
---|
126 |
|
---|
127 |
|
---|
128 | /* for each mark in 'library', if another matches with it, remove
|
---|
129 | one copy from the library, and erase the relevant avglib[] */
|
---|
130 | void
|
---|
131 | greedy_prune (marklistptr * library)
|
---|
132 | {
|
---|
133 | int count;
|
---|
134 | int i, j;
|
---|
135 | marklistptr step;
|
---|
136 | marktype d;
|
---|
137 |
|
---|
138 | count = marklist_length (*library);
|
---|
139 | /* an invariant, all marks <i have been kept in the pruned library */
|
---|
140 | for (i = 0; i < count; i++)
|
---|
141 | {
|
---|
142 | marklist_getat (*library, i, &d);
|
---|
143 |
|
---|
144 | for (j = 0, step = *library; j < i; j++, step = step->next)
|
---|
145 | {
|
---|
146 | if (NOT_SCREENED (d, step->data))
|
---|
147 | if (MATCH (&d, &step->data) < MATCH_VAL)
|
---|
148 | {
|
---|
149 | /* [i,d] has matched with library element [j,d2]. */
|
---|
150 | marklist_removeat (library, i); /* because we kill it here */
|
---|
151 | marklist_free (&avglib[d.symnum]);
|
---|
152 | avglib[d.symnum] = NULL;
|
---|
153 | i--, count--;
|
---|
154 | break;
|
---|
155 | }
|
---|
156 | }
|
---|
157 | }
|
---|
158 | }
|
---|
159 |
|
---|
160 |
|
---|
161 | void
|
---|
162 | prune_on_size (marklistptr * list, int sizethres)
|
---|
163 | {
|
---|
164 | int count, i;
|
---|
165 | marktype d;
|
---|
166 |
|
---|
167 | if (sizethres)
|
---|
168 | {
|
---|
169 | count = marklist_length (*list);
|
---|
170 | i = 0;
|
---|
171 | do
|
---|
172 | {
|
---|
173 | marklist_getat (*list, i, &d);
|
---|
174 | if ((d.w <= sizethres) && (d.h <= sizethres))
|
---|
175 | {
|
---|
176 | marklist_removeat (list, i);
|
---|
177 | i--;
|
---|
178 | count--;
|
---|
179 | }
|
---|
180 | i++;
|
---|
181 | }
|
---|
182 | while (i < count);
|
---|
183 | }
|
---|
184 | }
|
---|
185 |
|
---|
186 |
|
---|
187 |
|
---|
188 | void
|
---|
189 | prune_on_area (marklistptr * list, int areathres)
|
---|
190 | {
|
---|
191 | int count, i;
|
---|
192 | marktype d;
|
---|
193 |
|
---|
194 | if (areathres)
|
---|
195 | {
|
---|
196 | count = marklist_length (*list);
|
---|
197 | i = 0;
|
---|
198 | do
|
---|
199 | {
|
---|
200 | marklist_getat (*list, i, &d);
|
---|
201 | if (d.set <= areathres)
|
---|
202 | {
|
---|
203 | marklist_removeat (list, i);
|
---|
204 | i--;
|
---|
205 | count--;
|
---|
206 | }
|
---|
207 | i++;
|
---|
208 | }
|
---|
209 | while (i < count);
|
---|
210 | }
|
---|
211 | }
|
---|
212 |
|
---|
213 |
|
---|
214 | void
|
---|
215 | averagedout_addagain (marklistptr origlist, marklistptr * librarylist)
|
---|
216 | {
|
---|
217 | marklistptr step, stepi;
|
---|
218 | int notfound;
|
---|
219 | int i, j;
|
---|
220 |
|
---|
221 | for (i = 0, step = origlist; step; i++, step = step->next)
|
---|
222 | {
|
---|
223 | notfound = 1;
|
---|
224 |
|
---|
225 | for (j = 0, stepi = *librarylist; stepi; j++, stepi = stepi->next)
|
---|
226 | if (NOT_SCREENED (step->data, stepi->data))
|
---|
227 | if (MATCH (&step->data, &stepi->data) < MATCH_VAL)
|
---|
228 | {
|
---|
229 | notfound = 0;
|
---|
230 | break;
|
---|
231 | }
|
---|
232 |
|
---|
233 | if (notfound)
|
---|
234 | {
|
---|
235 | marklist_addcopy (librarylist, step->data);
|
---|
236 | marklist_addcopy (&avglib[libsize], step->data);
|
---|
237 | libsize++;
|
---|
238 | if (libsize >= avglibsize)
|
---|
239 | average_space_enlarge ();
|
---|
240 | }
|
---|
241 | }
|
---|
242 | }
|
---|
243 |
|
---|
244 |
|
---|
245 |
|
---|
246 |
|
---|
247 |
|
---|
248 | void
|
---|
249 | main (int argc, char *args[])
|
---|
250 | {
|
---|
251 | int i;
|
---|
252 | FILE *lib;
|
---|
253 |
|
---|
254 | marklistptr origlist = NULL, librarylist = NULL;
|
---|
255 | marklistptr step;
|
---|
256 | char tempn[1000], sysstr[1000];
|
---|
257 | int count;
|
---|
258 | char *libraryname = NULL, *prunename = NULL;
|
---|
259 | int sizethres = 3, areathres = 0;
|
---|
260 | int pass;
|
---|
261 | int num_passes = 3;
|
---|
262 | int overwrite = 0;
|
---|
263 |
|
---|
264 | V = 0;
|
---|
265 |
|
---|
266 | if (argc < 2)
|
---|
267 | usage ();
|
---|
268 |
|
---|
269 | for (i = 1; i < argc; i++)
|
---|
270 | {
|
---|
271 | if (!strcmp (args[i], "-v"))
|
---|
272 | V = 1;
|
---|
273 | else if (!strcmp (args[i], "-h"))
|
---|
274 | usage ();
|
---|
275 | else if (!strcmp (args[i], "-Q"))
|
---|
276 | {
|
---|
277 | num_passes = 0;
|
---|
278 | }
|
---|
279 | else if (!strcmp (args[i], "-s"))
|
---|
280 | {
|
---|
281 | i++;
|
---|
282 | if ((i < argc) && (isinteger (args[i])))
|
---|
283 | sizethres = atoi (args[i]);
|
---|
284 | else
|
---|
285 | error_msg (args[0], "follow the -s option with a numeric arg >=0", "");
|
---|
286 | }
|
---|
287 | else if (!strcmp (args[i], "-a"))
|
---|
288 | {
|
---|
289 | i++;
|
---|
290 | if ((i < argc) && (isinteger (args[i])))
|
---|
291 | areathres = atoi (args[i]);
|
---|
292 | else
|
---|
293 | error_msg (args[0], "follow the -a option with a numeric arg >=0", "");
|
---|
294 | }
|
---|
295 | else if (args[i][0] == '-')
|
---|
296 | error_msg (args[0], "unknown switch:", args[i]);
|
---|
297 | else if (!libraryname)
|
---|
298 | libraryname = args[i];
|
---|
299 | else if (!prunename)
|
---|
300 | prunename = args[i];
|
---|
301 | else
|
---|
302 | error_msg (args[0], "too many filenames", "");
|
---|
303 | }
|
---|
304 |
|
---|
305 | if (!libraryname)
|
---|
306 | error_msg (args[0], "please specify a library file", "");
|
---|
307 |
|
---|
308 | if (V)
|
---|
309 | fprintf (stderr, "%s: processing...\n", args[0]);
|
---|
310 |
|
---|
311 | overwrite = 0;
|
---|
312 | if (!prunename)
|
---|
313 | {
|
---|
314 | prunename = libraryname;
|
---|
315 | if (V)
|
---|
316 | fprintf (stderr, "overwriting previous library file.\n");
|
---|
317 | overwrite = 1;
|
---|
318 | }
|
---|
319 |
|
---|
320 | if (overwrite)
|
---|
321 | {
|
---|
322 | tmpnam (tempn);
|
---|
323 | }
|
---|
324 | else
|
---|
325 | strcpy (tempn, prunename);
|
---|
326 |
|
---|
327 |
|
---|
328 | avglibsize = count = read_library (libraryname, &origlist);
|
---|
329 | if (V)
|
---|
330 | fprintf (stderr, "%d marks...", count);
|
---|
331 |
|
---|
332 | avglib = (marklistptr *) malloc (count * sizeof (marklistptr));
|
---|
333 | if (!avglib)
|
---|
334 | error_msg (args[0], "out of memory", "");
|
---|
335 | for (i = 0; i < avglibsize; i++)
|
---|
336 | avglib[i] = NULL;
|
---|
337 |
|
---|
338 |
|
---|
339 | prune_on_size (&origlist, sizethres);
|
---|
340 |
|
---|
341 | prune_on_area (&origlist, areathres);
|
---|
342 | if (V)
|
---|
343 | fprintf (stderr, "after threshold pruning, %d marks\n", count = marklist_length (origlist));
|
---|
344 |
|
---|
345 |
|
---|
346 | if (V)
|
---|
347 | fprintf (stderr, "starting greedy library creation...\n");
|
---|
348 |
|
---|
349 | greedy_add (origlist, &librarylist);
|
---|
350 |
|
---|
351 |
|
---|
352 | for (pass = 0; pass < num_passes; pass++)
|
---|
353 | {
|
---|
354 | marklist_free (&librarylist);
|
---|
355 | if (V)
|
---|
356 | fprintf (stderr, "averaging...\n");
|
---|
357 | librarylist = average_library ();
|
---|
358 | averagedout_addagain (origlist, &librarylist);
|
---|
359 | greedy_prune (&librarylist);
|
---|
360 | if (V)
|
---|
361 | fprintf (stderr, "after pass %d greedy prune %d marks\n", 1 + pass, marklist_length (librarylist));
|
---|
362 | }
|
---|
363 |
|
---|
364 |
|
---|
365 | lib = fopen (tempn, "wb");
|
---|
366 | if (lib == NULL)
|
---|
367 | error_msg (args[0], "trouble creating prune-library file.", "");
|
---|
368 |
|
---|
369 |
|
---|
370 | if (V)
|
---|
371 | fprintf (stderr, "writing to file: %s...", prunename);
|
---|
372 | for (step = librarylist, count = 0; step; step = step->next, count++)
|
---|
373 | {
|
---|
374 | step->data.symnum = count;
|
---|
375 | write_library_mark (lib, step->data);
|
---|
376 | }
|
---|
377 |
|
---|
378 | if (V)
|
---|
379 | fprintf (stderr, "%d marks.\n", count);
|
---|
380 | fclose (lib);
|
---|
381 |
|
---|
382 | if (overwrite)
|
---|
383 | {
|
---|
384 | sprintf (sysstr, "mv %s %s", tempn, prunename);
|
---|
385 | system (sysstr); /* move temp to proper name */
|
---|
386 | }
|
---|
387 |
|
---|
388 | for (i = 0; i < avglibsize; i++)
|
---|
389 | {
|
---|
390 | marklist_free (&avglib[i]);
|
---|
391 | free (avglib[i]);
|
---|
392 | }
|
---|
393 | }
|
---|