2.1.

Operational Rate-Distortion Optimal Shape Coding

Let the ordered set $C=\{c_0,c_1,\cdots ,c_{N_C-1}\}$ denote the connected contour, where $c_i$ is the $i$’th pixel of $C$, $N_C$ is the total number of pixels in $C$, and $c_0=c_{N_C-1}$ for a closed contour. Let the ordered set $A=\{a_{\mathrm{0,0}},a_{\mathrm{1,0}},a_{\mathrm{1,1}},\cdots ,a_{N_C-\mathrm{1,0}}\}$ denote the admissible vertex set, where $a_{i,0}=c_i$, $a_{i,m}$ is the $m$’th admissible vertex associated with $c_i$, and $N(i)$ is the number of admissible vertices in $A$ associated to $c_i$. Let $L(i)$ denote the length of the sliding window in pixel along the contour, starting at contour point $c_i$. Let the two-tuple set $E_A=\{(a_{i,m},a_{j,n})\in A^2\text{:}\forall i<j\le i+L(i)\}$ denote the candidate edges for polygonal approximation. Let the ordered set $P=\{p_0,p_1,\cdots ,p_{N_P-1}\}$ denote the polygon used to approximate $C$, where $p_k$ is the $k$’th vertex of $P$, $N_P$ is the total number of vertices in $P$, and $P\subseteq A$. Let $r(p_{k-1},p_k)$ denote the bit rate of the edge $(p_{k-1},p_k)$ and $R(P)$ the bit rate for the entire polygon. Let $d(p_{k-1},p_k)$ denote the distortion of the edge $(p_{k-1},p_k)$, $D(P)$ the polygon distortion, and $D_{\max }$ the admissible distortion. The ORD shape coding finds an optimal polygon $P$ in the admissible vertex set $A$ which can be encoded with the lowest bit rate for a given admissible distortion $D_{\max }$.⁸ It can be formulated as follows:

Formulation (1) is virtually a shortest path problem in a weighted DAG $G=(A,E_A,w)$, as shown in Fig. 2.⁹ A valid path of order $K$ from vertex $v_0$ to a vertex $v_K$ is an ordered set is an ordered set $\{v_0,v_1,\cdots ,v_K\}$, such that $(v_{k-1},v_k)\in E_A$ for $k=\mathrm{1,2},\cdots ,K$, whose length is defined as follows:

Fig. 2

Modeled DAG and the shortest path of Fig. 1(d) (Notation—arrow: candidate edge with weights given by the eight-direction/eight-sector structure).

The above definition of the weight function leads to the length of infinity for every path, which includes an edge with the distortion above $D_{\max }$. Therefore, the shortest path will not include this edge. Every finite-length path that starts at vertex $a_{\mathrm{0,0}}$ and ends at vertex $a_{N_C-\mathrm{1,0}}$ results in a path length equal to the rate of the polygon it represents. Therefore, the shortest of all these paths corresponds to the polygon with the smallest bit rate, which is the solution to the problem in (1).

Let $R^{*}(a_{i,m})$ represents the minimum rate from $a_{\mathrm{0,0}}$ to $a_{i,m}$ via a polygon approximation. Let $q(a_{j,n})$ be the back pointer of $a_{j,n}$, which is used to remember the optimal path. Then, the solution of the shortest path can be found efficiently by the DAG shortest path algorithm²¹ formalized in Algorithm 1.

Algorithm 1

The ORD optimal shape coding algorithm.

We will explain how Algorithm 1 works. In lines 1 and 2, the admissible vertex set and the length of the sliding window length for each contour point are calculated. In line 3, the rate for encoding the starting point of the contour is assigned to the rate of the first polygon vertex, and the rate for reaching any of the admissible vertex is set to infinity. The “for loops” in lines 4 and 5 select the start vertex of a polygon edge and the “for loops” in lines 6 and 7 select its end vertex within the sliding window of the start vertex. The lines 8–10 are used to calculate the edge distortion and the edge rate, by which the edge weight can be determined. The most important part of this algorithm is the comparison in line 11. Here, it tests whether the new minimum rate, $R^{*}(a_{i,m})+w(a_{i,m},a_{j,n})$, to reach admissible vertex $a_{j,n}$, given that the last vertex was $a_{i,m}$, is smaller than the smallest minimum rate used so far to reach $a_{j,n}$, $R^{*}(a_{j,n})$. If this minimum rate is indeed smaller, then it is assigned as the new smallest minimum rate to reach admissible vertex $a_{j,n}$, $R^{*}(a_{j,n})=R^{*}(a_{i,m})+w(a_{i,m},a_{j,n})$, and the back pointer of $a_{j,n}$, $q(a_{j,n})$ is assigned to point to $a_{i,m}$ since this is the previous vertex used to achieve $R^{*}(a_{j,n})$. This algorithm leads to the optimal solution because when the rate $R^{*}(a_{i,m})$ of a vertex $a_{i,m}$ is given, then the selection of the future vertices $a_{j,n}$, $i<j\le L(i)$ is independent of the selection of the past vertices $a_{k,l}$, $0\le k<m$.

2.2.

Enhancements to the Operational Rate-Distortion Optimal Shape Coding

As we can see, the major problem in the ORD optimal shape coding algorithm is that the optimality is contingent on the chosen admissible vertex set,^1,9,10 sliding window strategy,^1,10,11 distortion measurement,^12–16 code table,^17–19 and the edge encoding structure. The former four parameters have been intensively investigated to relax their constraints and improve the shape coding performance. Here, we provide a brief summary.

2.3.

Traditional Eight-Direction Edge Encoding Structure

While intensive investigations have been made on the above four parameters, little attention has been paid to the edge encoding structure. Almost all the vertex-based ORD optimal shape coding algorithms employ the eight-direction edge encoding structure.²⁰ In this structure, the eight-connected chain code and the run-length encoding are combined by representing the edge between two admissible vertices by an angle ${\alpha }_{8\text{-}\mathrm{dir}}$ and a run ${\beta }_{8\text{-}\mathrm{dir}}$, which form the symbol $({\alpha }_{8\text{-}\mathrm{dir}},{\beta }_{8\text{-}\mathrm{dir}})$, as illustrated in Fig. 3(a). Each of the possible symbols $({\alpha }_{8\text{-}\mathrm{dir}},{\beta }_{8\text{-}\mathrm{dir}})$ gets a probability assigned and the resulting stream of the polygon $P$’s edges can be optimally encoded using these probabilities.

Fig. 3

Illustration of (a) the angle and the run of the eight-direction structure, (b) the quadrant number, the $x$-component magnitude, and the $y$-component magnitude of the quadrant structure, (c) the sector number, the short component magnitude, and the long component magnitude of the eight-sector structure, and (d) the sector number, the short component magnitude, and the long component magnitude of the 16-sector structure (Legend—solid line: encoding edge; asterisk: vertex; long dashed line: edge component; dashed line in (a): admissible positions for the next vertex given the current vertex at the origin; dashed line in (b): quadrant boundary; dashed line in (c) and (d): sector boundary).

In practical implementations, the design of code is under the hypothesis that the probability mass function of $({\alpha }_{8\text{-}\mathrm{dir}},{\beta }_{8\text{-}\mathrm{dir}})$ is separable²⁰ and ${\alpha }_{8\text{-}\mathrm{dir}}$ is uniformly distributed over all the eight restricted directions. Thus, ${\alpha }_{8\text{-}\mathrm{dir}}$ can be encoded separately and the optimal code for ${\alpha }_{8\text{-}\mathrm{dir}}$ is a 3-bit FLC. There are two main codes for ${\beta }_{8\text{-}\mathrm{dir}}$. One is based on the hypothesis that ${\beta }_{8\text{-}\mathrm{dir}}$ is geometrically distributed $[P({\beta }_{8\text{-}\mathrm{dir}}=j)=(1-p)/p^{j-1},j\ge 1]$ with a parameter $p=0.5$. In this case, the optimal code for ${\beta }_{8\text{-}\mathrm{dir}}$ is a RLC with ${\beta }_{8\text{-}\mathrm{dir}}-1$ zeros and a final “1.” Note that any positive integer value of ${\beta }_{8\text{-}\mathrm{dir}}$ is codable; therefore, the code has no edge length restriction. The other is based on the hypothesis that ${\beta }_{8\text{-}\mathrm{dir}}$ is piecewise uniformly distributed. In this case, the optimal code for ${\beta }_{8\text{-}\mathrm{dir}}$ is a VLC, which has the general form $[YX]$, where $Y$ is the length of $X$. Note that the largest possible value of ${\beta }_{8\text{-}\mathrm{dir}}$ has to be a finite positive integer $\epsilon$. A smaller $\epsilon$ often results in fewer bits for each edge, but requires more edges for the entire polygon. Conversely, a larger $\epsilon$ often results in fewer edges, but requires more bits for each edge. Usually, $\epsilon =15$ makes a good balance between the edge rate and the edge number over a wide range of contour characteristics and admissible distortions.¹¹ Thus, 15 codewords are needed. Reference 20 gives a typical example of such code table that $Y$ and $X$ are a 2-bit FLC and a $\lfloor {\log }_2{\beta }_{8\text{-}\mathrm{dir}}\rfloor$-bit FLC, respectively, where $\lfloor \rfloor$ is the floor operator.

