Abstract

In computerized tomography, line integrals of the absorptivity are used to reconstruct the object. In some applications only the locations, sizes, and shapes of internal opacities or near-opacities are needed. For these applications it is unnecessary to reconstruct an image by convolution backprojection [O(N3)] or by direct Fourier methods [O(N2 log N)]. We propose an algorithm suitable for this problem that requires only O(N) operations (N is of the order of the number of views). We analyze and demonstrate the high performance of the algorithm but show that the performance of the algorithm depends strongly on an appropriate choice of system parameters. These parameters, the number of views Nθ, and the detector spacing Δs are shown to be linked, and a choice of Δs strongly constrains the choice of Nθ. We show how an optimum Nθ can be determined for a fixed Δs, including practical values of Δs. A series of experiments that reinforce the theory is simulated on a computer.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chaps. 8 and 10.
  2. H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
    [CrossRef]
  3. B. P. Medoff, “Image reconstruction from limited data,” doctoral dissertation (Stanford University, Stanford, Calif., 1983).
  4. B. P. Medoff, “Image reconstruction from limited data: theory and application in computer tomography,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 7.
  5. R. M. Lewitt, R. H. T. Bates, “Image reconstruction from projections: IV. Projection completion methods (computational examples),” Optik 50, 269–278 (1978).
  6. I. Sezan, H. Stark, “Tomographic image reconstruction from incomplete view data by convex projections and direct Fourier inversion,” IEEE Trans. Med. Imag. TMI-3, 91–98 (1984).
    [CrossRef]
  7. K. C. Tam, V. Pérez-Méndez, “Tomographic imaging with limited-angle input,” J. Opt. Soc. Am. 71, 582–592 (1981).
    [CrossRef]
  8. T. Inouye, “Image reconstruction with limited view angle projections,” in Proceedings of the International Workshop on Physics and Engineering in Medical Imaging (Institute of Electrical and Electronics Engineers, New York, 1982), pp. 165–168.
    [CrossRef]
  9. K. Hanson, “Bayesian and related methods in image reconstruction from incomplete data,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 3.
  10. D. C. Youla, H. Webb, “Image restoration by the method of convex projections. Part I. Theory,” IEEE Trans. Med. Imag. TMI-1, 81–94 (1982).
    [CrossRef]
  11. G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chap. 1.
  12. There are other algorithms for shape estimation. For a partial list see S. R. Deans, The Radon Transform and Some of Its Applications (Wiley, New York, 1983), pp. 106–107.

1984 (1)

I. Sezan, H. Stark, “Tomographic image reconstruction from incomplete view data by convex projections and direct Fourier inversion,” IEEE Trans. Med. Imag. TMI-3, 91–98 (1984).
[CrossRef]

1982 (1)

D. C. Youla, H. Webb, “Image restoration by the method of convex projections. Part I. Theory,” IEEE Trans. Med. Imag. TMI-1, 81–94 (1982).
[CrossRef]

1981 (2)

K. C. Tam, V. Pérez-Méndez, “Tomographic imaging with limited-angle input,” J. Opt. Soc. Am. 71, 582–592 (1981).
[CrossRef]

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

1978 (1)

R. M. Lewitt, R. H. T. Bates, “Image reconstruction from projections: IV. Projection completion methods (computational examples),” Optik 50, 269–278 (1978).

Bates, R. H. T.

R. M. Lewitt, R. H. T. Bates, “Image reconstruction from projections: IV. Projection completion methods (computational examples),” Optik 50, 269–278 (1978).

Deans, S. R.

There are other algorithms for shape estimation. For a partial list see S. R. Deans, The Radon Transform and Some of Its Applications (Wiley, New York, 1983), pp. 106–107.

Hanson, K.

K. Hanson, “Bayesian and related methods in image reconstruction from incomplete data,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 3.

Herman, G. T.

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chap. 1.

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chaps. 8 and 10.

Hingorani, R.

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

Inouye, T.

T. Inouye, “Image reconstruction with limited view angle projections,” in Proceedings of the International Workshop on Physics and Engineering in Medical Imaging (Institute of Electrical and Electronics Engineers, New York, 1982), pp. 165–168.
[CrossRef]

Lewitt, R. M.

