Local Culprits of Shape Complexity

Abstract

Quantifying shape complexity is useful in several practical problems in addition to being interesting from a theoretical point of view. In this paper, instead of assigning a single global measure of complexity, we propose a distributed coding where to each point on the shape domain a measure of its contribution to complexity is assigned. We define the shape simplicity as the expressibility of the shape via a prototype shape. To keep discussions concrete we focus on a case where the prototype is a rectangle. Nevertheless, the constructions in the paper is valid in higher dimensions where the prototype is a hyper-cuboid. Thanks to the connection between differential operators and mathematical morphology, the proposed construction naturally extends to the case where diamonds serve as the prototypes.

1 Introduction

Given an 8-connected digital binary pattern representing a digital shape as a mapping $\mathbb {Z}^2 \rightarrow \left\{ 0,1 \right\}$, we are interested in quantifying, at each point on the pattern, the likelihood that the point belongs to a maximal prototype shape that fits the digital shape represented by the binary pattern in question. For the prototype shape, the measure is expected to be uniformly zero over the shape. The prototype shape serves as the simplest shape in a certain context.

The practical use of such a measure is two fold: First, if integrated over the pattern, the resulting number can be used as a measure of the tileability of the shape by the maximal prototype shape, which in turn can be used to quantify shape’s complexity. Second, directly as a local measure, it can be useful in identifying the locations to cut the shape so that the resulting pieces are tileable by the maximal prototype. A perfectly tileable shape can be digitally represented with maximum compression. By local culprits, we mean the points where the measure is significantly low, as they are the points responsible for the failure of tileability.

In this work, we focus on the case where the prototype shape is a rectangle. Nevertheless, as we discuss in Sect. 4, by changing the underlying metric the method naturally extends to the case where the prototype is a diamond. Though we illustrate the method only on 2D shapes (not necessarily simply connected), all discussions are valid in higher dimensions.

Quantifying rectangularity has practical uses in several applications e.g. urban planning and landscape ecology [1]. Rectangularity measures are also used to improve over-segmented images [2]. In the literature, there are several global measures for quantifying the conformity of a shape to a simple prototype [3,4,5]. These global measures do not convey point-wise information. For circular shapes defined in $\mathbb R^2$, the method in [6] provide local information for quantifying conformity to circles.

A related problem of recent interest is quantifying the complexity of high-dimensional datasets for estimating their classification difficulty. Varshney and Willsky [7] measured their classifiers in terms of level sets of the decision hypersurfaces’ geometrical complexity using ${\mathbf \epsilon }$-entropy. A growing number of works emphasize the role of the shape of the decision hypersurface as a determinant of either how complex the data is or how robust its classification by a certain classifier. An interesting claim by Fawzi et al. [8] is that vulnerability to adversarial attacks is related to positive curvature of the decision boundary. Fawzi et al. further attributed the robustness of the popular deep networks to the flatness of the shape of the produced decision boundaries.

Our construction relies on the connection between differential operators and shape sets, the so-called structuring elements of the mathematical morphology. Specifically, we resort to applying morphological derivatives to numerically approximate the infinity-Laplacian as in [9]. Proper numerical realizations of PDEs mimicking morphological process is an important issue. Among the recent works is [10] where the flux-corrected transport scheme to the PDE implementation of erosions and dilations with arbitrary structuring elements is considered.

2 Method

For a shape A, we consider the following PDE with the infinity Laplacian:

$$\begin{aligned} \left( \varDelta _\infty - \frac{1}{\rho ^2} \right) f_A = -1 \text{ subject } \text{ to } f_A \Big |_{\partial A} = 0. \end{aligned}$$

(1)

In numerical solutions to (1), $\rho$ is chosen to be equal to the shape radius, i.e. the maximal value of $L^\infty$ (chessboard) distance transform. After obtaining $f_A$, it is normalized such that the maximum value of the field is 1. These ensure the scale invariance of $f_A$. To acquire numerical solutions, the approximation to Laplace operator in $L^\infty$ [9],

$$\begin{aligned} \varDelta _\infty f_S(x) \approx \max _{y\in B(x)} f_S(y) + \min _{y\in B(x)} f_S(y) - 2 f_S(x) \end{aligned}$$

(2)

is used where B(x) denotes a unit ball centered at x. The numerical solution to (1) can be acquired by using the scheme proposed in [5].

This equation is favorable for us because the level curves of $f_A$ roughly serve as gradual transformation of the shape boundary $\partial A$ towards a square under the influence of the diffusion governed by the $L^\infty$ metric. The points at a system governed by (1) generate and cumulate the values of the field, $f_A$. For squares, due to their isotropy in $L^\infty$, the total accumulated values of points equidistant from the boundaries are the same. Therefore, for a square S, the value of the field at x depends only on the minimum distance of x to boundary (equivalently, on its distance to the shape center, by which we mean the points attaining the maximum distance transform value). The equidistant points form an equivalence class. As a result, the problem of acquiring an analytic solution reduces to disjoint one dimensional problems over regions of the square, which are continuous on the intersection on the regions.

