# Concise and Accessible Representations for Multidimensional Datasets: Introducing a Framework Based on thenD-EVM and Kohonen Networks

Authors: Ricardo Pérez-Aguila; Ricardo Ruiz-Rodríguez
Journal: Applied Computational Intelligence and Soft Computing
 (2015)

---

## Abstract

A new framework intended for representing and segmenting multidimensional datasets resulting in low spatial complexity requirements and with appropriate access to their contained information is described. Two steps are going to be taken in account. The first step is to specify (n-1)D hypervoxelizations, n≥2, as Orthogonal Polytopes whose nth dimension corresponds to color intensity. Then, the nD representation is concisely expressed via the Extreme Vertices Model in the n-Dimensional Space (nD-EVM). Some examples are presented, which, under our methodology, have storing requirements minor than those demanded by their original hypervoxelizations. In the second step, 1-Dimensional Kohonen Networks (1D-KNs) are applied in order to segment datasets taking in account their geometrical and topological properties providing a non-supervised way to compact even more the proposed n-Dimensional representations. The application of our framework shares compression ratios, for our set of study cases, in the range 5.6496 to 32.4311. Summarizing, the contribution combines the power of the nD-EVM and 1D-KNs by producing very concise datasets’ representations. We argue that the new representations also provide appropriate segmentations by introducing some error functions such that our 1D-KNs classifications are compared against classifications based only in color intensities. Along the work, main properties and algorithms behind the nD-EVM are introduced for the purpose of interrogating the final representations in such a way that it efficiently obtains useful geometrical and topological information.


---

## Body

## 1. Introduction

The representation of a polytope through a scheme of Hyperspatial Occupancy Enumeration is essentially a list of identical hyperspatial cells occupied by the polytope. Specific types of cells, called hypervoxels [1] are hyperboxes of a fixed size that lie in a fixed grid in the (n-1)-Dimensional space, n≥2. By instantiation, it is well known that a 2D hypervoxel is a pixel while a 3D hypervoxel is a voxel; the termrexel is suggested for referencing a 4D hypervoxel [1]. The collection of hyperboxes can be codified as an (n-1)D array Cx1,x2,…,xn-1. The array represents the color associated with each hypervoxel. If Cx1,x2,…,xn-1=0, the empty hypervoxel Cx1,x2,…,xn-1 represents an unoccupied region from the (n-1)D space. If Cx1,x2,…,xn-1=c, where c is in a given color scale (black & white, grayscale, RGB, etc.), then the occupied hypervoxel Cx1,x2,…,xn-1 represents a region from the (n-1)D space with intensity c. In fact, the set of occupied cells defines an orthogonal polytope p whose vertices coincide with some of the occupied cells’ vertices. By using the representation through an array, the spatial complexity of a (n-1)-Dimensional hypervoxelization is at least
(1)∏i=1n-1ni,
where ni, i=1,2,…,n-1, is the length of the grid along the Xi-axis. For example, a 3D grid with n1=n2=n3=1,000 requires to store 1 billion (1 × 109) voxels. Moreover, according to the used color scale each voxel will have a storing requirement: if the color space is RGB then each voxel will require three bytes (four, if the alpha channel is considered) for codifying its corresponding intensity.It is well known that some devices represent natively datasets through hypervoxelizations. However, sometimes their storing requirements make the manipulation and the extraction of information a difficult task. In this sense, several efforts have been made in order to reduce the spatial complexity of datasets always taking in account the information they contain, due to its importance and relevance, should be compromised as minimum as possible. For example, an algorithm for compression of datasets by means of quadtrees, in order to encode slices of data, is presented in [2]. Such encodings are used for discovering similarities between consecutive slices. In [3], 3D medical datasets are compressed via a method sustained in the use of octrees. Both works share us evidence of the spatial conciseness provided by considering the use of Solid Representation Schemes. This work is devoted to present an alternative representation for datasets whose color scales are not binary (in [4] is presented a methodology designed specifically for 3D datasets with black & white color scale). The main idea is to specify (n-1)D datasets, n≥2, as nD polytopes where the nth dimension corresponds to color. Then, the nD representation can be concisely expressed and manipulated through a polytopes’ representation scheme: the Extreme Vertices Model in the n-Dimensional Space (nD-EVM). However, we take one additional step: a 1-Dimensional Kohonen Network (1D-KN) will be applied in order to segment datasets taking in account their geometry and topology providing by instance a nonsupervised intelligent way to compact even more the proposed nD representations. In this last sense, neural networks-based segmentation is a topic well developed in the literature. In [5] is presented the moving average self-organizing map (MA-SOM) which is applied for segmenting medical images obtained by means of X-ray computer tomography, breast ultrasound imaging, and magnetic resonance imaging. In [6], Kohonen networks are used together with a threshold technique in order to segment satellite images. There is a review of segmenting methods based on clustering and neural networks approaches presented in [7]. In such work some experiments are presented based on the use of Multilayer Perceptrons trained with the well-known Backpropagation Algorithm. The paper by Jiang et al. [8] presents a survey of application of Neural Networks for medical support in processing images in tasks such as Image Segmentation, Edge Detection, and Computer Aided Diagnosis by means of application of the Multilayer Perceptrons, Hopfield Networks, and Self-Organizing Maps, among others. These works exemplify how the Artificial Neural Networks approach has gained confidence among Image Processing researchers due to valuable properties such as robustness to noise, plasticity, parallelism, and computational efficiency.This work is organized as follows: Section2 will describe the fundamentals behind the nD-EVM. The methodology for the conversion of a (n-1)D hypervoxelization dataset to a nD-EVM is described in Section 3. Also, there will be presented some examples of datasets expressed under the nD-EVM. By comparing the storing requirements between the original and the nD-EVM representations it is established the first level of conciseness of our proposal. Section 4 describes the fundamentals behind the 1D-KNs. In Section 5 it is described the way a 1D-KN assists us in the automatic nonsupervised segmentation of a dataset. In Section 6 how the classification provided by our 1D-KNs gives shape to the second level of conciseness by describing some examples and their final spatial requirements is presented. Section 7 provides arguments to sustain the segmentations that have been produced have good quality and they are even better than those segmentations produced by simple and direct classification based only in color intensities. For this purpose, some error functions are introduced. Finally, Section 8 presents our conclusions and lines for future research.


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

This section is a summary of results originally presented in [9, 10]. For the sake of brevity, only the required concepts for the purpose of this work are presented and some propositions are only enunciated. More details and formal proofs can be found in the two abovementioned references. Furthermore, in the following Sections we will make brief mentions of more concepts, applications, and algorithms, under the context of the nD-EVM, and the references where they are presented and described with enough detail.


### 2.1. Preliminary Background: then-Dimensional Orthogonal Pseudopolytopes (nD-OPPs)

Definition 1.
A singularn-Dimensional hyperbox in the n-Dimensional Euclidean Space is the continuous function
(2)In:0,1n⟶0,1nx⟼Inx=x.Definition 2.
For alli=1,2,…,n the two singular (n-1)D hyperboxes I(i,0)n and I(i,1)n are defined as follows. If x∈[0,1]n-1 then
(3)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 3.
In a general singularnD hyperbox c the (i,α) cell is defined as c(i,α)=c∘I(i,α)n.Definition 4.
The orientation of a cellc∘I(i,α)n is given by (-1)α+i.Definition 5.
An(n-1)D oriented cell is given by the scalar-function product (-1)i+α·c∘I(i,α)n.Definition 6.
A formal linear combination of singular generalkD hyperboxes, 1≤k≤n, for a closed set A is called a k-chain.Definition 7 (see [11]).
Given a singularnD hyperbox In the (n-1)-chain, called the boundary of In, is given by
(4)∂In=∑i=1n∑α=0,1-1i+α·I(i,α)n.Definition 8 (see [11]).
Given a singular generalnD hyperbox c the (n-1)-chain, called boundary of c, is defined by
(5)∂c=∑i=1n∑α=0,1-1i+α·c∘I(i,α)n.Definition 9 (see [11]).
The boundary of ann-chain ∑ci, where each ci is a singular general nD hyperbox, is given by
(6)∂∑ci=∑∂ci.Definition 10.
A collectionc1,c2,…,ck, 1≤k≤2n, of general singular nD hyperboxes is a combination of nD hyperboxes if and only if
(7)⋂α=1kcα0,1n=0,…,0︸n∧∀i,j,i≠j,1≤i,j≤kci0,1n≠cj0,1n.
In the above definition the first part of the conjunction establishes that the intersection between all thenD general singular hyperboxes is the origin, while the second part establishes that there are not overlapping nD hyperboxes.Definition 11.
Ann-Dimensional Orthogonal Pseudopolytope p, or just an nD-OPP p, will be an n-chain composed by nD hyperboxes arranged in such way that by selecting a vertex, in any of these hyperboxes, we have that such vertex describes a combination of nD hyperboxes composed up to 2n hyperboxes.


### 2.2. ThenD-EVM: Foundations

Definition 12 (see [10]).
Letc be a combination of hyperboxes in the n-Dimensional Euclidean Space. An Odd Edge will be an edge with an odd number of incident hyperboxes of c.Definition 13 (see [10]).
A brink, or extended edge, is the maximal uninterrupted segment, built out of a sequence of collinear and contiguous odd edges of annD-OPP.Definition 14 (see [10]).
The Extreme Vertices of annD-OPP p are the ending vertices of all the brinks in p.Definition 15 (see [10]).
Letp be an nD-OPP. The Extreme Vertices Model of p, denoted by EVMn(p), is defined as the model as only stores to all the extreme vertices of p.


### 2.3. Sections and Slices ofnD-OPPs

Definition 16.
Letp be an nD-OPP. A kD couplet of p, 1<k<n, 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 extended hypervolume if and only if e0 belongs to an (n-1)D cell present in ∂(p).Definition 17.
The Projection Operator for(n-1)D cells, points, and set of points is, respectively, defined as follows.(i)
Letc(I(i,α)n(x))=(x1,…,xn) be an (n-1)D cell embedded in the nD space. πjc(I(i,α)n(x)) will denote the projection of the cell c(I(i,α)n(x)) onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis: πjc(I(i,α)n(x))=(x1,…,x^j,…,xn).(ii)
Letv=(x1,…,xn) a point in the nD space. The projection of v in the (n-1)D space, denoted by πj(v), is given by πj(v)=(x1,…,x^j,…,xn).(iii)
LetQ be a set of points in the nD space. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in the (n-1)D space such that πj(Q)=p∈Rn-1:p=πj(x),x∈Q⊂Rn.Where x^j is the coordinate corresponding to Xj-axis to be suppressed.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Φki(p), or just Φki if no reference to p is needed, be the kth (n-1)D couplet of p which is perpendicular to Xi-axis, 1≤k≤npi.Definition 19.
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 Xi-axis, 1≤i≤n, which not coincide 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. Ski(p) will refer to the kth section of p between Φki(p) and Φk+1i(p), 1≤k<npi.Theorem 20 (see [10]).
The projection of the set of(n-1)D-couplets, πiΦki(p), of an nD-OPP p, can be obtained by computing the regularized XOR (⊗) between the projections of its previous πiSk-1i(p) and next πiSki(p) sections; that is,
(8)πiΦkip=πiSk-1ip⊗*πiSkip,∀k∈1,npi.Theorem 21 (see [10]).
The projection of any section,πiSki(p), of an nD-OPP p, can be obtained by computing the regularized XOR between the projection of its previous section, πiSk-1i(p), and the projection of its previous couplet πiΦki(p).


### 2.4. The Regularized XOR Operation on thenD-EVM

Theorem 22 (see [9]).
Letp and q be two nD-OPPs having EVMn(p) and EVMn(q) as their respective EVMs in nD space; then
(9)EVMnp⊗*q=EVMnp⊗EVMnq.This result allows expressing a formula for computingnD-OPPs’ sections from couplets and vice-versa, by means of their corresponding Extreme Vertices Models. These formulae are obtained by combining Theorem 22 with Theorem 20, and Theorem 22 with Theorem 21, respectively.Corollary 23 (see [9]).
(10)
E
V
M
n
-
1
π
i
Φ
k
i
p
=
E
V
M
n
-
1
π
i
S
k
-
1
i
p
⊗
E
V
M
n
-
1
π
i
S
k
i
p
.Corollary 24 (see [9]).
(11)
E
V
M
n
-
1
π
i
S
k
i
p
=
E
V
M
n
-
1
π
i
S
k
-
1
i
p
⊗
E
V
M
n
-
1
π
i
Φ
k
i
p
.Finally, the following corollary can be stated, which correspond to a specific situation of the XOR operand. It allows computing the union of twonD-OPPs when that specific situation is met.Corollary 25 (see [9]).
Letp and q be two disjoint or quasidisjoint nD-OPPs having EVMn(p) and EVMn(q) as their respective Extreme Vertices Models; then
(12)EVMnp∪q=EVMnp⊗EVMnq.


### 2.5. Basic Algorithms for thenD-EVM

According to previous sections the primitive operations shown in Algorithm1 can be defined based in the functions originally presented in [9]. FunctionMergeXor, according to Theorem 22, performs an XOR between two nD-EVMs; that is, it keeps all vertices belonging to either EVMn(p) or EVMn(q) and discards any vertex that belongs to both EVMn(p) and EVMn(q). Since the model is sorted, this function consists of a simple merging-like algorithm, and therefore, it runs on linear time [9, 10].Algorithm 1:Some primitive operations in the nD-EVM.
Output:
An empty
n
D
-EVM.
Procedure
InitEVM( )
{Returns the empty set.                      }
Input:
An
n
D-EVM
p
Output:
A Boolean.
Procedure
EndEVM(EVM
p
)
{Returns true if the end ofpalongX1-axis has been reached.  }
Input:
An
n
D-EVM
p
Output:
An (
n
−
1
)D-EVM embedded in (
n
−
1
)D space.
Procedure
ReadHvl(EVM
p
)
{Extracts next (n−1)D couplet perpendicular toX1-axis fromp.  }
Input:
Two
n
D-EVMs
p
and
q
.
Output:
An
n
D-EVM
Procedure
MergeXor(EVM
p
, EVM
q
)
{Applies the Exclusive OR operation to the vertices ofpandq
and returns the resulting set.                   }
Input:
An
n
D-EVM
p
Output:
A Boolean.
Procedure
IsEmpty(EVM
p
)
{Returns true ifpis an empty set.                 }From the above primitive operations, Algorithms2 and 3 are derived. Algorithm 4 computes the sequence of sections of an nD-OPP p from its nD-EVM using the previous functions. It sequentially reads the projections of the (n-1)D coupletshvl of polytope p. Then it computes the sequence of sections using functionGetSection. Each pair of sections Si and Sj (the previous and next sections about the currenthvl) is processed by a generic processing procedure (calledProcess), which performs the desired actions upon Si and Sj.Algorithm 2:Computing sections from couplets.
Input:
An (
n
−
1
)D-EVM corresponding to section
S
.
An (n−1)D-EVM corresponding to couplet hvl.
Output:
An (
n
−
1
)D-EVM.
Procedure
GetSection(EVM
S
, EVM
hvl
)
// Returns the projection of the next section of an nD-OPP whose previous section isS.
returnMergeXor(S,hvl)
end-of-procedureAlgorithm 3:Computing couplets from sections.
Input:
An (
n
−
1
)D-EVM corresponding to section
S
i
.
An (n−1)D-EVM corresponding to sectionSj.
Output:
An (
n
−
1
)D-EVM.
Procedure
GetHvl(EVM
S
i
, EVM
S
j
)
// Returns the projection of the couplet between consecutive sectionsSiandSj.
returnMergeXor(Si,Sj)
end-of-procedureAlgorithm 4:Computing the sequence of sections from an nD-OPP p represented through the nD-EVM.
Input:
An
n
D-EVM
p
.
Procedure
EVM_to_SectionSequence(EVM
p
)
EVMhvl   // Current couplet.
EVMSi,Sj  // Previous and next sections about hvl.
hvl= InitEVM( )
Si= InitEVM( )
Sj= InitEVM( )
hvl= ReadHvl(p)
while(Not(EndEVM(p)))
S
j
= GetSection(
S
i
,
hvl
)
Process(
S
i
,
S
j
)
S
i
=
S
j
hvl
= ReadHvl(
p
)
// Read next couplet.
end-of-while
end-of-procedure


## 2.1. Preliminary Background: then-Dimensional Orthogonal Pseudopolytopes (nD-OPPs)

