# An Adaptive Image Encryption Scheme Guided by Fuzzy Models

Mahdi Shariatzadeh  Mohammad Javad Rostami  Tel:+989133417396,
Fax:+3432477400, Email address<EMAIL_ADDRESS><EMAIL_ADDRESS>Mahdi
Eftekhari  Department of Computer Engineering, Shahid Bahonar University of
Kerman, Kerman, Iran

###### Abstract

A new image encryption scheme using the advanced encryption standard (AES), a
chaotic map, a genetic operator, and a fuzzy inference system is proposed in
this paper. In this work, plain images were used as input, and the required
security level was achieved. Security criteria were computed after running a
proposed encryption process. Then an adaptive fuzzy system decided whether to
repeat the encryption process, terminate it, or run the next stage based on
the achieved results and user demand. The SHA-512 hash function was employed
to increase key sensitivity. Security analysis was conducted to evaluate the
security of the proposed scheme, which showed it had high security and all the
criteria necessary for a good and eﬀicient encryption algorithm were met.
Simulation results and the comparison of similar works showed the proposed
encryptor had a pseudo-noise output and was strongly dependent upon the
changing key and plain image.

###### keywords:

Image Encryption , Chaotic map , Genetic Algorithm , FIS , AES.

##  1 Introduction

With the expansion of data analysis in recent years, data security has become
particularly important. Data security is provided in different ways, according
to the type of data, whether it is text, audio, image, video, etc.
Steganography, cryptography, and watermarking are some of the most common ways
to secure multimedia data [1]. In the field of cryptography, data is
transformed into meaningless and incomprehensible formats in order to make the
information unusable for everyone except the people who hold the cryptographic
key [2]. In steganography, considering that the meaninglessness of information
attracts the attention of others to the information and its users, the
information is hidden inside another type of information called the cover [3].
Watermarking is done for different purposes such as copyright protection, data
integrity, publishing path tracking, etc. [4]. The image, as one of the most
commonly used data types, has always been one of the most attractive fields of
research for researchers in various fields of science. The use of images in
various fields such as art, the military, advertising, commerce, etc. has
added to this attractiveness. Therefore, the importance of image security is
undeniable. As mentioned, encryption is one of the ways to secure data,
including image data.

Image encryption with the AES method is not effective when there is a strong
correlation between pixels. This problem becomes more serious when the image
has redundancy [5, 6]. Symmetric encryption algorithms such as AES, DES, etc.
are performed on small data blocks, generally128 bits long. The encryptor
output, which is replaced and sent, is equivalent to the input data block. The
number of encryptor input and output data blocks is similar. For example, if
block m is repeated in plaintext a hundred times, the block it is replaced
with will be viewed a hundred times in cipher text. Therefore for image blocks
that are identical, the equivalent replaced block will be repeated in
different sections of the image. Consequently uniform sections of the image
such as the image background will remain unchanged after the encryption, hence
the whole image is seen at a single glance [7]. Although AES is presently a
good method for text encryption, it is not suitable for image encryption due
to the following reasons [8]:

  1. (a)

The high volume of images tends to lower the speed of the algorithm.

  2. (b)

Pixel correlation between adjacent pixels is reflected in the encrypted image.

  3. (c)

Plain image redundancy is reflected in cipher image.

Therefore, it is crucial to make modifications to standard encryption
algorithms to improve the image features for use in image encryption
algorithms.

Chaotic maps are finite and deterministic while showing complex and dynamic
behavior. Accordingly, chaotic encryption and its eﬀiciency in image
encryption is better than common symmetric methods because of the image size,
correlation between adjacent pixels, and redundancy in images [9]; furthermore
there is a strong relationship between the dynamic specification of chaotic
maps and the required properties for the encryption system, which allows for
the use of chaotic maps in image encryption [10].

The rest of this paper is organized as follows. The next section discusses
related works. Section 3 describes the proposed algorithm and related
preliminaries. Section 4 includes results and the security analysis of the
proposed algorithm. Finally, section 5 concludes the paper.

##  2 Related Works

###  2.1 Image encryption methods using chaotic maps

The use of chaotic maps has many applications in image encryption. Arab et al.
[11] presented a new algorithm using the Arnold chaos sequence, integrating it
with a modified version of AES. Rostami et al. [12] presented an algorithm
with acceptable results using the logistic chaotic map, the XOR operator, and
chaotic windows. They stated that their proposed algorithm could be employed
in noisy communication networks and parallel processing.

Wang et al. [13] were able to encrypt images with acceptable security using a
logistic map and switching rows and columns. Liu et al. [14] introduced a new
chaotic map called 2D-SIMM. The map is based on the sine map and iterative
chaotic map with infinite collapse (ICMIC). They evaluated the eﬀiciency of
their chaotic map by several assessment methods and succeeded in introducing
2D-SIMM as a suitable chaotic map for image encryption. In addition, based on
2D-SIMM, an algorithm for image encryption was introduced with high security,
low time complexity, and resistance to brute-force, statistical, known-
plaintext, differential, and chosen-plaintext attacks. In fact, the algorithm
introduced in [14] is obtained by improving the key space in [13].

Pak and Huang [15] proposed a method for encrypting color images using the
output sequence differences of two one-dimensional chaos maps. One of their
innovations was the introduction of a new chaos map and a three-step algorithm
for image encryption. The three main steps in the algorithm proposed by [15]
are by a new permutation related to the key generator module, a diffusion that
is also related to the key generator module, and a linear transformation whose
output creates the final encrypted image. Li et al. [16] proposed another
algorithm for image encryption, using a similar architecture and a 5D chaotic
map. The algorithm proposed in [16] performs permutation operations at both
pixel and bit levels. They tried to solve the common problems in image
encryption algorithms using a high-dimensional chaotic map.

Li et al. [17] proposed an encryption scheme for images based on a chaotic
tent map. Their scheme is done in two steps. In the first step, a key for
cryptography is generated using a chaotic tent map. In the second step, the
encryption operation is performed using the key created in the first step.
Investigations have shown that their scheme does not provide adequate
security. Hermassi et al. [18] introduced an enhancement on the hyper-chaotic
image encryption scheme. Ye et al. [19] proposed an algorithm for image
encryption based on the generalized Arnold map. Norouzi et al. [20], using
hyper-chaotic sequences and plaintext, introduced a new algorithm for
encrypting images, which worked well. Song et al. [21] introduced a new
spatiotemporal chaotic system by defining a nonlinear map in coupled map
lattices (CML) and a chaotic map. Shariatzadeh et al. [22] proposed an AES-
inspired algorithm for image encryption using logistic chaotic map and 256
values in the finite field $2^{8}$.

###  2.2 Image encryption methods using DNA

There are methods and tools other than using chaotic maps to encrypt images.
Another way is to use deoxyribonucleic acid (DNA) technology to encrypt
images. DNA molecules contain genetic information. In this category of image
encryption methods, an attempt is made to use DNA molecules’ computational
power by simulating them [23]. Li et al. [24] developed a new algorithm for
image encryption using DNA, XOR, and real and complex turbulent systems. They
first created three sequences from color images using coding on R, G, and B
channels. They then created equal blocks using the Hamming distance between
the two generated keys. Finally, using the XOR operator, they combined the
generated blocks with DNA codes. The results obtained in [24] show acceptable
resistance to statistical and differential attacks. Wu et al. [5] also
introduced a new method for encrypting images by introducing a new chaotic map
called the two-dimensional Henon-Sine map (2D-HSM) using DNA encoding. Another
method that has used the DNA model is the method suggested by Enayatifar et
al. [25]. They first turned two-dimensional images into one-dimensional ones.
To increase the speed, they performed the permutation and diffusion steps
together. To perform these two steps, they used chaos mapping and DNA coding.

Wu et al. [26] presented a four-step scheme for color images based on three
chaotic one-dimensional systems and DNA sequencing operations. In the first
step, the cryptographic keys are prepared. This step is done using three one-
dimensional chaotic maps and the plain image. The cryptographic keys are then
converted to DNA matrices using DNA coding rules. In the second step, using
the XOR operation, the DNA matrices are changed. In the third step, the DNA
matrices are divided into equal blocks and these blocks are randomly
scrambled. In the fourth step, using DNA decoding rules, DNA matrices are
converted into an encrypted image. The results presented in [26] indicate that
this algorithm has a high resistance to statistical and differential attacks.
The algorithm proposed by [26] also deals with the noise resistance of the
cryptographic system. The results show that this algorithm has a higher
resistance to salt and pepper noise than to Gaussian noise. DNA encoding and
computation modulo 4 have been used to reduce the complexities of the image
encryption problem [27].

###  2.3 Image encryption methods using cellular automata

Another approach to image encryption is the use of cellular automata. Cellular
automata are made up of cells that are placed on a network with different
structures. These structures evolve in a variety of ways and simulate complex
structures. The vast body of rules in cellular automation is also developed in
a variety of ways. This evolution is created through simple logical
calculations with random behaviors. Reversible cellular automation is widely
used for block encryption. The main advantages of cellular automation in
encryption are the large space of rules and parallel work [23].

Ping et al. [28] used a balanced and non-aﬀine type of cellular automata with
complex behavior as blocks for their image encryption scheme. In their scheme,
local interaction between cells performs diffusion operations, while confusion
steps are achieved by nonlinear rules. With the method used in [28], the
confusion and diffusion stages are well integrated. The cryptographic scheme
of Niyat et al. [29] is based on cellular automata. Using a uniform cellular
automata framework, they tried to overcome the problems that this set of cells
have. They changed the position of the pixels using chaotic maps and created
an image as a key using cellular automata.

###  2.4 Image encryption methods using Meta-heuristic algorithms

Meta-heuristic algorithms are also used in the field of image encryption, and
they are based on population behavior. Meta-heuristic techniques are suitable
for solving NP-hard and optimization problems, and these techniques can be
used to optimize static parameters in image encryption algorithms [23, 30].
Using dynamic harmony search (DHS) and tent chaos mapping, Talarposhti and
Jamei [31] proposed an algorithm for encrypting grayscale images. The
encryption process in their proposed algorithm is done in two steps. In the
first stage, which is the diffusion stage, the fitness function is maximized
using DHS. They used entropy as a fitness function. In the second stage,
permutation is applied horizontally and vertically. One of the advantages of
their proposed algorithm is low time complexity.

###  2.5 Image encryption methods using fuzzy logic

The fuzzy-based approach is another technique for image encryption [23]. Fuzzy
logic is used in fuzzy systems. Fuzzy logic is a form of a multi-valued region
in which the logical value of variables can be any real number between 0 and
1. This logic is used to apply the concept of partial correctness. In this
logic, the amount of correctness can be any value between completely true and
completely false [32]. Seyedzadeh et al. [33] have presented a color image
encryption based on the Choquet fuzzy integral (CFI), which generates pseudo-
random keystreams. The output of the CFI is used to randomly shift the bits of
three gray-level components; then the three components of RGB color pixels and
the generated keystream are coupled to encrypt the permuted components.

Qaid and Sanjay [34] have supported user-desired security levels and their
corresponding processing levels by generating random keys for the
encryption/decryption process; this is achieved by using fuzzy logic and fuzzy
sets. Hashemi [35] introduces an image encryption algorithm based on DNA
addition combining and a coupled two-dimensional piecewise nonlinear chaotic
map. The generated sequence of the Sugeno fuzzy integral and the DNA sequence
addition operation is used to add encoded color component blocks.

