Discrepancy: Local/Global Shape Characterization with a Roundness Bias

Abstract

Disk shape frequently appears as a reference in shape characterization applications. We propose a local measure of deviation from a disk as the local difference between numerical solution of a PDE on the shape and an analytical expression in the form of modified Bessel function. The deviation defined at each shape point defines a field over the shape. This field has useful properties, which we demonstrate via illustrative applications ranging from shape decomposition to shape characterization. Furthermore, we show that a global measure extracted from the field is capable of characterizing the body roundness and periphery thickness uniformity.

1 Introduction

In the field of shape characterization, in one end of the spectrum are the structural descriptors in the form of part hierarchy trees or skeleton graphs extracted from distance transforms. They have been successfully employed in characterizing shapes with well-defined part hierarchy with semantically meaningful parts, e.g., a horse shape. In the other end of the spectrum are the global descriptors such as moments and specialized descriptors derived from moments, which may be better suited for shape collections that lack certain analytical hierarchy and as well as strong semantic meaning for either within the collection or within a particular member of the collection.

In this paper, we propose an alternative characterization equally suitable for shapes of both types. In the proposed scheme, a shape is modeled via a field defined on the entire shape domain where the field value is calculated locally using a reference shape and a global parameter. Specifically, the reference shape is a disk and the global parameter is the radius of the disk. The intuitive idea is to measure (at each shape location) the deviation of the local configuration from the reference shape. We call this field as discrepancy. If the shape is a perfect disk, discrepancy is uniformly zero.

Disk shape frequently appears as a reference in shape characterization applications since it has a simple form with fundamental properties such as compactness, convexity, isotropy, uniformity of distance from boundary to center, uniformity of boundary curvature. Different from the global shape measures that assign a single scalar value to a given shape, discrepancy provides richer information where it attains a value at each point of the shape domain when necessary global measures can be calculated using the field values.

A novel feature of our proposed scheme is that we calculate deviation from the reference disk indirectly using an auxiliary field. This makes calculations easy and robust. The auxiliary field is easily computable for an arbitrary shape using numerical methods. Furthermore, for a disk shape, the field value which depends only on the radial distance can be expressed in analytical form via special functions. Hence, we do not need to actually generate a digital disk.

The intuitive idea is explained in Fig. 1. Consider a disk with a triangular protrusion on top. In Fig. 1a–c, the cyan dot shows a domain point. In each case, an imaginary circle (red) which is tangent to the nearest boundary point and with the radius A equal to the radius of the maximal inscribed disk is drawn.

The first location, cyan dot shown in (a), is away from the triangular protrusion, and its local circle coincides with the maximal inscribed circle. The second location, cyan dot shown in (b), is still inside the disk, but in the upper half closer to the protrusion. The third location, cyan dot shown in (c), is in the protruding region. The cyan line segment measures the distance d between the point and its nearest boundary point. Notice that $A-d$ is the distance from the disk center to the cyan dot’s location. Discrepancy at each shape point is computed as the difference between the value of the auxiliary field and the value that the auxiliary field would take on a disk point located at the radial distance $A-d$. That is, discrepancy is a local property biased by the global shape.

1.1 Related Work

In [13], a global measure of circularity is derived using a geometric moment invariant of a disk shape and it is utilized in image processing tasks from medical, industrial and astronomical applications. As any ellipse can be obtained by applying an affine transform to a disk, an ellipticity measure is presented in [9] using an affine moment invariant of a disk shape where a highest possible ellipticity is assigned to all the ellipses, including circles. In [1], a family of ellipticity measures which distinguishes among ellipses of different aspect ratios is defined and applied to the galaxy classification problem. A generalization of moment-based circularity and ellipticity measures is presented in [7] so that they can be applied to higher-dimensional data. A probabilistic approach is followed in [4] to obtain a circularity measure which is not affected by discrete resolution, region overlaps or noisy/partial boundary.

Fig. 1

Imaginary reference disk at three distinct shape points marked via cyan dot in (a–c) (Color figure online)

In [8], a review of several methods which measure circularity and compactness of discrete shape regions is presented where the methods are divided into three main groups one of which is reference shape approaches. It is noted that generation of digitalized reference disks is a drawback of the reference shape approaches. We remark that while computing discrepancy, we do not need to generate a digitalized reference disk since we obtain the corresponding distance function of the reference disk analytically.

