00001
00019
00020
00021
00022 #include "intfx.h"
00023 #include "intmatcher.h"
00024 #include "const.h"
00025 #ifdef __UNIX__
00026 #include <assert.h>
00027 #endif
00028
00029
00030
00031
00032 int SaveFeature();
00033 UINT8 TableLookup();
00034 UINT8 MySqrt2();
00035 void ClipRadius();
00036
00055 make_int_var (RadiusGyrMinMan, 255, MakeRadiusGyrMinMan,
00056 16, 10, SetRadiusGyrMinMan, "Minimum Radius of Gyration Mantissa 0-255: ");
00057 make_int_var (RadiusGyrMinExp, 0, MakeRadiusGyrMinExp,
00058 16, 11, SetRadiusGyrMinExp, "Minimum Radius of Gyration Exponent 0-255: ");
00059 make_int_var (RadiusGyrMaxMan, 158, MakeRadiusGyrMaxMan,
00060 16, 12, SetRadiusGyrMaxMan, "Maximum Radius of Gyration Mantissa 0-255: ");
00061 make_int_var (RadiusGyrMaxExp, 8, MakeRadiusGyrMaxExp,
00062 16, 13, SetRadiusGyrMaxExp, "Maximum Radius of Gyration Exponent 0-255: ");
00065
00066
00067
00068 #define ATAN_TABLE_SIZE 64
00069
00073 static UINT8 AtanTable[ATAN_TABLE_SIZE];
00074
00075
00076
00077
00083 void InitIntegerFX() {
00084 int i;
00085
00086 for (i = 0; i < ATAN_TABLE_SIZE; i++)
00087 AtanTable[i] =
00088 (UINT8) (atan ((i / (float) ATAN_TABLE_SIZE)) * 128.0 / PI + 0.5);
00089 }
00090
00091
00102 int ExtractIntFeat(TBLOB *Blob,
00103 INT_FEATURE_ARRAY BLFeat,
00104 INT_FEATURE_ARRAY CNFeat,
00105 INT_FX_RESULT Results) {
00106
00107 TESSLINE *OutLine;
00108 EDGEPT *Loop, *LoopStart, *Segment;
00109 INT16 LastX, LastY, Xmean, Ymean;
00110 INT32 NormX, NormY, DeltaX, DeltaY;
00111 INT32 Xsum, Ysum;
00112 UINT32 Ix, Iy, LengthSum;
00113 UINT16 n;
00114 UINT8 Theta;
00115 UINT16 NumBLFeatures, NumCNFeatures;
00116 UINT8 RxInv, RyInv;
00117 UINT8 RxExp, RyExp;
00118
00119 register INT32 pfX, pfY, dX, dY;
00120 UINT16 Length;
00121 register int i;
00122
00123 Results->Length = 0;
00124 Results->Xmean = 0;
00125 Results->Ymean = 0;
00126 Results->Rx = 0;
00127 Results->Ry = 0;
00128 Results->NumBL = 0;
00129 Results->NumCN = 0;
00130
00131
00132 NumBLFeatures = 0;
00133 NumCNFeatures = 0;
00134 OutLine = Blob->outlines;
00135 Xsum = 0;
00136 Ysum = 0;
00137 LengthSum = 0;
00138 while (OutLine != NULL) {
00139 LoopStart = OutLine->loop;
00140 Loop = LoopStart;
00141 LastX = Loop->pos.x;
00142 LastY = Loop->pos.y;
00143
00144 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
00145 return FALSE;
00146 do {
00147 Segment = Loop;
00148 Loop = Loop->next;
00149 NormX = Loop->pos.x;
00150 NormY = Loop->pos.y;
00151
00152 n = 1;
00153 if (!is_hidden_edge (Segment)) {
00154 DeltaX = NormX - LastX;
00155 DeltaY = NormY - LastY;
00156 Length = MySqrt (DeltaX, DeltaY);
00157 n = ((Length << 2) + Length + 32) >> 6;
00158 if (n != 0) {
00159 Xsum += ((LastX << 1) + DeltaX) * (int) Length;
00160 Ysum += ((LastY << 1) + DeltaY) * (int) Length;
00161 LengthSum += Length;
00162 }
00163 }
00164 if (n != 0) {
00165 LastX = NormX;
00166 LastY = NormY;
00167 }
00168 }
00169
00170 while (Loop != LoopStart);
00171 OutLine = OutLine->next;
00172 }
00173 if (LengthSum == 0)
00174 return FALSE;
00175 Xmean = (Xsum / (INT32) LengthSum) >> 1;
00176 Ymean = (Ysum / (INT32) LengthSum) >> 1;
00177
00178 Results->Length = LengthSum;
00179 Results->Xmean = Xmean;
00180 Results->Ymean = Ymean;
00181
00182
00183
00184 Ix = 0;
00185 Iy = 0;
00186 NumBLFeatures = 0;
00187 OutLine = Blob->outlines;
00188 while (OutLine != NULL) {
00189 LoopStart = OutLine->loop;
00190 Loop = LoopStart;
00191 LastX = Loop->pos.x - Xmean;
00192 LastY = Loop->pos.y;
00193
00194 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
00195 return FALSE;
00196 do {
00197 Segment = Loop;
00198 Loop = Loop->next;
00199 NormX = Loop->pos.x - Xmean;
00200 NormY = Loop->pos.y;
00201
00202 n = 1;
00203 if (!is_hidden_edge (Segment)) {
00204 DeltaX = NormX - LastX;
00205 DeltaY = NormY - LastY;
00206 Length = MySqrt (DeltaX, DeltaY);
00207 n = ((Length << 2) + Length + 32) >> 6;
00208 if (n != 0) {
00209 Theta = TableLookup (DeltaY, DeltaX);
00210 dX = (DeltaX << 8) / n;
00211 dY = (DeltaY << 8) / n;
00212 pfX = (LastX << 8) + (dX >> 1);
00213 pfY = (LastY << 8) + (dY >> 1);
00214 Ix += ((pfY >> 8) - Ymean) * ((pfY >> 8) - Ymean);
00215 Iy += (pfX >> 8) * (pfX >> 8);
00216 if (SaveFeature (BLFeat, NumBLFeatures, (INT16) (pfX >> 8),
00217 (INT16) ((pfY >> 8) - 128),
00218 Theta) == FALSE)
00219 return FALSE;
00220 NumBLFeatures++;
00221 for (i = 1; i < n; i++) {
00222 pfX += dX;
00223 pfY += dY;
00224 Ix += ((pfY >> 8) - Ymean) * ((pfY >> 8) - Ymean);
00225 Iy += (pfX >> 8) * (pfX >> 8);
00226 if (SaveFeature
00227 (BLFeat, NumBLFeatures, (INT16) (pfX >> 8),
00228 (INT16) ((pfY >> 8) - 128), Theta) == FALSE)
00229 return FALSE;
00230 NumBLFeatures++;
00231 }
00232 }
00233 }
00234 if (n != 0) {
00235 LastX = NormX;
00236 LastY = NormY;
00237 }
00238 }
00239 while (Loop != LoopStart);
00240 OutLine = OutLine->next;
00241 }
00242 if (Ix == 0)
00243 Ix = 1;
00244 if (Iy == 0)
00245 Iy = 1;
00246 RxInv = MySqrt2 (NumBLFeatures, Ix, &RxExp);
00247 RyInv = MySqrt2 (NumBLFeatures, Iy, &RyExp);
00248 ClipRadius(&RxInv, &RxExp, &RyInv, &RyExp);
00249
00250 Results->Rx = (INT16) (51.2 / (double) RxInv * pow (2.0, (double) RxExp));
00251 Results->Ry = (INT16) (51.2 / (double) RyInv * pow (2.0, (double) RyExp));
00252 Results->NumBL = NumBLFeatures;
00253
00254
00255 NumCNFeatures = 0;
00256 OutLine = Blob->outlines;
00257 while (OutLine != NULL) {
00258 LoopStart = OutLine->loop;
00259 Loop = LoopStart;
00260 LastX = (Loop->pos.x - Xmean) * RyInv;
00261 LastY = (Loop->pos.y - Ymean) * RxInv;
00262 LastX >>= (INT8) RyExp;
00263 LastY >>= (INT8) RxExp;
00264
00265 if ((Loop == NULL) || (Loop->next == NULL) || (Loop->next == LoopStart))
00266 return FALSE;
00267 do {
00268 Segment = Loop;
00269 Loop = Loop->next;
00270 NormX = (Loop->pos.x - Xmean) * RyInv;
00271 NormY = (Loop->pos.y - Ymean) * RxInv;
00272 NormX >>= (INT8) RyExp;
00273 NormY >>= (INT8) RxExp;
00274
00275 n = 1;
00276 if (!is_hidden_edge (Segment)) {
00277 DeltaX = NormX - LastX;
00278 DeltaY = NormY - LastY;
00279 Length = MySqrt (DeltaX, DeltaY);
00280 n = ((Length << 2) + Length + 32) >> 6;
00281 if (n != 0) {
00282 Theta = TableLookup (DeltaY, DeltaX);
00283 dX = (DeltaX << 8) / n;
00284 dY = (DeltaY << 8) / n;
00285 pfX = (LastX << 8) + (dX >> 1);
00286 pfY = (LastY << 8) + (dY >> 1);
00287 if (SaveFeature (CNFeat, NumCNFeatures, (INT16) (pfX >> 8),
00288 (INT16) ((pfY >> 8)), Theta) == FALSE)
00289 return FALSE;
00290 NumCNFeatures++;
00291 for (i = 1; i < n; i++) {
00292 pfX += dX;
00293 pfY += dY;
00294 if (SaveFeature
00295 (CNFeat, NumCNFeatures, (INT16) (pfX >> 8),
00296 (INT16) ((pfY >> 8)), Theta) == FALSE)
00297 return FALSE;
00298 NumCNFeatures++;
00299 }
00300 }
00301 }
00302 if (n != 0) {
00303 LastX = NormX;
00304 LastY = NormY;
00305 }
00306 }
00307 while (Loop != LoopStart);
00308 OutLine = OutLine->next;
00309 }
00310
00311 Results->NumCN = NumCNFeatures;
00312 return TRUE;
00313 }
00314
00315
00324 UINT8 TableLookup(INT32 Y, INT32 X) {
00325 INT16 Angle;
00326 UINT16 Ratio;
00327 UINT32 AbsX, AbsY;
00328
00329 assert ((X != 0) || (Y != 0));
00330 if (X < 0)
00331 AbsX = -X;
00332 else
00333 AbsX = X;
00334 if (Y < 0)
00335 AbsY = -Y;
00336 else
00337 AbsY = Y;
00338 if (AbsX > AbsY)
00339 Ratio = AbsY * ATAN_TABLE_SIZE / AbsX;
00340 else
00341 Ratio = AbsX * ATAN_TABLE_SIZE / AbsY;
00342 if (Ratio >= ATAN_TABLE_SIZE)
00343 Ratio = ATAN_TABLE_SIZE - 1;
00344 Angle = AtanTable[Ratio];
00345 if (X >= 0)
00346 if (Y >= 0)
00347 if (AbsX > AbsY)
00348 Angle = Angle;
00349 else
00350 Angle = 64 - Angle;
00351 else if (AbsX > AbsY)
00352 Angle = 256 - Angle;
00353 else
00354 Angle = 192 + Angle;
00355 else if (Y >= 0)
00356 if (AbsX > AbsY)
00357 Angle = 128 - Angle;
00358 else
00359 Angle = 64 + Angle;
00360 else if (AbsX > AbsY)
00361 Angle = 128 + Angle;
00362 else
00363 Angle = 192 - Angle;
00364
00365
00366 Angle += 128;
00367 Angle &= 255;
00368 return (UINT8) Angle;
00369 }
00370
00371
00383 int SaveFeature(INT_FEATURE_ARRAY FeatureArray,
00384 UINT16 FeatureNum,
00385 INT16 X,
00386 INT16 Y,
00387 UINT8 Theta) {
00388 INT_FEATURE Feature;
00389
00390 if (FeatureNum >= MAX_NUM_INT_FEATURES)
00391 return FALSE;
00392
00393 Feature = &(FeatureArray[FeatureNum]);
00394
00395 X = X + 128;
00396 Y = Y + 128;
00397
00398 if (X > 255)
00399 Feature->X = 255;
00400 else if (X < 0)
00401 Feature->X = 0;
00402 else
00403 Feature->X = X;
00404
00405 if (Y > 255)
00406 Feature->Y = 255;
00407 else if (Y < 0)
00408 Feature->Y = 0;
00409 else
00410 Feature->Y = Y;
00411
00412 Feature->Theta = Theta;
00413
00414 return TRUE;
00415 }
00416
00417
00426 UINT16 MySqrt(INT32 X, INT32 Y) {
00427 register UINT16 SqRoot;
00428 register UINT32 Square;
00429 register UINT16 BitLocation;
00430 register UINT32 Sum;
00431
00432 if (X < 0)
00433 X = -X;
00434 if (Y < 0)
00435 Y = -Y;
00436
00437 if (X > EvidenceMultMask)
00438 X = EvidenceMultMask;
00439 if (Y > EvidenceMultMask)
00440 Y = EvidenceMultMask;
00441
00442 Sum = X * X + Y * Y;
00443
00444 BitLocation = 1024;
00445 SqRoot = 0;
00446 do {
00447 Square = (SqRoot | BitLocation) * (SqRoot | BitLocation);
00448 if (Square <= Sum)
00449 SqRoot |= BitLocation;
00450 BitLocation >>= 1;
00451 }
00452 while (BitLocation);
00453
00454 return SqRoot;
00455 }
00456
00457
00466 UINT8 MySqrt2(UINT16 N, UINT32 I, UINT8 *Exp) {
00467 register INT8 k;
00468 register UINT32 N2;
00469 register UINT8 SqRoot;
00470 register UINT16 Square;
00471 register UINT8 BitLocation;
00472 register UINT16 Ratio;
00473
00474 N2 = N * 41943;
00475
00476 k = 9;
00477 while ((N2 & 0xc0000000) == 0) {
00478 N2 <<= 2;
00479 k += 1;
00480 }
00481
00482 while ((I & 0xc0000000) == 0) {
00483 I <<= 2;
00484 k -= 1;
00485 }
00486
00487 if (((N2 & 0x80000000) == 0) && ((I & 0x80000000) == 0)) {
00488 N2 <<= 1;
00489 I <<= 1;
00490 }
00491
00492 N2 &= 0xffff0000;
00493 I >>= 14;
00494 Ratio = N2 / I;
00495
00496 BitLocation = 128;
00497 SqRoot = 0;
00498 do {
00499 Square = (SqRoot | BitLocation) * (SqRoot | BitLocation);
00500 if (Square <= Ratio)
00501 SqRoot |= BitLocation;
00502 BitLocation >>= 1;
00503 }
00504 while (BitLocation);
00505
00506 if (k < 0) {
00507 *Exp = 0;
00508 return 255;
00509 }
00510 else {
00511 *Exp = k;
00512 return SqRoot;
00513 }
00514 }
00515
00516
00527 void ClipRadius(UINT8 *RxInv, UINT8 *RxExp, UINT8 *RyInv, UINT8 *RyExp) {
00528 register UINT8 AM, BM, AE, BE;
00529 register UINT8 BitN, LastCarry;
00530 int RxInvLarge, RyInvSmall;
00531
00533 AM = RadiusGyrMinMan;
00535 AE = RadiusGyrMinExp;
00536 BM = *RxInv;
00537 BE = *RxExp;
00538 LastCarry = 1;
00539 while ((AM != 0) || (BM != 0)) {
00540 if (AE > BE) {
00541 BitN = LastCarry + (AM & 1) + 1;
00542 AM >>= 1;
00543 AE--;
00544 }
00545 else if (AE < BE) {
00546 BitN = LastCarry + (!(BM & 1));
00547 BM >>= 1;
00548 BE--;
00549 }
00550 else {
00551 BitN = LastCarry + (AM & 1) + (!(BM & 1));
00552 AM >>= 1;
00553 BM >>= 1;
00554 AE--;
00555 BE--;
00556 }
00557 LastCarry = (BitN & 2) > 1;
00558 BitN = BitN & 1;
00559 }
00560 BitN = LastCarry + 1;
00561 LastCarry = (BitN & 2) > 1;
00562 BitN = BitN & 1;
00563
00564 if (BitN == 1) {
00565 *RxInv = RadiusGyrMinMan;
00566 *RxExp = RadiusGyrMinExp;
00567 }
00568
00569 AM = RadiusGyrMinMan;
00570 AE = RadiusGyrMinExp;
00571 BM = *RyInv;
00572 BE = *RyExp;
00573 LastCarry = 1;
00574 while ((AM != 0) || (BM != 0)) {
00575 if (AE > BE) {
00576 BitN = LastCarry + (AM & 1) + 1;
00577 AM >>= 1;
00578 AE--;
00579 }
00580 else if (AE < BE) {
00581 BitN = LastCarry + (!(BM & 1));
00582 BM >>= 1;
00583 BE--;
00584 }
00585 else {
00586 BitN = LastCarry + (AM & 1) + (!(BM & 1));
00587 AM >>= 1;
00588 BM >>= 1;
00589 AE--;
00590 BE--;
00591 }
00592 LastCarry = (BitN & 2) > 1;
00593 BitN = BitN & 1;
00594 }
00595 BitN = LastCarry + 1;
00596 LastCarry = (BitN & 2) > 1;
00597 BitN = BitN & 1;
00598
00599 if (BitN == 1) {
00600 *RyInv = RadiusGyrMinMan;
00601 *RyExp = RadiusGyrMinExp;
00602 }
00603
00604 AM = RadiusGyrMaxMan;
00605 AE = RadiusGyrMaxExp;
00606 BM = *RxInv;
00607 BE = *RxExp;
00608 LastCarry = 1;
00609 while ((AM != 0) || (BM != 0)) {
00610 if (AE > BE) {
00611 BitN = LastCarry + (AM & 1) + 1;
00612 AM >>= 1;
00613 AE--;
00614 }
00615 else if (AE < BE) {
00616 BitN = LastCarry + (!(BM & 1));
00617 BM >>= 1;
00618 BE--;
00619 }
00620 else {
00621 BitN = LastCarry + (AM & 1) + (!(BM & 1));
00622 AM >>= 1;
00623 BM >>= 1;
00624 AE--;
00625 BE--;
00626 }
00627 LastCarry = (BitN & 2) > 1;
00628 BitN = BitN & 1;
00629 }
00630 BitN = LastCarry + 1;
00631 LastCarry = (BitN & 2) > 1;
00632 BitN = BitN & 1;
00633
00634 if (BitN == 1)
00635 RxInvLarge = 1;
00636 else
00637 RxInvLarge = 0;
00638
00639 AM = *RyInv;
00640 AE = *RyExp;
00641 BM = RadiusGyrMaxMan;
00642 BE = RadiusGyrMaxExp;
00643 LastCarry = 1;
00644 while ((AM != 0) || (BM != 0)) {
00645 if (AE > BE) {
00646 BitN = LastCarry + (AM & 1) + 1;
00647 AM >>= 1;
00648 AE--;
00649 }
00650 else if (AE < BE) {
00651 BitN = LastCarry + (!(BM & 1));
00652 BM >>= 1;
00653 BE--;
00654 }
00655 else {
00656 BitN = LastCarry + (AM & 1) + (!(BM & 1));
00657 AM >>= 1;
00658 BM >>= 1;
00659 AE--;
00660 BE--;
00661 }
00662 LastCarry = (BitN & 2) > 1;
00663 BitN = BitN & 1;
00664 }
00665 BitN = LastCarry + 1;
00666 LastCarry = (BitN & 2) > 1;
00667 BitN = BitN & 1;
00668
00669 if (BitN == 1)
00670 RyInvSmall = 1;
00671 else
00672 RyInvSmall = 0;
00673
00674 if (RxInvLarge && RyInvSmall) {
00675 *RyInv = RadiusGyrMaxMan;
00676 *RyExp = RadiusGyrMaxExp;
00677 }
00678
00679 }