###  2.6 Other related works

For real time applications, Bahrami and Naderi [36] have proposed a stream
encryption algorithm that has a good performance when faced with high speed
and the error probability of data transmission. The results have showed that
the performance speed of the proposed algorithm is better compared to A5/1 and
w7 stream ciphers. Kumar et al. [37] have performed a cryptanalysis on one of
the image encryption algorithms and showed that it is vulnerable to some types
of attack.

In this paper, in order to use an AES algorithm in image encryption, a chaotic
tent map, whose properties will be discussed in detail later in this paper, is
utilized as a simple chaos map. A random block is generated with a tent
chaotic map the size of AES-128 encryption blocks, which was XORed with the
first plain image block before running the AES. The genetic cross over
operator is used to increase the resistance of the proposed algorithm against
differential attacks, and finally, in case of process stop or continuation, a
proposed adaptive fuzzy system decides the type of input image and the results
of the previous sections according to user requirements.

The contributions of this paper include:

  * •

Using fuzzy models to provide security for the encrypted image according to
user requirements and input images.

  * •

Using a crossover genetic operation for changing the gray level of each pixel
of the image.

  * •

Using a chaotic logistic map combined with an AES algorithm to overcome the
drawbacks of a block- based encryptor for the image encryption problem.

  * •

Using the SHA-512 hash function to extract the needed key for the AES-128 from
a 1029 bit input master key.

  * •

Using an eﬀicient method for pixel shuffling using the chaotic map.

  * •

Increasing the key sensitivity through obtaining dependent initial conditions
upon the SHA-512 output key for the tent map.

  * •

The diffusion property is increased through using the sum of the last
encrypted block as a factor in the necessary initial value for the tent map,
which leads to increased resistance against differential attacks.

##  3 Proposed Algorithm

One of the problems of most AES-based encryption algorithms is their block-
based structure. In this structure, due to the separate encrypting of each
block, little change (one block or a few pixels) in the plain image will lead
to very little change in the encrypted image indicating inappropriate
diffusion. In addition, in most of these structures, permutation is conducted
at the block level only while in the proposed algorithm, permutation is
applied to the entire image. Furthermore, since the AES-related algorithms
have block-based structures, if the plain image is a uniform image, encrypted
blocks will be quite similar, leading one to recognize the uniform image.

In the proposed algorithm, in addition to the elimination of the mentioned
drawbacks in a combinational module, an adaptive fuzzy system decides on
continuing the encryption process by using a genetic crossover operation,
repeating the combinational module, or terminating the process due to the
achievement of results based on user demand. The proposed system has been
presented in two phases after the description of preliminaries.

###  3.1 Preliminaries

This section gives a brief review on the preliminary materials for the
proposed algorithm.

####  3.1.1 Tent chaotic map

Chaotic mapping in image encryption is very common and widely used [38]. Chaos
mappings are nonlinear dynamic systems that are very sensitive to their
initial conditions. So far, several chaotic maps have been proposed. Each of
them exhibits different behaviors and properties. One of the simplest of these
mappings is tent chaos mapping. The tent Chaos map was introduced by Yoshida
in 1983 [39]. The tent map has a parameter called $\mu$ and is one-
dimensional. Tent map is defined by

$x_{t+1}=\begin{cases}\mu x_{t}&x_{t}<\dfrac{1}{2}\\\ \\\
\mu(1-x_{t})&x_{t}\geq\dfrac{1}{2}.\end{cases}$ (1)

(a) The Tent chaos map path

(b) Tent map with $\mu$=1.9

(c) Tent map with $\mu$=0.95

(d) Tent map with $\mu$=1.1

(e) Tent map with $\mu$=1.5

Figure 1: Tent map

Figure 1(a) shows the tent chaos map path. Figures 1(b), 1(c), 1(d), 1(e) show
the tent chaos map behavior for different $\mu$ values. In these graphs, the
initial value of $x_{t}$ is assumed to be 0.4.

####  3.1.2 Pixel Shuffling

Pixel shuffling increases the security level of the image encryption algorithm
[40]. This operation is implemented in various methods along with chaotic
maps. In the proposed algorithm, pixel shuffling was used with simple types of
such methods. This procedure includes a gray-scale image with a $M\times N$
size ($Im_{M\times N}$). The image is converted and then the vector is
achieved ($P_{1\times(MN)}=\\{P_{1},P_{2}...P_{MN}\\}$); Next, the tent
chaotic map is iterated with the initial value $x_{0p}$ and the parameter
$\mu_{p}$ to generate a random sequence of length $M\times N$. By sorting them
in ascending order and getting their indices,
$I_{1\times(MN)}=\\{i_{1},i_{2}...i_{MN}\\}$ is generated. Pixel shuffling is
normally used to reorder $P_{1\times(MN)}$. For example, the $i_{1st}$ and
$i_{2nd}$ elements of $P_{1\times(MN)}$, reside in the first and second
position of the reordered vector. The reverse shuffling operation runs with
sequence $I$. For example, the first and the second elements of $P_{p}$ reside
in the $i_{1st}$ and $i_{2nd}$ place of $P$.

####  3.1.3 Genetic Crossover Operator

The cross over genetic operation is used for changing the gray level of each
pixel of the image and the chaos map by

###### Step 1

Initializing the tent chaotic map: To increase the security of the proposed
method, this value is specified from the 512-bit hash code of the key.

###### Step 2

Selecting two pixels of the image for cross over operation: The first pixel:
At the beginning of the process, the image is converted to 1D matrix that has
one row and 65536 columns. The first pixel is selected (in the next step, the
second pixel is selected, and then the sequential pixels to the last pixel are
selected).The second pixel: Chaos map is utilized to select the second pixel.

###### Step 3

Using the selected pixels for the crossover operation: The two specified
pixels in the previous step are selected for the crossover operation after
converting the gray level to base 2. The used cross over operation in this
stage is a single-point crossover.

###### Step 4

Steps 2 and 3 are repeated for all pixels of the image.

######

The decryption procedure is carried out in the reverse order of the encryption
procedure.

####  3.1.4 SHA-512

Figure 2: One iteration of the SHA-512 hash function. The components perform
the following operations:
$Ch(E,F,G)=(E\wedge F)\oplus(\neg E\wedge G),Ma(A,B,C)=(A\wedge
B)\oplus(A\wedge C)\oplus(B\wedge C),\newline \sum
0(A)=(A>>>2)\oplus(E>>>13)\oplus(A>>>22),\sum
1(E)=(E>>>6)\oplus(E>>>11)\oplus(E>>>25)$,
The + is addition modulo $2^{64}$

The SHA-512 is a hash algorithm for cryptography that can present the message
digest in 512-bit format [41]. The National Institute of Standards and
Technology (NIST) released SHA-2 as the information processing standard in
2001. This was done due to the detection of a security problem in the SHA-1
and the second version of SHA tried to fix the problems of its previous
version. SHA-2 was designed by the US National Security Agency (NSA) and
actually included SHA-224, SHA-256, SHA-384 and SHA-512. The end number of
these algorithms indicates the output length of these algorithms.

The proposed algorithm for image encryption in this paper uses SHA-512.
SHA-512 processes 64-bit words in 80 rounds. The SHA-512 input size consists
of eight 64-bit words. Figure 2 shows the integration performance in each
round of the SHA-512 algorithm. As can be seen in this figure, the hash
operation by SHA-512 is performed by the AND, XOR, Rotation, ADD, and OR
operators.

####  3.1.5 AES

Figure 3: Flowchart of AES-128 Table 1: Data block length, key length and number of iterations in the AES algorithm | Key length | Data block length | Number of iterations
---|---|---|---
AES-128 | 4 | 4 | 10
AES-192 | 6 | 4 | 12
AES-256 | 8 | 4 | 14

NIST published the AES in the FIPS 197 document in 2001 [42]. AES is a
symmetric cryptographic algorithm. This means that the encryption and
decryption operations are performed with the same key. In AES, the length of a
data block is 128 bits (equivalent to four 32-bit words). The encryption key
length can be 128 bits, 192 bits, or 256 bits. Selecting any of these keys
causes the number of iterations of the algorithm to run differently. Table 1
shows the length of the data block, the length of the key, and the number of
iterations in the AES algorithm.

The description of the AES algorithm is very simple, but the mathematical
foundations of this algorithm are very detailed. The AES performs encryption
operations using four functions: AddRoundKey, SubBytes, ShiftRows, and
MixColumn. The AES also expands the key using a complex and irreversible
algorithm. The flow chart of the AES 128 algorithm is shown in Figure 3.

In the SubByte function, each of the input bytes is replaced with new values
based on a fixed S-Box. This S-Box is a matrix that has 16 rows and 16
columns. In the RotateRows function, three input rows (which is a $4\times 4$
matrix) rotate to the left. In the AddRoundKey function, each input item is
XORed byte by byte with the corresponding item from the key in that iteration.
In the MixColumn function, each column of the input is integrated and tangled
independently of the other columns in the finite field ($2^{8}$).

####  3.1.6 Fuzzy Inference Systems

Figure 4: A scheme of a fuzzy inference system

Fuzzy logic based on fuzzy sets was first introduced by Professor Lotfi A.
Zadeh in 1965 [43]. This logic was developed and put into practice in 1970. In
fuzzy sets, variables are linguistic. The value of linguistic variables is not
a number, but words or sentences of a natural or artificial language. Unlike
Aristotelian and binary logic, where all variables are considered as yes or no
or zero or one, in fuzzy logic the variables change in the range between zero
and one. [32]. fuzzy inference system performs inference operations based on
fuzzy sets and fuzzy rules. The fuzzy inference system consists of three
components named fuzzification, fuzzy inference engine, and defuzzification
with the architecture shown in Figure 4.

Numerical variables are converted to linguistic variables by fuzzification. In
the inference engine, fuzzy rules are evaluated and inferred by inference
algorithms. The output of this section is given to defuzzification to convert
the generated values to a numeric value again. Defuzzification methods include
the weighted average, centroid, center of sums, center of largest area, first
of maxima, last of maxima, max membership, and mean-max membership methods
[44].

Fuzzy inference systems come in many forms. One of these systems is the
Mamdani fuzzy inference system. This system has high expressive power and is
implemented in two ways: multiple input multiple output (MIMO) and multiple
input single output (MISO). This system uses fuzzy sets as a result of rules.
The output of the rules in this system is nonlinear and fuzzy [45].

###  3.2 Encryption Process

The proposed algorithm encrypts the images in two phases. In the first phase,
using three operators XOR, pixel shuffling, and genetic crossover, the
confusion and diffusion of the system are increased. Increasing diffusion
means that the cryptographic system must prevent the transfer of the
statistical features of the input image to the output of the system. In other
words, the output pixels should not be correlated. Increasing confusion also
means that there should be no relationship between the input image and the
encrypted image.

In the second phase, using fuzzy inference systems, an attempt is made to
increase the static diversity (S-Dive) and dynamic diversity (D-Dive) of the
image. Static diversity refers to the statistical indicators of an image,
which are measured by entropy in this paper. Dynamic diversity also refers to
indicators related to avalanche effects and differential attacks, which are
measured using the UACI and the NPCR. The avalanche effect in cryptographic
systems means that a very small change in the input must lead to a very large
and unpredictable changes in the output.

The description of the encryption phases is by

##### Phase 1

This phase is done in 5 steps by

###### Step 1