R. M. Lewitt, R. H. T. Bates, “Image reconstruction from projections: IV. Projection completion methods (computational examples),” Optik 50, 269–278 (1978).

Medoff, B. P.

B. P. Medoff, “Image reconstruction from limited data,” doctoral dissertation (Stanford University, Stanford, Calif., 1983).

B. P. Medoff, “Image reconstruction from limited data: theory and application in computer tomography,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 7.

Paul, I.

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

Pérez-Méndez, V.

Sezan, I.

I. Sezan, H. Stark, “Tomographic image reconstruction from incomplete view data by convex projections and direct Fourier inversion,” IEEE Trans. Med. Imag. TMI-3, 91–98 (1984).
[CrossRef]

Stark, H.

I. Sezan, H. Stark, “Tomographic image reconstruction from incomplete view data by convex projections and direct Fourier inversion,” IEEE Trans. Med. Imag. TMI-3, 91–98 (1984).
[CrossRef]

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

Tam, K. C.

Webb, H.

D. C. Youla, H. Webb, “Image restoration by the method of convex projections. Part I. Theory,” IEEE Trans. Med. Imag. TMI-1, 81–94 (1982).
[CrossRef]

Woods, J. W.

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

Youla, D. C.

D. C. Youla, H. Webb, “Image restoration by the method of convex projections. Part I. Theory,” IEEE Trans. Med. Imag. TMI-1, 81–94 (1982).
[CrossRef]

IEEE Trans. Acoust. Speech Signal Process. (1)

H. Stark, J. W. Woods, I. Paul, R. Hingorani, “Direct Fourier reconstruction in computer tomography,” IEEE Trans. Acoust. Speech Signal Process. ASSP-29, 237–245 (1981).
[CrossRef]

IEEE Trans. Med. Imag. (2)

I. Sezan, H. Stark, “Tomographic image reconstruction from incomplete view data by convex projections and direct Fourier inversion,” IEEE Trans. Med. Imag. TMI-3, 91–98 (1984).
[CrossRef]

D. C. Youla, H. Webb, “Image restoration by the method of convex projections. Part I. Theory,” IEEE Trans. Med. Imag. TMI-1, 81–94 (1982).
[CrossRef]

J. Opt. Soc. Am. (1)

Optik (1)

R. M. Lewitt, R. H. T. Bates, “Image reconstruction from projections: IV. Projection completion methods (computational examples),” Optik 50, 269–278 (1978).

Other (7)

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chaps. 8 and 10.

B. P. Medoff, “Image reconstruction from limited data,” doctoral dissertation (Stanford University, Stanford, Calif., 1983).

B. P. Medoff, “Image reconstruction from limited data: theory and application in computer tomography,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 7.

G. T. Herman, Image Reconstruction from Projections—The Fundamentals of Computerized Tomography (Academic, New York, 1980), Chap. 1.

There are other algorithms for shape estimation. For a partial list see S. R. Deans, The Radon Transform and Some of Its Applications (Wiley, New York, 1983), pp. 106–107.

T. Inouye, “Image reconstruction with limited view angle projections,” in Proceedings of the International Workshop on Physics and Engineering in Medical Imaging (Institute of Electrical and Electronics Engineers, New York, 1982), pp. 165–168.
[CrossRef]

K. Hanson, “Bayesian and related methods in image reconstruction from incomplete data,” in Image Recovery: Theory and Applications, H. Stark, ed. (Academic, Orlando, Fla., 1987), Chap. 3.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (14)

Fig. 1
Fig. 1

Null regions in projection space that are due to opacity.

Fig. 2
Fig. 2

Null stripe in the shadow p(s, θ) resulting from a circular opacity contained within an elliptical object.

Fig. 3
Fig. 3

(a) Estimation of the convex hull H of the object O from projections, (b) A convex hull cannot be distinguished between the two objects shown.

Fig. 4
Fig. 4

Block diagram of shape- and area-estimation algorithm.

Fig. 5
Fig. 5

Partitioning of the N1-sided polygon representing the convex hull of the opacity into N1 − 2 triangles in order to compute the area by the cross-product method.

Fig. 6
Fig. 6

Shading: for a fixed row at a given x, all pixels in that row are assigned the value of 0 or 1. The assignment is made depending on which side of the polygonal chord the pixel is. The process is repeated for all x ∈ [xmin, xmax]. The three regions R1, R2, and R3 in this example correspond to pixel assignments of 0, 1, and 0, respectively.

