/******************************************************************************
** Filename: MergeNF.c
** Purpose: Program for merging similar nano-feature protos
** Author: Dan Johnson
** History: Wed Nov 21 09:55:23 1990, DSJ, Created.
**
** (c) Copyright Hewlett-Packard Company, 1988.
** Licensed under the Apache License, Version 2.0 (the "License");
** you may not use this file except in compliance with the License.
** You may obtain a copy of the License at
** http://www.apache.org/licenses/LICENSE-2.0
** Unless required by applicable law or agreed to in writing, software
** distributed under the License is distributed on an "AS IS" BASIS,
** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
** See the License for the specific language governing permissions and
** limitations under the License.
******************************************************************************/
/**----------------------------------------------------------------------------
Include Files and Type Defines
----------------------------------------------------------------------------**/
#include "mergenf.h"
#include "general.h"
#include "efio.h"
#include "clusttool.h"
#include "cluster.h"
#include "oldlist.h"
#include "protos.h"
#include "ndminx.h"
#include "ocrfeatures.h"
#include "const.h"
#include "featdefs.h"
#include "intproto.h"
#include "varable.h"
#include <stdio.h>
#include <string.h>
#include <math.h>
/**----------------------------------------------------------------------------
Variables
-----------------------------------------------------------------------------**/
/*-------------------once in subfeat---------------------------------*/
double_VAR(training_angle_match_scale, 1.0, "Angle Match Scale ...");
double_VAR(training_similarity_midpoint, 0.0075, "Similarity Midpoint ...");
double_VAR(training_similarity_curl, 2.0, "Similarity Curl ...");
/*-----------------------------once in fasttrain----------------------------------*/
double_VAR(training_tangent_bbox_pad, 0.5, "Tangent bounding box pad ...");
double_VAR(training_orthogonal_bbox_pad, 2.5, "Orthogonal bounding box pad ...");
double_VAR(training_angle_pad, 45.0, "Angle pad ...");
/**----------------------------------------------------------------------------
Global Data Definitions and Declarations
----------------------------------------------------------------------------**/
//int row_number; /* kludge due to linking problems */
/**----------------------------------------------------------------------------
Public Code
----------------------------------------------------------------------------**/
/*---------------------------------------------------------------------------*/
FLOAT32 CompareProtos(PROTO p1, PROTO p2) {
/*
** Parameters:
** p1, p2 protos to be compared
** Globals: none
** Operation: Compare protos p1 and p2 and return an estimate of the
** worst evidence rating that will result for any part of p1
** that is compared to p2. In other words, if p1 were broken
** into pico-features and each pico-feature was matched to p2,
** what is the worst evidence rating that will be achieved for
** any pico-feature.
** Return: Worst possible result when matching p1 to p2.
** Exceptions: none
** History: Mon Nov 26 08:27:53 1990, DSJ, Created.
*/
FEATURE Feature;
FLOAT32 WorstEvidence = WORST_EVIDENCE;
FLOAT32 Evidence;
FLOAT32 Angle, Length;
/* if p1 and p2 are not close in length, don't let them match */
Length = fabs (p1->Length - p2->Length);
if (Length > MAX_LENGTH_MISMATCH)
return (0.0);
/* create a dummy pico-feature to be used for comparisons */
Feature = NewFeature (&PicoFeatDesc);
Feature->Params[PicoFeatDir] = p1->Angle;
/* convert angle to radians */
Angle = p1->Angle * 2.0 * PI;
/* find distance from center of p1 to 1/2 picofeat from end */
Length = p1->Length / 2.0 - GetPicoFeatureLength () / 2.0;
if (Length < 0) Length = 0;
/* set the dummy pico-feature at one end of p1 and match it to p2 */
Feature->Params[PicoFeatX] = p1->X + cos (Angle) * Length;
Feature->Params[PicoFeatY] = p1->Y + sin (Angle) * Length;
if (DummyFastMatch (Feature, p2)) {
Evidence = SubfeatureEvidence (Feature, p2);
if (Evidence < WorstEvidence)
WorstEvidence = Evidence;
} else {
FreeFeature (Feature);
return 0.0;
}
/* set the dummy pico-feature at the other end of p1 and match it to p2 */
Feature->Params[PicoFeatX] = p1->X - cos (Angle) * Length;
Feature->Params[PicoFeatY] = p1->Y - sin (Angle) * Length;
if (DummyFastMatch (Feature, p2)) {
Evidence = SubfeatureEvidence (Feature, p2);
if (Evidence < WorstEvidence)
WorstEvidence = Evidence;
} else {
FreeFeature (Feature);
return 0.0;
}
FreeFeature (Feature);
return (WorstEvidence);
} /* CompareProtos */
/*---------------------------------------------------------------------------*/
void ComputeMergedProto (
PROTO p1,
PROTO p2,
FLOAT32 w1,
FLOAT32 w2,
PROTO MergedProto)
/*
** Parameters:
** p1, p2 protos to be merged
** w1, w2 weight of each proto
** MergedProto place to put resulting merged proto
** Globals: none
** Operation: This routine computes a proto which is the weighted
** average of protos p1 and p2. The new proto is returned
** in MergedProto.
** Return: none (results are returned in MergedProto)
** Exceptions: none
** History: Mon Nov 26 08:15:08 1990, DSJ, Created.
*/
{
FLOAT32 TotalWeight;
TotalWeight = w1 + w2;
w1 /= TotalWeight;
w2 /= TotalWeight;
MergedProto->X = p1->X * w1 + p2->X * w2;
MergedProto->Y = p1->Y * w1 + p2->Y * w2;
MergedProto->Length = p1->Length * w1 + p2->Length * w2;
MergedProto->Angle = p1->Angle * w1 + p2->Angle * w2;
FillABC (MergedProto);
} /* ComputeMergedProto */
/*---------------------------------------------------------------------------*/
int FindClosestExistingProto(CLASS_TYPE Class, int NumMerged[],
PROTOTYPE *Prototype) {
/*
** Parameters:
** Class class to search for matching old proto in
** NumMerged[] # of protos merged into each proto of Class
** Prototype new proto to find match for
** Globals: none
** Operation: This routine searches thru all of the prototypes in
** Class and returns the id of the proto which would provide
** the best approximation of Prototype. If no close
** approximation can be found, NO_PROTO is returned.
** Return: Id of closest proto in Class or NO_PROTO.
** Exceptions: none
** History: Sat Nov 24 11:42:58 1990, DSJ, Created.
*/
PROTO_STRUCT NewProto;
PROTO_STRUCT MergedProto;
int Pid;
PROTO Proto;
int BestProto;
FLOAT32 BestMatch;
FLOAT32 Match, OldMatch, NewMatch;
MakeNewFromOld (&NewProto, Prototype);
BestProto = NO_PROTO;
BestMatch = WORST_MATCH_ALLOWED;
for (Pid = 0; Pid < Class->NumProtos; Pid++) {
Proto = ProtoIn (Class, Pid);
ComputeMergedProto (Proto, &NewProto,
(FLOAT32) NumMerged[Pid], 1.0, &MergedProto);
OldMatch = CompareProtos (Proto, &MergedProto);
NewMatch = CompareProtos (&NewProto, &MergedProto);
Match = MIN (OldMatch, NewMatch);
if (Match > BestMatch) {
BestProto = Pid;
BestMatch = Match;
}
}
return BestProto;
} /* FindClosestExistingProto */
/*---------------------------------------------------------------------------*/
void MakeNewFromOld(PROTO New, PROTOTYPE *Old) {
/*
** Parameters:
** New new proto to be filled in
** Old old proto to be converted
** Globals: none
** Operation: This fills in the fields of the New proto based on the
** fields of the Old proto.
** Return: none
** Exceptions: none
** History: Mon Nov 26 09:45:39 1990, DSJ, Created.
*/
New->X = CenterX(Old->Mean);
New->Y = CenterY(Old->Mean);
New->Length = LengthOf(Old->Mean);
New->Angle = OrientationOf(Old->Mean);
FillABC (New);
} /* MakeNewFromOld */
/*-------------------once in subfeat---------------------------------*/
/**********************************************************************
* SubfeatureEvidence
*
* Compare a feature to a prototype. Print the result.
**********************************************************************/
FLOAT32 SubfeatureEvidence(FEATURE Feature, PROTO Proto) {
float Distance;
float Dangle;
Dangle = Proto->Angle - Feature->Params[PicoFeatDir];
if (Dangle < -0.5) Dangle += 1.0;
if (Dangle > 0.5) Dangle -= 1.0;
Dangle *= training_angle_match_scale;
Distance = Proto->A * Feature->Params[PicoFeatX] +
Proto->B * Feature->Params[PicoFeatY] +
Proto->C;
return (EvidenceOf (Distance * Distance + Dangle * Dangle));
}
/**********************************************************************
* EvidenceOf
*
* Return the new type of evidence number corresponding to this
* distance value. This number is no longer based on the chi squared
* approximation. The equation that represents the transform is:
* 1 / (1 + (sim / midpoint) ^ curl)
**********************************************************************/
FLOAT32 EvidenceOf (
register FLOAT32 Similarity)
{
Similarity /= training_similarity_midpoint;
if (training_similarity_curl == 3)
Similarity = Similarity * Similarity * Similarity;
else if (training_similarity_curl == 2)
Similarity = Similarity * Similarity;
else
Similarity = static_cast<float>(pow(static_cast<double>(Similarity),
training_similarity_curl));
return (1.0 / (1.0 + Similarity));
}
/*---------------------------------------------------------------------------*/
BOOL8 DummyFastMatch (
FEATURE Feature,
PROTO Proto)
/*
** Parameters:
** Feature feature to be "fast matched" to proto
** Proto proto being "fast matched" against
** Globals:
** training_tangent_bbox_pad bounding box pad tangent to proto
** training_orthogonal_bbox_pad bounding box pad orthogonal to proto
** Operation: This routine returns TRUE if Feature would be matched
** by a fast match table built from Proto.
** Return: TRUE if feature could match Proto.
** Exceptions: none
** History: Wed Nov 14 17:19:58 1990, DSJ, Created.
*/
{
FRECT BoundingBox;
FLOAT32 MaxAngleError;
FLOAT32 AngleError;
MaxAngleError = training_angle_pad / 360.0;
AngleError = fabs (Proto->Angle - Feature->Params[PicoFeatDir]);
if (AngleError > 0.5)
AngleError = 1.0 - AngleError;
if (AngleError > MaxAngleError)
return (FALSE);
ComputePaddedBoundingBox (Proto,
training_tangent_bbox_pad * GetPicoFeatureLength (),
training_orthogonal_bbox_pad * GetPicoFeatureLength (),
&BoundingBox);
return PointInside(&BoundingBox, Feature->Params[PicoFeatX],
Feature->Params[PicoFeatY]);
} /* DummyFastMatch */
/*----------------------------------------------------------------------------*/
void ComputePaddedBoundingBox (PROTO Proto, FLOAT32 TangentPad,
FLOAT32 OrthogonalPad, FRECT *BoundingBox) {
/*
** Parameters:
** Proto proto to compute bounding box for
** TangentPad amount of pad to add in direction of segment
** OrthogonalPad amount of pad to add orthogonal to segment
** BoundingBox place to put results
** Globals: none
** Operation: This routine computes a bounding box that encloses the
** specified proto along with some padding. The
** amount of padding is specified as separate distances
** in the tangential and orthogonal directions.
** Return: none (results are returned in BoundingBox)
** Exceptions: none
** History: Wed Nov 14 14:55:30 1990, DSJ, Created.
*/
FLOAT32 Pad, Length, Angle;
FLOAT32 CosOfAngle, SinOfAngle;
Length = Proto->Length / 2.0 + TangentPad;
Angle = Proto->Angle * 2.0 * PI;
CosOfAngle = fabs (cos (Angle));
SinOfAngle = fabs (sin (Angle));
Pad = MAX (CosOfAngle * Length, SinOfAngle * OrthogonalPad);
BoundingBox->MinX = Proto->X - Pad;
BoundingBox->MaxX = Proto->X + Pad;
Pad = MAX (SinOfAngle * Length, CosOfAngle * OrthogonalPad);
BoundingBox->MinY = Proto->Y - Pad;
BoundingBox->MaxY = Proto->Y + Pad;
} /* ComputePaddedBoundingBox */
/*--------------------------------------------------------------------------*/
BOOL8 PointInside(FRECT *Rectangle, FLOAT32 X, FLOAT32 Y) {
/*
** Parameters:
** Globals: none
** Operation: Return TRUE if point (X,Y) is inside of Rectangle.
** Return: Return TRUE if point (X,Y) is inside of Rectangle.
** Exceptions: none
** History: Wed Nov 14 17:26:35 1990, DSJ, Created.
*/
if (X < Rectangle->MinX) return (FALSE);
if (X > Rectangle->MaxX) return (FALSE);
if (Y < Rectangle->MinY) return (FALSE);
if (Y > Rectangle->MaxY) return (FALSE);
return (TRUE);
} /* PointInside */