Consider the points $P_1$ and $P_2$ as given in Fig. 1. Since they are equidistant from the boundaries, $f_S$ attains the same values at these two points by the above reasoning. Furthermore, this is true for all points having the same y coordinates in the shaded region $R_1$. In this region, $f_S$ changes in the y direction only, i.e. $\partial f_S / \partial x = 0$. Analogous arguments apply for points in $R_2$ where instead of y, x coordinates determine the equivalence classes. By the continuity of the field on the intersection of $R_1$ and $R_2$, the equivalence classes span both regions, and each is a square by itself.

Fig. 1.

Square with sides aligned with grid axes

With these, (1) reduces to

$$\begin{aligned} \begin{aligned} \frac{\partial ^2 f_S}{\partial y^2} - \frac{1}{\rho ^2} f_S&= -1, \quad \text {for } |y| \ge |x| \\ \frac{\partial ^2 f_S}{\partial x^2} - \frac{1}{\rho ^2} f_S&= -1, \quad \text {for } |y| \le |x| \\&\text {subject to } f_S\Big |_{\partial S} = 0. \end{aligned} \end{aligned}$$

(3)

In $R_1$, for the homogeneous part $f_{S,h} = A \exp \{ y/\rho \} + B \exp \{ -y/\rho \}$, and for the inhomogeneous part $f_{S,p} = \rho ^2$. Due to the symmetry of the boundary conditions, the acquired solution is invariant under $y \mapsto -y$ changes. This dictates $A = B$. Applying the boundary condition we acquire

$$ f_S\Big |_{R_1} = \rho ^2 -\rho ^2 \frac{e}{e^2+1} \left( \exp \left\{ \frac{y}{\rho } \right\} + \exp \left\{ -\frac{y}{\rho } \right\} \right) . $$

Following the same steps, the solution in $R_2$ is acquired. The joint solution is given in the closed form as

$$\begin{aligned} \begin{aligned} f_S&(x, y) = \rho ^2 - \rho ^2 \frac{e}{e^2+1} \times \\&\left( \exp \left\{ \frac{\max {\{|x|,|y|\}}}{\rho } \right\} + \exp \left\{ \frac{-\max {\{|x|,|y|\}}}{\rho } \right\} \right) . \end{aligned} \end{aligned}$$

(4)

Although this solution is derived for a square, it applies for rectangles as well. This is because the equivalence classes of a square, which are again squares, deform to rectangles: the distances to boundary and the shape center still add up to $\rho$ since the shape center is a line for a rectangle rather than a single point. The validity of the acquired solution for the elongated unit-circle (rectangle in this case) is due to $L^\infty$ norm, and in the general scheme does not hold. For example, in the case of $L^2$, an analytical solution for which is given in [6], circles are the corresponding equivalence classes, yet, the solution for circles does not apply for ellipses.

In the present form the solution is not translation invariant. To make it so, implicit reference to the origin should be removed. This can be satisfied by reformulating (4) in terms of $L^\infty$ distance transform since $\max {\{|x|,|y|\}} = \left\Vert (x,y) \right\Vert _\infty$. We acquire:

$$\begin{aligned} f_S = \rho ^2 - \rho ^2 \frac{e}{e^2+1} \left( \exp \{ t'^\infty \} + \exp \{-t'^\infty \} \right) \end{aligned}$$

(5)

where $t'^\infty = 1 - t^\infty / \rho$, and $t^\infty$ refers to $L^\infty$ distance transform of S.

In Fig. 2, the difference between the normalized (i.e. has 1 as its maximum value) numerical solution $\hat{f}_{S,numerical}$ and the normalized analytical solution $\hat{f}_{S,analytical}$ for a square of side length 256 is displayed.

Fig. 2.

$\hat{f}_{S,numerical}$ (left) and the difference $\hat{f}_{S,numerical} - \hat{f}_{S,analytical}$ (right)

The maxima of the non-normalized fields are 5766.3 and 5797.8, respectively. However, the mean error between the normalized fields is

$$ E = \dfrac{\int |\hat{f}_{S,numerical} - \hat{f}_{S,analytical}|}{|S|} = 0.001 $$

This is an acceptable error rate, considering that numerical solution is acquired to a first order approximation.

To construct a measure valid for all shapes, we need (5) to extend beyond rectangles. Thankfully, the solution is in terms of the distance transform of the shape and can be deployed as is as an extension of the field. Then for any shape A,

With the choice that we have here, we can assign scores of contribution to complexity to each point in the shape by simply subtracting the assumed extension from the numerically acquired solution. Thus we define the complexity encoding field $d_A$ as

This corresponds to measuring the error in assuming each point is coming from a square of radius $\rho$ in which the point is located $\rho \,t'^\infty$ away from the center.

Acquired fields, $\hat{f}_{A,numerical}$ and $d_A$, for a square with an appendage of size $64\times 128$ on one side are shown in Fig. 3.

