/****************************************************************************** ** 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 #include #include /**---------------------------------------------------------------------------- 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(pow(static_cast(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 */