Object Recognition in Structured and Random Environments: Locating Address Blocks on Mail Pieces

Ching-Huei Wang, Sargur N. SrihariAAAI 1986

Abstract

This paper presents the Address Block Location System (ABLS), a framework designed to identify destination addresses on mail pieces ranging from highly structured envelopes to chaotic, "random" environments like magazine covers. By employing a blackboard architecture and a modular "community of experts," ABLS integrates specialized image processing tools with rule-based inference and Dempster-Shafer uncertainty modeling to achieve robust object recognition in complex visual scenes.

Introduction

In the mid-1980s, postal automation faced a significant hurdle: while standard envelopes were easily processed, "flats" (magazines) and parcels remained a challenge. On a standard letter, the address is typically predictable. However, on a magazine cover, the address label might be placed anywhere amidst vibrant graphics, headlines, and advertisements.

The core challenge addressed by ABLS is balancing model-based reasoning—effective for predictable structures—with randomness handling, which is essential when those structures break down. The system must utilize spatial "rules of thumb" without being blinded by them when a mail piece deviates from the norm.

Architecture and Methodology

ABLS is built upon several sophisticated AI architectural patterns to manage the complexity of mail piece analysis. Central to the system is a Blackboard Architecture, which serves as a shared memory space for the current state of image analysis, including candidate blocks, hypotheses, and context frames.

The ABLS system architecture, featuring a blackboard, system manager, and tool manager.

Key components of the methodology include:

  • Specialized Tool Box: Rather than relying on a single algorithm, ABLS uses a suite of independent experts. These include adaptive and color thresholding to extract text from complex backgrounds, bottom-up segmenters to group characters, and texture discriminators to identify machine-printed or dot-matrix labels.
  • Tool Manager & Dependency Graph: To optimize computational resources, a Tool Manager uses a dependency graph to plan the most efficient sequence of tool applications based on emerging evidence.
  • Evidence Combination: Because different tools may provide conflicting data, the system utilizes Dempster-Shafer theory to combine confidence values and manage uncertainty across various hypotheses.

The system distinguishes between "structured" mail, where it relies on spatial models, and "random" mail, where it must rely on visual features and syntax. A primary example of a random environment is a magazine cover, where the address block is just one of many competing visual elements.

A magazine cover representing a 'random' environment where address location is challenging.

In these cases, ABLS uses "Compatibility Rules" to resolve ambiguity. For instance, if a candidate block is located in a position that spatial rules suggest is reserved for a postage stamp, the system can confidently refute the hypothesis that it is the destination address. This context-driven planning allows the system to maintain a "context frame" that tracks the difference between the current state and the goal, selecting tools that most effectively reduce ambiguity.

Key Insights and Results

The "Community of Experts" metaphor proved highly effective. By treating each tool as a local expert performing its own benefit/cost estimation, the system remains modular and extensible. Qualitative results demonstrated success in several difficult categories:

  • Magazine Covers: Using color thresholding and shape analysis, the system successfully filtered out graphics to isolate address labels.
  • Catalogs: Texture discriminators were used to identify dot-matrix printed labels, a high-confidence indicator for destination address blocks in that context.
  • Flexibility: The system demonstrated a robust ability to transition its logic based on the detected context of the mail piece.

Limitations and Future Work

Despite its successes, ABLS faced significant hurdles in 1986. The image processing tools were computationally intensive and slow, making real-time postal sorting difficult with the hardware of the era. Additionally, while the system could handle 90-degree rotations, it still assumed mail pieces were roughly rectangular and aligned. The authors noted that future development would require more refined tools and a broader variety of expert modules to handle increasingly complex commercial mail designs.

Summary updated

BibTeX
@inproceedings{wang1986object,
  author = {Ching-Huei Wang and Sargur N. Srihari},
  title = {{Object Recognition in Structured and Random Environments: Locating Address Blocks on Mail Pieces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure