An Efficient Region Merging Algorithm in Raster Space

Abstract

This work introduces a new region merging algorithm operating in raster space represented by a 4-connected graph. Necessary definitions are introduced first to derive a new merging function formally. An implementation is described after that, which consists of two steps: a determination of the shared trails of the input cycles, and construction of the resulting merged region. The cycles defining the regions are represented by the Freeman crack chain code in four directions. The algorithm works in linear time On, where n is the number of total graph vertices, i.e. pixels. However, the expected time complexity for one merging operation performed by the algorithm is O1.

1. Introduction

Region merging is one of the most commonly performed tasks in image processing that enables Object-Based Image Analysis (OBIA). Early approaches to OBIA performed image segmentation by the classical split and merge approach. Here, a meaningful partition was defined by applying a split process to define a set of elementary (homogeneous) regions that are then merged under certain conditions [1]. The latter may be based on geometric attributes like area, texture attributes like statistical moments of intensity distribution, shape attributes like shape factors, or any of their combinations [2, 3, 4]. On the other hand, more recent approaches to OBIA focus on hierarchical image segmentations that are based on scale-space representation, i.e. a set of image segmentations at different detail levels, in which the segmentation at finer levels are nested with respect to those at coarser levels [1, 5]. Some popular examples of such hierarchies include max-tree [6], $\alpha$-tree [7, 8], and watershed hierarchies [9]. Unfortunately, hierarchical segmentation results in a huge number of nested partitions, which have to be merged efficiently. The region merging becomes in this way one of the most critical parts of the segmentation process.

Region merging can be considered from different theoretical aspects. A set merging problem, which has a long history in computing, is the first of them. Hopcroft and Ullman [10] proposed two algorithms based on quadtrees, both working in $O\left(nlogn\right)$ time, where $n$ is the number of elements in the sets. In the first algorithm, the elements can be placed only in the leaves, while, in the second algorithm, the elements can exist in any of the tree vertices. Another tree-based algorithm was proposed by Tarjan [11] with the time complexity of $O\left(m\alpha \left(m,n\right)\right)$, where $\alpha \left(m,n\right)$ is related with the inverse Ackermann function, while $m$ and $n$ correspond to the numbers of elements in both sets. His algorithm was also used by Najman et al. [9] for hierarchical watershed cuts. Tarjan and van Leeuwen [12] performed the worst-case analysis of the algorithms and concluded that the linear-time set-merging algorithm remains an open problem. Cormen et al. [13] also considered merging of the disjoint sets using either linked lists or trees. Another solution for merging regions was introduced by Horowitz and Pavlidis [14]. This method is also based on quadtrees, with, as pointed out by Brun and Domenger, considerable limitations [15]. They recognised that the regions differ importantly from the classical understanding of the sets. Namely, the elements of the regions also have spatial attributes (i.e. raster coordinates), and, therefore, it is possible to determine the border of the regions uniquely. Brun and Domenger developed a method by placing the image in the Khalimsky plane [16]. The region is considered as a set of topological maps which are mapped in the Euclidean plane. Another approach is based on the theory of geometric and solid modelling [17, 18], where merging is considered as a special case of the Boolean union. The so-called regularised Boolean operations were introduced to preserve the dimension homogeneity of the resulting object [19]. The solution is, typically, found in two steps. First, the intersection points between the involved geometric objects are determined, and second, the resulting shape is determined by the so-called walkabout. In 2D, the first part is solved in the expected time $O\left(\left(n+m\right)log\left(n+m\right)+I\right)$, where $n$ and $m$ are the number of vertices determining the input polygons, and $I$ is the number of actual intersections [20]. If the proper data structure is used, the second step is realised in linear time. Such data structures have been proposed by Grainer and Horman [21], Vatti [22], and Liu et al. [23]. Rivero and Feito [24] proposed an approach for Boolean operations on polygons based on the theory of simplices. Their idea was later improved in ref. [25]. Very recently, an algorithm for Boolean operations for rasterised shapes was presented in ref. [26]. A space-filling curve was applied for the determination of the intersected pixels, while the walkabout was performed with a Greiner and Horman-like data structure. The proposed geometric approaches, however, cannot be applied in the OBIA, as they are based on the theory of regularised Boolean operations, which preserves the dimensional homogeneity of the resulting objects strictly. Consequently, this approach cannot handle all possible cases which may appear during region growth.

In this chapter, a new solution is proposed for a general region merging problem suitable for hierarchical OBIA. The main contributions are a theoretical derivation of the merging function in the raster space, represented by a 4-connected graph, and a proposal of an efficient implementation based on chain codes that ensure compact region representation.

