Yapay açıklıklı radar görüntüleme algoritmalarının interpolasyon kullanmaksızın gpu üzerinde gerçeklenmesi
Realization of interpolation-free synthetic aperture radar imaging algorithms by using gpu
Yazar: ÖZGÜR ALTUN
Danışman: PROF. DR. SELÇUK PAKER
İstanbul Teknik Üniversitesi / Bilişim Enstitüsü / İletişim Sistemleri Ana Bilim Dalı / Uydu Haberleşmesi ve Uzaktan Algılama Bilim Dalı
Derece: Yüksek Lisans, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Bilim ve Teknoloji = Science and Technology ; Savunma ve Savunma Teknolojileri = Defense and Defense Technologies
Dizin: Paralel programlama = Parallel programs ; Radar görüntüleri = Radar images ; Sentetik açıklık radarı = Synthetic aperture radar ; Uydu görüntüleri = Satellite images

Özet:
Yapay Açıklıklı Radar (Synthetic Aperture Radar ? SAR) sistemleri, görüntülenmek istenen bir hedef veya bölge üzerine farklı açılardan geniş bandlı ve yüksek frekanslı darbeler gönderip, elde edilen yansımaların sentezlenmesi ile yüksek çözünürlüklü görüntü elde edilmesi için dizayn edilirler. SAR sistemlerinde görüntünün elde edilebilmesi için gönderilen geniş bandlı darbelerin toplanarak çözümlenmesi ve dijital olarak işlenmeye hazır ham verinin elde edilmesi gerekmektedir. Elde edilen ham veri içerisinde genlik ve faz değerleri bulunan iki boyutlu bir matris olarak ifade edilmektedir. ?Iki boyutla ifade edilen ham verinin boyutlarından biri görüntüleme işlemi sırasında radarın hareket doğrultusu olan çapraz-menzil (azimuth) doğrultusunu, diğeri ise platformun hareket doğrultusuna dik olan menzil (range) doğrultusunu temsil etmektedir. Azimuth ve range doğrultularında elde edilen veriler, elde edilecek görüntünün çözünürlüğünün arttırılması hususuna doğrudan etki eden parametrelerdir.
SAR görüntüleme sistemlerinde, radar tarafından toplanan ve içerisinde hedefe gönderilip geri alınan işaretlerin genlik ve faz bilgilerini içeren iki boyutlu ham veri dijital olarak işlenerek görüntüye çevrilirler. Bu amaç doğrultusunda geliştirilen SAR görüntüleme algoritmaları SAR sistemi tarafından sunulan ham görüntü verilerini hem range hem de azimuth ekseninde işleyerek sonuç görüntüsünün oluşmasını sağlarlar. 
SAR görüntüleme algoritmaları Fourier dönüşümleri, bir boyutlu veya iki boyutlu filtreleme operasyonları ve interpolasyon adımlarından oluşmaktadır. Interpolasyon sürecinin uygulanması bilinmeyen bir noktanın tahminine dayalı olduğundan uygulama sonucunda belirli bir oranda hata görülmektedir. Buna göre algoritma içerisinde kullanılan interpolasyonun çeşidine göre radar görüntüsünün kalitesi de değişmektedir. SAR görüntüleme algoritmalarında interpolasyon işlemine ihtiyaç duyulmasının iki temel sebebi bulunmaktadır. Bunlardan birincisi kartezyen olmayan noktalarda elde edilen verilerin, kartezyen noktalar üzerine taşınmasını sağlamaktır. Diğeri ise, azimuth ekseninde yapılacak olan işlemlerin range ekseninde yapılan işlemlere bağımlı olmasından dolayı ayrıştırılamaması ve interpolasyon gibi bir dönüşüm sürecine ihtiyaç duyulmasıdır.
Yapılan tez çalışması kapsamında, SAR görüntüleme algoritmalarının uygulanmasından sonra elde edilen görüntünün üzerindeki hata miktarının minimum seviyeye indirilmesi ve doğruluğun arttırılması için algoritma akışında yer alan interpolasyon sürecinin kaldırılarak yerine eş değer bir operasyon olarak düzenlenen Paralel Ayrık Fourier Dönüşümü (Parallel Discrete Fourier Transform ? P-DFT) operasyonunun uygulanması sağlanmıştır. Ayrık Fourier Dönüşümü?nün paralel olarak işletilmesi Grafik?I şlem Birimi (Graphical Processing Unit ? GPU) üzerinde gerçekleştirilmiş ve sonuçların Merkezi ?I şlem Birimi (Central Processing Unit ? CPU) üzerinde yapılan paralelleştirme ile karşılaştırılması sağlanmıştır.
Yapılan tez çalışması Range Doppler Algoritması (Range Doppler Algorithm ? RDA) içersinde bulunan menzil hücre göçü üzeltmesi adımı üzerinde ve Bilgisayar Destekli Tomografi (Computer Aided Tomography ? CAT) algoritmasının işletimi sırasında kutupsal koordinat sisteminden kartezyen sisteme dönüşümün sağlandığı adım üzerinde uygulanmıştır. Yapılan test çalışmalarında RDA ve CAT algoritmaları hem interpolasyon hem de P-DFT kullanılarak gerçeklenmiştir. RDA ve CAT algoritmalarının interpolasyon ve P-DFT kullanılarak gerçeklenmesi işlemi de hem CPU hem de GPU üzerinde ayrı ayrı olarak gerçeklenmiştir. Bu işlemler sonrasında paralel olmayan çözüme göre zaman yönünden avantaj sağlamıştır. Bunun yanısıra interpolasyon uygulanmasının sonucunda elde edilen görüntü üzerine etkiyenbozulmalar açıkça görülmektedir. Bu kapsamda P-DFT?nin hem CPU hem de GPU üzerinde işletilmesi paralel interpolasyon uygulaması sonuçlarına göre hem zaman hem de doğruluk yönünden avantaj sağlamıştır. Ayrıca görüntüde bulunan veri sayısının artmasıyla oluşturulan uygulamanın daha hızlı sonuç üretilmesi bağlamında GPU üzerinde P-DFT uygulaması zaman yönünden büyük avantaj sağlamaktadır.

