~vcs-imports/tesseract-ocr/trunk

///////////////////////////////////////////////////////////////////////

// File:        strokewidth.cpp

// Description: Subclass of BBGrid to find uniformity of strokewidth.

// Author:      Ray Smith

// Created:     Mon Mar 31 16:17:01 PST 2008

//

// (C) Copyright 2008, Google Inc.

// 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.

//

///////////////////////////////////////////////////////////////////////

#ifdef _MSC_VER

#pragma warning(disable:4244)  // Conversion warnings

#endif

#ifdef HAVE_CONFIG_H

#include "config_auto.h"

#endif

#include "strokewidth.h"

#include <math.h>

#include "blobbox.h"

#include "colpartition.h"

#include "colpartitiongrid.h"

#include "imagefind.h"

#include "linlsq.h"

#include "statistc.h"

#include "tabfind.h"

#include "textlineprojection.h"

#include "tordmain.h"  // For SetBlobStrokeWidth.

namespace tesseract {

INT_VAR(textord_tabfind_show_strokewidths, 0, "Show stroke widths");

BOOL_VAR(textord_tabfind_only_strokewidths, false, "Only run stroke widths");

BOOL_VAR(textord_tabfind_vertical_text, true, "Enable vertical detection");

BOOL_VAR(textord_tabfind_force_vertical_text, false,

         "Force using vertical text page mode");

BOOL_VAR(textord_tabfind_vertical_horizontal_mix, true,

         "find horizontal lines such as headers in vertical page mode");

double_VAR(textord_tabfind_vertical_text_ratio, 0.5,

           "Fraction of textlines deemed vertical to use vertical page mode");

/** Allowed proportional change in stroke width to be the same font. */

const double kStrokeWidthFractionTolerance = 0.125;

/**

 * Allowed constant change in stroke width to be the same font. 

 * Really 1.5 pixels.

 */

const double kStrokeWidthTolerance = 1.5;

// Same but for CJK we are a bit more generous.

const double kStrokeWidthFractionCJK = 0.25;

const double kStrokeWidthCJK = 2.0;

// Radius in grid cells of search for broken CJK. Doesn't need to be very

// large as the grid size should be about the size of a character anyway.

const int kCJKRadius = 2;

// Max distance fraction of size to join close but broken CJK characters.

const double kCJKBrokenDistanceFraction = 0.25;

// Max number of components in a broken CJK character.

const int kCJKMaxComponents = 8;

// Max aspect ratio of CJK broken characters when put back together.

const double kCJKAspectRatio = 1.25;

// Max increase in aspect ratio of CJK broken characters when merged.

const double kCJKAspectRatioIncrease = 1.0625;

// Max multiple of the grid size that will be used in computing median CJKsize.

const int kMaxCJKSizeRatio = 5;

// Min fraction of blobs broken CJK to iterate and run it again.

const double kBrokenCJKIterationFraction = 0.125;

// Multiple of gridsize as x-padding for a search box for diacritic base

// characters.

const double kDiacriticXPadRatio = 7.0;

// Multiple of gridsize as y-padding for a search box for diacritic base

// characters.

const double kDiacriticYPadRatio = 1.75;

// Min multiple of diacritic height that a neighbour must be to be a

// convincing base character.

const double kMinDiacriticSizeRatio = 1.0625;

// Max multiple of a textline's median height as a threshold for the sum of

// a diacritic's farthest x and y distances (gap + size).

const double kMaxDiacriticDistanceRatio = 1.25;

// Max x-gap between a diacritic and its base char as a fraction of the height

// of the base char (allowing other blobs to fill the gap.)

const double kMaxDiacriticGapToBaseCharHeight = 1.0;

// Radius of a search for diacritics in grid units.

const int kSearchRadius = 2;

// Ratio between longest side of a line and longest side of a character.

// (neighbor_min > blob_min * kLineTrapShortest &&

//  neighbor_max < blob_max / kLineTrapLongest)

// => neighbor is a grapheme and blob is a line.

const int kLineTrapLongest = 4;

// Ratio between shortest side of a line and shortest side of a character.

const int kLineTrapShortest = 2;

// Max aspect ratio of the total box before CountNeighbourGaps

// decides immediately based on the aspect ratio.

const int kMostlyOneDirRatio = 3;

// Aspect ratio for a blob to be considered as line residue.

const double kLineResidueAspectRatio = 8.0;

// Padding ratio for line residue search box.

const int kLineResiduePadRatio = 3;

// Min multiple of neighbour size for a line residue to be genuine.

const double kLineResidueSizeRatio = 1.75;

// Aspect ratio filter for OSD.

const float kSizeRatioToReject = 2.0;

// Max number of normal blobs a large blob may overlap before it is rejected

// and determined to be image

const int kMaxLargeOverlaps = 3;

// Expansion factor for search box for good neighbours.

const double kNeighbourSearchFactor = 2.5;

StrokeWidth::StrokeWidth(int gridsize,

                         const ICOORD& bleft, const ICOORD& tright)

