freemandet.cc

手写识别是模式识别中研究得一个热点

//
// FreemanDet - the freeman vector quantization detector. It reads the raw data
//  and inserts markers for the end of freeman vectors (only pen down data 
//  points are processed.
// Input - reads HWRawDataC records from standard in.
// Output - writes HWRawDataC records to standard out w/ freeman events.
// Notes - 0,0 is the data point in the upper left of the tablet/screen.
//

// System Include Files.
#include <SLList.h>
#include <math.h>
#include <stdlib.h>

// Local Include Files.
#include "HWRawDataC.hh"

// Manifest Constants.
#define TOLERANCE 3
#define KEEP_LAST_POINT 1
#define KILL_LAST_POINT 0

// Prototypes.
float GetDeviationFromLine(SLList<HWDataPointC>&, HWDataPointC);
void OutputVectorMarker(SLList<HWDataPointC>&, long, int);
int GetFreemanDirection(HWDataPointC A, HWDataPointC B);
HWDataPointC GetNearestPoint(HWDataPointC A, HWDataPointC B, HWDataPointC C);
float GetDistanceBetween(HWDataPointC A, HWDataPointC B);
float GetSlope(HWDataPointC A, HWDataPointC B);
int GetYIntersect(HWDataPointC A, float Slope);

// Global Variables


int main(int argc, char *argv[])
{
  SLList<HWDataPointC> PointList;

  // Read off the header and put it back on the output stream.
  HWHeaderC Header;
  cin >> Header;
  cout << Header;

  // Process all of the data points.
  int PenDown = 0;
  HWRawDataC HWRawData;
  while(!!(cin >> HWRawData))
    {
      switch(HWRawData.Type)
	{
	case DATA_RECORD:			// Data point.
	  // Process points only if pen is down.
	  if (PenDown)
	    {
	      // Check if enough points in the list to process.
	      HWDataPointC NewPoint = HWRawData.DataPoint;
	      if (PointList.length() > 0)
		{
		  float NewVectorLength = 
		    GetDistanceBetween(PointList.front(), NewPoint);

		  // Determine if we should output before we add.
		  if (GetDeviationFromLine(PointList, NewPoint) 
		      > NewVectorLength/TOLERANCE)
		    {
		      // Output the vectors end point marker.
		      OutputVectorMarker(PointList, 
					 HWRawData.Time,
					 KEEP_LAST_POINT);
		    }
		}

	      // Append the new input point to the list.
	      PointList.append(NewPoint);
	    }
	  break;
	case PEN_DOWN:			// Pen down Event.
	  cerr << "Pen down\n";
	  PenDown = 1;
	  break;
	case PEN_UP:			// Pen up Event.
	  // Output what ever vector is in the list (if its long enough)
	  // and clear it.
	  cerr << "Pen Up\n";
	  PenDown = 0;
	  OutputVectorMarker(PointList, HWRawData.Time, KILL_LAST_POINT);
	  break;
	default:
	  cerr << "Unknown data type " << HWRawData.Type << "\n";
	  break;
	}

      // Pass through all of the original data points.
      cout << HWRawData;
    }
}


//
// OutputVectorMarker() - used to print place a vector marker on standard out
//  and clear the point list of all entries but the last one (the start of 
//  the next vector).
//
void OutputVectorMarker(SLList<HWDataPointC>& List, long Time, int KeepLast)
{
  // Only output if there's at least two points (fire wall).
  if (List.length() > 1)
    {
      // Figure out what vector we have in the list.
      int FreemanVect = GetFreemanDirection(List.front(), List.rear());
      float FreemanLength = GetDistanceBetween(List.front(), List.rear());

      cerr << "Detected Freeman vector " << FreemanVect << " from "
	<< List.front() << " to " << List.rear() << "\n";

      // Output the vector marker with time equal to the end of it.
      HWRawDataC VectorMarker;
      VectorMarker.Time = Time;
      VectorMarker.Type = FreemanVect+FREEMAN_0;
      cout << VectorMarker;
      
      // Clear the list of all except the last point (start
      // of next vector).
      HWDataPointC TempPoint = List.rear();
      List.clear();
      if (KeepLast)
	List.append(TempPoint);
    }
}

//
// GetDeviationFromLine() - returns the total deviation between a line from
//  the point at the head of the list to the new point and all of the points
//  in the list (the first and last points deviate by zero).
//
float GetDeviationFromLine(SLList<HWDataPointC>& PointList, 
			   HWDataPointC NewPoint)
{
  // If there is less than 3 points in the list the deviation is zero.
  if (PointList.length() < 3)
    return(0);

  // Process the entire list accumulating the total distance from the
  // liine to each point.
  Pix ListPointer = PointList.first();
  float TotalDev = 0;
  while(ListPointer != NULL)
    {
      HWDataPointC TempPoint = PointList(ListPointer);
      HWDataPointC PointOnLine = 
	GetNearestPoint(PointList.front(),NewPoint,TempPoint);
      float Distance = GetDistanceBetween(TempPoint, PointOnLine);
      TotalDev += Distance;
      PointList.next(ListPointer);
    }
  return(TotalDev);
}