To illustrate the eight-direction structure-based edge encoding scheme for encoding an edge, consider a restricted edge $(-\mathrm{7,7})$ (for simplicity, we use the coordinates of the ending point as the coordinates of the edge when this edge starts at the origin, similarly hereinafter), as shown in Fig. 3(a). Its angle and run take the values of $3·\pi /4$ and 7, which are encoded with a 3-bit FLC and a 7-bit RLC (a 4-bit VLC), resulting in 10 bits (7 bits) in total.

The above eight-direction structure-based edge encoding scheme is quite simple and easy to implement. However, the inherent limitation can be clarified as follows.

From a structural perspective, the uniquely decodable code for each edge consists of two parts representing ${\alpha }_{8\text{-}\mathrm{dir}}$ and ${\beta }_{8\text{-}\mathrm{dir}}$, and the total length of this code is $3+{\beta }_{8\text{-}\mathrm{dir}}$ when RLC is used or $5+\lfloor {\log }_2{\beta }_{8\text{-}\mathrm{dir}}\rfloor$ when VLC is used. For simplicity, assume that an edge of run ${\beta }_{8\text{-}\mathrm{dir}}$ approximates a contour segment of ${\beta }_{8\text{-}\mathrm{dir}}$ pixels. Then, the efficiency of this code, usually measured by the bits per contour pixel, is $3/{\beta }_{8\text{-}\mathrm{dir}}+1$ (${\beta }_{8\text{-}\mathrm{dir}}=\mathrm{1,2},\cdots$) or $(5+\lfloor {\log }_2{\beta }_{8\text{-}\mathrm{dir}}\rfloor )/{\beta }_{8\text{-}\mathrm{dir}}$ (${\beta }_{8\text{-}\mathrm{dir}}=\mathrm{1,2},\cdots ,15$). Note that both sequences are increasing as ${\beta }_{8\text{-}\mathrm{dir}}$ decreases; therefore, the shorter the run, the less efficient these codes are. Figures 1(a) and 1(b) show that many short restricted edges are needed for the contour segments which are not exactly in eight restricted directions. Therefore, the eight-direction edge encoding structure is inefficient.

From a description perspective, a good shape description should make the proportion of selected vertices at or near the corners of the original shape contour as high as possible so as to benefit the object-oriented applications.²² However, when the contour segments are not exactly in eight restricted directions, the eight-direction structure not only consumes a large number of closely spaced vertices, but also strengthens the contour quantization error and noise disturbances. This affects the subjective experiences of reconstruction contours as well as degrades the performance of the object-oriented applications.

Further, to reveal the problem of the existing eight-direction structure quantitatively from a systematic perspective, we map the contour segment in Fig. 1(b) into a weighted DAG, as shown in Fig. 2. It is observed that all 10 edge distortions uphold the admissible distortion, but 5 out of 10 edge weights are assigned infinity due to the direction restriction, making the shortest path in DAG quite long and thus the bit rate for the entire polygon much larger. Therefore, we should relax the direction restriction to increase the number of available edges. The following section follows this idea.

3.1.

Eight-Sector Edge Encoding Structure

