mfoutline.cpp File Reference

#include "clusttool.h"
#include "emalloc.h"
#include "mfoutline.h"
#include "blobs.h"
#include "const.h"
#include "mfx.h"
#include "params.h"
#include "classify.h"
#include <math.h>
#include <stdio.h>

Go to the source code of this file.

Namespaces
	tesseract

Macros
#define	MIN_INERTIA   (0.00001)

Functions
LIST	ConvertBlob (TBLOB *blob)
MFOUTLINE	ConvertOutline (TESSLINE *outline)
LIST	ConvertOutlines (TESSLINE *outline, LIST mf_outlines, OUTLINETYPE outline_type)
void	ComputeOutlineStats (LIST Outlines, OUTLINE_STATS *OutlineStats)
void	FindDirectionChanges (MFOUTLINE Outline, FLOAT32 MinSlope, FLOAT32 MaxSlope)
void	FreeMFOutline (void *arg)
void	FreeOutlines (LIST Outlines)
void	MarkDirectionChanges (MFOUTLINE Outline)
MFEDGEPT *	NewEdgePoint ()
MFOUTLINE	NextExtremity (MFOUTLINE EdgePoint)
void	NormalizeOutline (MFOUTLINE Outline, FLOAT32 XOrigin)
void	ChangeDirection (MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction)
void	CharNormalizeOutline (MFOUTLINE Outline, FLOAT32 XCenter, FLOAT32 YCenter, FLOAT32 XScale, FLOAT32 YScale)
void	ComputeDirection (MFEDGEPT *Start, MFEDGEPT *Finish, FLOAT32 MinSlope, FLOAT32 MaxSlope)
void	FinishOutlineStats (register OUTLINE_STATS *OutlineStats)
void	InitOutlineStats (OUTLINE_STATS *OutlineStats)
MFOUTLINE	NextDirectionChange (MFOUTLINE EdgePoint)
void	UpdateOutlineStats (register OUTLINE_STATS *OutlineStats, register FLOAT32 x1, register FLOAT32 x2, register FLOAT32 y1, register FLOAT32 y2)

Macro Definition Documentation

#define MIN_INERTIA   (0.00001)

Definition at line 33 of file mfoutline.cpp.

Function Documentation

void ChangeDirection	(	MFOUTLINE	Start,
		MFOUTLINE	End,
		DIRECTION	Direction
	)

---

Private Code

Definition at line 413 of file mfoutline.cpp.

                                                                          {
/*
 ** Parameters:
 **   Start, End  defines segment of outline to be modified
 **   Direction new direction to assign to segment
 ** Globals: none
 ** Operation: Change the direction of every vector in the specified
 **   outline segment to Direction.  The segment to be changed
 **   starts at Start and ends at End.  Note that the previous
 **   direction of End must also be changed to reflect the
 **   change in direction of the point before it.
 ** Return: none
 ** Exceptions: none
 ** History: Fri May  4 10:42:04 1990, DSJ, Created.
 */
  MFOUTLINE Current;

  for (Current = Start; Current != End; Current = NextPointAfter (Current))
    PointAt (Current)->Direction = Direction;

  PointAt (End)->PreviousDirection = Direction;

}                                /* ChangeDirection */

void CharNormalizeOutline	(	MFOUTLINE	Outline,
		FLOAT32	XCenter,
		FLOAT32	YCenter,
		FLOAT32	XScale,
		FLOAT32	YScale
	)

Definition at line 439 of file mfoutline.cpp.

                                          {
/*
 ** Parameters:
 **   Outline     outline to be character normalized
 **   XCenter, YCenter  center point for normalization
 **   XScale, YScale    scale factors for normalization
 ** Globals: none
 ** Operation: This routine normalizes each point in Outline by
 **   translating it to the specified center and scaling it
 **   anisotropically according to the given scale factors.
 ** Return: none
 ** Exceptions: none
 ** History: Fri Dec 14 10:27:11 1990, DSJ, Created.
 */
  MFOUTLINE First, Current;
  MFEDGEPT *CurrentPoint;

  if (Outline == NIL_LIST)
    return;

  First = Outline;
  Current = First;
  do {
    CurrentPoint = PointAt (Current);
    CurrentPoint->Point.x =
      (CurrentPoint->Point.x - XCenter) * XScale;
    CurrentPoint->Point.y =
      (CurrentPoint->Point.y - YCenter) * YScale;

    Current = NextPointAfter (Current);
  }
  while (Current != First);

}                                /* CharNormalizeOutline */

