# Automatic Representation and Segmentation of Video Sequences via a Novel Framework Based on thenD-EVM and Kohonen Networks

Authors: José-Yovany Luis-García; Ricardo Pérez-Aguila
Journal: Advances in Artificial Intelligence
 (2016)

---

## Abstract

Recently in the Computer Vision field, a subject of interest, at least in almost every video application based on scene content, is video segmentation. Some of these applications are indexing, surveillance, medical imaging, event analysis, and computer-guided surgery, for naming some of them. To achieve their goals, these applications need meaningful information about a video sequence, in order to understand the events in its corresponding scene. Therefore, we need semantic information which can be obtained from objects of interest that are present in the scene. In order to recognize objects we need to compute features which aid the finding of similarities and dissimilarities, among other characteristics. For this reason, one of the most important tasks for video and image processing is segmentation. The segmentation process consists in separating data into groups that share similar features. Based on this, in this work we propose a novel framework for video representation and segmentation. The main workflow of this framework is given by the processing of an input frame sequence in order to obtain, as output, a segmented version. For video representation we use the Extreme Vertices Model in then-Dimensional Space while we use the Discrete Compactness descriptor as feature and Kohonen Self-Organizing Maps for segmentation purposes.


---

## Body

## 1. Introduction

Video segmentation is an open problem in the Computer Vision and Pattern Recognition fields. In recent years, this problem is of high interest because of the applications that can be derived from it [1, 2], for example, video indexing in databases, video summary, surveillance, medical imaging, event analysis, and computer surgery. The applications based on video content usually analyze the scene of the sequence and they require semantic information about the events that are taking place in it. The events’ information is obtained from the objects that are relevant to the scene.Applications for video content analysis require that the object information is provided in a suitable manner. For example, a very common approach is to compute features for describing objects, such that it is possible to distinguish them among others. For this reason, one of the most important tasks involved in object extraction is the process of segmentation, because the information that will be computed from the objects depends largely on the quality of this task.Some the most common video applications that include a segmentation stage are the following:(i)
Action recognition: the objective is to determine the actions taking place in the scene, for example, if the people are walking, running, or jumping. Some related works for this applications are [3, 4].(ii)
Object recognition: it aims to object detection, where the main tasks involve feature extraction and measuring similarities with respect to an ideal model. So, the performance of these systems depends largely on the segmentation stage [5, 6].(iii)
Surveillance and traffic control: it is performed by dividing the scene in a background and the significant elements. Therefore, it is executed as object tracking and by this way it is possible to detect movement [7–9].(iv)
Video indexing: where the approach is to describe the scene content in form of text [10, 11]. By this way, it is possible to process a search query based on the content of the video. A survey of the state of the art for these applications is presented in [12]. One approach was implemented in [13], where a video can be indexed based on its Discrete Compactness.(v)
Background compression: the objects of interest, or at least the most prominent ones, are coded with more information than the background [14]. For example, when having a video-call we want to see more details about the person we are talking to, rather than the background [15]. A complete reference for video compression, under the well-known coding standards H.264 and MPEG-4, can be found in [16].(vi)
3D object reconstruction: these applications aim to reconstruct 3D objects from 2D frames which were captured from different angles [17]. These applications are commonly applied in order to generate a 3D view of an urban area [18, 19], as well as for obtaining 3D models of human body parts or faces [20].(vii)
Digital entertainment: such as changing the background of a scene, where the main characters are placed in a virtual location [21].Video and image segmentation can be defined as the process that forms groups of information that share same features [22–24]. A formal definition for image segmentation was given by Fu and Mui [22] by considering an image R that can be divided in Ri,i=1,2,…,m, disjoint nonempty regions. These regions should satisfy the following conditions:(i)
The union of all the regionsRi results in the original image.(ii)
The intersection of any two regions is the empty set.(iii)
The elements in a region share similar properties while elements in different regions have different properties.These conditions can be easily extended to video segmentation, taking into account that a 2D image can be represented as a functionf(x1,x2), such that we would have, for example, an additional third dimension. So, we can express an image that changes in time as a function f(x1,x2,t) which represents the color changes of a pixel in position (x1,x2) and along the temporal dimension t.The segmentation process is a key stage for a framework for image or video processing, such as the one shown in Figure1. As described in [23, 25, 26], the segmentation stage is very important for the subsequent stages because the computation of descriptors for the segmented objects varies for different segmentation results, and therefore this will impact the recognition results.Figure 1
A general video or image processing framework.


### 1.1. A New Approach to the Problem of Video Segmentation

In the literature there have been proposed several approaches for video segmentation based on unsupervised methods. For example, in [27] theMultiple Hypothesis Video Segmentation (MHVS) method is defined. It generates hypothesis for grouping and labeling a set of corresponding pixels in consecutive frames. In this way, asuperpixel is defined which is a collection of pixels in a contiguous region. An extension of this approach is given in [28], where the motion is considered for superpixels’ formation. Another important work in this line of research is presented in [29]. This work proposes the use ofMust-Link Constraints to reduce the amount of superpixels by a merging-like technique, consequently reducing the use of computing resources and improving the segmentation performance.This work boards the problem of video segmentation with a new approach. We propose using the Extreme Vertices Model in then-Dimensional Space (nD-EVM) for video sequences’ representation. Moreover, it is considered the clustering approach using theKohonen Self-Organizing Maps (SOM) as a segmentation method which in turn makes use of theDiscrete Compactness (DC) descriptor as a feature.ThenD-EVM model has been used for efficient representation of n-Dimensional Orthogonal Pseudo Polytopes (nD-OPPs) [30, 31]. One of the main advantages of this model is that it allows representing an nD-OPP using only a subset of its vertices: theextreme vertices.In the context of a 2D image, a frame can be represented through a higher dimensional polytope. We have a 2D base which is defined by the width and length of the image, and additional dimensions are required depending on the considered color scheme. Some well-known color schemes are grayscale, RGB, and RGBA, to mention a few ones. Now, we take a step further: we start from the idea that the information in a video sequence can be seen as annD-OPP since we have two geometrical dimensions for width and length of the frames, one temporal dimension, and a number of additional dimensions depending on the considered color scheme [26, 32]. In [32] the foundations of color video representation are presented in the nD-EVM model, where a color frame can be seen as a 3D-OPP and therefore it can be represented in a 3D-EVM. A drawback of this approach is because the RGB scheme is considered as only one dimension: the RGB24 scheme is a 24-bit color representation which in turn is extruded in only one dimension as an integer. This means that small variations in higher order bits produce large variations in the whole integer value. On the other hand, in [26], the same idea for representing a video sequence is taken, but instead of taking only one-third dimension for RGB frames, the color is split in three dimensions so that a color frame is represented through a 5D-EVM: a 2D base and three dimensions for the RGB scheme, one for each color component. Therefore, in order to represent a video sequence this can be done through a 6D-EVM. This approach is more reliable in the sense that we capture more information about the color of a single frame pixel, and its corresponding extrusion has geometrical and topological characteristics that allows us to distinguish it among others in a more efficient manner. Furthermore, using shape descriptors as features, such as DC, we can perform useful classification tasks.The DC descriptor is a shape descriptor that can be applied to annD-OPP expressed in the nD-EVM model. In this work we use DC to describe a small region inside the 6D-EVM of an animation. This region is a sixth dimensionalmask. Generally, a mask (sometimes calledtemplate) is used in image processing for querying or modifying the information in a certain area [33, 34]. In our context, for video sequences represented through the EVM model, a mask is only applied for obtaining a subanimation. The lengths of the mask in every axis of the 6D space are arbitrarily established. For example, we can take a small region in the 2D space, let us say a 5 × 5 square. But we can also establish the time length of the mask, 5 frames, for example. This can be seen as retrieving the changes in a specific time range of a certain region of the video sequence.With the above reasoning, we can obtain all the possible subanimations from a video sequence and compute the DC descriptor to characterize them. This process is similar to a convolution in the image processing field. These DC values form a training set, which will be used for the training process of the SOM. Once the SOM has been trained, we segment the video sequence intom classes, where m is the number of neurons or clusters that we want to obtain. Considering the clustering process only labels the cluster’s content with the cluster number, the subanimations in a cluster only have information of position in the 2D space and position in the temporal axis. Therefore, for a cluster, we generate a 3D-EVM which only contains the union of all the subanimations associated with it.


## 1.1. A New Approach to the Problem of Video Segmentation

In the literature there have been proposed several approaches for video segmentation based on unsupervised methods. For example, in [27] theMultiple Hypothesis Video Segmentation (MHVS) method is defined. It generates hypothesis for grouping and labeling a set of corresponding pixels in consecutive frames. In this way, asuperpixel is defined which is a collection of pixels in a contiguous region. An extension of this approach is given in [28], where the motion is considered for superpixels’ formation. Another important work in this line of research is presented in [29]. This work proposes the use ofMust-Link Constraints to reduce the amount of superpixels by a merging-like technique, consequently reducing the use of computing resources and improving the segmentation performance.This work boards the problem of video segmentation with a new approach. We propose using the Extreme Vertices Model in then-Dimensional Space (nD-EVM) for video sequences’ representation. Moreover, it is considered the clustering approach using theKohonen Self-Organizing Maps (SOM) as a segmentation method which in turn makes use of theDiscrete Compactness (DC) descriptor as a feature.ThenD-EVM model has been used for efficient representation of n-Dimensional Orthogonal Pseudo Polytopes (nD-OPPs) [30, 31]. One of the main advantages of this model is that it allows representing an nD-OPP using only a subset of its vertices: theextreme vertices.In the context of a 2D image, a frame can be represented through a higher dimensional polytope. We have a 2D base which is defined by the width and length of the image, and additional dimensions are required depending on the considered color scheme. Some well-known color schemes are grayscale, RGB, and RGBA, to mention a few ones. Now, we take a step further: we start from the idea that the information in a video sequence can be seen as annD-OPP since we have two geometrical dimensions for width and length of the frames, one temporal dimension, and a number of additional dimensions depending on the considered color scheme [26, 32]. In [32] the foundations of color video representation are presented in the nD-EVM model, where a color frame can be seen as a 3D-OPP and therefore it can be represented in a 3D-EVM. A drawback of this approach is because the RGB scheme is considered as only one dimension: the RGB24 scheme is a 24-bit color representation which in turn is extruded in only one dimension as an integer. This means that small variations in higher order bits produce large variations in the whole integer value. On the other hand, in [26], the same idea for representing a video sequence is taken, but instead of taking only one-third dimension for RGB frames, the color is split in three dimensions so that a color frame is represented through a 5D-EVM: a 2D base and three dimensions for the RGB scheme, one for each color component. Therefore, in order to represent a video sequence this can be done through a 6D-EVM. This approach is more reliable in the sense that we capture more information about the color of a single frame pixel, and its corresponding extrusion has geometrical and topological characteristics that allows us to distinguish it among others in a more efficient manner. Furthermore, using shape descriptors as features, such as DC, we can perform useful classification tasks.The DC descriptor is a shape descriptor that can be applied to annD-OPP expressed in the nD-EVM model. In this work we use DC to describe a small region inside the 6D-EVM of an animation. This region is a sixth dimensionalmask. Generally, a mask (sometimes calledtemplate) is used in image processing for querying or modifying the information in a certain area [33, 34]. In our context, for video sequences represented through the EVM model, a mask is only applied for obtaining a subanimation. The lengths of the mask in every axis of the 6D space are arbitrarily established. For example, we can take a small region in the 2D space, let us say a 5 × 5 square. But we can also establish the time length of the mask, 5 frames, for example. This can be seen as retrieving the changes in a specific time range of a certain region of the video sequence.With the above reasoning, we can obtain all the possible subanimations from a video sequence and compute the DC descriptor to characterize them. This process is similar to a convolution in the image processing field. These DC values form a training set, which will be used for the training process of the SOM. Once the SOM has been trained, we segment the video sequence intom classes, where m is the number of neurons or clusters that we want to obtain. Considering the clustering process only labels the cluster’s content with the cluster number, the subanimations in a cluster only have information of position in the 2D space and position in the temporal axis. Therefore, for a cluster, we generate a 3D-EVM which only contains the union of all the subanimations associated with it.


## 2. Self-Organizing Maps Foundations

As abovementioned, the segmentation process consists in a clustering process.Clustering is an unsupervised learning approach for categorizing a set of patterns. In this case, the labels (classes) of the patterns are not available, so the objective is to reveal the organization of them into clusters of similar patterns [35]. The clusters provide a structure to determine similarities and differences among the patterns. By this way it is possible to derive conclusions from such organization.As usual, the patterns are represented in terms of features. Therefore, there are some basic steps to follow in order to properly perform dataset clustering [35]:(i)
Feature selection: features play an important role because they must be properly selected for providing as much information as possible with respect to the pattern.(ii)
Proximity measure: they quantify the similarity or dissimilarity between two patterns.(iii)
Clustering criterion: it is a function of the proximity measure and it must be sensitive to the nature of the patterns. An expert on the field provides clues on the type of clusters expected.(iv)
Clustering algorithms: they are the algorithmic approaches for the clustering problem.(v)
Validation of results: This step allows validating the correctness of the clusters.(vi)
Interpretation: in this step conclusions are derived from the clustering results. Generally this step is performed by the expert in the application field.In this work the training dataset is formed by DC descriptors as features and the proximity measure is the Euclidean distance between two patterns. TheSelf-Organizing Map (SOM) is the selected algorithmic approach, specifically theKohonen model where the clustering criterion is based on competitive learning [36–38]. The neurons in the SOM compete to be activated and updated for every input pattern; therefore the neurons are tuned to different regions in the feature space. This way a meaningful structure representation is formed, where the spatial locations of the neurons represent intrinsic features of the input patterns, hence the name of map.There are three main stages for a SOM to be considered: competition, cooperation, and synaptic adaptation. Considering a generic case, these stages are described in the following subsections.


### 2.1. Competition Stage

Let us consider the case of a featurenD Euclidean space; then feature vectors are denoted as(1)X=x1x2⋯xnT.On the other hand, let us consider a total ofm neurons; in consequence the synaptic weight vectors are denoted as follows:(2)Wj=wj,1wj,2⋯wj,nTj=1,2,…,m.For a given input patternX, in order to find thewinning neuron the proximity measure between the feature vector and the synaptic weight of each neuron is computed. As mentioned before, the Euclidean distance is our proximity measure. Since the Euclidean distance is also a dissimilarity measure, in order to find the winning neuron we want to minimize the distance between X and Wj,j=1,2,…,m:(3)iX=argminjX-Wj.The winning neuron is the one that minimizes the Euclidean distance. This means that the weight updates will be centered on that neuron.


### 2.2. Cooperation Stage

Given a winning neuron, in this stage a neighborhood is defined having this neuron as its center. In simpler terms, nearby neurons process similar patterns and distant neurons process totally different patterns. This scheme was taken from the neurobiological nature of the human brain to process sensory information, this in the basis of many research works [39, 40].A neighborhood relationship is stronger in the closest neurons, and it decreases as the synaptic weight distance increases. For a given input pattern, when a weight update is performed in the winning neuron there are also weight updates in the neighbor neurons. But the weights of neighbor neurons are updated in function of the neighborhood distance. This means the weights of closest neurons are more affected than the farthest ones. This behavior is achieved with aGaussian function, and it has its maximum for a zero radius, which corresponds to the coordinates of the winning neuron, and it decreases as the distance of neighbor neurons increases.Since the SOM’s neurons are becoming more specialized on each dataset presentation, it is desired that the width of the neighborhood reduces when the number of presentations increases. Therefore, at the final presentations we will have a radius close to zero. The neighborhood function is then denoted as follows:(4)hj,iX,dj,i,t=exp-dj,i22σt2,where i(X) is the winning neuron for the current input pattern X, j is the neuron that we want to compute the neighborhood, dj,i is the Euclidean distance between neuron j and the winning neuron i, t is the current iteration of the dataset presentation, and finally σ(t) is the effective distance that indicates the degree in which the neighbor neurons are activated.


### 2.3. Adaptation Stage

This stage consists of synaptic weight updates. Given an input patternX, the weights are updated as follows:(5)Wjt+1=Wjt+α·hj,iX,dj,i,t·X-Wj,where Wj(t+1) is the new and updated weight and Wj(t) is the current weight of neuron j. As can be noted, the updates are a function of the winning neuron i, as previously mentioned. Another parameter is introduced: thelearning rateα. It is a function of the current iteration of the dataset presentation.


### 2.4. Summary of the Training Algorithm

With the previously described stages the basic training algorithm is defined for the formation of the SOM. Summarizing, this algorithm consists of the following steps:(1)
Initialization: all synaptic weights are initialized with a random number.(2)
Iterations: the training dataset is presented to the SOM network for weight adjustments:
(a)
for each patternX in the dataset, there exist
(i)
winning neuron: it is identified as the winning neuron, whose weight vector minimizes the Euclidean distance to the input pattern, as stated in (3),(ii)
weight updates: the weight updates are performed for the winning neuron and the neurons in the neighborhood. This is performed according to (5).


## 2.1. Competition Stage

Let us consider the case of a featurenD Euclidean space; then feature vectors are denoted as(1)X=x1x2⋯xnT.On the other hand, let us consider a total ofm neurons; in consequence the synaptic weight vectors are denoted as follows:(2)Wj=wj,1wj,2⋯wj,nTj=1,2,…,m.For a given input patternX, in order to find thewinning neuron the proximity measure between the feature vector and the synaptic weight of each neuron is computed. As mentioned before, the Euclidean distance is our proximity measure. Since the Euclidean distance is also a dissimilarity measure, in order to find the winning neuron we want to minimize the distance between X and Wj,j=1,2,…,m:(3)iX=argminjX-Wj.The winning neuron is the one that minimizes the Euclidean distance. This means that the weight updates will be centered on that neuron.


## 2.2. Cooperation Stage

Given a winning neuron, in this stage a neighborhood is defined having this neuron as its center. In simpler terms, nearby neurons process similar patterns and distant neurons process totally different patterns. This scheme was taken from the neurobiological nature of the human brain to process sensory information, this in the basis of many research works [39, 40].A neighborhood relationship is stronger in the closest neurons, and it decreases as the synaptic weight distance increases. For a given input pattern, when a weight update is performed in the winning neuron there are also weight updates in the neighbor neurons. But the weights of neighbor neurons are updated in function of the neighborhood distance. This means the weights of closest neurons are more affected than the farthest ones. This behavior is achieved with aGaussian function, and it has its maximum for a zero radius, which corresponds to the coordinates of the winning neuron, and it decreases as the distance of neighbor neurons increases.Since the SOM’s neurons are becoming more specialized on each dataset presentation, it is desired that the width of the neighborhood reduces when the number of presentations increases. Therefore, at the final presentations we will have a radius close to zero. The neighborhood function is then denoted as follows:(4)hj,iX,dj,i,t=exp-dj,i22σt2,where i(X) is the winning neuron for the current input pattern X, j is the neuron that we want to compute the neighborhood, dj,i is the Euclidean distance between neuron j and the winning neuron i, t is the current iteration of the dataset presentation, and finally σ(t) is the effective distance that indicates the degree in which the neighbor neurons are activated.


## 2.3. Adaptation Stage

This stage consists of synaptic weight updates. Given an input patternX, the weights are updated as follows:(5)Wjt+1=Wjt+α·hj,iX,dj,i,t·X-Wj,where Wj(t+1) is the new and updated weight and Wj(t) is the current weight of neuron j. As can be noted, the updates are a function of the winning neuron i, as previously mentioned. Another parameter is introduced: thelearning rateα. It is a function of the current iteration of the dataset presentation.


## 2.4. Summary of the Training Algorithm

With the previously described stages the basic training algorithm is defined for the formation of the SOM. Summarizing, this algorithm consists of the following steps:(1)
Initialization: all synaptic weights are initialized with a random number.(2)
Iterations: the training dataset is presented to the SOM network for weight adjustments:
(a)
for each patternX in the dataset, there exist
(i)
winning neuron: it is identified as the winning neuron, whose weight vector minimizes the Euclidean distance to the input pattern, as stated in (3),(ii)
weight updates: the weight updates are performed for the winning neuron and the neurons in the neighborhood. This is performed according to (5).