A simple and intuitive structure for an edge of arbitrary direction consists of a quadrant number ${\alpha }_{\mathrm{quad}}$, an $x$-component magnitude ${\beta }_{\mathrm{quad}}$, and an $y$-component magnitude ${\gamma }_{\mathrm{quad}}$, which form the symbol $({\alpha }_{\mathrm{quad}},{\beta }_{\mathrm{quad}},{\gamma }_{\mathrm{quad}})$. The quadrant number ${\alpha }_{\mathrm{quad}}$ is defined as: quadrant 0 is the set of $(x,y)$ such that $x\ge 1$, $y\ge 0$, quadrant 1: $x\le 0,y\ge 1,\dots$, and quadrant 3: $x\ge 0$, $y\le -1$, as illustrated in Fig. 3(b). Assume that ${\alpha }_{\mathrm{quad}}$, ${\beta }_{\mathrm{quad}}$, and ${\gamma }_{\mathrm{quad}}$ are independently distributed; ${\alpha }_{\mathrm{quad}}$ is uniformly distributed over all the four quadrants; ${\beta }_{\mathrm{quad}}$ and ${\gamma }_{\mathrm{quad}}$ are geometrically or piecewise uniformly distributed. Then, ${\alpha }_{\mathrm{quad}}$ can be separately and optimally encoded with a 2-bit FLC and ${\beta }_{\mathrm{quad}}$ and ${\gamma }_{\mathrm{quad}}$ can be optimally encoded with RLCs or VLCs. The procedures to implement the quadrant structure-based edge encoding scheme are as follows:

Now we compare the performance of this quadrant structure with the traditional eight-direction one. If RLC is selected, for the quadrant structure, the bit rate for the symbol $({\alpha }_{\mathrm{quad}},{\beta }_{\mathrm{quad}},{\gamma }_{\mathrm{quad}})$, denoted by $r({\alpha }_{\mathrm{quad}},{\beta }_{\mathrm{quad}},{\gamma }_{\mathrm{quad}})$, is

Compared Eq. (4) with Eq. (5), we have $r({\alpha }_{\mathrm{quad}},{\beta }_{\mathrm{quad}},{\gamma }_{\mathrm{quad}})=3+2{\beta }_{8\text{-}\mathrm{dir}}$ when ${\beta }_{\mathrm{quad}}={\gamma }_{\mathrm{quad}}={\beta }_{8\text{-}\mathrm{dir}}$. Thus, although the quadrant structure can change the unrestricted edge rate from infinity to a finite value, it increases the diagonal direction edge rate from $3+{\beta }_{8\text{-}\mathrm{dir}}$ to $3+2{\beta }_{8\text{-}\mathrm{dir}}$, resulting in ${\beta }_{8\text{-}\mathrm{dir}}$ bits increment. Assume that an edge of run ${\beta }_{8\text{-}\mathrm{dir}}$ approximates a contour segment of ${\beta }_{8\text{-}\mathrm{dir}}$ pixels. Then, for the the diagonal direction edge, the quadrant structure changes the code efficiency from $3/{\beta }_{8\text{-}\mathrm{dir}}+1$ to $3/{\beta }_{8\text{-}\mathrm{dir}}+2$, resulting in 1 bit increment per contour pixel. Such a large cost makes the quadrant structure unfeasible in practice. With a similar comparison method, we can draw the same conclusion for the VLC case.

To illustrate this deficiency in the quadrant structure-based edge encoding scheme, reconsider the restricted edge $(-\mathrm{7,7})$, as shown in Fig. 3(b). Its quadrant numbers, $x$-component magnitude and $y$-component magnitude, take the values of 2, 7, and 7, which are encoded with a 2-bit FLC, an 8-bit RLC (a 5-bit VLC), and a 7-bit RLC (a 4-bit VLC), resulting in 17 bits (11 bits) in total. This is 7 bits (4 bits) more than those used by eight-direction structure.

The reason that the quadrant structure does not work well is that there exists dependency between the $x$- and the $y$-component magnitudes and the independency assumption is unreasonable. It motivates us to make a good use of this dependency. To achieve this aim, we design an edge encoding structure consisting of a sector number ${\alpha }_{8\text{-}\sec }$, a short component magnitude ${\beta }_{8\text{-}\sec }$, and a long component magnitude ${\gamma }_{8\text{-}\sec }$, which form the symbol $({\alpha }_{8\text{-}\sec },{\beta }_{8\text{-}\sec },{\gamma }_{8\text{-}\sec })$. From Ref. 2, we define the sector number ${\alpha }_{8\text{-}\sec }$ as: sector 0 is the set of $(x,y)$ such that $0\le y<x$, sector 1: $1\le x\le y$, and sector 7: $1\le -y\le x$, as illustrated in Fig. 3(c). The short component is the smaller component of the edge’s $x$- and $y$-components, while the long component is the larger component of them. Because the long component magnitude ${\gamma }_{8\text{-}\sec }$ is not smaller than the short component magnitude ${\beta }_{8\text{-}\sec }$, we can encode ${\gamma }_{8\text{-}\sec }$ with differential encoding method. In this way, we can make a good use of the dependency between the $x$- and the $y$-component magnitudes, and allow a further reduction in the number of bits used.