void ComputeDirection	(	MFEDGEPT *	Start,
		MFEDGEPT *	Finish,
		FLOAT32	MinSlope,
		FLOAT32	MaxSlope
	)

Definition at line 480 of file mfoutline.cpp.

                                        {
/*
 ** Parameters:
 **   Start   starting point to compute direction from
 **   Finish    finishing point to compute direction to
 **   MinSlope  slope below which lines are horizontal
 **   MaxSlope  slope above which lines are vertical
 ** Globals: none
 ** Operation:
 **   This routine computes the slope from Start to Finish and
 **   and then computes the approximate direction of the line
 **   segment from Start to Finish.  The direction is quantized
 **   into 8 buckets:
 **     N, S, E, W, NE, NW, SE, SW
 **   Both the slope and the direction are then stored into
 **   the appropriate fields of the Start edge point.  The
 **   direction is also stored into the PreviousDirection field
 **   of the Finish edge point.
 ** Return: none
 ** Exceptions: none
 ** History: 7/25/89, DSJ, Created.
 */
  FVECTOR Delta;

  Delta.x = Finish->Point.x - Start->Point.x;
  Delta.y = Finish->Point.y - Start->Point.y;
  if (Delta.x == 0)
  if (Delta.y < 0) {
    Start->Slope = -MAX_FLOAT32;
    Start->Direction = south;
  }
  else {
    Start->Slope = MAX_FLOAT32;
    Start->Direction = north;
  }
  else {
    Start->Slope = Delta.y / Delta.x;
    if (Delta.x > 0)
      if (Delta.y > 0)
        if (Start->Slope > MinSlope)
          if (Start->Slope < MaxSlope)
            Start->Direction = northeast;
    else
      Start->Direction = north;
    else
      Start->Direction = east;
    else if (Start->Slope < -MinSlope)
    if (Start->Slope > -MaxSlope)
      Start->Direction = southeast;
    else
      Start->Direction = south;
    else
      Start->Direction = east;
    else if (Delta.y > 0)
    if (Start->Slope < -MinSlope)
      if (Start->Slope > -MaxSlope)
        Start->Direction = northwest;
    else
      Start->Direction = north;
    else
      Start->Direction = west;
    else if (Start->Slope > MinSlope)
    if (Start->Slope < MaxSlope)
      Start->Direction = southwest;
    else
      Start->Direction = south;
    else
      Start->Direction = west;
  }
  Finish->PreviousDirection = Start->Direction;
}                                /* ComputeDirection */

void ComputeOutlineStats	(	LIST	Outlines,
		OUTLINE_STATS *	OutlineStats
	)

Definition at line 108 of file mfoutline.cpp.

                                                                     {
/*
 ** Parameters:
 **   Outlines  list of outlines to compute stats for
 **   OutlineStats  place to put results
 ** Globals: none
 ** Operation: This routine computes several statistics about the outlines
 **   in Outlines.  These statistics are usually used to perform
 **   anistropic normalization of all of the outlines.  The
 **   statistics generated are:
 **     first moments about x and y axes
 **     total length of all outlines
 **     center of mass of all outlines
 **     second moments about center of mass axes
 **     radius of gyration about center of mass axes
 ** Return: none (results are returned in OutlineStats)
 ** Exceptions: none
 ** History: Fri Dec 14 08:32:03 1990, DSJ, Created.
 */
  MFOUTLINE Outline;
  MFOUTLINE EdgePoint;
  MFEDGEPT *Current;
  MFEDGEPT *Last;

  InitOutlineStats(OutlineStats);
  iterate(Outlines) {
    Outline = (MFOUTLINE) first_node (Outlines);

    Last = PointAt (Outline);
    Outline = NextPointAfter (Outline);
    EdgePoint = Outline;
    do {
      Current = PointAt (EdgePoint);

      UpdateOutlineStats (OutlineStats,
        Last->Point.x, Last->Point.y,
        Current->Point.x, Current->Point.y);

      Last = Current;
      EdgePoint = NextPointAfter (EdgePoint);
    }
    while (EdgePoint != Outline);
  }
  FinishOutlineStats(OutlineStats);

}                                /* ComputeOutlineStats */

LIST ConvertBlob

(

TBLOB *

blob

)

Definition at line 41 of file mfoutline.cpp.

                              {
  LIST outlines = NIL_LIST;
  return (blob == NULL)
      ? NIL_LIST
      : ConvertOutlines(blob->outlines, outlines, outer);
}

MFOUTLINE ConvertOutline

(

TESSLINE *

outline

)