Using SHA-512 the hash of the plain image is calculated. This hash code is
used for encryption operations in the second phase as well as for decryption
operations. After the encryption operation, this hash code is appended to the
primary key.

###### Step 2

The SHA-512 hash of the 512 bit Key is computed to achieve a 512 bit sequence
($K_{512}$) that depends on the primary key, then generate the new initial
conditions for the tent chaotic map and another key for the next phase by
following the equations:

$\begin{array}[]{l@{}l}x_{0}=\dfrac{bi2de(K_{512}[1:128])}{2^{128}},\\\ \\\
x_{1}=\dfrac{bi2de(K_{512}[129:256])}{2^{128}},\\\ \\\
x_{2}=\dfrac{bi2de(K_{512}[257:384])}{2^{128}},\\\ \\\
2nd\;phase\;key=K_{512}[385:512],\end{array}$ (2)

where ’$bi2de$’ converts a binary row vector to a non-negative decimal
integer. Since the generated 512 bit hashed key is dependent on the primary
key, if one bit is changed in the primary key, the hashed key and x0, x1, and
x2 will be changed dramatically, which strengthens the diffusion property.

###### Step 3

Using the tent chaos map with the initial value of $x_{0}$ obtained from the
primary key in the previous step, a sequence equal to the number of pixels in
the plain image is created. The values obtained are in the range $[0,1]$ and
are doubled. Using the following equation, these values are mapped to integers
and non-negative numbers in the range $[0,255]$:

$t_{i}=mod(x_{i}\times 10^{14},256),$ (3)

where $x_{i}$ is the value created by the tent chaos map and $t_{i}$ is an
integer obtained in the range $[0,255]$. In this step, after creating the
sequence $T$ where $T=\\{0\leq t_{i}\leq 255,t_{i}\in\mathbb{Z}\\}$, each of
the pixels of the plain image with its corresponding number in the sequence
$T$ is XORed bit by bit in binary form.

###### Step 4

To increase diffusion and confusion in the cryptographic system, pixel
shuffling is applied to the image as described in Section 3.1.2. The initial
value for the tent chaos map in this step is $x_{1}$.

###### Step 5

Figure 5: Architecture of encryption process in the first phase

The genetic crossover operation is applied to the image as described in
section 3.1.3. As in the previous step, this is done to increase confusion and
diffusion in the cryptographic system. The initial value for the tent chaos
map in this step is $x_{2}$. The output of this step is an image called the
pre-encrypted image.

Comparison of the plain image and pre-encrypted images has shown that steps 3
to 5 significantly eliminate the statistical properties of the plain image and
increase confusion and diffusion in the encryption system. This operation
causes the system to show high resistance to statistical attacks. The
flowchart of the first phase of the cryptographic system is shown in Figure 5.

##### Phase 2

Figure 6: Architecture of encryption process in the second phase

The encryption process on the pre-encrypted image is performed in the second
phase with the aim of increasing the static and dynamic diversity under the
supervision of two fuzzy inference systems named FIS1 and FIS2. In this phase,
two modules called ”AES Chaos Module” and ”XOR by hash code”are used for
encryption. These two modules use the AES and SHA-512 as described in sections
3.1.4 and 3.1.5. This phase also uses two check points for encryption. At the
first check point, the pre-encrypted image entropy value is calculated and
sent to FIS1 along with the SEC value, which indicates the level of security
requested by the user. The function of FIS1 is to calculate the value of
S-Dive. If the value of S-Dive is less than the value of $T_{1}$, the image is
sent to the AES-Chaos module. Studies have shown that the AES-Chaos module
increases static diversity. If the value of S-Dive is greater than the value
of $T_{1}$, the AES-Chaos module will not be applied to the image. If AES-
Chaos Module is applied to the image, a bit with a value of one is added to
the decryption key and otherwise a bit with a value of zero is added.

At the second check point, the UACI and NPCR values of the image are
calculated and sent to FIS2 with the SEC. The function of FIS2 is to calculate
D-Dive. If the value of D-Dive is less than the value of $T_{2}$, the XOR
operation is performed on the image by hash code. After performing XOR by hash
code, the value of D-Dive is calculated again. To calculate D-Dive, it is
necessary to recalculate the UACI and NPCR values of the image. If the D-Dive
value is again less than the $T_{2}$ value, the XOR is performed on the image
by hash code operation again. This process is repeated until either D-Dive
exceeds the value of $T_{2}$ or finally the operation XOR by hash code is
applied to the image fifteen times. Studies have shown that applying XOR by
hash code more than 15 times not only does not increase D-Dive, but in some
cases, even reduces D-Dive. At the end of the encryption operation, four bits
are added to the decryption key. The value of these four bits is between zero
and 15 and indicates the number of XOR by hash code operations applied to the
image.

The first fuzzy inference system, known as FIS1, was designed to calculate
S-Dive. This system is a Mamdani system and has two inputs called entropy and
SEC, one output called S-Dive and two rules. All FIS1 membership functions are
considered Gaussian functions. Figure 7 shows the membership functions for
entropy, SEC, and S-Dive. It should be noted that the range for entropy is
defined between 0 and 8, the range for SEC is defined between 0 and 100, and
the range for S-Dive is defined between 0 and 1. The rules in this inference
system are by

  * •

if Entropy is Low and SEC is High then S-Dive is Low

  * •

if Entropy is High then S-Dive is High

(a) Membership functions for Entropy input

(b) Membership functions for SEC input

(c) Membership functions for S-Dive output

Figure 7: Membership functions for inputs and outputs in FIS1

(a) Membership functions for NPCR input

(b) Membership functions for SEC input

(c) Membership functions for UACI input

(d) Membership functions for D-Dive output

Figure 8: Membership functions for inputs and outputs in FIS2

FIS2 is also a Mamdani system. FIS2 has three inputs and one output and is
designed to calculate D-Dive. The inputs of this system are the UACI, NPCR,
and SEC, all of which are in the range between 0 and 100. The output of the
system is D-Dive, which is in the range between 0 and 1. Figure 8 shows the
membership functions for FIS2 inputs and outputs. In this system, all
membership functions of Gaussian type are considered. FIS2 has three rules,
which are stated below:

  * •

if UACI is Low and SEC is High then D-Dive is Low

  * •

if NPCR is Low and SEC is High then D-Dive is Low

  * •

if UACI is High and NPCR is High then D-Dive is High

In the AES-Chaos module, as in the process of calculating $x_{0}$, $x_{1}$,
and $x_{2}$ from the primary key, the value of $x_{AES}$ is first calculated
from the 2nd phase key by

$x_{AES}=\dfrac{bi2de(2nd\;phase\;key)}{2^{128}},$ (4)

where ’$bi2de$’ converts a binary row vector to a non-negative decimal
integer. The value $x_{AES}$ is used to create a pseudo-random sequence of
natural numbers. Using the tent chaos map, a sequence is created and then
sorted in ascending order. The obtained indices are used for encryption. After
creating a random sequence of indices, the image is divided into $4\times 4$
blocks. The first block is encrypted using the 2nd phase key by the AES
algorithm. The encrypted content is used as the next block encryption key.

In the XOR by hash code module, the image is first divided into 512-bit
blocks. The first block is XORed bit by bit with the code obtained in the
first step of the first phase. The second block is also XORed bit by bit with
the XOR result from the first block. In the same way, the next blocks are
XORed bit by bit with the XOR result of their previous block.

###  3.3 Decryption

During the encryption process, a 1029-bit key called the decryption key is
created. Each part of this key is intended as a system guide for the
decryption process. This key consists of four parts, which consist of 512 bits
as the primary key, 512 bits as the hash code, one bit as a flag to perform
the AES-Chaos module process, and 4 bits as the number of XOR operations by
hash code.

The primary key is used to calculate the values of $x_{0}$, $x_{1}$, $x_{2}$,
$x_{AES}$, and the 2nd phase key based on equations 2 and 4. Using these
values, XOR by tent chaotic map, pixel shuffling, genetic crossover, and AES-
Chaos module can be performed in the reverse direction. Using the hash code,
the XOR by hash code operation can be performed in the reverse direction. The
last five bits of the decryption key are also used to guide the decryption
system. If the bit that is the flag of the AES-Chaos module is one, it is
necessary to perform the AES decryption operation on the encrypted image.
Otherwise, there is no need to perform this operation. The value of the last
four bits of the decryption key also indicates the number of XOR operations by
hash code and is applied to the encrypted image to obtain the decrypted image.
It is important to note that fuzzy inference systems are no longer used in the
decryption process.

To secure the key, it is necessary to provide a secure channel for key
transfer. Encrypted image security depends on the security of the encryption
key. Due to the fact that the hashed value of the image is used in the
decryption key, it is necessary to keep the decryption key confidential.

##  4 Security Analysis

A suitable encryption algorithm should be robust against all existing
cryptanalytic attacks [46]. In this section, we demonstrate the high security
level of the proposed encryption algorithm by showcasing its performance
according to a number of security analyses, including histogram, correlation
analysis, key sensitivity test, security key space analysis, statistical
analysis, information theory entropy, and differential analysis.

###  4.1 Key Space and Brute Force Attack

The key space of an encryption algorithm should be large enough to resist
brute-force attacks [47]. Key length is 1029 bits in the proposed algorithm.
The SHA-512 algorithm was used to extract a 512-bit key from the plain image
for the XOR by hash code module. This method extended the key space
significantly and increased key sensitivity to the master key with the SHA-512
algorithm. Therewith, as was said $x_{0}$, $x_{1}$, $x_{2}$, and
$x_{2nd\;phase\;key}$ were obtained from the master key by SHA-512 and since
the precision was $10^{-14}$, the key space was extended. Total key space was
calculated with the following formula:

$S=2^{1029}\times 10^{14}\simeq 2^{1029}\times 2^{46}=2^{1075}.$ (5)

which provides a safe key space.

###  4.2 Histogram

(a) Lena Image

(b) Histogram of Lena

(c) Lena encryption

(d) Histogram of Lena encryption

Figure 9: Histogram of the image and histogram of the encrypted image

A histogram is a graph that shows the frequency of pixels with different
values. In simpler term, a histogram is a bar chart whose horizontal axis
represents the values of the pixels (light pixels on the right and dark pixels
on the left) and its vertical axis represents the number of pixels in the
image. It has already been stated that a good cryptographic system for images
should be able to eliminate statistical features in images [48]. One of the
best criteria for examining statistical features in plain and cipher images is
to examine the histogram of these images. As can be seen in Figure 9, the
histogram of the cipher image bears no resemblance to the plain image, and all
statistical features of the input image are lost. An image encryption system
should be able to create a smooth histogram for the encrypted image. As can be
seen, the proposed system meets this requirement.

###  4.3 Information Entropy

Information entropy is a numerical measure of image randomness. The higher the
entropy of an image, the greater the ambiguity about that image, and vice
versa. Using the following formula, the entropy value of an image can be
calculated [49]:

$H(s)=\sum_{i=0}^{2^{M}-1}P(S_{i})\log_{2}\dfrac{1}{P(S_{i})}.$ (6)

In the above equation, $P(s_{i})$ represents the probability of $s_{i}$ and
$2^{M}$ represents all states of information. The maximum value for the
entropy of the encrypted image is 8. Table 2 presents the entropy values for
cipher images by different algorithms. By comparing these values and
considering the calculated averages for encrypted images it can be concluded
that the proposed system creates a better performance in creating ambiguity
for encrypted images.

Table 2: Entropy results