The auxiliary field we use is governed by screened Poisson equation. This equation has been successfully employed in shape analysis in approximating curvature dependent shape evolution and skeleton computation. Equipped with non-local terms, it is used to construct fluctuating distance fields that naturally split shape domain into perceptual parts [3, 10, 11]. In the present work, we merely use screened Poisson equation as an auxiliary mechanism.

2 Discrepancy

As the auxiliary field, we prefer a field that can be easily computable for an arbitrary shape and analytically computable (i.e., expressible in terms of mathematical functions) for the reference shape so that we do not need to digitally generate the reference shape. This motivated us to employ the screened Poisson equation. Other means may also be considered. Due to circular symmetry of the reference disk, the solution of the screened Poisson equation is rotationally invariant and hence characterized by only the radial distance $A-d$.

Let the shape S be an open connected bounded set with boundary $\partial S$. Let $v: S \rightarrow \ R$ be a mapping governed by the screened Poisson equation

$$\begin{aligned} ( \varDelta - a^2) v = 0 \text{ subject } \text{ to } v \left| _{\partial S} = 1 \right. \end{aligned}$$

(1)

where $\varDelta$ denotes the Laplace operator $\frac{\partial ^2}{\partial x^2} + \frac{\partial ^2}{\partial y^2}$. The solution to (1) can be easily calculated with numerical methods. A sample v function is depicted in Fig. 2a. Due to the selected uniform inhomogeneous boundary condition, v attains the highest value 1 at $\partial S$ and decays toward the interior regions.

Now let us consider the same equation on $\varOmega$, an open disk of radius A, with boundary $\partial \varOmega$,

$$\begin{aligned} ( \varDelta - a^2) v = 0 \text{ subject } \text{ to } v \left| _{\partial \varOmega } = 1 \right. \end{aligned}$$

(2)

Fig. 2

Illustration for the disk with an appendage. a The v function serving as the auxiliary field. b Discrepancy. c Analytical solution via Bessel functions extended to the shape domain

Due to rotational symmetry of $\varOmega$, the solution v depends only on the radial distance. Expressing the Laplace operator in polar coordinates yields the polar form of (2) in polar coordinates,

$$\begin{aligned} \begin{aligned} \left( \frac{\partial ^2}{\partial r^2} + \frac{1}{r} \frac{\partial }{\partial r} + \right.&\left. \frac{1}{r^2} \frac{\partial ^2}{\partial \theta ^2} - a^2 \right) v(r,\theta ) = 0 \\&\text{ subject } \text{ to } v \left| _{\partial \varOmega } = 1 \right. \end{aligned} \end{aligned}$$

(3)

where $0 \le r \le A$ and $0 \le \theta \le 2\pi$.

As we derive in Sect. 2.1, solution to (3) can be obtained in analytical form as

$$\begin{aligned} v (r,\theta ) = \frac{I_0(ar)}{I_0(aA)} \end{aligned}$$

(4)

where $I_0$ denotes the zeroth-order modified Bessel function of the first kind. Notice that $v (r,\theta )$ depends only on r, the radial distance from the disk center. That is, the solution is rotationally invariant. The circular symmetry and simplicity of the form (4) follow from the choice of uniform boundary condition, as detailed in Sect. 2.1.

Now, let S be an arbitrary shape with the maximal inscribed circle of radius A. Let us denote the solution of (1) for S using any numerical means as $v_S$ and $v^\varOmega$ to denote the analytical solution for the disk of appropriate radius. If the arbitrary shape S happens to be a disk, then we can speak of $v^\varOmega - v_S$ which is zero up to a numerical accuracy. Suppose the disk is perturbed via a small triangular appendage (previously shown in Fig. 1). Imagine the maximal inscribed circle in $S \cup \partial S$. Except for its small fragment, it will coincide with $\partial S$. On the small fragment, the solution $v_S$ will be smaller than 1, decaying further toward the fragment center. Now, one can imagine a new disk with a non-uniform boundary condition $f(\theta )$. Inside this new disk, because the propagated values from the boundary are lower than 1 at certain angles (direction of the triangular appendage), the realized solution becomes lower than the analytical estimate obtained via (4) under the assumption of uniform boundary condition $f(\theta )=1$.

