Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
The problem of computer tomography is considered from incomplete projection data with chaotic algorithms for some particular systems of reconstruction. The numerical reconstruction algorithms and numerical simulation results are presented for a number of modeling objects which can be described by me...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101570 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2008. — Т. 30, № 3. — С. 29-43. — Бібліогр.: 12 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101570 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1015702025-02-23T19:11:02Z Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data Gubareni, N. Pleszczynski, M. Информационные технологии, защита информации The problem of computer tomography is considered from incomplete projection data with chaotic algorithms for some particular systems of reconstruction. The numerical reconstruction algorithms and numerical simulation results are presented for a number of modeling objects which can be described by means of discrete functions. Рассмотрена задача компьютерной томографии по неполным проекционным данным с использованием хаотических алгоритмов для некоторых специальных систем восстановления. Представлены численные алгоритмы восстановления и результаты численного моделирования для ряда моделируемых объектов, которые могут быть описаны посредством дискретных функций. Розглянуто задачу комп’ютерної томографії по неповним проективним даним з використанням хаотичних алгоритмів для деяких спеціальних систем відновлення. Наведено числові алгоритми відновлення та результати числового моделювання для об’єктів, які можуть бути описані дискретними функціями. 2008 Article Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2008. — Т. 30, № 3. — С. 29-43. — Бібліогр.: 12 назв. — англ. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101570 en Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Информационные технологии, защита информации Информационные технологии, защита информации |
| spellingShingle |
Информационные технологии, защита информации Информационные технологии, защита информации Gubareni, N. Pleszczynski, M. Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data Электронное моделирование |
| description |
The problem of computer tomography is considered from incomplete projection data with chaotic algorithms for some particular systems of reconstruction. The numerical reconstruction algorithms and numerical simulation results are presented for a number of modeling objects which can be described by means of discrete functions. |
| format |
Article |
| author |
Gubareni, N. Pleszczynski, M. |
| author_facet |
Gubareni, N. Pleszczynski, M. |
| author_sort |
Gubareni, N. |
| title |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data |
| title_short |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data |
| title_full |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data |
| title_fullStr |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data |
| title_full_unstemmed |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data |
| title_sort |
chaotic iterative algorithms for image reconstruction from incomplete projection data |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2008 |
| topic_facet |
Информационные технологии, защита информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101570 |
| citation_txt |
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2008. — Т. 30, № 3. — С. 29-43. — Бібліогр.: 12 назв. — англ. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT gubarenin chaoticiterativealgorithmsforimagereconstructionfromincompleteprojectiondata AT pleszczynskim chaoticiterativealgorithmsforimagereconstructionfromincompleteprojectiondata |
| first_indexed |
2025-11-24T14:28:22Z |
| last_indexed |
2025-11-24T14:28:22Z |
| _version_ |
1849682299624357888 |
| fulltext |
N. Gubareni,
Czestochowa University of Technology
(Dabrowskiego str. 69, 42-200 Czestochowa, Poland,
E-mail: gubareni@zim.pcz.pl),
M. Pleszczynski
Silesian University of Technology
(Kaszubska str. 23, 42-401 Gliwice, Poland, E-mail: dm101live@interia.pl)
Chaotic Iterative Algorithms for Image
Reconstruction from Incomplete Projection Data
(Recommended by Prof. E. Dshalalow)
The problem of computer tomography is considered from incomplete projection data with chaotic
algorithms for some particular systems of reconstruction. The numerical reconstruction algo-
rithms and numerical simulation results are presented for a number of modeling objects which
can be described by means of discrete functions.
Ðàññìîòðåíà çàäà÷à êîìïüþòåðíîé òîìîãðàôèè ïî íåïîëíûì ïðîåêöèîííûì äàííûì ñ
èñïîëüçîâàíèåì õàîòè÷åñêèõ àëãîðèòìîâ äëÿ íåêîòîðûõ ñïåöèàëüíûõ ñèñòåì âîññòà-
íîâëåíèÿ. Ïðåäñòàâëåíû ÷èñëåííûå àëãîðèòìû âîññòàíîâëåíèÿ è ðåçóëüòàòû ÷èñëåííîãî
ìîäåëèðîâàíèÿ äëÿ ðÿäà ìîäåëèðóåìûõ îáúåêòîâ, êîòîðûå ìîãóò áûòü îïèñàíû ïîñðåäñò-
âîì äèñêðåòíûõ ôóíêöèé.
K e y w o r d s : computer tomography, algebraic reconstruction technique (ART), asynchronous
methods, chaotic algorithms, numerical simulation.
Technique of computerized tomography has a wide application not only in medi-
cine but also for solving many technical problems. In these applications the pro-
jection data are often not available at each angle of view and may be very limited
in number. In this case we say that we have an incomplete projection data. In par-
ticular, such kind of problems arises in mineral industries and engineering geo-
physics connected with acid drainage, the stability of mine workers, mineral ex-
ploration and others [1, 2]. For these problems the projection operator can be
represented algebraically and the problem of image reconstruction is reduced to
solving a system of linear algebraic equations. For solving such systems there
often used different kinds of algebraic iterative algorithms the most well-known
from which are Algebraic Reconstruction Technique (ART) algorithms [3—7].
They are generally simple, flexible and permit to use a priori knowledge of the
object before its reconstruction that is very important in many practical
applications.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 29
In this paper we consider the problem of image reconstruction from incom-
plete projection data for some particular reconstruction systems which arise in
some problems of engineering geophysics and mineral industry. For solving this
problems we use the chaotic iterative algebraic algorithms. Numerical simula-
tion of solving problems for image reconstruction from incomplete projection
data for some modeling objects, comparing evaluations of errors and rate of
convergence of these algorithms are presented. It is shown that for some choice
of parameters we can obtain a good enough quality of reconstruction with these
algorithms for some number of iterations.
Image reconstruction from incomplete projection data. Let f x y( , ) be a
function which represents the spatial distribution of a physical parameter. If L is
a line (ray) in the plane then the line integral
p f x y dLL
L
�
�
( , ) ,
which is usually called a projection, is usually obtained from physical measure-
ments.
From mathematical point of view the problem of reconstruction from pro-
jections is to find an unknown function f x y( , )by means of a given set of projec-
tions pL for all L. In practice we are given only discrete projection data that esti-
mate p for a finite number of rays. And we want to find an image function
f x y( , ), i. e. a reconstructed estimate of the unknown object. Moreover, we are
deal with limited precision of measured data and so the projection data are given
with some errors.
In many practical applications the projection data cannot be available for
each direction and its number is very limited. In this case we say that we have a
problem of image reconstruction with incomplete projection data. In particular,
such kind of problems arise in mineral industries and engineering geophysics
connected with acid drainage, the stability of mine workers, mineral exploration
and others [1, 2].
In dependence on the obtaining system of projections there are many image
reconstruction schemes, the main of them are parallel and beam schemes in the
two-dimensional space. In some practical problems, in engineering for example,
it is impossible to get projections from all directions because of the existing
some important reasons (such as situation, size or impossibility of an access to a
research object). This situation arises, for example, in the coal bed working (Fig. 1).
In such a coal bed during the preparing process for working in dependence on the
scheme the access to longwalls may be very difficult or impossible at all. Some-
times it is impossible to access to one or two sides of longwalls, and sometimes it
is impossible only to access to the basis but all the longwalls are accessible. Each
this situation has its own scheme of obtaining information.
N. Gubareni, M. Pleszczynski
30 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
In this paper we present results for image reconstructions only for two dif-
ferent schemes, which are described below.
Consider the scheme of obtaining projection data which we shall call as the
system (1�1). In this scheme we have an access to a research coal bed from only
two opposite sides. This situation often arises in engineering geophysics as well.
In this case the sources of rays are situated only on one side and the detectors are
situated on the opposite side of the research part of a coal bed. This scheme of
obtaining information is shown in Fig. 2, a. And the second scheme of obtaining
projection data, which we shall call the system (1�1, 1�1), is shown in Fig. 2, b.
In this situation we can have an access to all four sides of a coal bed. Then the
sources can been situated onto two neighboring sides, and the detectors can been
situated on the opposite sides. So the projections can be obtained from two pair
of the opposite sides.
Generalized model of asynchronous iterations. From mathematical point
of view asynchronous algorithms are based on the method of asynchronous
iterations which first introduced in the work [8], under the name “random relax-
ations” for solution of systems of linear algebraic equations. Further develop-
ment of these methods and their generalization for the case of nonlinear opera-
tors was obtained in the work [9, 10]. The important results were obtained by El
Tarazi [11] who introduced a visual model for the class of asynchronous algo-
rithms, and obtained the first correct conditions of convergence in the nonlinear
case for constraining operators.
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 31
1
3
2
4
E
5
6
Fig. 1. The scheme of a coal bed working: 1 — sources; 2 — detectors; 3 — unmined coal; 4 —
heading; 5 — longwall with mechanized lining, belt conveyor flight, heading machine so on; 6 –
caving or filling; E – researching coal bed
Let T i i
m
�
�
{ }T
1
be a set of nonlinear operators acting on the Euclidean space
R
n
and let S be an algorithmic operator. Consider the next iterative process:
y T x
k i
i
k, ( )
�
�1
, x S x y
k k k i
i
m
�
�
�
( {
( ) ,
, } )
1
1
,
where x is an n-dimensional vector of the space R
n
, i m�{ , ,..., }1 2 for every k =
= 0, 1, 2, ... .
We will consider the parallel asynchronous implementation of such an itera-
tive process on a parallel multiprocessor structure consisted of m independent
elementary processors and some central processor. Each i-th elementary pro-
cessor executes its calculations with its own pace in accordance with some for-
mula correspondent to the operator Ti . It has its own local memory and con-
nects only with central processor. We assume that each elementary processor
can have access to the central processor at any time. After each cycle of calcu-
lations of a vector y
k i,
the i-th processor sends this value to the central proces-
sor and loads from it the new value x
k
as its new initial data.
The important notion in the theory of asynchronous iterations is the se-
quence of chaotic sets.
Definition 1. A sequence of nonempty subsets I I k k�
�
�
{ }
0
of the set {1, 2…,
..., m} is a sequence of chaotic sets if lim sup { , ,..., }
j
jI m
��
� 1 2 (another words, if
each integer j m�{ , ,..., }1 2 appears in this sequence infinite many times).
For the first time such sequences were used in the work [9].
Definition 2. If I jk k�{ }, for any k, in a sequence of chaotic sets I I k k�
�
�
{ }
0
of the set {1,2…, m}, (i. e. each subset Ik consists of only one element), then
such sequence is called acceptable (or admissible).
N. Gubareni, M. Pleszczynski
32 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
1
1
a b
4
4
3
3
3
2
2
2
2
Fig. 2. The scheme of obtaining projection data: a — system (1�1); b — system (1�1, 1�1);
1 — sources of rays; 2 — research objects; 3 — rays; 4 — detectors
Suppose that Parallel Computing System (PCS) consists of m of processors
working local independently. In this case the notion of the sequence of chaotic
sets has a simple interpretation: it sets the time diagram of a work of each proces-
sor during non-synchronous work of PCS. So the subset Ik is the set of the num-
bers of those processors which access the central processor at the same time.
Note, that the definition of the sequence of chaotic sets can be given in the
following equivalent form.
Lemma 1. Let I I k k�
�
�
{ }
0
be a sequence of nonempty subsets of the set
{1,2..., m}. Then the following conditions are equivalent:
1) lim sup { , ,..., }
k
kI m
��
� 1 2 ;
2) the set {k | i� I k } is unlimited for each i = 1,2..., m.
3) for each j�N there exists p j( )�N such that the following condition satis-
fies:
I mi
i j
j p j
�
�
1
1 2
( )
{ , ,..., }� .
(1)
The proof of this lemma one can find, for example, in [4].
For any sequence of chaotic sets the numbers p j( ) depends on a number j.
In practice and for research of convergence of asynchronous implementations of
iterative processes there are more important sequences of chaotic sets, for which
these numbers do not depend on the number j.
Definition 3. If for a sequence of chaotic sets I I k k�
�
�
{ }
0
the numbers p j( ),
defined by (1), do not depend on the choice of number j, i. e., p j T( ) � �const
for each j�N, then such a sequence is called regular, and the number T is called
the number of regularity of the sequence I.
Note, that this definition coincides with concept of a regular sequence, in-
troduced in the paper [11] for the case of admissible sequence.
Other important concept in the theory of asynchronous iterations is the no-
tion of a sequence of delays.
Definition 4. A sequence J k k�
�
�
{ ( )}
1
of m-dimensional vectors
( )k �
�{ ( ), ( ),..., ( )}
1 2
k k km with integer coordinates, satisfying the following
conditions:
0 1� � �
i k k( ) ; (2)
lim ( )
k
i k
��
��
(3)
for each i = 1, 2, ..., m and k�N, is called a sequence of delays. In the case, when
instead of condition (3) it holds the following condition:
there exists a fixed number L�N such that
k k Li� �
( ) (4)
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 33
for each k�N and i = 1, 2, ..., m, the sequence is called a sequence with limited
delays and the number L is called a delay, or an asynchronous measure.
The sequence of delays determines the numbers of using iterations by each
fixed processor, and the number L shows a depth of used iterations and actually
reflects possibilities of the concrete computing system. For synchronous imple-
mentation of the iterative process the difference k ki�
( ) is equal to 0 for all i =
=1, 2, ..., m and k�N.
Recall the definition of generalized model of asynchronous computational
process [12].
Definition 5. Let we have a set of nonlinear operators Ti : R R
n n
� ,
i m�{ , ,..., }1 2 and an initial value of vector x R
0
�
n
. A generalized model of the
asynchronous iterations with limited delays for the set of operators Ti , i = 1, 2, ...
..., m is a method of building the sequence of vectors { }x
k
k�
�
0
, which is given re-
cursively by the following scheme:
y
T x
y
k i i
k
k
k i
i
i I,
( ( ))
,
, ;
,
�
�
�
�
�
�
�
if
otherwise;
1
x S x y
( ) ( ) ,
( , { } )
k k k i
i I k
�
�
�
1
,
where I I k k�
�
�
{ }
1
is a sequence of chaotic sets such that I mk �{ , ,..., }1 2 and
J ki
i
k�
�
�
{ ( )}
1
are sequences of limited delays (i = 1, 2, ..., m).
Chaotic iterative algorithms for image reconstruction. The full discrete
model of the problem of image reconstruction is reduced to solving a system of
linear algebraic equations of the form:
A x p� � , (5)
where A R�
m n,
is the matrix of coefficients; x R� �{ , ,..., }x x xn
T n
1 2
is the image
vector; p R� �{ , ,..., }p p pm
T m
1 2
is the measurement vector of projection data.
This system has a few characteristics: it is a rectangular as a rule and it has a
very large dimension. For solving this system it is often used different kind of
algebraic iterative algorithms which are based on the Kaczmarz method, the
most well-known of which are the additive algorithm ART [3—6]. These algo-
rithms are very flexible and allow to apply different a priory information about
object before its reconstruction which is especially very important when we have
an incomplete projection data. The basic idea of these algorithms is to run
through all equations cyclically with modification of the present estimate x
( )k
in
such a way that the present equation with index i is fulfilled. Denote by
P x x
a x
a
ai
i
i
i
ip
( )
( , )
� �
�
2
; P I Pi i
�
� �� � ( ) ,1
where a
i
is the i-th row of a matrix A, 0 < � < 2 is a relaxation parameter.
N. Gubareni, M. Pleszczynski
34 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
A l g o r i t h m 1 (ART):
1. x R
( )0
�
n
is an arbitrary vector.
2. The k-th iteration is calculated in accordance with following scheme:
x P x
( ) ( )k
i
kk
�
1 �
( , ,..., )i m�1 2 , where Pi
k�
are operators defined by (10), �k are
relaxation parameters, 0 <�k < 2 and i k k m( ) (mod )� 1.
Algorithm 1 was investigated in [6], and it was used successfully in medi-
cine. This algorithm is consequence, and moreover the numbers of operators in
this algorithm are chosen by the cyclic way.
In practice the vector of projection data is given as a rule with some error.
Therefore instead of a system of linear equation (5) we have a system of linear
inequalities:
p e A x p e� � � � , (6)
where e �{ , ,..., }� � �
1 2 m is a non-negative vector. And we can consider that the
vector e is given a priory and defines the errors of projection data. In this case
we can introduce the following projection operators:
P x x
a x a x
a
ai
i
i i i i
i
i
ip p
( )
(( , ) ) ( ( , ))
� �
� � � � �
� �
2
,
(7)
where
s
s s
�
��
�
, ;
,
if
otherwise;
0
0
and
P I Pi i
�
� �� � ( )1 (8)
where a
i
is the i-th row of a matrix A, 0 < � < 2 is a relaxation parameter.
For solving the system of inequalities (6) we use the following algorithm.
A l g o r i t h m 2 (ART-3):
1. x R
( )0
�
n
is an arbitrary vector.
2. The k-th iteration is calculated in accordance with such a scheme:
x CP x
( ) ( )k
i
kk
�
1 �
( , ,..., )i m�1 2 , where Pi
k�
are operators defined by (7) and (8), 0 <
< �k < 2 are relaxation parameters, i k k m( ) (mod )� 1, and C is a constraining
operator.
Now we apply the generalized model of asynchronous iterations for imple-
mentation of algorithm ART on non-synchronous computer structure. In this
case we obtain the following chaotic algorithm, where the numbers of operators
are chosen by the chaotic way.
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 35
A l g o r i t h m 3:
1. x R
( )0
�
n
is an arbitrary vector.
2. The k + 1-th iteration is calculated in accordance with such a scheme:
y
P x
y
k i i
k
k
k i
k
i
i I
�
�
�
�
�
�
1,
( ( ))
,
, ;
,
�
if
otherwise;
x y
( ) ,
,
k
i
k
i I
k i
k
�
� �
1 1
� ( , ,..., )i m�1 2 ,
where Pi
k�
are operators defined by (7) and (8), 0 <�k < 2 are relaxation parame-
ters, � i
k
are positive real numbers with property � k
i
i I k�
� �1 for each k�N, I �
�
�
�
{ }I k k 1
is a sequence of chaotic sets such that I mk �{ , ,..., }1 2 , J ki
i
k�
�
�
{ ( )}
1
are sequences of chaotic sets.
The convergence of this algorithm is given by the following theorem.
Theorem 1. Let system (5) be consistent, I I k k�
�
�
{ }
1
be a regular sequence
of chaotic sets I mk �{ , ,..., }1 2 with a number of regularity T, { ( )}
i
kk
�
�
1
be se-
quences with limited delays and
j
i
ik k( ) ( )� and , and let the number of de-
lay be equal to T. Then for every point x R
( )0
�
n
the sequence { }x
k
k�
�
0
defined
by algorithm 3 converges to some point x
*
�H, which is a fixed point of or-
thogonal projection operators Pi (i = 1, 2, ..., m).
The full proof of this theorem one can find in [4]. We now consider the par-
ticular case of algorithm 2, Chaotic Algebraic Reconstruction Technique
(CHART) when we have no delays and the sequence of chaotic sets is
acceptable.
A l g o r i t h m 4 (CHART-3):
1. x R
( )0
�
n
is an arbitrary vector.
2. The k+1-th iteration is calculated in accordance with following scheme:
y
P x
y
k i i
k
k
k i
k i I
,
( )
,
, ,
,
�
��
�
�
�
�
�
� 1
1
if
otherwise;
x C y
( ) ,
,
k
i
k
i I
k i
k
�
�
�� ( , ,..., )i m�1 2 ,
where Pi
k�
are operators defined by (7) and (8), 0 < �k < 2, are relaxation pa-
rameters, � i
k
are positive real numbers with property � k
i
i I k�
� �1 for each k�N,
N. Gubareni, M. Pleszczynski
36 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
I I k k�
�
�
{ }
1
is an acceptable sequence of chaotic sets such that I mk �{ , ,..., }1 2
and C is a constraining operator. In this paper we consider that C= C1 C2 C3
where
C
E
1
0
[ ]
, ,
,
x
x x
�
��
�
if
otherwise;
( [ ])
, ,
, ,
, ;
C
a x a
x a x b
b x b
i
i
i i
i
2
x �
�
� �
�
�
�
�
�
if
if
if
( [ ])
, ,
,
C
p a
x
j
i ij
j
3
0 0 0
x �
� � ��
�
if
otherwise.
The convergence of algorithm 4 is given by the following theorem.
Theorem 2. Let system (6) be consistent, I I k k�
�
�
{ }
1
be an acceptable
sequence of chaotic sets I mk �{ , , ..., }1 2 . Then for every point x R
( )0
�
n
the
sequence { }x
k
k�
�
0
defined by algorithm 4 converges to some solution of this
system.
The proof of this theorem is the same as theorem 1.
Computer simulation and experimental results. In order to evaluate the
goodness of the compute reconstruction of a high-construct image from incom-
plete data we tested different kinds of geometric figures and reconstruction
schemes.
An important factor in the simulation process of image reconstruction is the
choice of modeling objects which describe the density distribution of research ob-
jects. In a coal bed, where we search the reservoirs of compressed gas or
interlayers of a barren rock, the density distribution may be considered discrete
and the density difference of these three environments (coal, compressed gas and
barren rock) is significant. Therefore for illustration of the implementation of the
algorithms working with incomplete data we chose the discrete functions with
high contrast. In this paper we present only the results of computer reconstruction
for two discrete figures and two reconstructions systems (1 1� ) and (1 1� ,1 1� ).
The first discrete function f x y
1
( , ) is given by the following equation:
f x y
x y D E
1
2
1
0
( , )
, ( , ) ,
,
�
� � ��
�
R
otherwise,
where E is a square E x y x y� � � �{( , ): , }1 1 , and D is a subset of E of the form D=
= [–0.4,–0.2] � [–0.5,0.5] � [–0.2,0.2] � [0.3,0.5] � [–0.2,0.2] � [–0.1,0.1] �
������ ! � [0.1,0.3].
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 37
The second figure is given by the following equation:
f x y
x y D E
x y D E
x y D
2
1
2
2
2
3
1
2
3( , )
, ( , ) ,
, ( , ) ,
, ( , )�
� � �
� � �
�
R
R
� �
� � �
�
�
�
�
�
�
�
�
E
x y D E
R
R
2
4
2
4
0
,
, ( , ) ,
, otherwise,
where E is a square E x y x y� � � �{( , ): , }1 1 , and Di are subsets of E of the form
D1 = [–0.7, –0.4] � [–0.5, 0.2], D2= [–0.2, 0.2] � [–0.1, 0.1],
D3 = [–0.2, 0.2] � [0.3, 0.5], D4 = [0.4, 0.7] � [0.4, 0.7].
The three dimensional view of the plots of functions f x y
1
( , ) and f x y
2
( , )
are presented in Fig. 3. As was shown earlier (see for example [3, 5, 12]), the im-
age reconstruction of such objects from complete data gives a good enough re-
sults after 6-7 full iterations.
In this paper we present the numerical results of image reconstruction of
chosen functions with algebraic iterative algorithms ART-3 and chaotic algo-
rithm CHART-3 for two reconstruction systems (1 1� ) and (1 1� , 1 1� ). We com-
pare these results of reconstructions, and we investigate the influence of various
parameters of these algorithms such as a pixel initialization, relaxation parame-
ters, number of iterations and noise in the projection data on reconstruction
N. Gubareni, M. Pleszczynski
38 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
1
�1
�1
1
0.75
0.5
0.5
5
5
15
15
0.5
�0.5
�0.5
0.25
0
0
0
0
a b
1
1
10
10
20
20
2
3
4
Fig. 3. The original functions f x y
1
( , ) (a) and f x y
2
( , ) (b)
quality. The convergence of these algorithms was studied in dependence on dif-
ferent these parameters. The convergence characteristic plots are given in view
of plots for the maximum relative error:
"
1
100�
�max
~
max
%
i
i i
i
i
f f
f
,
and the mean absolute error
" � ��
1
n
f fi i
i
~
,
where fi is the value of a given modeling function in the center of the i-th pixel
and
~
f i is the value of the reconstructed function in the i-th pixel.
The reconstruction results of f x y
1
( , )with algorithms ART-3 and CHART-3
in the reconstruction scheme (1 1� ,1 1� ) for n = 20 � 20 pixels, m = 644 projections
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 39
1
0.75
0.5
0 0
0.0002
5 5
5 5
15 15
15 150.25
0.0001
0 0
a b
c d
10 10
10 10
20 20
20 20
1
9 10 11 12 13 14 15
2
3
ART-3
CHART-3
"
#
Iteration Iteration
0.0005
0.001
0.002
9 10 11 12 13 14 15
0.0015 ART-3
CHART-3
"
Fig. 4. The numerical simulation results of image reconstruction of f x y
1
( , ) with algorithms
ART-3 and CHART-3 for n = 20 � 20, m = 644 in the system (1 1� , 1 1� )
are presented in Fig. 4. The plots, which are presented in Fig. 4, a, b, illustrate the
dependence of the maximum relative error and the mean absolute error on num-
ber of iterations, correspondingly. The three dimensional view of the plot of the
reconstruction function f x y
1
( , )by algorithm ART-3 after 15 iterations is shown
in Fig. 4, c, and the plot of the mean absolute errors for this image reconstruction
is shown in Fig. 4, d.
The same function f x y
1
( , ) was also reconstructed in the system (1 1� ). The
numerical simulation results of this reconstruction with algorithms ART-3 and
CHART-3 for n = 20 � 20, m = 788 are shown in Fig. 5. The plots, which are pre-
sented in Fig. 5, a, b, illustrate the dependence of the maximum relative error and
the mean absolute error on the number of iterations, correspondingly. The three
dimensional view of the plot of the reconstruction function f x y
1
( , ) by algo-
rithm CHART-3 after 100 iterations is shown in Fig. 5, c, and the plot of the
mean absolute errors for this image reconstruction is shown in Fig. 5, d.
The analogous reconstructions were obtained for the function f x y
2
( , ). The
numerical simulation results of image reconstructions for f x y
2
( , ) with algo-
N. Gubareni, M. Pleszczynski
40 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
1
0.75
0.5
10
0 0
0.0005
5 5
5 5
15 15
15 150.25 0.00025
0.00075
0 0
a b
c d
10 10
10 10
20 20
20 20
20
20 40 60 80 100 120 140 20 40 60 80 100 120 140
30
40
50 ART-3
CHART-3
Iteration Iteration
0.01
0.001
0.02
0.03
ART-3
CHART-3
""
#
Fig. 5. The numerical simulation results of image reconstruction of f x y
1
( , ) with ART-3 and
CHART-3 for n = 20 � 20, m = 788 in the system (1 1� )
rithms ART-3 and CHART-3 in the system (1 1� ,1 1� ) for n = 20 � 20 pixels, m =
644 projections are given in Fig. 6. The plots, which are presented in Fig. 6, a, b,
illustrate the dependence of the maximum relative error and the mean absolute
error on number of iterations, correspondingly. The three dimensional view of
the plot of the reconstruction function f x y
2
( , ) by algorithm CHART-3 after 15
iterations is shown in Fig. 6, c, and the plot of the mean absolute errors for this
image reconstruction is shown in Fig. 6, d.
The same function f x y
2
( , ) was also reconstructed in the system (1 1� ). The
numerical simulation results of this reconstruction with algorithms ART-3 and
CHART-3 for n = 20 � 20, m = 788 are shown in Fig. 7. The plots, which are pre-
sented in Fig. 7, a, b, illustrate the dependence of the maximum relative error and
the mean absolute error on number of iterations, correspondingly. The three di-
mensional view of the plot of the reconstruction function f x y
2
( , ) by algorithm
CHART-3 after 25 iterations is shown in Fig. 7, c, and the plot of the mean ab-
solute errors for this image reconstruction is shown in Fig. 7, d.
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 41
1
0 0
3
5
0.0005
5
5
5
5
15
15
15
15
0.0015
0
a b
c d
10
10
10
10
20
20
20 20
2
9 10 11 12 13 14 15 9 10 11 12 13 14 15
4
6
ART-3
CHART-3
Iteration Iteration
0.002
0.001
0.004
0.008
0.006 ART-3
CHART-3
"
0
1
2
3
4
"
#
Fig. 6. The numerical simulation results of image reconstruction of f x y
2
( , ) with ART-3 and
CHART-3 for n = 20 � 20, m = 644 in the system (1 1� , 1 1� ).
All algorithms were implemented on IBM/PC (processor AMD Duron XP,
1600 MHz) by means of C++ and MATHEMATICA 5.1. One iteration by
means of Mathematica 5.1 was implemented approximately 0.5s for algorithm
ART-3 and CHART-3, and in C++ one iteration for both algorithms is imple-
mented in a real time.
Conclusion. The aim of this paper was an elaboration and comparison of
chaotic iterative algorithms for reconstruction of high-contrast objects from in-
complete projection data. We study the quality and convergence of these algo-
rithms. The experimental results show that convergent characteristics of algo-
rithm CHART-3 are considerably better by comparison with algorithm ART-3.
And the configuration (1 1� ,1 1� ) is considerably better by comparison with sys-
tem (1 1� ). For each considered system of reconstruction there exist the parame-
ters which allow to obtain an enough good quality of reconstruction after the
number of iterations but this number is considerably larger than for reconstruc-
tion with complete projection data. The number of iterations for achieving the
N. Gubareni, M. Pleszczynski
42 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 3
10
0 0
30
50
0.05
5
5
5
5
15
15
15
15
0.15
0
a b
c d
10
10
10 10
20 20
20
20
20
10 20 30 40 50 10 20 30 40 50
40
60 ART-3
CHART-3
Iteration Iteration
0.05
0.1
0.2
0.10
0.20
0.15
ART-3
CHART-3
"
0
1
2
3
4
"
#
Fig. 7. The numerical simulation results of image reconstruction of f x y
1
( , ) with ART-3 and
CHART-3 for n = 20 � 20, m = 788 in the system (1 1� )
stable reconstruction is approximately two times more for the second system by
comparison with the first one. And this number is approximately 10 times more
for the system (1 1� , 1 1� ) by comparison with the case of the complete data.
Ðîçãëÿíóòî çàäà÷ó êîìï’þòåðíî¿ òîìîãðàô³¿ ïî íåïîâíèì ïðîåêòèâíèì äàíèì ç âèêîðèñ-
òàííÿì õàîòè÷íèõ àëãîðèòì³â äëÿ äåÿêèõ ñïåö³àëüíèõ ñèñòåì â³äíîâëåííÿ. Íàâåäåíî
÷èñëîâ³ àëãîðèòìè â³äíîâëåííÿ òà ðåçóëüòàòè ÷èñëîâîãî ìîäåëþâàííÿ äëÿ îá’ºêò³â, ÿê³
ìîæóòü áóòè îïèñàí³ äèñêðåòíèìè ôóíêö³ÿìè.
1. Patella D. Introduction to ground surface self-potential tomography//Geophysical Prospect-
ing. — 1997. — Vol. 45. — P. 653—681.
2. Williams R. A., Atkinson K., Luke S.P. et al. Applications for Tomographic Technology in
Mining, Minerals and Food Engineering//Particle and Particle Systems Characterization.—
2004. — Vol. 12, N. 2. — P. 105—111.
3. Eggermont P. P. B., Herman G. T., Lent A. Iterative algorithms for large partitioned linear
systems with applications to image reconstruction//Ibed. — 1981. — Vol. 40. — P. 37—67.
4. Gubareni N. Computed Methods and Algorithms for Computer Tomography with limited
number of projection data. — Kiev : Naukova Dumka, 1997 (in Russian).
5. Herman G. T. Image Reconstruction from Projections. — N. Y. Academic Press, 1980.
6. Herman G. T. A relaxation method for reconstructing objects from noisy x-rays//Math. Pro-
gramming. — 1975. — Vol. 8. — P. 1—19.
7. Herman G. T. , Lent A., Rowland S. ART Mathematics and application (a report on the
mathematical foundations and on the applicability to real data of the Algebraic Reconstruc-
tion Techniques)// J. of Theoretica Biology. — 1973. — Vol. 43. — P. 1—32.
8. Chazan D., Miranker W. Chaotic relaxation// Ibed. — 1969. — Vol. 2. — P. 199—222.
9. Bru R., Elsner L., Neumann M. Models of Parallel Chaotic Iteration Methods//Linear Alge-
bra and its Appl. — 1988. — Vol. 103. — P. 175—192.
10. Baudet G. M. Asynchronous iterative methods for multiprocessors// J.Assoc. Comput.
Mach. — 1978. — Vol. 25. — P. 226—244.
11. El Tarazi M. Algorithms mixtes asychrones. Etude de convergence monotone// Numer.
Math. — 1984. —Vol. 44. — P. 363—369.
12. Gubareni N. Generalized Model of Asynchronous Iterations for Image Reconstruction//
Proc. of the third Int. Conf. on PPAM.— Kazimierz Dolny, Poland, 1999. — P. 266—275.
Ïîñòóïèëà 08.10.07
Chaotic Iterative Algorithms for Image Reconstruction from Incomplete Projection Data
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 3 43
|