Definition 1.
A singularn-Dimensional hyperbox in the n-Dimensional Euclidean Space is the continuous function
(2)In:0,1n⟶0,1nx⟼Inx=x.Definition 2.
For alli=1,2,…,n the two singular (n-1)D hyperboxes I(i,0)n and I(i,1)n are defined as follows. If x∈[0,1]n-1 then
(3)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 3.
In a general singularnD hyperbox c the (i,α) cell is defined as c(i,α)=c∘I(i,α)n.Definition 4.
The orientation of a cellc∘I(i,α)n is given by (-1)α+i.Definition 5.
An(n-1)D oriented cell is given by the scalar-function product (-1)i+α·c∘I(i,α)n.Definition 6.
A formal linear combination of singular generalkD hyperboxes, 1≤k≤n, for a closed set A is called a k-chain.Definition 7 (see [11]).
Given a singularnD hyperbox In the (n-1)-chain, called the boundary of In, is given by
(4)∂In=∑i=1n∑α=0,1-1i+α·I(i,α)n.Definition 8 (see [11]).
Given a singular generalnD hyperbox c the (n-1)-chain, called boundary of c, is defined by
(5)∂c=∑i=1n∑α=0,1-1i+α·c∘I(i,α)n.Definition 9 (see [11]).
The boundary of ann-chain ∑ci, where each ci is a singular general nD hyperbox, is given by
(6)∂∑ci=∑∂ci.Definition 10.
A collectionc1,c2,…,ck, 1≤k≤2n, of general singular nD hyperboxes is a combination of nD hyperboxes if and only if
(7)⋂α=1kcα0,1n=0,…,0︸n∧∀i,j,i≠j,1≤i,j≤kci0,1n≠cj0,1n.
In the above definition the first part of the conjunction establishes that the intersection between all thenD general singular hyperboxes is the origin, while the second part establishes that there are not overlapping nD hyperboxes.Definition 11.
Ann-Dimensional Orthogonal Pseudopolytope p, or just an nD-OPP p, will be an n-chain composed by nD hyperboxes arranged in such way that by selecting a vertex, in any of these hyperboxes, we have that such vertex describes a combination of nD hyperboxes composed up to 2n hyperboxes.


## 2.2. ThenD-EVM: Foundations

Definition 12 (see [10]).
Letc be a combination of hyperboxes in the n-Dimensional Euclidean Space. An Odd Edge will be an edge with an odd number of incident hyperboxes of c.Definition 13 (see [10]).
A brink, or extended edge, is the maximal uninterrupted segment, built out of a sequence of collinear and contiguous odd edges of annD-OPP.Definition 14 (see [10]).
The Extreme Vertices of annD-OPP p are the ending vertices of all the brinks in p.Definition 15 (see [10]).
Letp be an nD-OPP. The Extreme Vertices Model of p, denoted by EVMn(p), is defined as the model as only stores to all the extreme vertices of p.


## 2.3. Sections and Slices ofnD-OPPs

Definition 16.
Letp be an nD-OPP. A kD couplet of p, 1<k<n, 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 extended hypervolume if and only if e0 belongs to an (n-1)D cell present in ∂(p).Definition 17.
The Projection Operator for(n-1)D cells, points, and set of points is, respectively, defined as follows.(i)
Letc(I(i,α)n(x))=(x1,…,xn) be an (n-1)D cell embedded in the nD space. πjc(I(i,α)n(x)) will denote the projection of the cell c(I(i,α)n(x)) onto an (n-1)D space embedded in nD space whose supporting hyperplane is perpendicular to Xj-axis: πjc(I(i,α)n(x))=(x1,…,x^j,…,xn).(ii)
Letv=(x1,…,xn) a point in the nD space. The projection of v in the (n-1)D space, denoted by πj(v), is given by πj(v)=(x1,…,x^j,…,xn).(iii)
LetQ be a set of points in the nD space. The projection of the points in Q, denoted by πj(Q), is defined as the set of points in the (n-1)D space such that πj(Q)=p∈Rn-1:p=πj(x),x∈Q⊂Rn.Where x^j is the coordinate corresponding to Xj-axis to be suppressed.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Φki(p), or just Φki if no reference to p is needed, be the kth (n-1)D couplet of p which is perpendicular to Xi-axis, 1≤k≤npi.Definition 19.
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 Xi-axis, 1≤i≤n, which not coincide 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. Ski(p) will refer to the kth section of p between Φki(p) and Φk+1i(p), 1≤k<npi.Theorem 20 (see [10]).
The projection of the set of(n-1)D-couplets, πiΦki(p), of an nD-OPP p, can be obtained by computing the regularized XOR (⊗) between the projections of its previous πiSk-1i(p) and next πiSki(p) sections; that is,
(8)πiΦkip=πiSk-1ip⊗*πiSkip,∀k∈1,npi.Theorem 21 (see [10]).
The projection of any section,πiSki(p), of an nD-OPP p, can be obtained by computing the regularized XOR between the projection of its previous section, πiSk-1i(p), and the projection of its previous couplet πiΦki(p).


## 2.4. The Regularized XOR Operation on thenD-EVM

Theorem 22 (see [9]).
Letp and q be two nD-OPPs having EVMn(p) and EVMn(q) as their respective EVMs in nD space; then
(9)EVMnp⊗*q=EVMnp⊗EVMnq.This result allows expressing a formula for computingnD-OPPs’ sections from couplets and vice-versa, by means of their corresponding Extreme Vertices Models. These formulae are obtained by combining Theorem 22 with Theorem 20, and Theorem 22 with Theorem 21, respectively.Corollary 23 (see [9]).
(10)
E
V
M
n
-
1
π
i
Φ
k
i
p
=
E
V
M
n
-
1
π
i
S
k
-
1
i
p
⊗
E
V
M
n
-
1
π
i
S
k
i
p
.Corollary 24 (see [9]).
(11)
E
V
M
n
-
1
π
i
S
k
i
p
=
E
V
M
n
-
1
π
i
S
k
-
1
i
p
⊗
E
V
M
n
-
1
π
i
Φ
k
i
p
.Finally, the following corollary can be stated, which correspond to a specific situation of the XOR operand. It allows computing the union of twonD-OPPs when that specific situation is met.Corollary 25 (see [9]).
Letp and q be two disjoint or quasidisjoint nD-OPPs having EVMn(p) and EVMn(q) as their respective Extreme Vertices Models; then
(12)EVMnp∪q=EVMnp⊗EVMnq.


## 2.5. Basic Algorithms for thenD-EVM

According to previous sections the primitive operations shown in Algorithm1 can be defined based in the functions originally presented in [9]. FunctionMergeXor, according to Theorem 22, performs an XOR between two nD-EVMs; that is, it keeps all vertices belonging to either EVMn(p) or EVMn(q) and discards any vertex that belongs to both EVMn(p) and EVMn(q). Since the model is sorted, this function consists of a simple merging-like algorithm, and therefore, it runs on linear time [9, 10].Algorithm 1:Some primitive operations in the nD-EVM.
Output:
An empty
n
D
-EVM.
Procedure
InitEVM( )
{Returns the empty set.                      }
Input:
An
n
D-EVM
p
Output:
A Boolean.
Procedure
EndEVM(EVM
p
)
{Returns true if the end ofpalongX1-axis has been reached.  }
Input:
An
n
D-EVM
p
Output:
An (
n
−
1
)D-EVM embedded in (
n
−
1
)D space.
Procedure
ReadHvl(EVM
p
)
{Extracts next (n−1)D couplet perpendicular toX1-axis fromp.  }
Input:
Two
n
D-EVMs
p
and
q
.
Output:
An
n
D-EVM
Procedure
MergeXor(EVM
p
, EVM
q
)
{Applies the Exclusive OR operation to the vertices ofpandq
and returns the resulting set.                   }
Input:
An
n
D-EVM
p
Output:
A Boolean.
Procedure
IsEmpty(EVM
p
)
{Returns true ifpis an empty set.                 }From the above primitive operations, Algorithms2 and 3 are derived. Algorithm 4 computes the sequence of sections of an nD-OPP p from its nD-EVM using the previous functions. It sequentially reads the projections of the (n-1)D coupletshvl of polytope p. Then it computes the sequence of sections using functionGetSection. Each pair of sections Si and Sj (the previous and next sections about the currenthvl) is processed by a generic processing procedure (calledProcess), which performs the desired actions upon Si and Sj.Algorithm 2:Computing sections from couplets.
Input:
An (
n
−
1
)D-EVM corresponding to section
S
.
An (n−1)D-EVM corresponding to couplet hvl.
Output:
An (
n
−
1
)D-EVM.
Procedure
GetSection(EVM
S
, EVM
hvl
)
// Returns the projection of the next section of an nD-OPP whose previous section isS.
returnMergeXor(S,hvl)
end-of-procedureAlgorithm 3:Computing couplets from sections.
Input:
An (
n
−
1
)D-EVM corresponding to section
S
i
.
An (n−1)D-EVM corresponding to sectionSj.
Output:
An (
n
−
1
)D-EVM.
Procedure
GetHvl(EVM
S
i
, EVM
S
j
)
// Returns the projection of the couplet between consecutive sectionsSiandSj.
returnMergeXor(Si,Sj)
end-of-procedureAlgorithm 4:Computing the sequence of sections from an nD-OPP p represented through the nD-EVM.
Input:
An
n
D-EVM
p
.
Procedure
EVM_to_SectionSequence(EVM
p
)
EVMhvl   // Current couplet.
EVMSi,Sj  // Previous and next sections about hvl.
hvl= InitEVM( )
Si= InitEVM( )
Sj= InitEVM( )
hvl= ReadHvl(p)
while(Not(EndEVM(p)))
S
j
= GetSection(
S
i
,
hvl
)
Process(
S
i
,
S
j
)
S
i
=
S
j
hvl
= ReadHvl(
p
)
// Read next couplet.
end-of-while
end-of-procedure