Let ${\delta }_{8\text{-}\sec }$ denote the difference between ${\beta }_{8\text{-}\sec }$ and ${\gamma }_{8\text{-}\sec }$, i.e., ${\delta }_{8\text{-}\sec }={\gamma }_{8\text{-}\sec }-{\beta }_{8\text{-}\sec }$. In our practical implementation, we design the code under the the hypothesis that the probability mass function of $({\alpha }_{8\text{-}\sec },{\beta }_{8\text{-}\sec },{\gamma }_{8\text{-}\sec })$ is separable and ${\alpha }_{8\text{-}\sec }$ is uniformly distributed over all the eight sectors. Thus, ${\alpha }_{8\text{-}\sec }$ can be separately and optimally encoded with a 3-bit FLC. Similarly with the assumption about the run in the eight-direction structure-based scheme,²⁰ we simply assume that both ${\beta }_{8\text{-}\sec }$ and ${\delta }_{8\text{-}\sec }$ are geometrically or piecewise uniformly distributed. Therefore, the optimal codes for both ${\beta }_{8\text{-}\sec }$ and ${\delta }_{8\text{-}\sec }$ are RLCs or VLCs. The procedures to implement the eight-sector structure-based edge encoding scheme are as follows:

If VLC is selected, similarly with the run encoding in the eight-direction structure-based scheme, the magnitudes of both $x$- and $y$- components are restricted to a predefined number $\epsilon$. Thus, we should design a series of code tables of the ranges from 1 to 1, 1 to 2, 1 to $\epsilon$ for both ${\beta }_{8\text{-}\sec }$ and ${\delta }_{8\text{-}\sec }$. A series of reference code tables with $\epsilon =15$ are shown in Table 1. Then, encode ${\beta }_{8\text{-}\sec }$ according to the table of the range from 1 to $\epsilon$ and encode ${\delta }_{8\text{-}\sec }$ according to the table of the range from 1 to $\epsilon -{\beta }_{8\text{-}\sec }+1$.

Table 1

Variable length encoding table for ε=15. The number of bits is determined by both the range and the value of β8-sec (β16-sec) or δ8-sec (δ16-sec).

Here, we reason why this structure works better than the traditional eight-direction one. If RLC is selected, for the eight-sector structure, the bit rate for the symbol $({\alpha }_{8\text{-}\sec },{\beta }_{8\text{-}\sec },{\gamma }_{8\text{-}\sec })$, denoted by $r({\alpha }_{8\text{-}\sec },{\beta }_{8\text{-}\sec },{\gamma }_{8\text{-}\sec })$, is

3.2.

Sixteen-Sector Edge Encoding Structure

The above eight-sector structure defines the short component magnitude ${\beta }_{8\text{-}\sec }$ and the long component magnitude ${\gamma }_{8\text{-}\sec }$ as the smaller and the larger magnitudes of the edge’s $x$- and $y$-components, and encode ${\beta }_{8\text{-}\sec }$ and the difference ${\delta }_{8\text{-}\sec }$ in a separate way. If RLC is selected, this structure requires $4+{\beta }_{8\text{-}\sec }+{\delta }_{8\text{-}\sec }$ bits. Although it can basically keep the bit rate for restricted edges, it will lead to a relatively larger number of bits for unrestricted edges, especially when both ${\beta }_{8\text{-}\sec }$ and ${\delta }_{8\text{-}\sec }$ take large values. The reason for this inefficiency is that there exists dependency between ${\beta }_{8\text{-}\sec }$ and ${\delta }_{8\text{-}\sec }$ and the independency assumption is unreasonable. It motivates us to make a good use of this dependency.