  : BlobGrid(gridsize, bleft, tright), nontext_map_(NULL), projection_(NULL),

    denorm_(NULL), grid_box_(bleft, tright), rerotation_(1.0f, 0.0f) {

  leaders_win_ = NULL;

  widths_win_ = NULL;

  initial_widths_win_ = NULL;

  chains_win_ = NULL;

  diacritics_win_ = NULL;

  textlines_win_ = NULL;

  smoothed_win_ = NULL;

}

StrokeWidth::~StrokeWidth() {

  if (widths_win_ != NULL) {

    #ifndef GRAPHICS_DISABLED

    delete widths_win_->AwaitEvent(SVET_DESTROY);

    #endif  // GRAPHICS_DISABLED

    if (textord_tabfind_only_strokewidths)

      exit(0);

    delete widths_win_;

  }

  delete leaders_win_;

  delete initial_widths_win_;

  delete chains_win_;

  delete textlines_win_;

  delete smoothed_win_;

  delete diacritics_win_;

}

// Sets the neighbours member of the medium-sized blobs in the block.

// Searches on 4 sides of each blob for similar-sized, similar-strokewidth

// blobs and sets pointers to the good neighbours.

void StrokeWidth::SetNeighboursOnMediumBlobs(TO_BLOCK* block) {

  // Run a preliminary strokewidth neighbour detection on the medium blobs.

  InsertBlobList(&block->blobs);

  BLOBNBOX_IT blob_it(&block->blobs);

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    SetNeighbours(false, false, blob_it.data());

  }

  Clear();

}

// Sets the neighbour/textline writing direction members of the medium

// and large blobs with optional repair of broken CJK characters first.

// Repair of broken CJK is needed here because broken CJK characters

// can fool the textline direction detection algorithm.

void StrokeWidth::FindTextlineDirectionAndFixBrokenCJK(bool cjk_merge,

                                                       TO_BLOCK* input_block) {

  // Setup the grid with the remaining (non-noise) blobs.

  InsertBlobs(input_block);

  // Repair broken CJK characters if needed.

  while (cjk_merge && FixBrokenCJK(input_block));

  // Grade blobs by inspection of neighbours.

  FindTextlineFlowDirection(false);

  // Clear the grid ready for rotation or leader finding.

  Clear();

}

// Helper to collect and count horizontal and vertical blobs from a list.

static void CollectHorizVertBlobs(BLOBNBOX_LIST* input_blobs,

                                  int* num_vertical_blobs,

                                  int* num_horizontal_blobs,

                                  BLOBNBOX_CLIST* vertical_blobs,

                                  BLOBNBOX_CLIST* horizontal_blobs,

                                  BLOBNBOX_CLIST* nondescript_blobs) {

  BLOBNBOX_C_IT v_it(vertical_blobs);

  BLOBNBOX_C_IT h_it(horizontal_blobs);

  BLOBNBOX_C_IT n_it(nondescript_blobs);

  BLOBNBOX_IT blob_it(input_blobs);

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    BLOBNBOX* blob = blob_it.data();

    const TBOX& box = blob->bounding_box();

    float y_x = static_cast<float>(box.height()) / box.width();

    float x_y = 1.0f / y_x;

    // Select a >= 1.0 ratio

    float ratio = x_y > y_x ? x_y : y_x;

    // If the aspect ratio is small and we want them for osd, save the blob.

    bool ok_blob = ratio <= kSizeRatioToReject;

    if (blob->UniquelyVertical()) {

      ++*num_vertical_blobs;

      if (ok_blob) v_it.add_after_then_move(blob);

    } else if (blob->UniquelyHorizontal()) {

      ++*num_horizontal_blobs;

      if (ok_blob) h_it.add_after_then_move(blob);

    } else if (ok_blob) {

      n_it.add_after_then_move(blob);

    }

  }

}