## 3. Representing Hypervoxelization Datasets throughnD Orthogonal Polytopes

The conversion of a(n-1)D hypervoxelization to a nD polytope, and therefore to a nD-EVM, is in fact a straight procedure. The methodology to be described in this Section was originally presented, for the 4D case, in [12]. As commented in Section 1, the proposal is oriented to color spaces with three or more values. If it is the case that datasets have binary intensity values, then refer to [4], where a more appropriate representation is described. It is assumed the intensities of each hypervoxel are expressed as a single number.AnD hyperprism is a polytope generated by the parallel motion of an (n-1)D polytope; it is bounded by the (n-1)D polytope in its initial and final positions and by several (n-1)D hyperprisms [13, 14]. In this sense, each hypervoxel in a (n-1)D dataset is extruded towards the nth Dimension; that is, it is converted in a nD hyperprism whose bases are precisely the original hypervoxel and its height is given by its corresponding intensity-plus-one value in the dataset. The vertices’ coordinates X1,X2,…,Xn-1 in the hyperprism’s bases correspond to the original hypervoxel’s coordinates. The inferior base’s points have their Xn coordinate equal to zero, while in the remaining vertices the Xn coordinate is equal to the intensity-plus-one value (see Figure 1 for an example under the instance n=4). Let us call xf to the set composed by the nD hyperprisms (the extruded hypervoxels) of the extruded (n-1)D dataset.Extruding a voxel towards the fourth dimension. The result is a 4D hyperprism whose height is determined by the voxel’s intensity color.
(a)
(b)Letpri be a nD hyperprism in xf and npr the number of prisms in that set: npr is in fact equal to the number of hypervoxels in the original dataset. Since all hyperprisms in xf are quasidisjoint nD-OPPs, the extreme vertices, of the whole nD extruded dataset, can be easily obtained by computing the regularized union of all the hyperprisms in xf. Hence, Corollary 25 is applied in the following way:
(13)EVMnF=⨂i=1nprEVMnpri∈xf,
where F is the nD-OPP that represents the union of all the hyperprisms in xf. By this way, it is obtained a representation for a (n-1)D Dataset through a nD-OPP and the nD-EVM.Now we describe some first results related to the conversion from voxelizations (3D hypervoxelizations) to our proposed representation. Such datasets were taken fromThe Volume Library [15], and the University of Iowa’s Department of Radiology [16]. Datasets’ visualizations shown in Table 1 were obtained via a volume rendering software available at [17]. Table 1 also shows the space complexity measures obtained when the considered voxelizations were converted to 4D-OPPs and the nD-EVM. Now, let p be a dataset expressed under a (n-1)D hypervoxelization with size (x1Size×x2Size×⋯×xn-1Size) and with EVMn(p) as its corresponding nD-EVM. Consider the ratio [12]:
(14)x1Size·x2Size·⋯·xn-1SizeCardEVMnp.Table 1
Volume datasets used for conversion to 4D-OPPs and to be finally expressed through the 4D-EVM.
Aneurism
Statue Leg
CTMonkey
Description: rotational C-arm X-ray scan of the arteries of the right half of a human head. A contrast agent was injected into the blood and an aneurism is present.
Description: CT scan of a leg of a bronze statue.
Description: registered Monkey Head
Voxelization size:(256 × 256 × 256) ≡ 16,777,216
Voxelization size:(341 × 341 × 93) ≡ 10,814,133
Voxelization size:(256 × 256 × 62) ≡ 4,063,232
4D-EVM Size: 1,317,008
4D-EVM Size: 8,858,034
4D-EVM Size: 3,573,172For example, see modelAneurism (Table 1). Its source voxelization has size (256 × 256 × 256) which implies that it is required to store 16,777,216 voxels. The 4D-EVM associated toAneurism has 1,317,008 extreme vertices. Hence, the proposed ratio gives the value 12.7388 which tell us the number of stored voxels that belong to the original representation of the object is precisely 12.7388 times greater than the number of obtained extreme vertices. Table 2 shows the ratio Number-of-voxels/Number-of-Extreme-Vertices for the models described in Table 1. The value shared by the ratio depends on the topology and geometry of the objects being modeled, but it shows how some conciseness is gained, related to storing requirements, when they are represented through the nD-EVM.Table 2
The ratio number of voxels/number of extreme vertices for datasets shown in Table1.
Objectp
Voxelization size(number of voxels)
Card(EVM4(p))(number of extreme vertices)
x
1
Size
⋅
x
2
Size
⋅
x
3
Size
Card
(
EV
M
4
(
p
)
)
Aneurism
16,777,216
1,317,008
12.7388
Statue Leg
10,814,133
8,858,034
1.2208
CT Monkey
4,063,232
3,573,172
1.1371Tables3, 4, and 5 show some 3D couplets obtained from datasetsAneurism,CT-Monkey, andStatue Leg, respectively. 3D-EVM visualizations from Tables 3 to 6 were achieved by means of visualization software developed in [18–20]. Table 6 shows some 2D sections corresponding to one of the 3D couplets from the modelCT-Monkey. There are shown, by direct application of Algorithm 4, 22 of these 2D sections which allow understand the internal organization of the selected 3D couplet. It is possible to visualize some internal bone structures associated to the monkey’s cranium.Table 3
Some 3D Couplets, perpendicular to color axis, extracted from the 4D-EVM associated to datasetAneurism.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 3,535
3D Couplet 43CCL_EVM3(π4(Φ434)) = 724
3D Couplet 83CCL_EVM3(π4(Φ834)) = 394
3D Couplet 123CCL_EVM3(π4(Φ1234)) = 285
3D Couplet 163CCL_EVM3(π4(Φ1634)) = 210
3D Couplet 203CCL_EVM3(π4(Φ2034)) = 192Table 4
Some 3D Couplets, perpendicular to color axis, extracted from the 4D-EVM associated to datasetCT-Monkey.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 22,892
3D Couplet 23CCL_EVM3(π4(Φ234)) = 2,623
3D Couplet 63CCL_EVM3(π4(Φ634)) = 1,736
3D Couplet 103CCL_EVM3(π4(Φ1034)) = 1,613
3D Couplet 143CCL_EVM3(π4(Φ1434)) = 1,548
3D Couplet 173CCL_EVM3(π4(Φ1734)) = 1,558Table 5
Some 3D Couplets, perpendicular to color axis, extracted from the 4D-EVM associated to datasetStatue Leg.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 113,237
3D Couplet 23CCL_EVM3(π4(Φ234)) = 2,921
3D Couplet 103CCL_EVM3(π4(Φ1034)) = 1,981
3D Couplet 143CCL_EVM3(π4(Φ1434)) = 3,362
3D Couplet 203CCL_EVM3(π4(Φ2034)) = 1,129
3D Couplet 243CCL_EVM3(π4(Φ2434)) = 77Table 6
Visualizing some 2D Sections perpendicular toX1-axis which were processed from a 3D Couplet of the 4D-OPP associated to dataset CT-Monkey.
3D Couplet 18
2D Section  1
2D Section  21
2D Section  31
2D Section  41
2D Section  51
2D Section  61
2D Section  71
2D Section  81
2D Section  91
2D Section  111
2D Section  121
2D Section  131
2D Section  141
2D Section  151
2D Section  161
2D Section  191
2D Section  201
2D Section  211
2D Section  221
2D Section  231
2D Section  241
2D Section  251In [21] is presented an nD-EVM-based algorithm for computing Connected Components Labeling (CCL) over an nD-OPP. It is well known CCL is one of the most important tools in image processing and computer vision. The main idea is to assign labels to the pixels in an image such that all pixels that belong to a same Connected Component (CC) have the same label [22, 23]. The direct application of our CCL-EVM-Based algorithm over the 4D-EVMs associated to our three datasets will report only one component. This is because of the way the original 4D-OPPs were built (see (13)). Now, let CCL_EVM3(p) be the output shared by our mentioned CCL-EVM-Based algorithm when is sent as input a 3D-OPP p, expressed under the nD-EVM. In other words, CCL_EVM3(p) gives the number of 3D CCs present in p. For specific details about our CCL-EVM-Based algorithm refer to [21]. In Tables 3 to 5 we also make mention of the number of CCs present in the shown 3D couplets. These data is going to be part of an analysis to be performed in Section 6.The importance behind a dataset is the information can be obtained from it. If the datasets are represented through thenD-EVM then the extraction of its couplets perpendicular to Xn-axis will provide a classification of the elements in the original model according to their color intensities. Or in others words, we obtain a dataset’s segmentation based exclusively on color intensities. Given a dataset based on a scale of K intensities, then it is possible to obtain at most, from its corresponding nD-OPP, K+1  (n-1)D couplets perpendicular to the axis associated to color. The “extra” couplet, in fact the first couplet, is the result of the union of all the inferior bases of the nD hyperprisms in xf (the set composed by the dataset’s extruded hypervoxels): the points in such bases have value zero for the coordinate associated to color. Under this reasoning, Tables 3, 4, and 5 present part of the color-intensities-based segmentation achieved in our considered datasets.It is possible that color intensities correspond to physical properties. For example, in a 3D medical dataset intensities could refer to certain tissues. Hence, by extracting 3D couplets perpendicular to color axis we could obtain, for a given couplet, only those parts of the 3D dataset with the same type of tissue. The type of material is, in this case, assumed to be defined by the color intensity of the voxels in the original dataset. The projection of each couplet, perpendicular to the axis associated to color, in anD-EVM, is in fact a (n-1)D-EVM which in time corresponds to a binary dataset because it only contains material of the same type. Hence, it is possible to apply Algorithm 4 to these (n-1)D couplets in order to obtain their associated (n-2)D sections. These sections will share a description of the interior of the homogeneous object with the objective of performing the appropriate analyses according to the application, as seen previously in the example described in Table 6.This Section has focused about the representation of hypervoxelizations throughnD-OPPs which in time are expressed in the nD-EVM. Moreover, we have seen how the basic procedures under the Extreme Vertices Model share the extraction of useful information related to the original datasets: the classification of their elements according to intensities via (n-1)D couplets perpendicular to color axis. Likewise, it is possible to compute other geometrical and topological interrogations over an nD-EVM. By this way it could be obtained much more information and properties about the datasets. Furthermore, there are well specified procedures under the nD-EVM which allow performing Regularized Boolean Operations, Polytopes Splitting, Discrete Compactness Computation, Morphological Operations, Connected Components Labeling, Boundary Extraction, among others. In [9, 10, 12, 21, 24, 25] there are described with enough detail algorithms based in the nD-EVM which are useful and efficient for performing these interrogations and/or manipulations.According to the above discussion, if datasets are represented through thenD-EVM then the extraction of its couplets will provide a classification of the elements in the original model according to their color intensities. The projection of each couplet, perpendicular to the axis associated to color is in fact a (n-1)D-EVM which in time corresponds to a binary dataset because it only contains material of the same type, in this case, the same intensity. We are now in a critical point where the next logical step is given by the consideration of an additional approach in such way that the points in a dataset could be characterized by taking in account not only their color intensity but their class. Due to the presence of scanning noise and artifacts, a classification based only in intensities is sometimes not enough because points that should belong to the same class could be characterized as distinct points and therefore assigned to distinct classes, hence, our nD representation will integrate each point in distinct (n-1)D couplets. Let an intelligent approach, such as an Artificial Neural Network, be responsible for automatically identifying the classes of points present in a multidimensional dataset by taking in account their geometry, topology, neighborhood, and so forth. Once the classification is achieved, then the corresponding conversion to our proposed n-Dimensional representation could take place. It should be possible to assign to each class a coordinate on the nth dimension in such way (n-1)D couplets perpendicular to the nth axis now correspond to sets of points, in the original dataset, that belong to the same class. It is also hypothesized that by considering more appropriate points classification, a much better conciseness should be obtained. This is the line or reasoning which is going to be explored in the following Sections.