ours Ref. [5] Ref. [25] Ref. [29] Ref. [17] Ref. [18] Ref. [19] Ref. [20] Ref.
[21] AES in CBC mode lena 7.9974 7.9976 7.9975 7.9974 7.9913 7.9970 7.9970
7.9971 7.9972 7.9899 cameraman 7.9971 7.9975 7.9939 7.9971 7.9915 7.9972
7.9975 7.9974 7.9974 7.9897 baboon 7.9972 7.9971 7.9938 7.9970 7.9912 7.9970
7.9972 7.9975 7.9971 7.9900 plain 7.9977 7.9970 7.9974 7.9970 7.9912 7.9973
7.9973 7.9966 7.9970 7.9896 ship 7.9972 7.9971 7.9941 7.9973 7.9907 7.9970
7.9971 7.9972 7.9971 7.9889 peppers 7.9976 7.9974 7.9958 7.9972 7.9909 7.9972
7.9974 7.9974 7.9971 7.9900 average 7.9974 7.9973 7.9954 7.9972 7.9911 7.9971
7.9972 7.9972 7.9972 7.9897

###  4.4 Correlation of Pixels

Table 3: Correlation coefficients of two adjacent pixels in plain and ciphered
images

ours Ref. [5] Ref. [25] Ref. [29] Ref. [17] Ref. [18] Ref. [19] Ref. [20] Ref.
[21] AES in CBC mode lena horizontal 0.0062 0.0056 0.0023 0.0061 0.0041 0.0045
0.0199 0.0045 0.0294 0.0143 vertical 0.0111 0.0037 0.0019 0.0116 0.0021 0.0344
0.0056 0.0370 0.0296 0.0238 diagonal 0.0216 0.0032 0.0011 0.0018 0.0009 0.0097
0.0203 0.0098 0.0167 0.0070 cameraman horizontal 0.0212 0.0024 0.0198 0.0053
0.0148 0.0030 0.0117 0.0476 0.0039 0.0208 vertical 0.0217 0.0013 0.0132 0.0126
0.0084 0.0329 0.0137 0.0127 0.0033 0.0124 diagonal 0.0186 0.0098 0.0032 0.0005
0.0026 0.0080 0.0395 0.0125 0.0215 0.0088 baboon horizontal 0.0234 0.0026
0.0059 0.0060 0.0055 0.0011 0.0034 0.0470 0.0213 0.0277 vertical 0.0043 0.0009
0.0041 0.0058 0.0015 0.0006 0.0209 0.0391 0.0090 0.0077 diagonal 0.0081 0.0052
0.0028 0.0016 0.0041 0.0157 0.0151 0.0149 0.0053 0.0089 plain horizontal
0.0029 0.0028 0.0062 0.0054 0.0075 0.0056 0.0148 0.0329 0.0347 0.0143 vertical
0.0172 0.0041 0.0074 0.0081 0.0084 0.0039 0.0304 0.0639 0.0014 0.0277 diagonal
0.0347 0.0010 0.0009 0.0021 0.0011 0.0090 0.0011 0.0615 0.0045 0.0084 ship
horizontal 0.0141 0.0001 0.0073 0.0085 0.0073 0.0041 0.0016 0.0234 0.0107
0.0169 vertical 0.0215 0.0031 0.0109 0.0092 0.0216 0.0003 0.0099 0.0310 0.0062
0.0166 diagonal 0.0196 0.0015 0.0016 0.0024 0.0035 0.0000 0.0153 0.0019 0.0121
0.0320 peppers horizontal 0.0040 0.0016 0.0037 0.0049 0.0021 0.0011 0.0160
0.0013 0.0154 0.0219 vertical 0.0199 0.0059 0.0258 0.0031 0.0218 0.0006 0.0058
0.0084 0.0051 0.0064 diagonal 0.0024 0.0034 0.0079 0.0079 0.0096 0.0157 0.0021
0.0095 0.0054 0.0096

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 10: Correlation of adjacent pixels (a) Lena Image (b) Distribution of
two horizontally adjacent pixels in the Lena image (c) Distribution of two
vertically adjacent pixels in the Lena image (d)Distribution of two diagonally
adjacent pixels in the Lena image (e) Lena encryption (f) Distribution of two
horizontally adjacent pixels in the encrypted Lena image (g) Distribution of
two vertically adjacent pixels in the encrypted Lena image (h) Distribution of
two diagonally adjacent pixels in the encrypted Lena image

One of the most important targets in image encryption is to greatly decrease
the correlation between adjacent pixels so that no relation between pixels
could be spotted by naked eye. Calculating the correlation coeﬀicient, the
formulas of which are shown below, is the most common method to measure this
feature in horizontal, vertical, and diagonal directions [50]:

$\begin{array}[]{l@{}l}r_{xy}=\dfrac{cov(x,y)}{\sqrt{D(x)D(y)}},\\\ \\\
E_{x}=\dfrac{1}{N}\sum_{i=1}^{N}x_{i},\\\ \\\
D_{x}=\dfrac{1}{N}\sum_{i=1}^{N}(x_{i}-E(x_{i}))^{2},\\\ \\\
cov(x,y)=\dfrac{1}{N}\sum_{i=1}^{N}(x_{i}-E(x_{i}))(y_{i}-E(y_{i})).\end{array}$
(7)

The results of this factor have been represented in Table 3. Figure 10 shows
the correlation pixel diagram for the Lena image in horizontal, vertical, and
diagonal modes. Figure 10 also shows these diagrams for Lena’s encrypted
image. By comparing these diagrams, it can be concluded that the proposed
system reliably eliminates the correlation of adjacent pixels in different
directions.

###  4.5 Differential Attacks

Table 4: NPCR results

ours Ref. [5] Ref. [25] Ref. [29] Ref. [17] Ref. [18] Ref. [19] Ref. [20] Ref.
[21] AES in CBC mode lena 99.85 99.62 99.52 99.62 5.09E-04 35.76 99.21 99.73
99.64 1.52E-03 cameraman 99.59 99.61 99.00 99.63 5.09E-04 97.15 99.25 99.70
99.59 1.52E-03 baboon 99.62 99.59 99.11 99.61 5.09E-04 89.60 99.15 99.67 99.60
1.52E-03 plain 99.58 99.62 99.42 99.65 5.09E-04 21.45 99.65 99.72 99.59
1.52E-03 ship 99.84 99.62 99.25 99.62 5.09E-04 78.49 99.26 99.72 99.62
1.52E-03 peppers 99.79 99.61 98.50 99.66 5.09E-04 57.89 99.17 99.68 18.96
1.52E-03 average 99.71 99.61 99.13 99.63 5.09E-04 63.39 99.28 99.70 86.16
1.52E-03

Table 5: UACI results

ours Ref. [5] Ref. [25] Ref. [29] Ref. [17] Ref. [18] Ref. [19] Ref. [20] Ref.
[21] AES in CBC mode lena 33.52 33.42 33.59 33.42 1.9946E-06 0.28 33.43 33.33
33.52 1.85E-04 cameraman 33.45 33.53 33.10 33.47 1.9946E-06 0.38 33.42 33.38
33.49 7.77E-05 baboon 33.63 33.38 33.25 33.41 1.9946E-06 0.35 33.38 33.15
33.50 2.99E-05 plain 33.54 33.64 33.53 33.51 1.9946E-06 0.17 33.62 33.62 33.50
4.18E-05 ship 33.59 33.66 33.59 33.51 1.9946E-06 1.24 33.46 33.30 33.32
5.98E-06 peppers 33.42 33.50 32.95 33.44 1.9946E-06 0.55 33.37 33.39 33.44
1.79E-05 average 33.53 33.52 33.33 33.46 1.9946E-06 0.50 33.45 33.36 33.46
5.97E-05

In cryptography, differential attacks are common attacks where the plain image
is changed in as little as one bit, and then both the plain image and the
changed image are encrypted and compared [51]. Encryptor output must be
sensitive to the change in plain image to resist such attacks. In other words,
a slight change in plain image pixels affects the entire cipher image. Two
common measurements for this property are the NPCR and UACI, which imply the
number of pixel change rate and the unified averaged changed intensity,
respectively. In order to calculate these two quantities, plain image of
$C_{1}$ changes to a pixel named $C_{2}$; $C_{1}$ and $C_{2}$ are then
encrypted.

####  4.5.1 NPCR

The NPCR value is calculated using Equation 8 as follows [52]:

$\begin{array}[]{l@{}l}NPCR(C_{1},C_{2})=\dfrac{1}{M\times
N}\sum_{i=1}^{M}\sum_{j=1}^{N}D(i,j),\\\ \\\
D(i,j)=\begin{cases}0&C_{1}(i,j)=C_{2}(i,j)\\\ 1&C_{1}(i,j)\neq
C_{2}(i,j)\end{cases}.\end{array}$ (8)

where $C_{1}(i,j)$ represents the pixel intensity of the encrypted grayscale
image $C_{1}$, which is located in the $ith$ row and the $jth$ column. The
results of the NPCR calculation for the proposed algorithm and several other
algorithms are presented in Table 4. Comparing the obtained results, it is
observed that the proposed system has shown better performance than other
algorithms.

####  4.5.2 UACI

As mentioned, another measure of the cryptographic system’s resistance to
differential attacks is the UACI. The UACI value is calculated using the
following equation [53]:

$UACI(C_{1},C_{2})=\dfrac{1}{M\times
N}\sum_{i=1}^{M}\sum_{j=1}^{N}\dfrac{|C_{1}(i,j)-C_{2}(i,j)|}{255},$ (9)

where $C_{1}$ and $C_{2}$ are encrypted images. Table 5 presents the results
of the UACI calculation for the proposed algorithm and 4 other algorithms. By
close examination of the obtained values, the better performance of the
proposed system can be verified.

##  5 Conclusion

In this paper, a new image encryption algorithm was proposed based on the
AES-128 standard algorithm. The proposed algorithm used a 1029-bit key. To
increase key sensitivity, the master key was sent to the SHA-512 hash
function, and then the 128-bit key was obtained for AES-128. Also, the
required initial conditions for the tent map were dependent upon this 128-bit
key, which further increased the sensitivity. Next, a random block was
generated with a tent map the size of AES-128 encryption blocks ($4\times 4$)
which was XORed with the first plain image block before running the AES. The
sum of the last encrypted block affected the necessary initial value for the
tent map to increase the diffusion property. In this way, the permutation
stage affected image pixels with only slight changes in the plain image,
increasing resistance against differential attacks.