As S deviates more and more from disk, discrepancy will diverge more and more from the zero. The question is how to calculate discrepancy for points in S that do not coincide with the points in $\varOmega$. That is, we need an ability to produce an estimate of the analytical solution at those domain points falling out of the imaginary inscribed circle. Toward this end, we may utilize for each point p, its minimal distance d(p) to $\partial S$. Then, take r as $A-d(p)$. This is equivalent to imagining a local scenario where the point is at radial position $A-d(p)$ in polar coordinates centered at the center of a putative circle of radius A passing through the nearest boundary point of p. Notice that $0 \le d(p) \le A$ for all $p \in S$. Let $v^{S\rightarrow \varOmega }$ denote the analytical solution extended to entire S, then

$$\begin{aligned} v^{S\rightarrow \varOmega }(p) = \frac{I_0(a \left( A-d(p) \right) )}{I_0(aA)} \end{aligned}$$

(5)

Consequently, discrepancy is

$$\begin{aligned} D(p) = \frac{I_0(a \left( A-d(p) \right) )}{I_0(aA)} - v_{S}(p) \end{aligned}$$

(6)

If p happens to be on an appendage considerably narrower as compared to thickest part, such as the case in Fig. 1c, the analytical estimate will be lower than the numerical solution. This is because the numerical solution depends on the values propagated from the shape boundary (mainly the boundary of the appendage), whereas the analytical solution depends on the values propagated from the boundary of the imaginary circle associated with the point. As the point is closer to the shape boundary compared to the boundary of its associated imaginary circle, the numerical solution is higher than the analytical estimate. In contrast, as discussed before, in the innermost parts, analytical estimate will be higher than the realized numerical solution.

If the shape is a disk with an appendage or protrusion, then it is expected that discrepancy on the appendage or protrusion will be negative, whereas on an inscribed central disk it is positive. An illustration on the disk with an appendage is shown in Fig. 2.

We note that $-\,1< D(p) < 1$ for all $p \in S$ since $0< v^{S\rightarrow \varOmega }(p) < 1$ and $0< v_{S}(p) < 1$ for all $p \in S$.

2.1 Derivation of the Analytical Solution

Using separation of variables, we can express $v(r,\theta )$ as

$$\begin{aligned} v(r,\theta ) = R(r) \, \phi (\theta ),\quad \text{ where } {0 \le r \le A} \text{ and } {0 \le \theta \le 2\pi } \end{aligned}$$

Then, the partial differential equation (3) becomes

$$\begin{aligned}&r^2 \frac{R''}{R} + r \frac{R'}{R} + \frac{\phi ''}{\phi } - a^2 r^2 = 0 \nonumber \\&\quad \implies \frac{\phi ''}{\phi } = a^2 r^2 - r^2 \frac{R''}{R} - r \frac{R'}{R} = k \end{aligned}$$

(7)

Pulling the first equality in (7) yields

$$\begin{aligned} {\phi ''} - k \phi = 0 \end{aligned}$$

(8)

The boundary conditions on $\phi (\theta )$, $\phi (\theta ) = \phi (\theta +2\pi )$ and $\phi '(\theta ) = \phi '(\theta +2\pi )$, impose periodicity of $\phi$; hence, k cannot be positive. The solution to $\phi (\theta )$ is complex Fourier series. Thus, taking $k=-n^2$ where n is an integer, unit solutions are of the form, $c_{1,n} \, \sin (n \theta ) \, + c_{2,n} \, \cos (n \theta )$.

Pulling the second equality in (7) yields

$$\begin{aligned} r^2 R'' + r R' - (a^2 r^2 + n^2) R = 0 \end{aligned}$$

(9)

Note that (9) is the modified Bessel equation of order n. Its general solution is of the form, $c_{3,n} \, I_n(ar) + c_{4,n} \, K_n(ar)$ where $I_n$ is called as the nth-order modified Bessel function of the first kind and $K_n$ as the nth-order modified Bessel function of the second kind. Because $\lim _{r \rightarrow 0} {K_{n}} \rightarrow \infty$ even though $R(0) \text{ is } \text{ finite }$, the second term should disappear.

Combining the respective solutions for $\phi (\theta )$ and R(r) yields

$$\begin{aligned} v (r, \theta ) = \displaystyle \sum _{n=0}^{\infty } [ d_n \, I_n(ar) \sin (n \theta ) + e_n \, I_n(ar) \cos (n \theta ) ] \end{aligned}$$

(10)

First, let us consider $n=0$. (8) takes the form ${\phi ''}(\theta ) = 0$. Imposing the two boundary conditions, i.e.,$\phi (\theta ) = \phi (\theta +2\pi )$ and $\phi '(\theta ) = \phi '(\theta +2\pi )$, the solution for (8) is constant. Hence, we rewrite the general solution in the following form:

