Abstract

In this paper we demonstrate the theoretical equivalence of two robust techniques for two-dimensional phase unwrapping. The first is based on the least-squares (LS) approach, and the second is based on Green’s formulation. To be theoretically comparable with Green’s method, the LS phase unwrapping is formulated in the continuous domain, leading to the minimization of a specific functional. Subsequently, we investigate the computational requirements of the procedures implementing the two methods. To do this, we have modified the first Green’s identity-based algorithm to account for periodic phase patterns. This reformulation allows us to compare the existing efficient LS procedures and leads to a procedure whose memory and computational requirements are less stringent than those presented in Fornaro et al. [ IEEE Trans. Geosci. Remote Sens. 34, 720 ( 1996)].

© 1996 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. H. Hudgin, “Wave-front reconstruction for compensated imaging,” J. Opt. Soc. Am. 67, 370–375 (1977).
    [CrossRef]
  2. H. A. Zebker, R. M. Goldstein, “Topographic mapping from interferometric synthetic aperture radar observations,” J. Geophys. Res. 91, 4993–4999 (1986).
    [CrossRef]
  3. J. M. Martin, “Theory and design of interferometric synthetic aperture radars,” IEE Proc. F 139, 147–159 (1992).
  4. R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
    [CrossRef]
  5. Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
    [CrossRef]
  6. H. Takajo, T. Takahashi, “Noniterative methods for obtaining the exact solution for the normal equation in least-squares phase estimation from phase difference,” J. Opt. Soc. Am. A 5, 1818–1827 (1988).
    [CrossRef]
  7. D. C. Ghiglia, L. A. Romero, “Direct phase estimation from phase difference using fast elliptic partial differential equation solvers,” Opt. Lett. 14, 1107–1109 (1989).
    [CrossRef] [PubMed]
  8. D. C. Ghiglia, L. A. Romero, “Robust two-dimensional weighted and unweighted phase unwrapping that uses fast transform and iterative methods,” J. Opt. Soc. Am. A 11, 107–117 (1994).
    [CrossRef]
  9. M. D. Pritt, J. S. Shipman, “Least-squares two dimensional phase unwrapping using FFT’s,” IEEE Trans. Geosci. Remote Sens. 32, 706–708 (1994).
    [CrossRef]
  10. G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
    [CrossRef]
  11. E. Sansosti, “Tecniche di phase unwrapping in interferometria SAR,” laurea thesis (University of Naples Federico II, 1995).
  12. H. Margenau, G. M. Murphy, The Mathematics of Physics and Chemistry (Van Nostrand, New York, 1956), Chap. 6.
  13. A. V. Oppenheim, R. W. Schafer, Discrete-Time Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989), pp. 548–560 and 587–592.
  14. W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.
  15. D. S. Jones, Methods in Electromagnetic Wave Propagation (Clarendon, Oxford, 1979), Vol. 1, pp. 481–489.
  16. J. F. Botha, G. F. Pinder, Fundamental Concepts in the Numerical Solution of Differential Equations (Wiley, New York, 1983), pp. 22–42.

1996 (1)

G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
[CrossRef]

1994 (3)

D. C. Ghiglia, L. A. Romero, “Robust two-dimensional weighted and unweighted phase unwrapping that uses fast transform and iterative methods,” J. Opt. Soc. Am. A 11, 107–117 (1994).
[CrossRef]

Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
[CrossRef]

M. D. Pritt, J. S. Shipman, “Least-squares two dimensional phase unwrapping using FFT’s,” IEEE Trans. Geosci. Remote Sens. 32, 706–708 (1994).
[CrossRef]

1992 (1)

J. M. Martin, “Theory and design of interferometric synthetic aperture radars,” IEE Proc. F 139, 147–159 (1992).

1989 (1)

1988 (2)

H. Takajo, T. Takahashi, “Noniterative methods for obtaining the exact solution for the normal equation in least-squares phase estimation from phase difference,” J. Opt. Soc. Am. A 5, 1818–1827 (1988).
[CrossRef]

R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

1986 (1)

H. A. Zebker, R. M. Goldstein, “Topographic mapping from interferometric synthetic aperture radar observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

1977 (1)

Botha, J. F.

J. F. Botha, G. F. Pinder, Fundamental Concepts in the Numerical Solution of Differential Equations (Wiley, New York, 1983), pp. 22–42.

Flannery, B. P.

W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.

Fornaro, G.

G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
[CrossRef]

Franceschetti, G.

G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
[CrossRef]

Ghiglia, D. C.

Goldenstein, R. M.

R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

Goldstein, R. M.

H. A. Zebker, R. M. Goldstein, “Topographic mapping from interferometric synthetic aperture radar observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

Hudgin, R. H.

Jones, D. S.

D. S. Jones, Methods in Electromagnetic Wave Propagation (Clarendon, Oxford, 1979), Vol. 1, pp. 481–489.

Lanari, R.

G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
[CrossRef]

Lin, Q.

Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
[CrossRef]

Margenau, H.

H. Margenau, G. M. Murphy, The Mathematics of Physics and Chemistry (Van Nostrand, New York, 1956), Chap. 6.

Martin, J. M.

J. M. Martin, “Theory and design of interferometric synthetic aperture radars,” IEE Proc. F 139, 147–159 (1992).

Murphy, G. M.

H. Margenau, G. M. Murphy, The Mathematics of Physics and Chemistry (Van Nostrand, New York, 1956), Chap. 6.

Oppenheim, A. V.

A. V. Oppenheim, R. W. Schafer, Discrete-Time Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989), pp. 548–560 and 587–592.

Pinder, G. F.

J. F. Botha, G. F. Pinder, Fundamental Concepts in the Numerical Solution of Differential Equations (Wiley, New York, 1983), pp. 22–42.

Press, W. H.

W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.

Pritt, M. D.

M. D. Pritt, J. S. Shipman, “Least-squares two dimensional phase unwrapping using FFT’s,” IEEE Trans. Geosci. Remote Sens. 32, 706–708 (1994).
[CrossRef]

Romero, L. A.

Sansosti, E.

E. Sansosti, “Tecniche di phase unwrapping in interferometria SAR,” laurea thesis (University of Naples Federico II, 1995).

Schafer, R. W.

A. V. Oppenheim, R. W. Schafer, Discrete-Time Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989), pp. 548–560 and 587–592.

Shipman, J. S.

M. D. Pritt, J. S. Shipman, “Least-squares two dimensional phase unwrapping using FFT’s,” IEEE Trans. Geosci. Remote Sens. 32, 706–708 (1994).
[CrossRef]

Takahashi, T.

Takajo, H.

Teukolsky, S. A.

W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.

Vesecky, F.

Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
[CrossRef]

Vetterling, W. T.

W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.

Werner, C. L.

R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

Zebker, H. A.

Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
[CrossRef]

R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

H. A. Zebker, R. M. Goldstein, “Topographic mapping from interferometric synthetic aperture radar observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

IEE Proc. F (1)

J. M. Martin, “Theory and design of interferometric synthetic aperture radars,” IEE Proc. F 139, 147–159 (1992).

IEEE Trans. Geosci. Remote Sens. (2)

M. D. Pritt, J. S. Shipman, “Least-squares two dimensional phase unwrapping using FFT’s,” IEEE Trans. Geosci. Remote Sens. 32, 706–708 (1994).
[CrossRef]

G. Fornaro, G. Franceschetti, R. Lanari, “Interferomet-ric SAR phase unwrapping using Green’s formulation,” IEEE Trans. Geosci. Remote Sens. 34, 720–727 (1996).
[CrossRef]

Int. J. Remote Sens. (1)

Q. Lin, F. Vesecky, H. A. Zebker, “Comparison of elevation derived from INSAR data with DEM over large relief terrain,” Int. J. Remote Sens. 15, 1775–1790 (1994).
[CrossRef]

J. Geophys. Res. (1)