## 3. The Extreme Vertices Model in then-Dimensional Space (nD-EVM)

ThenD-EVM model is a scheme for representing n-Dimensional Orthogonal Pseudo Polytopes (nD-OPPs). The theoretical foundations of the nD-EVM were originally established in [30, 31]. Some research work related to this model considers representation and visualization of video sequences [32], modeling of 3D and 4D datasets [41, 42], and Discrete Compactness computation [13]. In order to understand the nD-EVM, we enunciate some fundamental propositions but for the sake of brevity their corresponding formal proofs are presented in the abovementioned references.


### 3.1.nD-OPPs Fundamentals

Definition 1 (see [43]).
A singularn-Dimensional hyperbox in Rn is given by the continuous function:(6)In:0,1n⟶0,1n,x~Inx=x.Definition 2 (see [43]).
A general singulark-Dimensional hyperbox in the closed set A⊂Rn is the continuous function c:0,1k→A.In the above definitions, the functionIn defines a unit hyperbox 0,1n in the nD Euclidean space. More specifically, and as an example, in the 2D case it defines a unit square, while in the 3D space this function defines a unit cube.Definition 3 (see [43]).
For alli=1,2,…,n, the two singular (n-1)D hyperboxes Ii,0n and Ii,1n are defined as follows: if x∈0,1n-1, then(7)Ii,0nx=Inx1,…,xi-1,0,xi,…,xn-1=x1,…,xi-1,0,xi,…,xn-1,Ii,1nx=Inx1,…,xi-1,1,xi,…,xn-1=x1,…,xi-1,1,xi,…,xn-1.Definition 4 (see [43]).
In a general singularnD hyperbox c one defines the (i,α) cell as c(i,α)=c∘Ii,αn.Definition 5 (see [43]).
The orientation of a(n-1)D cell c∘Ii,αn is given by (-1)i+α.Definition 6 (see [43]).
A(n-1)D oriented cell is given by the scalar-function product (-1)i+α·c∘Ii,αn.Definition 7 (see [43]).
A formal linear combination of singular generalkD hyperboxes, 1≤k≤n, for a closed set A is called a k-chain.Definition 8 (see [43]).
Given a singular generalnD hyperbox c we define the (n-1) chain, called the boundary of c, by(8)∂c=∑i=1n∑α=0,1-1i+α·c∘Ii,αn.Definition 9 (see [43]).
The boundary of ann-chain ∑ci, where each ci is a singular general nD hyperbox, is given by(9)∂∑ci=∑∂ci.The above definitions share with us the basis for handling collections of hyperboxes in thenD space. By this way, when the boundary of a collection of hyperboxes is computed, shared cells between hyperboxes are automatically deleted because of their sign’s orientation.Definition 10.
Ann-Dimensional Orthogonal Pseudo Polytope, or just an nD-OPP, is a n-chain composed by nD hyperboxes arranged in such way that, by selecting a vertex in any of these hyperboxes, it describes a combination of nD hyperboxes composed up to 2n hyperboxes.


### 3.2.nD-EVM Fundamentals

Definition 11.
Letc be a combination of hyperboxes in the nD space. An Odd Adjacency Edge of c, or just an Odd Edge, is an edge with an odd number of incident hyperboxes of c. Conversely, if an edge has an even number of incident hyperboxes of c, then it is called an Even Adjacency Edge, or just an Even Edge.Definition 12.
A Brink or Extended Edge is the maximal uninterrupted segment built out of a sequence of collinear and contiguous odd edges of annD-OPP.Considering that a brink is formed bym odd edges, m≥1, it contains m+1 vertices: two of them are extreme vertices and the remaining m-1 are interior vertices. We will see that the interior vertices are not considered in the EVM model which is going to be defined.Definition 13.
The ending vertices of all the brinks in annD-OPP p will be called the extreme vertices of p. EV(p) will denote the set of extreme vertices of p.Definition 14.
Letp be an nD-OPP. One defines the Extreme Vertices Model of p, denoted by EVMn(p), as the model that only stores all the extreme vertices of p.Theorem 15.
A vertex of annD-OPP p, n≥1, when it is locally described by a set of surrounding nD hyperboxes, is an extreme vertex if and only if it is surrounded by an odd number of such nD hyperboxes.Theorem 16.
Any extreme vertex of annD-OPP, n≥1, when it is locally described by a set of surrounding nD hyperboxes, has exactly n incident linearly independent odd edges.Let us take the example from Figure2. A 3D-OPP and its extreme vertices are presented. As can be observed, the continuous lines represent odd edges; on the other hand, the dotted line represents an Even Edge. Black dots are extreme vertices and white dots are internal vertices. In this case we can see that at the end of every brink an extreme vertex is found. On the other hand, vertices v1, v2, and v3 are nonextreme vertices. The remaining vertices satisfy the conditions established by Theorems 15 and 16: only extreme vertices have exactly three incident odd edges. As we can see, vertices v1, v2, and v3 all have at least four incident odd edges.Figure 2
Example of a 3D-OPP and its extreme vertices.Definition 17.
Letp be an nD-OPP. A kD couplet of p, 1<k<n, denoted by Φ(p), is the maximal set of kD cells of p that lies in a kD space, such that a kD cell e0 belongs to a kD couplet if and only if e0 belongs to an (n-1)D cell present in ∂(p); that is,(10)e0∈Φp⟺∃c,cbelongsto∂pe00,1k⊆c0,1n-1.Definition 18.
Consider annD-OPP p:(i)
Letnpi be the number of distinct coordinates present in the vertices of p along Xi-axis, 1≤i≤n.(ii)
LetΦkip be the kth (n-1)D couplet of p which is perpendicular to Xi-axis, 1≤i≤n.In Figure3 we illustrate an example for brinks and couplets for the 3D-OPP previously shown in Figure 2. As we can see, the brinks can be classified with respect to the coordinated axis they are aligned to. All the brinks shown in Figure 3(a) are aligned with respect to X1-axis. In a similar fashion, couplets can be classified according to which axis they are perpendicular to. In Figure 3(b) the couplets are shown that are perpendicular to X1-axis.Figure 3
Some brinks, couplets, and sections for a 3D-OPP.
(a)
(b)
(c)


#### 3.2.1. Sections and Slices

Definition 19.
A slice is the region contained in annD-OPP p between two consecutive couplets of p. Slicekip will denote the kth slice of p which is bounded by Φkip and Φk+1ip, 1≤k≤npi.Definition 20.
A section is the(n-1)D-OPP, n>1, resulting from the intersection between an nD-OPP p and a (n-1)D hyperplane perpendicular to the coordinate axis Xi,1<i<n, not coinciding with any (n-1)D couplet of p. A section will be called external or internal section of p if it is empty or not, respectively. Skip will refer to the kth section of p between Φkip and Φk+1ip,1<k<npi.In Figure3(c), sections are shown perpendicular to X1-axis for the 3D-OPP originally presented in Figure 2. Sections can be also classified considering their perpendicularity with respect to X2- and X3-axis.


#### 3.2.2. Computing Couplets and Sections

Definition 21.
The Projection Operator for(n-1)D cells, points, and sets of points is, respectively, defined as follows:(i)
LetcIi,αnx=x1,…,xn be an (n-1)D cell embedded in the nD space. Let πjcIi,αnx denote the projection of the cell cIi,αnx onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis:(11)πjcIi,αnx=x1,…,x^j,…,xn.(ii)
Letv=(x1,…,xn) a point in Rn. The projection of that point in the (n-1)D space, denoted by πj(v), is given by(12)πjv=x1,…,x^j,…,xn.(iii)
LetQ be a set of points in Rn. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in Rn-1 such that(13)πjQ=p∈Rn-1:p=πjx,x∈Q⊂Rn.
In all cases given by (11), (12), and (13), x^j is the coordinate corresponding to Xj-axis to be suppressed.Theorem 22.
The projection of the set of(n-1)D couplets, πiΦkip, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗) between the projections of its previous πiSk-1ip and next πiSkip sections; that is, πiΦkip=πiSk-1ip⊗∗πiSkip.Theorem 23.
The projection of any section,πiSkip, of an nD-OPP p, can be obtained by computing the regularized XOR between the projection of its previous section πiSk-1ip and the projection of its previous couplet πiΦkip.Theorem 24.
Letp and q be the two nD-OPPs having EVMn(p) and EVMn(q) as their respective EVMs in the nD space; then EVMn(p⊗∗q)=EVMn(p)⊗EVMn(q).In the previous theorems the foundations were given for obtaining couplets and sections sequences. This is useful for the specification of algorithms for performing modifications or operations between twonD-OPPs expressed in the nD-EVM.


### 3.3. Algorithms in thenD-EVM

In this subsection we present the basic algorithms for thenD-EVM model. The basic algorithms were introduced in [31] and in research works cited at the beginning of the section. The following list describes some primitive operations for the nD-EVM model:(i)
initEVM: initialize a nD-EVM object, which contains the empty set.(ii)
isEmpty: it returnstrue if a given nD-EVM p is empty; otherwise it returnsfalse.(iii)
endEVM: it returnstrue if the end of a given EVM p along the X1-axis has been reached. This is useful when an operation is performed or a procedure requires to explore the couplets sequence. This way we can know if we already explored all couplets in p.(iv)
readCouplet: it extracts the next (n-1)D couplet that is perpendicular to X1-axis from a given nD-EVM p. This reading is performed sequentially and orderly, which means that every time we call this procedure it will return a different couplet (the next one), and when we reach the end of p it will return an empty object.(v)
putCouplet: given a nD-EVM p and a (n-1)D couplet c, and considering that c is perpendicular to the X1-axis, it appends c to p.(vi)
getCurrentCoord: for a given nD-EVM p, it returns the x1 coordinate of the next (n-1)D couplet to be extracted from p.(vii)
setCoord: it sets the x1 coordinate value on every vertex of a (n-1)D couplet c.(viii)
mergeXor: it applies the exclusive XOR operation to the vertices of the given input nD-EVMs p and q and returns the resulting set.Now, from the above primitive operations it is possible to compute sections and couplets projections. This is based on Theorems22, 23, and 24, where themergeXOR algorithm is used:(i)
getCouplet: it computes the projection of a couplet between two consecutive sections. This is achieved by callingmergeXOR algorithm.(ii)
getSection: this algorithm computes the projection of a section from its previous section and following couplet. This is also achieved by usingmergeXOR algorithm.From the previous algorithms, Algorithm1 computes the sections sequence for an nD-OPP p expressed in the nD-EVM. As can be seen, this procedure is performed in a sequential manner: it reads the couplet projections from the given polytope and then computes the section projection considering the algorithmgetSection. Once a section is obtained, it is possible to perform operations or some processing to it, as can be observed in line 10. In practical terms, Algorithm 1 serves as layout for performing operations between two nD-EVMs as it establishes the main workflow of some algorithms for the nD-EVM.Algorithm 1:Computing the section sequence for a given nD-EVM p.
Input: An nD-EVM p.
(1)ProceduresectionSequence  (nD-EVM p)
(2)EVM couplet;
(3)EVM Si, Sj; // Previous and current section
(4)Couplet ← initEVM ( );
(5)Si ← initEVM ( );
(6)Sj ← initEVM ( );
(7)couplet ← readCouplet (p);
(8)while  !endEVM (p)  do
(9)Sj ← getSection (Si, couplet);
(10)Process the current section Sj;
(11)Si←Sj;
(12)couplet ← readCouplet (p);


#### 3.3.1. The Boolean Operations Algorithm

The Boolean Operations Algorithm under thenD-EVM is a very important procedure in the sense that it applies a Regularized Boolean Operation op∗∈{∪∗,∩∗,-∗,⊗∗} to a pair of given nD-OPPs p and q expressed in the nD-EVM. See Algorithm 2. The algorithm computes the resulting nD-OPP r=pop∗q. The main elements of the algorithm are described [31]:(i)
For bothnD-OPPs p and q their sections sequence is obtained as can be observed in lines 17 and 20. Because the algorithm performs the operations at the level of sections, it considers only the sections perpendicular to X1-axis.(ii)
The order of appearance of couplets of bothp and q is taken into account. This is performed in the functionnextObject (line 13). It returns the value of thecoordinate for the next couplet to process; this coordinate is common to both operands. It also sets two flagsfromP andfromQ: they indicate from which operand the next couplet is taken. These flags are evaluated at the conditions of lines 15 and 18.(iii)
The resulting sections ofr are computed as follows [30, 31]: Skir=Skipop∗Skiq. By this way a recursive pattern of execution for this algorithm is established, and it can be observed in line 22.(iv)
The sections forp and q are processed recursively until we reach the basic case: the Regularized Boolean Operations for 1D-OPPs which are managed bybooleanOperation1D function in line 8. By this way, we can build the result r from its sections’ projections, and the algorithm keeps track of the previous and current sections in order to compute the projection of the corresponding couplet, which is appended to the result in line 25.(v)
There are two repetition structures after the mainwhile structure, at lines 27 and 30. They manage the case when one of the nD-OPPs has reached the end with respect to X1-axis, but the other operand still has couplets to be operated. Therefore, in thosewhile structures it is considered the Regularized Boolean Operation that is being applied, because it depends if the remaining couplets are taken into account for the resulting final nD-EVM.Algorithm 2:Computing the Regularized Boolean Operations for two nD-EVMs.
Input: Two nD-EVMs p and q, the Boolean Operation op, and the dimensionality n.
Output: A resulting nD-EVM.
(1)ProcedurebooleanOperation  (nD-EVM p, nD-EVM q, booleanOperator op, integer n)
(2)     EVM pSection, qSection;
(3)     EVM couplet;
(4)     boolean fromQ, fromP;
(5)     real coord;
(6)     EVM result, rPrevSection, rCurrSection;
(7)     if n=1 then
(8)       return booleanOperation1D (p,q,op);
(9)     else
(10)pSection ← initEVM ( );
(11)qSection ← initEVM ( );
(12)rCurrSection ← initEVM ( );
(13)        nextObject (p,q,fromP,fromQ);
(14)while  !(endEVM (p))  and  !(endEVM (q))  do
(15)if  fromP  then
(16)couplet ← readCouplet (p);
(17)pSection ← getSection (pSection,couplet);
(18)if  fromQ  then
(19)couplet ← readCouplet (q);
(20)qSection ← getSection (qSection,couplet);
(21)rPrevSection ← rCurrSection
(22)rCurrSection ← booleanOperation (pSection,qSection,op,n-1);
(23)couplet ← getCouplet (rPrevSection, rCurrSection);
(24)        setCoord (couplet, coord);
(25)        putCouplet (couplet, result);
(26)        nextObject (p,q,coord,fromP,fromQ);
(27)while  !endEVM (p)  do
(28)couplet ← readCouplet (p);
(29)        putBool (couplet, result, op);
(30)while  !endEVM (q)  do
(31)couplet ← readCouplet (q);
(32)        putBool (couplet, result, op);
(33)  return result


#### 3.3.2. Computing the Content of annD-OPP

As described in [31], we aim to compute the nD content enclosed by an nD-OPP by considering its slices. As we know, a slice is a set of one or more disjoints nD hyperprisms; it has a (n-1)D section as its base and two boundary (n-1)D couplets. Let us take a 3D-OPP p as an example. The content of p can be obtained from the sum of the volumes of its 3D slices. Now, the volume of a Slicekip is given by the product between the area of the 2D section Skip (i.e., the 2D base of the 3D slice) and the distance between its two boundary 2D couplets Φkip and Φk+1ip (it is the height of the 3D slice). Now suppose that we have a 2D-OPP q=Skip which in fact is a 2D section of p and the base of Slicekip. The content of q, its area, is the sum of the areas of the 2D slices that form q. The area of a 2D is given by the product of the length of the 1D section Skiq as its base and the distance between 1D couplets Φkiq and Φk+1iq. In the basic case, for an 1D-OPP r, the content of r is computed as the sum of the lengths of its brinks. Now, the recursive formula for computing the content of a nD-OPP p is the following [31]:(14)Contentnp=Lengthpn=1∑k=1npi-1Contentn-1Skip·DistΦkip,Φk+1ipn>1.Algorithm3 is the implementation for (14). It computes the nD content enclosed by a given nD-OPP that is represented through the nD-EVM.Algorithm 3:Computing the nD content enclosed by a given nD-EVM p.
Input: A nD-EVM p and the number of dimensions n.
Output: The content of the nD space enclosed by p.
(1)ProcedureContent  (nD-EVM p, n)
(2)     contSum ← 0;
/∗ Objects initialization ∗/
(3)     EVM couplet  1, couplet  2;
(4)     EVM section;
(5)     if  n==1  then
(6)     return Length (p);
(7)     couplet  1 ← InitEVM ();
(8)     couplet  2 ← InitEVM ();
(9)     section ← InitEVM ();
(10)couplet  1  ←  readCouplet (p);
(11)while  !endEVM (p)  do
(12)  couplet  2 ← readCouplet (p);
(13)  section ← getSection (section, couplet  1);
(14)  contSum ← contSum + Content (section,n-1) ∗ dist (couplet  1, couplet  2);
(15)  couplet  1 ← couplet  2;
(16)return  contSum


#### 3.3.3. Computing the Discrete Compactness Descriptor