// Types all the blobs as vertical or horizontal text or unknown and

// returns true if the majority are vertical.

// If the blobs are rotated, it is necessary to call CorrectForRotation

// after rotating everything, otherwise the work done here will be enough.

// If osd_blobs is not null, a list of blobs from the dominant textline

// direction are returned for use in orientation and script detection.

bool StrokeWidth::TestVerticalTextDirection(TO_BLOCK* block,

                                            BLOBNBOX_CLIST* osd_blobs) {

  if (textord_tabfind_force_vertical_text) return true;

  if (!textord_tabfind_vertical_text) return false;

  int vertical_boxes = 0;

  int horizontal_boxes = 0;

  // Count vertical normal and large blobs.

  BLOBNBOX_CLIST vertical_blobs;

  BLOBNBOX_CLIST horizontal_blobs;

  BLOBNBOX_CLIST nondescript_blobs;

  CollectHorizVertBlobs(&block->blobs, &vertical_boxes, &horizontal_boxes,

                        &vertical_blobs, &horizontal_blobs, &nondescript_blobs);

  CollectHorizVertBlobs(&block->large_blobs, &vertical_boxes, &horizontal_boxes,

                        &vertical_blobs, &horizontal_blobs, &nondescript_blobs);

  if (textord_debug_tabfind)

    tprintf("TextDir hbox=%d vs vbox=%d, %dH, %dV, %dN osd blobs\n",

            horizontal_boxes, vertical_boxes,

            horizontal_blobs.length(), vertical_blobs.length(),

            nondescript_blobs.length());

  if (osd_blobs != NULL && vertical_boxes == 0 && horizontal_boxes == 0) {

    // Only nondescript blobs available, so return those.

    BLOBNBOX_C_IT osd_it(osd_blobs);

    osd_it.add_list_after(&nondescript_blobs);

    return false;

  }

  int min_vert_boxes = static_cast<int>((vertical_boxes + horizontal_boxes) *

                                        textord_tabfind_vertical_text_ratio);

  if (vertical_boxes >= min_vert_boxes) {

    if (osd_blobs != NULL) {

      BLOBNBOX_C_IT osd_it(osd_blobs);

      osd_it.add_list_after(&vertical_blobs);

    }

    return true;

  } else {

    if (osd_blobs != NULL) {

      BLOBNBOX_C_IT osd_it(osd_blobs);

      osd_it.add_list_after(&horizontal_blobs);

    }

    return false;

  }

}

// Corrects the data structures for the given rotation.

void StrokeWidth::CorrectForRotation(const FCOORD& rotation,

                                     ColPartitionGrid* part_grid) {

  Init(part_grid->gridsize(), part_grid->bleft(), part_grid->tright());

  grid_box_ = TBOX(bleft(), tright());

  rerotation_.set_x(rotation.x());

  rerotation_.set_y(-rotation.y());

}

// Finds leader partitions and inserts them into the given part_grid.

void StrokeWidth::FindLeaderPartitions(TO_BLOCK* block,

                                       ColPartitionGrid* part_grid) {

  Clear();

  // Find and isolate leaders in the noise list.

  ColPartition_LIST leader_parts;

  FindLeadersAndMarkNoise(block, &leader_parts);

  // Setup the strokewidth grid with the block's remaining (non-noise) blobs.

  InsertBlobList(&block->blobs);

  // Mark blobs that have leader neighbours.

  for (ColPartition_IT it(&leader_parts); !it.empty(); it.forward()) {

    ColPartition* part = it.extract();

    part->ClaimBoxes();

    MarkLeaderNeighbours(part, LR_LEFT);

    MarkLeaderNeighbours(part, LR_RIGHT);

    part_grid->InsertBBox(true, true, part);

  }

}

// Finds and marks noise those blobs that look like bits of vertical lines

// that would otherwise screw up layout analysis.