$$\begin{aligned} v(r,\theta ) =\,&e_0 I_0(ar) + \displaystyle \sum _{n=1}^{\infty } [ d_n \, I_n(ar) \sin (n \theta ) \nonumber \\&+ e_n \, I_n(ar) \cos (n \theta ) ] \end{aligned}$$

(11)

Finally, we need to determine $e_0$, $d_n$ and $e_n$. Using the condition at $r=A$:

$$\begin{aligned} v(A,\theta ) = 1 \end{aligned}$$

(12)

Hence,

$$\begin{aligned}&{e_0} \, I_0(aA) + \displaystyle \sum _{n=1}^{\infty } [ d_n \, I_n(aA) \sin (n \theta ) \nonumber \\&\quad + e_n \, I_n(aA) \cos (n \theta ) ] = 1 \end{aligned}$$

(13)

Integrating from 0 to $2\pi$:

$$\begin{aligned} e_0 \, I_0(aA) =\,&\frac{1}{2\pi } \int _0^{2\pi } {1 \, d\theta } = 1 \nonumber \\ \implies&e_0 =\frac{1}{I_0(aA)} \end{aligned}$$

(14)

Now, for $n \ne 0$,

$$\begin{aligned} d_n \, I_n(aA) =\,&\frac{1}{\pi } \int _0^{2\pi } {1 \sin (n \theta ) \, d\theta } \nonumber \\ =\,&-\frac{1}{n \pi } \cos (n\theta ) \Big |_0^{2\pi } \nonumber \\ \implies&d_n = 0 \end{aligned}$$

(15)

$$\begin{aligned} e_n \, I_n(aA) =\,&\frac{1}{\pi } \int _0^{2\pi } {1 \cos (n \theta ) \, d\theta } \nonumber \\ =\,&\frac{1}{n \pi } \sin (n\theta ) \Big |_0^{2\pi } = 0 \nonumber \\ \implies&e_n = 0 \end{aligned}$$

(16)

Based on (14)–(16) and (11),

$$\begin{aligned} v (r,\theta ) = \frac{I_0(ar)}{I_0(aA)} \, \end{aligned}$$

$\square$

2.2 Illustrative Results

In Fig. 3, illustrative discrepancy examples for 5 shapes from MPEG-7 dataset [5] are depicted. The highest positive values are attained on central regions, whereas the lowest negative values are attained on appendages, protrusions and boundary detail. For the three disks, discrepancy values are very close to zero. The case of disks is redisplayed at the bottom row where the dynamic range of the display is adjusted for improved visibility. Observe that placing regular circular bumps (middle) is less disturbing than irregular notching (right). The anisotropy of discrepancy in the later case is a consequence of non-uniform notching. The brighter central region of discrepancy extends toward the two deepest notches at approximately $120 ^\circ$ and $-\,30^\circ$.

Fig. 3

Highest positive values are attained in central regions, whereas the lowest negative values are attained on the appendages, protrusions and boundary detail. The bottom row depicts the first three shapes only. As seen in the color bar, the range of discrepancy for the three disks is quite low (Color figure online)

For an arbitrary shape, discrepancy takes both positive and negative values. However, for a perfect rod obtained by rolling a disk, all values are positive (see Fig. 4). The maximum value of discrepancy increases as the rod length increases.

Fig. 4

Discrepancy for two rods of varying length

Fig. 5

a–c Statistics of discrepancy at 6 different choices of a: 1 / (A), $1/(0.9\,A)$, $1/(0.8\,A)$, $1/(0.3\, A)$, $1/(0.2\,A)$ and $1/(0.1\,A)$. d Input shapes associated with x-axis

2.3 Entropy

For a perfect disk, discrepancy is uniformly zero; hence, discrepancy histogram is a scaled impulse. Consequently, the entropy is zero. If we add some noise, the entropy increases. Even for a noisy disk, the interior region with small positive discrepancy is significantly larger than the exterior region with negative discrepancy. If we add a smaller round piece on top of the disk (e.g., the handle of a pocket watch), the exterior region grows in size significantly contributing to an increase in the entropy. If, however, we make a hole in the handle to change the round handle to a ring of uniform thickness, two noteworthy effects are observed. First, the exterior region gets smaller. Second, the negative discrepancy distribution over the exterior region becomes more uniform. Note that discrepancy is a function of distance to boundary. Hence, discrepancy distribution over the ring of constant thickness has a lower variance compared to that over a disk of the same radius. Hence, the entropy decreases. If we consider putting together two disks of the same size, then both the size of exterior region and the overall entropy will decrease as compared to the size of the exterior region and the overall entropy obtained when the disks are of different size. The entropy in the interior region, however, may increase. This is because the interior region, depending on the neck thickness, may become more like a dumbbell rather than a disk.

