Shape Abstraction and Multi-Resolution Sketching

Amitabha Mukerjee
Center for Robotics and Dept of Mechanical Engineering
I.I.T. Kanpur, Kanpur 208016, INDIA
(e-mail: amit@iitk.ernet.in)

Nishant Mittal
Department of Computer Science
University of Texas, Austin
(e-mail: nishant@cs.utexas.edu)

Problem

Shape information is often required at many levels of approximation The Idealization Problem is that of finding the "right" level of approximation for a given task. Such models need to be definable at continuously varying resolutions, to handle a wide range of abstractions, and also to be reconstructible for the user to see.

In many spatial tasks, such as describing abstract shape (e.g. sketches), there is a further problem - different parts of the model may have different resolutions. We call this the Multi-Scale Idealization Problem.

Method: Qualitative-Quantitative Hybrid

We propose a new model for shape idealization based on qualitative-quantitative hybrid reasoning. The fundamental difference with traditional models is that the basic resolution itself is variable, and can adopt any of a series of smoothly varying discretizations (rough set categories) depending on the accuracy for the task at hand. We use a quantitative-qualitative hybrid discretization chosen according to a formal notion which we call "k-properness," implying that the result of certain operations are limited to k data intervals. These are used in a axis-based model for 2D contours using line-set voronoi diagrams. The contour is swept and deformed to obtain 3D shapes. Models at any given level of resolution can then be reconstructed and visualized by identifying a sample from the valid object space. We have compared this model with purely qualitative and frequency domain models of shape. The same set of objects are modeled using different discretizations, and the results compared in recognizability through cognitive tests on human users as also by numerical deviation from the original data. Fourier series models are compared only numerically. Result indicate a high degree of recognizability even at very great abstraction levels (10^-6 of the quantitative for some simpler objects), reflecting the salience preserving property of this representation. In areas such as pattern recognition, conceptual design or diagram understanding, shape information is often required at many levels of approximation (the problem of idealization). Currently, different idealizations are usually pre-chosen by the programmer, but computational approaches to approximation modeling are beginning to emerge, both for general reasoning models as well as for geometric objects [1,2]. Approximating models of a spatial nature is more complex since metric information such as distance, and also derivative concepts such as size, angles, or area are non-qualitative in nature, and are harder to abstract. The problem is made even more difficult since the traditional tools for spatial modeling are boundary-driven, and are often degenerate under information loss. In order to be able to develop models with wide capability for shape abstraction, an entirely different paradigm needs to be developed.

The qualities that we are seeking are that the model a) be capable of incremental refinement, as finer categories become needed in the representation, and that b) should handle a relatively wide range of abstractions, c) should not be so abstract as to be incapable of being visualized, and d) apply to both two and three dimensions (for the time being).

In this work, we explore such a paradigm evolving from research in the area of qualitative-quantitative hybrid reasoning. The fundamental aspect in which this approach differs from traditional quantitative models is in the discretization used. We investigate three different non-quantitative discretizations:

  1. A "qualitative" discretization, a term that has lent itself to much abuse in the recent past. By this word here, we mean a discretization that is a function of certain non-subjective aspects of the objects themselves, such as the tangencies and alignments between two neighbouring objects. All qualitative models, in this authors view, must start with a clear definition of this discretization. Any deviation from this definition constitutes a hybrid model.
  2. A "categoric" discretization. Instead of using quantitative numbers, we use categories, and construct an algebra capable of representing geometries and shapes. The categories may be fuzzy or rough, and need suitable membership functions.
  3. A "spatial frequency" characterization, where 2-D contours are represented as fourier functions; as the highest frequency increases, a shape contour can be more and more accurately represented.

The basic geometry is represented in terms of axial information and not in terms of the boundary. Three-dimensional models are similar to the generalized cylinder paradigm, where the swept contour is modeled using a line-set voronoi diagram to obtain the axis information. The parameters of the model are represented in the three levels of discretization described above. The purely qualitative model, based on tangencies and relative directions [3] results in wide variability in object shape, and is suited only for the simplest geometries. The spatial frequency model is compact and smooth, but does not provide good shape abstraction (into symbolic classes). The categoric discretization, which in our case is a quantitative-qualitative hybrid discretization, is found to be the most promising. We define a notion of "k-properness" for rough sets under a given class of operations, if the result data be limited to k data intervals. "K-proper" discretizations for the real line and the circle are used to model the axes and relative angles in the line-set voronoi diagrams for 2D shapes. The 3D axes of deformation are also represented using rough set quadrants. Models at any given level of resolution can then be reconstructed and visualized by identifying a sample from the valid object space.

The categoric and spatial frequency models have been implemented and tested both numerically and on human users. The same set of objects are modeled using different discretizations, and the results compared in recognizability through psychological tests on humans as also by numerical deviation from the original data. Fourier series models are compared only numerically. Result indicate a high degree of recognizability even at very great abstraction levels (10^-6 of the quantitative for some simpler objects), reflecting the salience preserving property of this representation.

KEYWORDS

Shape Modeling,
Idealization,
Geometric modeling,
Artificial Intelligence,
Spatial Reasoning,
Diagram Understanding,
Pattern Recognition.

References

  1. Agrawal, Ram Bhushan, Amitabha Mukerjee, and Kalyanmoy Deb, 1995 Modelling of Inexact 2-D Shapes using Real-coded Genetic Algorithms, Proceedings of the Symposium on Genetic Algorithms, March 25, 1995, Dehradun, India, p.41-49
  2. Falkenhainer, B.; and K.D. Forbus, 1991 Compositional modeling: finding the right model for the job, Artificial Intelligence, v.51:95-143.
  3. Hobbs, Jerry R., 1975 Granularity, IJCAI-75, p.432-435. Section 7.7, p.542-552.
  4. King, Joseph Scott, and Amitabha Mukerjee, 1990 Inexact Visualization, Proceedings of the IEEE Conference on Biomedical Visualization, Atlanta GA, May 22-25, 1990, p.136-143.
  5. Mukerjee, Amitabha, and Gene Joe, 1990 A qualitative model for space, AAAI-90, July 29-Aug 3, Boston, p.721-727.
  6. Mukerjee, Amitabha, and Nishant Mittal, 1994 A qualitative representation of frame-transformation motions in 3-dimensional space Proceedings of the IEEE Conference on Robotics & Automation, Nagoya, Japan 1995, Longer version in IIT Kanpur Department of Mechanical Engg, Technical report ME-94-026.
  7. Mukerjee, Amitabha, 1994 Metric-less Modeling of One, Two and Three Dimensional Metric Spaces AAAI Workshop on Spatial and Temporal Reasoning, Seattle, July 1994.
  8. Weld, Daniel S., 1988 Theories of comparative analysis, PhD Thesis, MIT AI TR 1035, May 1988, 174 pages.
amit@iitk.ernet.in