TheDiscrete Compactness (DC) descriptor is very useful for characterizing objects considering their similarity with some ideal objects. Moreover, Discrete Compactness improves the classicalShape Compactness descriptor [44, 45].It is important to mention the definition of a hypervoxelization [30, 31], which is the basis for properly establishing the DC descriptor. A hypervoxelization is a Hyperspatial Occupancy Enumeration scheme for polytopes. A hypervoxelization is a list of cells in the Hyperspace occupied by a polytope. These cells are called hypervoxels and they are hyperboxes of a fixed size in the nD space. In this sense, a hypervoxel in the 2D space is a pixel, a 3D hypervoxel is a voxel, and for the 4D space the termrexel is recommended. A collection of hypervoxels is codified as an array Cx1,x2,…,xn of dimensionality n, in which a black (occupied) hypervoxel and a white (unoccupied) hypervoxel are specified when Cx1,x2,…,xn=1 and Cx1,x2,…,xn=0, respectively. A polytope is then defined as a collection of occupied hypervoxels. It is important to note that hypervoxels are in fact disjoint or quasi-disjoint, which means that they do not overlap. The result of the union of all black hypervoxels in a given hypervoxelization describes in fact a nD-OPP p:(15)p=⋃λBlackHypervoxelλ.Considering that from a black nD hypervoxel 2n extreme vertices can be generated, the corresponding nD-EVM representation of p can be obtained as follows:(16)EVMnp=EVMn⋃λBlackHypervoxelλ=⨂λEVMnBlackHypervoxelλ.For computing the DC descriptor it is important to consider that thenD-OPPs were originally expressed as hypervoxelizations where the hypervoxels are hypercubes and their coordinates are integers. In [46, 47] the foundations for computing DC for 2D and 3D objects are presented. In [13] computation for objects in the nD space n≥3 was presented. In any case, formula for DC descriptor is the following:(17)DCp=Lcp-LMinLMax-LMin.Lc(p) is the number of internal contacts for the nD-OPP p. LMin is the minimal number of internal contacts for an ideal nD object with the same content as p. In similar way, LMax is the maximal number of internal contacts for an ideal nD object with the same content as p. The internal contacts for an nD-OPP are the (n-1)D cells that are shared between the nD hypervoxels that originally defined p. LMin and LMax must be specified according to the desired application. For an nD-OPP represented through the nD-EVM, the procedure for computing the internal contacts perpendicular to X1-axis is shown in Algorithm 4. This procedure is described as follows:(i)
We process the slices aligned with respect toX1-axis.(ii)
The number of internalx1-coordinates are obtained for the current slice. This is achieved by obtaining the x1-coordinates c1 and c2 for the bounding couplets of the slice (lines 12 and 13):(18)nCoords=c2-c1-1.(iii)
For every slice the(n-1)D content of the corresponding section Sj is obtained. The internal contacts perpendicular to X1-axis are computed as follows (line 14):(19)IC=nCoords·ContentSj.(iv)
It is considered that there may be contiguous and isolated slices; for this reason we need to obtain the internal contacts between boundaries of consecutive slices. This is achieved by computing the regularized intersection between consecutive sections and then computing the content of the result (lines 15 and 16).Algorithm 4:Computing the (n-1)D adjacencies, shared (n-1)D cells, between the hypervoxels that originally defined to a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The number of internal contacts perpendicular to X1-axis.
(1)ProcedureInternalContacts  (nD-EVM p, n)
(2)     EVM couplet, currentSection, previousSection;
(3)     EVM sectionInt; // Intersection result
(4)     integer c1, c2; // Couplets coordinates
(5)     integer nCoords;
(6)     integer ic←0; // Total internal contacts
(7)     previousSection ← InitEVM ( );
(8)     c1 ← getCoord (p);
(9)     couplet ← readCouplet (p);
(10)   while  !endEVM (p)  do
// Internal contacts for the current slice
(11)currentSection ← getSection (previousSection, couplet);
(12)c2 ← getCoord (p);
(13)nCoords←c2-c1-1;
(14)ic ← ic + nCoords ∗ Content (currentSection, n-1);
// Internal contacts between consecutive slices
(15)sectionInt ← BooleanOperation (previousSection, currentSection, ∩∗, n-1);
(16)ic ← ic + Content (sectionInt, n-1);
(17)previousSection←currentSection;
(18)c1←c2;
(19)couplet ← readCouplet (p);
(20)   return icSince Algorithm4 considers its processes in terms of the first coordinate, it will be required to apply it for every xi-coordinate, 1≤i≤n. At the implementation level, this is easy by reordering the coordinates of the EVM representation as follows:(20)AxisSorting=x1,x2,…,xn-1,xn,x2,x3,…,xn,x1,x3,x4,…,x1,x2,…,xn,x1,…,xn-2,xn-1.In order to compute the total internal contacts it is required to process all the possible axis orderings. In Algorithm 5 the procedure for computing the total internal contacts is shown, in which a new nD-EVM is obtained from a different axis ordering in line 5. In line 6 the cumulative sum of the total internal contacts is performed.Algorithm 5:Computing the total internal contacts, Lc(p), for a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The total number of internal contacts for the hyper-boxes of a given nD-EVM
(1)ProcedureTotalInternalContacts  (nD-EVM p, n)
(2)     integer ic←0; // Total internal contacts
(3)     EVM SortedP;
(4)     for each sorting ∈AxisSorting  do
(5)       SortedP←sortEVM (p, n, sorting);
(6)       ic← ic+ InternalContacts (SortedP,n);
(7)     return  icBefore computing the DC descriptor for a givennD-OPP p it is important to define the application context. So, it is required to provide the two nD-OPPs pl and pu which represent the ideal objects against all the pertinent nD-OPPs that will be compared. Once those bounds have been defined, we compute via Algorithm 5 the minimum and maximum internal contacts as follows:(21)LMin=TotalInternalContactspl,n,LMax=TotalInternalContactspu,n.Lc(p) is the number of total internal contacts for p, and finally the DC descriptor is computed using (17).


## 3.1.nD-OPPs Fundamentals

Definition 1 (see [43]).
A singularn-Dimensional hyperbox in Rn is given by the continuous function:(6)In:0,1n⟶0,1n,x~Inx=x.Definition 2 (see [43]).
A general singulark-Dimensional hyperbox in the closed set A⊂Rn is the continuous function c:0,1k→A.In the above definitions, the functionIn defines a unit hyperbox 0,1n in the nD Euclidean space. More specifically, and as an example, in the 2D case it defines a unit square, while in the 3D space this function defines a unit cube.Definition 3 (see [43]).
For alli=1,2,…,n, the two singular (n-1)D hyperboxes Ii,0n and Ii,1n are defined as follows: if x∈0,1n-1, then(7)Ii,0nx=Inx1,…,xi-1,0,xi,…,xn-1=x1,…,xi-1,0,xi,…,xn-1,Ii,1nx=Inx1,…,xi-1,1,xi,…,xn-1=x1,…,xi-1,1,xi,…,xn-1.Definition 4 (see [43]).
In a general singularnD hyperbox c one defines the (i,α) cell as c(i,α)=c∘Ii,αn.Definition 5 (see [43]).
The orientation of a(n-1)D cell c∘Ii,αn is given by (-1)i+α.Definition 6 (see [43]).
A(n-1)D oriented cell is given by the scalar-function product (-1)i+α·c∘Ii,αn.Definition 7 (see [43]).
A formal linear combination of singular generalkD hyperboxes, 1≤k≤n, for a closed set A is called a k-chain.Definition 8 (see [43]).
Given a singular generalnD hyperbox c we define the (n-1) chain, called the boundary of c, by(8)∂c=∑i=1n∑α=0,1-1i+α·c∘Ii,αn.Definition 9 (see [43]).
The boundary of ann-chain ∑ci, where each ci is a singular general nD hyperbox, is given by(9)∂∑ci=∑∂ci.The above definitions share with us the basis for handling collections of hyperboxes in thenD space. By this way, when the boundary of a collection of hyperboxes is computed, shared cells between hyperboxes are automatically deleted because of their sign’s orientation.Definition 10.
Ann-Dimensional Orthogonal Pseudo Polytope, or just an nD-OPP, is a n-chain composed by nD hyperboxes arranged in such way that, by selecting a vertex in any of these hyperboxes, it describes a combination of nD hyperboxes composed up to 2n hyperboxes.


## 3.2.nD-EVM Fundamentals

Definition 11.
Letc be a combination of hyperboxes in the nD space. An Odd Adjacency Edge of c, or just an Odd Edge, is an edge with an odd number of incident hyperboxes of c. Conversely, if an edge has an even number of incident hyperboxes of c, then it is called an Even Adjacency Edge, or just an Even Edge.Definition 12.
A Brink or Extended Edge is the maximal uninterrupted segment built out of a sequence of collinear and contiguous odd edges of annD-OPP.Considering that a brink is formed bym odd edges, m≥1, it contains m+1 vertices: two of them are extreme vertices and the remaining m-1 are interior vertices. We will see that the interior vertices are not considered in the EVM model which is going to be defined.Definition 13.
The ending vertices of all the brinks in annD-OPP p will be called the extreme vertices of p. EV(p) will denote the set of extreme vertices of p.Definition 14.
Letp be an nD-OPP. One defines the Extreme Vertices Model of p, denoted by EVMn(p), as the model that only stores all the extreme vertices of p.Theorem 15.
A vertex of annD-OPP p, n≥1, when it is locally described by a set of surrounding nD hyperboxes, is an extreme vertex if and only if it is surrounded by an odd number of such nD hyperboxes.Theorem 16.
Any extreme vertex of annD-OPP, n≥1, when it is locally described by a set of surrounding nD hyperboxes, has exactly n incident linearly independent odd edges.Let us take the example from Figure2. A 3D-OPP and its extreme vertices are presented. As can be observed, the continuous lines represent odd edges; on the other hand, the dotted line represents an Even Edge. Black dots are extreme vertices and white dots are internal vertices. In this case we can see that at the end of every brink an extreme vertex is found. On the other hand, vertices v1, v2, and v3 are nonextreme vertices. The remaining vertices satisfy the conditions established by Theorems 15 and 16: only extreme vertices have exactly three incident odd edges. As we can see, vertices v1, v2, and v3 all have at least four incident odd edges.Figure 2
Example of a 3D-OPP and its extreme vertices.Definition 17.
Letp be an nD-OPP. A kD couplet of p, 1<k<n, denoted by Φ(p), is the maximal set of kD cells of p that lies in a kD space, such that a kD cell e0 belongs to a kD couplet if and only if e0 belongs to an (n-1)D cell present in ∂(p); that is,(10)e0∈Φp⟺∃c,cbelongsto∂pe00,1k⊆c0,1n-1.Definition 18.
Consider annD-OPP p:(i)
Letnpi be the number of distinct coordinates present in the vertices of p along Xi-axis, 1≤i≤n.(ii)
LetΦkip be the kth (n-1)D couplet of p which is perpendicular to Xi-axis, 1≤i≤n.In Figure3 we illustrate an example for brinks and couplets for the 3D-OPP previously shown in Figure 2. As we can see, the brinks can be classified with respect to the coordinated axis they are aligned to. All the brinks shown in Figure 3(a) are aligned with respect to X1-axis. In a similar fashion, couplets can be classified according to which axis they are perpendicular to. In Figure 3(b) the couplets are shown that are perpendicular to X1-axis.Figure 3
Some brinks, couplets, and sections for a 3D-OPP.
(a)
(b)
(c)


### 3.2.1. Sections and Slices

Definition 19.
A slice is the region contained in annD-OPP p between two consecutive couplets of p. Slicekip will denote the kth slice of p which is bounded by Φkip and Φk+1ip, 1≤k≤npi.Definition 20.
A section is the(n-1)D-OPP, n>1, resulting from the intersection between an nD-OPP p and a (n-1)D hyperplane perpendicular to the coordinate axis Xi,1<i<n, not coinciding with any (n-1)D couplet of p. A section will be called external or internal section of p if it is empty or not, respectively. Skip will refer to the kth section of p between Φkip and Φk+1ip,1<k<npi.In Figure3(c), sections are shown perpendicular to X1-axis for the 3D-OPP originally presented in Figure 2. Sections can be also classified considering their perpendicularity with respect to X2- and X3-axis.


### 3.2.2. Computing Couplets and Sections

Definition 21.
The Projection Operator for(n-1)D cells, points, and sets of points is, respectively, defined as follows:(i)
LetcIi,αnx=x1,…,xn be an (n-1)D cell embedded in the nD space. Let πjcIi,αnx denote the projection of the cell cIi,αnx onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis:(11)πjcIi,αnx=x1,…,x^j,…,xn.(ii)
Letv=(x1,…,xn) a point in Rn. The projection of that point in the (n-1)D space, denoted by πj(v), is given by(12)πjv=x1,…,x^j,…,xn.(iii)
LetQ be a set of points in Rn. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in Rn-1 such that(13)πjQ=p∈Rn-1:p=πjx,x∈Q⊂Rn.
In all cases given by (11), (12), and (13), x^j is the coordinate corresponding to Xj-axis to be suppressed.Theorem 22.
The projection of the set of(n-1)D couplets, πiΦkip, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗) between the projections of its previous πiSk-1ip and next πiSkip sections; that is, πiΦkip=πiSk-1ip⊗∗πiSkip.Theorem 23.
The projection of any section,πiSkip, of an nD-OPP p, can be obtained by computing the regularized XOR between the projection of its previous section πiSk-1ip and the projection of its previous couplet πiΦkip.Theorem 24.
Letp and q be the two nD-OPPs having EVMn(p) and EVMn(q) as their respective EVMs in the nD space; then EVMn(p⊗∗q)=EVMn(p)⊗EVMn(q).In the previous theorems the foundations were given for obtaining couplets and sections sequences. This is useful for the specification of algorithms for performing modifications or operations between twonD-OPPs expressed in the nD-EVM.


## 3.2.1. Sections and Slices

Definition 19.
A slice is the region contained in annD-OPP p between two consecutive couplets of p. Slicekip will denote the kth slice of p which is bounded by Φkip and Φk+1ip, 1≤k≤npi.Definition 20.
A section is the(n-1)D-OPP, n>1, resulting from the intersection between an nD-OPP p and a (n-1)D hyperplane perpendicular to the coordinate axis Xi,1<i<n, not coinciding with any (n-1)D couplet of p. A section will be called external or internal section of p if it is empty or not, respectively. Skip will refer to the kth section of p between Φkip and Φk+1ip,1<k<npi.In Figure3(c), sections are shown perpendicular to X1-axis for the 3D-OPP originally presented in Figure 2. Sections can be also classified considering their perpendicularity with respect to X2- and X3-axis.


## 3.2.2. Computing Couplets and Sections

Definition 21.
The Projection Operator for(n-1)D cells, points, and sets of points is, respectively, defined as follows:(i)
LetcIi,αnx=x1,…,xn be an (n-1)D cell embedded in the nD space. Let πjcIi,αnx denote the projection of the cell cIi,αnx onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis:(11)πjcIi,αnx=x1,…,x^j,…,xn.(ii)
Letv=(x1,…,xn) a point in Rn. The projection of that point in the (n-1)D space, denoted by πj(v), is given by(12)πjv=x1,…,x^j,…,xn.(iii)
LetQ be a set of points in Rn. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in Rn-1 such that(13)πjQ=p∈Rn-1:p=πjx,x∈Q⊂Rn.
In all cases given by (11), (12), and (13), x^j is the coordinate corresponding to Xj-axis to be suppressed.Theorem 22.
The projection of the set of(n-1)D couplets, πiΦkip, of an nD-OPP p, can be obtained by computing the regularized XOR (⊗) between the projections of its previous πiSk-1ip and next πiSkip sections; that is, πiΦkip=πiSk-1ip⊗∗πiSkip.Theorem 23.
The projection of any section,πiSkip, of an nD-OPP p, can be obtained by computing the regularized XOR between the projection of its previous section πiSk-1ip and the projection of its previous couplet πiΦkip.Theorem 24.
Letp and q be the two nD-OPPs having EVMn(p) and EVMn(q) as their respective EVMs in the nD space; then EVMn(p⊗∗q)=EVMn(p)⊗EVMn(q).In the previous theorems the foundations were given for obtaining couplets and sections sequences. This is useful for the specification of algorithms for performing modifications or operations between twonD-OPPs expressed in the nD-EVM.


## 3.3. Algorithms in thenD-EVM

In this subsection we present the basic algorithms for thenD-EVM model. The basic algorithms were introduced in [31] and in research works cited at the beginning of the section. The following list describes some primitive operations for the nD-EVM model:(i)
initEVM: initialize a nD-EVM object, which contains the empty set.(ii)
isEmpty: it returnstrue if a given nD-EVM p is empty; otherwise it returnsfalse.(iii)
endEVM: it returnstrue if the end of a given EVM p along the X1-axis has been reached. This is useful when an operation is performed or a procedure requires to explore the couplets sequence. This way we can know if we already explored all couplets in p.(iv)
readCouplet: it extracts the next (n-1)D couplet that is perpendicular to X1-axis from a given nD-EVM p. This reading is performed sequentially and orderly, which means that every time we call this procedure it will return a different couplet (the next one), and when we reach the end of p it will return an empty object.(v)
putCouplet: given a nD-EVM p and a (n-1)D couplet c, and considering that c is perpendicular to the X1-axis, it appends c to p.(vi)
getCurrentCoord: for a given nD-EVM p, it returns the x1 coordinate of the next (n-1)D couplet to be extracted from p.(vii)
setCoord: it sets the x1 coordinate value on every vertex of a (n-1)D couplet c.(viii)
mergeXor: it applies the exclusive XOR operation to the vertices of the given input nD-EVMs p and q and returns the resulting set.Now, from the above primitive operations it is possible to compute sections and couplets projections. This is based on Theorems22, 23, and 24, where themergeXOR algorithm is used:(i)
getCouplet: it computes the projection of a couplet between two consecutive sections. This is achieved by callingmergeXOR algorithm.(ii)
getSection: this algorithm computes the projection of a section from its previous section and following couplet. This is also achieved by usingmergeXOR algorithm.From the previous algorithms, Algorithm1 computes the sections sequence for an nD-OPP p expressed in the nD-EVM. As can be seen, this procedure is performed in a sequential manner: it reads the couplet projections from the given polytope and then computes the section projection considering the algorithmgetSection. Once a section is obtained, it is possible to perform operations or some processing to it, as can be observed in line 10. In practical terms, Algorithm 1 serves as layout for performing operations between two nD-EVMs as it establishes the main workflow of some algorithms for the nD-EVM.Algorithm 1:Computing the section sequence for a given nD-EVM p.
Input: An nD-EVM p.
(1)ProceduresectionSequence  (nD-EVM p)
(2)EVM couplet;
(3)EVM Si, Sj; // Previous and current section
(4)Couplet ← initEVM ( );
(5)Si ← initEVM ( );
(6)Sj ← initEVM ( );
(7)couplet ← readCouplet (p);
(8)while  !endEVM (p)  do
(9)Sj ← getSection (Si, couplet);
(10)Process the current section Sj;
(11)Si←Sj;
(12)couplet ← readCouplet (p);


### 3.3.1. The Boolean Operations Algorithm

The Boolean Operations Algorithm under thenD-EVM is a very important procedure in the sense that it applies a Regularized Boolean Operation op∗∈{∪∗,∩∗,-∗,⊗∗} to a pair of given nD-OPPs p and q expressed in the nD-EVM. See Algorithm 2. The algorithm computes the resulting nD-OPP r=pop∗q. The main elements of the algorithm are described [31]:(i)
For bothnD-OPPs p and q their sections sequence is obtained as can be observed in lines 17 and 20. Because the algorithm performs the operations at the level of sections, it considers only the sections perpendicular to X1-axis.(ii)
The order of appearance of couplets of bothp and q is taken into account. This is performed in the functionnextObject (line 13). It returns the value of thecoordinate for the next couplet to process; this coordinate is common to both operands. It also sets two flagsfromP andfromQ: they indicate from which operand the next couplet is taken. These flags are evaluated at the conditions of lines 15 and 18.(iii)
The resulting sections ofr are computed as follows [30, 31]: Skir=Skipop∗Skiq. By this way a recursive pattern of execution for this algorithm is established, and it can be observed in line 22.(iv)
The sections forp and q are processed recursively until we reach the basic case: the Regularized Boolean Operations for 1D-OPPs which are managed bybooleanOperation1D function in line 8. By this way, we can build the result r from its sections’ projections, and the algorithm keeps track of the previous and current sections in order to compute the projection of the corresponding couplet, which is appended to the result in line 25.(v)
There are two repetition structures after the mainwhile structure, at lines 27 and 30. They manage the case when one of the nD-OPPs has reached the end with respect to X1-axis, but the other operand still has couplets to be operated. Therefore, in thosewhile structures it is considered the Regularized Boolean Operation that is being applied, because it depends if the remaining couplets are taken into account for the resulting final nD-EVM.Algorithm 2:Computing the Regularized Boolean Operations for two nD-EVMs.
Input: Two nD-EVMs p and q, the Boolean Operation op, and the dimensionality n.
Output: A resulting nD-EVM.
(1)ProcedurebooleanOperation  (nD-EVM p, nD-EVM q, booleanOperator op, integer n)
(2)     EVM pSection, qSection;
(3)     EVM couplet;
(4)     boolean fromQ, fromP;
(5)     real coord;
(6)     EVM result, rPrevSection, rCurrSection;
(7)     if n=1 then
(8)       return booleanOperation1D (p,q,op);
(9)     else
(10)pSection ← initEVM ( );
(11)qSection ← initEVM ( );
(12)rCurrSection ← initEVM ( );
(13)        nextObject (p,q,fromP,fromQ);
(14)while  !(endEVM (p))  and  !(endEVM (q))  do
(15)if  fromP  then
(16)couplet ← readCouplet (p);
(17)pSection ← getSection (pSection,couplet);
(18)if  fromQ  then
(19)couplet ← readCouplet (q);
(20)qSection ← getSection (qSection,couplet);
(21)rPrevSection ← rCurrSection
(22)rCurrSection ← booleanOperation (pSection,qSection,op,n-1);
(23)couplet ← getCouplet (rPrevSection, rCurrSection);
(24)        setCoord (couplet, coord);
(25)        putCouplet (couplet, result);
(26)        nextObject (p,q,coord,fromP,fromQ);
(27)while  !endEVM (p)  do
(28)couplet ← readCouplet (p);
(29)        putBool (couplet, result, op);
(30)while  !endEVM (q)  do
(31)couplet ← readCouplet (q);
(32)        putBool (couplet, result, op);
(33)  return result