//
// GetFreemanDirection() - used to determine the direction of a line 
//  bewteen two points in terms of the seven freeman vectors directions.
//
// Freeman irections:
//
//        3   2   1
//         \  |  /
//          \ | /
//        4-- + --0
//          / | \
//         /  |  \
//        5   6   7
//
// Data File Coordinate System:
//
// 0,0 ---------------- 6000,0
//  |                     |
//  |                     |
//  |                     |
//  |                     |
// 0,6000 ----------- 6000,6000
//
// Vector Slopes Based on above coordinate system:
//
//        1   0   -1
//         \  |  /
//          \ | /
//   (-inf)-- + --(inf)
//          / | \
//         /  |  \
//       -1   0   1
// 
int GetFreemanDirection(HWDataPointC A, HWDataPointC B)
{
  // Check for horiz line.
  if (A.YPos == B.YPos)
    {
      // Check for rightwards.
      if (A.XPos <= B.XPos)
	return(0);
      else
	return(4);
    }

  // Now check the normal cases.
  float Slope = (B.XPos-A.XPos)/(B.YPos-A.YPos);

  if ((Slope <= -2 || Slope > 2) && (A.XPos < B.XPos))
    return(0);
  else if ((Slope > -2 && Slope <= -0.5) && (A.XPos < B.XPos))
    return(1);
  else if ((Slope > -0.5 && Slope <= 0.5) && (A.YPos > B.YPos))
    return(2);
  else if ((Slope > 0.5 && Slope <= 2) && (A.YPos > B.YPos))
    return(3);

  else if ((Slope <= -2 || Slope > 2) && (A.XPos > B.XPos))
    return(4);
  else if ((Slope > -2 && Slope <= -0.5) && (A.XPos > B.XPos))
    return(5);
  else if ((Slope > -0.5 && Slope <= 0.5) && (A.YPos < B.YPos))
    return(6);
  else if ((Slope > 0.5 && Slope <= 2) && (A.YPos < B.YPos))
    return(7);
  else return(-666);
}


//
// GetNearestPoint - returns the point on the line between point A and 
//  point B nearest to the point C.
//
HWDataPointC GetNearestPoint(HWDataPointC A, HWDataPointC B, HWDataPointC C)
{
  HWDataPointC NearestPoint;

  // Check if line is horizontal (Y axis constant).
  if (A.YPos == B.YPos)
    {
      // Line is horizontal.
      NearestPoint.YPos = A.YPos;
      NearestPoint.XPos = B.XPos;
      return(NearestPoint);
    }

  // Check if line is vertical (X axis constant).
  if (A.XPos == B.XPos)
    {
      // Line is vertical.
      NearestPoint.XPos = A.XPos;
      NearestPoint.YPos = B.YPos;
      return(NearestPoint);
    }

  // Line must have a real slope.
  float Slope = GetSlope(A, B);
//  cerr << "Slope from " << A << " to " << B << " is " << Slope << "\n";

  int YIntersect = GetYIntersect(A, Slope);
//  cerr << "Y Intersect is " << YIntersect << "\n";

  NearestPoint.XPos = 
    (int)((float)(-1*Slope*YIntersect + C.XPos + Slope*C.YPos)/(float)((Slope*Slope)+1));
  NearestPoint.YPos = (int)(Slope*NearestPoint.XPos+YIntersect);

//  cerr << "Nearest Point to " << C << " is " << NearestPoint << "\n";

  return(NearestPoint);
}


//
// GetDistanceBetween - returns the distance between points A and B.
//
float GetDistanceBetween(HWDataPointC A, HWDataPointC B)
{
  return(sqrt( pow((double)abs(A.XPos-B.XPos),2) + 
	      pow((double)abs(A.YPos-B.YPos), 2) ));
}


//
// GetSlope - returns the slope of a line between point A and point B.
// Notes - returns 0 if the slope is zero or if the slope is infinite, so
//  the caller should check for these first.
//
float GetSlope(HWDataPointC A, HWDataPointC B)
{
  float Slope;

  if (B.XPos-A.XPos == 0)
    return(0);

  Slope = (float)(B.YPos-A.YPos)/(float)(B.XPos-A.XPos);
  return(Slope);
}


//
// GetYIntersect - returns the Y-intersect of a line through A with 
//  direction equal to Slope.
// Notes - this function does not consider horizontal or vertical lines, the
//  caller SHOULD check the Slope before calling.
//
int GetYIntersect(HWDataPointC A, float Slope)
{
  // b = y - mx.
  return(A.YPos-(int)(Slope*A.XPos));
}