H. A. Zebker, R. M. Goldstein, “Topographic mapping from interferometric synthetic aperture radar observations,” J. Geophys. Res. 91, 4993–4999 (1986).
[CrossRef]

J. Opt. Soc. Am. (1)

J. Opt. Soc. Am. A (2)

Opt. Lett. (1)

Radio Sci. (1)

R. M. Goldenstein, H. A. Zebker, C. L. Werner, “Satellite radar interferometry: two-dimensional phase unwrapping,” Radio Sci. 23, 713–720 (1988).
[CrossRef]

Other (6)

E. Sansosti, “Tecniche di phase unwrapping in interferometria SAR,” laurea thesis (University of Naples Federico II, 1995).

H. Margenau, G. M. Murphy, The Mathematics of Physics and Chemistry (Van Nostrand, New York, 1956), Chap. 6.

A. V. Oppenheim, R. W. Schafer, Discrete-Time Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1989), pp. 548–560 and 587–592.

W. H. Press, B. P. Flannery, S. A. Teukolsky, W. T. Vetterling, Numerical Recipes in C (Cambridge U. Press, Cambridge, 1988), pp. 398–424 and 676–680.

D. S. Jones, Methods in Electromagnetic Wave Propagation (Clarendon, Oxford, 1979), Vol. 1, pp. 481–489.

J. F. Botha, G. F. Pinder, Fundamental Concepts in the Numerical Solution of Differential Equations (Wiley, New York, 1983), pp. 22–42.

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 (11)

Fig. 1
Fig. 1

A, Unwrapped and B, wrapped 1-D linear phase patterns in the presence of a phase discontinuity α < π.

Fig. 2
Fig. 2

Same as Fig. 1, but for a > π.

Fig. 3
Fig. 3

Problem of the impulsive boundary components ϕ and ϕ m in the 1-D case.

Fig. 4
Fig. 4

Mirror reflection in the 1-D case for suppression of the impulsive gradient components on the boundary.

Fig. 5
Fig. 5

2-D mirror reflection. Both sx and sy components are reflected first around the vertical axis and then around the horizontal one.

Fig. 6
Fig. 6

Block diagram of the LS algorithm as presented in Ref. 9.

Fig. 7
Fig. 7

Block diagram of the PGF algorithm.

Fig. 8
Fig. 8

Comparison of the computational efficiency of the LS and PGF methods. The solid line represents the number of iterations (Nit) necessary for the PGF method to achieve the same LS computational efficiency for different data dimensions (MN). The dashed box shows the efficiency of the algorithm used by the data set of Fig. 9.

Fig. 9
Fig. 9

Wrapped C-band data relative to the Etna site acquired by the Spaceborn Imaging Radar-C (SIR-C).

Fig. 10
Fig. 10

Three-dimensional view of the unwrapped data obtained by the use of the PGF algorithm on the image of Fig. 9.

Fig. 11
Fig. 11

Convergence plot of the estimated first-order outward differences on the boundary. ε represents the mean absolute variation during iteration.

Equations (73)

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