The chapter is structured in five sections. Section 2 introduces the problem and formalises it. Brief implementation hints are given in Section 3. Section 4 presents empirical results, while Section 5 concludes the chapter.

2. Definitions

The key terms, needed to present the problem and to derive its formal solution, are defined in this section. Among other concepts, the region, raster space, and region merging are defined, which appeared in the title of this chapter.

Directed graph. $G=\left(V,E\right)$ defined by a vertex set $V=\left\{v_i\right\}$ and an edge set $E=\left\{e_{i,j}\right\}$ is a directed graph if $E$ is given by ordered pairs (directed edges) of vertices $e_{i,j}=\left(v_i,v_j\right)$.

Raster space. Let $G=\left(V,E\right)$ be a directed graph. If $V$ is determined by regularly spaced vertices $v_i=\left(x_i,y_i\right)$ with integer coordinates $x_i\in \left[0,X\right]$ and $y_i\in \left[0,Y\right]$, and $E$ imposes 4-connectivity on them, then $G$ defines the raster space. In other words, for each pair of adjacent vertices $v_i,v_j$ linked by edge $e_{i,j}\in E$, there exists either relation $e_{i,j}\to \left(x_j,y_j\right)=\left(x_i\pm 1,y_i\right)$ or $e_{i,j}\to \left(x_j,y_j\right)=\left(x_i,y_i\pm 1\right)$. Each vertex can also be linked to itself, thus, $\forall v_i\in V\to e_{i,i}\in E$.

Intuitively, a region is a group of connected raster cells (grid cells or pixels). It may be represented either as a collection of the pixels themselves or by its boundary. This second possibility is used in this work. It is based on the concepts of trail and cycle which must, therefore, be introduced first.

Trail. Trail $t_{i_0,i_L}=⟨v_{i_0},v_{i_1},\dots ,v_{i_L}⟩$ in G with length $L$ is a sequence of adjacent vertices where for each pair $v_{i_l},v_{i_{l+1}}\in t_{i_0,i_L}\to e_{i_l,i_{l+1}}\in E$. Trails $t_{i_0,i_L}$ and $t_{j_0,j_K}$ are connected if they share at least one subtrail, i.e. if a set of subtrails $T=t_{i_0,i_L}\cap t_{j_0,j_K}\ne \mathrm{Ø}$.

Figure 1 shows two cases of connected trails. Trails $t_{0,6}$ and $t_{7,8}$ are connected through subtrail $t_{4,4}=⟨v_4,v_4⟩$ in Figure 1a, while trails $t_{0,6}$ and $t_{9,7}$ in Figure 1b share two subtrails, namely $T=t_{0,6}\cap t_{9,7}=\left\{t_{1,1},t_{3,5}\right\}$, where $t_{1,1}=⟨v_1,v_1⟩$ and $t_{3,5}=⟨v_3,v_4,v_5⟩$. The shared subtrails will be hereinafter referred to as the intersection trails.

Figure 1.

Connected trails: (a) $t_{0,6}=⟨v_0,v_1,v_2,v_3,v_4,v_5,v_6⟩$, $t_{7,8}=⟨v_7,v_4,v_8⟩$, (b) $t_{0,6}=⟨v_0,v_1,v_2,v_3,v_4,v_5,v_6⟩$, $t_{9,7}=⟨v_9,v_1,v_8,v_3,v_4,v_5,v_7⟩$.

Trail $t_{i_0,i_L}$ can be split into two trails $t_{i_0,i_l}$ and $t_{i_{l+1},i_L}$ at any $v_{i_l}\in t_{i_0,i_L}$. $t_{i_0,i_L}$ is, therefore, a concatenation of $t_{i_0,i_l}$ and $t_{i_{l+1},i_L}$ as formally shown in Eq. (1):

$$t_{i_0,i_L}={t_{i_0,i_l}}^{⌢}{t}_{i_{l+1},i_L}.$$E1

Cycle. Trail $t_{i_0,i_L}=⟨v_{i_0},v_{i_1},\dots ,v_{i_{L+1}}⟩$ is cycle $c_{i_0,i_L}=⟨v_{i_0},v_{i_1},\dots ,v_{i_L}⟩$, if $i_0=i_{L+1}$. As each vertex can be linked to itself, the smallest cycle $c_{i_0,i_0}=⟨v_{i_0}⟩$ is defined by trail $t_{i_0,i_0}=⟨v_{i_0},v_{i_0}⟩$. Contrary to the traditional definition of cycle, we do require that all vertices, except the end vertices, are distinct in $c_{i_0,i_L}$. Any cycle can, because of this, be composed of more than one cycle, where intermediate vertices are contained more than once.

