Separating desired image and signal invariant components from extraneous variations

William J. Williams, Eugene J. Zalubas, Alfred O. HeroProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 1996 · DOI

TL;DR

This paper introduces a novel method for robust pattern recognition by first creating a Scale and Translation Invariant Representation (STIR) of an image or signal. This STIR is then processed using noise subspace techniques, inspired by high-resolution spectral analysis, to separate desired invariant features from extraneous variations like font style or noise, enabling more accurate classification.

What Problem Does This Paper Address?

Recognizing patterns in images and signals is a fundamental task, but it's often hampered by variations in the data. While techniques exist to make representations invariant to transformations like translation and scaling, distinguishing between different classes of patterns (e.g., different fonts of the same letter) becomes challenging due to other factors like noise, printing artifacts, or subtle "style" differences. The paper aims to address this by developing a method that can disentangle these extraneous variations from the core invariant features, allowing for more reliable classification.

Methods

The core of the proposed method involves two main stages:

  1. Scale and Translation Invariant Representation (STIR):
    • 2D Autocorrelation: This step is used to remove translational effects. The autocorrelation function provides a stable origin and is invariant to shifts in the image.
  2. 2D Scale Transform: Applied to the autocorrelation result, this transform aims to remove scaling effects, making the representation invariant to size changes. The paper details a direct discrete approximation of the scale transform.
  3. Quadrant Functions: The autocorrelation plane is divided into quadrants, and the scale transform is applied to specific quadrants (Q1 and Q2) to capture relevant information.
  4. Normalization: The resulting scale transform magnitudes are normalized to ensure scale invariance.
  5. Noise Subspace Classification:
    • Singular Value Decomposition (SVD): The STIR vectors (reshaped from the scale-transformed matrices) are analyzed using SVD.
  6. Noise Subspace Identification: Inspired by high-resolution spectral analysis, the paper leverages the concept of a "noise subspace." For a given class of training data, an orthogonal subspace is created.
  7. Classification: A test STIR vector is projected onto the noise subspace of each candidate class. A small projection (or a zero inner product with "noise vectors") indicates that the test vector belongs to that class. The method aims to identify subspaces with minimal overlap and accurately identify each subspace.

Datasets

The paper uses a dataset of lowercase letters from three different fonts (Courier, Helvetica, Times) across various point sizes (14, 18, 24, 28). These were generated from faxed versions of clean printed copy. The dataset was used for both training and testing, with the testing performed on characters of a different size (20pt) than some of the training data.

Key Insights and Ideas

  • Decomposing Invariances: The paper highlights that achieving invariance to translation and scale is a necessary but not sufficient step for robust recognition. The real challenge lies in separating these core invariances from other variations that define different classes.
  • Leveraging Noise Subspace: The novel application of noise subspace concepts, borrowed from spectral analysis, to pattern classification is a key insight. By identifying vectors orthogonal to the "signal" (desired invariant features), these vectors can act as discriminators for different classes.
  • STIR as a Feature Vector: The STIR representation, by combining autocorrelation and scale transform, effectively creates a compact feature vector that is invariant to translation and scale, making it suitable for subsequent classification.
  • Graceful Degradation: The method shows a "graceful degradation" when faced with noise or variations, meaning errors are often confined to misclassifications between similar characters rather than complete failure.

Key Results

  • Font Classification: The font classification step achieved perfect accuracy (100%) on 78 test characters (20pt size) from the three fonts.
  • Character Classification: For character determination within a known font, 75 out of 78 test characters were correctly classified.
  • Misclassifications: The misclassifications primarily occurred between characters that are 180-degree rotations of each other (e.g., 'd'/'p', 'u'/'n'), a known limitation due to the autocorrelation step.

Limitations and Future Work

  • 180-Degree Rotation Ambiguity: The autocorrelation step inherently loses phase information, leading to indistinguishable representations for 180-degree rotated versions of characters. This is acknowledged as a limitation, and the authors suggest that additional structural examination would be needed in a complete character recognition engine to resolve these ambiguities.
  • Segmentation Omitted: The paper focuses on the classification of individual character bitmaps and explicitly omits the task of image segmentation.
  • Contextual Information Not Used: Positioning within a word or line, adjacent characters, and character frequency are not utilized in the current approach.
  • Future Work: The authors plan to extend the method to space-spatial frequency representations and explore further optimizations for processing speed by adjusting the number of row and column scale coefficients. They also suggest that the method's robustness to noise and variations indicates potential for considerable improvement in refined versions.

Summary updated

Abstract

Images and signals can be characterized by representations invariant to time shifts, spatial shifts, frequency shifts, and scale changes as the situation dictates. Advances in time-frequency analysis and scale transform techniques have made this possible. The next step is to distinguish between invariant forms representing different classes of image or signal. Unfortunately, additional factors such as noise contamination and `style' differences complicate this. A ready example is found in text, where letters and words may vary in size and position within the image segment being examined. Examples of complicating variations include font used, corruption during fax transmission, and printer characteristics. The solution advanced in this paper is to cast the desired invariants into separate subspaces for each extraneous factor or group of factors. The first goal is to have minimal overlap between these subspaces and the second goal is to be able to identify each subspace accurately. Concepts borrowed from high-resolution spectral analysis, but adapted uniquely to this problem have been found to be useful in this context. Once the pertinent subspace is identified, the recognition of a particular invariant form within this subspace is relatively simple using well-known singular value decomposition techniques.
BibTeX
@inproceedings{williams1996separating,
  author = {William J. Williams and Eugene J. Zalubas and Alfred O. Hero},
  title = {{Separating desired image and signal invariant components from extraneous variations}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {1996},
  doi = {10.1117/12.255439},
}
Figure