d ϕ d x 2 π i sgn [ d ϕ d x ( x i ) ] δ ( x x i ) = d ϕ m d x ,
ϕ ( x i ) = n π , n odd ;
d ϕ d x = b + a δ ( x x d ) ,
d ϕ m d x = b ( 2 π a ) δ ( x x d ) 2 π δ ( x x 1 , 3 ) ,
s = d ϕ m d x + 2 π δ ( x x d ) + 2 π δ ( x x 1 , 3 ) = b + a δ ( x x d ) ,
d ϕ d x = b + ( 2 π + k ) δ ( x x d ) ,
d ϕ m d x = b + k δ ( x x d ) 2 π δ ( x x 1 , 3 ) .
s = b + k δ ( x x d ) .
ϕ = S ,
L [ ϕ ] = ϕ s 2 min ,
ϕ s 2 = ϕ s , ϕ s = D d S [ ( ϕ s ) · ( ϕ s ) * ] .
δ L = 2 D d S ( ϕ · δ ϕ s · δ ϕ ) = 0 .
v · u = · ( v u ) u · v ,
D d S 2 ϕ δ ϕ + C d l ϕ n δ ϕ D d S · ( s δ ϕ ) + D d S δ ϕ · s = 0 ,
D d S ( · s 2 ϕ ) δ ϕ C d l ( s · n ̂ ϕ n ) δ ϕ = 0 ,
{ 2 ϕ = · s in D ϕ n = s · n ̂ on C .
D d S ( ϕ 2 g + ϕ · g ) = C d l ϕ g n ,
2 g ( r ) = δ ( r ) .
ϕ ( r ) = D d S s ( r ) · g ( r r ) + C d l ϕ ( r C ) g ( r r C ) n , r D ,
D d S ϕ ( r ) 2 g ( r r ) = ϕ ( r ) ,
D d S g ( r r ) 2 ϕ ( r ) + C d l [ ϕ ( r C ) × g n ( r r C ) g ( r r C ) ϕ n ( r C ) ] = ϕ ( r ) .
D d S g ( r r ) · s ( r ) + C d l [ ϕ ( r C ) × g n ( r r C ) g ( r r C ) ϕ n ( r C ) ] = ϕ ( r ) ,
D d S · [ g ( r r ) s ( r ) ] D d S g ( r r ) · s ( r ) + C d l [ ϕ ( r C ) g n ( r r C ) g ( r r C ) ϕ n ( r C ) ] = ϕ ( r ) .
C d l g ( r r ) s ( r ) · n ̂ D d S g ( r r ) · s ( r ) + C d l [ ϕ ( r ) g n ( r r ) g ( r r ) ϕ n ( r ) ] = ϕ ( r ) ,
a n ( ϕ n + 1 , m ϕ n , m ) a n 1 ( ϕ n , m ϕ n 1 , m ) + b m ( ϕ n , m + 1 ϕ n , m ) b m 1 ( ϕ n , m ϕ n , m 1 ) = a n s n , m x a n 1 s n 1 , m x + b m s n , m y b m 1 s n , m 1 y , n = 0 , , N 1 , m = 0 , , M 1 ,
{ a n = 1 , n = 0 , , N 2 , a 1 = a N 1 = 0 { b m = 1 , m = 0 , , M 2 b 1 = b M 1 = 0 .
ϕ ( x , y ) ϕ ( x , y ) = ϕ ( x + p a , y + q b ) p , q ,
ϕ ( x , y ) ϕ ( x , y )
2 g ( x , y ) = p , q = + δ ( x p a , y q b ) .
ϕ ( x , y ) = S d S s ( x , y ) · g ( x x , y y ) ,
G n , m = 1 a b 1 ( 2 π n / a ) 2 + ( 2 π m / b ) 2 ,
G n , m = 1 a b j 2 π n / a ( 2 π n / a ) 2 + ( 2 π m / b ) 2 x ̂ 1 a b j 2 π m / b ( 2 π n / a ) 2 + ( 2 π m / b ) 2 y ̂ ,
Φ n , m = + j ( 2 π n / a ) x ̂ + ( 2 π m / b ) ] y ̂ a b [ ( 2 π n / a ) 2 + ( 2 π m / b ) 2 ] · S d x d y s exp [ j ( 2 π n x / a + 2 π m y / b ) ] .
ϕ ( x , y ) = n = + m = + Φ n , m × exp [ j 2 π n x / a + j 2 π m y / b ] .
{ x = a / 2 y = t , t [ b / 2 , b / 2 [ , { x = t , t [ a / 2 , a / 2 [ y = b / 2 .
Φ n , m = G n , m · S d S s exp ( j k n , m · r ) G n , m · r ) G n , m · L d l ( ϕ L · n ̂ ) n ̂ exp ( j k n , m · r L ) = Φ n , m ( 0 ) + Φ n , m ( 1 ) ,
ϕ L = ϕ ( r L ) , k n , m = 2 π a n x ̂ + 2 π b m y ̂ ,
ϕ L · n ̂ = n = + m = + j k n , m · n ̂ exp ( j k n , m · r L ) Φ n , m ( 0 ) + n = + m = + j k n , m · n ̂ × exp ( j k n , m · r L ) Φ n , m ( 1 ) ,
N c = 2 [ 2 N × 2 M 2 log 2 ( 2 N × 2 M ) ] + ( 2 N × 2 M ) = N M [ 4 log 2 ( N M ) + 12 ] ,
N c = 3 N M 2 log 2 ( N M ) + 2 N M + N it N M + [ N M 2 log 2 ( N M ) + 2 N M ] + [ 2 N M 2 log 2 ( N M ) + 4 N M ] = N M [ 3 log 2 ( N M ) + 8 + N it ] ,
N it = log 2 ( N M ) + 4 .
( ϕ n 1 , m 2 ϕ n , m + ϕ n + 1 , m ) + ( ϕ n , m 1 2 ϕ n , m + ϕ n , m + 1 ) = ( s n , m x s n 1 , m x ) + ( s n , m y s n , m 1 y ) , n = 1 , , N 2 , m = 1 , , M 2 .
( ϕ 1 , m 2 ϕ 0 , m + ϕ 1 , m ) + ( ϕ 0 , m 1 2 ϕ 0 , m + ϕ 0 , m + 1 ) = ( s 0 , m x s 1 , m x ) + ( s 0 , m y s 0 , m 1 y ) , m = 1 , , M 2 ,
ϕ x = s x ,
ϕ 0 , m + ϕ 1 , m = s 1 , m x .
( ϕ 0 , m + ϕ 1 , m ) + ( ϕ 0 , m 1 2 ϕ 0 , m + ϕ 0 , m + 1 ) = s 0 , m x + ( s 0 , m y s 0 , m 1 y ) , m = 1 , , M 2 .
ϕ ( r ) = S d S s ( r ) · g ( r r ) + C d l ϕ ( r C ) g n ( r r C ) .
{ x = a / 2 y = t t ( b / 2 , b / 2 ) .
f a / 2 ( x , y ) = b / 2 b / 2 d t ϕ ( a / 2 , t ) g x ( x a / 2 , y t ) .
{ x = a / 2 y = t t ( b / 2 , b / 2 ) ,
f a / 2 ( x , y ) = b / 2 b / 2 d t ϕ ( a / 2 , t ) × g x ( x + a / 2 , y t ) .
{ ϕ ( a / 2 , t ) = ϕ ( a / 2 , t ) t g x ( x a / 2 , y t ) = g x ( x + a / 2 , y t ) ; t , x , y
f a / 2 ( x , y ) + f a / 2 ( x , y ) = 0 , x , y .
g ( x , y ) = n , m G n , m exp ( + j 2 π n x / a + j 2 π m y / b ) ,
2 [ ( 2 π n / a ) 2 + ( 2 π m / b ) 2 ] ,
FS [ p , q = + δ ( x p a , y q b ) ] = 1 a b ,
FS [ g ( x , y ) x ] = + j 2 π a n G n , m .
G n , m = 1 2 j sin ( π n / N ) exp ( j π n / N ) sin 2 ( π n / N ) + sin 2 ( π m / M ) x ̂ 1 2 j sin ( π m / M ) exp ( j π m / M ) sin 2 ( π n / N ) + sin 2 ( π m / M ) y ̂ ,
Φ n , m = Φ n , m ( 0 ) + G n , m · x ̂ q = 0 M 1 [ ϕ ( 0 , q ) ϕ ( N 1 , q ) ] exp ( + j 2 π n / N ) exp ( j 2 π m q / M ) + G n , m · y ̂ l = 0 N 1 [ ϕ ( l , q ) ϕ ( l , M 1 ) ] × exp ( j 2 π n l / N ) exp ( + j 2 π m / M ) .
ϕ ( l , q ) = DFT n , m 1 ( Φ n , m ) = ϕ 0 ( l , q ) + t = 0 M 1 s x ( t ) f x ( l , q t ) + p = 0 N 1 s y ( p ) f y ( l p , q ) ϕ 0 ( l , q ) + α ( l , q ) + β ( l , q ) ,
ϕ 0 ( l , q ) = DFT n , m 1 [ Φ 1 ( 0 ) ] , f y ( l , q ) = 1 N M n = 0 N 1 m = 0 M 1 × j sin ( π n / N ) exp ( j π n / M ) 2 [ sin 2 ( π n / N ) + sin 2 ( π m / M ) ] × exp ( j 2 π n l / N ) exp ( j 2 π m q / M ) ,
f y ( l , q ) = 1 N M n = 0 N 1 m = 0 M 1 × j sin ( π m / M ) exp ( π m / M ) 2 [ sin 2 ( π n / N ) + sin 2 ( π m / M ) ] × exp ( j 2 π n l / N ) exp ( j 2 π m q / M ) , s x ( t ) = ϕ ( 0 , t ) ϕ ( N 1 , t ) , t = 0 , , M 1 , s y ( p ) = ϕ ( p , 0 ) ϕ ( p , M 1 ) , p = 0 , , N 1 .
{ l = N 1 q = 0 , , M 1 , { l = 0 , , N 1 q = M 1 .
s x ( q ) = ϕ 0 ( 0 , q ) ϕ 0 ( N 1 , q ) + t = 0 M 1 s x ( t ) [ f x ( 0 , q t ) f x ( N 1 , q t ) ] + p = 0 N 1 s y ( p ) [ f y ( p , q ) f y ( N 1 p , q ) ] = s 0 x ( q ) + t = 0 M 1 s x ( t ) b 1 ( q t ) + p = 0 N 1 s y ( p ) b 2 ( p , q ) ,
s 0 x ( q ) = ϕ 0 ( 0 , q ) ϕ 0 ( N 1 , q ) , b 1 ( q ) = f x ( 0 , q ) f x ( N 1 , q ) , b 2 ( p , q ) = f y ( p , q ) f y ( N 1 p , q ) .
s y ( l ) = s 0 y ( l ) + p = 0 N 1 s y ( p ) b 3 ( l p ) + t = 0 M 1 s x ( t ) b 4 ( l , t ) ,
s 0 y ( l ) = ϕ 0 ( l , 0 ) ϕ 0 ( l , M 1 ) , b 3 ( l ) = f y ( l , 0 ) f y ( l , M 1 ) , b 4 ( l , t ) = f x ( l , t ) f x ( l , M 1 t ) .
s x ( q ) = DFT q 1 { DFT q [ s 0 x ( q ) ] 1 DFT q [ b 1 ( q ) ] } + p = 0 N 1 s y ( p ) DFT q 1 { DFT q [ b 2 ( p , q ) ] 1 DFT q [ b 1 ( q ) ] } = s 0 x ( q ) + p = 0 N 1 s y ( p ) f y ( p , q ) ,
s y ( l ) = DFT l 1 { DFT l [ s 0 y ( l ) ] 1 DFT l [ b 3 ( l ) ] } + t = 0 M 1 s x ( t ) DFT l 1 { DFT l [ b 4 ( l , t ) ] 1 DFT l [ b 3 ( l ) ] } = s 0 y ( l ) + t = 0 M 1 s x ( t ) f x ( l , t ) .
N F = N it × N × M × 2 ,
N D = N F 2 + 2 N M 2 log 2 ( N M ) + 4 N M = 2 N M 2 log 2 ( N M ) + N M ( 4 + N it ) .
α ( l , q ) + β ( l , q ) = DFT q 1 { DFT q ( s x ) DFT q [ f x ( l , · ) ] } + DFT l 1 { DFT l ( s y ) DFT l [ f y ( · , q ) ] } .
N B N M 2 log 2 M + M N 2 log 2 N + 2 N M .

Metrics