Definition at line 51 of file mfoutline.cpp.

                                            {
  MFEDGEPT *NewPoint;
  MFOUTLINE MFOutline = NIL_LIST;
  EDGEPT *EdgePoint;
  EDGEPT *StartPoint;
  EDGEPT *NextPoint;

  if (outline == NULL || outline->loop == NULL)
    return MFOutline;

  StartPoint = outline->loop;
  EdgePoint = StartPoint;
  do {
    NextPoint = EdgePoint->next;

    /* filter out duplicate points */
    if (EdgePoint->pos.x != NextPoint->pos.x ||
        EdgePoint->pos.y != NextPoint->pos.y) {
      NewPoint = NewEdgePoint();
      ClearMark(NewPoint);
      NewPoint->Hidden = EdgePoint->IsHidden();
      NewPoint->Point.x = EdgePoint->pos.x;
      NewPoint->Point.y = EdgePoint->pos.y;
      MFOutline = push(MFOutline, NewPoint);
    }
    EdgePoint = NextPoint;
  } while (EdgePoint != StartPoint);

  if (MFOutline != NULL)
    MakeOutlineCircular(MFOutline);
  return MFOutline;
}

LIST ConvertOutlines	(	TESSLINE *	outline,
		LIST	mf_outlines,
		OUTLINETYPE	outline_type
	)

Definition at line 92 of file mfoutline.cpp.

                                               {
  MFOUTLINE mf_outline;

  while (outline != NULL) {
    mf_outline = ConvertOutline(outline);
    if (mf_outline != NULL)
      mf_outlines = push(mf_outlines, mf_outline);
    outline = outline->next;
  }
  return mf_outlines;
}

void FindDirectionChanges	(	MFOUTLINE	Outline,
		FLOAT32	MinSlope,
		FLOAT32	MaxSlope
	)

Definition at line 157 of file mfoutline.cpp.

                                            {
/*
 ** Parameters:
 **   Outline   micro-feature outline to analyze
 **   MinSlope  controls "snapping" of segments to horizontal
 **   MaxSlope  controls "snapping" of segments to vertical
 ** Globals: none
 ** Operation:
 **   This routine searches thru the specified outline, computes
 **   a slope for each vector in the outline, and marks each
 **   vector as having one of the following directions:
 **     N, S, E, W, NE, NW, SE, SW
 **   This information is then stored in the outline and the
 **   outline is returned.
 ** Return: none
 ** Exceptions: none
 ** History: 7/21/89, DSJ, Created.
 */
  MFEDGEPT *Current;
  MFEDGEPT *Last;
  MFOUTLINE EdgePoint;

  if (DegenerateOutline (Outline))
    return;

  Last = PointAt (Outline);
  Outline = NextPointAfter (Outline);
  EdgePoint = Outline;
  do {
    Current = PointAt (EdgePoint);
    ComputeDirection(Last, Current, MinSlope, MaxSlope);

    Last = Current;
    EdgePoint = NextPointAfter (EdgePoint);
  }
  while (EdgePoint != Outline);

}                                /* FindDirectionChanges */

void FinishOutlineStats

(

register OUTLINE_STATS *

OutlineStats

)

Definition at line 557 of file mfoutline.cpp.

                                                              {
/*
 ** Parameters:
 **   OutlineStats  statistics about a set of outlines
 ** Globals: none
 ** Operation: Use the preliminary statistics accumulated in OutlineStats
 **   to compute the final statistics.
 **   (see Dan Johnson's Tesseract lab
 **   notebook #2, pgs. 74-78).
 ** Return: none
 ** Exceptions: none
 ** History: Fri Dec 14 10:13:36 1990, DSJ, Created.
 */
  OutlineStats->x = 0.5 * OutlineStats->My / OutlineStats->L;
  OutlineStats->y = 0.5 * OutlineStats->Mx / OutlineStats->L;

  OutlineStats->Ix = (OutlineStats->Ix / 3.0 -
    OutlineStats->y * OutlineStats->Mx +
    OutlineStats->y * OutlineStats->y * OutlineStats->L);

  OutlineStats->Iy = (OutlineStats->Iy / 3.0 -
    OutlineStats->x * OutlineStats->My +
    OutlineStats->x * OutlineStats->x * OutlineStats->L);

  /* Ix and/or Iy could possibly be negative due to roundoff error */
  if (OutlineStats->Ix < 0.0)
    OutlineStats->Ix = MIN_INERTIA;
  if (OutlineStats->Iy < 0.0)
    OutlineStats->Iy = MIN_INERTIA;

  OutlineStats->Rx = sqrt (OutlineStats->Ix / OutlineStats->L);
  OutlineStats->Ry = sqrt (OutlineStats->Iy / OutlineStats->L);

  OutlineStats->Mx *= 0.5;
  OutlineStats->My *= 0.5;

}                                /* FinishOutlineStats */