2.4 Implementation Details

Shape interior is given by the blank (zero valued) pixels, whereas the outside set is fixed at 1 to represent the boundary condition. The distance transform is computed using the available MATLAB command, which is an implementation of the method in [6]. A is obtained as the maximum value of the distance transform. To compute the numerical solution on the shape domain, we discretize the PDE (1) on a standard grid via finite-difference method. The discretization yields a linear system of equations with sparse and symmetric positive definite system matrix. There is a plethora of direct and iterative alternatives to solve this system. We used a direct solver based on Cholesky factorization.

Fig. 6

Discrepancy for increasing values of a. From left to right, $a = 1/(0.1\, A)$, $a = 1/(0.5\, A)$, $a = 1/A$, and $a = 1/A^2$

The only parameter, a, is inversely related to the diffusion (smoothing radius). Hence, we take it on the order of the shape radius, i.e., we set it to 1 / A. As the diffusion level increases, the range of discrepancy decreases. Nevertheless, after level A, the overall pattern stabilizes. Hence, increasing diffusion level further becomes unnecessary. The illustrations in Figs. 5 and 6 also offer an experimental justification for fixing the value A as the diffusion level. In Fig. 5, we present statistics of discrepancy computed at six different choices of a for the input shapes shown in (d). Variation in the input shapes is due to the lower disk, which gradually increases in size and approaches to the upper disk. Notice that the reference shape (the maximal inscribed disk) remains the same for all input shapes. The maximum (positive) value of discrepancy, which results from the fact that the upper disk is a discretization of the reference shape, approaches to 0 as the diffusion level (1/a) increases. The minimum (negative) value of discrepancy, which is due to the difference between the lower disk and the reference shape, shows a smoother change as the diffusion level increases. Notice that the minimum value of discrepancy first decreases and then increases, which means that the lower disk is considered as a noise until it becomes comparable to the reference shape. Discrepancy entropy computed using the default bin size 0.001 shows compatible behavior for the different choices of a except 1 / (0.2A) and 1 / (0.1A) corresponding to very small diffusion levels. As evident in Fig. 6, increasing the level from A to $A^2$ does not bring further change to the pattern.

Fig. 7

a Discrepancy. b Signed distance with respect to maximal inscribed circle(s)

Fig. 8

Entropy order

2.5 Signed Distance with Respect to Maximal Inscribed Circle(s) Versus Discrepancy

Discrepancy behaves quite different than a signed distance field where the distances are calculated with respect maximal inscribed circle(s). The signed distance takes positive/negative values inside/outside maximal inscribed circle(s) where we linearly normalize the distances to have the maximum value of 1. The most obvious deficiency of any construction with reference to maximal inscribed circle(s) is the lack of representational stability. For example, consider a combination of two disks as shown in Fig. 7. In the first case, the disks have the same radius hence there are two maximal inscribed circles. In the second case, the radius of the lower disk is reduced just by 1 pixel, which is approximately 1–2%. We see that the signed distance shows an abrupt change against a small difference, whereas the discrepancy field exhibits a robust behavior.

3 Experiments-1: Entropy-Based Ordering

In the experiments, entropy values are calculated separately over the positive and the negative discrepancy values, and then, the shapes are ordered with respect to increasing mean entropy. The probability distribution of discrepancy values is obtained by constructing their histogram with a constant bin size and normalizing the histogram sum to 1. We compute discrepancy histogram by dividing the range $[-\,1, 1]$, which contains all possible values of discrepancy, into bins of equal size, and counting the number of shape pixels falling inside each bin. Default bin size is set 0.001.

Fig. 9

Entropy order. a Discrepancy. b Discrepancy (bin size 0.01). c Signed distance. d Signed distance (bin size 0.01)