void StrokeWidth::RemoveLineResidue(ColPartition_LIST* big_part_list) {

  BlobGridSearch gsearch(this);

  BLOBNBOX* bbox;

  // For every vertical line-like bbox in the grid, search its neighbours

  // to find the tallest, and if the original box is taller by sufficient

  // margin, then call it line residue and delete it.

  gsearch.StartFullSearch();

  while ((bbox = gsearch.NextFullSearch()) != NULL) {

    TBOX box = bbox->bounding_box();

    if (box.height() < box.width() * kLineResidueAspectRatio)

      continue;

    // Set up a rectangle search around the blob to find the size of its

    // neighbours.

    int padding = box.height() * kLineResiduePadRatio;

    TBOX search_box = box;

    search_box.pad(padding, padding);

    bool debug = AlignedBlob::WithinTestRegion(2, box.left(),

                                               box.bottom());

    // Find the largest object in the search box not equal to bbox.

    BlobGridSearch rsearch(this);

    int max_size = 0;

    BLOBNBOX* n;

    rsearch.StartRectSearch(search_box);

    while ((n = rsearch.NextRectSearch()) != NULL) {

      if (n == bbox) continue;

      TBOX nbox = n->bounding_box();

      if (nbox.height() > max_size) {

        max_size = nbox.height();

      }

    }

    if (debug) {

      tprintf("Max neighbour size=%d for candidate line box at:", max_size);

      box.print();

    }

    if (max_size * kLineResidueSizeRatio < box.height()) {

      #ifndef GRAPHICS_DISABLED

      if (leaders_win_ != NULL) {

        // We are debugging, so display deleted in pink blobs in the same

        // window that we use to display leader detection.

        leaders_win_->Pen(ScrollView::PINK);

        leaders_win_->Rectangle(box.left(), box.bottom(),

                                box.right(), box.top());

      }

      #endif  // GRAPHICS_DISABLED

      ColPartition::MakeBigPartition(bbox, big_part_list);

    }

  }

}

// Types all the blobs as vertical text or horizontal text or unknown and

// puts them into initial ColPartitions in the supplied part_grid.

// rerotation determines how to get back to the image coordinates from the

// blob coordinates (since they may have been rotated for vertical text).

// block is the single block for the whole page or rectangle to be OCRed.

// nontext_pix (full-size), is a binary mask used to prevent merges across

// photo/text boundaries. It is not kept beyond this function.

// denorm provides a mapping back to the image from the current blob

// coordinate space.

// projection provides a measure of textline density over the image and

// provides functions to assist with diacritic detection. It should be a

// pointer to a new TextlineProjection, and will be setup here.

// part_grid is the output grid of textline partitions.

// Large blobs that cause overlap are put in separate partitions and added

// to the big_parts list.

void StrokeWidth::GradeBlobsIntoPartitions(const FCOORD& rerotation,

                                           TO_BLOCK* block,

                                           Pix* nontext_pix,

                                           const DENORM* denorm,

                                           bool cjk_script,

                                           TextlineProjection* projection,

                                           ColPartitionGrid* part_grid,

                                           ColPartition_LIST* big_parts) {

  nontext_map_ = nontext_pix;

  projection_ = projection;

  denorm_ = denorm;

  // Clear and re Insert to take advantage of the tab stops in the blobs.

  Clear();

  // Setup the strokewidth grid with the remaining non-noise, non-leader blobs.

  InsertBlobs(block);

  // Run FixBrokenCJK() again if the page is CJK.

  if (cjk_script) {

    FixBrokenCJK(block);

  }

  FindTextlineFlowDirection(true);

  projection_->ConstructProjection(block, rerotation, nontext_map_);

  if (textord_tabfind_show_strokewidths) {

    ScrollView* line_blobs_win = MakeWindow(0, 0, "Initial textline Blobs");

    projection_->PlotGradedBlobs(&block->blobs, line_blobs_win);

    projection_->PlotGradedBlobs(&block->small_blobs, line_blobs_win);

  }

  projection_->MoveNonTextlineBlobs(&block->blobs, &block->noise_blobs);

  projection_->MoveNonTextlineBlobs(&block->small_blobs, &block->noise_blobs);

  // Clear and re Insert to take advantage of the removed diacritics.

  Clear();

  InsertBlobs(block);

  FindInitialPartitions(rerotation, block, part_grid, big_parts);

  nontext_map_ = NULL;

  projection_ = NULL;

  denorm_ = NULL;

}

static void PrintBoxWidths(BLOBNBOX* neighbour) {

  TBOX nbox = neighbour->bounding_box();

  tprintf("Box (%d,%d)->(%d,%d): h-width=%.1f, v-width=%.1f p-width=%1.f\n",

          nbox.left(), nbox.bottom(), nbox.right(), nbox.top(),

          neighbour->horz_stroke_width(), neighbour->vert_stroke_width(),

          2.0 * neighbour->cblob()->area()/neighbour->cblob()->perimeter());

}

