00001
00020
00021
00022
00023 #include "clusttool.h"
00024 #include "emalloc.h"
00025 #include "mfoutline.h"
00026 #include "debug.h"
00027 #include "hideedge.h"
00028 #include "blobs.h"
00029 #include "const.h"
00030 #include "mfx.h"
00031
00032 #include <math.h>
00033 #include <stdio.h>
00034
00035 #define MIN_INERTIA (0.00001)
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00088 static TPOINT BlobCenter;
00089
00090
00117
00118 make_int_var (NormMethod, character, MakeNormMethod,
00119 15, 10, SetNormMethod, "Normalization Method ...")
00120
00121 make_float_var (CharNormRange, 0.2, MakeCharNormRange,
00122 15, 11, SetCharNormRange, "Character Normalization Range ...")
00123 make_float_var (MinNormScaleX, 0.0, MakeMinNormScaleX,
00124 15, 12, SetMinNormScaleX, "Min char x-norm scale ...")
00125
00126 make_float_var (MaxNormScaleX, 0.325, MakeMaxNormScaleX,
00127 15, 13, SetMaxNormScaleX, "Max char x-norm scale ...")
00128
00129 make_float_var (MinNormScaleY, 0.0, MakeMinNormScaleY,
00130 15, 14, SetMinNormScaleY, "Min char y-norm scale ...")
00131
00132 make_float_var (MaxNormScaleY, 0.325, MakeMaxNormScaleY,
00133 15, 15, SetMaxNormScaleY, "Max char y-norm scale ...")
00134
00137
00138
00139
00154 void ComputeBlobCenter(TBLOB *Blob, TPOINT *BlobCenter) {
00155 TPOINT TopLeft;
00156 TPOINT BottomRight;
00157
00158 blob_bounding_box(Blob, &TopLeft, &BottomRight);
00159
00160 BlobCenter->x = ((TopLeft.x << VECSCALE) + (BottomRight.x << VECSCALE)) / 2;
00161 BlobCenter->y = ((TopLeft.y << VECSCALE) + (BottomRight.y << VECSCALE)) / 2;
00162
00163 }
00164
00165
00166
00175 LIST ConvertBlob(TBLOB *Blob) {
00176 LIST ConvertedOutlines = NIL;
00177
00178 if (Blob != NULL) {
00179 SettupBlobConversion(Blob);
00180 ConvertedOutlines = ConvertOutlines (Blob->outlines,
00181 ConvertedOutlines, outer);
00182 }
00183
00184 return (ConvertedOutlines);
00185 }
00186
00187
00188
00213 MFOUTLINE ConvertOutline(TESSLINE *Outline) {
00214 register BYTEVEC *Vector;
00215 TPOINT Position;
00216 TPOINT StartPosition;
00217 MFEDGEPT *NewPoint;
00218 MFOUTLINE MFOutline = NIL;
00219 EDGEPT *EdgePoint;
00220 EDGEPT *StartPoint;
00221 EDGEPT *NextPoint;
00222
00223 if (Outline == NULL ||
00224 (Outline->compactloop == NULL && Outline->loop == NULL))
00225 return (MFOutline);
00226
00227 if (is_baseline_normalized ()) {
00228 StartPoint = Outline->loop;
00229 EdgePoint = StartPoint;
00230 do {
00231 NextPoint = EdgePoint->next;
00232
00233
00234 if (EdgePoint->pos.x != NextPoint->pos.x ||
00235 EdgePoint->pos.y != NextPoint->pos.y) {
00236 NewPoint = NewEdgePoint ();
00237 ClearMark(NewPoint);
00238 IsHidden (NewPoint) = is_hidden_edge (EdgePoint) ? TRUE : FALSE;
00239 XPositionOf (NewPoint) = EdgePoint->pos.x;
00240 YPositionOf (NewPoint) = EdgePoint->pos.y;
00241 MFOutline = push (MFOutline, NewPoint);
00242 }
00243 EdgePoint = NextPoint;
00244 }
00245 while (EdgePoint != StartPoint);
00246 }
00247
00248 else if (Outline->loop == NULL) {
00249 Xof (Position) = Xof (StartPosition) = Outline->start.x;
00250 Yof (Position) = Yof (StartPosition) = Outline->start.y;
00251 Vector = Outline->compactloop;
00252 do {
00253 if (Vector->dx != 0 || Vector->dy != 0) {
00254 NewPoint = NewEdgePoint ();
00255 ClearMark(NewPoint);
00256
00257 IsHidden (NewPoint) = FALSE;
00258 CopyPoint (Position, PositionOf (NewPoint));
00259 MFOutline = push (MFOutline, NewPoint);
00260 }
00261 Xof (Position) += Vector->dx;
00262 Yof (Position) += Vector->dy;
00263 Vector++;
00264 }
00265 while ((Xof (Position) != Xof (StartPosition)) ||
00266 (Yof (Position) != Yof (StartPosition)));
00267 }
00268 else {
00269 StartPoint = Outline->loop;
00270 EdgePoint = StartPoint;
00271 do {
00272 NextPoint = EdgePoint->next;
00273
00274
00275 if (EdgePoint->pos.x != NextPoint->pos.x ||
00276 EdgePoint->pos.y != NextPoint->pos.y) {
00277 NewPoint = NewEdgePoint ();
00278 ClearMark(NewPoint);
00279 IsHidden (NewPoint) = is_hidden_edge (EdgePoint) ? TRUE : FALSE;
00280 XPositionOf (NewPoint) =
00281 (EdgePoint->pos.x + BlobCenter.x) / REALSCALE;
00282 YPositionOf (NewPoint) =
00283 (EdgePoint->pos.y + BlobCenter.y) / REALSCALE;
00284 MFOutline = push (MFOutline, NewPoint);
00285 }
00286 EdgePoint = NextPoint;
00287 }
00288 while (EdgePoint != StartPoint);
00289 }
00290
00291 MakeOutlineCircular(MFOutline);
00292 return (MFOutline);
00293
00294 }
00295
00296
00297
00314 LIST ConvertOutlines(TESSLINE *Outline,
00315 LIST ConvertedOutlines,
00316 OUTLINETYPE OutlineType) {
00317 MFOUTLINE MFOutline;
00318
00319 while (Outline != NULL) {
00320 if (Outline->child != NULL)
00321 if (OutlineType == outer)
00322 ConvertedOutlines = ConvertOutlines (Outline->child,
00323 ConvertedOutlines, hole);
00324 else
00325 ConvertedOutlines = ConvertOutlines (Outline->child,
00326 ConvertedOutlines, outer);
00327
00328 MFOutline = ConvertOutline (Outline);
00329 ConvertedOutlines = push (ConvertedOutlines, MFOutline);
00330 Outline = Outline->next;
00331 }
00332 return (ConvertedOutlines);
00333 }
00334
00335
00336
00357 void ComputeOutlineStats(LIST Outlines, OUTLINE_STATS *OutlineStats) {
00358 MFOUTLINE Outline;
00359 MFOUTLINE EdgePoint;
00360 MFEDGEPT *Current;
00361 MFEDGEPT *Last;
00362
00363 InitOutlineStats(OutlineStats);
00364 iterate(Outlines) {
00365 Outline = (MFOUTLINE) first (Outlines);
00366
00367 Last = PointAt (Outline);
00368 Outline = NextPointAfter (Outline);
00369 EdgePoint = Outline;
00370 do {
00371 Current = PointAt (EdgePoint);
00372
00373 UpdateOutlineStats (OutlineStats,
00374 XPositionOf (Last), YPositionOf (Last),
00375 XPositionOf (Current), YPositionOf (Current));
00376
00377 Last = Current;
00378 EdgePoint = NextPointAfter (EdgePoint);
00379 }
00380 while (EdgePoint != Outline);
00381 }
00382 FinishOutlineStats(OutlineStats);
00383
00384 }
00385
00386
00387
00400 void FilterEdgeNoise(MFOUTLINE Outline, FLOAT32 NoiseSegmentLength) {
00401 MFOUTLINE Current;
00402 MFOUTLINE Last;
00403 MFOUTLINE First;
00404 FLOAT32 Length;
00405 int NumFound = 0;
00406 DIRECTION DirectionOfFirst = north;
00407
00408 if (DegenerateOutline (Outline))
00409 return;
00410
00411
00412
00413 First = NextDirectionChange (Outline);
00414 Last = First;
00415 do {
00416 Current = NextDirectionChange (Last);
00417 Length = DistanceBetween (PositionOf (PointAt (Current)),
00418 PositionOf (PointAt (Last)));
00419 if (Length >= NoiseSegmentLength) {
00420 if (NumFound == 0) {
00421 NumFound = 1;
00422 DirectionOfFirst = DirectionOf (PointAt (Last));
00423 }
00424 else if (DirectionOfFirst != DirectionOf (PointAt (Last)))
00425 break;
00426 }
00427 Last = Current;
00428 }
00429 while (Last != First);
00430 if (Current == Last)
00431 return;
00432
00433
00434
00435
00436 First = Last;
00437 do {
00438 Current = NextDirectionChange (Last);
00439 Length = DistanceBetween (PositionOf (PointAt (Current)),
00440 PositionOf (PointAt (Last)));
00441 if (Length < NoiseSegmentLength)
00442 ChangeDirection (Last, Current, PreviousDirectionOf (PointAt (Last)));
00443
00444 Last = Current;
00445 }
00446 while (Last != First);
00447
00448 }
00449
00450
00451
00474 void FindDirectionChanges(MFOUTLINE Outline,
00475 FLOAT32 MinSlope,
00476 FLOAT32 MaxSlope) {
00477 MFEDGEPT *Current;
00478 MFEDGEPT *Last;
00479 MFOUTLINE EdgePoint;
00480
00481 if (DegenerateOutline (Outline))
00482 return;
00483
00484 Last = PointAt (Outline);
00485 Outline = NextPointAfter (Outline);
00486 EdgePoint = Outline;
00487 do {
00488 Current = PointAt (EdgePoint);
00489 ComputeDirection(Last, Current, MinSlope, MaxSlope);
00490
00491 Last = Current;
00492 EdgePoint = NextPointAfter (EdgePoint);
00493 }
00494 while (EdgePoint != Outline);
00495
00496 }
00497
00498
00499
00508 void FreeMFOutline(void *arg) {
00509 MFOUTLINE Start;
00510 MFOUTLINE Outline = (MFOUTLINE) arg;
00511
00512
00513 Start = rest (Outline);
00514 set_rest(Outline, NIL);
00515 while (Start != NULL) {
00516 c_free_struct (first (Start), sizeof (MFEDGEPT), "MFEDGEPT");
00517 Start = pop (Start);
00518 }
00519
00520 }
00521
00522
00523
00532 void FreeOutlines(LIST Outlines) {
00533 destroy_nodes(Outlines, FreeMFOutline);
00534 }
00535
00536
00537
00546 void InitMFOutlineVars() {
00547 MakeNormMethod();
00548 MakeCharNormRange();
00549 MakeMinNormScaleX();
00550 MakeMaxNormScaleX();
00551 MakeMinNormScaleY();
00552 MakeMaxNormScaleY();
00553 }
00554
00555
00556
00572 void MarkDirectionChanges(MFOUTLINE Outline) {
00573 MFOUTLINE Current;
00574 MFOUTLINE Last;
00575 MFOUTLINE First;
00576
00577 if (DegenerateOutline (Outline))
00578 return;
00579
00580 First = NextDirectionChange (Outline);
00581 Last = First;
00582 do {
00583 Current = NextDirectionChange (Last);
00584 MarkPoint (PointAt (Current));
00585 Last = Current;
00586 }
00587 while (Last != First);
00588
00589 }
00590
00591
00592
00601 MFEDGEPT *NewEdgePoint() {
00602 return ((MFEDGEPT *) c_alloc_struct (sizeof (MFEDGEPT), "MFEDGEPT"));
00603
00604 }
00605
00606
00607
00620 MFOUTLINE NextExtremity(MFOUTLINE EdgePoint) {
00621 EdgePoint = NextPointAfter (EdgePoint);
00622 while (NotExtremity (PointAt (EdgePoint)))
00623 EdgePoint = NextPointAfter (EdgePoint);
00624
00625 return (EdgePoint);
00626
00627 }
00628
00629
00630
00652 void NormalizeOutline(MFOUTLINE Outline,
00653 LINE_STATS *LineStats,
00654 FLOAT32 XOrigin) {
00655 MFEDGEPT *Current;
00656 MFOUTLINE EdgePoint;
00657 FLOAT32 ScaleFactor;
00658 FLOAT32 AscStretch;
00659 FLOAT32 DescStretch;
00660
00661 if (Outline != NIL) {
00662 ScaleFactor = ComputeScaleFactor (LineStats);
00663 AscStretch = 1.0;
00664 DescStretch = 1.0;
00665
00666 EdgePoint = Outline;
00667 do {
00668 Current = PointAt (EdgePoint);
00669
00670 YPositionOf (Current) = ScaleFactor *
00671 (YPositionOf (Current) -
00672 BaselineAt (LineStats, XPositionOf (Current)));
00673
00674 if (YPositionOf (Current) > NORMAL_X_HEIGHT)
00675 YPositionOf (Current) = NORMAL_X_HEIGHT +
00676 (YPositionOf (Current) - NORMAL_X_HEIGHT) / AscStretch;
00677
00678 else if (YPositionOf (Current) < NORMAL_BASELINE)
00679 YPositionOf (Current) = NORMAL_BASELINE +
00680 (YPositionOf (Current) - NORMAL_BASELINE) / DescStretch;
00681
00682 XPositionOf (Current) = ScaleFactor *
00683 (XPositionOf (Current) - XOrigin);
00684
00685 EdgePoint = NextPointAfter (EdgePoint);
00686 }
00687 while (EdgePoint != Outline);
00688 }
00689 }
00690
00691
00692
00716 void NormalizeOutlines(LIST Outlines,
00717 LINE_STATS *LineStats,
00718 FLOAT32 *XScale,
00719 FLOAT32 *YScale) {
00720 MFOUTLINE Outline;
00721 OUTLINE_STATS OutlineStats;
00722 FLOAT32 BaselineScale;
00723
00724 switch (NormMethod) {
00725 case character:
00726 ComputeOutlineStats(Outlines, &OutlineStats);
00727
00728 *XScale = *YScale = BaselineScale = ComputeScaleFactor (LineStats);
00729 *XScale *= OutlineStats.Ry;
00730 *YScale *= OutlineStats.Rx;
00731 if (*XScale < MinNormScaleX)
00732 *XScale = MinNormScaleX;
00733 if (*YScale < MinNormScaleY)
00734 *YScale = MinNormScaleY;
00735 if (*XScale > MaxNormScaleX && *YScale <= MaxNormScaleY)
00736 *XScale = MaxNormScaleX;
00737 *XScale = CharNormRange * BaselineScale / *XScale;
00738 *YScale = CharNormRange * BaselineScale / *YScale;
00739
00740 iterate(Outlines) {
00741 Outline = (MFOUTLINE) first (Outlines);
00742 CharNormalizeOutline (Outline,
00743 OutlineStats.x, OutlineStats.y,
00744 *XScale, *YScale);
00745 }
00746 break;
00747
00748 case baseline:
00749 iterate(Outlines) {
00750 Outline = (MFOUTLINE) first (Outlines);
00751 NormalizeOutline (Outline, LineStats, 0.0);
00752 }
00753 *XScale = *YScale = ComputeScaleFactor (LineStats);
00754 break;
00755 }
00756 }
00757
00758
00759
00773 void SettupBlobConversion(TBLOB *Blob) {
00774 ComputeBlobCenter(Blob, &BlobCenter);
00775
00776 }
00777
00778
00779
00796 void SmearExtremities(MFOUTLINE Outline, FLOAT32 XScale, FLOAT32 YScale) {
00797 MFEDGEPT *Current;
00798 MFOUTLINE EdgePoint;
00799 FLOAT32 MinXSmear;
00800 FLOAT32 MaxXSmear;
00801 FLOAT32 MinYSmear;
00802 FLOAT32 MaxYSmear;
00803
00804 if (Outline != NIL) {
00805 MinXSmear = -0.5 * XScale;
00806 MaxXSmear = 0.5 * XScale;
00807 MinYSmear = -0.5 * YScale;
00808 MaxYSmear = 0.5 * YScale;
00809 EdgePoint = Outline;
00810 do {
00811 Current = PointAt (EdgePoint);
00812 if (IsExtremity (Current)) {
00813 XPositionOf (Current) +=
00814 UniformRandomNumber(MinXSmear, MaxXSmear);
00815 YPositionOf (Current) +=
00816 UniformRandomNumber(MinYSmear, MaxYSmear);
00817 }
00818
00819 EdgePoint = NextPointAfter (EdgePoint);
00820 }
00821 while (EdgePoint != Outline);
00822 }
00823 }
00824
00825
00826
00827
00828
00844 void ChangeDirection(MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction) {
00845 MFOUTLINE Current;
00846
00847 for (Current = Start; Current != End; Current = NextPointAfter (Current))
00848 DirectionOf (PointAt (Current)) = Direction;
00849
00850 PreviousDirectionOf (PointAt (End)) = Direction;
00851
00852 }
00853
00854
00855
00870 void CharNormalizeOutline(MFOUTLINE Outline,
00871 FLOAT32 XCenter,
00872 FLOAT32 YCenter,
00873 FLOAT32 XScale,
00874 FLOAT32 YScale) {
00875 MFOUTLINE First, Current;
00876 MFEDGEPT *CurrentPoint;
00877
00878 if (Outline == NIL)
00879 return;
00880
00881 First = Outline;
00882 Current = First;
00883 do {
00884 CurrentPoint = PointAt (Current);
00885 XPositionOf (CurrentPoint) =
00886 (XPositionOf (CurrentPoint) - XCenter) * XScale;
00887 YPositionOf (CurrentPoint) =
00888 (YPositionOf (CurrentPoint) - YCenter) * YScale;
00889
00890 Current = NextPointAfter (Current);
00891 }
00892 while (Current != First);
00893
00894 }
00895
00896
00897
00920 void ComputeDirection(MFEDGEPT *Start,
00921 MFEDGEPT *Finish,
00922 FLOAT32 MinSlope,
00923 FLOAT32 MaxSlope) {
00924 FVECTOR Delta;
00925
00926 Delta.x = Finish->Point.x - Start->Point.x;
00927 Delta.y = Finish->Point.y - Start->Point.y;
00928 if (Delta.x == 0)
00929 if (Delta.y < 0) {
00930 Start->Slope = -MAX_FLOAT32;
00931 Start->Direction = south;
00932 }
00933 else {
00934 Start->Slope = MAX_FLOAT32;
00935 Start->Direction = north;
00936 }
00937 else {
00938 Start->Slope = Delta.y / Delta.x;
00939 if (Delta.x > 0)
00940 if (Delta.y > 0)
00941 if (Start->Slope > MinSlope)
00942 if (Start->Slope < MaxSlope)
00943 Start->Direction = northeast;
00944 else
00945 Start->Direction = north;
00946 else
00947 Start->Direction = east;
00948 else if (Start->Slope < -MinSlope)
00949 if (Start->Slope > -MaxSlope)
00950 Start->Direction = southeast;
00951 else
00952 Start->Direction = south;
00953 else
00954 Start->Direction = east;
00955 else if (Delta.y > 0)
00956 if (Start->Slope < -MinSlope)
00957 if (Start->Slope > -MaxSlope)
00958 Start->Direction = northwest;
00959 else
00960 Start->Direction = north;
00961 else
00962 Start->Direction = west;
00963 else if (Start->Slope > MinSlope)
00964 if (Start->Slope < MaxSlope)
00965 Start->Direction = southwest;
00966 else
00967 Start->Direction = south;
00968 else
00969 Start->Direction = west;
00970 }
00971 Finish->PreviousDirection = Start->Direction;
00972 }
00973
00974
00975
00987 void FinishOutlineStats(register OUTLINE_STATS *OutlineStats) {
00988 OutlineStats->x = 0.5 * OutlineStats->My / OutlineStats->L;
00989 OutlineStats->y = 0.5 * OutlineStats->Mx / OutlineStats->L;
00990
00991 OutlineStats->Ix = (OutlineStats->Ix / 3.0 -
00992 OutlineStats->y * OutlineStats->Mx +
00993 OutlineStats->y * OutlineStats->y * OutlineStats->L);
00994
00995 OutlineStats->Iy = (OutlineStats->Iy / 3.0 -
00996 OutlineStats->x * OutlineStats->My +
00997 OutlineStats->x * OutlineStats->x * OutlineStats->L);
00998
00999
01000 if (OutlineStats->Ix < 0.0)
01001 OutlineStats->Ix = MIN_INERTIA;
01002 if (OutlineStats->Iy < 0.0)
01003 OutlineStats->Iy = MIN_INERTIA;
01004
01005 OutlineStats->Rx = sqrt (OutlineStats->Ix / OutlineStats->L);
01006 OutlineStats->Ry = sqrt (OutlineStats->Iy / OutlineStats->L);
01007
01008 OutlineStats->Mx *= 0.5;
01009 OutlineStats->My *= 0.5;
01010
01011 }
01012
01013
01014
01024 void InitOutlineStats(OUTLINE_STATS *OutlineStats) {
01025 OutlineStats->Mx = 0.0;
01026 OutlineStats->My = 0.0;
01027 OutlineStats->L = 0.0;
01028 OutlineStats->x = 0.0;
01029 OutlineStats->y = 0.0;
01030 OutlineStats->Ix = 0.0;
01031 OutlineStats->Iy = 0.0;
01032 OutlineStats->Rx = 0.0;
01033 OutlineStats->Ry = 0.0;
01034 }
01035
01036
01037
01050 MFOUTLINE NextDirectionChange(MFOUTLINE EdgePoint) {
01051 DIRECTION InitialDirection;
01052
01053 InitialDirection = DirectionOf (PointAt (EdgePoint));
01054
01055 do
01056 EdgePoint = NextPointAfter (EdgePoint);
01057 while (DirectionOf (PointAt (EdgePoint)) == InitialDirection);
01058
01059 return (EdgePoint);
01060 }
01061
01062
01063
01088 void UpdateOutlineStats(register OUTLINE_STATS *OutlineStats,
01089 register FLOAT32 x1,
01090 register FLOAT32 x2,
01091 register FLOAT32 y1,
01092 register FLOAT32 y2) {
01093 register FLOAT64 L;
01094 register FLOAT64 Mx2;
01095 register FLOAT64 My2;
01096
01097
01098 L = sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
01099 OutlineStats->L += L;
01100
01101
01102 Mx2 = L * (y1 + y2);
01103 My2 = L * (x1 + x2);
01104 OutlineStats->Mx += Mx2;
01105 OutlineStats->My += My2;
01106
01107
01108 OutlineStats->Ix += Mx2 * (y1 + y2) - L * y1 * y2;
01109 OutlineStats->Iy += My2 * (x1 + x2) - L * x1 * x2;
01110
01111 }