| /********************************************************************** |
| * File: edgblob.c (Formerly edgeloop.c) |
| * Description: Functions to clean up an outline before approximation. |
| * Author: Ray Smith |
| * Created: Tue Mar 26 16:56:25 GMT 1991 |
| * |
| * (C) Copyright 1991, Hewlett-Packard Ltd. |
| ** 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 "mfcpch.h" |
| #include "scanedg.h" |
| #include "drawedg.h" |
| #include "edgloop.h" |
| #include "edgblob.h" |
| |
| #define EXTERN |
| |
| // Control parameters used in outline_complexity(), which rejects an outline |
| // if any one of the 3 conditions is satisfied: |
| // - number of children exceeds edges_max_children_per_outline |
| // - number of nested layers exceeds edges_max_children_layers |
| // - joint complexity exceeds edges_children_count_limit(as in child_count()) |
| EXTERN BOOL_VAR(edges_use_new_outline_complexity, FALSE, |
| "Use the new outline complexity module"); |
| EXTERN INT_VAR(edges_max_children_per_outline, 10, |
| "Max number of children inside a character outline"); |
| EXTERN INT_VAR(edges_max_children_layers, 5, |
| "Max layers of nested children inside a character outline"); |
| EXTERN BOOL_VAR(edges_debug, FALSE, |
| "turn on debugging for this module"); |
| |
| |
| EXTERN INT_VAR (edges_children_per_grandchild, 10, |
| "Importance ratio for chucking outlines"); |
| EXTERN INT_VAR(edges_children_count_limit, 45, |
| "Max holes allowed in blob"); |
| EXTERN BOOL_VAR (edges_children_fix, FALSE, |
| "Remove boxy parents of char-like children"); |
| EXTERN INT_VAR (edges_min_nonhole, 12, |
| "Min pixels for potential char in box"); |
| EXTERN INT_VAR (edges_patharea_ratio, 40, |
| "Max lensq/area for acceptable child outline"); |
| EXTERN double_VAR (edges_childarea, 0.5, |
| "Min area fraction of child outline"); |
| EXTERN double_VAR (edges_boxarea, 0.875, |
| "Min area fraction of grandchild for box"); |
| |
| /********************************************************************** |
| * OL_BUCKETS::OL_BUCKETS |
| * |
| * Construct an array of buckets for associating outlines into blobs. |
| **********************************************************************/ |
| |
| OL_BUCKETS::OL_BUCKETS ( |
| ////constructor |
| ICOORD bleft, //corners |
| ICOORD tright): bl (bleft), tr (tright) { |
| bxdim = (tright.x () - bleft.x ()) / BUCKETSIZE + 1; |
| bydim = (tright.y () - bleft.y ()) / BUCKETSIZE + 1; |
| //make array |
| buckets = new C_OUTLINE_LIST[bxdim * bydim]; |
| index = 0; |
| } |
| |
| |
| /********************************************************************** |
| * OL_BUCKETS::operator( |
| * |
| * Return a pointer to a list of C_OUTLINEs corresponding to the |
| * given pixel coordinates. |
| **********************************************************************/ |
| |
| C_OUTLINE_LIST * |
| OL_BUCKETS::operator () ( //array access |
| inT16 x, //image coords |
| inT16 y) { |
| return &buckets[(y-bl.y()) / BUCKETSIZE * bxdim + (x-bl.x()) / BUCKETSIZE]; |
| } |
| |
| |
| /********************************************************************** |
| * OL_BUCKETS::outline_complexity |
| * |
| * This is the new version of count_child. |
| * |
| * The goal of this function is to determine if an outline and its |
| * interiors could be part of a character blob. This is done by |
| * computing a "complexity" index for the outline, which is the return |
| * value of this function, and checking it against a threshold. |
| * The max_count is used for short-circuiting the recursion and forcing |
| * a rejection that guarantees to fail the threshold test. |
| * The complexity F for outline X with N children X[i] is |
| * F(X) = N + sum_i F(X[i]) * edges_children_per_grandchild |
| * so each layer of nesting increases complexity exponentially. |
| * An outline can be rejected as a text blob candidate if its complexity |
| * is too high, has too many children(likely a container), or has too |
| * many layers of nested inner loops. This has the side-effect of |
| * flattening out boxed or reversed video text regions. |
| **********************************************************************/ |
| |
| inT32 OL_BUCKETS::outline_complexity( |
| C_OUTLINE *outline, // parent outline |
| inT32 max_count, // max output |
| inT16 depth // recurion depth |
| ) { |
| inT16 xmin, xmax; // coord limits |
| inT16 ymin, ymax; |
| inT16 xindex, yindex; // current bucket |
| C_OUTLINE *child; // current child |
| inT32 child_count; // no of children |
| inT32 grandchild_count; // no of grandchildren |
| C_OUTLINE_IT child_it; // search iterator |
| |
| TBOX olbox = outline->bounding_box(); |
| xmin =(olbox.left() - bl.x()) / BUCKETSIZE; |
| xmax =(olbox.right() - bl.x()) / BUCKETSIZE; |
| ymin =(olbox.bottom() - bl.y()) / BUCKETSIZE; |
| ymax =(olbox.top() - bl.y()) / BUCKETSIZE; |
| child_count = 0; |
| grandchild_count = 0; |
| if (++depth > edges_max_children_layers) // nested loops are too deep |
| return max_count + depth; |
| |
| for (yindex = ymin; yindex <= ymax; yindex++) { |
| for (xindex = xmin; xindex <= xmax; xindex++) { |
| child_it.set_to_list(&buckets[yindex * bxdim + xindex]); |
| if (child_it.empty()) |
| continue; |
| for (child_it.mark_cycle_pt(); !child_it.cycled_list(); |
| child_it.forward()) { |
| child = child_it.data(); |
| if (child == outline || !(*child < *outline)) |
| continue; |
| child_count++; |
| |
| if (child_count > edges_max_children_per_outline) { // too fragmented |
| if (edges_debug) |
| tprintf("Discard outline on child_count=%d > " |
| "max_children_per_outline=%d\n", |
| child_count, |
| static_cast<inT32>(edges_max_children_per_outline)); |
| return max_count + child_count; |
| } |
| |
| // Compute the "complexity" of each child recursively |
| inT32 remaining_count = max_count - child_count - grandchild_count; |
| if (remaining_count > 0) |
| grandchild_count += edges_children_per_grandchild * |
| outline_complexity(child, remaining_count, depth); |
| if (child_count + grandchild_count > max_count) { // too complex |
| if (edges_debug) |
| tprintf("Disgard outline on child_count=%d + grandchild_count=%d " |
| "> max_count=%d\n", |
| child_count, grandchild_count, max_count); |
| return child_count + grandchild_count; |
| } |
| } |
| } |
| } |
| return child_count + grandchild_count; |
| } |
| |
| |
| /********************************************************************** |
| * OL_BUCKETS::count_children |
| * |
| * Find number of descendants of this outline. |
| **********************************************************************/ |
| |
| inT32 OL_BUCKETS::count_children( //recursive count |
| C_OUTLINE *outline, //parent outline |
| inT32 max_count //max output |
| ) { |
| BOOL8 parent_box; //could it be boxy |
| inT16 xmin, xmax; //coord limits |
| inT16 ymin, ymax; |
| inT16 xindex, yindex; //current bucket |
| C_OUTLINE *child; //current child |
| inT32 child_count; //no of children |
| inT32 grandchild_count; //no of grandchildren |
| inT32 parent_area; //potential box |
| FLOAT32 max_parent_area; //potential box |
| inT32 child_area; //current child |
| inT32 child_length; //current child |
| TBOX olbox; |
| C_OUTLINE_IT child_it; //search iterator |
| |
| olbox = outline->bounding_box (); |
| xmin = (olbox.left () - bl.x ()) / BUCKETSIZE; |
| xmax = (olbox.right () - bl.x ()) / BUCKETSIZE; |
| ymin = (olbox.bottom () - bl.y ()) / BUCKETSIZE; |
| ymax = (olbox.top () - bl.y ()) / BUCKETSIZE; |
| child_count = 0; |
| grandchild_count = 0; |
| parent_area = 0; |
| max_parent_area = 0; |
| parent_box = TRUE; |
| for (yindex = ymin; yindex <= ymax; yindex++) { |
| for (xindex = xmin; xindex <= xmax; xindex++) { |
| child_it.set_to_list (&buckets[yindex * bxdim + xindex]); |
| if (child_it.empty ()) |
| continue; |
| for (child_it.mark_cycle_pt (); !child_it.cycled_list (); |
| child_it.forward ()) { |
| child = child_it.data (); |
| if (child != outline && *child < *outline) { |
| child_count++; |
| if (child_count <= max_count) { |
| int max_grand = (max_count - child_count) / |
| edges_children_per_grandchild; |
| if (max_grand > 0) |
| grandchild_count += count_children (child, max_grand) * |
| edges_children_per_grandchild; |
| else |
| grandchild_count += count_children(child, 1); |
| } |
| if (child_count + grandchild_count > max_count) { |
| if (edges_debug) |
| tprintf("Discarding parent with child count=%d, gc=%d\n", |
| child_count,grandchild_count); |
| return child_count + grandchild_count; |
| } |
| if (parent_area == 0) { |
| parent_area = outline->outer_area (); |
| if (parent_area < 0) |
| parent_area = -parent_area; |
| max_parent_area = outline->bounding_box().area() * edges_boxarea; |
| if (parent_area < max_parent_area) |
| parent_box = FALSE; |
| } |
| if (parent_box && |
| (!edges_children_fix || |
| child->bounding_box().height() > edges_min_nonhole)) { |
| child_area = child->outer_area (); |
| if (child_area < 0) |
| child_area = -child_area; |
| if (edges_children_fix) { |
| if (parent_area - child_area < max_parent_area) { |
| parent_box = FALSE; |
| continue; |
| } |
| if (grandchild_count > 0) { |
| if (edges_debug) |
| tprintf("Discarding parent of area %d, child area=%d, max%g " |
| "with gc=%d\n", |
| parent_area, child_area, max_parent_area, |
| grandchild_count); |
| return max_count + 1; |
| } |
| child_length = child->pathlength (); |
| if (child_length * child_length > |
| child_area * edges_patharea_ratio) { |
| if (edges_debug) |
| tprintf("Discarding parent of area %d, child area=%d, max%g " |
| "with child length=%d\n", |
| parent_area, child_area, max_parent_area, |
| child_length); |
| return max_count + 1; |
| } |
| } |
| if (child_area < child->bounding_box().area() * edges_childarea) { |
| if (edges_debug) |
| tprintf("Discarding parent of area %d, child area=%d, max%g " |
| "with child rect=%d\n", |
| parent_area, child_area, max_parent_area, |
| child->bounding_box().area()); |
| return max_count + 1; |
| } |
| } |
| } |
| } |
| } |
| } |
| return child_count + grandchild_count; |
| } |
| |
| |
| |
| |
| /********************************************************************** |
| * OL_BUCKETS::extract_children |
| * |
| * Find number of descendants of this outline. |
| **********************************************************************/ |
| |
| void OL_BUCKETS::extract_children( //recursive count |
| C_OUTLINE *outline, //parent outline |
| C_OUTLINE_IT *it //destination iterator |
| ) { |
| inT16 xmin, xmax; //coord limits |
| inT16 ymin, ymax; |
| inT16 xindex, yindex; //current bucket |
| TBOX olbox; |
| C_OUTLINE_IT child_it; //search iterator |
| |
| olbox = outline->bounding_box (); |
| xmin = (olbox.left () - bl.x ()) / BUCKETSIZE; |
| xmax = (olbox.right () - bl.x ()) / BUCKETSIZE; |
| ymin = (olbox.bottom () - bl.y ()) / BUCKETSIZE; |
| ymax = (olbox.top () - bl.y ()) / BUCKETSIZE; |
| for (yindex = ymin; yindex <= ymax; yindex++) { |
| for (xindex = xmin; xindex <= xmax; xindex++) { |
| child_it.set_to_list (&buckets[yindex * bxdim + xindex]); |
| for (child_it.mark_cycle_pt (); !child_it.cycled_list (); |
| child_it.forward ()) { |
| if (*child_it.data () < *outline) { |
| it->add_after_then_move (child_it.extract ()); |
| } |
| } |
| } |
| } |
| } |
| |
| |
| /********************************************************************** |
| * extract_edges |
| * |
| * Run the edge detector over the block and return a list of blobs. |
| **********************************************************************/ |
| |
| void extract_edges( //find blobs |
| #ifndef GRAPHICS_DISABLED |
| ScrollView* window, //window for output |
| #endif |
| IMAGE *image, //image to scan |
| IMAGE *t_image, //thresholded image |
| ICOORD page_tr, //corner of page |
| BLOCK *block //block to scan |
| ) { |
| ICOORD bleft; //block box |
| ICOORD tright; |
| C_OUTLINE_LIST outlines; //outlines in block |
| //iterator |
| C_OUTLINE_IT out_it = &outlines; |
| |
| #ifndef GRAPHICS_DISABLED |
| get_outlines (window, image, t_image, page_tr, (PDBLK *) block, &out_it); |
| #else |
| get_outlines (image, t_image, page_tr, (PDBLK *) block, &out_it); |
| #endif |
| //block box |
| block->bounding_box (bleft, tright); |
| //make blobs |
| outlines_to_blobs(block, bleft, tright, &outlines); |
| } |
| |
| |
| /********************************************************************** |
| * outlines_to_blobs |
| * |
| * Gather together outlines into blobs using the usual bucket sort. |
| **********************************************************************/ |
| |
| void outlines_to_blobs( //find blobs |
| BLOCK *block, //block to scan |
| ICOORD bleft, |
| ICOORD tright, |
| C_OUTLINE_LIST *outlines) { |
| //make buckets |
| OL_BUCKETS buckets(bleft, tright); |
| |
| fill_buckets(outlines, &buckets); |
| empty_buckets(block, &buckets); |
| } |
| |
| |
| /********************************************************************** |
| * fill_buckets |
| * |
| * Run the edge detector over the block and return a list of blobs. |
| **********************************************************************/ |
| |
| void fill_buckets( //find blobs |
| C_OUTLINE_LIST *outlines, //outlines in block |
| OL_BUCKETS *buckets //output buckets |
| ) { |
| TBOX ol_box; //outline box |
| C_OUTLINE_IT out_it = outlines;//iterator |
| C_OUTLINE_IT bucket_it; //iterator in bucket |
| C_OUTLINE *outline; //current outline |
| |
| for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) { |
| outline = out_it.extract (); //take off list |
| //get box |
| ol_box = outline->bounding_box (); |
| bucket_it.set_to_list ((*buckets) (ol_box.left (), ol_box.bottom ())); |
| bucket_it.add_to_end (outline); |
| } |
| } |
| |
| |
| /********************************************************************** |
| * empty_buckets |
| * |
| * Run the edge detector over the block and return a list of blobs. |
| **********************************************************************/ |
| |
| void empty_buckets( //find blobs |
| BLOCK *block, //block to scan |
| OL_BUCKETS *buckets //output buckets |
| ) { |
| BOOL8 good_blob; //healthy blob |
| C_OUTLINE_LIST outlines; //outlines in block |
| //iterator |
| C_OUTLINE_IT out_it = &outlines; |
| C_OUTLINE_IT bucket_it = buckets->start_scan (); |
| C_OUTLINE_IT parent_it; //parent outline |
| C_BLOB *blob; //new blob |
| C_BLOB_IT good_blobs = block->blob_list (); |
| C_BLOB_IT junk_blobs = block->reject_blobs (); |
| |
| while (!bucket_it.empty ()) { |
| out_it.set_to_list (&outlines); |
| do { |
| parent_it = bucket_it; //find outermost |
| do |
| bucket_it.forward (); |
| while (!bucket_it.at_first () |
| && !(*parent_it.data () < *bucket_it.data ())); |
| } |
| while (!bucket_it.at_first ()); |
| |
| //move to new list |
| out_it.add_after_then_move (parent_it.extract ()); |
| good_blob = capture_children (buckets, &junk_blobs, &out_it); |
| blob = new C_BLOB (&outlines); |
| if (good_blob) |
| good_blobs.add_after_then_move (blob); |
| else |
| junk_blobs.add_after_then_move (blob); |
| |
| bucket_it.set_to_list (buckets->scan_next ()); |
| } |
| } |
| |
| |
| /********************************************************************** |
| * capture_children |
| * |
| * Find all neighbouring outlines that are children of this outline |
| * and either move them to the output list or declare this outline |
| * illegal and return FALSE. |
| **********************************************************************/ |
| |
| BOOL8 capture_children( //find children |
| OL_BUCKETS *buckets, //bucket sort clanss |
| C_BLOB_IT *reject_it, //dead grandchildren |
| C_OUTLINE_IT *blob_it //output outlines |
| ) { |
| C_OUTLINE *outline; //master outline |
| inT32 child_count; //no of children |
| |
| outline = blob_it->data (); |
| if (edges_use_new_outline_complexity) |
| child_count = buckets->outline_complexity(outline, |
| edges_children_count_limit, |
| 0); |
| else |
| child_count = buckets->count_children(outline, |
| edges_children_count_limit); |
| if (child_count > edges_children_count_limit) |
| return FALSE; |
| |
| if (child_count > 0) |
| buckets->extract_children (outline, blob_it); |
| return TRUE; |
| } |