## 4. A Survey on 1-Dimensional Kohonen Networks (1D-KNs)

A Kohonen Network withψ inputs and O neurons may be used to classify points embedded in an ψ-Dimensional space into O categories [26, 27]. Input points have the form (x1,…,xi,…,xψ). Each neuron j, j=1,2,…,O, has associated an ψ-Dimensional Weights Vector which has a representation of its corresponding class κj. All these vectors have the form Wj=(wj,1,…,wj,ψ), j=1,2,…,O.A set of training points are presented to the networkT times. According to [28], all values of Weight Vectors should be randomly initialized. In the tth presentation, t=1,2,…,T, the neuron whose Weights Vector Wj, 1≤j≤O, is the most similar to the input point P is chosen as Winner Neuron. In the model proposed by Kohonen, such selection is based on the Squared Euclidean Distance. The selected neuron is that with the minimal distance between its Weights Vector and the input point P:
(15)dj=∑i=1ψPi-Wj,it2,1≤j≤O.Once thelth Winner Neuron, 1≤l≤O, in the tth presentation, has been identified each one of the network’s weights vectors is updated according to:
(16)Wj,it+1=Wj,it+1t+1φj,lPi-Wj,it,i=1,2,…,ψ,j=1,2,…,O,
where the term 1/(t+1) is the learning coefficient and φ(j,l) is a neighborhood function that denotes the distance between the Winner Neuron l and the neuron j. For neurons close enough to the winner neuron, φ(j,l) should be a value near to 1. On the other hand, φ(j,l) is close to zero for those neurons characterized as distant to the Winner Neuron.When theT presentations have been achieved, the values of the Weights Vectors correspond to coordinates of the “gravity centers” of the clusters of the O categories.


## 5. Multidimensional Hypervoxelizations’ Segmentation Achieved by 1D-KNs