In Fig. 8, we present the entropy-based ordering of the shapes from the beetle and the device-2 categories of MPEG7 dataset [5]. Considering the beetle shapes, the entropy decreases with respect to roundness of the body and uniformity of the peripheral limbs. Considering the device-2 shapes, the entropy increases as the central region shrinks and the branch thickness becomes comparable to the central region thickness, which means divergence from a disk. Considering both of the orderings, we see that the shapes in the same sub-category are in consecutive order in spite of the variations due to rotation, scaling, antenna/leg crops, boundary noise addition and branch bending.

In Fig. 9, we present the entropy ordering of sample shapes using discrepancy and the signed distance (see Sect. 2.5) where sensitivity to the bin size is illustrated by employing a different selection (0.01). First, consider the ordering in Fig. 9a for which discrepancy is used with the default bin size. As expected, the entropy is smaller for the first seven shapes, which are composed of three versions of a disk (a plain one, one with circular bumps, and one with boundary notching) and four pairwise combinations of disks with the same or slightly different radius weakly connected or fused. Adding peripheral parts to a circular shape increases the entropy as in the case of the apple, the pocket and the octopus. The entropy increases when the octopus has an elliptic body rather than a circular one. The half circle is far from being round, and the entropy further increases when it is notched. The entropy is high for the pocket and the bat shapes both of which have details of varying thickness. We observe that the entropy ordering is robust to the change of the bin size when discrepancy is employed (see Fig. 9a, b). Flips occur between consecutive shapes, but the essential ordering is preserved. For example, the first seven shapes composed of disks keep preceding the other shapes, the shapes formed via attaching peripheral parts to a circular body keep succeeding the disks, and etc. Now, consider the ordering in Fig. 9c obtained using the signed distance. The representational instability of the signed distance is observed in the ordering as the pairwise combinations of disks with slightly different radius are far from the combination with the identical disks. In Fig. 9c, d, we see that there are significant differences between the two orderings, and hence, the entropy ordering is sensitive to the bin size when the signed distance is employed. For example, the detailed pocket precedes the three disks in the first ordering, whereas it succeeds them in the second one or the octopus shapes precede one of the disks in the first ordering, whereas they succeed all of the disks in the second one.

4 Experiments-2: Grouping

Both the range and the distribution of discrepancy depend on the complex way the shape deviates from a disk. In particular, we expect that discrepancy distribution to be a good property and the difference between a pair of distributions to be a good measure of dissimilarity.

We perform illustrative context-dependent grouping experiments using discrepancy histogram as the only shape property to calculate pairwise distances. Since the purpose of our experiments is to give a proof of concept, we employ only a single property (histogram) and use the $L^1$ distance between two histograms as pairwise shape dissimilarity measure.

In order to define the pairwise histogram distance, we first construct normalized discrepancy histograms as described in Sect. 4 and we then compute the sum of the absolute value of the bin-wise differences.

Fig. 10

Grouping of the device-2 shapes using discrepancy histogram. Discrepancy is smoothed at different levels. In the last result, no smoothing is applied

Fig. 11

a–c Grouping of the beetle shapes using discrepancy histogram. Discrepancy is smoothed at different levels. In the last result, no smoothing is applied. d Sample shapes in their true scales

Let the number of shapes in the collection be n. We represent each shape using an n-vector of which components denote pairwise histogram distances between the respective shape and all the n shapes in the collection. To observe grouping effect, we map all nn-dimensional feature vectors to a plane. For this purpose, we use t-Distributed Stochastic Neighbor Embedding (t-SNE) [12] which aims to model each object by a two- or three-dimensional point in such a way that similar objects are modeled by nearby points, whereas dissimilar objects are modeled by distant points. Each of the n shapes can then be visualized as a point in the plane.

We conduct two distinct groups of experiments. In the first, the input set is composed of the shapes from a single category. That is we focus on fine-grained categorization. In the second, we explore the robustness of discrepancy histogram with respect to visual transformations including extreme articulations. We focus on context-dependent category characterization, starting with a small number of categories and then gradually increasing the number.

In the grouping experiments, we consider smoothed versions of discrepancy as well as its non-smoothed version. The smoothing is performed at two different levels via diffusion of discrepancy with homogeneous Neumann boundary condition where the diffusion time is chosen as (0.5A) and ${(0.5 A)}^{1/2}$. This is equivalent to convolving discrepancy with the Gaussian of standard deviation $\sigma = \mathcal {O}(A^{1/2})$ and $\sigma = \mathcal {O}(A^{1/4})$.

Shapes from a Single Category