To achieve this aim, we design an edge encoding structure consisting of a sector number ${\alpha }_{16\text{-}\sec }$, a short component magnitude ${\beta }_{16\text{-}\sec }$, and a long component magnitude ${\gamma }_{16\text{-}\sec }$, which form a symbol $({\alpha }_{16\text{-}\sec },{\beta }_{16\text{-}\sec },{\gamma }_{16\text{-}\sec })$. The sector number ${\alpha }_{16\text{-}\sec }$ is defined as: sector 0 is the set of $(x,y)$ such that $0\le 2y<x$, sector 1: $1\le y<x\le 2y,\dots$, and sector 15: $1\le -2y\le x$, as illustrated in Fig. 3(d). The short component is the smaller component of the edge’s two octant direction components with $\pi /4$ difference in angle, while the long component is the larger component of them. Because the long component magnitude ${\gamma }_{16\text{-}\sec }$ is not smaller than the short component magnitude ${\beta }_{16\text{-}\sec }$, we can encode ${\gamma }_{16\text{-}\sec }$ with differential encoding method. Compared Fig. 3(d) with Fig. 3(c), we have ${\beta }_{16\text{-}\sec }=\min \{{\beta }_{8\text{-}\sec },{\delta }_{8\text{-}\sec }\}$ and ${\gamma }_{16\text{-}\sec }=\max \{{\beta }_{8\text{-}\sec },{\delta }_{8\text{-}\sec }\}$. Therefore, in this way, we can make a good use of the dependency between the short and the long component magnitudes of the eight-sector structure, and allow a further reduction in the number of bits used.

In our practical implementation, we use the same hypotheses and the corresponding optimal codes as we used in the eight-sector structure. The procedures to implement the 16-sector structure-based edge encoding scheme are as follows:

If VLC is selected, the magnitudes of both $x$- and $y$-components are restricted to $\epsilon$. Thus, we should design a series of code tables of the ranges from 1 to 1, 1 to 2, …, 1 to $\epsilon$ for both ${\beta }_{16\text{-}\sec }$ and ${\delta }_{16\text{-}\sec }$. Table 1 can also be used here:

Here, we reason why this structure with RLC can outperform the eight-sector one from a data compression perspective. For the 16-sector structure, the bit rate for the symbol $({\alpha }_{16\text{-}\sec },{\beta }_{16\text{-}\sec },{\gamma }_{16\text{-}\sec })$, denoted by $r({\alpha }_{16\text{-}\sec },{\beta }_{16\text{-}\sec },{\gamma }_{16\text{-}\sec })$, is

To illustrate this advantage, consider an unrestricted edge $(-\mathrm{3,7})$, as shown in Figs. 3(c) and 3(d). For the eight-sector structure, its sector number, short component magnitude, and long component magnitude take the values of 2, 3, and 7, which are encoded with a 3-bit FLC, a 4-bit RLC (4-bit VLC), and a 4-bit RLC (4-bit VLC), resulting in 11 bits in total. For the 16-sector structure, they take the values of 4, 3, and 4, which are encoded with a 4-bit FLC, a 4-bit RLC (a 3-bit VLC), and a 1-bit RLC (a 2-bit VLC), resulting in 9 bits in total. Thus, two bits are saved.

However, this bit reduction will degrade the ability in contour description. To look deep into this phenomenon, we plot the isorate contours for both the eight- and the 16-sector structures on Fig. 4, i.e., the traces of the ending points of the encoding edges having the same starting point and rate. For simplicity, assume that an edge of long component magnitude ${\gamma }_{8\text{-}\sec }$ approximates a contour segment of ${\gamma }_{8\text{-}\sec }$ pixels. We can see that for the eight-sector structure, the edges of the same rate have the same ${\gamma }_{8\text{-}\sec }$, thus can approximate contour segments of the same length in pixel. Therefore, for the eight-sector structure, the codes for the edges of the same rate have the same efficiency in terms of the bits per contour pixel. Instead, for the 16-sector structure, the edges of the same rate have different ${\gamma }_{8\text{-}\sec }$. To be more specific, the edges of directions $k·\pi /2\pm \arctan (1/2)$ ($k=\mathrm{0,1},\mathrm{2,3}$) have the maximum length over all the directions (named as preferential direction), while the edges of the restricted directions have the minimum length (named as nonpreferential direction), as shown in Fig. 4(b). Thus, the edges of the same rate but of different directions will approximate contour segments of the different lengths in pixel. Therefore, for the 16-sector structure, the codes for the edges of the same rate have different efficiencies, i.e., the codes for edges in or near the preferential directions have relatively higher efficiencies, whereas the codes for the edges in or near the nonpreferential directions have relatively lower efficiencies. This may bias the edge selection toward preferential directions via the ORD optimal framework, thereby giving false corners when contour segments are in or near the nonpreferential directions. We call it direction bias effect.

