A FRAMEWORK FOR WAVELET-BASED ANALYSIS AND PROCESSING OF COLOR FILTER ARRAY IMAGES WITH APPLICATIONS TO DENOISING

AND DEMOSAICING

BACKGROUND

Field of Invention

The present invention relates to image acquisition, and more particularly to wavelet-based processing of a sub-sampled image.

Discussion of Related Art

In digital imaging applications, data are typically obtained via a spatial subsampling procedure implemented as a color filter array (CFA), a physical construction whereby each pixel location measures only a single color. The most well known of these schemes involve the three colors of light: red, green, and blue. In particular, the Bayer pattern CFA, shown in Fig. 1, attempts to complement humans' spatial color sensitivity via a quincunx sampling of the green component that is twice as dense as that of red and blue.

The terms "demosaicing" and "demosaicking" refers to the inverse problem of reconstructing a spatially undersampled vector field whose components correspond to these primary colors. It is well known that the optimal solution to this ill-posed inverse problem, in the L ² sense of an orthogonal projection onto the space of bandlimited functions separately for each spatially subsampled color channel, produces unacceptable visual distortions and artifacts. Aside from the spatial undersampling inherent in the Bayer pattern, this phenomenon can be attributed to the observation that values of the color triple exhibit significant correlation, particularly at high spatial frequencies: such content often signifies the presence of edges, whereas low-frequency information contributes to distinctly perceived color content. As such, most demosaicing algorithms described in the literature attempt to make use (either implicitly or explicitly) of this correlation structure in the spatial frequency domain.

SUMMARY

One aspect of the present invention relates to a new approach to demosaicing of spatially sampled image data observed through a color filter array, in which properties of Smith-Barnwell filterbanks may be employed to exploit the correlation of color components in order to reconstruct a subsampled image. In some embodiments, the approach is amenable to wavelet-domain denoising prior to demosaicing. One aspect of the present invention relates to a framework for applying existing image denoising algorithms to color filter array data. In addition to yielding new algorithms for denoising and demosaicing, in some embodiments, this framework enables the application of other wavelet-based denoising algorithms directly to the CFA image data. Demosaicing and denoising according to some embodiments of the present invention may perform on a par with the state of the art for far lower computational cost, and provide a versatile, effective, and low-complexity solution to the problem of interpolating color filter array data observed in noise. According to one aspect of the present invention, a method of generating a processed representation of at least one image from a sub-sampled representation of the at least one image is provided. The method comprises A) determining a plurality of fϊlterbank subband coefficients based, at least in part, on the sub-sampled representation, and B) generating at least a portion of the processed representation by approximating at least one fϊlterbank subband coefficient of the processed representation based, at least in part, on at least one of the plurality of fϊlterbank subband coefficients, wherein the plurality of filterbank subband coefficients are adapted to conform to Smith-Barwell properties. According to one embodiment of the present invention, the method further comprises an act of C) denoising the at least one of the plurality of filterbank subband coefficients before approximating the at least one filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one of the plurality of filterbank subband coefficients includes at least one wavelet coefficient. According to another embodiment of the invention, the wavelet coefficient describes a Daubechies wavelet. According to another embodiment of the invention, the wavelet coefficient describes a Haar wavelet. According to another embodiment of the invention, wherein B) comprises combining spectrum information from at least a subset of the plurality of filterbank subband coefficients to approximate the at least one

filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one image includes a plurality of images that comprise a video.

According to one aspect of the present invention, an image processing apparatus is provided comprising a processor configured to determine a plurality of filterbank subband coefficients based, at least in part, on a sub-sampled representation of at least one image, and configured to generate at least a portion of a processed representation of the at least one image by approximating at least one filterbank subband coefficient of the processed representation based, at least in part, on at least one of the plurality of filterbank subband coefficients. According to one embodiment of the invention, the processor is further configured to denoise the at least one of the plurality of filterbank subband coefficients before approximating the at least one filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one of the plurality of filterbank subband coefficients includes at least one wavelet coefficient. According to another embodiment of the invention, the wavelet coefficient describes a Daubechies wavelet. According to another embodiment of the invention, the wavelet coefficient describes a Haar wavelet. According to another embodiment of the invention, the processor is configured to combine spectrum information from at least a subset of the plurality of filterbank coefficients to approximate the at least one filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one image includes a plurality of images that comprise a video.

According to one aspect of the present invention, a method for processing an image is provided. The method comprises acts of capturing image data through a color filter array, transforming the image data using at least one filterbank, reconstructing an image from the processed image data. According to another embodiment of the invention, reconstructing an image from the processed image data further comprises an act of approximating at least one filterbank subband coefficient. According to another embodiment of the invention, transforming the image data using at least one filterbank further comprises separating color components of the spatially sampled image data.

According to another embodiment of the invention, transforming the image data using at least one filterbank further comprises separating spectral energy of individual color

components. According to another embodiment of the invention, separating spectral energy of individual color components includes an act of using a wavelet transform. According to another embodiment of the invention, separating the spectral energy of individual color components further comprises an act of using a two-level wavelet transform.

According to one embodiment of the present invention, separating the spectral energy of individual color components further comprises an act of using a multi-level wavelet transform. According to another embodiment of the invention, transforming the image data using at least one filterbank further comprises decomposing the image data into a plurality of filterbank subband coefficients. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise a complete filterbank. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise an overcomplete filterbank. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise at least one of complete filterbank, an overcomplete filterbank, an undecimated wavelet coefficient, and a decimated wavelet coefficient According to another embodiment of the invention, at least one of the plurality of filterbank subband coefficients comprises at least one wavelet coefficient. According to another embodiment of the invention, the at least one wavelet coefficient describes a Daubechies wavelet. According to another embodiment of the invention, the at least one wavelet coefficient describes a Harr wavelet. According to another embodiment of the invention, the method further comprises an act of denoising the image data prior to demosaicing the image data.

According to one embodiment of the present invention, the act of transforming the image data using at least one filterbank further comprises an act of performing denoising on the image data. According to another embodiment of the invention, the act of performing denoising on the image is wavelet based. According to another embodiment of the invention, the method further comprises an act of estimating a luminance component of an image. According to another embodiment of the invention, the image data comprises a plurality of images. According to another embodiment of the invention, the plurality of images comprise video.

According to one aspect of the present invention, a method for reducing computational complexity associated with recovering an image is provided. The method

comprises accessing image data captured through a color filter array, transforming the image data into a plurality of subband coefficients using a filterbank, estimating at least one subband coefficient for a complete image based, at least in part, on the plurality of subband coefficients, reconstructing, at least part of a complete image, using the estimated at least one subband coefficient for the complete image. According to one embodiment of the present invention, the method further comprises an act of denoising the image data. According to another embodiment of the invention, the act of denoising the image data occurs prior to demosaicing the image data. According to another embodiment of the invention, the act of transforming the image data using at least one filterbank further comprises an act of performing denoising on the image data.

According to another embodiment of the invention, the act of performing denoising on the image is wavelet based. According to another embodiment of the invention, the method further comprises an act of estimating a luminance component of an image.

According to one aspect of the present invention, an image processing apparatus is provided. The apparatus comprises a processor adapted to transform image data into a plurality of subband coefficients using a filterbank, estimate at least one subband coefficient for a complete image, based, at least in part, on the plurality of coefficients, and reconstruct, at least part of a complete image, using the estimated at least one subband coefficient for the complete image. According to one embodiment of the present invention, the processor is further adapted to denoise the image data. According to another embodiment of the invention, the processor is further adapted to denoise the image data prior to demosaicing the image data. According to another embodiment of the invention, the processor is further adapted to transform the image data using at least one filterbank and denoise the image data as part of the same process. According to another embodiment of the invention, the processor is adapted to use wavelet based denoising. According to another embodiment of the invention, the processor is further adapted to estimate a luminance component of an image.

According to one aspect of the present invention, a computer-readable medium having computer-readable signals stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method for generating a processed representation of at least one image from a sub-sampled representation of the at least one image is provided. The method comprises acts of

determining a plurality of filterbank subband coefficients based, at least in part, on the sub-sampled representation, and generating at least a portion of the processed representation by approximating at least one filterbank subband coefficient of the processed representation based, at least in part, on at least one of the plurality of filterbank subband coefficients. According to one embodiment of the present invention, the method further comprises denoising the at least one of the plurality of filterbank subband coefficients before approximating the at least one filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one of the plurality of filterbank subband coefficients includes at least one wavelet coefficient. According to another embodiment of the invention, generating at least a portion of the processed representation by approximating at least one filterbank subband coefficient of the processed representation based, at least in part, on at least one of the plurality of filterbank subband coefficients further comprises combining spectrum information from at least a subset of the plurality of filterbank subband coefficients to approximate the at least one filterbank subband coefficient of the processed representation. According to another embodiment of the invention, the at least one image includes a plurality of images that comprise a video.

