Open access peer-reviewed chapter - ONLINE FIRST

An Efficient Region Merging Algorithm in Raster Space

Written By

Borut Žalik, David Podgorelec, Niko Lukač, Krista Rizman Žalik and Domen Mongus

Reviewed: January 14th, 2022 Published: March 1st, 2022

DOI: 10.5772/intechopen.102679

IntechOpen
Qualitative and Computational Aspects of Dynamical Systems Edited by Kamal Shah

From the Edited Volume

Qualitative and Computational Aspects of Dynamical Systems [Working Title]

Dr. Kamal Shah, Dr. . Eiman and Dr. Arshad Ali

Chapter metrics overview

37 Chapter Downloads

View Full Metrics

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.

Keywords

  • computer science
  • algorithms
  • 4-connected graph
  • merging function
  • chain code

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], α-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 Onlogntime, where nis 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 Omαmn, where αmnis related with the inverse Ackermann function, while mand ncorrespond 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 On+mlogn+m+I, where nand mare the number of vertices determining the input polygons, and Iis 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.

Advertisement

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=VEdefined by a vertex set V=viand an edge set E=ei,jis a directed graph if Eis given by ordered pairs (directed edges) of vertices ei,j=vivj.

Raster space.Let G=VEbe a directed graph. If Vis determined by regularly spaced vertices vi=xiyiwith integer coordinates xi0Xand yi0Y, and Eimposes 4-connectivity on them, then Gdefines the raster space. In other words, for each pair of adjacent vertices vi,vjlinked by edge ei,jE, there exists either relation ei,jxjyj=xi±1yior ei,jxjyj=xiyi±1. Each vertex can also be linked to itself, thus, viVei,iE.

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 ti0,iL=vi0vi1viLin G with length Lis a sequence of adjacent vertices where for each pair vil,vil+1ti0,iLeil,il+1E. Trails ti0,iLand tj0,jKare connected if they share at least one subtrail, i.e. if a set of subtrails T=ti0,iLtj0,jKØ.

Figure 1 shows two cases of connected trails. Trails t0,6and t7,8are connected through subtrail t4,4=v4v4in Figure 1a, while trails t0,6and t9,7in Figure 1b share two subtrails, namely T=t0,6t9,7=t1,1t3,5, where t1,1=v1v1and t3,5=v3v4v5. The shared subtrails will be hereinafter referred to as the intersection trails.

Figure 1.

Connected trails: (a)t0,6=v0v1v2v3v4v5v6,t7,8=v7v4v8, (b)t0,6=v0v1v2v3v4v5v6,t9,7=v9v1v8v3v4v5v7.

Trail ti0,iLcan be split into two trails ti0,iland til+1,iLat any vilti0,iL. ti0,iLis, therefore, a concatenation of ti0,iland til+1,iLas formally shown in Eq. (1):

ti0,iL=ti0,iltil+1,iL.E1

Cycle.Trail ti0,iL=vi0vi1viL+1is cycle ci0,iL=vi0vi1viL, if i0=iL+1. As each vertex can be linked to itself, the smallest cycle ci0,i0=vi0is defined by trail ti0,i0=vi0vi0. Contrary to the traditional definition of cycle, we do require that all vertices, except the end vertices, are distinct in ci0,iL. 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 v2, v3, and v4are contained twice in the cycle in Figure 2b. Note that any cycle can be rotated by any number of vertices 0<lL, i.e. ci0,iL=vi0vi1viL=vilvil+1viLvi0vi1vil1=cil,il1. Its decomposition can then be described as concatenation from Eq. (2):

Figure 2.

Cycles: (a)c0,7=v0v1v2v3v4v5v6v7, (b)c0,10=v0,v1,v2,v3,v4,v5,v6,v7,v4,v3,v8,v9,v2,v10.

ci0,iL=til,iktik+1,lL1.E2

As shown in Figure 3, any subtrail til,ikci0,iL,0l,kL, can be removed from cycle ci0,iLaccording to Eq.(3). The obtained result is also a subtrail.

Figure 3.

Removing trailtil,ik(on the right) from cycleci0,iLresults in subtrailtik+1,il1(on the left).

tik+1,il1=ci0,iL\til,ik.E3

