Mathematics and Computer Science Emory University

Mathematics And Computer Science Emory University-Free PDF

  • Date:08 Oct 2020
  • Views:0
  • Downloads:0
  • Pages:11
  • Size:6.40 MB

Share Pdf : Mathematics And Computer Science Emory University

Download and Preview : Mathematics And Computer Science Emory University

Report CopyRight/DMCA Form For : Mathematics And Computer Science Emory University


Large Scale Image Deblurring in Java,Piotr Wendykier and James G Nagy. Dept of Math and Computer Science Emory University Atlanta GA USA. piotr wendykier emory edu nagy mathcs emory edu, Abstract This paper describes Parallel Spectral Deconvolution PSD Java soft. ware for image deblurring A key component of the software JTransforms is the. first open source multithreaded FFT library written in pure Java Benchmarks. show that JTransforms is competitive with current C implementations including. the well known FFTW package Image deblurring examples including perfor. mance comparisons with existing software are also given. 1 Motivation, Instruments that record images are integral to advancing discoveries in science and. medicine from astronomical investigations to diagnosing illness to studying bacte. rial and viral diseases 1 2 3 Computational science has an important role in improv. ing image quality through the development of post processing image reconstruction. and enhancement algorithms and software Probably the most commonly used post. processing technique is image deblurring or deconvolution 4 Mathematically this is. the process of computing an approximation of a vector xtrue which represents the true. image scene from the linear inverse problem,b Axtrue 1. Here A is a large usually ill conditioned matrix that models the blurring operation. is a vector that models additive noise and b is a vector representing the recorded image. which is degraded by blurring and noise, Generally it is assumed that the blurring matrix A is known at least implicitly.
but the noise is unknown Because A is usually severely ill conditioned some form of. regularization needs to be incorporated 5 6 Many regularization methods including. Tikhonov truncated singular or spectral value decomposition TSVD and Wiener. filter compute solutions of the form xreg A r b where A r can be thought of as. a regularized pseudo inverse of A The precise form of A r depends on many things. including the regularization method the data b and the blurring matrix A 4 The. actual implementation of computing xreg can often be done very efficiently using fast. Fourier transforms FFT and fast discrete cosine transforms DCT. This paper describes our development of Parallel Spectral Deconvolution PSD 7. Java software for image deblurring including a plugin for the open source image pro. cessing system ImageJ 8 A key component of our software is the first open source. multithreaded FFT library written in pure Java which we call JTransforms 7. Research supported by the NSF under grant DMS 05 11454. This paper is organized as follows In Section 2 we describe some basic image de. blurring algorithms and how fast transforms such as FFTs and DCTs can be used for. efficient implementations Section 3 describes the performance of our Java implementa. tions with a particular focus on JTransforms Benchmarks show that our multithreaded. Java approach is competitive with current C implementations including the well known. FFTW package 9 Image deblurring examples including performance comparisons. with existing software are also given,2 Deblurring Techniques. The deblurring techniques considered in this paper are based on filtering out certain. spectral coefficients of the computed solution,2 1 Regularization by Filtering. We begin by showing why regularization is needed and how it can be done through. spectral filtering To simplify the discussion we assume A is an n n normal matrix. 10 meaning that it has a spectral value decomposition SVD 1. where is a diagonal matrix containing the eigenvalues of A Q is a matrix whose. columns qi are the corresponding eigenvectors Q is the complex conjugate transpose. of Q and Q Q I We assume further that the eigenvalues are ordered so that 1. 2 n 0 Using the spectral decomposition the inverse solution of. equation 1 can be written as,xinv A 1 b A 1 Axtrue xtrue A 1 xtrue qi. where b Q That is the inverse solution is comprised of two terms the desired. true solution and an error term caused by noise in the data To understand why the. error term usually dominates the inverse solution it is necessary to know the following. properties of image deblurring 4 5, Assuming the problem is scaled so that 1 1 the eigenvalues i decay to. and cluster at 0 without a significant gap to indicate numerical rank. The eigenvectors qi corresponding to small i tend to have more oscillations than. the eigenvectors corresponding to large i, These properties imply that the high frequency components in the error are highly mag.
nified by division of small eigenvalues The computed inverse solution is dominated by. We realize that SVD usually refers to singular value decomposition We do not think there. should be any confusion because our discussion of filtering can be done using the singular. value decomposition in place of the spectral value decomposition. these high frequency components and is in general a very poor approximation of the. true solution xtrue, In order to compute an accurate approximation of xtrue or at least one that is not. horribly corrupted by noise the solution process must be modified This process is. usually referred to as regularization 5 6 One class of regularization methods called. filtering can be formulated as a modification of the inverse solution 5 Specifically a. filtered solution is defined as,xreg A r b 2, where A r Q diag Q The filter factors i satisfy i 1 for. large i and i 0 for small i That is the large eigenvalue low frequency com. ponents of the solution are reconstructed while the components corresponding to the. small eigenvalues high frequencies are filtered out Different choices of filter factors. lead to different methods popular choices are the truncated SVD or pseudo inverse. Tikhonov and Wiener filters 5 6 11,2 2 Tikhonov Filtering. To illustrate spectral filtering consider the Tikhonov regularization filter factors. where the scalar is called a regularization parameter and usually satisfies n. 1 Note that smaller lead to more i approximating 1. The regularization parameter is problem dependent and in general it is nontrivial. to choose an appropriate value Various techniques can be used such as the discrep. ancy principle the L curve and generalized cross validation GCV 5 6 There are. advantages and disadvantages to each of these approaches 12 especially for large. scale problems In this work we use GCV which using the SVD of A requires finding. to minimize the function,X 2 bbi X 2, where bb Q b Standard optimization routines can be used to minimize G. Tikhonov filtering and using GCV to choose regularization parameters has proven. to be effective for a wide class of inverse problems Unfortunately for large scale prob. lems such as image deblurring it may not be computationally feasible to compute the. SVD of A One way to overcome this difficulty is to exploit structure in the problem. 2 3 Fast Transform Filters, In image deblurring A is a structured matrix that describes the blurring operation and.
is given implicitly in terms of a point spread function PSF A PSF is an image of a. point source object and provides the essential information to construct A The structure. of A depends on the PSF and on the imposed boundary condition 4 In this subsection. we describe two structures that arise in many image deblurring problems However due. to space limitations we cannot provide complete details the interested reader should. see 4 for more information, If the blur is assumed to be spatially invariant then the PSF is the same regardless. of the position of the point source in the image field of view In this case if we also. enforce periodic boundary conditions then A has a circulant matrix structure and the. spectral factorization, where F is a discrete Fourier transform DFT a d dimensional image implies F is a. d dimensional DFT matrix In this case the matrix F does not need to be constructed. explicitly a matrix vector multiplication Fb is equivalent to computing a DFT of b and. similarly F b is equivalent to computing an inverse DFT Efficient implementations of. DFTs are usually referred to as fast Fourier transforms FFT The eigenvalues of A. can be obtained by computing an FFT of the first column of A and the first column of. A can be obtained directly from the PSF Thus the computational efficiency of spec. tral filtering methods for image deblurring with a spatially invariant PSF and periodic. boundary conditions requires efficient FFT routines. If the image has significant features near the boundary of the field of view then. periodic boundary conditions can cause ringing artifacts in the reconstructed image. In this case it may be better to use reflexive boundary conditions But changing the. boundary conditions changes the structure of A and it no longer has the Fourier spectral. decomposition given in equation 5 However if the PSF is also symmetric about its. center then A is a mix of Toeplitz and Hankel structures 4 and has the spectral value. decomposition, where C is the discrete cosine transform DCT matrix a d dimensional image implies. C is a d dimensional DCT matrix As with FFTs there are very efficient algorithms for. evaluating DCTs Furthermore computations such as the matrix vector multiplication. Cb and CT b are done by calling DCT and inverse DCT functions The eigenvalues. of A can be obtained by computing a DCT of the first column of A and the first. column of A can be obtained directly from the PSF Note that in the case of the FFT. F has complex entries and thus computations necessarily require complex arithmetic. However in the case of the DCT C has real entries and all computations can be done. in real arithmetic, Efficient FFT and DCT routines are essential for spectral deblurring algorithms. The next section describes our contribution to the development of efficient parallel Java. codes for these important problems,3 Using Java for Image Deblurring.
Java is ideally suited to provide efficient open source image deblurring software that. can be used in inexpensive imaging devices for point of care medical applications Java. implementations are available for virtually all computing platforms and since May. 2007 the source code of Java is distributed under the terms of the GNU General Pub. lic License Moreover Java has native support for multithreaded programming which. has become a mandatory paradigm in the era of multicore CPUs Finally sophisticated. imaging functionality is built into Java allowing for efficient visualization and anima. tion of computational results, Significant improvements have been made to Java since the 1996 release of JDK 1 0. including Just In Time compilation memory allocation enhancements and utilization. of performance features in modern x86 and x64 CPUs 13 It is no longer the case that. Java is too slow for high performance scientific computing applications this point is. illustrated below for spectral image deblurring, There are disadvantages to using Java in scientific computing including no prim. itive type for complex numbers an inability to do operator overloading and no sup. port for IEEE extended precision floats In addition Java arrays were not designed for. high performance computing a multi dimensional array is an array of one dimensional. arrays making it difficult to fully utilize cache memory Moreover Java arrays are not. resizable and only 32 bit array indexing is possible Fortunately open source numerical. libraries such as Colt 14 have been developed to overcome these disadvantages For. our work we are implementing a fully multithreaded version of Colt which we call. Parallel Colt 7, In the rest of this section we describe Java implementations of JTransforms ImageJ. and associated plugins for image deblurring,3 1 JTransforms. Fast Fourier Transform An FFT algorithm is the most efficient method to compute. a DFT with a complexity of N log N to compute a DFT of a d dimensional array. containing N components An FFT algorithm was first proposed by Gauss in 1805. 15 but it was the 1965 work by Cooley and Tukey 16 that is generally credited for. popularizing its use The most common variant of the algorithm called radix 2 uses. a divide and conquer approach to recursively split the DFT of size N into two parts of. size N 2 Other splittings can be used as well including mixed radix and split radix. algorithms 17, Th split radix algorithm has the lowest arithmetic operation count to compute a.
DFT when N is a power of 2 18 The algorithm was first described in 1968 by Yavne. 19 and then reinvented in 1984 by Duhamel and Hollmann 20 The idea here is to. recursively divide a DFT of size N into one DFT of size N 2 and two DFTs of size N 4. Further details about split radix algorithm can be found in 17. Parallel Implementation in Java JTransforms is the first open source multithreaded. FFT library written in pure Java The code was derived from the General Purpose FFT. Package OouraFFT written by Ooura 21 OouraFFT is a multithreaded implementa. tion of the split radix algorithm in C and Fortran In order to provide more portability. both Pthreads and Windows threads are used in the implementation Moreover the code. is highly optimized and in some cases runs faster than FFTW Even so the package has. several limitations arising from the split radix algorithm First of all the length of the. input data has to be a power of two Second the number of computational threads must. TR 2008 002 Large Scale Image Deblurring in Java by Piotr Wendykier James Nagy Mathematics and Computer Science EMORY UNIVERSITY Large Scale Image Deblurring in Java Piotr Wendykier and James G Nagy Dept of Math and Computer Science Emory University Atlanta GA USA piotr wendykier emory edu nagy mathcs emory edu Abstract Thispaperdescribes ParallelSpectralDeconvolution PSD Javasoft

Related Books