Open Access Paper
8 February 2015 Shape simplification through polygonal approximation in the Fourier domain
Mark Andrews, Ramakrishna Kakarala
Author Affiliations +
Proceedings Volume 9406, Intelligent Robots and Computer Vision XXXII: Algorithms and Techniques; 94060D (2015) https://doi.org/10.1117/12.2078148
Event: SPIE/IS&T Electronic Imaging, 2015, San Francisco, California, United States
Abstract
Fourier descriptors have long been used to describe the underling continuous contours of two-dimensional shapes. Approximations of shapes by polygons is a natural step for efficient algorithms in computer graphics and computer vision. This paper derives mathematical relationships between the Fourier descriptors of the continuous contour, and the corresponding descriptors of a polygon obtained by connecting samples on the contour. We show that the polygon's descriptors may be obtained analytically in two ways: first, by summing subsets of the contour's descriptors; and second, from the discrete Fourier transform (DFT) of the polygon's vertices. We also analyze, in the Fourier domain, shape approximation using interpolators. Our results show that polygonal approximation, with its potential benefits for efficient analysis of shape, is achievable in the Fourier descriptor domain.

1.

INTRODUCTION

As many papers have demonstrated, the bounding contour of an object suffices to detect, classify, or recognize an object in an image.1, 2 The contour of an object in the physical world is by nature continuous, while its appearance in an image is discretized by the pixel grid. Accurate measurement of object properties, such as enclosed area or perimeter, requires a representation of the underlying continuous bounding contour.

Fourier descriptors have long been used to represent continuous contours.3 The value in Fourier descriptors lies, in part, in the way that they allow the powerful machinery of Fourier analysis to illuminate shape transformations such as rigid transformation and simplification through filtering. Indeed, it is possible to study Fourier descriptors as a branch of applied harmonic analysis, without reference to their applications in computer vision. It is in that spirit that this paper is devoted to the analysis of polygonal approximation in the Fourier domain.

Approximating shapes with polygons is a natural method for simplifying them, and is useful for applications in computer graphics4 and computer vision.5 However, existing research does not provide any mathematical relationships between the Fourier descriptors of a continuous contour and those of a polygon obtained by connecting samples taken on the contour. In this paper, we derive the theory of approximating shapes by polygons operating entirely in the Fourier domain. We show that the polygon’s Fourier descriptors may be obtained from the corresponding descriptors of the contour, and also through the DFT of the vertex locations. The results illuminate connections between sampling and interpolation in the Fourier domain.

2.

NOTATION AND CONVENTIONS

Let 00012_psisdg9406_94060D_page_1_1.jpg denote a closed, simple contour located in the complex plane ℂ. 00012_psisdg9406_94060D_page_1_1.jpg may be parameterized by a complex-valued function z, with parameter t ∈ [0,1]. From standard differential geometry, the speed of the contour is |z′|, and the arc length of a segment drawn by t ∈ [0, A], with 0 ≤ A ≤ 1 is

00012_psisdg9406_94060D_page_1_2.jpg

Figure 1.

A contour 00012_psisdg9406_94060D_page_1_1.jpg is sampled at N = 11 points, indicated with “X”, and the samples connected to form a polygonal approximation.

00012_psisdg9406_94060D_page_2_1.jpg

Let L = s(1) denote the total arc length of the contour. Differential geometry6 shows that 00012_psisdg9406_94060D_page_1_1.jpg may also be parameterized by a unit-speed function w whose argument is arc-length s, with 0 ≤ sL. Hence, both z and w parametrize the same contour, with varying and constant speeds, respectively.

Both z and w are periodic functions, since C is closed. Hence, they may be expanded in a Fourier series. Since the varying speed parameterization is more general of the two, we use it for analysis in this paper. Specifically, for z, this is

00012_psisdg9406_94060D_page_2_2.jpg

It should be understood that “u” may represent any parameterization, including arc length.

Suppose that 00012_psisdg9406_94060D_page_1_1.jpg is sampled at a set of N points, denoted p[0], p[1], …, p[N – 1]. When connected together, as shown in Figure 2, the points form a polygon. Each vertex is a point in the complex plane, and the discrete Fourier transform (DFT) of the vertices is

00012_psisdg9406_94060D_page_2_3.jpg

The samples of any complex-valued function may be interpolated to form a continuous function. While the ideal interpolator for band limited samples is the sinc function, simpler interpolators may be obtained from the zero-order hold