### 3.3.2. Computing the Content of annD-OPP

As described in [31], we aim to compute the nD content enclosed by an nD-OPP by considering its slices. As we know, a slice is a set of one or more disjoints nD hyperprisms; it has a (n-1)D section as its base and two boundary (n-1)D couplets. Let us take a 3D-OPP p as an example. The content of p can be obtained from the sum of the volumes of its 3D slices. Now, the volume of a Slicekip is given by the product between the area of the 2D section Skip (i.e., the 2D base of the 3D slice) and the distance between its two boundary 2D couplets Φkip and Φk+1ip (it is the height of the 3D slice). Now suppose that we have a 2D-OPP q=Skip which in fact is a 2D section of p and the base of Slicekip. The content of q, its area, is the sum of the areas of the 2D slices that form q. The area of a 2D is given by the product of the length of the 1D section Skiq as its base and the distance between 1D couplets Φkiq and Φk+1iq. In the basic case, for an 1D-OPP r, the content of r is computed as the sum of the lengths of its brinks. Now, the recursive formula for computing the content of a nD-OPP p is the following [31]:(14)Contentnp=Lengthpn=1∑k=1npi-1Contentn-1Skip·DistΦkip,Φk+1ipn>1.Algorithm3 is the implementation for (14). It computes the nD content enclosed by a given nD-OPP that is represented through the nD-EVM.Algorithm 3:Computing the nD content enclosed by a given nD-EVM p.
Input: A nD-EVM p and the number of dimensions n.
Output: The content of the nD space enclosed by p.
(1)ProcedureContent  (nD-EVM p, n)
(2)     contSum ← 0;
/∗ Objects initialization ∗/
(3)     EVM couplet  1, couplet  2;
(4)     EVM section;
(5)     if  n==1  then
(6)     return Length (p);
(7)     couplet  1 ← InitEVM ();
(8)     couplet  2 ← InitEVM ();
(9)     section ← InitEVM ();
(10)couplet  1  ←  readCouplet (p);
(11)while  !endEVM (p)  do
(12)  couplet  2 ← readCouplet (p);
(13)  section ← getSection (section, couplet  1);
(14)  contSum ← contSum + Content (section,n-1) ∗ dist (couplet  1, couplet  2);
(15)  couplet  1 ← couplet  2;
(16)return  contSum


### 3.3.3. Computing the Discrete Compactness Descriptor

TheDiscrete Compactness (DC) descriptor is very useful for characterizing objects considering their similarity with some ideal objects. Moreover, Discrete Compactness improves the classicalShape Compactness descriptor [44, 45].It is important to mention the definition of a hypervoxelization [30, 31], which is the basis for properly establishing the DC descriptor. A hypervoxelization is a Hyperspatial Occupancy Enumeration scheme for polytopes. A hypervoxelization is a list of cells in the Hyperspace occupied by a polytope. These cells are called hypervoxels and they are hyperboxes of a fixed size in the nD space. In this sense, a hypervoxel in the 2D space is a pixel, a 3D hypervoxel is a voxel, and for the 4D space the termrexel is recommended. A collection of hypervoxels is codified as an array Cx1,x2,…,xn of dimensionality n, in which a black (occupied) hypervoxel and a white (unoccupied) hypervoxel are specified when Cx1,x2,…,xn=1 and Cx1,x2,…,xn=0, respectively. A polytope is then defined as a collection of occupied hypervoxels. It is important to note that hypervoxels are in fact disjoint or quasi-disjoint, which means that they do not overlap. The result of the union of all black hypervoxels in a given hypervoxelization describes in fact a nD-OPP p:(15)p=⋃λBlackHypervoxelλ.Considering that from a black nD hypervoxel 2n extreme vertices can be generated, the corresponding nD-EVM representation of p can be obtained as follows:(16)EVMnp=EVMn⋃λBlackHypervoxelλ=⨂λEVMnBlackHypervoxelλ.For computing the DC descriptor it is important to consider that thenD-OPPs were originally expressed as hypervoxelizations where the hypervoxels are hypercubes and their coordinates are integers. In [46, 47] the foundations for computing DC for 2D and 3D objects are presented. In [13] computation for objects in the nD space n≥3 was presented. In any case, formula for DC descriptor is the following:(17)DCp=Lcp-LMinLMax-LMin.Lc(p) is the number of internal contacts for the nD-OPP p. LMin is the minimal number of internal contacts for an ideal nD object with the same content as p. In similar way, LMax is the maximal number of internal contacts for an ideal nD object with the same content as p. The internal contacts for an nD-OPP are the (n-1)D cells that are shared between the nD hypervoxels that originally defined p. LMin and LMax must be specified according to the desired application. For an nD-OPP represented through the nD-EVM, the procedure for computing the internal contacts perpendicular to X1-axis is shown in Algorithm 4. This procedure is described as follows:(i)
We process the slices aligned with respect toX1-axis.(ii)
The number of internalx1-coordinates are obtained for the current slice. This is achieved by obtaining the x1-coordinates c1 and c2 for the bounding couplets of the slice (lines 12 and 13):(18)nCoords=c2-c1-1.(iii)
For every slice the(n-1)D content of the corresponding section Sj is obtained. The internal contacts perpendicular to X1-axis are computed as follows (line 14):(19)IC=nCoords·ContentSj.(iv)
It is considered that there may be contiguous and isolated slices; for this reason we need to obtain the internal contacts between boundaries of consecutive slices. This is achieved by computing the regularized intersection between consecutive sections and then computing the content of the result (lines 15 and 16).Algorithm 4:Computing the (n-1)D adjacencies, shared (n-1)D cells, between the hypervoxels that originally defined to a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The number of internal contacts perpendicular to X1-axis.
(1)ProcedureInternalContacts  (nD-EVM p, n)
(2)     EVM couplet, currentSection, previousSection;
(3)     EVM sectionInt; // Intersection result
(4)     integer c1, c2; // Couplets coordinates
(5)     integer nCoords;
(6)     integer ic←0; // Total internal contacts
(7)     previousSection ← InitEVM ( );
(8)     c1 ← getCoord (p);
(9)     couplet ← readCouplet (p);
(10)   while  !endEVM (p)  do
// Internal contacts for the current slice
(11)currentSection ← getSection (previousSection, couplet);
(12)c2 ← getCoord (p);
(13)nCoords←c2-c1-1;
(14)ic ← ic + nCoords ∗ Content (currentSection, n-1);
// Internal contacts between consecutive slices
(15)sectionInt ← BooleanOperation (previousSection, currentSection, ∩∗, n-1);
(16)ic ← ic + Content (sectionInt, n-1);
(17)previousSection←currentSection;
(18)c1←c2;
(19)couplet ← readCouplet (p);
(20)   return icSince Algorithm4 considers its processes in terms of the first coordinate, it will be required to apply it for every xi-coordinate, 1≤i≤n. At the implementation level, this is easy by reordering the coordinates of the EVM representation as follows:(20)AxisSorting=x1,x2,…,xn-1,xn,x2,x3,…,xn,x1,x3,x4,…,x1,x2,…,xn,x1,…,xn-2,xn-1.In order to compute the total internal contacts it is required to process all the possible axis orderings. In Algorithm 5 the procedure for computing the total internal contacts is shown, in which a new nD-EVM is obtained from a different axis ordering in line 5. In line 6 the cumulative sum of the total internal contacts is performed.Algorithm 5:Computing the total internal contacts, Lc(p), for a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The total number of internal contacts for the hyper-boxes of a given nD-EVM
(1)ProcedureTotalInternalContacts  (nD-EVM p, n)
(2)     integer ic←0; // Total internal contacts
(3)     EVM SortedP;
(4)     for each sorting ∈AxisSorting  do
(5)       SortedP←sortEVM (p, n, sorting);
(6)       ic← ic+ InternalContacts (SortedP,n);
(7)     return  icBefore computing the DC descriptor for a givennD-OPP p it is important to define the application context. So, it is required to provide the two nD-OPPs pl and pu which represent the ideal objects against all the pertinent nD-OPPs that will be compared. Once those bounds have been defined, we compute via Algorithm 5 the minimum and maximum internal contacts as follows:(21)LMin=TotalInternalContactspl,n,LMax=TotalInternalContactspu,n.Lc(p) is the number of total internal contacts for p, and finally the DC descriptor is computed using (17).


## 3.3.1. The Boolean Operations Algorithm

The Boolean Operations Algorithm under thenD-EVM is a very important procedure in the sense that it applies a Regularized Boolean Operation op∗∈{∪∗,∩∗,-∗,⊗∗} to a pair of given nD-OPPs p and q expressed in the nD-EVM. See Algorithm 2. The algorithm computes the resulting nD-OPP r=pop∗q. The main elements of the algorithm are described [31]:(i)
For bothnD-OPPs p and q their sections sequence is obtained as can be observed in lines 17 and 20. Because the algorithm performs the operations at the level of sections, it considers only the sections perpendicular to X1-axis.(ii)
The order of appearance of couplets of bothp and q is taken into account. This is performed in the functionnextObject (line 13). It returns the value of thecoordinate for the next couplet to process; this coordinate is common to both operands. It also sets two flagsfromP andfromQ: they indicate from which operand the next couplet is taken. These flags are evaluated at the conditions of lines 15 and 18.(iii)
The resulting sections ofr are computed as follows [30, 31]: Skir=Skipop∗Skiq. By this way a recursive pattern of execution for this algorithm is established, and it can be observed in line 22.(iv)
The sections forp and q are processed recursively until we reach the basic case: the Regularized Boolean Operations for 1D-OPPs which are managed bybooleanOperation1D function in line 8. By this way, we can build the result r from its sections’ projections, and the algorithm keeps track of the previous and current sections in order to compute the projection of the corresponding couplet, which is appended to the result in line 25.(v)
There are two repetition structures after the mainwhile structure, at lines 27 and 30. They manage the case when one of the nD-OPPs has reached the end with respect to X1-axis, but the other operand still has couplets to be operated. Therefore, in thosewhile structures it is considered the Regularized Boolean Operation that is being applied, because it depends if the remaining couplets are taken into account for the resulting final nD-EVM.Algorithm 2:Computing the Regularized Boolean Operations for two nD-EVMs.
Input: Two nD-EVMs p and q, the Boolean Operation op, and the dimensionality n.
Output: A resulting nD-EVM.
(1)ProcedurebooleanOperation  (nD-EVM p, nD-EVM q, booleanOperator op, integer n)
(2)     EVM pSection, qSection;
(3)     EVM couplet;
(4)     boolean fromQ, fromP;
(5)     real coord;
(6)     EVM result, rPrevSection, rCurrSection;
(7)     if n=1 then
(8)       return booleanOperation1D (p,q,op);
(9)     else
(10)pSection ← initEVM ( );
(11)qSection ← initEVM ( );
(12)rCurrSection ← initEVM ( );
(13)        nextObject (p,q,fromP,fromQ);
(14)while  !(endEVM (p))  and  !(endEVM (q))  do
(15)if  fromP  then
(16)couplet ← readCouplet (p);
(17)pSection ← getSection (pSection,couplet);
(18)if  fromQ  then
(19)couplet ← readCouplet (q);
(20)qSection ← getSection (qSection,couplet);
(21)rPrevSection ← rCurrSection
(22)rCurrSection ← booleanOperation (pSection,qSection,op,n-1);
(23)couplet ← getCouplet (rPrevSection, rCurrSection);
(24)        setCoord (couplet, coord);
(25)        putCouplet (couplet, result);
(26)        nextObject (p,q,coord,fromP,fromQ);
(27)while  !endEVM (p)  do
(28)couplet ← readCouplet (p);
(29)        putBool (couplet, result, op);
(30)while  !endEVM (q)  do
(31)couplet ← readCouplet (q);
(32)        putBool (couplet, result, op);
(33)  return result


## 3.3.2. Computing the Content of annD-OPP

As described in [31], we aim to compute the nD content enclosed by an nD-OPP by considering its slices. As we know, a slice is a set of one or more disjoints nD hyperprisms; it has a (n-1)D section as its base and two boundary (n-1)D couplets. Let us take a 3D-OPP p as an example. The content of p can be obtained from the sum of the volumes of its 3D slices. Now, the volume of a Slicekip is given by the product between the area of the 2D section Skip (i.e., the 2D base of the 3D slice) and the distance between its two boundary 2D couplets Φkip and Φk+1ip (it is the height of the 3D slice). Now suppose that we have a 2D-OPP q=Skip which in fact is a 2D section of p and the base of Slicekip. The content of q, its area, is the sum of the areas of the 2D slices that form q. The area of a 2D is given by the product of the length of the 1D section Skiq as its base and the distance between 1D couplets Φkiq and Φk+1iq. In the basic case, for an 1D-OPP r, the content of r is computed as the sum of the lengths of its brinks. Now, the recursive formula for computing the content of a nD-OPP p is the following [31]:(14)Contentnp=Lengthpn=1∑k=1npi-1Contentn-1Skip·DistΦkip,Φk+1ipn>1.Algorithm3 is the implementation for (14). It computes the nD content enclosed by a given nD-OPP that is represented through the nD-EVM.Algorithm 3:Computing the nD content enclosed by a given nD-EVM p.
Input: A nD-EVM p and the number of dimensions n.
Output: The content of the nD space enclosed by p.
(1)ProcedureContent  (nD-EVM p, n)
(2)     contSum ← 0;
/∗ Objects initialization ∗/
(3)     EVM couplet  1, couplet  2;
(4)     EVM section;
(5)     if  n==1  then
(6)     return Length (p);
(7)     couplet  1 ← InitEVM ();
(8)     couplet  2 ← InitEVM ();
(9)     section ← InitEVM ();
(10)couplet  1  ←  readCouplet (p);
(11)while  !endEVM (p)  do
(12)  couplet  2 ← readCouplet (p);
(13)  section ← getSection (section, couplet  1);
(14)  contSum ← contSum + Content (section,n-1) ∗ dist (couplet  1, couplet  2);
(15)  couplet  1 ← couplet  2;
(16)return  contSum


## 3.3.3. Computing the Discrete Compactness Descriptor

TheDiscrete Compactness (DC) descriptor is very useful for characterizing objects considering their similarity with some ideal objects. Moreover, Discrete Compactness improves the classicalShape Compactness descriptor [44, 45].It is important to mention the definition of a hypervoxelization [30, 31], which is the basis for properly establishing the DC descriptor. A hypervoxelization is a Hyperspatial Occupancy Enumeration scheme for polytopes. A hypervoxelization is a list of cells in the Hyperspace occupied by a polytope. These cells are called hypervoxels and they are hyperboxes of a fixed size in the nD space. In this sense, a hypervoxel in the 2D space is a pixel, a 3D hypervoxel is a voxel, and for the 4D space the termrexel is recommended. A collection of hypervoxels is codified as an array Cx1,x2,…,xn of dimensionality n, in which a black (occupied) hypervoxel and a white (unoccupied) hypervoxel are specified when Cx1,x2,…,xn=1 and Cx1,x2,…,xn=0, respectively. A polytope is then defined as a collection of occupied hypervoxels. It is important to note that hypervoxels are in fact disjoint or quasi-disjoint, which means that they do not overlap. The result of the union of all black hypervoxels in a given hypervoxelization describes in fact a nD-OPP p:(15)p=⋃λBlackHypervoxelλ.Considering that from a black nD hypervoxel 2n extreme vertices can be generated, the corresponding nD-EVM representation of p can be obtained as follows:(16)EVMnp=EVMn⋃λBlackHypervoxelλ=⨂λEVMnBlackHypervoxelλ.For computing the DC descriptor it is important to consider that thenD-OPPs were originally expressed as hypervoxelizations where the hypervoxels are hypercubes and their coordinates are integers. In [46, 47] the foundations for computing DC for 2D and 3D objects are presented. In [13] computation for objects in the nD space n≥3 was presented. In any case, formula for DC descriptor is the following:(17)DCp=Lcp-LMinLMax-LMin.Lc(p) is the number of internal contacts for the nD-OPP p. LMin is the minimal number of internal contacts for an ideal nD object with the same content as p. In similar way, LMax is the maximal number of internal contacts for an ideal nD object with the same content as p. The internal contacts for an nD-OPP are the (n-1)D cells that are shared between the nD hypervoxels that originally defined p. LMin and LMax must be specified according to the desired application. For an nD-OPP represented through the nD-EVM, the procedure for computing the internal contacts perpendicular to X1-axis is shown in Algorithm 4. This procedure is described as follows:(i)
We process the slices aligned with respect toX1-axis.(ii)
The number of internalx1-coordinates are obtained for the current slice. This is achieved by obtaining the x1-coordinates c1 and c2 for the bounding couplets of the slice (lines 12 and 13):(18)nCoords=c2-c1-1.(iii)
For every slice the(n-1)D content of the corresponding section Sj is obtained. The internal contacts perpendicular to X1-axis are computed as follows (line 14):(19)IC=nCoords·ContentSj.(iv)
It is considered that there may be contiguous and isolated slices; for this reason we need to obtain the internal contacts between boundaries of consecutive slices. This is achieved by computing the regularized intersection between consecutive sections and then computing the content of the result (lines 15 and 16).Algorithm 4:Computing the (n-1)D adjacencies, shared (n-1)D cells, between the hypervoxels that originally defined to a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The number of internal contacts perpendicular to X1-axis.
(1)ProcedureInternalContacts  (nD-EVM p, n)
(2)     EVM couplet, currentSection, previousSection;
(3)     EVM sectionInt; // Intersection result
(4)     integer c1, c2; // Couplets coordinates
(5)     integer nCoords;
(6)     integer ic←0; // Total internal contacts
(7)     previousSection ← InitEVM ( );
(8)     c1 ← getCoord (p);
(9)     couplet ← readCouplet (p);
(10)   while  !endEVM (p)  do
// Internal contacts for the current slice
(11)currentSection ← getSection (previousSection, couplet);
(12)c2 ← getCoord (p);
(13)nCoords←c2-c1-1;
(14)ic ← ic + nCoords ∗ Content (currentSection, n-1);
// Internal contacts between consecutive slices
(15)sectionInt ← BooleanOperation (previousSection, currentSection, ∩∗, n-1);
(16)ic ← ic + Content (sectionInt, n-1);
(17)previousSection←currentSection;
(18)c1←c2;
(19)couplet ← readCouplet (p);
(20)   return icSince Algorithm4 considers its processes in terms of the first coordinate, it will be required to apply it for every xi-coordinate, 1≤i≤n. At the implementation level, this is easy by reordering the coordinates of the EVM representation as follows:(20)AxisSorting=x1,x2,…,xn-1,xn,x2,x3,…,xn,x1,x3,x4,…,x1,x2,…,xn,x1,…,xn-2,xn-1.In order to compute the total internal contacts it is required to process all the possible axis orderings. In Algorithm 5 the procedure for computing the total internal contacts is shown, in which a new nD-EVM is obtained from a different axis ordering in line 5. In line 6 the cumulative sum of the total internal contacts is performed.Algorithm 5:Computing the total internal contacts, Lc(p), for a given nD-OPP p.
Input: A nD-EVM p and the number of dimensions n.
Output: The total number of internal contacts for the hyper-boxes of a given nD-EVM
(1)ProcedureTotalInternalContacts  (nD-EVM p, n)
(2)     integer ic←0; // Total internal contacts
(3)     EVM SortedP;
(4)     for each sorting ∈AxisSorting  do
(5)       SortedP←sortEVM (p, n, sorting);
(6)       ic← ic+ InternalContacts (SortedP,n);
(7)     return  icBefore computing the DC descriptor for a givennD-OPP p it is important to define the application context. So, it is required to provide the two nD-OPPs pl and pu which represent the ideal objects against all the pertinent nD-OPPs that will be compared. Once those bounds have been defined, we compute via Algorithm 5 the minimum and maximum internal contacts as follows:(21)LMin=TotalInternalContactspl,n,LMax=TotalInternalContactspu,n.Lc(p) is the number of total internal contacts for p, and finally the DC descriptor is computed using (17).