/** Handles a click event in a display window. */

void StrokeWidth::HandleClick(int x, int y) {

  BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>::HandleClick(x, y);

  // Run a radial search for blobs that overlap.

  BlobGridSearch radsearch(this);

  radsearch.StartRadSearch(x, y, 1);

  BLOBNBOX* neighbour;

  FCOORD click(static_cast<float>(x), static_cast<float>(y));

  while ((neighbour = radsearch.NextRadSearch()) != NULL) {

    TBOX nbox = neighbour->bounding_box();

    if (nbox.contains(click) && neighbour->cblob() != NULL) {

      PrintBoxWidths(neighbour);

      if (neighbour->neighbour(BND_LEFT) != NULL)

        PrintBoxWidths(neighbour->neighbour(BND_LEFT));

      if (neighbour->neighbour(BND_RIGHT) != NULL)

        PrintBoxWidths(neighbour->neighbour(BND_RIGHT));

      if (neighbour->neighbour(BND_ABOVE) != NULL)

        PrintBoxWidths(neighbour->neighbour(BND_ABOVE));

      if (neighbour->neighbour(BND_BELOW) != NULL)

        PrintBoxWidths(neighbour->neighbour(BND_BELOW));

      int gaps[BND_COUNT];

      neighbour->NeighbourGaps(gaps);

      tprintf("Left gap=%d, right=%d, above=%d, below=%d, horz=%d, vert=%d\n"

              "Good=    %d        %d        %d        %d\n",

              gaps[BND_LEFT], gaps[BND_RIGHT],

              gaps[BND_ABOVE], gaps[BND_BELOW],

              neighbour->horz_possible(),

              neighbour->vert_possible(),

              neighbour->good_stroke_neighbour(BND_LEFT),

              neighbour->good_stroke_neighbour(BND_RIGHT),

              neighbour->good_stroke_neighbour(BND_ABOVE),

              neighbour->good_stroke_neighbour(BND_BELOW));

      break;

    }

  }

}

// Detects and marks leader dots/dashes.

//    Leaders are horizontal chains of small or noise blobs that look

//    monospace according to ColPartition::MarkAsLeaderIfMonospaced().

// Detected leaders become the only occupants of the block->small_blobs list.

// Non-leader small blobs get moved to the blobs list.

// Non-leader noise blobs remain singletons in the noise list.

// All small and noise blobs in high density regions are marked BTFT_NONTEXT.

// block is the single block for the whole page or rectangle to be OCRed.

// leader_parts is the output.

void StrokeWidth::FindLeadersAndMarkNoise(TO_BLOCK* block,

                                          ColPartition_LIST* leader_parts) {

  InsertBlobList(&block->small_blobs);

  InsertBlobList(&block->noise_blobs);

  BlobGridSearch gsearch(this);

  BLOBNBOX* bbox;

  // For every bbox in the grid, set its neighbours.

  gsearch.StartFullSearch();

  while ((bbox = gsearch.NextFullSearch()) != NULL) {

    SetNeighbours(true, false, bbox);

  }

  ColPartition_IT part_it(leader_parts);

  gsearch.StartFullSearch();

  while ((bbox = gsearch.NextFullSearch()) != NULL) {

    if (bbox->flow() == BTFT_NONE) {

      if (bbox->neighbour(BND_RIGHT) == NULL &&

          bbox->neighbour(BND_LEFT) == NULL)

        continue;

      // Put all the linked blobs into a ColPartition.

      ColPartition* part = new ColPartition(BRT_UNKNOWN, ICOORD(0, 1));

      BLOBNBOX* blob;

      for (blob = bbox; blob != NULL && blob->flow() == BTFT_NONE;

           blob = blob->neighbour(BND_RIGHT))

        part->AddBox(blob);

      for (blob = bbox->neighbour(BND_LEFT); blob != NULL &&

           blob->flow() == BTFT_NONE;

           blob = blob->neighbour(BND_LEFT))

        part->AddBox(blob);

      if (part->MarkAsLeaderIfMonospaced())

        part_it.add_after_then_move(part);

      else

        delete part;

    }

  }

  if (textord_tabfind_show_strokewidths) {

    leaders_win_ = DisplayGoodBlobs("LeaderNeighbours", 0, 0);

  }

  // Move any non-leaders from the small to the blobs list, as they are

  // most likely dashes or broken characters.

  BLOBNBOX_IT blob_it(&block->blobs);

  BLOBNBOX_IT small_it(&block->small_blobs);

  for (small_it.mark_cycle_pt(); !small_it.cycled_list(); small_it.forward()) {

    BLOBNBOX* blob = small_it.data();

    if (blob->flow() != BTFT_LEADER) {

      if (blob->flow() == BTFT_NEIGHBOURS)

        blob->set_flow(BTFT_NONE);

      blob->ClearNeighbours();

      blob_it.add_to_end(small_it.extract());

    }

  }

  // Move leaders from the noise list to the small list, leaving the small

  // list exclusively leaders, so they don't get processed further,

  // and the remaining small blobs all in the noise list.

  BLOBNBOX_IT noise_it(&block->noise_blobs);

  for (noise_it.mark_cycle_pt(); !noise_it.cycled_list(); noise_it.forward()) {

    BLOBNBOX* blob = noise_it.data();

    if (blob->flow() == BTFT_LEADER || blob->joined_to_prev()) {

      small_it.add_to_end(noise_it.extract());

    } else if (blob->flow() == BTFT_NEIGHBOURS) {

      blob->set_flow(BTFT_NONE);

      blob->ClearNeighbours();

    }

  }

  // Clear the grid as we don't want the small stuff hanging around in it.

  Clear();

}

