bestfirst.cpp

一ＯＣＲ的相关资料。．希望对研究ＯＣＲ的朋友有所帮助．

/* -*-C-*-
 ********************************************************************************
 *
 * File:        bestfirst.c  (Formerly bestfirst.c)
 * Description:  Best first search functions
 * Author:       Mark Seaman, OCR Technology
 * Created:      Mon May 14 11:23:29 1990
 * Modified:     Tue Jul 30 16:08:47 1991 (Mark Seaman) marks@hpgrlt
 * Language:     C
 * Package:      N/A
 * Status:       Experimental (Do Not Distribute)
 *
 * (c) Copyright 1990, Hewlett-Packard Company.
 ** 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.
 *
 ***************************************************************************/

/*----------------------------------------------------------------------
          I n c l u d e s
---------------------------------------------------------------------*/
#include "bestfirst.h"
#include "heuristic.h"
#include "plotseg.h"
#include "tordvars.h"
#include "debug.h"
#include "pieces.h"
#include "stopper.h"
#include "metrics.h"
#include "states.h"
#include "bitvec.h"
#include "freelist.h"
#include "permute.h"
#include "structures.h"
#include "wordclass.h"

void call_caller(); 

/*----------------------------------------------------------------------
          V a r i a b l e s
---------------------------------------------------------------------*/
int num_joints;                  /* Number of chunks - 1 */
int num_pushed = 0;
int num_popped = 0;

make_int_var (num_seg_states, 30, make_seg_states,
9, 1, set_seg_states, "Segmentation states");

make_float_var (worst_state, 1, make_worst_state,
9, 9, set_worst_state, "Worst segmentation state");
/**/
/*----------------------------------------------------------------------
          F u n c t i o n s
----------------------------------------------------------------------*/
/**********************************************************************
 * init_bestfirst_vars
 *
 * Create and initialize references to debug variables that control
 * operations in this file.
 **********************************************************************/
void init_bestfirst_vars() { 
  make_seg_states(); 
  make_worst_state(); 
}


/**********************************************************************
 * best_first_search
 *
 * Find the best segmentation by doing a best first search of the
 * solution space.
 **********************************************************************/
void best_first_search(CHUNKS_RECORD *chunks_record,
                       A_CHOICE *best_choice,
                       A_CHOICE *raw_choice,
                       STATE *state,
                       DANGERR *fixpt,
                       STATE *best_state,
                       INT32 pass) {
  SEARCH_RECORD *the_search;
  INT16 keep_going;
  STATE guided_state;

  num_joints = matrix_dimension (chunks_record->ratings) - 1;
  the_search = new_search (chunks_record, num_joints,
    best_choice, raw_choice, state);

#ifndef GRAPHICS_DISABLED
  save_best_state(chunks_record); 
#endif
  start_recording(); 

  guided_state = *state;
  do {
                                 /* Look for answer */
    if (!hash_lookup (the_search->closed_states, the_search->this_state)) {

      if (blob_skip) {
        free_state (the_search->this_state);
        break;
      }

      guided_state = *(the_search->this_state);
      keep_going =
        evaluate_state(chunks_record, the_search, fixpt, best_state, pass); 

      hash_add (the_search->closed_states, the_search->this_state);

      if (!keep_going ||
      (the_search->num_states > num_seg_states) || (blob_skip)) {
        free_state (the_search->this_state);
        break;
      }

      expand_node(chunks_record, the_search); 
    }

    free_state (the_search->this_state);
    num_popped++;
    the_search->this_state = pop_queue (the_search->open_states);
  }
  while (the_search->this_state);

  state->part1 = the_search->best_state->part1;
  state->part2 = the_search->best_state->part2;
  stop_recording(); 
  delete_search(the_search); 
}


/**********************************************************************
 * chunks_width
 *
 * Return the width of several of the chunks (if they were joined to-
 * gether.
 **********************************************************************/
int chunks_width(WIDTH_RECORD *width_record, int start_chunk, int last_chunk) { 
  int result = 0;
  int x;

  for (x = start_chunk * 2; x <= last_chunk * 2; x++)
    result += width_record->widths[x];

  return (result);
}


/**********************************************************************
 * delete_search
 *
 * Terminate the current search and free all the memory involved.
 **********************************************************************/
void delete_search(SEARCH_RECORD *the_search) { 
  float closeness;

  closeness = (the_search->num_joints ?
    (hamming_distance ((unsigned long *) the_search->first_state,
    (unsigned long *) the_search->best_state,
    2) / (float) the_search->num_joints) : 0.0);

  record_search_status (the_search->num_states,
    the_search->before_best, closeness);

  free_state (the_search->first_state);
  free_state (the_search->best_state);

  free_hash_table (the_search->closed_states);
  FreeHeapData (the_search->open_states, (void_dest) free_state);

  memfree(the_search); 
}


/**********************************************************************
 * evaluate_chunks
 *
 * A particular word level segmentation has been chosen.  Evaluation
 * this to find the word list that corresponds to it.
 **********************************************************************/
CHOICES_LIST evaluate_chunks(CHUNKS_RECORD *chunks_record,
                             SEARCH_STATE search_state,
                             STATE *this_state,
                             STATE *best_state,
                             INT32 pass) {
  CHOICES_LIST char_choices;
  CHOICES this_choice;
  int i;
  int x = 0;
  int y;

  char_choices = new_choice_list ();
  /* Iterate sub-paths */
  for (i = 1; i <= search_state[0] + 1; i++) {
    if (i > search_state[0])
      y = count_blobs (chunks_record->chunks) - 1;
    else
      y = x + search_state[i];

    if (blob_skip) {
      array_free(char_choices); 
      return (NULL);
    }                            /* Process one square */
    /* Classify if needed */
    this_choice = get_piece_rating (chunks_record->ratings,
      chunks_record->chunks,
      chunks_record->splits,
      x, y,
      chunks_record->fx,
      this_state, best_state, pass, i - 1);

    if (this_choice == NIL) {
      array_free(char_choices); 
      return (NULL);
    }
    /* Add permuted ratings */
    last_segmentation[i - 1].certainty = best_certainty (this_choice);
    last_segmentation[i - 1].match = best_probability (this_choice);

    last_segmentation[i - 1].width =
      chunks_width (chunks_record->chunk_widths, x, y);
    last_segmentation[i - 1].gap =
      chunks_gap (chunks_record->chunk_widths, y);

    char_choices = array_push (char_choices, this_choice);
    x = y + 1;
  }
  return (char_choices);
}


/**********************************************************************
 * evaluate_state
 *
 * Evaluate the segmentation that is represented by this state in the
 * best first search.  Add this state to the "states_seen" list.
 **********************************************************************/
INT16 evaluate_state(CHUNKS_RECORD *chunks_record,
                     SEARCH_RECORD *the_search,
                     DANGERR *fixpt,
                     STATE *best_state,
                     INT32 pass) {
  CHOICES_LIST char_choices;
  SEARCH_STATE chunk_groups;
  float rating_limit = class_probability (the_search->best_choice);
  INT16 keep_going = TRUE;
  PIECES_STATE widths;

  the_search->num_states++;
  chunk_groups = bin_to_chunks (the_search->this_state,
    the_search->num_joints);