Let ci0,i3=vi0vi1vi2vi3be an elementary clockwise oriented cycle, where vi0=xiyi,vi1=xiyi+1,vi2=xi+1yi+1, and vi3=xi+1yi. This elementary cycle defines a grid cell, with its interior on the right side of each edge eil,il+1=vilvil+1, 0l3as shown in Figure 4.

Figure 4.

Elementary cycleci0,i3enclosing a grid cell.

Region.The region Ris 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. Rwill be treated as a cycle or a set of cycles.

Figure 5 shows the result of merging two elementary cycles ci0,iLand cj0,jKL=K=3, 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 ci0,iLcj0,jK. Note, however, that ci0,iLand cj0,jKare 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 is defined here, such that ci0,iL=viLviL1vi0. 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 ci0,iLand cj0,jK, which share a single intersection trail til,ikcan be merged into a region Rby a merging function Mdefined by Eq. (4):

Mci0,iLcj0,jKtil,ik=ci0,iL\ci0,iLcj0,jKvilcj0,jK\cj0,jKci0,iLvik==ci0,iL\til,ikvilcj0,jK\tjn,jmvik==tik+1,il1viltjm+1,jn1vik==tik+1,il1vjmtjm+1,jn1vjn.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=til,ikhTiMci0,iLcj0,jK.til,ikh.E5

Eq. (4) is thus applied when Ti=Tj=1, where Ti=tik,il=ci0,iLcj0,jKand Tj=tjm,jn=cj0,jKci0,iL. On the other hand Ti=Tj>1implies utilisation of Eq. (5) and each intersection trail then results in a new cycle. Ticycles are, therefore, constructed, and the resulting region is described by the intersection of these cycles. Note that h, such that 0h<Ti, is an index of the intersection trail in Eq. (5). It is obvious that Eq. (5) is valid also when Ti=1.

Figure 7 shows an illustrative example. The set of intersection trails is Ti=ti5,i6ti8,i9. Applying Eq. (4) on the intersection trail ti5,i6Tiresults in Figure 7b. Similarly, using Eq. (4) on the second intersection trail ti8,i9Tigives 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 Rconsists of two cycles, which are exactly the same as Ti.

Figure 7.

ApplyingEq. (5)to merge two cycles whose intersection consists of two intersection trails, i.e.Ti=2.

Advertisement

3. Implementation

The concept of chain codes is used to represent regions RGin the presented method. The chain code, introduced by Freeman [27], consists of a few simple commands by which navigation through the edges of Gis 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, VCC) [28], Sánchez-Cruz and Rodríguez-Dagnino (Three-Orthogonal chain code, 3OT) [29], Žalik et al. (Unsigned Manhattan Chain Code, 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]. F4is the only chain code which can be used in both contexts, and its crack interpretation is used in this algorithm.

The F4alphabet consists of four commands/symbols σiΣF4, ΣF4=0,1,2,3, shown in Figure 8. Let σibe the sequence of F4commands. To embed the chain code in G, the position of the chain code starting vertex v0is needed, while the positions of the remaining vertices are determined from the F4commands according to Eq. (6):

Figure 8.

F4chain code symbols (a); the elementary cycle described byF4chain code symbols (b).

vi+1=xi+1yi,ifσi=0;xiyi1,ifσi=1;xi1yi,ifσi=2;xiyi+1,ifσi=3.E6

Figure 8b shows the elementary cycle ci0,i3determined as vi01,0,3,2, where vi0=xi0yi0are the coordinates of the cycle’s starting vertex.

Any region in Gcan 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 viRcan be part of two cycles at the same time, or, within each cycle, vican be passed twice, too. In the continuation, the cycle corresponding to the outer border of Ris 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 Ris shown schematically in Figure 10. It consists of an array of starting points and an array of F4chain code sequences. The loop is always located at index 0, and k, k0, rings follow in an arbitrary order. The algorithm, which implements Eq. (5), consists of two main steps:

  • Determining the intersection trails Tibetween cycles of input regions and

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

Figure 10.

Data structure of regionR: Array of starting points (left) of individual cycles and the corresponding sequences ofF4chain 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 On2time complexity, various approaches were suggested to reduce it [13, 34, 35, 36]. The presented solution exploits the fact that regions Riand Rjare embedded into common directed graph G, i.e. RiGRjG. The following data are associated with each vertex viG:

  • two pointers (Pi1and Pi2) into an array of F4symbols for region Ri(one or both pointers can be NULL),

  • two pointers (LRi1and LRi2) pointing to the loop, or to the corresponding ring of region Ri(similarly as above, one or both pointers can be NULL), and

  • the same information for region Rj.

