1 /******************************************************************************
2 ** Filename: intfx.c
3 ** Purpose: Integer character normalization & feature extraction
4 ** Author: Robert Moss
5 ** History: Tue May 21 15:51:57 MDT 1991, RWM, Created.
6 **
7 ** (c) Copyright Hewlett-Packard Company, 1988.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 ******************************************************************************/
18 /**----------------------------------------------------------------------------
19 Include Files and Type Defines
20 ----------------------------------------------------------------------------**/
21 #include "intfx.h"
22 #include "intmatcher.h"
23 #include "const.h"
24 #ifdef __UNIX__
25 #endif
26
27 /**----------------------------------------------------------------------------
28 Private Function Prototypes
29 ----------------------------------------------------------------------------**/
30 int SaveFeature();
31 uinT8 TableLookup();
32 uinT8 MySqrt2();
33 void ClipRadius();
34
35 INT_VAR(classify_radius_gyr_min_man, 255,
36 "Minimum Radius of Gyration Mantissa 0-255: ");
37
38 INT_VAR(classify_radius_gyr_min_exp, 0,
39 "Minimum Radius of Gyration Exponent 0-255: ");
40
41 INT_VAR(classify_radius_gyr_max_man, 158,
42 "Maximum Radius of Gyration Mantissa 0-255: ");
43
44 INT_VAR(classify_radius_gyr_max_exp, 8,
45 "Maximum Radius of Gyration Exponent 0-255: ");
46
47 /**----------------------------------------------------------------------------
48 Global Data Definitions and Declarations
49 ----------------------------------------------------------------------------**/
50 #define ATAN_TABLE_SIZE 64
51
52 static uinT8 AtanTable[ATAN_TABLE_SIZE];
53
54 /**----------------------------------------------------------------------------
55 Public Code
56 ----------------------------------------------------------------------------**/
57 /*---------------------------------------------------------------------------*/
InitIntegerFX()58 void InitIntegerFX() {
59 int i;
60
61 for (i = 0; i < ATAN_TABLE_SIZE; i++)
62 AtanTable[i] =
63 (uinT8) (atan ((i / (float) ATAN_TABLE_SIZE)) * 128.0 / PI + 0.5);
64
65 }
66
67
68 /*--------------------------------------------------------------------------*/
ExtractIntFeat(TBLOB * Blob,INT_FEATURE_ARRAY BLFeat,INT_FEATURE_ARRAY CNFeat,INT_FX_RESULT Results)69 int ExtractIntFeat(TBLOB *Blob,
70 INT_FEATURE_ARRAY BLFeat,
71 INT_FEATURE_ARRAY CNFeat,
72 INT_FX_RESULT Results) {
73
74 TESSLINE *OutLine;
75 EDGEPT *Loop, *LoopStart, *Segment;
76 inT16 LastX, LastY, Xmean, Ymean;
77 inT32 NormX, NormY, DeltaX, DeltaY;
78 inT32 Xsum, Ysum;
79 uinT32 Ix, Iy, LengthSum;
80 uinT16 n;
81 uinT8 Theta;
82 uinT16 NumBLFeatures, NumCNFeatures;
83 uinT8 RxInv, RyInv; /* x.xxxxxxx * 2^Exp */
84 uinT8 RxExp, RyExp;
85 /* sxxxxxxxxxxxxxxxxxxxxxxx.xxxxxxxx */
86 register inT32 pfX, pfY, dX, dY;
87 uinT16 Length;
88 register int i;
89
90 Results->Length = 0;
91 Results->Xmean = 0;
92 Results->Ymean = 0;
93 Results->Rx = 0;
94 Results->Ry = 0;
95 Results->NumBL = 0;
96 Results->NumCN = 0;
97
98 /* find Xmean, Ymean */
99 NumBLFeatures = 0;
100 NumCNFeatures = 0;
101 OutLine = Blob->outlines;
102 Xsum = 0;
103 Ysum = 0;
104 LengthSum = 0;
105 while (OutLine != NULL) {
106 LoopStart = OutLine->loop;
107 Loop = LoopStart;
108 LastX = Loop->pos.x;
109 LastY = Loop->pos.y;
110 /* Check for bad loops */
111 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
112 return FALSE;
113 do {
114 Segment = Loop;
115 Loop = Loop->next;
116 NormX = Loop->pos.x;
117 NormY = Loop->pos.y;
118
119 n = 1;
120 if (!is_hidden_edge (Segment)) {
121 DeltaX = NormX - LastX;
122 DeltaY = NormY - LastY;
123 Length = MySqrt (DeltaX, DeltaY);
124 n = ((Length << 2) + Length + 32) >> 6;
125 if (n != 0) {
126 Xsum += ((LastX << 1) + DeltaX) * (int) Length;
127 Ysum += ((LastY << 1) + DeltaY) * (int) Length;
128 LengthSum += Length;
129 }
130 }
131 if (n != 0) { /* Throw away a point that is too close */
132 LastX = NormX;
133 LastY = NormY;
134 }
135 }
136 while (Loop != LoopStart);
137 OutLine = OutLine->next;
138 }
139 if (LengthSum == 0)
140 return FALSE;
141 Xmean = (Xsum / (inT32) LengthSum) >> 1;
142 Ymean = (Ysum / (inT32) LengthSum) >> 1;
143
144 Results->Length = LengthSum;
145 Results->Xmean = Xmean;
146 Results->Ymean = Ymean;
147
148 /* extract Baseline normalized features, */
149 /* and find 2nd moments & radius of gyration */
150 Ix = 0;
151 Iy = 0;
152 NumBLFeatures = 0;
153 OutLine = Blob->outlines;
154 while (OutLine != NULL) {
155 LoopStart = OutLine->loop;
156 Loop = LoopStart;
157 LastX = Loop->pos.x - Xmean;
158 LastY = Loop->pos.y;
159 /* Check for bad loops */
160 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
161 return FALSE;
162 do {
163 Segment = Loop;
164 Loop = Loop->next;
165 NormX = Loop->pos.x - Xmean;
166 NormY = Loop->pos.y;
167
168 n = 1;
169 if (!is_hidden_edge (Segment)) {
170 DeltaX = NormX - LastX;
171 DeltaY = NormY - LastY;
172 Length = MySqrt (DeltaX, DeltaY);
173 n = ((Length << 2) + Length + 32) >> 6;
174 if (n != 0) {
175 Theta = TableLookup (DeltaY, DeltaX);
176 dX = (DeltaX << 8) / n;
177 dY = (DeltaY << 8) / n;
178 pfX = (LastX << 8) + (dX >> 1);
179 pfY = (LastY << 8) + (dY >> 1);
180 Ix += ((pfY >> 8) - Ymean) * ((pfY >> 8) - Ymean);
181 Iy += (pfX >> 8) * (pfX >> 8);
182 if (SaveFeature (BLFeat, NumBLFeatures, (inT16) (pfX >> 8),
183 (inT16) ((pfY >> 8) - 128),
184 Theta) == FALSE)
185 return FALSE;
186 NumBLFeatures++;
187 for (i = 1; i < n; i++) {
188 pfX += dX;
189 pfY += dY;
190 Ix += ((pfY >> 8) - Ymean) * ((pfY >> 8) - Ymean);
191 Iy += (pfX >> 8) * (pfX >> 8);
192 if (SaveFeature
193 (BLFeat, NumBLFeatures, (inT16) (pfX >> 8),
194 (inT16) ((pfY >> 8) - 128), Theta) == FALSE)
195 return FALSE;
196 NumBLFeatures++;
197 }
198 }
199 }
200 if (n != 0) { /* Throw away a point that is too close */
201 LastX = NormX;
202 LastY = NormY;
203 }
204 }
205 while (Loop != LoopStart);
206 OutLine = OutLine->next;
207 }
208 if (Ix == 0)
209 Ix = 1;
210 if (Iy == 0)
211 Iy = 1;
212 RxInv = MySqrt2 (NumBLFeatures, Ix, &RxExp);
213 RyInv = MySqrt2 (NumBLFeatures, Iy, &RyExp);
214 ClipRadius(&RxInv, &RxExp, &RyInv, &RyExp);
215
216 Results->Rx = (inT16) (51.2 / (double) RxInv * pow (2.0, (double) RxExp));
217 Results->Ry = (inT16) (51.2 / (double) RyInv * pow (2.0, (double) RyExp));
218 if (Results->Ry == 0) {
219 /*
220 This would result in features having 'nan' values.
221 Since the expression is always > 0, assign a value of 1.
222 */
223 Results->Ry = 1;
224 }
225 Results->NumBL = NumBLFeatures;
226
227 /* extract character normalized features */
228 NumCNFeatures = 0;
229 OutLine = Blob->outlines;
230 while (OutLine != NULL) {
231 LoopStart = OutLine->loop;
232 Loop = LoopStart;
233 LastX = (Loop->pos.x - Xmean) * RyInv;
234 LastY = (Loop->pos.y - Ymean) * RxInv;
235 LastX >>= (inT8) RyExp;
236 LastY >>= (inT8) RxExp;
237 /* Check for bad loops */
238 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
239 return FALSE;
240 do {
241 Segment = Loop;
242 Loop = Loop->next;
243 NormX = (Loop->pos.x - Xmean) * RyInv;
244 NormY = (Loop->pos.y - Ymean) * RxInv;
245 NormX >>= (inT8) RyExp;
246 NormY >>= (inT8) RxExp;
247
248 n = 1;
249 if (!is_hidden_edge (Segment)) {
250 DeltaX = NormX - LastX;
251 DeltaY = NormY - LastY;
252 Length = MySqrt (DeltaX, DeltaY);
253 n = ((Length << 2) + Length + 32) >> 6;
254 if (n != 0) {
255 Theta = TableLookup (DeltaY, DeltaX);
256 dX = (DeltaX << 8) / n;
257 dY = (DeltaY << 8) / n;
258 pfX = (LastX << 8) + (dX >> 1);
259 pfY = (LastY << 8) + (dY >> 1);
260 if (SaveFeature (CNFeat, NumCNFeatures, (inT16) (pfX >> 8),
261 (inT16) ((pfY >> 8)), Theta) == FALSE)
262 return FALSE;
263 NumCNFeatures++;
264 for (i = 1; i < n; i++) {
265 pfX += dX;
266 pfY += dY;
267 if (SaveFeature
268 (CNFeat, NumCNFeatures, (inT16) (pfX >> 8),
269 (inT16) ((pfY >> 8)), Theta) == FALSE)
270 return FALSE;
271 NumCNFeatures++;
272 }
273 }
274 }
275 if (n != 0) { /* Throw away a point that is too close */
276 LastX = NormX;
277 LastY = NormY;
278 }
279 }
280 while (Loop != LoopStart);
281 OutLine = OutLine->next;
282 }
283
284 Results->NumCN = NumCNFeatures;
285 return TRUE;
286 }
287
288
289 /*--------------------------------------------------------------------------*/
TableLookup(inT32 Y,inT32 X)290 uinT8 TableLookup(inT32 Y, inT32 X) {
291 inT16 Angle;
292 uinT16 Ratio;
293 uinT32 AbsX, AbsY;
294
295 assert ((X != 0) || (Y != 0));
296 if (X < 0)
297 AbsX = -X;
298 else
299 AbsX = X;
300 if (Y < 0)
301 AbsY = -Y;
302 else
303 AbsY = Y;
304 if (AbsX > AbsY)
305 Ratio = AbsY * ATAN_TABLE_SIZE / AbsX;
306 else
307 Ratio = AbsX * ATAN_TABLE_SIZE / AbsY;
308 if (Ratio >= ATAN_TABLE_SIZE)
309 Ratio = ATAN_TABLE_SIZE - 1;
310 Angle = AtanTable[Ratio];
311 if (X >= 0)
312 if (Y >= 0)
313 if (AbsX > AbsY)
314 Angle = Angle;
315 else
316 Angle = 64 - Angle;
317 else if (AbsX > AbsY)
318 Angle = 256 - Angle;
319 else
320 Angle = 192 + Angle;
321 else if (Y >= 0)
322 if (AbsX > AbsY)
323 Angle = 128 - Angle;
324 else
325 Angle = 64 + Angle;
326 else if (AbsX > AbsY)
327 Angle = 128 + Angle;
328 else
329 Angle = 192 - Angle;
330
331 /* reverse angles to match old feature extractor: Angle += PI */
332 Angle += 128;
333 Angle &= 255;
334 return (uinT8) Angle;
335 }
336
337
338 /*--------------------------------------------------------------------------*/
SaveFeature(INT_FEATURE_ARRAY FeatureArray,uinT16 FeatureNum,inT16 X,inT16 Y,uinT8 Theta)339 int SaveFeature(INT_FEATURE_ARRAY FeatureArray,
340 uinT16 FeatureNum,
341 inT16 X,
342 inT16 Y,
343 uinT8 Theta) {
344 INT_FEATURE Feature;
345
346 if (FeatureNum >= MAX_NUM_INT_FEATURES)
347 return FALSE;
348
349 Feature = &(FeatureArray[FeatureNum]);
350
351 X = X + 128;
352 Y = Y + 128;
353
354 if (X > 255)
355 Feature->X = 255;
356 else if (X < 0)
357 Feature->X = 0;
358 else
359 Feature->X = X;
360
361 if (Y > 255)
362 Feature->Y = 255;
363 else if (Y < 0)
364 Feature->Y = 0;
365 else
366 Feature->Y = Y;
367
368 Feature->Theta = Theta;
369
370 return TRUE;
371 }
372
373
374 /*---------------------------------------------------------------------------*/
MySqrt(inT32 X,inT32 Y)375 uinT16 MySqrt(inT32 X, inT32 Y) {
376 register uinT16 SqRoot;
377 register uinT32 Square;
378 register uinT16 BitLocation;
379 register uinT32 Sum;
380
381 if (X < 0)
382 X = -X;
383 if (Y < 0)
384 Y = -Y;
385
386 if (X > EvidenceMultMask)
387 X = EvidenceMultMask;
388 if (Y > EvidenceMultMask)
389 Y = EvidenceMultMask;
390
391 Sum = X * X + Y * Y;
392
393 BitLocation = 1024;
394 SqRoot = 0;
395 do {
396 Square = (SqRoot | BitLocation) * (SqRoot | BitLocation);
397 if (Square <= Sum)
398 SqRoot |= BitLocation;
399 BitLocation >>= 1;
400 }
401 while (BitLocation);
402
403 return SqRoot;
404 }
405
406
407 /*--------------------------------------------------------------------------*/
MySqrt2(uinT16 N,uinT32 I,uinT8 * Exp)408 uinT8 MySqrt2(uinT16 N, uinT32 I, uinT8 *Exp) {
409 register inT8 k;
410 register uinT32 N2;
411 register uinT8 SqRoot;
412 register uinT16 Square;
413 register uinT8 BitLocation;
414 register uinT16 Ratio;
415
416 N2 = N * 41943;
417
418 k = 9;
419 while ((N2 & 0xc0000000) == 0) {
420 N2 <<= 2;
421 k += 1;
422 }
423
424 while ((I & 0xc0000000) == 0) {
425 I <<= 2;
426 k -= 1;
427 }
428
429 if (((N2 & 0x80000000) == 0) && ((I & 0x80000000) == 0)) {
430 N2 <<= 1;
431 I <<= 1;
432 }
433
434 N2 &= 0xffff0000;
435 I >>= 14;
436 Ratio = N2 / I;
437
438 BitLocation = 128;
439 SqRoot = 0;
440 do {
441 Square = (SqRoot | BitLocation) * (SqRoot | BitLocation);
442 if (Square <= Ratio)
443 SqRoot |= BitLocation;
444 BitLocation >>= 1;
445 }
446 while (BitLocation);
447
448 if (k < 0) {
449 *Exp = 0;
450 return 255;
451 }
452 else {
453 *Exp = k;
454 return SqRoot;
455 }
456 }
457
458
459 /*-------------------------------------------------------------------------*/
ClipRadius(uinT8 * RxInv,uinT8 * RxExp,uinT8 * RyInv,uinT8 * RyExp)460 void ClipRadius(uinT8 *RxInv, uinT8 *RxExp, uinT8 *RyInv, uinT8 *RyExp) {
461 register uinT8 AM, BM, AE, BE;
462 register uinT8 BitN, LastCarry;
463 int RxInvLarge, RyInvSmall;
464
465 AM = classify_radius_gyr_min_man;
466 AE = classify_radius_gyr_min_exp;
467 BM = *RxInv;
468 BE = *RxExp;
469 LastCarry = 1;
470 while ((AM != 0) || (BM != 0)) {
471 if (AE > BE) {
472 BitN = LastCarry + (AM & 1) + 1;
473 AM >>= 1;
474 AE--;
475 }
476 else if (AE < BE) {
477 BitN = LastCarry + (!(BM & 1));
478 BM >>= 1;
479 BE--;
480 }
481 else { /* AE == BE */
482 BitN = LastCarry + (AM & 1) + (!(BM & 1));
483 AM >>= 1;
484 BM >>= 1;
485 AE--;
486 BE--;
487 }
488 LastCarry = (BitN & 2) > 1;
489 BitN = BitN & 1;
490 }
491 BitN = LastCarry + 1;
492 LastCarry = (BitN & 2) > 1;
493 BitN = BitN & 1;
494
495 if (BitN == 1) {
496 *RxInv = classify_radius_gyr_min_man;
497 *RxExp = classify_radius_gyr_min_exp;
498 }
499
500 AM = classify_radius_gyr_min_man;
501 AE = classify_radius_gyr_min_exp;
502 BM = *RyInv;
503 BE = *RyExp;
504 LastCarry = 1;
505 while ((AM != 0) || (BM != 0)) {
506 if (AE > BE) {
507 BitN = LastCarry + (AM & 1) + 1;
508 AM >>= 1;
509 AE--;
510 }
511 else if (AE < BE) {
512 BitN = LastCarry + (!(BM & 1));
513 BM >>= 1;
514 BE--;
515 }
516 else { /* AE == BE */
517 BitN = LastCarry + (AM & 1) + (!(BM & 1));
518 AM >>= 1;
519 BM >>= 1;
520 AE--;
521 BE--;
522 }
523 LastCarry = (BitN & 2) > 1;
524 BitN = BitN & 1;
525 }
526 BitN = LastCarry + 1;
527 LastCarry = (BitN & 2) > 1;
528 BitN = BitN & 1;
529
530 if (BitN == 1) {
531 *RyInv = classify_radius_gyr_min_man;
532 *RyExp = classify_radius_gyr_min_exp;
533 }
534
535 AM = classify_radius_gyr_max_man;
536 AE = classify_radius_gyr_max_exp;
537 BM = *RxInv;
538 BE = *RxExp;
539 LastCarry = 1;
540 while ((AM != 0) || (BM != 0)) {
541 if (AE > BE) {
542 BitN = LastCarry + (AM & 1) + 1;
543 AM >>= 1;
544 AE--;
545 }
546 else if (AE < BE) {
547 BitN = LastCarry + (!(BM & 1));
548 BM >>= 1;
549 BE--;
550 }
551 else { /* AE == BE */
552 BitN = LastCarry + (AM & 1) + (!(BM & 1));
553 AM >>= 1;
554 BM >>= 1;
555 AE--;
556 BE--;
557 }
558 LastCarry = (BitN & 2) > 1;
559 BitN = BitN & 1;
560 }
561 BitN = LastCarry + 1;
562 LastCarry = (BitN & 2) > 1;
563 BitN = BitN & 1;
564
565 if (BitN == 1)
566 RxInvLarge = 1;
567 else
568 RxInvLarge = 0;
569
570 AM = *RyInv;
571 AE = *RyExp;
572 BM = classify_radius_gyr_max_man;
573 BE = classify_radius_gyr_max_exp;
574 LastCarry = 1;
575 while ((AM != 0) || (BM != 0)) {
576 if (AE > BE) {
577 BitN = LastCarry + (AM & 1) + 1;
578 AM >>= 1;
579 AE--;
580 }
581 else if (AE < BE) {
582 BitN = LastCarry + (!(BM & 1));
583 BM >>= 1;
584 BE--;
585 }
586 else { /* AE == BE */
587 BitN = LastCarry + (AM & 1) + (!(BM & 1));
588 AM >>= 1;
589 BM >>= 1;
590 AE--;
591 BE--;
592 }
593 LastCarry = (BitN & 2) > 1;
594 BitN = BitN & 1;
595 }
596 BitN = LastCarry + 1;
597 LastCarry = (BitN & 2) > 1;
598 BitN = BitN & 1;
599
600 if (BitN == 1)
601 RyInvSmall = 1;
602 else
603 RyInvSmall = 0;
604
605 if (RxInvLarge && RyInvSmall) {
606 *RyInv = classify_radius_gyr_max_man;
607 *RyExp = classify_radius_gyr_max_exp;
608 }
609
610 }
611