Figure 2 shows examples of two cycles. The one in Figure 2a contains each vertex exactly once, while vertices $v_2$, $v_3$, and $v_4$ are contained twice in the cycle in Figure 2b. Note that any cycle can be rotated by any number of vertices $0<l\le L$, i.e. $c_{i_0,i_L}=⟨v_{i_0},v_{i_1},\dots ,v_{i_L}⟩=⟨v_{i_l},v_{i_{l+1}},\dots ,v_{i_L},v_{i_0},v_{i_1},\dots ,v_{i_{l-1}}⟩=c_{i_l,i_{l-1}}$. Its decomposition can then be described as concatenation from Eq. (2):

Figure 2.

Cycles: (a) $c_{0,7}=⟨v_0,v_1,v_2,v_3,v_4,v_5,v_6,v_7⟩$, (b) $c_{0,10}=⟨v_0,v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_4,v_3,$ $v_8,v_9,v_2,v_{10}⟩$.

$$c_{i_0,i_L}={t_{i_l,i_k}}^{⌢}{t}_{i_{k+1},l_{L-1}}.$$E2

As shown in Figure 3, any subtrail $t_{i_l,i_k}\subseteq c_{i_0,i_L},0\le l,k\le L$, can be removed from cycle $c_{i_0,i_L}$ according to Eq.(3). The obtained result is also a subtrail.

Figure 3.

Removing trail $t_{i_l,i_k}$ (on the right) from cycle $c_{i_0,i_L}$ results in subtrail $t_{i_{k+1},i_{l-1}}$ (on the left).

$$t_{i_{k+1},i_{l-1}}=c_{i_0,i_L}\backslash t_{i_l,i_k}.$$E3

Let $c_{i_0,i_3}=⟨v_{i_0},v_{i_1},v_{i_2},v_{i_3}⟩$ be an elementary clockwise oriented cycle, where $v_{i_0}=\left(x_i,y_i\right),v_{i_1}=\left(x_i,y_i+1\right),v_{i_2}=\left(x_i+1,y_i+1\right)$, and $v_{i_3}=\left(x_i+1,y_i\right)$. This elementary cycle defines a grid cell, with its interior on the right side of each edge $e_{i_l,i_{l+1}}=\left(v_{i_l},v_{i_{l+1}}\right)$, $0\le l\le 3$ as shown in Figure 4.

Figure 4.

Elementary cycle $c_{i_0,i_3}$ enclosing a grid cell.

Region. The region $R$ is either a grid cell defined by an elementary clockwise oriented cycle or a group of grid cells bounded by the resulting cycle(s) of the region merging function (defined soon after this definition). For simplicity, a region will be equated with its boundary in the continuation, i.e. $R$ will be treated as a cycle or a set of cycles.

Figure 5 shows the result of merging two elementary cycles $c_{i_0,i_L}$ and $c_{j_0,j_K}$ $\left(L=K=3\right)$, which share either an edge (Figure 5a) or a vertex (Figure 5b). It indicates that the resulting merged region is defined by a concatenation of both elementary cycles without their intersection $c_{i_0,i_L}\cap c_{j_0,j_K}$. Note, however, that $c_{i_0,i_L}$ and $c_{j_0,j_K}$ are both oriented in the clockwise direction, and, therefore, the orientation of the shared edges is opposite. To make them equal and, thus, to make their intersection non-empty, the orientation changing operation $\leftarrow$ is defined here, such that $\overleftarrow{c_{i_0,i_L}}=⟨v_{i_L},v_{i_{L-1}},\dots ,v_{i_0}⟩$. Figure 6 shows an example of merging two non-elementary cycles which still share a single, but longer intersection trail. A similar conclusion as above may be made. The region merging function may be formally defined now.

Figure 5.

Merging two elementary cycles with a shared edge (a) and vertex (b); the resulting cycles are in violet.

Figure 6.

Merging of two non-elementary cycles whose intersection trail is a longer sequence of edges.

Region merging function. Two cycles $c_{i_0,i_L}$ and $c_{j_0,j_K}$, which share a single intersection trail $t_{i_l,i_k}$ can be merged into a region $R$ by a merging function $\mathcal{M}$ defined by Eq. (4):

