ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or 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. Mohamme d Department of Astronomy, College of Science, Unive rsity of Baghdad Received in: 5 June 2011 ,Accepte d in:11October2011 Abstract Reconst ruction an object from its Fourier magn itude has taken a great deal in the literature and there is still no obvious solution for the failure of this algorithm. In this p ap er, the frequent failure of the phase retrieval is discussed in details and it has been shown t hat when the object is cento-sy mmetric, the object supp ort is vital element to ensure uniqueness while for asy mmetric object; the asy mmetric supp ort of the object is not enough to ensure uniqueness but the reconst ruction app ear to include most of the information of the or iginal object. T his is also t rue for the reconst ruction of a complex function. Keywords: Fourier t ransform, comp lex zero locat ion, phase ret rieval, object s reconst ruct ion Introduction The problem of phase retrieval (magn itude- reconst ruction only) has att racted a great deal of att ention in the literature and st ill many questions remain un answered. Phase retrieval involves finding the p hase of a complex wave f ield when only the intensity (or its p ositive square root) is known. For further back ground on the subject, the reader is referred to a review by the following p ap ers [1-6]. Exact solutions based up on p oly nomial models for the wave field and either factorization or comp lex zero location [5] encounter computational difficulties with large images and have limited st ability in the p resence of noise. The method based upon zero location has t he dist inct advantage that it generates all p ossible solutions and p rovides a means of testing for uniqueness. Iterative algorithms for p hase retrieval are well established [2,3,4] but t heir p erformance is oft en poor, p articularly if no additional const raints can be p laced up on the solution. M any attemp ts have been made to enhance the performance of p hase retrieval techn ique. Num erical investigation to the uniqueness of p hase retrieval was st udied extensively using gradient search [7]. Additional step such as usin g sup p ort constraint and low resolution image in conn ection with error reduction algorithm are used to retrieve the Fourier phase of a comp lex fun ction [8,9]. An algor ithm for reconst ruction a sy mmetric three dimensional ima ge from its Fourier intensity in the case of crystallogr aphic p roblem is p resented in [10]. Anot her app roach was made to formulate the p hase retrieval p roblem with mathematical care to establish new connections between well established numer ical phase retrieval schemes and classical conv ex optimization methods [11]. A p rojection-based method, the Hy brid p rojection reflection (HPR) algorithm was p rop osed for solving p hase retrieval p roblem [12]. The difficulties associated with p hase retrieval al gorithm and how to solve such problem using adap tive optics is described in [13]. Prior discrete Fourier transform (PDFT) sp ectral estimation technique was p rop osed to reconst ruct signals fro m in comp lete data [14]. The third-order intensity correlations from the data set of measured intensities for each distance triplet were calculated to r econst ruct astronomical ima ges [15]. Taking deriv ation of the field autocorrelation hologr aphy with extended reference allows direct reconst ruction of a comp lex object from measurement of its franhofer diffraction pattern [16]. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 A Fourier heighted p rojection is p rop osed to tackle the problem of far-field measurement that associated with the coherent lensin g imaging [17]. Finally a Fourier do main Wiener filter for the reconstruction of under sampled ima gery is p rop osed [18]. This filter is d epending on a net transfer function that characterizes the combined effects of the imaginary sy stem and reconst ruction p rocess. Although many att empts have been made to solve the problem, phase retrieval in p ractice is far from easy . The work described in this p aper tackles the frequent failure of iterative algorithms to conver ge to the correct solution [3]. Furt hermore, relatively little att ention has been p aid to the reconstruction of sp ecifically comp lex images. Theory In one dimension it is well known that the Fourier magnitude is non-unique, i.e. there exist s many functions f(x) with the same Fourier magnitude |F(u)|, where:  b a dxiuxxfuF )exp()()( (1) and [a,b] is the supp ort of f(x). In p ractice, iterative schemes for p hase retrieval in one dimension almost alway s fall to conver ge to the required solution [5]. This is att ributed that if the p oly nomial function describing the field from uniformly illuminated object, then in one dimension this p oly nomials can alway s be factorized over the field of complex numbers and this will produce well known ambigu ities. In two dimensions, the Fourier magnitude |F(u,v)| is uniquely sp ecifies an ima ge f(x, y), where   12 )](2exp[),(),( S dxdyvyuxiyxfvuF  (2) and S12 is the supp ort of f(x,y). Since |F | is identical to |F  | (where an asterisk denotes comp lex conju gation), Fourier magnitude data alone is insufficient to distinguish between the two. Consequently there is at least a two-fold ambiguity in magnitude-only reconst ruction 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 p hase factor. The corresp onding reconst ructed image is a shifted version of the original. Alternative ima ges of this kind havin g the same Fourier magnitude as the required solution are usua lly classed as trivial ambigu ities. Uniqueness is usually taken to mean that only f(x,y) or its trivial ambigu ities are consist ent with |F(u,v)|. Sp ecifically, the trivial amb iguities 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-sy mmetric image: ),(),( yxfyxf  (3) and |F(u,v)| is truly unique. In the following text, an image that is not centro-sy mmetric is referred to as an asy mmetric image, for which : ),(),( yxfyxf  (4) ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 and there exists a two – fold ambigu ity . It has often been assumed that there is no clear connection between the exp ectation of uniqueness and the success of iterative algorithms [4]. However, the results presented in this p ap er indicate a direct link between the absence of trivial ambiguities and suc cessful reconst ruction. Iterative p hase retrieval as d iscussed in this p aper refers to a generalization of the Gerchber g-Sa xton algor ithm [19] known as the error-reduction algor ithm [3] as shown in the block diagram that illustrated in Fi g.(1). The latest estimate of the image is Fouri er transformed, and the calculated Fourier magnitude replace by the known (true) magnitude. The modified Fouri er data (the true magn itude and the estimated p hase) are inverse Fouri er transformed, and the known supp ort of the image is imposed. The procedure is r epeated until the est imate of the image is sufficiently close to the original. In two dimensions, the exact supp ort of the image cannot be deduced from the autocorrelation function and the supp ort constraint tends to be weak. It is generally accep ted that if the supp ort constraint is tightened, then the convergence is imp roved. The supp ort of the object could be imp osed accordin g to the following equation:          syx syxyxg yxg k k ),(0 ),(),( ),( ' 1 (5) k represents number of iterations. An imp roved algorithm that can be used to sp eed up convergence is the hy brid inp ut- output algorithm [3] as shown in Fi g.(2). The Fourier transform, the Fourier domain constrains, and the inverse transform are classed as a single sy st em have an inp ut and an output. The (k+1) th inp ut is equal to the previous inp ut wherever the image domain constraints are satisfied, and equal to t he previous inp ut less some fraction of the outp ut. The new inp ut is no longer simply the best estimate of the image, but is an att emp t to drive the next output in the right direction. Results and Discussion Before we st art the st udy of frequent failure of magn itude only reconst ruction algor ithm, let us begin with the reconst ruction from using Fourier p hase information. Fig.(3) shows the imp ortance of the Fourier phase than Fourier magnitude in image reconstructions. Fig.(4 e,f,g,h) show the reconst ructions of centro-sy mmetric ima ges usin g exact centro- sy mmetric supp ort. In this case, the Fourier p hase is p articularly simple; it assumes values of only 0 or π. The reconst ruction is successful using exact supp ort. This is exp lained by noting that for a centro-sy mmetric image, the two p ermissible solutions (corresp onding to F and F ) are identical. While, the reconst ruction is fail to converge if the cento- sy mmetric supp ort is taken slightly bigger or smaller than the exact radius. Now, let us start chan ging the sy mmetry of the object. If the same centro-sy mmetric supp ort is used through the image f(x,y) is not centro-sy mmetric. The reconst ruction fails even if we imp osed the exact supp ort constraint. The two p ossible solutions are no longer identical, the algorithm is unable to converge on either one of them, and the reconst ruction appears to be a confused mixture of the two. Even through uniqueness to within a trivial ambiguity is assured (readily achiev ed by means of Eisenst ein's criterion [5], the sup p ort constraint is insufficient to ensure true uniqueness as shown in Fig.(5). Fig.(6) shows an original real p ositive image and its reconstruction when exact asy mmetric supp ort was imp osed. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Now, let us extend our st udy to include the reconst ruction of a comp lex function. The comp lex data is gener ated by assuming its real and ima ginary are centro-sy mmetric functions as shown in Fig.(7 b & c). This function is Fourier transformed and its absolute function represent t he est imates Fourier magnitude. The reconst ruction using exact sup p ort for the real and imaginary p arts are shown in Fig.(7 g&j). The results bear most of the information of the comp lex fun ction but not converge to t he required solution. Now if we ch anginge the sy mmetry of this comp lex function, the reconstruction is shown in Fig.(8). Fin ally, it should be pointed out here t hat t he number of iterations t hat used for all the reconstructions is 100. Conclusions The reconst ruction is good in sharp contrast . When rectangular or cir cular supp ort constraints are used, the reconst ruction is failed to conver ge by iterative means even when the additional constraints of reality and p ositivity are used. However, when an exact and asy mmetric supp ort is used, the reconstruction converges quickly to the required solution. The results p resented above su ggest that the conver gence is si gn ificantly bett er if the supp ort is asy mmetric and sp ecifically excludes one of the trivial ambiguities, namely the image reflected through the origin. It is sometimes thought that the constraints of reality and p ositivity are imp ortant in iterative reconst ruction of real p ositive images. However, it is shown that it is the supp ort constraint which most affects the likelihood of conver gence, and good results are obtained with comp lex ima ges. Re ference 1. Bates, R. H. T. (1984), Uniqueness of Solutions to two- dimensional Fourier phase problem for localized and posit ive images, Computer vision Graphics and Image Processing, 25(2): 205-217. 2. Fienup, J. R. (1978), Reconstruction of an object from the modu lus of its Fourier Transforms, Opt. let. 3:27-29. 3. Fienup, J. R. (1982), Phase retrieval algor ithms: 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 c omplex valued object from the modulus of its Fourier transform using a support c onstraint, 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 A l-Haitham Journal f or 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 var iants: a rev iew from convex optim ization, 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 Telesc ope, 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 Reconstruc tion 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 wit h 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 algor ithm for the determination of the phase from image and diffraction plane picture, Optik 35:237-246. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (1): Block Diagr am of Fourier Magnitude Reconstruc�on or sometimes called Error-reduc� on algorithm [3] . g F { } i eGG  SATIS FY FOURIER CONSTRAINTS i eFG  F - 1 { } SATIS FY FO URIE R CON STRAINTS g' Fig. (2): Bl ock Diagram of input- output algorithm ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or 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 A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (4): Ce nto-symmetric object and the re constructions with exact, longe r and smaller supports: 1. a)-(d) are cento-symmetric objects. 2. (e)-(h) Reconstructions of (1) conse quently using exact support. 3. (i)-(l) Reconstructions of (1) consequently with slightly bigger support. 4. (m)-(p) Reconstructions of (1) conseque ntly with smaller support. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (5): Changing the symme try of the object . 1. (a)-(d) are cento-symmetric objects. 2. (e)-(h) Reconstructions of (1) conse quently using exact support. 3. (i)-(l) Reconstructions of (1) consequently with slightly bigger support. 4. (m)-(p) Reconstructions of (1) conseque ntly with smaller support. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig. (6): Changing the symme try 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 A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig.(7): (a) Absol ute 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 A l-Haitham Journal f or Pure and Applied Science No. 1 Vol. 25 Year 2012 Fig (8): (a) Absol ute o f a complex function. (b) Re al of a comple x function . (c) Im agin ary of a complex fun cti on. 1. (d)-(g) Absolute of the re cons tructi ons. 2. (h)-(k) Re al of the reconstru ctions. 3. (l)-(o) Im agin ary of the re constructi ons. (a )-(e) Absolu te of the re con stru cte d comple x object. 1. (f)-(j Real of the re constructe d comple x obje ct. 2. (k)-(o) Im agin ary of the re constru cte d com plex obje ct. ة مجلة إبن الھیثم للعلوم الصرفة و التطبیقی 2012 السنة 25 المجلد 1 العدد Ibn A l-Haitham Journal f or 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 وتبین ان مقید الجسم مهم جدا لكل من الدالة الحقیقیة والخیالیة ً. تحویالت فوریر ، موقع الصفر المعقد ، استرجاع الطور ، اعادة تركیب الجسم : الكلمات المفتاحیة