OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 16, Iss. 7 — Mar. 31, 2008
  • pp: 4819–4823
« Show journal navigation

Optical generation of Voronoi Diagram

F. Giavazzi, R. Cerbino, S. Mazzoni, M. Giglio, and A. Vailati  »View Author Affiliations


Optics Express, Vol. 16, Issue 7, pp. 4819-4823 (2008)
http://dx.doi.org/10.1364/OE.16.004819


View Full Text Article

Acrobat PDF (1453 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

We present results of experiments of diffraction by an amplitude screen, made of randomly distributed circular holes. By careful selection of the experimental parameters we obtain an intensity pattern strongly connected to the Voronoi diagram (VD) generated by the centers of the apertures. With the help of simulations we give a description of the observed phenomenon and elucidate the optimal parameters for its observation. Finally, we also suggest how it can be used for a fast, all-optical generation of VDs.

© 2008 Optical Society of America

1. Introduction

Two dimensional VDs are made up by a set of adjoining space-filling convex polygonal domains associated to a given set of discrete generator points. For each specific generator, the associated Voronoi domain can be defined as the region of the plane including all points which are closer to the generator than to every other generator point [1

1. G. Voronoi and J. Reine Angew, “Nouvelles applications des parametres continus à la theorie des formes quadratiques,” Math. 134, 198 (1908).

]. VDs are used to describe a huge variety of structures occurring in many fields such as physics, geology, biology, engineering and finance. Basins of predation in an ecosystem, cellular textures in biological tissues, grain boundaries in materials, catchment areas in wireless networks or in public services are examples of spatial structures commonly modeled by VDs. A comprehensive review of VDs application can be found in [2

2. A. Okabe, B. Boots, and K. Sugihara, Spatial Tesselations: Concept and Applications of Voronoi Diagrams(Wiley, Chichester, 1992).

]. The study of the topological and metrical properties of the VD associated to a distribution of objects is an important tool in the structural characterization of random media (like glass, foams, cellular solids,…[3

3. G. Schliecker, “Structure and dynamics of cellular systems,” Adv. Phys. 51, 1319–1378 (2002). [CrossRef]

]). A prototypical example of this broad class is the random packing of discs in two dimensions [4

4. H. X. Zhu, S. M. Thorpe, and A. H. Windle, “The geometrical properties of irregular two-dimensional Voronoi tessellations,” Philos. Mag. A 81, 2765 (2001). [CrossRef]

,5

5. J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, “Arrangement of cells in Voronoi tesselations of monosize packing of discs,” Philos. Mag. B 81, 347 (1993).

].

In this paper we describe a physical system exploiting the well known, linear phenomenon of light propagation and interference. We show that the interference of the light diffracted by a set of circular apertures is capable of generating in a straightforward way the VD associated to the centers of the apertures (the centers act as the generating points of the diagram).

2. Experimental procedure

The experimental setup used to generate the patterns is sketched in Fig. 1.

Fig. 1. Schematic representation of the optical setup. The light diverging from a single mode optical fiber (1) coupled with a super-luminous Light Emitting Diode (spectral center 675 nm, spectral bandwidth, FWHM, 13.1 nm) is collimated by an achromatic doublet (2) of focal length f=20 cm. This collimated beam is sent trough an opaque metallic screen with non overlapping circular pinholes of radius R=150 µm chemically etched in random positions. The minimum distance allowed between the centers of the holes is 400 µm. The surface fraction covered by the holes is around 20%. A second lens (4) conjugates a plane lying at distance z from the mask to the plane of a CCD camera sensor (5).

A collimated beam is sent onto an opaque screen with randomly distributed circular apertures of radius R=150 µm and the scattered light is collected through a lens onto a CCD camera sensor (see Fig.1 caption for further details). We start from an imaging condition, where the image of the amplitude screen is formed onto the sensor plane. We then shift the camera along the optical axis and sequentially record the intensity distribution on different planes of increasing distance z from the screen.

For z>0 diffraction fringes are expected to appear inside the image of each hole. In practice, the fringes visibility is limited by both the finite bandwidth Δλ of the radiation employed and the finite resolution of the sensor. These limitations impose lower bounds on the observation distance z allowing the diffractive effects to be appreciable, respectively: z>R 2Δλ/λ 2 0≈0.07 cm and z>4R 2/ 0(λ 0 being the central wavelength of the light and n the width (in pixels) of the hole image recorded by the sensor). In our experimental condition (n≈20 pixels) the second condition is the most stringent and reads: z>0.7 cm. If z is further increased, also the interference between the light scattered from different apertures becomes visible.

A detail of a typical image (taken at z=1.7 cm) is shown in Fig. 2(a). The same image is shown in Fig 2(b) with a γ=0.25 correction, while in Fig. 2(c) we have superimposed to the γ -corrected image the VD calculated from the centers of the holes (i.e. having the center of the holes as generating set). Note that the chosen z value corresponds to a Fresnel number FR 2/λz≈2, yielding the dark Poisson’s spots lying at the centers of the images of holes. Therefore, in the conditions outlined above, the optical processor described in this paper allows to visualize both the VD and the position of the generator points of the diagram.

Fig. 2. (a). Measured intensity distributions of the light scattered from an opaque screen with circular pinholes of radius R=150 µm on a plane z=1.7 cm far from the screen. (b). Same of (a) with a γ=0.25 correction. (c). Same of (b) with the calculated VD generated by the holes centers superimposed.

As can be appreciated in Fig. 2, a structured interference pattern appears between neighboring holes. The positions of the maxima of the interference fringes are in good agreement with the position of the edges of the VD generated by the centers of the holes. Our attention in this paper will be focused on this peculiar regime.

It can be noticed that, if the observation distances z is further increased, the intensity distribution is no longer determined just by the interference between the light emerging from geometrical neighbors apertures: each point on the sensor receives light from a region containing a large number of holes. If the size of the contributing region is smaller than the size of a coherently illuminated region, then a speckle pattern is formed. The latter is characterized by the recently discovered [9

9. M. Giglio, M. Carpineti, and A. Vailati, “Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function g(r),” Phys. Rev Lett. 85, 1416 (2000). [CrossRef] [PubMed]

,10

10. J. W. Goodman, Speckle Phenomena in Optics (Greenwood Village, CO, 2007).

] peculiar property that the size of the speckles coincides with that of the circular apertures. If the distance is increased even more, then a single point on the sensor receives light from all the illuminated holes and the size of the speckles increases linearly with the distance z [10

10. J. W. Goodman, Speckle Phenomena in Optics (Greenwood Village, CO, 2007).

].

3. Discussion

A simple explanation of the working principle of the optical generation of VD is the following. Let’s start by considering a screen with just two circular holes or radius R, whose centers lie at a distance d>2R (Fig. 3(a)).

Fig. 3. (a). Transmittance profile of an opaque screen with two circular apertures (d=2.5R). (b). Numerically evaluated intensity distribution of the light diffracted by the holes of panel (a) on the plane z=R 2/3λ. (c). Numerically evaluated intensity distribution on the same plane when additional holes are introduced on the screen depicted in panel (a). (d). Same of (c) when a Canny-Deriche edge detection filter is applied. (e). Skeleton of the filtered image shown in panel (d).

When a plane, monochromatic, wave of wavelength λ impinges on the screen, the light diffracted by each hole is concentrated in a forward scattering lobe of increasing cross-section. Following the simple argument outlined in Reference 11 one can estimate the linear size of each diffraction spot at a distance z<R 2/λ from the screen as Rz~R+4λz . An estimate of the distance z * from the screen at which the two lobes start to overlap is thus z *≈(d-2R)2/4λ. The interference pattern visible in the overlap region consists, as a first approximation, of sinusoidal fringes of wavelength Λ≈λz/d, parallel to the median of the centers. So, if the intensity distribution of the scattered light is recorded at a distance slightly larger than z * such that the overlap region contains approximately one fringe, one expects to see two bright, nearly circularly symmetric spots separated by two parallel dark stripes at a distance Λ from each other. The dark stripes surround the maximum of the interference fringes, which appears as a bright line acting as an axis of symmetry for the hole centers. This situation is depiced in Fig. 3(b). Here the intensity distribution I on the plane z=R 2/λF (F=3) has been calculated numerically by convolving the N×N (N=1024) transmittancy matrix T, whose 512×512 central part is shown in Fig. 3(a), with a discretized Fresnel propagation kernel. This operation is actually done in the frequency domain: I=|ℑ-1(Hℑ(T))|2, where ℑ is the 2-dimensional discrete Fourier transform and Hkxkyexp[jπ(kx2+ky2)R2(N2F)] .

If additional holes are now introduced in the screen in such a way that the distance between neighboring holes is maintained approximately constant and equal to d, the above reasoning can be iterated for every pair of neighboring holes. The resulting intensity distribution will then contain all the medians of pairs of neighboring holes. These medians coincide with the edges separating the Voronoi domains associated with the centers of the pinholes (Fig. 3(c)).

In Figs. 3(d) and 3(e) is reported an example of a two-step image processing procedure allowing the extraction of the VD from the intensity pattern. Fig. 3(d) is obtained from Fig. 3(c) by applying a Canny-Deriche edge detection filter [12

12. B. Jähne, Digital Image Processing (Springer, 1995), Chap. 12.

], identifying the main fringes (of width ≈Λ) surrounding the Voronoi edges. From this filtered image the VD can be then extracted through a skeletonization algorithm [13

13. T. Bräunl, Parallel Image Processing (Springer, 2001), Chap. 5.

]. The result of this operation is the binary image depicted in Fig. 3(e).

A first requirement for the optical generation of VD by using the procedure described above can be expressed in terms of the spatial distribution of the generators. As pointed out above, the observation distance z corresponding to a good visibility of the interference fringes depends both on the radius and the mutual distance between the holes. The uniform emergence of the whole Voronoi-like pattern is then guaranteed whenever the spacing between the centers of contiguous holes is approximately constant through the sample. This condition is automatically fulfilled, for example, by the important class of random close-packed (high surface fraction) monodisperse discs, which appears thus as an ideal candidate for the proposed technique [5

5. J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, “Arrangement of cells in Voronoi tesselations of monosize packing of discs,” Philos. Mag. B 81, 347 (1993).

].

A good spatial coherence of the source is also a requirement. This is due to the fact that in order to obtain interference fringes from the superposition of the light diffracted by the two neighboring holes, the two holes must lie within the same coherence area. This implies that Ad 2, where A is the typical surface of the coherence areas illuminating the screen. On the contrary, a loose temporal coherence of the source is not a problem, instead it can be even beneficial as it decreases the visibility of the unwanted diffraction fringes, whose wavelength is smaller then the width Λ of the interference stripes. This is apparent from Fig. 2, which was obtained by using a source with a limited temporal coherence (spectral bandwidth, FWHM, Δλ=13.1 nm).

At this stage we point out that a dramatic improvement in the performances of an optical processor could be obtained by using an Electrically Addressed Spatial Light Modulator (EASLM) instead of the perforated metallic screen used in this work. Modern EASLMs are made up by rectangular arrays of pixels with a typical resolution of the order of 103×103pixels and a typical pixel pitch (the center-to-center spacing between adjacent pixels) of 15 µm. Each pixel in a EASLM can be addressed independently to impose an amplitude (or phase, or both amplitude and phase) modulation on the light impinging on it. A group of pixels arranged into a circle can reproduce a circular aperture and many of such circular groups of pixels can be addressed onto a single amplitude EASLM, so that it mimics the perforated metallic screen used in this work. A EASLM has the great advantage that the position of the apertures can be changed at will, even in real time, thus providing a fast optical processing of the VD which can be immediately visualized onto the sensor.

4. Conclusion

We have shown that whenever a collection of uniformly packed discs is illuminated with a reasonably coherent light source, a distance z * exists for the formation of an interference pattern akin to the VD of the disc centers. This phenomenon can be exploited for a fast, fully reproducible, all-optical generation of the VD associated to a given distribution of generator points.

In principle, there are no limits to the range of spatial scales that can be investigated, the latter being limited only by the size of the optical elements and by the detector resolution.

References and Links

1.

G. Voronoi and J. Reine Angew, “Nouvelles applications des parametres continus à la theorie des formes quadratiques,” Math. 134, 198 (1908).

2.

A. Okabe, B. Boots, and K. Sugihara, Spatial Tesselations: Concept and Applications of Voronoi Diagrams(Wiley, Chichester, 1992).

3.

G. Schliecker, “Structure and dynamics of cellular systems,” Adv. Phys. 51, 1319–1378 (2002). [CrossRef]

4.

H. X. Zhu, S. M. Thorpe, and A. H. Windle, “The geometrical properties of irregular two-dimensional Voronoi tessellations,” Philos. Mag. A 81, 2765 (2001). [CrossRef]

5.

J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, “Arrangement of cells in Voronoi tesselations of monosize packing of discs,” Philos. Mag. B 81, 347 (1993).

6.

D. Tolmachiev and A. Adamatzky, “Chemical processor for computation of Voronoi diagram,” Adv. Mater. Opt. Electron. 6, 191 (1996). [CrossRef]

7.

M. Doi, Y. Suzuki, T. Koyama, and F. Katsuki, “Pattern evolution of crystalline Ge aggregates during annealing of an Al/Ge bilayer film deposited on a SiO2 substrate,” Philos. Mag. Lett. 78, 241 (1998). [CrossRef]

8.

A. L. Zanin, A. W. Liehr, A. S. Moskalenko, and H.-G. Purwins, “Voronoi diagrams in barrier gas discharge,” Appl. Phys. Lett. 81, 3338 (2002). [CrossRef]

9.

M. Giglio, M. Carpineti, and A. Vailati, “Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function g(r),” Phys. Rev Lett. 85, 1416 (2000). [CrossRef] [PubMed]

10.

J. W. Goodman, Speckle Phenomena in Optics (Greenwood Village, CO, 2007).

11.

J. W. Goodman, Introduction to Fourier Optics (McGraw-Hill), Chap. 4.

12.

B. Jähne, Digital Image Processing (Springer, 1995), Chap. 12.

13.

T. Bräunl, Parallel Image Processing (Springer, 2001), Chap. 5.

OCIS Codes
(070.0070) Fourier optics and signal processing : Fourier optics and signal processing
(200.4740) Optics in computing : Optical processing
(200.4960) Optics in computing : Parallel processing

ToC Category:
Fourier optics and signal processing

History
Original Manuscript: October 11, 2007
Revised Manuscript: November 22, 2007
Manuscript Accepted: November 30, 2007
Published: March 25, 2008

Citation
F. Giavazzi, R. Cerbino, S. Mazzoni, M. Giglio, and A. Vailati, "Optical generation of Voronoi diagram," Opt. Express 16, 4819-4823 (2008)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-16-7-4819


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. G. Voronoi and J. Reine Angew, "Nouvelles applications des parametres continus à la theorie des formes quadratiques," Math. 134, 198 (1908).
  2. A. Okabe, B. Boots, and K. Sugihara, Spatial Tesselations: Concept and Applications of Voronoi Diagrams (Wiley, Chichester, 1992).
  3. G. Schliecker, "Structure and dynamics of cellular systems," Adv. Phys. 51,1319-1378 (2002). [CrossRef]
  4. H. X. Zhu, S. M. Thorpe, and A. H. Windle, "The geometrical properties of irregular two-dimensional Voronoi tessellations," Philos. Mag. A 81, 2765 (2001). [CrossRef]
  5. J. Lemaítre, A. Gervois, J. P. Troadec, N. Rivier, M. Ammi, L. Oger, and D. Bideau, "Arrangement of cells in Voronoi tesselations of monosize packing of discs," Philos. Mag. B 81, 347 (1993).
  6. D. Tolmachiev and A. Adamatzky, "Chemical processor for computation of Voronoi diagram," Adv. Mater. Opt. Electron. 6, 191 (1996). [CrossRef]
  7. M. Doi, Y. Suzuki, T. Koyama, and F. Katsuki, "Pattern evolution of crystalline Ge aggregates during annealing of an Al/Ge bilayer film deposited on a SiO2 substrate," Philos. Mag. Lett. 78, 241 (1998). [CrossRef]
  8. A. L. Zanin, A. W. Liehr, A. S. Moskalenko, and H.-G. Purwins, "Voronoi diagrams in barrier gas discharge," Appl. Phys. Lett. 81, 3338 (2002). [CrossRef]
  9. M. Giglio, M. Carpineti, and A. Vailati, "Space intensity correlations in the near field of the scattered light: A direct measurement of the density correlation function g(r)," Phys. Rev Lett. 85, 1416 (2000). [CrossRef] [PubMed]
  10. J. W. Goodman, Speckle Phenomena in Optics (Greenwood Village, CO, 2007).
  11. J. W. Goodman, Introduction to Fourier Optics (McGraw-Hill), Chap. 4.
  12. B. Jähne, Digital Image Processing (Springer, 1995), Chap. 12.
  13. T. Bräunl, Parallel Image Processing (Springer, 2001), Chap. 5.

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1. Fig. 2. Fig. 3.
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited