1 /******************************************************************************
2 ** Filename: mfoutline.c
3 ** Purpose: Interface to outline struct used for extracting features
4 ** Author: Dan Johnson
5 ** History: Thu May 17 08:14:18 1990, DSJ, 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 "clusttool.h" //If remove you get cought in a loop somewhere
22 #include "emalloc.h"
23 #include "mfoutline.h"
24 #include "hideedge.h"
25 #include "blobs.h"
26 #include "const.h"
27 #include "mfx.h"
28 #include "varable.h"
29
30 #include <math.h>
31 #include <stdio.h>
32
33 #define MIN_INERTIA (0.00001)
34
35 /**----------------------------------------------------------------------------
36 Global Data Definitions and Declarations
37 ----------------------------------------------------------------------------**/
38 /* center of current blob being processed - used when "unexpanding"
39 expanded blobs */
40 static TPOINT BlobCenter;
41
42 /**----------------------------------------------------------------------------
43 Variables
44 ----------------------------------------------------------------------------**/
45
46 /* control knobs used to control normalization of outlines */
47 INT_VAR(classify_norm_method, character, "Normalization Method ...");
48 /* PREV DEFAULT "baseline" */
49 double_VAR(classify_char_norm_range, 0.2, "Character Normalization Range ...");
50 double_VAR(classify_min_norm_scale_x, 0.0, "Min char x-norm scale ...");
51 /* PREV DEFAULT 0.1 */
52 double_VAR(classify_max_norm_scale_x, 0.325, "Max char x-norm scale ...");
53 /* PREV DEFAULT 0.3 */
54 double_VAR(classify_min_norm_scale_y, 0.0, "Min char y-norm scale ...");
55 /* PREV DEFAULT 0.1 */
56 double_VAR(classify_max_norm_scale_y, 0.325, "Max char y-norm scale ...");
57 /* PREV DEFAULT 0.3 */
58 /**----------------------------------------------------------------------------
59 Public Code
60 ----------------------------------------------------------------------------**/
61 /*---------------------------------------------------------------------------*/
ComputeBlobCenter(TBLOB * Blob,TPOINT * BlobCenter)62 void ComputeBlobCenter(TBLOB *Blob, TPOINT *BlobCenter) {
63 /*
64 ** Parameters:
65 ** Blob blob to compute centerpoint of
66 ** BlobCenter data struct to place results in
67 ** Globals: none
68 ** Operation:
69 ** This routine computes the center point of the specified
70 ** blob using the bounding box of all top level outlines in the
71 ** blob. The center point is computed in a coordinate system
72 ** which is scaled up by VECSCALE from the page coordinate
73 ** system.
74 ** Return: none
75 ** Exceptions: none
76 ** History: Fri Sep 8 10:45:39 1989, DSJ, Created.
77 */
78 TPOINT TopLeft;
79 TPOINT BottomRight;
80
81 blob_bounding_box(Blob, &TopLeft, &BottomRight);
82
83 BlobCenter->x = ((TopLeft.x << VECSCALE) + (BottomRight.x << VECSCALE)) / 2;
84 BlobCenter->y = ((TopLeft.y << VECSCALE) + (BottomRight.y << VECSCALE)) / 2;
85
86 } /* ComputeBlobCenter */
87
88
89 /*---------------------------------------------------------------------------*/
ConvertBlob(TBLOB * Blob)90 LIST ConvertBlob(TBLOB *Blob) {
91 /*
92 ** Parameters:
93 ** Blob blob to be converted
94 ** Globals: none
95 ** Operation: Convert Blob into a list of outlines.
96 ** Return: List of outlines representing blob.
97 ** Exceptions: none
98 ** History: Thu Dec 13 15:40:17 1990, DSJ, Created.
99 */
100 LIST ConvertedOutlines = NIL;
101
102 if (Blob != NULL) {
103 SettupBlobConversion(Blob); //ComputeBlobCenter (Blob, &BlobCenter);
104 ConvertedOutlines = ConvertOutlines (Blob->outlines,
105 ConvertedOutlines, outer);
106 }
107
108 return (ConvertedOutlines);
109 } /* ConvertBlob */
110
111
112 /*---------------------------------------------------------------------------*/
ConvertOutline(TESSLINE * Outline)113 MFOUTLINE ConvertOutline(TESSLINE *Outline) {
114 /*
115 ** Parameters:
116 ** Outline outline to be converted
117 ** Globals:
118 ** BlobCenter pre-computed center of current blob
119 ** Operation:
120 ** This routine converts the specified outline into a special
121 ** data structure which is used for extracting micro-features.
122 ** If the outline has been pre-normalized by the splitter,
123 ** then it is assumed to be in expanded form and all we must
124 ** do is copy the points. Otherwise,
125 ** if the outline is expanded, then the expanded form is used
126 ** and the coordinates of the points are returned to page
127 ** coordinates using the global variable BlobCenter and the
128 ** scaling factor REALSCALE. If the outline is not expanded,
129 ** then the compressed form is used.
130 ** Return: Outline converted into special micro-features format.
131 ** Exceptions: none
132 ** History: 8/2/89, DSJ, Created.
133 ** 9/8/89, DSJ, Added ability to convert expanded blobs.
134 ** 1/11/90, DSJ, Changed to use REALSCALE instead of VECSCALE
135 ** to eliminate round-off problems.
136 ** 2/21/91, DSJ, Added ability to work with pre-normalized
137 ** blobs.
138 ** 4/30/91, DSJ, Added concept of "hidden" segments.
139 */
140 register BYTEVEC *Vector;
141 TPOINT Position;
142 TPOINT StartPosition;
143 MFEDGEPT *NewPoint;
144 MFOUTLINE MFOutline = NIL;
145 EDGEPT *EdgePoint;
146 EDGEPT *StartPoint;
147 EDGEPT *NextPoint;
148
149 if (Outline == NULL ||
150 (Outline->compactloop == NULL && Outline->loop == NULL))
151 return (MFOutline);
152
153 /* have outlines been prenormalized */
154 if (classify_baseline_normalized) {
155 StartPoint = Outline->loop;
156 EdgePoint = StartPoint;
157 do {
158 NextPoint = EdgePoint->next;
159
160 /* filter out duplicate points */
161 if (EdgePoint->pos.x != NextPoint->pos.x ||
162 EdgePoint->pos.y != NextPoint->pos.y) {
163 NewPoint = NewEdgePoint ();
164 ClearMark(NewPoint);
165 NewPoint->Hidden = is_hidden_edge (EdgePoint) ? TRUE : FALSE;
166 NewPoint->Point.x = EdgePoint->pos.x;
167 NewPoint->Point.y = EdgePoint->pos.y;
168 MFOutline = push (MFOutline, NewPoint);
169 }
170 EdgePoint = NextPoint;
171 }
172 while (EdgePoint != StartPoint);
173 }
174 /* use compressed version of outline */
175 else if (Outline->loop == NULL) {
176 Position.x = StartPosition.x = Outline->start.x;
177 Position.y = StartPosition.y = Outline->start.y;
178 Vector = Outline->compactloop;
179 do {
180 if (Vector->dx != 0 || Vector->dy != 0) {
181 NewPoint = NewEdgePoint ();
182 ClearMark(NewPoint);
183 /* all edges are visible */
184 NewPoint->Hidden = FALSE;
185 NewPoint->Point.x = Position.x;
186 NewPoint->Point.y = Position.y;
187 MFOutline = push (MFOutline, NewPoint);
188 }
189 Position.x += Vector->dx;
190 Position.y += Vector->dy;
191 Vector++;
192 }
193 while (Position.x != StartPosition.x ||
194 (Position.y != StartPosition.y));
195 }
196 else { /* use expanded version of outline */
197 StartPoint = Outline->loop;
198 EdgePoint = StartPoint;
199 do {
200 NextPoint = EdgePoint->next;
201
202 /* filter out duplicate points */
203 if (EdgePoint->pos.x != NextPoint->pos.x ||
204 EdgePoint->pos.y != NextPoint->pos.y) {
205 NewPoint = NewEdgePoint ();
206 ClearMark(NewPoint);
207 NewPoint->Hidden = is_hidden_edge (EdgePoint) ? TRUE : FALSE;
208 NewPoint->Point.x =
209 (EdgePoint->pos.x + BlobCenter.x) / REALSCALE;
210 NewPoint->Point.y =
211 (EdgePoint->pos.y + BlobCenter.y) / REALSCALE;
212 MFOutline = push (MFOutline, NewPoint);
213 }
214 EdgePoint = NextPoint;
215 }
216 while (EdgePoint != StartPoint);
217 }
218
219 MakeOutlineCircular(MFOutline);
220 return (MFOutline);
221
222 } /* ConvertOutline */
223
224
225 /*---------------------------------------------------------------------------*/
ConvertOutlines(TESSLINE * Outline,LIST ConvertedOutlines,OUTLINETYPE OutlineType)226 LIST ConvertOutlines(TESSLINE *Outline,
227 LIST ConvertedOutlines,
228 OUTLINETYPE OutlineType) {
229 /*
230 ** Parameters:
231 ** Outline first outline to be converted
232 ** ConvertedOutlines list to add converted outlines to
233 ** OutlineType are the outlines outer or holes?
234 ** Globals: none
235 ** Operation:
236 ** This routine converts all given outlines into a new format.
237 ** of outlines. Outline points to a list of the top level
238 ** outlines to be converted. The children of these outlines
239 ** are also recursively converted. All converted outlines
240 ** are added to ConvertedOutlines. This is a list of outlines,
241 ** one for each outline that was converted.
242 ** Return: Updated list of converted outlines.
243 ** Exceptions: none
244 ** History: Thu Dec 13 15:57:38 1990, DSJ, Created.
245 */
246 MFOUTLINE MFOutline;
247
248 while (Outline != NULL) {
249 if (Outline->child != NULL) {
250 if (OutlineType == outer)
251 ConvertedOutlines = ConvertOutlines (Outline->child,
252 ConvertedOutlines, hole);
253 else
254 ConvertedOutlines = ConvertOutlines (Outline->child,
255 ConvertedOutlines, outer);
256 }
257
258 MFOutline = ConvertOutline (Outline);
259 ConvertedOutlines = push (ConvertedOutlines, MFOutline);
260 Outline = Outline->next;
261 }
262 return (ConvertedOutlines);
263 } /* ConvertOutlines */
264
265
266 /*---------------------------------------------------------------------------*/
ComputeOutlineStats(LIST Outlines,OUTLINE_STATS * OutlineStats)267 void ComputeOutlineStats(LIST Outlines, OUTLINE_STATS *OutlineStats) {
268 /*
269 ** Parameters:
270 ** Outlines list of outlines to compute stats for
271 ** OutlineStats place to put results
272 ** Globals: none
273 ** Operation: This routine computes several statistics about the outlines
274 ** in Outlines. These statistics are usually used to perform
275 ** anistropic normalization of all of the outlines. The
276 ** statistics generated are:
277 ** first moments about x and y axes
278 ** total length of all outlines
279 ** center of mass of all outlines
280 ** second moments about center of mass axes
281 ** radius of gyration about center of mass axes
282 ** Return: none (results are returned in OutlineStats)
283 ** Exceptions: none
284 ** History: Fri Dec 14 08:32:03 1990, DSJ, Created.
285 */
286 MFOUTLINE Outline;
287 MFOUTLINE EdgePoint;
288 MFEDGEPT *Current;
289 MFEDGEPT *Last;
290
291 InitOutlineStats(OutlineStats);
292 iterate(Outlines) {
293 Outline = (MFOUTLINE) first_node (Outlines);
294
295 Last = PointAt (Outline);
296 Outline = NextPointAfter (Outline);
297 EdgePoint = Outline;
298 do {
299 Current = PointAt (EdgePoint);
300
301 UpdateOutlineStats (OutlineStats,
302 Last->Point.x, Last->Point.y,
303 Current->Point.x, Current->Point.y);
304
305 Last = Current;
306 EdgePoint = NextPointAfter (EdgePoint);
307 }
308 while (EdgePoint != Outline);
309 }
310 FinishOutlineStats(OutlineStats);
311
312 } /* ComputeOutlineStats */
313
314
315 /*---------------------------------------------------------------------------*/
FilterEdgeNoise(MFOUTLINE Outline,FLOAT32 NoiseSegmentLength)316 void FilterEdgeNoise(MFOUTLINE Outline, FLOAT32 NoiseSegmentLength) {
317 /*
318 ** Parameters:
319 ** Outline outline to be filtered
320 ** NoiseSegmentLength maximum length of a "noise" segment
321 ** Globals: none
322 ** Operation: Filter out noise from the specified outline. This is
323 ** done by changing the direction of short segments of the
324 ** outline to the same direction as the preceding outline
325 ** segment.
326 ** Return: none
327 ** Exceptions: none
328 ** History: Fri May 4 10:23:45 1990, DSJ, Created.
329 */
330 MFOUTLINE Current;
331 MFOUTLINE Last;
332 MFOUTLINE First;
333 FLOAT32 Length;
334 int NumFound = 0;
335 DIRECTION DirectionOfFirst = north;
336
337 if (DegenerateOutline (Outline))
338 return;
339
340 /* find 2 segments of different orientation which are long enough to
341 not be filtered. If two cannot be found, leave the outline unchanged. */
342 First = NextDirectionChange (Outline);
343 Last = First;
344 do {
345 Current = NextDirectionChange (Last);
346 Length = DistanceBetween ((PointAt (Current)->Point),
347 PointAt (Last)->Point);
348 if (Length >= NoiseSegmentLength) {
349 if (NumFound == 0) {
350 NumFound = 1;
351 DirectionOfFirst = PointAt (Last)->Direction;
352 }
353 else if (DirectionOfFirst != PointAt (Last)->Direction)
354 break;
355 }
356 Last = Current;
357 }
358 while (Last != First);
359 if (Current == Last)
360 return;
361
362 /* find each segment and filter it out if it is too short. Note that
363 the above code guarantees that the initial direction change will
364 not be removed, therefore the loop will terminate. */
365 First = Last;
366 do {
367 Current = NextDirectionChange (Last);
368 Length = DistanceBetween (PointAt (Current)->Point,
369 PointAt (Last)->Point);
370 if (Length < NoiseSegmentLength)
371 ChangeDirection (Last, Current, PointAt (Last)->PreviousDirection);
372
373 Last = Current;
374 }
375 while (Last != First);
376
377 } /* FilterEdgeNoise */
378
379
380 /*---------------------------------------------------------------------------*/
FindDirectionChanges(MFOUTLINE Outline,FLOAT32 MinSlope,FLOAT32 MaxSlope)381 void FindDirectionChanges(MFOUTLINE Outline,
382 FLOAT32 MinSlope,
383 FLOAT32 MaxSlope) {
384 /*
385 ** Parameters:
386 ** Outline micro-feature outline to analyze
387 ** MinSlope controls "snapping" of segments to horizontal
388 ** MaxSlope controls "snapping" of segments to vertical
389 ** Globals: none
390 ** Operation:
391 ** This routine searches thru the specified outline, computes
392 ** a slope for each vector in the outline, and marks each
393 ** vector as having one of the following directions:
394 ** N, S, E, W, NE, NW, SE, SW
395 ** This information is then stored in the outline and the
396 ** outline is returned.
397 ** Return: none
398 ** Exceptions: none
399 ** History: 7/21/89, DSJ, Created.
400 */
401 MFEDGEPT *Current;
402 MFEDGEPT *Last;
403 MFOUTLINE EdgePoint;
404
405 if (DegenerateOutline (Outline))
406 return;
407
408 Last = PointAt (Outline);
409 Outline = NextPointAfter (Outline);
410 EdgePoint = Outline;
411 do {
412 Current = PointAt (EdgePoint);
413 ComputeDirection(Last, Current, MinSlope, MaxSlope);
414
415 Last = Current;
416 EdgePoint = NextPointAfter (EdgePoint);
417 }
418 while (EdgePoint != Outline);
419
420 } /* FindDirectionChanges */
421
422
423 /*---------------------------------------------------------------------------*/
FreeMFOutline(void * arg)424 void FreeMFOutline(void *arg) { //MFOUTLINE Outline)
425 /*
426 ** Parameters:
427 ** Outline micro-feature outline to be freed
428 ** Globals: none
429 ** Operation:
430 ** This routine deallocates all of the memory consumed by
431 ** a micro-feature outline.
432 ** Return: none
433 ** Exceptions: none
434 ** History: 7/27/89, DSJ, Created.
435 */
436 MFOUTLINE Start;
437 MFOUTLINE Outline = (MFOUTLINE) arg;
438
439 /* break the circular outline so we can use std. techniques to deallocate */
440 Start = rest (Outline);
441 set_rest(Outline, NIL);
442 while (Start != NULL) {
443 free_struct (first_node (Start), sizeof (MFEDGEPT), "MFEDGEPT");
444 Start = pop (Start);
445 }
446
447 } /* FreeMFOutline */
448
449
450 /*---------------------------------------------------------------------------*/
FreeOutlines(LIST Outlines)451 void FreeOutlines(LIST Outlines) {
452 /*
453 ** Parameters:
454 ** Outlines list of mf-outlines to be freed
455 ** Globals: none
456 ** Operation: Release all memory consumed by the specified list
457 ** of outlines.
458 ** Return: none
459 ** Exceptions: none
460 ** History: Thu Dec 13 16:14:50 1990, DSJ, Created.
461 */
462 destroy_nodes(Outlines, FreeMFOutline);
463 } /* FreeOutlines */
464
465
466 /*---------------------------------------------------------------------------*/
MarkDirectionChanges(MFOUTLINE Outline)467 void MarkDirectionChanges(MFOUTLINE Outline) {
468 /*
469 ** Parameters:
470 ** Outline micro-feature outline to analyze
471 ** Globals: none
472 ** Operation:
473 ** This routine searches thru the specified outline and finds
474 ** the points at which the outline changes direction. These
475 ** points are then marked as "extremities". This routine is
476 ** used as an alternative to FindExtremities(). It forces the
477 ** endpoints of the microfeatures to be at the direction
478 ** changes rather than at the midpoint between direction
479 ** changes.
480 ** Return: none
481 ** Exceptions: none
482 ** History: 6/29/90, DSJ, Created.
483 */
484 MFOUTLINE Current;
485 MFOUTLINE Last;
486 MFOUTLINE First;
487
488 if (DegenerateOutline (Outline))
489 return;
490
491 First = NextDirectionChange (Outline);
492 Last = First;
493 do {
494 Current = NextDirectionChange (Last);
495 MarkPoint (PointAt (Current));
496 Last = Current;
497 }
498 while (Last != First);
499
500 } /* MarkDirectionChanges */
501
502
503 /*---------------------------------------------------------------------------*/
NewEdgePoint()504 MFEDGEPT *NewEdgePoint() {
505 /*
506 ** Parameters: none
507 ** Globals: none
508 ** Operation:
509 ** This routine allocates and returns a new edge point for
510 ** a micro-feature outline.
511 ** Return: New edge point.
512 ** Exceptions: none
513 ** History: 7/21/89, DSJ, Created.
514 */
515 return ((MFEDGEPT *) alloc_struct (sizeof (MFEDGEPT), "MFEDGEPT"));
516
517 } /* NewEdgePoint */
518
519
520 /*---------------------------------------------------------------------------*/
NextExtremity(MFOUTLINE EdgePoint)521 MFOUTLINE NextExtremity(MFOUTLINE EdgePoint) {
522 /*
523 ** Parameters:
524 ** EdgePoint start search from this point
525 ** Globals: none
526 ** Operation:
527 ** This routine returns the next point in the micro-feature
528 ** outline that is an extremity. The search starts after
529 ** EdgePoint. The routine assumes that the outline being
530 ** searched is not a degenerate outline (i.e. it must have
531 ** 2 or more edge points).
532 ** Return: Next extremity in the outline after EdgePoint.
533 ** Exceptions: none
534 ** History: 7/26/89, DSJ, Created.
535 */
536 EdgePoint = NextPointAfter (EdgePoint);
537 while (!PointAt (EdgePoint)->ExtremityMark)
538 EdgePoint = NextPointAfter (EdgePoint);
539
540 return (EdgePoint);
541
542 } /* NextExtremity */
543
544
545 /*---------------------------------------------------------------------------*/
NormalizeOutline(MFOUTLINE Outline,LINE_STATS * LineStats,FLOAT32 XOrigin)546 void NormalizeOutline(MFOUTLINE Outline,
547 LINE_STATS *LineStats,
548 FLOAT32 XOrigin) {
549 /*
550 ** Parameters:
551 ** Outline outline to be normalized
552 ** LineStats statistics for text line normalization
553 ** XOrigin x-origin of text
554 ** Globals: none
555 ** Operation:
556 ** This routine normalizes the coordinates of the specified
557 ** outline so that the outline is deskewed down to the
558 ** baseline, translated so that x=0 is at XOrigin, and scaled
559 ** so that the height of a character cell from descender to
560 ** ascender is 1. Of this height, 0.25 is for the descender,
561 ** 0.25 for the ascender, and 0.5 for the x-height. The
562 ** y coordinate of the baseline is 0.
563 ** Return: none
564 ** Exceptions: none
565 ** History: 8/2/89, DSJ, Created.
566 ** 10/23/89, DSJ, Added ascender/descender stretching.
567 ** 11/89, DSJ, Removed ascender/descender stretching.
568 */
569 MFEDGEPT *Current;
570 MFOUTLINE EdgePoint;
571 FLOAT32 ScaleFactor;
572 FLOAT32 AscStretch;
573 FLOAT32 DescStretch;
574
575 if (Outline != NIL) {
576 ScaleFactor = ComputeScaleFactor (LineStats);
577 AscStretch = 1.0;
578 DescStretch = 1.0;
579
580 EdgePoint = Outline;
581 do {
582 Current = PointAt (EdgePoint);
583
584 Current->Point.y = ScaleFactor *
585 (Current->Point.y -
586 BaselineAt (LineStats, XPositionOf (Current)));
587
588 if (Current->Point.y > NORMAL_X_HEIGHT)
589 Current->Point.y = NORMAL_X_HEIGHT +
590 (Current->Point.y - NORMAL_X_HEIGHT) / AscStretch;
591
592 else if (Current->Point.y < NORMAL_BASELINE)
593 Current->Point.y = NORMAL_BASELINE +
594 (Current->Point.y - NORMAL_BASELINE) / DescStretch;
595
596 Current->Point.x = ScaleFactor *
597 (Current->Point.x - XOrigin);
598
599 EdgePoint = NextPointAfter (EdgePoint);
600 }
601 while (EdgePoint != Outline);
602 }
603 } /* NormalizeOutline */
604
605
606 /*---------------------------------------------------------------------------*/
NormalizeOutlines(LIST Outlines,LINE_STATS * LineStats,FLOAT32 * XScale,FLOAT32 * YScale)607 void NormalizeOutlines(LIST Outlines,
608 LINE_STATS *LineStats,
609 FLOAT32 *XScale,
610 FLOAT32 *YScale) {
611 /*
612 ** Parameters:
613 ** Outlines list of outlines to be normalized
614 ** LineStats statistics for text line normalization
615 ** XScale x-direction scale factor used by routine
616 ** YScale y-direction scale factor used by routine
617 ** Globals:
618 ** classify_norm_method method being used for normalization
619 ** classify_char_norm_range map radius of gyration to this value
620 ** Operation: This routine normalizes every outline in Outlines
621 ** according to the currently selected normalization method.
622 ** It also returns the scale factors that it used to do this
623 ** scaling. The scale factors returned represent the x and
624 ** y sizes in the normalized coordinate system that correspond
625 ** to 1 pixel in the original coordinate system.
626 ** Return: none (Outlines are changed and XScale and YScale are updated)
627 ** Exceptions: none
628 ** History: Fri Dec 14 08:14:55 1990, DSJ, Created.
629 */
630 MFOUTLINE Outline;
631 OUTLINE_STATS OutlineStats;
632 FLOAT32 BaselineScale;
633
634 switch (classify_norm_method) {
635 case character:
636 ComputeOutlineStats(Outlines, &OutlineStats);
637
638 /* limit scale factor to avoid overscaling small blobs (.,`'),
639 thin blobs (l1ift), and merged blobs */
640 *XScale = *YScale = BaselineScale = ComputeScaleFactor (LineStats);
641 *XScale *= OutlineStats.Ry;
642 *YScale *= OutlineStats.Rx;
643 if (*XScale < classify_min_norm_scale_x)
644 *XScale = classify_min_norm_scale_x;
645 if (*YScale < classify_min_norm_scale_y)
646 *YScale = classify_min_norm_scale_y;
647 if (*XScale > classify_max_norm_scale_x &&
648 *YScale <= classify_max_norm_scale_y)
649 *XScale = classify_max_norm_scale_x;
650 *XScale = classify_char_norm_range * BaselineScale / *XScale;
651 *YScale = classify_char_norm_range * BaselineScale / *YScale;
652
653 iterate(Outlines) {
654 Outline = (MFOUTLINE) first_node (Outlines);
655 CharNormalizeOutline (Outline,
656 OutlineStats.x, OutlineStats.y,
657 *XScale, *YScale);
658 }
659 break;
660
661 case baseline:
662 iterate(Outlines) {
663 Outline = (MFOUTLINE) first_node (Outlines);
664 NormalizeOutline (Outline, LineStats, 0.0);
665 }
666 *XScale = *YScale = ComputeScaleFactor (LineStats);
667 break;
668 }
669 } /* NormalizeOutlines */
670
671
672 /*---------------------------------------------------------------------------*/
SettupBlobConversion(TBLOB * Blob)673 void SettupBlobConversion(TBLOB *Blob) {
674 /*
675 ** Parameters:
676 ** Blob blob that is to be converted
677 ** Globals:
678 ** BlobCenter center of blob to be converted
679 ** Operation: Compute the center of the blob's bounding box and save
680 ** it in a global variable. This routine must be called before
681 ** any calls to ConvertOutline. It must be called once per
682 ** blob.
683 ** Return: none
684 ** Exceptions: none
685 ** History: Thu May 17 11:06:17 1990, DSJ, Created.
686 */
687 ComputeBlobCenter(Blob, &BlobCenter);
688 } /* SettupBlobConversion */
689
690
691 /*---------------------------------------------------------------------------*/
SmearExtremities(MFOUTLINE Outline,FLOAT32 XScale,FLOAT32 YScale)692 void SmearExtremities(MFOUTLINE Outline, FLOAT32 XScale, FLOAT32 YScale) {
693 /*
694 ** Parameters:
695 ** Outline outline whose extremities are to be smeared
696 ** XScale factor used to normalize outline in x dir
697 ** YScale factor used to normalize outline in y dir
698 ** Globals: none
699 ** Operation:
700 ** This routine smears the extremities of the specified outline.
701 ** It does this by adding a random number between
702 ** -0.5 and 0.5 pixels (that is why X/YScale are needed) to
703 ** the x and y position of the point. This is done so that
704 ** the discrete nature of the original scanned image does not
705 ** affect the statistical clustering used during training.
706 ** Return: none
707 ** Exceptions: none
708 ** History: 1/11/90, DSJ, Created.
709 */
710 MFEDGEPT *Current;
711 MFOUTLINE EdgePoint;
712 FLOAT32 MinXSmear;
713 FLOAT32 MaxXSmear;
714 FLOAT32 MinYSmear;
715 FLOAT32 MaxYSmear;
716
717 if (Outline != NIL) {
718 MinXSmear = -0.5 * XScale;
719 MaxXSmear = 0.5 * XScale;
720 MinYSmear = -0.5 * YScale;
721 MaxYSmear = 0.5 * YScale;
722 EdgePoint = Outline;
723 do {
724 Current = PointAt (EdgePoint);
725 if (Current->ExtremityMark) {
726 Current->Point.x +=
727 UniformRandomNumber(MinXSmear, MaxXSmear);
728 Current->Point.y +=
729 UniformRandomNumber(MinYSmear, MaxYSmear);
730 }
731
732 EdgePoint = NextPointAfter (EdgePoint);
733 }
734 while (EdgePoint != Outline);
735 }
736 } /* SmearExtremities */
737
738
739 /**----------------------------------------------------------------------------
740 Private Code
741 ----------------------------------------------------------------------------**/
742 /*---------------------------------------------------------------------------*/
ChangeDirection(MFOUTLINE Start,MFOUTLINE End,DIRECTION Direction)743 void ChangeDirection(MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction) {
744 /*
745 ** Parameters:
746 ** Start, End defines segment of outline to be modified
747 ** Direction new direction to assign to segment
748 ** Globals: none
749 ** Operation: Change the direction of every vector in the specified
750 ** outline segment to Direction. The segment to be changed
751 ** starts at Start and ends at End. Note that the previous
752 ** direction of End must also be changed to reflect the
753 ** change in direction of the point before it.
754 ** Return: none
755 ** Exceptions: none
756 ** History: Fri May 4 10:42:04 1990, DSJ, Created.
757 */
758 MFOUTLINE Current;
759
760 for (Current = Start; Current != End; Current = NextPointAfter (Current))
761 PointAt (Current)->Direction = Direction;
762
763 PointAt (End)->PreviousDirection = Direction;
764
765 } /* ChangeDirection */
766
767
768 /*---------------------------------------------------------------------------*/
CharNormalizeOutline(MFOUTLINE Outline,FLOAT32 XCenter,FLOAT32 YCenter,FLOAT32 XScale,FLOAT32 YScale)769 void CharNormalizeOutline(MFOUTLINE Outline,
770 FLOAT32 XCenter,
771 FLOAT32 YCenter,
772 FLOAT32 XScale,
773 FLOAT32 YScale) {
774 /*
775 ** Parameters:
776 ** Outline outline to be character normalized
777 ** XCenter, YCenter center point for normalization
778 ** XScale, YScale scale factors for normalization
779 ** Globals: none
780 ** Operation: This routine normalizes each point in Outline by
781 ** translating it to the specified center and scaling it
782 ** anisotropically according to the given scale factors.
783 ** Return: none
784 ** Exceptions: none
785 ** History: Fri Dec 14 10:27:11 1990, DSJ, Created.
786 */
787 MFOUTLINE First, Current;
788 MFEDGEPT *CurrentPoint;
789
790 if (Outline == NIL)
791 return;
792
793 First = Outline;
794 Current = First;
795 do {
796 CurrentPoint = PointAt (Current);
797 CurrentPoint->Point.x =
798 (CurrentPoint->Point.x - XCenter) * XScale;
799 CurrentPoint->Point.y =
800 (CurrentPoint->Point.y - YCenter) * YScale;
801
802 Current = NextPointAfter (Current);
803 }
804 while (Current != First);
805
806 } /* CharNormalizeOutline */
807
808
809 /*---------------------------------------------------------------------------*/
ComputeDirection(MFEDGEPT * Start,MFEDGEPT * Finish,FLOAT32 MinSlope,FLOAT32 MaxSlope)810 void ComputeDirection(MFEDGEPT *Start,
811 MFEDGEPT *Finish,
812 FLOAT32 MinSlope,
813 FLOAT32 MaxSlope) {
814 /*
815 ** Parameters:
816 ** Start starting point to compute direction from
817 ** Finish finishing point to compute direction to
818 ** MinSlope slope below which lines are horizontal
819 ** MaxSlope slope above which lines are vertical
820 ** Globals: none
821 ** Operation:
822 ** This routine computes the slope from Start to Finish and
823 ** and then computes the approximate direction of the line
824 ** segment from Start to Finish. The direction is quantized
825 ** into 8 buckets:
826 ** N, S, E, W, NE, NW, SE, SW
827 ** Both the slope and the direction are then stored into
828 ** the appropriate fields of the Start edge point. The
829 ** direction is also stored into the PreviousDirection field
830 ** of the Finish edge point.
831 ** Return: none
832 ** Exceptions: none
833 ** History: 7/25/89, DSJ, Created.
834 */
835 FVECTOR Delta;
836
837 Delta.x = Finish->Point.x - Start->Point.x;
838 Delta.y = Finish->Point.y - Start->Point.y;
839 if (Delta.x == 0)
840 if (Delta.y < 0) {
841 Start->Slope = -MAX_FLOAT32;
842 Start->Direction = south;
843 }
844 else {
845 Start->Slope = MAX_FLOAT32;
846 Start->Direction = north;
847 }
848 else {
849 Start->Slope = Delta.y / Delta.x;
850 if (Delta.x > 0)
851 if (Delta.y > 0)
852 if (Start->Slope > MinSlope)
853 if (Start->Slope < MaxSlope)
854 Start->Direction = northeast;
855 else
856 Start->Direction = north;
857 else
858 Start->Direction = east;
859 else if (Start->Slope < -MinSlope)
860 if (Start->Slope > -MaxSlope)
861 Start->Direction = southeast;
862 else
863 Start->Direction = south;
864 else
865 Start->Direction = east;
866 else if (Delta.y > 0)
867 if (Start->Slope < -MinSlope)
868 if (Start->Slope > -MaxSlope)
869 Start->Direction = northwest;
870 else
871 Start->Direction = north;
872 else
873 Start->Direction = west;
874 else if (Start->Slope > MinSlope)
875 if (Start->Slope < MaxSlope)
876 Start->Direction = southwest;
877 else
878 Start->Direction = south;
879 else
880 Start->Direction = west;
881 }
882 Finish->PreviousDirection = Start->Direction;
883 } /* ComputeDirection */
884
885
886 /*---------------------------------------------------------------------------*/
FinishOutlineStats(register OUTLINE_STATS * OutlineStats)887 void FinishOutlineStats(register OUTLINE_STATS *OutlineStats) {
888 /*
889 ** Parameters:
890 ** OutlineStats statistics about a set of outlines
891 ** Globals: none
892 ** Operation: Use the preliminary statistics accumulated in OutlineStats
893 ** to compute the final statistics.
894 ** (see Dan Johnson's Tesseract lab
895 ** notebook #2, pgs. 74-78).
896 ** Return: none
897 ** Exceptions: none
898 ** History: Fri Dec 14 10:13:36 1990, DSJ, Created.
899 */
900 OutlineStats->x = 0.5 * OutlineStats->My / OutlineStats->L;
901 OutlineStats->y = 0.5 * OutlineStats->Mx / OutlineStats->L;
902
903 OutlineStats->Ix = (OutlineStats->Ix / 3.0 -
904 OutlineStats->y * OutlineStats->Mx +
905 OutlineStats->y * OutlineStats->y * OutlineStats->L);
906
907 OutlineStats->Iy = (OutlineStats->Iy / 3.0 -
908 OutlineStats->x * OutlineStats->My +
909 OutlineStats->x * OutlineStats->x * OutlineStats->L);
910
911 /* Ix and/or Iy could possibly be negative due to roundoff error */
912 if (OutlineStats->Ix < 0.0)
913 OutlineStats->Ix = MIN_INERTIA;
914 if (OutlineStats->Iy < 0.0)
915 OutlineStats->Iy = MIN_INERTIA;
916
917 OutlineStats->Rx = sqrt (OutlineStats->Ix / OutlineStats->L);
918 OutlineStats->Ry = sqrt (OutlineStats->Iy / OutlineStats->L);
919
920 OutlineStats->Mx *= 0.5;
921 OutlineStats->My *= 0.5;
922
923 } /* FinishOutlineStats */
924
925
926 /*---------------------------------------------------------------------------*/
InitOutlineStats(OUTLINE_STATS * OutlineStats)927 void InitOutlineStats(OUTLINE_STATS *OutlineStats) {
928 /*
929 ** Parameters:
930 ** OutlineStats stats data structure to be initialized
931 ** Globals: none
932 ** Operation: Initialize the outline statistics data structure so
933 ** that it is ready to start accumulating statistics.
934 ** Return: none
935 ** Exceptions: none
936 ** History: Fri Dec 14 08:55:22 1990, DSJ, Created.
937 */
938 OutlineStats->Mx = 0.0;
939 OutlineStats->My = 0.0;
940 OutlineStats->L = 0.0;
941 OutlineStats->x = 0.0;
942 OutlineStats->y = 0.0;
943 OutlineStats->Ix = 0.0;
944 OutlineStats->Iy = 0.0;
945 OutlineStats->Rx = 0.0;
946 OutlineStats->Ry = 0.0;
947 } /* InitOutlineStats */
948
949
950 /*---------------------------------------------------------------------------*/
NextDirectionChange(MFOUTLINE EdgePoint)951 MFOUTLINE NextDirectionChange(MFOUTLINE EdgePoint) {
952 /*
953 ** Parameters:
954 ** EdgePoint start search from this point
955 ** Globals: none
956 ** Operation:
957 ** This routine returns the next point in the micro-feature
958 ** outline that has a direction different than EdgePoint. The
959 ** routine assumes that the outline being searched is not a
960 ** degenerate outline (i.e. it must have 2 or more edge points).
961 ** Return: Point of next direction change in micro-feature outline.
962 ** Exceptions: none
963 ** History: 7/25/89, DSJ, Created.
964 */
965 DIRECTION InitialDirection;
966
967 InitialDirection = PointAt (EdgePoint)->Direction;
968
969 do
970 EdgePoint = NextPointAfter (EdgePoint);
971 while (PointAt (EdgePoint)->Direction == InitialDirection);
972
973 return (EdgePoint);
974 } /* NextDirectionChange */
975
976
977 /*---------------------------------------------------------------------------*/
UpdateOutlineStats(register OUTLINE_STATS * OutlineStats,register FLOAT32 x1,register FLOAT32 x2,register FLOAT32 y1,register FLOAT32 y2)978 void UpdateOutlineStats(register OUTLINE_STATS *OutlineStats,
979 register FLOAT32 x1,
980 register FLOAT32 x2,
981 register FLOAT32 y1,
982 register FLOAT32 y2) {
983 /*
984 ** Parameters:
985 ** OutlineStats statistics to add this segment to
986 ** x1, y1, x2, y2 segment to be added to statistics
987 ** Globals: none
988 ** Operation: This routine adds the statistics for the specified
989 ** line segment to OutlineStats. The statistics that are
990 ** kept are:
991 ** sum of length of all segments
992 ** sum of 2*Mx for all segments
993 ** sum of 2*My for all segments
994 ** sum of 2*Mx*(y1+y2) - L*y1*y2 for all segments
995 ** sum of 2*My*(x1+x2) - L*x1*x2 for all segments
996 ** These numbers, once collected can later be used to easily
997 ** compute the center of mass, first and second moments,
998 ** and radii of gyration. (see Dan Johnson's Tesseract lab
999 ** notebook #2, pgs. 74-78).
1000 ** Return: none
1001 ** Exceptions: none
1002 ** History: Fri Dec 14 08:59:17 1990, DSJ, Created.
1003 */
1004 register FLOAT64 L;
1005 register FLOAT64 Mx2;
1006 register FLOAT64 My2;
1007
1008 /* compute length of segment */
1009 L = sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
1010 OutlineStats->L += L;
1011
1012 /* compute 2Mx and 2My components */
1013 Mx2 = L * (y1 + y2);
1014 My2 = L * (x1 + x2);
1015 OutlineStats->Mx += Mx2;
1016 OutlineStats->My += My2;
1017
1018 /* compute second moment component */
1019 OutlineStats->Ix += Mx2 * (y1 + y2) - L * y1 * y2;
1020 OutlineStats->Iy += My2 * (x1 + x2) - L * x1 * x2;
1021
1022 } /* UpdateOutlineStats */
1023