We performed two experiments using, respectively, the device-2 and the beetle categories of the MPEG-7 data set [5]. Each of the two categories contains 20 instances.

Fig. 12

Shapes from 7 categories each with 20 instances

Fig. 13

Groupings using discrepancy histogram. Top: Discrepancy is smoothed with the Gaussian of standard deviation $\sigma = \mathcal {O}(A^{1/2})$. Bottom: No smoothing is applied. a The elephant, the hand and the human shapes. b The cat and the face shapes are added. c The ray and the chopper shapes are added

The results are presented in Figs. 10 and 11, respectively. The device-2 category contains plain, chiral and noisy versions of the some basic shapes, naturally forming several equivalence classes serving as fine-grained sub-categories. Likewise, the beetle category contains instances obtained via scaling, rotation, boundary noise addition or antenna/leg crops. To emphasize these sub-categories, we highlight the respective instances using the same color. Note that scale normalization is employed for better visualization of the grouping results. True scales of the shapes, however, are preserved during the experiments. In Fig. 11d, we exemplify the transformations by presenting sample shapes in their true scales.

Observe that discrepancy (whether it is smoothed or not) is robust to these transformations since the shapes highlighted with the same color are positioned very close to each other. Considering the groupings in Fig. 10, we see that the shape set is divided into two coarse groups: the shapes with a larger center and short protrusions are on one side, whereas the shapes with a smaller center and long prevailing branches are on the other. Considering the groupings in Fig. 11, we see that the beetle shapes are grouped according to the form of their body which is highly elongated for the shapes on one corner, whereas it is composed of more circular regions for the shapes on the other side. We obtain similar grouping results when no smoothing is applied (shown in (c)) or discrepancy is smoothed with the Gaussian of standard deviation $\sigma = \mathcal {O}(A^{1/2})$ (shown in (a)) or $\sigma = \mathcal {O}(A^{1/4})$ (shown in (b)).

Multi-Category Context-Dependent Grouping

We perform a sequence of grouping experiments using the shapes shown in Fig. 12. There are 7 categories each with 20 instances, taken from the dataset in [2]. Notice that there are significant variations between the shapes of the same category in terms of their scale and position of their articulations.

First, we consider the first 60 shapes in the elephant, the hand and the human categories. We obtain a grouping result in which the three categories are clearly separated from each other (see Fig. 13a). We observe that the distinctness between the categories is captured by discrepancy histogram despite the variation in the shapes with respect to their scale and articulations. In Table 1, we present the extrema of discrepancy. Observe that the maximum discrepancy decreases as the central region becomes rounder. For example, among the three categories, the maximum discrepancy is smaller for the hand shapes which have a circular palm in contrast to the elongated body of the human and the elephant shapes. Also, observe that the absolute value of the minimum discrepancy decreases as the limb to body thickness ratio becomes smaller. These observations are consistent with our expectation since the limiting case would be a disk shape (a perfect circle with no limbs) for which discrepancy is 0.

Table 1 Range of discrepancy smoothed with the Gaussian of standard deviation $\sigma = \mathcal {O}(A^{1/2})$ for 8 different shape categories

Next, we add 40 more shapes from the cat and the face categories extending the set to include 5 categories with the total of 100 shapes. Considering the body and limbs, the cat shapes can be regarded as similar to the elephant shapes. Considering the lack of protrusions, the face category appears significantly separate from the remaining four. The grouping result shown in Fig. 13b is consistent with our expectation since the cat shapes are clustered close to the elephant shapes and the face shapes form a new group far from the other clusters. If we include the horse category in the shape set, we see that the horse shapes are grouped in the vicinity of the elephants and the cats. Accordingly, in Table 1, we observe that discrepancy has a similar range for the cat, the elephant and the horse categories and its extrema are closer to 0 for the face category.

Finally, we extend the experimental set with the chopper and the ray shapes. The result is presented in Fig. 13c. First, observe that the chopper shapes are clustered as a separate group in the middle of the other groupings as the chopper category shows both similarities and differences to the other categories. For example, considering the chopper and the face categories, their positive sets are similar (see Table 1) but, unlike the face shapes, the chopper shapes have several protrusions. Likewise, considering the chopper and the elephant categories, they are composed of peripheral parts connected to a central body, but their parts are not compatible in terms of their number, size and thickness.

5 Experiments-3: Partitioning