## References

  * [1] Mousomi Roy, Kalyani Mali, Sankhadeep Chatterjee, Shouvik Chakraborty, Reshmi Debnath, and Soumya Sen.  A study on the applications of the biomedical image encryption methods for secured computer aided diagnostics.  In 2019 Amity International Conference on Artificial Intelligence (AICAI), pages 881–886. IEEE, 2019.
  * [2] Huanhao Xu, Kutub Thakur, Abu S Kamruzzaman, and Md Liakat Ali.  Applications of cryptography in database: A review.  In 2021 IEEE International IOT, Electronics and Mechatronics Conference (IEMTRONICS), pages 1–6. IEEE, 2021.
  * [3] Alan A Abdulla, Harin Sellahewa, and Sabah A Jassim.  Improving embedding efficiency for digital steganography by exploiting similarities between secret and cover images.  Multimedia Tools and Applications, 78(13):17799–17823, 2019.
  * [4] Nasir N Hurrah, Shabir A Parah, Nazir A Loan, Javaid A Sheikh, Mohammad Elhoseny, and Khan Muhammad.  Dual watermarking framework for privacy protection and content authentication of multimedia.  Future generation computer Systems, 94:654–673, 2019.
  * [5] Jiahui Wu, Xiaofeng Liao, and Bo Yang.  Image encryption using 2d hénon-sine map and dna approach.  Signal Processing, 153:11–23, 2018.
  * [6] Yong Zhang and Yingjun Tang.  A plaintext-related image encryption algorithm based on chaos.  Multimedia Tools and Applications, 77(6):6647–6669, 2018.
  * [7] Yong Zhang.  Test and verification of aes used for image encryption.  3D Research, 9(1):1–27, 2018.
  * [8] Yong Zhang, Xueqian Li, and Wengang Hou.  A fast image encryption scheme based on aes.  In 2017 2nd International Conference on Image, Vision and Computing (ICIVC), pages 624–628. IEEE, 2017.
  * [9] Ahmed G Radwan, Sherif H AbdElHaleem, and Salwa K Abd-El-Hafiz.  Symmetric encryption algorithms using chaotic and non-chaotic generators: A review.  Journal of advanced research, 7(2):193–208, 2016.
  * [10] Jiyue Tang, Ziniu Yu, and Lingfeng Liu.  A delay coupling method to reduce the dynamical degradation of digital chaotic maps and its application for image encryption.  Multimedia Tools and Applications, 78(17):24765–24788, 2019.
  * [11] Alireza Arab, Mohammad Javad Rostami, and Behnam Ghavami.  An image encryption method based on chaos system and aes algorithm.  The Journal of Supercomputing, 75(10):6663–6682, 2019.
  * [12] Mohamad Javad Rostami, Abbas Shahba, Saeid Saryazdi, and Hossein Nezamabadi-pour.  A novel parallel image encryption with chaotic windows based on logistic map.  Computers & Electrical Engineering, 62:384–400, 2017.
  * [13] Xingyuan Wang, Qian Wang, and Yingqian Zhang.  A fast image algorithm based on rows and columns switch.  Nonlinear Dynamics, 79(2):1141–1149, 2015.
  * [14] Wenhao Liu, Kehui Sun, and Congxu Zhu.  A fast image encryption algorithm based on chaotic map.  Optics and Lasers in Engineering, 84:26–36, 2016.
  * [15] Chanil Pak and Lilian Huang.  A new color image encryption using combination of the 1d chaotic map.  Signal Processing, 138:129–137, 2017.
  * [16] Yueping Li, Chunhua Wang, and Hua Chen.  A hyper-chaos-based image encryption algorithm using pixel-level permutation and bit-level permutation.  Optics and Lasers in Engineering, 90:238–246, 2017.
  * [17] Chunhu Li, Guangchun Luo, Ke Qin, and Chunbao Li.  An image encryption scheme based on chaotic tent map.  Nonlinear Dynamics, 87(1):127–133, 2017.
  * [18] Houcemeddine Hermassi, Rhouma Rhouma, and Safya Belghith.  Improvement of an image encryption algorithm based on hyper-chaos.  Telecommunication Systems, 52(2):539–549, 2013.
  * [19] Guodong Ye and Kwok-Wo Wong.  An efficient chaotic image encryption algorithm based on a generalized arnold map.  Nonlinear dynamics, 69(4):2079–2087, 2012.
  * [20] Benyamin Norouzi, Sattar Mirzakuchaki, Seyed Mohammad Seyedzadeh, and Mohammad Reza Mosavi.  A simple, sensitive and secure image encryption algorithm based on hyper-chaotic system with only one round diffusion process.  Multimedia tools and applications, 71(3):1469–1497, 2014.
  * [21] Chun-Yan Song, Yu-Long Qiao, and Xing-Zhou Zhang.  An image encryption scheme based on new spatiotemporal chaos.  Optik-International Journal for Light and Electron Optics, 124(18):3329–3334, 2013.
  * [22] Mahdi Shariatzadeh, Mohammad Javad Rostami, and Mahdi Eftekhari.  Proposing a novel dynamic aes for image encryption using a chaotic map key management approach.  Optik, 246:167779, 2021.
  * [23] Manjit Kaur and Vijay Kumar.  A comprehensive review on image encryption techniques.  Archives of Computational Methods in Engineering, 27(1):15–43, 2020\.
  * [24] Xiang Li, Leyuan Wang, Yinfa Yan, and Ping Liu.  An improvement color image encryption algorithm based on dna operations and real and complex chaotic systems.  Optik, 127(5):2558–2565, 2016.
  * [25] Rasul Enayatifar, Abdul Hanan Abdullah, Ismail Fauzi Isnin, Ayman Altameem, and Malrey Lee.  Image encryption using a synchronous permutation-diffusion technique.  Optics and Lasers in Engineering, 90:146–154, 2017.
  * [26] Xiangjun Wu, Haibin Kan, and Jürgen Kurths.  A new color image encryption scheme based on dna sequences and multiple improved 1d chaotic maps.  Applied Soft Computing, 37:24–39, 2015.
  * [27] Mohamad Javad Rostami, Saeid Saryazdi, Hossein Nezamabadi-pour, and Abbas Shahba.  Chaos-based image encryption using sum operation modulo 4 and 256.  IETE Journal of Research, 62(2):179–188, 2016.
  * [28] Ping Ping, Feng Xu, and Zhi-Jian Wang.  Image encryption based on non-affine and balanced cellular automata.  Signal Processing, 105:419–429, 2014.
  * [29] Abolfazl Yaghouti Niyat, Mohammad Hossein Moattar, and Masood Niazi Torshiz.  Color image encryption based on hybrid hyper-chaotic system and cellular automata.  Optics and Lasers in Engineering, 90:225–237, 2017.
  * [30] Rasul Enayatifar, Abdul Hanan Abdullah, and Ismail Fauzi Isnin.  Chaos-based image encryption using a hybrid genetic algorithm and a dna sequence.  Optics and Lasers in Engineering, 56:83–93, 2014.
  * [31] Khadijeh Mirzaei Talarposhti and Mehrzad Khaki Jamei.  A secure image encryption method based on dynamic harmony search (dhs) combined with chaotic map.  Optics and Lasers in Engineering, 81:21–34, 2016.
  * [32] Paulo Vitor de Campos Souza, Edwin Lughofer, and Augusto Junio Guimaraes.  An interpretable evolving fuzzy neural network based on self-organized direction-aware data partitioning and fuzzy logic neurons.  Applied Soft Computing, page 107829, 2021.
  * [33] Seyed Mohammad Seyedzadeh, Benyamin Norouzi, and Sattar Mirzakuchaki.  Rgb color image encryption based on choquet fuzzy integral.  Journal of Systems and Software, 97:128–139, 2014.
  * [34] Gamil RS Qaid and Sanjay N Talbar.  Encrypting image by using fuzzy logic algorithm.  International Journal of Image Processing and Vision Sciences (IJIPVS), 2(1):25–29, 2013.
  * [35] Yasaman Hashemi.  Design a new image encryption using fuzzy integral permutation with coupled chaotic maps.  International Journal of Research in Computer Science, 3(1):27, 2013\.
  * [36] Saeed Bahrami and Majid Naderi.  Image encryption using a lightweight stream encryption algorithm.  Advances in Multimedia, 2012, 2012.
  * [37] Anil Kumar, Rhouma Rhouma, Yong Wang, Nicolas Sklavos, and MK Ghose.  Comments on,“a blind source separation-based method for multiple images encryption”.  Communications in Nonlinear Science and Numerical Simulation, 16(3):1675–1686, 2011.
  * [38] Hongyue Xiang and Lingfeng Liu.  An improved digital logistic map and its application in image encryption.  Multimedia Tools and Applications, 79(41):30329–30355, 2020.
  * [39] Prabir Kumar Naskar, Surojit Bhattacharyya, Dipta Nandy, and Atal Chaudhuri.  A robust image encryption scheme using chaotic tent map and cellular automata.  Nonlinear Dynamics, 100(3):2877–2898, 2020.
  * [40] Saiyma Fatima Raza and Vishal Satpute.  A novel bit permutation-based image encryption algorithm.  Nonlinear Dynamics, 95(2):859–873, 2019.
  * [41] N Saravanan and A Umamakeswari.  Hap-cp-abe based encryption technique with hashed access policy based authentication scheme for privacy preserving of phr.  Microprocessors and Microsystems, 80:103540, 2021.
  * [42] Thanikodi Manoj Kumar and Palanivel Karthigaikumar.  Fpga implementation of an optimized key expansion module of aes algorithm for secure transmission of personal ecg signals.  Design Automation for Embedded Systems, 22(1):13–24, 2018.
  * [43] Jerry M Mendel.  Human-inspired—zadeh—sets and logic.  In 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), pages 1–5. IEEE, 2020.
  * [44] Li Na and Weng Jing.  A new defuzzification method for enhance performance of fuzzy logic control system.  In Software Engineering and Knowledge Engineering: Theory and Practice, pages 403–409. Springer, 2012.
  * [45] MA Salman and Nezar Ismat Seno.  A comparison of mamdani and sugeno inference systems for a satellite image classification.  Anbar Journal for Engineering Sciences, 2010.
  * [46] SJ Sheela, KV Suresh, and Deepaknath Tandur.  Image encryption based on modified henon map using hybrid chaotic shift transform.  Multimedia Tools and Applications, 77(19):25223–25251, 2018.
  * [47] Jizhao Liu, Shusen Tang, Jing Lian, Yide Ma, and Xinguo Zhang.  A novel fourth order chaotic system and its algorithm for medical image encryption.  Multidimensional Systems and Signal Processing, 30(4):1637–1657, 2019.
  * [48] Behzad Yosefnezhad Irani, Peyman Ayubi, Fardin Amani Jabalkandi, Milad Yousefi Valandar, and Milad Jafari Barani.  Digital image scrambling based on a new one-dimensional coupled sine map.  Nonlinear Dynamics, 97(4):2693–2721, 2019.
  * [49] P Mathivanan and A Balaji Ganesh.  Qr code based color image cryptography for the secured transmission of ecg signal.  Multimedia Tools and Applications, 78(6):6763–6786, 2019.
  * [50] Yi Ding, Fuyuan Tan, Zhen Qin, Mingsheng Cao, Kim-Kwang Raymond Choo, and Zhiguang Qin.  Deepkeygen: a deep learning-based stream cipher generator for medical image encryption and decryption.  IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * [51] KU Shahna and Anuj Mohamed.  A novel image encryption scheme using both pixel level and bit level permutation with chaotic map.  Applied Soft Computing, 90:106162, 2020.
  * [52] Delia Torres-Muñoz, Héctor Vázquez-Leal, and Carlos Hernández-Mejía.  Exploring a novel fusion-scheme based on mathematical equation system for encryption-image algorithm.  Multimedia Tools and Applications, 79(33):24873–24888, 2020.
  * [53] Mohamed Zakariya Talhaoui, Xingyuan Wang, and Mohamed Amine Midoun.  Fast image encryption algorithm with high security level using the bülban chaotic map.  Journal of Real-Time Image Processing, 18(1):85–98, 2021.


# Visualization of Extremely Sparse Contingency Table by Taxicab
Correspondence Analysis: A Case Study of Textual Data

Choulakian V and Allard J, Université de Moncton, Canada
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(August 2023)