## 4. Video Processing with thenD-EVM Model and Self-Organizing Maps

In this section we present the foundations for our proposed framework. Summarizing, the framework is composed by four stages.Stage 1. Representation of a frame sequence: it is defined as the workflow for representing a given frame sequence in the nD-EVM.Stage 2. Subanimations extraction: it aims to obtain nD-EVMs that contain small portions of the animation.Stage 3. Computing the DC descriptor for every subanimation: a set that contains all the DC values is formed.Stage 4. Subanimations clustering using a SOM approach: the subanimations are grouped into m clusters. As a result we obtain m 3D-EVMs Pc, 1≤c≤m, one for each cluster.


### 4.1. Representation of Frame Sequences

For this stage it is considered that the frames are given in a plain image format, in this particular case the BMP image format. At first, each image defines a 2D rectangular region, the lengths are specified as thewidth andheight of the frame, and for the color extrusion the color scheme plays an important role. The amount of color components in the color scheme establishes the additional dimensions for the polytopes’ dimensionality.There are many color schemes, for example, grayscale, RGB, RGBA, or CMYK. The grayscale scheme only specifies one color component, which means that to represent a frame this would be achieved with a 3D-OPP. On the other hand, a frame in a RGB color scheme is represented through a 5D-OPP.Figure4 is an example of a grayscale frame 3D representation; the original frame is shown in Figure 4(a). Figure 4(b) illustrates its color extrusion towards the third dimension through a software designed specifically for 3D-EVM edition and visualization [48, 49].Figure 4
An example of color component extrusion.
(a)
Grayscale frame example
(b)
3D extrusionThe representation of a frame sequence in thenD-EVM model is called anEVM-animation. For an EVM-animation it is considered one additional dimension for the time in which the frames are sorted. Therefore, a RGB frame sequence is represented through a 6D-EVM. Algorithm 6 provides a generic procedure for generating an EVM-animation from a frame sequence.Algorithm 6:Generating an EVM-animation in the nD-EVM from a frame sequence.
Input: The path of the frames and time positions for initial and final frame.
(1)ProceduregenerateAnimation  (String workingDirectory, integer initFrame, integer endFrame)
(2)     EVM currentFrame, prevFrame, diffFrame;
(3)     string framePath;
(4)     prevFrame ← initEVM ( );
(5)     currentFrame ← initEVM ( );
(6)     for  i = initFrame  to  endFrame  do
(7)       currentFrame ← initEVM ( );
(8)       framePath ← workingDirectory + “frame” + toString (i) + “.image”;
(9)       currentFrame ← loadImage (framePath);
(10)     diffFrame ← getCouplet (prevFrame, currentFrame);
(11)     saveEVM (diffFrame, i);
(12)     prevFrame ← currentFrame;
(13)     saveEVM (prevFrame, endFrame + 1);The workflow for Algorithm6 is described as follows:(i)
For every frame its EVM representation is obtained.(ii)
Later, the differences are computed between consecutive frames. These differences are by instance expressed as a couplet. By this way the couplets’ projections are obtained.Algorithm6 indicates that only the couplets will be stored. The reason for this is because they have less information than sections (the frames themselves), and the original frames can be retrieved using Algorithm 1.As we can see in Algorithm6, the functionloadImage is required which builds the extrusion of the frame and returns its EVM representation. This function performs a double iteration for retrieving information from every pixel from the frame. Algorithm 7 shows the generic procedure for obtaining the extrusion of a frame.Algorithm 7:Algorithm for converting a frame to a EVM object.
Input: The frame file path.
Output: An EVM that is an extrusion for the input frame.
(1)ProcedureloadImage  (string imagePath)
(2)      EVM p // The resulting EVM.
(3)      ImageData imageData;
(4)      integer colorCount;
(5)      integer array hyperPrismBase, hyperPrismLengths;
(6)      p ← InitEVM ( );
(7)      imageData ← readImageData (imagePath);
(8)      colorCount ← imageData.colors;
/∗ Initialize the hyper-prism base and lengths ∗/
(9)      for  k=0  to  (colorCount − 1)  do
(10)        hyperPrismBase [2+k]←0;
(11)      hyperPrismLengths [0]←1;
(12)      hyperPrismLengths [1]←1;
(13)      for  i=0  to  (imageData.height − 1)  do
(14)        hyperPrismBase [1]←i;
(15)        for  j=0  to  (imageData.width − 1)  do
(16)         hyperPrismBase [0]←j;
/∗ Get every color component for the current pixel. ∗/
(17)       fork=0to (colorCount −1)  do
(18)           hyperPrismLengths[2+k] ← imageData.pixelData (i,j).color (k);
(19)         populateHyperPrism (p, hyperPrismBase, 2 +colorCount, 0, hyperPrismLengths);
(20)      return pIn the context of an extrusion, for every pixel of a frame a hyperprism whose base is built on the 2D coordinates of the pixel and the color components to zero is obtained (or the lowest value allowed). Therefore, as shown in Algorithm7, two arrays are defined,hyperPrismBase andhyperPrismLengths (line 5). Their purpose is to store the hyperprism initial coordinate (lines 9, 10, 14, and 16) and lengths (lines 11, 12, and 18), respectively. The lengths for the color components are equal to the pixel color information. These arrays are later sent as input to thepopulateHyperPrism function (line 19) which performs the hyperprism population based in the pixel position and color information. For each hyperprism in the nD space it is possible to generate 2n vertices, which are indeed extreme vertices. In this sense the final EVM for the given frame consists of the union of all the hyperprisms obtained from it. In this sense, it is important to note that all the hyperprisms are disjoint or quasi-disjoint; this means that they do not overlap. As described in [30, 31], when having two nD-OPPs p and q with those properties, considering their respective EVM representation, EVMn(p∪q)=EVMn(p)⊗EVMn(q).In Algorithm8 the procedure for obtaining a nD hyperprism fromhyperPrismBase andhyperPrismLengths arrays is shown. The functioninsertVertex tries to insert a vertex from the current hyperprism to EVM p. In case the vertex does not exist, then it is inserted to p; otherwise it deletes the vertex from p. This functionality provides the same behavior as the XOR operator, because it removes common vertices.Algorithm 8:Algorithm to populate the hyperprism from the hyperPrismBase and hyperPrismLengths arrays.
Input: The nD-EVM p, the hyperprism base and lengths, current the number of dimensions,
and the number of dimensions.
(1)ProcedurepopulateHyperPrism  (nD-EVM p, integer array hyperPrismBase, integer dimensions, integer currentDim,
integer arrayhyperPrismLengths)
(2)   if !(currentDim < dimensions) then
(3)    insertVertex (p, hyperPrismBase, dimensions);
(4)     return;
(5)   populateHyperPrism (p, hyperPrismBase, dimensions, currentDim + 1, hyperPrismLengths);
(6)   hyperPrismBase [currentDim] ← hyperPrismBase [currentDim] + hyperPrismLengths[currentDim];
(7)   populateHyperPrism (p, hyperPrismBase, dimensions, currentDim + 1, hyperPrismLengths);
(8)   hyperPrismBase [currentDim] ← hyperPrismBase [currentDim] – hyperPrismLengths [currentDim];Considering an example of representing a video with a grayscale color scheme, in Figure5 the resulting 3D couplet computed from the difference of two consecutive frames is shown.Figure 5
Computing a couplet from two consecutive frames.
(a)
First frame
(b)
Second frame
(c)
Couplet


### 4.2. Extraction of Subanimations

We know now an EVM-animation is a frame sequence represented through the EVM model. Moreover, we have stated a subanimation is a small portion from the original EVM-animation. In order to extract a subanimation we are going to use amask. In the image processing field, a mask is a small 2D region of fixed size, which is used for obtaining or changing information of an image [34]. This is achieved by exploring, with the mask, all possible regions in the image and obtaining the pixels’ information or performing the corresponding operations. Image filters are well-known examples of operators that make use of masks.In this work, we understand a mask is a small EVM-animation that has a fixed 2D base, a set of dimensions depending on the color scale, and a temporal dimension. That is, dimensionality of the mask is the same as the original EVM-animation. More specifically, due to the operations to be performed, color values for the mask are set to the maximum level. In the RGB context, this configuration corresponds to an EVM-animation where all frames have white color. For generating a mask’s EVM representation Algorithm8 is applied by providing it the initial coordinate and the mask’s corresponding lengths for each dimension. Once the mask has been configured and generated, for extracting a subanimation from the original one, the Regularized Intersection Operation between both EVM representations is performed: the EVM-animation and the mask.We exemplify the above procedure by assuming a given EVM-animation can be represented through an 3D-OPP; hence, its frames and couplets are represented through 2D-EVMs. Figure6 presents an EVM-animation with these properties. A mask placed in some location inside the EVM-animation is also shown. Under this scenario we can see a subanimation can be considered as an OPP that contains the changes through time of a small 2D region of some consecutive frames. For obtaining all possible subanimations, there are performed shifts on the EVM-animation’s possible coordinates x1, x2, and t.Figure 6
Example of an EVM-animation and a mask for subanimation extraction.


### 4.3. Computing the DC Descriptor for Subanimations

In order to differentiate the subanimations the DC descriptor is computed for each one. As explained in Section3.3.3, it is required to provide a pair of bounds for DC descriptor (see (17)). These bounds are set as follows:(i)
LMax is obtained directly from the mask to be utilized, where all color components are set to their maximum values.(ii)
LMin is computed from a mask with a similar configuration as the previous one. The difference lies in the color components’ values. They are set to the minimum possible values. For example, under the RGB color scheme we assign color values such that the mask refers to an animation with black frames.Now, we proceed to generate the training set for the SOM clustering. That set contains all DC values for every subanimation. This set is calledDCValues and its generation is based on the following steps:(i)
An iteration is performed over all thex1 and x2 coordinates covered by the original EVM-animation. This is analogous to the exploration of all pixels in an image. In our specific case, the exploration is performed by applying unitary shifts on the original mask.(ii)
Once the previous iteration has finished, a unit shift on the temporal dimension is applied, and the previous step is performed again. Time shifts are performed until all temporal coordinates covered by the EVM-animation have been processed.(iii)
For every subanimation obtained in the previous steps, its corresponding DC descriptor is computed.The elements of setDCValues are organized as follows:(22)DCValues=maskDC0,1maskDC0,2⋯maskDC0,imaskDC1,1maskDC1,2⋯maskDC1,i⋮maskDCτ,1maskDCτ,2⋯maskDCτ,i,where(i)
τ denotes temporal position of subanimation maskDCτ,i. The maximum temporal position depends on the original EVM-animation’s frames count and the mask’s temporal length. Hence τ=0,1,…,(endFrame-mask.timeLength+1),(ii)
indexi is assigned to every subanimation such that when a time shift is applied then i is set to zero in order to count subanimations associated with the new temporal coordinate. Therefore, index i is bounded as follows:(23)i=0,1,…,maxXShift·maxYShift,where (24)maxXShift=frame.width-mask.xLength+1,maxYShift=frame.length-mask.yLength+1.As previously commented, this process is similar to a convolution because we iterate over every shift that can be applied to the mask for subanimation extraction. Algorithm9 presents the generic for performing our proposed convolution process in order to build setDCValues from a given EVM-animation. The main flow of Algorithm 9 is described as follows:(i)
In lines 2–9 the variables initialization is performed.(ii)
The functionmaskAnimSections (lines 10 and 30) obtains an EVM-animation that contains only the frames (sections) that are currently intersected by the mask in its current position. As can be observed in lines 10 and 30, these frames are stored in variableframeSeq. By this way, the Regularized Intersection Operation is improved because it will not be required to compute all previous, and unused, sections just like the classical Boolean Operations Algorithm (see Algorithm 2).(iii)
The exploration of the EVM-animation, overX1-, X2-, and t-axis, is performed by means of the iterative while structures are specified in lines 15, 16, and 17.(iv)
In line 18 the Regularized Intersection Operation is performed between the current mask and the EVM-animation stored in theframeSeq object. As can be noted, the intersection operation is performed by using the functionmaskIntersection, which is a modified version of Algorithm 2. As mentioned before, with this function the intersection operation is improved in temporal terms because it does not require to compute all the previous sections in the original EVM-animation.(v)
In line 19 the DC descriptor for the current subanimation is computed. By this way setDCValues is being formed which contains DC values for each subanimation (line 20).(vi)
At lines 23, 26, and 31 the mask shifts for each axis are performed.(vii)
Finally, the final setDCValues is returned as output.Algorithm 9:Algorithm for the convolution process to generate set DCValues.
Input: The nD-EVM for the mask, temporal position of the final frame, and the width and height of the frame.
Output: The DCValues set that contains the values of DC descriptor for every possible sub-animation.
(1)ProcedureAnimConv  (nD-EVM mask, integer endFrame, integer width, integer length)
(2)   EVM currentResult; // Current intersection result
(3)   EVM frameSeq;
(4)   integer τ←0, maxTimeShift;
(5)   integer x←0, maxXShift;
(6)   integer y←0, maxYShift;
(7)   real maskDC;
(8)   Set of reals DCValues;
(9)   integer i←0; // Counter for every time shift.
/∗ Obtaining the frame sequence required for the intersection operation. ∗/
(10)frameSeq ←  maskAnimSections (mask, endFrame);
/∗ Obtaining the maximum shift for the time, X and Y dimensions. ∗/
(11)maxTimeShift ← endFrame − mask.timeLength +1;
(12)maxXShift ← width − mask.xLength +1;
(13)maxYShift ← length − mask.yLength +1;
(14)DCValues←⌀;
(15)while τ≤maxTimeShift do
(16)  while y ≤ maxYShift do
(17)    while x ≤ maxXShift do
(18)      currentResult ← maskIntersection (mask, frameSeq);
(19)      maskDCτ,i ← discreteCompactness (currentResult, mask.LcMin, mask.LcMax);
(20)      DCValues.addDCValue (maskDCτ,i);
(21)      mask.EVMTraslation (1, 1);
(22)      i←i+1;
(23)      x←x+1;
(24)    mask.dimReset (1);
(25)    mask.EVMTraslation (2, 1);
(26)    y←y+1;
(27)    x←0;
(28)  mask.dimReset (2);
(29)  mask.EVMTraslation (0,1);
(30)  frameSeq ← maskAnimSections (mask, endFrame);
(31)  τ←τ+1;
(32)  y←0;
(33)  i←0;
(34)return DCValues


### 4.4. Subanimations Clustering Using the SOM Approach

According to the SOM’s training stage described in Section2, in first place the training set’s presentations are performed to the network. Later, when the training stage has been achieved, another presentation is performed for obtaining the corresponding winning neuron for every subanimation. For a subanimation, the winning neuron gives thecluster number which it belongs to. Let us suppose that we have m neurons; therefore we obtain m clusters clusterj, j=1,2,…,m. A given clusterj will contain the indexes of the subanimations for which j is the corresponding winning neuron:(25)clusterj=τ,i:maskDCτ,i∈DCValues,minDistanceNeuronmaskDCτ,i=j.As can be seen, the clusters only contain indexes for their associated subanimations. In fact, in this stage such indexes are important because they are required for identifying all the subanimations that are going to be used in order to get the whole subanimation of a given cluster. By the way, a 3D-OPP is obtained for every cluster, which contains only the regions, with no color information, that are grouped in a given cluster. These 3D-OPPs consider only original X1- and X2-axis and also the temporal dimension. Nevertheless it is possible to query the original EVM-animation for obtaining the original color information for those regions.


## 4.1. Representation of Frame Sequences

For this stage it is considered that the frames are given in a plain image format, in this particular case the BMP image format. At first, each image defines a 2D rectangular region, the lengths are specified as thewidth andheight of the frame, and for the color extrusion the color scheme plays an important role. The amount of color components in the color scheme establishes the additional dimensions for the polytopes’ dimensionality.There are many color schemes, for example, grayscale, RGB, RGBA, or CMYK. The grayscale scheme only specifies one color component, which means that to represent a frame this would be achieved with a 3D-OPP. On the other hand, a frame in a RGB color scheme is represented through a 5D-OPP.Figure4 is an example of a grayscale frame 3D representation; the original frame is shown in Figure 4(a). Figure 4(b) illustrates its color extrusion towards the third dimension through a software designed specifically for 3D-EVM edition and visualization [48, 49].Figure 4
An example of color component extrusion.
(a)
Grayscale frame example
(b)
3D extrusionThe representation of a frame sequence in thenD-EVM model is called anEVM-animation. For an EVM-animation it is considered one additional dimension for the time in which the frames are sorted. Therefore, a RGB frame sequence is represented through a 6D-EVM. Algorithm 6 provides a generic procedure for generating an EVM-animation from a frame sequence.Algorithm 6:Generating an EVM-animation in the nD-EVM from a frame sequence.
Input: The path of the frames and time positions for initial and final frame.
(1)ProceduregenerateAnimation  (String workingDirectory, integer initFrame, integer endFrame)
(2)     EVM currentFrame, prevFrame, diffFrame;
(3)     string framePath;
(4)     prevFrame ← initEVM ( );
(5)     currentFrame ← initEVM ( );
(6)     for  i = initFrame  to  endFrame  do
(7)       currentFrame ← initEVM ( );
(8)       framePath ← workingDirectory + “frame” + toString (i) + “.image”;
(9)       currentFrame ← loadImage (framePath);
(10)     diffFrame ← getCouplet (prevFrame, currentFrame);
(11)     saveEVM (diffFrame, i);
(12)     prevFrame ← currentFrame;
(13)     saveEVM (prevFrame, endFrame + 1);The workflow for Algorithm6 is described as follows:(i)
For every frame its EVM representation is obtained.(ii)
Later, the differences are computed between consecutive frames. These differences are by instance expressed as a couplet. By this way the couplets’ projections are obtained.Algorithm6 indicates that only the couplets will be stored. The reason for this is because they have less information than sections (the frames themselves), and the original frames can be retrieved using Algorithm 1.As we can see in Algorithm6, the functionloadImage is required which builds the extrusion of the frame and returns its EVM representation. This function performs a double iteration for retrieving information from every pixel from the frame. Algorithm 7 shows the generic procedure for obtaining the extrusion of a frame.Algorithm 7:Algorithm for converting a frame to a EVM object.
Input: The frame file path.
Output: An EVM that is an extrusion for the input frame.
(1)ProcedureloadImage  (string imagePath)
(2)      EVM p // The resulting EVM.
(3)      ImageData imageData;
(4)      integer colorCount;
(5)      integer array hyperPrismBase, hyperPrismLengths;
(6)      p ← InitEVM ( );
(7)      imageData ← readImageData (imagePath);
(8)      colorCount ← imageData.colors;
/∗ Initialize the hyper-prism base and lengths ∗/
(9)      for  k=0  to  (colorCount − 1)  do
(10)        hyperPrismBase [2+k]←0;
(11)      hyperPrismLengths [0]←1;
(12)      hyperPrismLengths [1]←1;
(13)      for  i=0  to  (imageData.height − 1)  do
(14)        hyperPrismBase [1]←i;
(15)        for  j=0  to  (imageData.width − 1)  do
(16)         hyperPrismBase [0]←j;
/∗ Get every color component for the current pixel. ∗/
(17)       fork=0to (colorCount −1)  do
(18)           hyperPrismLengths[2+k] ← imageData.pixelData (i,j).color (k);
(19)         populateHyperPrism (p, hyperPrismBase, 2 +colorCount, 0, hyperPrismLengths);
(20)      return pIn the context of an extrusion, for every pixel of a frame a hyperprism whose base is built on the 2D coordinates of the pixel and the color components to zero is obtained (or the lowest value allowed). Therefore, as shown in Algorithm7, two arrays are defined,hyperPrismBase andhyperPrismLengths (line 5). Their purpose is to store the hyperprism initial coordinate (lines 9, 10, 14, and 16) and lengths (lines 11, 12, and 18), respectively. The lengths for the color components are equal to the pixel color information. These arrays are later sent as input to thepopulateHyperPrism function (line 19) which performs the hyperprism population based in the pixel position and color information. For each hyperprism in the nD space it is possible to generate 2n vertices, which are indeed extreme vertices. In this sense the final EVM for the given frame consists of the union of all the hyperprisms obtained from it. In this sense, it is important to note that all the hyperprisms are disjoint or quasi-disjoint; this means that they do not overlap. As described in [30, 31], when having two nD-OPPs p and q with those properties, considering their respective EVM representation, EVMn(p∪q)=EVMn(p)⊗EVMn(q).In Algorithm8 the procedure for obtaining a nD hyperprism fromhyperPrismBase andhyperPrismLengths arrays is shown. The functioninsertVertex tries to insert a vertex from the current hyperprism to EVM p. In case the vertex does not exist, then it is inserted to p; otherwise it deletes the vertex from p. This functionality provides the same behavior as the XOR operator, because it removes common vertices.Algorithm 8:Algorithm to populate the hyperprism from the hyperPrismBase and hyperPrismLengths arrays.
Input: The nD-EVM p, the hyperprism base and lengths, current the number of dimensions,
and the number of dimensions.
(1)ProcedurepopulateHyperPrism  (nD-EVM p, integer array hyperPrismBase, integer dimensions, integer currentDim,
integer arrayhyperPrismLengths)
(2)   if !(currentDim < dimensions) then
(3)    insertVertex (p, hyperPrismBase, dimensions);
(4)     return;
(5)   populateHyperPrism (p, hyperPrismBase, dimensions, currentDim + 1, hyperPrismLengths);
(6)   hyperPrismBase [currentDim] ← hyperPrismBase [currentDim] + hyperPrismLengths[currentDim];
(7)   populateHyperPrism (p, hyperPrismBase, dimensions, currentDim + 1, hyperPrismLengths);
(8)   hyperPrismBase [currentDim] ← hyperPrismBase [currentDim] – hyperPrismLengths [currentDim];Considering an example of representing a video with a grayscale color scheme, in Figure5 the resulting 3D couplet computed from the difference of two consecutive frames is shown.Figure 5
Computing a couplet from two consecutive frames.
(a)
First frame
(b)
Second frame
(c)
Couplet


