Mikrodalga görüntülemede seyreklik yaklaşımı yöntemlerinin uygulanması
Sparse approximation and applications in microwave imaging
Yazar: EMRE YALÇIN
Danışman: DOÇ. DR. ÖZGÜR ÖZDEMİR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı / Telekomünikasyon Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Elektrik ve Elektronik Mühendisliği = Electrical and Electronics Engineering

Özet:
Cisimlerin şekli, yeri ve dielektrik sabiti gibi özelliklerinin belirlenmesi elektromanyetik
ters saçılma problemi olarak adlandırılır. Ters saçılma problemi optik, radar,
akustik, sismik ve medikal görüntülemede büyük önem taşımaktadır. Ters saçılma
problemi lineer olmayan ve kötü kurulmuş (ill-posed) bir problemdir. Born ve Rytov
yaklaşıklı˘gı ters saçılma probleminin lineerleştirilmesinde kullanılan en yaygın iki
yöntemdir. Ters saçılma problemi lineer hale getirildikten sonra da hala kötü kurulmuş
bir problem olma özelli˘gini korumaktadır. Bu yüzden çözüm tek de˘gildir, bu durumun
üstesinden gelmek için regularizasyon teknikleri sıkça kullanılmaktadır ve literatürde
birçok teknik bulunmaktadır.
Bu bitirme çalışmasında mikrodalga görüntüleme probleminin çözümü için seyreklik
yaklaşımı yöntemleri kullanılmıştır. Bu yöntemler temel olarak Born yaklaşıklı˘gı
sonucu elde edilen lineer denklem sistemini çözmektedir. Tezin ilk kısmında ters
saçılma problemi anlatılmış ve Born yaklaşıklığıyla bu problemin nasıl lineer hale
getirildiği gösterilmiştir. Daha sonra Born İteratif Yöntemi (BİY) ele alınmıştır. Aynı
zamanda Born iteratif yöntemi içerisinde, cisim fonksiyonunu bulmak için lineer ters
problem çözümünde kullanılan Tikhonov regülarizasyonuna da değinilmiştir.
Tezin ikinci kısmında ise lineer ters problem çözümü için son yıllarda önem kazanan
seyreklik yaklaşımı incelenmiştir. Görüntülenecek cismin görüntülenen bölgeye
göre oransal olarak küçük olması, ters saçılma probleminin seyreklik yaklaşımı
ile ele alınabilmesine olanak sağlamaktadır. Bu doğrultuda literatürde seyreklik
yaklaşımı çözümünde kullanılan NESTA, seyrek yaklaşıklıkta gradyen izdüşümü
(Gradient Projection for Sparse Recovery - GPSR), iki adımlı iteratif kısaltarak
eşikleme (TwoWay İterative Shrinkage Thresholding - TWIST), hızlandırılmış iteratif
kısaltarak eşikleme (Fast İterative Shrinkage Thresholding - FISTA) ve l2 normu
ile regülarize edilmiş uyarlamalı sert eşikleme(l2 Regularized İterative Method for
Adaptive Thresholding - L2IMAT) yöntemleri incelenmiştir. Yöntemler incelenirken
kullandıkları l1 veya l0 norm küçültmesine göre sınıflandırılmıştır. Bu yöntemler
BİY içerisine entegre edilerek BİY ile karşılaştırılmıştır. Karşılaştırmada gürültüye
karşı dayanıklılık, cisim boyutu ve şekli, birden çok cisim için yakınlık durumu,
görüntülenen cismin kenarlarının belirginliği ve sıkıştırılmış algılama özellikleri
göz önünde bulundurulmuştur. Seyreklik yaklaşımı yöntemlerinin küçük cisimlerde
yüksek çözünürlük verdiği ve gürültüye karşı daha dayanıklı olduğu sonuçlarla
görülmüştür.