Nonsupervised segmentation of datasets has great potential in the practice, but this task is complex for several reasons, being one of them, for example, the datasets’ acquisition process which could introduce noise and artifacts which are difficult to correct. As commented previously, the specific problem now to be under attack is the automatic nonsupervised segmentation based on the assistance of a 1D-KN. It is expected there could be identified, during its training processes, the proper representations for a previously established number of classes. Hence, a dataset can be segmented in such way each type of region is appropriately identified. Many methods for description, object recognition or indexing are sustained on a preprocessing based on automatic segmentation [22, 29, 30]. This Section describes our methodology which is inspired in some facts established originally in [31].An aspect to be considered respect to the training sets to be used is the fact a first approach could suggest that the color intensity of each hypervoxel in a dataset can be seen as an input vector (formerly an input scalar). However, as discussed in several works, such as [32, 33], a network will be biased towards a characterization based only in intensities. It is clear each hypervoxel has an intensity which, it is understood, captures, or is associated, to a particular property (a type of tissue, material, etc.); however, it is important to consider the hypervoxels around it. The neighborhood surrounding a given hypervoxel complements the information about the properties to be identified. Let v be a hypervoxel in an (n-1)D dataset, n≥2. Given v it is possible to build a subdataset by taking those hypervoxels inside a hypercubical neighborhood of radius r and center at v. Hypervoxel v and its neighboring hypervoxels will be called a (n-1)-Dimensional mask. For example, given a 3D dataset, if we refer to 3D masks of radius r=2 then we have subdatasets of size (5 × 5 × 5) whose central voxel, with coordinates (r+1, r+1, r+1), is the one of interest and the remaining 124 voxels compose its cubical neighborhood.Now, the network’s training set is then composed by all the(n-1)D masks of radius r that can be generated in a given (n-1)D dataset. As commented in Section 4 a 1D-KN expects as input a vector, or point, embedded in the ψ-Dimensional Space. A (n-1)D mask is formerly seen as a (n-1)D array, but it is clear by stacking its columns on top of one another a vector is obtained. This straightforward procedurelinearizes a (n-1)D mask making it a suitable input for the network. The resulting vectors, composed by
(17)ψ=2r+1(n-1)
components, preserve the properties associated to the original (n-1)D masks. Each component has the color intensity of the corresponding hypervoxel in its associated (n-1)D mask. By this way, we have specified the elements that conform our proposed approach for automatic segmentation of (n-1)D hypervoxelizations. We proceed now to describe some experiments and the obtained results.Our study cases were based in the set of 3D datasets presented in Section3 plus two additional datasets described in Table 7. Both datasets were taken fromThe Volume Library [15] and the visualizations shown in Table 7 were achieved via a volume rendering software available at [17].Table 7
Additional volume datasets to be considered for automatic segmentation via a 1D Kohonen Network.
VL-Baby
VL-CT-Knee
Description: baby head.
Description: computed tomography of knee, anterior tibial osteotomy.
Voxelization size: (256× 256 × 98) ≡ 6,422,528
Voxelization size: (379× 229 × 305) ≡ 26,471,255The implemented 1D-KNs have the following topologies and training conditions:(i)
3D masks radius:r=2,(ii)
inputs:ψ = 5 × 5 × 5 = 125,(iii)
neurons (classes):O=40,(iv)
presentations:T=10.According to (16) we must define a neighborhood function. In this work we will use the following rule:
(18)φj,l=1,j=l,0,j≠l.
That is, once the Winner Neuron l has been identified, only its weights are updated as established in (16). As commented above, training sets’ cardinalities clearly depend on the value for radius r, but also relies on the dataset’s size. Because we are considering five testing voxelizations, each one to be managed by its corresponding 1D-KN, then we have to think about five different training sets. In Table 8 we can see the corresponding cardinalities of the training sets associated to each considered voxelization.Table 8
Training sets’ cardinalities for voxelizations described in Tables1 and 7.
Dataset
Voxelization size(number of voxels)
Training set’scardinality
Aneurism
16,777,216
16,003,008
Statue Leg
10,814,133
10,107,641
CT Monkey
4,063,232
3,683,232
VL-CT-Knee
26,471,255
25,396,875
VL-Baby
6,422,528
5,969,376Table9 shows the obtained distribution of the training 3D masks in each one of the available 40 classes. Firstly, according to this Table, the networks trained with 3D masks associated to datasetsAneurism, VL-CT-Knee, andVL-Baby, distributed all their 3D masks along their 40 classes. In the case for networks trained with 3D masks associated to datasetsStatue Leg andCT Monkey only 22 and 39 classes are, respectively, used. A second observation arises: in all the proposed networks there is a class which has associated more than 45% of the elements in its corresponding training set. Seeing Table 9 it is possible to identify such classes as follows.(i)
DatasetAneurism: class 4, 98.47%.(ii)
DatasetStatue Leg: class 24, 93.72%.(iii)
DatasetCT Monkey: class 27, 81.69%.(iv)
DatasetVL-CT-Knee: class 27, 48.17%.(v)
DatasetVL-Baby: class 9, 67.16%.As we will see with more detail in Section 6, we can mention in advance these abovementioned classes grouped 3D masks corresponding to empty regions in the original datasets. Members in these classes are precisely part of the point of discussion relative to the fact hypervoxelizations’ spatial complexities make sometimes difficult their manipulation and storage: under hypervoxelization representation we are also dealing with the processing and “cargo space” of empty regions. However, we will see in next Section by considering the nD-EVM model these regions can be taken in account in the representation without impacting spatial conciseness.Table 9
Classification of 3D masks according to 1D-KNs with 125 inputs, 40 output neurons, and 10 presentations.
Class
Aneurism
Statue Leg
CT Monkey
VL-CT-Knee
VL-Baby
1
3,128
5,789
8
912,693
15,469
2
21,773
6,349
16,683
117,273
8,358
3
4,862
33,243
25,979
1,901,801
25,431
4
15,758,840
29,837
31,162
3,150
58,846
5
18,296
0
13,020
3,261
1,332
6
5,927
0
14
87,610
1,139,659
7
2,231
15,417
9,116
15,387
10,155
8
3,041
128,851
6,518
4,197
3,700
9
8,320
0
8,784
8,652,128
4,009,622
10
4,753
19,665
13,841
25,555
14,959
11
3,037
13,651
34,950
435,107
13,488
12
3,564
20,424
4,360
35,484
60,688
13
8,821
25,873
2,723
2,005
4,712
14
24,639
15,408
0
1,891
2,210
15
904
0
91,616
30,631
23,891
16
3,251
51,575
106,880
2,097
41,951
17
2,377
16,316
31,121
115,289
5,112
18
101
0
111,560
1,096
29,300
19
2,610
34,834
6,353
7,794
113,790
20
3,947
0
10,229
41,661
56,087
21
9,784
17,119
3,069
25,514
3,810
22
2,762
10,638
6,144
32,693
3,229
23
3,142
45,111
258
31,775
6,435
24
18,959
9,473,821
45
6,852
21,690
25
5,640
9,689
10,385
2,035
33,498
26
3,089
0
4,694
68,408
1,323
27
930
0
3,009,111
12,234,834
49,447
28
5,513
0
17
25,474
17,353
29
5,496
11,810
7,282
34,373
23,895
30
7,333
0
1
2,489
10,582
31
5,372
0
8,586
22,581
3,057
32
4,885
0
61
138,980
9,024
33
12,722
8,559
19,599
18,576
3,405
34
6,908
0
59,738
1,315
27,012
35
1,234
0
1,906
20,623
4,184
36
117
0
5
29,828
20,019
37
8,460
113,662
6,703
78,950
32,802
38
5,258
0
5,623
8,005
3,350
39
5,368
0
6,365
127,575
6,370
40
5,614
0
8,723
89,885
50,131


## 6. The FrameworknD-EVM/Kohonen

