Representing size functions by complex polynomials

Massimo Ferri 1, Claudia Landi 2

1Dip. di Matematica, Università di Bologna,
I-40126 Bologna, Italy
E-mail: ferri@dm.unibo.it
2Dip. di Matematica, Università di Pisa,
I-56127 Pisa, Italy
E-mail: landi@dm.unipi.it

Keywords: Size function, distance, polynomial, multiplicity, pattern recognition, shape descriptor.

1. Introduction.

Size functions are shape descriptors of a geometrical-topological nature. They prove to be particularly useful in the classification of natural images, such as white blood cells [4], letters of the sign language [5], hand-written characters [3], signatures [2], hand-drawn sketches [1] and the like. Whatever the input, their output is always an integer valued function on R2, or rather on the half-plane xy. For definitions and general information on the theory of size functions, see [5, 7]; you can also visit the site www.dm.unibo.it/~ferri/vismath/sizefcts/sf.htm.

Previous research has recognized the special rôle of certain points of the plane (called “cornerpoints”), which condense all information for reconstructing a size function. Therefore, a synthetic representation was proposed, as a formal series of points of the plane [5].

Here we want to present a new representation of size functions, by complex polynomials. The basic idea is fairly simple: Think of points of the plane as of complex numbers, and use a polynomial instead of its solution set. Some necessary adaptations are developed, in order to grant an efficient comparison of size functions by a “natural” comparison of polynomials.

2. Shrinking the diagonal.

The leading comparison principle for size functions, via their cornerpoints, is very simple: Similar shapes correspond to close point sets. However, a very important heuristic correction is needed: Cornerpoints close to the “diagonal” x=y are to be considered close to each other. This agrees with the fact that such cornerpoints are often the result of noise.

Instead of modifying the distance, we have preferred to transform the sets. I.e., we shall codify by polynomials, not the true cornerpoints, but their images through the following map f: R2C.

3. Polynomials and their comparison.

A further needed feature of a good representation of size functions is the following. Cornerpoints with multiplicity greater than one reveal some sort of symmetry in the original image. This may be unstable, and a similar image might lose that symmetry: In place of a single point with multiplicity s one might find a cluster of several close points, whose multiplicities sum to s.

This suggests the following definition of the size polynomial associated to a size function ℓ: let Pi, i=1, ... , m be the cornerpoints of  ℓ not lying on the diagonal, and s(i) be the respective multiplicity. f is the function defined in the preceding section. Then we define

As a distance between size polynomials, we propose the following. Write p(x) as

and order its coefficients in a sequence, but by decreasing index, skipping the leading coefficient (always equal to one), and completing with zeroes beyond the constant term a0  (always 0), i.e. 

If another polynomial q(x) is represented by an analogous sequence (f1,...,fn,,0,...), then define the distance between p(x) and q(x) as

so as to reduce the influence of roots near zero, i.e. of cornerpoints near the diagonal. The chosen ordering makes the comparison happen between analogous symmetric functions of the roots, the stress being on the lower order ones. Also breaking of symmetries is dealt with fairly well.

4. Inclusion.

An important issue of size function is inclusion of a particular pattern in the set of cornerpoints: It may reveal the presence of a predefined object in an image, or – more generally – of a queried feature. Now, inclusion translates into divisibility of polynomials, so also this issue can be faced algebraically.

References.

[1]	Collina, C., Ferri, M., Frosini, P. and Porcellini, E., SketchUp: Towards qualitative shape data management, Proc. ACCV'98, Hong Kong 8-10 Jan. 1998, Springer LNCS 1351, vol. 1 (1998), 338-343.

[2]	Donatini, P., Frosini, P. and Lovato, A., Size functions for signature recognition, Proc. SPIE Workshop “Vision Geometry VII”, 3454 (1998), 178-183.

[3]	Ferri, M., Gallina, S., Porcellini, E. and Serena, M., On-line character and writer recognition by size functions and fuzzy logic, Proc. ACCV '95, Dec. 5-8, Singapore, vol. 3 (1995), 622-626.

[4]	Ferri, M., Lombardini, S. and Pallotti, C., Leukocyte classification by size functions, Proc. 2nd IEEE Workshop on Applications of Computer Vision, Sarasota, 1994 Dec. 5-7 (1994), 223-229. 

[5]	Frosini, P. and Landi, C., Size theory as a topological tool for computer vision, Pattern Recogn. and Image Analysis (to appear).

[6]	Uras, C. and Verri, A., On the recognition of the alphabet of the sign language through size functions, Proc. XII IAPR Int. Conf. on Pattern Recogn., Jerusalem (Israel) II, IEEE Comp. Soc. Press, Los Alamitos, CA (1994), 334-338.

[7]	Verri, A., Uras, C., Frosini, P. and Ferri, M., On the use of size functions for shape analysis, Biol. Cybern. 70 (1993), 99-107.