## 4.2. Extraction of Subanimations

We know now an EVM-animation is a frame sequence represented through the EVM model. Moreover, we have stated a subanimation is a small portion from the original EVM-animation. In order to extract a subanimation we are going to use amask. In the image processing field, a mask is a small 2D region of fixed size, which is used for obtaining or changing information of an image [34]. This is achieved by exploring, with the mask, all possible regions in the image and obtaining the pixels’ information or performing the corresponding operations. Image filters are well-known examples of operators that make use of masks.In this work, we understand a mask is a small EVM-animation that has a fixed 2D base, a set of dimensions depending on the color scale, and a temporal dimension. That is, dimensionality of the mask is the same as the original EVM-animation. More specifically, due to the operations to be performed, color values for the mask are set to the maximum level. In the RGB context, this configuration corresponds to an EVM-animation where all frames have white color. For generating a mask’s EVM representation Algorithm8 is applied by providing it the initial coordinate and the mask’s corresponding lengths for each dimension. Once the mask has been configured and generated, for extracting a subanimation from the original one, the Regularized Intersection Operation between both EVM representations is performed: the EVM-animation and the mask.We exemplify the above procedure by assuming a given EVM-animation can be represented through an 3D-OPP; hence, its frames and couplets are represented through 2D-EVMs. Figure6 presents an EVM-animation with these properties. A mask placed in some location inside the EVM-animation is also shown. Under this scenario we can see a subanimation can be considered as an OPP that contains the changes through time of a small 2D region of some consecutive frames. For obtaining all possible subanimations, there are performed shifts on the EVM-animation’s possible coordinates x1, x2, and t.Figure 6
Example of an EVM-animation and a mask for subanimation extraction.


## 4.3. Computing the DC Descriptor for Subanimations

In order to differentiate the subanimations the DC descriptor is computed for each one. As explained in Section3.3.3, it is required to provide a pair of bounds for DC descriptor (see (17)). These bounds are set as follows:(i)
LMax is obtained directly from the mask to be utilized, where all color components are set to their maximum values.(ii)
LMin is computed from a mask with a similar configuration as the previous one. The difference lies in the color components’ values. They are set to the minimum possible values. For example, under the RGB color scheme we assign color values such that the mask refers to an animation with black frames.Now, we proceed to generate the training set for the SOM clustering. That set contains all DC values for every subanimation. This set is calledDCValues and its generation is based on the following steps:(i)
An iteration is performed over all thex1 and x2 coordinates covered by the original EVM-animation. This is analogous to the exploration of all pixels in an image. In our specific case, the exploration is performed by applying unitary shifts on the original mask.(ii)
Once the previous iteration has finished, a unit shift on the temporal dimension is applied, and the previous step is performed again. Time shifts are performed until all temporal coordinates covered by the EVM-animation have been processed.(iii)
For every subanimation obtained in the previous steps, its corresponding DC descriptor is computed.The elements of setDCValues are organized as follows:(22)DCValues=maskDC0,1maskDC0,2⋯maskDC0,imaskDC1,1maskDC1,2⋯maskDC1,i⋮maskDCτ,1maskDCτ,2⋯maskDCτ,i,where(i)
τ denotes temporal position of subanimation maskDCτ,i. The maximum temporal position depends on the original EVM-animation’s frames count and the mask’s temporal length. Hence τ=0,1,…,(endFrame-mask.timeLength+1),(ii)
indexi is assigned to every subanimation such that when a time shift is applied then i is set to zero in order to count subanimations associated with the new temporal coordinate. Therefore, index i is bounded as follows:(23)i=0,1,…,maxXShift·maxYShift,where (24)maxXShift=frame.width-mask.xLength+1,maxYShift=frame.length-mask.yLength+1.As previously commented, this process is similar to a convolution because we iterate over every shift that can be applied to the mask for subanimation extraction. Algorithm9 presents the generic for performing our proposed convolution process in order to build setDCValues from a given EVM-animation. The main flow of Algorithm 9 is described as follows:(i)
In lines 2–9 the variables initialization is performed.(ii)
The functionmaskAnimSections (lines 10 and 30) obtains an EVM-animation that contains only the frames (sections) that are currently intersected by the mask in its current position. As can be observed in lines 10 and 30, these frames are stored in variableframeSeq. By this way, the Regularized Intersection Operation is improved because it will not be required to compute all previous, and unused, sections just like the classical Boolean Operations Algorithm (see Algorithm 2).(iii)
The exploration of the EVM-animation, overX1-, X2-, and t-axis, is performed by means of the iterative while structures are specified in lines 15, 16, and 17.(iv)
In line 18 the Regularized Intersection Operation is performed between the current mask and the EVM-animation stored in theframeSeq object. As can be noted, the intersection operation is performed by using the functionmaskIntersection, which is a modified version of Algorithm 2. As mentioned before, with this function the intersection operation is improved in temporal terms because it does not require to compute all the previous sections in the original EVM-animation.(v)
In line 19 the DC descriptor for the current subanimation is computed. By this way setDCValues is being formed which contains DC values for each subanimation (line 20).(vi)
At lines 23, 26, and 31 the mask shifts for each axis are performed.(vii)
Finally, the final setDCValues is returned as output.Algorithm 9:Algorithm for the convolution process to generate set DCValues.
Input: The nD-EVM for the mask, temporal position of the final frame, and the width and height of the frame.
Output: The DCValues set that contains the values of DC descriptor for every possible sub-animation.
(1)ProcedureAnimConv  (nD-EVM mask, integer endFrame, integer width, integer length)
(2)   EVM currentResult; // Current intersection result
(3)   EVM frameSeq;
(4)   integer τ←0, maxTimeShift;
(5)   integer x←0, maxXShift;
(6)   integer y←0, maxYShift;
(7)   real maskDC;
(8)   Set of reals DCValues;
(9)   integer i←0; // Counter for every time shift.
/∗ Obtaining the frame sequence required for the intersection operation. ∗/
(10)frameSeq ←  maskAnimSections (mask, endFrame);
/∗ Obtaining the maximum shift for the time, X and Y dimensions. ∗/
(11)maxTimeShift ← endFrame − mask.timeLength +1;
(12)maxXShift ← width − mask.xLength +1;
(13)maxYShift ← length − mask.yLength +1;
(14)DCValues←⌀;
(15)while τ≤maxTimeShift do
(16)  while y ≤ maxYShift do
(17)    while x ≤ maxXShift do
(18)      currentResult ← maskIntersection (mask, frameSeq);
(19)      maskDCτ,i ← discreteCompactness (currentResult, mask.LcMin, mask.LcMax);
(20)      DCValues.addDCValue (maskDCτ,i);
(21)      mask.EVMTraslation (1, 1);
(22)      i←i+1;
(23)      x←x+1;
(24)    mask.dimReset (1);
(25)    mask.EVMTraslation (2, 1);
(26)    y←y+1;
(27)    x←0;
(28)  mask.dimReset (2);
(29)  mask.EVMTraslation (0,1);
(30)  frameSeq ← maskAnimSections (mask, endFrame);
(31)  τ←τ+1;
(32)  y←0;
(33)  i←0;
(34)return DCValues


## 4.4. Subanimations Clustering Using the SOM Approach

According to the SOM’s training stage described in Section2, in first place the training set’s presentations are performed to the network. Later, when the training stage has been achieved, another presentation is performed for obtaining the corresponding winning neuron for every subanimation. For a subanimation, the winning neuron gives thecluster number which it belongs to. Let us suppose that we have m neurons; therefore we obtain m clusters clusterj, j=1,2,…,m. A given clusterj will contain the indexes of the subanimations for which j is the corresponding winning neuron:(25)clusterj=τ,i:maskDCτ,i∈DCValues,minDistanceNeuronmaskDCτ,i=j.As can be seen, the clusters only contain indexes for their associated subanimations. In fact, in this stage such indexes are important because they are required for identifying all the subanimations that are going to be used in order to get the whole subanimation of a given cluster. By the way, a 3D-OPP is obtained for every cluster, which contains only the regions, with no color information, that are grouped in a given cluster. These 3D-OPPs consider only original X1- and X2-axis and also the temporal dimension. Nevertheless it is possible to query the original EVM-animation for obtaining the original color information for those regions.


## 5. Segmentation Results

In this section we are going to verify that our proposed framework achieves its main objective: to obtain segmented and concise versions from the original EVM-animation. For this purpose we have run some tests and we present a description of the results. In all our tests the configuration of the mask consists in a 2D region of size 3 × 3 and 3 frames as the time length.


### 5.1. Tests for a Traffic Control Video Sequence

We analyze segmentation results for a traffic control video sequence taken from [50]. It consists in a static camera pointing to the center of a highway. Figure 7 shows some selected frames from this video sequence. As can be observed, the scene contains the movement of cars along the highway while at left and right sides green zones are found. The frames of this video sequence have a size of 160 × 120 pixels, and we have 60 consecutive frames at a rate of 20 frames per second. For this case, the frame sequence was represented in an EVM-animation that consists of a 6D-EVM with a total of 17,058,774 extreme vertices. The SOM’s tested configurations were 5 and 15 neurons. In both cases the training stage executed 200 iterations. The results are analyzed in the following subsections.Figure 7
Some frames of the traffic control video sequence.


#### 5.1.1. Results for 5 Neurons

In Table1 the sizes of every 3D-EVM are shown associated with every cluster. It can be observed that we have a total of 80,128 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 212.89. In Figure 8 the quantity of subanimations grouped in each cluster is presented.Table 1
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons.
Class
EVM size
0
28,968
1
1,528
2
24,674
3
6,308
4
18,650
Total
80,128Figure 8
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 5 neurons.Now we describe some information contained in clusters 0, 2, and 4:(i)
For cluster 0 its frame sequence is shown in Figure9. It can be observed that it grouped information related to dark regions of the highway and also contains movement of the cars. In Figure 10 the 3D-OPP can be observed generated for cluster 0. In this 3D-OPP the temporal evolution of the highway’s grouped regions can be appreciated.(ii)
Figure11 presents the frame sequence obtained for cluster 2. As can be observed, the brighter regions of the highway are grouped as well as the movement of the cars that take place in those regions. In Figure 12 the 3D-OPP is shown generated for cluster 2. In it, the regions can be seen grouped for the highway, the movement of the cars, and the evolution of those regions across time.(iii)
For cluster 4 we present the frame sequence shown in Figure13. This cluster contains important information because we can observe only the movement of the cars on the highway. This implies the SOM captured movement patterns and tried to separate them in a single cluster. Nevertheless, it also groups information of the highway’s green zones. This is because they have some similarities with the cars’ shadows in the sense that they are dark regions. In Figure 14 the 3D-OPP associated with cluster 4 is shown. In this OPP clearly we can observe regions correspondent to the movement of the cars across the time axis.Figure 9
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 0.Figure 10
3D-OPP associated with cluster 0: traffic control video sequence and 5 neurons.Figure 11
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 2.Figure 12
3D-OPP associated with cluster 2: traffic control video sequence and 5 neurons.Figure 13
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 4.Figure 14
3D-OPP associated with cluster 4: traffic control video sequence and 5 neurons.


#### 5.1.2. Results for 15 Neurons

In Table2 the sizes of every 3D-EVM associated with every cluster are shown. We have a total of 206,140 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 82.75. In Figure 15 the quantity of subanimations grouped in each cluster is presented.Table 2
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons.
Class
EVM size
0
176
1
38,826
2
8,560
3
15,116
4
3,070
5
23,346
6
1,408
7
8,352
8
33,272
9
45,096
10
496
11
0
12
0
13
4,796
14
23,626
Total
206,140Figure 15
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 15 neurons.We present a brief description of information contained in clusters 1, 5, and 9:(i)
For cluster 1, in Figure16, its frame sequence is shown. It is observed that this cluster groups darker regions of the highway and also the movements of cars which take place in such regions. Now, the corresponding 3D-OPP is shown in Figure 17. It is possible to observe the movement of the cars, the abovementioned darker regions, and their evolution across the temporal dimension.(ii)
In the case of cluster 5 see Figure18 for its frame sequence. As can be observed, for this cluster the SOM has provided a proper separation of the movement of the cars. In Figure 19 the 3D-OPP is shown formed with all the subanimations grouped. Clearly, we can observe the movement of cars in the center of the highway. There are also grouped regions from green zones because they are also dark zones.(iii)
The last cluster to be described is number 9. Its frame sequence is shown in Figure20, where we can observe that it groups the brighter regions of the highway and also grouped the movement of the cars that takes place in those zones. In Figure 21 the corresponding 3D-OPP is shown.Figure 16
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 1.Figure 17
3D-OPP associated with cluster 1: traffic control video sequence and 15 neurons.Figure 18
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 5.Figure 19
3D-OPP associated with cluster 5: traffic control video sequence and 15 neurons.Figure 20
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 9.Figure 21
3D-OPP associated with cluster 9: traffic control video sequence and 15 neurons.


### 5.2. Tests for a Billiard Game Video Sequence

Now we proceed to analyze segmentation results for a video sequence that consists in a game of a professional billiard player [51]. This video is a capture of a single play. Figure 22 shows some selected frames from this video sequence. The frames of this video sequence have a size of 240 × 160 pixels, and we have 48 consecutive frames under RGB color model. For this case, the frame sequence was represented as an EVM-animation that consists of a 6D-EVM with a total of 22,076,702 extreme vertices. The SOM’s tested configurations were 10 and 15 neurons. In both cases the training stage executed 200 iterations. The results are analyzed in the following subsections.Figure 22
Some frames for the Billiard Game Video Sequence.


#### 5.2.1. Results for 10 Neurons

In Table3 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 76,754 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 287.62. In Figure 23 the quantity of subanimations grouped in each cluster is presented.Table 3
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 10 neurons.
Class
EVM size
0
2,352
1
10,364
2
13,604
3
866
4
4,434
5
4,552
6
6,614
7
18,520
8
14,194
9
1,254
Total
76,754Figure 23
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 10 neurons.Now we provide a brief description of the information contained in clusters 1, 4, and 6:(i)
Cluster 1 has the frame sequence shown in Figure24. It contains regions corresponding to the borders of the elements present in the scene. In Figure 25 the 3D-OPP can be seen associated with the current cluster. In such OPP we can clearly observe the borders previously mentioned and also their evolution along the temporal dimension can be seen.(ii)
Cluster 4 contains the frame sequence that is shown in Figure26. It can be observed that it groups the regions corresponding to the movement of the billiard balls. In this case, the SOM has been able to distinguish movement patterns. In Figure 27 the 3D-OPP for cluster 4 can be observed. In it, we can clearly note the regions of the movement of the billiard balls.(iii)
Cluster 6 has the frame sequence shown in Figure28. We can observe it also groups regions related to the billiard balls movements, but in this case it also groups other small bright regions from the scene. Nevertheless, this cluster also captures the dynamic of the movement of the balls. In Figure 29 the 3D-OPP can be observed for the current cluster. Clearly, we can note the regions of the movement of the billiard balls and the bright regions mentioned before.Figure 24
Grouping results for cluster 1: billiard video sequence and 10 neurons.Figure 25
3D-OPP for cluster 1 of the billiard video sequence and 10 neurons.Figure 26
Grouping results for cluster 4: billiard video sequence and 10 neurons.Figure 27
3D-OPP for cluster 4 of the billiard video sequence and 10 neurons.Figure 28
Grouping results for cluster 6: billiard video sequence and 10 neurons.Figure 29
3D-OPP for cluster 6 of the billiard video sequence and 10 neurons.


#### 5.2.2. Results for 15 Neurons

In Table4 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 121,204 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 182.14. In Figure 30 the quantity of subanimations is presented grouped in each cluster.Table 4
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 15 neurons.
Class
EVM size
0
17,960
1
10,666
2
6,072
3
4,700
4
1,706
5
7,782
6
634
7
13,838
8
1,338
9
4,064
10
15,570
11
2,798
12
966
13
12,054
14
21,056
Total
121,204Figure 30
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 15 neurons.Now we provide a description of the information contained in clusters 1, 2, and 9:(i)
Cluster 1, which has the frame sequence shown in Figure31, contains regions related to the borders of the elements of the scene. A similar situation has been presented in the previous test (Section 5.2.1). The corresponding 3D-OPP for this cluster is shown in Figure 32, where we can observe the borders of the elements and their evolution across time.(ii)
Clusters 2 and 9 present the case of the patterns of movement of the billiard balls. It is important to consider that both clusters contain similar information, but cluster 2 contains information about the environment of the scene, that is, elements such as the billiard table. The frame sequences of both clusters are shown in Figures33 and 35, respectively. Their corresponding 3D-OPPs are shown in Figures 34 and 36. In these OPPs how they grouped the movement of the balls can be seen clearly, but cluster 9 obtains a better isolation of the event. This result has been observed in previous tests, and it is very promising in the sense that the SOM is able to recognize movement patterns across time.Figure 31
Grouping results for cluster 1: billiard video sequence and 15 neurons.Figure 32
3D-OPP for cluster 1 of the billiard video sequence and 15 neurons.Figure 33
Grouping results for cluster 2: billiard video sequence and 15 neurons.Figure 34
3D-OPP for cluster 2 of the billiard video sequence and 15 neurons.Figure 35
Grouping results for cluster 9: billiard video sequence and 15 neurons.Figure 36
3D-OPP for cluster 9 of the billiard video sequence and 15 neurons.


## 5.1. Tests for a Traffic Control Video Sequence

We analyze segmentation results for a traffic control video sequence taken from [50]. It consists in a static camera pointing to the center of a highway. Figure 7 shows some selected frames from this video sequence. As can be observed, the scene contains the movement of cars along the highway while at left and right sides green zones are found. The frames of this video sequence have a size of 160 × 120 pixels, and we have 60 consecutive frames at a rate of 20 frames per second. For this case, the frame sequence was represented in an EVM-animation that consists of a 6D-EVM with a total of 17,058,774 extreme vertices. The SOM’s tested configurations were 5 and 15 neurons. In both cases the training stage executed 200 iterations. The results are analyzed in the following subsections.Figure 7
Some frames of the traffic control video sequence.