Fig. 7
Fig. 7

Calculation of the area-estimation error for a circular opacity.

Fig. 8
Fig. 8

The fractional area-estimation error versus the number of views for a circular disk with arbitrarily fine detector spacing.

Fig. 9
Fig. 9

A three-dimensional drawing of the area-estimation error as a function of the number of views and the detector spacing.

Fig. 10
Fig. 10

x coordinate of vertices as a function of the view angle with detector spacing Δs set at 0.3 (1 pixel width), (a) Ideal variation (Δs = 0, Nθ = ∞), (b) Nθ = 5, (c) Nθ = 10, (d) Nθ = 45.

Fig. 11
Fig. 11

Same as Fig. 10 except that Δs is set at 0.15 (1/2 pixel width).

Fig. 12
Fig. 12

Variation of the x coordinate of the vertices, with 180 views, for (a) Δs = , (b) Δs = 0.01, (c) Δs = 0.1, (d) Δs = 0.3.

Fig. 13
Fig. 13

Estimated opacity displayed for (a) Nθ= 2, (b) Nθ = 5, (c) Nθ = 10, (d) Nθ = 45. The detector spacing is Δs = 0.3.

Fig. 14
Fig. 14

Estimated opacity displayed for (a) Δs = , (b) Δs = 0.01, (c) Δs = 0.1, (d) Δs = 0.3. The number of views is Nθ = 180.

Tables (4)

Tables Icon

Table 1 Area-Estimation Error for a Detector Spacing of 0.3 and Various Numbers of Views

Tables Icon

Table 2 Area-Estimation Error for a Detector Spacing of 0.15 and Various Numbers of Views

Tables Icon

Table 3 Area-Estimation Error for 180 Views and Various Detector Spacings

Tables Icon

Table 4 Shape-Estimation Error for Different Detector Spacings and Various Numbers of Views

Equations (48)

Equations on this page are rendered with MathJax. Learn more.

