Triangular Covers

(A Linear-time Combinatorial Algorithm
for Digital Objects)


Algorithm

B. Das, M. Dutt, A. Biswas, P. Bhowmick, and B. B. Bhattacharya, A Combinatorial Technique for Construction of Triangular Covers of Digital Objects, 16th International Workshop on Combinatorial Image Analysis: IWCIA'14, Brno, Czech Republic, May 28-30, 2014, LNCS 8466, pp. 76–90, 2014.


What's it

The construction of a minimum-area geometric cover of a digital object is important in many fields of image analysis and computer vision. We have proposed the first algorithm for constructing a minimum-area polygonal cover of a 2D digital object as perceived on a uniform triangular grid. The polygonal cover is triangular in the sense that its boundary consists of a sequence of edges on the underlying triangular grid.

The algorithm designed by us is based on certain combinatorial properties of a digital object on a grid, and it computes the tightest cover in time linear in perimeter of the object. We present experimental results to demonstrate the efficacy, robustness, and versatility of the algorithm, and they indicate that the runtime varies inversely with the grid size.

 horse-g14

Triangular grid


trigrid
Above figure shows a portion of a triangular grid, the UGTs $\{T_0,T_1,\ldots,T_5\}$ incident at a grid point $p$, and the direction codes $\{0,1,\ldots,5\}$ of neighboring grid points of $p$.

Vertex classification



(a)
(b)
(c)
(d)

(e)
(f)
(g)
(h)

(i)
(j)
(k)
(l)

The object occupancy vector corresponding to $\langle T_i:i=0,1,\ldots,5\rangle$ incident at a grid point $q$ is given by $A_q=\langle a_0a_1\cdots a_5\rangle$, where, for $i=0,1,\ldots,5$, we have $a_i=1$ if $T_i$ incident at $q$ has object occupancy, and 0 otherwise. The object occupancy of each $T_i$ is determined by checking its interior integer points lying along its borders. The algorithm then uses the vector $A_q$ to determine whether $q$ lies on $\overline{P}$ and to compute the edges of $\overline{P}$ incident at $q$. For example, $A_q=000011$ implies $T_4$ and $T_5$ are object-occupied. So, the direction of the incoming edge at $q$ becomes 3 and that of the outgoing edge becomes 5, since the object lies left during traversal of $\overline{P}$.

A grid point $q$ lies on $\overline{P}$ if $A_q$ contains both 0's and 1's. If $A_q=0^6$, then $q$ lies outside $\overline{P}$; and $A_q=1^6$ implies $q$ lies strictly inside $\overline{P}$. Apart from these two cases, there arise $2^6-2=62$ combinatorial cases of $A_q$. These 62 cases can be simplified to following 5 cases only, with their corresponding sub-cases, depending on the number of 1's in $A_q$, which is denoted by $k(=1,2,\ldots,5)$.

Figure above: (a)$\,k=0$, (b)$\,k=1$, (c,d)$\,k=2$, (e-g)$\,k=3$, (h-j)$\,k=4$, (k)$\,k=5$, (l)$\,k=6$. A red line indicates the traversal direction of the outer triangular polygon, and a blue line indicates that of an outer triangular hole polygon. For detailed explanation, see the paper.
drummer-g10