/** Inserts the block blobs (normal and large) into this grid.

 * Blobs remain owned by the block. */

void StrokeWidth::InsertBlobs(TO_BLOCK* block) {

  InsertBlobList(&block->blobs);

  InsertBlobList(&block->large_blobs);

}

// Checks the left or right side of the given leader partition and sets the

// (opposite) leader_on_right or leader_on_left flags for blobs

// that are next to the given side of the given leader partition.

void StrokeWidth::MarkLeaderNeighbours(const ColPartition* part,

                                       LeftOrRight side) {

  const TBOX& part_box = part->bounding_box();

  BlobGridSearch blobsearch(this);

  // Search to the side of the leader for the nearest neighbour.

  BLOBNBOX* best_blob = NULL;

  int best_gap = 0;

  blobsearch.StartSideSearch(side == LR_LEFT ? part_box.left()

                                             : part_box.right(),

                             part_box.bottom(), part_box.top());

  BLOBNBOX* blob;

  while ((blob = blobsearch.NextSideSearch(side == LR_LEFT)) != NULL) {

    const TBOX& blob_box = blob->bounding_box();

    if (!blob_box.y_overlap(part_box))

      continue;

    int x_gap = blob_box.x_gap(part_box);

    if (x_gap > 2 * gridsize()) {

      break;

    } else if (best_blob == NULL || x_gap < best_gap) {

      best_blob = blob;

      best_gap = x_gap;

    }

  }

  if (best_blob != NULL) {

    if (side == LR_LEFT)

      best_blob->set_leader_on_right(true);

    else

      best_blob->set_leader_on_left(true);

    #ifndef GRAPHICS_DISABLED

    if (leaders_win_ != NULL) {

      leaders_win_->Pen(side == LR_LEFT ? ScrollView::RED : ScrollView::GREEN);

      const TBOX& blob_box = best_blob->bounding_box();

      leaders_win_->Rectangle(blob_box.left(), blob_box.bottom(),

                              blob_box.right(), blob_box.top());

    }

    #endif  // GRAPHICS_DISABLED

  }

}

// Helper to compute the UQ of the square-ish CJK charcters.

static int UpperQuartileCJKSize(int gridsize, BLOBNBOX_LIST* blobs) {

  STATS sizes(0, gridsize * kMaxCJKSizeRatio);

  BLOBNBOX_IT it(blobs);

  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {

    BLOBNBOX* blob = it.data();

    int width = blob->bounding_box().width();

    int height = blob->bounding_box().height();

    if (width <= height * kCJKAspectRatio && height < width * kCJKAspectRatio)

      sizes.add(height, 1);

  }

  return static_cast<int>(sizes.ile(0.75f) + 0.5);

}

// Fix broken CJK characters, using the fake joined blobs mechanism.

// Blobs are really merged, ie the master takes all the outlines and the

// others are deleted.

// Returns true if sufficient blobs are merged that it may be worth running

// again, due to a better estimate of character size.