###### Abstract

We present an overview of taxicab correspondence analysis, a robust variant of
correspondence analysis, for visualization of extremely sparse contingency
tables. In particular we visualize an extremely sparse textual data set of
size 590 by 8265 concerning fragments of 8 sacred books recently introduced by
Sah and Fokoué (2019) and studied quite in detail by (12 + 1) dimension
reduction methods (t-SNE, UMAP, PHATE,…) by Ma, Sun and Zou (2022).

Key words: sparse contingency table; taxicab correspondence analysis;
Benzécri’s principle of distributional equivalence; data visualization;
dimension reduction.

AMS 2010 subject classifications: 62H25, 62H30

##  1 Introduction

Extremely sparse contingency tables often are high-dimensional and ubiquitous
in many scientific disciplines; their embeddings into low-dimensional spaces
for visualization is an active area of research. This article offers a study
from the perspective of correspondence analysis (CA) and its robust variant
taxicab CA (TCA). We start by summarizing the results of the main paper which
motivated our work.

An extremely sparse contingency table, textual data set or a bag of words
recently introduced by Sah and Fokoué (2019), of size $I\times J=590\times
8265$, where $I=590$ represents fragments of chapters of 8 sacred books and
$J=8265$ represents the number of distinct words, is studied-visualized quite
in detail by (12+1) dimension reduction methods in Ma, Sun and Zou
(2022,2023). The (12+1) methods are:

1) Principal component analysis (PCA) (Hotelling 1933)

2) Multi-dimensional scaling (MDS) (Torgerson 1952 and Gower 1966)

3) Non-metric MDS (iMDS) (Kruskal 1964)

4) Sammon’s mapping (Sammon) (Sammon 1969)

5) Kernel PCA (kPCA) (Schölkopf, Smola and Müller 1998)

6) Locally linear embedding (LLE) (Roweis and Saul 2000)

7) Isomap (Tenenbaum, Silva and Langford 2000)

8) Hessian LLE (HLLE) (Donoho and Grimes 2003)

9) Laplacian eigenmap (LEIM) (Belkin and Niyogi 2003)

10) t-SNE (van der Maaten and Hinton 2008)

11) Uniform manifold approximation and projection for dimension reduction
(UMAP) (McInnes, Healy and Melville 2018)

12) (PHATE) (Moon et al. 2019)

13) Meta-visualization (meta-spec) (Ma, Sun and Zou 2022, 2023)

###  1.1 Remarks on the 13 maps

1) Figure 10 in (Ma, Sun and Zou 2022) shows that PCA and MDS maps are
identical, for MDS is the dual of PCA, a well known result, see Torgerson
(1952) and Gower (1966).

2) For the four methods, kPCA, t-SNE, UMAP and PHATE, two tuning parameters
are used, so there are two maps designated by the addition of integers either
1 or 2 on the title of the maps. This means that the last method meta-
visualization named (meta-spec) is based on the 16 candidate Euclidean
distances computed from the obtained 2-dimensional maps.

3) Only 12 maps are reproduced in (Ma, Sun and Zou 2022)’s paper: PHATE2,
t-SNE2, kPCA1 and meta-spec in Figure 3; Sammon, LLE, LEIM, UMAP, PCA, MDS,
ISOMAP, PHATE in Figure 10.

4) Maps produced by iMDS and HLLE are missing. Furthermore, two almost
identical maps produced by PHATE are represented in Figures 3 and 10.

5) The map (meta-spec) is the best: it discriminates completely the Eastern
and the Western (biblical) chapters; while only the 2 PHATE maps somewhat
ambiguously discriminate the two groups. We will see that the TCA map
discriminates the two groups almost as well as the (meta-spec) map;
furthermore it provides additional complementary information on the two groups
by the interpretation of words associated with each group, as is practised in
CA.

6) All of the above mentioned methods are based on the pairwise Euclidean
distances among the 590 chapters, where each chapter is a vector of counts of
8260 words. The well-known phenomenon of the norm concentration of the
Euclidean distances, see for instance among others (François, Wertz, Verleysen
2007) and (Lee and Verheysen 2011), manifests itself clearly and differently
in the high-dimensional data space and in the embedded low-dimensional
visualization maps: this is the main reason that the maps produced by the 12
simple methods are not sufficiently good enough.

###  1.2 Contents of this paper

We see from the above summary that neither correspondence analysis (CA) nor
its robust $l_{1}$ variant named taxicab CA (TCA) have been applied for
visualization. So, our primary goal is to show that for sparse, and in
particular for extremely sparse high-dimensional contingency tables it is
worth applying CA and TCA jointly. For small sized sparse data sets see
Mallet-Gauthier and Choulakian (2015) and Choulakian (2017).

Benzécri (1973) is the reference book on CA but difficult to read because of
his use of tensor notation. Among others, Greenacre (1984) is the best
representative of Benzécri’s approach; Beh and Lombardo (2014) present a
panoramic review of CA.

We suppose that the theory of CA is known. So the contents of this paper are:
In section 2 we present an overview of taxicab singular value decomposition
(TSVD) on which TCA is developed; in section 3, we present an overview of TCA.
In section 4, we analyze the religious data set introduced above; finally we
conclude in section 5.

##  2 An overview of taxicab singular value decomposition

Consider a matrix $\mathbf{X}$ of size $I\times J$ and $rank(\mathbf{X})=k$.
Taxicab singular value decomposition (TSVD) of X is a decomposition similar to
SVD of X, see Choulakian (2006, 2016).

For a vector $\mathbf{u}=\mathbf{(}u_{i}),$ its taxicab or L1 norm is
$\left|\left|\mathbf{u}\right|\right|_{1}=\sum_{i}|u_{i}|,$ the Euclidean or
L2 norm is
$\left|\left|\mathbf{u}\right|\right|_{2}=(\sum_{i}|u_{i}|^{2})^{1/2}$ and the
L∞ norm is $\left|\left|\mathbf{u}\right|\right|_{\infty}=\max_{i}\ |u_{i}|$.

In TSVD the calculation of the dispersion measures $(\delta_{\alpha})$,
principal axes ($\mathbf{u}_{\alpha},\mathbf{v}_{\alpha})$ and principal
scores $(\mathbf{a}_{\alpha},\mathbf{b}_{\alpha})$ for $\alpha=1,...,k$ is
done in a stepwise manner. We put $\mathbf{X}_{1}=\mathbf{X}=(x_{ij})$ and
$\mathbf{X_{\alpha}}$ be the residual matrix at the $\alpha$-th iteration for
$\alpha=1,...,k$.

The variational definitions of the TSVD at the $\alpha$-th iteration are

$\displaystyle\delta_{\alpha}$
$\displaystyle=\max_{\mathbf{u\in\mathbb{R}}^{J}}\frac{\left|\left|\mathbf{X_{\alpha}u}\right|\right|_{1}}{\left|\left|\mathbf{u}\right|\right|_{\infty}}=\max_{\mathbf{v\in\mathbb{R}}^{I}}\
\frac{\left|\left|\mathbf{X_{\alpha}^{\prime}v}\right|\right|_{1}}{\left|\left|\mathbf{v}\right|\right|_{\infty}}=\max_{\mathbf{u\in\mathbb{R}}^{J},\mathbf{v\in\mathbb{R}}^{I}}\frac{\mathbf{v}^{\prime}\mathbf{X_{\alpha}u}}{\left|\left|\mathbf{u}\right|\right|_{\infty}\left|\left|\mathbf{v}\right|\right|_{\infty}},$
(1) $\displaystyle=\max\ ||\mathbf{X_{\alpha}u||}_{1}\ \ \text{subject to
}\mathbf{u}\in\left\\{-1,+1\right\\}^{J},$ $\displaystyle=\max\
||\mathbf{X_{\alpha}^{\prime}v||}_{1}\ \ \text{subject to
}\mathbf{v}\in\left\\{-1,+1\right\\}^{I},$
$\displaystyle=\max\mathbf{v}^{\prime}\mathbf{X_{\alpha}u}\text{ \ subject to
\
}\mathbf{u}\in\left\\{-1,+1\right\\}^{J},\mathbf{v}\in\left\\{-1,+1\right\\}^{I}.$

The $\alpha$-th principal axes are

$\mathbf{u}_{\alpha}\
=\arg\max_{\mathbf{u}\in\left\\{-1,+1\right\\}^{J}}\left|\left|\mathbf{X_{\alpha}u}\right|\right|_{1}\text{
\ \ and \ \ }\mathbf{v}_{\alpha}\
=\arg\max_{\mathbf{v}\in\left\\{-1,+1\right\\}^{I}}\left|\left|\mathbf{X_{\alpha}v}\right|\right|_{1}\text{,}$
(2)

and the $\alpha$-th principal projections of the rows and the columns are

$\mathbf{a}_{\alpha}=\mathbf{X_{\alpha}u}_{\alpha}\text{ \ and \
}\mathbf{b}_{\alpha}=\mathbf{X_{\alpha}^{\prime}v}_{\alpha}.$ (3)

Furthermore, the following relations are also useful

$\mathbf{u}_{\alpha}=sign(\mathbf{b}_{\alpha})\text{ \ and \
}\mathbf{v}_{\alpha}=sign(\mathbf{a}_{\alpha}),$ (4)

where $sign(.)$ is the coordinatewise sign function, $sign(x)=1$ if $x>0,$ and
$sign(x)=-1$ if $x\leq 0.$

The $\alpha$-th taxicab dispersion measure $\delta_{\alpha}$ can be
represented in many different ways

$\displaystyle\delta_{\alpha}\ $
$\displaystyle=\left|\left|\mathbf{X_{\alpha}u}_{\alpha}\right|\right|_{1}=\left|\left|\mathbf{a}_{\alpha}\right|\right|_{1}=\mathbf{a}_{\alpha}^{\prime}\mathbf{v}_{\alpha},$
(5)
$\displaystyle=\left|\left|\mathbf{X_{\alpha}^{\prime}v}_{\alpha}\right|\right|_{1}=\left|\left|\mathbf{b}_{\alpha}\right|\right|_{1}=\mathbf{b}_{\alpha}^{\prime}\mathbf{u}_{\alpha}$
$\displaystyle=\mathbf{v}_{\alpha}{}^{\prime}\mathbf{X_{\alpha}u}_{\alpha}=sign(\mathbf{a}_{\alpha})^{\prime}\mathbf{X_{\alpha}}sign(\mathbf{b}_{\alpha}).$

The $(\alpha+1)$-th residual matrix is

$\mathbf{X_{\alpha+1}}=\mathbf{X_{\alpha}-a}_{\alpha}\mathbf{b}_{\alpha}^{\prime}/\delta_{\alpha}.$
(6)

An interpretation of the term
$\mathbf{a}_{\alpha}\mathbf{b}_{\alpha}^{\prime}/\delta_{\alpha}$ in (6) is
that, it represents the best rank-1 approximation of the residual matrix
$\mathbf{X_{\alpha}}$, in the sense of the taxicab matrix norm (1).

Thus TSVD of $\mathbf{X}$ corresponds to the bilinear decomposition

$x_{ij}=\sum_{\alpha=1}^{k}a_{\alpha}(i)b_{\alpha}(j)/\delta_{\alpha},$ (7)

a decomposition similar to SVD, but where the vectors
$(\mathbf{a}_{\alpha},\mathbf{b}_{\alpha})$ for $\alpha=1,...,k$ are
conjugate; that is

