Iterative approximation environments for modeling the evolution of an image propagating through a physical medium in restoration and other applications

Abstract

Image processing utilizing numerical calculation of fractional exponential powers of a diagonalizable numerical transform operator for use in an iterative or other larger computational environments. In one implementation, a computation involving a similarity transformation is partitioned so that one part remains fixed and may be reused in subsequent iterations. The numerical transform operator may be a discrete Fourier transform operator, discrete fractional Fourier transform operator, centered discrete fractional Fourier transform operator, and other operators, modeling propagation through physical media. Such iterative environments for these types of numerical calculations are useful in correcting the focus of misfocused images which may originate from optical processes involving light (for example, with a lens or lens system) or from particle beams (for example, in electron microscopy or ion lithography).

1. A method performed by a numerical processor for approximating the evolution of images propagating through a physical medium by calculating a fractional power of a numerical operator, said numerical operator being defined by said physical medium and comprising a diagonalizable numerical linear operator raised to a power (α), said method comprising:
 (a) representing a plurality of images using an individual data array for each of said plurality of images;  
 (b) representing said numerical operator with a linear operator formed by multiplying an ordered similarity transformation operator (P) by a correspondingly-ordered diagonal operator (Λ), the result of which is multiplied by an approximate inverse (P −1 ) of said ordered similarity transformation operator (P);  
 (c) raising diagonal elements of said correspondingly-ordered diagonal operator (Λ) to said power (α) to produce a fractional power diagonal operator;  
 (d) multiplying said fractional power diagonal operator by an approximate inverse of said ordered similarity transformation operator (P −1 ) to produce a first partial result;  
 (e) multiplying a  the data array of one of said plurality of images by said ordered similarity transformation operator (P) to produce a modified data array;  
 (f) multiplying said modified data array by said first partial result to produce said fractional power of said numerical operator; and  
 (g) repeating operations (e) and (f) for each of said plurality of images; and  
 (h) producing a transformed image from the modified data array for each of said plurality of images.  
 
     
     
       2. The method according to  claim 1 , wherein said data array, for each of said plurality of images, is a vector. 
     
     
       3. The method according to  claim 1 , wherein said data array, for each of said plurality of images, is a matrix. 
     
     
       4. The method according to  claim 3 , wherein each of said plurality of matrices represent a monochrome image. 
     
     
       5. The method according to  claim 3 , wherein each of said plurality of matrices represent a luminance component of a represented image. 
     
     
       6. The method according to  claim 3 , wherein each of said plurality of matrices represent a chroma component of a represented image. 
     
     
       7. The method according to  claim 1 , wherein said data array, for each of said plurality of images, is a tensor. 
     
     
       8. The method according to  claim 7 , wherein each of said plurality of tensors represent a color image. 
     
     
       9. The method according to  claim 1 , wherein said numerical operator comprises a representation of a discrete Fourier transform. 
     
     
       10. The method according to  claim 9 , wherein said discrete Fourier transform comprises a one-dimensional transformation acting on vectors. 
     
     
       11. The method according to  claim 9 , wherein said discrete Fourier transform comprises a two-dimensional transformation acting on matrices. 
     
     
       12. The method according to  claim 11 , wherein said two-dimensional discrete Fourier transform is represented as a tensor product of two one-dimensional discrete Fourier transforms, wherein a first one of said two one-dimensional discrete Fourier transforms is uniquely associated with rows of said data array, and a second one of said two one-dimensional discrete Fourier transforms is uniquely associated with columns of said data array. 
     
     
       13. The method according to  claim 1 , wherein said numerical operator comprises a matrix. 
     
     
       14. The method according to  claim 13 , wherein said ordered similarity transformation operator (P) comprises an array formed from eigenvectors of said numerical operator. 
     
     
       15. The method according to  claim 14 , wherein said correspondingly-ordered diagonal operator (Λ) comprises a diagonal matrix of eigenvalues corresponding to said eigenvectors which are arranged in corresponding order relative to said eigenvalues. 
     
     
       16. The method according to  claim 1 , wherein said multiplying accomplished in operations (b), (d), (e), and (f) is accomplished using matrix multiplication. 
     
     
       17. The method according to  claim 1 , wherein said numerical operator comprises a tensor. 
     
     
       18. The method according to  claim 1 , wherein said ordered similarity transformation operator (P) comprises a matrix. 
     
     
       19. The method according to  claim 1 , wherein said multiplying of said approximate inverse of said ordered similarity transformation operator and said correspondingly-ordered diagonal operator is realized by multiplying each column of said ordered similarity transformation operator by a value of a diagonal element of a corresponding row of said correspondingly-ordered diagonal operator. 
     
     
       20. The method according to  claim 1 , wherein said numerical operator comprises a zero origin which matches a zero origin of each of said plurality of images. 
     
     
       21. The method according to  claim 20 , said method further comprising:
 shifting an index of said numerical operator so that said zero origin of said numerical operator matches said zero origin of each of said plurality of images.  
 
     
     
       22. The method according to  claim 20 , wherein said plurality of images form a composite image. 
     
     
       23. A method performed by a numerical processor for approximating the evolution of images propagating through a physical medium by calculating a fractional power of a numerical operator, said numerical operator being defined by said physical medium and comprising a diagonalizable numerical linear operator raised to a power (α) having any one of a plurality of values, said method comprising:
 (a) representing an image using a data array;  
 (b) representing said numerical operator with a linear operator formed by multiplying an ordered similarity transformation operator (P) by a correspondingly-ordered diagonal operator (Λ), the result of which is multiplied by an approximate inverse (P −1 ) of said ordered similarity transformation operator (P);  
 (c) raising diagonal elements of said correspondingly-ordered diagonal operator (Λ) to one of said plurality of values of said power (α) to produce a fractional power diagonal operator;  
 (d) multiplying said fractional power diagonal operator by an approximate inverse of said ordered similarity transformation operator (P −1 ) to produce a first partial result;  
 (e) multiplying said data array by said ordered similarity transformation operator (P) to produce a modified data array;  
 (f) multiplying said modified data array by said first partial result to produce said fractional power of said numerical operator; and  
 (g) repeating operations (c) and (d) for each of said plurality of values of said power (α); and  
 (h) producing a transformed image from the modified data array for each of said plurality of images.  
 
     
     
       24. The method according to  claim 23 , wherein said data array, for each of said plurality of images, is a vector. 
     
     
       25. The method according to  claim 23 , wherein said data array, for each of said plurality of images, is a matrix. 
     
     
       26. The method according to  claim 25 , wherein each of said plurality of matrices represent a monochrome image. 
     
     
       27. The method according to  claim 25 , wherein each of said plurality of matrices represent a luminance component of a represented image. 
     
     
       28. The method according to  claim 25 , wherein each of said plurality of matrices represent a chroma component of a represented image. 
     
     
       29. The method according to  claim 23 , wherein said data array, for each of said plurality of images, is a tensor. 
     
     
       30. The method according to  claim 29 , wherein each of said plurality of tensors represent a color image. 
     
     
       31. The method according to  claim 23 , wherein said numerical operator comprises a representation of a discrete Fourier transform. 
     
     
       32. The method according to  claim 31 , wherein said discrete Fourier transform comprises a one-dimensional transformation acting on vectors. 
     
     
       33. The method according to  claim 31 , wherein said discrete Fourier transform comprises a two-dimensional transformation acting on matrices. 
     
     
       34. The method according to  claim 33 , wherein said two-dimensional discrete Fourier transform is represented as a tensor product of two one-dimensional discrete Fourier transforms, wherein a first one of said two one-dimensional discrete Fourier transforms is uniquely associated with rows of said data array, and a second one of said two one-dimensional discrete Fourier transforms is uniquely associated with columns of said data array. 
     
     
       35. The method according to  claim 23 , wherein said numerical operator comprises a matrix. 
     
     
       36. The method according to  claim 35 , wherein said ordered similarity transformation operator (P) comprises an array formed from eigenvectors of said numerical operator. 
     
     
       37. The method according to  claim 36 , wherein said correspondingly-ordered diagonal operator (Λ) comprises a diagonal matrix of eigenvalues corresponding to said eigenvectors which are arranged in corresponding order relative to said eigenvalues. 
     
     
       38. The method according to  claim 23 , wherein said multiplying accomplished in operations (b), (d), (e), and (f) is accomplished using matrix multiplication. 
     
     
       39. The method according to  claim 23 , wherein said numerical operator comprises a tensor. 
     
     
       40. The method according to  claim 23 , wherein said ordered similarity transformation operator (P) comprises a matrix. 
     
     
       41. The method according to  claim 23 , wherein said multiplying of said approximate inverse of said ordered similarity transformation operator and said correspondingly-ordered diagonal operator is realized by multiplying each column of said ordered similarity transformation operator by a value of a diagonal element of a corresponding row of said correspondingly-ordered diagonal operator. 
     
     
       42. The method according to  claim 23 , wherein said numerical operator comprises a zero origin which matches a zero origin of said image. 
     
     
       43. The method according to  claim 42 , said method further comprising:
 shifting an index of said numerical operator so that said zero origin of said numerical operator matches said zero origin of said image.  
 
     
     
       44. The method according to  claim 42 , wherein said image is one portion of a composite image. 
     
     
       45. A computer-readable medium containing instructions for controlling a computer system to approximate the evolution of images propagating through a physical medium by calculating a fractional power of a numerical operator, said numerical operator being defined by said physical medium and comprising a diagonalizable numerical linear operator raised to a power (α), said controlling provided by said computer system being accomplished according to operations comprising:
 (a) representing a plurality of images using an individual data array for each of said plurality of images;  
 (b) representing said numerical operator with a linear operator formed by multiplying an ordered similarity transformation operator (P) by a correspondingly-ordered diagonal operator (Λ), the result of which is multiplied by an approximate inverse (P −1 ) of said ordered similarity transformation operator (P);  
 (c) raising diagonal elements of said correspondingly-ordered diagonal operator (Λ) to said power (α) to produce a fractional power diagonal operator;  
 (d) multiplying said fractional power diagonal operator by an approximate inverse of said ordered similarity transformation operator (P −1 ) to produce a first partial result;  
 (e) multiplying a data array of one of said plurality of images by said ordered similarity transformation operator (P) to produce a modified data array;  
 (f) multiplying said modified data array by said first partial result to produce said fractional power of said numerical operator; and  
 (g) repeating operations (e) and (f) for each of said plurality of images; and  
 (h) producing a transformed image from the modified data array for each of said plurality of images.  
 
     
     
       46. A computer-readable medium containing instructions for controlling a computer system to approximate the evolution of images propagating through a physical medium by calculating a fractional power of a numerical operator, said numerical operator being defined by said physical medium and comprising a diagonalizable numerical linear operator raised to a power (α) having any one of a plurality of values, said controlling provided by said computer system being accomplished according to operations comprising:
 (a) representing an image using a data array;  
 (b) representing said numerical operator with a linear operator formed by multiplying an ordered similarity transformation operator (P) by a correspondingly-ordered diagonal operator (Λ), the result of which is multiplied by an approximate inverse (P −1 ) of said ordered similarity transformation operator (P);  
 (c) raising diagonal elements of said correspondingly-ordered diagonal operator (Λ) to one of said plurality of values of said power (α) to produce a fractional power diagonal operator;  
 (d) multiplying said fractional power diagonal operator by an approximate inverse of said ordered similarity transformation operator (P −1 ) to produce a first partial result;  
 (e) multiplying said data array by said ordered similarity transformation operator (P) to produce a modified data array;  
 (f) multiplying said modified data array by said first partial result to produce said fractional power of said numerical operator; and  
 (g) repeating operations (c) and (d) for each of said plurality of values of said power (α); and  
 (h) producing a transformed image from the modified data array for each of said plurality of images.  
 
     
     
       47. A method performed by a numerical processor for numerically modeling an image propagating through a medium, the method comprising:
 representing the image using image data comprising a plurality of spatially-indexed amplitude values, the image data comprising a center located relative to the plurality of spatially indexed amplitude values;    providing a propagation medium model comprising quadratic phase properties which are defined relative to a propagation centerline of the propagation medium model;    aligning the propagation centerline of the propagation medium model relative to the center of the image data;    approximating the propagation medium model with a numerical operator for applying an index-shifted numerical fractional Fourier transform operation on the image data, the numerical operator having original-domain indices and transform-domain indices, wherein the original domain indices comprise a zero original-domain origin that is centered within the original domain indices, and the transform-domain indices comprise a zero transform-domain origin that is centered within the transform-domain indices;    aligning the zero original-domain origin relative to the center of the image data to produce transformed image data comprising-a zero frequency-domain origin that is centered within the transform-domain indices; and    producing a transformed image from the transformed image data of the image.   
     
     
       48. The method of  claim 47 , wherein the propagation medium model corresponds to effects induced by a single lens. 
     
     
       49. The method of  claim 47 , wherein the propagation medium model corresponds to effects induced by a system of lenses.  
     
     
       50. The method of  claim 47 , wherein the propagation medium model corresponds to effects induced by graded-index material. 
     
     
       51. The method of  claim 50 , wherein said graded-index material is an optical fiber.  
     
     
       52. The method of  claim 47 , wherein the image data comprises an image formed by light. 
     
     
       53. The method of  claim 47 , wherein the image data comprises an image formed by a particle beam. 
     
     
       54. The method of  claim 47 , wherein the transformed image data is structured to permit correction of misfocus in the image. 
     
     
       55. The method of  claim 47 , wherein the index-shifted numerical fractional Fourier transform operation further comprises a fractional power which is an adjustable parameter. 
     
     
       56. The method of  claim 47 , wherein the modeled medium comprises a spatial separation.  
     
     
       57. The method of  claim 47 , wherein the index-shifted numerical fractional Fourier transform operation is obtained by reorganizing operations on the eigenvectors for a traditional numerical discrete Fourier transform matrix or tensor. 
     
     
       58. The method of  claim 47 , wherein the center of the image data is either an exact center or an approximate center.