bool StrokeWidth::FixBrokenCJK(TO_BLOCK* block) {

  BLOBNBOX_LIST* blobs = &block->blobs;

  int median_height = UpperQuartileCJKSize(gridsize(), blobs);

  int max_dist = static_cast<int>(median_height * kCJKBrokenDistanceFraction);

  int max_size = static_cast<int>(median_height * kCJKAspectRatio);

  int num_fixed = 0;

  BLOBNBOX_IT blob_it(blobs);

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    BLOBNBOX* blob = blob_it.data();

    if (blob->cblob() == NULL || blob->cblob()->out_list()->empty())

      continue;

    TBOX bbox = blob->bounding_box();

    bool debug = AlignedBlob::WithinTestRegion(3, bbox.left(),

                                               bbox.bottom());

    if (debug) {

      tprintf("Checking for Broken CJK (max size=%d):", max_size);

      bbox.print();

    }

    // Generate a list of blobs that overlap or are near enough to merge.

    BLOBNBOX_CLIST overlapped_blobs;

    AccumulateOverlaps(blob, debug, max_size, max_dist,

                       &bbox, &overlapped_blobs);

    if (!overlapped_blobs.empty()) {

      // There are overlapping blobs, so qualify them as being satisfactory

      // before removing them from the grid and replacing them with the union.

      // The final box must be roughly square.

      if (bbox.width() > bbox.height() * kCJKAspectRatio ||

          bbox.height() > bbox.width() * kCJKAspectRatio) {

        if (debug) {

          tprintf("Bad final aspectratio:");

          bbox.print();

        }

        continue;

      }

      // There can't be too many blobs to merge.

      if (overlapped_blobs.length() >= kCJKMaxComponents) {

        if (debug)

          tprintf("Too many neighbours: %d\n", overlapped_blobs.length());

        continue;

      }

      // The strokewidths must match amongst the join candidates.

      BLOBNBOX_C_IT n_it(&overlapped_blobs);

      for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {

        BLOBNBOX* neighbour = NULL;

        neighbour = n_it.data();

        if (!blob->MatchingStrokeWidth(*neighbour, kStrokeWidthFractionCJK,

                                       kStrokeWidthCJK))

          break;

      }

      if (!n_it.cycled_list()) {

        if (debug) {

          tprintf("Bad stroke widths:");

          PrintBoxWidths(blob);

        }

        continue;  // Not good enough.

      }

      // Merge all the candidates into blob.

      // We must remove blob from the grid and reinsert it after merging

      // to maintain the integrity of the grid.

      RemoveBBox(blob);

      // Everything else will be calculated later.

      for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {

        BLOBNBOX* neighbour = n_it.data();

        RemoveBBox(neighbour);

        // Mark empty blob for deletion.

        neighbour->set_region_type(BRT_NOISE);

        blob->really_merge(neighbour);

        if (rerotation_.x() != 1.0f || rerotation_.y() != 0.0f) {

          blob->rotate_box(rerotation_);

        }

      }

      InsertBBox(true, true, blob);

      ++num_fixed;

      if (debug) {

        tprintf("Done! Final box:");

        bbox.print();

      }

    }

  }

  // Count remaining blobs.

  int num_remaining = 0;

  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {

    BLOBNBOX* blob = blob_it.data();

    if (blob->cblob() != NULL && !blob->cblob()->out_list()->empty()) {

      ++num_remaining;

    }

  }

  // Permanently delete all the marked blobs after first removing all

  // references in the neighbour members.

  block->DeleteUnownedNoise();

  return num_fixed > num_remaining * kBrokenCJKIterationFraction;

}

// Helper function to determine whether it is reasonable to merge the

// bbox and the nbox for repairing broken CJK.

// The distance apart must not exceed max_dist, the combined size must

// not exceed max_size, and the aspect ratio must either improve or at

// least not get worse by much.

static bool AcceptableCJKMerge(const TBOX& bbox, const TBOX& nbox,

                               bool debug, int max_size, int max_dist,

                               int* x_gap, int* y_gap) {

  *x_gap = bbox.x_gap(nbox);

  *y_gap = bbox.y_gap(nbox);

  TBOX merged(nbox);

  merged += bbox;

  if (debug) {

    tprintf("gaps = %d, %d, merged_box:", *x_gap, *y_gap);

    merged.print();

  }

  if (*x_gap <= max_dist && *y_gap <= max_dist &&

      merged.width() <= max_size && merged.height() <= max_size) {