Fig. 4

(a) Isorate contour of the eight-sector structure when $R=12\text{bits}$, (b) isorate contour of the 16-sector structure when $R=11\text{bits}$, where the direction bias effect happens when contour segments are in or near the nonpreferential directions (Legend—solid line: isorate contour; dashed line in (a): restricted direction; long dashed line in (b): preferential direction; dashed line in (b): nonpreferential direction; dotted line in (b): encoding edge for the 8-sector structure; dashed dotted line in (b): encoding edge for the 16-sector structure; asterisk in (b): vertex).

To illustrate this effect, we take the approximation of the horizontal contour segment from point $a_{i,m}(\mathrm{0,0})$ to point $a_{j,n}(\mathrm{0,12})$ shown in Fig. 4(b) as an example. For the eight-sector structure, among all approximations, the one directly using edge $(a_{i,m},a_{j,n})$ is of the most efficiency. However, for the 16-sector structure, according to Eq. (7), nonpreferential direction edge $(a_{i,m},a_{j,n})$ will consume 17 bits, whereas two preferential direction edges $(a_{i,m},a_{k,l})$ and $(a_{k,l},a_{j,n})$ consume 8 bits and 8 bits, respectively, resulting in 16 bits in total. Thus, the ORD optimal framework may select these two edges rather than edge $(a_{i,m},a_{j,n})$ to approximate the horizontal contour segment, which gives a false corner $a_{k,l}(\mathrm{3,6})$. This effect may significantly affect the performance of related object-oriented applications, which will be further displayed in the next section.

4.1.

Arbitrary Direction Edge Encoding Structures for Shape Coding

For the RD performance assessments, five MPEG-4 binary shape sequences, namely Weather.qcif, News.qcif, Stefan.sif, Children.sif, and Forman.cif, are used. These sequences have various spatial and temporal resolutions.

Figure 5(a) shows the cumulative RD curves generated with different ORD optimal algorithms. As expected, our two structures always outperform the traditional eight-direction structure, with up to 48.9% bit savings. Figure 5(b) compares the number of available edges between eight-direction and our arbitrary direction structures on Stefan sequence when $D_{\max }=1.5\mathrm{pels}$. The numbers of edges available for our arbitrary direction structures without AVB and with AVB are 3–6.3 and 3.5–5.5 times of those available for the eight-direction structure. These additional available edges provide the ORD optimal framework more opportunities to find a shorter shortest paths in a weighted DAG with much less infinity weights. That is why our structures can result in much fewer encoding bits than the eight-direction one, which is consistent with the analysis given in Sec. 2.3. It also indicates how important the direction relaxation is from a compression perspective.

Fig. 5

Compression performance comparisons. (a) Cumulative RD results from five sequences calculated by various ORD optimal algorithms; (b) number of available edges calculated frame by frame on the Stefan sequence when $D_{\max }=1.5\mathrm{pels}$.

Figure 5(a) also reveals that the coding gain varies with different parameter configurations. Here, we only point out the variations with two different configurations and give explanations as follows.

For the description assessments, the Stefan object of the 100th frame of the Stefan sequence has been used.

Figure 6 shows the polygons generated with various ORD optimal algorithms. Considering the first column as an example, we can see that the traditional eight-direction structure needs 68 vertices for contour approximation, but both of our structures only need 28 vertices. As a result, the traditional one needs 453 bits, whereas our two proposals need 359 and 325 bits for contour encoding, resulting in 94 and 128 bit savings, respectively.

Fig. 6

Description ability comparisons among various ORD optimal algorithms on the Stefan object (Legends—solid line: approximating polygon; dashed line: original contour; asterisk: vertex). (a) Traditional eight-direction edge encoding structure, (b) proposed eight-sector edge encoding structure, (c) proposed 16-sector edge encoding structure.