Let us consider the example in Figure 11, where the loop’s edges of Riare plotted in red, the edges of its ring in black, while edges of region Rjare 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 va, for example, belongs to Ri, its Pi1points to the index 1 in the array of F4chain codes, and the vertex belongs to the loop (LRi2=0). Vertex vfis met two times by the edges of the Riloop and, therefore, two pointers are pointing to the 3rd and 15th positions. Vertex vhis the most interesting. In this vertex three cycles are met. Pointer Pi1points to the 7thRiloop position, and Pi2points to the 3rdposition of the first Riring. The loop of Rjis accessed by the chain code command stored at position 9 in the F4array.

Figure 11.

RegionsRi(red and black) andRj(cyan) embedded intoG, and some characteristic vertices considered inTable 2.

i:0123456789101112131415
Ri0(1, 3)F4:1030103032321212
i:0123
1(3, 3)F4:3012
Rji:0123456789
0(4, 2)F4:2210003321

Table 1.

Data structures for regions Riand Rjfrom Figure 11.

Vertex in Figure 11Pi1Pi2LRi1LRi2Pj1Pj2LRj1LRj2
va1/0/////
vb2/0/2/0/
vc5/0/1/0/
vd6/0/0/0/
ve////7///
vf31500////
vg4001////
vh73019/0/
vi8/0/8/0/
vj13101////
(NULL pointers are marked with ’/’)

Table 2.

The content of Gat specific vertices marked in Figure 11.

Having marked the vertices in Gproperly, it is easy to determine the intersection trails. The region with the smallest number of edges is found (let us suppose it is Rj), 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 visitedand the remaining edges as not visited.

  2. Find an arbitrary non-visited edge eRj. If such edge does not exist, jump to step 9.

  3. The initial vertex of eis chosen as the starting vertex vsfor the walkabout. An empty queue Qis created.

  4. Walk along the edges of Rj, mark each passed edge as visitedand store passed F4commands into Quntil vsis met, or the vertex with set Ripointer is reached.

  5. If vsis reached, go to step 8, otherwise switch to the edge of region Riusing the pointer stored at the vertex from G.

  6. Walk along the edges of Ri, mark each passed edge as visitedand store passed F4commands into Quntil the vsis met or the vertex with Rjpointer is detected.

  7. If vsis not reached yet, switch to the region Rjusing 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 LoCand return to step 2.

  9. Insert non-visited cycles of input both regions Riand Rjinto LoC.

  10. Find the loop in LoC; all others cycles in LoCrepresent 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=σi(F4chain code commands σiare treated as integers for this purpose).

o=i=0Q11:σi=0σi+1modΣF4=ΣF411:σi=ΣF41σi+1modΣF4=0σi+1modΣF4σi:otherwiseE7

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

Algorithm 1Merging regions Riand Rj.

 1: functionMerge(G, Ri, Rj)

 2:          ⊳ function merges regions Riand Rjembedded in graph G

 3:   Insert(G, Ri, NonVisited)  ⊳ insert region into G, mark edges as NonVisited

 4:   Insert(G, Rj, NonVisited)

 5:   MarkIntersectionEdges(G,Ri,Rj) ⊳ intersection edges are marked as Visited

 6:   e= GetNonVisitedEdge(Rj)

 7:   LoC=              ⊳ List of Cycles should be empty

 8:   whileVisited(Rj,e) = NonVisiteddo

 9:   CycleFound= false

10:   Q=          ⊳ clear the queue containing F4 symbols

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

12:   vs= ReturnVertex(Rj,e)           ⊳ store the starting vertex

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

14:   e= NextEdge(Rj,e)     ⊳ move one edge forward along Rjboundary

15:   repeat

16:    while(Visited(Rj,e) = NonVisited) AND

17:       (ReturnVertex(Rj,e) vs)do    ⊳ walk along edges of Rj

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

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

20:      e= NextEdge(Rj,e) ⊳ move one edge forward along Rjboundary

21:    end while

22:    ifReturnVertex(Rj,e) = vsthen        ⊳ the cycle is formed

23:      CycleFound= true

24:    else             ⊳ otherwise continue the walk on Ri

25:      e= ReturnEdgeFromOtherRegion(Rj,e)       ⊳ get eRi