### 5.1.1. Results for 5 Neurons

In Table1 the sizes of every 3D-EVM are shown associated with every cluster. It can be observed that we have a total of 80,128 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 212.89. In Figure 8 the quantity of subanimations grouped in each cluster is presented.Table 1
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons.
Class
EVM size
0
28,968
1
1,528
2
24,674
3
6,308
4
18,650
Total
80,128Figure 8
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 5 neurons.Now we describe some information contained in clusters 0, 2, and 4:(i)
For cluster 0 its frame sequence is shown in Figure9. It can be observed that it grouped information related to dark regions of the highway and also contains movement of the cars. In Figure 10 the 3D-OPP can be observed generated for cluster 0. In this 3D-OPP the temporal evolution of the highway’s grouped regions can be appreciated.(ii)
Figure11 presents the frame sequence obtained for cluster 2. As can be observed, the brighter regions of the highway are grouped as well as the movement of the cars that take place in those regions. In Figure 12 the 3D-OPP is shown generated for cluster 2. In it, the regions can be seen grouped for the highway, the movement of the cars, and the evolution of those regions across time.(iii)
For cluster 4 we present the frame sequence shown in Figure13. This cluster contains important information because we can observe only the movement of the cars on the highway. This implies the SOM captured movement patterns and tried to separate them in a single cluster. Nevertheless, it also groups information of the highway’s green zones. This is because they have some similarities with the cars’ shadows in the sense that they are dark regions. In Figure 14 the 3D-OPP associated with cluster 4 is shown. In this OPP clearly we can observe regions correspondent to the movement of the cars across the time axis.Figure 9
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 0.Figure 10
3D-OPP associated with cluster 0: traffic control video sequence and 5 neurons.Figure 11
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 2.Figure 12
3D-OPP associated with cluster 2: traffic control video sequence and 5 neurons.Figure 13
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 4.Figure 14
3D-OPP associated with cluster 4: traffic control video sequence and 5 neurons.


### 5.1.2. Results for 15 Neurons

In Table2 the sizes of every 3D-EVM associated with every cluster are shown. We have a total of 206,140 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 82.75. In Figure 15 the quantity of subanimations grouped in each cluster is presented.Table 2
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons.
Class
EVM size
0
176
1
38,826
2
8,560
3
15,116
4
3,070
5
23,346
6
1,408
7
8,352
8
33,272
9
45,096
10
496
11
0
12
0
13
4,796
14
23,626
Total
206,140Figure 15
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 15 neurons.We present a brief description of information contained in clusters 1, 5, and 9:(i)
For cluster 1, in Figure16, its frame sequence is shown. It is observed that this cluster groups darker regions of the highway and also the movements of cars which take place in such regions. Now, the corresponding 3D-OPP is shown in Figure 17. It is possible to observe the movement of the cars, the abovementioned darker regions, and their evolution across the temporal dimension.(ii)
In the case of cluster 5 see Figure18 for its frame sequence. As can be observed, for this cluster the SOM has provided a proper separation of the movement of the cars. In Figure 19 the 3D-OPP is shown formed with all the subanimations grouped. Clearly, we can observe the movement of cars in the center of the highway. There are also grouped regions from green zones because they are also dark zones.(iii)
The last cluster to be described is number 9. Its frame sequence is shown in Figure20, where we can observe that it groups the brighter regions of the highway and also grouped the movement of the cars that takes place in those zones. In Figure 21 the corresponding 3D-OPP is shown.Figure 16
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 1.Figure 17
3D-OPP associated with cluster 1: traffic control video sequence and 15 neurons.Figure 18
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 5.Figure 19
3D-OPP associated with cluster 5: traffic control video sequence and 15 neurons.Figure 20
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 9.Figure 21
3D-OPP associated with cluster 9: traffic control video sequence and 15 neurons.


## 5.1.1. Results for 5 Neurons

In Table1 the sizes of every 3D-EVM are shown associated with every cluster. It can be observed that we have a total of 80,128 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 212.89. In Figure 8 the quantity of subanimations grouped in each cluster is presented.Table 1
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons.
Class
EVM size
0
28,968
1
1,528
2
24,674
3
6,308
4
18,650
Total
80,128Figure 8
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 5 neurons.Now we describe some information contained in clusters 0, 2, and 4:(i)
For cluster 0 its frame sequence is shown in Figure9. It can be observed that it grouped information related to dark regions of the highway and also contains movement of the cars. In Figure 10 the 3D-OPP can be observed generated for cluster 0. In this 3D-OPP the temporal evolution of the highway’s grouped regions can be appreciated.(ii)
Figure11 presents the frame sequence obtained for cluster 2. As can be observed, the brighter regions of the highway are grouped as well as the movement of the cars that take place in those regions. In Figure 12 the 3D-OPP is shown generated for cluster 2. In it, the regions can be seen grouped for the highway, the movement of the cars, and the evolution of those regions across time.(iii)
For cluster 4 we present the frame sequence shown in Figure13. This cluster contains important information because we can observe only the movement of the cars on the highway. This implies the SOM captured movement patterns and tried to separate them in a single cluster. Nevertheless, it also groups information of the highway’s green zones. This is because they have some similarities with the cars’ shadows in the sense that they are dark regions. In Figure 14 the 3D-OPP associated with cluster 4 is shown. In this OPP clearly we can observe regions correspondent to the movement of the cars across the time axis.Figure 9
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 0.Figure 10
3D-OPP associated with cluster 0: traffic control video sequence and 5 neurons.Figure 11
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 2.Figure 12
3D-OPP associated with cluster 2: traffic control video sequence and 5 neurons.Figure 13
Traffic control video sequence under SOM with 5 neurons: segmentation results for cluster 4.Figure 14
3D-OPP associated with cluster 4: traffic control video sequence and 5 neurons.


## 5.1.2. Results for 15 Neurons

In Table2 the sizes of every 3D-EVM associated with every cluster are shown. We have a total of 206,140 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 82.75. In Figure 15 the quantity of subanimations grouped in each cluster is presented.Table 2
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons.
Class
EVM size
0
176
1
38,826
2
8,560
3
15,116
4
3,070
5
23,346
6
1,408
7
8,352
8
33,272
9
45,096
10
496
11
0
12
0
13
4,796
14
23,626
Total
206,140Figure 15
Number of subanimations for each cluster associated with the traffic control video sequence under a SOM with 15 neurons.We present a brief description of information contained in clusters 1, 5, and 9:(i)
For cluster 1, in Figure16, its frame sequence is shown. It is observed that this cluster groups darker regions of the highway and also the movements of cars which take place in such regions. Now, the corresponding 3D-OPP is shown in Figure 17. It is possible to observe the movement of the cars, the abovementioned darker regions, and their evolution across the temporal dimension.(ii)
In the case of cluster 5 see Figure18 for its frame sequence. As can be observed, for this cluster the SOM has provided a proper separation of the movement of the cars. In Figure 19 the 3D-OPP is shown formed with all the subanimations grouped. Clearly, we can observe the movement of cars in the center of the highway. There are also grouped regions from green zones because they are also dark zones.(iii)
The last cluster to be described is number 9. Its frame sequence is shown in Figure20, where we can observe that it groups the brighter regions of the highway and also grouped the movement of the cars that takes place in those zones. In Figure 21 the corresponding 3D-OPP is shown.Figure 16
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 1.Figure 17
3D-OPP associated with cluster 1: traffic control video sequence and 15 neurons.Figure 18
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 5.Figure 19
3D-OPP associated with cluster 5: traffic control video sequence and 15 neurons.Figure 20
Traffic control video sequence under SOM with 15 neurons: segmentation results for cluster 9.Figure 21
3D-OPP associated with cluster 9: traffic control video sequence and 15 neurons.


## 5.2. Tests for a Billiard Game Video Sequence

Now we proceed to analyze segmentation results for a video sequence that consists in a game of a professional billiard player [51]. This video is a capture of a single play. Figure 22 shows some selected frames from this video sequence. The frames of this video sequence have a size of 240 × 160 pixels, and we have 48 consecutive frames under RGB color model. For this case, the frame sequence was represented as an EVM-animation that consists of a 6D-EVM with a total of 22,076,702 extreme vertices. The SOM’s tested configurations were 10 and 15 neurons. In both cases the training stage executed 200 iterations. The results are analyzed in the following subsections.Figure 22
Some frames for the Billiard Game Video Sequence.


### 5.2.1. Results for 10 Neurons

In Table3 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 76,754 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 287.62. In Figure 23 the quantity of subanimations grouped in each cluster is presented.Table 3
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 10 neurons.
Class
EVM size
0
2,352
1
10,364
2
13,604
3
866
4
4,434
5
4,552
6
6,614
7
18,520
8
14,194
9
1,254
Total
76,754Figure 23
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 10 neurons.Now we provide a brief description of the information contained in clusters 1, 4, and 6:(i)
Cluster 1 has the frame sequence shown in Figure24. It contains regions corresponding to the borders of the elements present in the scene. In Figure 25 the 3D-OPP can be seen associated with the current cluster. In such OPP we can clearly observe the borders previously mentioned and also their evolution along the temporal dimension can be seen.(ii)
Cluster 4 contains the frame sequence that is shown in Figure26. It can be observed that it groups the regions corresponding to the movement of the billiard balls. In this case, the SOM has been able to distinguish movement patterns. In Figure 27 the 3D-OPP for cluster 4 can be observed. In it, we can clearly note the regions of the movement of the billiard balls.(iii)
Cluster 6 has the frame sequence shown in Figure28. We can observe it also groups regions related to the billiard balls movements, but in this case it also groups other small bright regions from the scene. Nevertheless, this cluster also captures the dynamic of the movement of the balls. In Figure 29 the 3D-OPP can be observed for the current cluster. Clearly, we can note the regions of the movement of the billiard balls and the bright regions mentioned before.Figure 24
Grouping results for cluster 1: billiard video sequence and 10 neurons.Figure 25
3D-OPP for cluster 1 of the billiard video sequence and 10 neurons.Figure 26
Grouping results for cluster 4: billiard video sequence and 10 neurons.Figure 27
3D-OPP for cluster 4 of the billiard video sequence and 10 neurons.Figure 28
Grouping results for cluster 6: billiard video sequence and 10 neurons.Figure 29
3D-OPP for cluster 6 of the billiard video sequence and 10 neurons.


### 5.2.2. Results for 15 Neurons

In Table4 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 121,204 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 182.14. In Figure 30 the quantity of subanimations is presented grouped in each cluster.Table 4
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 15 neurons.
Class
EVM size
0
17,960
1
10,666
2
6,072
3
4,700
4
1,706
5
7,782
6
634
7
13,838
8
1,338
9
4,064
10
15,570
11
2,798
12
966
13
12,054
14
21,056
Total
121,204Figure 30
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 15 neurons.Now we provide a description of the information contained in clusters 1, 2, and 9:(i)
Cluster 1, which has the frame sequence shown in Figure31, contains regions related to the borders of the elements of the scene. A similar situation has been presented in the previous test (Section 5.2.1). The corresponding 3D-OPP for this cluster is shown in Figure 32, where we can observe the borders of the elements and their evolution across time.(ii)
Clusters 2 and 9 present the case of the patterns of movement of the billiard balls. It is important to consider that both clusters contain similar information, but cluster 2 contains information about the environment of the scene, that is, elements such as the billiard table. The frame sequences of both clusters are shown in Figures33 and 35, respectively. Their corresponding 3D-OPPs are shown in Figures 34 and 36. In these OPPs how they grouped the movement of the balls can be seen clearly, but cluster 9 obtains a better isolation of the event. This result has been observed in previous tests, and it is very promising in the sense that the SOM is able to recognize movement patterns across time.Figure 31
Grouping results for cluster 1: billiard video sequence and 15 neurons.Figure 32
3D-OPP for cluster 1 of the billiard video sequence and 15 neurons.Figure 33
Grouping results for cluster 2: billiard video sequence and 15 neurons.Figure 34
3D-OPP for cluster 2 of the billiard video sequence and 15 neurons.Figure 35
Grouping results for cluster 9: billiard video sequence and 15 neurons.Figure 36
3D-OPP for cluster 9 of the billiard video sequence and 15 neurons.


## 5.2.1. Results for 10 Neurons

In Table3 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 76,754 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 287.62. In Figure 23 the quantity of subanimations grouped in each cluster is presented.Table 3
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 10 neurons.
Class
EVM size
0
2,352
1
10,364
2
13,604
3
866
4
4,434
5
4,552
6
6,614
7
18,520
8
14,194
9
1,254
Total
76,754Figure 23
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 10 neurons.Now we provide a brief description of the information contained in clusters 1, 4, and 6:(i)
Cluster 1 has the frame sequence shown in Figure24. It contains regions corresponding to the borders of the elements present in the scene. In Figure 25 the 3D-OPP can be seen associated with the current cluster. In such OPP we can clearly observe the borders previously mentioned and also their evolution along the temporal dimension can be seen.(ii)
Cluster 4 contains the frame sequence that is shown in Figure26. It can be observed that it groups the regions corresponding to the movement of the billiard balls. In this case, the SOM has been able to distinguish movement patterns. In Figure 27 the 3D-OPP for cluster 4 can be observed. In it, we can clearly note the regions of the movement of the billiard balls.(iii)
Cluster 6 has the frame sequence shown in Figure28. We can observe it also groups regions related to the billiard balls movements, but in this case it also groups other small bright regions from the scene. Nevertheless, this cluster also captures the dynamic of the movement of the balls. In Figure 29 the 3D-OPP can be observed for the current cluster. Clearly, we can note the regions of the movement of the billiard balls and the bright regions mentioned before.Figure 24
Grouping results for cluster 1: billiard video sequence and 10 neurons.Figure 25
3D-OPP for cluster 1 of the billiard video sequence and 10 neurons.Figure 26
Grouping results for cluster 4: billiard video sequence and 10 neurons.Figure 27
3D-OPP for cluster 4 of the billiard video sequence and 10 neurons.Figure 28
Grouping results for cluster 6: billiard video sequence and 10 neurons.Figure 29
3D-OPP for cluster 6 of the billiard video sequence and 10 neurons.


## 5.2.2. Results for 15 Neurons

In Table4 the sizes of every 3D-EVM are shown associated with each cluster. It can be observed that we have a total of 121,204 extreme vertices. By comparing against the 6D-EVM of the original EVM-animation we obtained a compression rate of 182.14. In Figure 30 the quantity of subanimations is presented grouped in each cluster.Table 4
Size of the 3D-EVMs generated for every cluster associated with the billiard video sequence under a SOM with 15 neurons.
Class
EVM size
0
17,960
1
10,666
2
6,072
3
4,700
4
1,706
5
7,782
6
634
7
13,838
8
1,338
9
4,064
10
15,570
11
2,798
12
966
13
12,054
14
21,056
Total
121,204Figure 30
Number of subanimations for each cluster associated with the billiard video sequence under a SOM with 15 neurons.Now we provide a description of the information contained in clusters 1, 2, and 9:(i)
Cluster 1, which has the frame sequence shown in Figure31, contains regions related to the borders of the elements of the scene. A similar situation has been presented in the previous test (Section 5.2.1). The corresponding 3D-OPP for this cluster is shown in Figure 32, where we can observe the borders of the elements and their evolution across time.(ii)
Clusters 2 and 9 present the case of the patterns of movement of the billiard balls. It is important to consider that both clusters contain similar information, but cluster 2 contains information about the environment of the scene, that is, elements such as the billiard table. The frame sequences of both clusters are shown in Figures33 and 35, respectively. Their corresponding 3D-OPPs are shown in Figures 34 and 36. In these OPPs how they grouped the movement of the balls can be seen clearly, but cluster 9 obtains a better isolation of the event. This result has been observed in previous tests, and it is very promising in the sense that the SOM is able to recognize movement patterns across time.Figure 31
Grouping results for cluster 1: billiard video sequence and 15 neurons.Figure 32
3D-OPP for cluster 1 of the billiard video sequence and 15 neurons.Figure 33
Grouping results for cluster 2: billiard video sequence and 15 neurons.Figure 34
3D-OPP for cluster 2 of the billiard video sequence and 15 neurons.Figure 35
Grouping results for cluster 9: billiard video sequence and 15 neurons.Figure 36
3D-OPP for cluster 9 of the billiard video sequence and 15 neurons.


## 6. Comparisons with Alternative Masks Definitions

In the previous sections we have described the elements that compose our proposed framework and some experimental results obtained when it was applied to two video sequences. As we have previously stated, one of the framework’s main elements is the one related to the representation of a video sequence as a higher dimensional OPP. There were considered two geometrical dimensions, one temporal dimension, and one dimension for each color component under the respective color model. As seen before, our presented study cases were expressed as 6D-OPPs because of the use of the RGB color model.In this section we are going to present some additional experiments whose objective is the one related to the study of two scenarios.Scenario 1.
Pixels in a frame can be distinguished from pixels from another frame because we have information related to the temporal position, in the video sequence, for these frames. Hence, we could define masks as stated in Section4 but omitting the temporal component. This implies a mask describes only a region from only one frame, instead of being a subanimation that contains information from several consecutive frames. For this new type of masks its respective DC value can be obtained which in turn is used for training a SOM. Then, a 3D-OPP associated with a cluster, containing a temporal dimension, can also be built by simply recurring to the frame membership of each mask. Taking into account the RGB color model, we have 5D masks (instead of the 6D masks defined in Section 4): two geometrical dimensions and three dimensions associated with each color component. What differences arise, with respect to our proposed framework, when training a SOM without temporal information?Scenario 2.
In Section1.1 a representation of RGB video sequences was mentioned where the three components’ values were integrated as a single integer. Therefore only one dimension is assigned for managing color in a frame’s extrusion. One effect that is well identified is the fact that small variations in the integer’s higher order bits produce large variations in the whole integer value. Now, we can define masks where the temporal dimension is omitted and only one dimension is assigned to color scale. Again, just as commented above, these masks describe only a region from only one frame but their respective DC values can be obtained and used for training a SOM. Then, a 3D-OPP associated with a cluster, containing a temporal dimension, is built by recurring to the frame membership of each mask. In this scenario we are dealing with 3D masks: two geometrical dimensions and one dimension related to color scale. What differences arise, with respect to our proposed framework, when training a SOM not only without temporal information but by comprising color components in just one dimension?The results obtained from the abovementioned pair of scenarios provide us with experimental evidence related to the reason for considering a 6D representation (by using the RGB color scale) for our video sequences, and, for instance, the definition of masks as subanimations taken from this 6D polytope, as stated in Section4. As seen, these 6D masks provide geometrical, temporal, and color information, with each color component expressed in individual way, to the SOM. For the sake of brevity, we will concentrate only on comparing sizes of the 3D-OPPs obtained in the new experiments with the 3D-OPPs described in Section 5. That is, we are going to compare conciseness of the obtained video segmentations. We will use the same pair of video sequences considered in previous section.


### 6.1. Scenario1: Removal of the Temporal Component

Just as presented in Section5, the two video sequences under consideration are a traffic control video sequence and a Billiard Game Video Sequence. In both cases the configuration of the 5D mask consists in a 2D region of size 3 × 3, three dimensions for red, green, and blue components, without temporal information. The SOM’s training stage executed 200 iterations.


