source: trunk/indexers/mg/src/images/match.c@ 3745

Last change on this file since 3745 was 3745, checked in by mdewsnip, 21 years ago

Addition of MG package for search and retrieval
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 10.8 KB
Line 
1/**************************************************************************
2 *
3 * match.c -- Functions related to matching marks
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: match.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 "utils.h"
29
30
31/* error mask goes from 0..8, single pixel errors are worth nothing */
32int
33WXOR_match (marktype b1, marktype b2)
34{
35 int r, c, i, j;
36 int minr, minc;
37 int maxr, maxc;
38 int offx, offy;
39 int p1, p2;
40 int count = 0;
41 marktype d;
42
43 offx = b1.xcen - b2.xcen;
44 offy = b1.ycen - b2.ycen;
45
46 minc = min (0, offx);
47 minr = min (0, offy);
48
49 maxc = max (b1.w, b2.w + offx);
50 maxr = max (b1.h, b2.h + offy);
51
52 d.w = maxc - minc + 1;
53 d.h = maxr - minr + 1;
54 d.bitmap = pbm_allocarray (d.w, d.h);
55
56
57 for (r = minr; r < maxr; r++)
58 for (c = minc; c < maxc; c++)
59 {
60 if ((r >= 0) && (c >= 0) && (r < b1.h) && (c < b1.w))
61 p1 = pbm_getpixel (b1.bitmap, c, r);
62 else
63 p1 = 0; /* 0 = back ground colour */
64 if ((r - offy >= 0) && (c - offx >= 0) && (r - offy < b2.h) && (c - offx < b2.w))
65 p2 = pbm_getpixel (b2.bitmap, c - offx, r - offy);
66 else
67 p2 = 0; /* background colour */
68 pbm_putpixel (d.bitmap, c - minc, r - minr, p1 != p2);
69 }
70 for (r = minr; r < maxr; r++)
71 for (c = minc; c < maxc; c++)
72 if (pbm_getpixel (d.bitmap, c - minc, r - minr))
73 for (i = -1; i <= 1; i++)
74 for (j = -1; j <= 1; j++)
75 if ((r + j >= 0) && (c + i >= 0) && (r + j < d.h) && (c + i < d.w) && ((i != 0) || (j != 0)) && (pbm_getpixel (d.bitmap, c + i - minc, r + j - minr)))
76 count++;
77 pbm_freearray (&d.bitmap, d.h);
78 return count;
79}
80
81
82
83/* define an array for most matches, if it is a massive mark, then WXOR is called */
84#define S_SIZE 500
85
86static unsigned char scratch[S_SIZE][S_SIZE], sc2[S_SIZE][S_SIZE];
87
88
89
90
91/* Weighted AND-NOT */
92
93int
94WAN_match (marktype b1, marktype b2)
95{
96 int r, c, i, j;
97 int minr, minc;
98 int maxr, maxc;
99 int offx, offy;
100 int p1, p2;
101 int count = 0;
102
103 offx = b1.xcen - b2.xcen;
104 offy = b1.ycen - b2.ycen;
105
106 minc = min (0, offx);
107 minr = min (0, offy);
108
109 maxc = max (b1.w, b2.w + offx);
110 maxr = max (b1.h, b2.h + offy);
111
112 if (((maxc - minc) >= S_SIZE) || ((maxr - minr) >= S_SIZE))
113 return WXOR_match (b1, b2);
114
115 for (r = minr; r < maxr; r++)
116 for (c = minc; c < maxc; c++)
117 {
118 scratch[r - minr][c - minc] = sc2[r - minr][c - minc] = 0;
119 if ((r >= 0) && (c >= 0) && (r < b1.h) && (c < b1.w))
120 p1 = pbm_getpixel (b1.bitmap, c, r);
121 else
122 p1 = 0; /* 0 == background colour */
123 if ((r - offy >= 0) && (c - offx >= 0) && (r - offy < b2.h) && (c - offx < b2.w))
124 p2 = pbm_getpixel (b2.bitmap, c - offx, r - offy);
125 else
126 p2 = 0;
127
128 if ((p1 == 0) && (p2 == 1)) /* p1 not set, p2 = set */
129 scratch[r - minr][c - minc] = 1;
130 if ((p1 == 1) && (p2 == 0)) /* p1 set, p2 not set */
131 sc2[r - minr][c - minc] = 1;
132 }
133
134 count = 0;
135 for (r = minr; r < maxr; r++)
136 for (c = minc; c < maxc; c++)
137 if (scratch[r - minr][c - minc])
138 for (i = -1; i <= 1; i++)
139 for (j = -1; j <= 1; j++)
140 if ((r + j >= minr) && (c + i >= minc) && (r + j < maxr) && (c + i < maxc) && ((i != 0) || (j != 0)) && scratch[r - minr + j][c - minc + i])
141 count++;
142
143 for (r = minr; r < maxr; r++)
144 for (c = minc; c < maxc; c++)
145 if (sc2[r - minr][c - minc])
146 for (i = -1; i <= 1; i++)
147 for (j = -1; j <= 1; j++)
148 if ((r + j >= minr) && (c + i >= minc) && (r + j < maxr) && (c + i < maxc) && ((i != 0) || (j != 0)) && sc2[r - minr + j][c - minc + i])
149 count++;
150
151 return count;
152}
153
154/* oc 8 must be in a clock wise order, with oc[0] a corner */
155struct
156{
157 int x, y;
158}
159oc[8] =
160{
161 {
162 -1, -1
163 }
164 ,
165 {
166 0, -1
167 }
168 ,
169 {
170 1, -1
171 }
172 ,
173 {
174 1, 0
175 }
176 ,
177 {
178 1, 1
179 }
180 ,
181 {
182 0, 1
183 }
184 ,
185 {
186 -1, 1
187 }
188 ,
189 {
190 -1, 0
191 }
192};
193
194
195
196static void
197xormatchscratch (marktype * b1, marktype * b2, int minr, int maxr, int minc, int maxc, int offx, int offy)
198{
199 int r, c, rmm, roo, coo;
200 int p1, p2;
201 Pixel **bm1 = b1->bitmap, **bm2 = b2->bitmap;
202 int w1 = b1->w, h1 = b1->h, w2 = b2->w, h2 = b2->h;
203
204 for (r = minr; r < maxr; r++)
205 {
206 rmm = r - minr;
207 roo = r - offy;
208 p1 = 0;
209 for (c = minc; c < 0; c++)
210 {
211 coo = c - offx;
212 scratch[rmm][c - minc] = sc2[rmm][c - minc] = 0;
213 if ((coo >= 0) && (roo >= 0) && (coo < w2) && (roo < h2))
214 p2 = pbm_getpixel (bm2, coo, roo);
215 else
216 p2 = 0; /* background */
217 scratch[rmm][c - minc] = p1 != p2;
218 }
219 for (c = 0; c < maxc; c++)
220 {
221 coo = c - offx;
222 scratch[rmm][c - minc] = sc2[rmm][c - minc] = 0;
223 if ((r >= 0) && (c < w1) && (r < h1))
224 p1 = pbm_getpixel (bm1, c, r);
225 else
226 p1 = 0; /* background */
227 if ((coo >= 0) && (roo >= 0) && (coo < w2) && (roo < h2))
228 p2 = pbm_getpixel (bm2, coo, roo);
229 else
230 p2 = 0; /* background */
231 scratch[rmm][c - minc] = p1 != p2;
232 }
233 }
234}
235
236
237
238int
239CSIS_match (marktype * b1, marktype * b2)
240{
241 int r, c, i;
242 int minr, minc;
243 int maxr, maxc;
244 int offx, offy, fepcount;
245 int totscratch = 0;
246
247
248 offx = b1->xcen - b2->xcen;
249 offy = b1->ycen - b2->ycen;
250
251 minc = min (0, offx);
252 minr = min (0, offy);
253
254 maxc = max (b1->w, b2->w + offx);
255 maxr = max (b1->h, b2->h + offy);
256
257 if (((maxc - minc) >= S_SIZE) || ((maxr - minr) >= S_SIZE))
258 return WXOR_match (*b1, *b2);
259
260 /* set the scratch array to 1 if there is an XOR match */
261
262 xormatchscratch (b1, b2, minr, maxr, minc, maxc, offx, offy);
263 /* We how have the XOR map. Scratch contains the number of neighbours, 1=1 neighbour set...etc */
264
265 /* CSIS rule 1, if FEP (four error pels) then exit */
266 fepcount = 0;
267 for (r = minr; r < maxr - 1; r++)
268 for (c = minc; c < maxc - 1; c++)
269 if ((scratch[r - minr][c - minc]) && (scratch[r - minr + 1][c - minc]) &&
270 (scratch[r - minr][c - minc + 1]) && (scratch[r - minr + 1][c - minc + 1]))
271 {
272 fepcount++;
273 if (fepcount == 1)
274 return 10001;
275 }
276
277 /* foreach set pixel, update scratch with the number of pels around in five dir's.
278 FPN (five-pel neighbour hood) */
279 for (r = minr; r < maxr; r++)
280 for (c = minc; c < maxc; c++)
281 if (scratch[r - minr][c - minc])
282 {
283 sc2[r - minr][c - minc] = 1; /* itself */
284 for (i = 1; i < 8; i += 3)
285 if (((r + oc[i].y) >= minr) && ((c + oc[i].x) >= minc) && ((r + oc[i].y) < maxr) && ((c + oc[i].x) < maxc))
286 if (scratch[r + oc[i].y - minr][c + oc[i].x - minc])
287 sc2[r - minr][c - minc]++;
288 }
289 /* now scratch has the value of the FPN - 1=single error, 5=4 neighbouring errors etc... */
290
291 /* set scratch and sc2 to be the same */
292 for (r = minr; r < maxr; r++)
293 for (c = minc; c < maxc; c++)
294 totscratch += scratch[r - minr][c - minc] = sc2[r - minr][c - minc];
295
296 for (r = minr; r < maxr; r++)
297 for (c = minc; c < maxc; c++)
298 {
299 /* CSIS rule 2i: an error pel has 2 or more neighbours---this num is the same as PMS */
300 if (scratch[r - minr][c - minc] >= 3)
301 if ((r - minr >= 1) && (c - minc >= 1) && (r - minr < (maxr - 1)) && (c - minc < (maxc - 1)))
302 {
303 int i, numsep = 0;
304 /* find how many neighbours a set pixel has, only check the 4 edges-FPN */
305 for (i = 1; i < 8; i += 2)
306 if (scratch[r + oc[i].y - minr][c + oc[i].x - minc]) /* if a scratch pixel is set */
307 {
308 if ((scratch[r + oc[(i + 2) % 8].y - minr][c + oc[(i + 2) % 8].x - minc] == 0) &&
309 (scratch[r + oc[(i + 6) % 8].y - minr][c + oc[(i + 6) % 8].x - minc] == 0)
310 )
311 numsep++;
312 }
313
314 if ((b1->w >= 12) || (b2->w >= 12) || (b1->h >= 12) || (b2->h >= 12))
315 {
316
317 /* PMS rule 2ii: at least two of its neigh. error p's aren't connected */
318 if (numsep >= 2)
319 {
320 int i, j, p, p2, same;
321
322 /* PMS rule 2(iii), look for regions in the original images of 3x3 the same */
323 if ((c >= 0) && (r >= 0) && (c < b1->w) && (r < b1->h))
324 {
325 p = pbm_getpixel (b1->bitmap, c, r);
326 same = 0;
327 for (i = -1; i <= 1; i++)
328 for (j = -1; j <= 1; j++)
329 {
330 if ((c + i >= 0) && (r + j >= 0) && (c + i < b1->w) && (r + j < b1->h))
331 p2 = pbm_getpixel (b1->bitmap, c + i, r + j);
332 else
333 p2 = 0;
334 if (p2 == p)
335 same++;
336 } /* i,j loop */
337 /* PMS rule 2(iii) */
338 if (same == 9)
339 {
340 return 10002;
341 }
342 } /* (*b1) in range */
343
344 if ((c - offx >= 0) && (r - offy >= 0) && (c - offx < b2->w) && (r - offy < b2->h))
345 {
346 p = pbm_getpixel (b2->bitmap, c - offx, r - offy);
347 same = 0;
348 for (i = -1; i <= 1; i++)
349 for (j = -1; j <= 1; j++)
350 {
351 if ((c + i - offx >= 0) && (r + j - offy >= 0) && (c + i - offx < b2->w) && (r + j - offy < b2->h))
352 p2 = pbm_getpixel (b2->bitmap, c + i - offx, r + j - offy);
353 else
354 p2 = 0;
355 if (p2 == p)
356 same++;
357 } /* i,j loop */
358 /* PMS rule 2(iii) */
359 if (same == 9)
360 {
361 return 10003;
362 }
363 }
364 }
365 }
366 else
367 { /* do the CSIS rule */
368 /* CSIS rule 2ii: at least two of its neigh. error p's aren't connected */
369 if (numsep >= 2)
370 {
371 int i, p, p2, same;
372
373 /* PMS rule 2(iii), look for regions in the original images of 3x3 the same */
374 if ((c >= 0) && (r >= 0) && (c < b1->w) && (r < b1->h))
375 {
376 p = pbm_getpixel (b1->bitmap, c, r);
377 same = 1;
378 for (i = 1; i < 8; i += 2)
379 if ((c + oc[i].x >= 0) && (r + oc[i].y >= 0) && (c + oc[i].x < b1->w) && (r + oc[i].y < b1->h))
380 p2 = pbm_getpixel (b1->bitmap, c + oc[i].x, r + oc[i].y);
381 else
382 p2 = 0;
383 if (p2 == p)
384 same++;
385
386 /* CSIS rule 2(iii) */
387 if (same == 5)
388 {
389 return 10002;
390 }
391 }
392
393 if ((c - offx >= 0) && (r - offy >= 0) && (c - offx < b2->w) && (r - offy < b2->h))
394 {
395 p = pbm_getpixel (b2->bitmap, c - offx, r - offy);
396 same = 1;
397 for (i = 1; i < 8; i += 2)
398 if ((c + oc[i].x - offx >= 0) && (r + oc[i].y - offy >= 0) && (c + oc[i].x - offx < b2->w) && (r + oc[i].y - offy < b2->h))
399 p2 = pbm_getpixel (b2->bitmap, c + oc[i].x - offx, r + oc[i].y - offy);
400 else
401 p2 = 0;
402 if (p2 == p)
403 same++;
404
405 /* CSIS rule 2(iii) */
406 if (same == 5)
407 {
408 return 10003;
409 }
410 }
411 }
412 }
413 }
414 }
415
416 return totscratch;
417}
Note: See TracBrowser for help on using the repository browser.