$$\begin{array}{ll}\mathcal{M}\left(c_{i_0,i_L},c_{j_0,j_K},t_{i_l,i_k}\right)& ={\left(c_{i_0,i_L}\backslash \left(c_{i_0,i_L}\cap \overleftarrow{c_{j_0,j_K}}\right)\right)}^{⌢}{⟨v_{i_l}⟩}^{⌢}{\left(c_{j_0,j_K}\backslash \left(c_{j_0,j_K}\cap \overleftarrow{c_{i_0,i_L}}\right)\right)}^{⌢}⟨v_{i_k}⟩=\\ & ={\left(c_{i_0,i_L}\backslash t_{i_l,i_k}\right)}^{⌢}{⟨v_{i_l}⟩}^{⌢}{\left(c_{j_0,j_K}\backslash t_{j_n,j_m}\right)}^{⌢}⟨v_{i_k}⟩=\\ & ={t_{i_{k+1},i_{l-1}}}^{⌢}{⟨v_{i_l}⟩}^{⌢}{t_{j_{m+1},j_{n-1}}}^{⌢}⟨v_{i_k}⟩=\\ & ={t_{i_{k+1},i_{l-1}}}^{⌢}{⟨v_{j_m}⟩}^{⌢}{t_{j_{m+1},j_{n-1}}}^{⌢}⟨v_{j_n}⟩.\end{array}$$E4

In a general case, where the intersection of the input cycles consists of more trails, the merged region R is defined by Eq. (5):

$$R=\bigcap _{t_{i_l,i_k}^{\left(h\right)}\in T_i}\mathcal{M}\left(c_{i_0,i_L},c_{j_0,j_K}.t_{i_l,i_k}^{\left(h\right)}\right).$$E5

Eq. (4) is thus applied when $\mid T_i\mid =\mid T_j\mid =1$, where $T_i=\left\{t_{i_k,i_l}\right\}=c_{i_0,i_L}\cap \overleftarrow{c_{j_0,j_K}}$ and $T_j=\left\{t_{j_m,j_n}\right\}=c_{j_0,j_K}\cap \overleftarrow{c_{i_0,i_L}}$. On the other hand $\mid T_i\mid =\mid T_j\mid >1$ implies utilisation of Eq. (5) and each intersection trail then results in a new cycle. $\mid T_i\mid$ cycles are, therefore, constructed, and the resulting region is described by the intersection of these cycles. Note that $h$, such that $0\le h<\mid T_i\mid$, is an index of the intersection trail in Eq. (5). It is obvious that Eq. (5) is valid also when $\mid T_i\mid =1$.

Figure 7 shows an illustrative example. The set of intersection trails is $T_i=\left\{t_{i_5,i_6},t_{i_8,i_9}\right\}$. Applying Eq. (4) on the intersection trail $t_{i_5,i_6}\in T_i$ results in Figure 7b. Similarly, using Eq. (4) on the second intersection trail $t_{i_8,i_9}\in T_i$ gives Figure 7c. The final result is then obtained as an intersection (Eq. (5)) between cycles from Figure 7b and c. As seen in Figure 7d, the resulting region $R$ consists of two cycles, which are exactly the same as $\mid T_i\mid$.

Figure 7.

Applying Eq. (5) to merge two cycles whose intersection consists of two intersection trails, i.e. $\mid T_i\mid =2$.

3. Implementation

The concept of chain codes is used to represent regions $R\subseteq G$ in the presented method. The chain code, introduced by Freeman [27], consists of a few simple commands by which navigation through the edges of $G$ is made possible. Freeman proposed two chain codes known as Freeman chain code in eight ($F8$) and four ($F4$) directions. Other chain codes were discovered by Bribiesca (Vertex Chain Code, $\mathit{VCC}$) [28], Sánchez-Cruz and Rodríguez-Dagnino (Three-Orthogonal chain code, $3\mathit{OT}$) [29], Žalik et al. (Unsigned Manhattan Chain Code, $\mathit{\text{UMCC}}$) [30], and Dunkelberger and Mitchell (Mid-crack Chain Code) [31]. In general, there are two types of chain codes: those operating on raster pixels and those working with raster edges. The latter is known as crack-chain codes [32, 33]. $F4$ is the only chain code which can be used in both contexts, and its crack interpretation is used in this algorithm.

The $F4$ alphabet consists of four commands/symbols ${\sigma }_i\in {\mathrm{\Sigma }}_{F4}$, ${\mathrm{\Sigma }}_{F4}=\left\{\mathrm{0,1,2,3}\right\}$, shown in Figure 8. Let $⟨{\sigma }_i⟩$ be the sequence of $F4$ commands. To embed the chain code in $G$, the position of the chain code starting vertex $v_0$ is needed, while the positions of the remaining vertices are determined from the $F4$ commands according to Eq. (6):

Figure 8.

$F4$ chain code symbols (a); the elementary cycle described by $F4$ chain code symbols (b).

