Anchor Points Coding (APC)

The algorithm encodes the contour of an image, where the contours are represented using a contour graph and the position of vertices in the contour graph.

(1) Search column-wise in the contour graph for a vertex with at least one unvisited adjacent vertex (an anchor point). Mark the found vertexP1= (i, j) as Υ(i, j) = 1.

(2) IfP1is an edge anchor point, select its only adjacent vertex as the direction point.

IfP1= (i, j) is a double anchor point, then selectP2= (i, j+ 1) as direction point, and ifP1 is selected again as anchor point, then select (i+ 1, j) as direction point.

(3) Generate the current contour segment, Γk,by either selecting the only unvisited adjacent vertex as the next vertex to visit, or by selecting one of the unvisited adjacent vertices using Directives T1-T4 as the next vertex to visit.

(4) Check each vertex from the vector Γk,of vertices that draws the current contour segment, if it is a possible anchor point using the Directives C1 and C2. Save the position of the found presumptive anchor points in the list Ψ of possible relative anchor points, and mark in Υ,using the symbol ‘2’, the remaining vertices in Γk. (5) While the current index`points to an incremented location in Ψ:

(5.1) If Ψ(`) is an anchor point, then set Φ(`) = 1, else set Φ(`) = 0.

(5.2) Determine the position of the direction point from the way the anchor point was traversed the first time using Directives T1-T2.

(5.2) Continue generating the current contour segment Γkas in step (4).

(6) Continue with step (1) until no more anchor points are found.

(7) Codify using the 3OT representation each Γk (starting from 3^rd position), and generate a vectorSk. Concatenate all the vectorsSkintoS= [S1^T S^T2 · · · S^Tn_Γ]^T. (8) Encode each entityS, Φ,and Υ (in this order) usingCTMwith Laplace estimator.

3.2.2 Encoding contour edges

In publication [P3], we introduce a different strategy for compressing the contours, where we choose to represent the contour using contour edges (called in [P3] crack-edges). The contour edges (crack-edges) are stored using two binary matrices, each of size nr×nc: one matrix to store the vertical contour edges, denoted V; and one matrix to store the horizontal contour edges, denoted H. Using these two matrices we are able to achieve a much simpler connection between the image grid and the contour edge grid. In each location of the vertical binary matrix a vertical edge is stored, that is set as follows: if the pixel positions (x, y−1) and (x, y), in the initial image Z, are belonging to two different regions, i.e. if Z(x, y−1)6=Z(x, y), then the vertical edge is set as active byV(x, y) = 1, else it is set as inactive byV(x, y) = 0. Similarly, in each location of the horizontal binary matrix a horizontal edge is stored, whereH(x, y) = 1 ifZ(x−1, y)6=Z(x, y) and H(x, y) = 0 otherwise. Figure 3.6 shows an example of the way active contour edges are set in the two binary matrices.

Figure 3.6: The representation of contour edges using two binary matrices. Black lines are marking the inactive contour edges. A cyan line is marking the active vertical edge,V(x, y) = 1,betweenZ(x, y) andZ(x, y−1).A blue line is marking the active horizontal edge,H(x, y) = 1,betweenZ(x, y) andZ(x−1, y).

The image contour is transmitted to the decoder by encoding the two binary matricesH andV.Although the information regarding the crack-edges is divided into two matrices, the coding of each vertical and horizontal edge is done using both binary matrices. Template Context Tree Model (^TCTM) is the statistical model used to encode the representation, where two different templates are introduced.

The template shown in Figure 3.7.(a) is used to encode a vertical edge, where the previous two lines in the two binary matrices are used to create the template context using 10 horizontal edges from H and 7 vertical edges from V. Let us denoteT^v the context tree obtained using this template. The template shown in Figure 3.7.(b) is used to encode a horizontal edge. Similarly, the previous two lines in the two binary matrices are used to create the template context using 7 horizontal edges from H and 10 vertical edges from V. Let us denoteT^h the context tree obtained using this template. Note that in both cases the length of the context is 17. The order, in which the edges are collected in the template context, was fixed after testing different orders for a set of five different depth-map images. Each image has an optimal order selection that could be found by a greedy method. We choose not to search for it because its method is increasing the algorithm’s complexity and the obtained decrease in bitrate is very small.

The two binary matrices, V and H, are scanned row-wise by first traversing the rowxfromH, and then traversing rowxfromV. The symbols distributions, at each node in each context treeT^v and T^h, are collected in the first pass. The two context trees are then pruned, and the optimal context treesT^v and T^h are obtained. In the second pass, the contour edges saved in the two binary matrices are encoded using the two optimal trees [51, 70]. To lower the complexity of the algorithm and to decrease the runtime, in [P3], we developed two versions for the contour compression algorithm. We summarized the High Complexity (HiCo) ver-sion (described above) in an algorithm denoted Algorithm C (^{Alg. C}), presented in Algorithm 3.2. In the second version of the algorithm, called Fast, the com-plexity is decreased by using only one pass to encode each binary matrix. Hence,

(a) (b)

Figure 3.7: The context template used to encode: (a) a vertical edge; (b) a horizontal edge. The cyan lines are marking the position of the vertical edges added in the templates. The blue lines are marking the positions of the horizontal edges added in the templates. The numbers in the circles are denoting the contour edges order in the template. Both images represent the imageZ,with the contour edges marked as in Figure 3.6.

in Fastthe balanced treesT^v andT^hare used to encode the contour edges, and the context template length (and tree depth), is decreased from 17 to 15.

The regions in the image must be separated by a continuous contour; otherwise we cannot distinguish two neighbor regions, which give the contour edge the pro-priety that each of its ends is connected with at least one other contour edge end.

Exceptions appear only for the contour edges at the image boundary. This propri-ety is used in [P3] to improve the compression by finding deterministic cases where the contour edge can be predicted from its neighboring edges. Unfortunately, only for the vertical edges we found deterministic cases. In Figure 3.7.(a), if all the con-tour edges in the positions 1,2,and 3 are inactive, then the unknown vertical edge marked with the red line is also inactive. A simple explanation is that, because all the contour edges in the three positions are inactive, all four pixels, between which these contour edges are set, are in the same region, and hence the last unknown edge out of the four is always inactive. If only one contour edge is active and has any position 1,2,or 3,then the unknown vertical edge, marked with the red line in Figure 3.7.(a), is always active. The propriety described above is used here, since the unknown vertical edge has at the upper end a connection with one active contour edge, it must be active so that the contour can be continuous.

The non-stationarity propriety of the context distributions was used in publi-cation [P3], where during the count collection, we try to down-weigh some counts in each context by halving the values of the symbols distribution. Note that the context that has all the contour edges inactive is the only context that has a