As discrepancy attains positive and negative values where the positives are cumulated on the central region, we may consider splitting the shape domain into two subsets according to discrepancy sign. Another alternative is to use the mean value as a threshold. We have performed partitioning experiments using both alternatives on an extensive shape set and obtained a partitioning result equivalent to those in [3, 10, 11] in a much easier and faster way since one of the functions is calculated via table look up.

Fig. 14

a Discrepancy. b Thresholding at zero. c Thresholding at mean value. d–e Dilating the respective yellow zones (Color figure online)

In Fig. 14, partitioning feature of discrepancy is illustrated on two sample shapes. The first one is a giraffe shape with semantically meaningful parts consisting of the body, four legs, tail and head together with neck. The second one is an umbrella shape which can be partitioned into the handle, canopy and four bumps along the canopy edge. We present discrepancy for both shapes in Fig. 14a. By thresholding discrepancy according to its sign, we obtain the partitioning results shown in Fig. 14b which are consistent with our expectation. When we choose the mean discrepancy value as the threshold, central yellow zones shrink (see Fig. 14c). In Fig. 14d, e, we dilate the respective yellow zones given in Fig. 14 b, c using a circular structuring element whose radius at each point is determined via the distance to the nearest boundary point. In this way, the central regions touch the shape boundary and the remaining peripheral regions are further divided (see Fig. 14c, e).

Fig. 15

Sample partitionings via discrepancy. The mean value is used as threshold. The set composed of larger values is dilated

In Fig. 15, we present sample partitionings via discrepancy. We dilate the set composed of the shape points at which discrepancy is higher than the mean value. Observe how the central regions are captured by the yellow zones and the peripheral parts are obtained via the green sections. Also, we see that the partitioning results are consistent among the shapes from the same category.

In Fig. 16a, we present partitioning of the shape boundary for a set of shapes according to the sign of discrepancy. We smooth discrepancy slightly (see Fig. 16b) in order to filter the noise resulting from the discretization, especially near the shape boundary. Observe that the parts of the shapes corresponding to protrusions, appendages and boundary detail are successfully segmented by simple thresholding as discrepancy does most of the tricks. Also, note that the regions surrounded by green contours represent the shape features which are distinctive with respect to the reference shape, a disk with a radius equal to the maximum shape thickness where the thickness at each shape point depends on the distance to the nearest boundary point. First consider the disk shape with regular circular bumps. We see that the boundary detail, the circular bumps, is easily differentiated from the main disk shape. Next consider the four device-2 shapes whose branches are similarly segmented in spite of their variation due to bending, boundary noise and thickness change. Now consider the beetle shapes first of which seems to be more elongated compared to the second one. The head, tail and six legs are separated from the body for both shapes as illustrated by the corresponding green contour fragments. Finally consider the bird shapes which are segmented into the same semantically meaningful parts despite the variation between their bodies in terms of their elongation.

Fig. 16

Partitioning of the shape boundary for a set of shapes according to the sign of discrepancy. a No smoothing. b Smoothing with the Gaussian of standard deviation $\sigma = \mathcal {O}(A^{1/4})$

6 Summary and Conclusion

We provided a novel shape characterization tool called discrepancy. It measures deviation of the local configuration of each shape point from a reference disk indirectly using an auxiliary field. The radius of the reference disk, A, is determined as a global shape feature, the radius of the maximal inscribed disk of the shape. For the shape domain, the auxiliary field can be easily computed using numerical methods. For the reference disk, the auxiliary field depends on the radial distance and it is expressed in analytical form via special functions. For each shape point p at distance d(p) to the shape boundary, the corresponding reference point is a point in the disk with the radial position $A-d(p)$. As expected, for a perfect disk, the auxiliary field is the same for the shape and the reference disk; hence, discrepancy is uniformly zero. Considering an arbitrary shape, discrepancy attains the highest positive values on central regions, whereas it attains the lowest negative values on periphery.

We claimed that discrepancy is a powerful tool applicable to all planar shapes. To give a proof of concept, we experimented with illustrative applications. First, we demonstrated the capability of discrepancy entropy as a global measure of the roundness of the shape’s main body and the uniformity of the thickness of its periphery. Next, we demonstrated the potential of discrepancy histogram as a feature in context-dependent categorization and sub-categorization tasks. We experimentally observed that discrepancy is invariant to translation, rotation and scaling up to discretization differences as well as being robust to variation in articulations. Finally, we showed that it provides a natural binary partitioning of the shape domain.