void FreeMFOutline

(

void *

arg

)

Definition at line 200 of file mfoutline.cpp.

                              {  //MFOUTLINE                             Outline)
/*
 ** Parameters:
 **   Outline   micro-feature outline to be freed
 ** Globals: none
 ** Operation:
 **   This routine deallocates all of the memory consumed by
 **   a micro-feature outline.
 ** Return: none
 ** Exceptions: none
 ** History: 7/27/89, DSJ, Created.
 */
  MFOUTLINE Start;
  MFOUTLINE Outline = (MFOUTLINE) arg;

  /* break the circular outline so we can use std. techniques to deallocate */
  Start = list_rest (Outline);
  set_rest(Outline, NIL_LIST);
  while (Start != NULL) {
    free_struct (first_node (Start), sizeof (MFEDGEPT), "MFEDGEPT");
    Start = pop (Start);
  }

}                                /* FreeMFOutline */

void FreeOutlines

(

LIST

Outlines

)

Definition at line 227 of file mfoutline.cpp.

                                 {
/*
 ** Parameters:
 **   Outlines  list of mf-outlines to be freed
 ** Globals: none
 ** Operation: Release all memory consumed by the specified list
 **   of outlines.
 ** Return: none
 ** Exceptions: none
 ** History: Thu Dec 13 16:14:50 1990, DSJ, Created.
 */
  destroy_nodes(Outlines, FreeMFOutline);
}                                /* FreeOutlines */

void InitOutlineStats

(

OUTLINE_STATS *

OutlineStats

)

Definition at line 597 of file mfoutline.cpp.

                                                   {
/*
 ** Parameters:
 **   OutlineStats  stats data structure to be initialized
 ** Globals: none
 ** Operation: Initialize the outline statistics data structure so
 **   that it is ready to start accumulating statistics.
 ** Return: none
 ** Exceptions: none
 ** History: Fri Dec 14 08:55:22 1990, DSJ, Created.
 */
  OutlineStats->Mx = 0.0;
  OutlineStats->My = 0.0;
  OutlineStats->L = 0.0;
  OutlineStats->x = 0.0;
  OutlineStats->y = 0.0;
  OutlineStats->Ix = 0.0;
  OutlineStats->Iy = 0.0;
  OutlineStats->Rx = 0.0;
  OutlineStats->Ry = 0.0;
}                                /* InitOutlineStats */

void MarkDirectionChanges

(

MFOUTLINE

Outline

)

Definition at line 243 of file mfoutline.cpp.

                                             {
/*
 ** Parameters:
 **   Outline   micro-feature outline to analyze
 ** Globals: none
 ** Operation:
 **   This routine searches thru the specified outline and finds
 **   the points at which the outline changes direction.  These
 **   points are then marked as "extremities".  This routine is
 **   used as an alternative to FindExtremities().  It forces the
 **   endpoints of the microfeatures to be at the direction
 **   changes rather than at the midpoint between direction
 **   changes.
 ** Return: none
 ** Exceptions: none
 ** History: 6/29/90, DSJ, Created.
 */
  MFOUTLINE Current;
  MFOUTLINE Last;
  MFOUTLINE First;

  if (DegenerateOutline (Outline))
    return;

  First = NextDirectionChange (Outline);
  Last = First;
  do {
    Current = NextDirectionChange (Last);
    MarkPoint (PointAt (Current));
    Last = Current;
  }
  while (Last != First);

}                                /* MarkDirectionChanges */

MFEDGEPT* NewEdgePoint

(

)

Definition at line 281 of file mfoutline.cpp.

                         {
  return ((MFEDGEPT *) alloc_struct(sizeof(MFEDGEPT), "MFEDGEPT"));
}

MFOUTLINE NextDirectionChange

(

MFOUTLINE

EdgePoint

)

Definition at line 621 of file mfoutline.cpp.

                                                   {
/*
 ** Parameters:
 **   EdgePoint start search from this point
 ** Globals: none
 ** Operation:
 **   This routine returns the next point in the micro-feature
 **   outline that has a direction different than EdgePoint.  The
 **   routine assumes that the outline being searched is not a
 **   degenerate outline (i.e. it must have 2 or more edge points).
 ** Return: Point of next direction change in micro-feature outline.
 ** Exceptions: none
 ** History: 7/25/89, DSJ, Created.
 */
  DIRECTION InitialDirection;

  InitialDirection = PointAt (EdgePoint)->Direction;

  MFOUTLINE next_pt = NULL;
  do {
    EdgePoint = NextPointAfter(EdgePoint);
    next_pt = NextPointAfter(EdgePoint);
  } while (PointAt(EdgePoint)->Direction == InitialDirection &&
           !PointAt(EdgePoint)->Hidden &&
           next_pt != NULL && !PointAt(next_pt)->Hidden);

  return (EdgePoint);
}                                /* NextDirectionChange */

