tesseract  3.04.00
mfoutline.cpp
Go to the documentation of this file.
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 "blobs.h"
25 #include "const.h"
26 #include "mfx.h"
27 #include "params.h"
28 #include "classify.h"
29 
30 #include <math.h>
31 #include <stdio.h>
32 
33 /*----------------------------------------------------------------------------
34  Public Code
35 ----------------------------------------------------------------------------*/
36 
37 /*---------------------------------------------------------------------------*/
38 // Convert a blob into a list of MFOUTLINEs (float-based microfeature format).
40  LIST outlines = NIL_LIST;
41  return (blob == NULL)
42  ? NIL_LIST
43  : ConvertOutlines(blob->outlines, outlines, outer);
44 }
45 
46 
47 /*---------------------------------------------------------------------------*/
48 // Convert a TESSLINE into the float-based MFOUTLINE micro-feature format.
50  MFEDGEPT *NewPoint;
51  MFOUTLINE MFOutline = NIL_LIST;
52  EDGEPT *EdgePoint;
53  EDGEPT *StartPoint;
54  EDGEPT *NextPoint;
55 
56  if (outline == NULL || outline->loop == NULL)
57  return MFOutline;
58 
59  StartPoint = outline->loop;
60  EdgePoint = StartPoint;
61  do {
62  NextPoint = EdgePoint->next;
63 
64  /* filter out duplicate points */
65  if (EdgePoint->pos.x != NextPoint->pos.x ||
66  EdgePoint->pos.y != NextPoint->pos.y) {
67  NewPoint = NewEdgePoint();
68  ClearMark(NewPoint);
69  NewPoint->Hidden = EdgePoint->IsHidden();
70  NewPoint->Point.x = EdgePoint->pos.x;
71  NewPoint->Point.y = EdgePoint->pos.y;
72  MFOutline = push(MFOutline, NewPoint);
73  }
74  EdgePoint = NextPoint;
75  } while (EdgePoint != StartPoint);
76 
77  if (MFOutline != NULL)
78  MakeOutlineCircular(MFOutline);
79  return MFOutline;
80 }
81 
82 
83 /*---------------------------------------------------------------------------*/
84 // Convert a tree of outlines to a list of MFOUTLINEs (lists of MFEDGEPTs).
85 //
86 // Parameters:
87 // outline first outline to be converted
88 // mf_outlines list to add converted outlines to
89 // outline_type are the outlines outer or holes?
91  LIST mf_outlines,
92  OUTLINETYPE outline_type) {
93  MFOUTLINE mf_outline;
94 
95  while (outline != NULL) {
96  mf_outline = ConvertOutline(outline);
97  if (mf_outline != NULL)
98  mf_outlines = push(mf_outlines, mf_outline);
99  outline = outline->next;
100  }
101  return mf_outlines;
102 }
103 
104 /*---------------------------------------------------------------------------*/
106  FLOAT32 MinSlope,
107  FLOAT32 MaxSlope) {
108 /*
109  ** Parameters:
110  ** Outline micro-feature outline to analyze
111  ** MinSlope controls "snapping" of segments to horizontal
112  ** MaxSlope controls "snapping" of segments to vertical
113  ** Globals: none
114  ** Operation:
115  ** This routine searches thru the specified outline, computes
116  ** a slope for each vector in the outline, and marks each
117  ** vector as having one of the following directions:
118  ** N, S, E, W, NE, NW, SE, SW
119  ** This information is then stored in the outline and the
120  ** outline is returned.
121  ** Return: none
122  ** Exceptions: none
123  ** History: 7/21/89, DSJ, Created.
124  */
125  MFEDGEPT *Current;
126  MFEDGEPT *Last;
127  MFOUTLINE EdgePoint;
128 
129  if (DegenerateOutline (Outline))
130  return;
131 
132  Last = PointAt (Outline);
133  Outline = NextPointAfter (Outline);
134  EdgePoint = Outline;
135  do {
136  Current = PointAt (EdgePoint);
137  ComputeDirection(Last, Current, MinSlope, MaxSlope);
138 
139  Last = Current;
140  EdgePoint = NextPointAfter (EdgePoint);
141  }
142  while (EdgePoint != Outline);
143 
144 } /* FindDirectionChanges */
145 
146 
147 /*---------------------------------------------------------------------------*/
148 void FreeMFOutline(void *arg) { //MFOUTLINE Outline)
149 /*
150  ** Parameters:
151  ** Outline micro-feature outline to be freed
152  ** Globals: none
153  ** Operation:
154  ** This routine deallocates all of the memory consumed by
155  ** a micro-feature outline.
156  ** Return: none
157  ** Exceptions: none
158  ** History: 7/27/89, DSJ, Created.
159  */
160  MFOUTLINE Start;
161  MFOUTLINE Outline = (MFOUTLINE) arg;
162 
163  /* break the circular outline so we can use std. techniques to deallocate */
164  Start = list_rest (Outline);
165  set_rest(Outline, NIL_LIST);
166  while (Start != NULL) {
167  free_struct (first_node (Start), sizeof (MFEDGEPT), "MFEDGEPT");
168  Start = pop (Start);
169  }
170 
171 } /* FreeMFOutline */
172 
173 
174 /*---------------------------------------------------------------------------*/
175 void FreeOutlines(LIST Outlines) {
176 /*
177  ** Parameters:
178  ** Outlines list of mf-outlines to be freed
179  ** Globals: none
180  ** Operation: Release all memory consumed by the specified list
181  ** of outlines.
182  ** Return: none
183  ** Exceptions: none
184  ** History: Thu Dec 13 16:14:50 1990, DSJ, Created.
185  */
186  destroy_nodes(Outlines, FreeMFOutline);
187 } /* FreeOutlines */
188 
189 
190 /*---------------------------------------------------------------------------*/
192 /*
193  ** Parameters:
194  ** Outline micro-feature outline to analyze
195  ** Globals: none
196  ** Operation:
197  ** This routine searches thru the specified outline and finds
198  ** the points at which the outline changes direction. These
199  ** points are then marked as "extremities". This routine is
200  ** used as an alternative to FindExtremities(). It forces the
201  ** endpoints of the microfeatures to be at the direction
202  ** changes rather than at the midpoint between direction
203  ** changes.
204  ** Return: none
205  ** Exceptions: none
206  ** History: 6/29/90, DSJ, Created.
207  */
208  MFOUTLINE Current;
209  MFOUTLINE Last;
210  MFOUTLINE First;
211 
212  if (DegenerateOutline (Outline))
213  return;
214 
215  First = NextDirectionChange (Outline);
216  Last = First;
217  do {
218  Current = NextDirectionChange (Last);
219  MarkPoint (PointAt (Current));
220  Last = Current;
221  }
222  while (Last != First);
223 
224 } /* MarkDirectionChanges */
225 
226 
227 /*---------------------------------------------------------------------------*/
228 // Return a new edge point for a micro-feature outline.
230  return ((MFEDGEPT *) alloc_struct(sizeof(MFEDGEPT), "MFEDGEPT"));
231 }
232 
233 
234 /*---------------------------------------------------------------------------*/
236 /*
237  ** Parameters:
238  ** EdgePoint start search from this point
239  ** Globals: none
240  ** Operation:
241  ** This routine returns the next point in the micro-feature
242  ** outline that is an extremity. The search starts after
243  ** EdgePoint. The routine assumes that the outline being
244  ** searched is not a degenerate outline (i.e. it must have
245  ** 2 or more edge points).
246  ** Return: Next extremity in the outline after EdgePoint.
247  ** Exceptions: none
248  ** History: 7/26/89, DSJ, Created.
249  */
250  EdgePoint = NextPointAfter(EdgePoint);
251  while (!PointAt(EdgePoint)->ExtremityMark)
252  EdgePoint = NextPointAfter(EdgePoint);
253 
254  return (EdgePoint);
255 
256 } /* NextExtremity */
257 
258 
259 /*---------------------------------------------------------------------------*/
261  FLOAT32 XOrigin) {
262 /*
263  ** Parameters:
264  ** Outline outline to be normalized
265  ** XOrigin x-origin of text
266  ** Globals: none
267  ** Operation:
268  ** This routine normalizes the coordinates of the specified
269  ** outline so that the outline is deskewed down to the
270  ** baseline, translated so that x=0 is at XOrigin, and scaled
271  ** so that the height of a character cell from descender to
272  ** ascender is 1. Of this height, 0.25 is for the descender,
273  ** 0.25 for the ascender, and 0.5 for the x-height. The
274  ** y coordinate of the baseline is 0.
275  ** Return: none
276  ** Exceptions: none
277  ** History: 8/2/89, DSJ, Created.
278  */
279  if (Outline == NIL_LIST)
280  return;
281 
282  MFOUTLINE EdgePoint = Outline;
283  do {
284  MFEDGEPT *Current = PointAt(EdgePoint);
285  Current->Point.y = MF_SCALE_FACTOR *
286  (Current->Point.y - kBlnBaselineOffset);
287  Current->Point.x = MF_SCALE_FACTOR * (Current->Point.x - XOrigin);
288  EdgePoint = NextPointAfter(EdgePoint);
289  } while (EdgePoint != Outline);
290 } /* NormalizeOutline */
291 
292 
293 /*---------------------------------------------------------------------------*/
294 namespace tesseract {
296  FLOAT32 *XScale,
297  FLOAT32 *YScale) {
298 /*
299  ** Parameters:
300  ** Outlines list of outlines to be normalized
301  ** XScale x-direction scale factor used by routine
302  ** YScale y-direction scale factor used by routine
303  ** Globals:
304  ** classify_norm_method method being used for normalization
305  ** classify_char_norm_range map radius of gyration to this value
306  ** Operation: This routine normalizes every outline in Outlines
307  ** according to the currently selected normalization method.
308  ** It also returns the scale factors that it used to do this
309  ** scaling. The scale factors returned represent the x and
310  ** y sizes in the normalized coordinate system that correspond
311  ** to 1 pixel in the original coordinate system.
312  ** Return: none (Outlines are changed and XScale and YScale are updated)
313  ** Exceptions: none
314  ** History: Fri Dec 14 08:14:55 1990, DSJ, Created.
315  */
316  MFOUTLINE Outline;
317 
318  switch (classify_norm_method) {
319  case character:
320  ASSERT_HOST(!"How did NormalizeOutlines get called in character mode?");
321  break;
322 
323  case baseline:
324  iterate(Outlines) {
325  Outline = (MFOUTLINE) first_node(Outlines);
326  NormalizeOutline(Outline, 0.0);
327  }
328  *XScale = *YScale = MF_SCALE_FACTOR;
329  break;
330  }
331 } /* NormalizeOutlines */
332 } // namespace tesseract
333 
337 /*---------------------------------------------------------------------------*/
338 void ChangeDirection(MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction) {
339 /*
340  ** Parameters:
341  ** Start, End defines segment of outline to be modified
342  ** Direction new direction to assign to segment
343  ** Globals: none
344  ** Operation: Change the direction of every vector in the specified
345  ** outline segment to Direction. The segment to be changed
346  ** starts at Start and ends at End. Note that the previous
347  ** direction of End must also be changed to reflect the
348  ** change in direction of the point before it.
349  ** Return: none
350  ** Exceptions: none
351  ** History: Fri May 4 10:42:04 1990, DSJ, Created.
352  */
353  MFOUTLINE Current;
354 
355  for (Current = Start; Current != End; Current = NextPointAfter (Current))
356  PointAt (Current)->Direction = Direction;
357 
358  PointAt (End)->PreviousDirection = Direction;
359 
360 } /* ChangeDirection */
361 
362 
363 /*---------------------------------------------------------------------------*/
364 void CharNormalizeOutline(MFOUTLINE Outline, const DENORM& cn_denorm) {
365 /*
366  ** Parameters:
367  ** Outline outline to be character normalized
368  ** XCenter, YCenter center point for normalization
369  ** XScale, YScale scale factors for normalization
370  ** Globals: none
371  ** Operation: This routine normalizes each point in Outline by
372  ** translating it to the specified center and scaling it
373  ** anisotropically according to the given scale factors.
374  ** Return: none
375  ** Exceptions: none
376  ** History: Fri Dec 14 10:27:11 1990, DSJ, Created.
377  */
378  MFOUTLINE First, Current;
379  MFEDGEPT *CurrentPoint;
380 
381  if (Outline == NIL_LIST)
382  return;
383 
384  First = Outline;
385  Current = First;
386  do {
387  CurrentPoint = PointAt(Current);
388  FCOORD pos(CurrentPoint->Point.x, CurrentPoint->Point.y);
389  cn_denorm.LocalNormTransform(pos, &pos);
390  CurrentPoint->Point.x = (pos.x() - MAX_UINT8 / 2) * MF_SCALE_FACTOR;
391  CurrentPoint->Point.y = (pos.y() - MAX_UINT8 / 2) * MF_SCALE_FACTOR;
392 
393  Current = NextPointAfter(Current);
394  }
395  while (Current != First);
396 
397 } /* CharNormalizeOutline */
398 
399 
400 /*---------------------------------------------------------------------------*/
402  MFEDGEPT *Finish,
403  FLOAT32 MinSlope,
404  FLOAT32 MaxSlope) {
405 /*
406  ** Parameters:
407  ** Start starting point to compute direction from
408  ** Finish finishing point to compute direction to
409  ** MinSlope slope below which lines are horizontal
410  ** MaxSlope slope above which lines are vertical
411  ** Globals: none
412  ** Operation:
413  ** This routine computes the slope from Start to Finish and
414  ** and then computes the approximate direction of the line
415  ** segment from Start to Finish. The direction is quantized
416  ** into 8 buckets:
417  ** N, S, E, W, NE, NW, SE, SW
418  ** Both the slope and the direction are then stored into
419  ** the appropriate fields of the Start edge point. The
420  ** direction is also stored into the PreviousDirection field
421  ** of the Finish edge point.
422  ** Return: none
423  ** Exceptions: none
424  ** History: 7/25/89, DSJ, Created.
425  */
426  FVECTOR Delta;
427 
428  Delta.x = Finish->Point.x - Start->Point.x;
429  Delta.y = Finish->Point.y - Start->Point.y;
430  if (Delta.x == 0)
431  if (Delta.y < 0) {
432  Start->Slope = -MAX_FLOAT32;
433  Start->Direction = south;
434  }
435  else {
436  Start->Slope = MAX_FLOAT32;
437  Start->Direction = north;
438  }
439  else {
440  Start->Slope = Delta.y / Delta.x;
441  if (Delta.x > 0)
442  if (Delta.y > 0)
443  if (Start->Slope > MinSlope)
444  if (Start->Slope < MaxSlope)
445  Start->Direction = northeast;
446  else
447  Start->Direction = north;
448  else
449  Start->Direction = east;
450  else if (Start->Slope < -MinSlope)
451  if (Start->Slope > -MaxSlope)
452  Start->Direction = southeast;
453  else
454  Start->Direction = south;
455  else
456  Start->Direction = east;
457  else if (Delta.y > 0)
458  if (Start->Slope < -MinSlope)
459  if (Start->Slope > -MaxSlope)
460  Start->Direction = northwest;
461  else
462  Start->Direction = north;
463  else
464  Start->Direction = west;
465  else if (Start->Slope > MinSlope)
466  if (Start->Slope < MaxSlope)
467  Start->Direction = southwest;
468  else
469  Start->Direction = south;
470  else
471  Start->Direction = west;
472  }
473  Finish->PreviousDirection = Start->Direction;
474 } /* ComputeDirection */
475 
476 /*---------------------------------------------------------------------------*/
478 /*
479  ** Parameters:
480  ** EdgePoint start search from this point
481  ** Globals: none
482  ** Operation:
483  ** This routine returns the next point in the micro-feature
484  ** outline that has a direction different than EdgePoint. The
485  ** routine assumes that the outline being searched is not a
486  ** degenerate outline (i.e. it must have 2 or more edge points).
487  ** Return: Point of next direction change in micro-feature outline.
488  ** Exceptions: none
489  ** History: 7/25/89, DSJ, Created.
490  */
491  DIRECTION InitialDirection;
492 
493  InitialDirection = PointAt (EdgePoint)->Direction;
494 
495  MFOUTLINE next_pt = NULL;
496  do {
497  EdgePoint = NextPointAfter(EdgePoint);
498  next_pt = NextPointAfter(EdgePoint);
499  } while (PointAt(EdgePoint)->Direction == InitialDirection &&
500  !PointAt(EdgePoint)->Hidden &&
501  next_pt != NULL && !PointAt(next_pt)->Hidden);
502 
503  return (EdgePoint);
504 } /* NextDirectionChange */
#define NextPointAfter(E)
Definition: mfoutline.h:68
float y() const
Definition: points.h:212
FLOAT32 Slope
Definition: mfoutline.h:41
Definition: fpoint.h:29
FLOAT32 y
Definition: fpoint.h:31
MFEDGEPT * NewEdgePoint()
Definition: mfoutline.cpp:229
void LocalNormTransform(const TPOINT &pt, TPOINT *transformed) const
Definition: normalis.cpp:305
TESSLINE * outlines
Definition: blobs.h:377
MFOUTLINE ConvertOutline(TESSLINE *outline)
Definition: mfoutline.cpp:49
bool IsHidden() const
Definition: blobs.h:153
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:204
void FindDirectionChanges(MFOUTLINE Outline, FLOAT32 MinSlope, FLOAT32 MaxSlope)
Definition: mfoutline.cpp:105
void NormalizeOutline(MFOUTLINE Outline, FLOAT32 XOrigin)
Definition: mfoutline.cpp:260
FPOINT Point
Definition: mfoutline.h:40
LIST MFOUTLINE
Definition: mfoutline.h:33
void MarkDirectionChanges(MFOUTLINE Outline)
Definition: mfoutline.cpp:191
const int kBlnBaselineOffset
Definition: normalis.h:29
void free_struct(void *deadstruct, inT32, const char *)
Definition: memry.cpp:43
#define MAX_FLOAT32
Definition: host.h:124
LIST push(LIST list, void *element)
Definition: oldlist.cpp:323
MFOUTLINE NextDirectionChange(MFOUTLINE EdgePoint)
Definition: mfoutline.cpp:477
TPOINT pos
Definition: blobs.h:163
#define NULL
Definition: host.h:144
TESSLINE * next
Definition: blobs.h:258
LIST pop(LIST list)
Definition: oldlist.cpp:305
#define PointAt(O)
Definition: mfoutline.h:67
LIST ConvertBlob(TBLOB *blob)
Definition: mfoutline.cpp:39
float x() const
Definition: points.h:209
inT16 x
Definition: blobs.h:71
void * alloc_struct(inT32 count, const char *)
Definition: memry.cpp:39
#define list_rest(l)
Definition: oldlist.h:138
#define DegenerateOutline(O)
Definition: mfoutline.h:66
#define ClearMark(P)
Definition: mfoutline.h:72
DIRECTION Direction
Definition: mfoutline.h:45
BOOL8 Hidden
Definition: mfoutline.h:43
#define iterate(l)
Definition: oldlist.h:159
DIRECTION PreviousDirection
Definition: mfoutline.h:46
OUTLINETYPE
Definition: mfoutline.h:49
#define MarkPoint(P)
Definition: mfoutline.h:73
DIRECTION
Definition: mfoutline.h:35
EDGEPT * next
Definition: blobs.h:169
#define NIL_LIST
Definition: oldlist.h:126
void CharNormalizeOutline(MFOUTLINE Outline, const DENORM &cn_denorm)
Definition: mfoutline.cpp:364
void FreeMFOutline(void *arg)
Definition: mfoutline.cpp:148
Definition: points.h:189
#define MakeOutlineCircular(O)
Definition: mfoutline.h:69
void NormalizeOutlines(LIST Outlines, FLOAT32 *XScale, FLOAT32 *YScale)
Definition: mfoutline.cpp:295
void ChangeDirection(MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction)
Definition: mfoutline.cpp:338
void ComputeDirection(MFEDGEPT *Start, MFEDGEPT *Finish, FLOAT32 MinSlope, FLOAT32 MaxSlope)
Definition: mfoutline.cpp:401
Definition: blobs.h:261
FLOAT32 x
Definition: fpoint.h:31
void FreeOutlines(LIST Outlines)
Definition: mfoutline.cpp:175
#define MAX_UINT8
Definition: host.h:121
#define first_node(l)
Definition: oldlist.h:139
#define set_rest(l, cell)
Definition: oldlist.h:222
EDGEPT * loop
Definition: blobs.h:257
MFOUTLINE NextExtremity(MFOUTLINE EdgePoint)
Definition: mfoutline.cpp:235
#define MF_SCALE_FACTOR
Definition: mfoutline.h:63
float FLOAT32
Definition: host.h:111
#define ASSERT_HOST(x)
Definition: errcode.h:84
Definition: mfoutline.h:36
Definition: mfoutline.h:36
LIST ConvertOutlines(TESSLINE *outline, LIST mf_outlines, OUTLINETYPE outline_type)
Definition: mfoutline.cpp:90
Definition: blobs.h:76
inT16 y
Definition: blobs.h:72