$\displaystyle\mathbf{a}_{\alpha}^{\prime}\mathbf{v}_{\beta}$
$\displaystyle=\mathbf{a}_{\alpha}^{\prime}sign(\mathbf{a}_{\beta})$ (8)
$\displaystyle=\mathbf{b}_{\alpha}^{\prime}\mathbf{u}_{\beta}=\mathbf{b}_{\alpha}^{\prime}sign(\mathbf{b}_{\beta})$
$\displaystyle=0\text{ for }\alpha\geq\beta+1.$

In the package TaxicabCA in R, the calculation of the principal component
weights, $\mathbf{u}_{\alpha}$ and $\mathbf{v}_{\alpha},$ are accomplished by
three algorithms. The first one, based on complete enumeration equation (2),
is named exhaustive. The second one, based on iterating the transition
formulae (3,4), is named criss-cross. The third one, based on the genetic
algorithm, is named genetic.

##  3 Taxicab correspondence analysis: An overview

CA is a dimension reduction method for exploratory visualization of
contingency tables based on Benzécri’s principle of distributional equivalence
property.

In the journal Revue Philosophique de la France et de l’Étranger, Benzécri
(1966) wrote an elaborate article entitled Linguistique et mathématique, where
he presented his project of uncovering grammatical rules or patterns from
texts by announcing his conceptual formulation of the principle of
distributional equivalence ”que des éléments distributionnellement proches
soient proches sur le diagramme et réciproquement” on which the geometric-
mathematical formulation of CA was essentially developed, and which can be
described by the following two definitions.

Definition 1: Two non negative vectors x and y of the same size are
distributionally equivalent if $\mathbf{x=}C\mathbf{y}$, where $C>0.\vskip
12.0pt plus 4.0pt minus 4.0pt$

Definition 2: A method of analysis satisfies distributional equivalence
property, if it is applied to a table of nonnegative values where two rows (
or two columns) are proportional, then the method will produce maps where the
two proportional rows (or the two proportional columns) coincide. Furthermore,
one can merge the proportional rows (or the proportional columns), and the
method will keep the results invariant.

Remark 1: Many different methods satisfy Definition 2, see among others
Choulakian, Allard and Mahdi (2023).

###  3.1 Preliminaries

Let $\mathbf{N}=(n_{ij})$ for $i=1,...,I$ and $j=1,...,J$ be a 2-way
contingency table and $\mathbf{P=N/}n=(p_{ij})$ of size $I\times J$ the
associated correspondence matrix (probability table) of N, where
$n=\sum_{i,j}n_{ij}$. We define as usual $p_{i+}=\sum_{j=1}^{J}p_{ij}$ the
marginal probability of the $i$-th row, and similarly
$p_{+j}=\sum_{i=1}^{I}p_{ij}$ the marginal property of the $j$-th column.

The CA association index of P is

$\displaystyle\Delta_{ij}$ $\displaystyle=(\frac{p_{ij}}{p_{i+}p_{+j}}-1)$
$\displaystyle=\frac{1}{p_{i+}p_{+j}}(p_{ij}-p_{i+}p_{+j})$
$\displaystyle=\frac{1}{p_{i+}}(\frac{p_{ij}}{p_{+j}}-p_{i+})$
$\displaystyle=\frac{1}{p_{+j}}(\frac{p_{ij}}{p_{i+}}-p_{+j})$

where: $\frac{p_{ij}}{p_{i+}p_{+j}}$ is density function of $p_{ij}$ with
respect to $p_{i+}p_{+j},$ $\frac{p_{ij}}{p_{+j}}$ is the profile of the
$j$-th column and similarly $\frac{p_{ij}}{p_{i+}}$ is the profile of the
$i$-th row.

The CA or Taxicab CA (TCA) decomposition is

$\frac{p_{ij}}{p_{i+}p_{+j}}-1=\sum_{\alpha=1}^{k}f_{\alpha}(i)g_{\alpha}(j)/\delta_{\alpha},$
(9)

where for principal dimensions $\alpha=1,...,k$, $\delta_{\alpha}$ is the
dispersion measure and $(f_{\alpha}(i),g_{\alpha}(j))$ are the principal
factor scores of the rows and the columns respectively; and they are
calculated by generalized singular value decomposition (SVD) or taxicab SVD
(TSVD) of $\Delta_{ij}$, where $k=rank(\Delta_{ij}).$

In CA, the parameters $(f_{\alpha}(i),g_{\alpha}(j),\delta_{\alpha})$ in (9)
satisfy: for $\alpha,\beta=1,...,k$

$\delta_{\alpha}^{2}=\sum_{\alpha=1}^{k}f_{\alpha}^{\ \
2}(i)p_{i+}=\sum_{\alpha=1}^{k}g_{\alpha}^{2}(j)p_{+j}$

$0=\sum_{\alpha=1}^{k}f_{\alpha}(i)p_{i+}=\sum_{\alpha=1}^{k}g_{\alpha}(j)p_{+j}$

$0=\sum_{\alpha=1}^{k}f_{\alpha}(i)f_{\beta}(i)p_{i+}=\sum_{\alpha=1}^{k}g_{\alpha}(j)g_{\beta}(j)p_{+j}$
for $\alpha\neq\beta.$

In TCA, the parameters $(f_{\alpha}(i),g_{\alpha}(j),\delta_{\alpha})$ in (9)
satisfy: for $\alpha,\beta=1,...,k$

$\delta_{\alpha}=\sum_{\alpha=1}^{k}|f_{\alpha}^{\
}|(i)p_{i+}=\sum_{\alpha=1}^{k}|g_{\alpha}(j)|p_{+j}$

$0=\sum_{\alpha=1}^{k}f_{\alpha}(i)p_{i+}=\sum_{\alpha=1}^{k}g_{\alpha}(j)p_{+j}$

$0=\sum_{\alpha=1}^{k}f_{\alpha}(i)\
sign(f_{\beta}(i))p_{i+}=\sum_{\alpha=1}^{k}g_{\alpha}(j)\
sign(g_{\beta}(j))p_{+j}$ for $\alpha>\beta.\vskip 12.0pt plus 4.0pt minus
4.0pt$

The following result is essential in CA of extremely sparse contingency
tables.

Theorem 1: (Benzécri 1973, pp188-190): If $\delta_{1}=1$ in CA, then the
contingency table has two blocks diagonal structure.

Remark 2: Benzécri (1973, p.189-190) observed that ”for sparse data” it is
rare to have $\delta_{1}=1;$ but ”not uncommon” to have $\delta_{1}\geq
0.837,$ then the structure of the contingency table could be quasi-2-blocks
diagonal. For an example see Choulakian (2021).

In the next subsection, we explain in what sense TCA is ROBUST compared to CA.

###  3.2 The robustness of TCA

TCA is computed in 3 steps iteratively. We detail the 1st iteration $\alpha=1$

$\mathbf{P}^{(\alpha)}=\mathbf{P}^{(1)}=(p_{ij}^{(1)}=p_{ij}-p_{i+}p_{+j}$) is
the cross-covariance matrix

Step 1: computation

$\ \ \ \ \ \ \ \ \ \ \ \ \
\mathbf{u}_{1}=(u_{1}(j))=\arg\max_{\mathbf{u\in}\left\\{-1,1\right\\}}||\mathbf{P}^{(1)}\mathbf{u}||_{1}$

$\ \ \ \ \ \ \ \ \ \ \ \ \ \mathbf{a}_{1}=\mathbf{P}^{(1)}\mathbf{u}_{1}$

$\ \ \ \ \ \ \ \ \ \ \ \ \mathbf{v}_{1}=sign(\mathbf{a}_{1})$

$\ \ \ \ \ \ \ \ \ \ \ \
\mathbf{b}_{1}=(\mathbf{P}^{(1)})^{\prime}\mathbf{v}_{1}$

$\ \ \ \ \ \ \ \ \ \ \ \ \mathbf{u}_{1}=sign(\mathbf{b}_{1})$

$\ \ \ \ \ \ \ \ \ \ \ \
\delta_{1}=\mathbf{v}_{1}^{\prime}\mathbf{P}^{(1)}\mathbf{u}_{1}$

Step 2: scaling

$\ \ \ \ \ \ \ \ \ \ \ \ \mathbf{f}_{1}=\mathbf{a}_{1}/(p_{i+})$

$\ \ \ \ \ \ \ \ \ \ \ \ \mathbf{g}_{1}=\mathbf{b}_{1}/(p_{+j})$

Step 3: residual matrix…

$\ \ \ \ \ \ \ \ \ \
\mathbf{P}^{(2)}=\mathbf{P}^{(1)}-f_{1}(i)g_{1}(j)/\delta_{1}$

$\alpha=\alpha+1$ go to Step 1

The robustness of TCA follows from the following two observations that we
describe for the 1st iteration $\alpha=1$:

Fact 1: $p_{ij}^{(1)}=p_{ij}-p_{i+}p_{+j}$ is double-centered: $\sum_{i}$
$p_{ij}^{(1)}=\sum_{j}$ $p_{ij}^{(1)}=0.$

Fact 2: The coordinates of the principal axes (weights)
$\mathbf{u}_{1}=(u_{1}(j))$ and $\mathbf{v}_{1}=(v_{1}(j))$ have values $1$ or
$-1$.

These two facts imply that at iteration $\alpha=1$, the residual (cross-
covariance) matrix is divided into 4 balanced quadrants equally dispersed (not
true in CA):

$\displaystyle\delta_{1}/4$ $\displaystyle=\sum_{i,j}(p_{ij}^{(1)}:\
v_{1}(i)=u_{1}(j)=1)$ $\displaystyle=\sum_{i,j}(p_{ij}^{(1)}:\
v_{1}(i)=u_{1}(j)=-1)$ $\displaystyle=\sum_{i,j}(p_{ij}^{(1)}:\
v_{1}(i)=-u_{1}(j)=1)$ $\displaystyle=\sum_{i,j}(p_{ij}^{(1)}:\
v_{1}(i)=-u_{1}(j)=-1).$

From which we define 5 QSR (quality of signs of residuals) indices for each
principal dimension: 1 global, 2 attractive (positive) and 2 repulsive
(negative).

For $\alpha=1...k$

$QSR_{\alpha}=\frac{\delta_{\alpha}}{\sum_{i,j}|p_{ij}^{(\alpha)}|}$

$QSR_{\alpha}(v_{\alpha}(i)=u_{\alpha}(j)=1)=\frac{\delta_{\alpha}/4}{\sum_{(i,j:v_{\alpha}(i)=u_{\alpha}(j)=1)}|p_{ij}^{(\alpha)}|}$

$QSR_{\alpha}(v_{\alpha}(i)=u_{\alpha}(j)=-1)=\frac{\delta_{\alpha}/4}{\sum_{(i,j:v_{\alpha}(i)=u_{\alpha}(j)=-1)}|p_{ij}^{(\alpha)}|}$

$QSR_{\alpha}(v_{\alpha}(i)=-u_{\alpha}(j)=1)=-\frac{\delta_{\alpha}/4}{\sum_{(i,j:v_{\alpha}(i)=-u_{\alpha}(j)=1)}|p_{ij}^{(\alpha)}|}$

$QSR_{\alpha}(v_{\alpha}(i)=-u_{\alpha}(j)=-1)=-\frac{\delta_{\alpha}/4}{\sum_{(i,j:v_{\alpha}(i)=-u_{\alpha}(j)=-1)}|p_{ij}^{(\alpha)}|}$