26:      while(Visited(Ri,e) = NonVisited) AND  ⊳ walk along Riedges

27:         (ReturnVertex(Ri,e) vs)do

28:       Q=AddF4Symbol(Q, Ri,e)

29:       MarkVisitedEdge(Ri,e)

30:       e= NextEdge(Ri,e)

31:      end while

32:      if ReturnVertex(Ri,e) = vsthen

33:       CycleFound= true

34:      else             ⊳ jump to the Rjboundary again

35:       e= ReturnEdgeFromOtherRegion(Ri,e)      ⊳ get eRj

36:      end if

37:    end if

38:   untilCycleFound= true

39:   LoC= StoreCycle(vs, Q)          ⊳ store constructed cycle

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

41:   end while

42:   AddNonVisitedCycles(LoC,Ri)      ⊳ add non-visited cycles (holes)

43:   AddNonVisitedCycles(LoC,Rj)

44:   DetermineLoop(LoC)   ⊳ among all cycles the loop is found by (Eq. 7)

45:   R= ConstructRegion(LoC)

46:   returnR

47: end function.

Advertisement

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 Gconsist of nvertices. Let kiand kjrepresent the number of F4edges defining cycles of Riand Rj, respectively. ki=kj=kmay be assumed without loss of generality. At first, both regions are embedded into G. This is done in Tek=Tki+Tkj=2ktime. One of the regions is walked-about and the edges of the intersection trails are determined in time Twk=k. The first part of the algorithm is, therefore, executed in T1k=Tek+Twk=3ktime.

During the walkabout, all edges of both regions not being part of the intersection trail, are visited exactly once. In the worst case, all 2kedges must be visited in time T2k=2k.

The orientation of the cycles of the merged region is determined in the last step. This task is also terminated in T3=2ktime, as the merged region cannot have more than 2kedges.

The proposed merging algorithm is, therefore, realised in Tk=T1k+T2k+T3k=3k+2k+2k=7k=Ok. kcannot be greater than n, and therefore, one merging operation is terminated in the worst case in Ontime. However, in the majority of cases, k<<n. In such, an expected case, one merging operation is terminated in a constant time O1.

The algorithm needs memory for Gwith nvertices, i.e. SGn=n. In addition, two regions need to be stored. In the worst case, both regions require additional SRn=nmemory space. The algorithm, therefore, works in Sn=2n=Onspace.

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 nis increasing by the power of 4, and the number of required merging operations follows this exponential growth; actually, the number of merging operations is n1.

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)ntL(s)tPsSize (pixels)ntBs
64×6440960.0140.01763×6037800.018
128×12816,3840.0810.064125×12015,0000.169
256×25665,5360.7150.624250×24060,0001.682
512×512262,1447.88511.778500×480240,00020.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)tL(s)tP(s)Size (pixels)tB(s)
64×640.6830.60263×600.892
128×1288.7658.646125×12013.823
256×256219.450211.762250×240247.323
512×512OOMaOOMa500×480OOMa

Table 4.

Spent CPU time with the referenced approach.

OOM denotes out-of-memory.


Advertisement

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 Onfor one merging operation, where nis 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 O1.

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.

Advertisement

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.

Advertisement

Thanks

Thanks to Anže Fercec, who implemented the referenced merging algorithm.

Advertisement

Nomenclature

c

cycle

CPU

central processing unit

e

edge

E

set of edges

F4

Freeman chain code in four directions

G

directed graph

L

the number of vertices in a trail or in a cycle

LR

pointer to the loop/ring of the region

LoC

list of cycles

M

merging function

OBIA

Object-Based Image Analysis

P

pointer to the region

Q

queue

R

region

ΣF4

alphabet of Freeman’s chain code in four directions

σ

F4symbol

t

trail

T

set of trails

v

vertex

V

set of vertices