x i cos θ i + y i sin θ i = s i ( θ i ) , x i cos θ i + 1 + y i sin θ i + 1 = s i ( θ i + 1 ) ,
x θ = s 1 ( θ ) cos θ s 1 ( θ ) sin θ ,
y θ = s 1 ( θ ) sin θ s 1 ( θ ) cos θ ,
x i = s 1 ( θ i ) sin θ i + 1 s 1 ( θ i + 1 ) sin θ i sin Δ θ , y i = s 1 ( θ i ) cos θ i + 1 s 1 ( θ i + 1 ) cos θ i sin Δ θ .
A 1 = ½ W 12 × W 13 ,
A k = ½ W 1 , k + 1 × W 1 , k + 2 .
r 0 2 tan ( π N 1 ) π r 0 2 N 1 .
A = N 1 r 0 2 tan ( π N 1 ) π r 0 2 π r 0 2 = N 1 π tan ( π N 1 ) 1 .
A = π 2 3 N 1 2 = π 2 12 N θ 2 .
x θ = s 1 ( θ ) cos θ s 1 ( θ ) sin θ , y θ = s 1 ( θ ) sin θ + s 1 ( θ ) cos θ .
s 1 ( θ i ) = s 1 ( θ i ) + i , | i | < 0.5 Δ s ,
s 1 ( θ i + 1 ) = s 1 ( θ i + 1 ) + i + 1 , | i + 1 | < 0.5 s .
x i = s 1 ( θ i ) sin [ ( i + 1 ) Δ θ ] s 1 ( θ i + 1 ) sin θ i sin Δ θ .
x i = s 1 ( θ i ) sin [ ( i + 1 ) Δ θ ] s 1 ( θ i + 1 ) sin θ i sin Δ θ .
Δ V i ( x ) x i x i 2 δ s 1 ( θ ) sin Δ θ Δ s sin Δ θ .
Δ θ Δ V max Δ s , Δ V max N θ Δ s π .
Δ V max Δ s sin ( π / N θ ) .
δ ¯ υ 2 = Δ s 2 12 sin 2 Δ θ = Δ s 2 12 sin 2 ( π / N θ ) ,
δ ¯ υ 2 = ( N θ Δ s ) 2 12 π 2 ,
A = 2 N θ π tan ( π 2 N θ ) 1 ,
M = ( Δ s r 0 ) 2 [ N θ 6 π tan ( π / N θ ) ] .
A = 2 N θ π [ tan ( π 2 N θ ) π 2 N θ + ( Δ s r 0 ) 2 1 12 tan ( π / N θ ) ] .
s 1 ( θ ) = x 0 cos θ + y 0 sin θ r 0 ,
x θ = x 0 r 0 cos θ . y θ = y 0 r 0 sin θ
A = area ( MPI ) area ( disk ) area ( disk ) × 100 % ,
IND T ( x , y ) = { 1 if ( x , y ) is inside or on the boundary of the disk 0 if ( x , y ) is outside the boundary
IND E ( x , y ) = { 1 if ( x , y ) is inside or on the boundary of the estimated shape 0 otherwise
E = ( x , y ) | IND E ( x , y ) IND T ( x , y ) | ( x , y ) IND T ( x , y ) × 100 % .
s 1 ( θ ) = x i cos θ i + y i sin θ i , s 1 ( θ i + 1 ) = x i cos θ i + 1 + y i sin θ i + 1 ,
x i = s 1 ( θ i ) sin θ i + 1 s 1 ( θ i + 1 ) sin θ i sin ( Δ θ ) , y i = s 1 ( θ i ) cos θ i + 1 s 1 ( θ i + 1 ) cos θ i sin ( Δ θ ) ,
s 1 ( θ i + 1 ) = s 1 ( θ i ) + s 1 ( θ i ) Δ θ + O [ ( Δ θ ) 2 ] .
x i s 1 ( θ ) ( sin θ + Δ θ cos θ ) [ s 1 ( θ ) + s 1 ( θ ) Δ θ ] sin θ Δ θ , y i s 1 ( θ ) ( cos θ Δ θ sin θ ) [ s 1 ( θ ) + s 1 ( θ ) Δ θ ] cos θ Δ θ
Δ V i ( x ) = x i x i = 1 sin Δ θ ( α i i β i i + 1 ) ,
δ i 2 = Δ s 2 12 sin 2 Δ θ { sin 2 [ ( i + 1 ) Δ θ ] + sin 2 i Δ θ } .
δ V 2 ¯ 1 N 1 i = 1 N 1 1 δ i 2 ,
δ V 2 ¯ = 1 N 1 Δ s 2 12 sin 2 Δ θ i = 1 N 1 1 ( α i 2 + β i 2 ) ,
sin θ = 1 2 j ( e j θ e j θ )
i = 0 N 1 e j i θ = 1 e j N θ 1 e j θ ;
δ V 2 ¯ = Δ s 2 12 sin 2 Δ θ ,
A T = k = 1 N 1 2 A k = 1 2 k = 1 N 1 2 W 1 , k + 1 × W 1 , k + 2 = 1 2 k = 0 N 1 1 ( V k + 1 V 1 ) × ( V k + 2 V 1 ) = 1 2 k = 0 N 1 1 V k + 1 × V k + 2 .
M = 1 2 [ i = 1 N 1 ( V i + Δ V i ) × ( V i + 1 + Δ V i + 1 ) i = 1 N 1 ( V i × V i + 1 ) ] ,
M = 1 2 i = 1 N 1 [ Δ V i × V i + 1 + V i × Δ V i + 1 + Δ V i × Δ V i + 1 ] .
Δ V i ( x ) = i a i + 1 i + 1 a i , Δ V i ( y ) = i b i + 1 i + 1 b i ,
a i sin ( i Δ θ ) sin ( Δ θ ) , b i cos ( i Δ θ ) sin ( Δ θ ) .
M = E [ M ] = 1 2 i = 1 N 1 E ( Δ V i × Δ V i + 1 ) ,
M = 1 2 i = 1 N 1 E [ ( a i + 1 i a i i + 1 ) ( b i + 2 i + 1 b i + 1 i + 2 ) ( a i + 2 i + 1 a i + 1 i + 2 ) ( b i + 1 i b i i + 1 ) ] .
M = N 1 2 ( Δ s ) 2 12 sin 2 Δ θ sin 2 Δ θ .
M = N θ 6 π ( Δ s r 0 ) 2 1 tan Δ θ .

Metrics