The 5 QSR indices satisfy

Lemma 1: For $\mathbf{P}^{(\alpha)}$ for $\alpha=1,...,k$ and
rank($\mathbf{P}^{(1)})=k$

a) $-1\leq QSR\leq 1$

b) For $\alpha=1,...,k-1,$ $QSR_{\alpha}=1$ if and only if

$QSR_{\alpha}(v_{\alpha}(i)=u_{\alpha}(j)=1)=QSR_{\alpha}(v_{\alpha}(i)=u_{\alpha}(j)=-1)=$

$-QSR_{\alpha}(v_{\alpha}(i)=-u_{\alpha}(j)=1)=-QSR_{\alpha}(v_{\alpha}(i)=-u_{\alpha}(j)=-1)=1.$

c) For $\alpha=k,$ $QSR_{\alpha}=1.\vskip 12.0pt plus 4.0pt minus 4.0pt$

In the next section, we analyze-visualize the religious data set by CA and TCA
using two R packages: ca by Greenacre, Nenadic and Friendly (2020) and
TaxicabCA by Allard and Choulakian (2019).

##  4 CA and TCA maps

The data set, constructed by (Sah and Fokoué, 2019), concerns $I=590$
fragments of texts extracted from English translations of 8 religious-sacred
scripts: the first 4 of them from the ancient Bible and the rest from extreme
Orient countries Tibet (B), China (T) and India (Y, U):

Book of Proverb (P) composed of 31 chapters

Book of Ecclesiastes (E) composed of 12 chapters

Book of Ecclesiasticus (e) composed of 50 chapters

Book of Wisdom (W) composed of 19 chapters

Four Noble Truth of Buddhism (B) composed of 45 chapters

Tao Te Ching (T) composed of 81 chapters

Yogasutras (Y) composed of 189 chapters

Upanishads (U) composed of 162 chapters

Remark 3:

a) A symbol such as (P) represents a chapter from the Book of Proverb. The 8
letters (P, E, e, W, B, T, Y, U) in the parentheses will be used to represent
the rows of the data set on the CA and TCA maps.

b) The total number of ORIENTAL chapters is 478 (number of words counted is
30252), which is much larger than (almost equal to) the total number of
Biblical chapters 112 (number of words counted is 30355). This means that on
the average the chosen fragments of ORIENTAL books are much sparser than the
chosen fragments from the BIBLICAL books.

c) The apparent % of zero cells is 99.14% based on the initial data set of
size $590\times 8265$. While by Benzécri’s principle of distributional
equivalence property (see Definitions 1 and 2), the real % of zero cells is
98.65% based on the merged data set of size $589\times 4864$. Note that the
marginal count of the words in the chosen fragment of ch 14 of the B book is
null; so in CA and TCA this row is eliminated. So we consider the data set as
extremely sparse.

###  4.1 CA map

Figure 1 displays the CA map, where the % of explained inertia is 1.1%
$(06+0.5)$ considered too small, and the Buddhism (B) chapters dominate the
first and the second principal dimensions. However, examining the first four
dispersion values (0.80, 0.72, 0.71 and 0.70), we see that the first
dispersion value 0.80 is quite near to Benzécri’s advocated lower bound of
0.837 as stated in Remark 2. So we can guess that the structure of the
contingency table could be quasi-2-blocks diagonal.

###  4.2 TCA maps

Figure 2 displays the TCA map of 589 chapters, where we notice that: a) The
first principal dimension impressively separates the EASTERN books and the
Bible books. This confirms Benzécri’s observation that the data set has
quasi-2-blocks structure. The Eastern books are much more dispersed than the
Bible books, because of Remark 3b. b) Concerning the interpretation of the
second principal dimension, we observe: on the right clear separation of the
books (B,T) and the books (Y,U); and on the left, the separation of the book
(W) from the rest.

Figure 3 displays the TCA map of the words, where we observe that: a) The
EASTERN books are positively-attractively associated with the words (pain,
view, mental, bodily, external, perception, effort, consciousness, eternal,
mystical, spiritual, psychical, powers) representing mainly intangible
concepts; b) The BIBLE books are positively-attractively associated with the
words (enemies, hands, mercy, judgement, grace, justice, gold, lips, ways,
tongue mouth, wicked, house, poor) representing mainly tangible objects.

Table 1 displays the five QSR indices for the first four principal dimensions.
QSR${}_{1}=38.3\%$ is clearly different from the rest. The first two columns
show that the attractive associations (27.7% and 31.1%) are much smaller in
absolute values than the repulsive associations $(-59.1\%,$ $-51.9\%)$; which
implies the role played by the extreme sparsity of the contingency table thus
exhibiting the quasi-2-blocks diagonal structure.

Table 1: QSR (%) for the first 4 principal dimensions.
---
| TCA of $(n_{ij})$ |  |  |
Axis $\alpha$ | $QSR_{\alpha}(V_{+}U_{+},V_{-}U_{-})$ | $QSR_{\alpha}(V_{-}U_{+},V_{+}U_{-})$ | $QSR_{\alpha}$ | $\delta_{\alpha}$
1 | (27.7, 31.1) | (-59.1, -51.9) | 38.3 | 0.669
2 | (21.3, 21.1) | (-31.8, -33.7) | 25.7 | 0.437
3 | (23.3, 16.0) | (-30.2, -36.5) | 24.1 | 0.431
4 | (18.5, 19.4) | (-28.0, -27.8) | 22.6 | 0.391

##  5 Conclusion

There are two main approaches for dimension reduction of high-dimensional data
sets SVD-like or MDS-like. MDS-like methods are distance based, often
Euclidean. Recently developed methods (t-SNE, UMAP, …) in machine learning are
MDS-like, and they are characterized by the following two general points:
First, the pairwise distances computed in the high-dimensional spaces take
into consideration the nonlinear (local and global) structures, thus
emphasizing or balancing one aspect over the other; second, a loss-function is
minimized to compute the pairwise distances in the low-dimensional spaces; see
for example Wang et al. (2021). CA can be interpreted both as a generalized
SVD decomposition or a MDS-like method. While TCA is based on TSVD without a
loss function exactly imitating-generalizing Hotelling (1933)’s PCA approach.

The topic of interpretability being central in machine learning nowadays, see
for instance (Allen, Gan, Zheng 2023), this paper shows that our approach
based on CA framework is preferable to the approaches used in (Ma, Sun and Zou
2022): Figure 2 of this paper is very similar to Figure 3c (meta-spec) in (Ma,
Sun and Zou 2022); however the words embedded in Figur 3 of this paper brings
further interpretable details, which are missing in the methods discussed in
(Ma, Sun and Zou 2022) paper.

This paper showed on a case study that the joint use of CA and TCA are valid
visualization methods for sparse or extremely sparse contingency tables, and
they are worth trying.

    \bigskip Acknowledgements

Choulakian’s research has been supported by NSERC of Canada.

References

Allard J, Choulakian V (2019) Package TaxicabCA in R

Allen GI, Gan L, Zheng L (2023) Interpretable machine learning for discovery:
Statistical challenges & opportunities. https://arxiv.org/pdf/2308.01475.pdf

Beh E, Lombardo R (2014) Correspondence Analysis: Theory, Practice and New
Strategies. N.Y: Wiley

Belkin M, Niyogi P (2003). Laplacian eigenmaps for dimensionality reduction
and data representation. Neural Computation, 15 (6), 1373-1396

Benzécri JP (1973) L’Analyse des Données: Vol. 2: L’Analyse des
Correspondances. Paris: Dunod

Choulakian V (2006) Taxicab correspondence analysis. Psychometrika, 71,
333-345

Choulakian V (2016) Matrix factorizations based on induced norms. Statistics,
Optimization and Information Computing, 4, 1-14

Choulakian V (2017) Taxicab correspondence analysis of sparse contingency
tables. Italian Journal of Applied Statistics, 29 (2-3), 153-179

Choulakian V (2021) Quantification of intrinsic quality of a principal
dimension in correspondence analysis and taxicab correspondence analysis.
Available on arXiv:2108.10685

Choulakian V, Allard J, Mahdi S (2023) Taxicab correspondence analysis and
Taxicab logratio analysis: A comparison on contingency tables and
compositional data. Austrian Journal of Statistics, 52, 39 – 70

Donoho DL, Grimes C (2003). Hessian eigenmaps: Locally linear embedding
techniques for high-dimensional data. Proceedings of the National Academy of
Sciences, 100 (10), 5591-5596

François D, Wertz V, Verleysen M (2007) The concentration of fractional
distances. IEEE Transactions on Knowledge and Data Engineering, 19 (7),
873–886.

Gower JC (1966) Some distance properties of latent root and vector methods
used in multivariate analysis. Biometrika 53 (3), 325–338

Greenacre MJ (1984) Theory and Applications of Correspondence Analysis.
Academic Press, London

Kruskal JB (1964) Nonmetric multidimensional scaling: A numerical method.
Psychometrika, 29 (2), 115-129

Hotelling H (1933) Analysis of a complex of statistical variables into
principal components. Journal of Educational Psychology, 24(6), 417-441

Lee JA, Verleysen M (2011) Shift-invariant similarities circumvent distance
concentration in stochastic neighbor embedding and variants. International
Conference on Computational Science, Procedia Computer Science 4, 538–547

Ma R, Sun E, Zou J (2023) A spectral method for assessing and combining
multiple data visualizations. Nature Communications, 14(1):780 doi:
10.1038/s41467-023-36492-2

Ma R, Sun E, Zou J (2023) A spectral method for assessing and combining
multiple data visualizations. https://arxiv.org/pdf/2210.13711.pdf

Mallet-Gauthier S, Choulakian V (2015) Taxicab correspondence analysis of
abundance data in archeology: three case studies revisited. Archeologia e
Calcolatori, 26, 77-94

McInnes L, Healy J, Melville J (2018). Umap: Uniform manifold approximation
and projection for dimension reduction. arXiv:1802.03426

Moon KR, van Dijk D, Wang Z, Gigante S, Burkhardt DB, Chen WS, Yim K, van den
Elzen A, Hirn MJ, Coifman DR, Natalia B Ivanova NB, Wolf G, Krishnaswamy S
(2019). Visualizing structure and transitions in highdimensional biological
data. Nature Biotechnology 37 (12), 1482-1492

Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear
embedding. Science, 290 (5500), 2323-2326

Sah P, Fokoué E (2019) What do asian religions have in common? an unsupervised
text analytics exploration. arXiv:1912.10847

Sammon JW (1969) A nonlinear mapping for data structure analysis. IEEE
Transactions on Computers, 100 (5), 401-409

Scholkopf B, Smola A, Muller KR (1997) Kernel principal component analysis. In
International Conference on Artificial Neural Networks, 583-588, Springer

Tenenbaum JB, Silva V, Langford JC (2000) A global geometric framework for
nonlinear dimensionality reduction. Science, 290 (5500), 2319-2323

Torgerson W (1952) Multidimensional scaling: I. theory and method.
Psychometrika, 17(4), 401–419

van der Maaten L, Hinton G (2008) Visualizing data using t-SNE. Journal of
Machine Learning Research 9(Nov), 2579-2605

Wang Y, Huang H, Rudin C, Shaposhnik Y (2021) Understanding how dimension
reduction tools work: An empirical approach to deciphering t-sne, umap,
trimap, and pacmap for data visualization. Journal of Machine Learning
Research, 22, 1-73