Stochastic Systems Group Wide-Angle SAR Image Formation with Migratory Scattering Centers and Regularization in Hough Space Kush R. Varshney, Müjdat Çetin, John W. Fisher III, and Alan S. Willsky June 6, 2006 Massachusetts Institute of Technology Stochastic Systems Group Outline • Spotlight-Mode SAR Imaging • Joint Image Formation and Anisotropy Characterization • Overcomplete Basis Formulation • Sparsifying Regularization • Moving From Pixels to Objects Migratory Scattering Centers Regularization in Hough Space Massachusetts Institute of Technology Page 2 Stochastic Systems Group 2-D Spotlight-Mode SAR s ( x, y ) Massachusetts Institute of Technology Page 3 Stochastic Systems Group Observation Model • Phase history domain: − j 4 πc f ( x cosθ + y sin θ ) r ( f , θ ) = ∫∫ s ( x, y )e dxdy x 2 + y 2 ≤ L2 • Range profile domain: ˆ (ρ , θ ) = R s( x, y )δ (ρ − x cos θ − y sin θ )dxdy 2 ∫∫ x + y 2 ≤ L2 Projection of scattering function in direction specified by θ • Related by 1-D Fourier transform L r ( f ,θ ) = R ˆ (ρ ,θ ) exp − j 4πf ρ dρ c ∫ −L Massachusetts Institute of Technology { } Page 4 Stochastic Systems Group Point Scatterers • At typical SAR frequencies, scattering appears as though coming from a set of discrete points • s( x, y ) = δ (x0 , y0 ) { } • Phase history: r ( f ,θ ) = exp − j 4πc f ( x0 cos θ + y0 sin θ ) • Range profile: Rˆ (ρ ,θ ) = δ (ρ − x cos θ − y sin θ ) 0 0 • Sinusoid in range profile: ρ = x0 cos θ + y0 sin θ Massachusetts Institute of Technology Page 5 Stochastic Systems Group Wide-Angle Imaging and Anisotropy • In principle, wide-angle apertures (long flight path) allow formation of images with high cross-range resolution • Isotropic scattering assumption violated • Scattering function depends on aspect angle θ Massachusetts Institute of Technology s ( x, y , θ ) Page 6 Stochastic Systems Group Point-Scatterer Model with Anisotropy • With P point-scattering centers and with anisotropy, phase history measurements modeled as: ⎧ 4πf ⎫ ( ) ( ) r ( f , θ ) = ∑ s x p , y p , θ exp ⎨− j x p cos θ + y p sin θ ⎬ c ⎩ ⎭ p =1 P • Joint image formation and anisotropy characterization: Recover s(x,y,θ) from r(f,θ) Massachusetts Institute of Technology Page 7 Stochastic Systems Group Approach • Spatial locations (xp,yp) can be pixels or points of interest • Expand s(xp,yp,θ) into an overcomplete basis • Ill-posed inverse problem • Solve for coefficients with sparsifying regularization Massachusetts Institute of Technology Page 8 Stochastic Systems Group Overcomplete Basis Expansion • Expand s(xp,yp,θ) into {b1(θ), b2(θ), …, bM(θ)} ⎧ 4πf ⎫ (x p cos θ + y p sin θ )⎬ r ( f , θ ) = ∑∑ a p ,mbm (θ ) exp ⎨− j c ⎩ ⎭ p =1 m =1 P M • Problem: determine unknown coefficients ap,m • f, θ discrete variables f1, f2, …, fK θ1, θ2, …, θN • Overcomplete basis M>N Massachusetts Institute of Technology Page 9 Stochastic Systems Group Matrix-Vector Form • Expressible in matrix-vector form: ⎡ r ( f1 , θ ) ⎤ ⎡ b1 (θ )e − 4 jπf1 ( x1 cos θ + y1 sin θ ) c ⎢ r( f , θ)⎥ ⎢ − 4 jπf 2 ( x1 cos θ + y1 sin θ ) c ⎢ 2 ⎥ = ⎢ b1 (θ )e ⎢ # ⎥ ⎢ # ⎥ ⎢ ⎢ − 4 jπf K ( x1 cos θ + y1 sin θ ) c ⎣r ( f K , θ )⎦ ⎢⎣b1 (θ )e " b M (θ )e − 4 jπf1 ( x1 cos θ + y1 sin θ ) c b1 (θ )e − 4 jπf1 ( x2 cos θ + y2 sin θ ) c " " b M (θ )e − 4 jπf 2 ( x1 cos θ + y1 sin θ ) c % # b1 (θ )e − 4 jπf 2 ( x2 cos θ + y2 sin θ ) c # " b M (θ )e − 4 jπf K ( x1 cos θ + y1 sin θ ) c b1 (θ )e − 4 jπf K ( x2 cos θ + y2 sin θ ) c " " % ⎡ a1,1 ⎤ ⎥ ⎢ b M (θ )e − 4 jπf1 ( xP cos θ + y P sin θ ) c ⎤ ⎢ # ⎥ ⎥ b M (θ )e − 4 jπf 2 ( xP cos θ + y P sin θ ) c ⎥ ⎢ a1, M ⎥ ⎥ ⎢ ⎥ ⎢ a2,1 ⎥ # ⎥ b M (θ )e − 4 jπf K ( xP cos θ + y P sin θ ) c ⎥⎦ ⎢ # ⎥ ⎥ ⎢ ⎢⎣aP , M ⎥⎦ • r = Φa • (r = Φa + n) Massachusetts Institute of Technology Page 10 Stochastic Systems Group Specific Choice of Basis • What are the bm(θ)? • Choose to allow parsimonious representation |s(θ)| • Contiguous intervals of anisotropy – all widths and all shifts Aspect Angle Massachusetts Institute of Technology Page 11 Stochastic Systems Group Specific Choice of Basis • Rectangular pulses, for example Can seamlessly insert any other shape Hamming, Triangle, Raised Triangle • Incorporates some prior information b1 b2 bM θ1 θ2 θ3 θ4 θ5 θ6 θ7 θ8 Massachusetts Institute of Technology Page 12 Stochastic Systems Group Sparsifying Regularization 2 k • Find a that minimizes J (a) = r − Φa + α a , k < 1 2 k • k denotes ℓk-norm • First term: data fidelity • Second term: regularization term favoring sparsity • J(a) can be minimized effectively Quasi-Newton method [Çetin & Karl 2001] Greedy graph-structured algorithm [Varshney et al. 2006] Massachusetts Institute of Technology Page 13 Stochastic Systems Group Quick Example least-squares solution (α = 0) 0.5 0 0 -0.5 0 0.5 0 0 -0.5 0.8 0 3 3 4 2 Massachusetts Institute of Technology θ θ 0.8 2 4 4 2 2 0.8 0 θ 0 θ 4 0.8 0 0 θ | s( x , y , θ)| 0.8 0.8 1 3 3 | s( x , y , θ)| 1 0 θ | s( x , y , θ)| s(θ) 500 1000 a 0.8 1 | s( x , y , θ)| 0.8 0 | s( x , y , θ)| 500 1000 a | s( x , y , θ)| -0.5 0 500 1000 a3 1 0.5 -0.5 500 1000 a1 | s( x , y , θ)| 0 | s( x , y , θ)| coefficients 0.5 sparse solution (α = 3) 0 θ 0 θ Page 14 Stochastic Systems Group Moving from Pixels to Objects • Scattering centers have more meaning than just pixels • More information is available to allow scene interpretation • 2 phenomena Anisotropy width and spatial extent are related Certain scattering mechanisms migrate as a function of θ Massachusetts Institute of Technology Page 15 Stochastic Systems Group Glint Anisotropy • Glint or flash – like a mirror • Very thin response in θ • Corresponds to long flat plate in space • Thinner anisotropy, longer spatial extent • Would like to explain glint anisotropy parsimoniously Additional sparsity along a line Can infer properties about objects in scene such as orientation and spatial extent Massachusetts Institute of Technology Page 16 Stochastic Systems Group Range profile • ρ parameterizes direction of θ in ground plane geometry • For fixed θ, ρ = xcosθ + ysinθ Massachusetts Institute of Technology Page 17 Stochastic Systems Group Hough Transform Ideas • Points on a line in image space x • Intersecting sinusoids in range profile space ρ θ* ρ* Massachusetts Institute of Technology y ρ* θ* Page 18 θ Stochastic Systems Group Sparsity Along A Line • For sparsity along a line, use Hough transform ideas • Sparsity among scatterers in ρ-θ cells 2 k • J (a) = r − Φa + α 0 a + α1 2 k Li,j = Si,jFΦ’ K (ρi,θj) N ∑∑ i =1 j =1 Li, ja k k Φ’ takes coefficients to phase history domain (not exactly Φ) F, DFT-like operator, converts to range profile domain Si,j selects the (i,j)th cell in the range profile domain Massachusetts Institute of Technology Page 19 Stochastic Systems Group Scene with Glint Anisotropy Conventional image (formed with polar format algorithm) True anisotropy at a point -0.5 magnitude range (m) -1 0 0.5 1 1.5 -1 0 cross-range (m) 1 Massachusetts Institute of Technology θ Page 20 Stochastic Systems Group Example: α0 = 30, α1 = 0 Magnitude parsimonious in basis vectors per pixel 1 211 421 631 8411051126114711681189121012311252127312941315133613571378139914201441146214831 Massachusetts Institute of Technology Page 21 Stochastic Systems Group Example: α0 = 0, α1 = 20 Magnitude parsimonious in pixels 1 211 421 631 8411051126114711681189121012311252127312941315133613571378139914201441146214831 Massachusetts Institute of Technology Page 22 Stochastic Systems Group Example: α0 = 30, α1 = 20 Magnitude solution represents entire glint with one basis vector 1 211 421 631 8411051126114711681189121012311252127312941315133613571378139914201441146214831 Massachusetts Institute of Technology Page 23 Stochastic Systems Group Other Hough-Type Regularization Terms • Sparsity along a line is not the only possibility • Can favor other types of spatial geometry in image formation Massachusetts Institute of Technology Page 24 Stochastic Systems Group Migratory Scattering Centers • Other effect besides anisotropy prominent in wide-angle SAR • Certain types of scattering centers migrate as function of θ • Parameterize migration around a ‘center’ • Scattering center closer to radar by R(θ) • If circle, R(θ) = R Massachusetts Institute of Technology Page 25 Stochastic Systems Group Trigonometry Rcosθ Rsinθ θ (xc, yc) R (xc–Rcosθ, yc–Rsinθ) • s(x, y) = δ(xc–Rcosθ, yc–Rsinθ) • ρ = (xc–Rcosθ)cosθ + (yc–Rsinθ)sinθ = xccosθ + ycsinθ – R • ρ = xccosθ + ycsinθ – R(θ) Massachusetts Institute of Technology Page 26 Stochastic Systems Group Migratory Scattering Center Observation Model (x p , yp ) invariant spatial location (when θ = 0) ⎧ 4πf r ( f , θ ) = ∑ s (x p , y p , θ )exp ⎨− j c ⎩ p =1 P Massachusetts Institute of Technology ((x ⎫ ) ) ( ) ( ) + + − R 0 cos θ y sin θ R θ ⎬ p p p p ⎭ Page 27 Stochastic Systems Group Procedures for Circular Migration Characterization • Restricting to migration in a circle, two methods • Method 1: even more overcomplete basis P L M ⎧ 4πf ⎫ ( ( ) ) ( ) − + + − a b θ exp j x R cos θ y sin θ R ⎨ ∑∑∑ p ,l , m m p p ,l p p ,l ⎬ c ⎩ ⎭ p =1 l =1 m =1 • Techniques to minimize cost function unchanged Massachusetts Institute of Technology Page 28 Stochastic Systems Group Procedures for Circular Migration Characterization • Method 2: optimize over vector of radii R (one entry per scatterer) R { min r − Φ(R ) arg min r − Φ(R ) 2 + α a a k k } 2 2 basis vectors as function of radius: ⎧ ⎩ φk , p ,m (R p ) = bm (θ ) ⋅ exp⎨− j 2 4πf k ((x p + R p )cosθ + y p sin θ − R p )⎫⎬ c ⎭ minimization by nonlinear least-squares optimization techniques, where the nonlinear function involves solving the inner sparsifying regularization minimization Massachusetts Institute of Technology Page 29 Stochastic Systems Group Example true migratory scattering shape overlaid on conventional image migratory scattering solution overlaid on conventional image solution gives much more object-level information than conventional image Massachusetts Institute of Technology Page 30 Stochastic Systems Group Non-Circular Migration • Characterize circular migration over subapertures -0.4 -1 -0.8 -0.6 -0.2 -0.2 range (m) range (m) -0.4 0 0.2 0 0.4 0.6 0.8 1 -1 -0.5 0 cross-range (m) 0.5 Massachusetts Institute of Technology 1 0.2 -0.2 -0.1 0 0.1 0.2 cross-range (m) 0.3 0.4 Page 31 Stochastic Systems Group Conclusion • Novel overcomplete basis and sparse signal representation formulation for anisotropy characterization in wide-angle SAR • Exploit available information in phase history measurements to extract object-level information Hough space regularization for glint anisotropy Migratory basis vectors in overcomplete basis for migratory scattering Massachusetts Institute of Technology Page 32 Stochastic Systems Group Questions Massachusetts Institute of Technology