Abstract:
Synthetic Aperture Radar (SAR) is a kind of high-resolution radar which can be applied widely in remote sensing and to acquire information about the Earth's surface from radar signals gathered by a moving platform such as an aircraft. In order to produce high-resolution image in a SAR system, obtained signals must be modulated and raw data should be generated which will be used to produce high-resolution image. The obtained raw data is expressed as a two dimensional matrix which keeps the amplitude and phase values of the signal. One of the dimensions of this matrix is azimuth direction which is parallel direction to the radar flight path while scanning the area or object. The other dimension of this matrix is range direction which is perpendicular to azimuth direction. Both azimuth and range direction are the key parameters that directly affect to increase the resolution of the radar image. Besides of this, this raw data includes complex valued
In the SAR imaging system, the resultant image is acquired by applying digital processing techniques to the SAR raw data. In order to acquire an image, many SAR imaging algorithm are developed by the researchers. These algorithms process the raw data digitally on both azimuth and range direction and produce the resultant data which is interpretable as an image by using special programs. But, because of the complex form of the radar signal and intensive floating-point operations, producing high-resolution requires more computations times.
General SAR imaging algorithm includes Fourier transformation, one and two dimensional filtering operations and interpolation step. Almost all interpolation process results with computation errors because of the pointwise convergence. Besides of this, the 2-D complex valued interpolation also needs extra processing because of ambiguous search operation. For this reason, in order to increase the quality of the resultant image we should use an interpolation which produces minimum computation error while processing the data.  There are two main reasons that require applying an interpolation process in the SAR imaging algorithm. One of these reasons is mapping the non- Cartesian coordinated point onto Cartesian coordinated point. The data, which are obtained by radar, don't have equal distance according to each other as both linearly and radially. Therefore, Fast Fourier Transform (FFT) operation cannot be applied to the data in order to perform processing quickly. In order to provide applying FFT operation to the data while processing SAR image algorithms, the data must be expressed in Cartesian coordinated system. For this reason, the data which are expressed on non-Cartesian coordinate system must be mapped to the Cartesian coordinate system. The other one is the operations which are realized on the azimuth axis are depends on the operations which are realized on the range axis. Therefore, these operations cannot be separated and requires a transformation process like an interpolation.
In order to realize the interpolation process for our system, we use nearest n neighbor and weighted nearest n neighbor interpolation method to regulate the position of the points in the radar image. Nearest n neighbor interpolation process is used to determine desired number of nearest points according to selected reference point in the whole data. To do this, all data should be scanned and corresponding points must be determined. After that, average of the point values must be calculated to update the reference point with this calculation result. Similar process must be performed for all chosen data respectively. In weighted interpolation method, weights of the chosen neighbors are determined according to the distance to the reference point and apply to the data in order to update the reference point value with the result of the multiplication of the neighbor's value and its determined weight value. Therefore, mentioned methods takes very long time. On the other hand, the interpolation operation results with calculation errors because of the pointwise convergence.
In this thesis study, in order to minimize the error and increase the accuracy of the resultant image data which is obtained after applying SAR imaging algorithms, we have applied an equivalent operation, which is named Parallel Discrete Fourier Transform (P-DFT), instead of interpolation process.  While processing the SAR image algorithm, the Cartesian points places can be calculated analytically and the values on this Cartesian points can be calculated by using Discrete Fourier Transform (DFT) operation. In our work, DFT and Inverse Fast Fourier Transform (IFFT) operation have been applied respectively to get rid of the interpolation process.  Actually, Discrete Fourier Transform (DFT) operation is a costly operation and has been applied at the expense of the additional computation cost. Therefore, GPU have been used to parallelize the DFT operation to perform this operation as fast as possible.
The main aim in the SAR processing concept is performing all operation as fast as possible. Generally, real time processing of SAR images can be performed on Digital Signal Processor (DSP) and Field Programmable Gate Array (FPGA) systems. Due to difficulties of programming and debugging processes on DSP and FPGA other programming environment options should be considered. For this reason, applications of SAR processing have been performed on the other processing environments such as CPU and GPU platforms. At this point, parallelization of process provides us very big advantage to accelerate the processing of the algorithm. One of novel technique for SAR image processing is using Graphical Processing Unit (GPU) to obtain the high computation rate.
GPU is the one of the technology which has widely usage area in processing intensive data. In the GPU computing, CPU and GPU are used together in a heterogeneous co-processing computing model. In general, sequential operations are processed on CPU and parallel processing of data and acceleration are processed on GPU. To develop an application on the GPU several programming language have been produced. In our work, The Compute Unified Device Architecture (CUDA) programming interface produced by NVDIA are used for developing application to perform our proposed algorithm on the GPU. CUDA programming interface is integrated into C programming language and called as CUDA C.
Our study have been applied on Range Cell Migration Correction (RCMC) step of Range Doppler Algorithm (RDA) and the step which is provide transformation from polar coordinate system to Cartesian coordinate system while processing Computer Aided Tomography (CAT) algorithm.  In our work, to show the performance of our system, RDA and CAT have been applied by using interpolation and P-DFT method in parallel. The parallelization of DFT has been performed both on GPU and CPU. Besides of this, we also performed the interpolation operation in parallel both on GPU and CPU. Although the interpolation operation could be realized by using parallel processing, the errors caused by applying interpolation would still remain on the results. Obtained results show us, performing P-DFT on GPU is faster than the interpolation. On the other hand, the obtained results provided by P-DFT are more accurate than interpolation. The results also show us processing on GPU improves the performance of the used algorithm. We have tested used algorithms with different data size. Our results show us, the processing time is growing considerably while the data size is increasing. We can clearly determine that performing P-DFT algorithm on GPU is more suitable in order to process SAR data fast and get more accurate results.