MFOUTLINE NextExtremity

(

MFOUTLINE

EdgePoint

)

Definition at line 287 of file mfoutline.cpp.

                                             {
/*
 ** Parameters:
 **   EdgePoint start search from this point
 ** Globals: none
 ** Operation:
 **   This routine returns the next point in the micro-feature
 **   outline that is an extremity.  The search starts after
 **   EdgePoint.  The routine assumes that the outline being
 **   searched is not a degenerate outline (i.e. it must have
 **   2 or more edge points).
 ** Return: Next extremity in the outline after EdgePoint.
 ** Exceptions: none
 ** History: 7/26/89, DSJ, Created.
 */
  EdgePoint = NextPointAfter(EdgePoint);
  while (!PointAt(EdgePoint)->ExtremityMark)
    EdgePoint = NextPointAfter(EdgePoint);

  return (EdgePoint);

}                                /* NextExtremity */

void NormalizeOutline	(	MFOUTLINE	Outline,
		FLOAT32	XOrigin
	)

Definition at line 312 of file mfoutline.cpp.

                                       {
/*
 ** Parameters:
 **   Outline   outline to be normalized
 **   XOrigin   x-origin of text
 ** Globals: none
 ** Operation:
 **   This routine normalizes the coordinates of the specified
 **   outline so that the outline is deskewed down to the
 **   baseline, translated so that x=0 is at XOrigin, and scaled
 **   so that the height of a character cell from descender to
 **   ascender is 1.  Of this height, 0.25 is for the descender,
 **   0.25 for the ascender, and 0.5 for the x-height.  The
 **   y coordinate of the baseline is 0.
 ** Return: none
 ** Exceptions: none
 ** History: 8/2/89, DSJ, Created.
 */
  if (Outline == NIL_LIST)
    return;

  MFOUTLINE EdgePoint = Outline;
  do {
    MFEDGEPT *Current = PointAt(EdgePoint);
    Current->Point.y = MF_SCALE_FACTOR * (Current->Point.y - BASELINE_OFFSET);
    Current->Point.x = MF_SCALE_FACTOR * (Current->Point.x - XOrigin);
    EdgePoint = NextPointAfter(EdgePoint);
  } while (EdgePoint != Outline);
}                                /* NormalizeOutline */

void UpdateOutlineStats	(	register OUTLINE_STATS *	OutlineStats,
		register FLOAT32	x1,
		register FLOAT32	x2,
		register FLOAT32	y1,
		register FLOAT32	y2
	)

Definition at line 652 of file mfoutline.cpp.

                                             {
/*
 ** Parameters:
 **   OutlineStats  statistics to add this segment to
 **   x1, y1, x2, y2  segment to be added to statistics
 ** Globals: none
 ** Operation: This routine adds the statistics for the specified
 **   line segment to OutlineStats.  The statistics that are
 **   kept are:
 **     sum of length of all segments
 **     sum of 2*Mx for all segments
 **     sum of 2*My for all segments
 **     sum of 2*Mx*(y1+y2) - L*y1*y2 for all segments
 **     sum of 2*My*(x1+x2) - L*x1*x2 for all segments
 **   These numbers, once collected can later be used to easily
 **   compute the center of mass, first and second moments,
 **   and radii of gyration.  (see Dan Johnson's Tesseract lab
 **   notebook #2, pgs. 74-78).
 ** Return: none
 ** Exceptions: none
 ** History: Fri Dec 14 08:59:17 1990, DSJ, Created.
 */
  register FLOAT64 L;
  register FLOAT64 Mx2;
  register FLOAT64 My2;

  /* compute length of segment */
  L = sqrt ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
  OutlineStats->L += L;

  /* compute 2Mx and 2My components */
  Mx2 = L * (y1 + y2);
  My2 = L * (x1 + x2);
  OutlineStats->Mx += Mx2;
  OutlineStats->My += My2;

  /* compute second moment component */
  OutlineStats->Ix += Mx2 * (y1 + y2) - L * y1 * y2;
  OutlineStats->Iy += My2 * (x1 + x2) - L * x1 * x2;

}                                /* UpdateOutlineStats */