00012_psisdg9406_94060D_page_2_4.jpg

The first order hold interpolator, r1, is obtained by convolving r0 with itself: r1 = r0 * r0, and is described as:

00012_psisdg9406_94060D_page_2_5.jpg

The Fourier transform of r0 is

00012_psisdg9406_94060D_page_2_6.jpg

Consequently, the first order hold has the transform

00012_psisdg9406_94060D_page_2_7.jpg

3.

POLYGONAL APPROXIMATION IN THE FOURIER DOMAIN

The main results of our paper connect the Fourier series coefficients of a contour with those of a polygonal approximation obtained by connecting samples taken from the contour. Suppose a closed, simple contour is represented by a complex-valued function x, with argument u ∈ [0,1] denoting an arbitrary parameter.

Write x in a Fourier series as

00012_psisdg9406_94060D_page_3_1.jpg

If we sample x at N evenly-spaced points, u = 0, 1/N, …, (N – 1)/N, and connect those points with straight lines to form a polygon, then the polygon’s contour may also be represented by a periodic complex-valued function z with Fourier series

00012_psisdg9406_94060D_page_3_2.jpg

Our first result connects the polygon’s Fourier coefficients with those of the underlying contour.

Theorem 3.1.

The Fourier coefficients of the polygon in (9) are obtained from those of the contour in (8) as follows:

00012_psisdg9406_94060D_page_3_3.jpg

Proof.

Since x is a periodic function, its samples may be described using a Dirac comb on the real line as:

00012_psisdg9406_94060D_page_3_4.jpg

The sampling operation at spacing 1/N transforms in the Fourier domain to another Dirac comb with reciprocal spacing. Consequently, the Fourier transform of (11) is,

00012_psisdg9406_94060D_page_3_5.jpg

The continuous-time Fourier transform X of the underlying curve with series (2) is

00012_psisdg9406_94060D_page_3_6.jpg

Putting (13) into (12) gives

00012_psisdg9406_94060D_page_3_7.jpg

Connecting the samples of xs with straight lines is equivalent to convolving (11) with the first order hold interpolation function r1(Nu), where the scale factor N applied to the argument to account for the 1/N spacing of samples. The corresponding Fourier transform of the interpolator is

00012_psisdg9406_94060D_page_3_8.jpg

Consequently, the polygon obtained by z(u) = xs(u) * r1(Nu) has the transform:

00012_psisdg9406_94060D_page_3_9.jpg

The inverse transform of Z yields

00012_psisdg9406_94060D_page_4_1.jpg

Grouping terms of k = Nn + m yields the desired result:

00012_psisdg9406_94060D_page_4_2.jpg

The Theorem requires the Fourier series coefficients b of the original curve, which may not always be known. It seems reasonable to expect to obtain the desired coefficients in (9) using only the vertices of the polygon formed by the samples. We now consider how this works.

As above, let p[n], 0 ≤ nN – 1, denote the vertices of the polygon obtained by taking N samples of the curve x(u), 0 ≤ u ≤ 1, i.e., p[n] = x(n/N), with corresponding DFT (3). It is understood that P[k + N] = P[k].. The polygon forms a closed curve, with Fourier series (9). We establish the following connection.

Theorem 3.2.

The Fourier series coefficients of the polygon (9) are obtained from the DFT of the vertices as follows:

00012_psisdg9406_94060D_page_4_3.jpg

With these coefficients, the curve (9) satisfies

00012_psisdg9406_94060D_page_4_4.jpg

Proof.

The polygon is described by the following sequence of convolutions, which repeat one period over the real line followed by interpolation:

00012_psisdg9406_94060D_page_4_5.jpg

In the Fourier domain, this results in two multiplications:

00012_psisdg9406_94060D_page_4_6.jpg

Combining summations, and using the sampling property of the Dirac delta function, we obtain

00012_psisdg9406_94060D_page_4_7.jpg

The sum in brackets is the DFT (3). We obtain (18) by taking the inverse Fourier transform:

00012_psisdg9406_94060D_page_4_8.jpg

To prove (19), we see from (20) that

00012_psisdg9406_94060D_page_5_1.jpg
00012_psisdg9406_94060D_page_5_2.jpg
00012_psisdg9406_94060D_page_5_3.jpg

Substituting t = m/N, we have

00012_psisdg9406_94060D_page_5_4.jpg

