##
Mikrodalga Görüntülemede Seyreklik Yaklaşımı Yöntemlerinin Uygulanması

Mikrodalga Görüntülemede Seyreklik Yaklaşımı Yöntemlerinin Uygulanması

##### Dosyalar

##### Tarih

2017-01-9

##### Yazarlar

Yalçın, Emre

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

Institute of Science and Technology

Institute of Science and Technology

##### Ö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.

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.

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.

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2016

Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2016

Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2016

##### Anahtar kelimeler

Seyreklik Yaklaşımı,
Ters Saçılma,
Nesta,
Fısta,
Bıy,
L2ımat,
Twıst,
Sparse Approximation,
Inverse Scattering Problem,
Nesta,
Fista,
Bim,
L2imat,
Twist