The previously defined 1D-KNs have provided us with segmentations associated with datasets by establishing a number of classes and a size for the(n-1)D masks that describe the used training sets. As commented previously, each one of these (n-1)D masks describes in fact a subdataset by considering a hypervoxel of interest and its neighborhood of radius r. Then, the masks are sent as input to a 1D-KN and through the corresponding training process there are determined their associated classes. More specifically, once the training has finished, given a (n-1)D mask as input it is obtained as output the number of the corresponding class which is assigned only to the input mask’s central hypervoxel. Our hypervoxelizations were originally expressed with K color intensities, however, we have now through a 1D-KN these K intensities have been mapped onto a set of O elements: the number of classes established for training the 1D-KN. Therefore, the color intensity value for a hypervoxel can now be replaced by its corresponding number of associated class given as output by the network. The hypervoxelization’s original size is not affected except on its boundaries because masks of radius r cannot be completed. Therefore, to consider a hypervoxelization again as the appropriate representation for storing the segmentation achieved by means of a 1D-KN does not provides a reduction in terms of spatial complexity.Now we reconsider our process for expressing(n-1)D hypervoxelizations using the nD-EVM which was described in Section 3. We recall that given a hypervoxel with color intensity c it was obtained a nD hyperprism whose inferior base contains vertices with the same coordinates just as the vertices in the original (n-1)D hypervoxel but incorporating a nth coordinate with zero value. On the other side, vertices in the upper base also corresponded with vertices in the original hypervoxel, but in this case, the nth coordinate has value c+1. Our proposed Framework nD-EVM/Kohonen takes place when a dataset’s segmentation achieved by a 1D-KN is represented by using the nD-EVM, considering the conversion methodology abovementioned but replacing color intensity values by the class numbers generated as output by the corresponding 1D-KN. From a “n-Dimensional point of view”, the Xn-axis now is referring to the number of class which is associated a hypervoxel respect to the segmented dataset.Summarizing, the following is the workflow for our FrameworknD-EVM/Kohonen.Input. A (n-1)D hypervoxelization under K color intensities, n≥2, K≥3.Step 1.
Given valuer for radius of (n-1)D masks it is built a training set.Step 2.
Given valuesT and O for number of presentations and number of classes, respectively, it is trained a 1D-KN using as training set all the masks generated in the previous step.Step 3.
The training set is used again as input for the 1D-KN with adjusted weights. Each(n-1)D mask is sent as input to the 1D-KN and it is obtained the corresponding output: the number of its associated class. This number is assigned only to the input mask’s central hypervoxel (The remaining hypervoxels are classified in time when they take the role of central hypervoxels in their corresponding masks). Coordinates, respect to the original hypervoxelization, of the central hypervoxel in the input (n-1)D mask, are used together with its class number for building a nD hyperprism.Step 4.
All generated hyperprisms are integrated in such way it is obtained the corresponding wholenD-OPP which in turn is expressed in the nD-EVM.Output. The final nD-EVM.Just in the way we proceed in Section3, Tables 10 to 14 show some 3D couplets, perpendicular to X4-axis, obtained from our considered 5 datasets,Aneurism, CT-Monkey, Statue Leg, VL-Baby, andVL-CT-Knee, respectively, after the application of Framework nD-EVM/Kohonen. The 3D-EVM visualizations from these Tables were again achieved by means of visualization software developed in [18–20]. We remember the projection of 3D couplets under our 4D-EVM representation collect those voxels that were grouped inside the same class by the corresponding 1D-KN. We can see, for example, in Table 13, how it is possible to appreciate couplets 12, 19, and 28 were bone tissue is only present. On the other hand, 3D couplets 5, 17, 20, and 26 describe the grouping of skin tissue (and other support medical accessories). A very similar situation can be appreciated respect to voxelizationVL-CT-Knee (Table 14) where all of the shown 3D couplets, except 12, 21, and 28, correspond to different parts of bone tissue.Table 10
Some 3D couplets, perpendicular to color axis, extracted from the 4D-EVM produced by means of FrameworknD-EVM/Kohonen and associated to dataset Aneurism.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 58
3D Couplet 5CCL_EVM3(π4(Φ54)) = 78
3D Couplet 7CCL_EVM3(π4(Φ74)) = 87
3D Couplet 12CCL_EVM3(π4(Φ124)) = 412
3D Couplet 15CCL_EVM3(π4(Φ154)) = 825
3D Couplet 24CCL_EVM3(π4(Φ244)) = 660
3D Couplet 30CCL_EVM3(π4(Φ304)) = 508
3D Couplet 39CCL_EVM3(π4(Φ394)) = 239In Section5 we made mention of the fact that all considered 1D-KNs were grouping more than 45% of the elements in their training sets in just one class. This can be visually appreciated in 3D couplets 5, 27, 19, 10, and 28 from Tables 10, 11, 12, 13, and 14, respectively. All of these 3D couplets present a block-like structure whose minimal bounding box has the same dimensions than the original voxelizations minus the volume removed by those 3D masks of radius 2 that could not be completed at the datasets’ boundaries. These are the regions that correspond to empty space in the original voxelizations. In Section 5 we gave an argument regarding the observation that these 3D couplets are considered in our 4D-EVM representation. We also mentioned this empty space is precisely one of the disadvantages behind a voxelization because it only contributes to spatial complexity. Our argument serves for the purpose of touching a crucial point: the spatial complexity of the representations achieved by the Framework nD-EVM/Kohonen. Table 15 shows the cardinalities for the 4D-EVMs obtained for expressing our 5 voxelizations. We also compute (14) in order to observe the number of times our 4D models are exceeded by its original voxelizations. We can see for example, datasetCT Monkey originally required to be stored in more than 4 million voxels. In Section 3 we saw this dataset had adirect 4D-EVM representation with 3,573,172 extreme vertices: an slight improvement over the original voxelization. By taking in account the proposed framework we have were used 789,320 extreme vertices, or in other words, the original voxelization is 5.1477 times greater, in terms of spatial storage, than the final 4D-EVM’s cardinality. A more impacting example comes from datasetAneurism: the original voxelization is formed by 16,777,216 voxels; thedirect 4D-EVM representation had 1,317,008 extreme vertices; and finally, the Framework nD-EVM/Kohonen shared a 4D-EVM with 517,318 extreme vertices: giving the ratio 32.4311. We should take in account our representations are also considering the storing of the regions corresponding to empty space. This give us an advantage by storing in the same representation both the occupied and the empty space but without affecting the memory needed to store the models. These results share us evidence of the conciseness’ power achieved when the grouping properties of 1D-KNs are combined with the storing properties of a model like the nD-EVM: spatial complexity is reduced and a more appropriate segmentation is achieved, which impacts how the elements in the datasets are classified and by consequence accessed. For example, Table 16 shows some 2D sections corresponding to one of the 3D couplets from the modelCT-Monkey after the application of Framework nD-EVM/Kohonen. There are shown, via direct application of Algorithm 4, 17 of these 2D sections which allow understand the internal organization of the selected 3D couplet. It is possible to visualize some internal bone structures associated to the monkey’s cranium.Table 11
Some 3D couplets, perpendicular to color axis, extracted from the 4D-EVM produced by means of FrameworknD-EVM/Kohonen and associated to dataset CTMonkey.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 1,554
3D Couplet 6CCL_EVM3(π4(Φ64)) = 402
3D Couplet 12CCL_EVM3(π4(Φ124)) = 551
3D Couplet 15CCL_EVM3(π4(Φ154)) = 581
3D Couplet 18CCL_EVM3(π4(Φ184)) = 1,169
3D Couplet 27CCL_EVM3(π4(Φ274)) = 31
3D Couplet 31CCL_EVM3(π4(Φ314)) = 650
3D Couplet 34CCL_EVM3(π4(Φ344)) = 1,039Table 12
Some 3D couplets, perpendicular to color axis, extracted from the 4D-EVM produced by means of FrameworknD-EVM/Kohonen and associated to dataset Statue Leg.
3D Couplet 3CCL_EVM3(π4(Φ34)) = 570
3D Couplet 6CCL_EVM3(π4(Φ64)) = 527
3D Couplet 9CCL_EVM3(π4(Φ94)) = 1,089
3D Couplet 12CCL_EVM3(π4(Φ124)) = 530
3D Couplet 15CCL_EVM3(π4(Φ154)) = 77
3D Couplet 18CCL_EVM3(π4(Φ184)) = 843
3D Couplet 19CCL_EVM3(π4(Φ194)) = 5
3D Couplet 21CCL_EVM3(π4(Φ214)) = 1,059
3D Couplet 23CCL_EVM3(π4(Φ234)) = 585Table 13
Some 3D couplets, perpendicular to color axis, extracted from the 4D-EVM produced by means of FrameworknD-EVM/Kohonen and associated to dataset VL-Baby.
3D Couplet 5
3D Couplet 10
3D Couplet 12
3D Couplet 17
3D Couplet 19
3D Couplet 20
3D Couplet 26
3D Couplet 28Table 14
Some 3D couplets, perpendicular to color axis, extracted from the 4D-EVM produced by means of FrameworknD-EVM/Kohonen and associated to dataset VL-CT-Knee.
3D Couplet 3
3D Couplet 4
3D Couplet 12
3D Couplet 18
3D Couplet 21
3D Couplet 23
3D Couplet 28
3D Couplet 30
3D Couplet 33Table 15
The ratio number of voxels/number-of-extreme-vertices for datasets shown in Tables1 and 7 after processing via Framework nD-EVM/Kohonen.
Objectp
Voxelization Size(number of voxels)
Card(EVM4(p)) by Framework nD-EVM/Kohonen
x
1
Size
⋅
x
2
Size
⋅
x
3
Size
Card
(
EV
M
4
(
p
)
)
Aneurism
16,777,216
517,318
32.4311
Statue Leg
10,814,133
604,970
17.8754
CT Monkey
4,063,232
789,320
5.1477
VL-CT-Knee
26,471,255
2,799,470
9.4558
VL-Baby
6,422,528
1,136,792
5.6496Table 16
Visualizing some 2D sections perpendicular toX4-axis which were processed from one 3D couplet of the 4D-OPP associated to dataset CTMonkey after the application of Framework nD-EVM/Kohonen.
3D Couplet 15
2D Section  1
2D Section  11
2D Section  21
2D Section  31
2D Section  51
2D Section  61
2D Section  71
2D Section  91
2D Section  111
2D Section  131
2D Section  141
2D Section  161
2D Section  171
2D Section  181
2D Section  191
2D Section  201
2D Section  211


## 7. Quality of Segmentations Achieved by thenD-EVM/Kohonen Framework

