Block-Parallel Chaotic Algorithms for Image Reconstruction
The paper is devoted to the elaboration and implementation of block-parallel asynchronous algorithms for computer tomography. The numerical reconstruction algorithms and numerical simulation results for a number of modeling objects and some particular systems of reconstruction are presented. Разрабо...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/101514 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Block-Parallel Chaotic Algorithms for Image Reconstruction / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2009. — Т. 31, № 5. — С. 41-54. — Бібліогр.: 14 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859740875593089024 |
|---|---|
| author | Gubareni, N. Pleszczynski, M. |
| author_facet | Gubareni, N. Pleszczynski, M. |
| citation_txt | Block-Parallel Chaotic Algorithms for Image Reconstruction / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2009. — Т. 31, № 5. — С. 41-54. — Бібліогр.: 14 назв. — англ. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | The paper is devoted to the elaboration and implementation of block-parallel asynchronous algorithms for computer tomography. The numerical reconstruction algorithms and numerical simulation results for a number of modeling objects and some particular systems of reconstruction are presented.
Разработаны и выполнены блочно-параллельные алгоритмы компьютерной томографии.Представлены численные алгоритмы восстановления и результаты численного моделирования для ряда тестовых задач и некоторых частных случаев систем реконструкции сбора данных.
Розроблено та виконано блочно-паралельні алгоритми комп’ютерної томографії. Наведено чисельні алгоритми відновлення та результати чисельного моделювання для тестових задач і деяких окремих випадків систем реконструкції збирання даних.
|
| first_indexed | 2025-12-01T18:02:39Z |
| format | Article |
| fulltext |
N. Gubareni
Politechnika Cz stochowska
(ul. Dabrowskiego 69, 42-200 Cz stochowa, Poland,
E-mail: gubareni@zim.pcz.pl),
M. Pleszczynski
Politechnika Slaska
(ul. Kaszubska, 23, 44-101 Gliwice, Poland,
E-mail: dm101live@interia.pl)
Block-Parallel Chaotic
Algorithms for Image Reconstruction
(Recommended by Prof. E. Dshalalow)
The paper is devoted to the elaboration and implementation of block-parallel asynchronous algo-
rithms for computer tomography. The numerical reconstruction algorithms and numerical simu-
lation results for a number of modeling objects and some particular systems of reconstruction are
presented.
Ðàçðàáîòàíû è âûïîëíåíû áëî÷íî-ïàðàëëåëüíûå àëãîðèòìû êîìïüþòåðíîé òîìîãðàôèè.
Ïðåäñòàâëåíû ÷èñëåííûå àëãîðèòìû âîññòàíîâëåíèÿ è ðåçóëüòàòû ÷èñëåííîãî ìîäåëè-
ðîâàíèÿ äëÿ ðÿäà òåñòîâûõ çàäà÷ è íåêîòîðûõ ÷àñòíûõ ñëó÷àåâ ñèñòåì ðåêîíñòðóêöèè
ñáîðà äàííûõ.
K e y w o r d s: computer tomography, incomplete projection data, asynchronous algorithms,
computer reconstruction, block-parallel algorithms.
Introduction. Some parallel implementations of iterative algebraic algorithms
for image reconstruction for some particular reconstruction schemes which arise
in some problems of engineering geophysics and mineral industry are consid-
ered in the paper. In such computing structure each elementary processor exe-
cutes its independent calculations by means of the same simple algorithms con-
nected with a set of corresponding equations.
It is assumed that each processor executes its calculations with its own
pace and the communication channels are allowed to deliver messages out of
order. In this case this results in the chaotic character of interactions in such
computer parallel structure (CPS) which corresponds to some chaotic iterative
algorithm. This algorithm realized on such CPS is based on the asynchronous
methods [1—3].
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 41
������� ����
�
��
�������
‘
‘
�
In order to reduce the computation time and memory space of the computer
other algebraic algorithms were proposed which allow their parallelization and
may be realized on the fast massively parallel computing systems (MPCS) con-
sisting of elementary processors and a central processor [4—6].
We represent in this paper some kinds of the block-parallel asynchronous
algorithms for image reconstruction which are a certain generalization of paral-
lel chaotic iteration methods considered by Bru, Elsner and Neumann [7].
Numerical simulation of the solving the problems of image reconstruction from
incomplete projection data for some modeling objects, comparing the errors evalua-
tions and rate of convergence of these algorithms are presented. It is shown that for
some choice of parameters one can obtain a good quality of reconstruction with
these algorithms, and that these algorithms have much higher rate of convergence
in comparison with the corresponding synchronous algorithms.
Block-parallel iterative algorithms for image reconstruction. Certain
parallel and block-iterative algorithms are used in the paper, some of which
were considered in papers [8—10], for solving the system of linear equations
A x p� � , (1)
where A R� �( )
,aij
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 pro-
jection data; and system of linear inequalities
p e A x p e� � � � + , (2)
where e �{ , ,..., }� � �
1 2 m is a non-negative vector.
Denote by
P x x
a x a x
a
ai
i
i i i i
i
i
ip p
( )
(( , ) ) ( ( , ))
� �
� � � � �
� �
2
, (3)
where
s
s s
�
�
�
, ;
,
if
otherwise
0
0
and
P I Pi i
�
� �� � ( )1 , (4)
where a
i
is i-th row of a matrix A, � is a relaxation parameter.
A l g o r i t h m 1 (PART).
1. x R
( )0
�
n
is an arbitrary vector.
2. The k + 1-th iteration is calculated in accordance with such a scheme:
y k i
i
kk, ( )
�P x
�
( , , ..., )i m�1 2 , (5)
N. Gubareni, M. Pleszczynski
42 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
x C B y
( ) ,k
i
k k i
i
m
�
� �
1
1
,
(6)
where P
i
k� are operators defined by (3) and (4),�k are relaxation parameters, C
is a constrained operator and B i
k
are matrices of dimension n n� with real
nonnegative elements and
B Ei
k
i
m
=
�
�
1
, B i
k
i
m
�
�
� 1
1
,
for all k N� , where E is the unit matrix of dimension n n� .
The parallel implementation of this algorithm may be organized as follows:
begin
x
(0)
=initial
for k = 0, 1, ... until convergence
do
for i-th processor, i = 1 to m
do
y i
i
kk
�P x
� ( )
enddo
x C B y
( )k
i
k i
i
m
�
� �
1
1
enddo
end
Let B i
k
jj
i
j
n
�
�
( )�
1
be a diagonal matrix with elements 0 1� �� jj
i
. If � �jj
i
i�
for each j J� , i I� , C = I, then there results the Cimmino algorithm [11].
The sufficient conditions of convergence of algorithm 1 are given by the fol-
lowing theorem.
Theorem 1. If system (2) is consistent and 0 <�k < 2, then the sequence
{ }
( )
x
k
k�
�
1
defined by algorithm 1 converges to some solution of the system (2).
For many practical applications x
0, the elements of a matrix A = (aij) are
nonnegative real numbers and pi > 0 for all i I� . In this case the following paral-
lel multiplicative algorithm is proposed for solving a system of linear inequali-
ties (2).
A l g o r i t h m 2 (MARTP).
1. x R
( )0
�
n
and x
(0)
> 0.
2. The k +1-th iteration is calculated in accordance with such a scheme:
x x y
j
k
j
k
j
k i
i
m
( ) ( ) ,
:
�
� �
1
1
,
(7)
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 43
where
y
p
j
k i i
i k
aij
k
ij
,
( )
:
( , )
�
�
�
�
�
�
�
a x
�
(8)
(i = 1, 2, ..., m; j = 1, 2, ..., n), � ij
k
are positive real numbers such that
0 1
1
� �
�
� a
ij ij
k
i
m
�
for every j, k.
The parallel realization of this algorithm may be given in such a form:
begin
x
j
( )0
= initial
for k = 0,1, ... until convergence
do
for i-th processor, i = 1 to m
do
for j-th point, j = 1 to n
do
y
p
j
k i i
i k
aij
k
ij
,
( )
:
( , )
�
�
�
�
�
�
�
a x
�
( , , ..., )i m�1 2
enddo
enddo
x x y
j
k
j
k
j
k i
i
m
( ) ( ) ,
:
�
� �
1
1
enddo
end
The similar algorithms for image reconstruction were considered in works
[11—12].
The sufficient conditions of convergence of the algorithm 2 are given by the
following theorem.
Theorem 2. Let system (2) be consistent and have if only one positive solu-
tion. If aij
0, a
i
� 0, pi > 0,
� �
ij
k
i
� 0, 0 1
1
� �
�
�a
ij ij
k
i
m
�
for all i, j, k, x
( )
( )
0
�
R n
, the sequence { }
( )
x
k
k�
�
1
defined by the algorithm 2
converges to some solution of the system (2).
N. Gubareni, M. Pleszczynski
44 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
The proofs of theorems 1 and 2 are presented in [9].
These algorithms may be realized on parallel computing structures consist-
ing of m elementary processors and one central processor. On each (k + 1)-th
step of iteration every i-th elementary processor computes the coordinates of
vector y
k,i
in accordance with formula (5) or (8) and then the central processor
computes the (k + 1)-th iteration of the image vector x in accordance with for-
mula (6) or (7).
The main defect of parallel algorithms considered above is their practical re-
alization on parallel computational structures because it needs a lot of local pro-
cessors in such MPCS. In order to reduce the number of required local proces-
sors we consider a block-iterative additive and multiplicative algorithms.
For this purpose decompose the matrix A and the projection vector p into
M subsets in accordance with decomposition {1, 2, ..., m} = H H H M1 2
� � �... ,
where
H m m mt t t t�
� �
{ , , ..., }
1 1
1 2 , 0 = m 0 < m1 < ... < mM = m . (9)
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:
x C B P y
( )
( )
k
i
k
i
i
i H
m
k
t k
�
� �
1 �
,
where t (k) = k (mod M) +1, P
i
k� are operators defined by (3) and (4), �k are re-
laxation parameters, C is a constrained operator and B i
k
are matrices of dimen-
sion n n� with real nonnegative elements and
B Ei
k
i H
m
=
t k�
�
( )
, B i
k
i H
m
t k
�
�
� 1
( )
,
(10)
ffor all k N� , where E is the unit matrix of the dimension n n� . The parallel im-
plementation of this algorithm can be described as follows:
y k i
i
kk, ( )
�P x
� i H t k�
( )
, x C B y
( ) ,
( )
k
i
k k i
i H
m
t k
�
� �
1
,
or may be given by such a form:
begin
x
(0)
= initial
for k = 0, 1, ... until convergence
do
t(k) = k(mod M) +1
do
for i-th processor, i H t�
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 45
do
y k i
i
kk, ( )
�P x
�
enddo
x C B y
( )
:
k
i
k i
i H
m
t
�
� �
1
enddo
end
The conditions of convergence of algorithm 3 may be given by the follow-
ing theorem.
Theorem 3. If system (2) is consistent and ���k � 2 , then for every point
x R
( )0
�
n
the sequence{ }
( )
x
k
k�
�
1
defined by algorithm 3 converges to some so-
lution of the system (2).
The block-iterative algorithms represent examples of sequential-parallel al-
gorithms. They may be considered as an intermediate version between sequen-
tial algorithms and full parallel ones. In each step of iterative process the
block-iterative algorithm uses simultaneously information about all equations
concerning the given block.
Block-iterative algorithms may be also considered in the case of multiplica-
tive algorithms. In this case the following algorithm is obtained.
A l g o r i t h m 4 (BMART).
1. x R
( )0
�
n
and x
(0)
> 0.
2. The k + 1-th iteration is calculated in accordance with such a scheme:
x x
p
j
k
j
k i
i k
a
i H
ij
k
ij
t k
( ) ( )
:
)
( )
�
�
�
�
�
�
�
�
�
�
�
1
( ,a x
�
,
where � ij
k
are positive real numbers such that
�� �aij
i H
ij
k
t k�
� �
( )
1
for every j, k ; Ht(k) are defined in accordance with (9), and t (k) is almost cycle
control sequence. If � �ij
k
i
� for all k, j and0 1� �aij ,
i H
i
t k�
� �
( )
� 1, then as a re-
sult the block-iterative multiplicative algorithm proposed in [6] is obtained.
The conditions of convergence are the same as for the algorithm 2.
Block-parallel asynchronous algorithms for computer tomography. In
this section the generalized model ofa asynchronous iterations, considered in
[13], is applied for implementation of block-parallel algorithms on nonsynchro-
nous computer structure. We shall use the basic notions of the theory of asyn-
chronous iterations which were introduced by Chazan and Miranker in [3] and
Baudet in [1] (see, also [14]).
N. Gubareni, M. Pleszczynski
46 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
Applying the generalized model of asynchronous iterations for implementa-
tion of algorithm BPART on nonsynchronous computer structure results in ob-
taining the following algorithm, where the numbers of operators are chosen in
the chaotic way:
A l g o r i t h m 5.
1. x R
( )0
�
n
is an arbitrary vector.
2. The k + 1-th iteration is calculated in accordance with such a scheme:
x C B P x
k i
i
k
i
k
i H
k
i
t k
�
� �
1, ( ( ))
( )
� �
,
where P
i
k� are operators defined by (3) and (4), �k are relaxation parameters, C
is a constrained operator, t (k) = Ik, I I k k�
�
�
{ }
0
is a sequence of chaotic sets such
that I mk { , , ..., }1 2 and B i
k
are matrices of dimension n n� with real non-
negative elements which satisfy the conditions of (10), J ki
i
k�
�
�
{ ( )}�
1
are se-
quences of delays.
The convergence of this algorithm is given by the following theorem.
Theorem 4. Let system (1) be consistent, I I k k�
�
�
{ }
0
be a regular sequence
of chaotic sets I mk { , ,..., }1 2 with the number of regularity T, J ki
i
k�
�
�
{ ( )}�
1
be sequences with limited delays and � �j
i
i
k k( ) ( )� , and let the number of de-
lays be equal to T. Then for every point x R
( )0
�
n
the sequence{ }
( )
x
k
k�
�
1
defined
by algorithm 5 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 [9]. In this paper the con-
strained operator C is given in the form C = C1 C2, where
( [ ])
, ;
, ;
, ;
C
a x a
x a x b
b x b
i
i
i i
i
1
x �
�
� �
�
�
�
!
!
if
if
if
( [ ])
, ;
,
C
p a
x
j
i ij
j
2
0 0 0
x �
� ��
�
if and
otherwise.
Computer simulation and experimental results. In this section we pres-
ent some numerical results of applying the special cases of block-parallel algo-
rithm BPART-3 and chaotic block-parallel algorithm CHBP-3 considered in the
previous sections for the reconstruction of high contrast objects from incom-
plete projection data in the case when they are not available at each angle of view
and they are a few-number limited. The influence of various parameters of these
algorithms such as a pixel initialization, relaxation parameters, the number of it-
erations and noise in the projection data on reconstruction quality and conver-
gence of these algorithm are also studied there.
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 47
In dependence on obtaining the system of projections there are many image
reconstruction schemes. In some practical problems, in engineering for exam-
ple, it is impossible to get projections from all directions because of the existing
of 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.
In this paper the goodness of the applied algorithm of reconstruction was
tested for different kinds of geometric figures and reconstruction schemes.
The discrete functions with high contrast were chosen to illustrate the im-
plementation of these algorithms working with incomplete data. The results pre-
sented in this paper are given for the following function:
f x y
x y D E
x y D E
x y D( , )
, ( , ) ;
, ( , ) ;
, ( , )�
�
�
�
1
2
3
1
2
2
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 fol-
lowing 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 plot of this function is given in Fig. 1. The results for image reconstruc-
tions are represented for only two different schemes, which are described in [14]
N. Gubareni, M. Pleszczynski
48 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
Fig. 1. The original function f (x, y)
and were called system (1 � 1) and (1 � 1, 1 � 1). Both of these systems are
shown in Fig. 2.
In the first scheme of obtaining the projection data, which we shall call the
system (1 � 1), we have an access to the research object from only two opposite
sides. This situation often arises in engineering geophysics. In this case the
sources of rays are located only on one side and the detectors are located on the
opposite side of the research part of a coal bed. This scheme of information ob-
taining is shown in Fig. 2.
The convergence characteristics of image reconstruction are given in a view
of plots for the following measures of errors:
the absolute error: " ( , ) ( , )
~
( , )x y f x y f x y� � ;
the maximal absolute error: # � �max
~
i
if f ;
the maximal relative error:
"
1
100�
�max
~
max
%
i
i i
i
i
f f
f
;
the mean absolute error:
"
2
1
� ��
n
f fi i
i
~
,
where fi is the value of the 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. As the result of
computer simulation it was assumed, that n is the number of pixels, i.e. the
number of variables; m is the number of rays, i.e. the number of equations; M is
the number of blocks; iter is the number of full iterations.
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 49
1 1
12
2
3
3
4
4
4
Fig. 2. The schemes of obtaining projection data: system (1 � 1) and system (1 � 1, 1 � 1): 1 —
sources of rays; 2 — research object; 3 — rays; 4 — detectors
In all experiments it was also assumed that M is equal to the number of de-
tectors; the sequence of chaotic sets Ik has the form {$ k }, where $ k is an integer
random variable in the interval [1, m] with uniform distribution; the reconstruc-
tion domain E x y x y� � � �{( , ): , }1 1 was divided into n = 20 � 20 pixels; the
number of projections m in the system (1 � 1) is equal to 788, and in the system
(1�%&'%�1) the number m = 644.
The results of image reconstructions for f x y( , ) with block-parallel algo-
rithm BPART-3, and chaotic block-parallel algorithm CHBP-3 in the system
(1�1, 1�1) for the same parameters are given in Fig. 3.
The plots, which are presented in Fig. 4, illustrate the dependence of the
maximum relative error and the mean absolute error on the number of iterations
of image reconstruction of f x y( , ) with algorithms BPART-3 and CHBP-3 in
the system (1�1, 1�1). Table 1 shows the dependence of the maximum absolute
error # on the number of iterations for algorithms BPART-3 and CHBP-3 in the
system (1�1, 1�1).
The results of reconstruction of the function f x y( , ) with algorithm BPART-3
and CHBP-3 in the system (1�1, 1�1) is shown in Fig. 5.
N. Gubareni, M. Pleszczynski
50 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
15
15
5
5
10
10
0
1
2
3
4
20
20
15
15
5
5
10
10
0
1
2
3
4
20
20
15
15
5
5
10
10
0
0.002
0.004
0.006
0.008
20
20
15
15
5
5
10
10
0
0.001
0.002
0.003
0.004
20
20
a
b
Fig. 3. The image reconstruction and the absolute error for f (x, y) obtained with algorithm
BPART-3 (a) and algorithm CHBP-3 (b) for n = 20 � 20, m = 644, M = 36, iter = 75 in the sys-
tem (1 � 1, 1 � 1)
The plots presented in Fig. 6 illustrate the dependence of the maximum rela-
tive error and the mean absolute error on the number of iterations of image re-
construction of f x y( , ) with algorithms BPART-3 and CHBP-3 in the sys-
tem (1 � 1).
Table 2 shows the dependence of the maximum absolute error # on the
number of iterations for algorithms BPART-3 and CHBP-3 in the system (1 � 1).
All experimental results in the case of reconstruction of objects from limited
projection data show that the errors of reconstruction with algorithms BPART-3
and CHBP-3 are constantly reduced with increasing the number of iterations.
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 51
"
1
30
20
10
0
10 20 30 40 50 60
BPART-3
CHBP-3
*
*
*
* * * * * * * *
"
2
0.10
0.08
0.06
0.04
0.02
0
10 20 30 40 50 60 iter
BPART-3
CHBP-3
*
*
*
* * * * * * * *
Fig. 4. Dependence of the mean absolute error "2 and the maximum relative error "1 on the num-
ber of iterations for image reconstruction of f x y( , ) with algorithm BPART-3 and CHBP-3 in
the system (1 � 1, 1 � 1)
Iter BPART-3 CHBP-3
10 0.4640 0.2112
20 0.1973 0.0478
40 0.0293 0.0054
50 0.0113 0.0018
100 0.0001 0.000001
Table 1
Iter BPART-3 CHBP-3
100 0.1902 0.2668
200 0.0883 0.1345
500 0.0146 0.0168
1000 0.0007 0.0006
2000 2.109 �10
–6
7.872 � 10
–7
Table 2
The obtained results also show that chaotic algorithm CHBP-3 gives better re-
sults as compared with block-parallel algorithm BPART-3.
Table 3 shows the number of iterations required for obtaining the image re-
construction with a given maximum relative error "
2
for the considered algo-
rithms BPART-3, CHBP-3 and for the considered systems.
N. Gubareni, M. Pleszczynski
52 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
15
15
5
5
10
10
0
1
3
4
20
20
15
15
5
5
10
10
0
1
2
3
4
20
20
15
15
5
5
10
10
0
0.02
0.04
0.06
0.08
20
20
15
15
5
5
10
10
0
0.02
0.04 20
20
a
b
Fig. 5. The image reconstruction and the absolute error for f x y( , )obtained with BPART-3 (a)
and algorithm CHBP-3 (b) for n = 20 � 20, m = 788, M = 28 in the system (1 � 1): a — iter = 600;
b – iter = 200
(1�1, 1�1) (1�1)
"
2
, %
BPART-3 CHBP-3 BPART-3 CHBP-3
13 24 74 95 <10
23 30 178 148 <5
47 46 953 271 <1
60 53 271 340 <0,5
Table 3
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 1s for algorithm
BPART-3 and CHBP-3, and in C++ one iteration for both algorithms is imple-
mented in a real time.
Conclusion. New chaotic iterative algorithms for image reconstruction are
presented in the paper. These algorithms can be realized on a parallel computing
structure consisting of elementary processors and some central processor, all of
which are connected with shared memory. The quality and convergence of these
algorithms were studied by computing simulation on sequential computer. The
experimental results show that convergent characteristics of block-parallel cha-
otic algorithm CHBP-3 are better as compared with block-parallel algorithm
BPART-3. Taking into account that the time of implementation of block-parallel
computer algorithm on parallel computer is approximately M times less (where
M is the number of processors) in comparison with a sequential computer, it fol-
lows from results of computer simulation that the time characteristics of block-
parallel algorithms are better as compared with sequential ART-3. It also fol-
lows from our experiments that the configuration (1�1, 1�1) is considerably
better as compared with the scheme (1�1). And for each considered scheme of
reconstruction there exist the parameters which allow to obtain a rather good
quality of reconstruction after some number of iterations, but this number is
considerably larger than that for reconstruction with complete projection data.
The number of iterations for achieving the stable reconstruction is approxi-
mately two times more for the second scheme in comparison with the first one.
And this number is approximately 10 times more for the scheme (1�1, 1�1) in
comparison with the case of complete data.
Block-Parallel Chaotic Algorithms for Image Reconstruction
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2009. Ò. 31. ¹ 5 53
"
1
30
20
10
0
100 200 300 400 500
BPART-3
CHBP-3
*
*
*
*
*
**
* * * * * * * * * * * * *
"
2
0.04
0.03
0.02
0.01
0
100 200 300 400 500 iter
BPART-3
CHBP-3*
*
*
*
* * * * ** * * * * * * * * *
Fig. 6. Dependence of the mean absolute error "2 and the maximum relative error "1 on the num-
ber of iterations for image reconstruction of f x y( , ) with algorithm BPART-3 and CHBP-3 in
the system (1 � 1)
Ðîçðîáëåíî òà âèêîíàíî áëî÷íî-ïàðàëåëüí³ àëãîðèòìè êîìï’þòåðíî¿ òîìîãðàô³¿. Íàâåäå-
íî ÷èñåëüí³ àëãîðèòìè â³äíîâëåííÿ òà ðåçóëüòàòè ÷èñåëüíîãî ìîäåëþâàííÿ äëÿ òåñòîâèõ
çàäà÷ ³ äåÿêèõ îêðåìèõ âèïàäê³â ñèñòåì ðåêîíñòðóêö³¿ çáèðàííÿ äàíèõ.
1. Baudet G. M. Asynchronous Iterative Methods for Multiprocessors // J. Assoc. Comput.
Mach. — 1978. — 25. — P. 226—244.
2. Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation:Numerical Methods. —
Englewood Cliffs, NJ : Prentice-Hall, 1989.
3. Chazan D., Miranker W. Chaotic Relaxation//Linear Alg. its Appl. — 1969. — 2. — P. 199—
222.
4. Censor Y. Parallel Application of Block-iterative Methods in Medical Imaging and Ra-
diation Therapy // Math. Programming. — 1988. — 42. — P. 307—325.
5. De Pierro A. R., Iusem A. N. A Simultaneous Projections Method for Linear Inequalities //
Linear Algebra and Its Appl. — 1985. — 64. — P. 243—253.
6. De Pierro A. R., Iusem A. N. A Parallel Projection Method of Finding a Common Point of a
Family of Convex Sets // Pesquisa Oper. — 1985. — 5. — P. 1—20.
7. Bru R., Elsner L., Neumann M. Models of Parallel Chaotic Iteration Methods // Linear Alg.
Its Appl. — 1988. — 103. — P. 175—192.
8. 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.
9. Gubareni N. Computer Methods and Algorithms for Computer Tomography with Limited
Number of Projection Data. — Kiev : Naukova Dumka, 1997 (in Russian).
10. Gubareni N., Katkov A. Simulation of Parallel Algorithms for Computer Tomography //
Proc. of the 12-th Europ. Simulation Multiconf. — Manchester, United Kingdom, June
16-19. — 1998. — P. 324—328.
11. Censor Y. Parallel Application of Block-iterative Methods in Medical Imaging and Radia-
tion Therapy // Math. Programming. — 1974. — 42. — P. 307—325.
12. De Pierro, A. R. Multiplicative Iterative Methods in Computer Tomography // Lecture
Notes in Mathematics. — 1990. — 1497. — P. 133—140.
13. Gubareni N., Katkov A., Szopa J. Parallel Asynchronous Team Algorithm for Image Recon-
struction // Proc. 15-th IMACS World Congress on Scientific Computation, Modelling and
Applied Mathematics. — Berlin : Computational Mathematics (ed. by A.Sydow). — 1997,
Vol. 1. — P. 553—558.
14. Gubareni N., Pleszczynski M. Chaotic Iterative Algorithms for Image Reconstruction from
Incomplete Projection Data // Electronic Modeling. — 2008. — 30, N 3. — P. 29—43.
Ïîñòóïèëà 20.05.09
N. Gubareni, M. Pleszczynski
54 ISSN 0204–3572. Electronic Modeling. 2009. V. 31. ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-101514 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | English |
| last_indexed | 2025-12-01T18:02:39Z |
| publishDate | 2009 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Gubareni, N. Pleszczynski, M. 2016-06-04T10:15:20Z 2016-06-04T10:15:20Z 2009 Block-Parallel Chaotic Algorithms for Image Reconstruction / N. Gubareni, M. Pleszczynski // Электронное моделирование. — 2009. — Т. 31, № 5. — С. 41-54. — Бібліогр.: 14 назв. — англ. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101514 The paper is devoted to the elaboration and implementation of block-parallel asynchronous algorithms for computer tomography. The numerical reconstruction algorithms and numerical simulation results for a number of modeling objects and some particular systems of reconstruction are presented. Разработаны и выполнены блочно-параллельные алгоритмы компьютерной томографии.Представлены численные алгоритмы восстановления и результаты численного моделирования для ряда тестовых задач и некоторых частных случаев систем реконструкции сбора данных. Розроблено та виконано блочно-паралельні алгоритми комп’ютерної томографії. Наведено чисельні алгоритми відновлення та результати чисельного моделювання для тестових задач і деяких окремих випадків систем реконструкції збирання даних. en Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Информационные технологии Block-Parallel Chaotic Algorithms for Image Reconstruction Article published earlier |
| spellingShingle | Block-Parallel Chaotic Algorithms for Image Reconstruction Gubareni, N. Pleszczynski, M. Информационные технологии |
| title | Block-Parallel Chaotic Algorithms for Image Reconstruction |
| title_full | Block-Parallel Chaotic Algorithms for Image Reconstruction |
| title_fullStr | Block-Parallel Chaotic Algorithms for Image Reconstruction |
| title_full_unstemmed | Block-Parallel Chaotic Algorithms for Image Reconstruction |
| title_short | Block-Parallel Chaotic Algorithms for Image Reconstruction |
| title_sort | block-parallel chaotic algorithms for image reconstruction |
| topic | Информационные технологии |
| topic_facet | Информационные технологии |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/101514 |
| work_keys_str_mv | AT gubarenin blockparallelchaoticalgorithmsforimagereconstruction AT pleszczynskim blockparallelchaoticalgorithmsforimagereconstruction |