References

  1. 1. Guimarães SJF, Cousty J, Kenmochi Y, Najman L. A Hierarchical Image segmentation algorithm based on an observation scale. In: Gimel’farb G, Hancock E, Imiya A, Kuijper A, Kudo M, Omachi S, Windeatt T, Yamada K, editors. Structural, Syntactic, and Statistical Pattern Recognition. Lecture Notes in Computer Science;7626. Berlin, Heidelberg: Springer; 2012. pp. 116-125. DOI: 10.1007/978-3-642-34166-3_13
  2. 2. Materka A, Strzelecki M. Texture analysis methods – a review. Lodz, Poland: COST B11 report, Institute of Electronics, Technical University of Lodz; 1998. Available from:https://www.researchgate.net/publication/249723259_Texture_Analysis_Methods_-_A_Review[Accessed: 2021-12-22]
  3. 3. Zhang D, Lu G. Review of shape representation and description techniques. Pattern Recognition. 2004;37(1):1-19. DOI: 10.1016/j.patcog.2003.07.008
  4. 4. Kurnianggoro L, Jo KH. A survey of 2D shape representation: Methods, evaluations, and future research directions. Neurocomputing. 2018;300:1-16. DOI: 10.1016/j.neucom.2018.02.093
  5. 5. Xu Y, Carlinet E, Géraud T, Najman L. Efficient computation of attributes and saliency maps on tree-based image representations. In: Benediktsson J, Chanussot J, Najman L, Talbot H, editors. Mathematical Morphology and Its Applications to Signal and Image Processing. Lecture Notes in Computer Science; 9082. Berlin, Heidelberg: Springer; 2015. pp. 693-704. DOI: 10.1007/978-3-319-18720-4_58
  6. 6. Salembier P, Oliveras A, Garrido L. Antiextensive connected operators for image and sequence processing. IEEE Transactions on Image Processing. 1998;7(4):555-570. DOI: 10.1109/83.663500
  7. 7. Ouzounis GK, Soille P. Pattern spectra from partition pyramids and hierarchies. In: Soille P, Pesaresi M, Ouzounis GK, editors. Mathematical Morphology and Its Applications to Image and Signal Processing. Berlin, Heidelberg: Lecture Notes in Computer Science; 6671, Springer; 2011. pp. 108-119. DOI: 10.1007/978-3-642-21569-8_10
  8. 8. Ouzounis GK, Soille P. The alpha-tree algorithm: Theory, algorithms and applications. Luxembourg: Technical reports JCR74511, European Commission, Joint Research Centre; 2012. DOI: 10.2788/48773
  9. 9. Najman L, Cousty J, Perret B. Playing with Kruskal: Algorithms for morphological trees in edge-weighted graphs. In: Hendriks CLL, Borgefors G, Strand R, editors. Mathematical Morphology and Its Applications to Signal and Image Processing. Lecture Notes in Computer Science; 7883. Berlin, Heidelberg: Springer; 2013. pp. 135-146. DOI: 10.1007/978-3-642-38294-9_12
  10. 10. Hopcroft JE, Ullman JD. Set merging algorithms. SIAM Journal of Computing. 1973;2(4):294-303. DOI: 10.1137/0202024
  11. 11. Tarjan RE. Efficiency of a good but non-linear set union algorithm. Journal of ACM. 1975;22(2):215-225. DOI: 10.1145/321879.321884
  12. 12. Tarjan RE, Leeuwen J. Worst-case analysis of set union algorithms. Journal of ACM. 1984;31(2):245-281. DOI: 10.1145/62.2160
  13. 13. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. 3rd ed. Cambridge, London: MIT; 2009. p. 1292
  14. 14. Horowitz SL, Pavlidis T. Picture segmentation by a tree traversal algorithm. Journal od ACM. 1976;23(2):368-388. DOI: 10.1145/321941.321956
  15. 15. Brun L, Domenger JP. A new split and merge algorithm with topological maps. In: Proceedings of the 5th International Conference in Central Europe on Computer Graphics and Visualization (WSCG’97), 10–14 February 1996, Plzen, Czech Republic: University of West Bohemia. p. 21–31. Available from:https://www.researchgate.net/publication/2658919_A_New_Split_and_Merge_Algorithm_with_Topological_Maps[Accessed: 2021-12-22]
  16. 16. Khalimsky E, Kopperman R, Meyer PR. Boundaries in digital planes. Journal of Applied Mathematics and Stochastic Analysis. 1990;3(1):27-55. DOI: 10.1155/S1048953390000041
  17. 17. Hoffmann CM. Geometric and solid modeling: An introduction. San Francisco: Morgan Kaufmann; 1989. 338 p. Available from:https://dl.acm.org/doi/book/10.5555/74803[Accessed: 2021-12-23]
  18. 18. Mäntylä M. An introduction to solid modeling. New York: Computer Science Press; 1987. 401 p. Available from:https://dl.acm.org/doi/book/10.5555/39278[Accessed: 2021-12-23]
  19. 19. Mortenson ME. Geometric Modeling. 2nd ed. New York: Wiley; 1997. 523 p. Available from:https://dl.acm.org/doi/book/10.5555/248381[Accessed: 2021-12-23]
  20. 20. Mairson HG, Stolfi J. Reporting and counting intersections between two sets of line segments. In: Earnshaw R, editor. Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series; F40. Berlin, Heidelberg: Springer; 1988. pp. 307-325. DOI: 10.1007/978-3-642-83539-1_11
  21. 21. Greiner G, Hormann K. Efficient clipping of arbitrary polygons. ACM Transaction on Graphics. 1998;17(2):71-83. DOI: 10.1145/274363.274364
  22. 22. Vatti BR. A generic solution to polygon clipping. Communications of ACM. 1992;35(7):56-63. DOI: 10.1145/129902.129906
  23. 23. Liu YK, Wang XQ, Bao SZ, Gomboši M, Žalik B. An algorithm for polygon clipping, and for determining polygon intersections and unions. Computers & Geosciences. 2007;33(5):589-598. DOI: 10.1016/j.cageo.2006.08.008
  24. 24. Rivero M, Feito FR. Boolean operations on general planar polygons. Computers & Graphics. 2000;24(6):881-896. DOI: 10.1016/S0097-8493(00)00090
  25. 25. Peng Y, Yong JH, Dong WM, Zhang H, Sun JG. A new algorithm for Boolean operations on general polygons. Computers & Graphics. 2005;29(1):57-70. DOI: 10.1016/j.cag.2004.11.001
  26. 26. Žalik B, Mongus D, Rizman Žalik K, LukacN. Boolean operations on rasterized shapes represented by chain codes using space filling curves. Journal of Visual Communication and Image Representation 2017;49:420–432. DOI: 10.1016/j.jvcir.2017.10.003
  27. 27. Freeman H. On the encoding of arbitrary geometric configurations. IRE Transactions on Electronic Computers. 1961;EC10(2):260-268. DOI: 10.1109/TEC.1961.5219197
  28. 28. Bribiesca E. A new chain code. Pattern Recognition. 1999;32(2):235-251. DOI: 10.1016/S0031-3203(98)00132-0
  29. 29. Sánchez-Cruz H, Rodríguez-Dagnino RM. Compressing bi-level images by means of a 3-bit chain code. Optical Engineering. 2005;44(9):097004. DOI: 10.1117/1.2052793
  30. 30. Žalik B, Mongus D, Liu YK, LukacN. Unsigned Manhattan chain code. Journal of Visual Communication and Image Representation 2016;38:186–194. DOI: 10.1016/j.jvcir.2016.03.001
  31. 31. Dunkelberger KA, Mitchell OR. Contour tracing for precision measurements. St. Luis, USA: IEEE International conference on robotics and automation (ICRA); 25–28 March 1985. pp. 22-27. DOI: 10.1109/ROBOT.1985.1087356
  32. 32. Wilson GR. Properties of contour codes. IEE Proceedins – Vision, Image and Signal Processing. 1997;144(3):145-149. DOI: 10.1049/ip-vis:19971159
  33. 33. Kabir S. A compressed representation of Mid-Crack code with Huffman code. International Journal on Image, Graphics and Signal Processing. 2015;7(10):11-18. DOI: 10.5815/ijigsp.2015.10.02
  34. 34. de Berg M, Cheong O, van Kreveld M, Overmars M. Computational geometry: Algorithms and applications. 3rd ed. Berlin Heidelberg: Springer; 2008. p. 386. DOI: 10.1007/978-3-540-77974-2
  35. 35. Chazelle B, Edelsbrunner H. An optimal algorithm for intersection line segments in the plane. Journal of ACM. 1992;39(1):1-54. DOI: 10.1145/147508.147511
  36. 36. Žalik B. Two efficient algorithms for determining intersection points between simple polygons. Computers & Geosciences. 2000;26(2):137-151. DOI: 10.1016/S0098-3004(99)00071-0

Written By

Borut Žalik, David Podgorelec, Niko Lukač, Krista Rizman Žalik and Domen Mongus

Reviewed: January 14th, 2022 Published: March 1st, 2022