Fig. 3.

A square with a rectangular appendage: $\hat{f}_{A,numerical}$ (left) and $d_A$ (right)

This, being one of the simplest cases of complexity, is informative in understanding the behavior of the proposed field. High negative values occur around the rectangular appendage. Pixels near boundary, be them of base square or appendage, attain smaller values and would be disregarded in a thresholded treatment of the field. The extrema is attained at the two center pixels in the vertical direction along the edge of the square.

3 Illustrative Experiments

In all the experimental results depicting $d_A$s, if the color bar is not shown, the color scale is between 0 and $-0.446$ where the yellow denotes zero. In the first experiment, we demonstrate the method on composite rectangles of constant width. The size of the square is $64\times 64$, i.e., one quarter of the previous square used in Fig. 2. As shown in Fig. 4, these shapes have no pixels that increase the complexity. Slight fluctuations in $d_A$ are due to the first order approximation to $f_{A,numerical}$.

Fig. 4.

Composite rectangles of constant width

In the second experiment, we apply the method to floor plans of increasing complexity. Results are depicted in Fig. 5. The first floor plan is composed of four identical rooms. This plan has no pixels that increase the complexity. As we introduce missing or extra segments, respective locations start to attain negative $d_A$ values. The last floor plan consists of multiple rooms of varying sizes. The two rooms of the largest size are deemed as the simplest with $d_A$ values near zero. $d_A$ attain higher negative values inside the smaller rooms. Note that the measure $d_A$ is parameterless. As such it implicitly measures the deviation from the rectangle that maximally fits into the shape due to the choice of $\rho$ (Sect. 2). Hence, smaller rooms are identified as parts of the plan that increase the plan’s complexity.

Fig. 5.

$d_A$s (top row) for some floor plans (bottom row)

For specific purposes, however, one might be tolerant of the size or interested in identifying complexity with reference to a prototype shape of certain size rather than the maximal size. To this end, one can simply treat $\rho$ as a parameter. In that case positive values for $d_A$ arise in the central parts of larger rectangles. This is illustrated in Fig. 6. The rightmost figure shows the original result from Fig. 5, i.e., $\rho ' = \rho$. In the remaining two results, notice that $d_A$s take both negative and positive values as indicated by the color bars. In the leftmost figure, $\rho ' = 8\rho /9$ coinciding with the width of the two identical square-shaped rooms on the right-side of the plan. Inside these two rooms $d_A$ is almost uniformly zero as indicated by the color bar. Furthermore, the number of pixels where $d_A$ is negative decreases.

Fig. 6.

When the critical width $\rho '$ is treated as a parameter

In the third experiment, we explore quantifying the shape complexity with a single value by using $1000 \times \text {mean}(|d_A|)$ rounded to the closest integer. Some illustrative results are shown in Fig. 7.

Fig. 7.

A variety of shapes of increasing complexity

In the final experiment we explore how we can simplify a complex shape towards a rectangle. We had observed that the local extrema of $d_A$ are near the centers of regions that increase complexity. Furthermore, at the extrema, the gradient of $f_{A,numerical}$ indicates the position of such regions relative to the shape body. Thus, the orthogonal direction to the gradient reveals the directions to cut in order to acquire a more rectangular shape.

As a proof of concept, we developed a greedy iterative algorithm. It uses both fields at each iteration step, $d_A$ providing information on the cut location and $f_{A,numerical}$ providing information on the cut direction. For example, for the square with an appendage (Fig. 3), the mean gradient of $f_{A,numerical}$ at the two neighboring extrema of $d_A$ has no component in y direction. Therefore, the shape is cut along the y direction from these extrema, separating the base square and the appendage.

Illustrative cuts are shown in Fig. 8. When determining the direction normal to the gradient, the numerically computed direction is replaced with the direction of closest axis if the angle between them is lesser than 2.86 degrees ($\approx \arctan 0.05$).

Fig. 8.

Iterative simplifications of various shapes towards a rectangle

4 Summary and Future Work

We proposed a new measure $d_A$ for distributed coding of the shape complexity. Each pixel on the shape is assigned a value $d_A$ quantifying the pixel’s contribution to overall complexity where the simplicity is understood as the expressibility of the shape in terms of an assumed prototype. Throughout the paper we assumed that the prototype is a rectangle (or hyper-cuboid in higher dimensions). We have performed proof of concept experiments to demonstrate the practical applicability of the method.

To first order approximation, the proposed method relies on partial differential equations driven by the morphological Laplacian. An interesting future research based on this would be changing the underlying metric and using a corresponding structuring element that represents the unit circle of the chosen metric. Then, the distance transform appearing in the analytical solution can be computed, for example, in $L^1$ to acquire a similar shape descriptor addressing rhombicity. In the numerical solution part, this can be imitated by using a diamond structuring element instead of a square one. Sample results for $L^1$ acquired in this way are displayed in Fig. 9.

Fig. 9.

Extending the method to measure rhombicity