مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Object Reconstruction From Fourier Magnitude Information Only A.J. Tawfiq, F.N. Hassan, and A. T. Mohammed Department of Astronomy, College of Science, University of Baghdad Received in: 5 June 2011 ,Accepted in:11October2011 Abstract Reconstruction an object from its Fourier magnitude has taken a great deal in the literature and there is still no obvious solution for the failure of this algorithm. In this paper, the frequent failure of the phase retrieval is discussed in details and it has been shown that when the object is cento-symmetric, the object support is vital element to ensure uniqueness while for asymmetric object; the asymmetric support of the object is not enough to ensure uniqueness but the reconstruction appear to include most of the information of the original object. This is also true for the reconstruction of a complex function. Keywords: Fourier t ransform, complex zero location, phase retrieval, objects reconstruction Introduction The problem of phase retrieval (magnitude- reconstruction only) has attracted a great deal of attention in the literature and still many questions remain unanswered. Phase retrieval involves finding the phase of a complex wave field when only the intensity (or its positive square root) is known. For further background on the subject, the reader is referred to a review by the following papers [1-6]. Exact solutions based upon polynomial models for the wave field and either factorization or complex zero location [5] encounter computational difficulties with large images and have limited stability in the presence of noise. The method based upon zero location has the distinct advantage that it generates all possible solutions and provides a means of testing for uniqueness. Iterative algorithms for phase retrieval are well established [2,3,4] but their performance is often poor, particularly if no additional constraints can be placed upon the solution. Many attempts have been made to enhance the performance of phase retrieval technique. Numerical investigation to the uniqueness of phase retrieval was studied extensively using gradient search [7]. Additional step such as using support constraint and low resolution image in connection with error reduction algorithm are used to retrieve the Fourier phase of a complex function [8,9]. An algorithm for reconstruction a symmetric three dimensional image from its Fourier intensity in the case of crystallographic problem is presented in [10]. Another approach was made to formulate the phase retrieval problem with mathematical care to establish new connections between well established numerical phase retrieval schemes and classical convex optimization methods [11]. A projection-based method, the Hybrid projection reflection (HPR) algorithm was proposed for solving phase retrieval problem [12]. The difficulties associated with phase retrieval algorithm and how to solve such problem using adaptive optics is described in [13]. Prior discrete Fourier transform (PDFT) spectral estimation technique was proposed to reconstruct signals from incomplete data [14]. The third-order intensity correlations from the data set of measured intensities for each distance triplet were calculated to reconstruct astronomical images [15]. Taking derivation of the field autocorrelation holography with extended reference allows direct reconstruction of a complex object from measurement of its franhofer diffraction pattern [16]. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 A Fourier heighted projection is proposed to tackle the problem of far-field measurement that associated with the coherent lensing imaging [17]. Finally a Fourier domain Wiener filter for the reconstruction of under sampled imagery is proposed [18]. This filter is depending on a net transfer function that characterizes the combined effects of the imaginary system and reconstruction process. Although many attempts have been made to solve the problem, phase retrieval in practice is far from easy. The work described in this paper tackles the frequent failure of iterative algorithms to converge to the correct solution [3]. Furthermore, relatively little attention has been paid to the reconstruction of specifically complex images. Theory In one dimension it is well known that the Fourier magnitude is non-unique, i.e. there exists many functions f(x) with the same Fourier magnitude |F(u)|, where:  b a dxiuxxfuF )exp()()( (1) and [a,b] is the support of f(x). In practice, iterative schemes for phase retrieval in one dimension almost always fall to converge to the required solution [5]. This is attributed that if the polynomial function describing the field from uniformly illuminated object, then in one dimension this polynomials can always be factorized over the field of complex numbers and this will produce well known ambiguities. In two dimensions, the Fourier magnitude |F(u,v)| is uniquely specifies an image f(x,y), where   12 )](2exp[),(),( S dxdyvyuxiyxfvuF  (2) and S12 is the support of f(x,y). Since |F | is identical to |F  | (where an asterisk denotes complex conjugation), Fourier magnitude data alone is insufficient to distinguish between the two. Consequently there is at least a two-fold ambiguity in magnitude-only reconstruction of the image f(x,y). Both f(x,y) and f(-x,-y) have the same Fourier magnitude. Similarly, the magnitude is unaffected by a multiplicative linear phase factor. The corresponding reconstructed image is a shifted version of the original. Alternative images of this kind having the same Fourier magnitude as the required solution are usually classed as trivial ambiguities. Uniqueness is usually taken to mean that only f(x,y) or its trivial ambiguities are consistent with |F(u,v)|. Specifically, the trivial ambiguities refer to f(-x,-y). i.e., the image is reflected through the origin, as well as it is shifted version of the original image. For a centro-symmetric image: ),(),( yxfyxf  (3) and |F(u,v)| is truly unique. In the following text, an image that is not centro-symmetric is referred to as an asymmetric image, for which: ),(),( yxfyxf  (4) مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 and there exists a two – fold ambiguity . It has often been assumed that there is no clear connection between the expectation of uniqueness and the success of iterative algorithms [4]. However, the results presented in this paper indicate a direct link between the absence of trivial ambiguities and successful reconstruction. Iterative phase retrieval as discussed in this paper refers to a generalization of the Gerchberg-Saxton algorithm [19] known as the error-reduction algorithm [3] as shown in the block diagram that illustrated in Fig.(1). The latest estimate of the image is Fourier transformed, and the calculated Fourier magnitude replace by the known (true) magnitude. The modified Fourier data (the true magnitude and the estimated phase) are inverse Fourier transformed, and the known support of the image is imposed. The procedure is repeated until the estimate of the image is sufficiently close to the original. In two dimensions, the exact support of the image cannot be deduced from the autocorrelation function and the support constraint tends to be weak. It is generally accepted that if the support constraint is tightened, then the convergence is improved. The support of the object could be imposed according to the following equation:          syx syxyxg yxg k k ),(0 ),(),( ),( ' 1 (5) k represents number of iterations. An improved algorithm that can be used to speed up convergence is the hybrid input- output algorithm [3] as shown in Fig.(2). The Fourier transform, the Fourier domain constrains, and the inverse transform are classed as a single system have an input and an output. The (k+1) th input is equal to the previous input wherever the image domain constraints are satisfied, and equal to the previous input less some fraction of the output. The new input is no longer simply the best estimate of the image, but is an attempt to drive the next output in the right direction. Results and Discussion Before we start the study of frequent failure of magnitude only reconstruction algorithm, let us begin with the reconstruction from using Fourier phase information. Fig.(3) shows the importance of the Fourier phase than Fourier magnitude in image reconstructions. Fig.(4 e,f,g,h) show the reconstructions of centro-symmetric images using exact centro- symmetric support. In this case, the Fourier phase is particularly simple; it assumes values of only 0 or π. The reconstruction is successful using exact support. This is explained by noting that for a centro-symmetric image, the two permissible solutions (corresponding to F and F ) are identical. While, the reconstruction is fail to converge if the cento- symmetric support is taken slightly bigger or smaller than the exact radius. Now, let us start changing the symmetry of the object. If the same centro-symmetric support is used through the image f(x,y) is not centro-symmetric. The reconstruction fails even if we imposed the exact support constraint. The two possible solutions are no longer identical, the algorithm is unable to converge on either one of them, and the reconstruction appears to be a confused mixture of the two. Even through uniqueness to within a trivial ambiguity is assured (readily achieved by means of Eisenstein's criterion [5], the support constraint is insufficient to ensure true uniqueness as shown in Fig.(5). Fig.(6) shows an original real positive image and its reconstruction when exact asymmetric support was imposed. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Now, let us extend our study to include the reconstruction of a complex function. The complex data is generated by assuming its real and imaginary are centro-symmetric functions as shown in Fig.(7 b & c). This function is Fourier transformed and its absolute function represent the estimates Fourier magnitude. The reconstruction using exact support for the real and imaginary parts are shown in Fig.(7 g&j). The results bear most of the information of the complex function but not converge to the required solution. Now if we changinge the symmetry of this complex function, the reconstruction is shown in Fig.(8). Finally, it should be pointed out here that the number of iterations that used for all the reconstructions is 100. Conclusions The reconstruction is good in sharp contrast. When rectangular or circular support constraints are used, the reconstruction is failed to converge by iterative means even when the additional constraints of reality and positivity are used. However, when an exact and asymmetric support is used, the reconstruction converges quickly to the required solution. The results presented above suggest that the convergence is significantly better if the support is asymmetric and specifically excludes one of the trivial ambiguities, namely the image reflected through the origin. It is sometimes thought that the constraints of reality and positivity are important in iterative reconstruction of real positive images. However, it is shown that it is the support constraint which most affects the likelihood of convergence, and good results are obtained with complex images. Reference 1. Bates, R. H. T. (1984), Uniqueness of Solutions to two- dimensional Fourier phase problem for localized and positive images, Computer vision Graphics and Image Processing, 25(2): 205-217. 2. Fienup, J. R. (1978), Reconstruction of an object from the modulus of its Fourier Transforms, Opt. let. 3:27-29. 3. Fienup, J. R. (1982), Phase retrieval algorithms: a comparison, Appl. Opt. 21:2758-2769. 4. Fienup, J. R. and Wackerman, C. C. (1986), phase Retrieval Stagnation problems and solutions, J. Opt. Soc. Am. A, 3: 897-1907. 5. Fiddy, M. A; Brames, B. J. and Dainty, J. C. (1983), Enforcing irreducibility for phase retrieval in two dimensions, Opt. Lett. 8: 96-98. 6. Dainty, J. C. and Fiddy, M. A.(1984), The essential role of Prior Knowledge in phase retrieval, Optica Acta, 31(3):325-330. 7. Seldin, J. H. and Fienup, J. R. (1990), Numerical investigation of the uniqueness of phase retrieval, J. Opt. Soc. Am. A, 7( 3):412. 8. Fienup, J. R. (1987), Reconstruction of a complex valued object from the modulus of its Fourier transform using a support constraint, J. Opt. Soc. Am. A, 4(1): 118-123. 9. Fienup, J.R. and Kowalczyk, A.M.,(1990), Phase retrieval for a complex- valued object by using a low-resolution image, J. Opt. Soc. Am. A., 7(3):450. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 10. Millane, R. P. and Strond, W. J., (1997), Reconstruction symmetric images from their under sampled Fourier intensities, J. Opt. Soc. Am. A, 14:568- 579. 11. Bauschke, H. H. Combettes, P. L. and Luke, D.R., (2002), Phase retrieval, error reduction algorithm, and Fienup variants: a review from convex optimization, J. Opt. Soc. Am. A,19:1334-1345. 12. Bauschke, H. H. , Combettes, P. L., and Luke, D.R., (2003), Hybrid projection-retlection methods for phase ", J. Opt. Soc. Am. A,20:1025-1034. 13. Fienup, J. R. (2003), Phase retrieval: Habble and James Webb spase Telescope, Internal report submitted to the university of Rochester Institute of Optics. 14. Shieh, H. M.; Testorf, M.; Byrne C. L. and Fiddy, M. A. (2006), Iterative image Reconstruction using prior knowledge, .J. Opt. Soc. Amer. A , 23: 1292-1310. 15. Zhilyaev, B. E.(2008),Bispectral technique for reconstruction the astronomical images with an intensity interferometer , contribution to the SPIE meeting in Marseille on 27 June. 16. Manuel Guizar –Sicairos and Fienup, J. R. (2008), Direct image Reconstruction from a Fourier Intensity Pattern us ing HERALDO, Opt. Lett., 33(22). 17. Manuel Guizar –Sicairos and Fienup, J. R. (2008), Phase retrieval with Fourier-Weighted projections, J. Opt. Soc. Am. A, 25:701-709. 18. Thurman, Samuel T, and Fienup J. R.,(2009), Weiner reconstruction of undersampled imagery, J. Opt. Soc. Am. A, 26:283-288. 19. Gerchberg, R. W. and Saxton, W. O. (1972), A practical algorithm for the determination of the phase from image and diffraction plane picture, Optik 35:237-246. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (1): Block Diagram of Fourier Magnitude Reconstruc�on or sometimes called Error-reduc�on algorithm [3]. g F { } ieGG  SATISFY FOURIER CONSTRAINTS ieFG  F -1 { } SATISFY FOURIER CONSTRAINTS g' Fig. (2): Block Diagram of input- output algorithm مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (3): The importance of Fourier phase in Image reconstruction (F denotes Fourier transfer operator) مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (4): Cento-symmetric object and there constructions with exact, longer and smaller supports: 1. a)-(d) are cento-symmetric objects. 2. (e)-(h) Reconstructions of (1) consequently using exact support. 3. (i)-(l) Reconstructions of (1) consequently with slightly bigger support. 4. (m)-(p) Reconstructions of (1) consequently with smaller support. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (5): Changing the symmetry of the object . 1. (a)-(d) are cento-symmetric objects. 2. (e)-(h) Reconstructions of (1) consequently using exact support. 3. (i)-(l) Reconstructions of (1) consequently with slightly bigger support. 4. (m)-(p) Reconstructions of (1) consequently with smaller support. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (6): Changing the symmetry of the object a- Real object b- Reconstruction with exact support. c- Reconstruction with circle support shown in (e). d- Reconstruction with square support shown in (f). مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig.(7): (a) Absolute of a complex function. (b) Real of a complex function. (c) Imaginary of a complex function. 1. (d)-(f) Absolute of the reconstructions. 2. (g)-(i) Real of the reconstructions. 3. (j)-(l) Imaginary of the reconstructions. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig (8): (a) Absolute of a complex function. (b) Real of a complex function. (c) Imaginary of a complex function. 1. (d)-(g) Absolute of the reconstructions. 2. (h)-(k) Real of the reconstructions. 3. (l)-(o) Imaginary of the reconstructions. (a)-(e) Absolute of the reconstructed complex object. 1. (f)-(j Real of the reconstructed complex object. 2. (k)-(o) Imaginary of the reconstructed complex object. مجلة إبن الھیثم للعلوم الصرفة و التطبیقیة 2012 السنة 25 المجلد 1 العدد Ibn Al-Haitham Journal for Pure and Applied Science No. 1 Vol. 25 Year 2012 استرجاع الجسم من معلومات معامل فوریر فقط علي طالب محمد، فؤاد ندیم حسن ، اسیل جمیل توفیق ة بغدادجامع، كلیة العلوم ، قسم الفلك 2011 تشرین االول 11: قبل البحث في2011حزیران 5:استلم البحث في الخالصة كن استرجاع الجسم من معلومات تحویالت فوریر حظیت بتغطیة كبیرة في مختلف الدوریات والنشرات العلمیة ول ان هذه التقنیة تمت دراستها Fourier magnitudeواضحة لعدم نجاح استرجاع الجسم من معلومات " لم تعط حلوال object support فإن مقید معلومات الجسم centro-symmetricبعنایة وتبین انه في حالة الجسم المتشابه مركزیا constraint یؤدي دورا مهما في هذه التقنیة، بینما بالنسبة الى asymmetric object فإن هذا المقید غیر كاف complexذلك درس استعمال هذه التقنیة على اجسام معقدة " فضال. عملیة االسترجاع الصحیحةللوصول إلى functions وتبین ان مقید الجسم مهم جدا لكل من الدالة الحقیقیة والخیالیة ً. تحویالت فوریر ، موقع الصفر المعقد ، استرجاع الطور ، اعادة تركیب الجسم : الكلمات المفتاحیة