Moreover, we see that the polygons approximated by our proposals are quite compact and have strong ability to reflect the characteristics of the original object contour, since a relatively straight contour segment is easier to be approximated by an edge, so that the turns of the polygons are more likely to be the corners of the object contour. This will benefit the successive object-oriented applications. In the next section, we will apply these polygons to hand gesture recognition.

4.2.

Arbitrary Direction Edge Encoding Structures for Hand Gesture Recognition

Hand gesture recognition is of great importance in human-computer interaction. Usually, the shape feature is sufficient for successful recognition.²³ However, due to the nature of optical camera, the quality of captured images is sensitive to the lighting conditions and cluttered backgrounds, which makes it very difficult to obtain hand shapes.²⁴

Due to the new advent of Kinect depth camera (Shenzhen, China),²⁵ new opportunities for shape-based hand gesture recognition emerge. With the Kinect depth camera, we collect three hand gesture categories, namely Rock, Paper, and Scissors; each category has 50 samples, which contain various rotations, scales, viewpoints, and even self-occlusions. Then, by thresholding from the nearest depth position with a certain gap, we can obtain the hand shapes robustly. Some exemplars, including their color maps, depth maps, and segmented hand shapes, are illustrated in Fig. 7.

Fig. 7

Illustration of our hand gesture dataset captured by the Kinect camera. The first and second columns are the color and depth maps in our dataset, and the third column is the segmentations of hands.

However, even with the help of Kinect camera, due to the limited camera resolution and the complex monitoring environment, quantization error and contour noise are almost inevitable in shape acquisition. Since the ORD optimal algorithms with our two arbitrary edge encoding structures can approximate the contour segments with arbitrary directions, quantization error, and contour noise, it is suitable to handle this recognition task.

Here, we only choose RLC to guarantee that there is no limitation on the encoding edge length. We approximate the hand shape contour by the polygons using our proposals. It is important to determine a proper $D_{\max }$. We let $D_{\max }$ be proportional to the radius of the maximal inscribed disk of the hand shape, so that $D_{\max }$ is adaptive to the size of palm. To be specific, we set $D_{\max }$ to 30% of the radius, as this can well discriminate nonsalient fingers from large shape deformations. Only the negative turns of the polygons are considered, since it was reported that the negative corners are much more informative than the positive ones.²⁶ Suppose that there are $k$ negative turns, we classify a hand gesture to Rock if $k=0$, Paper if $k\ge 3$, and Scissors otherwise.

Table 2 provides the confusion matrices and the mean recognition accuracies for various ORD optimal algorithms with our two arbitrary direction structures. As expected, the mean accuracies of the eight-sector structure are much higher than those of the 16-sector structure due to the direction bias effect as mentioned in Sec. 3.2.

Table 2

Confusion matrices for Basic-8-Sector/Basic-16-Sector and AVB-8-Sector/AVB-16-Sector algorithms. The mean recognition accuracies are 93.33%/86% and 94%/76%, respectively. For each gesture category, the higher recognition accuracy between the 8-sector structure and the 16-sector structure is marked in bold. We can see that 8-sector structure always results in higher recognition accuracy, endorsing the earlier comment about 8-sector structure having stronger description ability than 16-sector one.

To further reveal this direction bias effect, Fig. 8 shows some results selected from our collected dataset. The odd columns show the hand gestures correctly recognized by both of our structures, while the even columns show those correctly recognized by the eight-sector structure but wrongly recognized by the 16-sector structure, except the Paper results which are wrongly recognized by the Basic-16-Sector algorithms. We take the second Rock gesture recognized by the Basic algorithms as an example. Although the 16-sector structure can reduce the total rates from 259 to 202 bits compared with the eight-sector structure, the bottom right contour segment of the direction near the restricted direction of zero is approximated by two edges of the directions near the preferential directions of $\mp \arctan (1/2)$ due to the direction bias effect, and therefore, a false-negative turn is generated. It demonstrates that the 16-sector structure does well in compression but is not good at description for object-oriented applications, which is the opposite of the eight-sector structure.

Fig. 8

Hand gesture recognition by the negative turn detection (Legends—solid line: approximating polygon; dashed line: original contour; asterisk: vertex; dot: negative turn). (a) Contour approximations of the Rock gestures, (b) contour approximations of the Paper gestures, (c) contour approximations of the Scissors gestures.