Welcome to Week Seven. As I mentioned at the end of last week, we'll continue this week with the exciting topic of image and video recovery. Last week we covered deterministic restoration approaches. That is, the unknown image is treated as a deterministic signal. Given a specific observation, we are interested in obtaining the best restored image that gave rise to the observed data. Of course, we also saw that in order to restrict the set of all possible solutions, prior information about the image was incorporated into the restoration process. Such as the information that the original image is smooth. As we'll see this week, this prior knowledge is incorporated into the restoration process in a different way, by assuming that the image is a sample of a random field. This means that, it belongs to a class of images, so called example, which share several characteristics. The topic of recovery is rather mathematical, as everything's by last weeks material. This will be the case this week as well. This week we'll need knowledge about two dimensional random processes, also called random fields. Now, probability in random processes is a rather broad and challenging topic in its own right. It is typically covered in an engineering science curriculum by at least one undergraduate and one graduate level courses. Clearly it's outside the scope of this class to cover this material in any depth, if you've already heard this material then you know much more then we'll use here. However, if you had not had any such material before you can still be in good shape. By that I mean that I'll just briefly cover what we need, but more importantly, even the if the derivation details of a field are not crystal clear. You'll still have a useful framework you can apply to solving other problems, and also a specific restoration algorithm you can use right away to restore a distorted image of interest in your obligation. [BLANK_AUDIO] With the above in mind, we'll cover specifically the Wiener restoration filter, the Wiener noise smoothing filter, maximum likelihood, and maximum a posteriori estimation. The general framework as well as the deviation of specific image resolution results for certain prior models. We'll also briefly describe in words the so called hierarchical inference approach. Finally, we show the formulation of some of the recovery problems we briefly talked about at the beginning of last week. Let us proceed first with the derivation of the celebrated winner restoration field of. As you'll see, in order to define the filter we only need the other correlation function of an image. And the cross correlation function between two images all the Fourier transfer, which I refer to as the power specter. We'll define and explain such functions and also show how they are altered by LSI system. So with that, let's start with the material of week seven. In this segment of the course, we are going to look into stochastic restoration approaches. With such approaches, the original image f is not treated as a deterministic signal, but instead of a sample of the random field. So, more specifically, we are going to look into the Wiener filter and then under Bayesian formulations, we're going to derive for special cases, the maximum likelihood and maximum a posteriori estimates. And we're going to say a few things about hierarchical Bayesian approach. So, let us proceed now with the Wiener Restoration Filter. Random variables in random stochastic processes is a rather challenging topic. Typically, in a science or engineering curriculum, there is at least one required course on probability random variables, followed by at least one graduate course on random processes, and maybe a specialized course of random fields. These are two dimensional stochastic processes, random fields like the ones we're interested in here when we talk about images. Then of course there are courses which make heavy use of probability, random processes such as estimation theory and spectral estimation. We'll be covering Stochastic Restoration fields at some high level. For completeness on one hand, but also because they play an important role in the field of image and video recovery. If you go ahead and hear that course on probability and random processes. Then you know more than we will need here. I also chose to cover stochastic restoration filters to demonstrate that we will only need certain aspects of random fields, which are not terribly complicated in that most steps could be carried out based on what we have covered in the course so far. In any case, at the end of the day you'll end up with some useful restoration filters that you would use right away even if not all the mathematical details of how these filters were derived are crystal clear. So here the elemental need to derive the winner restoration figure. I'd like to explain them in plain English terms if you wish, keeping in mind the students who may not have had this material before. For the rest of you, just bear with me, we will need the notion of auto or cross correlation as well as stationary fields. So, here is the definition of autocorrelation of a random field f. As we see here, the autocorrelation function is a function of four variables, i, j, k, l. And it's equal to dating the image f, the random field f, at, which is at location i, j. Taking the same field now to location k,l. So you might say it's centered at i,j, the first one. The second is centered at j,l. This star here denotes complex conjugation for the case of the field is it, it's, it's complex. If the field is real then the conjugation has no effect the conjugate of a real number is the number itself. We then have to perform this expectation operation. So, the idea here is that we have an image that is modeled as a random field, and I observe one image. I have one image available, this is one realization of this random field. So, to perform this expectation operation, I need to have many realizations of this random field, which form a so called ensemble. It's a collection of realization, it's, it's an ensemble. So this is the expected value, the mint value you might say, with respect to this ensemble of images. So had I been able to observe multiple, again, realization of this random field then I could perform this expectation. A very useful notion when it comes to correlation is the notion of wide sense stationary. So stationery fields are easier to deal with. More convenient, and the whole idea is that with stationary fields, it's irreverent where the axes are located, in the sense that, now, all I'm interested is the distance between these shifts of, of the images. So I mean this, the, the distance between i and k in the one-dimension, and j and l in the other dimension. So, the auto-correlation in this case becomes now a function of two variables, which, is again the distance between the origins after the shift of the images, you might say, all right? So it's independent of the location of the axis. So the correlations are useful every time we create the images as random fields and are people have used various models to for for this or the correlations for example this isotropic. Exponential decay model has been used. So according to this, the auto-correlation function of a random field is equal to a constant. Times gamma, another constant with a minus absolute value of n1 plus absolute value of n2. [BLANK_AUDIO]. So clearly, the larger n1 and or n2, the smaller the value of the, of the correlation, so it's a decaying exponential, so the feather away, two pixels they are the less correlated they are. It's another way to say that, and it's isotropic because it depends on absolutely value of n1 and 2, it does not distinguish. Which direction I'm looking at in this random field, so typically when a model is used for the other correlation and then we're going to use this model to process a specific image we fit this model to the data, so try to find the C and gamma here values. So, that this particular model better again explains the data we're working with. Now, if we need to estimate the auto-correlation from the available. Data, if I do have an ensemble of images, many realizations, then in principle I could perform this expectation here, operation is shown here, but since in most cases you only have available one image. One realization, then we invoke the notion of ergodicity, which tells us that sample averages equals spatial averages. So in other words, I can find this expectation by taking this spacial average. So I choose a 2n+1 by 2n+1 window and then with this that, within this window I form the product of g and g conjugates shifted by n1 and two and I sum up and this will give me one value a specific n1 and two one value of the correlation function. Finally, one more concept to need in deriving the, with the restoration field is the notion of the power spectrum which is defined as the fluid transfer this is what the calligraphic f shows denotes of the auto correlation function. It's noted by P so the spectrum of f. The power spectrum is just again the Fourier transform as shown here. I also talked about here cross correlation. Everything carries over when, I'm not talking about the same image f, but an image f and an image g. So then the cross correlation, you know, R of g is the expected value of f. G complex conjugate, everything carries through as I explained here. So, equipped with all of this knowledge, we are ready to start talking about the Weiner Restoration Filter. The Wiener Filter is attributed to Norbert Wiener. Who developed it in the 1940s and published it in 1949. >> A discrete version of it actually was published by Kolmogorov in 1941, and because of that it's very often referred to as the Wienerâ€“Kolmogorov Filter. So, according to it as we'll see, all we need to know is the signal and noise spectral characteristics. We assume that whites stayed stationary, and therefore we know the auto-correlation and cross-correlation of the signals. It is the non-causal version of the filter, because we assume that all data the noise and blur de-module tried to restore is available. So we start with the degradation model shown here. So, [SOUND] we observe the image y, i, j is the result of convolving the original image f with the points first function of the degradation filter or system, and w is clearly the additive noise. So given y, and given h, the knowledge of the degradation system,. And the model for F and W would try to find an estimate of the original image F. And again, F is a random process a random field and we know its autocoorelation we know the autocoorelation of the noise as well. And we know the cross-correlation between f and w. So the objective is to find the restored image f we've got here, which is the argument that minimizes. That arrow here squared, and the arrow is just the difference between the original image and the estimated image. So this is the absolute value [INAUDIBLE] complex squared. We need the expectation here, because again f is realization of a random field, a two-dimensional random process. So we observe an image from this collection, or ensemble of images, but we want the estimation error to be minimized not just for the image we observed, but for all the images in this ensemble. So next time, another image from this ensemble is provided to us to be restored. We are guaranteed that we can provide the restoration that will result in the smallest possible restoration error. The additional requirement imposed by the Wiener Filter is that this restoration filter should be, is required, is desired to be a linear, especially in variant filter. So, in other words, the restored image, f-hat, will be the convolution of the impulses parts of the restoration field there, r, i, j, with the available data. So pictorially, here is the degradation restoration system, right? The original image goes through the degradation system, noise is added, y is the observed image,. We want to operate on need with restoration filter with inputs r(i, j) so that we obtain an estimate of the original image here, so that the error between f and f hat, our estimate, the absolute value of this squared in the expected sense is the smallest possible one. So, let's see what are the steps to obtain this estimate here which will represent the non-causal Wiener restoration filter. We saw in the block diagram shown in the previous slide that there are random signals going through LSI systems. Therefore, important useful to seem general quarter sum of the results that tell us how the autocorrelation of the output of such a system relates to the autocorrelation of the imput, and also what are the cross correlations between imput and output equal to. So we have shown here an LSI system with impulses points h, i, j. f is the input, y is the output, f is a random signal. It makes sense than y is also random, while h here is the mystic signal. We know from material we covered early on that that output is simply the convolution of the input with the impulse response of the system. [BLANK_AUDIO]. We assume that the input is y set stationary with auto correlation R of f f i j. So the first question is, what is R of y y equal to? If I take this expression and substitute it into the definition of the auto correlation, and keep in mind that h i j is a deterministic signal. Therefore, it goes through expectations. It's rather straightforward to show after four or five lines of computation here, but. This is how the autocorrelation of the output relates to the autocorrelation of the imput. I have to take the autocorrelation of the imput and perform the convolution with h,i,j, another convolution with h complex conjugate minus i minus j. [BLANK_AUDIO] I can take this expression to the frequency domain, we mention earlier that the Fulia transform of the autocorrelation becomes the power spectrum of the signal. And they'll use the convolution theorem, which tells us that convolution in the spacial domain becomes multiplication in the frequency domain. So, if the Fourier transform of this is H omega one, omega two, that's the frequency response of the system, then according to one of the properties of the Fourier transform, the Fourier transform of this signal will be H complex conjugate. Omega one, omega two. So multiplying in the frequency domain h with h complex conjugate I'm going to get the magnitude of h squared. So, dating this with the frequency domain gives rise to this expression. So this is one of those general and useful results that. You'll find yourselves utilizing all over the place, and tells me that the power spectrum of the output equals the power spectrum of the input multiplied with the magnitude of the frequency response of the LSI systems. I can follow similar steps and find now that the cross correlation between input and output is given by this expression. Taking this to the frequency domain, becomes this expression, and then finally can find the cross correlation between the output and input, it's a similar expression when taking the frequency domain gives rise to the cross spectrum. Cross bar spectrum between y and f. So, let's make immediate use of this result in deriving the Wiener restoration filter. So here is again the block diagram of the degradation and restoration system we're considering. The assumption is that both f and w are wide stands stationary, and therefore so is y. The solution is based on this orthogonality so-called principle, that states that the error is orthogonal to the data, or the correlation between error in data is zero. And this is the expression for the correlation we've been using and e is the error again, estimation error, and y is the data. So, if I substitute the, expression for the error into this I get this expression and I can break this expression down one more step. So we have expected value of f i j, y complex conjugate k l equals the expected value of f hat, which is. Well, we write it, f hat i j, y k l, right, but this is equal, f hat is just y i j. Convolved with the impulses parts of the restoration filter, times y complex conjugate k l. So from this, clearly, I have that the cross correlation between the input and the output of the degradation system. This term here equals. If I look at this I have R is deterministic, so it comes outside the expectation. And I'm left with the expectation between y, y complex conjugate, so this the other correlation of y, convolved with the impulse response of the restoration filter. So if I take this to the frequency domain, I have the frequency response of the restoration filter is equal to this. So this is the cross power spectral density between input and output of the first system, and this is the power spectral density of the output of the system y. So, this is really the Wiener filter, and now we want to see how can further express breakdown this spiral spectral densities that we have here. Two commonly used assumptions are shown here. The first one is that the image, original image and noise are uncorrelated. This is the definition of the color of correlation, and uncorrelated means that the expected value of the product equals the product of the expected values, as shown here. In addition, it assumes that both image and noise are zero mean. Which substituted to the equation above makes the cross correlation equal to 0. So equipped with these two assumptions,. We can show that the cross power spectral density between the original image and the observation is given by this expression. This is actually exactly the same expression we had before, but before, there was no noise present. However, due to the assumptions above, the cross terms involving signal and noise. Cross out, since again they're uncorrelated, and they're zero mean. This is the numerator of the frequency response of the restoration filter we found in the previous slide. And this is the denominator, so this is the power spectrum of the output signal. We had this term before, no noise was present. Now we have the power spectral density of the noise. No cross terms again, due to the assumptions we had before. Again, both of these expressions are a few lines of calculations utilizing the assumption zero. So, this is the numerator this is the denominator of the frequency response of the Wiener filter. And if we substitute, this is the frequency response of the celebrated Wiener Filter. H, omega one, omega two, is the frequency. These parts of the degredation system is supposed to be known, and also the spectral densities of the original image and noise are supposed to be known as well.