Abstract:
In the electromagnetic theory, imaging burried object is called as inverse scattering
problem. Inverse scattering can be described as determining properties of burried
objects from their response to a known electromagnetic excitation. Some physical
and geometric properties such as shape, location, dielectric permitivity can be
reconstructed from inverse scattering theorem. Mathematical model of inverse
scattering problem has importance in optical, radar, acoustic, seismic and medical
imaging. Inverse scattering problem is non-linear and ill-posed equation. To linearize
it, Born and Rytov approximation methods are widely used. However, after the
linearization, inverse scattering problem is still ill-posed and there is no unique
solution. To deal with ill-posedness, there are many regularization techniques in
literature.
The measurement data , that is required to image the object, is obtained by applying
Moment Method. In the Born approximation, total electric field in the object is
assumed to be equal to the incident field. Since this method is valid for only weak
scatters. Born Iterative Method can be explained via three main step. First step is to
calculate the initial object function by using the Born Approximation. In the second
step, total electric field on the object is updated according to object function that is
found in first step. In the third step of this method, object function is updated by using
new total field that is result of second step. These steps are runned until convergence.
In this study, sparse approximation techniques are used to solve inverse scattering
problem. These techniques mainly solve linear inverse problem that is obtained after
born approximation.
In chapter 2, nature of inverse scattering problem is discussed and linearization with
Born approximation is shown. Then Born Iterative Method (BIM) is explained
extensively step by step. Also Tikhonov regularization technique is discussed within
Born ˙Iterative Method. ˙Inverse scattering problem resembles the properties of ill-posed
problems. These problems usually arise from pyhsical limitations of knowledge
about object. Physically ill-posed problems lead to computationally ill-conditioned
problems. So the solution for inverse scattering problem is higly sensitive to error.
Discretization and noise can be source of error. The computed solution for inverse
scattering problem oscilates strongly. To cope with this difficulty, any additional
knowledge of physical nature quantity of object is needed in order to make the solution
physically meaningful and possible correct. ˙It can be achieved by regularization
methods. For instance, in Tikhonov regularization l2 norm is added to cost function.
This lead l2 norm of minimizer of cost function must be little. In other words,
regularization reduce the solution space so as to truncate the oscilation. And also
l2 norm is not only the type of norm that used in regularization, l1 and l0 norm can also
be used in regularization to solve inverse scattering problem. If the object is sparse,
l1 or l0 norm regularization gives pyhsically meaningful and correct solution. Because
sparse object has lower l1 and l0 norm.
In chapter 3, sparse approximation methods that become a popular in recent years
are explained. Sparsity means that number of significant (nonzero) components are
relatively small compared to the signal length. If the imaging domain is sparse, sparse
approximation methods can work well for an imaging application. These methods
often use l0 and l1 norm minimization and this allows to hold significant components
while forcing other component to be zero. l0 norm are also explained mathematically
in this chapter, but briefly it can be assumed as a count of nonzero elements of signal.
l1 norm is the sum of absolute values of all elements in signal. Cost function of inverse
scattering problem is squared norm of residual error. Moreover it is also ill-posed
problem thus it requires regularization. Tikhonov method adds l2 norm of signal to
the cost function to regularize it. This can give analytical solution to the ill-posed
problem. Adding l0 and l1 norm to cost function doesn't give analytical solution to
the ill-posed problem. Because many different signals may have same l0 or l1 norm
value. Therefore regularizing the cost function with these norms provides solution
that minimizes squared norm of residual which is necessarily sparse. Because of this
property, l0 or l1 norm are useful in sparse approximation. The l2 norm regularization
term in the cost function enhances smoothness in the solution. At the same time, l2
regularized cost functions become inefficient when the sparsity or sharpness exist in
the search domain. Some microwave imaging areas include this type of search domain
such as through the wall imaging and radar imaging. The nature of l0 norm has discrete
structure so it makes the problem non-convex. l0 norm can be replaced by l1 norm
which is convex approximation of l0 norm. This makes problem convex. Eventually,
many convex optimization techniques can be used in sparse approximation.
Methods are classified according to the use of type of norm minimization. In this
study, NESTA, Gradient Projection for Sparse Recovery (GPSR), Two Way ˙Iterative
Shrinkage Thresholding (TWIST), Fast ˙Iterative Shrinkage Thresholding (FISTA) are
classified as l1 norm minimization and l2 Regularized ˙Iterative Method for Adaptive
Thresholding (L2IMAT) is classified as l0 norm minimization. NESTA and GPSR
algorithm aims to find gradient of l1 norm of signals to minimize cost function. NESTA
algorithm minimizes cost function by iteratively estimating three sequences xk, yk
and zk. At step k, yk is the current guess of the optimal solution. ˙Iterating only yk
corresponds only standart firs order technique. zk is the novelty which keeps in mind
the previous steps. This leads fast convergence of NESTA algorithm. Further, another
aspect of zk is use of proximal function. The proximal function doesn't allow zk go too
far away from the center. Main sequence xk is computed from weighted average of yk
and zk. yk includes Lipschitz constant of cost function and gradient of cost function.
In case zk consists Lipschitz constant of cost function, sum of previous gradient and
proximal function. NESTA uses Huber function that is smooth approximation of
l1 norm while computing gradient of l1 term in the cost function. GPSR involves
two type of algorithm, GPSR-Basic and GPSR-BB (BB stands for Barzilai-Borwein).
In this study, GPSR-Basic is used. GPSR-Basic iterates signal estimate along the
negative gradient and projects it onto the non-negative orthant, and then performs
backtracking process which ensures minimization of cost function. GPSR-Basic
utilizes non-negative description of l1 norm while calculating gradient of cost function.
After extracting l1 norm in the cost function , a new quadratic cost function can be
organized. GPSR-Basic loses time because of backtracking process. The bactracking
line search optimizes the best step size which satisfies the minimization of cost
funciton for GPSR-Basic algorithm. TWIST, FISTA and L2IMAT utilize Landweber
iteration to decrease squared norm of residual. Landweber iteration is a special case
of gradient descent algorithm. Briefly, they find new signal estimation by applying
threshold function to the result of Landweber iteration. This method is also called
truncated Landweber iteration. TWIST and FISTA methods use previous computed
values in their iteration. TWIST method applies threshold function twice in each
iteration. Two step in TWIST comes from Iterative Reweighted Shrinkage and Two
Step Method for Linear Systems. Iterative Reweighted Shrikage algorithm finds a
linear representation for shrinkage problem while using diagonal matris that consists
non-negative components of signal. After this linear represantation used in Two Step
Method for Linear Systems, TWIST algorithm is obtained. FISTA method is an
accelareted version of ˙Iterative Shrinkage Thresholding Algorithm (ISTA), it updates
both previous and older computed values. In FISTA and TWIST method, hard and soft
threshold function can be used for shrinkage. In this study, soft threshold function is
used for both methods. Soft thresholding technique corresponds l1 minimization while
hard thresholding corresponds l0 minimization. The threshold value plays key role in
the accuracy of methods that use hard threshold function. By keeping threshold value
larger, hard threshold function can discard significant elements but it may produce
good results against noise factor. On the other hand, by keeping threshold value
smaller, hard threshold function picks all siginificant elements but it may produce bad
results against noise factor.
In this thesis, NESTA, GPSR, TWIST, FISTA and L2IMAT methods are replaced
with Tiknonov regularization while finding object function in Born Iterative Method.
This leads positive impact on the result of imaging small object for Born Iterative
Method. To show this improvement, some tests like noise resistance, resolution on
closely located objects and edge preserving are applied to BIM-NESTA, BIM-TWIST,
BIM-FISTA, BIM-GPSR, BIM-L2IMAT and BIM. And also l1 and l0 norm
regularization techniques enable recovery of signal after Compressive Sensing (CS)
application. Compressed Sampling based on obtaining signal from fewer measurement
unlike the Nyquist sampling. Two conditions must be satisfied in order to apply CS to
a given problem. First, the signal to be reconstructed must be sparse and the sensing
matrix must be incoherent. According to the CS theory, a randomized sensing matrix
allows compression of the measurement, hence reducing the amount of measurements.
Randomized matrix has low coherence and that leads preserving nature of sparsity of
imaging domain so that it gives same results despite reduction. After all of these, the
simple idea in CS theory that measurements should not match signal's structure at all,
the measurement should look like random noise in order to apply CS. A sparse signal
can be shown in another transform domain. Basis for this transform domain called
sparsifying basis. In our simulation, we have a priori knowledge about sparsity of
search domain so that we use identity matrix instead of sparsifying basis. So that our
sensing matrix is made up of system modelling matrix that includes green coefficients
and total field and random matris that is used for sampling. We choose sampling
matrix as a random i.i.d gaussian matrix to hold incohorency of sensing matrix. After
multiplying both measurement vector and system modelling matrix with random i.i.d
gaussian matrix, we reduce the data size of linear system. In the CS theory, there must
be at least 4 times incoherent samples for each significant component in a sparse signal
so as to recover signal form reduced measurement. According to this, we reduce 400
measurements to 100 measurements in our simulation.