$$v_{i+1}=\left\{\begin{array}{cc}\left(x_i+1,y_i\right),& \text{if}{\sigma }_i=0;\\ \left(x_i,y_i-1\right),& \text{if}{\sigma }_i=1;\\ \left(x_i-1,y_i\right),& \text{if}{\sigma }_i=2;\\ \left(x_i,y_i+1\right),& \text{if}{\sigma }_i=3.\end{array}\right.$$E6

Figure 8b shows the elementary cycle $c_{i_0,i_3}$ determined as $v_{i_0}⟨\mathrm{1,0,3,2}⟩$, where $v_{i_0}=\left(x_{i_0},y_{i_0}\right)$ are the coordinates of the cycle’s starting vertex.

Any region in $G$ can be represented in this way. For example, regions containing more cycles are shown in Figure 9, where, for better presentation, the inner cells of the region are shadowed. According to the definitions from Section 2, a vertex $v_i\in R$ can be part of two cycles at the same time, or, within each cycle, $v_i$ can be passed twice, too. In the continuation, the cycle corresponding to the outer border of $R$ is considered as a loop, while cycles representing holes are named rings [19]. The orientation of the loop is clockwise, while the rings’ is the opposite (Figure 9).

Figure 9.

Region with two rings: The rings’ vertices (green, black) can be shared with the loop (red); the vertices within the loop can be used twice.

A data structure for representing $R$ is shown schematically in Figure 10. It consists of an array of starting points and an array of $F4$ chain code sequences. The loop is always located at index 0, and $k$, $k\ge 0$, rings follow in an arbitrary order. The algorithm, which implements Eq. (5), consists of two main steps:

• Determining the intersection trails $T_i$ between cycles of input regions and

• Realising Eq. (5) by performing a walkabout through the edges not in $T_i$.

Figure 10.

Data structure of region $R$: Array of starting points (left) of individual cycles and the corresponding sequences of $F4$ chain codes (right).

3.1 Determining the intersection trails

Determination of intersection points between edges of regions can be related with the problem of finding intersections between polygon edges. As the naive implementation of the latter works with $O\left(n^2\right)$ time complexity, various approaches were suggested to reduce it [13, 34, 35, 36]. The presented solution exploits the fact that regions $R_i$ and $R_j$ are embedded into common directed graph $G$, i.e. $R_i\in G\wedge R_j\in G$. The following data are associated with each vertex $v_i\in G$:

• two pointers ($P_{i1}$ and $P_{i2}$) into an array of $F4$ symbols for region $R_i$ (one or both pointers can be NULL),

• two pointers (${\mathit{LR}}_{i1}$ and ${\mathit{LR}}_{i2}$) pointing to the loop, or to the corresponding ring of region $R_i$ (similarly as above, one or both pointers can be NULL), and

• the same information for region $R_j$.

Let us consider the example in Figure 11, where the loop’s edges of $R_i$ are plotted in red, the edges of its ring in black, while edges of region $R_j$ are in cyan. The content of data structures for both regions is given in Table 1. Table 2 shows the information of some characteristic vertices in $G$. Vertex $v_a$, for example, belongs to $R_i$, its $P_{i1}$ points to the index 1 in the array of $F4$ chain codes, and the vertex belongs to the loop (${\mathit{LR}}_{i2}=0$). Vertex $v_f$ is met two times by the edges of the $R_i$ loop and, therefore, two pointers are pointing to the 3rd and 15th positions. Vertex $v_h$ is the most interesting. In this vertex three cycles are met. Pointer $P_{i1}$ points to the $7^{\mathit{th}}$ $R_i$ loop position, and $P_{i2}$ points to the $3^{\mathit{rd}}$ position of the first $R_i$ ring. The loop of $R_j$ is accessed by the chain code command stored at position 9 in the $F4$ array.

Figure 11.

Regions $R_i$ (red and black) and $R_j$ (cyan) embedded into $G$, and some characteristic vertices considered in Table 2.

			i:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$R_i$	0	(1, 3)	$F4$:	1	0	3	0	1	0	3	0	3	2	3	2	1	2	1	2
			i:	0	1	2	3
	1	(3, 3)	$F4$:	3	0	1	2
$R_j$			i:	0	1	2	3	4	5	6	7	8	9
	0	(4, 2)	$F4$:	2	2	1	0	0	0	3	3	2	1

Table 1.

Data structures for regions $R_i$ and $R_j$ from Figure 11.

Vertex in Figure 11	$P_{i1}$	$P_{i2}$	${\mathit{LR}}_{i1}$	${\mathit{LR}}_{i2}$	$P_{j1}$	$P_{j2}$	${\mathit{LR}}_{j1}$	${\mathit{LR}}_{j2}$
$v_a$	1	/	0	/	/	/	/	/
$v_b$	2	/	0	/	2	/	0	/
$v_c$	5	/	0	/	1	/	0	/
$v_d$	6	/	0	/	0	/	0	/
$v_e$	/	/	/	/	7	/	/	/
$v_f$	3	15	0	0	/	/	/	/
$v_g$	4	0	0	1	/	/	/	/
$v_h$	7	3	0	1	9	/	0	/
$v_i$	8	/	0	/	8	/	0	/
$v_j$	13	1	0	1	/	/	/	/
(NULL pointers are marked with ’/’)

Table 2.

The content of $G$ at specific vertices marked in Figure 11.

Having marked the vertices in $G$ properly, it is easy to determine the intersection trails. The region with the smallest number of edges is found (let us suppose it is $R_j$), and all its vertices are visited. The sequence of edges marked with pointers of both regions is identified as being a part of the intersection trail.

3.2 Performing the walkabout

Those trails which were not labelled as the intersection ones, are united into the new region by the algorithm, consisting of the following steps:

1. Mark all edges from intersection trails as visited and the remaining edges as not visited.

2. Find an arbitrary non-visited edge $e\in R_j$. If such edge does not exist, jump to step 9.

3. The initial vertex of $e$ is chosen as the starting vertex $v_s$ for the walkabout. An empty queue $Q$ is created.

4. Walk along the edges of $R_j$, mark each passed edge as visited and store passed $F4$ commands into $Q$ until $v_s$ is met, or the vertex with set $R_i$ pointer is reached.

5. If $v_s$ is reached, go to step 8, otherwise switch to the edge of region $R_i$ using the pointer stored at the vertex from $G$.

6. Walk along the edges of $R_i$, mark each passed edge as visited and store passed $F4$ commands into $Q$ until the $v_s$ is met or the vertex with $R_j$ pointer is detected.

7. If $v_s$ is not reached yet, switch to the region $R_j$ using the pointer stored at the considered vertex, and go to step 4, otherwise go to the next step.

8. Store the obtained cycle into the list of cycles $\mathit{LoC}$ and return to step 2.

9. Insert non-visited cycles of input both regions $R_i$ and $R_j$ into $\mathit{LoC}$.

10. Find the loop in $\mathit{LoC}$; all others cycles in $\mathit{LoC}$ represent rings of the merged region $R$.

These steps are highlighted in Algorithm 1. The decision whether the cycle defines a loop or a ring depends on its orientation. It can be determined by Eq. (7), where $Q=⟨{\sigma }_i⟩$ ($F4$ chain code commands ${\sigma }_i$ are treated as integers for this purpose).

$$\begin{array}{l}o=\sum _{i=0}^{\mid Q\mid -1}\left\{\begin{array}{ccc}-1& :& {\sigma }_i=0\wedge {\sigma }_{\left(i+1\right)\mathit{mod}\mid {\mathrm{\Sigma }}_{F4}\mid }=\mid {\mathrm{\Sigma }}_{F4}\mid -1\\ 1& :& {\sigma }_i=\mid {\mathrm{\Sigma }}_{F4}\mid -1\wedge {\sigma }_{\left(i+1\right)\mathit{mod}\mid {\mathrm{\Sigma }}_{F4}\mid }=0\\ {\sigma }_{\left(i+1\right)\mathit{mod}\mid {\mathrm{\Sigma }}_{F4}\mid }-{\sigma }_i& :& \text{otherwise}\hfill \end{array}\right.\end{array}$$E7

The equation evaluates each right turn with $-1$ and each left turn with $1$. The clockwise oriented cycles result in $o=-4$, while the counter-clockwise cycles achieve $o=4$.

Algorithm 1 Merging regions $R_i$ and $R_j$.

 1: function Merge($G$, $R_i$, $R_j$)

 2:          ⊳ function merges regions $R_i$ and $R_j$ embedded in graph $G$

 3:   Insert($G$, $R_i$, $\mathit{\text{NonVisited}}$)  ⊳ insert region into $G$, mark edges as NonVisited

 4:   Insert($G$, $R_j$, $\mathit{\text{NonVisited}}$)

 5:   MarkIntersectionEdges($G,R_i,R_j$) ⊳ intersection edges are marked as Visited

 6:   $e$ = GetNonVisitedEdge($R_j$)

 7:   $\mathit{LoC}=\left\{\right\}$               ⊳ List of Cycles should be empty

 8:   while Visited($R_j,e$) = $\mathit{\text{NonVisited}}$ do

 9:   $\mathit{\text{CycleFound}}$ = false

10:   $Q=\left\{\right\}$          ⊳ clear the queue containing F4 symbols

11:   $Q=$AddF4Symbol($Q$, $R_j,e$)      ⊳ add F4 chain code symbol of $e$

12:   $v_s$ = ReturnVertex($R_j,e$)           ⊳ store the starting vertex

13:   MarkVisitedEdge($R_j,e$)            ⊳ mark edge as visited

14:   $e$ = NextEdge($R_j,e$)     ⊳ move one edge forward along $R_j$ boundary

15:   repeat

16:    while (Visited($R_j,e$) = $\mathit{\text{NonVisited}}$) AND

17:       (ReturnVertex($R_j,e$) $\ne v_s)$ do    ⊳ walk along edges of $R_j$

18:      $Q=$ AddF4Symbol($Q$, $R_j,e$)   ⊳ add F4 chain code symbol of $e$

19:      MarkVisitedEdge($R_j,e$)         ⊳ mark edge as visited

20:      $e$ = NextEdge($R_j,e$) ⊳ move one edge forward along $R_j$ boundary

21:    end while

22:    if ReturnVertex($R_j,e$) = $v_s$ then        ⊳ the cycle is formed

23:      $\mathit{\text{CycleFound}}$ = true

24:    else             ⊳ otherwise continue the walk on $R_i$

25:      $e$ = ReturnEdgeFromOtherRegion($R_j,e$)       ⊳ get $e\in R_i$

26:      while (Visited($R_i,e$) = $\mathit{\text{NonVisited}}$) AND  ⊳ walk along $R_i$ edges

27:         (ReturnVertex($R_i,e$) $\ne v_s)$ do

28:       $Q=$ AddF4Symbol($Q$, $R_i,e$)

29:       MarkVisitedEdge($R_i,e$)

30:       $e$ = NextEdge($R_i,e$)

31:      end while

32:      if ReturnVertex($R_i,e$) = $v_s$ then

33:       $\mathit{\text{CycleFound}}$ = true

34:      else             ⊳ jump to the $R_j$ boundary again

35:       $e$ = ReturnEdgeFromOtherRegion($R_i,e$)      ⊳ get $e\in R_j$

36:      end if

37:    end if

38:   until $\mathit{\text{CycleFound}}$ = true

39:   $\mathit{LoC}$ = StoreCycle($v_s$, $Q$)          ⊳ store constructed cycle

40:   $e$ = GetNonVisitedEdge($R_j$)        ⊳ get next non-visited edge

41:   end while

42:   AddNonVisitedCycles($\mathit{LoC},R_i$)      ⊳ add non-visited cycles (holes)

43:   AddNonVisitedCycles($\mathit{LoC},R_j$)

44:   DetermineLoop($\mathit{LoC}$)   ⊳ among all cycles the loop is found by (Eq. 7)

45:   $R$ = ConstructRegion($\mathit{LoC}$)

46:   return $R$

47: end function.

4. Analysis of the algorithm

4.1 Time and space complexity estimation

The proposed algorithm consists of three parts: finding the intersection trails, performing the walkabout, and determination of loop and rings.

Let the four-connected graph $G$ consist of $n$ vertices. Let $k_i$ and $k_j$ represent the number of $F4$ edges defining cycles of $R_i$ and $R_j$, respectively. $k_i=k_j=k$ may be assumed without loss of generality. At first, both regions are embedded into $G$. This is done in $T_e\left(k\right)=T\left(k_i\right)+T\left(k_j\right)=2k$ time. One of the regions is walked-about and the edges of the intersection trails are determined in time $T_w\left(k\right)=k$. The first part of the algorithm is, therefore, executed in $T_1\left(k\right)=T_e\left(k\right)+T_w\left(k\right)=3k$ time.

During the walkabout, all edges of both regions not being part of the intersection trail, are visited exactly once. In the worst case, all $2k$ edges must be visited in time $T_2\left(k\right)=2k$.

The orientation of the cycles of the merged region is determined in the last step. This task is also terminated in $T_3=2k$ time, as the merged region cannot have more than $2k$ edges.

The proposed merging algorithm is, therefore, realised in $T\left(k\right)=T_1\left(k\right)+T_2\left(k\right)+T_3\left(k\right)=3k+2k+2k=7k=O\left(k\right)$. $k$ cannot be greater than $n$, and therefore, one merging operation is terminated in the worst case in $O\left(n\right)$ time. However, in the majority of cases, $k<<n$. In such, an expected case, one merging operation is terminated in a constant time $O\left(1\right)$.

The algorithm needs memory for $G$ with $n$ vertices, i.e. $S_G\left(n\right)=n$. In addition, two regions need to be stored. In the worst case, both regions require additional $S_R\left(n\right)=n$ memory space. The algorithm, therefore, works in $S\left(n\right)=2n=O\left(n\right)$ space.

4.2 Experiment

The standard benchmark images shown in Figure 12 have been used in the experiment with different resolutions. A criterion for merging two neighbouring regions was the colour similarity. By doubling the size of the image in both directions iteratively, the number of pixels $n$ is increasing by the power of 4, and the number of required merging operations follows this exponential growth; actually, the number of merging operations is $n-1$.

Figure 12.

Images used in the experiments: (a) Lenna, (b) peppers, and (c) baboon.

Table 3 shows spent CPU time while performing merging from single pixels up to the entire image. A personal computer with a 3,5 GH Intel® Core™ i5–6600 K processor and 32 G bytes of RAM was used in the experiment. The program was implemented in C++ and compiled with C++ Visual Studio 2019 under the Windows 10 operating system. As can be seen, the actual CPU time spent depends on the colour characteristics of the images. The image Lenna has large parts of very similar colours and therefore, the regions grow rapidly which is reflected in the shortest CPU spent time. The image Peppers exposes a similar characteristic. On the other hand, the image Baboon consists of very small homogeneous regions, reflecting in longer CPU time spent.

Size (pixels)	$n$	$t_L$ (s)	$t_P\left(s\right)$	Size (pixels)	$n$	$t_B\left(s\right)$
$64\times 64$	4096	0.014	0.017	$63\times 60$	3780	0.018
$128\times 128$	16,384	0.081	0.064	$125\times 120$	15,000	0.169
$256\times 256$	65,536	0.715	0.624	$250\times 240$	60,000	1.682
$512\times 512$	262,144	7.885	11.778	$500\times 480$	240,000	20.454

Table 3.

Spent CPU time for images Lenna (L), peppers (P), and baboon (B) at different resolutions.

We implemented the set-based version of the merging operation for comparison. In this case, the region is represented by the STD structure unordered_map. The obtained results are shown in Table 4. As can be seen, the set-based approach performs considerably slower. In addition, it obviously spends more memory, as images with the highest resolutions cannot be processed any more.

Size (pixels)	$t_L$ (s)	$t_P$ (s)	Size (pixels)	$t_B$ (s)
$64\times 64$	0.683	0.602	$63\times 60$	0.892
$128\times 128$	8.765	8.646	$125\times 120$	13.823
$256\times 256$	219.450	211.762	$250\times 240$	247.323
$512\times 512$	OOMa	OOMa	$500\times 480$	OOMa

Table 4.

Spent CPU time with the referenced approach.

^a

OOM denotes out-of-memory.

5. Conclusion

A new region merging algorithm, suitable for hierarchical object-based image analysis, is proposed in this chapter. The raster space is represented by a 4-connected graph, and a merging function is derived formally upon it. The implementation follows the theoretical investigation strictly. The edges forming the border of the region embedded in the 4-connected graph are represented by the Freeman crack chain code in four directions. The implementation works in two main steps: a determination of the common vertices and edges of the regions being merged, and a walkabout, which realises the theoretically derived merging function. A classification of the obtained region’s edges to those representing the holes and those defining the outer border, may be done at the end.

The algorithm’s worst-case time complexity is $O\left(n\right)$ for one merging operation, where $n$ is the number of graph vertices. However, as the number of edges defining the two regions being merged is much smaller than $n$, the expected time complexity is actually independent on $n$, i.e. the expected time complexity of the proposed algorithm is $O\left(1\right)$.

In addition to the methodical implementation of the region merging procedure, the proposed chain code-based approach enables efficient extraction of various essential shape descriptors [3]. The approaches for extracting these descriptors can be divided roughly into the region- and contour-based approaches, and the latter are known as being computationally demanding for traditional hierarchical segmentation and region growing. Namely, they require the boundary to be extracted after each region merging operation. Because of this, these are rarely used, e.g. as stopping criteria during the region growing, or as thresholds for hierarchical cuts. On the other hand, chain codes by themselves allow for efficient description of shapes.

Acknowledgments

The authors acknowledge the financial support from the Slovenian Research Agency (Research Core Funding No. P2-0041 and Project No. N2-0181), and the Company IGEA, d.o.o., for co-financing this research.

Nomenclature

Thanks

Thanks to Anže Fer$\stackrel{⌣}{\mathrm{c}}$ec, who implemented the referenced merging algorithm.