Random Curve Generation

(A linear-time algorithm for closed and irreducible, random digital curves)


logo-youtube
Algorithm: Partha Bhowmick, Oishee Pal, and Reinhard Klette,
A Linear-time Algorithm for Generation of Random Digital Curves,
4th Pacific-Rim Symposium on Image & Video Technology (PSIVT 2010),
14-17 November, 2010, Singapore (accepted). poster

Background: The problem of generating random curves is quite interesting, whose historical origin can be traced back to several classical studies on Brownian motion (in ℝ2) [5, 6] and random walk [8, 10, 11]. Closed random curves also find a resemblance with polygons whose generation has received considerable attention in recent times [1, 7, 14, 12].

Significance: There is no published work till date on generating (closed and irreducible) random digital curves. A polygon-generation algorithm works with vertices of the polygon as input, generated randomly but a priori. On the contrary, our algorithm generates the points on the fly while creating the digital curve C. Starting from a random point (vertex) p1, it choose the next safe point p2 randomly, connects the points p1 and p2, again chooses the next safe point p3 randomly and connects it with p2, and so forth, and eventually ends at the start point p1, thereby generating a closed digital curve.

Applications: For testing an algorithm A that takes a digital curve as input [2, 9, 3, 13]. Ideally, one would like to test the behavior and performance of A on various real-world digital curves, which are often very difficult to obtain. So a proven algorithm is necessary to generate a sufficiently large set of random curves of finite length in the digital plane.
Problem difficulty lies in generating a curve C on the fly such that C never intersects or touches itself, and hence becomes simple and irreducible. This, in turn, calls for detecting every possible “narrow-mouthed” trap formed by a previously generated part of C, which, if entered into, cannot be exited without touching or intersecting C.

Detecting and avoiding a trap: A trap may be arbitrarily nested in multiple and has to be detected fast without any backtracking (due to some already-entered part of the curve through the mouth of the trap) in order to minimize the computations involved. Further, since C has to be closed, it must be ensured that the (k-connected) path traced by the algorithm finally reaches the very start point.

Proof of correctness: Follows from the principle of mathematical induction.

Runtime: Linear in the length of C.

003-512-12-B1.png

An Overview of the Algorithm
Java Applet

The relevant theorems are given below. For their proofs and related definitions, see the paper.

Theorem 1 There exists a free path from the current cell ci to the starting cell c1 if and only if N4(ci) ∩ Ri ≠ ∅.
Note:  A point in the digital plane ℤ2 is said to be a digital point. The set of four horizontally and vertically adjacent points of a point p(x, y) is called the 4-neighborhood (4-N) of p, given by N4(p) = {(x', y') : |x—x' |+|y—y' | = 1}. Similarly, the 8-neighborhood (8-N) of p is N8(p) = {(x', y') : max(|x—x' |, |y—y' |) = 1}. Each point in Nk(p) (k = 4 or 8) is said to be a k-neighbor of p.
The (cellular) open region Ri corresponding to the current cell ci is the maximal set of free cells of the canvas such that there exists a free path from each cell of Ri to the free border cell (i.e., c1(5)).
Ensuing hole Ei ⊂ Ri is an ensuing hole corresponding to ci if and only if
(e1)  ∃ c ∈ Ñ(ci) such that δ(c ; ci) = B;
(e2)  for each c' ∈ Ei, δ(c' ; ci) ∈ {L, R, X}; 
(e3)  ∃ ρ(ci+1, c1(5)); and for each ρ(ci+1, c1(5)), c ∈ ρ(ci+1, c1(5)).

Note:  Only the cells belonging to the region Ñ(ci) = N8(ci) − (N4(ci-1) ∪ N4(ci+1)) are labeled in the i th iteration.
Corollary 1 The edge between ci and ci(t) is safe if and only if ci(t) belongs to Ri.
Theorem 2 When the construction of C is over, each cell c can have either β(c) ≥ 16 (c is blocked) or δ(c) ∈ {L, R, X}; that is, B can be the interim label but cannot be the final label of any free cell.
Corollary 2 Either a hole or an ensuing hole is created if and only if at least one free cell in Ñ(ci) gets the label B as ci becomes the current cell.

Theorem 3 The current cell ci gives rise to an ensuing hole Ei if and only if there exists a free cell bi ∈ Ñ(ci) such that
(E1)  δ(bi ; ci) = B;
(E2) ∃ ρ(ai , bi) ⊆ N8(ci+1)  for each ai ∈ Ei ∩ N4(ci+1).

Corollary 3 ci gives rise to a hole Hi if and only if E1 is true and E2 is false.

References

  1. T. Auer and M. Held. Heuristics for the generation of random polygons. In Proc. CCCG, pages 38–44, 1996.
  2. P. Bhowmick and B. B. Bhattacharya. Fast polygonal approximation of digital curves using relaxed straightness properties. IEEE Trans. PAMI, 29(9):1590–1602, 2007.
  3. I. Debled-Rennesson, R. Jean-Luc, and J. Rouyer-Degli. Segmentation of discrete curves into fuzzy segments. Electronic Notes in Discrete Mathematics, 12:372–383, 2003.
  4. I. D.-Rennesson and J. P. Reveilles. A linear algorithm for segmentation of digital curves. IJPRAI, 9:635–662, 1995.
  5. A. Einstein. Über die von der molekularkinetischen Theorie der wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen. Annalen der Physik, 17:549–560, 1905.
  6. A. Einstein. Investigations on the Theory of Brownian Movement. Dover Publications, NY, 1926 (reprint: 1956).
  7. P. Epstein. Generating geometric objects at random. CS Dept., Carleton University, Canada, 1992. Masters thesis.
  8. S. Finch. Pòlya’s random walk constant. §5.9 in Mathematical Constants, Cambridge University Press, 2003.
  9. R. Klette and A. Rosenfeld. Digital Geometry: Geometric Methods for Digital Picture Analysis. 2004.
  10. G. Pòlya. Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stassennetz. Mathematische Annalen, 84:149–160, 1921.
  11. S. Rohde and O. Schramm. Basic properties of sle. Annals Math., 161:879–920, 2005.
  12. J. Rourke and M. Virmani. Generating random polygons. TR:011, CS Deptt., Smith College, Northampton, 1991.
  13. A.W. M. Smeulders and L. Dorst. Decomposition of discrete curves into piecewise segments in linear time. Contemporary Math., 119:169–195, 1991.
  14. C. Zhu, G. Sundaram, J. Snoeyink, and J. S. B. Mitchell. Generating random polygons with given vertices. CGTA, 6:277–290, 1996.
Best viewed in Mozilla Firefox
© Partha Bhowmick (August 2010)