From (5), it follows that r1(mnNk) = 0, unless mn = Nk. For 0 ≤ m, nN, this requires k = 0, and m = n. Therefore, z(m/N) = p[m], as desired. □

The two Theorems lead to the following identity.

Corollary 3.3.

For N samples p[n] = x(n/N), 0 ≤ nN, from a curve x with Fourier series (8), we have

00012_psisdg9406_94060D_page_5_5.jpg

Although the Corollary is a direct result of the theorems, insight comes from the following analysis. Substitution shows that

00012_psisdg9406_94060D_page_5_6.jpg

Simplifying, we find that the right hand side becomes

00012_psisdg9406_94060D_page_5_7.jpg

The sum in brackets is reducible using the Poisson summation formula to

00012_psisdg9406_94060D_page_5_8.jpg

Substituting this back into (29) shows that both sides are indeed equal. Further insight into the two theorems comes from examining additional points.

  • 1. The sinc function is zero at all integers except zero, and hence the polygon’s Fourier descriptors ck vanish for k = ±N, ±2N, ±3N, ….

  • 2. Combining (18) and (19), we obtain the interesting identity

    00012_psisdg9406_94060D_page_5_9.jpg

    This is an interesting variation on the inverse DFT formula:

    00012_psisdg9406_94060D_page_5_10.jpg

    The relationship between (32) and (33) is understood by substituting for the DFT in (32), yielding

    00012_psisdg9406_94060D_page_6_1.jpg

    Rearranging terms gives

    00012_psisdg9406_94060D_page_6_2.jpg

    Hence, we must have

    00012_psisdg9406_94060D_page_6_3.jpg

    where δ[] is the Kronecker delta. In particular, setting Í = 0, we have

    00012_psisdg9406_94060D_page_6_4.jpg

    Setting N = 1 gives the obvious result:

    00012_psisdg9406_94060D_page_6_5.jpg

    Interestingly, it can be shown7 that:

    00012_psisdg9406_94060D_page_6_6.jpg

  • 3. By inserting (18) into (2), and grouping terms involving each DFT coefficient, we obtain:

    00012_psisdg9406_94060D_page_6_7.jpg

    In particular, since sinc2(k) = δ[k], we have

    00012_psisdg9406_94060D_page_6_8.jpg

    This shows that the “center” of the polygon is at 00012_psisdg9406_94060D_page_6_9.jpg For N =1, the polygon is a single point z[0], and we obtain

    00012_psisdg9406_94060D_page_6_10.jpg

    as expected. For N = 1, the polygon is a line from p[0] to p[1], and back again. The curve then becomes

    00012_psisdg9406_94060D_page_6_11.jpg

    Since P[0] = p[0] + p[1] and P[1] = p[0] – p[1], it follows that at t = 0, we have z(0) = 1/2 (P[0] + P[1]) = p[0], as expected. We must have z(1/2) = p[1] by (19). Hence, we obtain again another interesting identity:

    00012_psisdg9406_94060D_page_6_12.jpg

    Remarkably, this result is independent of N.

4.

INTERPOLATORS AND POLYGONS

The analysis of the previous section relied on the first order hold and its transform, the sinc squared function. Other interpolators are, of course, possible and it is interesting to analyze their effect in the Fourier domain. As we have seen, the analysis may be carried out in the frequency domain, requiring only the transform of the interpolating function. For example, if the interpolator has transform R(f), then Theorems (3.1) and (3.2) show that:

00012_psisdg9406_94060D_page_7_1.jpg
00012_psisdg9406_94060D_page_7_2.jpg

If, for example, the zero-order-hold (4) is used, the transform is 00012_psisdg9406_94060D_page_7_3.jpg sinc(f/N), and the resulting expressions are:

00012_psisdg9406_94060D_page_7_4.jpg
00012_psisdg9406_94060D_page_7_5.jpg

The ideal interpolator, with samples spaced 1/N apart, is the sinc function:

00012_psisdg9406_94060D_page_7_6.jpg

with corresponding transform

00012_psisdg9406_94060D_page_7_7.jpg

Using the ideal interpolator, we have

00012_psisdg9406_94060D_page_7_8.jpg
00012_psisdg9406_94060D_page_7_9.jpg

It is not obvious that this recovers the original samples, as it should. The Appendix shows that by revisiting the proof of Theorem 3.1, we find perfect recovery.

An interesting interpolator that preserves the original samples is the cardinal spline of the 2-nd order,8 which has the transform

00012_psisdg9406_94060D_page_7_10.jpg

5.

SUMMARY AND CONCLUSIONS

Simplifying shapes into polygons is a basic operation in computer graphics and computer vision. This paper derives mathematical results connecting the Fourier descriptors of the underlying shape to those of the polygon. The Fourier descriptors are shown to be obtained from the vertices using the DFT, and also by summing groups of coefficients of the underlying curve. The results extend to cover other interpolators.

The relationships derived in this paper illuminate connections between sampling theory and the planar geometry of curves and polygon that are not well known. It is interesting that such results are obtained in the Fourier domain. In future, we explore whether the Fourier series basis functions are indeed the best ones when representing polygons.

Appendices

Appendix

We show that the ideal interpolator recovers samples exactly. Given that the sampled function, repeated across the real line, has transform

00012_psisdg9406_94060D_page_8_1.jpg

We obtain the interpolated signal zi by convolution with the ideal interpolator:

00012_psisdg9406_94060D_page_8_2.jpg

In the frequency domain, this is Zi(f) = X(f)Ri(f). This gives

00012_psisdg9406_94060D_page_8_3.jpg
00012_psisdg9406_94060D_page_8_4.jpg

The sum in brackets may be reorganized by noting that the exponentials ej2πfn/N are periodic with period N, allowing us to write

00012_psisdg9406_94060D_page_8_5.jpg

Applying the inverse Fourier transform to Zi gives us

00012_psisdg9406_94060D_page_8_6.jpg
00012_psisdg9406_94060D_page_8_7.jpg
00012_psisdg9406_94060D_page_8_8.jpg

Rearranging the sum gives

00012_psisdg9406_94060D_page_8_9.jpg

The sum in brackets is simply the DFT of the polygon vertices, yielding

00012_psisdg9406_94060D_page_8_10.jpg

In particular, we have, by the inverse DFT, that

00012_psisdg9406_94060D_page_8_11.jpg

ACKNOWLEDGMENTS

The support of the Singapore Ministry of Education under grant MOE-T2-1-010 is gratefully acknowledged.

REFERENCES

[1]. 

Ling, H. and Jacobs, D., “Inner distance using the shape context,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29 286 –289 (2007). https://doi.org/10.1109/TPAMI.2007.41 Google Scholar

[2]. 

Premachandran, V. and Kakarala, R., “Perceptually motivated shape context which uses shape interiors,” Pattern Recognition, 46 2092 –2102 (2013). https://doi.org/10.1016/j.patcog.2013.01.030 Google Scholar

[3]. 

Zahn, C. T. and Roskies, R. Z., “Fourier descriptors for plane closed curves,” Computers, IEEE Transactions on, C-21 269 –281 (1972). https://doi.org/10.1109/TC.1972.5008949 Google Scholar

[4]. 

Douglas, D. and Peucker, T., “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” The Canadian Cartographer, 10 (3), 112 –122 (1973). https://doi.org/10.3138/FM57-6770-U75U-7727 Google Scholar

[5]. 

Osada, R., Funkhouser, T. A., Chazelle, B., and Dobkin, D. P., “Shape distributions,” ACM Trans. Graph, 21 (4), 807 –832 (2002). https://doi.org/10.1145/571647.571648 Google Scholar

[6]. 

do Carmo, M. P., Differential Geometry of Curves and Surfaces, Prentice-Hall, Upper Saddle River, NJ (1976). Google Scholar

[7]. 

Baillie, R., Borwein, D., and Borwein, J. M., “Surprising sinc sums and formulas,” The American Mathematical Monthly, 115 (10), 888 –901 (2008). https://doi.org/10.1080/00029890.2008.11920606 Google Scholar

[8]. 

Aldroubi, A., Unser, M., and Eden, M., “Cardinal spline filters: Stability and convergence to the ideal sinc interpolator,” Signal Processing, 28 127 –138 (1992). https://doi.org/10.1016/0165-1684(92)90030-Z Google Scholar
© (2015) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Mark Andrews and Ramakrishna Kakarala "Shape simplification through polygonal approximation in the Fourier domain", Proc. SPIE 9406, Intelligent Robots and Computer Vision XXXII: Algorithms and Techniques, 94060D (8 February 2015); https://doi.org/10.1117/12.2078148
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Fourier transforms

Computer graphics

Computer vision technology

Machine vision

Shape analysis

Computer engineering

Convolution

RELATED CONTENT


Back to Top