#### 6.1.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations, for this video sequence, were 5 and 15 neurons. Tables5 and 6 present the obtained classification results. Concerning SOM’s configuration with 5 neurons a total of 127,262 extreme vertices were obtained for 3D-EVM representation (Table 5). In Section 5.1.1, for the same SOM configuration and considering 6D masks, a 3D-EVM representation was reported with 80,128 extreme vertices. Table 6 reports results for SOM configuration with 15 neurons where 396,794 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D mask, in Section 5.1.2 we reported that 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having EVM representations 1.58 and 1.92 times greater than those presentations achieved by means of using 6D masks.Table 5
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons and removal of the temporal component.
Class
Members
EVM size
0
369,462
28,872
1
211,473
34,846
2
707,381
56,644
3
11,028
5,490
4
5,736
1,410
Total
1,305,080
127,262Table 6
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons and removal of the temporal component.
Class
Members
EVM size
0
9,111
8,310
1
5,063
4,658
2
147,723
61,178
3
2,839
1,324
4
83,716
30,748
5
3,131
2,930
6
249,764
62,728
7
143,663
55,420
8
141,288
36,546
9
139,151
18,918
10
2,404
2,192
11
100,026
45,394
12
250,749
50,160
13
924
400
14
25,528
15,888
Total
1,305,080
396,794


#### 6.1.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations, for this case, were 10 and 15 neurons. Tables7 and 8 present the obtained classification results. Concerning SOM’s configuration with 10 neurons 119,420 extreme vertices were required for 3D-EVM representation (Table 7). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 8 reports results for SOM configuration with 15 neurons where 231,660 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported that 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having alternative representations 1.55 and 1.91 times greater than those presentations achieved by means of using 6D masks.Table 7
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons and removal of the temporal component.
Class
Members
EVM size
0
12,795
4,766
1
271,960
23,592
2
43,324
9,662
3
3,144
1,158
4
568,858
25,418
5
588,160
11,790
6
4,142
2,010
7
287,241
31,304
8
6,414
2,832
9
18,954
6,888
Total
1,804,992
119,420Table 8
Size of the 3D-EVMs generated for clusters associated with Billiard Game Video Sequence under a SOM with 15 neurons and removal of temporal component.
Class
Members
EVM size
0
244,714
40,280
1
187,126
22,722
2
2,048
930
3
201,427
30,670
4
3,428
2,062
5
210,437
42,532
6
189,185
25,880
7
8,776
3,966
8
11,881
5,808
9
548,273
10,294
10
143,238
25,930
11
29,990
8,946
12
16,003
7,350
13
4,944
2,732
14
3,522
1,558
Total
1,804,992
231,660


### 6.2. Scenario2: Removal of the Temporal Component and Unification of RGB Components

In both considered video sequences the configuration of the 3D mask consists in a 2D region of size 3 × 3, one dimension integrating as a single integer the red, green, and blue components, without temporal information. The SOM’s training stage executed 200 iterations.


#### 6.2.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations were 5 and 15 neurons. Tables9 and 10 present the obtained classification results. Concerning SOM’s configuration with 5 neurons 168,862 extreme vertices were required for 3D-EVM representation (Table 9). In Section 5.1.1 a 3D-EVM representation was reported with 80,128 extreme vertices. Table 10 reports results for SOM configuration with 15 neurons where 459,974 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.1.2 we reported 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts in having alternative representations 2.1 and 2.23 times greater than those presentations achieved by means of using 6D masks.Table 9
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
236,870
44,890
1
60,893
6,106
2
273,111
39,546
3
628,234
60,900
4
105,972
17,420
Total
1,305,080
168,862Table 10
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
101,659
41,200
1
8,090
1,544
2
75,412
27,546
3
20,303
4,132
4
39,248
19,346
5
100,466
44,756
6
141,671
54,886
7
50,004
26,708
8
32,365
13,120
9
237,961
62,432
10
29,493
8,780
11
25,558
7,496
12
190,047
62,248
13
186,832
52,542
14
65,971
33,238
Total
1,305,080
459,974


#### 6.2.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations were 10 and 15 neurons. Tables11 and 12 present the obtained classification results. Concerning SOM’s configuration with 10 neurons there were required 172,376 extreme vertices for 3D-EVM representation (Table 11). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 12 reports results for SOM configuration with 15 neurons where 280,928 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts on having alternative representations 2.24 and 2.31 times greater than those presentations achieved by means of using 6D masks.Table 11
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
82,064
13,552
1
340,045
45,358
2
250,389
9,012
3
180,390
26,104
4
66,439
8,896
5
49,017
6,072
6
15,538
2,726
7
672,032
37,044
8
73,421
11,524
9
75,657
12,088
Total
1,804,992
172,376Table 12
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
206,717
8,288
1
44,117
6,288
2
11,638
4,048
3
8,596
2,282
4
47,503
10,082
5
47,525
11,804
6
332,658
58,154
7
381,654
39,536
8
46,984
11,182
9
53,709
8,540
10
116,704
19,198
11
41,066
11,092
12
60,888
13,880
13
249,839
46,318
14
155,394
30,236
Total
1,804,992
280,928


## 6.1. Scenario1: Removal of the Temporal Component

Just as presented in Section5, the two video sequences under consideration are a traffic control video sequence and a Billiard Game Video Sequence. In both cases the configuration of the 5D mask consists in a 2D region of size 3 × 3, three dimensions for red, green, and blue components, without temporal information. The SOM’s training stage executed 200 iterations.


### 6.1.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations, for this video sequence, were 5 and 15 neurons. Tables5 and 6 present the obtained classification results. Concerning SOM’s configuration with 5 neurons a total of 127,262 extreme vertices were obtained for 3D-EVM representation (Table 5). In Section 5.1.1, for the same SOM configuration and considering 6D masks, a 3D-EVM representation was reported with 80,128 extreme vertices. Table 6 reports results for SOM configuration with 15 neurons where 396,794 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D mask, in Section 5.1.2 we reported that 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having EVM representations 1.58 and 1.92 times greater than those presentations achieved by means of using 6D masks.Table 5
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons and removal of the temporal component.
Class
Members
EVM size
0
369,462
28,872
1
211,473
34,846
2
707,381
56,644
3
11,028
5,490
4
5,736
1,410
Total
1,305,080
127,262Table 6
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons and removal of the temporal component.
Class
Members
EVM size
0
9,111
8,310
1
5,063
4,658
2
147,723
61,178
3
2,839
1,324
4
83,716
30,748
5
3,131
2,930
6
249,764
62,728
7
143,663
55,420
8
141,288
36,546
9
139,151
18,918
10
2,404
2,192
11
100,026
45,394
12
250,749
50,160
13
924
400
14
25,528
15,888
Total
1,305,080
396,794


### 6.1.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations, for this case, were 10 and 15 neurons. Tables7 and 8 present the obtained classification results. Concerning SOM’s configuration with 10 neurons 119,420 extreme vertices were required for 3D-EVM representation (Table 7). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 8 reports results for SOM configuration with 15 neurons where 231,660 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported that 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having alternative representations 1.55 and 1.91 times greater than those presentations achieved by means of using 6D masks.Table 7
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons and removal of the temporal component.
Class
Members
EVM size
0
12,795
4,766
1
271,960
23,592
2
43,324
9,662
3
3,144
1,158
4
568,858
25,418
5
588,160
11,790
6
4,142
2,010
7
287,241
31,304
8
6,414
2,832
9
18,954
6,888
Total
1,804,992
119,420Table 8
Size of the 3D-EVMs generated for clusters associated with Billiard Game Video Sequence under a SOM with 15 neurons and removal of temporal component.
Class
Members
EVM size
0
244,714
40,280
1
187,126
22,722
2
2,048
930
3
201,427
30,670
4
3,428
2,062
5
210,437
42,532
6
189,185
25,880
7
8,776
3,966
8
11,881
5,808
9
548,273
10,294
10
143,238
25,930
11
29,990
8,946
12
16,003
7,350
13
4,944
2,732
14
3,522
1,558
Total
1,804,992
231,660


## 6.1.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations, for this video sequence, were 5 and 15 neurons. Tables5 and 6 present the obtained classification results. Concerning SOM’s configuration with 5 neurons a total of 127,262 extreme vertices were obtained for 3D-EVM representation (Table 5). In Section 5.1.1, for the same SOM configuration and considering 6D masks, a 3D-EVM representation was reported with 80,128 extreme vertices. Table 6 reports results for SOM configuration with 15 neurons where 396,794 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D mask, in Section 5.1.2 we reported that 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having EVM representations 1.58 and 1.92 times greater than those presentations achieved by means of using 6D masks.Table 5
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons and removal of the temporal component.
Class
Members
EVM size
0
369,462
28,872
1
211,473
34,846
2
707,381
56,644
3
11,028
5,490
4
5,736
1,410
Total
1,305,080
127,262Table 6
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons and removal of the temporal component.
Class
Members
EVM size
0
9,111
8,310
1
5,063
4,658
2
147,723
61,178
3
2,839
1,324
4
83,716
30,748
5
3,131
2,930
6
249,764
62,728
7
143,663
55,420
8
141,288
36,546
9
139,151
18,918
10
2,404
2,192
11
100,026
45,394
12
250,749
50,160
13
924
400
14
25,528
15,888
Total
1,305,080
396,794


## 6.1.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations, for this case, were 10 and 15 neurons. Tables7 and 8 present the obtained classification results. Concerning SOM’s configuration with 10 neurons 119,420 extreme vertices were required for 3D-EVM representation (Table 7). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 8 reports results for SOM configuration with 15 neurons where 231,660 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported that 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component impacts on having alternative representations 1.55 and 1.91 times greater than those presentations achieved by means of using 6D masks.Table 7
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons and removal of the temporal component.
Class
Members
EVM size
0
12,795
4,766
1
271,960
23,592
2
43,324
9,662
3
3,144
1,158
4
568,858
25,418
5
588,160
11,790
6
4,142
2,010
7
287,241
31,304
8
6,414
2,832
9
18,954
6,888
Total
1,804,992
119,420Table 8
Size of the 3D-EVMs generated for clusters associated with Billiard Game Video Sequence under a SOM with 15 neurons and removal of temporal component.
Class
Members
EVM size
0
244,714
40,280
1
187,126
22,722
2
2,048
930
3
201,427
30,670
4
3,428
2,062
5
210,437
42,532
6
189,185
25,880
7
8,776
3,966
8
11,881
5,808
9
548,273
10,294
10
143,238
25,930
11
29,990
8,946
12
16,003
7,350
13
4,944
2,732
14
3,522
1,558
Total
1,804,992
231,660


## 6.2. Scenario2: Removal of the Temporal Component and Unification of RGB Components

In both considered video sequences the configuration of the 3D mask consists in a 2D region of size 3 × 3, one dimension integrating as a single integer the red, green, and blue components, without temporal information. The SOM’s training stage executed 200 iterations.


### 6.2.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations were 5 and 15 neurons. Tables9 and 10 present the obtained classification results. Concerning SOM’s configuration with 5 neurons 168,862 extreme vertices were required for 3D-EVM representation (Table 9). In Section 5.1.1 a 3D-EVM representation was reported with 80,128 extreme vertices. Table 10 reports results for SOM configuration with 15 neurons where 459,974 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.1.2 we reported 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts in having alternative representations 2.1 and 2.23 times greater than those presentations achieved by means of using 6D masks.Table 9
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
236,870
44,890
1
60,893
6,106
2
273,111
39,546
3
628,234
60,900
4
105,972
17,420
Total
1,305,080
168,862Table 10
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
101,659
41,200
1
8,090
1,544
2
75,412
27,546
3
20,303
4,132
4
39,248
19,346
5
100,466
44,756
6
141,671
54,886
7
50,004
26,708
8
32,365
13,120
9
237,961
62,432
10
29,493
8,780
11
25,558
7,496
12
190,047
62,248
13
186,832
52,542
14
65,971
33,238
Total
1,305,080
459,974


### 6.2.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations were 10 and 15 neurons. Tables11 and 12 present the obtained classification results. Concerning SOM’s configuration with 10 neurons there were required 172,376 extreme vertices for 3D-EVM representation (Table 11). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 12 reports results for SOM configuration with 15 neurons where 280,928 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts on having alternative representations 2.24 and 2.31 times greater than those presentations achieved by means of using 6D masks.Table 11
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
82,064
13,552
1
340,045
45,358
2
250,389
9,012
3
180,390
26,104
4
66,439
8,896
5
49,017
6,072
6
15,538
2,726
7
672,032
37,044
8
73,421
11,524
9
75,657
12,088
Total
1,804,992
172,376Table 12
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
206,717
8,288
1
44,117
6,288
2
11,638
4,048
3
8,596
2,282
4
47,503
10,082
5
47,525
11,804
6
332,658
58,154
7
381,654
39,536
8
46,984
11,182
9
53,709
8,540
10
116,704
19,198
11
41,066
11,092
12
60,888
13,880
13
249,839
46,318
14
155,394
30,236
Total
1,804,992
280,928


## 6.2.1. Tests for a Traffic Control Video Sequence

The SOM’s tested configurations were 5 and 15 neurons. Tables9 and 10 present the obtained classification results. Concerning SOM’s configuration with 5 neurons 168,862 extreme vertices were required for 3D-EVM representation (Table 9). In Section 5.1.1 a 3D-EVM representation was reported with 80,128 extreme vertices. Table 10 reports results for SOM configuration with 15 neurons where 459,974 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.1.2 we reported 206,140 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts in having alternative representations 2.1 and 2.23 times greater than those presentations achieved by means of using 6D masks.Table 9
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 5 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
236,870
44,890
1
60,893
6,106
2
273,111
39,546
3
628,234
60,900
4
105,972
17,420
Total
1,305,080
168,862Table 10
Size of the 3D-EVMs generated for every cluster associated with the traffic control video sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
101,659
41,200
1
8,090
1,544
2
75,412
27,546
3
20,303
4,132
4
39,248
19,346
5
100,466
44,756
6
141,671
54,886
7
50,004
26,708
8
32,365
13,120
9
237,961
62,432
10
29,493
8,780
11
25,558
7,496
12
190,047
62,248
13
186,832
52,542
14
65,971
33,238
Total
1,305,080
459,974


## 6.2.2. Tests for a Billiard Game Video Sequence

The SOM’s tested configurations were 10 and 15 neurons. Tables11 and 12 present the obtained classification results. Concerning SOM’s configuration with 10 neurons there were required 172,376 extreme vertices for 3D-EVM representation (Table 11). In Section 5.2.1 a 3D-EVM representation was reported with 76,754 extreme vertices. Table 12 reports results for SOM configuration with 15 neurons where 280,928 extreme vertices are required for 3D-EVM representation. For this same SOM configuration, and by using 6D masks, in Section 5.2.2 we reported 121,204 extreme vertices were required for 3D-EVM representation. Therefore the removal of the temporal component and the integration of color components in a single dimension impacts on having alternative representations 2.24 and 2.31 times greater than those presentations achieved by means of using 6D masks.Table 11
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 10 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
82,064
13,552
1
340,045
45,358
2
250,389
9,012
3
180,390
26,104
4
66,439
8,896
5
49,017
6,072
6
15,538
2,726
7
672,032
37,044
8
73,421
11,524
9
75,657
12,088
Total
1,804,992
172,376Table 12
Size of the 3D-EVMs generated for every cluster associated with the Billiard Game Video Sequence under a SOM with 15 neurons, removal of the temporal component and unification of RGB components.
Class
Members
EVM size
0
206,717
8,288
1
44,117
6,288
2
11,638
4,048
3
8,596
2,282
4
47,503
10,082
5
47,525
11,804
6
332,658
58,154
7
381,654
39,536
8
46,984
11,182
9
53,709
8,540
10
116,704
19,198
11
41,066
11,092
12
60,888
13,880
13
249,839
46,318
14
155,394
30,236
Total
1,804,992
280,928


## 7. Concluding Remarks and Future Work

According to the results presented in Section5, many potential applications can be proposed for our proposed framework. At first, it was possible to represent video sequences as a 6D-OPP considering the RGB color scheme, but as we mentioned in Section 4, it is possible to represent videos considering other color schemes, for example, grayscale. This feature of the framework provides versatility in the sense that it can be adjusted to the application we want to develop and the video sources available.The video sequences’ segmentation was performed by means of extraction of subanimations. For each one of these subanimations its DC descriptor was computed which is a feature that considers the shape and topology of the subanimations. Moreover, upper and lower bounds were proposed in order to compute the DC descriptor: the upper bound is obtained from a subanimation which contains only white frames, while the lower bound is determined from a subanimation that contains only black frames.To form the training setDCValues for the SOM, a convolution was performed between the 6D representation of the original animation and a mask. By this way the convolution is given by the mask’s unit shifts over the X1-, X2-, and t-axis. An important characteristic of the convolution process’ implementation lies in the fact that only some sections from the original animation are required for performing the regularized intersection between the mask and the animation. In that sense, this enhancement represents an improvement with respect to the original Boolean Operations Algorithm under the nD-EVM because it is not required to manage all sections from the original animation. Finally, for every cluster a 3D-OPP was formed expressed under the 3D-EVM, which contains only the regions belonging to all the subanimations grouped precisely in the cluster.In general terms, as seen in experiments from Section5, the framework we have developed separates the regions in an animation in such way that there are grouped regions that share similar patterns. From the segmentation tests we comment on some observations:(i)
Some clusters group a considerable quantity of information. This is because some video sequences present temporal redundancy. On the other hand, there are some groups that contain a small quantity of information because they tend to group small regions that are different to the rest of the scene.(ii)
There are clusters that contain regions where borders of the elements of the scene are only present.(iii)
In some clusters we observed that they group regions related to the shadows of the objects in the scene. This behavior is very interesting because this could be useful to identify the quantity of objects in the scene; see for example, [52, 53].(iv)
Another interesting behavior that was observed in the performed tests is that the SOM is able to group regions of moving objects and isolate them from the rest of the scene. This result is important because it represents a starting point for identifying movement patterns, and therefore it could be used for other applications.The experiments performed in Section6 have provided us with experimental evidence related to the importance for considering the temporal dimension as well as to explicitly separate color components. Although it is possible to define alternative masks whose DC descriptor can be also computed, we have seen how, in first instance, by omitting time as a dimension (Section 6.1) we obtained 3D-OPPs’ representations whose sizes range from 1.55 to 1.92 times greater than those presented in Section 5 for the same video sequences. In a second instance, we have observed that by integrating available color components in a single dimension (Section 6.2), and omitting again temporal dimension, the differences increase: we have obtained 3D-OPPs’ representations whose sizes range from 2.1 and 2.31 times greater than those obtained by means of our original proposal using 6D subanimations. Summarizing this point, these experiments share us elements for justifying the managing of two geometrical dimensions, one dimension for each color component, and finally, the time axis.The general conclusion of this work lies in the fact that it was possible to develop a framework for representing and segmenting frame sequences using thenD-EVM model and the SOM approach. This fact encourages us to the development of various future research works. One of them considers the generation of segmentation results for video sequences with different color schemes than that used in this work. Experiments are going to be made in order to determine if there is a color scheme that is more suitable for segmentation tasks.The segmentation results are promising and encouraging by using the DC descriptor. For this reason, we consider that it is important to develop algorithms for computing other shape descriptors fornD-OPPs expressed in the EVM. By this way it would be possible to form feature vectors for each subanimation. This would provide us with more elements for better subanimations’ comparison. Therefore, it would be possible to improve the performance of the clustering stage. Nevertheless, the challenge here remains in the development of algorithms that can be applied for EVMs for any dimensionality or by defining specific cases.The segmentation stage using the SOM approach was developed in a modular fashion, which means that other clustering approaches can be used. This provides an opportunity for developing a study and comparison of the clustering performance using different clustering approaches such as [35]k-means,fuzzyc-means, andvector quantization, just to mention a few ones.Considering that some clusters group regions of the borders of the objects in the scene, we propose developing a classification system using the supervised learning approach. In this approach the goals are to form a training set that contains all the regions of objects borders. Then the training of the classification system will be performed, and at the end of the training stage this system would be able to identify all the regions containing borders for a completely new animation. This idea can also be applied for image processing.Another line of future research that can be derived from this work consists in using the same approach of supervised learning. But this time we will provide, to the classification system, a training set that contains movement patterns. By this way the classification system will learn how to identify movement in a video sequence. In this sense, it would be possible to train the classification system for recognizing the movement of humans, cars, animals, and so forth and separate them from the rest of the scene.



---

*Source: 6361237-2016-03-02.xml*