According to one aspect of the present invention, a computer-readable medium having computer-readable signals stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method for processing an image is provided. The method comprises accessing image data captured through a color filter array, transforming the image data using at least one filterbank, reconstructing an image from the processed image data. According to one embodiment of the present invention, reconstructing an image from the processed image data further comprises an act of approximating at least one filterbank subband coefficient. According to another embodiment of the invention, transforming the image data using at least one filterbank further comprises separating color components of the spatially sampled image data. According to another embodiment of the invention, transforming the image data using at least one filterbank further comprises separating spectral energy of individual color components. According to another embodiment of the invention, separating spectral energy of individual color components includes an act of using a wavelet transform. According to another embodiment of the invention, separating the spectral

energy of individual color components further comprises an act of using a two-level wavelet transform. According to another embodiment of the invention, separating the spectral energy of individual color components further comprises an act of using a multilevel wavelet transform. According to one embodiment of the present invention, transforming the image data using at least one filterbank further comprises transforming the image data into a plurality of filterbank subband coefficients. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise a complete filterbank. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise an overcomplete filterbank. According to another embodiment of the invention, the plurality of filterbank subband coefficients comprise at least one of complete filterbank, an overcomplete filterbank, an undecimated wavelet coefficient, and a decimated wavelet coefficient According to another embodiment of the invention, at least one of the plurality of filterbank subband coefficients comprises at least one wavelet coefficient. According to another embodiment of the invention, the at least one wavelet coefficient describes a Daubechies wavelet. According to another embodiment of the invention, the at least one wavelet coefficient describes a Harr wavelet. According to another embodiment of the invention, the method further comprises an act of denoising the image data prior to demosaicing. According to one embodiment of the present invention, the act of transforming the image data using at least one filterbank further comprises an act of performing denoising on the image data. According to another embodiment of the invention, the act of performing denoising on the image is wavelet based. According to another embodiment of the invention, the method further comprises an act of estimating a luminance component of an image.

According to one aspect of the present invention, a computer-readable medium having computer-readable signals stored thereon that define instructions that, as a result of being executed by a computer, instruct the computer to perform a method for reducing computational complexity associated with recovering an image if provided. The method comprises accessing image data captured through a color filter array, transforming the image data into a plurality of subband coefficients using a filterbank, estimating at least one subband coefficient for a complete image based, at least in part, on the plurality of

subband coefficients, and reconstructing, at least part of a complete image, using the estimated at least one subband coefficient for the complete image.

BRIEF DESCRIPTION OF DRAWING The accompanying drawings are not intended to be drawn to scale. In the drawings, each identical or nearly identical component that is illustrated in various figures is represented by a like numeral. For purposes of clarity, not every component may be labeled in every drawing. In the drawings:

Fig. 1 illustrates a Bayer pattern CFA; Fig. 2 illustrates an example image capturing device according to one embodiment of the present invention;

Figs. 3A-P illustrate frequency-domain representations of CFA data; Figs. 4A-B, illustrate two representations of equivalent filterbanks; Figs. 5A-B, illustrate two tables indicating results of performing various methods on CFA data;

Figs. 6A-I, illustrate representations of the 'clown" image and the same image with various method applied;

Fig. 7 illustrates an example process that may be used to process image data; Fig. 8(a)-(f) illustrate color images captured using different color filter arrays and with processing;

Fig. 9(a)-(d) illustrate examples of log-magnitude spectra of a color image; Figs. 10(a)-(b) illustrate examples of aliasing structure in local spectra and conditioned local image features of the surrounding;

Fig 11 illustrates an example of a one level fϊlterbank; Figs. 12(a)-(b) illustrate examples of two equivalent filterbanks; and

Figs. 13(a)-(b) illustrate examples of two equivalent filterbanks.

DETAILED DESCRIPTION

This invention is not limited in its application to the details of construction and the arrangement of components set forth in the following description or illustrated in the drawings. The invention is capable of other embodiments and of being practiced or of being carried out in various ways. Also, the phraseology and terminology used herein is

for the purpose of description and should not be regarded as limiting. The use of "including," "comprising," "having," "containing," "involving," and variations thereof herein, is meant to encompass the items listed thereafter and equivalents thereof as well as additional items. Various embodiments of the present invention may include one or more cameras or other image capturing devices. In some embodiments, a camera 200, as illustrated in Fig. 2, may include a plurality of light sensitive elements 201. Each light sensitive element may be configured to measure a magnitude of light 203 at a location within an image being captured. The measurements of light may later be combined to create a representation of the image being captured in a process referred to as demosaicing. In one embodiment of the present invention, the plurality of light sensitive elements 201 may include a plurality of photo sensitive capacitors of a charge-coupled device (CCD). In one embodiment, the plurality of light sensitive elements 201 may include one or more complementary metal-oxide-semiconductor (CMOS). During image capture, each photo sensitive capacitor may be exposed to light 203 for a desired period of time, thereby generating an electric charge proportional to a magnitude of the light at a corresponding image location. After the desired period of time, the electric charges of each of the photosensitive capacitors may then be measured to determine the corresponding magnitudes of light at each image location. In some embodiments of the present invention, in order to capture a color image, one or more color filters 205 may be disposed on one or more of the light sensitive elements 201. A color filter 205 may allow only a desired portion of light of one or more desired colors (i.e., wavelengths) to pass from an image being captured to the respective light sensitive element on which the color filter 205 is disposed. In some implementations, a color filter may be generated by placing a layer of coloring materials (e.g., ink, dye) of a desired color or colors on at least a portion of a clear substrate. In traditional image capturing applications, the color filters are arranged into a color filter array 207 having colors arranged in a pattern known as the Bayer pattern, which is shown in Fig. 1 and described in more detail below. In some embodiments, an indication of the magnitudes of light measured by each light sensitive element may be transmitted to at least one processor 209. In one embodiment in which a plurality of photosensitive capacitors of a CCD are used as light

sensitive elements 201, the current in each photo sensitive capacitor may be measured and converted into a signal that is transmitted from the CCD to the processors. In some embodiments, the processor 209 may include a general purpose microprocessor and/or an application specific integrated circuit (ASIC). In some embodiments, the processor may include memory elements (e.g., registers, RAM, ROM) configured to store data (e.g., measured magnitudes of light, processing instructions, demosaiced representations of the original image). In some embodiments, the processor 209 may be part of the image capturing device (e.g., camera 200). In other embodiments, the processor 209 may be part of a general purpose computer or other computing device. In some embodiments, the processor 209 may be coupled to a communication network 211 (e.g., a bus, the Internet, a LAN). In some embodiments, one or more storage components 213, a display component 215, a network interface component (not shown), a user interface component 217, and/or any other desired component may be coupled to the communication network 211 and communicate with the processor 209. In some implementations, the storage components 213 may include nonvolatile storage components (e.g., memory cards, hard drives, ROM) and/or volatile memory (e.g., RAM). In some implementations, the storage components 213 maybe used to store mosaiced and/or demosaiced representations of images captured using the photo sensitive elements 201. In some embodiments, the processor 209 may be configured to perform a plurality of processing functions, such as responding to user input, processing image data from the photosensitive elements 201, and/or controlling the storage and display components 213, 215. In some embodiments, one or more such processors may be configured to perform demosaicing and/or denoising functions on image data captured by the light sensitive elements 201 in accordance with the present invention.

In some embodiments, the image capturing device (e.g., camera 200) and/or processor 209 may be configured to store or transmit at least one representation of an image (e.g., on an internal, portable, and/or external storage device, to a communication network). In some implementations, the representation may include a representation of the image that has been demosaiced and/or denoised in accordance with an embodiment of the present invention. In some implementations the representation may include a representation of the magnitudes of light measured by the light sensitive elements 201.

In some embodiments, the representation may be stored or transmitted in a machine readable format, such as a JPEG or any other electronic file format.

In some embodiments, the image capturing device may include a video camera configured to capture representations of a series of images. In addition to or as an alternative to capturing a representation of a single image, as described above, such a video camera may capture a plurality of representations of a plurality of images over time. The plurality of representations may comprise a video. The video may be stored on a machine readable medium in any format, such as a MPEG or any other electronic file format.

Spectral Analysis of CFA Images

One aspect of the present invention relates to performing wavelet analysis of sub- sampled CFA images according to fundamental principles of Fourier analysis and filterbanks to generate an approximation of an original image. In one embodiment, the present invention provides a new framework for wavelet-based CFA image denoising and demosaicing methods, which in turn enables the application of existing wavelet- based image denoising techniques directly to sparsely sampled data. This capability is important owing to the fact that various noise sources inherent to the charge-coupled device (CCD) or other imaging technique employed must be taken into account in practice. In some implementations, noise reduction procedures take place prior to demosaicing (both to improve interpolation results and to avoid introducing additional correlation structure into the noise). While earlier work has been focused primarily on demosaicing prior to denoising, embodiments of the present invention perform wavelet- based denoising and demosaicing together in the same process. In one aspect of the present invention, it is recognized that the CFA image may be viewed as the sum of a fully observed green pixel array and sparsely sampled difference images corresponding to red and blue. Specifically, let index pixel locations and define

to be the corresponding color triple at a pixel location. If we define difference signals and , then the CFA image is given by

where

are the sparsely sampled difference images.

The fact that difference channels and may exhibit rapid spectral decay relative to the green channel follows from the (de-)correlation of color content at high frequencies, as described above. This result is well known, and may be observed empirically in Figs. 3A-C, which show the log-magnitude spectra of respectively denoted by for frequency variable of a well-known sample image known as "clown" obtained using a Bayer pattern CFA. It follows from the composition of the dyadic decimation and interpolation operators induced by the Bayer sampling pattern that the Fourier transform of

(4)

Figure 3D shows of the sample "clown" image from the Bayer pattern CFA data of Figures 3A-C represented as a sum of (i.e., green), (i.e., red difference signal), and (i.e., blue difference signal). Note that the rectangular subsampling lattice of the Bayer pattern CFA shifts the spectral content of and ("aliasing"), and also induces spectral copies 301 centered about the set of frequencies ("imag ing"). In some embodiments of the present invention, it is possible to take advantage of the lowpass nature of these subsampled difference signals to separate the color components of data observed through a color filter array, as described in more detail below.

In one aspect of the present invention, it is recognized that a separable wavelet transform is equivalent to a set of convolutions corresponding to directional filtering in two dimensions followed by a separable dyadic decimation about both spatial frequency axes. The application of these steps to is detailed in Figs. 3E-H, which shows the log-magnitude spectrum after filtering according to the standard directional wavelet filterbank low- and highpass transfer functions and respectively, and Figs. 3I-L which shows the result of subsequent decimation.

The application of each filter function (e.g., etc.) and subsequent decimation is equivalent to a remapping of each color channel's spatial frequency content to the origin, and a subsequent dilation of each spectrum. In one aspect of the present invention, it is recognized that if the spectral content of the difference channels is sufficiently low relative to that of the green channel, the application of such filter functions and subsequent decimation provides a method for effectively separating the spectral energy of individual color components, as shown in Figs. 3M-P.

Wavelet Analysis of Subsampled Sequences

In one aspect of the present invention, it is recognized that wavelet analysis may be used to recover spectra information of a subsampled image. In some embodiments, such wavelet analysis may be performed using Daubechies wavelets. Suppose that, as in the case of Daubechies wavelets, the directional transfer functions comprise a filterbank satisfying the Smith-Barnwell (S-B) condition. In this case, the subsampled difference images and may be conveniently represented in the wavelet domain. An example of this representation is described below in the univariate domain, though this representation may be extended to any number of dimensions. In considering a univariate wavelet representation of the difference images, let be an S.B filter pair such that the S-B condition of

, where ^m is an odd integer is satisfied, and let

index the filter passband of the decomposition at level For a sequence

and its corresponding even-subsampled version

the first-level filterbank decomposition of 7*("), denoted ^ <*i(>*0, is equivalent to the sum of the corresponding decompositions of "^*) and ^{( ~} 1)"7( ^« ) (denoted 3^<?i M and S^Ji ("^, respectively). These decompositions in turn are related to the spectrum

TM oflf H as:

where * denotes the complex conjugate, and for ^rιt odd:

(6)

Although this example is given using Daubechies wavelets, the invention is not limited to any particular set or type of wavelets. Rather, the present invention may include any arrangement or combination of any filterbanks.

In some implementations, these equations may be simplified by using Haar wavelets. For the case of the Haar wavelet, we have ^H <<ι — ' >h ^H λ, and hence by construction the scaling coefficient of ^{( ~} *-> ^" ? ( ^{n i} is equal to the wavelet coefficient of ^ " ^** '', and vice- versa. It follows that the multi-level wavelet decomposition of ⁽ — l ⁾ "τ( ^« ) is equivalent to the same multi-level wavelet packet decomposition of ^ ^" \ but in the reverse order of coarseness to fineness. An example of this filterbank structure equivalence is shown in Figs. 4A and B.

Wavelet-Based CFA Image Demosaicing In addition to providing a natural way to recover the spectra associated with individual color components of a given CFA image filterbank decompositions also provide a simple formula for reconstructing a representation of the complete (i.e., non- subsampled) image Returning to describe the two-dimensional application of filterbank decompositions to a captured image in accordance with some embodiments of the present invention, let be the two-level wavelet (packet) transforms via S-B filterbanks of , respectively, where

indicates the filter orientation. Then (as may be seen from the example of Fig. 3, particularly Fig. 3D), if the spectral content of the difference channels is sufficiently lowpass (i.e., a sufficient amount of difference information is in the low frequency regions of Figs. 3B and C) with respect to that of the green color channel, the following approximations will be accurate:

where ~ denotes reversal of a sequence. Similarly,

In some embodiments of the present invention, a demosaicing algorithm may assume that these approximations hold. In practice, these approximations may be accurate for a majority of captured images. In such embodiments, a representation of ^χ ( ⁿ ) may be recovered from its wavelet coefficients as follows:

where ^ indicates an approximation of a value from the original image. It should be recognized that although the above example is described using two-level wavelet transforms of the original CFA data, the invention is not limited to two-level wavelet transforms. Rather, embodiments of the present invention may include any number of

levels of any arrangement or combination of filterbank transforms/filterbank coefficients. For example, in some embodiments, filterbank coefficients may include complete and/or overcomplete filterbanks.

Wavelet-Based CFA Image Denoising

Wavelet-based methods for image denoising have proved immensely popular in the literature, in part because the resultant shrinkage or thresholding estimators are simple and computationally efficient, yet they may enjoy excellent theoretical properties and adapt well to spatial inhomogeneities. However, typical techniques have been designed for grayscale or complete color image data, and hence have been applied after demosaicing.

Although it may be possible to model noisy difference images in the wavelet domain directly within the statistical framework of missing data, the computational burden of doing so may be severe. However, in one aspect of the present invention, it is recognized that the wavelet analysis described above suggests a simpler scheme.

First, note that in some embodiments, when it can be expected that the wavelet coefficients estimated by some shrinkage operator will satisfy the relationship Furthermore, equation (7) implies that represents the i subband coefficients of:

which provides a means of estimating an image's luminance component (which in turn exhibits statistics similar to a grayscale image). Thus, in some embodiments, may be obtained via a standard denoising strategy. Finally, the quantities of equations shown at (8) correspond to subband coefficients from the difference images and . As smoothed approximate versions of images themselves, in some embodiments, they may be amenable to standard wavelet-based denoising algorithms.

Process Example

Figure 7 illustrate an example of a process implementing some of the features discussed above. In particular, Figure 7, shows process 700 initiated at 701 by accessing image data captured through a color filter array at 702. One should appreciate that the image data may be received directly from a CMOS sensor for example and transmitted to an image processor as discussed with respect to certain system embodiments above. One should also appreciate that the image data may be stored for later access and the medium upon which the data is stored may be transmitted or physically transported to a system upon which the image data is processed. Once the image data has been accessed, it is transformed into a plurality of filterbank subband coefficients by passing the image data through filterbanks at 704. The filterbanks may be adapted to conform to the Smith-Barnwell properties and enabling representation of the transformed image data as wavelets. In particular, Haar and Daubechies wavelet representations may be used, although in other alternatives different classes of wavelet transforms are contemplated.

Illustrated in Figure 7 is a decision node where a determination of whether donoising will occur is made at 706. In 706 Yes denoising schemes may be employed to reduce the image data to a form free or reduced from noise, at 708. In particular, wavelet based denoising may be employed. One should appreciate based on the transformation process that denoising can occur before, in conjunction with, or after demosaicing and need not take place in the same order described in the example of process 700, shown in Figure 7. In 706 No, no denoising algorithm is employed.

At 710, an estimate is generated for subband coefficients of a complete image, and the value of the estimated subband coefficient is determined from values of the plurality of subband coefficients of the transformed image data, whether denoised at 706 Yes or not at 706 No. At 712, a complete image is reconstructed from the value of the estimated subband coefficient, yielding images as shown in, for example Figure 61.

One should appreciate that process 700 is shown by way of example and that certain steps may be performed in an order different than presented, and certain steps may be omitted and/or different steps included in performing an image processing process according to different embodiment of the invention.

Experimental Results

In order to test the proposed denoising and demosaicing schemes for CFA data, both separately as well as in tandem, a variety of numerical experiments was performed using widely available test images commonly referred to as "Clown" and "Lena." These images were first subsampled according to the Bayer pattern and then corrupted with additive white Gaussian noise of mean zero. Reconstruction methods were implemented using separable Daubechies wavelets, with cycle-spinning employed for the first-level decomposition, and the nondecimated wavelet transform for the subsequent.

First, the corrupted data were used to compare the performance of three wavelet- based algorithms for denoising: the SURE Shrink method applied independently to each wavelet coefficient; a model based on scale mixtures of Gaussians applied to each of the de-interlaced color channels of the CFA image in turn; and the wavelet coefficient model describing statistically estimating wavelet values at each location of a wavelet transform of an image from wavelet values of nearby locations. Denoising was performed using a total of three decomposition levels and a shrinkage operator, with the noise variance estimated from the subband. Figure 5A illustrates a table comparing the mean- square error (MSE) of the various denoised CFA images. By treating the denoised output as input to the demosaicing algorithm described above (e.g., with respect to equation (9)), an example embodiment of the present invention comprising combined denoising and demosaicing was obtained and subsequently tested. Figure 5B illustrates a table showing the average SCIELAB distance of the output images from the original input images for this example embodiment as well as several alternative methods; a method using the Shrink SURE method followed by the method described by Gunturk, et. al.; a method using the method of Portilla, et. al. followed by the method of Gunturk, et. al.; a method using the method of Gunturk, et. al., followed by the method of Portilla, et. al.; and a method of Hirakawa, et. al.

Fig. 6 A shows the original "clown" image. Fig. 6B shows the Bayer pattern CFA data captured from the original image of Fig. 6A. Fig. 6C shows the CFA image of Fig. 6B with added noise. Figs. 6D-I illustrate the results of applying the methods listed in the table of Fig. 5B to the data of Fig. 6C, in the order of the table. In some

embodiments, performance of the tested techniques produced results substantially comparable to prior-art methods but with significantly reduced computational cost as can be seen by comparing Figs. 6D-H (i.e., output of the prior art methods) with Fig. 61 (i.e., output of an example embodiment of the present invention). In some embodiments, performance of methods in accordance with the present invention improves noticeably upon the introduction of noise, and offers enhanced edge preservation relative to alternatives that treat denoising and demosaicing separately.

Results indicate that embodiments of the present invention perform at least on a par with the state of the art with far lower computational cost, and provide a versatile, effective, and low-complexity solution to the problem of interpolating color filter array data observed in noise. Denoising algorithms and demosaicing algorithms may be combined using the above described wavelet analysis to allow for further optimization of wavelet-based compression schemes in conjunction with denoising and demosaicing of CFA data.

Additional Considerations: Joint Denoising/Demosaicking

As the general trend of increased image resolution continues due to prevalence of multimedia, the importance of interpolation is de-emphasized while the concerns for computational efficiency, noise, and color fidelity play an increasingly prominent role in the decision making of a digital camera architect. For instance, the interpolation artifacts become less noticeable as the size of the pixel shrinks with respect to the image features, while the decreased dimensionality of the pixel sensors on the complementary metal oxide semiconductor (CMOS) and charge coupled device (CCD) sensors make the pixels more susceptible to noise. Photon-limited influences are also evident in low-light photography, ranging from a specialty camera for precision measurement to indoor consumer photography.

Sensor data, which can be interpreted as subsampled or incomplete image data, undergo a series of image processing procedures in order to make the image data displayable. However, these same steps are also responsible for amplifying the distortions introduced at the image sensor. Specifically, the demosaicking step is a major source of conflict between the image processing pipeline and image sensor noise characterization because the interpolation methods give high priority to preserving the

shaφness of edges and textures. In the presence of noise, noise patterns may form false edge structures, and therefore the distortions at the output are typically correlated with the signal in a complicated manner that makes noise modeling mathematically intractable. Thus, it is natural to conceive of a rigorous tradeoff between image interpolation and image denoising.

To illustrate, Figure 8(a) shows a typical color image. Suppose we simulate the noisy sensor observation by subsampling this image according to a CFA pattern (Figure 8(b)) and corrupting with noise (Figure 8(c)). While state-of-the-art demosaicking methods do an impressive job in estimating the full-color image given ideal sensor data (Figure 8(d)), the interpolation may also amplify the noise in the sensor measurements, as demonstrated in Figure 8(f). The state-of-the-art denoising methods applied to Figure 8(f) yield unsatisfactory results (Figure 8(g)), suggesting a lack of coherent strategy to address interpolation and noise issues jointly. For comparison, the output from one example of a joint demosaicking and denoising method is shown in Figure 8(h) with observable advantages. Figure 8(e) shows demosaicing of 8(c).

According to one aspect, the problem of estimating the complete noise- free image signal of interest given a set of incomplete observation of pixel components that are corrupted by noise may be approached statistically from a point of view of Bayesian statistics, that is modeling of the various quantities involved in terms of priors and likelihood. Three examples of design regimes that will be considered here can be thought of as a simultaneous interpolation and image denoising, though one should appreciate the wider scope, in the sense that modeling the image signal, missing data, and the noise process explicitly yield insight into the interplay between the noise and the signal of interest. Presented, through example, is a basis for generatlization of the image signal models to the noisy subsampled case, and building blocks for manipulating such data. Some embodiments provide a number of advantages to the proposed estimation schemes over the obvious alternative, which is the serial concatenation of the independently designed interpolation and image denoising algorithms. For example, the inherent image signal model assumptions underlying the interpolation procedure may differ from those of the image denoising. This discrepancy is not only contradictory and thus inefficient, but also triggers mathematically intractable interactions between mismatched models. Specifically, interpolating distorted image data may impose

correlation structures or bias to the noise and image signal in an unintended way. Furthermore, a typical image denoising algorithm assumes a statistical model for natural images, not that of the output of interpolated image data. While grayscale and color image denoising techniques have been suggested, removing noise after demosaicking, however, is impractical. Likewise, although many demosaicking algorithms developed in the recent years yield impressive results in the absence of sensor noise, the performance is less than desirable in the presence of noise.

In one embodiment, it is important to characterize the noise in an image sensor. The CMOS photodiode active pixel sensor typically uses a photodiode and three transistors, all major sources of noise. The CCD sensors rely on the electron-hole pair that is generated when a photon strikes silicon. A detailed investigation of the noise source is not discussed, however, studies suggest that the number of photons encountered during an integration period (duration between resets), is a Poisson process

where is the pixel location index, and y(n) is the expected photon count per integration period at location n , which is linear with respect to the intensity of the light. Note E[z(n) | y(n)] = y(n) and E[z ² (n) - E[z(n) | y(n)] ² | y(n)] = y(n) . Then, as the integration period increases, p(z(n) \ y(n)) converges weakly to _or

where is independent of y . This approximation is justifiable via a straightforward application of central limit theorem to the binomial distribution. The noise term, s commonly referred to as the shot noise.

In practice of one embodiment, the photodiode charge (e.g. photodetector readout signal) is assumed proportional to z(n) , thus we interpret y(n) and z(n) as the ideal and noisy sensor data at pixel location n , respectively. For a typical consumer-grade digital camera, the approximation in (I) is reasonable. The significance of (I) is that the signal-to-noise ratio improves for a large value of y(n) (e.g. outdoor photography),

while for a small value of y(n) (e.g. indoor photography) the noise is severe. To make the matters worse, human visual response to the light y(ή) is often modeled as suggesting a heightened sensitivity to the deviation in the dark regions of the image. To see this, the perceived noise magnitude is proportional to:

which is a monotonically decreasing function with respect to y(n) for a fixed value ofe ^l π).

In some attempts, efforts to address signal-dependent noise in (I) lags behind those of image interpolation and image denoising for additive white Gaussian noise (AWGN). A standard technique for working with signal-dependent noise is to apply an invertible nonlinear operator /(•) on z such that signal and noise are (approximately) decoupled. That is,

for some constant σ ² . Homomorphic filtering is one such operator designed with monotonically-increasing nonlinear pointwise function. The Haar-Fisz transform is a multiscale method that asymptotically decorrelates signal and noise. In any case, a signal estimation technique (assuming AWGN) is used to estimate γ(y) given γ(z) , and the inverse transform γ ^~λ (•) yields an estimate of y . The advantage of this approach is the modularity of the design of /(•) and the estimator. The disadvantage is that the signal model assumed for y may not hold for γ{y) and the optimality of the estimator (e.g. minimum mean squared error estimator) in the new domain does not translate to optimality in the rangespace of y , especially when /(■) significantly deviates from linearity.

An alternative to decorrelation is to approximate the noise standard deviation, The AWGN noise model is effectively a zero-th order Taylor expansion of the

Poisson process; an affine noise model is the first order Taylor expansion of (I). In practice, these approximations yield acceptable performance because the CMOS sensors operate on a relatively limited dynamic range, giving validity to the Taylor assumption (when the expansion is centered about the midpoint of the operating range). The human

visual system can also tolerate a greater degree of error in the brighter regions of the image, allowing for more accurate noise characterization for small values of y (at the cost of poorer characterization for higher rangespace of y ). Alternatively, empirical methods that address signal-dependent noise take a two-step approach. First, a crude estimate of the noise variance at each pixel location n is found; second, conditioned on this noise variance estimate, we assume that the signal is corrupted by signal- independent noise. Apiecewise AWGN model achieves a similar approximation.

Methods that work with the posterior distribution of the coefficients of interests, such as Markov chain Monte Carlo and importance sampling, either have a slow convergence rate or require a large number of observations. Emerging frameworks in Bayesian analysis for Poisson noise yield an asymptotic representation of the Poisson process in the wavelets domain, but the manipulation of data in this class of representation is extremely complicated.

The estimation of the mean y given the Poisson process z is not a well- understood problem; and existing methods use variations of AWGN models to address the Poisson noise. Hence, while acknowledging inadequacies, some emboidment employ:

where Taking a closer look at the sampling scheme shows the structure of aliasing induced by the Bayer color filter array. The estimation of missing pixel components given observed pixel components is generally an ill-posed problem. By assuming that the image signals are highly structured, however, the signal-of-interest may be identical in a lower-dimensional subspace that can be represented by the subspace spanned by the color filter array. Thus, although the loss of data at the hardware interface is inevitable, the loss of information due to sampling may be limited. Fourier analysis and aliasing serve as a measure of loss of information, and motivate joint modeling and manipulation of subsampled data and noise (which will subsequently be fine-tuned) For some embodiments, images have an image pixel value, x(n) = (x, (n), x ₂ (n), x ₃ (n)) ^r that is a vectored value at the pixel position ^r> - ^ ^{" *} typically expressed in terms of RGB coordinates, respectively. By inspection, the

corresponding complete red, green, and blue images contain redundant information with respect to edge and textural formation, reflecting the fact that the changes in color at the object boundary is secondary to the changes in intensity. It follows from the (de- correlation of color content at high frequencies that the difference images (e.g. red- green, blue-green) exhibit rapid spectral decay relative to monochromatic image signals (e.g. gray, red, green), and are therefore slowly-varying over spatial domain. Such heuristic intuitions are further backed by the human physiology — the contrast sensitivity function for the luminance channel in human vision is typically modeled with a much higher pass-band than that of the chrominance channels. In one example, let c(n) = (c ₁ (n),c ₂ (n).c ₃ (iι)) ^7' e {(l,0,0) ^r ,(0,l,0) ^r ,(0,0,l) ^r } be a

CFA coding such that the noise- free sensor data can be written as an inner product, y(n) = c ^r (n)x(n) . Given that it is a convex combination, we may then decompose y(n) in the following manner:

where the difference images are approximations for the chrominance channels. In other words, the convex combination above can be thought of as the summation of x ₂ (n) with the subsampled difference images, c,(n)α(n) and c ₃ (u)β(u) ; as their sum is equal to the sensor data. It follows from the composition of the dyadic decimation and interpolation operators induced by the Bayer sampling pattern that y(ώ) , the Fourier transform of sensor data y(u) , is a sum of x ₂ (ω) and the spectral copies of ά(ω) and β(ω) :

where, without loss of generality, the origin is fixed on the first color, c(0,0) = (l,0,0) ^r , and

is an approximation to the luminance channel.

The representation of sensor data (IV) in terms of luminance £ and difference images a and β is convenient because a and β are typically sparse in the Fourier domain. To see this by example, consider Figure 9(a)-9(d), in which the log-magnitude spectra of a typical color image, "clown," is shown. The high-frequency components, a well-accepted indicator for edges, object boundaries, and textures, are easily found in Figure 9(a). In contrast, the spectra in Figures 9(b-c) reveal that a and β are low-pass, which support the slowly- varying nature of the signals discussed above. Estimating a lower bandwidth signal from its sparsely subsampled versions is less complex, since it is less subject to aliasing. Figure 10(a)-(b) shows aliasing structure in local spectra and conditioned local image features of the surrounding. In one example, it follows from Figure 10 that a Fourier domain representation of sensor data similar to what is illustrated in Figure 9(d) — the spectral copies of ά - β centered around {π,0) ^τ and (0,π) ^τ overlap with the baseband I , while ά + β centered around (π,π) ^τ remain alias- free.

There exists no straightforward global strategy such that we recover unaliased £ because both spectral copies centered around (π,0) ^τ and (0,π) ^τ are aliased with the baseband £ . However, the local image features of the baseband, £ , exhibit a strong directional bias, and therefore either (a - β)(ω - (π,0) ^τ ) or (a - β)(ω - (0, π) ^τ ) is locally recoverable from the sensor data. In one example, this observation motivates nonlinear processing that is locally adaptive — in fact, most existing demosaicking methods can be reexamined from this perspective. Figure 10(a)-(b) illustrates examples of an estimated local aliasing pattern. The locally horizontal images suffer from aliasing between £ and {a - β)(ω - (π,0) ) while (a -β)(ω -(0,π) ) remains relatively intact. Conversely, locally vertical images suffer from aliasing between £ and (ά -β)(ω - (0,π) ^τ ) while (ά -β)(ω -(π,0) ^τ ) is clean. On a sidenote, locally diagonal image features, which are often ignored by the demosaicking algorithm designs, do not interfere with (a - β)(ω -(π,0) ) and (a -β)(ω -(0,π) ) , making the reconstruction

of diagonal features a trivial task, in some embodiments. Let z(n) be the noisy sensor data,

In one example, the Fourier transform of a noisy observation is

In other words, the sensor data is the baseband luminance image £ distorted by the noise έ and aliasing due to spectral copies of ά and β , where ε , ά , and β are conditionally normal. One example of a unified strategy to demosaicking and denoising, therefore, is to design an estimator that suppresses noise and attenuates aliased components simultaneously. In one embodiment, this is accomplished via a spatially- adaptive linear filter whose stop-band contains the spectral copies of the difference images and pass-band suppresses noise.

As image signals are highly non-stationary/inhomogeneous and thus an orthogonal filterbank (or wavelet packet) expansion for sparsely sampled signal would prove useful in some embodiments.

In one example, consider first a one-dimensional signal ^{τ "} ** ^→ ** ^■ A one-level filterbank structure defined by filters {h _Q , h _x , f ₀ , f _x } is shown in Figure 11. It is a linear transformation composed of convolution filters and decimators. The channel containing the low- frequency components is often called approximation (denoted yiζ (n) ), and the other containing the high-frequency components is referred to as the detail (denoted W _x (n) ). The decomposition can be nested recursively to gain more precision in frequency. The approximation and detail coefficients from one-level decomposition can be analyzed in the Fourier domain as:

w

where i e {0,1 } . With a careful choice of filters

(A ₀ (1102), A ₁ (1104), / ₀ (1106), f (1108)} , the original signal, x{n) can be recovered exactly from the filterbank coefficients W _Q (X) and wf (n) . To see this, consider the example of the reconstruction of one-level filterbank, as in Figure 11. The transfer function of the system (or the reconstructed signal x ^rec (n) ) has the following form in the frequency domain:

In other words, the output is a linear combination of the filtered versions of the signal x{ω) and a frequency-modulated signal x(ω-π) . The structure in Figure 11 is called a perfect reconstruction filterbank if

In other words, the filters corresponding to x(ω) constitute a constant, whereas the filters corresponding to the aliased version is effectively a zero. A large body of literature exists on designing a set of filters (A ₀ , A ₁ , / ₀ , f _x } that comprise a perfect reconstruction filterbank including wavelet packets belonging to a class of filterbanks arising from the factorizing filters satisfying the Nyquist condition (Smith-Barnwell). In one example, the following are met by construction:

In other words, A ₁ is a time-shifted, time-reversed, and frequency-modulated version of A ₀ ; and / ₀ and f are time-reversed versions of A ₀ and A ₁ , respectively. One may define modulated signal and subsampled signal of x{ή) , respectively, as

-l) ^« *(n)

To derive an explicit filterbank representation of x _s (n) , we are interested in characterizing the relationship between filterbank coefficients of x{ή) and x _m (n) . Let

W _Q "' (ή) and w ^*m {ή) be the approximation and detail coefficients of the one-level filterbank decomposition of (-l)"x(n) . Then substituting into (VII) we obtain

where m is an odd integer, and * denotes the complex conjunction. A subtle but important detail of the equations above is that if the approximation and detail coefficients of x(n) were computed using h _o (-n -m) and A,(-n-/w) instead of A ₀ (n) and A,(«) , these coefficients behave exactly like the detail ( w, ^A '" (n) ) and approximation ( W _Q " ¹ (n) ) coefficients for (-1)" x(n) , respectively (note the reversed ordering of detail and approximation). It is straightforward to verify that if {/z ₀ («),/?,(«)} comprise perfect reconstruction filterbank, then {h _Q (-n -m),h^(-n -m)} constitute a legitimate perfect

reconstruction filterbank as well (we will refer to the latter as the time-reversed filterbank). Reversal of coefficients is illustrated in Figure 12 — the system in 12(a) and 12(b) are equivalent. Figure 12 illustrates examples of two equivalent filterbanks for x _m (n) = (-Y)" x(ή) . Here, * indicates time-reversed filter coefficients. Restricting our attention to the Haar decomposition for the rest of discussion and fixing m = 1 , we have that Zz ₀ (ή) = Zz ₀ (-« - 1 ) and Zz ₁ (n) = -Zz ₁ (-n - 1 ) and the approximation coefficient of (-1)" x(n) is exactly equal to the detail coefficient of x(n) by construction, and vice-versa — i.e. w^ ¹ " (n) = w, ^λ (n) and w ^* '" (n) = vt£(n) . It follows that the multi-level filterbank decomposition of (-l)"x(n) is equivalent to the time- reversed filterbank decomposition of x(ή) , but with the reversed ordering of low-to-high frequency coefficients. This reversed-order filterbank can be used to derive the filterbank representation of x _s (n) . Specifically, let (ή) be the approximation and detail coefficients of the one-level filterbank decomposition of x _i (ή) . Then

Now, update the definition of w, ^x to mean the i -th subband of (/ + 1) -level filterbank decomposition. Then by recursion, we have a general form

See Figure 13. Figure 13 illustrates examples of two equivalent filter banks for (up to multiplicative constant 2). In Figure 13 used was the Haar decomposition. Similar analyses for x _s can be performed for non-Haar decompositions, but are omitted here for simplicity.

Extending to two-dimensional signals, the decomposition of CFA image in the separable wavelet packet domain may be shown. Let w[ (n), w" (n), wf (n) be the filterbank coefficients corresponding to l(ή),a(ή),β(n) , respectively, where i = (z ₀ , z, Ϋ e {0, 1 , ... , I} ² indexes the horizontal and the vertical filterbank channels,

respectively. As before, assume without loss of generality that c(0,0) = (l,0,0) ^r . In order to apply the fϊlterbank analysis to the sensor data, we re- write y(ή) in the following manner:

and its corresponding filterbank representation:

where the minus signs in some w ^β terms occur due to translation in space, and W (n) is the filterbank coefficients of the signal in(V). The globally bandlimitedness of difference images, discussed above allows us to conclude that w"(v) « 0 and wf (v) « 0, VZ ₀ > /on, > I for some / . The above simplifies to a form that reveals the energy compaction structure within an example CFA image:

Recall (II) and that the filterbank transforms with appropriate choices of filters constitutes a unitary transform. Thus,

i±i ( n ) =w%{n ) + wξ(rt ) QQ

where is a filterbank transform of ^f -(n). In other words, the filterbank transformation of noisy sensor data w ^z is the baseband luminance coefficient w ^e distorted by the noise ft' ⁴ and aliasing due to reversed-order filterbank coefficients / and v/ , where w , w ^a , and w ^β are (conditionally) normal. Another example of a unified strategy to demosaicking and denoising, therefore, is to design an estimator that estimates w , w ^a , and w ^β from the mixture of w , w ^a , w ^β . and «" .

One should appreciate that (XI) can be generalized to any filterbanks that satisfy (VII) using time-reversed filter coefficients for Zz ₀ and Zz ₁ .

In one embodiment, given that the difference images are sufficiently low-pass, simplification in (IX) reveal that there is a surprising degree of similarity between w( (n) and W _; ' (n) . Specifically, w/' (n) « vi/ (n) for the majority of subbands — the exceptions are the subbands that are normally considered high-frequency, which now contain a strong mixture of the low-frequency (or scaling) coefficients from the difference images, a and β . Operating under the premises that the filterbank transform decomposes image signals such that subbands are approximately uncorrelated from each other, the posterior mean estimate of w[ (n) takes the form

for all subbands that meet the w? (n) « w[ (n) approximation. Wavelet shrinkage ) function is leveraged to the CFA image context.

In one example where , the L estimator is

However in embodiments wherein the subbands contain a mixture of w. , wf , w? , and wf , require further analysis. In one example, let

Consider the case such that / ₀ > / -7 and

/, < / , and define j = (z ₀ , / - i _λ ), k = (/ - i ₀ , 1 - z, ) . Then wf (n), w? (n), w^ (n) are highly correlated due to their common components in their mixture, w" and wjf , where i'= (/ -Z ₀₅ Z ₁ ) . Thus the Z- ² estimates for vt/ (n), wj ^n), w _k ^e (n) are

Similarly,

Once ^st are computed Vi, n as above, then x ^est (n) is calculated by taking the inverse filterbank transform o to find the estimates of /(U) ₅ Qr(Ii) ₅ ^(Ii) , which in turn is used to solve x ^est . Actual implementation of this method may include cycle-spinning, a technique in filterbank and wavelet processing whereby a linear space-variant system can be transformed into linear space-invariant system via averaging over all possible spacial shifts. One should appreciate that the estimator naturally extends to multivariate normal or heavy-tailed distributions. According to one aspect, investigation of the relationship between the analysis and synthesis filters admits a closed-form expression for the filterbank coefficients corresponding to the subsampled signal in terms of the filterbank coefficients corresponding to the complete signal, where the subsequent reverse-ordered scale structure (ROSS) reveals the time-frequency analysis counterpart to the classical notion of aliasing and Nyquist rate in the Fourier domain. Examples of the ROSS in filterbank is highly versatile and particularly amenable to designing Bayesian statistical methods. A maximum likelihood estimator for model parameters and optimal t and I ² estimators for the complete signal given a noisy subsampled signal are derived, in some embodiments discussed below. A celebrated result of Nyquist-Shannon sampling theorem states that exact reconstruction of a signal is possible if the signal is bandlimited and the sampling

frequency is greater than twice the signal bandwidth. The Whittaker- Shannon ideal reconstruction, however, is an orthogonal projection of the observed data onto the span of all low-bandwidth signals, a task requiring a convolution with a sine function with infinite support in time ; and undersampling below the critical sampling rate (a.k.a Nyquist rate) results in a manifestation of aliasing, a phenomenon where the underlying signal is indistinguishable from the frequency-modulated version of the same signal. Witness the bid to approximate ideal reconstruction and to circumvent the critical sampling rate by exploiting additional information and structures known about the signal Examples focus on a rigorous treatment of sampling when the underlying signal is inhomogeneous or nonstationary because the frequency domain perspective on sampling is inadequate to processing signals that do not exhibit low-pass qualities everywhere. The need to characterize inhomogeneous and locally stationary data have prompted the advancement of some joint time-frequency analysis techniques, including short-time Fourier transform, filterbanks, wavelets, and frames, and embodiments formalize the preeminent structure of aliasing governing them. Adopting the language of filterbanks and wavelets, shown is that a peculiar relationship between the analysis and synthesis filters admits a closed-form expression for the filterbank coefficients corresponding to the subsampled signal in terms of the filterbank coefficients corresponding to the complete signal. Some examples of these representations are useful for analyzing signal features that exhibit temporal locality, as they distinguish or isolate the regions susceptible to localized aliasing (to be made precise in the sequal) from regions that are unaffected by sampling. Note that this is a notion absent from the classical interpretation of aliasing in the Fourier sense, as it is defined globally.

In some embodiments, the form of time-frequency analysis proposed subsequently gives rise to a reverse-ordered scale structure (ROSS), a fundamental structure to localized aliasing. The ROSS, in conjunction with the vanishing moment property of wavelet transforms, suggests a Nyquist rate ^" counterpart" in terms of smoothness of the underlying functions that can be re-cast as a condition for exact reconstructability when sampling inhomogeneous signals. Alternatively, the closed-form expression for the subsampled signals in the transform domain and the ROSS warrant a direct manipulation of the filterbank coefficients. While the transform coefficients corresponding to the complete signal are

not observed, in one example, explicitly, the coefficients of the subsampled signals are nevertheless not far removed from the desiderata. Adopting a Bayesian statistics point of view in one embodiment; that is, model the complete signal in terms of the prior probability for the transform coefficients, and the loss of information due to subsampling is coded into the likelihood function. Then the posterior distribution of the coefficients are readily accessible by reversing the arguments for ROSS, and minimization of Bayes risk is an attainable goal in some embodiments, without invoking the statistical treatment of missing data, a mathematically cumbersome and computationally demanding task. A maximum likelihood estimator of the model parameters and the optimal t and i ² estimators for complete signal given a noisy subsampled signal are derived below, for some embodiments.

Filterbank, which superceeds discrete wavelet transform, is a convenient form of analyzing inhomogenous and nonstationary discrete signals. Local in both frequency and time, filterbank coefficients represent the concentration of energy in nearby frequency components and in nearby samples. Let ^" ' ^" ^ be a one-dimensional signal, and an integer index. Then we define subsampled signal ^""* ' as

(nJ + ( - 1)" jr(«)i = Equivalently,

where ^{2 v E} - ^{R '2} ' ^{v >c} is the discrete Fourier transform operator and ^ ' ^ffi / ² " its corresponding normalized frequency. An observation here is that the subsampled signal x _s (n) , for some embodiments is an arithmetic average of the signal of interest x(n) and its frequency modulated version (-1)" x(n) . When the bandwidth of the signal (i.e. the support of the signal in the Fourier domain) is sufficiently large, x(ω) and x{ω -π) are

indistinguishable in x _s (ω) , and this phenomenon is called aliasing — the classical interpretation is that the aliased portions of the signal are irrecoverable from x _s (a>) .

Let a ^β -ϋi ^'o^i . - Z - ^í R be finite impulse response filters and z E {0,1 } . Formally, v _; ^λ («) is a one-level filterbank coefficient corresponding to the signal x : 1 -r Eif

where ® denotes a convolution operator; or correspondingly,

The set, 1 ^v i ^ ⁰ ' ^: ^ ^r/ ^ ^f, is collectively referred to as the / th filterbank channel. In one example, Filterbank transform is said to be perfectly reconstructable if X ₁ = x , where

or equivalently using standard polyphase notation,

where the summation in the convolution ® _m is performed over the index m . The reconstruction step in (R3) is commonly referred to as the synthesis filterbank.

In one example, let j = 4-ϊ . Important and well-known theorems associated with (R2) and (R3) have established the following.

Theorem 1 (Vetterli) The filterbank {go,g _λ ,h _<) ,h _\ } is perfectly reconstructable or any input signal if and only if the following statements are true:

Theorem 2 (Mallat) If the filterbank {g ₀ , ^ ₁ , A ₀ , A ₁ } is perfectly reconstructable, then

and

for some a ξ i and b € 2. The above theorems are the basis for the reverse-ordered scale structure in filterbanks, in some embodiments. Also, define g _; (ή) = a ^~λ g _t (n + (2b + 1 )) and

(time-reversed, time-shifted, and scaled versions of g _t and H ₁ ), where a and b are as defined in Theorem 2. Then w ^* (n) is called a dual-fϊlterbank coefficient of v ₍ ^λ (ή) if

Straightforward brute-force arithmetics verify that if the filterbank is perfectly reconstructable, then the filterbank is perfectly reconstructable as well. That is, X ₁ , = x, where

In general, if g ₀ is a low-pass filter, Zz ₀ is a low-pass and g, and h _x are high-pass.

Thus, V _Q and w _o ^x measure local low-pass energy concentration while v, ^x and w/ measure local high-pass energy. The time-frequency resolution can be fine-tuned by nesting the one-level transform recursively.

Proveable Examples of Reverse-Ordered Scale Structure and Subsampled Signal Lemma 3 (Reverse-Order) Define modulated signal x _m = (-1)" x(ή) . If the filterbank is perfectly reconstructable, then

Proof. Assume that the filterbank is perfectly reconstructable. Modulation of x by π implies

By Theorem 2,

where we used the property λ,(fi>) = ae ^A2b+l)ω h _l (ω) . Substituting (R5) for g, yields

(«).

Corollary 4 (Modulation) The filterbank {g ₀ ,g _v h ₀ ,h} is perfectly reconstructable. Then

Proof. Substituting (R5) into Theorem 1,

where the last equality comes from plugging in ω for ω - π .

Lemma 5 (Localized Aliasing) Define subsampled signal x _s (n) as before. If the filterbank {g ₀ , S^h ₀ , Ji ₁ ] is perfectly reconstructable, then

Proof. From (Rl),

where the last equality comes from Lemma 3. Furthermore, solving for W ₁ ^" (n) in (R4),

Then,

Lemma 3 characterizes the reversal of scale ordering when the signal x(n) is modulated by π . That is, the low-frequency filterbank coefficient for the modulated signal ( V ₀ '"' (n) ) behaves like the high-frequency dual filterbank coefficient for the original signal ( w, ^λ (n) ), and vice- versa. This filterbank channel role-reversal is consistent with the Fourier interpretation of modulation by π , as the low- and high- frequency components are swapped, per modulo- 2π .

Corollary 4 offers another interpretation for the ROSS in filterbank: exchanging the low- and high-frequency channels of the synthesis filterbank results in modulation. To see this, consider reconstruction of the dual-filterbank coefficients via the synthesis filterbank (R3) with reverse-ordered channels:

Similarly, Lemma 5 is the joint time- frequency analysis counterpart to the aliasing in (Rl). Filterbank coefficients corresponding to the subsampled signal x _s (n) are arithmetic averages of low- and high-frequency coefficients corresponding to x(n) , and localized aliasing occurs when v _t ^x (ή) and w^ _t ' (n) are both supported simultaneously and hence indistinguishable in v] ^s (n) . Unlike (Rl), however, the aliasing is confined to a temporally localized region when the underlying sequence is inhomogeneous, as v, ^v (ή) and W ₁ ^" (n) are indexed by the location pointer n .

If in some embodiments, we restrict our attention to orthogonal or Smith-Barnwell type filterbanks, we have

where '*' denotes complex conjunction. Solving for g _o (ω) gives

and by Theorem 2,

In one particular example, Haar wavelets have the special property that , and its ROSS reduces to a remarkably simple form:

^V , ^A "' ( ⁿ ) ^{= v} i-i ( ⁿ ) ■ To see this,

From Lemma 3,

It follows that

Multilevel Expansion Example

According to one aspect, multilevel filterbank expansion, or wavelet packets, is a means to gain more precision in frequency at the cost of resolution in time. Modify the definition of v, ¹ (n) to be the / -level filterbank coefficient corresponding to the signal x , where i = (i _o ,i _] ,...,i,) ^τ and i _k e {0, 1 } indexes the analysis filters used in the k th level decomposition (i.e. g ₀ or g, ). More precisely, we recursively apply (R2) to x repeatedly as follows: v, ¹ (») = te,, ® _M/ {...{^ (m,) ®,^ {g, _o ®x}(2m,)}(2m ₂ )...}(2m _/ )}(2n). (R6)

Acknowledging an abuse of notation, update the definition of w^(n) also as follows:

"?(*) = &,, ® _m/ {• •• {£,, K )®,,,, {^ ₀ ®x}(2m ₁ )}(2m ₂ )...}(2m _/ )}(2n). (R7)

Note that the dual basis, {h ₀ , AJ , is used in the 0 th level decomposition only.

Then the ROSS naturally generalizes to multilevel filterbank, as outlined in the corollary to Lemmas 3 and 5 below. Corollary 6 (Multilevel ROSS) Suppose the filterbank {g ₀ , g, , Zz ₀ , Zz ₁ } is perfectly reconstructable. Let i = (i ₀ , /,,..., i,) ^τ and i _k e {0,1 } as before, and define

i'= (\ -i _o ,i _λ ,...,i,) ^τ . Then the following two statements are true:

Proof. The proof is a straightforward application of Lemmas 3 and 5. Substituting Lemma 3 into (R6),

The sketch of the proof for follows the exact scenario in the proof of Lemma 5.

Connections to Continuous Time Signals This form of time-frequency analysis reveals the fundamental structure to aliasing, in some embodiments.

According to another aspect, given a subsampled signal (or observation), suppose we are interested in estimating or making a statistical inference on the complete signal (or latent variable). Bayesian statistical estimation and inference techniques make use of the posterior probability, or the probability of a latent variable conditioned on the observation. It is proportional to the product of the prior, or prior probability distribution of the latent variable, and the likelihood function, or the probability of the observation conditioned on the latent variable.

Owing to the properties of joint time-frequency analysis that compress energy and approximately decorrelate temporal redundancies in sequential data, filterbank and wavelets are popular and convenient platforms for statistical signal modeling, applicatons of which include real -world signals in speech, audio, and images. Issues pertaining to the loss of information due to subsampling is difficult to reconcile because the effects of each lost sample permeate across scale and through multiple coefficients.

The loss of information due to subsampling, as characterized by the ROSS, can be coded into the likelihood function of the observed filterbank coefficients, in some embodiments. Consequently, the posterior distribution of the filterbank coefficients v?(ri) is readily accessible as the prior and likelihood are now both prescribed in the filterbank domain. Detailing the likelihood function as deduced from Lemma 5, and assuming a conditionally normal prior distribution (which is by now a standard practice), derive the corresponding posterior distribution and optimal t and I ² estimators for the latent variables, and an algorithm to estimate the model parameters that maximize the marginal log-likelihood of the observation in some embodiments. Some embodiments assume that the filterbank coefficients are independent, and use the fact that v?(n) and w?,(n) are independent.

Likelihood Function, Posterior Distribution, and Time-Frequency Analysis

Lemma 5 linearly combines a filterbank coefficient with its reverse-ordered dual coefficient as a result of subsampling. Thus, the likelihood of an observed filterbank coefficient simplifies to:

In one embodiment, let f = ( 1 - i ₀ ,/,,..., i, ) ^τ as before, and where understood, we hereafter drop the time index n and the superscript x from v; ^v («) , w?(n) . Then, the joint posterior distribution of v?(n) and w?, (n) is

where S(-) is a Dirac function. Suppose the observation y(n) is made in noise,

and when let {g ^" _{0 >} S ^" i » ^o » ^i } comprise an orthonormal filterbank,

Then the joint posterior distribution of and

W _y (ή) is

where and . Integration over all possible values of w?, (ή) yields

where we used the definition of convolution in the last step. Another interpretation is that we have a standard form of posterior distribution in (RlO):

where the likelihood of v;' (ή) with respect to v: ^v («) is

which could have been derived from (R8) directly by integrating out the dependencies on wf, :

As an alternative to the noise model in (R9), it is probable that noisy measurements may have been made for even-indexed samples only (i.e. 2n ):

Conceptually, y _s (ή) is equivalent to making a noisy measurement on the complete signal x(ή) first before subsampling according to the model in (Rl). Thus V ₁ ¹ ^n) obeys

Corollary 6 (and Lemma 5), where if we continue to assume for some embodiments, comprise an orthonormal filterbank, the averaging in Corollary 6 occurs between v? and w?, that are both corrupted by i.i.d. noise with distribution *

Effectively, \ and the posterior distribution in (Rl 0) and all other results presented are equally valid for y _s if we replace σ ² with σ ² /2.

According to one emdodiment, it is realized that the noise in vf ^s would no longer be independent, as noise in v? ^s and vιζ ^s are perfectly correlated (and correlated with v?, ^s by extension).

Heavy-Tailed Prior Distribution

Adopting Bayesian statistical methods for some embodiments, coefficients modeled with conditionally normal distributions have conditionally normal posterior distribution as well, the following form appears frequently:

where in the i -channel, and q. _t (n) ≠ 0 is also a random variable whose distribution is as specified by sparsity and the shape of the tail. Similarly, let

where r _t . (n) ≠ 0 is a random variable whose distribution we expect is identical to that of q _x (n) , /Lf is the variance of w? in the i -channel, and we expect /L ² = /? ² .

Working with (RlO) and the prior distribution models above, the posterior distribution of V _J is conditionally normal:

where the sums of conditionally normal variables in (R9) and Lemma 5 lead to

Integrating p(v _x \ y,q-,,r _v ) over q. _λ and r _v , we find the posterior distribution of V ₁ :

where the last step makes use of the joint posterior distribution of q. _t and ^ ₁

For some choices of p(q-,) and p(r _r ) , the integral above can be evaluated explicitly (e.g. if V _; has Laplace distribution, or if q _i is a discrete variable). In one example, when the closed form expression for the integral does not exist, the integral may be evaluated numerically via approximation techniques such as Reimann sum, numerical quadrature, and Monte Carlo methods.

Bayes Estimator for Filterbank Coefficients

Using the prior and the posterior distributions above, some examples derive estimators for the latent variables that minimize some Bayes risk functions (which may also be thought of as simultaneous interpolation and denoising). For example, the minimum mean squared error (MMSE) estimator is the posterior mean of v. derived from (RI l) and (Rl 2):

Although MMSE estimators permeate the optimization literature, it is not as robust as the minimum t error estimator when the underlying signal is inhomogeneous. The optimal estimate in the t error sense, in one embodiment, is the posterior median of V _; , or a choice of v. that solves

v _{

5)

where is the cumulative distribution function of φ(x I σ ² ) . Note that the I ² and t estimators in (R14) and (Rl 5) can be pre-computed when the model parameters and the distributions of q _x and r _v are known a priori.

Maximum Likelihood Estimation for Parameters

In some examples, the maximum likelihood estimate (MLE) of the model parameters may not have an analytic form when the integral in the marginal likelihood (Rl 3) cannot be found explicitly. In one case, there exists an application of ECME

(expectation-conditional maximization either) algorithm that estimate these parameters. The computational burden of the proposed ECME algorithm is far imporved, owing to the conciseness of the likelihood function.

Specifically, for some embodiments assume that y (or equivalently, v:'(n) ) is the only observed data and let θ, = {σ ² ,p ² } , where /L ² = σ ² is used and the identical distributions for q _κ and r _{ , and θ ₂ are a set of all unknown parameters that the distribution for q. _t needs. The object of ECME in this example is to estimate θ = {θ,,θ ₂ } by maximizing the marginal log-likelihood

In some embodiments, the direct maximization may be difficult because of the complexities associated with the integral in (Rl 3). The ECME algorithm circumvents this problem by iteratively maximizing the much easier augmented-data log-likelihood log ^(U I θ) , where U = {y, x, q) is the augmented data and q = {q _x (n) | Vi, ή) . Given θ' = {θj , θ' ₂ } , the t th iterate of the model parameters, the algorithm makes the use of the celebrated monotonicity property of log-likelihood functions:

wher e

Thus, the choice of θ, that maximizes — that is, the next iterate of θ, — increases our objective function, log p(y The advantage of one embodiment in maximizing £?( ^• ; ^■ ) instead of directly the targeted observed data log-likelihood function is that the augmented-data log-likelihood often depends on U linearly via a set of augmented-data sufficient statistics S(U) . The ECME algorithm is carried out by iterating these basic steps:

• (E-step) Compute

• (CMl-step) θ; ^+I = argmax _θI

^• (CM2-step) θ' ₂ ^+I = argmaxβ

The iteration continues until log p(y \ θ') converges. In the ECME context, computation of is referred to the ε-step (expectation step), whereas the steps to compute maximization of Q(-, ) and the log-likelihood function are called the CM-steps (conditional maximization steps). Below, discussed is an example of the CM- steps first, as the details of the sufficient statistics emerge from CMl-step.

Conditional Maximization Steps

Given the tth. iterate parameter, the explicit formula for Q(Q;Q') is in a closed- form:

Taking the derivative with respect to θ, , it is easy to verify that the maximizer of Q({Q _λ ,Q' ₂ };Q') is the weighted least-squares estimate in some embodiments:

where TV is the total number of samples in the signal and N. _t is the number of coefficients in the i th subband. Thus the sufficient statistics are:

According to one aspect, the maximization of \ogp{y | {θ5 ⁺¹ ,θ ₂ }) with respect to θ ₂ is a problem highly dependent on the choice of probability distribution considered for q. _χ . Assuming sufficient smoothness, the computation of the second CM-step solves the value of θ ₂ that satisfy f (θ ₂ 1 θj ⁺¹ ) = 0 , where f (θ ₂ 10 ₁ ) is the first derivative of with respect t similarly as the second derivative). Then the procedure can be carried out via Newton-Raphson:

where the iteration in (R 17) is carried out until θ ₂ converges. Expectation Step

In the E-step, we evaluate

where p(q _x ,r _x , | _y,θ') is a computable quantity according to (Rl 2). When the integration over q _x and r _x , does not have a closed-form, it is evaluated numerically as before. Using (R 14) and conditioned on q _x and r _x , , all co variance matrices of interest can be calculated analytically:

It should be understood that the present invention is not limited to red, green, and blue color components. Rather the present invention may comprise a CFA comprising any color and any number of colors.

Having thus described several aspects of at least one embodiment of this invention, it is to be appreciated various alterations, modifications, and improvements will readily occur to those skilled in the art. Such alterations, modifications, and

improvements are intended to be part of this disclosure, and are intended to be within the spirit and scope of the invention. Accordingly, the foregoing description and drawings are by way of example only.