In some sense, we have sustained, in implicit way, datasets’ representations generated by the FrameworknD-EVM/Kohonen provide appropriate segmentations that are in fact better than those segmentations produced by simple and direct classification based only in color intensities. Part of the asseveration is sustained in the sense our 1D-KNs classifications are taking in account geometry and topology surrounding each hypervoxel in the dataset: the concept of multidimensional mask as training element. This Section provides more formal arguments to sustain the segmentations that have been produced have good quality and they are even better than those produced by classifications based only in color intensities. For this purpose, some previously defined concepts are revisited and error functions are introduced.Original 4D-EVM representations for datasetsAneurism, CT-Monkey, andStatue Leg were described in Section 3 (Tables 3, 4, and 5). The respective visual comparison with Tables 10, 11, and 12 clearly show us how our proposed framework has provided more cohesive representations for these voxelizations. We sustain our claim by considering the number of produced 3D CCs. Let function CCL3 be defined as follows:
(19)CCL3p=∑i=1np4CCL_EVM3π4Φi4p,
where np4 denotes the number of 3D couplets perpendicular to X4-axis for 4D-OPP p expressed under the EVM, and function CCL_EVM3, originally defined in Section 3, shares the number of 3D CCs for a 3D-OPP, a 3D couplet in the current instance. Then, it is clear CCL3 shares us the total number of 3D CCs present in all couplets, perpendicular to X4-axis, associated to the input 4D-EVM p. We recall CCs computation can be achieved by our previously mentioned CCL-EVM-Based algorithm whose specific details are presented in [21]. We compute CCL3 for representations of datasetsAneurism, Statue Leg, andCT-Monkey. Table 17 presents the corresponding values for bothdirect 4D-EVM representation (Section 3) and under Framework nD-EVM/Kohonen. The same source data were used for building both representations, but as seen in Table 17, our framework produces much more cohesive and compact representations. A counterargument to this claim could arise by establishing the gained compaction and cohesion is product of the fact our 1D-KNs “forces” the data to be classified under 40 classes while the segmentation based on intensity has “more space” because 256 classes are available. We attack this situation by proposing some error functions. Let vector [g1,i,jg2,i,j⋯gψ,i,j]T be alinearized(n-1)D mask in a training set TS, such that it was characterized as part of class κj once a 1D-KN was trained precisely with TS. Index i only refers to an arbitrary position assigned to the mask belonging class κj. Now consider to Weights Vector Wj=[W1,jW2,j⋯Wψ,j]T associated to class κj. Wj can be also seen as alinearized(n-1)D mask and for instance it can be also compared with those (n-1)D masks located in the corresponding class [34]. We define then to the “Error in Classjrespect toWj”, denoted by ErrjW, as [34]
(20)ERRjW=∑i=1Card(κj)∑p=1ψgp,i,j-Wp,j.
It is clear by computing ERRjW we are obtaining the differences existing between each (n-1)D mask that belongs to class j with Weights Vector Wj, which in fact is its representative. We can think if ERRjW has a low value then Wj is a good representative for all the (n-1)D masks belonging to κj. This reasoning can be extended for considering all the representatives of all classes for a given 1D-KN. Therefore, we have a value for measuring the classification quality shared by a network. We say the “Global Error for Training Set TS respect to its Representatives”, denoted by ERRTSW, can be defined as [34]
(21)ERRTSW=∑j=1OERRjW.
Prior to make a comparison between the two presented 4D representations by using the above error functions we face the situation related to the fact that segmentation based on intensities only considers the color intensity of the hypervoxel of interest and nothing more; while our Framework nD-EVM/Kohonen requires, as specified in Section 5, the creation of a training set whose elements are (n-1)D masks which contain the hypervoxels of interest and also their neighborhoods of radius r. This situation recall us we are considering different aspects for the considered segmentations, however, the fundament behind the use of (n-1)D masks is to take in account geometrical and topological properties such that a 1D-KN use them in order to achieve and to enhance the classification. On the other hand, because of simplicity in implementing color-intensity based segmentation the notion of a representative for a class is absent: the hypervoxels included in a class share the same intensity. In order to apply our proposed error functions to classification achieved only by color intensity we build a representative for elements in a same class. Consider a hypervoxel v with color intensity c+1, then, it is located in class κc+1. Now, we will consider the neighborhood of radius r for the given hypervoxel v respect to the original hypervoxelization. Then, we are defining a (n-1)D mask whose center is v. Given value for r, the corresponding (n-1)D mask also have 2r+1(n-1) elements (Equation (17)). The mask can be alsolinearized in such way we obtain the vector representation [g1,i,c+1g2,i,c+1⋯gψ,i,c+1]T. Index i only refers to an arbitrary position assigned to the mask belonging class κc+1. One of the elements in the vector is precisely color intensity, c+1, of central hypervoxel v while the rest are the color intensities of the hypervoxels inside its neighborhood. Given the above elements we build a representative of class κc+1, but under color-intensity based segmentation (CIBS), as follows:
(22)Wc+1CIBS=1Cardκc+1∑i=1Cardκc+1g1,i,c+1∑i=1Cardκc+1g2,i,c+1⋮∑i=1Cardκc+1gψ,i,c+1.
That is, given the members of class κc+1, under color-intensity based segmentation, its representative has as components the average color intensity for each one of the 2r+1(n-1) positions in each one of the (n-1)D masks defined for the class’ members. On one side, we have now representatives in order to apply them over our proposed error functions. On the other side, we proceeded in the way described because if it is false our asseveration related to the fact geometry and topology described by a neighborhood enhances classification, in particular with our 1D-KNs, then the masks and representatives defined by use of (22) when applied over our error functions will report results as good, and even better, than those reported by the use of 1D-KNs. Table 18 shows the global error respect to its representatives, obtained for each one of the training sets generated with datasetsAneurism, Statue Leg andCT-Monkey. The results presented are encouraging: global errors underdirect 4D-EVM representation are 1.5877, 2.2248, and 1.6362 times greater than those obtained by Framework nD-EVM/Kohonen for our datasetsAneurism, Statue Leg andCT-Monkey, respectively. We then recur again to Table 17 where CCL3s under direct 4D-EVM representation are 6.0964, 45.031, and 18.4845 times greater than those generated by Framework nD-EVM/Kohonen for the same datasets, respectively. This experimental analysis has share us elements to sustain cohesiveness produced by our proposal is appropriate because presented measures tell us the voxels were better positioned by the 1D-KNs producing better segmentation based in information supported by (n-1)D neighborhoods.Table 17
CCL
3s’ comparisons for representation of volume datasets (see text for details).
Dataset
CCL
3 under direct 4D-EVM representation
CCL
3 under Framework nD-EVM/Kohonen
Aneurism
130,483
21,403
Statue Leg
778,137
17,280
CTMonkey
431,651
23,352Table 18
Global errors’ comparisons for representation of volume datasets (see text for details).
Dataset
ER
R
TS
W under direct 4D-EVM representation
ER
R
TS
W under Framework nD-EVM/Kohonen
Aneurism
8,707,543.1607
5,484,105.9349
Statue Leg
24,690,070.9348
11,097,469.3973
CTMonkey
17,304,147.229
10,575,227.2008


## 8. Conclusions and Future Work

In this work we have developed the FrameworknD-EVM/Kohonen whose purposes are (1) the concise representation of multidimensional datasets, and (2) a modeling of the data they contain in such way the information contained can be accessed in efficient and useful way. These purposes have been achieved by the consideration of the Extreme Vertices Model in the n-Dimensional Space as the representation scheme that provides conciseness, as seen in Sections 3 and 6, but providing an appropriate organization of datasets’ elements by means of taking in account an extra geometrical dimension whose objective is allow grouping only those elements characterized as members of the same class. Precisely, the classification process, is achieved by the use of 1-Dimensional Kohonen Networks whose task is the automatic nonsupervised characterization of the elements in a dataset. As seen in Section 5, we have defined training sets taking in account the geometry and topology surrounding each hypervoxel. The experimental results we have obtained show us the use of 1D-KNs trained according to our proposal produce classes whose members form connected components with more cohesion and more compact than those generated by segmentation achieved only by color intensity. The expressed asseverations, discussed in Section 7, have been sustained by the use of function errors that have shown, for our study cases, that classification achieved by means of 1D-KNs is a good option due to the way members in each class relate to their corresponding representatives. Moreover, we have seen these 1D-KN-assisted classifications impact even more the conciseness of the nD-EVMs obtained producing compression ratios, for our study cases, between 5.1477 and 32.4311. Summarizing, we have presented evidence related to how our established framework effectively combine the power of the nD-EVM and the 1D-KNs in order to produce very concise datasets’ representations but also providing an appropriate segmentation.In terms of lines of future research we make mention we will direct our efforts into the manipulation of datasets where hypervoxels have associated, besides spatial information, data that requires to be expressed with more than a scalar value. In fact, an immediate line of attack could be the manipulation of datasets in RGB colorspace where precisely the red, green and blue components are separated and forming a vector. We hypothesize the FrameworknD-EVM/Kohonen could be able to manipulate and represent this kind of situation in such way not only one additional dimension is required, maybe more extra dimensions are going to be taken in account.We also expect to aboard in the future the study of the utility of the classifications produced by 1D-KNs in terms of application in specific areas and by taking in account evaluation by experts. More specifically, we are going to attack the particular topic of medical datasets’ segmentations. The idea is to represent and manipulate these datasets using our FrameworknD-EVM/Kohonen but we will analyze particularly the automatic tissue classification task. In a first stage, classification is going to be automatically achieved by our 1D-KNs and it will be evaluated against segmentations produced by physicians. In a second stage there will be studied evaluations’ results and procedures, if it would be necessary, for enhancing them. In this sense we can mention some experiments have been developed, in [31, 34, 35], for automatically classifying brain tissue in Computed Tomography Brain Slices. We can mention the obtained results are encouraging. Such as in our current line of research, we aim to propose concise and useful representations for these medical datasets but without compromising the information they contain because of its obvious importance and relevance. Finally, in a more independent-of-the-application point of view, we are also going to study algorithmic approaches in order to automatically avoid the phenomenon of under and over segmentation and the way these methodologies can be incorporated in the Framework nD-EVM/Kohonen.



---

*Source: 676780-2015-03-01.xml*